CHESS

CHESS is a tool developed by Microsoft Research in order to discover automatically find bugs in highly concurrent systems. These "Heisenbugs" can otherwise be quite difficult to reproduce due to only occurring when a specific interleaving of threads happens.

To solve the problem, CHESS captures non-deterministic inputs, focusing especially on synchronization APIs that can cause different threads to run. By taking control of this and then allowing CHESS to deterministically decide which path to take, bugs can be found and reproduced. Each run through CHESS takes a different path.

As a Windows developer (including quite a bit of kernel mode), I was impressed with the work done in this paper. They wisely chose to intercept data at a layer higher than the kernel, where they would otherwise lose some of the context needed. I have spent days tracking down concurrency problems, and this tool would make it easier.

I also was intrigued by the search algorithm for determining which state to check next. Because any thread can be pre-empted, I knew when I started the paper that the potential different thread interleavings are practically infinite. They showed that most bugs could be reproduced with only a few threads since all options are searched, and that pre-empting is usually not too interesting. Keeping it too a minimum and only using fair schedules makes the search space manageable.