Name
Abstract | ||
|---|---|---|
Program analysis has been increasingly used in softwareengineering tasks such as auditing programs for securityvulnerabilities and finding errors in general. Such tools oftenrequire analyses much more sophisticated than those traditionallyused in compiler optimizations. In particular, context-sensitivepointer alias information is a prerequisite for any sound andprecise analysis that reasons about uses of heap objects in aprogram. Context-sensitive analysis is challenging because thereare over 1014 contexts in a typical large program, evenafter recursive cycles are collapsed. Moreover, pointers cannot beresolved in general without analyzing the entire program.This paper presents a new framework, based on the concept ofdeductive databases, for context-sensitive program analysis. Inthis framework, all program information is stored as relations;data access and analyses are written as Datalog queries. To handlethe large number of contexts in a program, the database representsrelations with binary decision diagrams (BDDs). The system we havedeveloped, called bddbddb, automatically translates databasequeries into highly optimized BDD programs.Our preliminary experiences suggest that a large class ofanalyses involving heap objects can be described succinctly inDatalog and implemented efficiently with BDDs. To make developingapplication-specific analyses easy for programmers, we have alsocreated a language called PQL that makes a subset of Datalogqueries more intuitive to define. We have used the language to findmany security holes in Web applications. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1065167.1065169 | PODS |
Keywords | Field | DocType |
context-sensitive program analysis,program analysis,context-sensitive analysis,typical large program,program information,database query,sound andprecise analysis,heap object,developingapplication-specific analysis,bdd program,entire program,sensitivity analysis,binary decision diagram,compiler optimization,relational data | Pointer (computer programming),Alias,Programming language,Computer science,Binary decision diagram,Theoretical computer science,Heap (data structure),Optimizing compiler,Program analysis,Datalog,Data access,Database | Conference |
ISBN | Citations | PageRank |
1-59593-062-0 | 89 | 4.13 |
References | Authors | |
36 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Monica S. Lam | 1 | 5585 | 705.61 |
| John Whaley | 2 | 735 | 53.70 |
| Ben Livshits | 3 | 2108 | 123.83 |
| Michael C. Martin | 4 | 335 | 21.26 |
| Dzintars Avots | 5 | 205 | 9.61 |
| Michael Carbin | 6 | 782 | 38.09 |
| Christopher Unkel | 7 | 89 | 4.13 |