# mc_frontend

**Repository Path**: qturing/mc_frontend

## Basic Information

- **Project Name**: mc_frontend
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2026-01-06
- **Last Updated**: 2026-07-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# mc_frontend — 基于DFG的密码算法识别系统

## 项目简介

本项目实现了一套基于编译器中间表示（LLVM IR）的密码算法自动识别系统。通过自定义 LLVM Pass 提取算法的数据流图（Data Flow Graph, DFG），利用 VF3 子图同构算法与预计算的签名模板进行匹配，从而自动识别目标程序的密码算法类型。

## 软件架构

```
mc_frontend/
├── alg-analy/
│   ├── llvm_DFGPass/          # LLVM DFG 提取 Pass（C++/CMake）
│   │   ├── DFG/
│   │   │   ├── DFGPass.cpp        # 主 DFG 提取 Pass
│   │   │   ├── ConstantExtractor.cpp  # 常量提取辅助 Pass
│   │   │   └── LoopAnalyzer.cpp      # 循环分析辅助 Pass
│   │   ├── build/                 # 构建输出
│   │   ├── dfg_gen.sh             # DFG 生成脚本
│   │   ├── autobuild.sh           # 自动编译脚本
│   │   └── build_passes.sh        # Pass 编译脚本
│   ├── vf3lib/                # VF3 子图同构匹配库（C++）
│   ├── DFG_Signature/         # 算法签名模板
│   │   ├── grf/                   # .grf 格式签名文件
│   │   └── dot/                   # .dot 格式签名文件
│   ├── cryptography/          # 密码算法参考实现（C）
│   │   ├── aes128/            # AES-128
│   │   ├── aes192/            # AES-192
│   │   ├── aes256/            # AES-256
│   │   ├── des/               # DES / 3DES
│   │   ├── md5/               # MD5
│   │   ├── sha1/              # SHA-1
│   │   ├── sha224/            # SHA-224
│   │   ├── sha256/            # SHA-256
│   │   ├── sha384/            # SHA-384
│   │   ├── sha512/            # SHA-512
│   │   └── sm3/               # SM3
│   ├── scripts/               # Python 工具脚本
│   │   └── dot_to_grf.py      # DOT → GRF 格式转换
│   ├── match.py               # 算法识别主程序（v1）
│   └── match_v2.py            # 算法识别主程序（v2）
```

## 环境依赖

| 依赖 | 版本要求 | 用途 |
|------|----------|------|
| LLVM | 18.x / 4.0.2+ | 生成 IR 并运行 DFG 提取 Pass |
| CMake | 3.16+ | 编译 LLVM Pass 和 VF3 库 |
| GCC / Clang | 支持 C++17 | 编译 C/C++ 代码 |
| Graphviz | 任意版本 | 可视化 DFG 图 |
| Python | 3.x | 运行脚本和匹配程序 |

### 一键安装

```bash
# Ubuntu/Debian
sudo apt install llvm-18 llvm-18-dev clang-18 cmake graphviz python3

# 创建 llvm-config 软链接（如需要）
sudo ln -s /usr/bin/llvm-config-18 /usr/local/bin/llvm-config
```

## 快速开始

### 1. 编译 LLVM Pass

```bash
cd alg-analy/llvm_DFGPass
./autobuild.sh
```

编译生成以下 Pass 动态库：
- `build/DFG/libDFGPass.so` — 主 DFG 提取 Pass
- `build/DFG/libConstantExtractorPass.so` — 常量提取 Pass
- `build/DFG/libLoopAnalyzerPass.so` — 循环分析 Pass

### 2. 编译 VF3 匹配库

```bash
cd alg-analy/vf3lib
make
```

### 3. 生成算法的 DFG 图

```bash
cd alg-analy/llvm_DFGPass

# 编辑 dfg_gen.sh，将 INPUT 变量指向目标 .c 文件，然后运行：
./dfg_gen.sh
```

脚本会依次执行：
1. Clang 编译 C 代码生成 LLVM IR（`.ll`）
2. 运行 DFGPass 从 IR 提取数据流图（`.dot`）
3. 运行 ConstantExtractor 和 LoopAnalyzer 提取辅助信息（`constants.json`, `loops.json`）

### 4. 转换 DOT 为 GRF 格式

```bash
cd alg-analy
python3 scripts/dot_to_grf.py <input.dot>
# 示例
python3 scripts/dot_to_grf.py llvm_DFGPass/sha256.dot
```

### 5. 运行算法识别

```bash
cd alg-analy

# v1 — 基于 VF3 子图同构匹配
python3 match.py ./DFG_Signature/grf/ <target_alg_dir>

# v2 — 改进版匹配逻辑
python3 match_v2.py
```

## 支持的算法签名

系统预置了以下算法的 DFG 签名模板（`DFG_Signature/grf/`）：

### 已验证（match_v2.py 三层识别）

| 算法 | 结构签名 | init 签名 | fshl | 分组 | 匹配结果 | 识别准确率 |
|------|----------|-----------|------|------|----------|-----------|
| MD5 | md5_sig4.grf | — | 64 | high | 64 匹配 | 100% |
| SHA-1 | sha1_sig1.grf | — | 9 | low | 4 匹配 | 100% |
| SHA-224 | sha256_sig1.grf | sha224_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-256 | sha256_sig1.grf | sha256_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-384 | sha256_sig1.grf | sha384_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-512 | sha256_sig1.grf | sha512_init_sig.grf | 16 | mid | 4 + init | 100% |
| SM3 | sm3_sig1.grf | — | 24 | mid | 6 匹配 | 100% |

> **init 签名**：SHA-224/256 共享压缩函数，SHA-384/512 共享压缩函数。init 签名通过匹配 init 函数中 `k_0x` 格式的 IV 常量值精确区分同族算法。

### 预置签名（待验证/开发中）

| 算法 | 签名文件 | 状态 |
|------|----------|------|
| SHA-512/224 | sha512_224_sig1~3.grf | 待验证 |
| SHA-512/256 | sha512_256_sig1~3.grf | 待验证 |
| SHA-3 | sha3_sig1~3.grf | 部分支持（与 SHAKE256 无法区分） |
| SHAKE256 | shake256_sig1~3.grf | 部分支持（与 SHA3 无法区分） |
| SM4 | sm4_sig1~3.grf | 待验证 |
| AES-128/192/256 | 待生成 | 开发中 |
| DES/3DES | 待生成 | 开发中 |

## 工作原理

### DFG 提取

LLVM Pass 遍历函数的 IR 指令，构建数据流图：

- **节点**：每条 IR 指令为一个节点，标注操作码（add、xor、shl、fshl 等）
- **边**：表示指令执行顺序（前驱指令 → 后继指令）
- **特殊处理**：
  - `fshl`/`fshr` — LLVM 循环移位 intrinsic，识别为独立操作码（34/35），用于区分不同算法
  - **常量编码** — 加密常量立即数（≥ 0x100）创建为带值标签的节点（如 `k_0x6A09E667`），在 GRF 中分配专属 opcode（36-67），用于区分同族算法
  - 循环结构 — 通过 LoopAnalyzer 分析循环体中的操作模式

### 签名匹配（match_v2.py 三层架构）

**第一层 — fshl 粗筛**：统计主循环图中 fshl 节点数量，将目标算法归入 `low/mid/high/very_high` 分组。

**第二层 — 结构签名匹配**：在对应分组内使用 VF3 子图同构匹配特异性签名。例如 `sha256_sig1.grf`（5 节点 `fshl→fshl→xor→fshl→xor`）识别所有 SHA-2 变体的 sigma 函数。

**第三层 — init 签名区分**：对于结构相同但 IV 不同的同族算法（SHA-224 vs SHA-256、SHA-384 vs SHA-512），使用 init 函数中的 IV 常量签名精确区分：

```
sha256_init_sig.grf:  k_0x510E527F → store   (SHA-256 IV[4])
sha224_init_sig.grf:  k_0xFFC00B31 → store   (SHA-224 IV[4])
sha512_init_sig.grf:  k_0x6A09E667F3BCC908 → store  (SHA-512 IV[0])
sha384_init_sig.grf:  k_0xCBBB9D5DC1059ED8 → store  (SHA-384 IV[0])
```

### 识别策略

不同算法具有独特的 DFG 结构特征：

- **SHA-2 家族**: `fshl → fshl → xor → fshl → xor` sigma 函数模式（sha256_sig1），通过 init IV 常量值区分具体变体
- **SHA-1**: `fshl → add → icmp` 结构（sha1_sig1）
- **SM3**: `fshl → fshl → fshl` 三重循环移位（sm3_sig1）
- **MD5**: `fshl → add` 模式，通过数量阈值判断（md5_sig4）

## 添加新算法

1. 在 `alg-analy/cryptography/` 下创建新目录，编写算法的 C 参考实现
2. 运行 `dfg_gen.sh` 生成 `.dot` 和 `.grf` 文件
3. 将生成的 `.grf` 文件作为签名模板放入 `DFG_Signature/grf/`
4. 在 `match.py` 中添加新算法的识别逻辑

## 已知问题

- LLVM 18 生成的 DFG 中，循环移位操作为 `fshl`/`fshr` intrinsic，与早期版本的 `shl+lshr+or` 组合模式不同
- SHA-3 系列和 SHAKE256 目前共用相似的 Keccak 结构，无法通过现有签名区分
- AES/DES/SM4 等对称加密算法的 DFG 签名和识别逻辑仍在开发中
- Shell 脚本中的路径引用为硬编码，迁移到新环境时需更新

## 参与贡献

1. Fork 本仓库
2. 新建 `Feat_xxx` 分支
3. 提交代码
4. 新建 Pull Request