Introduction

Effector Map是AFL中使用的一个机制，用来加速fuzzing跳过一些没必要的比特位

从头开始讲，fuzzing的一个特点就是快，这个快需要测试目标target执行的快来支撑。但是对于AFL来说它不能直接地加快target的执行速度(forkserver一定程度上可以加快一点点)，但是可以变相的少执行一定次数从宏观上让整个过程看起来快一点，那么怎么科学的选择减少执行次数就要很讲究，不然会出现漏报，这就很影响fuzzing的效率。

That said, there is one (trivial) exception to this rule: when a new queue entry goes through the initial set of deterministic fuzzing steps, and tweaks to some regions in the file are observed to have no effect on the checksum of the execution path, they may be excluded from the remaining phases of deterministic fuzzing - and the fuzzer may proceed straight to random tweaks.

from: https://lcamtuf.coredump.cx/afl/technical_details.txt

一个例外：当一个新的queue entry通过最初的几个deterministic步骤之后，观察到输入文件的某些区域对执行路径的checksum没有影响，那么fuzzing就会跳过deterministic fuzzing的余下阶段，并直接开始随机的调整(havoc,splicing)

AFL中的具体实现

eff_map对bitmap 1/1 2/1 4/1是不起作用的，对eff_map的初始化在bitflip8/8之前，且只对后续的deterministic stage起效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define EFF_MAP_SCALE2 3
...
#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    = ck_alloc(EFF_ALEN(len));
eff_map[0] = 1;

if (EFF_APOS(len - 1) != 0) {
    eff_map[EFF_APOS(len - 1)] = 1;
    eff_cnt++;
}

eff_map大小大致为为testcase的1/8，如果换算的时候没有对齐的话会多一字节。

但是对应关系并不是eff_map中一个比特位，对应testcase中的一个字节，而是eff_map的一个字节对应testcase中的8个字节。

初始化时，除了eff_map的首尾置1，其余部分均置0。

eff_map仅在bitflip 8/8中被更新，在后续阶段中仅作为跳过该阶段的依据

bitflip 8/8:

1
2
3
4
5
6
7
8
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
if (!eff_map[EFF_APOS(stage_cur)]) {
    ...
        if (cksum != queue_cur->exec_cksum) {//如果前后两次的checksum发生了变化,那么执行路径发生了变化
            eff_map[EFF_APOS(stage_cur)] = 1;//将该字节在effector_map中置1,表示该字节"有效",即会影响执行路径
            eff_cnt++;//eff_cnt会计数有效字节数
        }
}

后续阶段:

1
2
3
4
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {
    stage_max--;
    continue;
}

就是这么简单粗暴

那么，什么情况下，eff_map会被更新？AFL会对执行后的checksum进行计算，与当前testcase保存的checksum不同时就认为发现了新的执行路径，那就更新eff_map:

1
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

所以checksum其实就是直接关联上了trace_bits这个位图

1
EXP_ST u8* trace_bits;                /* SHM with instrumentation bitmap  */

trace_bits那就是用来记录执行路径信息的

run_target()中，当程序被执行后，以下代码将被执行:

1
classify_counts((u32*)trace_bits);
1
2
3
4
5
6
7
8
9
10
11
12
static inline void classify_counts(u32* mem) {
  u32 i = MAP_SIZE >> 2;
  while (i--) {
    /* Optimize for sparse bitmaps. */
    if (unlikely(*mem)) {
      u16* mem16 = (u16*)mem;
      mem16[0] = count_class_lookup16[mem16[0]];
      mem16[1] = count_class_lookup16[mem16[1]];
    }
    mem++;
  }
}

目的就是，在trace_bits上规整每个元素的值，trace_bits记录的是每个执行路径的执行次数，所谓的规整就是将一定范围内的执行次数统一成某一个值，AFL认为这个范围内的执行次数表示发生了相同的执行情况情况

1
2
3
4
5
6
7
8
9
10
11
12
13
static const u8 count_class_lookup8[256] = {

  [0]           = 0,
  [1]           = 1,
  [2]           = 2,
  [3]           = 4,
  [4 ... 7]     = 8,
  [8 ... 15]    = 16,
  [16 ... 31]   = 32,
  [32 ... 127]  = 64,
  [128 ... 255] = 128

};

在save_if_interesting()中，trace_bits会被简化，其中保存的执行次数信息会被简化成是否执行

1
simplify_trace((u32*)trace_bits);

所以传回到fuzz_one中决定是否更新eff_map的就是这个简化之后的我trace_bits，仅保留了是否探索了新的路径。对其作hash，然后决定是否需要更新eff_map.

后记

暂时先写这么多，其实并没有找到trace_bits是在哪里更新的，可能是在插桩代码中就进行了具体的更新。

话说回来，为什么我要写这个呢，因为我在做毕设，内容大概是python-afl+AFL对AI进行fuzzing。这是一个很玄学的场景，因为这个场景下，首先coverage就没用了，只能记录python上的表面的代码，具体的model中的内容是探索不到的，我fuzz的也不是crash，而是预测错误这一事件，所以我新定义了一个内容错误的fault与crash并列。然后，作为对照的AFL，我对它的预计是eff_map是不会更新的，因为没有覆盖率的更新啊，所以AFL在执行了bitflip8/8之后，后续的位理应被跳过才对，但是实际上它执行了， 这就有点超出我的预期了，所以我就回头又来分析AFL源码了。

然后我发现我之前对eff_map的理解出现了错误，它不是1位对应1字节，而是1字节对应8字节，但是这个不能说是功能上的认知错误，这个错误不是我遇到的问题的原因。后续原因有待继续挖掘，这篇博客先写到这边了。

References

https://lcamtuf.coredump.cx/afl/technical_details.txt