TreeVada is a deterministic grammar inference tool. Given a black-box parser and example programs, TreeVada can infer high quality grammar. TreeVada adapts the tree generalization via bubble and merge technique from Arvada.

Reproducibility

Pull the Docker image from here to reproduce the results reported in our paper. The image contains all the seed inputs used in our experiments. You need to have Docker installed in your system.

docker pull marefin/treevada:v2
docker run --rm -it marefin/treevada:v2

/treevada-artifact/Readme.md contains a detailed overview of the directory structure and how to run the scripts to reproduce the results.

Building

Requires at least python 3.6. Install the following two packages via pip to make sure everything runs:

$ pip3 install lark-parser tqdm

Running TreeVada

Running TreeVada is analogous to running Arvada. The following section is adopted from their repository. Suppose you have a directory containing a set of examples, TRAIN_DIR, and an oracle for a valid example, ORACLE_CMD. The restrictions on ORACLE_CMD are as follows:

• ORACLE_CMD filename should run the oracle on the file with name filename
• ORACLE_CMD filename should return 0 if the example in filename is valid, and an exit code greater than 0 if it is invalid.

You can then run TreeVada via:

$ python3 search.py external ORACLE_CMD TRAIN_DIR LOG_FILE

this will store the learned grammar as a pickled dictionary in LOG_FILE.gramdict, and some information about training in LOG_FILE.

If you also have a held-out test set in TEST_DIR, you can evaluate the precision and recall of the mined grammar with the utility eval.py. This utility also handily prints out the unpickled grammar to LOG_FILE.eval file. The provided LOG_FILE must match one generated by search.py, as this utility looks for LOG_FILE.gramdict.

$ python3 eval.py external [-n PRECISION_SET_SIZE] ORACLE_CMD TEST_DIR LOG_FILE

The optional PRECISION_SET_SIZE argument specifies how many inputs to sample from the mined grammar to evaluate precision. It is 1000 by default.

Of course, if you do not have a held-out test set, you can still evaluate the precision of the mined grammar by using your training directory as test:

$ python3 eval.py external [-n PRECISION_SET_SIZE] ORACLE_CMD TRAIN_DIR LOG_FILE

The Recall should be 1.0 in this case.

Citation

If you find TreeVada useful in your research, please cite our work:

@inproceedings{arefin2024fast,
  title={Fast Deterministic Black-box Context-free Grammar Inference},
  author={Arefin, Mohammad Rifat and Shetiya, Suraj and Wang, Zili and Csallner, Christoph},
  booktitle={Proceedings of the IEEE/ACM 46th International Conference on Software Engineering},
  pages={1--12},
  year={2024}
}

Acknowledgements

TreeVada is built upon its predecessor tool Arvada. Arvada is licensed under MIT license, please see the Arvada License for details. We thank the developers @carolemieux and @neil-kulkarni for their pioneering work.