Gauntlet: Finding Bugs in Compilers for Programmable Packet Processing 记录
这是一篇关于 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变量被输出,则会忽略它。
实现细节
核心思路还是比较清晰的,但到具体实现会存在一些阻力,好在这些阻力还算好解决:
如何判断程序等价
对两个函数可以用一个构造的方法判断两个函数是否相同:
但是作者在论文中明确表示使用无量词公式(quantifier free formulas),我不懂 Z3。
处理 Translation Validation 中的边缘情况
这个问题非常重要,一个普通的 P4 程序可能面临以下问题
对于无效变量、未初始化变量,他们的值是未定义的,处理不好,极有可能让程序等价分析难以进行(FN)。
要谨慎对待 extern 函数,他们是 P4 的边界
对此作者分别使用以下方法:
标记脏变量,在分析的时候用具体值代替
将 header 包装成了一个带 bool 的元组,进行特殊处理
如何翻译 Match-Action-Table
Match-Action-Table 是一个类似跳表的映射:
:从程序状态中提取的匹配键。
:第 个 Action 。
:默认 Action 。
、:是参数
这个映射关系是由控制平面设置的,因此翻译这个表并不容易。最简单的办法就是随意用一个表,直接变成了一个静态映射。但是这样难以说明两个程序一定相同,也不能测到所有路径,如果要尝试所有的表更不现实。
Paper 采用的方法是将参数,和当作一个输入参数,如下例子
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 )这实际上换了一个角度,将原来的查表,提升为了两个自由变量,通过升维解决了复杂度,我无法证明源程序 与转换后的程序 的等价关系,因为这两个东西明显是不等价的。但是我们可以证明存在两个程序 与 和对应的转换程序 与
其中,我们不严谨的定义这里的恒等式表示程序对于某些给定输入等价,这实际上很好证明。接着,根据我们的写法易知:
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 直接被丢了,这个问题就非常难办了,完全无法判断是那层的问题
数据包的传递依赖于外部,无法分析
Gauntlet: Finding Bugs in Compilers for Programmable Packet Processing 记录
https://anishan.top/archives/u4JWadig