{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T15:17:24Z","timestamp":1791299844074,"version":"4.1.0"},"reference-count":63,"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"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["SHF-1901242"],"award-info":[{"award-number":["SHF-1901242"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["SHF-1910300"],"award-info":[{"award-number":["SHF-1910300"]}]},{"name":"National Science Foundation","award":["Proto-OKN 2333736"],"award-info":[{"award-number":["Proto-OKN 2333736"]}]},{"name":"National Science Foundation","award":["IIS2416835"],"award-info":[{"award-number":["IIS2416835"]}]},{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","award":["VSPELLS - HR001120S0058"],"award-info":[{"award-number":["VSPELLS - HR001120S0058"]}],"id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000005","name":"DOD U.S. Department of Defense","doi-asserted-by":"publisher","award":["ONR N00014-23-1-2081"],"award-info":[{"award-number":["ONR N00014-23-1-2081"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Static program analysis plays an essential role in program optimization, bug detection, and debugging. However, reliance on compilation and limited customization hinder its adoption in the real world. This paper presents a compositional neuro-symbolic approach named NESA that facilitates compilation-free and customizable static program analysis using large language models (LLMs) with mitigated hallucinations. Specifically, we propose an analysis policy language, a restricted form of Datalog, to support users decomposing a static program analysis problem into several sub-problems that target simpler syntactic or semantic properties upon smaller code snippets. The problem decomposition enables the LLMs to target more manageable semantic-related sub-problems with reduced hallucinations, while the syntactic ones are resolved by parsing-based analysis without hallucinations. An analysis policy then is evaluated with lazy and incremental prompting, which  \nsignificantly mitigates the hallucinations and improves the performance. We evaluate NESA for program slicing and bug detection upon benchmark and real-world programs. Evaluation results show that while NESA supports compilation-free and customizable analysis, it can still achieve comparable and even better performance than existing techniques. In a customized taint vulnerability detection upon TaintBench, for example, NESA achieves a precision of 66.27%, a recall of 78.57%, and an F1 score of 0.72, surpassing an industrial approach by 0.20 in F1 score. NESA also detects 13 real-world memory leak bugs, which have been fixed by developers.<\/jats:p>","DOI":"10.1145\/3808161","type":"journal-article","created":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T17:06:14Z","timestamp":1782839174000},"page":"3486-3509","source":"Crossref","is-referenced-by-count":2,"title":["NESA: Relational Neuro-Symbolic Static Program Analysis"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0617-5322","authenticated-orcid":false,"given":"Chengpeng","family":"Wang","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5421-4619","authenticated-orcid":false,"given":"Yifei","family":"Gao","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8039-0528","authenticated-orcid":false,"given":"Wuqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5319-1160","authenticated-orcid":false,"given":"Xuwei","family":"Liu","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2352-8307","authenticated-orcid":false,"given":"Jinyao","family":"Guo","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6032-6045","authenticated-orcid":false,"given":"Mingwei","family":"Zheng","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8297-8998","authenticated-orcid":false,"given":"Qingkai","family":"Shi","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9544-2500","authenticated-orcid":false,"given":"Xiangyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594299"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3661167"},{"key":"e_1_2_1_4_1","volume-title":"Black","author":"Boland Tim","year":"2012","unstructured":"Tim Boland and Paul E. Black. 2012. Juliet 1."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/mc.2012.345"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385990"},{"key":"e_1_2_1_8_1","volume-title":"Strange Loop Conference,. Accessed-. URL: https:\/\/www. thestrangeloop. com\/\/tree-sitter-a-new-parsing-system-for-programming-tools. html.","author":"Brunsfeld Max","year":"2018","unstructured":"Max Brunsfeld. 2018. Tree-sitter-a new parsing system for programming tools. In Strange Loop Conference,. Accessed-. URL: https:\/\/www. thestrangeloop. com\/\/tree-sitter-a-new-parsing-system-for-programming-tools. html."},{"key":"e_1_2_1_9_1","volume-title":"Engler","author":"Cadar Cristian","year":"2008","unstructured":"Cristian Cadar, Daniel Dunbar, and Dawson R. Engler. 2008. KLEE: Unassisted and Automatic Generation of High- Coverage Tests for Complex Systems Programs. In 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008, December 8-10, 2008, San Diego, California, USA, Proceedings, Richard Draves and Robbert van Renesse (Eds.). USENIX Association, 209-224."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480917"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649829"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970347"},{"key":"e_1_2_1_13_1","volume-title":"https:\/\/clang.llvm.org\/extra\/clang-tidy\/. [Online","year":"2025","unstructured":"Clang-Tidy. 2025. Clang-Tidy. https:\/\/clang.llvm.org\/extra\/clang-tidy\/. [Online; accessed 29-May-2025]."},{"key":"e_1_2_1_14_1","volume-title":"Query-Based Code Analysis Engine. https:\/\/github.com\/codefuse-ai\/CodeFuse-Query. [Online","year":"2025","unstructured":"CodeFuse. 2025. Query-Based Code Analysis Engine. https:\/\/github.com\/codefuse-ai\/CodeFuse-Query. [Online; accessed 29-May-2025]."},{"key":"e_1_2_1_15_1","volume-title":"8th International Conference on Learning Representations, ICLR 2020","author":"Dinella Elizabeth","year":"2020","unstructured":"Elizabeth Dinella, Hanjun Dai, Ziyang Li, Mayur Naik, Le Song, and Ke Wang. 2020. Hoppity: Learning Graph Transformations to Detect and Fix Bugs in Programs. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. https:\/\/openreview.net\/forum?id=SJeqs6EFvB"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-17108-6_9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785477_2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN55064.2022.9892280"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2312.08477"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523446"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2023.FINDINGS-EMNLP.123"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2310.06770"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2013.6606613"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10664-016-9437-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649828"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2504.16057"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00090"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10664-021-10013-5"},{"key":"e_1_2_1_29_1","volume-title":"The Artifact of NESA. https:\/\/github.com\/chengpeng-wang\/NESA. [Online","author":"NESA.","year":"2026","unstructured":"NESA. 2026. The Artifact of NESA. https:\/\/github.com\/chengpeng-wang\/NESA. [Online; accessed 20-Feb-2026]."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2013.6606623"},{"key":"e_1_2_1_31_1","volume-title":"Accessed","author":"AI.","year":"2026","unstructured":"OpenAI. 2026. API Pricing. https:\/\/openai.com\/api\/pricing\/. Accessed: March 17, 2026."},{"key":"e_1_2_1_32_1","first-page":"27496","volume-title":"International Conference on Machine Learning, ICML 2023","author":"Pei Kexin","year":"2023","unstructured":"Kexin Pei, David Bieber, Kensen Shi, Charles Sutton, and Pengcheng Yin. 2023. Can Large Language Models Reason about Program Invariants?. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 27496-27520. https:\/\/proceedings.mlr.press\/v202\/pei23a. html"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2308.03312"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2105.12655"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1128\/CDLI.9.6.1235-1239.2002"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1953-0053041-6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192418"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE55347.2025.00115"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_14"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3643737"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250748"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3623345"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_1_46_1","volume-title":"CodeQL for Java. https:\/\/codeql.github.com\/docs\/codeql-language-guides\/codeql-for-java\/. [Online","author":"QL.","year":"2025","unstructured":"CodeQL. 2025. CodeQL for Java. https:\/\/codeql.github.com\/docs\/codeql-language-guides\/codeql-for-java\/. [Online; accessed 29-May-2025]."},{"key":"e_1_2_1_47_1","volume-title":"Bug Report of NESA. https:\/\/repoaudit-home.github.io\/bugreports.html. [Online","author":"Wang Chengpeng","year":"2026","unstructured":"Chengpeng Wang, Yifei Gao, Wuqi Zhang, Xuwei Liu, Jinyao Guo, Mingwei Zheng, Qingkai Shi, and Xiangyu Zhang. 2026. Bug Report of NESA. https:\/\/repoaudit-home.github.io\/bugreports.html. [Online; accessed 10-Jan-2026]."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1800"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616271"},{"key":"e_1_2_1_50_1","volume-title":"Practical Security Analysis of Zero-Knowledge Proof Circuits. In 33rd USENIX Security Symposium, USENIX Security 2024","author":"Wen Hongbo","year":"2024","unstructured":"Hongbo Wen, Jon Stephens, Yanju Chen, Kostas Ferles, Shankara Pailoor, Kyle Charbonnet, Isil Dillig, and Yu Feng. 2024. Practical Security Analysis of Zero-Knowledge Proof Circuits. In 33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, August 14-16, 2024, Davide Balzarotti and Wenyuan Xu (Eds.). USENIX Association. https:\/\/www.usenix.org\/conference\/usenixsecurity24\/presentation\/wen"},{"key":"e_1_2_1_51_1","volume-title":"A wrapper script to build whole-program LLVM bitcode files. https:\/\/github.com\/travitch\/wholeprogram-llvm. [Online","author":"WLLVM.","year":"2025","unstructured":"WLLVM. 2025. A wrapper script to build whole-program LLVM bitcode files. https:\/\/github.com\/travitch\/wholeprogram-llvm. [Online; accessed 29-May-2025]."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468605"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2308.04748"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649814"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00209"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.44"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3731569.3764827"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2401.00812"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620666.3651366"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2023.EMNLP-MAIN.151"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP54263.2024.00146"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2309.01219"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640382"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808161","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T18:24:54Z","timestamp":1782843894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,30]]},"references-count":63,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3808161"],"URL":"https:\/\/doi.org\/10.1145\/3808161","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,30]]}}}