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, high-variety, and high-quantity seed inputs. To address these challenges, we present REINAM, a reinforcement-learning approach for synthesizing a probabilistic context-free program-input grammars without any seed input. REINAM includes an industrial symbolic execution engine to generate an initial set of inputs for the given target program, and includes an iterative process of grammar generalization to proactively generate additional inputs in order to infer grammars generalized from the 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 the problem of reinforcement learning. Our evaluation results on five real-world subjects show 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 valid input space. REINAM is able to synthesize a grammar covering the whole valid input space for some subjects without decreasing accuracy of the grammar.

Publication
In the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering.
Date