The HPC Garage

Today, Sangmin will present his work on Falcon, a tool to localize faults in concurrent software, at the International Conference on Software Engineering (ICSE), which is being held in Cape Town, South Africa. Here’s a brief summary of the main ideas underlying Sangmin’s work.

Prior work suggests that concurrency bugs can be described heuristically by patterns of thread-interleaved memory references. However, just because a particular pattern occurs at run-time does not mean it is associated with a bug. Thus, the Falcon technique works as follows. First, we assume that a given program can be executed multiple times, and that there is a test oracle that tells us whether an execution “passed” or “failed.” Falcon then works by (a) observing both patterns and test execution outcomes; and (b) analyzes this data statistically to determine which patterns are most associated with the failing runs, and ranks those patterns. Since the patterns themselves correspond to locations in the source code, this overall analysis effectively gives the programmer a ranked list of program locations to inspect. In Sangmin’s benchmark suite, the first or second most highly ranked patterns/locations were always associated with the bug! By contrast, prior efforts of which we are aware produce either an unranked list of patterns, or a ranked list of individual statements rather than complete patterns.