Salaheddine El Hssani:用第二实现校验编译器

Salaheddine El Hssani:用第二实现校验编译器

💡 原文英文,约1900词,阅读约需7分钟。
📝

内容提要

文章介绍用“第二实现”校验策略编译器rowstile:以缓慢直白的参考求值器与编译后的SQL对比,随机生成策略、数据与变更进行差分测试。该方法发现组条件、函数权限等错误,但也暴露共享解析器、生成器覆盖不足等局限,故辅以手算用例、独立语法和故意注入错误来检验检查器本身。

🔎

延伸解读

差分测试为何能发现共享盲区之外的错误

文章指出,当测试与实现出自同一作者时,对问题的相同误解会同时存在于代码和测试中,导致测试通过而缺陷上线。rowstile 的差分测试用缓慢但直白的参考求值器与编译后的 SQL 对比,随机生成策略、数据和变更,从而绕开作者预设的输入。这种方法能发现组条件、函数权限等错误,但前提是参考求值器本身正确,因此仍需独立校验。

参考求值器自身的校验缺口

参考求值器并非天然可信。文章披露,其条件读取逻辑从未与数据库对比,首次随机条件测试就发现 1949 个条件中有 626 个与 PostgreSQL 解读不同,涉及排序规则、类型转换和 ID 比较。这说明第二实现也需要被检验,否则差分测试可能因双方共享同一误解而失效。作者随后用手算用例和独立语法来约束求值器。

随机生成器的覆盖边界与补充手段

随机策略生成器只能覆盖它构造出的世界。文章提到,首次公开发布前的 11 个权限错误中,随机策略只发现 1 个,其余多由人工阅读发现,涉及分区、默认权限、搜索路径、迁移事务等数据库周边因素。因此作者扩展了测试环境以变化目录、会话、角色和区域设置,并辅以手算用例和故意注入错误来检验检查器本身是否有效。

故意注入错误:验证检查器是否真的在检查

一个从不失败的对比可能根本没有在检查。文章介绍,作者向编译器手工注入 64 个错误,测试套件捕获 60 个;向求值器注入 40 个,捕获 26 个。自十月起按规则生成约一万个错误,截至 10 月 20 日,2749 个改变编译结果的错误被捕获 98.7%。每个漏网错误都会补充检查或说明为何不改变答案,以此持续校准测试的有效性。

❓

Q&A

什么是“第二实现”校验方法,它为什么能发现编译器中的错误?

“第二实现”校验方法是指为同一个问题编写一个缓慢、直白的参考实现,然后与优化后的编译器在随机生成的输入上对比结果。因为测试和代码可能来自同一种错误理解,而第二实现独立计算答案,能暴露两者不一致的地方。

rowstile 编译器将策略编译成什么?它的输出为什么需要校验?

rowstile 将简短策略(如“如果文件夹共享给你或你能查看其父文件夹,则你可以查看”)编译成 PostgreSQL 的视图、行级安全策略、由触发器维护的闭包表以及单行检查函数。输出为速度做了优化(如闭包表、省略冗余查找),每个优化点都可能出错,因此需要校验。

差分测试框架 difftest.py 是如何工作的?它做了哪些随机变更?

difftest.py 将策略应用到真实数据库,填充随机数据,然后进行随机变更:移动、新链接、循环、组中组、开始和结束的共享、ID 变更、TRUNCATE、一个事务中的多条语句。每次变更后读取整个状态,交给参考求值器,并对每个用户询问双方相同的问题(可列出什么、能否操作每行、行级安全允许读什么、谁拥有每个权限及原因)。

随机策略生成器 genpolicy.py 有什么特点?它如何帮助发现错误?

genpolicy.py 随机生成类型、关系、权限及其表和数据,并执行相同的检查。三分之一的策略使用大写、保留字、引号和重音符号命名表;近一半使用非 bigint 键;文本键中一半使用单词(受排序规则影响)。每晚运行一百个新种子,失败时缩小到仍失败的最小策略。它曾发现组条件错误和函数权限错误。

参考求值器本身可能存在哪些错误?如何检验求值器?

求值器可能错误解读条件(如文本排序、类型转换、ID 比较)。检验方法包括:用随机条件测试(conditions_test.py)对比 PostgreSQL 的答案,首次运行发现 1949 个条件中 626 个读法不同;以及手工计算答案的用例和故意注入错误来检验检查器本身。

第二实现校验方法有哪些局限性?如何弥补?

局限性包括:两个实现共享同一解析器,可能共同误读策略;生成器只能覆盖它构建的世界,许多错误(如分区、默认权限、搜索路径等)不在其中。弥补措施:使用手工计算答案的用例、独立语法解析器交叉验证、故意注入错误检验检查器,并扩展测试框架以变化目录、会话、角色和区域设置。

🏷️

标签

➡️

继续阅读