Finding and diagnosing concurrency bugs in a kernel through systematic instruction scheduling

Abstract

Concurrency bugs in the kernel is an important class of bugs, severly affecting the reliability and security of the entire system. If a concurrency bug manifests in the kernel, a system may become unresponsive, or even worse, an attacker may launch a privilege escalation attack to gain root privileges. However, despite such severity of kernel concurrency bugs, finding and diagnosing kernel concurrency bugs are notoriously difficult, mainly due to the non-deterministic behavior of thread interleaving and the enormous search space of thread interleaving. To address these challenges caused by thread interleaving, we propose two techniques, Razzer and Aitia, to find and diagnose kernel concurrency bugs respectively. Specifically, Razzer is a fuzz testing technique to effectively find kernel concurrency bugs. Razzer first identifies over-approximated potential racing spots in the kernel using a static anslysis, and then deterministically triggers a concurrency bug by enforcing thread interleaving at runtime. On the other hand, Aitia is an automated root cause diagnosis technique for kernel concurrency bugs. Aitia first reconstructs a totally-ordered instruction sequence that uses a concurrency failure, and then, Aitia filps an interleaving order of a single pair of instructions to test the causality of each instruction pair to a concurrency failure. As a result, Aitia generates the root cause of a concurrency bug as a chained sequence consisting of interleaved pairs of instructions, called a causality chain. We implement prototypes of Razzer and Aitia, and conduct experiments to verify the effectiveness of these techniques against the latest Linux kernel. As a result, Razzer discovers 30 new concurrency bugs in the kernel, with 16 subsequently confirmed and accordingly patched by kernel developers. In addition, we show that Aitia can successfully diagnose 22 real-world kernel concurrency bugs including six unfixed bugs

5 were correctly diagnosed, and one is waiting for developers’ confirmation.