CISPA
Browse

"Synthesizing Input Grammars": A Replication Study

Download (475.35 kB)
conference contribution
posted on 2023-11-29, 18:20 authored by Bachir Bendrissou, Rahul Gopinath, Andreas ZellerAndreas Zeller
When producing test inputs for a program, test generators ("fuzzers") can greatly profit from grammars that formally describe the language of expected inputs. In recent years, researchers thus have studied means to _recover_ input grammars from programs and their executions. The GLADE algorithm by Bastani et al., published at PLDI 2017, was the first black-box approach to claim context-free approximation of input specification for non-trivial languages such as XML, Lisp, URLs, and more. Prompted by recent observations that the GLADE algorithm may show lower performance than reported in the original paper, we have reimplemented the Glade algorithm from scratch. Our evaluation confirms that the effectiveness score (F1) reported in the GLADE paper is overly optimistic, and in some cases, based on the wrong language. Furthermore, GLADE fares poorly in several real-world languages evaluated, producing grammars that spend megabytes to enumerate inputs.

History

Preferred Citation

Bachir Bendrissou, Rahul Gopinath and Andreas Zeller. "Synthesizing Input Grammars": A Replication Study. In: ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2022.

Primary Research Area

  • Threat Detection and Defenses

Name of Conference

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Legacy Posted Date

2022-04-14

Open Access Type

  • CC

BibTeX

@inproceedings{cispa_all_3607, title = ""Synthesizing Input Grammars": A Replication Study", author = "Bendrissou, Bachir and Gopinath, Rahul and Zeller, Andreas", booktitle="{ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC