基本信息
原文名称 HTFuzz: Heap Operation Sequence Sensitive Fuzzing
原文作者 Yuanping Yu, Xiangkun Jia, Yuwei Liu等
原文链接 https://conf.researchr.org/details/
ase-2022/ase-2022-research-papers/70/HTFuzz-Heap-Operation-Sequence-Sensitive-Fuzzing
发表期刊 ASE 2022: The 37th IEEE/ACM International Conference on Automated Software Engineering
开源代码 GitHub - sharedata21/HTFuzz: MS-Fuzz data
项目截图如下
摘要部分
堆时序漏洞（UAF、Double-Free、null pointer dereference等）对操作序列高度敏感，可以集成堆操作序列反馈来扩展传统代码覆盖引导的模糊测试。本篇论文利用fuzzing来提高堆操作序列覆盖率和这些堆操作访问的指针多样性，前者反映控制流，后者反映堆操作序列的数据流。随着这两者的增加，fuzzer可以发现更多基于堆时序的漏洞。提出HTFuzz原型，并在14个开源软件上进行测试，结果显示HTFuzz在发现堆时序漏洞上效果更好，并发现了37个CVE。
Introduction
由于AFL覆盖率过于简单，有很多工具如TortoiseFuzz、AFL-sensitive和Ankou，用不同的方法来提高覆盖率的灵敏度，但是都缺乏对堆操作序列的感知。包括PathAFL等，都无法针对堆时序漏洞进行检测。
为了在模糊测试中检测堆漏洞，研究人员提出的一些方案：
依赖先前知识和静态分析来识别候选的漏洞操作，然后像定向fuzz一样引导fuzzer到这些代码区域进行fuzzing。比如UAFL利用静态分析来找到候选HT-Vul和相关堆操作，并将这些堆操作之间的转换作为新反馈，以引导模糊器朝向目标操作序列并触发候选HT-Vuls。
LTL-Fuzzer依靠专家知识在与潜在时间违规相关的位置对应用程序插桩，指导模糊器探索此类检测位置，并在运行时验证违规。
UAFuzz使用定向Fuzz来探索用户预定义的UAF站点。
这篇论文提出了一种新的堆操作序列敏感模糊化解决方案HTFuzz。它不依赖于预定义或预先分析的候选操作序列。相反，我们建议增加堆操作序列的多样性，而不是专注于探索一组有限的候选操作序列。总体来说，我们尝试跟踪堆操作序列，将其用作代码覆盖率之外的新反馈，并引导模糊器增加多样性。堆操作序列的多样性越大，就越有可能找到潜在的HT-Vul。有以下三个问题需要解决：
01
获取堆操作序列反馈的开销：测试用例的执行跟踪中的堆操作数量非常大，记录这些信息需要大量时间和内存。此外很难对两个测试用例的堆操作序列进行对比。HTFuzz使用环形缓冲区来跟踪堆的申请和释放操作，每次访问内存操作都使用环形缓冲区的哈希值作为索引来更新序列覆盖图。意思就是在内存节点将一个完整的堆分配/释放操作序列拆分为几个固定长度的段，将所有段（类似AFL的边）记录在序列覆盖位图中。
02
指针别名的敏感度：堆漏洞还需要堆操作访问的指针，指针可能有不同的别名和不同的生命周期，这会给开发者带来管理上的麻烦，理论上指针别名越多，更有可能触发堆漏洞。但是在Fuzzing中跟踪别名消耗较高，HTFuzz解决方案是：Fuzzing过程中统计堆操作访问的指针（和别名）的数量，在能量调度阶段堆访问更多指针的测试用例进行优先级排序。
03
堆操作序列引导与代码覆盖率协同：代码覆盖率也是很有效的，但是两种引导机制会发生冲突。AFL使用effector map来记录那些可以触发新代码覆盖的interesting字节，在Fuzzing过程中跳过其他字节的变异。但是那些跳过的字节可能有助于堆操作序列的多样化。HTFuzz升级了AFL对应算法，利用MOPT算法来动态调度变异操作来平衡代码覆盖引导和堆操作序列引导。
Contribution
提出了一种新的堆操作序列敏感模糊化解决方案HTFuzz，以有效地发现HT-Vul。
实现了一个HTFuzz原型，并对其有效性进行了评估。在堆操作序列的数量和发现的HT -Vul方面，它超过了所有11个最先进的模糊器。此外，我们还发现了37个新漏洞，包括32个新的HT-Vul。
开源了HTFuzz和相关数据。
Motivation
typedef struct{
const struct box_registry_entry *registry;
...
} GF_Box;
static struct box_registry_entry {
GF_Box * (*new_fn)();
void (*del_fn)(GF_Box *a);
GF_Err (*read_fn)(GF_Box *s, GF_BitStream *bs);
...
} box_registry;
//isomedia/box_funcs.c
void gf_isom_box_del(GF_Box *a) {
other_boxes = a->other_boxes; { use()} //crash
if (!a->registry && use_dump_mode)
a->registry->del_fn(a); // del_fn =free,...
}
GF_Box *gf_isom_box_new_ex(...) {
a = box_registry[idx].new_fn(); //new_fn =stco_New,...
}
GF_Err gf_isom_box_read(GF_Box *a, GF_BitStream *bs) {
return a->registry->read_fn(a,bs); //read_fn =stbl_Read,minf_Read...
}
GF_Err gf_isom_box_parse_ex(...){
if (...)
newBox = gf_isom_box_new_ex(...); ->stco_New() ->malloc()
if (...)
e = gf_isom_box_read(newBox, bs);
}
//isomedia/box_code_base.c
GF_Err stbl_AddBox(GF_Box *s, GF_Box *a) {
switch (a->type) {
case GF_ISOM_BOX_TYPE_STCO:
gf_isom_box_del(s->ChunkOffset); ->free();
}}
GF_Err stbl_Read(GF_Box *s, GF_BitStream *bs) {
e = gf_isom_box_array_read(s, bs, stbl_AddBox);
CALL(gf_isom_box_array_read_ex(..., GF_Err (*add_box)))//do callback
{
while (parent->size>=8){
e = gf_isom_box_parse_ex(...); ->gf_isom_box_new_ex()
e = add_box(parent, a); //if add_box = stbl_AddBox
}}}
//isomedia/box_funcs.c
GF_Err gf_isom_box_array_read_ex(...,GF_Err(*add_box)(GF_Box*,GF_Box*)) {
GF_Err e;
GF_Box *a = NULL;
while (parent->size>=8){
e = gf_isom_box_parse_ex(&a, ...); ->gf_isom_box_read()
if (e && a) gf_isom_box_del(a);
e = add_box(parent, a);
...
}}
int main(){
...
-> gf_isom_box_array_read_ex(...);
以上是一个堆时序漏洞样例，来自MP4Box，the UAF vulnerability CVE-2019-20164，对应CG如图所示，节点表示函数，边表示调用关系。
触发该UAF分为三步：
01
main()一直运行到gf_isom_box_new_ex，这个函数alloc一个堆内存对象
02
后续stbl_AddBox被调用，调用gf_isom_box_del把这个堆对象释放
03
最后，当gf_isom_box_del访问了指向以上这个危险堆内存对象的指针时就会发生crash
触发该UAF的代码行序列：
[56-45-49-24-28-21-22-36-41-24-26 (malloc)-42-31-34-13-14 (use)-16 (free)-50-13-14 (crashed use)]
传统代码覆盖率引导fuzzer忽略了时间线性关系的信息。有两个种子seed1 [mal-loc,use1,use2,free] 和seed2 [malloc,use1,free,use2]，他们对于代码覆盖率来说是相同的，因此seed2会被丢弃，尽管seed2更有保留价值。
Methodology
Overview
基于AFL，主要修改三个部分：种子保留，种子筛选，变异算法。下面详细介绍三个方面采用的关键技术。
堆操作序列反馈
堆操作序列反馈是模糊处理中种子保存、选择和变异的基础。
使用二进制数表示堆操作节省记录空间，如1表示分配，0表示释放。堆操作序列由此可以表示为一串数字。将堆操作序列分割成为片段来更有效地记录。在内存访问操作前将堆操作序列投影到执行时间线上，这些序列由具有堆分配、释放和访问操作的段组成。由于在随后的存储器访问时刻的堆操作序列源自先前存储器访问的状态，序列记录可能会重叠。因此只在内存访问操作之前记录长度为L的最新的堆操作序列。
使用长度为L的环形缓冲区跟踪最新的堆操作。假设堆操作序列表示为[1, 1, access1, 0,0, access2, 1, access3, access4, 0]，若L设置为3，则序列被分割为[0, 1, 1]、[1, 0, 0]、[0, 0, 1]、[0, 0, 1]，然后进一步将缓冲区编码为十进制3、4、1、1，然后使用内存访问操作位置作为下标保存到新位图中。这个位图大致记录了Fuzzing期间堆操作序列的反馈。
access | 缓冲区变化 | 分割区间 | 区间编码 |
0 | [0, 0, 0] <- (1, 1) | - | - |
1 | [0, 1, 1] <- (0, 0) | [0, 1, 1] | 3 |
2 | [1, 0, 0] <- (1) | [1, 0, 0] | 4 |
3 | [0, 0, 1] | [0, 0, 1] | 1 |
4 | [0, 0, 1] | [0, 0, 1] | 1 |
L值越大，反馈对堆操作组合越敏感。但由于开销，L过大会降低Fuzzing效率，通过经验来选择L合适的值，缓解爆炸问题，提高比较差异的效率。
指针别名追踪
堆操作序列的感知可能会使模糊器保存太多Interesting的种子，我们应该优先考虑有价值的种子，以在实践中加速HT-Vul的模糊化过程。
指针别名多样性是发现HT-Vul另一重要因素，在种子选择阶段使用更多的指针对种子进行优先级排序。静态标识那些与指针（别名）访问相关指令，并计算种子执行期间这些指令的频率来粗略表示种子的访问次数。
堆操作序列协同
种子变异阶段，AFL使用 “bitflip 8/8” 的变异方法来提高变异效率， effector map 是用于标识输入中有用的字节，后续避免对那些没有用的字节进行变异。有人指出变异操作的影响差异很大，提出了MOPT算法来动态调度变异操作，以提高代码覆盖率。这两种变异方法都是为代码覆盖率设计的，不适合堆操作序列的探索。
HTFuzz修改了 effector map 的识别算法，将能产生更多新堆操作序列的interesting测试用例的字节也做了标记。此外，基于新的interesting测试用例，引用MOPT算法来调度变异操作，这些测试用例来自堆操作序列反馈以及原始代码覆盖率反馈。
Implementation
插桩
LLVM插桩，除了代码覆盖率，增加追踪堆操作序列和一些指针信息，如算法1所示。
对基本块（line15）进行插桩，收集代码覆盖率作为 BranchCov，存于bitmap。此外，对指针检索相关指令（line18-19）进行插桩，这些指令的操作码为 GetElementPtr 或者操作数为 GetElementPtr 表达式，然后计算runtime时指针访问的次数。
对内存分配和释放函数（line20-21）进行插桩 malloc()、realloc()和free()，在每次调用时进行检测，记录长度为L的环形缓冲区中最新的堆操作。实验部分将L设置为3。
最后，对基本块内的第一次内存访问指令（line22-24）插桩，将环形缓冲区记录到附加映射HeapOpSeq中，这个附加映射用于记录堆操作作为序列反馈。使用mayReadFromMemory和mayWriteToMemory两个LLVM的API来判断是否为一个内存访问指令。
Fuzzing Loop
优化原生AFL的反馈机制，如算法2所示，并升级了种子变异算法和周公子保留和筛选策略。
变异一个种子的时，和AFL一样为这个种子构建一个 effector map 来识别interesting的字节。改进该算法，使得fuzzer也会考虑产生新堆操作序列反馈的那些字节。然后使用MOPT算法对变异操作进行调度，对种子进行变异产生新测试用例。
那些产生新代码覆盖或产生新堆操作序列反馈的种子认为是interesting的用例，并加入种子队列中。公式如下：
改进种子筛选策略（line13），升级AFL的 Update_Bitmap_score()，这个函数用作与调整种子队列里种子的顺序并把一些种子标记为favor。主要改动是把那些有更多指针访问的种子也标记为favor。
Evaluation
研究目标
实验阶段主要通过回答以下三个问题来验证Truzz：
RQ1：HTFuzz是否能找到真实世界的堆时序漏洞？
RQ2：HTFuzz对于堆时序漏洞的fuzzing有多大的提升？
RQ3：HTFuzz与其他fuzzer相比如何？
实验设置
将HTFuzz与11个Fuzzer进行了比较，包括2个专门针对UAF漏洞设计的Fuzzer（即UAFL 和UAFuzz）和9个最先进的Fuzzer（AFL、Angora、MOPT、Path AFL、Memlock、AnKou、TotoiseFuzz和AFL-sensitive的两种实现），再对每个程序进行长时间的(即72小时)测试，直到模糊器达到相对稳定的状态。其次，每次实验进行8次，以消除模糊处理过程中的随机噪声。
实验环境是4台在相同配置的机器上运行，即Intel ( R ) Xeon ( R ) CPU E5-2630 v3 Processor ( 2.40GHz , 32芯)和32GB RAM，64位Ubuntu LTS 16.04
具体实验
RQ1：HTFuzz是否能找到真实世界的堆时序漏洞？
下表是HTFuzz和比较其他Fuzzer发现的漏洞总数，包括HT-Vuls和其他类型的0day和1day漏洞。对于X - Y - Z，X为所有类型的漏洞数目，Y为HT - Vuls漏洞数目，Z为HTFuzz漏掉的HT - Vuls漏洞数目。
RQ2：HTFuzz的消融研究
消融研究的目的就是证明该工具的真实有效性。由于需要设置环形缓冲区长度L和序列位图大小，首先通过对比模糊测试性能来研究不同的设置。然后，修改AFL的三个组成部分（AFL-S、AFL-SP和AFL-SM）时，进行了消融研究，说明不同修改在HTFuzz中的贡献。
1：参数设置
首先对Fuzzer的参数进行验证，这里性能指标选择位图密度和漏洞数量。在原生AFL中，基线为K = 16和L = 0。经过实验，在L = 3，K = 16时得到最好的结果，作为HTFuzz的默认设置。实验数据如下表所示。
2：消融验证
HTFuzz对AFL进行了三部分修改，分别设置了AFL - S、AFL - SP和AFL - SM三个选项来控制每一个选项。此步骤选择的性能指标为：HT-Vul数量、代码覆盖率和堆时序数量。
数据表明三种修改都对最终结果有贡献。虽然代码覆盖率的获胜者是AFL - SM ( 26.41 % )，但AFLSM发现HT - Vuls的能力低于HTFuzz，说明代码覆盖率并不是发现HT - Vuls的唯一标准。因此，HTFuzz的整个解决方案应该包含这三种修改。
RQ3：与其他Fuzzer比较
1：与UAFL和UAFuzz比较
与两个针对UAF漏洞设计的模糊测试(即UAFL和UAFuzz)进行了比较，因为它们是典型的HT - Vuls。具体来说，我们将UAFL或UAFuzz发现的基准应用程序中的漏洞作为指标，在具有相同版本和相同命令的应用程序上运行HTFuzz，看看是否可以发现这些漏洞。表7的结果表明，HTFuzz能够发现数据集中所有已报道的UAF和DF ( Double-Free )漏洞。此外，我们发现了7个之前未知的UAF漏洞，这些漏洞可以被认为是之前模糊测试的漏报漏洞。其中5个被赋予了新的CVEs，另外2个已被他人报道。
2：与其他灰盒Fuzzer比较
“U”和“Avg”分别表示总试验中HT - Vuls的总量和平均值。P值是假定值。“-”表示对应的模糊器无法编译二进制。
如有侵权请联系:admin#unsafe.sh