(论文复现)GREBE: Unveiling Exploitation Potential for Linux Kernel Bugs

源码：Markakd/GREBE (github.com)

1. Analysis

1.1 关键内核结构确定

1.1.1 report来源：

​ syzbot是一个基于syzkaller的自动化fuzzing系统。它能持续不停的运行syzkaller，对linux内核各个分支进行模糊测试，自动报告crash，监控bug的当前状态（是否已被修复等），监测对于bug的patch是否有效，完成发现-报告-复现-修复的整个流程。

​ 对每个错误，syzbot会发布其对应的报告以及可能存在的POC程序：

​ 如上图所示，syzbot发布了某个错误发生时其对应的寄存器内容，call trace以及3次crashes（底部）的对应信息，可以看到，该错误提供了一个syz脚本编写的reproducer，也就是Poc程序。

​ syzkaller repro是用特殊的syzkaller符号编写的程序，它们可以在目标系统上执行。并且，syzkaller repro可以转化为对应的C语言poc，如果syzbot没有提供C语言的repro，它就无法使用C语言程序来触发该错误（这可能只是因为该错误是由一个竞态条件触发的）。

​ GREBE就是从这些报告中提取call trace进行后续分析。

1.1.2 编译Analyzer

​ 安装llvm–10（LLVM Debian/Ubuntu packages）：

#To install a specific version of LLVM:
wget https://apt.llvm.org/llvm.sh
chmod +x llvm.sh
sudo ./llvm.sh <version number>

​ clang-10被安装在/usr中，故将analyer的make文件修改来指定clang，如下（这里直接指定C与C++编译器）：

CUR_DIR = $(shell pwd)
SRC_DIR := ${CURDIR}/src
BUILD_DIR := ${CURDIR}/build

include Makefile.inc

NPROC := ${shell nproc}

build_ka_func = \
	(mkdir -p ${2} \
		&& cd ${2} \
        &&    cmake ${1} \
				-DCMAKE_CXX_COMPILER=/home/wx/Shaw/llvm/patched_llvm/bin/clang++\
				-DCMAKE_C_COMPILER=/home/wx/Shaw/llvm/patched_llvm/bin/clang\
                -DCMAKE_BUILD_TYPE=Release \
                -DCMAKE_CXX_FLAGS_RELEASE="-std=c++14 -fno-rtti -fpic -g" \
		&& make -j${NPROC})

all: analyzer

analyzer:
	$(call build_ka_func, ${SRC_DIR}, ${BUILD_DIR})

​ 接着修改analyzer/src中的CMakeLists.txt文件来指定LLVM：

cmake_minimum_required(VERSION 2.8.8)
project(KANALYZER)
#指定LLVM版本
set(LLVM_DIR "/home/wx/Shaw/llvm/patched_llvm/lib/cmake/llvm")

find_package(LLVM REQUIRED CONFIG)

message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")
message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}")

# Set your project compile flags.
# E.g. if using the C++ header files
# you will need to enable C++14 support
# for your compiler.
# Check for C++14 support and set the compilation flag
include(CheckCXXCompilerFlag)
#CHECK_CXX_COMPILER_FLAG("-std=c++14" COMPILER_SUPPORTS_CXX14)
# if(COMPILER_SUPPORTS_CXX14)
# 	set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++14 -fno-rtti -fPIC -Wall")
# else()
# 	message(STATUS "The compiler ${CMAKE_CXX_COMPILER} has no C++14 support. Please use a different C++ compiler.")
# endif()

include_directories(${LLVM_INCLUDE_DIRS})
add_definitions(${LLVM_DEFINITIONS})

add_subdirectory (lib)

​ 编译好的analyer位于GREBE/analyzer/build/lib中。

1.1.3 编译内核bitcode文件

1.1.3.1 安装带补丁的LLVM

​ 内核bitcode文件指的是待测试的Linux内核，需要将其编译为bc文件后进行分析。

​ 这里需要使用llvm-10并且给LLVM编译器打上补丁，以便在调用任何编译器优化通道之前转储比特码。通过这种方式，可以防止编译器优化影响分析的准确性。故这里单独准备一个llvm并安装到特定文件夹中，以避免对全局llvm的影响：

git clone https://github.com/llvm/llvm-project
cd llvm-project
git checkout 5521236a18074584542b81fd680158d89a845fca

​ 打补丁：

patch -p0 < WriteBitcode.patch

​ build clang:

mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=/home/wx/Shaw/llvm/patched_llvm -DLLVM_ENABLE_PROJECTS=clang -DCMAKE_BUILD_TYPE=Release  -G "Unix Makefiles" ../llvm
sudo make -j$(nproc) && make install

​ 这里通过指定DCMAKE_INSTALL_PREFIX的方式指定其安装位置。注意，LLVM编译后体积非常大，如果在虚拟机中编译需要给足够内存和硬盘空间（80G+）。

1.1.3.2 编译内核

​ 编译安装完带有特定补丁的LLVM，接下来就需要使用其来编译Linux内核源码。

​ 以KASAN: slab-use-after-free Read in hfsplus_read_wrapper为例，其附带的.config文件中详细的说明了漏洞的内核版本、config编译选项等信息。

​ 在kernel/git/torvalds/linux.git - Linux kernel source tree处下载对应版本的内核源码，解压后先安装编译所需的包：

sudo apt-get install git fakeroot build-essential ncurses-dev xz-utils libssl-dev bc flex libelf-dev bison

​ 使用如下命令编译,CC和CXX指定为带补丁的clang，由于LLVM-10存在一定bug，这里令LLVM_IAS为0关闭integrated assembler：

make CC=/home/wx/Shaw/llvm/patched_llvm/bin/clang CXX=/home/wx/Shaw/llvm/patched_llvm/bin/clang++ LLVM_IAS=0 all -j$(nproc) 

​ analyzer编译完成后，使用如下命令运行：

python run_analyze.py ./case

​ 可以在对应case目录下看到对应的解析结果sys.txt：

​ 注意：

1. 编译analyzer与源码的LLVM一定要相同版本；

2. 作者给出的LLVM-10是可以成功运行的，但是存在的问题如下：

   a. 目前使用LLVM编译新版本的内核最低要求其版本为11，其无法编译内核；

   b. 如果使用LLVM-11，其编译analyzer存在错误（见文末错误日志）；

   故目前作者仓库中给出的代码仅适合版本不高的内核。

3. 部分工作已通过脚本自动化，整个内核的下载+解压+编译已自动化为/analyzer/scripts/get_kernel.py，复现analyzer需要：

   a. 在/analyzer/Testcase/下创建对应case文件夹，命名格式为case+数字；

   b. 将对应report中的.config文件与report文件以名称.config和report复制到case文件夹中；

   c. 修改/analyzer/scripts/下的三个py文件中的CASE_DIR，PATCHED_LLVM和AnalyzerPath变量，使其分别对应Testcase，打过补丁的LLVM和编译好的analyzer；

   d. 按次序运行get_cg.py、get_kernel.py和run_analyze.py，其参数为case序号，例如：

   #分析/analyzer/Testcases/case7
   python get_cg.py 7
   python get_kernel.py 7
   python run_analyze.py 7

1.1.3 静态分析代码解析

​ 见(代码分析)GREBE-Analyzer污点分析代码解析 | Shaw (shawdox.github.io)

2. Fuzzing

2.1 编译GCC

​ 使用作者提供的gcc-9.3.0来编译内核，首先进入其文件夹中编译GCC：

./contrib/download_prerequisites
mkdir gcc-bin
export INSTALLDIR=`pwd`/gcc-bin
mkdir gcc-build
cd gcc-build
../configure --prefix=$INSTALLDIR --enable-languages=c,c++
make -j`nproc` && make install

​

2.2 使用GCC编译内核

​ 在内核代码中运行：

export OBJ_FILE="/home/wx/Shaw/GREBE/analyzer/TestCases/case7/sts.txt"
make CC="/home/wx/Shaw/GREBE/gcc-9.3.0/gcc-bin/bin/gcc" -j`nproc`

​ 注意，内核的.config文件标志了其编译所需的最低版本，故不论是用clang编译还是gcc都需要符合对应版本。

2.3 编译Fuzzer

​ GREBE的Fuzzer是syzkaller的改版，其使用方法与syzkaller基本相同。根据syzkaller官方给出的方法编译，这里集成为/fuzzer/compile_fuzzer.py：

#Author: xiao wu
#Time: 2023.6.16
#Functionality:
#   Complie the modified syzkaller

import sys
import os
assert ('linux' in sys.platform)

GO_DIR = "/home/wx/Shaw/go"
FUZZ_DIR = "/home/wx/Shaw/GREBE/fuzzer"

os.environ["PATH"] += GO_DIR+"/bin"
os.chdir(FUZZ_DIR)
os.system("make")

​ 这里需要在脚本中指定Go语言环境以及fuzzer的位置，Go的版本需要大于等于1.11。编译好的fuzzer位于/fuzzer/bin中。

2.4 测试QEMU

​ syz-manager需要通过ssh来与ssh-fuzzer通信，后者运行在QEMU中，故在运行syzkaller之前，需要手动测试QEMU连通性：

qemu-system-x86_64 \
  -m 2G \
  -smp 2 \
  -kernel $KERNEL/arch/x86/boot/bzImage \
  -append "console=ttyS0 root=/dev/sda earlyprintk=serial net.ifnames=0" \
  -drive file=$IMAGE/bullseye.img,format=raw \
  -net user,host=10.0.2.10,hostfwd=tcp:127.0.0.1:10021-:22 \
  -net nic,model=e1000 \
  -enable-kvm \
  -nographic \
  -pidfile vm.pid \
  2>&1 | tee vm.log

​ 注意，QEMU需要当前系统支持KVM虚拟化，如果是虚拟机可以直接查找对应处理器设置，如果是物理机需要在BIOS中开启。

​ 成功开启QEMU后另开一个bash，用ssh测试其连通性：

ssh -i $IMAGE/bullseye.id_rsa -p 10021 -o "StrictHostKeyChecking no" root@localhost

​ 如果成果连通则说明QEMU通信部分没有问题，具体配置过程以及相关可能的问题可见：(技术积累)Syzkaller环境配置 | Shaw (shawdox.github.io)

​

2.5 运行fuzzer

​ 直接使用/fuzzer/scripts/run_fuzzer.py脚本即可运行fuzzer，其会自动定位case文件夹并创建对应的config文件，运行syz-manager:

python run_fuzzer.py [case_number]
#python run_fuzzer.py 8

​ 下面是run_fuzzer.py的运行逻辑：

1. 首先在对应的case文件夹下创建其config文件：

   

   1. 然后将config文件复制到workdir（如上图）中：

​ 如上图fuzzer源码所示，注意到poc是默认位于workdir中的，故在使用命令时仅传入poc文件名称即可（此次复现中，poc.txt默认位于对应的case文件夹中，这里run_fuzzer.py脚本会在运行syz-manager前将对应的poc.txt复制过来）。

3. 运行syz-manager:

syz-manager -config /home/wx/Shaw/GREBE/analyzer/TestCases/case8/syzconfig.cfg --auxiliary poc.txt

​ 再次注意，由于fuzzer源码限制，使用--auxiliary标志传入poc.txt只能传入该名称，并且poc.txt文件应该位于workdir文件夹下。

​ 运行即可得到对应结果：

2.6 原理解析

​ 对gcc和kernel都做了修改，使其在编译内核时可以将特定的basic block的16bit地址替换为一个magic_number，这样在代码覆盖率反馈中就可以识别哪些basic block属于关键内核对象。

2.6.1 Syzkaller原理

​ 如上图所示，具体描述见：syzkaller/docs/internals.md at master · google/syzkaller · GitHub

2.6.2 Syscall descriptions

​ Syzkaller使用声明性的系统调用描述来控制程序（系统调用的序列），举例：

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_mode = S_IRUSR, S_IWUSR, S_IXUSR, S_IRGRP, S_IWGRP, S_IXGRP, S_IROTH, S_IWOTH, S_IXOTH

​ 翻译后的系统调用描述被用来生成、变异、执行、最小化、序列化和反序列化程序，程序指的是有着一系列具体参数的系统调用，例如：

r0 = open(&(0x7f0000000000)="./file0", 0x3, 0x9)
read(r0, &(0x7f0000000000), 42)
close(r0)

​ 在实际操作中，syzkaller使用类似AST的内存表示法，由prog/prog.go中定义的Call和Arg值组成。这种表示法被用来分析、生成、变异、最小化、验证等程序。内存中的表示法可以转换为文本形式，以存储在磁盘语料库中，并展示给人类，等等。还有另一种程序的二进制表示法（称为exec），它更简单，不包含丰富的类型信息（不可逆），用于实际执行（解释）程序。

2.6.3 Coverage

2.6.3.1 Syzkaller Coverage

​ 覆盖率通过追踪coverage points的方式获取，coverage points一般通过编译器插入对象代码中。coverage points一般指一个基本块或者CFG边（取决于编译器，例如clang默认是cfg边而gcc是基本块），编译器在翻译转换和优化代码的过程中插入coverage points。

​ 因此，覆盖率与源代码的关系可能很差。例如，你可能会在一个非覆盖行之后看到一个覆盖行，或者你可能在你期望看到的地方没有看到覆盖点，反之亦然（如果编译器拆分基本块，或将控制流结构变成没有控制流的条件动作，就可能发生这种情况。）。

https://github.com/google/syzkaller/blob/master/docs/coverage.md#syz-cover这里可以参照官网的syz-cover来从原始覆盖数据中生成报告。

​ Syzkaller使用kcov来从Linux内核中获取代码覆盖率，kcov会输出每个被运行的基本块的地址，然后syzkaller会用objdump、nm、addr2line、readelf等binutils工具来将该地址映射到源码对应的行数。

2.6.3.2 GREBE Coverage

• GREBE-GCC

​ add grebe code changes · whoismissing/grebe-gcc@172f8e6 (github.com)这里可以看到GREBE对GCC9.3.0版本做了怎样的修改，其修改了两个文件：sancov.c和sanitizer.def。

​ 首先，GREBE在sancov.c中定义了存储关键对象的结构struct_maps:

​ 定义了init_structs()函数，用于将从analyzer生成的内核关键对象读取到st_map->st数组中：

​ 定义了process_tree()函数，用于匹配关键内核对象：

​ 定义了find_st()函数，用于从tree中找出符合关键内核对象的子树：

​ 然后在sancov_pass()函数中插入以下代码：

​ 这段代码的大致作用是选择对basic block做插桩的函数，BUILT_IN_SANITIZER_COV_TRACE_PC是kcov原本的插桩函数，BUILT_IN_SANITIZER_OBJ_COV_TRACE_PC是GREBE实现的插桩函数，二者都在对应内核的kernel/kcov.c文件中实现，二者的区别如下：

​ 其中，_RET_IP_代表当前函数的返回地址，可以发现，GREBE实现的BUILT_IN_SANITIZER_OBJ_COV_TRACE_PC相较于BUILT_IN_SANITIZER_COV_TRACE_PC就是将返回地址截取了前32位。

​ 回到sancov_pass()，其遍历每个基本块，对于非空基本块判断其是否是关键内核对象，如果是则将fndecl设置为BUILT_IN_SANITIZER_OBJ_COV_TRACE_PC，否则设置为BUILT_IN_SANITIZER_COV_TRACE_PC。然后代码根据fndecl设置一个gcall，将其插入到代码块之前。

​ 最后，在sanitizer.def文件中，将自己实现的__sanitizer_obj_cov_trace_pc()定义为sanitizer函数:

• GREBE-Syzkaller

3. 错误日志

• 问题1：编译llvm时报错：

  Killed (program cc1plus)
  Please submit a full bug report,
  with preprocessed source if appropriate.
  See file:///usr/share/doc/gcc-5/README.Bugs for instructions.
  lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/build.make:494: recipe for target ‘lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/EnumTables.cpp.o’ failed
  make[2]: [lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/EnumTables.cpp.o] Error 4
  CMakeFiles/Makefile2:6769: recipe for target ‘lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/all’ failed
  make[1]: [lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/all] Error 2

解决方法：

编译时虚拟机的内存与硬盘空间太小，在服务器上跑即可成功编译。

• 问题2：在编译analyzer时报错：

  error: no member named ‘hasNPredecessorsOrMore’ in ‘llvm::BasicBlock’

• 解决方法：

  查看错误报告发现是LLVM的BasicBlock没找到对应的子数据结构hasNPredecessorsOrMore，首先在LLVM官网查找对应数据结构定义：

  

  ​ 可以看到在BasicBlock.cpp的319行有该数据结构的定义，查找本机上下载的llvm源码：

  

  ​ 查找对应源码是可以发现对应数据结构定义的：

  

  ​ 阅读报错信息，发现编译时自动搜索到了以前安装的llvm-6.0旧版本，手动更改路径，上述问题解决，但是发现仍旧报错。

  ​ 在llvm的github项目中找到了一样错误：Build failure when targeting LLVM 11.0 · Issue #87 · google/autofdo (github.com)。可以基本确定这是LLVM-11的问题，换回LLVM-10版本即可解决。

• 问题3：在编译analyzer时报错：

  ld: cannot find -lz

  解决方法：

sudo apt-get install zlib1g zlib1g-dev

• 问题4：在使用analyer时报错：

  /home/wx/Shaw/GREBE/analyzer/build/lib/analyzer: error loading file ‘./case/linux-bitcode/lib/dump_stack.c.bc’

  解决方法：

  问题定位到KAMain.cc文件使用ParseIR()函数解析bc文件：

  std::unique_ptr<Module> M = parseIRFile(InputFilenames[i], Err, *LLVMCtx);
  if (M == NULL) {
       errs() << argv[0] << ": error loading file '" << InputFilenames[i] << "'\n";
       continue;
  }

• 问题5：编译内核（部分版本）时报错：

  error New address family defined, please update secclass_map.

  解决方法：

  编译错误 error New address family defined, please update secclass_map.解决-CSDN博客

• 问题6：编译内核（部分版本）时报错：

  passing argument 1 to restrict-qualified parameter aliases with argument 5 [-Werror=restrict]

  cc1: all warnings being treated as errors

  解决方法：

  对tools/lib/str_error_r.c打如下补丁：

  Re: New -Werror=restrict error with incremental gcc - Laura Abbott (kernel.org)

  

• 问题7：无法使用py脚本（在其中使用export）改变环境变量

  解决方法：

  How to use export with Python on Linux - Stack Overflow

Reference

• GREBE:
  • GREBE/analyzer at master · Markakd/GREBE (github.com)
  • Markakd/LLVM-O0-BitcodeWriter: patch for LLVM to generate O0 bitcode (github.com)
• LLVM:
  • LLVM Debian/Ubuntu packages
• Kernel:
  • How To Build Linux Kernel {Step-By-Step} | phoenixNAP KB
  • Setup: Ubuntu host, QEMU vm, x86-64 kernel (googlesource.com)
  • KCOV: code coverage for fuzzing — The Linux Kernel documentation
  • 内核测试指南 — The Linux Kernel documentation
• Syzkaller：
  • syzkaller/docs/internals.md at master · google/syzkaller · GitHub
  • syzkaller/docs/linux/setup_ubuntu-host_qemu-vm_x86-64-kernel.md at master · google/syzkaller · GitHub
  • (技术积累)Syzkaller环境配置 | Shaw (shawdox.github.io)
  • Understanding kcov – play with -fsanitize-coverage=trace-pc from the user space | davejingtian.org
  • kcov-用于内核模糊测试的代码覆盖-CSDN博客