A-Str: Acyclic String Constraint Solver withNative Java String API Support
本文提出了一种名为 A-Str 的基于无环自动机的字符串约束求解器，它原生支持 Java String API，能够高效且鲁棒地解决复杂的 Java 验证和动态符号执行基准测试，在处理 Java 特定任务时优于现有工具，同时在标准 SMT-LIB 基准测试中保持竞争力。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在数字世界中，软件验证是一个严谨的过程，旨在证明一个计算机程序将完全按照预期运行，而不会发生崩溃或泄露秘密。为了实现这一目标，工程师们经常使用一种被称为符号执行的技术，该技术不将程序的输入视为固定的数字或单词，而是将其视为可以代表任何可能值的开放式变量。随着程序的运行，系统会追踪这些变量为达到特定点（例如安全检查或关键计算）所必须满足的规则和条件。挑战在于当这些变量是字符串时——即字母和数字的序列。与简单的数学不同，字符串对于如何进行拼接、拆分或比较有着复杂的规则。为了确定程序是否可能进入危险状态，计算机必须解开一个谜题：能否找到特定的单词，使得所有这些规则同时成立？这就是字符串约束求解器的工作，它是一个专门用于处理文本的逻辑引擎。虽然存在通用型的求解器，但它们往往难以应对现代编程语言（如 Java）中那些独特的、复杂的文本操作指令。
博伊西州立大学的研究人员 Nathanael Steven 和 Elena Sherman 开发了一种名为 A-Str 的新工具来解决这一特定的差距。他们的工作聚焦于这样一个事实：该领域使用的标准逻辑工具通常过于僵化，无法处理 Java 程序中执行的全范围文本操作。在 Java 中，程序员可以轻松地反转一个单词、删除空格或检查一个句子是否以另一个句子开头。然而，用于向计算机描述这些问题的标准数学语言并不具备直接处理这些动作的指令。当现有工具试图对这些 Java 命令进行建模时，它们往往不得不使用复杂的递归定义，这会导致运行速度变慢或直接放弃。作者意识到，与其强行将这些复杂的 Java 命令套入标准的模具，不如构建一个能够原生理解 Java 语言的求解器，并采用一种基于有限自动机的方法。在这种语境下，自动机可以被理解为一条字符串可能采取的所有路径的地图；由于研究人员限制了他们的地图为无环图（即不包含循环），系统可以保证始终在合理的时间内完成计算。
A-Str 系统的核心是一个与以往尝试不同的后向传播框架。想象一位侦探正在根据犯罪现场追踪嫌疑人。大多数求解器会先猜测嫌疑人的身份，然后再检查线索是否吻合。然而，A-Str 从最终的线索——即程序结束时必须满足的条件——开始，通过程序中的每一步向后追溯，以查看起始单词必须是什么才能产生该结果。该系统构建了一个程序逻辑的流程图，并将一组可能的字符串向后移动。在每一步中，它都会执行所发生操作的反向操作。如果程序添加了一个字母，求解器就会移除它；如果程序检查了一个单词是否以特定字母开头，求解器就会过滤掉所有不以该字母开头的单词。本文的一个关键创新在于系统如何处理单个操作可能源自多个不同起始点的情况。求解器并没有因此卡住，而是智能地将问题拆分为更小、更易处理的部分，检查每种可能性，直到找到一致的路径或证明不存在这样的路径。
研究人员将 A-Str 与工业界使用的当前最先进工具进行了对比测试，包括 Z3-Noodler、cvc5 和 Ostrich。他们在三种不同的场景下对这个新求解器进行了评估。首先，他们在直接源自真实世界 Java 验证任务的约束上对其进行了测试。在这种环境下，A-Str 表现得异常鲁棒，成功处理了它收到的每一个基准测试。面对复杂的真实 Java 代码时，它避免了其他工具经常遇到的超时或返回“未知”响应的问题。其次，他们在由实际 Java 程序进行动态符号执行生成的基准测试集上对其进行了测试。这些测试涉及更复杂且更多变的字符串操作。在此方面，A-Str 的表现与目前最快的现有求解器 Z3-Noodler 持平，能够高效地完成其他工具难以完成的最难查询。最后，团队在用于比较所有字符串求解器的标准通用基准测试上测试了该求解器。在这个特定类别中，A-Str 虽然具备能力，但竞争力不如那些针对此类通用、抽象问题进行了优化的既有领先工具。
研究结果表明，虽然通用型求解器仍然是抽象理论领域的王者，但在实际的软件验证中，一种专门化的方法要优越得多。通过接受一个限制——即它只解决在预定义长度范围内的问题——研究人员在 Java 程序的特定领域内获得了速度和可靠性方面的显著优势。论文明确反对这样一种观点，即认为一个通用的、单一的求解器可以高效地同时处理通用的数学基准测试和现实世界编程语言中丰富的复杂操作。作者证明，试图使用标准的、通用的逻辑来为 Java 丰富的文本命令建模，往往会导致效率低下和失败。相反，他们展示了通过直接操纵文本底层结构（而不依赖复杂的递归定义）来设计的求解器，可以更轻松地应对真实程序的约束。这项研究证实，对于验证 Java 软件这一特定任务，一个旨在理解其原生操作的工具不仅是一个有益的替代方案，更是应对现代代码复杂性而不至于陷入停滞的必然演进。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。