Context-sensitive program analysis as database queries

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.