{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T21:20:07Z","timestamp":1787520007772,"version":"build-2736575974"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:00:00Z","timestamp":1775779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2024YFF0908003"],"award-info":[{"award-number":["2024YFF0908003"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62172429"],"award-info":[{"award-number":["62172429"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62032024"],"award-info":[{"award-number":["62032024"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62372162"],"award-info":[{"award-number":["62372162"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,4,10]]},"abstract":"<jats:p>\n                    Symbolic execution faces the challenge of generating valid inputs when analyzing the program with complex input formats. Token-based symbolic execution can partially tackle this challenge but is still doomed by the difficulty of passing input checking and failing to analyze the code after input checking. We propose\n                    <jats:sc>Lase<\/jats:sc>\n                    , an online input grammar synthesis aided symbolic execution method, to generate valid inputs for improving the effectiveness of symbolic execution. Inside\n                    <jats:sc>Lase<\/jats:sc>\n                    , we propose an input grammar-oriented search strategy and a token-level grammar synthesis method. The search strategy selects the paths to cover more syntax rules in priority. The token-level grammar synthesis improves the synthesized grammar\u2019s precision and completeness while ensuring efficiency. The experimental results on real-world parsing programs with complex input grammars demonstrate that\n                    <jats:sc>Lase<\/jats:sc>\n                    can improve the coverage of parsing code and generate more valid inputs to improve the coverage of functionality code significantly. Furthermore, compared with the state-of-the-art grammar synthesis methods, the grammars learned by\n                    <jats:sc>Lase<\/jats:sc>\n                    have better precision and recall on most benchmark programs.\n                  <\/jats:p>","DOI":"10.1145\/3798243","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T14:33:43Z","timestamp":1775831623000},"page":"1180-1207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Input Grammar Synthesis Aided Symbolic Execution"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9079-3566","authenticated-orcid":false,"given":"Ke","family":"Ma","sequence":"first","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1730-7796","authenticated-orcid":false,"given":"Yunlai","family":"Luo","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4066-7892","authenticated-orcid":false,"given":"Zhenbang","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7092-3658","authenticated-orcid":false,"given":"Weijiang","family":"Hong","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6082-4501","authenticated-orcid":false,"given":"Yufeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0637-8744","authenticated-orcid":false,"given":"Ji","family":"Wang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"2001. Java compiler. http:\/\/janino-compiler.github.io\/janino"},{"key":"e_1_3_1_3_1","unstructured":"2015. C compiler. https:\/\/github.com\/FTRobbin\/LoliCCompiler.git"},{"key":"e_1_3_1_4_1","unstructured":"2020. PHP compiler. https:\/\/github.com\/jphp-group\/jphp.git"},{"key":"e_1_3_1_5_1","unstructured":"2023. Csharp compiler. https:\/\/github.com\/Fireball19\/simple-csharp-compiler.git"},{"key":"e_1_3_1_6_1","unstructured":"2024. JavaScript interpreter. https:\/\/github.com\/TopchetoEU\/jscript.git"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/6448"},{"key":"e_1_3_1_8_1","unstructured":"Shahbaz Ali Hailong Sun and Yongwang Zhao. 2019. Model Learning: A Survey on Foundation Tools and Applications. CoRR\u201919 abs\/1901.01910 (2019). arXiv:1901.01910 http:\/\/arxiv.org\/abs\/1901.01910"},{"key":"e_1_3_1_9_1","doi-asserted-by":"crossref","unstructured":"Saswat Anand Patrice Godefroid and Nikolai Tillmann. 2008. Demand-driven compositional symbolic execution. In Proceedings of the Theory and practice of software 14th international conference on Tools and algorithms for the construction and analysis of systems. 367\u2013381.","DOI":"10.1007\/978-3-540-78800-3_28"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71209-1_12"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062455.1062530"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_3_1_13_1","unstructured":"Mohammad Rifat Arefin Suraj Shetiya Zili Wang and Christoph Csallner. 2024. Fast Deterministic Black-box Context-free Grammar Inference. ICSE 2024."},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3182657"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062349"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009015"},{"key":"e_1_3_1_17_1","unstructured":"Cristian Cadar Daniel Dunbar and Dawson Engler. 2008. KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs. In USENIX\u201908. 209\u2013224."},{"key":"e_1_3_1_18_1","doi-asserted-by":"crossref","unstructured":"Cristiano Calcagno Dino Distefano Peter O\u2019Hearn and Hongseok Yang. 2009. Compositional shape analysis by means of bi-abduction. In POPL 2009. 289\u2013300.","DOI":"10.1145\/1480881.1480917"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451152"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","unstructured":"Leonardo Mendon\u00e7a de Moura and Nikolaj Bj\u00f8rner. 2008. Z3: An Efficient SMT Solver. In TACAS\u201908. 337\u2013340. doi:10.1007\/978-3-540-78800-3_24","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.01.015"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190226"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375607"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065036"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409679"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46002-0_25"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.156594"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45923-5_6"},{"key":"e_1_3_1_30_1","unstructured":"Nikolas Havrikov. 2019. tribble 1.0.0. https:\/\/github.com\/havrikov\/tribble"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00027"},{"key":"e_1_3_1_32_1","unstructured":"Marc R Hoffmann E Mandrikov and M Friedenhagen. 2014. JaCoCo Java code coverage library."},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1454320"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970321"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2010.08.037"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","unstructured":"Ren\u00e9 Just. 2014. The major mutation framework: efficient and scalable mutation analysis for Java (ISSTA 2014). Association for Computing Machinery 433\u2013436. doi:10.1145\/2610384.2628053","DOI":"10.1145\/2610384.2628053"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338934"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360252"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2004.16"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678879"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254088"},{"key":"e_1_3_1_42_1","unstructured":"lark parser. 2021. Lark - a parsing toolkit for Python. https:\/\/github.com\/lark-parser\/lark"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535857"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","unstructured":"Zhiqiang Lin and Xiangyu Zhang. 2008. Deriving input syntactic structure from execution. In FSE \u201908. ACM 83\u201393. doi:10.1145\/1453101.1453114","DOI":"10.1145\/1453101.1453114"},{"key":"e_1_3_1_45_1","volume-title":"An introduction to formal languages and automata, 4th Edition","author":"Linz Peter","year":"2006","unstructured":"Peter Linz. 2006. An introduction to formal languages and automata, 4th Edition. Jones and Bartlett Publishers."},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","unstructured":"Ke Ma Yunlai Luo Zhenbang Chen Weijiang Hong Yufeng Zhang and Ji Wang. 2026. Artifact for: Online Input Grammar Synthesis Aided Symbolic Execution. doi:10.5281\/zenodo.18811809","DOI":"10.5281\/zenodo.18811809"},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321631.1321653"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3395363.3397348"},{"key":"e_1_3_1_49_1","unstructured":"Oracle. 2011. Java class format. https:\/\/docs.oracle.com\/javase\/specs\/jvms\/se7\/html\/jvms-4.html#jvms-4.10.1.9"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460319.3464845"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250705"},{"key":"e_1_3_1_52_1","unstructured":"RFC. 1989. TCP\/IP package format. https:\/\/www.rfc-editor.org\/rfc\/inline-errata\/rfc793.html"},{"key":"e_1_3_1_53_1","unstructured":"Jos\u00e9 Fragoso Santos Petar Maksimovic Sacha-\u00c9lie Ayoun and Philippa Gardner. 2020. Gillian: Compositional Symbolic Execution for All. CoRR abs\/2001.05059 (2020). arXiv:2001.05059 https:\/\/arxiv.org\/abs\/2001.05059"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081706.1081750"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454051"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2019.00081"},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338958"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","unstructured":"Tao Xie Nikolai Tillmann Jonathan de Halleux and Wolfram Schulte. 2009. Fitness-guided path exploration in dynamic symbolic execution. In DSN 2009. 359\u2013368. doi:10.1109\/DSN.2009.5270315","DOI":"10.1109\/DSN.2009.5270315"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","unstructured":"Qiuping Yi Yifan Yu and Guowei Yang. 2024. Compatible Branch Coverage Driven Symbolic Execution for Efficient Bug Finding. 8 PLDI Article 213 (June 2024) 23 pages. doi:10.1145\/3656443","DOI":"10.1145\/3656443"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180227"},{"key":"e_1_3_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2015.80"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T20:30:42Z","timestamp":1787517042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,10]]},"references-count":60,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2026,4,10]]}},"alternative-id":["10.1145\/3798243"],"URL":"https:\/\/doi.org\/10.1145\/3798243","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,10]]},"assertion":[{"value":"2025-10-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}