{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T19:10:24Z","timestamp":1782846624172,"version":"3.54.5"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"FSE","license":[{"start":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T00:00:00Z","timestamp":1782777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>We present RSFuzz, a new technique to enhance grammar-based fuzzing by reducing the generation of coverage-equivalent inputs during testing. Grammar-based fuzzers apply production rules from a given grammar (e.g., forming a derivation tree) to generate well-structured inputs for the target program. However, a key limitation is that many existing fuzzers still produce a large number of \u201dcoverage-equivalent\u201d inputs\u2014those that revisit already explored program paths\u2014thereby restricting their ability to uncover new bugs and improve coverage. To address this issue, RSFuzz automatically identifies recurrent sequences of production rules that lead to coverage-equivalent inputs and prevents their reuse during fuzzing. A key challenge lies in the large number of coverage-equivalent input groups, each with many inputs and corresponding derivation trees, making it difficult to identify underlying recurrent sequences. RSFuzz tackles this challenge with a customized algorithm that iteratively groups coverage-equivalent inputs, selects promising groups, and extracts recurrent sequences by abstracting derivation trees based on accumulated data while running any grammar-based fuzzer. We integrated RSFuzz with existing random, probabilistic, and grammar-coverage based fuzzers and evaluated it on 12 real-world programs using JavaScript, JSON, CSV, and Markdown input formats. Experimental results show that incorporating RSFuzz into the three fuzzers detects 121, 46, and 17 additional crashes with distinct stack traces, increases line coverage by 6.0%, 4.8%, and 3.0%, and reduces duplicate-coverage input generation by 23.3%, 28.7% and 14.9%, respectively, compared to their performance without RSFuzz.<\/jats:p>","DOI":"10.1145\/3808210","type":"journal-article","created":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T17:06:14Z","timestamp":1782839174000},"page":"4622-4643","source":"Crossref","is-referenced-by-count":0,"title":["Reducing Coverage-Equivalent Inputs in Grammar-Based Fuzzing by Avoiding Recurrent Rule Sequences"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5502-7520","authenticated-orcid":false,"given":"Jaehan","family":"Yoon","sequence":"first","affiliation":[{"name":"Sungkyunkwan University, Suwon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9192-6762","authenticated-orcid":false,"given":"Yunji","family":"Seo","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1900-7654","authenticated-orcid":false,"given":"Hakjoo","family":"Oh","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4697-8536","authenticated-orcid":false,"given":"Sooyoung","family":"Cha","sequence":"additional","affiliation":[{"name":"Sungkyunkwan University, Suwon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jsish-2.0 (77.4K) [11 19] JSON Genson-1.4 (4.8K) [10 17 18 37]"},{"key":"e_1_2_1_2_1","unstructured":"Rhino-1.7.10 (42.0K) [10 27 35 37 44] Gson-2.8.5 (4.4K) [10 17 20 37]"},{"key":"e_1_2_1_3_1","unstructured":"JerryScript-2.4.0 (33.4K) [11 19 21 31 43 44] Argo-5.4 (1.5K) [10 17 18 37]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304187"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2019.23412"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062349"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3663529.3663790"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978428"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.400568"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Leonardo De Moura and Nikolaj Bj\u00f8rner. 2008. Z3: An Efficient SMT Solver (TACAS'08\/ETAPS'08). 337-340.","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_13_1","volume-title":"International Symposium on Search Based Software Engineering. 105-120","author":"Eberlein Martin","year":"2020","unstructured":"Martin Eberlein, Yannic Noller, Thomas Vogel, and Lars Grunske. 2020. Evolutionary grammar-based fuzzing. In International Symposium on Search Based Software Engineering. 105-120."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680389"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001460.3001507"},{"key":"e_1_2_1_16_1","volume-title":"14th USENIX Workshop on Offensive Technologies (WOOT 20)","author":"Fioraldi Andrea","year":"2020","unstructured":"Andrea Fioraldi, Dominik Maier, Heiko Ei\u00dffeldt, and Marc Heuse. 2020. AFL++ : Combining Incremental Steps of Fuzzing Research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2017.8115618"},{"key":"e_1_2_1_18_1","volume-title":"European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE).","author":"Gopinath Rahul","year":"2020","unstructured":"Rahul Gopinath, Bj\u00f6rn Mathis, and Andreas Zeller. 2020. Mining Input Grammars from Dynamic Control Flow. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE)."},{"key":"e_1_2_1_19_1","volume-title":"CLIFuzzer: Mining Grammars for Command-Line Invocations. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE).","author":"Gupta Abhilash","year":"2022","unstructured":"Abhilash Gupta, Rahul Gopinath, and Andreas Zeller. 2022. CLIFuzzer: Mining Grammars for Command-Line Invocations. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.60882\/cispa.24612432.v1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00027"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484823"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460319.3464795"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3278186.3278193"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2362793.2362831"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970321"},{"key":"e_1_2_1_27_1","first-page":"437","volume-title":"Proceedings of the 2014 International Symposium on Software Testing and Analysis (ISSTA'14)","author":"Just Ren\u00e9","unstructured":"Ren\u00e9 Just, Darioush Jalali, and Michael D. Ernst. 2014. Defects4J: A Database of Existing Faults to Enable Controlled Testing Studies for Java Programs. In Proceedings of the 2014 International Symposium on Software Testing and Analysis (ISSTA'14). 437-440."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3713081.3731736"},{"key":"e_1_2_1_29_1","first-page":"138","volume-title":"Search-Based Software Engineering: 6th International Symposium (SSBSE '14)","author":"Kifetew Fitsum Meshesha","year":"2014","unstructured":"Fitsum Meshesha Kifetew, Roberto Tiella, and Paolo Tonella. 2014. Combining stochastic grammars and genetic programming for coverage testing at the system level. In Search-Based Software Engineering: 6th International Symposium (SSBSE '14). 138-152."},{"key":"e_1_2_1_30_1","volume-title":"Generating valid grammar-based test inputs by means of genetic programming and annotated grammars. Empirical Software Engineering","author":"Kifetew Fitsum Meshesha","year":"2017","unstructured":"Fitsum Meshesha Kifetew, Roberto Tiella, and Paolo Tonella. 2017. Generating valid grammar-based test inputs by means of genetic programming and annotated grammars. Empirical Software Engineering (2017), 928-961."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Fitsum meshesha Kifetew Roberto Tiella and Paolo Tonella. 2017. Generating Valid Grammar-Based Test Inputs by Means of Genetic Programming and Annotated Grammars. Empirical Softw. Engg. (2017) 928-961.","DOI":"10.1007\/s10664-015-9422-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364452.3364455"},{"key":"e_1_2_1_33_1","first-page":"2613","volume-title":"Montage: A Neural Network Language Model-Guided JavaScript Engine Fuzzer. In 29th USENIX Security Symposium (USENIX Security '20)","author":"Lee Suyoung","year":"2020","unstructured":"Suyoung Lee, HyungSeok Han, Sang Kil Cha, and Sooel Son. 2020. Montage: A Neural Network Language Model-Guided JavaScript Engine Fuzzer. In 29th USENIX Security Symposium (USENIX Security '20). 2613-2630."},{"key":"e_1_2_1_34_1","volume-title":"Deity: Finding Deep Rooted Bugs in JavaScript Engines. In 2019 IEEE 19th International Conference on Communication Technology (ICCT). IEEE, 1585-1594","author":"Lin Hongyang","year":"2019","unstructured":"Hongyang Lin, Junhu Zhu, Jianshan Peng, and Dixia Zhu. 2019. Deity: Finding Deep Rooted Bugs in JavaScript Engines. In 2019 IEEE 19th International Conference on Communication Technology (ICCT). IEEE, 1585-1594."},{"key":"e_1_2_1_35_1","volume-title":"MOPT: Optimized Mutation Scheduling for Fuzzers. In 28th USENIX Security Symposium (USENIX Security '19)","author":"Lyu Chenyang","year":"2019","unstructured":"Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and Raheem Beyah. 2019. MOPT: Optimized Mutation Scheduling for Fuzzers. In 28th USENIX Security Symposium (USENIX Security '19). 1949-1966."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510120"},{"key":"e_1_2_1_37_1","first-page":"1224","volume-title":"2020 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE '20)","author":"Olsthoorn Mitchell","year":"2020","unstructured":"Mitchell Olsthoorn, Arie van Deursen, and Annibale Panichella. 2020. Generating highly-structured input data by combining search-based testing and grammar-based fuzzing. In 2020 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE '20). 1224-1228."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293882.3330576"},{"key":"e_1_2_1_39_1","volume-title":"Proc. ACM Program. Lang.","author":"Park Jiwon","year":"2021","unstructured":"Jiwon Park, Dominik Winterer, Chengyu Zhang, and Zhendong Su. 2021. Generative Type-Aware Mutation for Testing SMT Solvers. Proc. ACM Program. Lang. (2021)."},{"key":"e_1_2_1_40_1","volume-title":"Inputs From Hell: Learning Input Distributions for Grammar-Based Test Generation","author":"Soremekun Ezekiel","year":"2022","unstructured":"Ezekiel Soremekun, Esteban Pavese, Nikolas Havrikov, Lars Grunske, and Andreas Zeller. 2022. Inputs From Hell: Learning Input Distributions for Grammar-Based Test Generation. IEEE Transactions on Software Engineering (2022), 1138-1153."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3540250.3549139"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3631520"},{"key":"e_1_2_1_43_1","unstructured":"JaCoCo Team. 2024. https:\/\/github.com\/jacoco\/jacoco."},{"key":"e_1_2_1_44_1","volume-title":"A tool for measuring coverage","year":"2021","unstructured":"Gcov. A tool for measuring coverage. 2021. https:\/\/gcc.gnu.org\/onlinedocs\/gcc\/Gcov.html."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/SP.2017.23","volume-title":"2017 IEEE Symposium on Security and Privacy (S&P '17)","author":"Wang Junjie","year":"2017","unstructured":"Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2017. Skyfire: Data-driven seed generation for fuzzing. In 2017 IEEE Symposium on Security and Privacy (S&P '17). 579-594."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2019.00081"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/NaNA51271.2020.00071"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338958"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460319.3464803"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3728915"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T18:28:23Z","timestamp":1782844103000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,30]]},"references-count":50,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3808210"],"URL":"https:\/\/doi.org\/10.1145\/3808210","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,30]]}}}