@inproceedings{c1590e94a110469abb91876473209cbc,
title = "REINAM: Reinforcement learning for input-grammar inference",
abstract = "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.",
keywords = "Dynamic symbolic execution, Fuzzing, Grammar synthesis, Reinforcement learning",
author = "Zhengkai Wu and Evan Johnson and Wei Yang and Osbert Bastani and Dawn Song and Jian Peng and Tao Xie",
note = "Publisher Copyright: {\textcopyright} 2019 ACM.; 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2019 ; Conference date: 26-08-2019 Through 30-08-2019",
year = "2019",
month = aug,
day = "12",
doi = "10.1145/3338906.3338958",
language = "English (US)",
series = "ESEC/FSE 2019 - Proceedings of the 2019 27th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering",
publisher = "Association for Computing Machinery",
pages = "488--498",
editor = "Sven Apel and Marlon Dumas and Alessandra Russo and Dietmar Pfahl",
booktitle = "ESEC/FSE 2019 - Proceedings of the 2019 27th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering",
address = "United States",
}