SherLock: Unsupervised Synchronization-Operation Inference

Synchronizations are fundamental to the correctness and performance of concurrent software. They determine which operations can execute concurrently and which can-not—the key to detecting and fixing concurrency bugs, as well as understanding and tuning performance. Unfortunately, correctly identifying all synchronizations has become extremely difficult in modern software systems due to the various forms of concurrency and various types of synchronizations.

Previous work either only infers specific type of synchronization by code analysis or relies on manual effect to annotate the synchronization. This paper proposes SherLock, a tool that automatically infers synchronizations without code analysis or annotation. SherLock leverages the fact that most synchronizations appear around the conflicting operations and encodes the inference problem into a linear system with properties and hypotheses about how synchronizations are typically used. To collect useful observations, SherLock runs the target problem for a small number of runs with feedback-guided delay injection.

We have applied SherLock on 8 C# open-source applications. Without any prior knowledge, SherLock automatically inferred more than 120 unique synchronizations, with few false positives. These inferred synchronizations cover a wide variety of types, including lock operations, fork-join operations, asynchronous operations, framework synchronization, and custom synchronization.