{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:44:49Z","timestamp":1773193489192,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"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":["62172209"],"award-info":[{"award-number":["62172209"]}],"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":[[2024,6,30]]},"abstract":"<jats:p>\n            Skeletal program enumeration (SPE) can generate a great number of test programs for validating the correctness of compilers or interpreters. The classic SPE generates programs by exhaustively enumerating all possible variable usage patterns into a given syntactic structure. Even though it is capable of producing many test programs, the exhaustive enumeration strategy generates a large number of invalid programs, which may waste plenty of testing time and resources. To address the problem, this article proposes a tree-based SPE technique. Compared to the state-of-the-art, the key merit of the tree-based approach is that it allows us to take the dependency information into consideration when producing test programs and, thus, make it possible to (1) directly generate non-equivalent programs and (2) apply dominance relations to eliminate invalid test programs that have undefined variables. Hence, our approach significantly saves the cost of the na\u00efve SPE approach. We have implemented our approach into an automated testing tool,\n            <jats:sc>IFuzzer<\/jats:sc>\n            , and applied it to test eight different implementations of Python interpreters, including CPython, PyPy, IronPython, Jython, RustPython, GPython, Pyston, and Codon. In three months of fuzzing,\n            <jats:sc>IFuzzer<\/jats:sc>\n            detected 142 bugs, of which 87 have been confirmed to be previously unknown bugs, of which 34 have been fixed. Compared to the state-of-the-art SPE techniques,\n            <jats:sc>IFuzzer<\/jats:sc>\n            takes only 61.0% of the time cost given the same number of testing seeds and improves 5.3% source code function coverage in the same time budget of testing.\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3647994","type":"journal-article","created":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T11:55:57Z","timestamp":1707738957000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Enumerating Valid Non-Alpha-Equivalent Programs for Interpreter Testing"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2078-9578","authenticated-orcid":false,"given":"Xinmeng","family":"Xia","sequence":"first","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7477-3642","authenticated-orcid":false,"given":"Yang","family":"Feng","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8297-8998","authenticated-orcid":false,"given":"Qingkai","family":"Shi","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5359-7934","authenticated-orcid":false,"given":"James A.","family":"Jones","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of California, Irvine, Irvine, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9544-2500","authenticated-orcid":false,"given":"Xiangyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University, West Lafayette, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7743-1296","authenticated-orcid":false,"given":"Baowen","family":"Xu","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,4]]},"reference":[{"key":"e_1_3_4_2_2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho Alfred V.","year":"2007","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compilers: Principles, Techniques, and Tools. Pearson Addison Wesley."},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134020"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2785841"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPW.2018.00026"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(97)00017-7"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/1375341.1375345"},{"key":"e_1_3_4_8_2","volume-title":"Top Programming Languages 2021; Python dominates as the de facto platform for new technologies","author":"Cass Stephen","year":"2021","unstructured":"Stephen Cass. 2021. Top Programming Languages 2021; Python dominates as the de facto platform for new technologies. Retrieved from: https:\/\/spectrum.ieee.org\/top-programming-languages-2021"},{"key":"e_1_3_4_9_2","unstructured":"Adam Cecchetti and Michael Eddington. 2018. Whitebox Network Fuzzing. US Patent 9 910 766."},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2884781.2884878"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3363562"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462173"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380381"},{"key":"e_1_3_4_14_2","volume-title":"Practical Nonparametric Statistics","author":"Conover William Jay","year":"1999","unstructured":"William Jay Conover. 1999. Practical Nonparametric Statistics. Vol. 350. John Wiley & Sons."},{"key":"e_1_3_4_15_2","volume-title":"CPython","year":"2023","unstructured":"CPython. 2023. CPython. Retrieved from https:\/\/github.com\/python\/cpython"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213848"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28891-3_12"},{"key":"e_1_3_4_18_2","unstructured":"Python Issue Tracker Devguide. 2022. Retrieved from https:\/\/devguide.python.org\/triaging\/"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPW.2015.33"},{"key":"e_1_3_4_20_2","volume-title":"Mathematical Constants","author":"Finch Steven R.","year":"2003","unstructured":"Steven R. Finch. 2003. Mathematical Constants. Cambridge University Press."},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/3155562.3155573"},{"key":"e_1_3_4_22_2","volume-title":"gpython","year":"2023","unstructured":"gpython. 2023. gpython. Retrieved from https:\/\/github.com\/go-python\/gpython"},{"key":"e_1_3_4_23_2","first-page":"445","volume-title":"Proceedings of the 21st USENIX Security Symposium (USENIX Security\u201912)","author":"Holler Christian","year":"2012","unstructured":"Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with code fragments. In Proceedings of the 21st USENIX Security Symposium (USENIX Security\u201912). 445\u2013458."},{"key":"e_1_3_4_24_2","unstructured":"IFuzzer. 2023. Retrieved from https:\/\/github.com\/xiaxinmeng\/IFuzzer"},{"key":"e_1_3_4_25_2","volume-title":"IronPython","year":"2023","unstructured":"IronPython. 2023. IronPython. Retrieved from https:\/\/ironpython.net"},{"key":"e_1_3_4_26_2","volume-title":"ISO\/IEC 9899:2011 Information technology\u2014Programming languages\u2014C","year":"2011","unstructured":"ISO. 2011. ISO\/IEC 9899:2011 Information technology\u2014Programming languages\u2014C. International Organization for Standardization, Geneva, Switzerland. Retrieved from http:\/\/www.iso.org\/iso\/iso_catalogue\/catalogue_tc\/catalogue_detail.htm?csnumber=57853"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMPSAC48688.2020.0-156"},{"key":"e_1_3_4_28_2","volume-title":"Jython","year":"2023","unstructured":"Jython. 2023. Jython. Retrieved from https:\/\/www.jython.org"},{"key":"e_1_3_4_29_2","first-page":"111","article-title":"Systematic search for lambda expressions.","volume":"6","author":"Katayama Susumu","year":"2005","unstructured":"Susumu Katayama. 2005. Systematic search for lambda expressions. Trends Function. Program. 6 (2005), 111\u2013126.","journal-title":"Trends Function. Program."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89197-0_21"},{"key":"e_1_3_4_31_2","first-page":"43","volume-title":"Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation","author":"Katayama Susumu","year":"2012","unstructured":"Susumu Katayama. 2012. An analytical inductive functional programming system that avoids unintended programs. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. 43\u201352."},{"key":"e_1_3_4_32_2","volume-title":"The Art of Computer Programming. 1. Fundamental Algorithms","author":"Knuth Donald Ervin","year":"1975","unstructured":"Donald Ervin Knuth. 1975. The Art of Computer Programming. 1. Fundamental Algorithms. Addison-Wesley."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/260999"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/309739.309744"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594334"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814319"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771785"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737986"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428264"},{"key":"e_1_3_4_40_2","doi-asserted-by":"crossref","unstructured":"H. B. Mann and D. R. Whitney. 1947. On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics 18 1 (1947) 50\u201360.","DOI":"10.1214\/aoms\/1177730491"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2522920.2522922"},{"issue":"1","key":"e_1_3_4_42_2","first-page":"100","article-title":"Differential testing for software","volume":"10","author":"McKeeman William M.","year":"1998","unstructured":"William M. McKeeman. 1998. Differential testing for software. Digit. Technic. J. 10, 1 (1998), 100\u2013107.","journal-title":"Digit. Technic. J."},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/96267.96279"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjtsldm.7.91"},{"key":"e_1_3_4_45_2","volume-title":"Principles of Program Analysis","author":"Nielson Flemming","year":"2004","unstructured":"Flemming Nielson, Hanne R. Nielson, and Chris Hankin. 2004. Principles of Program Analysis. Springer Science & Business Media."},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/1830479"},{"key":"e_1_3_4_47_2","volume-title":"PyPy","year":"2023","unstructured":"PyPy. 2023. PyPy. Retrieved from https:\/\/www.pypy.org"},{"key":"e_1_3_4_48_2","volume-title":"Pyston","year":"2023","unstructured":"Pyston. 2023. Pyston. Retrieved from https:\/\/www.pyston.org"},{"key":"e_1_3_4_49_2","volume-title":"RustPython","year":"2023","unstructured":"RustPython. 2023. RustPython. Retrieved from https:\/\/rustpython.github.io"},{"key":"e_1_3_4_50_2","unstructured":"Kostya Serebryany. 2015. LibFuzzer. LibFuzzer: A library for coverage-guided fuzz testing. http:\/\/llvm.org\/docs\/LibFuzzer.html. Last Accessed: 2023-03-03"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3578360.3580275"},{"issue":"12","key":"e_1_3_4_52_2","first-page":"354","article-title":"Python\u2014The fastest growing programming language","volume":"4","author":"Srinath K. R.","year":"2017","unstructured":"K. R. Srinath. 2017. Python\u2014The fastest growing programming language. Int. Res. J. Eng. Technol. 4, 12 (2017), 354\u2013357.","journal-title":"Int. Res. J. Eng. Technol."},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007512.1007531"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2884781.2884879"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2931037.2931074"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-019-8231-0"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.23"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522728"},{"key":"e_1_3_4_59_2","doi-asserted-by":"crossref","unstructured":"Ziyuan Wang Dexin Bu Aiyue Sun Shanyi Gou Yong Wang and Lin Chen. 2022. An empirical study on bugs in python interpreters. IEEE Transactions on Reliability 71 2 (2022) 716\u2013734.","DOI":"10.1109\/TR.2022.3159812"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"},{"key":"e_1_3_4_61_2","article-title":"American fuzzy lop","author":"Zalewski Michal","year":"2007","unstructured":"Michal Zalewski. 2007. American fuzzy lop. Retrieved from http:\/\/lcamtuf.coredump.cx\/afl","journal-title":"R"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062379"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2020.110884"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647994","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3647994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:56:52Z","timestamp":1750291012000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,4]]},"references-count":62,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3647994"],"URL":"https:\/\/doi.org\/10.1145\/3647994","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,4]]},"assertion":[{"value":"2023-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}