-
Two Rules for Random Testing
When you run a test case on a piece of software, you’re conducting an experiment where the null hypothesis is “the system under test correctly executes this test.” The problem is that the value of each such experiment is small because there are so many possible inputs. Random testing has a stronger null hypothesis: “the…
-
Probabilities in Random Testing
A typical real computer system has an extremely large input space and no testing method can cover more than an infinitesimal part of it. On the other hand, broad regions of the input space will trigger bugs. The problem is that we do not know the shapes or locations of the buggy parts of the…
-
Outgunned
Several years ago I published my favorite kind of paper: it took a problem that was hard to solve by hand, and solved it using 20% cleverness and 80% brute force. The details don’t matter here, but the solution had scalability problems. Therefore, the next iteration of the work (done primarily by a very smart…
-
The Day I Learned To Love Perl
Following my second year of grad school, I spent the summer of 1997 as an intern for Myricom, a company in the L.A. area that makes really fast local-area networks. It was a great place to work: small, and filled with super-smart ex-Caltech people. One day I was hacking while the important people were in…
-
Cryptocontributions, Blogs, and How Science Works
Most people — including many scientists — understand the process of science to be repeated application of the scientific method. In this model, a hypothesis is formulated, experiments are conducted to test the hypothesis, data is analyzed, and the results usually lead to a new hypothesis. This adequately captures the “99% perspiration” aspect of doing…
-
Csmith @ PLDI
My group’s paper Finding and Understanding Bugs in C Compilers was accepted to PLDI 2011 (subject to shepherding, which is generally a pretty calm process). I’m excited about this since we’ve put a lot of effort into this project. Thanks to all the people who helped us make this work better!
-
The Piano Test for Program Verification
[Update from Feb 1 2011: I’ve written a new post that adds some technical details.] Here’s a little thought experiment: You’re spending the day visiting the Utah computer science department. We’re chatting and I describe a software verification project where my group has proved that some particular version of OpenSSH is memory safe: it will…
-
The Synergy Between Delta Debugging and Compiler Optimization
Before reporting a compiler bug, it’s best to reduce the size of the failure-inducing input. For example, this morning I reported an LLVM bug where the compiler enters an infinite loop when compiling this C code: static int foo (int si1, int si2) { return si1 – si2; } void bar (void) { unsigned char…