Falcon: fault localization in concurrent programs (ICSE 2010) - A Short Review

Falcon: fault localization in concurrent programs - Sangmin Park, Richard W. Vuduc, Mary Jean Harrold

This paper presents a new dynamic fault localization technique that can pinpoint faulty data-access patterns in multithreaded concurrent programs. The authors explain the technique by means of running example which proceedings with the following steps

-          The authors start with defining concurrency violations of interest for this paper

o   Data Race – do not focus on it in this paper but the method can handle this

o   Order Violation – Conflicting interleaving patterns

o   Atomicity Violation –  Unserializable interleaving patterns

-          Online Pattern Identification, in this step they monitor an instrumented version of the program which is run multiples times. In each of these runs a fixed sliding window is used to identify patterns. Any interesting pattern is an interleaving of read write accesses to a shared memory location. These patterns are associated with passing and failing executions.

o   Within a particular siding window look for access for a particular shared memory location

o   Once the window becomes full, scan it for unserializable interleaving patterns

o   If there is no unserializable interleaving pattern check for conflicting interleaving patterns

o   Emit all patterns found

o   These patterns are then associated with passing and failing executions

-          In the second step the patterns are ranked using suspiciousness (based on Jaccard Index) which represents the likelihood of a pattern being related to a fault.

                                                                                                

A prototype implementation (FALCON) of this technique in Java and a detailed empirical study of the system is given next in the paper. They evaluate the effectiveness and efficiency of the system with respect to the ability to indentify suspicious patterns which relate to faults. The results from the study of window size show that for most cases a moderate window (10) size can still enable FALCON to detect many relevant suspicious patterns (75%). Finally a study indirectly compares FALCON to CCI (which is a related recent work done in fault localization) the authors conclude that FALCON ranks the patterns much better than the related ranking of accesses from CCI.

Even though the initial study is promising there are a number of limitations which can form future work, current system only take 1 test input and execute the program multiple times. There is no relation between the pattern and the actual bug that causes the suspicious pattern.  A single bug may give rise to many patterns or vice versa. There are other types of violations like deadlocks which are not currently indentified using FALCON.