这是一篇关于 P4C 编译器测试的论文,其中主要思路是利用形式化工具验证 IR 等价,以及利用 e2e 测试验证,其中 Gauntlet 是该Paper实现的工具名。

相关概念

SMT:Satisfiability Modulo Theories,用于解决一种约束求解问题,或者更直接地,可以求解 SAT 问题,标准的 ACM 算法课程中应该会包含简单的2SAT问题的讲解,在这里不多阐述。文中使用 Z3 求解器。

copy-in/copy-out:类似C语言经常使用的输入输出参数,P4的函数是有返回值的。下文也说明了这种模型,导致了不少编译器 bug,同时 copy-out 参数是未经初始化的。

extern:一般是平台实现函数,这会给分析带来一点不便

programmable block:这是一个网络设施的概念,应该和一些硬件实现,或固定实现的部分相反的可以编程的部分,我不懂,不多赘述。

BMv2:用软件实现的可编程交换机,约等于一个模拟器。

Tofino:可编程交换机,是一个硬件,是 P4 的目标平台之一。

Header Validity:P4 编程语言的 header 类似 struct 声明,但是会多出一个有效性,对无效 header 的读是未定义行为。

数据平面、控制平面:现代网络设备概念,P4 编写程序主要面向数据平面,具体不懂。

核心思路

P4 是一个 DSL,不像通用编程语言那样复杂,且 P4 也没有太多的 UB 行为。这意味着,很多在高级编程语言上不可解的分析方法,能在P4上进行。同时,P4 也缺少多种编译器实例,也不能调优化级别,这让让差分测试变得困难。

Gauntlet 首先是会进行随机代码生成的,其代码生成采用 AST 作为中间表达,并且尽量保证目标无关。Gauntlet 保证生成的代码是无误的,然后采用两种方案进行测试:

Translation Validation

利用 Z3 求解器,分析(SMT)的方法。

具体来说,Gauntlet 会对所有 Pass 的 IR 进行翻译,利用 Z3 判定多个公式是否一致,这种方法可以很直观的找到具体到 Pass 的 bug。这意味着,Translation Validation 测试不做E2E,而且直接依赖前端产出的 IR。

Model-based Testing

E2E测试,类似大多数 Fuzzling 的做法,但有更巧妙的 Test Orcale 生成方法。

具体来说,Gauntlet 充分使用上文 Translation Validation 生成的 Z3 表达式,利用添加约束的方法,尝试着重压测不同的分支。同时,Z3 可以直接给出多个符合条件的 Test Orcle 。E2E测试依赖平台,文中尝试了 BMv2 和 Tofino,其中 Tofino 硬件平台太麻烦后面直接用 Tofino 软件虚拟机调试。

处理UB

实际上 P4 没有太多的 UB 问题,而且 Gauntlet 也不尝试消除所有的 UB 行为,相反 Gauntlet 会追踪纪录 UB 变量,找到传播关系。

在 Translation Validation 中,UB 变量在分析时会被特殊处理;在 Model-based Testing 中如果UB变量被输出,则会忽略它。

实现细节

核心思路还是比较清晰的,但到具体实现会存在一些阻力,好在这些阻力还算好解决:

如何判断程序等价

对两个函数可以用一个构造的方法判断两个函数是否相同:

∃x,f(x)≠g(x)\exist x, \quad f(x) \neq g(x)

但是作者在论文中明确表示使用无量词公式(quantifier free formulas),我不懂 Z3。

处理 Translation Validation 中的边缘情况

这个问题非常重要,一个普通的 P4 程序可能面临以下问题

  • 对于无效变量、未初始化变量,他们的值是未定义的,处理不好,极有可能让程序等价分析难以进行(FN)。

  • 要谨慎对待 extern 函数,他们是 P4 的边界

对此作者分别使用以下方法:

  • 标记脏变量,在分析的时候用具体值代替

  • 将 header 包装成了一个带 bool 的元组,进行特殊处理

如何翻译 Match-Action-Table

Match-Action-Table 是一个类似跳表的映射:

T(S)={A1(S,θ1),K(S)∈M1 且表项 1 被选中A2(S,θ2),K(S)∈M2 且表项 2 被选中⋮An(S,θn),K(S)∈Mn 且表项 n 被选中Ad(S,θd),没有匹配项T(S)= \begin{cases} A_1(S,\theta_1), & K(S)\in M_1 \text{ 且表项 1 被选中}\\ A_2(S,\theta_2), & K(S)\in M_2 \text{ 且表项 2 被选中}\\ \vdots\\ A_n(S,\theta_n), & K(S)\in M_n \text{ 且表项 n 被选中}\\ A_d(S,\theta_d), & \text{没有匹配项} \end{cases}
  • K(S)K(S):从程序状态中提取的匹配键。

  • AiA_i:第 ii 个 Action 。

  • AdA_d:默认 Action 。

  • SS、θi\theta_i:是参数

这个映射关系是由控制平面设置的,因此翻译这个表并不容易。最简单的办法就是随意用一个表,直接变成了一个静态映射。但是这样难以说明两个程序一定相同,也不能测到所有路径,如果要尝试所有的表更不现实。

Paper 采用的方法是将参数SS,和AiA_i当作一个输入参数,如下例子

struct Hdr { bit<8> a; bit<8> b; }

control ingress (inout Hdr hdr) {
  action assign () { hdr.a = 1; }
  table t {
    key = hdr.a : exact ;
    actions = {
      assign() ;
      NoAction() ;
    }
    default_action = NoAction() ;
  }
  apply {
    t.apply() ;
  }
}

转换

Input:  t_table_key, t_action, hdr
Output: hdr_out

hdr_out =
  if (hdr.a == t_table_key ):
    if (1 == t_action ): Hdr (1 , hdr.b)
    otherwise : Hdr ( hdr .a , hdr . b )
  otherwise : Hdr ( hdr .a , hdr . b )

这实际上换了一个角度,将原来的查表,提升为了两个自由变量,通过升维解决了复杂度,我无法证明源程序 PP 与转换后的程序 P^\hat P的等价关系,因为这两个东西明显是不等价的。但是我们可以证明存在两个程序 PP 与 P′P' 和对应的转换程序 P^\hat P与 P′^\hat {P'}

P^≡P′^⟹P≡P′\hat P \equiv \hat {P'} \Longrightarrow P \equiv P'

其中,我们不严谨的定义这里的恒等式表示程序对于某些给定输入等价,这实际上很好证明。接着,根据我们的写法易知:

∀S, ∃αs.t. P(S)=P^(α(S)) \forall S, \, \exist \alpha \quad \text{s.t.} \ P(S) = \hat P(\alpha(S))

S 是当前状态, α\alpha是转换函数,一个抽象函数,对应一个符合 PP 的转换。已知 P^(α(S))≡P′^(α(S))\hat P(\alpha(S)) \equiv \hat {P'}(\alpha(S)) 那么直接将两侧利用上面的等式代换,得到

P(S)≡P′(S)P(S) \equiv P'(S)

处理 Model-Based Testing 的边缘情况

E2E 测试也存在一些边缘情况

  • 无效变量问题。

  • UB问题。

这里作者处理方法很简单,作者不会阻止全部 UB 的生成,Model-Based Testing 要使用 Z3 求解,所以一些变量可能会使用常量替换,这样推导出的 Test Orcale 不一定符合某些平台的行为,所以作者采用两种方法解决:

  • 上文的脏标记法,对于输出受到影响的 bit 位标记为 "don't care"

  • 让设置的 Z3 的常量满足平台要求,此时的输出当作预期行为

还有一些小细节:

  • 通过 Z3 得到的 Test Oracle 倾向于非零解,因为文章中发现几个和默认零相关的 bug

  • 集成测试,那来自控制平面的 table 数据哪来呢?上面的 Z3 变形意味着可以求出 action 和 key 的值,但是这个值对应到表上,能否比较良好映射到表,难说,作者完全没有讨论。

总结

该文章眼光独特,非常巧妙的抓住了 DSL 与 通用编程语言的边界,利用分析方法做等价性测试。其中,程序的升维变型是全篇的精华,大幅减少了 table 等价求解问题的复杂度。以及利用多 Pass 做差分测试,兼具创新与工程。

同时作者也抛出了几个问题:

  • 慢,长程序做 Z3 的判定有点慢

  • 平台可能存在硬性问题,导致 Z3 求解的 Test Orcale 直接被丢了,这个问题就非常难办了,完全无法判断是那层的问题

  • 数据包的传递依赖于外部,无法分析