用细齿梳检查 SQLite

# 用细齿梳梳理 SQLite – Embedded in Academia Source: https://blog.regehr.org/archives/1292 我在 Trust-in-Soft 做的一件事就是查找开源软件中的缺陷。我花时间最多的程序是 SQLite：一个部署极为广泛的轻量级数据库。SQLite 大约有 113 KSLOC 的指针密集型代码，难以进行轻松的静态验证。另一方面，它拥有一个极其出色的测试套件（https://www.sqlite.org/testing.html），该套件已经被用来驱动 Valgrind、ASan 和 UBSan 等动态工具。我一直在将这些测试与 tis-interpreter（http://trust-in-soft.com/tis-interpreter/）一起使用。 这里我尝试描绘各种未定义行为（UB）的类别，本文主要关注蓝色阴影区域： 该图略去了许多 UB（总共有几百种），并且不按比例绘制。 说实话，我应该补充一点：使用 tis-interpreter 并非毫无痛苦（它不是从头设计的 C 解释器，而是对一个可靠的正式方法工具的改编）。它甚至比 Valgrind 还慢。它在处理单独编译的库和与系统交互的代码（如 mmap() 调用）时会遇到麻烦。正如我试图在上图中展示的，当运行在对于 ASan 和 UBSan 而言干净的代码上时，它往往会发现许多人不愿意听到的棘手问题。无论如何，我推动 SQLite 通过 tis-interpreter 运行的原因之一，是帮助我们发现并修复这些痛点。 接下来让我们看一些 bug。我一边做一边报告问题，我报告的不少问题已经在 SQLite 中修复了。我还会讨论这些 bug 与“友好 C 方言”（https://blog.regehr.org/archives/1180）这一概念的关系。 ## 悬空指针的值 SQLite 喜欢使用——但不解引用——指向已被释放的堆块的指针。它在不少地方都这样做了。例如，在 zHdr 悬空的时候： ``` if( (zHdr>=zEndHdr && (zHdr>zEndHdr || offset64!=pC->payloadSize)) || (offset64 > pC->payloadSize) ){ rc = SQLITE_CORRUPT_BKPT; goto abort_due_to_error; } ``` 这些使用是未定义行为，但当前的 C 编译器会不会对其进行有害的编译？我没有证据表明会，但在其他情况下，编译器会利用指针悬空这一事实；参见这篇文章（http://trust-in-soft.com/dangling-pointer-indeterminate/）以及这里的获奖作品 #2（https://blog.regehr.org/archives/767）。玩悬空指针要自担风险。据我所知，Valgrind 和 ASan 并不试图捕获这些使用。 使用悬空指针的值是一种棘手的 UB，它带来不便，同时——据我所知——在现实情况下几乎不会给优化器增加任何能力。对于友好 C 来说，消除它是显而易见的。 ## 未初始化存储的使用 我发现了多处对未初始化存储的读取。这介于未指定行为和未定义行为之间（http://blog.frama-c.com/index.php?post/2013/03/13/indeterminate-undefined）。 其中一种惯用法是这样的： ``` int dummy; some sort of loop { ... // we don't care about function()'s return value // (but its other callers might) dummy += function(); ... } // dummy is not used again ``` 这里的意图是避免编译器对忽略返回值发出警告。当然，更好的替代方案是初始化 dummy；如果 function() 被内联或以其他方式特化，编译器仍然可以优化掉不需要的簿记。 至少我们发现的一处未初始化读取可能是有害的，尽管我们无法让它表现得不可预测。而且，Valgrind 也没有发现它。这两个事实——可预测性以及没有报警——都可以用编译器复用了之前包含不同局部变量的栈槽来解释。当然，我们不能指望这样的巧合总能如愿。 友好 C 可以忽略对未初始化存储的读取，理由是这类错误的检测工具支持已经足够好。这是我会提倡的解决方案。一种更严厉的替代方案是由编译器强制将堆块和自动变量清零。 ## 越界指针 在 C 中，你不允许计算——更不用说使用或解引用——一个不在对象内部或对象末尾之后一个元素位置的指针。 SQLite 的 vdbe 结构体有一个名为 aMem 的成员，它使用从 1 开始的数组索引。为了避免浪费一个元素，这个数组是这样初始化的： ``` p->aMem = allocSpace(...); p->aMem--; ``` 我省略了一堆代码，完整版本在这个文件（http://www.sqlite.org/cgi/src/artifact/2c15cf88de4df974）的 sqlite3VdbeMakeReady() 中。实际情况更复杂，因为 allocSpace() 不仅仅是 malloc() 的包装：只有当 aMem 指向 malloc() 返回的块的开头时，才会发生 UB。这可以通过避免基于 1 的寻址、分配一个永远不会被使用的第零个元素、或者重新排列结构体字段来修复。 SQLite 中还有其他的越界指针，是在指向字符数组的指针越过末尾时计算出来的。这类特殊的 UB 即使在加固的 C 代码中也很常见。只有在指针越界很远，或者所讨论的对象分配在地址空间末尾附近时，它才可能成为问题。在这些情况下，越界指针可能会回绕，导致边界检查未能触发，从而可能造成安全问题。完整情况涉及一种不受欢迎的基于 UB 的优化，而且相当有意思（https://lwn.net/Articles/278137/）。正如 LWN 文章所建议的，一个好的解决方案是把边界检查移到整数域中。友好 C 的解决方案是使越界指针的创建和比较合法化。或者，我们可以强化 sanitizer，让它们对这些事情发出抱怨。 ## 非法参数 使用无效或空指针参数调用 memset()、memcpy() 和其他库函数是 UB。GCC 会积极利用这种 UB 来优化代码（https://goo.gl/h7K89h）。SQLite 中有一处使用无效指针调用 memset()，还有一处使用空指针调用 memcpy()。两种情况下的长度参数都是零，所以这些调用在其他方面是无害的。友好 C 方言只会要求每个指针指向长度参数所暗示的必需存储量，包括完全不指向任何存储。 ## 指向无关对象的指针的比较 当关系运算符 >、>=、<、<= 被用来比较两个指针时，除非两个指针都指向同一个对象，或者指向其末尾之后的一个位置，否则程序具有未定义行为。SQLite 和许多其他程序一样，想要进行这类比较。解决方案是通过转换为 uintptr_t 并比较得到的整数，将未定义行为降级为实现定义行为。例如，SQLite 现在有了这个方法，用来检查一个指针（可能指向另一个对象）是否位于某个内存范围内： ``` # define SQLITE_WITHIN(P,S,E) \ ((uintptr_t)(P)>=(uintptr_t)(S) && \ (uintptr_t)(P)<(uintptr_t)(E)) ``` 这个宏的使用可以在 btree.c（http://www.sqlite.org/cgi/src/artifact/6eee126fe9d1f571）中找到。 关于指针比较，tis-interpreter（以及 Frama-C）的意图比仅仅检测未定义行为更强：我们希望确保执行是确定性的。比较无关对象会破坏确定性，因为分配器不保证它们的相对位置。另一方面，如果 SQLITE_WITHIN 调用中的两个比较被原子地对待，并且 S 和 E 指向同一个对象，那么就没有违反确定性。我们在 Frama-C 中添加了一个 “within” 内建函数，可以在不违反确定性的情况下使用；还添加了一个裸指针比较——如果使用它，就会破坏 Frama-C 的结果对所有可能分配顺序都成立的保证。对依赖于不同分配对象相对位置的程序进行可靠分析是一个研究问题，需要类似模型检查器的东西。 在友好 C 中，指向无关对象的指针比较将表现得就像它们已经被转换为 uintptr_t 一样。我认为这根本不会束缚优化器的手脚。 ## 总结 SQLite 是一个精心设计并经过全面测试的软件。即便如此，它仍然包含未定义行为，因为直到最近，还没有好的检查器来检测这些行为。如果说有什么能把我们从 UB 地狱中拯救出来，那就是工具，以及愿意倾听工具意见的开发者。Richard Hipp 是一位编程英雄，他总是迅速回复，并且乐于接受我在这里谈到的这类棘手问题。 ## 现在该做什么 尽管情况比五年前好得多，但 C 和 C++ 开发者仍不会站在坚实的基础上，除非每一种未定义行为都落入以下两类之一： - 错误的 UB，并且存在可靠且普遍（但可能是可选且低效的）的检测器。这些检测器可以在编译时或运行时工作。 - 良性行为，并且编译器开发者已经为其提供了有文档的语义。