This repository implements a mechanism to perform bpf program verification
in user space. It further utilizes llvm sanitizer and fuzzer framework to
extend error detection coverage.
Motivation
The motivation of this project is to test verifier in userspace so that
we can take advantage of llvm's sanitizer and fuzzer framework. One bug
has been discovered because of this effort:
http://permalink.gmane.org/gmane.linux.network/376864
Directory Overview
- bld
- config
- src
- helper
- test
- linux-samples-bpf
- fuzzer
The bld directory is used to build and run test programs.
The config directory holds the recommended linux config file
The src/helper contains helper files for kernel and
user hooks. The src/test/linux-samples-bpf contains
related test verifier files from linux/samples/bpf/ and
src/test/fuzzer contains a hook with llvm fuzzer framework.
Prerequisite
A linux source tree is needed. The source tree is used to pre-process kernel files.
Note that kernel headers will need to be generated at default <kernel_root>/usr/include
directory. The default config does not have all necessary BPF options enabled,
and will make verifier tests fail.
you can try to use the one at the config directory instead of default
linux:arch/x86/configs/x86_64_defconfig.
git clone git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git
# change defconfig and apply necessary patch as decribed below
cd net-next
make defconfig
make headers_install
For above linux tree, apply the following patch so that llvm can cope with linux
inline assembly:
yhs@ubuntu:~/work/fuzzer/net-next$ git diff
diff --git a/Makefile b/Makefile
index c361593..cacbe0f 100644
--- a/Makefile
+++ b/Makefile
@@ -686,6 +686,8 @@ KBUILD_CFLAGS += $(call cc-disable-warning, tautological-compare)
# See modpost pattern 2
KBUILD_CFLAGS += $(call cc-option, -mno-global-merge,)
KBUILD_CFLAGS += $(call cc-option, -fcatch-undefined-behavior)
+# no integrated assembler so not checking inlining assembly format
+KBUILD_CFLAGS += $(call cc-option, -no-integrated-as)
else
# This warning generated too much noise in a regular build.
yhs@ubuntu:~/work/fuzzer/net-next$
A llvm/clang compiler with compiler-rt is needed. The compiler-rt is necessary
for llvm sanitizer support.
sudo apt-get -y install bison build-essential cmake flex git libedit-dev python zlib1g-dev
git clone http://llvm.org/git/llvm.git
cd llvm/tools; git clone http://llvm.org/git/clang.git
cd ../projects; git clone http://llvm.org/git/compiler-rt.git
cd ..; mkdir -p build/install; cd build
cmake -G "Unix Makefiles" -DLLVM_TARGETS_TO_BUILD="BPF;X86" -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=$PWD/install ..
make -j4
make install
export PATH=$PWD/install/bin:$PATH
Build and Run
export KERNEL_TREE_ROOT=<kernel_tree_root>
cd bld
make setup
make all
The "setup" target creates common symbolic links and download
and build llvm fuzzer. It only needs to run once.
The "all" target builds two binaries, test_verifier and test_fuzzer.
test_verifier is essentially linux/samples/bpf/test_verifier.c with
slight modification to adapt to the new test framework, with
sanitizer support. test_fuzzer uses llvm fuzzer framework
for testing.
test_verifier can also generate initial test cases for test_fuzzer.
These test cases will make fuzzer more effective in generating relevent
new test cases.
# generate initial test cases for fuzzer, put them into ./corpus directory
./test_verifier -g ./corpus
./test_fuzzer -max_len=1024 ./corpus
To report memory leaks, the test_fuzzer needs to terminate normally.
This can be done by limiting the number of runs, e.g.,
./test_fuzzer -max_len=1024 -runs=1000000 ./corpus
The following command can be used to find the number of coverages:
# the actual number of coverages should be the number of lines minus one
# to account for function declaration.
objdump -D test_fuzzer | grep '<__sanitizer_cov>' | wc
With this information, you can compare to test_fuzzer output to
see what is the coverage. For example, if the total number of
edge coverages is 1106, and you have the following from test_fuzzer
output:
......
#3466257868 NEW cov: 884 bits: 3749 units: 936 exec/s: 38408 L: 47
#3486994800 NEW cov: 884 bits: 3750 units: 937 exec/s: 38396 L: 64
#3491234878 NEW cov: 886 bits: 3752 units: 938 exec/s: 38394 L: 58
#3495108828 NEW cov: 886 bits: 3754 units: 939 exec/s: 38391 L: 58
You will know 886 out of 1106 edges are covered so far.
