通过符号解析从代码中推断输入语法

《ACM Transactions on Software Engineering and Methodology》：Inferring Input Grammars from Code with Symbolic Parsing

符号解析技术自动提取递归下降解析器输入语法，通过限制递归调用路径和生成语法扩展替代方案，解决复杂解析器分析难题，准确率达99-100%且无需样本输入。

　　

摘要

为软件系统生成有效的测试输入时，这些输入必须是有效的（valid），否则它们会被直接拒绝而无法实现实际的功能。在缺乏输入语言规范的情况下，常见的测试生成技术依赖于样本输入，这些样本输入被抽象成相应的语法，并在测试覆盖率的指导下进行优化。然而，如果样本输入未能涵盖输入语言的所有特征，那么随机生成这些特征的概率就非常低。

在这项工作中，我们提出了一种首次实现的方法，能够符号化且自动地从递归下降解析器的代码中提取输入语法。到目前为止，由于解析器的复杂性，这种符号化分析一直极具挑战性，甚至难以实现。我们实现的符号化解析技术通过以下方式克服了这些挑战：（1）将每个解析器函数parse_elem()与一个非终结符关联起来；（2）限制递归调用和循环迭代次数，使得对parse_elem()的符号化分析只需考虑有限的路径；（3）为每个路径生成的扩展选项。由于符号化解析是完全静态的，因此不需要初始输入数据；同时，它能够有效防止路径爆炸问题，从而适用于复杂的解析器。

我们的评估表明，符号化解析具有很高的准确性。应用于TINY-C或JSON等复杂语言的解析器时，我们的STALAGMITE实现能够以99–100%的准确率提取语法，这一成果显著优于现有技术，而且该方法仅依赖于程序代码，无需任何输入样本。生成的语法能够覆盖所有输入范围，从而支持全面的测试生成、逆向工程和文档编写。