RWCTF2021 Mop 0day Writeup

在刚刚结束的RW上,今年又出现了一道2019年类似的master of php,刚开始我还不知道,在看完orange的议题之后,主持人讲解的时候我才知道今年又有一道mop,orange的议题也是带来的关于php的web和binary结合,似乎对web选手们越来越不友好了...

回到正题,2021的mop是一道0day,但是很多人应该拿非预期的spldoublelink秒了,我也不例外,今天不讲它,这里我只想分享一下我是如何利用作者预期的0day.

作者给出的0day还是比较有趣的,绕过了php里面type hint,从而导致的type confusion. 我们具体来看一下作者给的trigger poc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<?php  
//author: https://github.com/wupco/
//realworldctf 2021 MoP https://realworldctf.com/challenge
class A{
function __construct(){
// str_ireplace could be replaced by other functions which have "reference args" such as similar_text etc.
$this->{'str_ireplace'} = "call_user_func_array";
}
}

$type_confusion ="AAAAAAAAA";

//arguments list
$args = array("a","b","a",$type_confusion);
array_walk(new A(), "call_user_func", $args);
print_r($type_confusion);
?>

php里面的type hint是个什么东西呢? php本身是个弱类型的脚本语言,但是它也提供typed机制,例如你在定义函数的时候,你如果在参数前面标识上它的类型,这个类型在这里就是一个type hint,如果你传递参数的时候不满足它的类型定义,会直接抛出异常。

但是有趣的是,如果你调用php函数的时候走的是zend_call_function,它也会检查type hint,但是不会抛异常,只会抛一个warning,并且在args no separation的情况下它不会对你传的参数做任何的其他的事,直接的给你传到目标函数上. 如果你的目标函数没有很好二次check参数类型的时候,就可能会发生一些意想不到的情况. 上面的str_ireplace就是一个很典型的例子,它的第4个参数需要的是一个引用类型,在non-debug模式下,它是不会二次检查这个参数类型的,从而导致了类型混淆.如果利用这个type hint的bypass加到fuzzer上,应该也会有一些不错的发现.

我们来看一下这个类型混淆,到底能给我们提供哪些帮助?

1
2
3
4
5
6
7
8
9
10
11
12
13
#define _ZEND_TRY_ASSIGN_LONG(zv, lval, is_ref) do { \
zval *_zv = zv; \
if (is_ref || UNEXPECTED(Z_ISREF_P(_zv))) { \
zend_reference *ref = Z_REF_P(_zv); \
if (UNEXPECTED(ZEND_REF_HAS_TYPE_SOURCES(ref))) { \
zend_try_assign_typed_ref_long(ref, lval); \
break; \
} \
_zv = &ref->val; \
} \
zval_ptr_dtor(_zv); \
ZVAL_LONG(_zv, lval); \
} while (0)

上面zv变量被误认为reference类型进行assign的过程,我们简单看一下reference类型的结构

1
2
3
4
5
struct _zend_reference {
zend_refcounted_h gc;
zval val;
zend_property_info_source_list sources;
};

assign的过程,分为两步:先把原变量的内容尝试释放掉,再把新的值赋给这个变量,你用这个逻辑去看上面的代码,会很快明白这里在干什么。值得注意的是如果reference里面的sources字段不为空的话,会进入一个漫长的判断过程,我们肯定不希望它进去的,因为我们要为此做很多额外的工作.

到了这一步,我的想法是要用这个assign的过程第一步造一个UAF出来,但是非常无奈的是这里似乎没有任何leak的方式,没有一个有效内存块的地址,我们拿什么释放?这里地方我想了一会儿,我想了一个比较有趣的方式,无法leak,我就给它造一个地址出来!

怎么造呢? php有自己独特的内存管理,但是这个内存管理安全性到不怎么样,是因为经常可以通过它实现任意写的效果. 在申请大内存的时候指超过2M的时候,会直接mmap一块内存,这就非常有用了,如果我能再去读一下/proc/self/maps,这块内存地址我们是可以轻易拿到的,然后我们尝试在上面造一个小内存块出来,把它利用上面的洞,再释放掉,丢到php的main heap bins storage上,这样UAF的效果就实现了。

具体怎么做呢? 首先申请一个比较大的内存块 , 然后从这个 里面再切一块大小为2M的chunk出来,因为heap bins storage操作对象是一个chunk,我们把这个fake chunk修剪修剪让它变成一个看起来不错的chunk,再在其上面划分bins,利用类型混淆释放掉再丢到main heap bins storage上. 常规的UAF就是拿到一个可控的closure,然后把其内部的函数handler修改成zif_system,所以我们释放一个closure大小的bin就是比较好的.

我们可以总结一下这个过程:

  1. 申请一个比较大的内存块 ,用maps拿到其地址.
  2. 上在划一个正常的2M的chunk出来,你需要修剪一下,让它成为一个合法的chunk,这里面包括一些比较重要的字段,比如page maps,main heap.
  3. 还是在 上剩下的内存上构造一个fake reference类型结构出来,让它能释放指定内存.
  4. 我们这里最开始用long类型来制造类型混淆,因为long可以直指我们的fake reference.
  5. 最后trigger UAF, alloc closure, motify closure.... 这都是常规思路.

原题只需要通过ini_alter绕一下open_basedir,是有机会读maps的,所以可以造一个有地址的fake chunk出来,还是比较有趣的. 详细的exploit见.

那么不读maps,应该如何leak呢?想一想这个问题...

旭哥儿,最近在筹备我们论坛新年一个小小的趣味ctf活动,让我出一个题,我也想出一个php上的UAF,它不同于功能性造成的UAF,它是php编译优化里面的一个小小东西,是我曾经写出来一个bug... 我觉得php8的进步在于他的optimizer,往这方面研究研究应该是非常有趣的. 不知道大家有没有兴趣....

函子等价

定理1.1. 如果一个函子是等价的,当且仅当这个函子是faithful,full,essentially surjective on objects(dense)。

在证明这个定理之前,需要提出一个小lemma

引理1.2. 对于态射 和同构 , 可以唯一确定态射 ,等价地下面四个交换图

img

从这几个交换图上我们已经很容易构造出 了,简单描述一下,定义 ,反之它们的逆用 表示。第一个最为直观

开始证明定理1.1 给定 定义了一个范畴间的等价关系。对于任意的 ,有 ,取 ,显然 是稠密的。再考虑两个并行的态射 ,如果 ,则 同时满足下面交换图

img

根据引理1.2 是唯一确定的,所有 ,因此 是一个局部单.对称地,考虑 和同构 ,可以唯一确定

img

,所以 是局部满的。

这个方向证明,我在怎么用dense这个性质的时候想了很久,最后突然发现一句“由选择公理”就完了,就完了,是的,你没有听错...

任取 ,由dense性质和选择公理,是可以构造一个 ,在dense下选一个 .对象映射处理好了,就可以来构造一个交换图了

img

任取范畴 中一个态射 , 都是同构,所以可以上面的lemma可以唯一确定一个 。因为 是faithful,所以换个角度看 也是唯一的,现在 里面所有的components都是可以确定一个交换图的,且都是同构的,但是这里有一个问题,我们用选择公理弄了上面这样一个 出来,我们并没有证明它确实是一个函子,还少一步验证它对态射作用,首先是单位态射,我们有下面这个交换图

img

还是由前面的lemma和 上对态射的单射性质,这里有 ,相似地,再给一个态射 ,我们有下面的交换图

img

这里有 .

现在已经完成了前一半的证明,接下来想一下如何构造 .并不能直接来构造,尝试构造下面的交换图

img

声明一下其中的几个定义,态射 ,两个component , ,把 定义为 . 这样做的目的是使得 再反过来做一次就得到了同构 .

再看这个大长方形和两个小正方形的交换性,大长方形由上述定义交换,右边这个小正方形因为 是个自然同构,所以也是交换的,言下之意左边这个小正方形也是交换的。这两个小正方形带来的作用是什么?左边这个交换可以得到

再由 的faithful性质,即有 ,这个等式就表示下面的图交换

img

乎将近拖了半个月的证明,终于证完了,选择公理的应用和间接构造自然同构,还是得在细细想想...

php-optimizer-about-identifying-loops

php optimizer about identifying loops

这篇文章用于记录php optimizer中关于循环结构识别算法,看了一些php optimizer components,目前最大的感受就是一个component一篇论文,每一个component都有它的出处,你如果单看代码,你很难去读懂它在描述怎样一种算法,所以你必须去看它出处的论文,只有读懂论文以后,你才能抓住最本质是东西去套代码。很幸运我遇见了正在“高速”发展的php,我很珍惜跟随着这些写optimizer的developers去学习的机会,php里面几乎%90的optimizers都是dmitry写的,我真的很佩服他...

我最近的工作中也需要identity loops的协助,有向图中循环识别算法很多,php里面用的算法来自于

Identifying Loops Using DJ Graph

这篇论文构造了一种叫DJ图结构去辅助识别循环,DJ图到底是什么呢?其实用特定的flowgraph生成的dominator tree(支配树)的基础上,把原flowgraph的边(不在dominator tree 中)以join edge的形式又添加到了dominator tree上,就构造了所谓的DJ图,这里J就是指的join edge。

Definition: 是flowgraph上的一条边,如果, 则称边是一条join edge。

这里我们引用论文里面的图,来具体的理解一下:

img

图a是原flowgraph,图b是生成的DJ graph,其中虚线是原flowgrpah的dominator tree上的边,而黑体实线就是join edges。

介绍完了关于DJ图构造,现在需要稍微了解一下关于循环的定义,循环也是有两种具体分类:

  • reducible loop

    从循环最本质的直觉上,循环开始叫loop header(循环头),在reducible loop里面这个loop header是唯一,且是严格支配其loop body(循环体)里面所有的节点。

    当然还有更一般的定义,reducible loop 也是指单入口强连通分量。reducible loop也关系到flowgraph的可约性,如果一个图是可约的,当且仅当我们可以对它的边划分为两个disjoint groups:

    • forward edges :所有的forward edges里面的边,可以构造一个无环图,且所有图上的点和root节点都是可达的。
    • back edges:所有的back edges里面的边,目标节点支配源节点,即
  • irreducible loop

    irreducible loop 我们可以使用暴力的手法,不是reducible loop的其他循环都是irreducible loop (很多定义都是这样,但是出奇的好用,哈哈)

有了关于DJ图和循环的基本概念,尝试理解为什么DJ图能辅助识别原flowgraph里面的循环?

我们对dominator tree引入的J边构造了DJ图,可以看到DJ图上也有循环,现在我们还不知道这个循环是不是和原flowgraph是一一对应的,但是我们在尝试关注循环的时候,常常关注一种特殊的edge,称之为back edge,狭义上的理解就是把一条长而直的路径,突然把头和尾连起来变成了一个环。这种定义还是很模糊,我们尝试把这样的边放到DJ图上去,这样边肯定属于J边了,不可能是dominator tree上的边。现在给出严格定义:

Definition:将J边分为两种类型的边: Back J(BJ) 和 Cross J(CJ).

  1. 若一个J边是BJ边,则 dom
  2. 不是BJ边的其余边都是CJ边

BJ边就是我们环里面很重要的一类边,但是我们需要验证一下DJ图上的环和原flowgraph的环是不是一一对应的?

如何证明呢?其实不用证明只要保证原flowgraph上的边都在DJ图上出现了即可,哈哈 有趣。但是呢DJ图因为dominator tree的原因加入了一些在原flowgraph不存在的边?这些边会有什么副作用吗?实际上并不会,你看见似乎引入了很多新环,但是其实我们关注的只有BJ边,BJ边都是实际flowgraph存在的边。

上面把DJ图和原flowgraph的关系理清楚了,那么我们具体是怎么识别环的呢?

一个自然循环在flowgraph里面有循环头和循环体,例如常规的while,for等等,但是也有那么不太自然的循环,例如用goto来构造一个循环,常规的循环其实就是reducible loop,而用goto你就有可能搞出来irreducible loop,前面已经提到了,在reducible loop里面循环头是严格支配其循环体所有结点的,所以只要把每个reducible loop header弄出来,就可以唯一确定一个reducible loop。但是irreducible loop没有这个唯一的循环头啊,怎么办呢?为了和reducible loop识别方法统一,我也要给irreducible loop加一个header,但是这个header不唯一怎么呢?还有办法,对DJ图做一次深度遍历得到一个生成树,在生成树上那个最前面的那个header,我们作为irreducible loop的header。

值得一提是这里有一个小lemma,即使irreducible loop的header不唯一,但是它们都有一个唯一的idominator,这个lemma证明很简单,只需要用反证法假设有两个idominator即可证明,Sreedhar的论文中有详细的过程。

下面是在php中的具体应用

前置工作我们需要的是一个dominator tree,还需要一个DFS spanning tree(深度优先生成树)。在这里php并没有生成一个生成一个显式的spanning tree,而是很聪明地使用entry/times的方式记录深度遍历过程中节点与节点的关系,可以理解为一个拓扑路径: A_entry,B_entry,B_exit,A_exit,这样就相当于B是A的子孙节点,不需要生成完整的spanning tree原因是,我只需要在识别irreducible loop的时候,查询loop header之间的祖孙关系,去唯一标识一个header即可。

找loop header是从DJ图的最下面往上找的,这个可以根据dominator tree level进行排序,具体过程我可以用一个简化的算法表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (n = 0; n < cfg->blocks_count; n++) {
n = sorted_blocks[n].id //sorted_blcokeds 里面已经是从dominator level 从高到底排好了基本块
for (j = 0; j < blocks[i].predecessors_count; j++){ //所有的入度边
if (blocks[i].idom == pred) { //我们只关注J边
continue;
}

if (dominates(blocks, i, pred)) { //当前bb支配前驱节点,也是我们说的BJ边
//这里就是标记reducible loop的位置
}else{
if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) {
//不是BJ边,我们只标记在spanning tree里面那个bb为循环头
//这里就是irreducible loop
}
}
}
//...
}

有了循环头之后,之后就是把循环体对应到循环头上,这里面需要考虑循环嵌套的过程。所以每个bb只关联离他最近那个循环头。

呼,洋洋洒洒写了一些东西,我记性不好,写下来以后忘了看看,不然觉得挺可惜的。后面有时间我也许可以记录一些php里面其他optimizer的东西。如果有人看的话,看看就行,因为很多也是我胡诌的,哈哈。

Fuzzing Error Handling Code using Context-Sensitive Software Fault Injection

paper

0x00 Introduction

Why should fuzzing error handling code?

因为有一些bug存在于错误和异常处理当中,而且想要fuzzing覆盖错误处理,实际上是比较难。

just a challenge,nothing else!

History

static analysis 容易造成很多的false positives(缺少运行时的信息, reachable?),为了减少false positives,开始尝试用fuzzing来解决问题,简单的input-driven只能在一定程度上解决问题,因为存在一些异常并不依赖输入。基于直觉的software fault injection (SFI)运营而生,尝试人为的注入一些错误和异常,观察程序在运行时是否能正常的捕获这些错误和异常。

现存的一些SFI技术,通常采用是context insensitive fault injection,这种技术单纯地静态在某一些位置注入异常或者错误,可能会导致程序每次执行到该位置时都会触发错误,而导致一些其他行为,例如程序可能就直接exit,这样的情况下可能会错过一些real bugs,引用文中的例子:

image-20201015104630396 采用上下文不敏感的方法在FuncP中的malloc注入错误,将会导致在调用FuncB时就直接退出了,而你就会错过调用FuncB而导致的double-free。试想有选择性地在FuncPmalloc中注入错误,将会有机会捕获到这个异常(第一个疑问when injects? )。

Bug Examples in Error Handling Code

文中有一个例子举的很好,一下直观的说明了解决这个问题的意义:

image-20201016104742594

patch之前很明显这是UAF ,但是触发这个UAF必须先进入上这个if,文中提到必须在av_frame_new_side_data在申请内存失败,才会进这个if,这下子文章的整个主题“bugs in error handling code”就变得有意义起来了,有些异常的触发极有可能不依赖于输入,文中将异常分为了两类:1) input-related error 和 2) occasional error,第一类好理解,输入相关,第二类通常为内存或者网络引发的错误。为了触发第二类异常,需要改变改变mutate对象,结合Fuzzingfault injection可以擦出怎样的灿烂火花?

0x01 Basic Idea and Approach

Basic idea

为了实现Fuzzingfault injection结合,文中构造了一个error sequence,其中包含多个error point,一个error point表示异常和错误可达且可被捕获,当使用fault injection可以决定每一个error point是否触发错误和异常,类似一个选择开关,形式化的表示如下: \[ ErrSeq = [ErrPt_1,ErrPt_2,\ldots,ErrPt_x],ErrPt_i=\{0,1\} \] 类似程序输入,同样影响着程序执行,其中核心问题变成了“哪些error point应该被触发?使其能覆盖尽可能多的异常处理代码“,在这里插入Fuzzing的思想,把mutation作用到error sequence,来解决这个核心核心。

Error Sequence Model

基础定义:

context insensitive error point\(ErrPt = <ErrLoc>\) (单纯用error site来描述)

context sensitive error point: \(ErrPt = <ErrLoc, CallCtx>\) (在error site的基础上,添加了运行时的调用栈来表示上下文)

其中 \(CallCtx = [CallInfo_1,CallInfo_2,\ldots,CallInfo_x]\)

每一次函数调用包括callercalle\(CallInfo_i=<CallLoc,FuncLoc>\)

FIFUZZ

FIFUZZ就是原文提出的一种针对上面问题的context sensitive fault injection解决方法。它由6个步骤组成:

  1. statically identifying the error sites in the source code of the tested program (静态地识别被测程序源码中的error sites
  2. running the tested program and collecting runtime information about calling contexts of each executed error site and code coverage (在运行时收集error site执行时的上下文和覆盖率)
  3. creating error sequences about executed error sites according to runtime information, and each element of such a sequence is differentiated by the location of the executed error site and the information about its calling context (利用收集到的运行时的error point信息,构造用于执行mutationfault inject的错误序列,)
  4. after running the program, mutating each created error sequence to generate new sequences (迭代生成新的错误序列)
  5. running the tested program and injecting faults according to the mutated error sequences (继续跑输入,并且在运行时执行fault injection
  6. collecting runtime information, creating new error sequences and performing mutation of these error sequences again, which constructs a fuzzing loop (循环往复)

error side定义是指注入的fault可以被正常触发和捕获的位置(code location

image-20201017154306819 我从直觉上猜测的是,通过instrument标记error side,一次运行程序,得到可以被覆盖的error side,并不是简单的count,应该是有上下文敏感的count,通过得到这个信息,构造一个error sequence序列,表示应该去触发哪些error side

文中整个Fuzzing Loop的不同于一般情况下,mutation的对象重点关注错误序列,还有一个问题哪些因素会去影响mutation?其实还是覆盖率,只是变成了error sequence带来的覆盖率,如果一次error sequence可以带来新覆盖率,就把它加到mutation过程的pool里面(还有一个优先级的东西,但是太模糊,“贡献的覆盖率”是指这个error sequence完整的覆盖率,还是在prev error sequence上增长的覆盖率,显然后一种似乎并没有什么道理)。

Fuzzing Loop有一个初始化的过程,因为第一次跑程序的时候,其实是没有反馈的信息的,构造了下面一个初始化的mutation过程,initial error sequence每个error point都是0,然后把它拆开成多个error sequence,其中每个error sequence都只有一个error point是1,且每个error sequence是唯一的。 image-20201017123848006

后面的迭代过程基于覆盖率,mutation尝试将mutate每一个error point(\(1 \rightarrow 0 \ or\ 0 \rightarrow 1\)) ,整个过程并无亮点,我觉得难点在于怎么在动态根据上下文做到的fault injection如何做到的同时mutate程序输入和错误序列?

How to identity error side?

这一章节是第一次接触fault injection的人应该最想要知道的,用它的时候,你必须保证你触发的错误是实际中存在的,不然造成的false positive是没有任何意义的。文中尝试通过静态分析的方法去识别error side,更具体一点,一个特殊的函数调用可能变成一个error side,其unexpect的返回值可能触发异常和错误处理,所以识别error side的粒度其实以函数为标准,具体分析过程如下:

  1. Identifying candidate error sites :在大多数情况下,函数返回值为空指针或者负值时,表示一个failure,如果一个函数调用可能是一个error side,从两个方面来看:1)如果它的返回值类型为指针或者整型;2)它的返回值流到if上,并且检查其值是否为NULL或者zero

  2. Selecting library functions: 在大多数情况下,异常和错误产生于外部的库函数,从这个角度出发,如果定义在当前程序中的函数可能触发异常和错误,代表着它作用域下库函数可能会触发异常和错误。这个描述太过于模糊,应该建立函数的返回值和库函数(可能触发异常和错误)的联系。

  3. 这一步不太容易理解,我尝试用我的理解来讲一下(可能并不是原文的意思,读者需斟酌),第一步确定了候选的函数调用,需要进一步确定这些函数调用的目标函数返回值是否受错误和异常的影响?第二步给了一个最基础的标准,我们可以已知的库函数会引发错误和异常,通过这些库函数再去迭代标识,程序中定义的函数是否可能引发错误和异常?这两个步骤已经可以基本确定一些error side了,然后再这些error side处做一些特殊的instrument,如下: image-20201017152245471

    注意红色的部分,当指定的error point被触发时(需要检查上下文),将被标记为error side的函数调用替换成NULL或者zero,让其触发异常处理。但是第二步描述的非常模糊(个人觉得),只能识别一部分函数可能导致错误和异常,为了尽可能多的识别error function,在第三步这里用了一个统计方法,如果某个函数调用在候选的error side,在程序中全局搜索所有该函数调用的数量 \(S\) ,其中该函数调用的返回值进入if数量为 \(s_j\) ,且 \(s_j/S > R\) ,则认为该函数调用的目标函数是一个error function\(R\) 代表一个阀值,如果 \(R\) 越大,导致error function越少,随之error side越少, \(R\) 的适配需要根据被测程序的实际情况来决定。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int Func_a(){
    p = maybeTriggerError(...);
    if(!p){
    //error handling
    }
    ....
    }


    int Func_b(){
    maybeTriggerError(...);
    ...
    //maybe error handling
    }

0x02 Self Conclusion

有意思的一篇文章,改变了mutation的对象,在这里我总结了几个我想要知道的问题:

  1. fault injection是个什么东西?如何确定error side
  2. 文中新的mutation对象error sequence是如何构造的?
  3. 如何在动态运行时根据上下文做到的fault injection
  4. 如何做到的同时mutate程序输入和错误序列?(相互协调)

这几个问题都在前面有描述了,但是4文中没有提到,Fuzzing Loop反馈驱动比较常规,重点在于如何连续的Perform Software fault injection?

Angora: Efficient Fuzzing by Principled Search

Angora: Efficient Fuzzing by Principled Search

0x00 解决路径问题的五种技术

  1. 上下文敏感路径覆盖 (像AFL这种都是基于bitmap的edge计数,并不细分edge的上下文)

  2. 关于taint analysis 确定 input 和 path constraints之间的映射。

  3. 梯度下降算法 作用在 input mutate(ion)

  4. input的结构推导 (shape => 结构, type => 结构里面字段)

  5. input长度的探索方法

0x01 Something interesting

上下文分支敏感的分支统计

通常情况下我们的分支记录在有向图CFG上来完成,通过执行过程中对经过有向边edge进行计数,这里会丢失一些东西,理想情况下,在CFG上记录一条完整的分支,应该是edges的一个拓扑排序 ,这里变成了单纯的edge计数。作者并没有对这里进行改进,同样还是edge计数,但是他们把相同的edge,置于不同的上下文当作两个不同的edge,这里的上下文特指执行当前edge的函数调用栈。这样在原来计数的基础上提出了更细的计数对象,在一定程度能更细致的区别执行过程中edge的变化。(这些理解只看原文,其实有一点难理解,需要具体的看一下Angora中LLVM Pass过程)

文章在这里用一个例子说明问题,但是这个例子我觉得并不好,作者认为原有的edge计数并不能区别输入为1001的区别,实际上是可以区别的:

image-20201009104051280

10: L3:true;L4:false;L3:false;L10:true; 01: L3:false:L10:true;L3:true:L4:true;L5:(true|false);

两次执行走的分支情况,在01下是其实触发了新的路径,会多出一个L5分支记录,原文说两次都触发执行了L4,L10会被认为没有触发新路径。但是01的时候是触发了L5。 f

注意label %5这个基本块,01是会触发label %5label %8这条边的。所以这个例子实际上在这里不合适。那在这里什么样的例子应该合适呢?应该是确保走过相同的edge的,不同上下文带来的影响。我能想到的唯一改变是下列这种情况:

1
2
3
4
5
6
7
8
9
10
void f(int x){
...
}

void main(){
if(input()=='111'){
f(input());
f(input());
}
}

加入context以后,因为L7和L8,处于不同callside,但是两者调用f,假设经过的edge一样,会导致在f,会多出一倍的edge元素,就像我前面说的,可能以前某个edge计数为2,可能现在被拆分成了两个不同的edge。在某种程度上改变了AFL中的edge计数的feature,可能变得更“敏感”一些了。但是我很难去推演它的这种”敏感“,到底能带来什么?我想要知道这种形式的”敏感“,是否可以孤身存在,而不对其他东西产生影响?这些东西于我而言,现在还是难以解释。

字节粒度的污点分析 (没有涉及taint rules)

文中没有细讲taint的过程,而是主要讲了一下taint过程中的污点表示,taint存在的意义是为了将输入和路径条件建立映射关系,在mutating阶段能更好的去解决路径条件。

定义:标签 表示输入input中的哪些字节会流入变量 。通常 用位向量来表示, 会随着输入的大小线性增长。为了应对large input,文中构造了一个数据结构,来存储和查询

  1. Binary tree:( 代表一个位向量, 代表位向量的长度,长度概念应用树里面,就是指结点的高度)每一个位向量 ,都可以用这个树上的高度为 的节点 唯一表示,从根节点root 路径上的节点依次展开为 。其中的每个结点都一个指向它父结点的指针,这样可以从 开始顺着树回溯遍历得到完整

  2. Look-up table: 表里存储着 , 即保存着指向 Binary tree里面结点的指针。

    画了一个图,方便理解和记忆:

    binary_tree1

插入操作: 1. 去掉 结尾所有的0。 2. 遵循Binary tree策略,用 去遍历Binary tree,如果 ,则follow左子结点,反之亦然,如果子结点不存在则创建结点。 3. 把 存储到树上最后一个visited的结点。

注意到这个算法只在生产新结点的时候,插入 ,所以某个结点如果存在 则后面都是不会发生改变的。我计算得到的空间复杂度跟原文有一定区别,原文是 ,我在计算最坏复杂度时得到的是 . Maybe i am wrong,who know!

基于梯度下降的搜索算法

目标是解决路径,让路径条件满足某种要求,我们从最简单的条件出发,某个二元运算,和两个基本变量:我用 泛指所有可能出现的二元运算,基本变量用 , 表示: 文中尝试将求解约束转化成最优化问题,所以需要让上面的问号变成一个具体的值,而不是通常情况下的 ,文中做一个漂亮的转换。

image-20201010112614754

将二元运算转化成了具体函数,函数值间接表示约束的成立。通过合适的函数表示,将所有的约束成立都变成了 ,复杂的组合条件可以经过转换变成简单的二元运算:

1
2
3
4
5
6
7
8
if(a&b){}

//transform
if(a){
if(b){

}
}

这样,向最优化问题的转换变成了可能。注意 实际上还是一个黑盒函数,你是并不知道它完整构造的,只能通过输入,得到输出,也是一个无约束最优化的标准问题,为了解决这个问题,文中使用梯度下降的方法。

使用梯度下降过程中需要计算梯度,但是前面说了这里的 是一个完全黑盒的函数,甚至可能都不是一个连续的函数。在没有其他方法的情况,只能通过近似计算梯度,来保证后面的运算。

现给出 的定义: ,其中 ,即输入input中与f对应二元运算相关联的值。注意这里的 并不完全是像 中的 一样是单个字节,后面还有一个结构感知的过程,这里 可能是一个完整类型的变量。对于多元函数 而言,它的梯度定义为:

其中 $$ 是一个极小的正数(e.g. ,1), 表示 方向上的单位向量。为了计算每个方向上的偏导数,需要跑两次input,第一次使用original input ,第二次使用经过变换preturbed input ,这里有一个非常重要的问题,有可能第二次使用preturbed input的时候,导致 所指的二元运算所在程序位置变成了unreachable,这个时候会导致无法计算或者计算出来的结果是毫无意义的。原文在这里没有细谈,而是一笔带过,但是在Matryoshka中在这里提到一种解决方法,有兴趣的同学可以去看看。

最后是否能收敛到理想状态的下(小于0或者小于等于0) ,文中提到了三个点:

  • 是一个单调函数或者凸函数。
  • 局部最小值满足约束。
  • 如果局部最小值不满足于约束,Angora将会随机的使用其他的 ,直到局部最小值满足约束。

结构和类型推断

前面提到过 中的 并不是完全字节粒度的位向量,Angora会尝试把一起使用的字节归纳为一个type。文中这里也提到了一个问题,关于为什么要引入这个机制?假设某个程序把4个连续的字节 当作一个int类型,用 代表这个整型,那么在计算 的时候,只需要在 加上 ,但是把其分开成4个方向偏导数分别计算,可能会影响其收敛速度。

结构推断:哪些bytes总是一起被使用?

类型推断:一起被使用bytes是什么类型?

Angora里面的primitive type分为1,2,4,8bytes。它们之前可能会出现矛盾情况(e.g. 相同连续位置,被fetch一次8bytes,同时也被fetch一次4bytes),这种情况下,取最短的type。类型推断的依据使用其上下文的语义所决定的,比如某个指令操作对象是signed int,那么对应的type也是signed int。注意其整个过程都是在动态的污点分析中完成的。

输入长度探索

Angora这里特别地采取了关于输入长度的判断策略,通过关联read-like函数和read 系统调用,对read-like函数传参判定对应的输入offset(taint相关), 还会特殊标记它们的返回值,如果它们的返回值流到了路径条件上,且没有满足路径条件,Angora会尝试增加输入长度。这里我觉得这个策略并不会普遍适用于一般的程序输入,只能说一种有趣的尝试。

0x02 Self Conclusion

很有趣且朴素的一篇文章,使用的5种解决路径方法很实用,且开源(能看代码的感觉真好),但是仔细研究细节可能还是与自己想的不太一样。其中很多东西,可以尝试应用到实际情况下,我觉得就值得。“纸上得来终觉浅,绝知此事要躬行”。

Matryoshka:Fuzzing Deeply Nested Branches

0x00 Questions

这篇文章意在解决“嵌套”的条件结构(注意这里的嵌套并不是狭义上控制结构嵌套),这是一个比较难处理的问题,在找到一个能触发新分支 的输入 ,接下来的策略肯定就是在这个输入 上,去构造新的输入 来触发更多的新的分支,但是这里面有一 个问题,假设新分支 内有一个子分支条件是 ,这个分支条件位置为 (reachable by ),那么分支 的子分支就可以抽象为 ,构造出来的输入 ,极有可能 点并不是reachable,因为可能 点之前的某个分支条件满足性,在输入 上并不相同:

matryoshka

这里通过一个代码片段,来特别地说明几种特殊的情况:

image-20201003200124109

控制流依赖,L6依赖于L2,L3,L4。(这里的依赖对象是分支条件,下同) 数据流依赖,L6依赖于L2,L3。

如果我们想要进入L6的true分支,首先(1 L6 is reachable,(2 satisfies L6’s condition。

0x01 The ways

1.1 分支条件的控制流依赖

这个依赖可以看作是从CFG上剥离出来的东西,图上的点从基本块变成了分支条件,什么是分支条件?可以更具体一点,cmp/jmpz(nz) 等等的组合,为了把分支条件之间的关系,描述更加紧密,文中抽象了一个叫prior conditional statements 的概念,对一个指定的路径条件 ,它的prior conditional statements是可能导致 变成unreachable的一组路径条件。

这个定义在实现过程中还是比较抽象,需要具体的研究一下它的性质,首先考虑它并不是一个等价关系(不满足对称性),那么它是一个偏序吗?自反性很显然,传递性也很显然,反对称性呢?考虑两个不相同的路径条件是否相互为prior conditional statement ,这个不要去想的太复杂,在这篇文章描述的依赖关系下,是不可能做到,因为执行流,两个statements,肯定有一个是先执行的。

抛开反对称性不说,重点关注它的传递性,这里prior conditional statement 关系我用 表示。传递性可以描述为 为了找到指定路径条件 所有的prior conditional statements,可以使用这个性质,但是还需要定义一个immediate prior conditional statement,如果 的一个immediate prior conditional statement,则在 之前找不到第二个prior conditional statement,这个“之前”是指所有执行到 到路径,往后看 都是最后一个路径条件。可以简单的理解为 最近。这个定义对研究路径的同学来说,是非常熟悉的,就是dominator tree的定义,仿照它的定义,是可以给出计算prior conditional statements的算法的。 其中IPrior表示immediate prior conditional statement

通常来说dominator tree只定义在过程内,文中又进一步改进,引入了过程间的prior conditional statement 关系,这个也很好理解,如果一个路径条件 在过程内没有prior conditional statement,那就去找调用个过程的callprior conditional statement,这里会产生一个疑惑不是描述路径条件之前的关系吗?怎么又突然来了一个call,按照定义描述的是“可能导致这个call 变成unreachable的路径条件”,其实是合理的。

我以为文中技术实现是完全建立在静态分析上,但是直到读到这里,tracestack的出现,告诉我极有可能是在动态过程中做的,而且文中给的找immediate prior conditional statement的算法是可以在动态做的。

Intraprocedural immediate prior conditional statement:( of

  • s在同一个函数内

  • 不是 post-dominator (post-dominator :如果 exit -point的所有路径都经过 )

Interprocedural immediate prior conditional statement of

  • 不在同一个函数内
  • 执行的时候, 的返回地址在当前的栈中。
  • 执行过的最后一个调用, 不是 post-dominators

文中还提到的路径分支包含terminator的情况,其实这种属于上面第一种情况了,因为第二个条件已经限定了。但是作者在这里还是特别的拿出来说了一下,我还是在这个放个小例子:

1
2
3
4
5
6
7
if(x==1){
exit();
}

if(y==2){//target
//...
}

1.2 分支条件的数据流依赖

表示流到分支条件 上的input bytes集合, 表示一个或者多个分支条件。当input 处可达,为了进入 代表的分支,需要进一步修改input, 在修改之后, 里面路径条件选择不变的情况下, 还是reachable,从直觉上来说,为了尽可能小的影响 里面的路径条件,需要尽可能的避免修改 input bytes,但是这样做有可能带来负反馈,例如F2中 ,这将直接导致根本无法进入L6所代表的分支。

这种情况下只考虑了分支条件的控制流依赖,并没有考虑路径条件之前的数据流依赖,这里文中又定义了第二种关系effective prior conditional statements ,我们需要稍微去改变一下上面我们的直觉,先忽略考虑reachable,我们需要改变 里面涉及到的input bytes ,改变这些input bytes 意味着 里面和它相关的路径条件的选择可能就会发生变化,我们需要尽可能保证他们的选择,所以应该去重点修改 ,很显然在这里 。这个直觉要比第一次的直觉要好那么一点点,但是也有问题,例如F2中 , ,所以 . 这个直觉在Matryoshka中是第一个求解约束的策略Prioritize reachability

1.3 求解约束

前面已经提到求解约束的一个策略,在这里需要综合考量reachablesatisfy constraints ,文中在这里提出了三种可选的策略,顺序执行:

  1. Prioritize reachability
  2. Prioritize satisfiability
  3. Joint optimization for both reachability and satisfiability

1.3.1 Prioritize satisfiability

这个策略非常有意思,修改 之后可能导致 变成unreachable,但是强制使 里面的路径条件选择不变(运行时),这个过程叫forward, 当在某次修改input之后,满足了条件,结果有两种:(1 如果 中的路径条件选择并没有发生变化,代表 成功了 (2 如果 中的路径条件选择发生了变化,则需要修补发生改变的路径条件,进入backtrack过程。

bracktrace过程从 向后按顺序fuzz 里面的每个路径条件 ,这个过程中需要避免修改流入 或者在 后面的effective prior conditional statementsinput bytes,bracktrace成功的标志是处理完所有EPrior(s)的路径条件。

还是用F2中的例子来说明问题:假设当前的输入为 , L2,L3是L6的effective prior conditional statements,L2和L3下进入都是true分支,目标是进入L6的true分支,在修改 关联的input bytes过程中,强制使L2和L3也保持true分支,假设 ,满足了 但是L3选择是false,所以进入bracktrace过程,继续slove L3,这个时候需要避免动 的值,当 的时候,就找到一组满足L6的input bytes.但是这里如果在一个forward过程中选择了y=3,就直接导致后面的bracktrace失败了。

1.3.3 Joint optimization for both reachability and satisfiability

总结一下,Prioritize reachability旨在修改那些不会影响EPrior(s)input bytes,保证 reachablePrioritize satisfiability使用forward-backtrace方法,尽可能的满足 .但是它们都可能在尝试优化多个路径条件的时候失败。这里文中通过对Angora的梯度下降算法再改造:

  • 表示 中每一个路径条件的黑盒抽象函数,同样使用和Angora一样的转换表:
image-20201004163325349
  • 其中 相当于一个max函数, 二元运算符表示取最大的那个操作数,并用 表示 的抽象运算。观察这里转换表比Angora多了一个 ,用于区别路径条件类型的最小正数。当 的时候,必然有 , 在这里把 作为预期最优解。(我觉得应该是 ,如何保证每个 这个事实?)。需要注意的是它这里要比Angora做的更好,因为Angora在计算偏导数的时候,并不能保证 reachable,这样得到的结果没有意义,Angora面对这个问题,只是简单提到了通过改变单位分向量的值。这里Matryoshka可以强制保证previous分支选择,来保证计算过程。

    同样这样也用F2中的例子来说明问题,让 为初始 通过梯度下降,最终会得到一个solution

1.4 隐式条件路径

直接用例子来说明问题: image-20201004184742827

L6计算显式的 ,很显然L3应该是属于 的,但是现有的方法是无法把它区分出来的,针对这种类似隐式的污点传递,通常的做法是如果路径条件被污染,则把该分支下的所有赋值操作都视为污点传递。这种方法文中提到,可能会导致over tainttaint explosion 。(但是我认为这样做理论上并没有问题,例如L4中n也被tainted,作者认为是useless,就算它是useless也不会影响其他的东西,考虑到因为这些污点导致更深的传递过程,也是合乎情理的,这属于一种indirect tainted,我猜测处理它的难点在于与之关联的input bytes不好做对应,这个过程需要手工的添加一些额外的taint rule

作者并不想按照通常的手法来操作,而是通过相关的策略把隐式污点过程筛出来:假设当前的 reachable的,但是经过mutate以后变成unreachable了。再额外运行两次,第一次记录original input过程中经过的路径条件,第二次记录mutated input过程中经历的路径,但是这个过程强制进入original input的路径选择,使其变成reachable,这两次得到的路径条件序列应该是相同的,按时间倒序检查它们的路径条件序列。

如果存在一个 ,并且 前后两次路径选择并不一样,则有可能存在与 的隐式路径依赖,需要进一步做验证,再跑一次mutated input,并且强制针对下面的路径条件和original input做到统一:

  • 所有在r之前的条件路径

  • 所有显式的effective prior conditional statements

  • 所有已知的隐式的effective prior conditional statements

如果结果sunreachable 确定是存在的隐式路径依赖,我举个小例子,帮助理解和回忆:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
y=0;
z=input();
if(z){
y=1;
x=2;
}

if(y){
useless=1;
}

if(x==2){
if(a==19970131){//target conditional statement
//...
}
}

假设original input对L13是reachable,但是mutated inputunreachable.两次的路径序列:

  • L4:true;L8:true;L12:true
  • L4:false;L8:false;L12:false

逆序比较:

  • L12不属于 ,按照验证算法,这里是L13是unreachable的,所以L12属于隐式的effective prior conditional statement

  • L8不属于 ,按照验证算法,这里L13还是reachable的,所以L8不属于隐式的effective prior conditional statement

  • L3不属于 ,按照验证算法,这里是L13是reachable的,所以L3不属于隐式的effective prior conditional statement

奇怪得到的结果却是L3不属于隐式的effective prior conditional statement,原文中的逆序比较似乎不合理?这个演算结果我没有想到。

0x01 Self Conclusion

在看Angora我就有一个疑问,关于梯度下降算法,因为无法保证目标路径分支是reachable的,所以计算梯度得到的结果是毫无意义的,在这篇文章里面给了我想要的答案,作者似乎修补了这个很重要的问题,用force的方法,保证两次走过的路径条件一样。疑问又来了,这样做的理论依据在哪呢?

Out Of Control: Overcoming Control-Flow Integrity

PS:读的同学需要有一点ROP的基础

Abstract

Abstract—As existing defenses like ALSR, DEP, and stackcookies are not sufficient to stop determined attackers fromexploiting our software, interest in Control Flow Integrity (CFI)is growing. In its ideal form, CFI prevents any flow of controlthat was not intended by the original program, effectively puttinga stop to exploitation based on return oriented programming(and many other attacks besides). Two main problems haveprevented CFI from being deployed in practice. First, many CFIimplementations require source code or debug information thatis typically not available for commercial software. Second, inits ideal form, the technique is very expensive. It is for thisreason that current research efforts focus on making CFI fastand practical. Specifically, much of the work on practical CFI isapplicable to binaries, and improves performance by enforcing aloosernotion of control flow integrity. In this paper, we examinethe security implications of such looser notions of CFI: are theystill able to prevent code reuse attacks, and if not, how hard is itto bypass its protection? Specifically, we show that with two newtypes of gadgets, return oriented programming is still possible.We assess the availability of our gadget sets, and demonstratethe practicality of these results with a practical exploit againstInternet Explorer that bypasses modern CFI implementations.

0x00 文章的贡献点

  • 评估现有的CFI技术,证明它们并不能有效的防御一些高级的ROP攻击
  • 提出一种针对CFI的普遍绕过技术
  • 在realworld里面使用了这种技术

0x01 CFI技术背景

  • 理想CFI

    所有的程序控制流传输过程可以分为:直接跳转(direct jmp)和间接跳转(indirect jmp),direct jmp是硬编码的一个fixed address,所以没必要对它做额外的检测,而indirect jmp指向目标可能并不固定,这时候需要根据程序本身的CFG或者CG收集一张可能指向的目标地址列表,在跳转之前插桩检查实际目标地址是否在这个列表里面。对每一个可能成为target的instruction设置一个unique id,前面这张表就可以存储目标地址所在的instruction的unique id.

    构建理想状态下CFI会有一些问题: 比如需要绝对精准的CFG和CG图,同时还有一个不能忽视的问题是性能问题,例如target list 是一个很长的表,可以想象频繁调用这个indirect jmp可能带来的问题。

  • 部分CFI

    尝试聚合unique ID,没有必要给每一个可能成为target的instruction设置一个unique id. 同样完整的CFG也是重中之重(pointer analysis 就显得尤为重要),那么怎么解决这个问题呢? 研究人员想了一个非常极端的方法,将控制流可能传输到的位置分类,主要是根据indirect jmp的类型: function calls,returns ,indirect jmps. 所有把indirect calls target 定为 functions, 把ret target 定为 instructions follow funtions call(注意这里的函数是指所有出现在当前程序里面的函数), 前面这一串叙述就是在说indirect call的目标地址只能是函数的开头和ret指令的目标地址只能是某个call指令后面的指令.

    这个解决方案,个人觉得算是一种妥协吧,把所有合理的indirect jump target都收集起来,针对这个方法,后续就提出一些有趣的改进,transfer 意味着传输关系的start端:

    image-20200927114054599
  • weekness

    作者在文中提出了一个ideal CFI下依然存在的缺陷,就算是完整的CFG,也不能提供运行时的sensitive context,我举个小例子,a -> b,c->b都可达,在实际runtime阶段调用a->b,但是b在return的时候并不能保证它的return到caller也就是a,因为这个静态CFG提供的映射关系并不是单射。在更普通的情况下,如果只用两个IDs来实现CFI,其中红线就是可能会出问题的地方。

    image-20200927124821198

0x02 在CFI下实现ROP

  • CFI下可用的gadget

    1. Call-side gadgets : 紧跟着call/indirect jmp 指令后面的gadgets

    2. Entry-point gadgets: 函数入口处的gadgets

      image-20200927141448231

      这类gadget都是indirect 跳转下allowable target的开头,不同于正常情况下的gadget,它们的起始需要一点限制,并且这可能导致这些gadgets的大小变的不可控。作者提到这种gadget中还可能包含一些分支路径,如果这些分支路径的条件我们可控,那么是可能去跳过执行某些代码,这可以使得一个gadget多用.

      文中将CS类型和EP类型组合而成的gadgets具体的分为了18种,对一个具体gadget的prefix,body和suffix分别进行分类. 这样做的目的是刻画执行一个gadget时控制流可能发生的状态. 如下表: image-20200927225632019

  • 如何调用函数?

    1. 直接通过indirect call :因为indirect call总是允许调用存在的函数,这里的前提是我们有机会直接控制这个call的target。CFI规则越松散,越多的函数我们可以调用。

    2. 通过gadgets里面的call指令:直接用一张图来说明:

    image-20200927225412276

    特别的说一下中间这种gadget可能允许我们访问敏感函数,例如CCFIR就对敏感函数做了特殊的处理。

  • 如何连接这些gadgets?

    这些gadgets 连接过程需要非常特殊,如果你可以控制ret的目标地址,那这个目标地址就只能是CS后面的指令。

    image-20200927233226900

    同样如果你可以控制indirect call的目标地址,那这个目标地址就只能是函数入口,也就是说无法做到任意链接,这里的链接过程是有限制的。

image-20200927233247609

​ CS和EP两种gadget之间是可以相互转换的,例如EP 转CS:image-20200927233337505

这里有一个细节需要注意,也就是注释框里面提到的,B函数中间的这个indirect call必须要这个ptr合法,这也是前面我提到的为什么要细分两种gadget的中间指令。下面是CS转EP的过程:

image-20200927233337505

  • 从ROP到代码执行

    单纯的用ROP来实现getshell是比较难的,文章作者思路是用ROP调整page的权限,然后写shellcode,最后通过间接跳转执行这段shellcode。

0x03 Do it at Realworld

这一节作者利用了一个ie 浏览器的堆溢出来说明他的方法是可行的,关于漏洞具体构造需要自己手动实践,在这里我主要记录几个有意思的东西。

  • Springboard section

    CCFIR里面使用了这个东西,这个东西是一个indirect call的跳板:

    image-20200928100941676

    可以看到这里一个indirect call首先变成了一个direct jmp,跳到了这个特殊的Springboard section上,这个设计还是比较精妙的,在这个特殊的section上全程是没有动栈的结构,所以在ret的时候可以不用担心。那么在这种机制下面,check的条件就发生了变化,首先indirect call和ret的目标地址都是在Springboard section上的而且是对齐的,这就对使用gadget来实现函数调用提出了更高的要求,在实现上通过重定位和导出表的信息把指定函数位置替换成了CCFIR自定义的stub地址,其中还提到这个stub位置在加载时候是随机的,这函数调用变得更加困难了,意外着你必须首先泄露这些stub的信息。

  • 主要实现细节

    通过这个堆异常,给了attacker控制一个indirect jmp的机会,但是为了实现ROP,作者尝试把这个indirect jmp 变成 retn ,但是还需要一个stack pivoting (我称之为切栈小助手)来保证你有一个可控的栈来执行更多的gadget,后面就是相关函数调用。 这里面出现了几个有趣的问题:

    1. 为什么要把这个可控的indirect jmp转换成可控的retn?这过程中遇到了哪些问题?

      因为前面我们知道,indirect jmp 只能衔接EP类型的gadgets,但是EP类型gadgets实际并不好利用,CS类型gadgets相对来说更好利用,而且比较多,为了用CS类型的gadgets,就必须需要一个可控的ret才 行。

      image-20200928110644624作者通过四个gadgets完成了这件事,在堆溢出这个地方,indirect call控制的是ecx,这个要先了解一下,最后,让我们来一起用欣赏的眼光来看看这四个gadgets!

      image-20200928110921577

      这是图中第一个EP-IC gadget,ecx是我们可控的,间接导致来edi我们可控,最后这个indirect call可控。image-20200928112042240

      这是图中第二个EP-IC gadget,在这个gadget里面没有改变edi的值,edi还是可控的,所以现在还可以控制栈最后结构,最后这个call依赖于eax,而eax同样是被ecx控制。

      image-20200928111219406

      图中第三个EP-R gadgets,可以用简洁有力来形容,还可以控制返回值。这个gadget主要来用来应对突然出现的indirect call不会报错和其他副作用,就单纯的直接return到caller。

      image-20200928112907683

      图中最后一个EP-IC-R gadgets,第三个gadget 就可以用在第9行,防止这个多余的indirect call造成其他的影响,这个返回值是否可控依赖于eax,但是这个eax是从是栈上获取的,而且是第一个参数,而这个参数已经在第二个gadget中被控制了,所以最终就完成了对ret的控制。

      整个过程用的gadgets虽然不多,都是都比较精妙,非常值得学习!

  1. stack pivoting

    有了可控的ret之后,现在可以用CS 类型的gadgets了,为了回到正确的ROP道路上,还需要一个fake stack,注意到在前面的最后一个gadget中,ebp已经是可控了的,因为在pop之前,push 的这个eax是可控的。所以接下来需要改esp,作者找到了一个非常好的stack pivoting,可以直接把esp覆盖成ebp。

    image-20200928115612822这样就有了完全对stack的控制,后面就是正常通过CS gadgets构造的ROP过程。

0x04 Evaluation

作者分析了164个PE文件,提取CS和EP类型的gadgets:

image-20200928122322431

可以看到这一类的gadgets是比较普遍的,CS类型的gadgets要普遍多余EP类型的gadgets,这也是为什么前面要把indirect call 变成ret的主要原因。作者为了执行代码,主要使用了memcpy 和 VirtualAlloc,用来调整page的权限和写入shellcode,同样也分析了一下其他PE文件里面这类包含这些函数调用的gadgets:

image-20200928122722244

虽然不多,但是有!也能说明一些问题。

0x05 Discussion

  1. 一些其他缓解措施:

    kBouncer 通过监控进程来检查函数返回地址是否在call指令后面,这一技术需要硬件的支持(Last Record Branch),其还支持一种启发式的算法,用来检查在没有call的情况下频繁的return操作,这样完全用CS-R构造的ROP chain就没法用了,但是CS-IC-R或者CS-F-R还是有可能骗过这个算法的。

    G-free 通过二次编译,用一些转换公式消除gadgets,并且不允许直接跳到某个函数中间执行代码。这个方法几乎把所有CS类型的gadgets都整没了。但是EP类型的gadgets依然奏效,但是实际上仅用EP来构造exp在实际中是比较难的。

  2. 一些可行缓解措施 在最早的CFI工作中,为了在运行时来实现CFI,构造了一个shadow stack,来保存所有的返回地址,但是这种方法被一些编译优化打破,并不是每一个call都有一个ret所匹配,导致无法在某些情况track the stack。

    ROPDefender 也是一种构造shadow stack的方法,但是它关注的是call-ret的匹配,因此如果一个ret没有被相应的call匹配到,就直接报错了,但是也会被上面的情况所影响。

    CFL(Control-Flow Locking)通过锁的方式来保证CFI,在indirect tranfer之前lock,如果是合理的target则执行unlock操作,locks和unlocks是配对的,基于源代码的CFG形成的。作者认为这种方法在未来是可行的,可以有效的防治它们的攻击,但是缺陷是如果没源码就做不了。

Fuzzing: Challenges and Reflections

0x00 自动化

  1. 需要更多的fuzz工具,针对不同类型的对象,the questions:

    • 如何fuzzing有状态交互的对象?e.g. 协议
    • 如何fuzzing用同时使用多种语言编写的程序?
    • 如何fuzzing图形化程序?(输入可能是用户接口的事件队列)
    • 如何将符号执行应用到输入是高度结构化的对象上?(通常来说符号执行约束对象是数值或者字符串序列)
  2. 如何去发现更多类型的bug?

    • 不应该局限于crash带来的影响,需要更多不同的类型类似AddressSanitizer的东西,在合适的时间和合适的位置,添加合适的assertion。
    • bug的类型通常比较局限于fuzzing对象所实现的语言,大部分可能集中在c/c++,我们更应该关注其他语言可能带来的特性,从更上层的观念来看bug的形成,而不是又把它们翻译成c/c++。
  3. 如何去发现更深层次的bug?(这样的bugs通常满足复杂的触发条件),下面是一些有趣的解决方案。

    • 基于结构感知和语法模版的fuzzer
    • 基于静态分析和符号执行的灰盒fuzzer
    • 基于静态patch的fuzzer
    • 更有效的错误发现策略
    • 基于bugs优先级的策略(种子优先级?)
  4. 需要更多的对bug的认知经验

  • 经过长时间的fuzzing,为什么这些bugs没有检测出来?究竟是什么让它们无法触发?需要自身去实际分析这些bugs的本质,并将它们区分出来。
  1. fuzzer从来都不是一个黑盒子!

    • 许多人认为我们只需要人为对fuzzing初始阶段做一些准备,然后安静的等待结果,把fuzzer想象成一个黑盒子,但是实际上它并不是一个这样的黑盒子,更重要的是我们应该能在某个时刻去干预它,让它在我们预期的道路上,越走越远!
    • 如何让fuzzer和安全人员之间以一种更有效的方式交互呢?
    • 如何让安全人员在fuzzer运行过程中动态的去干预它呢?
    • 如何让fuzzer以更直观方式告诉安全人员,它们遇到的一些难以继续进行的阻力?或者说安全人员如何帮助fuzzer去解决这些阻力?
  2. 如何增强fuzzer的易用性?

    • 各种版本的fuzzer层出不穷,在尝试使用这些fuzzer的时候,我们需要对它有一个完整的认识,这个过程是有学习成本的,如何快速的认知到底这个fuzzer适不适合我去花时间和成本去了解它的内在原理?(减少学习成本)

    • 如何让开发者和软件工程师去更便捷的使用它?(面向人群可能不仅仅是安全人员)

    • 如何快速的利用一些test driver去尝试体验fuzzer?

    • 尝试把fuzzer放到CI或者IDE?

    • 如何打印出更详细的bug reports,让使用者能快速的知道哪里出问题了,出现的是什么类型的bug?

0x01 Fuzzing 论

It is important for any discipline to stand on a firm scientific foundation

有许多前沿的fuzzing技术,但是如何证明某种方法就一定比其他的方法要好呢?这些方法的局限性是什么?我们需要去解释这些方法所产生的结果,并能从结果中做出推断。为了实现这些,我们迫切需要有一个完整针对fuzzing的理论模型。

  1. 当fuzzing过程失败的时候,如何去评估剩余的威胁等级? (失败可以理解为fuzzing结束没有得到相关的bugs结果)

    如果从黑盒测试和白盒测试两个角度来看这个问题,当你使用的是黑盒测试,如果这个时候没有bugs report产生,相对于白盒测试来说,说明剩余威胁等级低的可信度一定是比较小的。进一步我们想象在最理想的环境下,在白盒的基础上用符号执行,把所有路径都能枚举到,并且在每一条路径上都添加assertion,那么它的结果就一定可以作为我们评估的标记,可实际上并不存在。(如果有这样一个god存在,它不需要告诉我哪里有漏洞,只需要告诉我有多少个,那该多好啊!)

    如果把不同类型fuzzer说明问题的能力,用一条光谱来表示,那么黑盒测试和白盒测试一定是位于这条光谱的两端。前面说了一下如何通过白盒方法去理想的验证剩余威胁度,当然黑盒情况下,我们也能通过一些方法说明问题,把黑盒测试想象成对程序输入空间的一个随机抽样,通过统计学的方法建立威胁评估。

    同样介于黑盒测试和白盒测试之间,还存在灰盒测试,灰盒测试通过程序反馈来构建比黑盒更有效的输入,但是如何通过程序反馈来区别于黑盒测试的评估过程?(我想程序反馈的引入,相对于提供了一种映射存在,映射的存在直接导致是等价关系的产生,使我们能缩小程序的输入空间,这种映射是很自然的满射,如果用代数的思想去看代它,类似同态,但是这个特殊的代数结构它的二元关系怎么定义呢?即输入和输入如何建立运算呢?非常值得探索!很多fuzzer输入和输入之间都是独立的!)。

    说了这么多,其实最后我们希望能有一个完整的理论框架来帮助我们去回答这样的种种问题,让其中的方法更加的general。

  2. 黑盒fuzzing,灰盒fuzzing,白盒fuzzing它们的理论限制是什么呢?

    在一般情况下,fuzzing的速度上黑盒 > 灰盒 > 白盒,但是在效果上 白盒 > 灰盒 > 黑盒。这将会导致一些问题的解决方式:

    1. 如果给定时间限制,我们应该如何选择不同的fuzzing技术?或者说通过组合不同的技术? 目的是让其在指定的时间内,找到更多的漏洞!
    2. 被测程序的文件大小和复杂度是否会影响不同fuzzing技术的适应性和性能?
    3. 如果拥有的计算资源提升,对fuzzing效率是一种怎样的增长?

    通过理解不同现存fuzzing的理论限制,我们就能去尝试回答上面的一些问题,并且开发出更有效的fuzzing技术!

0x02 评估和基准测试

当一个新的fuzzing技术横空出世的时候,我们需要用完整的方法去评估它。一般来说,我们常常关注它是否能在合理的时间中找到更多有趣的bugs (the better fuzzer)。 那么问题就来了,“合理的时间”,“有趣的bugs”,如何去用更本质方法的描述呢?如何防止过度拟合呢? 合适的基线对照组应该是什么呢? 如何比较它们的effectiveness和efficency

  1. 如何评估一些特殊的fuzzers?

    现存的基准测试方法可能无法覆盖所有的不同类型的被测系统,在这种没有情况下,我们就代表研究者去选择合适的程序和基线对照组。

  2. 如何防止benchmark过度拟合?

    将不同类型的fuzzer的benchmark分类,让所有的研究者来维护它,种做法主要是为了防止单一的组织对benchmark的过度控制(透明且多样)。其实1,2两个问题都可以归纳到如何解决Fuzzing工具相互竞争?其中一种方法是将不同类型的fuzzer分类,同一范畴下相互比较,例如基于覆盖率的fuzzing,指向型fuzzing等等。未来也许可以进一步在范畴下根据检测bugs类型和程序类型再划分。另一种方法是让fuzzer去处理一些challenge problems,其中里面是藏着一些经过精心设计的bugs,fuzzer的设计者只需要负责将自己的工具调整到最佳状态。

  3. 人造的bugs是否说明问题?

    synthetic =?real world

  4. fuzzer 发现的real world bugs是否之前已经被发现了?是否有代表性?

    建立被fuzzer发现的漏洞数据库

  5. 覆盖率是否真的是一个用于测量fuzzer effectiveness好的度量?

    覆盖率的增长对发现漏洞可能性增长 是怎样一种关系?

  6. 什么是合理的时间预算?

    时间的增加是否影响漏洞被发现的可能性?相同时间下,发现的漏洞数量,是一种测量effetiveness的方法,但是这个时间应该如何去做限制呢?

  7. How do we evaluate techniques instead of implementations?

自己的观点

最大的感触就是“Human in the loop”,我把它翻译成了Fuzzing从来都不是一个黑盒子,这一点我自己深有感触,在做实际做东西当产品用的时候,却偏偏让你做成一个黑盒子,这一类的安全产品实际上并不是给完全不会安全的人用的,这一点要特别明确。但是让安全产品快速的让普通的程序员,就马上使用,在未来依然是一个很大的挑战。关于evaluate的东西我记录的很少,因为我总觉得没有一个规范的东西在那里,也许小领域也就这样,没有完整而坚实的理论基础,Fuzzing未来的路真的还有很远要走。

尝试化简php-mm中关于small_bin的index计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>

int zend_mm_small_size_to_bit(int size){
return (__builtin_clz(size) ^ 0x1f) + 1;
}

int php(int size){
unsigned int t1, t2;

if (size <= 64) {
/* we need to support size == 0 ... */
return (size - !!size) >> 3;
} else {
t1 = size - 1;//311
t2 = zend_mm_small_size_to_bit(t1) - 3;//
t1 = t1 >> t2;
//printf("t1:%d\n",t1);
t2 = t2 - 3;
t2 = t2 << 2;
//printf("t2:%d\n",t2);
return (int)(t1 + t2);
}
}

int my0(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-1;
offset = (t1 - (1<<high) + (1 << (3+high-5))) >> (3+high-5);
//printf("offset:%d\n",offset);
return offset + ((high-4)<<2)-1;
}

int my1(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-1;
offset = (t1 - (1<<high) + (1 << (high-2))) >> (high-2);
//printf("offset:%d\n",offset);
return offset + ((high-4)<<2)-1;
}


int my2(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-3;
offset = (t1 - (1<<(high+2)) + (1 << (high))) >> (high);
//printf("offset:%d\n",offset);
return offset + ((high-2)<<2)-1;
}

int my3(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-3;
offset = ((t1 - (1<<(high+2))) >> (high)) + 1;
//printf("offset:%d\n",offset);
return offset + ((high-2)<<2)-1;
}


int my4(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-3;
offset = ((t1 - (1<<(high+2))) >> (high));
//printf("offset:%d\n",offset);
return offset + ((high-2)<<2);
}


int my5(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-3;
offset = (t1 >> high) -(1<<2) ;
//printf("offset:%d\n",offset);
return offset + ((high-2)<<2);
}


int my6(int size){
unsigned t1,high,offset;
t1 = size-1;
high = zend_mm_small_size_to_bit(t1)-3;
offset = (t1 >> high);
//printf("offset:%d\n",offset);
return offset + ((high-3)<<2);
}


int main(){
/*
8,16,24,32,40,48,56,64 (+8)
80,96,112,128 (16)
160,192,224,256 (32)
320,384,448,512 (64)
640,768,886,1024 (128)
1280,1536,1792,2048 (256)
2560,3072 (512)
*/
printf("%d\n",my6(2600));
printf("%d\n",php(2600));
return 1;
}

small_index在8-64之前按8递增,所以直接除8即可(考虑size==0的情况,!!0==1)

对于t1和t2的我理解是:t1表示区间偏移,t2区间。整体上区间可以划分位(1-64],(64,128],(128,256],(256,512],(512,1024],(1024,2048],(2048,3072]

第一个区间按8划分偏移,第二个区间按16划分偏移,,,,

可以看出来是有规律的,需要申请的内存大小可能落在其中一个区间里面,区间里面在细分。

如果要判断落在那个区间,直觉上要看size最高位的1落在哪个地方,举个例子如果落在2^6上,则一定在(64,128]上(假设已经排除了<=64)。

最高位用bsr算,则为第7bit位,我们需要再算它在这个区间上的偏移,需要先减去前一个区间最大的binsize,然后再除以现区间的划分size。

kAFL: Hardware-Assisted Feedback Fuzzing for OS Kernels

0x00 贡献点:

  • 系统无关
  • 基于硬件的状态反馈
  • 可扩展和模块化
  • 开源

0x01 在未读文章之前心里的几个问题:

  1. 怎么做到的系统无关?在给kvm和qemu都下patch的情况下?难道是linux kernel作为直接作为host VMM吗?再通过qemu进行系统无关的测试?

  2. 什么是agent?

  3. fuzzing kernel的时候输入是什么?

  4. hypercall是怎么设计的?

  5. fuzzer kernel 发生系统级别的crash怎么办?或者说怎么定义在kernel的crash(像二进制那样)

  6. 整个系统虚拟化的构建是怎么样的?

  7. 如何利用intel PT?

  8. 关于qemu-pt相关patch的实践?

  9. 最后也是构造了AFL里面的bitmap,那么如何通过intel PT的数据来构造的?

0x02 通过阅读得到的答案

  1. Agent 是什么?

    全称User Mode Agent,它运行在虚拟化的系统中,用于通过hypercall 同步fuzzing逻辑的输入和输出,比如你想测试一个文件系统,那么输入就是文件映像,通过挂载文件映像,来实现对内核的输入。

    实际上在实践中,还存在一个loader组件,用于接收所有通过hypercall传输的二进制,这些二进制就代表 user mode agent,这些二进制通过loader来执行。这样策略是得可以重用一个VM的快照,通过传输不同的二进制。

    这里我其实还有一个问题,这里面有两个agent,一个agent 负责运行用来处理payload的另一个agent。那么第一个loader agent是怎么放到vm里面并且运行起来的?这个过程出现在https://github.com/RUB-SysSec/kAFL主页,需要自己封装一个vm,在里面运行loader agent,然后创建一个快照。

  2. 整个系统虚拟化的构建情况

    fuzzing主要逻辑就是通过qemu-pt和kvm-pt交互来运行目标VMs。

    关于物理cpu,逻辑cpu,虚拟化cpu的结构定义:物理cpu就是指硬件cpu,逻辑cpu指通过物理cpu衍生出来逻辑上的cpu,一个物理cpu可能对应多个逻辑cpu,当某一个时刻只有一个逻辑cpu在运行,而虚拟化的cpu是指,虚拟机使用的cpu,在逻辑cpu上又分化出来的东西

    kvm-pt 和 qemu-pt交互主要用于inter pt的操作。kvm-pt给qemu-pt传输相关的trace信息,trace的解码过程发生在qemu里面,还涉及到trace相关的过滤问题。

  3. 如何利用intel PT?

    首先通过一个特殊MSR(model speical register)IA32_RTIT_CTL_MSR.TraceEn 打开,然后做一些关于filter的选择。这个trace针对的是一个逻辑cpu,所以针对它的修改必须发生在cpu把host context切换到vm context上,关闭trace的操作即相反。

    intel PT的需要一些配置项来支持,也是通过设置其他的MSR来完成的,为了避免收集一些不必要的trace信息,通过intel vt-x来在VM-entry和VM-exit来自动自动加载这些配置项。

    那么存储trace信息的结构是什么?在配置的时候会选择一个物理地址,trace信息会不断的写入这个物理地址,直到被写满。这个buffer被一个叫 Table of Physical Addresses数组结构管理,这个数组可以存储很多元素,结尾有一个End 元素。

    文中还考虑了一个溢出的问题,为了避免溢出造成的trace丢失,这里使用了两个ToPA元素,当一个被填充满时,会触发一个中断,当中断传递到位时可以接着使用第二个buffer,如果第二个buffer也被填满了,将直接导致trace 停止。第二个buffer大小的选择是作者在实践中遇到溢出最多的trace info的4倍。后面如果第二个够buffer被填满以后,可以动态的调整第二个buffer的大小来满足所有的trace 信息。

  4. 关于qemu-pt中相关patch的实践?

    首先qemu作为fuzzer和kvm的中间连接点,如果想了解整个系统的过程,必须弄清楚qemu在其中的担任的角色。从fuzzer和qemu的交互开始,qemu-pt在注册了一个新的pci device,这个新的device负责在qemu的启动的时候,建立fuzzer和vm的联系。

    1
    "-chardev socket,server,nowait,path=" + self.control_filename + \

    qemu 通过这个本地的socket和 fuzzer进行交互。这个fuzzer只通过这个socket进行对qemu的行为控制,agent 二进制,bitmap,payload的传输还是通过shm来交互。

    1
    2
    3
    "-device kafl,chardev=kafl_interface,bitmap_size=" + str(self.bitmap_size) + ",shm0=" + self.binary_filename + \
    ",shm1=" + self.payload_filename + \
    ",bitmap=" + self.bitmap_filename
  5. VM-exit 之后kvm和qemu的交互是怎么样的?

    这个过程涉及到kvm的异常处理,例如当hypercall导致的VM-exit,kvm中vmx驱动有一个专门响应不同情况下VM-exit的handler:

    image-20200728112652038

    这里hypercall对应的就是handle_vmcall -> kvm_emulate_hypercall,在这个里面处理各种来自ring0或者ring3的hypercall。vmcall有几个相关的寄存器,其实类似syscall,以kafl打的patch为例:

    image-20200728113139166

    这是一个处理来自ring3的请求,即agent的请求,rax里面代表kafl相关的hypercall,rbx则代表了agent的相关需要,其中exit_reason代表了VM-exit的原因,后面则是相关需要返回给qemu的参数值。

    而在qemu里面有一个闭环,这个闭环发生在kvm_cpu_exec里面,这里闭环我简略成下面的形式:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    do{
    ...
    run_ret = kvm_vcpu_ioctl(cpu, KVM_RUN, 0);
    switch (run->exit_reason) {
    case KVM_EXIT_KAFL_ACQUIRE:
    handle_hypercall_kafl_acquire(run, cpu);
    ret = 0;
    break;
    case KVM_EXIT_KAFL_GET_PAYLOAD:
    handle_hypercall_get_payload(run, cpu);
    ret = 0;
    break;
    case KVM_EXIT_KAFL_GET_PROGRAM:
    handle_hypercall_get_program(run, cpu);
    ret = 0;
    break;
    ...
    }

    }while(ret==0)

    qemu就负责处理来自kvm的返回信息,处理完成,进而又让vm重新运行起来。

  6. qemu是怎么把guest virtual address转化成在qemu可以写入(读)的地址?

    kafl 整体上是qemu和kvm交互,然后在客户os里面放了一个agent,这个agent负责对客户机进行输入,同时接收来自qemu传递的payload,为了实现agent的功能,它们在kvm里面搞了几个特殊的ring3级别的hypercall。agent进行vmcall 系统调用的时候,这个vmcall和syscall类似会被kvm捕捉到。比如现在agent 需要payload输入了,就弄一个vmcall告诉kvm,同时附上这个输入payload的地址,这个地址就是客户机的虚拟地址,kvm捕捉到了这个hypercall把信息返回给了qemu,然后qemu要向这个客户机的虚拟地址(gva)写入payload。

    在写的时候,我发现它里面逻辑似乎有点问题的,客户机的物理地址实际都是qemu的给定的,在对gva进行写入的时候,需要先把gva转化成客户机的物理地址(gpa),gpa就对应了qemu给定的宿主机的虚拟内存。

    在写的时候,如果数据比较大,需要分页写入,因为x86里面的内存交换大小是0x1000。比如写入往0x10010写入0x2000的数据,首先要去找0x10000对应的客户机物理地址phyadr,然后往phyadr+0x10 写入 0x1000-0x10的大小的数据。 相对于写了0x900,还剩下0x1100,那么接下来需要去找0x11000对应的客户机物理地址,再循环写入。

    但是看kafl里面qemu关于对客户机虚拟地址写入的相关代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    bool write_virtual_memory(uint64_t address, uint8_t* data, uint32_t size, CPUState *cpu)
    {
    int asidx;
    MemTxAttrs attrs;
    hwaddr phys_addr;
    MemTxResult res;

    uint64_t counter, l, i;

    counter = size;
    while(counter != 0){
    l = x86_64_PAGE_SIZE;
    if (l > counter)
    l = counter;

    kvm_cpu_synchronize_state(cpu);
    //cpu_synchronize_state(cpu);
    asidx = cpu_asidx_from_attrs(cpu, MEMTXATTRS_UNSPECIFIED);
    attrs = MEMTXATTRS_UNSPECIFIED;
    phys_addr = cpu_get_phys_page_attrs_debug(cpu, (address & x86_64_PAGE_MASK), &attrs);

    if (phys_addr == -1){
    printf("FAIL 1 (%lx)!\n", address);
    return false;
    }

    phys_addr += (address & ~x86_64_PAGE_MASK);
    res = address_space_rw(cpu_get_address_space(cpu, asidx), phys_addr, MEMTXATTRS_UNSPECIFIED, data, l, true);
    if (res != MEMTX_OK){
    printf("FAIL 1 (%lx)!\n", address);
    return false;
    }

    i++;
    data += l;
    address += l;
    counter -= l;
    }

    return true;
    }

    用我们之前的例子,这里的size是0x2000,l的大小是页大小0x1000,按照第一个条件这里1是小于counter大小的,所以写入长度为l的大小0x1000,但是我们前面正常逻辑这里一个是写入0x900,因为是从0x10010开始的,写入0x1000超过了一张物理页的大小。所以这里还应该考虑一下剩余页大小,读的时候也有这个问题。

  7. 如何利用intel PT的数据来构造和AFL里面关联edge的bitmap?

    这个其中详细技术细节在原论文中并没有太多的介绍,我自己通过翻intel 手册里面关于processor trace的相关资料,能大概的知道整个技术细节。首先需要从intel PT output的数据结构开始。在kafl中只重点关注三种packet:

    • TNT : 条件分支,taken or ont taken
    • TIP : 间接分支,异常,中断和其他分支或者事件的目的IP。
    • FUP:异步事件(中断或者异常)的源IP。

    后面两种其实合为一种,都是只管关注IP属性,简单介绍一下三种数据包的结构:

    • TNT :每个条件指令的token or not taken用1bit的1和0来表示,TNT又有两种分组:分为short TNT(1字节)和 long TNT(8字节),short TNT可以最多包含6个bit TNT,long TNT可以最多包含47bit TNT,结尾用1标志或者stop bit。

      image-20200730123357990
    • TIP:包大大小9字节,第一个字节包含TIP类型标示位和IP压缩的类型。image-20200730123322047

      这个IP压缩策略,意味目标IP的大小是多样的,用IPBytes来表示压缩策略,IP压缩通过与上一次的IP相互进行比较来生成当前IP,比如上一次IP(last_ip)和这一次IP有同样的高位字节,就可以只记录一次高位字节,压缩的原理就在于压缩高位字节,所以decoder在解码的时候需要记录last_ip,来生成每一次TIP里面的经过压缩的IP真实数据,IP压缩策略有下面几种:image-20200730124118977

    • FUP的结构是TIP上一样的,这里就省略了。

      可以通过intel手册上一个例子,来比较形象的体会这样的trace 信息。

      image-20200730124427212

    可以看到上面三种trace信息中,是无法直接利用的,我们需要准确的指令位置和目标地址,当时intel trace信息是充分考虑了效率,对于条件分支为什么只需要记录taken 信息就够了?因为上面例子可以看到,对应的二进制指令是有准确的目标地址的,所以不需要再额外记录。所以这也是为什么qemu-pt中除了pt-decoder以为还需要,反汇编的阶段。

    利用intel PT的ip filter功能,可以把trace 信息集中在某个具体的二进制中,就给我们的反汇编提供了地方。在qemu-pt也是这么做的:

    1
    2
    3
    4
    5
    6
    buf = malloc(ip_b-ip_a);
    if(!read_virtual_memory(ip_a, buf, ip_b-ip_a, cpu)){
    printf("FAIL 2\n");
    free(buf);
    return -EINVAL;
    }

    再讲intel PT的trace 信息和反汇编的结构结合起来,就能准确的描述每一个分支指令所在的地址和目标地址,这样就有了edge,有了edge就可以翻译成AFL相关的bitmap。kafl在这里利用了一个map结构,把相关汇编指令结构缓存了起来,可以在第二次fetch相关指令的时候直接使用,减少了intel 直接出品的lib runtime dasm的消耗。

  8. The input and crash handler of fuzzing kernel

    1. 对内核输入,取决于你要测试对像,例如你要测试文件系统,那么你输入就是需要挂在的文件映像,挂载过程通过agent来实现。

    2. 怎么捕获内核的crash 和 panic? 在kafl里面通过agent 找到相关kernel自身的异常处理handler地址,再把这个地址替换成自己的handler,这个过程通过hypercall来实现,比如在linux kernel下

      loader agent 先找系统自身的错误处理,在通过hypercall发送给kvm,kvm再发给qemu:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      panic_handler = get_address("T panic\n");
      printf("Kernel Panic Handler Address:\t%lx\n", panic_handler);

      kasan_handler = get_address("t kasan_report_error\n");
      if (kasan_handler){
      printf("Kernel KASAN Handler Address:\t%lx\n", kasan_handler);
      }

      kAFL_hypercall(HYPERCALL_KAFL_SUBMIT_PANIC, panic_handler);
      if (kasan_handler){
      kAFL_hypercall(HYPERCALL_KAFL_SUBMIT_KASAN, kasan_handler);
      }

      qemu把它们替换成ring0级别的hypercall:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      /*
      * Panic Notifier Payload (x86-64)
      * fa cli
      * 48 c7 c0 1f 00 00 00 mov rax,0x1f
      * 48 c7 c3 08 00 00 00 mov rbx,0x8
      * 48 c7 c1 00 00 00 00 mov rcx,0x0
      * 0f 01 c1 vmcall
      * f4 hlt
      */
      #define PANIC_PAYLOAD "\xFA\x48\xC7\xC0\x1F\x00\x00\x00\x48\xC7\xC3\x08\x00\x00\x00\x48\xC7\xC1\x00\x00\x00\x00\x0F\x01\xC1\xF4"

      /*
      * KASAN Notifier Payload (x86-64)
      * fa cli
      * 48 c7 c0 1f 00 00 00 mov rax,0x1f
      * 48 c7 c3 08 00 00 00 mov rbx,0x9
      * 48 c7 c1 00 00 00 00 mov rcx,0x0
      * 0f 01 c1 vmcall
      * f4 hlt
      */
      #define KASAN_PAYLOAD "\xFA\x48\xC7\xC0\x1F\x00\x00\x00\x48\xC7\xC3\x09\x00\x00\x00\x48\xC7\xC1\x00\x00\x00\x00\x0F\x01\xC1\xF4"

0x03 自身的感受

这次搬论文,我没有从论文的结构开始搬,我先大概看了一下,心里总结了一些问题。然后我在去深入的解决这些问题,学到了非常多的东西,受用无穷。这样的论文太少了,没有比较华丽浮躁的技术,但是完整的构建了整个对于kernel的fuzzing系统,并且主要是有源码,在读源码过程中,真的太爽了。kafl是第二个对我受用无穷的东西(第一个给了angr和hopper,哈哈哈),希望我浅薄的理解能带给大家帮助!