TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function Pointers
Article No.: 72, Pages 1609 - 1631
Abstract
C++ is crucial in software development, providing low-level memory control for performance and supporting object-oriented programming to construct modular, reusable code structures. Consequently, tackling pointer analysis for C++ becomes challenging, given the need to address these two fundamental features. A relatively unexplored research area involves the handling of C++ member function pointers. Previous efforts have tended to either disregard this feature or adopt a conservative approach, resulting in unsound or imprecise results. C++ member function pointers, handling both virtual (via virtual table indexes) and non-virtual functions (through addresses), pose a significant challenge for pointer analysis due to the mix of integers and pointers, often resulting in unsound or imprecise analysis. We introduce TIPS, the first pointer analysis that effectively manages both pointers and integers, offering support for C++ member function pointers by tracking their value flows. Our evaluation on TIPS demonstrates its accuracy in identifying C++ member function call targets, a task where other tools falter, across fourteen large C++ programs from SPEC CPU, Qt, LLVM, Ninja, and GoogleTest, while maintaining low analysis overhead. In addition, our micro-benchmark suite, complete with ground truth data, allows for precise evaluation of points-to information for C++ member function pointers across various inheritance scenarios, highlighting TIPS's precision enhancements.
References
[1]
Martín Abadi, Mihai Budiu, Ulfar Erlingsson, and Jay Ligatti. 2005. Control-Flow Integrity. In Proceedings of the 12th ACM SIGSAC Conference on Computer and Communications Security. ACM, New York. 340–353.
[2]
Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. In PhD Dissertation. University of Copenhagen, Denmank. 111–152.
[3]
Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014. FlowDroid: Precise Context, Flow, Field, Object-Sensitive and Lifecycle-Aware Taint Analysis for Android Apps. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, USA. 259–269. https://doi.org/10.1145/2666356.2594299
[4]
Avast. 2024. A Retargetable Machine-Code Decompiler Based on LLVM. https://github.com/avast/retdec Accessed May 10, 2024
[5]
George Balatsouras and Yannis Smaragdakis. 2016. Structure-Sensitive Points-To Analysis for C and C++. In Static Analysis: 23rd International Symposium, SAS 2016, Edinburgh, UK, September 8-10, 2016, Proceedings 23. Springer, USA. 84–104.
[6]
Cristian Cadar, Daniel Dunbar, and Dawson R Engler. 2008. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In Symposium on Operating Systems Design and Implementation. USENIX Association, USA. 209–224.
[7]
Yuandao Cai, Peisen Yao, and Charles Zhang. 2021. Canary: Practical Static Detection of Inter-Thread Value-Flow Bugs. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, USA. 1126–1140. https://doi.org/10.1145/3453483.3454099
[8]
The GoogleTest Open-Source Community. 2024. Google Testing and Mocking Framework. https://github.com/google/googletest Accessed May 10, 2024
[9]
The LLVM Open-Source Community. 2024. The LLVM Project. https://github.com/llvm/llvm-project Accessed May 10, 2024
[10]
The Ninja Open-Source Community. 2024. Ninja. https://github.com/ninja-build/ninja Accessed May 10, 2024
[11]
The Qt Company. 2024. Qt Base. https://github.com/qt/qtbase Accessed May 10, 2024
[12]
Rukayat Ayomide Erinfolami and Aravind Prakash. 2020. Devil Is Virtual: Reversing Virtual Inheritance in C++ Binaries. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM, USA. 133–148. https://doi.org/10.1145/3372297.3417251
[13]
Xiaokang Fan, Yulei Sui, Xiangke Liao, and Jingling Xue. 2017. Boosting the precision of virtual call integrity protection with partial pointer analysis for C++. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2017). ACM, New York, NY, USA. 329–340. isbn:9781450350761 https://doi.org/10.1145/3092703.3092729
[14]
George Fourtounis, Leonidas Triantafyllou, and Yannis Smaragdakis. 2020. Identifying Java Calls in Native Code via Binary Scanning. In Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM, USA. 388–400. https://doi.org/10.1145/3395363.3397368
[15]
Shengjian Guo, Meng Wu, and Chao Wang. 2018. Adversarial Symbolic Execution for Detecting Concurrency-Related Cache Timing Leaks. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM, USA. 377–388. https://doi.org/10.1145/3236024.3236028
[16]
Ben Hardekopf and Calvin Lin. 2009. Semi-Sparse Flow-Sensitive Pointer Analysis. In Proceedings of the 36th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, USA. 226–238. https://doi.org/10.1145/1594834.1480911
[17]
Ben Hardekopf and Calvin Lin. 2011. Flow-Sensitive Pointer Analysis for Millions of Lines of Code. In International Symposium on Code Generation and Optimization. IEEE, USA. 289–298. https://doi.org/10.1109/CGO.2011.5764696
[18]
Dongjie He, Jingbo Lu, and Jingling Xue. 2022. Qilin: A New Framework for Supporting Fine-Grained Context-Sensitivity in Java Pointer Analysis (Artifact). Dagstuhl Artifacts Ser., 8, 2 (2022), 06:1–06:3. https://doi.org/10.4230/DARTS.8.2.6
[19]
Minseok Jeon and Hakjoo Oh. 2022. Return of CFA: Call-Site Sensitivity Can Be Superior to Object Sensitivity Even for Object-Oriented Programs. In Proceedings of the ACM SIGPLAN Symposium on Principles of programming Languages. ACM, USA. 1–29. https://doi.org/10.1145/3498720
[20]
Yuseok Jeon, Priyam Biswas, Scott Carr, Byoungyoung Lee, and Mathias Payer. 2017. HexType: Efficient Detection of Type Confusion Errors for C++. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, USA. 2373–2387. https://doi.org/10.1145/3133956.3134062
[21]
Jeehoon Kang, Chung-Kil Hur, William Mansky, Dmitri Garbuzov, Steve Zdancewic, and Viktor Vafeiadis. 2015. A Formal C Memory Model Supporting Integer-Pointer Casts. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, USA. 326–335. https://doi.org/10.1145/2813885.2738005
[22]
Jakob Koschel, Pietro Borrello, Daniele Cono D’Elia, Herbert Bos, and Cristiano Giuffrida. 2023. Uncontained: Uncovering Container Confusion in the Linux Kernel. In Proceedings of the 32nd USENIX Security Symposium. USENIX Association, USA. 5055–5072.
[23]
Markus Kusano and Chao Wang. 2016. Flow-Sensitive Composition of Thread-Modular Abstract Interpretation. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, USA. 799–809. https://doi.org/10.1145/2950290.2950291
[24]
Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation. In International symposium on Code Generation and Optimization. IEEE, USA. 75–86.
[25]
Chris Lattner, Andrew Lenharth, and Vikram Adve. 2007. Making Context-Sensitive Points-To Analysis with Heap Cloning Practical for the Real World. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, USA. 278–289. https://doi.org/10.1145/1273442.1250766
[26]
Ondřej Lhoták and Laurie Hendren. 2003. Scaling Java Points-To Analysis using Spark. In Proceedings of the 12th International Conference on Compiler Construction. Springer, USA. 153–169.
[27]
Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. 2018. Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity. In Proceedings of the 2018 26th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, USA. 129–140. https://doi.org/10.1145/3276988
[28]
Yuanbo Li, Qirun Zhang, and Thomas Reps. 2023. Single-Source-Single-Target Interleaved-Dyck Reachability via Integer Linear Programming. In Proceedings of the ACM SIGPLAN Symposium on Principles of programming Languages. ACM, USA. 1003–1026. https://doi.org/10.1145/3571228
[29]
Bozhen Liu and Jeff Huang. 2022. SHARP: Fast Incremental Context-Sensitive Pointer Analysis for Java. In Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM, USA. 1–28. https://doi.org/10.1145/3527332
[30]
Peiming Liu, Yanze Li, Brad Swain, and Jeff Huang. 2022. PUS: A Fast and Highly Efficient Solver for Inclusion-Based Pointer Analysis. In Proceedings of the 44th International Conference on Software Engineering. ACM, USA. 1781–1792. https://doi.org/10.1145/3510003.3510075
[31]
Peng Liu, Omer Tripp, and Xiangyu Zhang. 2016. IPA: Improving Predictive Analysis with Pointer Analysis. In Proceedings of the 25th International Symposium on Software Testing and Analysis. ACM, USA. 59–69. https://doi.org/10.1145/2931037.2931046
[32]
V Benjamin Livshits and Monica S Lam. 2003. Tracking Pointers with Path and Context Sensitivity for Bug Detection in C Programs. In Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering. IEEE, USA. 317–326. https://doi.org/10.1145/940071.940114
[33]
LLVM. 2024. LLVM Language Reference Manual. https://llvm.org/docs/LangRef.html Accessed May 10, 2024
[34]
Jingbo Lu and Jingling Xue. 2019. Precision-preserving yet fast object-sensitive pointer analysis with partial context sensitivity. Proc. ACM Program. Lang., 3, OOPSLA (2019), Article 148, 29 pages. https://doi.org/10.1145/3360574
[35]
Wenjie Ma, Shengyuan Yang, Tian Tan, Xiaoxing Ma, Chang Xu, and Yue Li. 2023. Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer Analysis. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, USA. 539–564. https://doi.org/10.1145/3591242
[36]
Ana Milanova, Atanas Rountev, and Barbara G Ryder. 2005. Parameterized Object Sensitivity for Points-To Analysis for Java. ACM Transactions on Software Engineering and Methodology, 14, 1 (2005), 1–41. https://doi.org/10.1145/1044834.1044835
[37]
Hakjoo Oh, Wonchan Lee, Kihong Heo, Hongseok Yang, and Kwangkeun Yi. 2014. Selective Context-Sensitivity Guided by Impact Pre-Analysis. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, USA. 475–484. https://doi.org/10.1145/2594291.2594318
[38]
David J Pearce, Paul HJ Kelly, and Chris Hankin. 2007. Efficient Field-Sensitive Pointer Analysis of C. ACM Transactions on Programming Languages and Systems, 30, 1 (2007), 4–es. https://doi.org/10.1145/1290520.1290524
[39]
Tristan Ravitch. 2024. Whole Program LLVM. https://github.com/travitch/whole-program-llvm Accessed May 10, 2024
[40]
Philipp Dominik Schubert, Ben Hermann, and Eric Bodden. 2019. PhASAR: An Inter-Procedural Static Analysis Framework for C/C++. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, USA. 393–410.
[41]
Qingkai Shi, Xiao Xiao, Rongxin Wu, Jinguo Zhou, Gang Fan, and Charles Zhang. 2018. Pinpoint: Fast and Precise Sparse Value Flow Analysis for Million Lines of Code. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, USA. 693–706. https://doi.org/10.1145/3192366.3192418
[42]
Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. 2011. Pick Your Contexts Well: Understanding Object-Sensitivity. In Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, USA. 17–30. https://doi.org/10.1145/1925844.1926390
[43]
Yulei Sui, Yue Li, and Jingling Xue. 2013. Query-Directed Adaptive Heap Cloning for Optimizing Compilers. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization. IEEE, USA. 1–11. https://doi.org/10.1109/CGO.2013.6494978
[44]
Yulei Sui and Jingling Xue. 2016. On-Demand Strong Update Analysis via Value-Flow Refinement. In Proceedings of the 2016 24th ACM SIGSOFT international symposium on foundations of software engineering. ACM, USA. 460–473. https://doi.org/10.1145/2950290.2950296
[45]
Yulei Sui and Jingling Xue. 2016. SVF: Interprocedural Static Value-Flow Analysis in LLVM. In Proceedings of the 25th international conference on compiler construction. ACM/IEEE, USA. 265–266. https://doi.org/10.1145/2892208.2892235
[46]
Yulei Sui and Jingling Xue. 2024. SVF. https://github.com/SVF-tools/SVF Accessed May 10, 2024
[47]
Yulei Sui, Ding Ye, and Jingling Xue. 2012. Static Memory Leak Detection using Full-Sparse Value-Flow Analysis. In Proceedings of the 2012 International Symposium on Software Testing and Analysis. ACM, USA. 254–264. https://doi.org/10.1145/2338965.2336784
[48]
Yulei Sui, Ding Ye, and Jingling Xue. 2014. Detecting Memory Leaks Statically with Full-Sparse Value-Flow Analysis. IEEE Transactions on Software Engineering, 40, 2 (2014), 107–122. https://doi.org/10.1109/TSE.2014.2302311
[49]
David Trabish, Timotej Kapus, Noam Rinetzky, and Cristian Cadar. 2020. Past-Sensitive Pointer Analysis for Symbolic Execution. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM, USA. 197–208. https://doi.org/10.1145/3410246
[50]
David Trabish, Andrea Mattavelli, Noam Rinetzky, and Cristian Cadar. 2018. Chopped Symbolic Execution. In Proceedings of the 40th International Conference on Software Engineering. ACM, USA. 350–360. https://doi.org/10.1145/3180155.3180251
[51]
Xizao Wang, Zhiqiang Zuo, Lei Bu, and Jianhua Zhao. 2023. DStream: A Streaming-Based Highly Parallel IFDS Framework. In Proceedings of the 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). IEEE/ACM, USA. 2488–2500. https://doi.org/10.1109/ICSE48619.2023.00208
[52]
Hua Yan, Yulei Sui, Shiping Chen, and Jingling Xue. 2018. Spatio-Temporal Context Reduction: A Pointer-Analysis-Based Static Approach for Detecting Use-After-Free Vulnerabilities. In Proceedings of the 40th International Conference on Software Engineering. ACM, USA. 327–337. https://doi.org/10.1145/3180155.3180178
[53]
Hongtao Yu, Jingling Xue, Wei Huo, Xiaobing Feng, and Zhaoqing Zhang. 2010. Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization. ACM/IEEE, USA. 218–229. https://doi.org/10.1145/1772954.1772985
[54]
Jisheng Zhao, Michael G Burke, and Vivek Sarkar. 2018. Parallel Sparse Flow-Sensitive Points-To Analysis. In Proceedings of the 27th International Conference on Compiler Construction. ACM, USA. 59–70. https://doi.org/10.1145/3178372.3179517
[55]
Changwei Zou. 2024. TIPS. https://github.com/sheisc/TIPS.git Accessed May 10, 2024
Index Terms
- TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function Pointers
Recommendations
Precise Call Graphs for C Programs with Function Pointers
The use of pointers presents serious problems for software productivity tools for software understanding, restructuring, and testing. Pointers enable indirect memory accesses through pointer dereferences, as well as indirect procedure calls (e.g., ...
Semi-sparse flow-sensitive pointer analysis
POPL '09Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Tracking pointers with path and context sensitivity for bug detection in C programs
This paper proposes a pointer alias analysis for automatic error detection. State-of-the-art pointer alias analyses are either too slow or too imprecise for finding errors in real-life programs. We propose a hybrid pointer analysis that tracks actively ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
2770 pages
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2024
Published in PACMSE Volume 1, Issue FSE
Author Tags
Qualifiers
- Research-article
Funding Sources
- Australian Research Council
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 220Total Downloads
- Downloads (Last 12 months)220
- Downloads (Last 6 weeks)49
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in