php optimizer about ssa

0x01 e-SSA Pis

在SSA我们经常能听见Phi,那么什么是Pi呢?,Pi就是一个特殊的Phi,它有range和constraint.,例如:

1
2
3
4
5
if($a>5){
$a = pi($a) > 5
//..
}
$a = phi($a) <= 5 ???

在路径条件的约束下,转头去执行不同路径分支时,某些变量就自动的满足了约束,但是有些情况我们是可以确定的,比如插入的第一个pi,但是第二个的phi的约束不一定完全正确,因为if分支可能影响$a的值。

php里面只考虑条件分支影响下的局部约束,记录一下几种特殊的约束法则的应用。

  • $a > 5 很显然的约束
  • $a + 5 == 0 这里可以做一个变换 $a = 0 - 5 ,分两种情况讨论即
  • $a + 5 == $b +6 同样这里也可以做变换 $a = $b+((-5)-(-6))$a+((-6)-(-5)) = $b. 这里的range除了constant还有其他变量的依赖. 这里为什么要写成上述的形式,我是按照php里面的计算方式来的,他会有一个操作数的adjustment,比如上面equal的RHS操作数的adjustment就是-5. 同理LHS操作数的adjustment是-6. 最后需要把$a$b都单独表示表示出来,就需要adjustment之间做一下运算了.

上述提到的只是php中关于range的特殊约定格式,你也可以写出自己独特的约定。局部约束真的还是挺优雅的。

考虑几种情况不需要插

  1. 变量在target位置并不活跃,只用了一次,后面就不用了,我们在target位置插入一个,没有什么意义.

  2. 依赖于incoming edge,如果有两条相同的incoming edge就不插,这是什么意思呢? 两条相同的incoming edge会无法区分pi是属于哪条edge. 但是我好奇什么时候会导致有两条相同的incoming edge,真奇怪?

  3. 还有一种非常特殊的情况,首先给一个definition: incoming edge定义为从'from'到'to',我们需要在to这里插入pi,我们考虑插入的pi目的是在to这里添加constraint,给我们后面的分析带来一些便利,但是可能你添加constraint是冗余的,举个例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    $a = $b??$c;

    /*
    *1: T1 = ZEND_COALESCE $b,3

    *2: T1 = QM_ASSIGN $c

    *3: ASSIGN $a,T1
    */

    这里有3行opcode对应了三个blocks,第1行这里是可以尝试给第3行这里添加一个pi的,因为如果从第1行跳到第3行,那么$b肯定不是null. 自然地我们可以在第3行这里添加一个pi断言$b不是null. 但是这没有意义,因为如果执行了第2行,那么第3行这里$b又是一个null,相当于之前添加的那个pi没有任何effort在这里起作用,即. 我们对$b是什么还是一无所知.

    所以我们需要识别可能某个opcode造成的两种互斥的约束是否会merge,如果互斥的值同时可能流到to上,那我们去添加pi几乎没有任何意义的,幸运是,当前php的control flow相关的opcode都只有两个successors,所以我们可能不用考虑多个互斥的值同时作用.

    所以我们现在需要考虑from另外的successor(除了from到to的这条edge),我们记为other. 那么具体的问题是other到to是否有一条路径,并且这条路上,里面constraint对应var没有发生变化?

    其实这个问题回答其实是比较复杂的,因为找路径的同时你还要去关注var没有发生变化. php里面只做了最简单的优化. 记住我们在这里考虑要不要插pi,只是为了避免冗余的constraint,并不是说不能插,也就是说即使插了也是safe的. 所以尽量能减少多少算多少)php在这里会直接考虑to的直接前驱predecessor,如果predecessor里面的var发生变化了,不用想,经过这个predecessor都不会在我们的考虑范围之内了. 如果var没有发生变化,我们就要考虑other到这个predecessor有没有一条路径了,判断有没有路径最简单的方法就是看other是不是这个predecessor的dominator. (笑死!!!!) 再结合我们的问题下一步就显而易见了,有路径不插入pi, 实际上这个是不太准确的,我们在这里只知道有路径,但是路径具体是那条我们并不知道,并且在predecessor前面的路径上的节点var有没有发生变化,我们也是不知道. 所以这里只是作者的小推测. 其他我们没有提到的情况都会插入pi.

    这里考虑如果插入的是prefect pi,那么它是真的有作用的. 如果插入是冗余的pi,这个constraint会造成一些错误吗?因为整个模式都偏向于不要插(留下这个问题,我要去看inference). 但是实际是要插入,而导致没有插入,将会导致后面inference的精度降低.

    exmaple

0x02 SSA Definition

  • 在SSA表示下,任意状态下的某个变量使用,只有一个var definition能够生效。
  • 程序的控制流在SSA下保持不变。
  • 有一个特殊的merge操作,用于处理多个前驱node的变量definition的交汇取值。
  • 并不是所有node交汇处都需要
  • 自然地如果在交汇处所有前驱node对某个变量的definition都相同,则不需要使用
  • use-def analysis is faster on SSA (application)。
  • SSA to machine code i.e code generation

如何精确的插入phi呢?

single reaching-definition: A definition of variable reaches a point in the CFG if there exists a path from to that does not pass through another definition of . (简而言之就是具体某个变量的definition和use之间存在一个条路径,且在这条路径上变量的值没有改变).

直觉上如果有两个distinct 基本块,他们都有关于同一个变量的definition,并且存在一个是它们一个join node即存在非空路径. 那么我们应该在的开头插入,但是这样做可能会导致一些不必要的插入,所以在插入时候,考虑了minimality的问题,理论上我们需要去掉来自两个不同前驱但是对有相同definition的情况,为了解决这样问题这里就引入的join set的,它就表示了对于每个变量的应该至少需要插入的source个数.

Join Set Definition 给定图上的节点集合, 表示一些特殊节点的集合(通常表示某个变量的Assignment BBs):

给定 , 至少有两条来自不同起始节点()的路径在点交汇,且这样的路径之间除了点以外不应该有它们不应该有其他相同的节点(也就是说之间只有一个交点),则

的迭代操作表示为,定义如下: 这样迭代的意义是什么呢? 如果给定的是某个变量被赋值的基本块集合,即下面红色节点,得到了蓝色的结点,得到了绿色结点.这样做的目的就可以找到所有的变量的definition交汇的结点,其实也就是需要放置的位置。

it-of-ssa

那么如何让插函数变得efficient呢?就需要用到dominator tree和dominance frontier的概念,dominator tree就不用介绍了,主要把dominance frontier的概念弄清楚,这个概念是相对于某个结点来说的,即某个dominator tree上结点的dominance frontier:

如何插入phiDefinition 给定某个结点表示的dominance frontier,若, 则之间存在一条路径,且是这条路径上第一个不支配的结点.

dominance frontier如何插入phi

为什么dominance frontier可以帮助我们解决在哪里插入 如果某个变量在结点下定义,理论上变量可能会被传到所有被如何插入phi它严格支配的结点上,当变量抵达dominance frontier时,就要考虑其他来自其他结点的是否也有关于变量的定义,这是最初的直觉。

那么如何计算呢?

how-to-compute-df

这算法很神奇啊,从每个结点的每个前驱开始在dominator tree上向上回溯,直到碰到停止,中间所有遇到的结点都把扔到它们的里面去。让我想想这背后的直觉到底是什么?

  1. 首先这个算法并不是一开始就对某个点寻找它的df,而是在确定是谁的df? 所以算法一开始从的前驱开始。

  2. 因此考虑每个前驱结点,从在dominator tree向上回溯,得到结点序列都是严格支配,所以这个结点序列任意一个结点的所有路径上都有支配的,接下来只要保证不支配,那么,这也是上述while循环中的条件.

    这里也需要一个小lemma,dominator tree上的路径并不是CFG中的真实路径:

    dominator tree上任意两点,, 如果他们之间有一条路径, 不失一般性假设的level小于的level,那么也可以在CFG上找到一条的路径,且支配这条路径上的所有结点。

    proof: 假设不存在这样的路径,即所有这样的路径,都不完全支配其上的所有点,那么总可以找到一条从start不经过的路径,这和 dom 是矛盾. 所以原命题得证。

还有一个小问题,为什么可以保证一定可以碰到,因为的前驱,有几种情况:

  1. 就是. 这是trivial的
  2. 如果不是,我们需要证明也必须是的dominator,假设不是的dominator,则存在一条经过不经过的路径抵达,产生矛盾了不支配. 所以的一个dominator,所以往上回溯总可以碰到.

0x03 SSA Construction

  1. 变量声明周期的维护,保证runtime阶段所有definition reachable且任一程序点某一时间点只有一个definition起作用.
  2. 每个变量只有一次的赋值机会,即每次assignment的左端的变量名都是独一无二的,保证definition的唯一性.

phi-insertion

这个算法看起来也很简单,先收集所有的变量的defBB, 丢到worklist里面,然后one by one算支配边界,在支配边界上插, 同时这个支配边界也变成了一个变量的defBB,直到worklist空为止.

直觉上是ok的,所有变量的defBB都会被考虑到,所以是不会漏掉,但是可能会造成不是minimal的,因为需要考虑一下是否used情况.

variable-renaming

让我们来推理一下这算法这背后的直觉?

这个过程里面糅杂了reachingDefinition的东西,这玩意儿就是一个definitions cache,也正是我们处理和use-def时候需要的, 大循环按照先序深度遍历dominator tree,内在两个小循环,一个小循环遍历每个instruction,另外一个小循环更新后继的phi的use. 在遍历每一个instruction的时候,我们需要先更新当前instrument的use-var,再考虑是否有def-var的情况. 在更新use-var时候,我们找离这个instrument最近的对应var的definition,注意这是是排除了phi函数的,phi函数的use-var由它的前驱负责更新. 如果有def-var的情况,我们需要考虑给def-var重命名,并且更新原var的definition, 让后面的instruction在更新use-var的时候,使用这个新命名的变量. 最后处理完当前的基本块所有instruction之后,更新后继节点的中phi函数可能用到的use-var.

这个reachingDefinition作用是什么呢? 注意在上述在处理def-var的时候,会把一个变量老的definition和新的definition用一张链表串起来. 那么reachingDefinition的作用就是你想在某个instruction处使用某个变量,它会准确地帮你找到这个变量的定义,如何描述“准确”呢? 就是离这个instruction最近的关于对应变量的definition,“最近”表示某个变量definition所在的基本块是dominate当且使用这个变量的基本,且这个definition所在的instruction离当且instruction在线性距离上最近(closest definition that dominates i). 你也理解为先在当且基本块找definition,找不到再去idom,具体操作见下图. reachingDefinition会帮你管理好这样一条def-chain,其中v.reachingDef就是一个链表元素。

use-def-chain

一些细节问题:

  1. 为什么要深度遍历dominator tree?

    我们目的是给每个assignment的左边重命名,再把assignment右边的变量名再修正. 所谓重命名就是给某一变量在重新被赋值的时候,给变量名加了一个下标,这个东西叫version. 为了控制version我们需要有序东西存在,采用dominator tree先序遍历的原因:

    1. 可以保证在处理每个基本块的Phi的时候,Phi里面的source var已经被重命名了.
    2. 让reachingDef chain works.

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多了一个 ,用于区别路径条件类型的最小正数。当 的时候,必然有