Context-sensitive program analysis as database queries
Monica S. Lam, John Whaley, V. Benjamin Livshits et al. · ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) · 2005
Program analysis has been increasingly used in software engineering tasks such as auditing programs for security vulnerabilities and finding errors in general. Such tools often require analyses much more sophisticated than those traditionally used in compiler optimizations. In particular, context-sensitive pointer alias information is a prerequisite for any sound and precise analysis that reasons about uses of heap objects in a program. Context-sensitive analysis is challenging because there are over 1014 contexts in a typical large program, even after recursive cycles are collapsed. Moreover, pointers cannot be resolved in general without analyzing the entire program.
Cited by 172 works. doi:10.1145/1065167.1065169
Authors
- Monica S. Lam
- John Whaley
- V. Benjamin Livshits
- Michael C. Martin
- Dzintars Avots
- Michael Carbin
- Christopher Unkel
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Principles of database and knowledge-base systems
- The On-Line Encyclopedia of Integer Sequences
- A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities.
- A static analyzer for finding dynamic programming errors
- Points-to analysis in almost linear time
- Detecting format string vulnerabilities with type qualifiers
- Magic sets and other strange ways to implement logic programs (extended abstract)
- Principles of Database and Knowledge-Base Systems Volume II: The New Technologies
- Efficient context-sensitive pointer analysis for C programs