Efficient Execution Path Exploration for Detecting Races in Concurrent Programs

摘要

Concurrent programs are more difficult to test or debug than sequential programs because their non-deterministic behaviors can produce errors that depend on timing and interleaving of threads. A different interleaving might affect branch outcomes that can lead the execution path into one different from that in which the error was detected. In order to detect concurrent errors, a programmer needs to re-execute the concurrent program many times by changing the interleaving, but it is not always feasible to conduct all the tests due to a large number of possible different interleavings. This paper proposes an efficient method to minimize the number of test cases for detecting errors in a concurrent program. This method generates test cases with different interleavings based on the execution trace. The method reduces redundant test cases without sacrificing the precision of error detection. The method is novel because it exploits the branch structure and utilizes data flows from trace information to identify only those interleavings that affect branch outcomes, whereas existing methods try to identify all interleavings that seem to affect shared variables. In order to reduce the number of test cases, those execution paths with equivalent lock sequences and accesses to shared variables are grouped together into the same "race-equivalent" group and only one member of the group is tested. We evaluated the proposed method against several concurrent Java programs. The experimental results for a Java program for telnet show the number of test cases is reduced from 147, which is based on the existing TPAIR method, to only 2 by the proposed method. Moreover, for concurrent programs that contain infinite loops, the proposed method generates only a finite and very few number of test cases, while many existing methods generate an infinite number of test cases.