这是一篇编译器测试论文,存在少量公式,但是并没有太多的数学理论在其中,他只是在用形式化语言描述算法,和函数式语言没多大区别,总体阅读难度较低。我不打算介绍改论文解决了什么痛点,因为我不知道之前相关研究是什么程度。

我目前认识到的方法,很多都是在尝试尽可能多的扩大搜索空间,这也似乎是他们的核心假设,一个很直观但是属于启发式的结论。本文也不是用反馈指导“找bug”,是随机搜索bug。如果将编译器看作一个函数C:Σ∗⇀PtargetC:\Sigma *\rightharpoonup\mathcal P_{\mathrm{target}} ,任何字符串输入理应都是编译器的定义域,但是绝大多数字符串组合可以说都是“平凡的”。本篇编译器测试比较注重“非平凡”情况,也就是可以编译通过,指定测试输入下具有良定义语义,在这里我称其为有效输入 PvP_v 和编译器可接受输入 PsrcP_{src},易知 Pv⊊PsrcP_v \subsetneq P_{src}。

由于工业编译器实现非常复杂,难以形式化分析,这个函数的PvP_v难以推导。如果我们把这些随机代码生成工具也看作一个函数G:S→PsrcG:S\rightarrow\mathcal P_{\mathrm{src}}(S 是种子的空间),理论上通过这样的随机程序是可以探测bug的,但很多工具的输出是难以达到 PsrcP_{src},这里称作实际输出 Preal=Im⁡(Greal)P_{real} = \operatorname{Im}(G_{real}),PsrcP_{src} 是 PrealP_{real}的超集。将这两个集的差集越小越好,搜索能力越强,但是实际效果难说。

每篇论文前面都要巴啦巴啦强调编译器正确性问题,但是我觉得这是废话。直奔主题,论文在插入“无关代码”的基础上,试图利用运行时追踪变量值,并随机在插入点插入扰动代码块,通过插入各种“相关操作”并在退出代码块之前还原“相关变量”实现同义转换,这就是为什么是Live Code Mutation,该过程是增量的。论文实现的软件叫做 Hermes。

论文涉及的基础概念

Equivalence Modulo Inputs(EMI):输入模等价,虽然听起来有点像数学中的模 n 相等(Congruent Modulo n),但是通篇看下来该技术并没有任何与代数学相关内容,这里的“模”也不是模运算。文中尝试用数理逻辑表达EMI,

⟦P⟧=I⟦Q⟧  ⟺  ∀i∈I,  ⟦P⟧(i)=⟦Q⟧(i)\llbracket P \rrbracket =_I \llbracket Q \rrbracket \iff \forall i \in I, \; \llbracket P \rrbracket(i) = \llbracket Q \rrbracket(i)

其中

P,Q∈L(deterministic semantics ⟦⋅⟧)I⊆dom(P)∩dom(Q)EMI(P,I)={Q∈L∣⟦P⟧=I⟦Q⟧}\begin{aligned} & P, Q \in \mathcal{L} \quad \text{(deterministic semantics } \llbracket \cdot \rrbracket \text{)} \\ & I \subseteq \text{dom}(P) \cap \text{dom}(Q) \\ & \text{EMI}(P, I) = \{ Q \in \mathcal{L} \mid \llbracket P \rrbracket =_I \llbracket Q \rrbracket \} \end{aligned}

简单来说就是,对于任意程序P,经过各种修改后的新程序Q,要保证语义一致性,意味着对于所有给定输入,得到的输出是一致的。注意到这个程序必须是确定的程序,即使是生成随机数,也可以通过输入种子的方式得到相同输出。

Profile映射和Env映射

Profile:Loc→EnvEnv:Var→P(Z)\begin{align*} \text{Profile} &: \text{Loc} \to \text{Env} \\ \text{Env} &: \text{Var} \to \mathcal{P}(\mathbb{Z}) \end{align*}

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

这个方法有几个问题

  • 依赖采样函数,可能难以生成相同的内容,比如 (a∗b)+(a∗b)(a * b) + (a * b)

  • 依赖二元运算规约,存在不收敛或收敛慢的可能

  • 随机生成全是副作用,代码写起来非常难受

文章不在意第一个问题,因此完全没有提,第二个问题通过硬性可配置计数限制解决。

UB分析

文章需要实现对未定义行为的判定,文章从代码生成的时候就避免了一些简单的结构性UB,比如自增自减同时读写,求值顺序不确定等问题。但求值本身可能还会有ub,比如有符号加法溢出、除零、模零...

文章着重讨论了如何避免求值的ub,利用的方法叫做 “speculative execution”,这是一种对运行时的模糊估计,对于某个表达式,他可能有三个变体

  • 表达式 expr 是变量,对应变量名 v

  • 表达式 expr 是一元运算符,对应运算符 op,子表达式 e1e_1

  • 表达式 expr 是二元运算符,对应运算符op,子表达式分别是 e1e_1 e2e_2

定义

Spec(env, e)={env(v)expr 是变量{op⁡x∣x∈Spec(env,e1)}expr 是一元运算{xop⁡y∣(x,y)∈Spec(env,e1)×Spec(env,e2)}expr 是二元运算Spec(\text{env, e}) = \begin{cases} \text{env}(v) & \text{expr 是变量} \\ \left\{\operatorname{op} x \mid x \in Spec(\text{env}, e_1) \right\} & \text {expr 是一元运算} \\ \left\{ x \operatorname{op} y \mid (x, y) \in Spec(env, e_1) \times Spec(\text{env}, e_2) \right\} & \text{expr 是二元运算} \end{cases}

很明显这个定义就是利用运行时收集的的变量当作定义域,从而推导出值域,这样的定义存在几个问题,

  • 二元运算符存在组合爆炸问题,

  • 可能存在性能和内存问题

  • 这是一种保守估计

文中没有讨论组合爆炸的问题,这个问题他们似乎不打算解决,不过对于他们使用了按需采样(稀疏采样)的方法减少采样次数,在Profiling 前随机选择部分插桩点,只收集这些位置的运行时信息。

此外TCB会出现side effect这意味着原始插入点的Env,可能过时,文中提到会模拟合成,用计算的Spex来增量更新到新的Env

总结

Hermes 是一次很成功的尝试,测试出了很多 GCC 和 Clang 问题,大部分都是分支循环以及计算bug,也测试到编译器没有覆盖的边界情况,以及常量优化等地方的问题。结合运行时信息进行粗略估计的方法也很有启发性质。

我推测 Hermes 应该大量使用了 Clang ,整个过程应该也是在 AST 上进行的,进行的三种变换以及粗略估计都比较保守,或许还可以进行

  • 原表达式改写,同义替换、合并、拆分

  • 顺序调换,将表达式以某种规则分离,或许能在中间进行更多的复杂运算

  • 更激进的值的构造,比如循环构造值,甚至可以组合成包括 Duff's device 的方法复杂化过程

  • 更激进的估计,例如将分支递归结构逻辑展平

也就是在 Hermes 基础上继续 添加 变换已有的计算、更复杂的控制流与数据流、更大的生成空间。但是这些猜测,存在很多缺点,很多问题甚至可以用原文回答:

  • 包括表达式改写,顺序调换一般在线性IR(混合IR)上比较方便其复杂度较高,可能写出比编译器本身更多的 bug

  • 实验并没有证明提高表达式复杂度,对表达式本身做Mutation有很大帮助

  • 循环构造值很大程度上依赖样板代码,难以自动化生成复杂多样的值构造

  • 更激进的估计意味着更高的性能和内存消耗

  • 逻辑展平仅为初步构想,在非线性的IR(混合IR)上进行分析会存在困难,具体场景可能存在诸多边界条件