Guided test for detecting concurrency errors

Mainstream programming is migrating to concurrent archi-tectures to improve performance and facilitate more complex computation. The state of the art analysis tools for detect-ing concurrency errors such as deadlocks and race condi-tions are imprecise, generate a large number of false error reports, and require manual verification of each error report. In this paper we present a guided test approach to help au-tomate the verification of reported errors in multi-threaded Java programs. The input to the guided test is a small se-quence of program locations (partial error trace) manually generated from the potential errors reported by the impre-cise static analysis techniques. The guided test dynamically controls thread schedules during program execution in an effort to drive the program through the partial error trace and elicit a concurrency error. The scheduling decisions are made based on a two tier ranking system that first considers the portion of the error trace already observed and the per-ceived closeness to the next location in the error trace. The error traces generated by the technique are real and require no manual verification. We show the effectiveness of our ap-proach in a set of benchmarked concurrency programs, and we automatically verify the existence of race conditions and deadlocks in the JDK 1.4 concurrent libraries as reported from the Jlint static analysis tool. 1