LR-Miner: Static Race Detection in OS Kernels by Mining Locking Rules

Data race is one of the most common concurrency issues in OS kernels, and it can cause severe problems like system crashes and privilege escalation. Therefore, detecting kernel races is important and necessary. A critical step of kernel race detection is to identify locking rules that which variable should be protected by which lock. However, due to insufficient documents of kernel concurrency, it is challenging to identify accurate locking rules, causing existing approaches to produce many false results in kernel race detection. In this paper, we design a new static analysis approach named LR-Miner, to effectively detect data races in OS kernels by mining locking rules from kernel code. LR-Miner consists of three key techniques: (1) a field-aware mining method that constructs and statistically analyzes the structure field relation between locks and accessed variables, to mine accurate locking rules from kernel code; (2) an alias-aware checking method to detect data races that violate the mined locking rules; (3) a pattern-based estimation strategy to estimate the security impact of the found races and identify harmful ones. We have evaluated LR-Miner on two popular OS kernels including Linux and FreeBSD, and it finds 306 real races with a false positive rate of 19.9%. Among these found races, 200 are estimated to be harmful, and 61 of them have been confirmed by kernel developers. 10 harmful races have been assigned with CVE IDs.