Reading Papers 20 - Others
# Reverse Debugging
# EuroSys'10 - ESD
KEY Idea ：除了 replay 完全相同的执行路径以外，如果有能够触发相同缺陷的其它可行路径，也足以用于缺陷的调试和诊断。
执行综合 (execution synthesis) ：仅从程序源码、崩溃时的 coredump 和 bug report 出发，综合出一条能触发相同错误的执行路径。ESD 结合静态分析与动态符号执行来实现执行综合。
ESD 顺序执行综合 ：
ESD 根据 coredump 解析出程序崩溃所在的 basic block 以及触发错误的约束条件，根据缺陷的种类进行不同的解析。
ESD 利用静态分析来缩减搜索空间，缩减后得到一组可能触发目标缺陷的路径集合。具体地讲，ESD 从崩溃点开始进行后向分析，找出 CFG 上的 critical edges（即必经之路），然后据此将分析过程分解为若干个连续的子过程。
定义 intermediate goal 为目标 BB 的 dominate BB（即必经之路），然后：
解析每条 critical edge 的 branch condition 以及条件表达式中每个变量 的 reaching definition 指令 ，搜索能满足 branch condition 的指令的组合。
将这样的组合作为 intermediate goal ，以此将分析过程分解为向下一个子目标迈进的子过程。如果存在多个可行组合，则计算析取集。
ESD 基于 KLEE 实现符号执行，利用有关 critical edge 的信息迅速放弃已知不可达的路径。此外，ESD 估计每个状态与下一个中间目标的 接近程度 (proximity) 作为 heuristic ，评估执行状态的优先级。
- 因为静态分析的不精确，无法判断各个中间目标的先后顺序，所以要同时处理所有中间目标。
proximity-guided search ：
当目标位于当前正在执行的函数中时，估算指令数距离作为接近度。
如果存在 call instr 则将 callee 的指令数也纳入计算结果。
如果存在难以处理的代码段（例如递归调用、复杂循环、syscall），则简单估算为固定距离。
否则，ESD 考虑当前 calling stack 中的其他栈帧，因为当前执行的函数可能会返回，然后由某个先前调用执行中的函数出发到达目标。具体地讲，ESD 估算从 calling stack 中每个调用点出发到达目标的距离，然后取最小值。
ESD 线程调度综合 ：
# OSDI'18 - REPT
KEY Idea ：利用 online hardware tracing 以极低的性能负载记录程序的控制流，然后根据 coredump 和控制流信息由 offline binary analysis 来恢复数据流信息。
对于可逆的指令（例如 add rbx, rax），直接进行后向分析即可。
对于存在不可逆指令（例如 xor rax, rax）、但不存在内存访问的程序：
将程序状态和指令描述为序列 ，其中 是已知的。
对于序列 ，交替进行前向和后向的分析，试图推断每个程序状态上各个寄存器的值，直到不动点为止。
对于存在内存访问（例如 mov [rbx], rax）的程序（占绝大多数）：
对于无法确定目标地址的内存写入操作，直接将其忽视会引入过度的数据丢失。
REPT 在交替分析的过程中捕获冲突，并据此修正内存中的实际值，而不去考虑如何处理每个写内存指令。
details ：
REPT 在交替分析的过程中维护一个 data inference graph ：
DIG 中的节点表示被指令访问的寄存器或内存地址，用于读则为 use node ，用于写则为 def node ，都有则创建两个不同的 use/def nodes 。memory dump 中的数据被视为 use node ，用于后向分析。
维护每个节点的 dereference level ，用于捕获冲突和修正错误。
value edge 表示 REPT 用 的值来推断 的值，address edge 表示 REPT 用 的值来计算 的地址。
horizontal value edge 用于单一指令内表示的推断关系，在后向分析中 def node (known) → use node ，在前向分析中 use node (known) → def node 。
vertical value edge 用于连接（不同指令中）表示同一内存位置的不同节点，事实上构成了 def-use chain（例如 def 与其所有 use）。
REPT 捕获冲突和修正错误：