Bachelor- and Master Seminar

Speaker: Pavithra Krishna
Type of talk: Master Final talk
Advisor: Dr.Rahul Gopinath
Supervisor: Prof.Dr.Andreas Zeller
Title: Fuzzing the Extended Berkeley PacketFilter verifier using Grammars
Research Area:RA2

Background/Key terms:
i)eBPF: It is a sandbox/virtual machine within the Linux kernel to execute programs and obtain needed information. An interesting topic for security is that this feature allows a program defined in the user-space to be executed in the kernel. Furthermore, the usability and performance of this feature has gained a lot of attention in the recent years. As on date, there are around 100+ tools based on this feature developed only within a short span of few years.
ii)eBPF verifier: This is the security mechanism which guarentees that no ebpf program provided from the user-space can cause unintented behaviour within the kernel. It is quite complex in nature as it does static checking and register state simulation. The code which is over several thousand lines include several techniques like Directed acyclic graphs, Depth first search, register state monitoring etc., The eBPF programs approved by the verifier are only allowed to execute within the kernel.
iii)Fuzzing: It is a dynamic testing technique for software that examines the code response during run time to discover unexpected behavior. The techniques used to produce the test inputs have changed over the years and have become more sophisticated.
iv)Grammars: They are widely used to represent different input properties,specifically, the syntactic rules to define its structure.
v)Grammar-based Fuzzer: It is a generation based and a smart Fuzzer. This technique is beneficial to generate inputs with high efficiency. These inputs can surpass the parser, which does syntactic analysis on the inputs and, thus, deeper into the program.

Introduction:
  The eBPF technology is ubiquitous within the Linux kernel world due to the enormous benefits such as performance and adaptability. The feature has critical priviledges such as leak kernel memory addresses, read-write access to arbitrary locations, filter system calls, monitor network packets, trace kernel processes and many more. It also has extended into security applications such as firewall(ip-tables), secure computing(seccomp), run-time security enforcement (tetragon/cilium).
Considering the time of development, it is evident that it was very rapid and enormous within a short period of time. The talks based on eBPF presented at recent conferences such as DEF CON29, Black hat 2021 reveals that security bugs are inevitable. This indicates that the claimed guarentees by the eBPF verifier can be falsified under certain scenarios. Furthermore, there exists a non-negligible gap between its development and testing.
  The analysis indicate that every new kernel release is accompanied by functional tests which check for Pass/Fail criteria. It is also observed that certain tech giants such as Google, Netflix make use of AFL and Syzkaller to test eBPF. Eventhough such fuzzers help to improve security using mutation techniques or coverage guidance, they are also limited. The major reasons are either the instruction set used is not complete nor all possible combinations are considered.

Research contribution:
   Given the complexity and the security criticality of the eBPF verifier, the aim of my thesis is to answer the following research questions:
RQ1. Can the eBPF verifier be tested using the entire instruction set?
RQ2. What percentage of the inputs generated using Grammars surpass the eBPF verifier and cause undefined behavior?

 In order to realize it, the methodology chosen revolves around few objectives.First, to test the verifier against syntactically valid and varied eBPF programs. As second,to verify the behaviour of the loaded programs during run time. Then, to check the verifier's response against programs with code fragments of bugs identified in the past and last but not the least, to have a simple and easy to use interface with support for batch processing of eBPF programs.
 The core technique combines several ideas from the Fuzzing book(created and maintained by CISPA experts), linux tools used for kernel debugging, Python libraries, C code, Bash scripting and GCC compiler. The infrastructure relies on a customly built Linux kernel that supports BPF compilation and execution, kernel for crash analysis and serial connection between cloned virtual machines. Furthermore the initially defined Grammar has been optimized with Kernel code coverage metrics, reusing code fragments from past buggy programs. The key metrics used are time for generation and execution, memory consumption, quality, usability and support debugging.
 The results obtained are rated as direct or indirect based on how they are related to eBPF. As part of direct findings, leakage of kernel memory information, unreachable instructions being accepted, segmentation failures, program crashes, kernel traps were found. There are also indirect findings such as Windows blue screen of death(BSOD), system hangs, kernel oops.

Key take away:
 Fuzzing is a versatile technique which has been researched for several years. On combining different techniques, it can unwrap deeper bugs and improve security. The eBPF technology is one of the several linux kernel features that are potential attack vectors. As indicated by the results of this work, using Grammars are very effective and efficient in dynamic security testing. Having provided with more memory and other observatory tools, this technique can scale to handle larger programs and other advanced features such as function calling between eBPF programs.The proposed framework can be used as stand-alone or in combination with existing testing methods.