CHC-based Automated Verification of WebAssembly Programs
本文提出了一种针对 WebAssembly 子集的自动化静态验证方法，该方法利用约束 Horn 子句，通过基于类型的过滤有效地处理间接函数调用，并通过控制流分析摘要来管理大型恐慌处理程序（panic handlers）。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，互联网是一座巨大且繁忙的城市，其中的每一栋建筑都是一个网站。多年来，这些建筑都是按照一套特定的、沉重的蓝图建造的，虽然保证了安全，但有时建造速度较慢。随后，一种名为 WebAssembly 的新型高效语言问世了。它就像是一个通用的、高速的无人机配送系统，可以在互联网的任何地方飞行，运载着运行游戏、工具和应用程序的高性能代码，直接在你的浏览器中运行。因为这些无人机既快速又强大，所以我们需要确保它们永远不会撞到建筑物，或者把货物掉落在错误的地方。这就是“验证”（verification）的任务——这是一个高级词汇，指的是在程序运行之前，通过数学方法证明其安全性。
为了实现这一点，计算机科学家经常使用一种名为“可满足性求解器”（Satisfiability Solver）的工具。你可以把这个求解器想象成一位超级聪明的侦探，他可以通过观察一套规则，瞬间判断出某种场景是可能发生的还是不可能发生的。如果规则说“无人机必须在空中”且“无人机必须在地面上”同时成立，侦探就会知道这是一个矛盾，因此计划是不安全的。这篇论文正是通过教导这位侦探如何理解 WebAssembly 特有的、棘手的规则，特别是涉及间接调用其他函数以及处理大规模错误信息的部分。
变形调用之谜
作者们——来自东京大学的八木明久（Akihisa Yagi）、坂寄健（Ken Sakayori）和小林直树（Naoki Kobayashi）——面临着一个复杂的谜题。WebAssembly 程序就像一个巨大的图书馆，书（函数）可以动态地从书架上取下。有时，代码并不会说“打开 A 书”；相反，它会说“打开第 5 号书架上的书”。这被称为间接函数调用（indirect function call）。
问题在于，如果你试图检查图书馆里的每一本书，看看第 5 号书架上可能有什么，侦探（求解器）就会不堪重负。这就像是试图检查一百万把锁的所有可能组合，以找到正确的钥匙。幼稚的做法是列出所有可能性，但这会产生堆积如山的文书工作，任何计算机都无法在合理的时间内解决。
作者们的解决方案是扮演一名非常严格的图书管理员。他们意识到 WebAssembly 有一条规则：你只能从书架上取出一本与你寻找的特定“类型”（genre/type）相匹配的书。因此，他们的这种方法不再检查图书馆里的每一本书，而是查看调用点所要求的“类型”，并过滤掉所有不符合要求的书。这极大地缩小了候选名单，使侦探的工作变得轻松得多。他们还加入了第二个技巧：如果图书馆的书架是锁定且永不变化的（只读），他们就可以预先计算出每本书的具体位置，从而将一个复杂的谜题转化为简单的“如果……那么……”规则。
巨大的恐慌按钮
第二个挑战是“恐慌处理器”（panic handler）。想象一个程序，当它出错时，它不仅仅是停止运行，而是会启动一段长达 10,000 步的演说，详细解释到底出了什么错，甚至包括诊断图表和错误代码，最后才最终放弃。在 WebAssembly 中，这些恐慌处理器是当事情出错时触发的巨大代码块。
对于安全检查器来说，这些宏大的演说是一种干扰。唯一重要的事情是程序最终能安全地停止运行（到达“不可达”指令）。那段用于构建错误信息的漫长且曲折的路径实际上并不会改变程序正在崩溃的事实。然而，如果侦探试图追踪那 10,000 步演说的每一个步骤，就会陷入泥潭。
作者引入了一种“摘要化”（summarization）技术。他们意识到，如果一段代码仅仅是为了导致崩溃，那么他们可以略过中间环节。他们利用控制流分析来识别这些漫长且曲折的路径，并将它们替换为一个简单的快捷方式：“如果你进入这个房间，你最终会崩溃。”这就像是告诉导游：“跳过大堂里那 50 分钟的历史讲座吧；直接告诉我们出口被封锁了就行。”这使得验证工作能够专注于关键的安全问题，而不至于迷失在错误信息的噪音之中。
结果：一项进行中的工作
为了测试他们的想法，团队构建了一个名为 WASMVERIFIER 的原型工具。他们向其输入了 90 个不同的程序，其中包括一些用 Rust 和 C 编写的程序，并要求它证明这些程序的安全性。
结果是令人鼓舞但并不完美的。通过使用两种不同的侦探求解器（Z3 Spacer 和 Eldarica），该工具成功验证或证伪了大约 54 到 56 个程序的安全性。然而，在约 20 到 22 个程序上，它遇到了瓶颈，出现了“超时”（timeout）或内存不足的问题。在大约 11 到 12 个案例中，它发出了“误报”（false alarm），即认为程序是不安全的，而实际上程序是正常的。作者解释说，这些误报是因为他们的工具必须将某些不支持的指令替换为“崩溃”占位符，这使得安全检查变得过于谨慎。
论文指出，虽然这种方法是实现全自动安全检查迈出的有力一步，但它目前还不是一根“魔杖”。作者提到，该方法仍在不断完善，特别是在如何处理复杂的位运算（bit-vectors）以及如何处理目前尚无法完全理解的指令方面。他们怀疑该方法是可靠且完备的，但尚未编写其正式的数学证明，这仍是未来的任务。
简而言之，这篇论文表明，通过更聪明地过滤间接调用，以及对混乱的错误处理进行摘要化处理，我们可以使 WebAssembly 的自动化安全检查变得更加实用。这是一个坚实的基石，但这位侦探仍需要更多的训练才能破解所有的案件。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。