-
Computer Science Culture Clash
It’s not uncommon for an empirical CS researcher to get a review saying something like “Sure, these results look good, but we need to reject the paper since the authors never proved anything about the worst case.” Similarly, when I interviewed for faculty jobs ten years ago, a moderately famous professor spent a while grilling…
-
Foothill Sunset
I went for a hike last night to celebrate being out from under whatever virus made me more or less sick for most of the last month. The foothill wildflowers are more subdued than the ones that will cover the big mountains in July and August. Four mountain ranges and the Great Salt Lake. Looking…
-
Procedural Decomposition
While teaching a CS class I spend quite a bit of time looking over the shoulders of students whose code doesn’t work. Sometimes they have a simple mistake and I’ll either point it out or ask a question that will lead them to the problem. However, other times the code is just generally not very…
-
Memory Safe C/C++: Time to Flip the Switch
For a number of years I’ve been asking: If the cost of memory safety bugs in C/C++ codes is significant, and if solutions are available, why aren’t we using them in production systems? Here’s a previous blog post on the subject and a quick summary of the possible answers to my question: The cost of…
-
Reading Code
Reading code is an important skill that doesn’t get enough emphasis in CS programs. There are three main aspects: the external view of the code: documentation, comments, APIs, white papers, information from developers, etc. the static view: reading the code like a book the dynamic view: reading the code as it executes, probably with help from…
-
Labyrinth Rims
The Green River’s Labyrinth Canyon begins south of the town of Green River UT; the Labyrinth Rims refers to the area of BLM land on either side of this canyon. We spent four days in this somewhat isolated area of the San Rafael Desert without seeing any other people except for a group in the…
-
Fuzzers Need Taming
[This post explains a paper that we recently made available; it’s going to be presented at PLDI 2013.] Random testing tools, or fuzzers, are excellent at finding bugs that human testers miss. A particularly important use case for fuzzing is finding exploitable bugs, and companies such as Google use clusters to do high-throughput fuzzing. Whether…
-
Stochastic Superoptimization
“Stochastic Superoptimization” is a fancy way to say “randomized search for fast machine code.” It is also the title of a nice paper that was presented recently at ASPLOS. Before getting into the details, let’s look at some background. At first glance the term “superoptimization” sounds like nonsense because the optimum point is already the best one.…
-
Exhaustive Testing is Not a Proof of Correctness
It is often said that exhaustively testing a piece of software is equivalent to performing a proof of correctness. Although this idea is intuitively appealing—and I’ve said it myself a few times—it is incorrect in a technical sense and also in practice. What’s wrong with exhaustive testing in practice? The problem comes from the question:…
-
Proofs from Tests
An idea that I’ve been interested in for a while is that a good test suite should be able to directly support formal verification. How would this work, given that testing usually misses bugs? The basic insight is that a test case is usually telling us about more than just one execution: it’s telling us…