∞
Simplifying and Isolating Failure-Inducing Input – Zeller and Hildebrandt
Abstract
Given some test case, a program fails. Which circumstances of the test case are responsible for the particular failure? The Delta Debugging algorithm generalizes and simplifies some failing test case to a minimal test case that still produces the failure; it also isolates the difference between a passing and a failing test case.
Comments Delta debugging is an interesting idea, and reasonably broadly applicable. They even manage to apply it to a series of UI input actions by using a UI replay tool. However, setting up the machinery to get such a technique working is non-trivial and pretty program/system specific. If it’s going to be worth your while, you’d better have a lot of bug inducing inputs that need reducing, or some very hard to track down bugs. The authors point out that programmers have historically done this sort of thing manually, and that may be the approach that makes the most economic sense.
They previously applied the technique to program versions, honing in on the program changes that caused a regression. This seems more useful to me, though even this is something that I’ve felt the need to do only a handful of times in the 15+ years that I’ve even had a version control system to do it with.
If one could set up a totally automated bug triage system (and this is a colossally big if), I could see this technique fitting in to reduce whatever input or trace data came along with the bug report. However, getting machine readable data that can be used to reliably reproduce a bug is usually 90+% of the battle.
∞
DART: Directed Automated Random Testing – Godefroid, et al.
Abstract
Presents a new tool, DART, for automatically testing software that combines three main techniques: (1) automated extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of a test driver for this interface that performs random testing to simulate the most general environment the program can operate in; and (3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths.
Comments
This paper introduced the idea of what is now called concolic testing, which is a clever idea for increasing test coverage. However, like so much research in test generation, it seems to have failed to achieve much traction in industry. The idea as presented here is problematic: they just extract functions from your program and start calling them with random values. That’s definitely likely to cause things to break, but it may be hard to separate the useful errors (i.e. those that might occur in your program) from the myriad crashes induced by calling functions with arguments that are “known” never to occur.
What would help this technique a great deal is a concise way to provide tighter constraints on function input values. There’s already a lot of work in that area on things like nullability enforcing type systems and code contracts. Given sane bounds on function inputs, it becomes a lot more interesting to throw random values at the function that are within specified bounds and perturb them to obtain maximal coverage of the code within the function. You still have no idea whether the output is “correct”, but if you have any assertions in the function or the code called by the function, you might tease out a violation of those.
In the meanwhile, concolic testing could prove fruitful if combined with something like Quick Check.
∞
Object and Reference Immutability using Java Generics – Zibin, et al.
Summary
Proposes an extension to Java’s type system (Immutable Generic Java, or IGJ) for checking class, object and reference immutability. The type system supports transitivity (properties hold for entire object graph), it is static (nothing tracked or checked at runtime), it supports polymorphism (abstracting over mutability), and it’s fairly simple (adds a mutability type parameter and a few annotations). Syntax and typing rules are described. Various wrinkles covered: constructing read-only objects, covariant and no-variant type parameters, allowing mutation of non-state (caches, memos). Proof of soundness included (at no extra charge!).
Comments
I like the idea of expressing mutability constraints and having them enforced by the compiler. Class and object immutability are also great, especially in the wild world of parallelism, because you sometimes want to be sure that no one is going to mutate an object, not just whether or not you are allowed to do so. The use of the first type parameter to communicate mutability is clever and works nicely with the existing generic type system.
It’s not clear whether using such a system is all-or-nothing. Can I just use mutability annotations in places where I feel the need to be explicit? Is everything else “mutable by default”? I also don’t have a good feeling for whether communicating and enforcing mutability restrictions is worth the syntactic overhead. I’d have to put this in action on a decent size codebase to really tell. Fortunately, I can since there’s a checker for it. Another item for the list of things to do once I’m out of the woods on my current research project.
∞
Mining Temporal Specifications from Object Usage – Wasylkowski and Zeller
Summary
Describes technique (and tool, Tikanga) for computing operational preconditions: a description of how to satisfy a function’s preconditions (e.g. call createX to obtain an X, then you can pass that to consumeX). Process: create object usage models for identifiable objects; convert to prefix models that focus on call events; transform prefix models into Kripke structures; generate a set of CTL formulas using the Kripke structures; model check those and filter out any that do not hold; for each formal parameter of a method, look for sets of CTL formulas that are common to many objects passed to that method, these form an operational precondition. Violations of operational preconditions are then located, ranked and reported to the user as potential bugs. Evaluation provided on six extant Java projects.
Comments
This is definitely an interesting idea. In theory, you can figure out how the arguments to methods are generally “prepared” before a method is called. Since this includes the receiver, this encompasses something of the idea of type states as well. Then you can either use this information to provide usage examples or look for potentially bogus usage which might indicate bugs. However, its application to that latter task turned up an awful lot of false positives (spoken as a programmer, rather than a researcher; apparently 56% false positives is good compared to other research techniques). They didn’t characterize the types of bugs it found, and I’d be interested in seeing that. Are they subtle? Are they the sorts that are already found by already widely deployed techniques? I’m also curious about how difficult it is to wade through the false positives. Does one have to pore over a lot of source to tell whether the tool is pointing out something meaningful?
An interesting and readable collection of essays on astrophysics. The author isn’t afraid to expose his sense of humor, which livens up potentially dry material at the cost of the occasional groaner. He ranges somewhat randomly through astronomy, physics, and math, with a fair bit of history thrown in for color and background. It was a relaxingly easy read, especially in contrast to the first few hundred pages of The Road to Reality that I soldiered through on my winter break.
In the nineteenth century, which was a dark and inflationary age in typography and type design, many compositors were encouraged to stuff extra spaces between sentences. Generations of twentieth-century typists were taught to do the same, by hitting the spacebar twice after every period. Your typing as well as your typesetting will benefit from unlearning this quaint Victorian habit.
Robert Bringhurst, “The Elements of Typographic Style”
