{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T23:19:22Z","timestamp":1768778362262,"version":"3.49.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T00:00:00Z","timestamp":1740355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62161146003"],"award-info":[{"award-number":["62161146003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Reducing test inputs that trigger bugs is crucial for efficient debugging. Delta debugging is the most popular approach for this purpose. When test inputs need to conform to certain specifications, existing delta debugging practice encounters a validity problem: it blindly applies reduction rules, producing a large number of invalid test inputs that do not satisfy the required specifications. This overall diminishing effectiveness and efficiency becomes even more pronounced when the specifications extend beyond syntactical structures. Our key insight is that we should leverage input generators, which are aware of these specifications, to generate valid reduced inputs, rather than straightforwardly performing reduction on test inputs. In this article, we propose a generator-based delta debugging method, namely GReduce, which derives validity-preserving reducers. Specifically, given a generator and its execution, demonstrating how the bug-inducing test input is generated, GReduce searches for other executions on the generator that yield reduced, valid test inputs. The evaluation results on five benchmarks (i.e., graphs, DL models, JavaScript programs, SymPy, and algebraic data types) show that GReduce substantially outperforms state-of-the-art syntax-based reducers including Perses and T-PDD, and also outperforms QuickCheck, SmartCheck, as well as the state-of-the-art choice-sequence-based reducer Hypothesis, demonstrating the effectiveness, efficiency, and versatility of GReduce.<\/jats:p>","DOI":"10.1145\/3705305","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T16:31:46Z","timestamp":1734971506000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Validity-Preserving Delta Debugging via Generator Trace Reduction"],"prefix":"10.1145","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-5291-7880","authenticated-orcid":false,"given":"Luyao","family":"Ren","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2565-7769","authenticated-orcid":false,"given":"Xing","family":"Zhang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8348-5232","authenticated-orcid":false,"given":"Ziyue","family":"Hua","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7651-9560","authenticated-orcid":false,"given":"Yanyan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3000-0795","authenticated-orcid":false,"given":"Xiao","family":"He","sequence":"additional","affiliation":[{"name":"University of Science and Technology Beijing, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8991-747X","authenticated-orcid":false,"given":"Yingfei","family":"Xiong","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6731-216X","authenticated-orcid":false,"given":"Tao","family":"Xie","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/93548.93576"},{"key":"e_1_3_2_3_2","unstructured":"Tianqi Chen Thierry Moreau Ziheng Jiang Lianmin Zheng Eddie Q. Yan Haichen Shen Meghan Cowan Leyuan Wang Yuwei Hu Luis Ceze et al. 2018. TVM: An automated end-to-end optimizing compiler for deep learning. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201918). Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.) USENIX Association 578\u2013594. Retrieved from https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00071"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"e_1_3_2_6_2","unstructured":"difflib. 2023. Difflib\u2014helpers for computing deltas. Retrieved February 1 2024 from https:\/\/docs.python.org\/3\/library\/difflib.html"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454092"},{"key":"e_1_3_2_8_2","unstructured":"The Python Software Foundation. 2024. Ast\u2014abstract syntax trees. Retrieved July 1 2024 from https:\/\/docs.python.org\/3\/library\/ast.html"},{"key":"e_1_3_2_9_2","unstructured":"GCC. 2022. How to minimize Test cases for bugs. Retrieved February 1 2024 from https:\/\/gcc.gnu.org\/bugs\/minimize.html"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3607842"},{"key":"e_1_3_2_11_2","unstructured":"Google. 2023. Google closure compiler. Retrieved February 1 2024 from https:\/\/github.com\/google\/closure-compiler"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2784769"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510092"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/swf.41"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3624007.3624056"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243838"},{"key":"e_1_3_2_17_2","first-page":"445","article-title":"Fuzzing with code fragments","author":"Holler Christian","year":"2012","unstructured":"Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with code fragments. In 21st USENIX Security Symposium (USENIX Security \u201912), 445\u2013458.","journal-title":"21st USENIX Security Symposium (USENIX Security \u201912)"},{"key":"e_1_3_2_18_2","unstructured":"Paul Holser. 2023. junit-quickcheck: Property-based testing JUnit-style. Retrieved February 1 2024 from https:\/\/github.com\/pholser\/junit-quickcheck"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598046"},{"key":"e_1_3_2_20_2","unstructured":"IBM. 2017. The T. J. Watson libraries for analysis. Retrieved February 1 2024 from http:\/\/wala.sourceforge.net\/"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065016"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338956"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454091"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90054-3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510628"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009868"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428264"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2020.13"},{"key":"e_1_3_2_30_2","unstructured":"Esben Sparre Andreasen Martin Torp. 2023. JS Delta. Retrieved February 1 2024 from https:\/\/github.com\/wala\/jsdelta"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381449"},{"key":"e_1_3_2_32_2","unstructured":"Mircrosoft. 2017. Open neural network exchange. Retrieved February 1 2024 from https:\/\/onnx.ai\/"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1134285.1134307"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510182"},{"key":"e_1_3_2_35_2","first-page":"8","volume-title":"11th International Workshop on Satisfiability Modulo Theories (SMT)","author":"Niemetz Aina","year":"2013","unstructured":"Aina Niemetz and Armin Biere. 2013. DdSMT: A Delta debugger for the SMT-LIB v2 format. In 11th International Workshop on Satisfiability Modulo Theories (SMT), 8\u20139."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293882.3330576"},{"key":"e_1_3_2_37_2","first-page":"1","article-title":"The definitive ANTLR 4 reference","author":"Parr Terence","year":"2013","unstructured":"Terence Parr. 2013. The definitive ANTLR 4 reference. The Definitive ANTLR 4 Reference (2013), 1\u2013326.","journal-title":"The Definitive ANTLR 4 Reference"},{"key":"e_1_3_2_38_2","unstructured":"Terence Parr. 2023. ANTLR v4. Retrieved February 1 2024 from https:\/\/github.com\/antlr\/antlr4"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2633357.2633365"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380399"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254104"},{"key":"e_1_3_2_42_2","unstructured":"Luyao Ren. 2023. Project website. Retrieved February 1 2024 from https:\/\/github.com\/GReduce\/GReduce"},{"key":"e_1_3_2_43_2","unstructured":"Luyao Ren Ziheng Wang Yingfei Xiong Li Zhang Guoyue Jiang and Tao Xie. 2023. Effective random test generation for deep learning compilers. arXiv:2302.00842. Retrieved form https:\/\/arxiv.org\/abs\/2302.00842"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2088456.1863525"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180236"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00072"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468625"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE59848.2023.00060"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.23"},{"key":"e_1_3_2_50_2","volume-title":"Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method","author":"Weiser Mark David","year":"1979","unstructured":"Mark David Weiser. 1979. Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method. University of Michigan."},{"key":"e_1_3_2_51_2","unstructured":"Wikipedia. 2023. Instrumentation (computer programming). Retrieved February 1 2024 from https:\/\/en.wikipedia.org\/wiki\/Instrumentation_(computer_programming)"},{"key":"e_1_3_2_52_2","unstructured":"Wikipedia. 2023. Shortlex Order. Retrieved February 1 2024 from https:\/\/en.wikipedia.org\/wiki\/Shortlex_order"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375611"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3690631"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586049"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48166-4_16"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.988498"},{"key":"e_1_3_2_59_2","unstructured":"Mengxiao Zhang Yongqiang Tian Zhenyang Xu Yiwen Dong Shin Hwei Tan and Chengnian Sun. 2023. Lampr: Boosting the effectiveness of language-generic program reduction via large language models. arXiv:2312.13064. Retrieved from https:\/\/arxiv.org\/abs\/2312.13064"},{"key":"e_1_3_2_60_2","unstructured":"Mengxiao Zhang Zhenyang Xu Yongqiang Tian Xinru Cheng and Chengnian Sun. 2024. Deep dive Into probabilistic delta debugging: Insights and simplifications. arXiv:2408.04735. Retrieved from https:\/\/arxiv.org\/abs\/2408.04735"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2019.2919823"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3705305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3705305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:02Z","timestamp":1750295882000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3705305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,24]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3705305"],"URL":"https:\/\/doi.org\/10.1145\/3705305","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,24]]},"assertion":[{"value":"2024-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}