Reading Papers 20 - Others
# Static Testing
# ASPLOS'11 - Faults-in-Linux
在 2001 年 Chou et al. 发表了一项关于 OS 代码中故障的类型、分布和生命周期的研究,主要关注 Linux 内核 <2.4.1 版本的 x86 代码。从大型代码库中自动收集故障信息的能力在当时是革命性的,具有很大的影响力。本文将该工作延伸到 Linux 2.6 以重新评估 Linux 内核开发的现状,扩展了 Chou et al. 的工作,并且发布了开源代码。
在 Chou et al. 的工作的基础上重新实现了一组静态检查器:
Block :为避免死锁,不应在禁用中断或持有自旋锁的情况下调用会引起阻塞的函数。实现该 checker 需要知道三个函数集合:可能引起阻塞的、可能禁用中断的、可能获取自旋锁的。本文利用过程间分析迭代地计算函数集合,从一些由人工判断的函数出发。
Null :检查由各种函数返回的所有空指针。类似地,从显式返回 NULL 的函数集出发进行迭代的过程间分析。
Var :不应在固定大小的内核栈上分配过大的局部栈区变量。本文直接查找所有声明为大数组的局部变量,仅考虑使用显式常量的数组声明,不考虑可能存在问题的宏展开。
Inull :不应对指针是否为空做出不一致的假设。本文区分两种情况:IsNull 表示在空指针测试后对指针解引用,NullRef 表示在对指针解引用后进行空指针测试。前者一定是 BUG ,而后者可能只是一个过度谨慎的安全性检查(但也存在罕见的此类错误)。
Range :始终检查派生自 user space 的数组索引和循环边界。本文检查 memcpy_fromfs
, copy_from_user
, get_user
函数的数据流传递,在涉及数组索引和循环边界时是否进行合法检查。
Lock and Intr :不能获取同一把锁两次,正确释放获得的锁;正确恢复被禁用的中断。
Free, Float, Size :略。
实验结果非常多,详见论文原文。
# Compiler Testing
# PLDI'11 - Csmith
尽管编译器验证的相关工作近年来取得了不错的进展,编译器测试的相关工作仍然是必要的:
验证编译器最多使其和源语言以及目标语言的语义规范一样好,而这些规范本身就是复杂且 error-prone 的。
验证很少能提供 end-to-end guarantees (?),被认为是可信的外部环境事实上会引入错误。
Csmith 沿用了过去的 differential testing 的方法,但是能生成更 expressive 的程序,包含使用了许多 C 语言功能的复杂代码,在 state-of-the-art 的基础上有较大改善。
Csmith 保证生成的程序不包含任何 undefined behaviour 和 unspecified behaviour ,同时保证生成的程序具有单一的含义:定义 C 程序的含义为其执行的一系列 side effects ,对于由 Csmith 生成的程序是一个总结程序执行的输出结果,其值为执行结束时所有非指针全局变量的值的 checksum 。
为了生成更 expressive 的程序,Csmith 在程序生成过程中动态维护以下结构:
全局环境:包括类型、全局变量和函数等 top-level definition 。
局部环境:包括当前上下文的函数调用链(支持上下文敏感指针分析),可能的对象读写信息(从当前函数、当前调用点、以及上一个 sequence point 开始),当前作用域内指针的 point-to 信息。
Csmith 的程序生成过程如下:
随机生成一组 struct 类型的声明,随机决定成员的数量和类型。然后,从 main 函数出发 top-down 地迭代生成程序:
从语法规则中为当前程序点随机选取一个可行的产生式。随机选取与可行判定的决策分别来自于当前点的概率表和过滤器函数。
如果产生式需要一个 target ,例如变量或函数,则同样基于概率表进行随机决策,例如随机选取一个可行的已有目标,或生成一个符合条件的新目标。
如果产生式需要一个类型,则同样基于概率表进行随机决策。
如果产生式是一个非终结式,则进行递归。
根据产生式更新当前的局部环境。
执行一系列安全检查,如果检查不通过则回滚。
Csmith 实现了一系列机制以避免生成包含 undefined behaviour 的程序,细节略。
Csmith 实现了一系列安全检查,例如使用保守的过程间指针分析来避免由 side effects 的 evaluation order 引起的 undefined behaviour ,等等,细节略。
# 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 捕获冲突和修正错误:
# Debugging
# Others
# FSE'11 - Fixes2Bugs
该文章对大型操作系统 Linux ,OpenSolaris ,FreeBSD 和一个成熟的商业操作系统在过去 12 年的开发和演化过程中的 bug fixes 进行了全面的特征研究。
bug fixes 中的错误可能由许多原因引起:
修复错误的需求通常时间紧迫,导致修复者没有足够的时间进行谨慎的思考,尤其是 bug fix 可能引入的潜在 side effects 以及被修复部分与系统其余部分的交互。
修复错误的目标比一般开发“狭窄”,修复者通常更关注 bug 本身,而不是系统其余部分的正确性;而测试人员同样可能只关注 bug 是否被修复,而忘记测试被修复部分与系统其余部分的交互,以及修复是否引入了新的问题。
修复者、审阅者和测试人员可能并非原先的开发者,对相关代码并不熟悉。
在实验样本中,incorrect bug fixes 的占比为 14.8% ~ 24.4% 。
在实验样本的 incorrect bug fixes 中,45.1% 引入错误功能,14.0% 引入崩溃,8.4% 导致系统宕机,15.4% 导致数据损坏或丢失,5.6% 导致安全问题,7.0% 导致性能下降。
在实验样本中,incorrect fixes 占比最高的是并发错误 39% ,其次是语义错误占比 17% ,以及内存错误占比 14% 。该文章仅关注并发错误和内存错误,因为语义错误的 root cause 是多样化的,很难从中观察到 general 的模式。
在实验样本的并发错误 incorrect fixes 中,data race 占比 33% ,死锁占比 29% ,buffer overflow 占比 8% ,内存泄漏占比 6% 。
为了修复 data race ,常见的方法是添加同步原语(例如互斥锁),然而这很容易出错,正确的修复需要深入推理添加同步原语所引入的所有 side effects :可能会引入死锁,或是未能完整修复所有的 data race 。
为了修复死锁,经常需要颠倒锁的顺序,或是删除一些锁,然而这可能会引入另外的死锁,或是暴露出原本被死锁掩盖的其它错误(尤其是 data race)。
为了修复 buffer overflow ,常见的方法包括:增加长度检查或改用安全的字符串操作函数(例如
snprintf
)以限制存入缓冲区的数据长度,静态地扩大栈区缓冲区的大小,将栈区缓冲区替换为动态分配的堆区内存。- 方法 1 通常是安全的,很少引入另外的错误;方法 2 可能会由于错误地预估输入数据的长度而出现问题;方法 3 可能由于错误地处理 alloc/free 配对而引入另外的内存错误。
内存泄漏一经发现,其修复代码通常是直接了当的;然而由于修复者可能不清楚释放对象的准确条件,可能会引入空指针或野指针引用,或是暴露出原本被内存泄漏掩盖的 use after free 错误。此外,对于复杂的数据结构,修复者可能会忘记释放所有的成员。
作者关于缓解 incorrect fixes 问题的一些思考:
如果能将潜在受 bug fixes 影响的代码呈现给修复者,可能会有更好的机会正确修复错误。设想可以扩展诸如程序切片一类的编译器技术以分析这些信息,将代码对补丁的依赖作为切片标准。
存在现有工具以检查某些类型的 incorrect bug fixes ,但是在应用补丁后将这些工具应用于整个系统是 impractical 的。根据经验观察,很多时候仅在函数内进行检查就有很大概率能发现问题。
存在现有技术以在整个系统中搜索(与修复位置)具有相同模式或使用场景的其它代码,可以用于缓解 bug fix 不完整的问题。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01