Compiler

Symbolic Debugging of Optimized Code.

John Hennessy. 1982. Symbolic Debugging of Optimized Code. ACM Trans. Program. Lang. Syst. 4, 3 (jul 1982), 323–344.

优化对符号调试的影响

优化分为局部优化（基本块内）和全局优化（跨基本块），仅部分优化会破坏变量值一致性。

2.1 局部优化的影响

作用范围：单个基本块（无控制流分支的代码段）。

关键操作：消除冗余存储（如同一基本块内两次赋值变量，消除第一次）、重排序计算。

后果：基本块内部分变量成为非当前变量，例如：

变量被提前赋值（如公共子表达式消除导致值过早存储）；

变量被遗漏赋值（如冗余存储消除导致值未更新）。

2.2 全局优化的影响

2.2.1 不影响调试的全局优化

包括常量折叠、复制传播、全局公共子表达式消除（不移动代码时）、循环展开，这些优化不改变变量存储的 “语句级一致性”，仅可能影响错误位置报告或断点插入。

2.2.1 破坏调试的全局优化

代码外提（Code Motion）：将循环内不变代码移到循环外（预头节点），导致循环内变量值与原代码不一致（仅首次循环执行时变量非当前）。

归纳变量消除（Induction-Variable Elimination）：用单个临时变量替代多个循环计数器（如i和j=i*2用T=2*i替代），原计数器成为非当前变量。

全局死存储消除（Global Dead-Store Elimination）：删除未被后续引用的变量存储，导致变量在消除点到下一次赋值间为非当前变量。

3. 局部优化的模型：增强有向无环图（Augmented DAG）

为描述局部优化对变量的影响，作者提出增强 DAG模型，用于同时表示优化后代码的依赖关系与原代码结构。

3.1 DAG 节点标签定义

节点类型	标签内容	作用
叶子节点	变量 / 常量标识符	表示基本块入口时的变量 / 常量值
内部节点	运算符符号	表示计算操作（如+、*）
所有节点	代码起始标签（整数）	标记该节点对应目标指令的起始位置
变量标签（可选）	1. 变量名；2. 类型（当前 / 旧标签）；3. 实际节点指针	- 当前标签：变量当前值等于该节点值；- 旧标签：变量曾等于该节点值（后被覆盖）；- 实际节点指针：指向原代码中该变量存储的节点

3.2 DAG 的核心作用

后序遍历：按 “根节点集” 的顺序后序遍历 DAG，可恢复原代码的执行序列；

调试器映射：错误需报告在 “包含错误节点的第一个源语句”（避免误报后续语句），断点仅能插入 “无共享起始节点的语句”。

4. 局部优化：非当前变量的检测（Algorithm 1）

4.1 变量分类

回滚变量（RBV）：因优化提前赋值（如公共子表达式消除），值与原代码不一致；

前滚变量（RFV）：因优化未赋值（如冗余存储消除），值与原代码不一致。

4.2 算法逻辑

初始化RBV=∅、RFV=∅；

第一遍：标记 “应已执行但未执行” 的节点，将其当前标签变量加入RFV；

第二遍：将 “旧标签且未被新值覆盖” 的变量加入RFV；

第三遍：将 “提前执行的当前标签变量”（实际节点指针≥停止点）加入RBV，“未执行却已赋值” 的变量加入RBV。

4.3 算法特性

正确性：严格对应 RBV/RFV 的定义；

时间复杂度：O(|D|)（|D|为 DAG 节点数），因使用位向量实现常量时间操作。

5. 局部优化：非当前变量的恢复（Algorithm 2）

目标是找到可恢复变量集（Recoverable），即能通过 DAG 信息还原原代码值的非当前变量。

5.1 核心函数：Available(n, d)

判断 DAG 节点n的值在停止点d是否可用：

若n有当前标签变量：可用；

若n是父节点且已执行：递归判断子节点是否可用；

若n是叶子节点：变量未被覆盖则可用。

5.2 恢复逻辑

恢复 RBV：对每个v∈RBV，找到最后一个含v旧标签的节点n，若Available(n,d)则加入Recoverable；

恢复 RFV：对每个v∈RFV，若存在已执行的当前标签节点则加入Recoverable，否则找最后一个旧标签节点n，若Available(n,d)则加入。

5.3 注意事项

恢复时忽略运算符语义（避免精度问题，如不通过A-C反推B）；

若恢复中遇到新错误：递归处理错误节点，将停止点前移，直至基本块起始。

6. 局部优化的实证结果

基于 Pascal 子集编译器（生成栈式中间代码）的实验，覆盖 5000 + 行代码（含小型程序与编译器），关键结论：

指标	结果	意义
基本块平均大小（P-code 指令）	9.0	局部优化的典型作用范围
含公共子表达式的基本块比例	67%	局部优化的高频场景
含非平凡公共子表达式的基本块比例	30%	复杂优化（多操作数）占比不低
含非当前变量的基本块比例	20%	非当前变量的发生频率
非当前变量恢复率	58%	恢复策略的有效性

结论：局部优化的变量恢复具有实际价值，成本可控。

7. 全局优化的模型：流图（Flow Graph）

全局优化涉及跨基本块控制流，模型由流图 + 增强 DAG组成：

流图节点：每个节点对应一个基本块（含 DAG）；

预头节点（Preheader）：用于代码外提，存储从循环内移出的代码；

归纳变量管理：用临时变量T_F替代归纳变量家族F，记录系数m_i' = m_i/m_F、n_i' = n_i - (m_i×n_F)/m_F；

死存储标记：用 DAG 的旧标签标记被消除的存储。

7.1 原代码重构步骤

执行预头节点 DAG，按实际节点指针延迟赋值；

循环内按系数计算归纳变量值并赋值；

执行旧标签对应的存储，恢复死存储。

8. 全局优化：非当前变量的检测与恢复

8.1 检测方法

全局优化类型	检测策略	局限性
代码外提	预头设flag=false ，原位置设flag=true ，flag=false 时变量非当前	增加循环迭代的赋值开销
归纳变量消除	用循环执行次数（或临时变量值）判断，若循环执行 > 1 次则变量非当前	需跟踪循环状态
死存储消除	检测 “濒危变量”（存在路径无后续赋值），分 “全路径濒危 / 部分路径濒危”	部分路径濒危时需运行时标志，成本高

8.2 恢复方法

代码外提 / 死存储消除：需数据流分析（确定变量定义集A），仅当|A|=1且操作数无中间定义时可恢复，成本高、效果差；

归纳变量消除：可通过临时变量T的递推关系（T_i = m×T_{i-1}+n）恢复，根据停止点位置（当前 / 下一个 / 前一个T值）计算变量值，恢复成功率 100%（因系数已知）。

Debug Information Validation for Optimized Code.

PLDI’20: Li, Yuanbo, Shuo Ding, Qirun Zhang, and Davide Italiano. “Debug Information Validation for Optimized Code.”

• 代码位置问题（Code Location Problem）：源码中的部分程序点（如行号）会被优化删除，调试器无法在这些位置设置断点。
• 数据值问题（Data Value Problem）：调试器可能读取未初始化变量、数组越界等未定义行为的变量，导致结果不可靠。

2.1 关键创新：可操作程序（Actionable Program）

定义：针对特定优化流程，可操作程序P_{<s, v>}包含一个程序位置s（行号）和一个变量v，满足以下两个条件：

无论在未优化版本还是优化版本中，调试器均能在s处停下；

在s处读取变量v的 value 无未定义行为。

可操作程序的本质是通过源码转换，将 “不可验证的调试场景” 转化为 “可系统验证的场景”，为后续对比测试提供可靠输入。

2.2 三大核心技术步骤

步骤 1：预处理（Pre-processing）

目标：构建验证所需的数据结构。

操作：

对输入的合法种子程序（如来自 GCC/LLVM 测试集、Csmith 生成的无未定义行为程序）进行插桩，收集行覆盖率（即哪些行被执行），得到行集合S；

遍历程序抽象语法树（AST），为每个行s ∈ S构建作用域内变量集V_s（即该行可见的所有变量）。

步骤 2：影子验证（Shadow Validation）—— 解决数据值问题

目标：确保在位置s读取变量v无未定义行为。

原理：将 “调试时读取变量” 转化为 “源码中插入打印语句”，通过动态分析验证打印行为的合法性。

操作：

对原始程序P，在位置s插入print(v)语句，生成 “影子程序”P₁；

用 CompCert 参考解释器（验证编译器的可信执行器）和 Clang 未定义行为检查器（UBSanitizer）检测P₁是否存在未定义行为；

若P₁合法，则(s, v)对通过验证；否则丢弃该候选。

步骤 3：行增强（Line Augmentation）—— 解决代码位置问题

目标：确保调试器能在被优化删除的位置s设置断点。

原理：插入 “不可优化的函数调用” 作为 “优化屏障”，强制编译器保留该位置的调试信息。

操作：

检查 DWARF 行号表：若调试器已能在s处停下，仅在该行添加// v注释标记待验证变量；

若s被优化删除，则在s前插入外部函数调用opt_me_not()（定义在独立编译单元，编译器无法进行跨单元优化，故无法删除该调用），并添加变量注释，生成增强程序P₂。

2.3 系统测试算法

通过 “对比优化版与未优化版的调试结果” 验证调试信息正确性，流程如下：

生成可操作程序集：对每个(s, v) ∈ S × V_s，经影子验证和行增强得到P_{<s, v>}；

生成参考值：将P_{<s, v>}以-O0 -g编译（无优化），插入print(v)得到参考值PRINT(P, s, v)；

生成优化版结果：将P_{<s, v>}以-O1/-O2/-O3/-Og编译（优化），通过调试器执行动作序列A_{<s, v>} = break(s) → run → print(v) → quit，得到调试结果DBG(P', A_{<s, v>})；

对比验证：若DBG(P', A_{<s, v>}) ≠ PRINT(P, s, v)（且v未被优化删除），则判定编译器生成的调试信息存在 bug。

Who’s debugging the debuggers? exposing debug information bugs in optimized binaries

ASPLOS’21: Who’s debugging the debuggers? exposing debug information bugs in optimized binaries

• 此前研究仅聚焦单一环节：要么只测试调试器功能，要么仅验证变量值正确性，未覆盖整个工具链的调试信息生命周期（从编译器优化到调试器解析）。
• 即使编译器提供 “调试友好” 优化级别（如-Og），仍存在大量未被发现的调试信息 bug。

核心贡献：

Debug2 框架：首个针对优化二进制文件，全面检测工具链调试信息 bug 的框架，覆盖 “程序生成→轨迹对比→违规分析→bug 分类” 全流程。

四大 Trace Invariants：基于调试实体（行、栈帧、变量、参数）一致性设计的通用规则，支持跨工具链、跨语言检测。

实验成果：在三大主流工具链发现 34 个新 bug，14 个已修复：

LLVM（clang/lldb）：23 个（16 个编译器 bug，7 个调试器 bug）；

GNU（GCC/gdb）：8 个；

Rust（rustc/lldb）：3 个。

行业影响：推动 LLVM 开发者发布优化阶段调试信息维护指南，暴露 DWARF 调试格式的设计缺陷。

Debug2 框架设计

框架核心思想：对比 “优化二进制” 与 “未优化二进制” 的调试轨迹（trace），通过 Invariant 检查不一致性，定位工具链 bug。共分 4 个模块，流程如下图所示：

plaintext

程序生成 → 测试工具链（生成优化/未优化轨迹） → Trace一致性检查（Invariant验证） → 违规分类（聚类+简化用例）

1. 模块 1：程序生成

功能：生成无未定义行为、确定性、单线程的源代码，用于测试工具链。

实现：

基础生成：使用 Csmith（C 语言随机程序生成器）和 Yarpgen，过滤未定义行为（通过 CompCert 验证）；

可选方案：基于 MUSIC 的变异生成（效果弱于 Csmith/Yarpgen）。

2. 模块 2：测试工具链

功能：对生成的源代码，分别编译为 “优化版”（如-O1/-O2/-Og）和 “未优化版”（-O0），并生成调试轨迹。

轨迹内容：

行信息：每步执行的源代码行（无信息时标记为⊥）；

变量信息：全局 / 局部变量、参数及其值（优化掉的变量标记为⊥）；

栈帧信息：当前执行步骤的函数调用栈（backtrace）。

3. 模块 3：Trace 一致性检查

功能：对比优化轨迹（T (opt)）与未优化轨迹（T (unopt)），通过四大 Trace Invariants检测不一致，标记潜在 bug。

4. 模块 4：违规分类

功能：减少手动验证工作量，聚类同一根因的违规用例。

方法：

指纹生成：对违规用例，在多版本工具链中定位首个触发违规的优化 pass，生成指纹；

聚类与简化：相同指纹的用例归为一类，用 C-Reduce 将用例简化为最小可复现版本，手动验证后提交 bug。

Where Did My Variable Go? Poking Holes in Incomplete Debug Information.

ASPLOS’23: Assaiante, Cristian, Daniele Cono D’Elia, Giuseppe Antonio Di Luna, and Leonardo Querzoni. “Where Did My Variable Go? Poking Holes in Incomplete Debug Information.”

此前研究（如 [13, 30]）聚焦调试信息正确性：以未优化版本（-O0）为 “oracle”，检测优化版本的调试信息是否与未优化版本一致（如变量值是否错误）。但本文指出一个未被解决的核心问题 ——调试信息完整性：

• 优化可能不可逆转地改变程序结构（如合并变量、调整语句顺序），导致部分调试信息缺失是 “优化必然结果”；
• 但部分缺失是 “编译器实现 bug”，却无可靠 oracle 区分二者。

三大猜想的核心例子（含代码 + 问题解析）

（一）猜想 1：函数调用参数源的可见性（Opaque 函数参数变量缺失）

1. 例子背景

涉及工具：clang（编译器）

触发优化：InstructionCombining（窥孔优化，简化逻辑运算）

优化级别：-O3

DIE 缺陷类型：Missing DIE（变量无对应 DIE）

官方 bug 编号：clang #49975 [32]（已确认）

2. 核心代码

c

运行

static short a = 4;  // 全局静态变量，初始值4
void b(int c) {
    short v1 = 0;
    int v2, v3 = 2, v4 = 9, v5 = 5, v6 = 5;
    // v2赋值：v2 = a（a=4），后续参与逻辑运算&
    v7 = (v2 = a) == 0 & c;  
    foo(v1, v2, v3, v4, v5, v6, v7);  // foo是Opaque函数（跨编译单元，编译器未知实现）
}
int main() {
    b(a);  // 传入a=4
    a = 0;
}

3. 问题解析（为什么是 bug 而非正常优化？）

关键前提：foo是 Opaque 函数（编译器无法优化其参数，必须保留参数值的物理存储和调试信息）；

正常逻辑：v2作为foo的参数，编译器需在foo调用行保留v2的 DIE（含DW_AT_location或DW_AT_const_value），调试器应能查看v2=4；

实际情况：clang 的InstructionCombining优化简化(v2=a)==0 & c时，误将v2的 DIE 删除（Missing DIE），导致调试器在foo调用行看不到v2（提示 “变量未定义”）；

验证：编译器实际生成的汇编中，v2的数值（4）已作为参数传入foo（物理存储存在），但调试信息缺失 —— 属于 “编译器维护 DWARF 时的实现漏洞”。

4. 社区反馈

clang 开发者确认：优化模块在简化逻辑运算时，未同步保留 Opaque 函数参数的 DIE，属于 “可避免的调试信息丢失”，需在优化过程中增加 “参数变量 DIE 保护” 逻辑。

（二）猜想 2：赋值表达式成分的可用性（循环变量调试信息缺失）

1. 例子背景

涉及工具：clang（编译器）

触发优化：LoopStrengthReduce（LSR，循环强度削减优化）

优化级别：-O1/-O2/-O3/-Os（不同级别表现不同）

DIE 缺陷类型：Hollow DIE（变量有 DIE，但无位置 / 常量值属性）

官方 bug 编号：clang #53855 [35]（已确认，部分修复）

2. 核心代码

c

运行

// 全局数组（volatile修饰，确保内存操作不被优化省略）
volatile int c;  
int a[2][4][4] = {{{1,2,3,4}, ...}, ...};  // 三维数组初始化
unsigned short b[4] = {1,2,3,4};          // 一维数组初始化

int main(void) {
    int i, j, k;
    // 外层循环：i为induction变量（循环计数变量）
    for (i = 0; i < 2; i++)
        for (j = 0; j < 4; j++)
            for (k = 0; k < 4; k++)
                c = a[i][j][k];  // 赋值到全局volatile变量，表达式不可简化
    
    // 第二个循环：i复用为induction变量
    for (i = 0; i < 4; i++)
        c = b[i];  // 同样赋值到全局volatile变量
    
    return 0;
}

3. 问题解析（为什么是 bug 而非正常优化？）

关键前提：c是volatile全局变量，赋值操作不可被优化省略；i是循环 induction 变量，参与全局数组索引计算，且后续会被复用（满足猜想 2 的 “值不可被优化改变 + 后续使用” 条件）；

正常逻辑：调试器在两个c=赋值行都应看到i的当前值（如第一个循环i=0/1，第二个循环i=0-3）；

实际情况（不同优化级别的异常表现）：

优化级别	第一个赋值行（三维数组）	第二个赋值行（一维数组）	DIE 问题
-O1/-Og	i 不可见（Hollow DIE）	i 可见	缺少DW_AT_location
-O2/-O3	i 可见	i 可见	无异常
-Os	i 可见	i 不可见（Hollow DIE）	缺少DW_AT_location

本质原因：clang 的 LSR 优化模块在处理 “复用的循环 induction 变量” 时，仅为部分赋值行更新 DIE 的位置信息，未覆盖所有相关源码行 —— 属于 “优化模块设计时未充分考虑调试信息完整性”。

4. 社区反馈

开发者确认 LSR 优化的 “调试信息挽救（salvage）逻辑” 不足，后续通过补充 “induction 变量 DIE 位置信息覆盖规则” 修复了部分场景（如 - O1/-Og 下第一个赋值行的i可见性）。

（三）猜想 3：变量可见性的衰减性（变量可用性反向变化）

1. 例子背景

涉及工具：gcc（编译器）

触发优化：-ftree-ccp（基于树的稀疏条件常量传播）

优化级别：-Og（调试友好优化，反而出现 bug）

DIE 缺陷类型：Incomplete DIE（DIE 位置信息未覆盖变量全生命周期）

官方 bug 编号：gcc #104938 [18]（已确认）

2. 核心代码

c

运行

int a = 0;  // 全局变量，初始值0
int b = 0;  // 全局变量，初始值0
void foo(int *d) { a = 0; }  // 函数修改全局变量a

int main() {
    int *v1 = &b;  // v1指向b（地址固定）
    int **v2 = &v1;  // v2是二级指针，指向v1
    
f:  if (a)  // 循环条件：a非0则跳转f（初始a=0，循环不执行）
        goto f;
    
    *v2 = v1;  // 二级指针赋值：v2指向的v1，赋值为v1本身（地址不变）
    foo(*v2);  // 调用foo，传入v1（指向b）
}

3. 问题解析（为什么是 bug 而非正常优化？）

关键前提：变量v1的生命周期覆盖 “赋值后→循环→foo 调用”，按猜想 3，其可用性应 “不变或变差”（如一直可用，或在循环后不可用）；

正常逻辑：v1是局部变量，赋值后未被优化回收，调试器应在*v2 = v1和foo(*v2)行都能看到v1的值（&b）；

实际情况：

在*v2 = v1行：v1显示 “优化掉了”（不可用）；

在foo(*v2)行：v1突然变得可用（显示&b）；

本质原因：gcc 的-ftree-ccp优化在 - Og 级别未将a的加载指令从循环中提升（高优化级别会提升），导致v1的 DIE 范围（DW_AT_location覆盖的地址）未包含循环后的*v2 = v1行 —— 属于 “DIE 范围计算错误”。

方法

步骤 1：合成程序生成（输入层）

工具：Csmith（编译器模糊测试专用工具）

做法：生成 1000 个异构 C 程序，覆盖不同语法场景（循环、指针、全局变量、函数调用等），且保证 “输入无关”（避免动态执行结果受输入影响）；

关键设计：程序中主动植入 “符合猜想场景的代码”（如 Opaque 函数调用、全局变量赋值、循环 induction 变量），确保能触发猜想验证。

步骤 2：Violation 检查（核心验证层）

这是验证 “是否违反猜想” 的核心步骤，完全自动化：

编译程序：用目标编译器（gcc/clang）以不同优化级别（-Og/-O1/-O2/-O3/-Os）编译，生成带 DWARF 调试信息的二进制；

动态执行 + 调试器检查：

用 gdb/lldb 的脚本化接口（如 gdb 的 Python API）执行程序，在关键行（如 Opaque 函数调用行、全局赋值行）暂停；

检查变量的 “可见性 / 可用性”：

可见性：调试器能否识别变量名（对应 DIE 是否存在）；

可用性：调试器能否打印变量值（对应 DIE 是否有DW_AT_location/DW_AT_const_value）；

违规判定：对比检查结果与猜想规则，记录违反猜想的 “违规（Violation）”。

步骤 3：定位 Culprit 优化（根因定位层）

找到 “哪个编译器优化模块导致了违规”，是方法的关键创新（方便开发者修复）：

（1）针对 clang 的方法：opt-bisect-limit 二分法

clang 的优化过程由多个 “优化 pass”（如 InstructionCombining、LSR）按顺序执行；

用-opt-bisect-limit=N参数控制 “只执行前 N 个优化 pass”，通过二分法找到最小的 N—— 当执行到第 N 个 pass 时出现违规，第 N-1 个 pass 时无违规 → 第 N 个 pass 就是 culprit 优化；

（2）针对 gcc 的方法：遍历 - fno-opt flags

gcc 的优化模块可通过-fno-<opt-name>关闭（如-fno-tree-ccp关闭 ccp 优化）；

遍历所有可用的-fno-<opt-name> flags，找到 “关闭该优化后违规消失” 的 flag → 对应的优化模块就是 culprit 优化。

步骤 4：测试用例最小化（复现层）

工具：C-Reduce（C 代码简化工具）

做法：将违规的测试程序输入 C-Reduce，工具会自动删除无关代码，保留 “触发违规 + 关联 culprit 优化” 的核心逻辑；

目标：生成几行到几十行的极简代码（如之前讲解的例子），方便编译器开发者复现和修复 bug。

步骤 5：bug 确认与验证

将最小化的用例 + culprit 优化信息提交给编译器 / 调试器社区；

验证修复：待社区修复后，重新运行 Pipeline，确认违规消失 → 完成闭环。

方法的关键技术细节（创新点）

1. 无 oracle 设计（核心创新）

放弃 “以 - O0 版本为参考” 的传统思路，改用 “基于编译器原理的猜想” 作为判断标准；

解决了 “优化必然缺失 vs 编译器 bug” 的区分难题，误报率大幅降低（论文中 38 个违规最终确认 24 个真实 bug，误报率约 37%，远低于传统方法）。

2. 跨工具适配性

兼容 gcc/clang（编译器）、gdb/lldb（调试器）；

适配所有主流优化级别（-Og/-O1/-O2/-O3/-Os/-Oz），覆盖生产环境常用场景。

3. 动态检查而非静态分析

传统方法多静态解析 DWARF（如检查 DIE 是否存在），但可能误判（如 DIE 存在但调试器无法解析）；

论文方法通过 “调试器动态执行 + 打印变量” 验证，结果更贴近实际调试场景（与开发者日常调试体验一致）。

4. 端到端自动化

从程序生成到 bug 定位，无需人工干预；

开源工具链（https://github.com/cristianassaiante/incomplete-debuginfo），可直接复用

Plankton: Reconciling Binary Code and Debug Information.

ASPLOS’24: Zhou, Anshunkang, Chengfeng Ye, Heqing Huang, Yuandao Cai, and Charles Zhang. “Plankton: Reconciling Binary Code and Debug Information.”

二进制提升的现有瓶颈

为规避编译干预，可通过二进制提升（将二进制转换为中间表示 IR）直接分析，但现有提升器（如 McSema、RetDec）存在精度缺陷，核心问题源于两点：

问题类型	具体表现	影响
变量边界缺失	二进制栈内存 “扁平化”，不同变量可能重叠（如编译器复用非重叠作用域的栈槽），导致数据流图（DDG）出现虚假依赖	静态分析误判数据依赖，增加假阳性 / 假阴性
类型信息丢失	汇编代码使用 “统一类型”（如 X86 的rax 寄存器无类型区分），丢失源码级类型（如指针 / 整数），破坏类型敏感分析	如 SVF 忽略 “表现为整数的指针”，导致内存泄漏误报、堆对象建模失败

即使有调试信息（如 DWARF），编译器也无法将所有二进制代码反向映射到源码，信息仍不完整。

Plankton 是基于 LLVM 的二进制提升器，通过两个核心算法填补二进制与源码的鸿沟，生成高质量 LLVM IR，支持完整静态分析。

2.1 栈消歧算法：恢复变量边界

目标：将扁平化的栈内存拆分为离散的源码级变量，解决虚假依赖问题，分为 “必须作用域” 和 “可能作用域” 两步：

2.1.1 必须作用域（Must Scope）推断

基础：从调试信息获取初始变量映射，结合数据流分析（跟踪栈槽的定义 - 使用关系，如寄存器间接访问栈内存）；

关键：应用作用域不变量保证变量作用域的正确性：

连续性：变量在两个可达程序点可见，则中间所有点均可见；

块覆盖性：变量跨基本块可见时，需完整覆盖除起始块外的所有块；

支配性：作用域的起始 / 结束点需满足（后）支配关系；

聚合类型一致性：聚合类型（如结构体）的字段可见时，整个变量可见。

结果：得到变量的 “精确但保守” 的作用域，合并重叠且同时活跃的栈槽为同一变量。

2.1.2 可能作用域（May Scope）推断

动机：必须作用域可能遗漏部分可见点（如无数据流关联的字段访问），需补充以保证分析安全性；

方法：基于增强的活性分析（同时向前 / 向后传播），引入KILL（标记不可见变量）和OVER（合并点过滤冲突变量）集合，避免无关变量误合并；

效果：减少 11% 假阳性、1.2% 假阴性，提升 10.9% 真阳性。

2.2 类型强制算法：恢复类型信息

目标：为 IR 中的值分配正确源码级类型，减少类型转换（如ptrtoint/inttoptr），分为 “提升” 和 “降级” 两类变换：

2.2.1 变换规则

变换类型	目的	示例
提升（Promotion）	向类型格 “下方” 移动，获取更精确类型（如将整数算术转换为指针索引getelementptr ）	把ptrtoint + add 序列转为getelementptr ，恢复数组 / 结构体字段访问类型
降级（Demotion）	向类型格 “上方” 移动，修正过度精确类型（如将 phi 指令中的指针类型降级为整数）	对指针类型的 phi 指令插入类型转换，避免类型冲突

2.2.2 固定点迭代

流程：结合 LLVM 原生优化（如InstCombine）和自定义变换，迭代执行提升 / 降级，直到类型转换数量不再变化（固定点）；

类型格：顶部为 “任意类型”（最不精确），底部为 “具体类型”（最精确），保证变换的单调性和终止性。

实验基础

环境：Intel Xeon E5-1620 v3、500GB 内存、Ubuntu 16.04；

静态分析工具：SVF（指针分析）、Pinpoint（稀疏值流分析），检测 5 类 CWE 漏洞（空指针、UAF、双释放、文件描述符泄漏、内存泄漏）；

基准测试集：

标准套件：Juliet Test Suite（CWE 漏洞测试用例）；

真实项目：17 个开源 C/C++ 项目（如 PHP、FFmpeg、Redis），共 48 个二进制（Clang/GCC 编译，含不同优化级-O0/-O3）；

对比对象：5 个现有二进制提升器（RetDec、McSema、Reopt、revng、mctoll）。

3.2 核心实验结果

3.2.1 与现有提升器的对比

以 “编译 IR（wllvm 生成）的分析结果” 为基准，Plankton 表现显著优于现有工具：

指标	Plankton	现有提升器（平均）	关键差异
与编译 IR 的结果差异	17.2%	94.1%	Plankton 接近源码级分析精度
SVF 假阳性率	13.7%	62.3%	降低 48.6%
SVF 假阴性率	22.1%	60.6%	降低 38.5%
真阳性数量	接近编译 IR	几乎为 0（如 McSema/revng）	现有工具生成低级别 IR，不兼容源码级分析

备注：McSema 虽能处理所有二进制，但生成 “仿真式 IR”；RetDec 未处理调试信息不完整；mctoll 因崩溃完全失败。

Robustifying Debug Information Updates in LLVM via Control-Flow Conformance Analysis

PLDI’25: Robustifying Debug Information Updates in LLVM via Control-Flow Conformance Analysis

二： 研究背景与核心问题

2.1 调试信息的重要性

现代软件（如 Linux 发行版、Firefox）通常以优化模式编译，LLVM 需生成调试信息（尤其是调试位置信息）建立 “源程序 - 机器码” 映射，支撑调试器（GDB/LLDB）、 sanitizer（AddressSanitizer）、profile 优化（SamplePGO）等工具。其中，调试位置信息以元数据形式附着于 LLVM IR 指令，格式为(行号, 列号, 作用域)。

2.2 调试位置更新的挑战

LLVM 优化（如循环优化、尾递归消除）会重排 / 替换 / 删除 IR 指令，需手动更新调试位置，其更新包含三个核心要素：

要素	定义
目标指令（dst）	优化后需更新调试位置的指令（位于优化程序 P’）
源指令（src）	提供调试位置参考的指令（位于原程序 P）
更新操作	三种官方定义操作：- Preserve：将单个 src 的调试位置赋给 dst- Merge：合并多个 src 的调试位置赋给 dst- Drop：删除 dst 的调试位置

核心问题：

缺乏调试位置更新的形式化规范，手动实现易出错（如漏更导致 “丢失调试位置”，错更导致 “错误调试位置”）；

现有黑盒测试（如 Debug2）仅能检测 “P 与 P’ 的调试信息不一致”，无法定位优化代码中的错误位置，更无法生成修复方案。

三、核心技术：控制流一致性分析

3.1 核心观察

优化程序 P’ 的控制流路径上，调试位置集合不能超出原程序 P 对应路径的调试位置集合，即：对 P’ 的任意路径 γ’ 及其在 P 中的对应路径 γ，需满足 L(γ') ⊆ L(γ)（L 表示路径上的调试位置集）。—— 避免优化引入 “额外调试位置” 导致调试误导。

3.2 技术流程（分 3 步）

步骤 1：监控指令操作，识别 src 与 dst

通过插桩（Instrumentation）监控 LLVM 优化过程中 4 种关键指令操作，建立 “src-dst” 映射：

指令操作	语义	目标指令（dst）	源指令（src）
Create	新建指令 s	s	-
Clone	从旧指令 s_old 克隆新指令 s_new	s_new	s_old
Move	将指令从位置 p_from 移至 p_to（记为 s_to）	s_to	s_from
Replace	用 s_to 替换 s_from 的所有引用	s_to（需先通过前 3 种操作识别）	s_from

步骤 2：收集控制流图（CFG）的调试位置集

对原程序 P 的 CFG：收集所有经过 src 的路径，提取调试位置集L_src；

对优化程序 P’ 的 CFG：收集所有经过 dst 的路径，提取调试位置集L_dst；（注：路径遍历循环仅 1 次，避免路径爆炸，同时覆盖分支调试位置）

步骤 3：基于一致性规则确定更新操作

根据L_src与L_dst的关系，自动判断正确的更新操作：

若L_dst ⊈ L_src：执行Drop（避免引入额外调试位置）；

若L_dst ⊆ L_src且|src|=1：执行Preserve（保留单个源的调试位置）；

若L_dst ⊆ L_src且|src|>1：执行Merge（合并多个源的调试位置）。

四、工具实现：MetaLoc

MetaLoc 包含两个核心组件，无缝集成到 LLVM 编译流程：

LLVM 内置库：实现控制流一致性分析、调试位置集收集、更新操作判断；

独立插桩工具：注入钩子（Hook）监控优化过程，具体钩子类型如下：

钩子类型	功能	目标 LLVM API 示例
指令操作监控	捕获 Create/Clone/Move/Replace，识别 src 与 dst	Instruction::clone 、Value::replaceAllUsesWith
更新操作监控	捕获开发者手动实现的 Preserve/Merge/Drop，用于对比校验	Instruction::setDebugLoc 、Instruction::dropLocation
分析初始化 / 收尾	初始化分析、收集 P/P’ 的调试位置、生成修复骨架	Pass::run （优化入口 / 返回前）

此外，MetaLoc 会生成更新骨架（含具体变量名和 LLVM API），辅助开发者将骨架转化为可直接提交的补丁（如Drop(AccRecInstrNew)）。

Debugger Toolchain Validation via Cross-Level Debugging.

ASPLOS’25: Yang, Yibiao, Maolin Sun, Jiangchang Wu, Qingyang Li, and Yuming Zhou. “Debugger Toolchain Validation via Cross-Level Debugging.”

调试器工具链（编译器 + 调试器）的正确性对软件开发至关重要，但现有验证技术存在显著缺陷：

1. Oracle 依赖问题：现有方法以 “未优化可执行文件的调试轨迹” 为可靠参照（Oracle），对比优化 / 未优化文件的轨迹来检测 bug，但编译器优化会大幅修改源码元素、变量表示和指令顺序，导致两类轨迹不可比。
2. 覆盖范围狭窄：仅聚焦 “编译器优化相关的调试信息 bug”，无法检测非优化相关的 bug（如调试器自身逻辑错误）。
3. 假阳性高：优化导致的代码删减 / 重排会产生大量误报，干扰 bug 定位。

解决方案：跨级调试（CLD）与 Devil 框架

1. CLD 核心思想

对同一可执行文件，分别通过 “源码级调试（Source-Level）” 和 “指令级调试（Instruction-Level）” 获取轨迹，基于 “同一文件的不同调试级别轨迹应满足特定约束” 的洞察，检测约束违反以定位 bug。

2. CLD 的三大关键约束（形式化定义）

约束名称	核心含义	形式化描述（简化）
R#1：可达性保持	源码级调试能命中的程序位置（如行号），指令级调试必能命中	∀l∈程序 P，l∈源码级命中集合 Hₛ ⇒ l∈指令级命中集合 Hᵢ
R#2：顺序保持	源码级中位置 lₐ先于 lᵦ命中，指令级中顺序必一致	∀lₐ,lᵦ∈P，源码级顺序 Oₛ(lₐ) > Oₛ(lᵦ) ⇨ 指令级顺序 Oᵢ(lₐ) > Oᵢ(lᵦ)
R#3：值一致性	同一程序位置在两类调试中，变量初始值必相同	∀变量 v 在位置 l，源码级值 Vₛ(v,l) = 指令级值 Vᵢ(v,l)

3. Devil 框架实现步骤

Devil 是 CLD 的工程化实现，核心流程（对应 Algorithm 1）如下：

Forwarding Program（程序转发）：在调试器中启动可执行文件，通过随机选择位置（源码行 / 指令地址）、设置断点或步进，确保程序运行到该起始位置（覆盖更多程序状态）。

Stepping Program（程序步进）：从起始位置开始，分别以 “源码级（如 GDB 的step）” 和 “指令级（如 GDB 的stepi）” 逐步执行，直至程序退出。

Recording Traces（轨迹记录）：记录两类调试的动态状态，包括：程序位置（文件名、行号、指令地址）、命中顺序、变量值（通过 GDB 的bt -frame-info/info args等命令提取）。

Comparing Traces（轨迹对比）：检查轨迹是否违反 R#1-R#3，若违反则标记为潜在 bug（需手动排除重复 / 误报）。

研究问题（RQ1-RQ5）

RQ1：Devil 能否有效检测真实 bug？

RQ2：Devil 发现的 bug 重要性与影响范围？

RQ3：CLD 三大约束对 bug 检测的贡献？

RQ4：Devil 与现有技术（如 Debug2）的对比？

RQ5：Devil 的性能开销？

Debug like a Human: A Large Language Model Debugger via Verifying Runtime Execution Step-by-Step.

Zhong, Li, Zilong Wang, and Jingbo Shang. “Debug like a Human: A Large Language Model Debugger via Verifying Runtime Execution Step-by-Step.” arXiv:2402.16906. Preprint, arXiv, June 6, 2024. https://doi.org/10.48550/arXiv.2402.16906.

现有 LLM 调试方法（如 Self-Debugging）将程序视为不可分割的整体，仅依赖 “执行后反馈”（如单元测试结果、错误信息），存在两大问题：

缺乏细粒度运行时信息：未利用 “中间变量值”“执行流轨迹” 等人类调试的核心依据；

对复杂场景无效：面对复杂控制流（循环、递归）或数据操作时，难以定位具体错误。

研究目标：

模仿人类调试逻辑（设置断点、检查中间状态），提出LDB（Large Language Model Debugger）框架，将 “运行时执行信息” 融入 LLM 调试，提升复杂程序的错误定位与修复能力。

核心方法：LDB 框架设计

LDB 的核心思想是：将程序分解为 “基本块”，跟踪每个块的运行时状态，让 LLM 逐块验证正确性，流程分为 “种子生成→Profiling（运行时信息采集）→Debugging（逐块验证）→Regeneration（程序精炼）”，迭代直至通过可见测试或达到最大迭代次数（默认 10 次）。

2.1 关键概念铺垫

基本块（Basic Block）：单入口、单出口的直线代码段，执行时无分支跳转，是调试的最小单元；

控制流图（CFG）：描述程序所有可能执行路径的图，节点为基本块，边为控制流转移；

执行轨迹（Execution Trace）：程序运行时实际经过的基本块序列（对应 CFG 中的一条路径）；

中间状态（Intermediate State）：执行完第 i 个基本块后，所有变量的实时值（记为Vi），用于反映 “执行是否符合任务意图”。

2.2 三阶段工作流程

阶段 1：Profiling（运行时信息采集）

静态分析：对 LLM 生成的 “种子程序”（A0）构建 CFG，分解为基本块；

动态执行：输入 “失败的可见测试用例”，记录执行轨迹（如[B1,B2,…,Bn]）；

状态采集：记录每个基本块执行前后的变量值（即中间状态(Vi−1,Bi,Vi)，Vi−1为块入口状态，Vi为块出口状态）。

阶段 2：Debugging（逐块验证与错误定位）

逐块查询 LLM：将 “任务描述 + 基本块 + 前后中间状态” 输入 LLM，让其判断块的正确性（Di∈{True,False}）并生成错误解释（Ei）；

优化策略：

选择性调试：对长轨迹（如循环、递归）采样Nb个块（默认 10 个），避免 LLM token 超限；

批量调试：将所有采样块的状态批量输入 LLM，而非逐块查询，提升 token 效率。

阶段 3：Regeneration（程序精炼）

将 “任务描述 + 调试结果（错误块、解释）” 输入 LLM，生成精炼后的程序（A∗）；重复 “Profiling→Debugging→Regeneration”，直至程序通过所有可见测试或达到最大迭代次数。