一句话：提出 REINAM，用强化学习从符号执行生成的输入中推断概率上下文无关输入文法，无需种子输入。
程序输入文法能够编码合法程序输入的语言，可支撑符号执行、增量调试等任务。但现有文法合成方法常受程序中不可分析代码以及缺少高质量、多样化种子输入的限制，只能覆盖很小的有效输入空间。REINAM 不依赖种子输入，先使用工业符号执行引擎为目标程序生成初始输入，再通过迭代式文法泛化主动生成额外输入，从而推断泛化文法；为在巨大的候选泛化算子空间中高效搜索，该方法将搜索问题建模为强化学习问题。在 11 个真实基准上，REINAM 合成文法的精确率和召回率优于现有最先进方法，基于其文法的模糊测试显著提升有效输入空间覆盖，部分基准甚至能在不降低文法准确率的情况下覆盖整个有效输入空间。
Program input grammars (i.e., grammars encoding the language of valid program inputs) facilitate a wide range of applications in software engineering such as symbolic execution and delta debugging. Grammars synthesized by existing approaches can cover only a small part of the valid input space mainly due to unanalyzable code (e.g., native code) in programs and lacking high-quality and high-variety seed inputs. To address these challenges, we present REINAM, a reinforcement-learning approach for synthesizing probabilistic context-free program input grammars without any seed inputs. REINAM uses an industrial symbolic execution engine to generate an initial set of inputs for the given target program, and then uses an iterative process of grammar generalization to proactively generate additional inputs to infer grammars generalized from these initial seed inputs. To efficiently search for target generalizations in a huge search space of candidate generalization operators, REINAM includes a novel formulation of the search problem as a reinforcement learning problem. Our evaluation on eleven real-world benchmarks shows that REINAM outperforms an existing state-of-the-art approach on precision and recall of synthesized grammars, and fuzz testing based on REINAM substantially increases the coverage of the space of valid inputs. REINAM is able to synthesize a grammar covering the entire valid input space for some benchmarks without decreasing the accuracy of the grammar.
@inproceedings{paperbot5056,
title = {REINAM: reinforcement learning for input-grammar inference},
author = {Zhengkai Wu and Evan Johnson and Wei Yang and Osbert Bastani and Dawn Song and Jian Peng and Tao Xie},
booktitle = {FSE},
year = {2019},
doi = {10.1145/3338906.3338958}
}