V. Benjamin Livshits
ABSTRACT
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 manipulated pointers held in local variables and parameters accurately with path and context sensitivity and handles pointers stored in recursive data structures less precisely but efficiently. We make the unsound assumption that pointers passed into a procedure, in parameters, global variables, and locations reached by applying simple access paths to parameters and global variables, are all distinct from each other and from any other locations. This assumption matches the semantics of many functions, reduces spurious aliases and speeds up the analysis.We present a program representation, called IPSSA, which captures intraprocedural and interprocedural definition-use relationships of directly and indirectly accessed memory locations. This representation makes it easy to create demand-driven path-sensitive and context-sensitive analyses.We demonstrate how a program checker based on IPSSA can be used to find security violations. Our checker, when applied to 10 programs, found 6 new violations and 8 previously reported ones. The checker generated only one false warning, suggesting that our approach is effective in creating practical and easy-to-use bug detection tools.
- R. A. Ballance, A. B. Maccabe, and K. J. Ottenstein. The program dependence web: A representation supporting control-, data-, and demand-driven interpretation of imperative languages. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 257--271, 1990. Google Scholar
Digital Library
- W. R. Bush, J. D. Pincus, and D. J. Sielaff. A static analyzer for finding dynamic programming errors. In Proceedings of Software Practice and Experience, pages 775--802, 2000. Google ScholarDigital Library
- D. R. Chase, M. Wegma, and F. K. Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 296--310, 1990. Google ScholarDigital Library
- A. Chou, B. Chelf, D. Engler, and M. Heinrich. Using meta-level compilation to check FLASH protocol code. In Proceedings of Architectural Support or Programming Languages and Operating Systems, pages 59--70, 2000. Google ScholarDigital Library
- F. C. Chow, S. Cha, S.-M. Liu, R. Lo, and M. Streich. Effective representation of aliases and indirect memory operations in SSA form. In Proceedings of the Sixth International Conference on Compiler Construction, pages 253--267, 1996. Google ScholarDigital Library
- Cigital. ITS4: Software security tool. http://www.cigital.com/its4/.Google Scholar
- R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Effciently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, October 1991. Google ScholarDigital Library
- R. Cytro and R. Gershbein. Effcient accomodation of may-alias information in SSA form. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 253--267, June 1993. Google ScholarDigital Library
- A. DeKok. PScan: A limited problem scanner for C source files. http://www.striker.ottawa.on.ca/~aland/pscan/.Google Scholar
- R. DeLine and M. Fahndrich. Enforcing high-level protocols in low-level software. In Proceedings of the ACM SIGPLAN '01 Conference on Programming Language Design and Implementation, pages 59--69, 2001. Google ScholarDigital Library
- D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the ACM Conference on Operating Systems Design and Implementation, pages 1--16, 2000. Google ScholarDigital Library
- D. Evans and D. Larochelle. Improving security using extensible lightweight static analysis. IEEE Software, 19(1):42--51, 2002. Google ScholarDigital Library
- Nevin Heintze and Olivier Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of C code. In Proceedings of the ACM SIGPLAN '01 Conference on Programming Language Design and Implementation, pages 146--161, 2001. Google ScholarDigital Library
- C. Lapkowski and L. J. Hendre. Extended SSA numbering: Introducing SSA properties to language with multi-level pointers. In Proceedings of the Seventh International Conference on Compiler Construction, pages 128--143, 1998. Google ScholarDigital Library
- S.-W. Liao, A. Diwa, R. P. Bosch, A. Ghuloum, and M. Lam. SUIF explorer: An interactive and interprocedural parallelizer. In Proceedings of the 26th Annual ACM Symposium on Principles of Programming Languages, pages 37--48, 1999. Google ScholarDigital Library
- A. Pinkus. Yacas manual. http://www.xs4all.nl/~apinkus/manindex.htmlGoogle Scholar
- S. Sagiv, T. W. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. In Proceedings of the 26th Annual ACM Symposium on Principles of Programming Languages, pages 105--118, 1999. Google ScholarDigital Library
- U. Shankar, K. Talwar, J. S. Foster, and D. Wagner. Detecting format string vulnerabilities with type qualifiers. In Proceedings of the 10th USENIX Security Symposium, pages 201--220, 2001. Google ScholarDigital Library
- Secure Software. RATS, a scanning tool. http://www.securesoftware.com/rats.Google Scholar
- B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23th Annual ACM Symposium on Principles of Programming Languages, pages 32--41, 1996. Google ScholarDigital Library
- P. Tu and D. Padua. Efficient building and placing of gating functions. In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 47--55, 1995. Google ScholarDigital Library
- P. Tu and D. Padua. Gated SSA-based demand-drive symbolic analysis for parallelizing compilers. In Proceedings of the 1995 ACM International Conference on Supercomputing, pages 414--423, 1995. Google ScholarDigital Library
- D. Wagner, J. Foster, E. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings of Network and Distributed Systems Security Symposium, pages 3--17, 2000.Google Scholar
- J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of Object-oriented Programming, Systems, Languages, and Applications, pages 187--206, 1999. Google ScholarDigital Library
- R. P. Wilson. Efficient, Context-Sensitive Pointer Analysis for C Programs. PhD thesis, Stanford University, 1998. Google ScholarDigital Library
- R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 1--12, 1995. Google ScholarDigital Library
Index Terms
- Tracking pointers with path and context sensitivity for bug detection in C programs
Recommendations
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 ...
Context transformations for pointer analysis
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationPoints-to analysis for Java benefits greatly from context sensitivity. CFL-reachability and k-limited context strings are two approaches to obtaining context sensitivity with different advantages: CFL-reachability allows local reasoning about data-value ...
Improving software security with a C pointer analysis
ICSE '05: Proceedings of the 27th international conference on Software engineeringThis paper presents a context-sensitive, inclusion-based, field-sensitive points-to analysis for C and uses the analysis to detect and prevent security vulnerabilities in programs. In addition to a conservative analysis, we propose an optimistic ...
Comments