Input Data Description using Stratified Context-Free Grammar

Taehwan Kim, Damho Lee, Hyunji Seo, Changwoo Pyo

http://doi.org/10.5626/JOK.2019.46.4.321

This paper defines Data Description Language (DDL) based on a context-free grammar that describes syntactic characteristics of input from multiple input files or devices. Each input file or device has its input description, which is connected to its upper-level input description to form a hierarchy. We also developed a method generating input data using DDL. To demonstrate DDL’s utility, we have compared our method with two others using the metrics of basic block coverage and input generation times. For 37 programs of Coreutils, our method generated valid input faster by O(10³) times, and the coverage was higher by 25.44% than KLEE. Compared to the method of single context-free grammars, ours took 1.52 times, but basic block coverage was larger by 6.59%. Currently, we use DDL for generating regular input for dynamic control-flow analysis.