Mining Input Grammars with AUTOGRAM

Knowledge about how a program processes its inputs can help to understand the structure of the input as well as the structure of the program. In a JSON value like [1, true, "Alice"], for instance the integer value 1, the boolean value true and the string value "Alice" would be handled by different functions or stored in different variables. Our AUTOGRAM tool uses dynamic tainting to trace the data flow of each input character for a set of sample inputs and identifies syntactical entities by grouping input fragments that are handled by the same functions. The resulting context-free grammar reflects the structure of valid inputs and can be used for reverse engineering of formats and can serve as direct input for test generators. A video demonstrating AUTOGRAM is available at https://youtu.be/Iqym60iWBBk.