Computer Science Colloquium

Finding Thousands of Bugs in Millions of Lines of Code

Yichen Xie
Stanford University

Friday, March 28, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Richard, (212) 998-3119


Static analysis is a promising technique that helps programmers detect software errors early in the development cycle. One key challenge in building an effective static analysis is the tradeoff between precision and scalability. Precise analyses are often expensive and cannot be readily applied to industrial size code bases, while scalable analyses have limited analysis power which results in a large number of false warnings.

This talk describes a general framework that allows analysis designers to exploit program structure to achieve both precision and scalability. In particular, we show how to scale Boolean methods, a precise technique that has traditionally been applied to checking small models, to large code bases with millions of lines of code. I will also present experimental results that show the dramatically improved effectiveness of our approach over traditional methods.

In addition, I will briefly describe three other static analysis techniques that I have worked on in the past. The analyses combined have uncovered over a thousand bugs in mature and popular open source software, most of which have been reported and fixed.

top | contact