Context-sensitive program analysis as database queries Export

@inproceedings{citeulike:694759, abstract = {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. This paper presents a new framework, based on the concept of deductive databases, for context-sensitive program analysis. In this framework, all program information is stored as relations; data access and analyses are written as Datalog queries. To handle the large number of contexts in a program, the database represents relations with binary decision diagrams (BDDs). The system we have developed, called bddbddb, automatically translates database queries into highly optimized BDD programs. Our preliminary experiences suggest that a large class of analyses involving heap objects can be described succinctly in Datalog and implemented efficiently with BDDs. To make developing application-specific analyses easy for programmers, we have also created a language called PQL that makes a subset of Datalog queries more intuitive to define. We have used the language to find many security holes in Web applications.}, address = {New York, NY, USA}, author = {Lam, Monica S. and Whaley, John and Livshits, Benjamin V. and Martin, Michael C. and Avots, Dzintars and Carbin, Michael and Unkel, Christopher}, booktitle = {PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems}, citeulike-article-id = {694759}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1065169}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1065167.1065169}, doi = {10.1145/1065167.1065169}, isbn = {1-59593-062-0}, keywords = {binary-decision-diagram, datalog, homework-pas-1, language-java, lecture-pas, tool-bddbddb}, location = {Baltimore, Maryland}, pages = {1--12}, posted-at = {2008-11-18 23:10:44}, priority = {0}, publisher = {ACM}, title = {Context-sensitive program analysis as database queries}, url = {http://dx.doi.org/10.1145/1065167.1065169}, year = {2005} }

TY - CONF ID - citeulike:694759 L3 - citeulike-article-id:694759 N2 - 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. This paper presents a new framework, based on the concept of deductive databases, for context-sensitive program analysis. In this framework, all program information is stored as relations; data access and analyses are written as Datalog queries. To handle the large number of contexts in a program, the database represents relations with binary decision diagrams (BDDs). The system we have developed, called bddbddb, automatically translates database queries into highly optimized BDD programs. Our preliminary experiences suggest that a large class of analyses involving heap objects can be described succinctly in Datalog and implemented efficiently with BDDs. To make developing application-specific analyses easy for programmers, we have also created a language called PQL that makes a subset of Datalog queries more intuitive to define. We have used the language to find many security holes in Web applications. CY - Baltimore, Maryland SN - 1-59593-062-0 AD - New York, NY, USA EP - 12 TI - Context-sensitive program analysis as database queries PB - ACM T2 - PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems SP - 1 KW - binary-decision-diagram KW - datalog KW - homework-pas-1 KW - language-java KW - lecture-pas KW - tool-bddbddb AU - Lam, Monica AU - Whaley, John AU - Livshits, Benjamin AU - Martin, Michael AU - Avots, Dzintars AU - Carbin, Michael AU - Unkel, Christopher PY - 2005/// UR - http://dx.doi.org/10.1145/1065167.1065169 ER -