标题: [AFL]测试用例洗牌是什么

分类: Fuzzing
创建: 2022-10-31 07:12
修改: 
链接: http://0x2531.tech/fuzzing/202210310712.txt

--------------------------------------------------------------------------------

通过设置运行时环境变量 AFL_SHUFFLE_QUEUE，在将测试用例添加到输入队列时（函数 
read_testcases），可以改变测试用例在输入队列中的顺序，这就是测试用例洗牌

if (getenv("AFL_SHUFFLE_QUEUE")) shuffle_queue    = 1;

默认情况下，测试用例在输入队列中的顺序是按照文件名以字母顺序排列的，如输入目录中有 foo.png、
bar.png 和 baz.png 三个测试用例，则它们在输入队列中的顺序将是 bar.png、baz.png 和 foo.
png，也就是说 bar.png 最先被传递给目标程序。

nl_cnt = scandir(in_dir, &nl, NULL, alphasort);

这在多数情况下没有问题。考虑如下两种情形：

- 测试用例数量较多且大小较大，这种情况下，可能跑很长时间第一轮确定性变异策略都还没跑完。如果这
  时停止 fuzzing，那么靠后的测试用例将没有被测试到
- 使用公共的语料库，这些语料库靠前的测试用例被测试过无数次，靠后的测试用例被测试的次数相对较
  少。如果我们有更大的概率使用到这些靠后的测试用例，发现漏洞的概率也会更高

基于以上两种情形，所以我们需要对测试用例洗牌。

if (shuffle_queue && nl_cnt > 1) {

    ACTF("Shuffling queue...");
    shuffle_ptrs((void**)nl, nl_cnt);

}

当然，如果只有一个测试用例文件，就没有洗牌的必要了。

/* Shuffle an array of pointers. Might be slightly biased. */

static void shuffle_ptrs(void** ptrs, u32 cnt) {

  u32 i;

  for (i = 0; i < cnt - 2; i++) {

    u32 j = i + UR(cnt - i);
    void *s = ptrs[i];
    ptrs[i] = ptrs[j];
    ptrs[j] = s;

  }

}

UR(cnt - i) 将返回一个 [0, cnt-i-1]间的随机数，所以 j = [i, cnt-1]间的随机数。洗牌逻辑非
常简单，就是循环的将下标 j 存储的测试用例和下标 i 存储的测试用例互换位置。

如：当有5个测试用例时，即：cnt=5
当i=0时，j=[0,4]，即第1个测试用例随机的和其余5个测试用例（包括自己）互换位置
当i=1时，j=[1,4]，即第2个测试用例随机的和其余4个测试用例互换位置
当i=2时，j=[2,4]，即第3个测试用例随机的和其余3个测试用例互换位置

这里有1个小 bug，倒数第2个测试用例不参与洗牌。比如上面的例子，第4个测试用例则不再洗牌。再比如
如果只有2个测试用例，虽然满足洗牌的条件，但也不会洗牌。但这个基本没啥影响，你可以理解为倒数第2
个测试用例和自己互换位置了。

另外，如果设置了洗牌的环境变量，当某个测试用例没有产生新的执行路径时，不会产生 "No new 
instrumentation output, test case may be useless." 的告警信息。

以上，则是测试用例洗牌的全部内容。