{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:15:20Z","timestamp":1760044520836,"version":"3.41.2"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"ISSTA","funder":[{"name":"NSF","award":["2133487"],"award-info":[{"award-number":["2133487"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2025,6,22]]},"abstract":"<jats:p>Pointer analysis serves as a fundamental component in the realm of binary code reverse engineering. It can be leveraged to reconstruct a binary program's call graph and can be further applied to various security analyses. However, the absence of symbols and type information within binary code presents formidable challenges to effective pointer analysis. Existing works often apply approximations when performing pointer analysis on binary. Nevertheless, these methods tend to be inefficient and produce numerous false positive targets. In this paper, we propose BinDSA, a novel model tailored for binary pointer analysis. BinDSA prioritizes precision and efficiency over soundness. It is field- and context-sensitive, employing unification-based techniques and reconstructing a context-sensitive heap. It jointly recovers data structure and points-to relations so that precision can be further improved. In evaluation, we demonstrate that BinDSA is 5 times more efficient and notably more precise than the current state-of-the-art technique without significantly sacrificing soundness. We also apply BinDSA on CVE reachability analysis and vulnerability detection, demonstrating its effective application to security tasks.<\/jats:p>","DOI":"10.1145\/3728928","type":"journal-article","created":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T10:52:56Z","timestamp":1750589576000},"page":"1190-1211","source":"Crossref","is-referenced-by-count":1,"title":["BinDSA: Efficient, Precise Binary-Level Pointer Analysis with Context-Sensitive Heap Reconstruction"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4899-875X","authenticated-orcid":false,"given":"Lian","family":"Gao","sequence":"first","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8942-7742","authenticated-orcid":false,"given":"Heng","family":"Yin","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Juliet C\/C++ 1.3. https:\/\/samate.nist.gov\/SARD\/test-suites\/112\/"},{"key":"e_1_2_1_2_1","unstructured":"2024. BinAbsInspector. https:\/\/github.com\/KeenSecurityLab\/BinAbsInspector\/"},{"key":"e_1_2_1_3_1","unstructured":"2024. cwe_checker. https:\/\/github.com\/fkie-cad\/cwe_checker\/"},{"key":"e_1_2_1_4_1","unstructured":"2024. Ghidra. https:\/\/ghidra-sre.org\/"},{"key":"e_1_2_1_5_1","unstructured":"2024. Zoom. https:\/\/zoom.us\/"},{"key":"e_1_2_1_6_1","unstructured":"Lars Ole Andersen. 1994. Program analysis and specialization for the C programming language."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1749608.1749612"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485547"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370334"},{"key":"e_1_2_1_11_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Chen Sanchuan","year":"2021","unstructured":"Sanchuan Chen, Zhiqiang Lin, and Yinqian Zhang. 2021. $SelectiveTaint$: Efficient Data Flow Tracking With Static Binary Rewriting. In 30th USENIX Security Symposium (USENIX Security 21). 1665\u20131682."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349309"},{"key":"e_1_2_1_14_1","volume-title":"Deepbindiff: Learning program-wide code representations for binary diffing. In Network and distributed system security symposium.","author":"Duan Yue","year":"2020","unstructured":"Yue Duan, Xuezixiang Li, Jinghan Wang, and Heng Yin. 2020. Deepbindiff: Learning program-wide code representations for binary diffing. In Network and distributed system security symposium."},{"key":"e_1_2_1_15_1","volume-title":"2018 International Conference on Cloud Computing, Big Data and Blockchain (ICCBB). 1\u20138.","author":"Feng Zenan","year":"2018","unstructured":"Zenan Feng, Zhenyu Wang, Weiyu Dong, and Rui Chang. 2018. Bintaint: a static taint analysis method for binary vulnerability mining. In 2018 International Conference on Cloud Computing, Big Data and Blockchain (ICCBB). 1\u20138."},{"key":"e_1_2_1_16_1","volume-title":"SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode Diffing. In Network and Distributed System Security Symposium","author":"Gao Lian","year":"2024","unstructured":"Lian Gao, Yu Qu, Sheng Yu, Yue Duan, and Heng Yin. 2024. SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode Diffing. In Network and Distributed System Security Symposium, February 2024 (NDSS\u201924)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1306878.1307362"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480911"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764696"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/381694.378855"},{"key":"e_1_2_1_21_1","volume-title":"25th USENIX Security Symposium (USENIX Security 16)","author":"Jana Suman","year":"2016","unstructured":"Suman Jana, Yuan Jochen Kang, Samuel Roth, and Baishakhi Ray. 2016. Automatically detecting error handling bugs using error specifications. In 25th USENIX Security Symposium (USENIX Security 16). 345\u2013362."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970354"},{"key":"e_1_2_1_23_1","unstructured":"Sun Hyoung Kim Cong Sun Dongrui Zeng and Gang Tan. 2021. Refining Indirect Call Targets at the Binary Level.. In NDSS."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3497776.3517776"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250766"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32304-2_3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238199"},{"key":"e_1_2_1_28_1","volume-title":"2022 IEEE Symposium on Security and Privacy (SP). 1100\u20131119","author":"Liu Zhibo","year":"2022","unstructured":"Zhibo Liu, Yuanyuan Yuan, Shuai Wang, and Yuyan Bao. 2022. Sok: Demystifying binary lifters through the lens of downstream applications. In 2022 IEEE Symposium on Security and Privacy (SP). 1100\u20131119."},{"key":"e_1_2_1_29_1","volume-title":"Vijay Janapa Reddi, and Kim Hazelwood","author":"Luk Chi-Keung","year":"2005","unstructured":"Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: building customized program analysis tools with dynamic instrumentation. Acm sigplan notices, 40, 6 (2005), 190\u2013200."},{"key":"e_1_2_1_30_1","volume-title":"International Symposium on Research in Attacks, Intrusions, and Defenses. 423\u2013444","author":"Muntean Paul","year":"2018","unstructured":"Paul Muntean, Matthias Fischer, Gang Tan, Zhiqiang Lin, Jens Grossklags, and Claudia Eckert. 2018. cfi: Type-assisted control flow integrity for x86-64 binaries. In International Symposium on Research in Attacks, Intrusions, and Defenses. 423\u2013444."},{"key":"e_1_2_1_31_1","volume-title":"Static Analysis: 11th International Symposium, SAS 2004, Verona, Italy, August 26-28, 2004. Proceedings 11","author":"Nystrom Erik M","year":"2004","unstructured":"Erik M Nystrom, Hong-Seok Kim, and Wen-Mei W Hwu. 2004. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Static Analysis: 11th International Symposium, SAS 2004, Verona, Italy, August 26-28, 2004. Proceedings 11. 165\u2013180."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_1_33_1","volume-title":"Soundness is not even necessary for most modern analysis applications, however, as many. Commun. ACM, 58, 2","author":"Perhaps Desirable","year":"2015","unstructured":"Desirable Perhaps. 2015. Soundness is not even necessary for most modern analysis applications, however, as many. Commun. ACM, 58, 2 (2015)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892226"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263703"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_1_38_1","volume-title":"Programming Languages and Systems: 9th Asian Symposium, APLAS 2011, Kenting, Taiwan, December 5-7, 2011. Proceedings 9. 155\u2013171","author":"Sui Yulei","year":"2011","unstructured":"Yulei Sui, Sen Ye, Jingling Xue, and Pen-Chung Yew. 2011. SPAS: Scalable path-sensitive pointer analysis on full-sparse SSA. In Programming Languages and Systems: 9th Asian Symposium, APLAS 2011, Kenting, Taiwan, December 5-7, 2011. Proceedings 9. 155\u2013171."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2214"},{"key":"e_1_2_1_40_1","series-title":"SIAM journal on computing, 1, 2","volume-title":"Depth-first search and linear graph algorithms","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing, 1, 2 (1972), 146\u2013160."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.60"},{"key":"e_1_2_1_42_1","volume-title":"2018 IEEE Symposium on Security and Privacy (SP). 661\u2013678","author":"Xu Meng","year":"2018","unstructured":"Meng Xu, Chenxiong Qian, Kangjie Lu, Michael Backes, and Taesoo Kim. 2018. Precise and scalable detection of double-fetch bugs in OS kernels. In 2018 IEEE Symposium on Security and Privacy (SP). 661\u2013678."},{"key":"e_1_2_1_43_1","volume-title":"International Static Analysis Symposium. 319\u2013336","author":"Ye Sen","year":"2014","unstructured":"Sen Ye, Yulei Sui, and Jingling Xue. 2014. Region-based selective flow-sensitive pointer analysis. In International Static Analysis Symposium. 319\u2013336."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772985"},{"key":"e_1_2_1_45_1","volume-title":"2021 IEEE Symposium on Security and Privacy (SP). 813\u2013832","author":"Zhang Zhuo","year":"2021","unstructured":"Zhuo Zhang, Yapeng Ye, Wei You, Guanhong Tao, Wen-chuan Lee, Yonghwi Kwon, Yousra Aafer, and Xiangyu Zhang. 2021. Osprey: Recovery of variable and data structure via probabilistic analysis for stripped binary. In 2021 IEEE Symposium on Security and Privacy (SP). 813\u2013832."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360563"},{"key":"e_1_2_1_47_1","volume-title":"2023 IEEE Symposium on Security and Privacy (SP). 2357\u20132374","author":"Zhu Wenyu","year":"2023","unstructured":"Wenyu Zhu, Zhiyao Feng, Zihan Zhang, Jianjun Chen, Zhijian Ou, Min Yang, and Chao Zhang. 2023. Callee: Recovering call graphs for binaries with transfer and contrastive learning. In 2023 IEEE Symposium on Security and Privacy (SP). 2357\u20132374."}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:53:09Z","timestamp":1752684789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,22]]},"references-count":47,"journal-issue":{"issue":"ISSTA","published-print":{"date-parts":[[2025,6,22]]}},"alternative-id":["10.1145\/3728928"],"URL":"https:\/\/doi.org\/10.1145\/3728928","relation":{},"ISSN":["2994-970X"],"issn-type":[{"type":"electronic","value":"2994-970X"}],"subject":[],"published":{"date-parts":[[2025,6,22]]}}}