News and Coverage

Bug Finding by Solving Constraints in the Cloud

Location: Crystal Room Level: Intermediate
Average rating: ****.
(4.00, 1 rating)

David MolnarI will talk about how to improve software “fuzz testing” by using new advances in constraint solving and cloud computing. Traditional fuzz testing, or sending “random-looking” inputs to software, has a long history of finding serious bugs, starting with a dark and stormy night in 1989, and continuing on through the “Month of Browser Bugs” and friends in 2006. Unfortunately, traditional fuzz testing does not look at what the software actually does with these inputs, which limits the kinds of bugs it can find.

The first key advance Molnar will talk about is looking inside a piece of running software, then coming up with systems of constraints that capture how the program works. He will show how solving these constraints allows us to generate new inputs to a program that are more likely to find bugs.

While solving these constraints in general is a difficult problem, he will show that current free and open source software solvers are capable of solving constraints derived from most current software quickly. He will discuss several recent systems that use this technique, then go into depth on Catchconv, a GPLv2 licensed system developed at Berkeley that uses this approach.

The second key advance he will talk about is the use of cloud computing for testing, specifically Amazon’s Elastic Compute Cloud. He will show, a service they have developed at UC Berkeley to test Linux binary programs. That service uses a cluster at Berkeley and Amazon EC2 to run through thousands of test cases, sieve out the tests which cause programs to crash, and then generates reports for programmers. The Metafuzz code is hosted on Sourceforge and distributed under a BSD license, so others can contribute and improve the work. The vision is to make effective testing available at low cost, in whatever quantity a programmer desires.

Finally, Molnar will briefly discuss the wide variety of other problems that can be approached using recent advances in constraint solvers. He will demonstrate these solvers in action and give pointers to free and open source solvers that attendees can download and use in their own projects. He will show attendees how their specific problems can contribute to a competition between constraint solvers, thereby causing smart people from all over the world to work on solving their problem.

David Molnar

University of California, Berkeley

David Molnar is a PhD candidate at University of California, Berkeley, interested in cryptography, privacy, and computer security. Previously worked on privacy issues in Radio Frequency Identification (RFID) , including testimony on RFID issues to the California Legislature and as a volunteer expert for Berkeley and San Francisco public libraries. Now works on applying new techniques in constraint solving to the problem of finding software bugs.

David is a previous National Science Foundation Graduate Fellow and Intel Open Collaboration Research Fellow.

  • Sun Microsystems
  • Yahoo! Inc.
  • IEEE
  • Make magazine
  • Orange Labs