基于BFS算法的LLVM IR CFG深度对比Python代码故障排查

问题概述 #

使用Python结合LLVM IR分析控制流图（CFG），通过BFS算法计算两个CFG之间的深度差异，但目前代码仅能输出深度0（起始节点）和深度1的对比结果，无法展示深度2、3及更深层级的内容。

示例LLVM IR代码 #

; 示例CFG 1
define i32 @func1() {
entry:
  br label %loop

loop:
  %cnt = phi i32 [ 0, %entry ], [ %inc, %loop ]
  %inc = add nsw i32 %cnt, 1
  %cond = icmp slt i32 %inc, 5
  br i1 %cond, label %loop, label %exit

exit:
  ret i32 %inc
}

; 示例CFG 2
define i32 @func2() {
entry:
  br label %loop

loop:
  %cnt = phi i32 [ 0, %entry ], [ %inc, %loop ]
  %inc = add nsw i32 %cnt, 1
  %cond = icmp slt i32 %inc, 10
  br i1 %cond, label %loop, label %exit

exit:
  ret i32 %inc
}

当前输出 #

深度0节点对比：
func1.entry vs func2.entry -> 匹配
深度1节点对比：
func1.loop vs func2.loop -> 匹配

现有Python代码 #

import llvm.core as ll
from collections import deque

def get_cfg(func):
    cfg = {}
    for block in func.basic_blocks:
        succs = [succ.name for succ in block.successors]
        cfg[block.name] = succs
    return cfg

def compare_cfg_depth(cfg1, cfg2, start_node1, start_node2):
    visited1 = set()
    visited2 = set()
    queue = deque()
    queue.append((start_node1, start_node2, 0))
    visited1.add(start_node1)
    visited2.add(start_node2)

    while queue:
        node1, node2, depth = queue.popleft()
        print(f"深度{depth}节点对比：")
        print(f"{node1} vs {node2} -> 匹配")

        # 获取后继节点
        succs1 = cfg1.get(node1, [])
        succs2 = cfg2.get(node2, [])

        # 仅处理第一个后继？
        if succs1 and succs2 and not succs1[0] in visited1 and not succs2[0] in visited2:
            queue.append((succs1[0], succs2[0], depth + 1))
            visited1.add(succs1[0])
            visited2.add(succs2[0])

if __name__ == "__main__":
    # 加载LLVM模块
    module = ll.Module.from_assembly_path("example.ll")
    func1 = module.get_function_named("func1")
    func2 = module.get_function_named("func2")

    cfg1 = get_cfg(func1)
    cfg2 = get_cfg(func2)

    compare_cfg_depth(cfg1, cfg2, "entry", "entry")

问题原因分析 #

1. 后继节点处理不完整：现有代码仅处理每个节点的第一个后继节点，忽略了分支节点的多个后继（比如条件跳转的true/false分支），导致BFS队列无法获取深层节点。
2. 访问集合逻辑片面：仅标记第一个后继为已访问，同一节点的其他后继无法被加入队列遍历。
3. 节点匹配逻辑缺失：仅通过节点名称判断匹配，未验证节点内的指令逻辑，且未处理CFG分支不对称的情况。

解决方案 #

修改BFS逻辑，遍历所有后继节点，完善节点匹配与访问控制：

import llvm.core as ll
from collections import deque

def get_cfg(func):
    cfg = {}
    for block in func.basic_blocks:
        succs = [succ.name for succ in block.successors]
        cfg[block.name] = succs
    return cfg

def is_block_match(block1, block2):
    # 基础匹配逻辑：比较指令数量和操作码（可按需扩展为指令内容对比）
    if len(block1.instructions) != len(block2.instructions):
        return False
    for inst1, inst2 in zip(block1.instructions, block2.instructions):
        if inst1.opcode_name != inst2.opcode_name:
            return False
    return True

def compare_cfg_depth(func1, func2, start_node_name1, start_node_name2):
    cfg1 = get_cfg(func1)
    cfg2 = get_cfg(func2)
    # 缓存基本块对象，用于匹配验证
    blocks1 = {b.name: b for b in func1.basic_blocks}
    blocks2 = {b.name: b for b in func2.basic_blocks}

    visited1 = set()
    visited2 = set()
    queue = deque()
    queue.append((start_node_name1, start_node_name2, 0))
    visited1.add(start_node_name1)
    visited2.add(start_node_name2)

    while queue:
        node1, node2, depth = queue.popleft()
        block1 = blocks1[node1]
        block2 = blocks2[node2]
        match_status = "匹配" if is_block_match(block1, block2) else "不匹配"
        print(f"深度{depth}节点对比：")
        print(f"{node1} vs {node2} -> {match_status}")

        # 遍历当前节点的所有后继节点
        succs1 = cfg1.get(node1, [])
        succs2 = cfg2.get(node2, [])
        # 按分支顺序配对后继（若需处理分支不对称，可调整配对逻辑）
        for s1, s2 in zip(succs1, succs2):
            if s1 not in visited1 and s2 not in visited2:
                visited1.add(s1)
                visited2.add(s2)
                queue.append((s1, s2, depth + 1))

if __name__ == "__main__":
    module = ll.Module.from_assembly_path("example.ll")
    func1 = module.get_function_named("func1")
    func2 = module.get_function_named("func2")

    compare_cfg_depth(func1, func2, "entry", "entry")

改进说明 #

• 遍历所有后继：不再局限于第一个后继，确保分支节点的所有路径都能被BFS遍历到。
• 完善节点匹配：新增is_block_match函数，通过指令特征验证节点是否真正匹配，避免名称匹配的误差。
• 修正访问控制：对每个后继节点单独判断访问状态，保证所有未访问的深层节点都能进入队列。

内容的提问来源于stack exchange，提问作者tamanna