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.
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
