Syzkaller: coverage-guided fuzzer for the Linux kernel
Andrey Konovalov <andreyknvl@google.com>
DC4822 Meetup
June 23rd 2018
Whoami
Dynamic tools: userspace
Agenda
Introduction
Static and dynamic analysis
Dynamic analysis: why?
Dynamic analysis
To successfully perform dynamic analysis we need:
Fuzzing
Grammar-based fuzzing
Fuzzer uses explicit input grammar to generate complex realistic inputs:
HTTP-message = Simple-Request | Simple-Response | Full-Request | Full-Response
Simple-Request = "GET" SP Request-URI CRLF
Full-Request = Request-Line *( General-Header | Request-Header | Entity-Header ) CRLF
[ Entity-Body ]
Request-Line = Method SP Request-URI SP HTTP-Version CRLF
Method = "OPTIONS" | "GET" | "HEAD" | "POST" | "PUT" | "PATCH" | "COPY" | "MOVE" |
"DELETE" | "LINK" | "UNLINK" | "TRACE" | "WRAPPED" | extension-method
Request-URI = "*" | absoluteURI | abs_path
absoluteURI = scheme ":" *( uchar | reserved )
HTTP-Version = "HTTP" "/" 1*DIGIT "." 1*DIGIT
http_URL = "http:" "//" host [ ":" port ] [ abs_path ]
...
Coverage-guided fuzzing
start with some initial corpus of inputs (potentially empty)
for (;;) {
choose an input form the corpus and mutate it
execute and collect code coverage
if (input gives new coverage)
add it to corpus
}
Advantages:
Target:
Linux kernel
Linux kernel
Kernel inputs
Kernel
Userspace
syscalls
network
...
USB
Linux kernel fuzzing
Bug detectors:
Sanitizers
Kernel Sanitizers
KASAN report
BUG: KASAN: use-after-free in sctp_id2assoc+0x3a3/0x3b0 net/sctp/socket.c:224
Read of size 8 at addr ffff8800385b6838 by task syz-executor2/5889
Call Trace:
sctp_id2assoc+0x3a3/0x3b0 net/sctp/socket.c:224
sctp_setsockopt_rtoinfo net/sctp/socket.c:2931 [inline]
sctp_setsockopt+0x4b7/0x60f0 net/sctp/socket.c:4018
sock_common_setsockopt+0x95/0xd0 net/core/sock.c:2850
SYSC_setsockopt net/socket.c:1798 [inline]
SyS_setsockopt+0x270/0x3a0 net/socket.c:1777
entry_SYSCALL_64_fastpath+0x1f/0xbe
KASAN report
Allocated by task 5841:
kzalloc include/linux/slab.h:663 [inline]
sctp_association_new+0x114/0x2180 net/sctp/associola.c:309
...
SyS_connect+0x24/0x30 net/socket.c:1569
entry_SYSCALL_64_fastpath+0x1f/0xbe
Freed by task 5882:
kfree+0xe8/0x2b0 mm/slub.c:3882
sctp_association_destroy net/sctp/associola.c:435 [inline]
...
syscall_return_slowpath+0x3ba/0x410 arch/x86/entry/common.c:263
entry_SYSCALL_64_fastpath+0xbc/0xbe
Fuzzer:
syzkaller
Existing system call fuzzers
Trinity (and others) in essence:
while (true) syscall(rand(), rand(), rand());
Knows argument types, so more like:
while (true) syscall(rand(), rand_fd(), rand_addr());
syzkaller
syzkaller
Coverage for the Linux kernel
__fuzz_coverage(); // 1
if (...) {
__fuzz_coverage(); // 2
...
}
__fuzz_coverage(); // 3
if (...) {
...
}
Syscall descriptions
Declarative description of all syscalls:
open(file filename, flags flags[open_flags],
mode flags[open_mode]) fd
read(fd fd, buf buffer[out], count len[buf])
close(fd fd)
open_flags = O_RDONLY, O_WRONLY, O_RDWR, O_APPEND ...
Programs
The description allows to generate and mutate "programs" in the following form:
mmap(&(0x7f0000000000), (0x1000), 0x3, 0x32, -1, 0)
r0 = open(&(0x7f0000000000)="./file0", 0x3, 0x9)
read(r0, &(0x7f0000000000), 42)
close(r0)
Algorithm
External kernel inputs
Kernel
Userspace
syscalls
network
...
USB
TUN/TAP
Gadget API
Test machines
Currently supports:
The list is extensible, to support a new type need to:
Demo
syzkaller:
automation
Ideally...
FUZZER
Resources
PoCs
Reality
Operation of a typical kernel fuzzer:
Works only if you want to find a handful of crashes. Otherwise - full time job.
syzkaller operation
syz-manager
Resources
PoCs
test machines
corpus/programs
console output
*but may incur higher up-front setup cost
Further automation
Demo
Exploitation
Contribution
Questions?
Andrey Konovalov <andreyknvl@google.com>
syzkaller@googlegroups.com
Backup
Other Linux kernel fuzzers
Process structure
Syscall descriptions:
discriminated syscalls
socket$inet_tcp(
domain const[AF_INET],
type const[SOCK_STREAM],
proto const[0]) sock_tcp
socket$packet(
domain const[AF_PACKET],
type flags[packet_socket_type],
proto const[ETH_P_ALL_BE]) sock_packet
Syscall descriptions:
struct layout
sockaddr_ll {
sll_family const[AF_PACKET, int16]
sll_protocol flags[packet_protocols, int16be]
sll_ifindex ifindex
sll_hatype const[ARPHRD_ETHER, int16]
sll_pkttype int8
sll_halen const[6, int8]
sll_addr mac_addr
pad array[const[0, int8], 2]
}
bind$packet(fd sock_packet, addr ptr[in, sockaddr_ll], addrlen len[addr])
Syscall descriptions:
resources
resource sock[fd]
socket(domain flags[socket_domain], type flags[socket_type],
proto int8) sock
bind(fd sock, addr ptr[in, sockaddr_storage], addrlen len[addr])
resource sock_packet[sock]
socket$packet(domain const[AF_PACKET], type flags[packet_socket_type], proto const[ETH_P_ALL_BE]) sock_packet
bind$packet(fd sock_packet, addr ptr[in, sockaddr_ll], addrlen len[addr])
External Stimulus
Systems calls and external stimulus in the same program:
listen(r0)
emit_ethernet(syn)
emit_ethernet(ack)
r1 = accept(r0)
emit_ethernet(data)
read(r1)
emit_ethernet(rst)
Work in progress; also applicable to USB, ...
Finding 0days in the Linux kernel