Baptiste Lepers

OFence: Pairing Barriers to Find Concurrency Bugs in the Linux Kernel 

Knowing which functions may execute concurrently is key to finding concurrency-related bugs. Existing tools infer concurrency using dynamic analysis or by pairing functions that use the same locks. Code that relies on more relaxed concurrency controls is, by and large, out of the reach of existing concurrency-related bug-tracking tools.

In this talk, I will present a new heuristic to automatically infer concurrency in lockless code that relies on memory barriers (memory fences) for correctness, a task made complex by the fact that barriers do not have a unique identifier and do not have a clearly delimited scope.

To infer concurrency between barriers, we propose a novel heuristic based on matching objects accessed before and after barriers. The approach is based on the observation that barriers work in pairs: if a write memory barrier orders writes to a set of objects, then there should be a read barrier that orders reads to the same set of objects. This pairing strategy allows inferring which barriers are meant to run concurrently and, in turn, check the code surrounding the barriers for concurrency-related bugs. As an example of a type of concurrency bug, we focus on bugs related to the incorrect ordering of memory accesses. When we detect inconsistent ordering constraints in the code, we automatically produce a patch to fix them.

We evaluate our heuristic on the Linux kernel. We fixed 12 incorrect ordering constraints that could have resulted in hard-to-debug data corruption or kernel crashes. The patches have been merged in the mainline kernel. None of the bugs could have been found using existing static analysis heuristics.

back to overview

Watch Recording


Dr. Baptiste Lepers is a university lecturer at the University of Sydney. He was a postdoc at EPFL working with Willy Zwaenepoel and at SFU working with Alexandra Fedorova. He completed his PhD at the Université de Grenoble under the supervision of Vivien Quéma. His research topics include scalability of operating systems and databases, parallel graph engines, and static analysis of concurrent applications.