参考了kiprey学长的阅读笔记，https://kiprey.github.io/2022/03/other_paper_notes/

这篇文章感觉还是比较难，重点在静态分析，现在也没有太弄懂，回头再细扣扣。（为什么图片显示不出来，不太理解，就这样吧

提出一个静态二进制分析工具来自动推测系统调用类型。NtFuzz：类型敏感的windows内核模糊测试器

introduction

系统调用嵌套且相互依赖，在没有类型感知的情况下，很难生成有意义的测试用例。

难点：闭源，syscalls未知，没有文档，经常更改等。

NtFuzz分两步：分析kernel132.dll，ntdll.dll等调用系统调用的文件并推断类型。然后使用推得的类型进行类型敏感的变异。

第一步

有文档的API通过其函数来调用系统调用。因此我们可以通过静态分析来得到无文档的系统调用的信息。

但api函数互相关联，进行静态分析时需要同时考虑内存，寄存器和在多个二进制文件中的函数。

通过模块分析来解决，对函数进行参数化，被调用的时候进行参数化

第二步

使用用户态程序拦截系统调用，并对其调用的参数进行变异。

contribution：

首次将静态分析和模糊测试在windows kernel fuzz中结合
提出静态工具来推断系统调用类型
提出使用最少人工的类型感知模糊测试器
发现win10的11个bug和4个cve

background

windows架构：

用户程序通过调用高阶API来调用系统调用。NtFuzz通过分析这些api来推断无文档的函数和syscall

实际实现windows api函数的系统dll在本文中被称作系统二进制文件

只关注人工识别出来的系统核心库

Motivation

（这个伪代码哪来的？）

以该漏洞为例，vuln的函数为一个字符串指针，在第六行，对指针长度做了判断，长度奇怪（len & 1）的时候会调用logerror，但这不会导致syscall中断，因此可以这样来绕过指针合法判断。

对于fuzzer，需要知道该函数的参数是一个只想UNICODE_STRING结构体的指针，才能有限的生成测试样例。

下面的函数有文档，而上面的没有，上面的函数参数是通过下面的推得的。

API function级别的fuzz测试难以触发严重漏洞，21行会把len设置为偶数。

OVERVIEW

NtFuzz结构：

主要包括两部分，静态分析器和内核模糊测试器

static analyzer

主要包含三个部分：前端将系统二进制文件转换为中间表示并构建CFGs，此外将提取API function重的类型信息，并转化为适合分析的形式。

模块化分析引擎：遍历控制流图并观察系统二进制文件怎么构造调用参数

类型推断：基于二进制行为决定每个syscall的参数类型

kernel fuzzer

通过重复以下三步运行：

准备好syscall hook然后运行给定的seeds

变异器更改每个syscall的参数值

最后detector监察是否crash，crash的话dump内存

模块分析器算法

总体分两步：将目标程序分割为几个模块（函数？），汇总各个部分的分析结果。对于每个函数，分析器推断其语意并且总结器行为，以便当期被调用时直接调用而不是重新分析。整个程序的运行会被自底向上的构建。

类型推断伪代码⬆️

将CFGs，CG和API规范作为输入，把推断得到的类型作为输出。算法首先将调用图进行拓扑排序，然后从叶节点开始遍历，并用抽象框架概括每一个CG上的函数。

一个函数的总结包括：函数调用了哪些系统调用，运行f的时候内存状态如何变化

从叶节点开始遍历以方便复用

第八行的decidetype通过循环使用每个函数的总结信息决定最终的syscall参数类型

优点：inter-procedural，语法敏感。对同一函数的复用可以降低分析的消耗

不能可靠（soundly）的处理间接和递归调用。

运行样例

例子中f位documented function，我们将malloc和syscall作为内存分配和系统调用的原语函数。g和h函数在实际中都是二进制文件，这里以伪代码展示是为了方便演示。算法的结果是得到第九行的syscall的参数类型。

walk-through

NtFuzz从4b中的拓扑图的叶节点开始。假设便利序列是h->g->f。

先分析h就会得到一个*a = b的summary。然后分析g得到一个包括syscall的summary，这里可以直接得到syscall 的第一个函数类型。注意summary是参数化的，即summary可以背具体化为不同的实例。

然后通过复用g和h的summary来处理f。首先通过APIsec获取f的参数类型，我们实例化h来知晓p指针，也就是堆上的结构体是如何变化的，即offset 0处有一个handle，offset 4 处有一个整数。当p作为参数传入函数g时，我们实例化g函数，发现syscall的第二个函数是指向一个结构体的指针。

challenges：我们对数据流的追踪必须能跨越函数便捷，比如需要理解f到g的数据流

分析器要能够跟踪程序中的内存状态，比如知道结构体的结构。

static analyzer design

front-end

使用B2R2来对二进制进行解析和提取。（足够快

（例子中删去了简单的一元运算和分支语句为了方便演示）

B2R2将二进制文件提取为中间表示，其仅用简单的一些基本操作即可表达二进制文件语义。

提取为中间表示的程序伴随调用递归运行，从而给每个函数构建一个CFG，来构建一个二进制文件间的CG。

为了所见CG的大小，我们删除掉不必要的节点（函数）

从包含syscall的节点开始反向遍历，直到遇到一个documented API fucntion为止。将对每一个函数遍历后途径的节点计作S1

然后统计所有S1中节点可达的节点作为S2。

将S1并S2得到的集合作为删减后的CG中的所有节点

解析SDK中的函数声明来获取所有的类型信息。同时还会解析源码的注释（SAL）来获取一下数组大小之类的内容

Modular Analyzer

对每个函数采用流敏感的分析，对CFG中的每个节点计算出一个抽象程序状态。

抽象状态包括：作为系统调用的参数传入的值，程序入口点和出口点间状态的变化。

抽象域

抽象整数：一个可以存储在寄存器或内存单元中的数。用线性表达式来表示。

其中T表示任何整数的集合，倒T表示没有任何实际意义的数。

只有在具体的要求下才能得出一个具体的值，否则就是T

抽象地址：一个值的潜在为止。有四种。

SymLoc.Global(a)表示全局变量a的地址

Stack(f,o)表示一个局部变量在栈帧f的偏移o处。

heap(a,o)表示内存单元在从a开始分配的内存的偏移o处

SymLoc(s,o)表示指针s偏移o的位置。

类型约束：包括一个具体的类型t和一个符号类型SymTyp(a)，a是一个符号。

抽象语义

exp

定义V：对于给定的Abstract State内的exp，计算得到值Abstract Value。

S[0]可以返回寄存器状态的map

S[1]可以返回内存地址的map

第一个式子过了

第二个式子：表示对抽象状态S传入表达式e，返回表达式e的值在内存中对应位置的值，相当于解指针。先求解得到表达式e表达的在内存中的集合。

第三个式子：对于值是0的时候，无法判断其是空指针还是0，因此忽略其类型约束

i在datasection中时认为其是一个指针，因此不关心其具体值，

其他情况认为其为普通的整形

第四个式子：二元操作：定义加和乘的操作。

如果结果是非线性的，直接返回一个T

为了防止指针出现指向任意区域的情况，只考虑常量偏移而不考虑类似数组的偏移。

stmt

put：把寄存器存入内存

store：把一片内存存入另一片内存

update；wake update

call：为了体现call可能出现的副作用（副作用的定义）

如果被调用函数documented，还会更新起参数的类型约束。

trade-off

syscall经常接收嵌套指针作为参数，涉及了大量的内存更新。因此，经常会出现函数调用时副作用的激增，导致静态分析去扩展受限。

因此，采用Nse参数，设置一个更新次数的上限。

type infer

structer infer

如果参数不是指针，那可以在上面的推断中直接确定其类型

通过搜索类似heap(line 3, *)的结构，可以获得c中的结构体

栈中的结构体更难推断

a中两个结构体的声明在二进制中无法和两个局部变量的的声明区分开

也就是说a和b两个程序编译得到的二进制文件是相同的，在栈上我们没办法确定一个指针指向的是不是一个结构体。

如果我们认为所有指向栈上的指针都是结构体，那就需要确定结构体的边界，如果直接认为边界是栈底，就会得到太多的伪字段。

通过观察内存访问模式来启发是的解决这个问题：1. 如果一个相邻的内存被定义而从不使用，则认为其是一个被传入syscall的结构体。2. 如果一个内存区域未被定义就直接被使用，也认为其是被sysccall初始化的结构体区域。

如8a所示，查看s最相邻的内存区域，s.y从未被使用，认为其是结构体内的内容，而k在后文中被使用，被认为是非结构体的区域。

array infer

1 documented的API函数中说明类型的函数可能作为syscall的参数传递，此外，数组大小单独声明为变量可能作为参数传递。

documented function f

通过内存分配方式来推断类型。

在第八行可以发先p指向的内存对象大小总与x相同，因此可以推断第一个参数是数组指针而第二个参数是数组大小

resolving conflicts

由于一个syscall通常在很多函数中都会被调用，为了解决得到的类型冲突，我们统计得到的所有类型中的多数。这一过程可能需要递归进行，比如先确定是一个指针，再确定指针所指向内容的类型。

kernel fuzz design

launcher

fuzzer通过拦截seed中的系统调用并变异其参数来运行 - hooking based

hooking based fuzzer需要提供合法的用户输入来执行，由于winsows的应用大多为图形化界面交互，徐哦咦塑腰通过运行脚本来模拟图形化交互。

Mutator

1 type aware 2 not get stuck by error handler

type-aware

整型：使用和afl相同的策略，即四种变异方式：位翻转，算术，极值，随机值

字符串类型：随机选择一个字符并更改其为随机字符串

将一个字符串随机扩展

随机截断

handle type 不变异

结构体：对其每一个部分分别进行变异

数组：如果已知长度，则对齐每一个元素进行变异，否则只变异第一个元素

指针：对被指向的内容和指针的值都进行变异。

被指向内容：根据指针类型进行变异

对指针本身，和整数变异类似

对所有的syscall参数都进行变异可能会导致syscall序列不合法，因此用变异概率p来控制变异。在变异前先通过概率来决定是否进行变异。在0-1之间随机选择一个数，只有小于p时才进行变异。

lazy mutation

由于syscall错误会直接导致进程结束，这就导致在syscall序列前面的syscall有更大的可能被变异。这个问题就通过lazy mutation来解决

3-6行中抽样统计每个未经变异的的seed中包含的syscall数量，计算avgcnt，并且每次随机选择跳过变异的数量，从这个数量之后的syscall才开始变异。

crash found

在crash时可能会直接重启，因此在虚拟机崩溃时将创建内存存储，在重启后回将存储的文件转发到宿主机。此外内存中还会存储最近的syscall payloads

EVALYATION

静态分析：i7-6700 3.4GHz CPU 64G memory

fuzz：intel Xeon E5-2699 2.2GHz CPU 每个VM 4G memory Vitural box 6.1.0环境运行

windows 分别用了2018的17134.1和2020的18362.592（当时最新）

选取了八个用户程序

AdapterWatch 1.05, Chess Titans [96], DxDiag, PowerPoint 2019 10361.20002, SpaceSniffer 1.3.0.2, SumatraPDF 3.2, Unity Sample [90], and WordPad

RQ1：静态分析的准确度如何？

先从微软的手册中人工提取了64个syscall和326个参数作为基本真值

为什么至少也有31%的误报率？Null指针和栈上的结构体。

为什Nse上涨但是正确率下降？

可扩展性如何？

RQ2确定fuzzer的参数

即变异概率p

p = 0.01 × 2^n, where n ∈ {−3, −2, …, 3}.

对每个p，跑48h，重复五次

不同的p会发现不同的crash。因此，在每次变异的时候随机选择一个p值而不是固定的p值，得到了最多的crash

在下面的实验中也使用随机变化的p值

RQ3 类型推断对fuzz效率的影响

有没有type-aware

type infer正确性。随机将type infer的结果换成整形或者将指针指向的数据大小翻倍。跑48h

NtFuzz阅读笔记