钻头
PDF文学可执行文件
Terence Kelly
“钻头”专栏旨在改进真实世界的代码。例如，最近的几期通过添加新功能来增强广泛使用的主力工具：用于无处不在的数据库的崩溃容错6 和用于不可或缺的实用程序的持久内存7。本期内容更广泛。它提出了一种简单的约定，使编译后的二进制程序和库更实用、更透明和更易于管理。本专栏中提供的工具可以轻松地将新约定应用于您自己的软件，并且示例代码将该工具应用于您可能每天都在使用的程序。
原则与实践
1980 年代的自由软件运动15 和 1990 年代的开源运动3 定义了崇高的理想，在当时是激进的，但此后已成为主流。如今，无数高质量的程序原则上提供了分析、重新编译、修改和重新分发这些程序的自由。
然而，在实践中，当今名义上的自由/开源软件未能达到最初运动的核心务实目标。对于普通用户来说，找到与二进制可执行文件对应的确切源代码应该很容易，但即使对于经验丰富的开发人员来说也非常困难。我对资深程序员（包括流行开源软件包的贡献者）的非正式调查发现，没有人能够自信地指出他们在主要的 GNU/Linux 发行版上每天使用的程序和库的源代码。知道或多或少相关的源代码据称在某处可用，当您现在需要正确的代码时，这只是微不足道的安慰。
$ opaque < input > output
opaque: elusive.c:476: whatfun
Assertion `! confused´ failed.
幸运的是，纠正自由软件片面的成功并不困难。我们可以保留来之不易的原则性成果，同时恢复方便而精确的源代码访问。有很多方法可以将二进制文件绑定到源代码。神秘而脆弱的替代方案采用了可疑的当前做法：将源代码秘密隐藏在远离常用 $PATH 的本地文件系统中，或者委托给注定最终会消亡的遥远服务器。简单而万无一失的方法是重新定义编译后的二进制文件和相应的源代码之间的关系，使其类似于鸡和蛋的关系：坚持认为任何一方都可以产生另一方。
文学可执行文件是编译后的程序和库，其中包含并根据需要公开从中构建的源代码。精确定位与文学可执行文件对应的确切源代码非常简单，这反过来又使得分析、调试、重新编译和修改软件变得容易。文学的机制并非专门针对源代码，因此文学可执行文件还可以包含其自身的文档、示例输入、测试装置或我们选择的任何其他文件。
文学性出乎意料地廉价且容易实现。即使要将其改造到复杂的遗留软件中，也只需要一小段简单的代码，我们很快就会看到。主要前提是决心：说服自己，如果您要运行自由软件，那么您应该拥有源代码，并且没有比将源代码保存在相应的可执行文件内部更好的地方了。俗话说，汽车用户手册应该放在手套箱里。文学可执行文件也将完整的蓝图放在那里。
谷仓生物学
源代码 tarball 是我们类比中的鸡蛋，虽然不活跃，但充满了潜力。它体现了一种基因型，定义了其物种。经过构建过程孵化后，鸡/可执行文件呈现出个体表型，该表型取决于构建环境和目标架构。例如，来自 ftp.gnu.org 的 grep-3.7.tar.xz tarball 包含当前 grep 实用程序的源代码。构建过程在 Linux/Intel 和 Solaris/SPARC 上产生不同的 grep 二进制文件，但它们的运行时行为显示出家族相似性，这证明了它们共同的祖先。
图 1 中的小型 C 程序 litr8x 将鸡蛋植入鸡中。自然，我们将安排 litr8x 发出其自身的源代码，图 1（目标程序）和图 2（编译/植入/运行脚本）共同说明了赋予文学性的通用技术。目标程序必须静态分配鸡蛋的空间——图 1 第 6 行的数组 E。当适当地调用时，程序将转储此数组（第 19-20 行），但首先必须将鸡蛋植入其中。预处理器 #define 保留足够的空间并用特殊字符串标记数组（第 6 行）；编译创建一个准备接收鸡蛋的鸡。 litr8x 程序内存映射鸡和鸡蛋二进制文件（第 22 和 23 行），在鸡中找到标记（第 24 行），并用鸡蛋覆盖该位置（第 25 行）。
图 1
litr8x.c（省略注释和 #include）图 2 的 shell 脚本编译并运行 litr8x。第 3 行创建一个标记字符串，用于指定编译程序中鸡蛋植入的位置。此脚本使用源代码的抗冲突校验和，但任何未在编译程序其他位置出现的标记都可以。第 4 和 5 行编译程序，传递鸡蛋（源文件）的大小和标记字符串作为预处理器 #define。
图 2 用于编译和测试
litr8x.c 的 Shell 脚本如果我们尝试使用 litr8x 可执行文件将鸡蛋植入自身，则会产生错误，第 6-8 行规避了该错误：我们无法 open() 运行中的可执行文件进行写入。因此，我们将可执行文件复制到 /tmp/（第 6 行），使用副本进行植入（第 7 行），然后删除副本（第 8 行）。值得庆幸的是，当 litr8x 植入自身以外的程序时，这种繁琐的操作是不必要的。
最后，第 9 和 10 行检查植入是否成功。第 9 行打印之前在第 3 行计算的 litr8x.c 校验和。第 10 行调用不带参数的 litr8x 可执行文件，这应该会导致它下蛋（图 1 的第 19 和 20 行），并将输出管道传输到校验和程序。如果一切顺利，图 2 的脚本会产生相同的校验和
$ ./run.sh
source file: d981431fc0d599a0...
exec output: d981431fc0d599a0...
当然，直接调用不带参数的 litr8x 会产生同样令人信服的演示：它打印自己的源代码（图 1 加上 #include 和注释）。
“在糟糕的旧时代，善意的程序员‘修补’二进制目标代码……”
—Jon Bentley，转载于 Knuth [8, p. 140]
谨慎的程序员对使用自制工具修补编译后的二进制文件感到担忧是理所当然的；他们以格外谨慎的态度审核该工具及其建议的用法。然而，一些开发人员出于安全考虑而感到震惊，以至于他们不考虑细节就断然拒绝该建议。正如我的祖母会形容任何同样因胆怯而瘫痪的人那样，“他们会害怕把湿漉漉的孩子放进烘干机里！” 确定 litr8x 是否按广告宣传的那样工作；如果您得出结论它确实如此，请按照指示放心地使用它。
工业级文学性
除了 litr8x 程序之外，本专栏的示例代码还包括一个脚本，该脚本将文学性改造到 grep 实用程序 3.7 版本中。4 此补丁脚本向文件 grep.c 添加了 10 行代码，并添加了一个新的构建脚本，该脚本使用 litr8x 创建文学可执行文件 grep。文学 grep 可以转储一个 tarball，从中可以构建文学 grep，形成图 3 中描述的循环。
图 3 文学执行循环
文学可执行文件可以吐出内部 tarball 的任何子集，而 tarball 又可以包含我们选择的任何内容。例如，文学 grep 可以生成其自身的文档以及其自身的源代码；标准实用程序提取 man 页面
$ grep --dump-txz | xzcat \
| tar xOf - grep-3.7.litr8x/doc/grep.in.1 \
| man -l -
文学可执行文件可以像发出教学视频一样容易。动态链接库的源代码是文学可执行文件可能不应包含的少数内容之一，因为此类库是在运行时选择的。
将零星的东西存储在可执行文件中可以使一切井井有条。当前流行的替代方案是将杂项分散在许多目录中——bin/、lib/、man/、info/ 和其他几个目录。分散会造成混乱，尤其是当同一系统上安装了可执行文件的多个变体时。系统管理员对奥卡姆剃刀的类比敦促我们最大限度地减少必须保持相互协调的位置数量。同样，SPOT 规则通过强制执行单一真相来源来排除不一致和遗漏。要使用软件工件，您必须拥有可执行文件，因此可执行文件是保存工件相关文件的理想位置。
文学性会使二进制文件膨胀，但绝对成本是可以承受的。例如，在我的 Fedora 笔记本电脑上，所有已安装软件包的源代码总大小约为 7 GiB。所有可用软件包——所有内容加上厨房水槽，极少有用户需要或想要——为 84 GiB。如今，一个好的 1TB SSD 的价格可以达到 100 美元，因此我的已安装软件包的源代码的快速存储成本不到一美元——这可能是我有史以来最划算的一美元。存储所有可用源代码的成本不到 10 美元，这对于快速、万无一失的源代码访问来说是一个适中的价格。除了在存储方面轻装上阵之外，文学可执行文件中的 tarball 强加了零运行时开销：现代操作系统按需分页将可执行文件从存储器分页到内存中，因此只有当鸡下蛋时，鸡蛋才会离开存储器。
相关工作与实践
编写简洁的自打印程序或 quine10 自编译语言诞生以来，一直是一项编码挑战和一种幼稚的艺术形式。早在 1970 年代初，学生们就用自打印 FORTRAN 自娱自乐8。Unix 创始人 Ken Thompson 和他的大学同学沉迷于这种消遣；多年后，他以自打印 C 代码开始了图灵奖讲座16。越来越小巧和神秘的 quine 一直是 Obfuscated C 竞赛9 的主要内容，直到 Szymon Rusinkiewicz 用可证明最小的自打印 C 程序：零长度文件，永远结束了这场无聊的军备竞赛14。文学可执行文件将自打印重新用于通用软件和严肃目的。
“无中生有。”
—李尔王
Donald Knuth 提出了文学编程，以使代码对人类更具可读性。他的 WEB 系统允许作者在一个文件中穿插 Pascal 和散文，工具从中提取 .tex 用于排版文档，并提取代码用于编译器；代码提取器将丑陋武器化，以阻止检查和编辑8。精美的打印列表可能会将创造性能量误导到排版装饰上，而牺牲了健全的编码：Douglas McIlroy 指出，文学编程的一个突出的早期展示被极其过度简化了1。Norman Ramsey 的 noweb 系统不再强调精美打印，并从 WEB 的 Pascal 推广到任何编程语言11,12。文学编程被用于多个严肃的编码项目，例如 David Hanson 的 C 库5，但没有像其支持者希望的那样广泛流行。文学可执行文件借鉴了文学编程的最佳思想：将所有内容放在一个文件中。
可重现构建项目旨在“创建从源代码到二进制代码的独立可验证路径”，以确保源代码的安全审计与相应的可执行文件相关13。可重现构建试图使构建系统具有确定性和明确定义（即，保证从基因型到表型的一对一映射）。文学可执行文件的工作方向相反，从可执行文件到源代码，并允许从源代码到可执行文件的一对多映射。
深入挖掘
通过使用 litr8x 的实践经验，您将学会停止担心并喜欢图 3 中的循环依赖关系图。
位
从 https://queue.org.cn/downloads/2022/Drill_Bits_08_example_code.tar.gz 下载示例代码。您将获得图 1 的 litr8x.c 源代码、图 2 的编译/运行脚本以及 grep-文学化脚本。
钻孔
1. pinpoint 您计算机上 grep 实用程序的源代码。向怀疑论者证明您确定的源代码已编译到可执行文件中。
2. 向 litr8x.c 添加安全/健全性检查：检查鸡蛋的大小（在变量 se 中）是否与植入数组的大小（sizeof E，应等于 LITR8X_SIZE）匹配。
3. 按照我的 grep-文学化脚本的示例，将文学性改造到您最喜欢的程序或库中。
4. 为任意 Java 代码实现文学性。
5. 图 1 中的第 13 行是否不吉利？如果 size_t 是四个字节，但文件可以超过 4 GiB 怎么办？我们是否应该 static_assert() size_t 和 off_t 的大小相同？
6. 查看 NetBSD，据说在 NetBSD 上查找源代码比在 GNU/Linux 上更容易。
7. 阅读有关 MacOS 应用程序包和相关概念（例如应用程序目录）的信息。文学可执行文件与将源代码等放置在应用程序包中的替代方案相比如何？
8. 图 2 的标记过程是否冒险？第 3 行的标记是否可能出现在编译后的二进制文件中，而不是预期的植入位置？
9. 证明如果文件大小不受限制，则必须存在一个包含其自身校验和的文本文件。创建这样一个文件；使其尽可能小。
“把你所有的鸡蛋放在一个篮子里，并非常小心地看管那个篮子。”
—Andrew Carnegie
10. 考虑安全性：文学性是否会产生新的漏洞？它能否使攻击者的工作更难？
11. 在 Python 或 Perl 中实现一个“鸡蛋植入器”程序来替换 litr8x。Python 或 Perl 是否使编码更容易或程序更安全？
12. 示例 grep-文学化脚本是 C shell。Tom Christiansen 说 csh 不适合编写脚本2。如果用 Bourne-ish 方言重写此脚本，它会如何改进？
13. 使用 du 实用程序比较鸡蛋植入前后鸡/二进制文件的存储占用空间（要查看差异，您的文件系统必须支持稀疏文件，并且您可能需要 fallocate --dig-holes 来稀疏化编译和植入之间的可执行文件）。
14. 编写一个工具来从鸡中取出鸡蛋，使后者恢复为与其植入前状态完全相同的字节。使用 fallocate --dig-holes 来减少去除鸡蛋后的二进制文件的存储占用空间（需要稀疏文件）。
致谢
gdbm 的作者 Phil Nelson 在我撰写本文之前与我交流了想法，然后审阅了草稿。Programming Pearls 的作者 Jon Bentley 对草稿提供了广泛的反馈。noweb 的作者 Norman Ramsey 对草稿提供了反馈。GNU grep 维护者 Paul Eggert 对示例代码中的 grep-补丁脚本提供了反馈。
参考文献
1. Bentley, J., Knuth, D. E., McIlroy, D. 1986. Programming pearls: A literate program. Communications of the 29(6), 471-483; https://dl.acm.org/doi/pdf/10.1145/5948.315654.
2. Christiansen, T. 1995. Csh programming considered harmful. Internet FAQ Archives; http://www.faqs.org/faqs/unix-faq/shell/csh-whynot/.
3. DiBona, C., Ockman, S., Stone, M., editors. 1999. Open Sources: Voices from the Open Source Revolution. O'Reilly Media.
4. GNU grep. 2022; https://gnu.ac.cn/software/grep/.
5. Hanson, D. R. 1997. C Interfaces and Implementations. Addison-Wesley.
6. Kelly, T. 2021. Crashproofing the original NoSQL key-value store. acmqueue 19(4); https://queue.org.cn/detail.cfm?id=3487353.
7. Kelly, T., Tan, Z.F., Li, J., Volos, H. 2022. Persistent memory allocation: leverage to move a world of software. acmqueue 20(2). https://queue.org.cn/detail.cfm?id=3534855. (Official gawk 5.2 uses my persistent memory allocator: https://ftp.gnu.org/gnu/gawk/gawk-5.2.0.tar.xz.)
8. Knuth, D. E. 1992. Literate Programming. Stanford Center for the Study of Language and Information. (See p. 11 for self-printing programs and p. 140 for weaponized ugliness.)
9. Libes, D. 1993. Obfuscated C and Other Mysteries. Wiley. (See pp. 313–315 for self-printing C program.)
10. Quine (computing). 2022; https://en.wikipedia.org/wiki/Quine_(computing).
11. Ramsey, N. 1994. Literate programming simplified. IEEE Software 11(5); https://www.cs.tufts.edu/~nr/pubs/lpsimp.pdf. (The author cautions: "Avoid the published version; it is littered with misprints.")
12. Ramsey, N. 2022. Noweb—a simple, extensible tool for literate programming; https://www.cs.tufts.edu/~nr/noweb/.
13. Reproducible Builds. 2022; https://reproducible-builds.org/.
14. Rusinkiewicz, S. 1994. The world's smallest self-replicating program. Guaranteed. https://www.ioccc.org/years.html#1994_smr.
15. Stallman, R. M. 2002. Free Software, Free Society. GNU Press; https://gnu.ac.cn/philosophy/fsfs/rms-essays.pdf#page=49.
16. Thompson, K. 1984. Reflections on trusting trust [Turing Award lecture]. Communications of the 27(8), 761-763; https://dl.acm.org/doi/pdf/10.1145/358198.358210.
Terence Kelly ([email protected]) 感谢他的祖母使用“精细”循环。
版权所有 © 2022 归所有者/作者所有。出版权已授权给 。
最初发表于 Queue vol. 20, no. 5—
在 数字图书馆 中评论本文
© 保留所有权利。