WebStorm 网络视频直播系统 IntelliJ IDEA教程 nhibernate pagination Material UI Egret Engine 百度seo关键词优化 vuejs视频教程 bootstrap后台管理模板 oracle可视化工具 java上传图片 matlab求向量的模 python中assert python环境搭建 简单python脚本实例 java抽象类 java学习手册 java变量类型 java编译 javastringbuilder java怎么输出数组 javastring比较 linux硬盘 wps2011 java电子书下载 网站数据分析工具 oem修改器 生存猎人属性 pycharm中文版 vscode全局搜索 小程序游戏源码 sendto函数 五子棋大师 k3刷机 桌面系统 华为手机屏保怎么设置 快剪辑怎么录制视频 excel并排查看 yy打不开
当前位置: 首页 > 学习教程  > 编程语言

afl学习(二)变异策略

2020/12/5 10:57:32 文章标签:

根据afl白皮书的说法,afl-fuzz大部分的(尤其是前期的)工作都是高度确定的(highly deterministic),random havoc和test case splicing只在后期的部分进行。 确定性的策略包括: 1.bitflip,位反转 即按位进行翻转,0变1&a…

根据afl白皮书的说法,afl-fuzz大部分的(尤其是前期的)工作都是高度确定的(highly deterministic),random havoc和test case splicing只在后期的部分进行。

确定性的策略包括:
1.bitflip,位反转
即按位进行翻转,0变1,1变0。
根据翻转量/步长,按位翻转的策略有以下几种
bitflip 1/1,每次翻转1个bit,按照每1个bit的步长从头开始
bitflip 2/1,每次翻转相邻的2个bit,按照每1个bit的步长从头开始
bitflip 4/1,每次翻转相邻的4个bit,按照每1个bit的步长从头开始
bitflip 8/8,每次翻转相邻的8个bit,按照每8个bit的步长从头开始,即依次对每个byte做翻转
bitflip 16/8,每次翻转相邻的16个bit,按照每8个bit的步长从头开始,即依次对每个word做翻转
bitflip 32/8,每次翻转相邻的32个bit,按照每8个bit的步长从头开始,即依次对每个dword做翻转
这里有一个afl->stage_max的变量,应该是将要进行多少次变异

以bitflip1/1为例,解释一下大概的逻辑

afl->stage_short = "flip1";  
  afl->stage_max = len << 3; 
  afl->stage_name = "bitflip 1/1";  

  afl->stage_val_type = STAGE_VAL_NONE;

  orig_hit_cnt = afl->queued_paths + afl->unique_crashes;

  prev_cksum = afl->queue_cur->exec_cksum;

  for (afl->stage_cur = 0; afl->stage_cur < afl->stage_max; ++afl->stage_cur) {

    afl->stage_cur_byte = afl->stage_cur >> 3;

    FLIP_BIT(out_buf, afl->stage_cur);

    if (common_fuzz_stuff(afl, out_buf, len)) { goto abandon_entry; }

    FLIP_BIT(out_buf, afl->stage_cur);

这里的变量afl->stage_max = len << 3,即文件长度*8,那么可以推断出这个stage_max就是可以用来变异的次数。
看到下面的for循环,从0遍历到stage_max,每个比特都调用FLIP_BIT函数,FLIP_BIT函数作用就是翻转指定位置的一个比特。

#define FLIP_BIT(_ar, _b)                   \
  do {                                      \
                                            \
    u8 *_arf = (u8 *)(_ar);                 \
    u32 _bf = (_b);                         \
    _arf[(_bf) >> 3] ^= (128 >> ((_bf)&7)); \
                                            \
  } while (0)

之后进行判断if (common_fuzz_stuff(afl, out_buf, len)) { goto abandon_entry; }common_fuzz_stuff函数返回1就说明是时候bail out了,所以直接进入退出程序。如果返回0,、那么之后进行恢复操作,再进行一次FLIP_BIT将之前翻转的比特再翻转回来,然后进入下一个位置的比特翻转。

在bitflip1/1中还有一部分是实现寻找token

自动检测token
在进行bitflip 1/1变异时,对于每个byte的最低位(least significant bit)翻转还进行了额外的处理:如果连续多个bytes的最低位被翻转后,程序的执行路径都未变化,而且与原始执行路径不一致(检测程序执行路径的方式可见上篇文章中“分支信息的分析”一节),那么就把这一段连续的bytes判断是一条token。这里用路径的hash来判断是否改变。
例如,PNG文件中用IHDR作为起始块的标识,那么就会存在类似于以下的内容
…IHDR…
在执行 bitflip 1/1 时,如果连续翻转多个字节后的用例,都能让程序走到新的代码路径,那么就称连续翻转的字节是一个 token。
当翻转到字符I的最高位时,因为IHDR被破坏,此时程序的执行路径肯定与处理正常文件的路径是不同的;随后,在翻转接下来3个字符的最高位时,IHDR标识同样被破坏,程序应该会采取同样的执行路径。由此,AFL就判断得到一个可能的token:IHDR,并将其记录下来为后面的变异提供备选。
AFL采取的这种方式是非常巧妙的:就本质而言,这实际上是对每个byte进行修改并检查执行路径;但集成到bitflip后,就不需要再浪费额外的执行资源了。此外,为了控制这样自动生成的token的大小和数量,AFL还在config.h中通过宏定义了限制.

#define MIN_AUTO_EXTRA 3  
#define MAX_AUTO_EXTRA 32

对于一些文件来说,如果我们已知其格式中出现的token长度不会超过4,那么我们就可以修改MAX_AUTO_EXTRA为4并重新编译AFL,以排除一些明显不会是token的情况。遗憾的是,这些设置是通过宏定义来实现,所以不能做到运行时指定,每次修改后必须重新编译AFL。
这里有个maybe_add_auto函数,该函数会将传入的token添加到数组中,如果数组还有空间则添加进来。
没有的话那就在数组的下半部分随机删除一个token,然后将新的添加进来。

bitflip2/1,4/1与1/1大同小异,只是在一次循环中调用2次或4次FLIP_BIT而已

FLIP_BIT(out_buf, afl->stage_cur);
    FLIP_BIT(out_buf, afl->stage_cur + 1);

    if (common_fuzz_stuff(afl, out_buf, len)) { goto abandon_entry; }

    FLIP_BIT(out_buf, afl->stage_cur);
    FLIP_BIT(out_buf, afl->stage_cur + 1);

在bitflip8/8时,代码里多了一个数据结构eff_mapeff_map的类型是u8(这是一个uint8_t = unsigned char 形,8比特(0~255)),并且u8类型只有这一个是map命名形式的,在后面的注释中如果出现Effector map,说的就是这个变量。主要的作用就是标记,用来标记每一个字节的变异是否有效,有效记为1,无效为0,为后面的变异节省时间。在初始化数组的地方有这么一段注释Initialize effector map for the next step (see comments below). Always flag first and last byte as doing something.把第一个和最后一个字节单独标记出来用作其他用途,这里其实就说明了,这个map是标记作用,那是标记什么呢,标记当前byte对应的map块是否需要进行阶段变异。如果是0意味着不需要变异,1就需要变异。
它的初始化代码如下

#define EFF_APOS(_p) ((_p) >> EFF_MAP_SCALE2) 
#define EFF_REM(_x) ((_x) & ((1 << EFF_MAP_SCALE2) - 1)) 
#define EFF_ALEN(_l) (EFF_APOS(_l) + !!EFF_REM(_l)) 
#define EFF_SPAN_ALEN(_p, _l) (EFF_APOS((_p) + (_l)-1) - EFF_APOS(_p) + 1)
eff_map = afl_realloc(AFL_BUF_PARAM(eff), EFF_ALEN(len));

这里解释一下这几行代码
EFF_MAP_SCALE2在config.h中定义为3,这里就是对传入的参数p右移3位并返回。
EFF_REM(_x)求的是 _x 与 ((1 << EFF_MAP_SCALE2) - 1)进行按位与,实际上就是跟 7 以二进制形式按位与,即返回 (_x & 7)
EFF_ALEN(_l):这里的 !! 是一个两次否,目的是归一化。举个例子,如果 r = !!a,如果a是整数0,则r=0,如果a是整数非0,则r=1。这里如果l不为0,那么返回EFF_APOS(_l) + 1
EFF_SPAN_ALEN(_p, _l)就是返回(EFF_APOS((_p) + (_l) - 1) - EFF_APOS(_p) + 1)
最后为eff_map分配大小为EFF_ALEN(len)的内存,len来自于队列当前结点queue_cur的成员len,len = afl->queue_cur->len,是input length(输入长度),所以这里分配给eff_map的大小是EFF_APOS(_l) + !!EFF_REM(_l),即 (文件大小/8) 向下取整再+1(文件大小不为0)。例如文件长度为17字节,那么此时EFF_ALEN(_l) = (EFF_APOS(_l) + !!EFF_REM(_l) = 17/8 + 1 = 3。

eff_map数组元素只有 0/1 两种值,很明显是标记的意思,到底是标记什么呢?
要想明白 effector map 的原理需要了解三个点:

1.为什么是 8/8 的时候出现?个人理解:因为这里设置 eff_map 是为了之后的启发式判断,而后面的文件数据变异都是 8/8 起步的,所以这里在 8/8 处进行判断。因为 8bit(比特)的时候是 1byte(字节),如果一个字节的翻转都无法带来路径变化,此byte极有可能是不会导致crash的数据,所以之后应该用一种思路避开无效byte。
2.标记是干什么用的?根据上面的分析,就很好理解了,标记好的数组可以为之后的变异服务,相当于提前“踩雷(踩掉无效byte的雷)”,相当于进行了启发式的判断。无效为0,有效为1。
3.达到了怎样的效果?要知道判断的时间开销,对不停循环的fuzzing过程来说是致命的,所以 eff_map 利用在这一次8/8的判断中,通过不大的空间开销,换取了可观的时间开销。(暂时是这样分析的,具体是否真的节约很多,不得而知)

bitflip8/8还是同样的使用这个for循环for (afl->stage_cur = 0; afl->stage_cur < afl->stage_max; ++afl->stage_cur),不同的是,这里的afl->stage_max = len,即这里遍历的单位是每个字节,对每个在eff_map数组中标记为0的字节进行操作,并对没用的字节标记为1。

这里有个比较有意思的操作,如果百分之90以上的字节都是有效的,那么afl会认为所有字符都是有效的,直接全部标记为1。因为既然百分之就是以上的都是有效的,那么跳过其余的也节省不了多少时间,干脆全部变成有效的。

if (eff_cnt != (u32)EFF_ALEN(len) &&
      eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) { //如果百分之九十以上都是,全部标记为1

    memset(eff_map, 1, EFF_ALEN(len));

    afl->blocks_eff_select += EFF_ALEN(len);

  } 

2.arithmetic,进行加减操作
bitflip 结束之后,就进入 arithmetic 阶段,目标大小和阶段与 bitflip 非常类似:

arith 8/8,每次8bit进行加减运算,8bit步长从头开始,即对每个byte进行整数加减变异;
arith 16/8,每次16bit进行加减运算,8bit步长从头开始,即对每个word进行整数加减变异;
arith 32/8,每次32bit进行加减运算,8bit步长从头开始,即对每个dword进行整数加减变异;

其中对于加减变异的上限,在 config.h 中有所定义:
#define ARITH_MAX 35
如果需要修改此值,在头文件中修改完之后,要进行编译才会生效。

这里以 arithmetic 的8/8变异这一段为例(16和32的变异大同小异),把重要部分做解释

 afl->stage_name = "arith 8/8";//状态名
  afl->stage_short = "arith8"; 
  afl->stage_cur = 0;
  afl->stage_max = 2 * len * ARITH_MAX;
  afl->stage_val_type = STAGE_VAL_LE;

  orig_hit_cnt = new_hit_cnt;

  for (i = 0; i < (u32)len; ++i) {

    u8 orig = out_buf[i];//out_buf = afl_realloc(AFL_BUF_PARAM(out), len); 应该是取出第i个字节

    /* Let's consult the effector map... */

    if (!eff_map[EFF_APOS(i)]) { 
      afl->stage_max -= 2 * ARITH_MAX;  
      continue;

    }

    afl->stage_cur_byte = i;  //当前byte

    for (j = 1; j <= ARITH_MAX; ++j) { //分别进行 +/- 操作 j = 1~35

      u8 r = orig ^ (orig + j);

      /* Do arithmetic operations only if the result couldn't be a product of a bitflip. */
      //只有当arithmetic变异跟bitflip变异不重合时才会进行
      if (!could_be_bitflip(r)) {

        afl->stage_cur_val = j;
        out_buf[i] = orig + j;

        if (common_fuzz_stuff(afl, out_buf, len)) { goto abandon_entry; }
        ++afl->stage_cur;

      } else {

        --afl->stage_max; //如果没有进行变异,stage_max减一,因为这里属于无效操作

      }

      r = orig ^ (orig - j);

      if (!could_be_bitflip(r)) {

        afl->stage_cur_val = -j;
        out_buf[i] = orig - j;

        if (common_fuzz_stuff(afl, out_buf, len)) { goto abandon_entry; }
        ++afl->stage_cur;

      } else {

        --afl->stage_max;

      }

      out_buf[i] = orig; //复原

    }

  }

  new_hit_cnt = afl->queued_paths + afl->unique_crashes;//如果8/8期间有新crash的话会加到这里

  afl->stage_finds[STAGE_ARITH8] += new_hit_cnt - orig_hit_cnt;//这期间增加了的
  afl->stage_cycles[STAGE_ARITH8] += afl->stage_max;//如果之前没有有效变异的话stage_max这里就已经变成0了

config.h中定义 #define ARITH_MAX 35 ARITH_MAX就是加减变异的最大值限制35。那么这里的stage_max = 2 * len * ARITH_MAX,即对每个字节的加减操作:文件大小len bytes,然后进行 +/- 操作乘以2,每个byte要进行的 +/- 操作各35次,所以这个stage_max意思就是将要进行多少次变异,但是之后要是没有进行有效变异就要给减去,即如果当前第i个字节在eff_map对应位置是0,那么就跳过此次循环,进入for循环的下一次,并且此字节对应的变异无效,所以要减 2*ARITH_MAX

```c
 if (!eff_map[EFF_APOS(i)]) { 
   afl->stage_max -= 2 * ARITH_MAX;  
      continue;
 }

在这里对整数目标进行+1,+2,+3…+35,-1,-2,-3…-35的变异。由于整数存在大端序和小端序两种表示,AFL会对这两种表示方式都进行变异。
前面也提到过AFL设计的巧妙之处,AFL尽力不浪费每一个变异,也会尽力让变异不冗余,从而达到快速高效的目标。AFL会跳过某些arithmetic变异:

1.即前面提到的effector map:如果一个整数的所有bytes都被判断为“无效”,那么就跳过对整数的变异。
2.之前bitflip已经生成过的变异:如果加/减某个数后,其效果与之前的某种bitflip相同,那么这次变异肯定在上一个阶段已经执行过了,此次便不会再执行。这里的判断用的就是could_be_bitflip函数。

这里解释一下could_be_bitflip函数,该函数的作用是判断是否进行了bitflip变异。

could_be_bitfilp

static u8 could_be_bitflip(u32 xor_val) { 

  u32 sh = 0;

  if (!xor_val) { return 1; }

  /* Shift left until first bit set. 应该为右移?*/

  while (!(xor_val & 1)) {

    ++sh;
    xor_val >>= 1;

  }

  /* 1-, 2-, and 4-bit patterns are OK anywhere. */

  if (xor_val == 1 || xor_val == 3 || xor_val == 15) { return 1; }

  /* 8-, 16-, and 32-bit patterns are OK only if shift factor is
     divisible by 8, since that's the stepover for these ops. */

  if (sh & 7) { return 0; }

  if (xor_val == 0xff || xor_val == 0xffff || xor_val == 0xffffffff) {

    return 1;

  }

  return 0;

}

xor_val为旧的值和新的值的异或
首先,若是xor_val为0,说明旧的值和新的值是相同的,那么执行将会浪费时间,所以返回1。
之后进行一个while循环,若xor_val末位是0则进行右移操作,并记录下右移次数,直到末位为1为止。此时,进行判断if (xor_val == 1 || xor_val == 3 || xor_val == 15),即判断后4位是否为0001,0011,1111,对应的就是是否进行了1位,2位,4位的比特反转。以0011为例,异或值为0011,则说明旧的值和新的值在目前的最后两位是不同的,那么正是因为在这两位进行了bitflip,才会出现这样的结果,所以返回1。
之后进行判断if (sh & 7) { return 0; },将sh与7,当sh后四位为1000时,sh&7为0,此时sh为8的倍数,所以之后进行判断if (xor_val == 0xff || xor_val == 0xffff || xor_val == 0xffffffff) {return 1; },即判断是否进行了8位,16位,32位的bitflip。如果sh&7结果不为0,则说明没有进行bitflip操作,返回0。

类似的,还有could_be_arith函数和could_be_interest函数。

could_be_artih

static u8 could_be_arith(u32 old_val, u32 new_val, u8 blen) {  

  u32 i, ov = 0, nv = 0, diffs = 0;

  if (old_val == new_val) { return 1; }

  /* See if one-byte adjustments to any byte could produce this result. */

  for (i = 0; i < blen; ++i) { //每次将旧的值和新的值右移一个字节,看调整后的数据是否相同

    u8 a = old_val >> (8 * i), b = new_val >> (8 * i);

    if (a != b) {

      ++diffs; //diffs必定>=1
      ov = a;
      nv = b;

    }
    
  }

  /* If only one byte differs and the values are within range, return 1. 
  可能进行过bitflip?
  */
  
  //只有一次diffs即未进行移位操作时的different,此时判断二者之差是否在范围内即可
  if (diffs == 1) {
    if ((u8)(ov - nv) <= ARITH_MAX || (u8)(nv - ov) <= ARITH_MAX) { return 1; }

  }
 
  //文件长度为一个字节并且新旧值之差大于arith的范围,则可以判定未进行过arithmetic变异
  if (blen == 1) { return 0; } 
  
  /* See if two-byte adjustments to any byte would produce this result. */

  diffs = 0;

  //每次将旧的值和新的值右移两个字节,看调整后的数据是否相同
  for (i = 0; i < blen / 2; ++i) {
    
    u16 a = old_val >> (16 * i), b = new_val >> (16 * i);
    
    if (a != b) {

      ++diffs;
      ov = a;
      nv = b;

    }

  }

  /* If only one word differs and the values are within range, return 1. */
  
  if (diffs == 1) { //同上

    if ((u16)(ov - nv) <= ARITH_MAX || (u16)(nv - ov) <= ARITH_MAX) {

      return 1;

    }

    ov = SWAP16(ov); //SWAP16交换前后八位
    nv = SWAP16(nv);
    
    //有可能在前八位进行了arithmetic变异,交换之后判断是否在范围内
    if ((u16)(ov - nv) <= ARITH_MAX || (u16)(nv - ov) <= ARITH_MAX) {

      return 1;

    }

  }

我们从头到尾捋一遍,该函数有三个参数old_val, new_val,顾名思义就是旧的值和新的值,还有一个参数blen应该就是以字节为单位的文件长度。

一开始判断新旧值是否相同,相同就返回1。

之后使用一个循环对每一个字节进行调整(因为arith只有三种情况8/8,16/8和32/8),看是否在该字节发生了arith变异,每次右移八位,第一次 i=0 不进行右移,此时必然有一次diffs,所以diffs必定是大于等于1的。如果之后右移全部相同,那么进入下一个if判断。

if (diffs == 1) {
    if ((u8)(ov - nv) <= ARITH_MAX || (u8)(nv - ov) <= ARITH_MAX) { return 1; }
  }

ARITH_MAX是已经定义好的加减操作的上限。这里就是判断新旧值的绝对值之差是否在这个范围内,如果是就证明可能进行过arith变异。

之后重置diffs,进行两个字节的判断,依旧是通过循环每次右移16位,当diffs=1时进行绝对值之差的判断,这里跟之前都一样。不同之处在于16位的时候多了一个SWAP16的操作:

#define SWAP16(_x)                    \
  ({                                  \
                                      \
    u16 _ret = (_x);                  \
    (u16)((_ret << 8) | (_ret >> 8)); \
                                      \
  })

作用就是将u16的数据前八位和后八位进行交换。即进行了大小端交换。
交换后再次进行范围判断,这里的目的就是看arith变异是否变异在前8位而不是后8位,因为arith的步长为8。

之后32位时使用SWAP32交换大小端,之后的判断与上面类似,就不再赘述。

could_be_interest

could_be_interest函数判断方式与could_be_arith大同小异,就不再详细解释,这里只说说一些区别。

could_be_interest函数有四个参数,比could_be_arith多了一个参数check_le,目的是判断是否是小端方式,因为interest变异支持大端和小端操作。

之后的判断使用两层for循环分别遍历interesting_8,interesting_16,interesting_32中的每个元素对每个字节的插入情况。
3.interest,把一些“有意思”的特殊内容替换到原文件中。
interest的三个步骤跟arithmetic相同:
interest 8/8,每次8bit进行加减运算,8bit步长从头开始,即对每个byte进行替换;
interest 16/8,每次16bit进行加减运算,8bit步长从头开始,即对每个word进行替换;
interest 32/8,每次32bit进行加减运算,8bit步长从头开始,即对每个dword进行替换;

用于替换的叫做 interesting values ,是AFL预设的特殊数,在config.h中定义

static s8  interesting_8[]  = { INTERESTING_8 };
static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };
static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };
#define INTERESTING_8                                    \
  -128,    /* Overflow signed 8-bit when decremented  边界溢出条件*/ \
      -1,  /*                                         */ \
      0,   /*                                         */ \
      1,   /*                                         */ \
      16,  /* One-off with common buffer size         */ \
      32,  /* One-off with common buffer size         */ \
      64,  /* One-off with common buffer size         */ \
      100, /* One-off with common buffer size         */ \
      127                        /* Overflow signed 8-bit when incremented  */
      
#define INTERESTING_16                                    \
  -32768,   /* Overflow signed 16-bit when decremented */ \
      -129, /* Overflow signed 8-bit                   */ \
      128,  /* Overflow signed 8-bit                   */ \
      255,  /* Overflow unsig 8-bit when incremented   */ \
      256,  /* Overflow unsig 8-bit                    */ \
      512,  /* One-off with common buffer size         */ \
      1000, /* One-off with common buffer size         */ \
      1024, /* One-off with common buffer size         */ \
      4096, /* One-off with common buffer size         */ \
      32767                      /* Overflow signed 16-bit when incremented */
      
#define INTERESTING_32                                          \
  -2147483648LL,  /* Overflow signed 32-bit when decremented */ \
      -100663046, /* Large negative number (endian-agnostic) */ \
      -32769,     /* Overflow signed 16-bit                  */ \
      32768,      /* Overflow signed 16-bit                  */ \
      65535,      /* Overflow unsig 16-bit when incremented  */ \
      65536,      /* Overflow unsig 16 bit                   */ \
      100663045,  /* Large positive number (endian-agnostic) */ \
      2147483647                 /* Overflow signed 32-bit when incremented */

可以看到,用于替换的基本都是可能会造成溢出的数。

与之前类似,effector map仍然会用于判断是否需要变异;此外,如果某个interesting value,是可以通过bitflip或者arithmetic变异达到,那么这样的重复性变异也是会跳过的。

4.dictionary
用户提供的字典里有token,用来替换要进行变异的文件内容,如果用户没提供就使用 bitflip 自动生成的 token。
此时已是deterministic fuzzing 的结尾,有以下几个阶段:
1.user extras (over),从头开始,将用户提供的tokens依次替换到原文件中
2.user extras (insert),从头开始,将用户提供的tokens依次插入到原文件中
3.auto extras (over),从头开始,将自动检测的tokens依次替换到原文件中
其中,用户提供的tokens,是在词典文件中设置并通过-x选项指定的,如果没有则跳过相应的子阶段

 afl->stage_max = afl->extras_cnt * len; 

afl->extras_cnt为tokens的总数

1.user extras (over)

对于用户提供的tokens,AFL先按照长度从小到大进行排序。这样做的好处是,只要按照顺序使用排序后的tokens,那么后面的token不会比之前的短,从而每次覆盖替换后不需要再恢复到原状。
随后,AFL会检查tokens的数量,如果数量大于预设的MAX_DET_EXTRAS(默认值为200),那么对每个token会根据概率来决定是否进行替换:

//检查tokens的数量,如果数量大于预设的MAX_DET_EXTRAS(默认值为200),那么对每个token会根据概率来决定是否进行替换

```c
  if ((afl->extras_cnt > afl->max_det_extras &&   //afl->max_det_extras = MAX_DET_EXTRAS (默认值为200)
       rand_below(afl, afl->extras_cnt) >= afl->max_det_extras) ||  //rand_below 函数生成一个0到afl->extras_cnt - 1 之间的随机数
      afl->extras[j].len > len - i ||
      !memcmp(afl->extras[j].data, out_buf + i, afl->extras[j].len) ||
      !memchr(eff_map + EFF_APOS(i), 1,
              EFF_SPAN_ALEN(i, afl->extras[j].len))) {

    --afl->stage_max;
    continue;

  }

这里的 rand_below(afl, afl->extras_cnt)是运行时生成的一个0到afl->extras_cnt - 1之间的随机数。所以,如果用户词典中一共有400个tokens,那么每个token就有200/400=50%的概率执行替换变异。我们可以修改MAX_DET_EXTRAS的大小来调整这一概率。
由上述代码也可以看到,effector map在这里同样被使用了:如果要替换的目标bytes全部是“无效”的,那么就跳过这一段,对下一段目标执行替换。

2.user extras (insert)
user extras (insert)是对用户提供的tokens执行插入变异,与user extras (over)不同,由于原文件并未发生替换,effector map在这里不再被使用了。并且此时并没有对tokens数量的限制,所以全部tokens都会从原文件的第1个byte开始,依次向后插入。这一子阶段最特别的地方,就是变异不能简单地恢复。之前每次变异完,在变异位置处简单取逆即可,例如bitflip后,再进行一次同样的bitflip就恢复为原文件。正因为如此,之前的变异总体运算量并不大。

3.auto extras (over)

这一项与”user extras (over)”很类似,区别在于,这里的tokens是最开始bitflip阶段自动生成的。另外,自动生成的tokens总量会由USE_AUTO_EXTRAS限制(默认为128)。

之后就是非确定性变异

5.havoc
havoc,是对原文件的“大破坏”。具体来说,havoc包含了对原文件的多轮变异,每一轮都是将多种方式组合(stacked)而成。
havoc注释说明拼接文件时也会调用havoc阶段突变代码。

switch ((r = rand_below(afl, r_max)))

上文提到过rand_below函数生成0-r_max - 1之间的一个随机数,r_max的初始化代码如下

if (unlikely(afl->expand_havoc)) {

    /* add expensive havoc cases here, they are activated after a full
       cycle without finds happened */

    r_max = 16 + ((afl->extras_cnt + afl->a_extras_cnt) ? 2 : 0);

  } else {

    r_max = 15 + ((afl->extras_cnt + afl->a_extras_cnt) ? 2 : 0);

  }

havoc的方式有以下十几种:

随机选取某个bit进行翻转
随机选取某个byte,将其设置为随机的interesting value
随机选取某个word,并随机选取大、小端序,将其设置为随机的interesting value
随机选取某个dword,并随机选取大、小端序,将其设置为随机的interesting value
随机选取某个byte,对其减去一个随机数
随机选取某个byte,对其加上一个随机数
随机选取某个word,并随机选取大、小端序,对其减去一个随机数
随机选取某个word,并随机选取大、小端序,对其加上一个随机数
随机选取某个dword,并随机选取大、小端序,对其减去一个随机数
随机选取某个dword,并随机选取大、小端序,对其加上一个随机数
随机选取某个byte,将其设置为随机数
随机删除一段bytes
随机选取一个位置,插入一段随机长度的内容,其中75%的概率是插入原文中随机位置的内容,25%的概率是插入一段随机选取的数
随机选取一个位置,替换为一段随机长度的内容,其中75%的概率是替换成原文中随机位置的内容,25%的概率是替换成一段随机选取的数
随机选取一个位置,用随机选取的token(用户提供的或自动生成的)替换
随机选取一个位置,用随机选取的token(用户提供的或自动生成的)插入
之后,AFL会生成一个随机数,作为变异组合的数量,并根据这个数量,每次从上面那些方式中随机选取一个,依次作用到文件上。

6.splice
顾名思义,splice是将两个seed文件拼接得到新的文件,并对这个新文件继续执行havoc变异。

具体地,AFL在seed文件队列中随机选取一个,与当前的seed文件做对比。
if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) { goto retry_splicing; }如果两者差别不大,就再重新随机选一个;如果两者相差比较明显,那么就随机选取一个位置,split_at = f_diff + rand_below(afl, l_diff - f_diff);将两者都分割为头部和尾部。最后,将当前文件的头部与随机文件的尾部拼接起来,就得到了新的文件。在这里,AFL还会过滤掉拼接文件未发生变化的情况。

上面的变异完成后,AFL会对文件队列的下一个进行变异处理。当队列中的全部文件都变异测试后,就完成了一个”cycle”,这个就是AFL状态栏右上角的”cycles done”。而正如cycle的意思所说,整个队列又会从第一个文件开始,再次进行变异,不过与第一次变异不同的是,这一次就不需要再进行deterministic fuzzing了。

当然,如果用户不停止AFL,那么seed文件将会一遍遍的变异下去。
这里我就有一个疑惑,为什么不是当前的尾拼接随机文件的头?


本文链接: http://www.dtmao.cc/news_show_450353.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?