Static detection of software errors

Automatic program analysis tools are increasingly developed and deployed to combat the perenniel software quaility problem that plagues the IT industry. Traditional tools faces a stark tradeoff between precision and scalability: scalable tools are often imprecise, limiting themselves to detecting relatively shallow errors; precise tools are often not scalable and are thus only applied to simplified models of the core parts of large systems. This study presents techniques and results on how to exploit existing structures of large software systems to make precise program analyses scale. As an example, the author show how to scale Boolean Satisfiability (SAT) based analysis - traditionally applied to small models with hundreds of lines of code - to the whole Linux kernel, which contains millions of lines of code. This study is directed to designers and users of software analysis tools alike. It offers detailed descriptions of several state-of-the-art automatic error detection algorithms and presents experimental results on mature open-source systems. The approach can be potentially generalized to the design and deployment of a wide range of program analysis tools.