# Matryoshka:Fuzzing Deeply Nested Branches **URL:** \ **Category:** 学术研究\ **Created:** [2020 年10 月 4 日 13:21 UTC](https://forum.90sec.com/t/topic/1323 "2020-10-04T13:21:05Z")\ **Posts on this page:** 1\ **Page:** 1
作者： ![maplgebra](https://forum.90sec.com/user_avatar/forum.90sec.com/maplgebra/32/1628_2.png) [@maplgebra](https://forum.90sec.com/u/maplgebra)\ 发布日期： [2020 年10 月 4 日 13:21 UTC](https://forum.90sec.com/t/topic/1323/1 "2020-10-04T13:21:05Z")
# Matryoshka:Fuzzing Deeply Nested Branches ### 0x00 Questions 这篇文章意在解决“嵌套”的条件结构（注意这里的嵌套并不是狭义上控制结构嵌套），这是一个比较难处理的问题，在找到一个能触发新分支 b 的输入 i ，接下来的策略肯定就是在这个输入 i 上，去构造新的输入 i' 来触发更多的新的分支，但是这里面有一 个问题，假设新分支 b 内有一个子分支条件是 s ,这个分支条件位置为 P (reachable by i ),那么分支 b 的子分支就可以抽象为 \{s\} \cap P ,构造出来的输入 i' ,极有可能 P 点并不是_reachable_，因为可能 P 点之前的某个分支条件满足性，在输入 i 和 i' 上并不相同: ![matryoshka](https://forum.90sec.com/uploads/default/original/2X/c/cf02522b494eda569687485546cf9fafd1c491a2.png) 这里通过一个代码片段，来特别地说明几种特殊的情况： ![image-20201003200124109](https://forum.90sec.com/uploads/default/original/2X/2/260b361c83c6903a5c9639d000aa312ca4ba9285.png) **控制流依赖** ，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_ 的概念，对一个指定的路径条件 s ,它的_prior conditional statements_是可能导致 s 变成unreachable的一组路径条件。 这个定义在实现过程中还是比较抽象，需要具体的研究一下它的性质，首先考虑它并不是一个等价关系（不满足对称性），那么它是一个偏序吗？自反性很显然，传递性也很显然，反对称性呢？考虑两个不相同的路径条件是否相互为_prior conditional statement_ ,这个不要去想的太复杂，在这篇文章描述的依赖关系下，是不可能做到，因为执行流，两个statements，肯定有一个是先执行的。 抛开反对称性不说，重点关注它的传递性，这里_prior conditional statement_ 关系我用 \preccurlyeq 表示。传递性可以描述为 \text{if}\ a \preccurlyeq b, b \preccurlyeq c ,\text{then}\ a \preccurlyeq c 为了找到指定路径条件 s 所有的_prior conditional statements_，可以使用这个性质，但是还需要定义一个_immediate prior conditional statement_,如果 r 是 s 的一个_immediate prior conditional statement_,则在 r 和 s 之前找不到第二个_prior conditional statement_,这个“之前”是指所有执行到 s 到路径，往后看 r 都是最后一个路径条件。可以简单的理解为 r 离 s 最近。这个定义对研究路径的同学来说，是非常熟悉的，就是_dominator tree_的定义，仿照它的定义，是可以给出计算_prior conditional statements_的算法的。 Prior(s) = IPrior(b) \cup IPrior(IPrior(b))\cdots 其中_IPrior_表示_immediate prior conditional statement_ 通常来说_dominator tree_只定义在过程内，文中又进一步改进，引入了过程间的_prior conditional statement 关系_，这个也很好理解，如果一个路径条件 s 在过程内没有_prior conditional statement_,那就去找调用个过程的_call_的_prior conditional statement_，这里会产生一个疑惑不是描述路径条件之前的关系吗？怎么又突然来了一个_call_，按照定义描述的是“可能导致这个_call_ 变成_unreachable_的路径条件”，其实是合理的。 我以为文中技术实现是完全建立在静态分析上，但是直到读到这里，_trace_和_stack_的出现，告诉我极有可能是在动态过程中做的，而且文中给的找_immediate prior conditional statement_的算法是可以在动态做的。 _Intraprocedural immediate prior conditional statement_：（ r of s ） - r 和 _s_在同一个函数内 - s 不是 r 的 _post-dominator_ (_post-dominator_ ：如果 r 到_exit -point_的所有路径都经过 s ) _Interprocedural immediate prior conditional statement_（ r of s ） - r 和 s 不在同一个函数内 - 当 s 执行的时候， f\_r 的返回地址在当前的栈中。 - r\_c 是 f\_r 执行过的最后一个调用， r\_c 不是 r 的_post-dominators_ 文中还提到的路径分支包含_terminator_的情况，其实这种属于上面第一种情况了，因为第二个条件已经限定了。但是作者在这里还是特别的拿出来说了一下，我还是在这个放个小例子： ```c if(x==1){ exit(); } if(y==2){//target //... } ``` **1.2 分支条件的数据流依赖** 用 b(s) 表示流到分支条件 s 上的_input bytes_集合， s 表示一个或者多个分支条件。当_input_在 s 处可达，为了进入 s 代表的分支，需要进一步修改_input_, 在修改之后， Prior(s) 里面路径条件选择不变的情况下， s 还是_reachable_，从直觉上来说，为了尽可能小的影响 Prior(s) 里面的路径条件，需要尽可能的避免修改 b(Prior(s)) 的_input bytes_,但是这样做有可能带来负反馈，例如F2中 b(Prior(s\_{l6}))=\{x,y,z\} ,这将直接导致根本无法进入L6所代表的分支。 这种情况下只考虑了分支条件的控制流依赖，并没有考虑路径条件之前的数据流依赖，这里文中又定义了第二种关系_effective prior conditional statements_ ,我们需要稍微去改变一下上面我们的直觉，先忽略考虑_reachable_，我们需要改变 s 里面涉及到的_input bytes_ ，改变这些_input bytes_ 意味着 Prior(s) 里面和它相关的路径条件的选择可能就会发生变化，我们需要尽可能保证他们的选择，所以应该去重点修改 b(s)\setminus b(EPrior(s)) ,很显然在这里 EPrior(s) \subset Prior(s) 。这个直觉要比第一次的直觉要好那么一点点，但是也有问题，例如F2中 b(s\_{l6})=\{y\} , b(EPrior(s\_{l2}))=\{x,y\} ,所以 b(s\_{l6}) \setminus b(EPrior(s\_{l6}))=\emptyset . 这个直觉在Matryoshka中是第一个求解约束的策略_Prioritize reachability_ **1.3 求解约束** 前面已经提到求解约束的一个策略，在这里需要综合考量_reachable_ 和 _satisfy constraints_ ，文中在这里提出了三种可选的策略，顺序执行： 1. _Prioritize reachability_ 2. _Prioritize satisfia_bility 3. _Joint optimization for both reachability and satisfiability_ 1.3.1 _Prioritize satisfia_bility 这个策略非常有意思，修改 input 之后可能导致 s 变成_unreachable_,但是强制使 EPrior(s) 里面的路径条件选择不变（运行时），这个过程叫_forward_, 当在某次修改_input_之后，满足了条件$s$,结果有两种：(1 如果 EPrior(s) 中的路径条件选择并没有发生变化，代表 forward 成功了 （2 如果 EPrior(s) 中的路径条件选择发生了变化，则需要修补发生改变的路径条件，进入_backtrack_过程。 _bracktrace_过程从 s 向后按顺序fuzz EPrior(s) 里面的每个路径条件 r ,这个过程中需要避免修改流入$s$ 或者在 r 后面的_effective prior conditional statements_的_input bytes_,_bracktrace_成功的标志是处理完所有\*EPrior(s)\*的路径条件。 还是用F2中的例子来说明问题：假设当前的输入为 x=1,y=1,z=1111 , L2,L3是L6的_effective prior conditional statements_，L2和L3下进入都是_true_分支，目标是进入L6的_true_分支，在修改 s 关联的_input bytes_过程中，强制使L2和L3也保持true分支,假设 y=2 ,满足了 s 但是L3选择是_false_，所以进入_bracktrace_过程，继续slove L3，这个时候需要避免动 y 的值，当 x=0 的时候，就找到一组满足L6的_input bytes_.但是这里如果在一个_forward_过程中选择了_y=3_,就直接导致后面的_bracktrace_失败了。 1.3.3 _Joint optimization for both reachability and satisfiability_ 总结一下，_Prioritize reachability_旨在修改那些不会影响_EPrior(s)的input bytes_，保证 s 是_reachable_，_Prioritize satisfia_bility使用_forward-backtrace_方法，尽可能的满足 s .但是它们都可能在尝试优化多个路径条件的时候失败。这里文中通过对Angora的梯度下降算法再改造： - f\_i(x)\leq 0,\forall i \in [1,n] 表示 EPrior(s) 中每一个路径条件的黑盒抽象函数，同样使用和Angora一样的转换表： - g(x) = \sum\_{i=0}^{n}R(f\_i(x))\ ,R(x) \equiv 0 \vee x 其中 R(x) 相当于一个_max_函数， \vee 二元运算符表示取最大的那个操作数，并用 f\_0(x) 表示 s 的抽象运算。观察这里转换表比Angora多了一个 \epsilon ,用于区别路径条件类型的最小正数。当 g(x)=0 的时候，必然有 \forall i\in[1,n],f\_i(x)=0 , 在这里把 g(x)=0 作为预期最优解。（我觉得应该是 g(x)\le 0 ,如何保证每个 f\_i(x)=0 这个事实？）。需要注意的是它这里要比Angora做的更好，因为Angora在计算偏导数的时候，并不能保证 s 是_reachable_，这样得到的结果没有意义，Angora面对这个问题，只是简单提到了通过改变单位分向量的值。这里Matryoshka可以强制保证_previous_分支选择，来保证计算过程。 同样这样也用F2中的例子来说明问题，让 [x,y]=[1,3] 为初始 input ： g([x,y]) = R(x-2+\epsilon) +R(x+y-3+\epsilon) + R(1-y+\epsilon) 通过梯度下降，最终会得到一个_solution_ 为 g([0,2])=0 **1.4 隐式条件路径** 直接用例子来说明问题： ![image-20201004184742827](https://forum.90sec.com/uploads/default/original/2X/5/5f16846c91e9d678defe7873a319a78343d7f469.png) L6计算显式的 EPrior(s\_{l6})=\emptyset ,很显然L3应该是属于 EPrior(s\_{l6}) 的，但是现有的方法是无法把它区分出来的，针对这种类似隐式的污点传递，通常的做法是如果路径条件被污染，则把该分支下的所有赋值操作都视为污点传递。这种方法文中提到，可能会导致_over taint_ 和 _taint explosion_ 。（但是我认为这样做理论上并没有问题，例如L4中_n_也被_tainted_,作者认为是_useless_，就算它是_useless_也不会影响其他的东西，考虑到因为这些污点导致更深的传递过程，也是合乎情理的，这属于一种_indirect tainted_,我猜测处理它的难点在于与之关联的_input bytes_不好做对应，这个过程需要手工的添加一些额外的_taint rule_） 作者并不想按照通常的手法来操作，而是通过相关的策略把隐式污点过程筛出来：假设当前的 input 对 s 是_reachable_的，但是经过_mutate_以后变成_unreachable_了。再额外运行两次，第一次记录_original input_过程中经过的路径条件，第二次记录_mutated input_过程中经历的路径，但是这个过程强制进入_original input_的路径选择，使其变成_reachable_,这两次得到的路径条件序列应该是相同的，按时间倒序检查它们的路径条件序列。 如果存在一个 r \notin EPrior(s) ,并且 r 前后两次路径选择并不一样，则有可能存在与 s 的隐式路径依赖，需要进一步做验证，再跑一次_mutated input_，并且强制针对下面的路径条件和_original input_做到统一： - 所有在_r_之前的条件路径 - 所有显式的_effective prior conditional statements_ - 所有已知的隐式的_effective prior conditional statements_ 如果结果_s_是_unreachable_则 r 确定是存在的隐式路径依赖，我举个小例子，帮助理解和回忆： ```c 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 input_是_unreachable_.两次的路径序列： - L4:true;L8:true;L12:true - L4:false;L8:false;L12:false 逆序比较: - L12不属于 EPrior(s) ，按照验证算法，这里是L13是_unreachable_的，所以L12属于隐式的_effective prior conditional statement_ - L8不属于 EPrior(s) ，按照验证算法，这里L13还是_reachable_的，所以L8不属于隐式的_effective prior conditional statement_ - L3不属于 EPrior(s) ，按照验证算法，这里是L13是_reachable_的，所以L3不属于隐式的_effective prior conditional statement_ 奇怪得到的结果却是L3不属于隐式的_effective prior conditional statement_,原文中的逆序比较似乎不合理？这个演算结果我没有想到。 ### 0x01 Self Conclusion 在看Angora我就有一个疑问，关于梯度下降算法，因为无法保证目标路径分支是_reachable_的，所以计算梯度得到的结果是毫无意义的，在这篇文章里面给了我想要的答案，作者似乎修补了这个很重要的问题，用_force_的方法，保证两次走过的路径条件一样。疑问又来了，这样做的理论依据在哪呢？