Finding driver bugs with DR. CHECKER
Drivers are a consistent source of kernel bugs, at least partly due to less
review, but also because drivers are typically harder for tools to
analyze. A team from the University of California, Santa Barbara has set
out to change that with a static-analysis tool called DR. CHECKER. In a paper
[PDF] presented at the recent 26th USENIX
Security Symposium, the team introduced the tool and the results of
running it on nine production Linux kernels. Those results were rather
encouraging:
"it
correctly identified 158 critical zero-day
bugs with an overall precision of 78%
".
Technique
The researchers, Aravind Machiry, Chad Spensky, Jake Corina, Nick Stephens, Christopher Kruegel, and Giovanni Vigna, added their analysis module to the LLVM compiler. It is a "soundy" analysis—a term derived from "soundiness"—which means that it is mostly based on fully accurate (or sound) reasoning about the program. In order to keep the analysis space tractable and to provide usable results without overwhelming numbers of false positives, various unsound assumptions and tradeoffs are made. The researchers tried to limit those, however:
As part of the motivation for creating the tool, the team describes an integer overflow bug found in the Huawei Bastet driver. The driver uses a user-controlled field in a structure to calculate the size of a buffer to allocate, but the integer overflow allows an attacker to cause the buffer to be far too small, resulting in a buffer overrun. As described in the paper, the bug demonstrates the need for a tool like DR. CHECKER:
DR. CHECKER takes a modular approach to its analysis. There are two analysis clients that are invoked throughout the analysis pass through the code, which is called the "soundy driver traversal" (SDT). Those clients share global state and can benefit from each others' results. Once that pass is complete, the global state is used by various vulnerability detectors to find specific kinds of bugs and generate warnings.
In order to focus solely on the driver code, the tool makes the assumption that Linux API calls operate completely correctly, so that they lie outside the scope of the analysis. That means that only function calls within the driver need to be followed and tracked
The two clients implement a "points-to" analysis to determine where pointers are pointing in a field-sensitive way and a "taint" analysis to determine when values could have been provided by user space. The points-to client tracks dynamic allocation as well as static and automatic variables. It knows enough about the kernel API to recognize allocation functions; it can also recognize the effects of library calls like memcpy(). The taint analysis looks at the sources for tainted data, either as arguments to entry points (e.g. ioctl()) or via kernel functions that copy data from user space (e.g. copy_from_user()).
There are eight separate vulnerability detectors that are each briefly described in the paper. Almost all of them look for incorrect handling of tainted data in one way or another, so they are heavily reliant on the taint analysis results. The tests look at such things as improperly using tainted data (e.g. passing to risky functions like strcmp()), arithmetic on tainted data that could lead to an under or overflow, casts to differently sized types, dereferencing tainted pointers, accessing global variables without proper locking, and so on.
The paper goes into quite a bit of detail of the techniques used and is worth a read for those interested. There were some logistical hurdles to overcome in trying to identify the vendor drivers in multiple kernel source trees. Beyond that, finding the entry points into the drivers was tricky as well; different subsystems have different views of the offset for a driver's ioctl() function, for example.
Results
The researchers ran DR. CHECKER on the drivers in nine mobile devices from four different manufacturers. A total of 3.1 million lines of code was analyzed in 437 separate drivers. They also ran four other static-analysis tools: flawfinder, RATS, Cppcheck, and Sparse. Ultimately, those tools were found wanting for a variety of reasons, most often because of the number of false positives generated.
DR. CHECKER uses Clang to compile each of the driver source files into LLVM bitcode, which contains the compiler's intermediate representation. Compiling the drivers required some changes to Clang to support the GCC-specific constructs and compiler flags used by the normal kernel build. Those individual bitcode files are then combined using the llvm-link tool to create a single file to hand off to DR. CHECKER.
Some 5,000 warnings were generated, of which nearly 4,000 were verified as correct by the team. Of those, 158 were actual bugs that were reported upstream and fixed. So 78% of the reports were correct and 3% actually resulted in security fixes for the kernel. The paper noted that there are a number of improvements that could be made to reduce duplicated, but correct, warnings as well as false positives. It also points out that the code could likely be adapted for other code bases.
Overall, DR. CHECKER looks like a useful tool that could potentially be applied more widely. Vendors may wish to analyze their drivers and device makers could do the same for all of the drivers in their device. It would also seem like there may be some lurking bugs in mainline drivers that could be ferreted out using the tool.
[Thanks to Paul Wise for pointing us toward DR. CHECKER.]
| Index entries for this article | |
|---|---|
| Security | Static analysis |