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 opensource
systems. The approach can be potentially generalized to the design
and deployment of a wide range of program analysis tools.