We present a new decision procedure for detecting property violations in concurrent programs that use lock-based synchronization, where each thread's lock operations are properly nested (à la synchronized methods in Java). The technique checks properties expressed as indexed phase automata (PAs) -- a class of non-deterministic finite automata in which the only loops are self-loops.

Our interest in PAs stems from their ability to capture atomic-set serializability violations. (Atomic-set serializability is a relaxation of atomicity to only a user-specified set of memory locations.) We implemented the decision procedure and applied it to detecting atomic-set-serializability violations in concurrent Java programs. Compared with a prior method based on a semi-decision procedure, not only was the decision procedure 7.5X faster overall, but the semi-decision procedure timed out on about 68% of the queries versus 4% for the decision procedure.

[Click here to access the (revised) technical report: tr1649r.pdf.]