Google engineers that contribute to the Linux kernel have announced that they have discovered hundreds of "Race Conditions", in the kernel using KCSAN. The company has long been working on AddressSanitizer to find errors related to memory corruption or UndefinedBehaviorSanitizer for undefined behavior in code.
This time, Google offers a new “Race Conditions” detector for the Linux kernel called KCSAN (Kernel Concurrency Sanitizer). These critical vulnerabilities are not new. In fact the Race Conditions occur when two or more threads in the same process access the same memory location simultaneously, where at least one of the accesses is for writing, and when the threads do not use any exclusive locks to control their access to this memory.
When these conditions are met, the access order is not deterministic and the calculation may give different results from one run to another depending on this order.
Race Conditions are increasingly seen as concurrent access errors and are difficult to duplicate and diagnose in parallel programs. The Linux kernel is a large-scale software system, in which thread-intensive parallelism and non-deterministic thread interleaving are more subject to competitive conditions.
Some competitive situations can be benign, but many of them identified so far are considered mistakes.
The Linux kernel provides several mechanisms to avoid and manage these types of conditions Since there are tools such as Thread Analyzer or KTSAN (Kernel Thread Sanitizer) to detect critical execution errors in the Linux Kernel.
However, Google, which also contributes to the Linux kernel, recently proposed KCSAN, a new Race Conditions detector for the Kernel, similar to KTSAN.
According to Google, KCSAN focuses on discovering competitive situations in the kernel code. This dynamic critical hit detector is an alternative to the Kernel Thread Sanitizer (KTSAN).
As per Google's explanation, KCSAN is based on sampling monitoring points, unlike KTSAN detector, which is a critical race detector before the event. Key priorities in KCSAN design are lack of false positives, scalability, and simplicity.
KCSAN uses compilation tools to access memory. KCSAN is compatible with the GCC and Clang compilers. With GCC, it requires version 7.3.0 or later and with Clang, it requires version 7.0.0 or later.
On the project's GitHub pageGoogle's Marco Elver wrote that using KCSAN in tests last month, they found in just two days more than 300 unique core competition situations. KCSAN provides several configuration options to customize its behavior.
“We have been using KCSAN through Syzkaller for several weeks, and we have found a lot of bugs. Initially in September 2019, we identified more than 300 unique competition situations in just two days, ”he wrote.
Google said the overall approach is based on DataCollider, another dynamic detector of competitive situations in the kernel modules. But unlike DataCollider, KCSAN does not use hardware monitoring points, instead it relies on compilation tools.
The monitoring points are implemented using efficient encoding that stores the type, size, and access address in a long file. The benefits of using flexible monitoring points are portability and greater flexibility in limiting the access that a monitoring point can activate.
Here are some of the key points that KCSAN made for Google:
- High performance: KCSAN runtime is minimal and does not require shared state locking for each access. The result is much better performance than KTSAN.
- No additional memory: according to Google, no cache is required. The current implementation uses a small number of lengths to encode the monitoring point information, which is negligible.
- Memory command: KCSAN does not know the Linux kernel memory model (LKMM) control rules. This can result in critical races lost (false negatives) compared to a pre-event race detector like KTSAN
- Precision: According to Google, KCSAN is imprecise because it uses a sampling strategy;
- Requires annotation: minimal annotation is required outside of the KCSAN runtime. In the case of a precondition event listener, any omission leads to false positives, which is particularly important in the context of the kernel that includes custom timing mechanisms.
- Detection of dynamic writes from devices: By checking data values during watchpoint setup, dynamic writes from devices can also be detected.