Finding Compiler Bugs via Live Code Mutation 记录
这是一篇编译器测试论文,存在少量公式,但是并没有太多的数学理论在其中,他只是在用形式化语言描述算法,和函数式语言没多大区别,总体阅读难度较低。我不打算介绍改论文解决了什么痛点,因为我不知道之前相关研究是什么程度。
我目前认识到的方法,很多都是在尝试尽可能多的扩大搜索空间,这也似乎是他们的核心假设,一个很直观但是属于启发式的结论。本文也不是用反馈指导“找bug”,是随机搜索bug。如果将编译器看作一个函数 ,任何字符串输入理应都是编译器的定义域,但是绝大多数字符串组合可以说都是“平凡的”。本篇编译器测试比较注重“非平凡”情况,也就是可以编译通过,指定测试输入下具有良定义语义,在这里我称其为有效输入 和编译器可接受输入 ,易知 。
由于工业编译器实现非常复杂,难以形式化分析,这个函数的难以推导。如果我们把这些随机代码生成工具也看作一个函数(S 是种子的空间),理论上通过这样的随机程序是可以探测bug的,但很多工具的输出是难以达到 ,这里称作实际输出 ,是 的超集。将这两个集的差集越小越好,搜索能力越强,但是实际效果难说。
每篇论文前面都要巴啦巴啦强调编译器正确性问题,但是我觉得这是废话。直奔主题,论文在插入“无关代码”的基础上,试图利用运行时追踪变量值,并随机在插入点插入扰动代码块,通过插入各种“相关操作”并在退出代码块之前还原“相关变量”实现同义转换,这就是为什么是Live Code Mutation,该过程是增量的。论文实现的软件叫做 Hermes。
论文涉及的基础概念
Equivalence Modulo Inputs(EMI):输入模等价,虽然听起来有点像数学中的模 n 相等(Congruent Modulo n),但是通篇看下来该技术并没有任何与代数学相关内容,这里的“模”也不是模运算。文中尝试用数理逻辑表达EMI,
其中
简单来说就是,对于任意程序P,经过各种修改后的新程序Q,要保证语义一致性,意味着对于所有给定输入,得到的输出是一致的。注意到这个程序必须是确定的程序,即使是生成随机数,也可以通过输入种子的方式得到相同输出。
Profile映射和Env映射
Profile可以简单理解成一个map,
key是源码位置在原文中称作 program points,一个插桩点,可能是Statment的ID,文章没有具体讨论这个工程问题 。
value是一个env对象。
env也是一个map
key是变量(名)
value是一个集合,这里面记录了这个变量在该插入点所有可能的取值(观察值)
所以一个env就是假设在当前点插入代码,所需的上下文信息,能访问什么变量,变量的“值域”。为什么他要使用一个集合记录变量,因为同一行的代码可能执行多次,比如循环,递归,期间可能修改变量。
副作用(Side-Effect):
In computer science, an operation or expression is said to have a side effect if it has any observable effect other than its primary effect of reading the value of its arguments and returning a value to the invoker of the operation.
这是一个函数式编程语言常见概念,不多赘述。
CSmith
本篇与CSmith的思路有几点不同:
CSmith 是纯粹的随机代码生成,做差分验证,Hermes 是尝试检查 EMI
CSmith 采用Top-Down + 检测回退 生成方案,Hermes 采用 Top-Down 和表达式 Bottom Up 方案。
CSmith 做差分验证需要多个编译结果做比较,Hermes不需要,它存在“权威解”(Test Oracle)。
但是本篇文章并非 CSmith 的升级或者替代,Hermes的种子程序要依赖类似 CSmith 这种随机代码生成器。
Hermes整体算法
首先要有一个种子源程序,这个源程序编译无误,且在给定输入下是正确的。
有两个阶段
记录阶段:执行程序,并追踪记录程序的变量,也就是上面的Profile Env,事实上全量记录这个东西太墨迹了,文章直接采用按需记录,也就是真的决定要在这个阶段进行Mutation才记录
异变阶段:在这个阶段进行EMI Mutation
记录阶段,采用 Clang 工具库实现在这里不再赘述,论文也没有着重介绍
异变分析
分析过程非常简单,我可以用非常简短的代码表示出来,我会写haskell,因为单纯最近学了haskell非常想试试
test :: Compiler c -> Program P -> Input I -> IO ()
test c, p, i =
let oracle = execute (compile c p)
foldM (\p _ -> do
p' <- emi p i
output <- compile_execute c p' i
when (output /= oracle) $ report_bug c p'
pure p'
) p [1 .. maxIter]
emi p i =
let prof = profile p i
let stms = statements p
foldM (\p s -> do
p' <- mutate s, p
pure p'
) p stms
mutate p' s prof =
let env = ...
let child_statements = statments . chlid p
coin <- flip_coin
if not . null env && coin
code <- SynCode(env)
p = insert_before p s code
foldM (\p s -> do
p2 <- mutate p s prof
pure p2
) child_statements
所以整体非常简单
Mutation
由于编译器优化,这种 Mutate 可能会被编译器优化掉,Hermes为了防止这种情况的发生引入了条件跳转来干扰编译器编译。
Hermes会插入三种代码块
Always False Conditional Block(FCB):他会生成各种if while语句,条件是根据Env随机生成的,不过由于Env的存在可以保证不会执行,在内部生成破坏性代码。
Always True Guard (TG) :同上,一个if语句,利用Env随机生成条件,使其一定执行,将原本的状态转移移到放到TG中
Always True Conditional Block (TCB) ,
这不是Thread Control Block,一定会执行的块,但是会引入副作用,在离开块的时候还原副作用,EMI过程主要发生在这里
代码生成
代码生成存在 Top-Down 和 Bottom-Up 两种方式,CSmith 使用 Top-Down,Hermes对语句(Statement)采用 Top-Down,对表达式(Expression)采用 Bottom-Up,因为他要确定表达式不会发生UB行为。
Top Down随机代码生成就是手写递归下降 + 受限随机生成,非常简单无序赘述。
这是类型定义
data Expr = Const Integer | Var String | Paren Expr
| UnaryExpr UnaryOp Expr | BinaryExpr BinaryOp Expr Expr
deriving (Show, Eq)
data UnaryOp = Not | BitNot | Neg
deriving (Show, Eq, Enum, Bounded)
data BinaryOp = Add | Sub | Mul | Div | Mod | Shl | Shr
| BitAnd | BitOr | BitXor | Gt | Ge | Eq | Ne | Le | Lt
deriving (Show, Eq, Enum, Bounded)
unaryOps = [minBound .. maxBound] :: [UnaryOp]
binaryOps = [minBound .. maxBound] :: [BinaryOp]Bottom Up直观上可以利用随机选择Shift、Reduce,以及随机选择终结符(随机选择DFA转移边)的方式实现,不过这样要依赖一个LR分析表,论文中的处理方法更简单,通过随机采样的方式确定所有终结符,然后不断随机选择运算符规约。
sample_two :: [Expr] -> IO (Expr, Expr, [Expr])
sample_one :: [Expr] -> IO (Expr, [Expr])
flip_coin :: IO Bool
shuffle_uny_ops :: IO [UnaryOP]
shuffle_bin_ops :: IO [BinaryOP]
sync_expr :: Env -> IO Expr
sync_expr env = do
exprs <- sample env
sync_expr_recv env exprs
sync_expr_recv :: Env -> [Expr] -> IO Expr
sync_expr_recv env [expr] = pure expr
sync_expr_recv env worklist = do
coin <- flip_coin
if coin then do
(v, new_worklist) <- sample_one worklist
ops <- shuffle_uny_ops
case find (not . is_undefined_unary env v) ops of
Just op ->
sync_expr_recv env (UnaryExpr op v : new_worklist)
Nothing ->
sync_expr_recv env worklist
else do
(v1, v2, new_worklist) <- sample_two worklist
ops <- shuffle_bin_ops
case find (not . is_undefined_binary env v1 v2) ops of
Just op ->
sync_expr_recv env (BinaryExpr op v1 v2 : new_worklist)
Nothing ->
sync_expr_recv env worklist这个方法有几个问题
依赖采样函数,可能难以生成相同的内容,比如
依赖二元运算规约,存在不收敛或收敛慢的可能
随机生成全是副作用,代码写起来非常难受
文章不在意第一个问题,因此完全没有提,第二个问题通过硬性可配置计数限制解决。
UB分析
文章需要实现对未定义行为的判定,文章从代码生成的时候就避免了一些简单的结构性UB,比如自增自减同时读写,求值顺序不确定等问题。但求值本身可能还会有ub,比如有符号加法溢出、除零、模零...
文章着重讨论了如何避免求值的ub,利用的方法叫做 “speculative execution”,这是一种对运行时的模糊估计,对于某个表达式,他可能有三个变体
表达式 expr 是变量,对应变量名 v
表达式 expr 是一元运算符,对应运算符 op,子表达式
表达式 expr 是二元运算符,对应运算符op,子表达式分别是
定义
很明显这个定义就是利用运行时收集的的变量当作定义域,从而推导出值域,这样的定义存在几个问题,
二元运算符存在组合爆炸问题,
可能存在性能和内存问题
这是一种保守估计
文中没有讨论组合爆炸的问题,这个问题他们似乎不打算解决,不过对于他们使用了按需采样(稀疏采样)的方法减少采样次数,在Profiling 前随机选择部分插桩点,只收集这些位置的运行时信息。
此外TCB会出现side effect这意味着原始插入点的Env,可能过时,文中提到会模拟合成,用计算的Spex来增量更新到新的Env
总结
Hermes 是一次很成功的尝试,测试出了很多 GCC 和 Clang 问题,大部分都是分支循环以及计算bug,也测试到编译器没有覆盖的边界情况,以及常量优化等地方的问题。结合运行时信息进行粗略估计的方法也很有启发性质。
我推测 Hermes 应该大量使用了 Clang ,整个过程应该也是在 AST 上进行的,进行的三种变换以及粗略估计都比较保守,或许还可以进行
原表达式改写,同义替换、合并、拆分
顺序调换,将表达式以某种规则分离,或许能在中间进行更多的复杂运算
更激进的值的构造,比如循环构造值,甚至可以组合成包括 Duff's device 的方法复杂化过程
更激进的估计,例如将分支递归结构逻辑展平
也就是在 Hermes 基础上继续 添加 变换已有的计算、更复杂的控制流与数据流、更大的生成空间。但是这些猜测,存在很多缺点,很多问题甚至可以用原文回答:
包括表达式改写,顺序调换一般在线性IR(混合IR)上比较方便其复杂度较高,可能写出比编译器本身更多的 bug
实验并没有证明提高表达式复杂度,对表达式本身做Mutation有很大帮助
循环构造值很大程度上依赖样板代码,难以自动化生成复杂多样的值构造
更激进的估计意味着更高的性能和内存消耗
逻辑展平仅为初步构想,在非线性的IR(混合IR)上进行分析会存在困难,具体场景可能存在诸多边界条件
Finding Compiler Bugs via Live Code Mutation 记录
https://anishan.top/archives/wVPq1eH4