RESEARCH_PAPER.md 51 KB
SliceFusion-LLM: 基于调用链的代码分片融合技术研究
摘要
本研究提出了一种基于函数调用链的代码分片融合技术（SliceFusion-LLM），旨在将目标代码片段智能地拆分并嵌入到已有程序的多个函数中。该技术融合了程序分析、编译原理和大语言模型（LLM）三大领域的方法论。
具体而言，本研究首先通过词法分析和语法解析构建目标程序的控制流图（Control Flow Graph, CFG），随后基于数据流分析框架计算各基本块的支配关系（Dominance Relation），识别出程序执行的必经点（Critical Point）。在此基础上，利用大语言模型对待融合代码进行语义理解和智能拆分，生成满足依赖约束的代码片段序列。最后，将各片段精确插入到调用链函数的融合点位置，并通过全局变量或参数传递机制实现跨函数的状态共享。
系统还集成了多层验证机制，包括基于规则的语法结构验证和基于 LLM 的语义正确性审查，确保融合后代码的正确性。
实验表明，本方法能够有效地将完整代码逻辑分散到多个函数中执行，同时保证程序语义的等价性。该技术可广泛应用于代码混淆、软件水印嵌入、安全漏洞测试、软件保护等领域，具有重要的理论价值和实践意义。
关键词：代码融合；控制流图；支配分析；大语言模型；程序变换；代码验证
1. 研究背景与目标
1.1 研究动机
在软件安全与逆向工程领域，代码的结构化程度直接影响分析难度。传统的代码混淆技术主要关注单函数内部的变换，如控制流平坦化、不透明谓词插入等。然而，这些技术往往忽略了函数间调用关系所蕴含的混淆潜力。
本研究的核心洞察在于：利用已有程序的函数调用链作为"载体"，将敏感代码分散嵌入，可以显著提高代码的隐蔽性。这一思路的优势体现在：
- 利用已有代码结构：无需构造新的控制流，直接复用现有函数
- 语义级分散：代码片段在语义层面分离，而非仅仅语法层面
- 分析抗性：单独分析任一函数均无法还原完整逻辑
1.2 问题形式化定义
设目标程序 $\mathcal{P}$ 包含函数集合 $\mathcal{F}_{all}$，其中存在一条深度为 $n$ 的调用链：
$$ \mathcal{F} = {f_1, f_2, \ldots, fn} \subseteq \mathcal{F}{all} $$
调用关系满足：
$$ \forall i \in [1, n-1]: fi \xrightarrow{\text{call}} f{i+1} $$
给定待融合的目标代码片段 $C_{target}$，本研究的目标是找到一个拆分函数 $\phi$ 和融合函数 $\psi$，使得：
$$ \phi: C_{target} \rightarrow {c_1, c_2, \ldots, c_n} $$
$$ \psi: (\mathcal{F}, {c_1, \ldots, c_n}) \rightarrow \mathcal{F}' = {f_1', f_2', \ldots, f_n'} $$
其中融合后的函数集合 $\mathcal{F}'$ 需满足以下语义等价性约束：
$$ \boxed{\text{Exec}(f_1') \equiv \text{Exec}(f1) \circ \text{Exec}(C{target})} $$
即执行 $f_1'$ 的效果等价于先执行原始 $f1$ 再执行目标代码 $C{target}$。
更精确地，设 $\sigma$ 为程序状态，$\llbracket \cdot \rrbracket$ 为语义函数，则：
$$ \llbracket f_1' \rrbracket(\sigma0) = \llbracket C{target} \rrbracket(\llbracket f_1 \rrbracket(\sigma_0)) $$
1.3 约束条件
代码拆分需满足以下约束：
约束 1（完整性约束）：所有片段的并集覆盖原始代码的全部语句：
$$ \bigcup_{i=1}^{n} \text{Stmts}(ci) \supseteq \text{Stmts}(C{target}) $$
约束 2（依赖约束）：若语句 $s_j$ 数据依赖于语句 $s_i$（记作 $s_i \xrightarrow{dep} s_j$），且 $s_i \in c_k$，$s_j \in c_l$，则：
$$ s_i \xrightarrow{dep} s_j \Rightarrow k \leq l $$
约束 3（可达性约束）：对于任意片段 $c_i$，其插入位置 $p_i \in fi$ 必须在调用 $f{i+1}$ 之前执行：
$$ \text{Dominates}(pi, \text{CallSite}(f{i+1})) $$
1.4 研究目标
本研究的具体目标包括：
- 设计高效的 CFG 构建算法：支持 C/C++ 代码的控制流分析
- 实现精确的支配节点计算：基于迭代数据流分析框架
- 开发智能代码拆分方法：利用 LLM 进行语义感知的代码分片
- 构建完整的融合系统：支持多种状态传递策略
- 验证方法的有效性：通过实验评估融合效果
2. 理论基础
2.1 控制流图（Control Flow Graph, CFG）
2.1.1 定义与性质
定义 2.1（控制流图）：程序 $P$ 的控制流图是一个四元组：
$$ G{CFG} = (V, E, v{entry}, V_{exit}) $$
其中：
- $V = {v_1, v_2, \ldots, v_m}$ 为基本块（Basic Block）的有限集合
- $E \subseteq V \times V$ 为控制流边的集合
- $v_{entry} \in V$ 为唯一的入口基本块
- $V_{exit} \subseteq V$ 为出口基本块的集合
定义 2.2（基本块）：基本块是满足以下条件的最大指令序列 $B = \langle i_1, i_2, \ldots, i_k \rangle$：
- 单入口：只有 $i_1$ 可以从外部跳转进入
- 单出口：只有 $i_k$ 可以跳转到外部
- 顺序执行：若 $ij$ 执行，则 $i{j+1}, \ldots, i_k$ 必然顺序执行
形式化表示：
$$ \text{BasicBlock}(B) \Leftrightarrow \begin{cases} \text{Entry}(B) = {i_1} \ \text{Exit}(B) = {i_k} \ \forall j \in [1, k-1]: \text{Succ}(ij) = {i{j+1}} \end{cases} $$
2.1.2 基本块识别算法
基本块的首指令（Leader）识别规则：
$$ \text{Leader}(i) = \begin{cases} \text{True} & \text{if } i \text{ 是程序的第一条指令} \ \text{True} & \text{if } i \text{ 是某条跳转指令的目标} \ \text{True} & \text{if } i \text{ 紧跟在某条跳转指令之后} \ \text{False} & \text{otherwise} \end{cases} $$
算法 2.1：基本块划分算法
输入: 指令序列 I = [i_1, i_2, ..., i_n]
输出: 基本块集合 B
1: Leaders ← {i_1} // 第一条指令是 leader
2: for each instruction i_j in I do
3: if i_j is a branch instruction then
4: Leaders ← Leaders ∪ {target(i_j)}
5: if j < n then
6: Leaders ← Leaders ∪ {i_{j+1}}
7: B ← ∅
8: for each leader l in sorted(Leaders) do
9: b ← new BasicBlock starting at l
10: extend b until next leader or end
11: B ← B ∪ {b}
12: return B
2.1.3 边的构建
控制流边 $(v_i, v_j) \in E$ 当且仅当：
$$ (v_i, v_j) \in E \Leftrightarrow \begin{cases} \text{last}(v_i) \text{ 是无条件跳转到 } \text{first}(v_j) \ \lor\ \text{last}(v_i) \text{ 是条件跳转，} v_j \text{ 是可能目标} \ \lor\ \text{last}(v_i) \text{ 不是跳转，} v_j \text{ 是顺序后继} \end{cases} $$
2.1.4 CFG 的性质
性质 2.1（连通性）：从 $v_{entry}$ 可达所有 $v \in V$：
$$ \forall v \in V: v_{entry} \leadsto v $$
性质 2.2（规范性）：任意 $v{exit} \in V{exit}$ 的后继集合为空：
$$ \forall v \in V_{exit}: \text{Succ}(v) = \emptyset $$
2.2 支配关系（Dominance Relation）
2.2.1 基本定义
定义 2.3（支配）：在 CFG $G = (V, E, v{entry}, V{exit})$ 中，节点 $d$ 支配 节点 $n$（记作 $d\ \text{dom}\ n$），当且仅当从 $v_{entry}$ 到 $n$ 的每条路径都经过 $d$：
$$ d\ \text{dom}\ n \Leftrightarrow \forall \text{ path } \pi: v_{entry} \leadsto n,\ d \in \pi $$
等价的集合论定义：
$$ d\ \text{dom}\ n \Leftrightarrow d \in \text{Dom}(n) $$
其中 $\text{Dom}(n)$ 是节点 $n$ 的支配者集合。
定义 2.4（严格支配）：$d$ 严格支配 $n$（记作 $d\ \text{sdom}\ n$）：
$$ d\ \text{sdom}\ n \Leftrightarrow d\ \text{dom}\ n \land d \neq n $$
定义 2.5（直接支配者）：节点 $n \neq v_{entry}$ 的直接支配者（immediate dominator）$\text{idom}(n)$ 是 $n$ 的严格支配者中最接近 $n$ 的节点：
$$ \text{idom}(n) = d \Leftrightarrow d\ \text{sdom}\ n \land \forall d': d'\ \text{sdom}\ n \Rightarrow d'\ \text{dom}\ d $$
定理 2.1：除入口节点外，每个节点有且仅有一个直接支配者。
2.2.2 支配集合的计算
支配关系可通过数据流分析的迭代算法计算。数据流方程为：
$$ \text{Dom}(n) = \begin{cases} {v{entry}} & \text{if } n = v{entry} \ {n} \cup \left( \displaystyle\bigcap_{p \in \text{Pred}(n)} \text{Dom}(p) \right) & \text{otherwise} \end{cases} $$
算法 2.2：支配集合迭代计算
输入: CFG G = (V, E, v_entry, V_exit)
输出: 每个节点的支配集合 Dom
1: Dom(v_entry) ← {v_entry}
2: for each v ∈ V \ {v_entry} do
3: Dom(v) ← V // 初始化为全集
4: repeat
5: changed ← false
6: for each v ∈ V \ {v_entry} do
7: new_dom ← {v} ∪ (⋂_{p ∈ Pred(v)} Dom(p))
8: if new_dom ≠ Dom(v) then
9: Dom(v) ← new_dom
10: changed ← true
11: until not changed
12: return Dom
复杂度分析：设 $|V| = n$，$|E| = m$，则：
- 空间复杂度：$O(n^2)$（存储所有支配集合）
- 时间复杂度：$O(n \cdot m)$（最坏情况下的迭代次数）
2.2.3 支配树（Dominator Tree）
定义 2.6（支配树）：CFG 的支配树 $T{dom} = (V, E{dom})$ 是一棵以 $v_{entry}$ 为根的树，其中：
$$ (d, n) \in E_{dom} \Leftrightarrow d = \text{idom}(n) $$
支配树的性质：
$$ d\ \text{dom}\ n \Leftrightarrow d \text{ 是 } T_{dom} \text{ 中 } n \text{ 的祖先} $$
2.3 必经点（Critical Point）
2.3.1 定义
定义 2.7（必经点）：在 CFG $G$ 中，节点 $v$ 是必经点，当且仅当移除 $v$ 后，从 $v_{entry}$ 无法到达任何出口节点：
$$ v \in \mathcal{C}(G) \Leftrightarrow \forall v{exit} \in V{exit}: v{entry} \not\leadsto{G \setminus {v}} v_{exit} $$
其中 $G \setminus {v}$ 表示从 $G$ 中移除节点 $v$ 及其关联边后得到的子图。
等价定义：
$$ v \in \mathcal{C}(G) \Leftrightarrow v\ \text{dom}\ v{exit},\ \forall v{exit} \in V_{exit} $$
2.3.2 必经点的判定
算法 2.3：必经点判定
输入: CFG G, 待检查节点 v
输出: v 是否为必经点
1: if v = v_entry then
2: return True
3: G' ← G \ {v} // 移除节点 v
4: for each v_exit ∈ V_exit do
5: if Reachable(G', v_entry, v_exit) then
6: return False
7: return True
定理 2.2：必经点集合 $\mathcal{C}(G)$ 等于所有出口节点支配集合的交集：
$$ \mathcal{C}(G) = \bigcap{v{exit} \in V{exit}} \text{Dom}(v{exit}) $$
2.3.3 必经点的性质
性质 2.3（链式结构）：必经点集合在支配树上形成一条从根到某节点的链：
$$ \forall c_1, c_2 \in \mathcal{C}(G): c_1\ \text{dom}\ c_2 \lor c_2\ \text{dom}\ c_1 $$
性质 2.4（必经性传递）：若 $c_1\ \text{dom}\ c_2$ 且 $c_2 \in \mathcal{C}(G)$，则 $c_1 \in \mathcal{C}(G)$。
2.4 融合点（Fusion Point）
2.4.1 定义与条件
定义 2.8（融合点）：适合代码插入的位置，需满足以下条件：
$$ v \in \mathcal{P}{fusion}(G) \Leftrightarrow v \in \mathcal{C}(G) \land \Phi{struct}(v) \land \Phi_{flow}(v) $$
其中：
结构条件 $\Phi_{struct}(v)$：
$$ \Phi_{struct}(v) \Leftrightarrow |\text{Pred}(v)| \leq 1 \land |\text{Succ}(v)| \leq 1 $$
控制流条件 $\Phi_{flow}(v)$：前驱和后继的跳转必须是无条件跳转：
$$ \Phi_{flow}(v) \Leftrightarrow \neg\text{IsConditionalBranch}(\text{Pred}(v) \to v) \land \neg\text{IsConditionalBranch}(v \to \text{Succ}(v)) $$
2.4.2 融合点的优先级
当存在多个融合点时，按以下优先级选择：
$$ \text{Priority}(v) = \alpha \cdot \text{Depth}(v) + \beta \cdot \text{Centrality}(v) + \gamma \cdot \text{Stability}(v) $$
其中：
- $\text{Depth}(v)$：在支配树中的深度
- $\text{Centrality}(v)$：在 CFG 中的中心性度量
- $\text{Stability}(v)$：基本块的大小（越大越稳定）
- $\alpha, \beta, \gamma$：权重系数
3. 方法设计
3.1 系统架构
SliceFusion-LLM 系统采用模块化设计，由六个核心层次构成：
┌─────────────────────────────────────────────────────────────────────────────┐
│ SliceFusion-LLM System │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────┐ │
│ │ Input Layer │ │
│ │ ┌───────────┐ │ │
│ │ │ 源代码数据 │ │ │
│ │ │ (JSONL) │ │ │
│ │ └─────┬─────┘ │ │
│ └────────┼────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Data Processing Layer │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ │
│ │ │ 调用关系提取 │───▶│ 调用链分组 │───▶│ 深度筛选 │ │ │
│ │ │ extract_call_ │ │ 按连通分量分组 │ │ filter_by_ │ │ │
│ │ │ relations.py │ │ │ │ call_depth.py │ │ │
│ │ └─────────────────┘ └─────────────────┘ └───────┬─────────┘ │ │
│ └────────────────────────────────────────────────────────┼────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Analysis Layer │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ │
│ │ │ CFG 构建 │───▶│ 支配分析 │───▶│ 融合点识别 │ │ │
│ │ │ cfg_analyzer.py │ │ dominator_ │ │ │ │ │
│ │ │ │ │ analyzer.py │ │ │ │ │
│ │ └─────────────────┘ └─────────────────┘ └───────┬─────────┘ │ │
│ └────────────────────────────────────────────────────────┼────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Splitting Layer │ │
│ │ ┌─────────────────────────────────────────────────────────────┐ │ │
│ │ │ LLM Code Splitter │ │ │
│ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │
│ │ │ │ Prompt 构建 │───▶│ LLM 调用 │───▶│ 结果解析 │ │ │ │
│ │ │ │ │ │ (Qwen API) │ │ │ │ │ │
│ │ │ └─────────────┘ └─────────────┘ └──────┬──────┘ │ │ │
│ │ └──────────────────────────────────────────────┼──────────────┘ │ │
│ └─────────────────────────────────────────────────┼───────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Fusion Layer │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ │
│ │ │ 状态生成 │───▶│ 代码插入 │───▶│ 代码生成 │ │ │
│ │ │ (Global/Param) │ │ code_fusion.py │ │ main.py │ │ │
│ │ └─────────────────┘ └─────────────────┘ └───────┬─────────┘ │ │
│ └────────────────────────────────────────────────────────┼────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Verification Layer │ │
│ │ ┌─────────────────────────────────────────────────────────────┐ │ │
│ │ │ Verification Agent │ │ │
│ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │
│ │ │ │ 语法验证器 │───▶│ 语义审查器 │───▶│ 综合报告 │ │ │ │
│ │ │ │ (规则检查) │ │ (LLM 审查) │ │ 生成 │ │ │ │
│ │ │ └─────────────┘ └─────────────┘ └──────┬──────┘ │ │ │
│ │ └──────────────────────────────────────────────┼──────────────┘ │ │
│ └─────────────────────────────────────────────────┼───────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Output Layer │ │
│ │ ┌───────────┐ │ │
│ │ │ 融合代码 │ │ │
│ │ │ (.c 文件) │ │ │
│ │ └───────────┘ │ │
│ └─────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
3.2 调用链分析
3.2.1 函数调用关系提取
从代码中提取函数调用关系，构建调用图 $G{call} = (V{func}, E_{call})$：
$$ (f_i, fj) \in E{call} \Leftrightarrow f_i \text{ 的函数体中存在对 } f_j \text{ 的调用} $$
调用关系提取采用正则表达式匹配：
$$ \text{Callees}(f) = {g \mid \exists \text{ pattern } ``g\text{(}'' \in \text{Body}(f)} $$
3.2.2 调用链深度计算
定义调用链深度函数 $d: V{func} \times V{func} \to \mathbb{N}$：
$$ d(f_i, f_j) = \begin{cases} 0 & \text{if } f_i = fj \ 1 + \min{f_k \in \text{Callees}(f_i)} d(f_k, f_j) & \text{if } f_i \neq f_j \land f_i \leadsto f_j \ \infty & \text{otherwise} \end{cases} $$
最长调用链深度：
$$ D{max}(G{call}) = \max_{f_i, fj \in V{func}} d(f_i, f_j) $$
3.2.3 调用链分组
使用 Union-Find 算法将有调用关系的函数分组。设 $\sim$ 为传递闭包关系：
$$ f_i \sim f_j \Leftrightarrow f_i \leadsto f_j \lor f_j \leadsto f_i $$
则分组 $\mathcal{G}$ 为等价类：
$$ \mathcal{G} = V{func} / \sim = {[f]\sim \mid f \in V_{func}} $$
3.3 代码拆分算法
3.3.1 问题建模
代码拆分可建模为约束满足问题（CSP）：
$$ \text{CSP}_{split} = (X, D, C) $$
其中：
- 变量 $X = {x_1, x_2, \ldots, x_n}$：每个变量表示一个代码片段
- 域 $D$：每个变量的取值范围为原始代码的语句子集
- 约束 $C$：包括完整性、依赖性、平衡性约束
约束 C1（完整性）：
$$ \bigcup_{i=1}^{n} xi = \text{Stmts}(C{target}) $$
约束 C2（不重叠）：
$$ \forall i \neq j: x_i \cap x_j = \emptyset $$
约束 C3（依赖保持）：
$$ \forall s_a \xrightarrow{dep} s_b: (\text{Index}(s_a) \leq \text{Index}(s_b)) $$
其中 $\text{Index}(s)$ 返回语句 $s$ 所属片段的索引。
3.3.2 LLM 辅助拆分
利用大语言模型进行语义感知的代码拆分。设 LLM 为函数 $\mathcal{L}$：
$$ \mathcal{L}: (\text{Prompt}, \text{Context}) \rightarrow \text{Response} $$
Prompt 模板构建：
$$ \text{Prompt} = \text{Template}(C_{target}, n, \mathcal{F}, M, \text{Examples}) $$
其中：
- $C_{target}$：目标代码
- $n$：拆分片段数
- $\mathcal{F}$：调用链函数名列表
- $M \in {\text{global}, \text{parameter}}$：状态传递方法
- $\text{Examples}$：Few-shot 示例
LLM 输出解析：
$$ \text{Parse}: \text{JSON} \rightarrow ({ci}{i=1}^n, \mathcal{S}, \text{Decl}) $$
其中 $\mathcal{S}$ 为共享状态集合，$\text{Decl}$ 为声明代码。
3.3.3 Fallback 机制
当 LLM 调用失败时，采用启发式拆分：
算法 3.1：启发式代码拆分
输入: 代码 C, 片段数 n
输出: 代码片段列表 {c_1, ..., c_n}
1: stmts ← ParseStatements(C)
2: k ← |stmts|
3: if k < n then
4: // 补充空片段
5: for i = 1 to k do
6: c_i ← stmts[i]
7: for i = k+1 to n do
8: c_i ← "// empty"
9: else
10: // 均分
11: chunk_size ← ⌊k / n⌋
12: for i = 1 to n do
13: start ← (i-1) × chunk_size + 1
14: end ← min(i × chunk_size, k) if i < n else k
15: c_i ← Join(stmts[start:end])
16: return {c_1, ..., c_n}
3.4 状态传递方法
3.4.1 全局变量法
定义 3.1（全局状态空间）：设共享变量集合为 $\mathcal{S} = {s_1, s_2, \ldots, s_k}$，全局状态空间为：
$$ \mathcal{G} = {g_i = \text{global}(s_i) \mid s_i \in \mathcal{S}} $$
变量重命名映射 $\rho_{global}: \mathcal{S} \to \mathcal{G}$：
$$ \rho_{global}(s_i) = g_s_i \quad (\text{添加前缀 } g_) $$
全局声明生成：
$$ \text{Decl}{global} = \bigcup{s_i \in \mathcal{S}} \text{``static } T_i\ g_s_i\text{;''} $$
其中 $T_i$ 为 $s_i$ 的类型。
代码变换：
$$ c_i' = c_i[s_j \mapsto g_s_j,\ \forall s_j \in \mathcal{S}] $$
形式化语义：
设 $\sigma_G$ 为全局状态，$\sigma_L$ 为局部状态，则：
$$ \llbracket c_i' \rrbracket(\sigma_G, \sigma_L) = \llbracket c_i \rrbracket(\sigma_G \cup \sigma_L) $$
3.4.2 参数传递法
定义 3.2（状态结构体）：定义结构体类型 $\Sigma$：
$$ \Sigma = \text{struct FusionState} {T_1\ s_1;\ T_2\ s_2;\ \ldots;\ T_k\ s_k;} $$
函数签名变换：
$$ f_i: (A_1, \ldots, A_m) \to R \quad \Longrightarrow \quad f_i': (A_1, \ldots, A_m, \Sigma^*\ state) \to R $$
变量访问变换：
$$ \rho_{param}(s_j) = state \to s_j $$
代码变换：
$$ c_i' = c_i[s_j \mapsto state \to s_j,\ \forall s_j \in \mathcal{S}] $$
函数调用变换：
$$ \text{Call}(f{i+1}, args) \Longrightarrow \text{Call}(f{i+1}', args, state) $$
初始化代码：
FusionState state_data;
memset(&state_data, 0, sizeof(state_data));
FusionState* state = &state_data;
3.4.3 两种方法的对比
| 特性 | 全局变量法 | 参数传递法 |
|---|---|---|
| 实现复杂度 | $O(k)$ | $O(k + n)$ |
| 函数签名修改 | 否 | 是 |
| 线程安全 | ❌ | ✅ |
| 可重入性 | ❌ | ✅ |
| 副作用 | 有 | 无 |
| 适用场景 | 单线程 | 多线程/库函数 |
形式化比较：
$$ \text{Overhead}{global} = O(1) \quad \text{vs} \quad \text{Overhead}{param} = O(n \cdot \text{sizeof}(\Sigma^*)) $$
3.5 融合算法
3.5.1 完整算法
算法 3.2：SliceFusion-LLM 主算法
输入:
- 目标代码 C_target
- 调用链函数集 F = {f_1, ..., f_n}
- 传递方法 M ∈ {global, parameter}
- 验证选项 V ∈ {full, syntax_only, skip}
输出: 融合后的函数集 F' = {f_1', ..., f_n'} 及验证报告 R
Phase 1: 分析阶段
1: for i = 1 to n do
2: G_i ← BuildCFG(f_i)
3: Dom_i ← ComputeDominators(G_i)
4: C_i ← FindCriticalPoints(G_i, Dom_i)
5: P_i ← FilterFusionPoints(C_i)
6: end for
Phase 2: 拆分阶段
7: (slices, S, decl) ← LLM_Split(C_target, n, F, M)
8: if slices = ∅ then
9: slices ← FallbackSplit(C_target, n, M)
10: end if
Phase 3: 状态生成阶段
11: if M = global then
12: state_code ← GenerateGlobalDeclarations(S)
13: else
14: state_code ← GenerateStructDefinition(S)
15: end if
Phase 4: 融合阶段
16: for i = 1 to n do
17: p_i ← SelectBestFusionPoint(P_i)
18: c_i ← slices[i]
19: if M = parameter then
20: c_i ← TransformToParameterAccess(c_i, S)
21: end if
22: f_i' ← InsertCodeAtPoint(f_i, p_i, c_i)
23: end for
Phase 5: 验证阶段
24: if V ≠ skip then
25: R ← ∅
26: for i = 1 to n do
27: r_syntax ← SyntaxValidator.validate(f_i')
28: if V = full then
29: r_semantic ← SemanticReviewer.review(f_i', c_i)
30: end if
31: R ← R ∪ {VerificationAgent.combine(r_syntax, r_semantic)}
32: end for
33: end if
Phase 6: 输出阶段
34: output ← CombineCode(state_code, F')
35: return (output, R)
3.5.2 复杂度分析
设 $n$ 为调用链长度，$m$ 为平均函数大小（基本块数），$k$ 为共享变量数：
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| CFG 构建 | $O(n \cdot m)$ | $O(n \cdot m)$ |
| 支配分析 | $O(n \cdot m^2)$ | $O(n \cdot m^2)$ |
| LLM 拆分 | $O(T_{LLM})$ | $O( |
| 状态生成 | $O(k)$ | $O(k)$ |
| 代码融合 | $O(n \cdot m)$ | $O(n \cdot m)$ |
| 语法验证 | $O(n \cdot m)$ | $O(n)$ |
| 语义审查 | $O(n \cdot T_{LLM})$ | $O(n \cdot m)$ |
| 总计 | $O(n \cdot m^2 + n \cdot T_{LLM})$ | $O(n \cdot m^2)$ |
其中 $T_{LLM}$ 为 LLM API 调用延迟。
3.5.3 正确性证明
定理 3.1（语义等价性）：若算法 3.2 成功执行，则融合后的程序与原程序加目标代码的语义等价。
证明：
设原始程序状态为 $\sigma_0$，需证明：
$$ \llbracket f_1' \rrbracket(\sigma0) = \llbracket C{target}; f_1 \rrbracket(\sigma_0) $$
由于代码拆分满足完整性约束：
$$ \bigcup_{i=1}^{n} ci \equiv C{target} $$
且每个 $c_i$ 插入在 $fi$ 调用 $f{i+1}$ 之前（融合点性质保证），因此执行 $f_1'$ 时：
- 执行 $c_1$
- 调用 $f_2'$，执行 $c_2$
- ...
- 调用 $f_n'$，执行 $c_n$
由依赖约束，这等价于顺序执行 $c_1; c_2; \ldots; cn$，即 $C{target}$。
状态传递的正确性由 $\rho{global}$ 或 $\rho{param}$ 的双射性质保证。 $\square$
4. 实现细节
4.1 项目结构
SliceFusion-LLM/
├── README.md # 项目文档
│
├── data/ # 数据集目录
│ ├── primevul_valid.jsonl # 验证集
│ ├── primevul_valid_paired.jsonl
│ ├── primevul_test.jsonl # 测试集
│ └── primevul_test_paired.jsonl
│
├── utils/ # 工具模块
│ └── data_process/ # 数据处理工具
│ ├── extract_call_relations.py # 调用关系提取
│ └── filter_by_call_depth.py # 调用深度筛选
│
├── src/ # 核心源代码
│ ├── __init__.py # 包初始化
│ ├── requirements.txt # 依赖列表
│ │
│ │ # 分析模块
│ ├── cfg_analyzer.py # CFG 分析器
│ ├── dominator_analyzer.py # 支配节点分析器
│ │
│ │ # 拆分与融合模块
│ ├── llm_splitter.py # LLM 代码拆分器
│ ├── code_fusion.py # 代码融合引擎
│ │
│ │ # 验证模块
│ ├── syntax_validator.py # 语法结构验证器
│ ├── semantic_reviewer.py # LLM 语义审查器
│ ├── verification_agent.py # 验证代理（整合验证）
│ │
│ └── main.py # 主程序入口
│
├── output/ # 输出目录
│ ├── fused_code/ # 融合后的代码文件
│ │ ├── all_fused_code.c # 汇总文件
│ │ └── fused_group_*.c # 各组融合代码
│ ├── primevul_valid_grouped.json
│ ├── primevul_valid_grouped_depth_*.json
│ ├── fusion_results.json
│ └── test_verification.json # 验证测试结果
│
└── .gitignore
4.2 核心模块详解
4.2.1 CFG 分析器 (cfg_analyzer.py)
主要类：
@dataclass
class BasicBlock:
id: int # 基本块 ID
name: str # 基本块名称
statements: List[str] # 语句列表
start_line: int # 起始行号
end_line: int # 结束行号
is_entry: bool # 是否为入口块
is_exit: bool # 是否为出口块
@dataclass
class ControlFlowGraph:
function_name: str # 函数名
blocks: Dict[int, BasicBlock] # 基本块字典
edges: List[Tuple[int, int]] # 边列表
entry_block_id: Optional[int] # 入口块 ID
exit_block_ids: List[int] # 出口块 ID 列表
关键方法：
| 方法 | 功能 | 复杂度 |
|---|---|---|
_remove_comments() |
移除代码注释 | $O(n)$ |
_extract_function_body() |
提取函数体 | $O(n)$ |
_tokenize_statements() |
语句分词 | $O(n)$ |
_is_control_statement() |
判断控制语句 | $O(1)$ |
_build_basic_blocks() |
构建基本块 | $O(n)$ |
_build_edges() |
构建控制流边 | $O(m)$ |
4.2.2 支配分析器 (dominator_analyzer.py)
数据流方程实现：
def compute_dominators(self) -> Dict[int, Set[int]]:
# 初始化
dominators = {node: all_nodes.copy() for node in all_nodes}
dominators[entry] = {entry}
# 迭代求解
changed = True
while changed:
changed = False
for node in all_nodes:
if node == entry:
continue
# Dom(n) = {n} ∪ (∩ Dom(p) for p in pred(n))
new_dom = all_nodes.copy()
for pred in self.cfg.get_predecessors(node):
new_dom &= dominators[pred]
new_dom.add(node)
if new_dom != dominators[node]:
dominators[node] = new_dom
changed = True
return dominators
4.2.3 LLM 拆分器 (llm_splitter.py)
API 配置：
client = OpenAI(
api_key=os.getenv("DASHSCOPE_API_KEY"),
base_url="https://dashscope.aliyuncs.com/compatible-mode/v1"
)
model = "qwen-plus" # 或 qwen-turbo, qwen-max
Prompt 模板关键部分：
【重要】由于每个片段在不同的函数中执行，局部变量无法直接传递！
你必须：
1. 将需要跨函数共享的变量声明为全局变量/结构体成员
2. 第一个片段负责初始化
3. 后续片段使用共享状态
4. 最后一个片段执行最终操作
4.2.4 代码融合引擎 (code_fusion.py)
融合计划数据结构：
@dataclass
class FusionPlan:
target_code: str # 目标代码
call_chain: CallChain # 调用链
slice_result: SliceResult # 拆分结果
insertion_points: List[Tuple[str, int, str]] # 插入点列表
代码插入策略：
$$ \text{InsertPosition}(f_i, p_i) = \begin{cases} \text{AfterDeclarations} & \text{if } pi = v{entry} \ \text{BeforeStatement}(p_i) & \text{otherwise} \end{cases} $$
4.2.5 语法验证器 (syntax_validator.py)
主要功能：
- 括号匹配检查（花括号、圆括号、方括号）
- 字符串/字符引号匹配
- 语句完整性检查（分号验证）
- 函数结构完整性验证
核心类：
@dataclass
class SyntaxError:
level: ErrorLevel # error/warning/info
message: str
line: int = 0
column: int = 0
context: str = ""
@dataclass
class ValidationResult:
valid: bool
errors: List[SyntaxError]
warnings: List[SyntaxError]
验证流程：
- 预处理：移除代码注释
- 括号匹配检查
- 引号匹配检查
- 语句完整性检查
- 函数结构验证
4.2.6 语义审查器 (semantic_reviewer.py)
主要功能： 使用 LLM 进行深度语义审查，检查：
- 插入位置是否合理
- 变量使用是否正确
- 数据流是否正确
- 是否破坏原函数逻辑
核心类：
class IssueLevel(Enum):
CRITICAL = "critical" # 严重问题
MAJOR = "major" # 主要问题
MINOR = "minor" # 次要问题
SUGGESTION = "suggestion" # 改进建议
@dataclass
class ReviewResult:
valid: bool
confidence: float # 置信度 0.0-1.0
issues: List[SemanticIssue]
suggestions: List[str]
4.2.7 验证代理 (verification_agent.py)
主要功能： 整合语法验证和语义审查，提供统一的验证接口。
验证状态：
class VerificationStatus(Enum):
PASSED = "passed" # 完全通过
PASSED_WITH_WARNINGS = "passed_with_warnings" # 通过但有警告
FAILED = "failed" # 验证失败
SKIPPED = "skipped" # 跳过验证
验证流程：
融合代码 ──▶ 语法验证器 ──▶ 语义审查器 ──▶ 综合报告
│ │ │
▼ ▼ ▼
括号匹配 插入合理性 验证状态
引号匹配 变量正确性 错误列表
语句完整 数据流分析 建议列表
4.3 环境配置
4.3.1 依赖安装
# 创建虚拟环境
conda create -n slicefusion python=3.10
conda activate slicefusion
# 安装依赖
pip install -r src/requirements.txt
依赖列表 (src/requirements.txt)：
openai>=1.0.0
tree-sitter>=0.20.0
tree-sitter-c>=0.20.0
tree-sitter-cpp>=0.20.0
networkx>=3.0
graphviz>=0.20
4.3.2 API 配置
# 设置阿里云 DashScope API Key
export DASHSCOPE_API_KEY="your-api-key-here"
4.4 使用方法
4.4.1 数据预处理
# Step 1: 提取调用关系
python utils/data_process/extract_call_relations.py \
--input data/primevul_valid.jsonl \
--output output/primevul_valid_grouped.json
# Step 2: 按调用深度筛选
python utils/data_process/filter_by_call_depth.py \
--input output/primevul_valid_grouped.json \
--depth 4
4.4.2 代码融合
# 使用全局变量方法
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--output output/fusion_results.json \
--target-code "int secret = 42; int key = secret ^ 0xABCD; printf(\"key=%d\", key);" \
--method global \
--max-groups 5
# 使用参数传递方法
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--output output/fusion_results.json \
--target-file my_code.c \
--method parameter \
--max-groups 10
4.4.3 验证模式
# 完整验证（语法 + 语义审查）
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--output output/fusion_results.json \
--target-code "..." \
--verify full
# 仅语法验证（快速模式，无需 LLM）
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--output output/fusion_results.json \
--target-code "..." \
--verify syntax
# 跳过验证
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--output output/fusion_results.json \
--target-code "..." \
--verify skip
4.4.4 仅分析模式
python src/main.py \
--input output/primevul_valid_grouped_depth_4.json \
--analyze-only
5. 实验与分析
5.1 数据集描述
本研究使用 PrimeVul 数据集，该数据集包含从多个开源项目中提取的真实漏洞代码。
数据集统计：
| 统计指标 | 数值 |
|---|---|
| 总记录数 | 25,430 |
| 成功提取函数数 | 24,465 |
| 涉及项目数 | 218 |
| 总分组数 | 4,777 |
| 单独函数组（无调用关系） | 3,646 (76.3%) |
| 有调用关系的组 | 1,131 (23.7%) |
| 最大调用链深度 | 25 |
| 平均调用链深度 | 2.68 |
主要项目分布：
| 项目名称 | 函数数量 | 占比 |
|---|---|---|
| Linux Kernel | 7,120 | 28.0% |
| MySQL Server | 920 | 3.6% |
| HHVM | 911 | 3.6% |
| GPAC | 875 | 3.4% |
| TensorFlow | 656 | 2.6% |
| 其他 | 14,948 | 58.8% |
语言分布：
$$ P(\text{Language} = l) = \begin{cases} 0.815 & l = \text{C} \ 0.185 & l = \text{C++} \end{cases} $$
5.2 调用深度分布分析
设 $X$ 为调用链深度随机变量，其分布函数为：
$$ P(X = d) = \frac{|{g \in \mathcal{G} : \text{depth}(g) = d}|}{|\mathcal{G}|} $$
实测分布：
| 深度 $d$ | 组数 | 概率 $P(X=d)$ | 累积概率 $F(d)$ |
|---|---|---|---|
| 1 | 4,057 | 0.849 | 0.849 |
| 2 | 489 | 0.102 | 0.951 |
| 3 | 135 | 0.028 | 0.979 |
| 4 | 50 | 0.010 | 0.990 |
| 5 | 13 | 0.003 | 0.993 |
| 6 | 16 | 0.003 | 0.996 |
| 7+ | 17 | 0.004 | 1.000 |
分布特征：
- 众数（Mode）：$\text{Mo}(X) = 1$
- 期望（Mean）：$E[X] = \sum_d d \cdot P(X=d) \approx 1.24$
- 方差（Variance）：$\text{Var}(X) = E[X^2] - (E[X])^2 \approx 0.89$
- 偏度（Skewness）：正偏，存在长尾
分布近似服从几何分布：
$$ P(X = d) \approx p(1-p)^{d-1}, \quad p \approx 0.85 $$
5.3 融合效果评估
5.3.1 融合成功率
定义融合成功率：
$$ \text{SuccessRate} = \frac{|{g : \text{Fusion}(g) = \text{Success}}|}{|\mathcal{G}_{processed}|} $$
实验结果：
| 配置 | 处理组数 | 成功数 | 成功率 |
|---|---|---|---|
| 全局变量法 | 50 | 50 | 100% |
| 参数传递法 | 50 | 50 | 100% |
| LLM 拆分成功 | 50 | 48 | 96% |
| Fallback 拆分 | 50 | 2 | 4% |
5.3.2 代码膨胀率
定义代码膨胀率：
$$ \text{Bloat}(f_i) = \frac{|\text{LOC}(f_i')| - |\text{LOC}(f_i)|}{|\text{LOC}(f_i)|} $$
平均膨胀率：
$$ \overline{\text{Bloat}} = \frac{1}{n} \sum_{i=1}^{n} \text{Bloat}(f_i) \approx 0.15 $$
即平均增加约 15% 的代码行数。
5.3.3 融合效果示例
输入目标代码（格式化字符串漏洞）：
void vulnerable_function(char *input) {
char buffer[256];
printf(input); // 漏洞点
strncpy(buffer, input, sizeof(buffer) - 1);
buffer[sizeof(buffer) - 1] = '\0';
printf("\nInput processed: %s\n", buffer);
}
int test() {
char malicious_input[] = "Hello World! %x %x %x %x\n";
vulnerable_function(malicious_input);
return 0;
}
融合后代码分布（参数传递法，调用链深度=4）：
┌─────────────────────────────────────────────────────────────────┐
│ typedef struct { │
│ char buffer[256]; │
│ char* input; │
│ char malicious_input[256]; │
│ } FusionState; │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ crypto_get_certificate_data() [最外层] │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ /* Fused Code */ ││
│ │ strcpy(state->malicious_input, "Hello World! %x..."); ││
│ │ state->input = state->malicious_input; ││
│ └─────────────────────────────────────────────────────────────┘│
│ ... 原始代码 ... │
│ crypto_cert_fingerprint(xcert); ──────────────────────────┐ │
└─────────────────────────────────────────────────────────────│───┘
│
┌────────────────────────────────┘
▼
┌─────────────────────────────────────────────────────────────────┐
│ crypto_cert_fingerprint() [第二层] │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ /* Fused Code */ ││
│ │ printf(state->input); // 🔴 漏洞触发点 ││
│ └─────────────────────────────────────────────────────────────┘│
│ ... 原始代码 ... │
│ crypto_cert_fingerprint_by_hash(xcert, "sha256"); ────────┐ │
└─────────────────────────────────────────────────────────────│───┘
│
┌────────────────────────────────┘
▼
┌─────────────────────────────────────────────────────────────────┐
│ crypto_cert_fingerprint_by_hash() [第三层] │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ /* Fused Code */ ││
│ │ strncpy(state->buffer, state->input, 255); ││
│ │ state->buffer[255] = '\0'; ││
│ └─────────────────────────────────────────────────────────────┘│
│ ... 原始代码 ... │
│ crypto_cert_hash(xcert, hash, &fp_len); ──────────────────┐ │
└─────────────────────────────────────────────────────────────│───┘
│
┌────────────────────────────────┘
▼
┌─────────────────────────────────────────────────────────────────┐
│ crypto_cert_hash() [最内层] │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ /* Fused Code */ ││
│ │ printf("\nInput processed: %s\n", state->buffer); ││
│ └─────────────────────────────────────────────────────────────┘│
│ ... 原始代码 ... │
└─────────────────────────────────────────────────────────────────┘
5.4 性能分析
5.4.1 处理时间
设 $T$ 为总处理时间，分解为：
$$ T = T{load} + T{analyze} + T{llm} + T{fuse} + T_{output} $$
各阶段耗时（处理 50 个组，开启完整验证）：
| 阶段 | 耗时 (s) | 占比 |
|---|---|---|
| 数据加载 $T_{load}$ | 0.5 | 1.0% |
| CFG/支配分析 $T_{analyze}$ | 2.3 | 4.6% |
| LLM 拆分 $T_{llm_split}$ | 28.5 | 57.0% |
| 代码融合 $T_{fuse}$ | 1.2 | 2.4% |
| 语法验证 $T_{syntax}$ | 0.3 | 0.6% |
| 语义审查 $T_{semantic}$ | 16.4 | 32.8% |
| 文件输出 $T_{output}$ | 0.8 | 1.6% |
| 总计 | 50.0 | 100% |
可见 LLM 调用是主要瓶颈（拆分 + 语义审查），占总时间的约 90%。
💡 优化建议：仅启用语法验证模式可将处理时间降低至约 34 秒。
5.4.2 内存使用
峰值内存使用：
$$ M{peak} \approx M{data} + M{cfg} + M{llm_context} $$
实测约 150-200 MB（处理 50 个组）。
6. 局限性
当前方法存在以下局限：
- 控制流支持有限：未完全支持复杂控制流（如
goto、异常处理） - 语言限制：目前仅支持 C/C++ 代码
- LLM 依赖：拆分和语义审查质量依赖于 LLM 的理解能力
编译验证缺失：已集成基于规则的语法验证和 LLM 语义审查
附录 A：数学符号表
| 符号 | 含义 |
|---|---|
| $G_{CFG}$ | 控制流图 |
| $V, E$ | 节点集、边集 |
| $v_{entry}$ | 入口节点 |
| $V_{exit}$ | 出口节点集 |
| $\text{dom}$ | 支配关系 |
| $\mathcal{L}$ | LLM 函数 |
| $T_{LLM}$ | LLM API 调用延迟 |
| $R$ | 验证报告 |
| $V$ | 验证选项 |
附录 B：验证错误代码表
| 错误代码 | 级别 | 描述 |
|---|---|---|
BRACKET_MISMATCH |
ERROR | 括号不匹配 |
QUOTE_MISMATCH |
ERROR | 引号不匹配 |
MISSING_SEMICOLON |
WARNING | 可能缺少分号 |
INVALID_INSERTION |
CRITICAL | 插入位置无效 |
UNDEFINED_VARIABLE |
MAJOR | 使用未定义变量 |
DATA_FLOW_BREAK |
CRITICAL | 数据流中断 |
LOGIC_CONFLICT |
MAJOR | 与原函数逻辑冲突 |