Mining input grammars from dynamic control flow
Mining input grammars from dynamic control flow
复制标题
DOI：
10.1145/3368089.3409679
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Rahul Gopinath;Björn Mathis;A. Zeller
中科院分区：
文献类型：
--
作者：
Rahul Gopinath;Björn Mathis;A. Zeller
程序的关键属性之一是其输入规范。拥有正式的输入规范对于漏洞分析、逆向工程、软件测试、克隆检测或重构等领域至关重要。不幸的是，典型程序的准确输入规范通常不可用或已经过时。在本文中，我们提出了一种通用算法，该算法采用程序和一小组样本输入，并自动推断出捕获程序输入语言的可读上下文无关语法。我们仅通过观察输入解析器不同位置的输入字符的访问来推断句法输入结构。这适用于所有基于堆栈的递归下降输入解析器，包括解析器组合器，并且完全无需程序特定的启发法即可工作。我们的 Mimid 原型为各种评估主题生成了准确且可读的语法，包括 JSON、TinyC 和 JavaScript 等复杂语言。
One of the key properties of a program is its input specification. Having a formal input specification can be critical in fields such as vulnerability analysis, reverse engineering, software testing, clone detection, or refactoring. Unfortunately, accurate input specifications for typical programs are often unavailable or out of date. In this paper, we present a general algorithm that takes a program and a small set of sample inputs and automatically infers a readable context-free grammar capturing the input language of the program. We infer the syntactic input structure only by observing access of input characters at different locations of the input parser. This works on all stack based recursive descent input parsers, including parser combinators, and works entirely without program specific heuristics. Our Mimid prototype produced accurate and readable grammars for a variety of evaluation subjects, including complex languages such as JSON, TinyC, and JavaScript.