Grammar Mutation for Testing Input Parsers
ACM Transactions on Software Engineering and Methodology · 31.05.2025 · 34 (4) · 1-21
DOI: 10.1145/3708517 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Software Engineering and Methodology, online erschienen am 28.04.2025. Verfasst von Bachir Bendrissou und 2 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Union’s Horizon 2020, UK Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
Grammar-based fuzzing is an effective method for testing programs that consume structured inputs, particularly input parsers. However, if the available grammar does not accurately represent the input format, or if the system under test (SUT) does not conform strictly to the grammar, there may be an impedance mismatch between inputs generated via grammars and inputs accepted by the SUT. Even if the SUT has been designed to strictly conform to the grammar, the SUT parser may exhibit vulnerabilities that would only be triggered by slightly invalid inputs. Grammar-based generation, by construction, will not yield such edge case inputs. To overcome these limitations, we present two mutational-based approaches: Gmutator and G+M . Both approaches are built upon Grammarinator , a grammar-based generator. Gmutator applies mutations to the grammar input of Grammarinator , while G+M directly applies byte-level mutations to Grammarinator -generated inputs. To evaluate the effectiveness of these techniques ( Grammarinator , Gmutator , G+M ) in testing programs that parse various input formats, we conducted an experimental evaluation over four different input formats and twelve SUTs (three per input format). Our findings suggest that both Gmutator and G+M excel in generating edge case inputs, facilitating the detection of disparities between input specifications and parser implementations.
Förderung
- European Union’s Horizon 2020
- UK Engineering and Physical Sciences Research Council
Zitieren
APA
Bendrissou, B., Cadar, C., & Donaldson, A. F. (2025). Grammar Mutation for Testing Input Parsers. ACM Transactions on Software Engineering and Methodology, 34(4), 1-21. https://doi.org/10.1145/3708517
Vancouver
Bendrissou B, Cadar C, Donaldson AF. Grammar Mutation for Testing Input Parsers. ACM Transactions on Software Engineering and Methodology. 2025;34(4):1-21. doi:10.1145/3708517
BibTeX
@article{Bendrissou2025,
author = {Bendrissou, Bachir and Cadar, Cristian and Donaldson, Alastair F.},
title = {Grammar Mutation for Testing Input Parsers},
journal = {ACM Transactions on Software Engineering and Methodology},
year = {2025},
volume = {34},
number = {4},
pages = {1--21},
doi = {10.1145/3708517}
}
EUVIMED