2.2 结构匹配与图算法

2.2.1 控制流图特征 #

CFG提取 #

class BasicBlock:
    """基本块"""
    def __init__(self, addr):
        self.addr = addr          # 起始地址
        self.instructions = []     # 指令列表
        self.successors = []       # 后继块
        self.predecessors = []     # 前驱块
    
    @property
    def size(self):
        return len(self.instructions)
    
    @property
    def out_degree(self):
        return len(self.successors)
    
    @property
    def in_degree(self):
        return len(self.predecessors)

class CFG:
    """控制流图"""
    def __init__(self, func):
        self.func = func
        self.blocks = {}          # addr -> BasicBlock
        self.entry = None         # 入口块
        self.exit_blocks = []     # 出口块列表
    
    def extract_features(self):
        """提取CFG特征"""
        return {
            'num_blocks': len(self.blocks),
            'num_edges': self.count_edges(),
            'max_depth': self.compute_max_depth(),
            'num_loops': self.detect_loops(),
            'cyclomatic_complexity': self.cyclomatic_complexity()
        }

CFG特征向量 #

特征向量示例
┌─────────────────────────────────────────┐
│ 特征                    │ 值    │ 权重  │
├─────────────────────────────────────────┤
│ 基本块数量              │ 15    │ 0.15  │
│ 边数量                  │ 18    │ 0.10  │
│ 最大深度                │ 8     │ 0.10  │
│ 循环数量                │ 2     │ 0.15  │
│ 圈复杂度                │ 5     │ 0.15  │
│ 条件跳转数              │ 4     │ 0.10  │
│ 调用指令数              │ 7     │ 0.15  │
│ 返回指令数              │ 1     │ 0.10  │
└─────────────────────────────────────────┘
特征向量: [15, 18, 8, 2, 5, 4, 7, 1]

2.2.2 图同构算法 #

VF2算法 #

经典的图同构检测算法：

VF2算法流程
┌─────────────────────────────────────────────────┐
│ 输入: 图G1和G2                                  │
│ 输出: 同构映射或NULL                            │
│                                                 │
│ 1. 初始化状态S = (M, T1, T2)                    │
│    M: 当前映射                                  │
│    T1, T2: 候选节点集                           │
│                                                 │
│ 2. 如果|M| == |V(G1)|, 返回M                    │
│                                                 │
│ 3. 选择候选对(a, b) ∈ T1 × T2                   │
│                                                 │
│ 4. 检查可行性(Fs函数):                          │
│    - 语义一致性                                 │
│    - 结构一致性                                 │
│    - 前瞻约束                                   │
│                                                 │
│ 5. 如果可行:                                    │
│    - 将(a, b)加入M                              │
│    - 更新T1和T2                                 │
│    - 递归调用                                   │
└─────────────────────────────────────────────────┘

def vf2_isomorphic(cfg1, cfg2):
    """
    VF2图同构检测
    """
    # 快速过滤
    if len(cfg1.blocks) != len(cfg2.blocks):
        return False, None
    
    if cfg1.count_edges() != cfg2.count_edges():
        return False, None
    
    # VF2核心算法
    state = VF2State(cfg1, cfg2)
    return vf2_match(state)

2.2.3 图编辑距离 #

定义： 将图G1转换为G2所需的最小编辑操作数。

编辑操作
├── 节点操作
│   ├── 插入节点 (cost: c_ins)
│   ├── 删除节点 (cost: c_del)
│   └── 替换节点标签 (cost: c_sub)
│
└── 边操作
    ├── 插入边
    ├── 删除边
    └── 修改边标签

计算公式：

def graph_edit_distance_approx(cfg1, cfg2):
    """
    近似图编辑距离计算
    使用匈牙利算法进行节点匹配
    """
    n1, n2 = len(cfg1.blocks), len(cfg2.blocks)
    
    # 构建代价矩阵
    cost_matrix = np.zeros((n1, n2))
    
    for i, block1 in enumerate(cfg1.blocks.values()):
        for j, block2 in enumerate(cfg2.blocks.values()):
            cost_matrix[i, j] = 1 - block_similarity(block1, block2)
    
    # 匈牙利算法求最优匹配
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    
    total_cost = cost_matrix[row_ind, col_ind].sum()
    total_cost += abs(n1 - n2) * 1.0
    
    return total_cost

2.2.4 基本块相似度计算 #

指令级比较 #

def block_similarity_syntactic(b1, b2):
    """
    基于语法的相似度（指令序列）
    """
    opcodes1 = [insn.mnemonic for insn in b1.instructions]
    opcodes2 = [insn.mnemonic for insn in b2.instructions]
    
    dist = levenshtein_distance(opcodes1, opcodes2)
    max_len = max(len(opcodes1), len(opcodes2))
    
    return 1 - dist / max_len

def levenshtein_distance(s1, s2):
    """计算编辑距离"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                )
    
    return dp[m][n]