EagerMerge: an optimistic technique for efficient points-to analysis
Pages 47 - 58
Abstract
We present an information-merging technique for efficient computation of points-to information for C programs. Invalid use of pointers can lead to hard-to-find bugs and may expose security vulnerabilities. Thus, analyzing them is critical for software analysis as well as optimization. Pointer analysis is a key step during compilation, and the computed points-to information is useful for client analyses from varied domains such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to name a few. Former research on pointer analysis has indicated that the main bottleneck towards scalability is large propagation of points-to information in the constraint graph. To reduce the propagation cost, we present a technique based on temporal similarity of points-to sets. The method tracks pointers whose dynamically changing points-to information remains equal for a while. Based on the optimism gained by observing the points-to sets over time, the analysis decides to merge the corresponding nodes. Using the notion of merge and split, we build a family of points-to analyses, and compare their relative precisions in the context of existing analyses. We illustrate the effectiveness of our approach using a suite of sixteen SPEC 2000 benchmarks and three large open-source programs, and show that the technique improves the analysis time over BDD and bitmap based Hybrid Cycle Detection, well-known Andersen's analysis, and Deep Propagation, affecting minimal precision (precision is 96.4% on an average). Specifically, it is faster than Deep Propagation by 45%.
References
[1]
Iago Abal, Claus Brabrand, and Andrzej Wasowski. 42 Variability Bugs in the Linux Kernel: A Qualitative Analysis. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, ASE ’14, pages 421–432, New York, NY, USA, 2014. ACM.
[2]
L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).
[3]
Marc Berndl, Ondrej Lhoták, Feng Qian, Laurie Hendren, and Navindra Umanee. Points-to Analysis Using BDDs. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, PLDI ’03, pages 103–114, New York, NY, USA, 2003. ACM.
[4]
Georg Cantor. Contributions to the Founding of the Theory of Transfinite Numbers. Dover Publications, 1915.
[5]
Manuvir Das. Unification-based Pointer Analysis with Directional Assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI ’00, pages 35–46, New York, NY, USA, 2000. ACM.
[6]
Greg DeFouw, David Grove, and Craig Chambers. Fast interprocedural class analysis. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’98, pages 222–236, New York, NY, USA, 1998. ACM.
[7]
Jens Dietrich, Nicholas Hollingum, and Bernhard Scholz. Giga-scale Exhaustive Points-to Analysis for Java in Under a Minute. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 535–551, New York, NY, USA, 2015. ACM.
[8]
Manuel Fähndrich, Jeffrey S. Foster, Zhendong Su, and Alexander Aiken. Partial Online Cycle Elimination in Inclusion Constraint Graphs. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI ’98, pages 85–96, New York, NY, USA, 1998. ACM.
[9]
Samuel Z. Guyer and Calvin Lin. Client-driven Pointer Analysis. In Proceedings of the 10th International Conference on Static Analysis, SAS’03, pages 214–236, Berlin, Heidelberg, 2003. Springer-Verlag.
[10]
Ben Hardekopf. BDD-based Lazy Cycle Detection, http://www.cs.ucsb.edu/ benh/research/downloads.html.
[11]
Ben Hardekopf and Calvin Lin. Exploiting Pointer and Location Equivalence to Optimize Pointer Analysis. In Proceedings of the 14th International Conference on Static Analysis, SAS’07, pages 265–280, Berlin, Heidelberg, 2007. Springer-Verlag.
[12]
Ben Hardekopf and Calvin Lin. The Ant and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’07, pages 290–299, New York, NY, USA, 2007. ACM.
[13]
Ben Hardekopf and Calvin Lin. Flow-sensitive pointer analysis for millions of lines of code. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’11, pages 289–298, Washington, DC, USA, 2011. IEEE Computer Society.
[14]
Nevin Heintze and Olivier Tardieu. Ultra-fast Aliasing Analysis Using CLA: A Million Lines of C Code in a Second. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pages 254–263, New York, NY, USA, 2001. ACM.
[15]
Michael Hind and Anthony Pioli. Which Pointer Analysis Should I Use? In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA ’00, pages 113–123, New York, NY, USA, 2000. ACM.
[16]
David Hovemeyer and William Pugh. Finding More Null Pointer Bugs, but Not Too Many. In Proceedings of the 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE ’07, pages 9–14, New York, NY, USA, 2007. ACM.
[17]
Vineet Kahlon. Bootstrapping: A Technique for Scalable Flow and Context-sensitive Pointer Alias Analysis. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’08, pages 249–259, New York, NY, USA, 2008. ACM.
[18]
Atsushi Kanamori and Daniel Weise. Worklist Management Strategies for Dataflow Analysis, MSR Technical Report, MSR-TR-94-12, 1994.
[19]
George Kastrinis and Yannis Smaragdakis. Hybrid Context-sensitivity for Points-to Analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, pages 423–434, New York, NY, USA, 2013. ACM.
[20]
Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04), Palo Alto, California, Mar 2004.
[21]
Chris Lattner, Andrew Lenharth, and Vikram Adve. 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, PLDI ’07, pages 278–289, New York, NY, USA, 2007. ACM.
[22]
Ondˇ rej Lhoták and Laurie Hendren. Scaling Java Points-to Analysis Using SPARK. In Proceedings of the 12th International Conference on Compiler Construction, CC’03, pages 153–169, Berlin, Heidelberg, 2003. Springer-Verlag.
[23]
Yi Lu, Lei Shang, Xinwei Xie, and Jingling Xue. An Incremental Points-to Analysis with CFL-Reachability. In Proceedings of the 22nd International Conference on Compiler Construction, CC’13, pages 61–81, Berlin, Heidelberg, 2013. Springer-Verlag.
[24]
Mario Mendez-Lojo, Martin Burtscher, and Keshav Pingali. A gpu implementation of inclusion-based points-to analysis. In Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, PPoPP ’12, pages 107–116, New York, NY, USA, 2012. ACM.
[25]
Rupesh Nasre. Approximating Inclusion-based Points-to Analysis. In Proceedings of the 2011 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness, MSPC ’11, pages 66–73, New York, NY, USA, 2011. ACM.
[26]
Rupesh Nasre. Exploiting the Structure of the Constraint Graph for Efficient Points-to Analysis. In Proceedings of the 2012 International Symposium on Memory Management, ISMM ’12, pages 121–132, New York, NY, USA, 2012. ACM.
[27]
Rupesh Nasre. Time- and space-efficient flow-sensitive points-to analysis. ACM Trans. Archit. Code Optim., 10(4):39:1–39:27, December 2013.
[28]
Rupesh Nasre and R. Govindarajan. Prioritizing Constraint Evaluation for Efficient Points-to Analysis. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’11, pages 267–276, Washington, DC, USA, 2011. IEEE Computer Society.
[29]
Rupesh Nasre and Ramaswamy Govindarajan. Points-to Analysis As a System of Linear Equations. In Proceedings of the 17th International Conference on Static Analysis, SAS’10, pages 422–438, Berlin, Heidelberg, 2010. Springer-Verlag.
[30]
Rupesh Nasre, Kaushik Rajan, R. Govindarajan, and Uday P. Khedker. Scalable Context-Sensitive Points-to Analysis Using Multi-dimensional Bloom Filters. In Proceedings of the 7th Asian Symposium on Programming Languages and Systems, APLAS ’09, pages 47–62, Berlin, Heidelberg, 2009. Springer-Verlag.
[31]
David J. Pearce, Paul H. J. Kelly, and Chris Hankin. Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis. Software Quality Control, 12(4):311–337, December 2004.
[32]
Fernando Pereira. Wave Propagation / Deep Propagation website, http://compilers.cs.ucla.edu/fernando/projects/pta/home/.
[33]
Fernando Magno Quintao Pereira and Daniel Berlin. Wave Propagation and Deep Propagation for Pointer Analysis. In CGO ’09: Proceedings of the 2009 International Symposium on Code Generation and Optimization, pages 126–135, Washington, DC, USA, 2009. IEEE Computer Society.
[34]
Atanas Rountev and Satish Chandra. Off-line Variable Substitution for Scaling Points-to Analysis. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI ’00, pages 47–56, New York, NY, USA, 2000. ACM.
[35]
Cindy Rubio-González and Ben Liblit. Defective Error/Pointer Interactions in the Linux Kernel. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, ISSTA ’11, pages 111–121, New York, NY, USA, 2011. ACM.
[36]
Marc Shapiro and Susan Horwitz. Fast and Accurate Flow-insensitive Points-to Analysis. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’97, pages 1–14, New York, NY, USA, 1997. ACM.
[37]
Yannis Smaragdakis and George Balatsouras. Pointer Analysis. Foundations and Trends ˜ A ´ C ˆ A˝ o in Programming Languages, 2(1):1–69, 2015.
[38]
Yannis Smaragdakis, George Balatsouras, and George Kastrinis. Set-based Pre-processing for Points-to Analysis. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, pages 253–270, New York, NY, USA, 2013. ACM.
[39]
Smaragdakis, Yannis and Kastrinis, George and Balatsouras, George. Introspective Analysis: Context-sensitivity, Across the Board. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, pages 485–495, New York, NY, USA, 2014. ACM.
[40]
Bjarne Steensgaard. Points-to analysis in almost linear time. In POPL ’96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 32–41, New York, NY, USA, 1996. ACM.
[41]
Yulei Sui, Sen Ye, Jingling Xue, and Jie Zhang. Making context-sensitive inclusion-based pointer analysis practical for compilers using parameterised summarisation. Software: Practice and Experience, 44(12):1485–1510, 2014.
[42]
John Whaley and Monica S. Lam. An Efficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages. In Proceedings of the 9th International Symposium on Static Analysis, SAS ’02, pages 180–195, London, UK, UK, 2002. Springer-Verlag.
[43]
John Whaley and Monica S. Lam. Cloning-based Context-sensitive Pointer Alias Analysis Using Binary Decision Diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, pages 131–144, New York, NY, USA, 2004. ACM.
[44]
Hongtao Yu, Jingling Xue, Wei Huo, Xiaobing Feng, and Zhaoqing Zhang. 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, CGO ’10, pages 218–229, New York, NY, USA, 2010. ACM. Introduction EagerMerge using an Example Points-to Analysis using EM Family of Analyses Relative Precisions of Analyses Points-to Analysis Algorithm Data Structures Experimental Evaluation Analysis Time Precision Memory Effect of Parameter K Effect of Partial Merge Related Work Conclusion Acknowledgments References
Index Terms
- EagerMerge: an optimistic technique for efficient points-to analysis
Recommendations
Points-to analysis with efficient strong updates
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThis paper explores a sweet spot between flow-insensitive and flow-sensitive subset-based points-to analysis. Flow-insensitive analysis is efficient: it has been applied to million-line programs and even its worst-case requirements are quadratic space ...
Points-to analysis with efficient strong updates
POPL '11This paper explores a sweet spot between flow-insensitive and flow-sensitive subset-based points-to analysis. Flow-insensitive analysis is efficient: it has been applied to million-line programs and even its worst-case requirements are quadratic space ...
Refinement-based context-sensitive points-to analysis for Java
Proceedings of the 2006 PLDI ConferenceWe present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths, (2) a context-sensitive heap abstraction, and (3) a context-sensitive call graph. Previous work [21] has shown ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
452 pages
ISBN:9781450343909
DOI:10.1145/2931037
- General Chair:
- Andreas Zeller,
- Program Chair:
- Abhik Roychoudhury
Copyright © 2016 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 ACM 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]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 July 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISSTA '16
Sponsor:
ISSTA '16: International Symposium on Software Testing and Analysis
July 18 - 20, 2016
Saarbrücken, Germany
Acceptance Rates
Overall Acceptance Rate 58 of 213 submissions, 27%
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 238Total Downloads
- Downloads (Last 12 months)8
- Downloads (Last 6 weeks)3
Reflects downloads up to 13 Dec 2024
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