Diagnosing Kernel Concurrency Failures with AITIA

Abstract

Kernel concurrency failures are notoriously difficult to identify and diagnose their fundamental reason, the root cause. Kernel concurrency bugs frequently involve challenging patterns such as multi-variable races, data races with asynchronous kernel threads, and pervasive benign races. We perform an in-depth study of real-world kernel concurrency bugs and elicit three requirements: comprehensiveness, patternagnostic, and conciseness. To fulfill the requirements, this paper defines the root cause as a chained sequence of data races, called a causality chain. A causality chain is presented as a comprehensive form to explain how a failure eventually happens in the presence of multi-variable races rather than simply pointing out a few instructions related to the root cause. To build a causality chain, this work proposes two practical approaches: Least Interleaving First Search to reproduce a concurrency failure, and Causality Analysis to identify the root cause. Causality Analysis runs the kernel to confirm what data races contribute to the failure among all detected data races. The approach is pattern-agnostic because it dynamically tests data races without counting on pre-defined patterns. While testing data races, Causality Analysis rules out failure-irrelevant data races such as benign races, producing a concise causality chain. AITIA is a system implementing the two approaches. By evaluating AITIA with 22 real-world concurrency failures, we show that AITIA can successfully build their causality chain. With AITIA, we found the root causes of six unfixed bugs; three bugs were concurrently fixed, the root causes of three bugs were confirmed by kernel developers.