Sorry, you need to enable JavaScript to visit this website.

Linux Kernel Performance

Linux development evolves rapidly. The performance and scalability of the OS kernel has been a key part of its success. However, discussions have appeared on LKML (Linux Kernel Mailing List) regarding large performance regression between kernel versions. These discussions underscore the need for a systematic and disciplined way to characterize, improve, and test Linux kernel performance. Our goal is to work with the Linux community to further enhance the Linux kernel with consistent performance increases (avoiding degradations) across releases. The information available on this site gives community members better information about what 0-Day and LKP (Linux Kernel Performance) are doing to preserve performance integrity of the kernel.

Fuzzing in 0-Day: Finding and Debugging Even the Most Obscure Bugs in Linux*

BY 01 Staff (not verified) ON Aug 23, 2017

Abstract

The Linux* kernel is an incredibly complex piece of software comprised of millions of lines of code contributed by a myriad of developers around the globe. It is continually exposed to untrusted user input. Testing the kernel is important to ensure its quality. Up until now, it has been difficult and time-consuming to pinpoint and debug the most obscure bugs in the kernel. In this article, we discuss the integration of the fuzz test into an automated test service to help developers identify and resolve even the most obscure bugs in Linux.

The fuzz test

The fuzz test is an automated software testing technique used to reveal potential software bugs or security holes in a program. The fuzz test, or “fuzzing”, works by providing massive amounts of random, invalid, and unexpected data — referred to as “fuzz” — as inputs to a program. The program is then monitored for exceptions such as crashes, for failing built-in assertions, or to find potential memory leaks. Individual fuzz tests are also referred to as “fuzzers”. Fuzzers test programs dealing with untrusted user inputs. Fuzzing works best at detecting problems that can cause a program to crash, such as buffer overflow, cross-site scripting, denial of service attacks, format bugs, and other such issues.

Fuzzing the kernel

The Linux kernel is a piece of software that is continually exposed to untrusted user input, so it is important to do fuzzing for the Linux kernel. The basic implementation of fuzzing for the Linux kernel has been around for a long time. The fuzz test feeds huge numbers of random inputs through system calls and then testers watch for crashes. A basic implementation that only emits random inputs blindly is not efficient enough to detect the most obscure bugs in the kernel. Although there is a “template-based” fuzzer that has built-in knowledge to generate more valid input patterns, it still requires manual work to create these pre-defined templates. Besides, even if we find an obscure bug with fuzzing, there isn’t a convenient reproducer program for the developer to use to debug it easily. What’s more, it is time-consuming to identify the culprit commit that caused the kernel failure.

Solution

The 0-Day CI (Continuous Integration) test service is a well-known, automated test service that provides comprehensive test coverage of the Linux kernel. Integrating fuzzing into 0-Day CI can leverage its ability to find the exact patch that caused the kernel bug. With fuzzing integrated into 0-Day CI, we can reveal more kernel security holes and improve the overall code coverage of 0-Day CI’s Linux kernel testing.To detect more kernel bugs with fuzzing more efficiently, we integrated a coverage-guided kernel fuzzer called syzkaller into 0-Day CI.

Syzkaller not only relies on templates that indicate the argument domains for each system call, but also uses feedback from code coverage information to guide the fuzzing. The fuzzer tries to maximize the amount of code covered (building an ever-expanding corpus of test inputs along the way), by mutating existing inputs and saving anything that hits new code. Syzkaller also has a useful utility, called syz-repro, to generate the exact reproducer program by using the crash log. This not only facilitates developers’ debug/fix work, but also make it possible for 0-Day CI to bisect the culprit commit using the small reproducer. An example of the framework is shown below:

Syz-repro can generate small reproducer programs for 0-Day CI to dispatch on test machines and do bisection, if needed. To prevent various regressions from leaking into the mainline kernel, 0-Day CI monitors hundreds of maintainers’ and developers’ trees and periodically merges these trees as well as patches in Linux Kernel Mailing List (LKML). 0-Day CI then generates a general kernel image for syzkaller to run to detect more potential regressions across the kernel subsystems at an early stage of development.

Result

0-Day CI got its first bisect report [2] for the syzkaller test quickly after the service was deployed. The original report in syzkaller contains a kernel warning as shown below:

 

------------[ cut here ]------------ 
WARNING: CPU: 2 PID: 23784 at /kbuild/src/consumer/kernel/time/hrtimer.c:805 
hrtimer_forward+0x1f0/0x2e0 
Kernel panic - not syncing: panic_on_warn set ... 

CPU: 2 PID: 23784 Comm: syz-executor2 Not tainted 4.12.0-rc4-wt-ath-05992-g2728455 #1 
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.7.5-20140531_083030-gandalf 
04/01/2014 
Call Trace:
 dump_stack+0xb3/0x10b
 panic+0x1b4/0x392
 __warn+0x1c4/0x1e0
 report_bug+0x213/0x2d0
 do_trap+0x37f/0x480
 do_error_trap+0x11e/0x240
 do_invalid_op+0x1b/0x20
 invalid_op+0x1e/0x30 
RIP: 0010:hrtimer_forward+0x1f0/0x2e0 
RSP: 0018:ffff8800310f7cf8 EFLAGS: 00010083 
RAX: 0000000000010000 RBX: ffff880032334cd8 RCX: ffffc90002e2b000 
RDX: 000000000000002c RSI: ffffffff813a5530 RDI: ffff880032334d10 
RBP: ffff8800310f7d40 R08: ffff88003ffd909c R09: ffff88003ffd9088 
R10: ffff88003ffd9098 R11: ffff88003ffd9090 R12: 14c5e4ad3cf5542d 
R13: 00000042e4843739 R14: 14c5e4f021798b66 R15: 1bc16d674ec80000
 common_hrtimer_forward+0x4b/0x60
 common_timer_get+0x3dc/0x4d0
 SyS_timer_gettime+0x123/0x220
 entry_SYSCALL_64_fastpath+0x1f/0xbe 
RIP: 0033:0x450749 
RSP: 002b:00007f36dcb38b68 EFLAGS: 00000216 ORIG_RAX: 00000000000000e0 
RAX: ffffffffffffffda RBX: 00000000006f8000 RCX: 0000000000450749 
RDX: 0000000000000000 RSI: 0000000020003000 RDI: 0000000000000000 
RBP: 0000000000000046 R08: 0000000000000000 R09: 0000000000000000 
R10: 0000000000000000 R11: 0000000000000216 R12: ffffffffffffff9c 
R13: 0000000020003000 R14: 0000000000000001 R15: 0000000000000000 
Dumping ftrace buffer:
   (ftrace buffer empty) 
Kernel Offset: disabled 
Rebooting in 86400 seconds..

 

This warning resulted in panic due to syzkaller setting panic_on_warn=1 for its qemu configuration. 0-Day CI continued to figure out the exact reproducible sequences that triggered this crash with the help of syz-repro utility. After a few iterations, syz-repro was managed to generate a small c program that reproduces the crash on the test kernel. Below is the main part of the program.

 

long r[23]; 
void loop() 
{ 
        memset(r, -1, sizeof(r)); 
        r[0] = execute_syscall(__NR_mmap, 0x20000000ul, 0x6000ul, 0x3ul, 0x32ul, 0xfffffffffffffffful, 0x0ul, 0, 0, 0); 
        NONFAILING(*(uint64_t*)0x20001fb0 = (uint64_t)0x0); 
        NONFAILING(*(uint32_t*)0x20001fb8 = (uint32_t)0x1); 
        NONFAILING(*(uint32_t*)0x20001fbc = (uint32_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001fc0 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001fc8 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001fd0 = (uint64_t)0x4); 
        NONFAILING(*(uint64_t*)0x20001fd8 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001fe0 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001fe8 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001ff0 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20001ff8 = (uint64_t)0x0); 
        r[12] = execute_syscall(__NR_timer_create, 0x0ul, 0x20001fb0ul, 0x20000ffcul, 0, 0, 0, 0, 0, 0); 
        if (r[12] != -1) 
                NONFAILING(r[13] = *(uint32_t*)0x20000ffc); 
        r[14] = execute_syscall(__NR_clock_gettime, 0x4ul, 0x20002ff0ul, 0, 0, 0, 0, 0, 0, 0); 
        if (r[14] != -1) 
                NONFAILING(r[15] = *(uint64_t*)0x20002ff0); 
        if (r[14] != -1) 
                NONFAILING(r[16] = *(uint64_t*)0x20002ff8); 
        NONFAILING(*(uint64_t*)0x20003fe0 = (uint64_t)0x77359400); 
        NONFAILING(*(uint64_t*)0x20003fe8 = (uint64_t)0x0); 
        NONFAILING(*(uint64_t*)0x20003ff0 = r[15]); 
        NONFAILING(*(uint64_t*)0x20003ff8 = r[16]+10000000); 
        r[21] = execute_syscall(__NR_timer_settime, r[13], 0x0ul, 0x20003fe0ul, 0x0ul, 0, 0, 0, 0, 0); 
        r[22] = execute_syscall(__NR_timer_gettime, r[13], 0x20003000ul, 0, 0, 0, 0, 0, 0, 0); 
} 
int main() 
{ 
        setup_main_process(); 
        int pid = do_sandbox_none(0, false); 
        int status = 0; 
        while (waitpid(pid, &status, __WALL) != pid) {} 
        return 0; 
}

 

Then 0-Day CI moved on to queue this reproduce program into lkp test environment and start bisection automatically. Finally, it was able to bisect out the culprit commit - 91d57bae08 ("posix-timers: Make use of forward/remaining callbacks") on linux-next tree within a day.

The report was sent to the developer with necessary information such as kernel configuration, crash context, and reproducer program. The author came up with the fix patch [3] promptly with the exact reproducer program. This example demonstrates the ability to detect and fix kernel bugs using the combination of syzkaller and 0-Day CI during early kernel development. We look forward to seeing more output from it.

References

[1] https://github.com/google/syzkaller [2] https://lists.01.org/pipermail/lkp/2017-June/006461.html [3] http://git.kernel.org/tip/c6503be587e9c5c0aac4e2b45de982352f676a5b