<b>FINDING KERNEL CONCURRENCY BUGS WITH SCALABLE CONTROL- AND DATA-FLOW ANALYSIS</b>

<p dir="ltr">Operating system kernels heavily rely on concurrency for high scalability and performance; however, this reliance also makes kernels susceptible to elusive concurrency bugs. These defects, arising from non-deterministic thread interleavings and the inherent kernel complexity, are notoriously difficult to find and pose serious threats to system reliability and security. While kernel concurrency testing aims to find such bugs by observing actual executions, its efficiency is often hindered by the significant difficulty of navigating vast search spaces of test inputs and thread interleavings.</p><p dir="ltr">This dissertation tackles three fundamental challenges in kernel concurrency testing by developing distinct yet complementary systems, each employing novel and scalable kernel analysis techniques to target a specific critical stage of the testing pipeline. First, to address the challenge of generating effective kernel concurrent inputs, Snowboard systematically analyzes potential inter-thread memory communications in the kernel to construct high-quality inputs. Second, to efficiently explore the thread interleaving space, Snowcat introduces a novel machine learning predictor to predict the code coverage of kernel concurrent inputs and schedules without costly dynamic execution, facilitating effective test prioritization. Finally, to find high-quality sequential inputs—which form the basis of concurrent tests, Snowplow develops a machine learning based white-box mutator to guide kernel input mutations, efficiently discovering inputs that trigger specific kernel code regions. These systems are designed to be synergistic: high-quality sequential inputs from Snowplow provide a stronger foundation for Snowboard’s concurrent input generation, and Snowcat can subsequently optimize the exploration of tests derived from Snowboard, creating a more comprehensive and effective testing strategy.</p>