Program Behavior Discovery and Verification: A Graph Grammar Approach

Discovering program behaviors and functionalities can ease program comprehension and verification. Existing program analysis approaches have used text mining algorithms to infer behavior patterns or formal models from program execution. When one tries to identify the hierarchical composition of a program behavior at different abstraction levels, textual descriptions are not informative and expressive enough. To address this, we present a semi-automatic graph grammar approach to retrieving the hierarchical structure of the program behavior. The hierarchical structure is built on recurring substructures in a bottom-up fashion. We formulate the behavior discovery and verification problem as a graph grammar induction and parsing problem, i.e., automatically iteratively mining qualified patterns and then constructing graph rewriting rules. Furthermore, using the induced grammar to parse the behavioral structure of a new program could verify if the program has the same behavioral properties specified by the grammar.