afl-fuzz.c:fuzz_one 函数中,havoc 变异之前加入了 tree stage,它的核心代码为:

afl-fuzz.c:fuzz_one
tree_stage:
 
... ...
// Read the additional testcase into a new buffer.
fd = open(target->fname, O_RDONLY);
... ...
new_buf = ck_alloc_nozero(target->len);
ck_read(fd, new_buf, target->len, target->fname);
close(fd);
stage_max=parse(in_buf,len,new_buf,target->len);
ck_free(new_buf);
 
orig_hit_cnt =  queued_paths + unique_crashes;
 
for(stage_cur=0;stage_cur<stage_max;stage_cur++){
   char* retbuf=NULL;
   size_t retlen=0;
   fuzz(stage_cur,&retbuf,&retlen);
   ...
   common_fuzz_stuff(argv, retbuf, retlen);
   ...
}
 
new_hit_cnt = queued_paths + unique_crashes;
 
stage_finds[STAGE_TREE]  += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_TREE] += stage_max;

在 tree mutate 阶段,fuzzer 会从种子队列中选择一个种子,然后调用 parse 函数做变异,这次变异会生成若干个输入,之后通过 fuzz 函数去选择指定 stage_cur 的输入,最后对目标进行测试。

接下来重点看 parse 逻辑。

在 superion 中,不同的语法有着不同的 parse 实现,不过它们的参数类似。parse 函数的定义为:

int parse(char* target,size_t len,char* second,size_t lenS)

parse 函数的核心逻辑为:

...
// first string
tree::ParseTree *tree = parser.program();
visitor->visit(tree);
int interval_size = visitor->intervals.size();
for (int i = 0; i < interval_size; i++)
{
    ...
    intervals.push_back(visitor->intervals[i]);
}
int texts_size = visitor->texts.size();
for (int i = 0; i < texts_size; i++)
{
    ...
    texts.push_back(visitor->texts[i]);
    ...
}
// second string
tree::ParseTree *treeS = parserS.program();
visitorS->visit(treeS);
texts_size = visitorS->texts.size();
for (int i = 0; i < texts_size; i++)
{
    ...
    texts.push_back(visitorS->texts[i]);
    ...
}
// mutate
interval_size = intervals.size();
sort(texts.begin(), texts.end());
texts_size = texts.size();
 
for (int i = 0; i < interval_size; i++)
{
    for (int j = 0; j < texts_size; j++)
    {
        rewriter.replace(intervals[i].a, intervals[i].b, texts[j]);
        ret[num_of_smaples++] = rewriter.getText();
        if (num_of_smaples >= MAXSAMPLES)
            break;
    }
    if (num_of_smaples >= MAXSAMPLES)
        break;
}
  • 解析第一个字符串 target
  • 从解析树中提取代码片段,加入 intervals 数组和 text 数组;
  • 解析第二个字符串 second
  • 从解析树中提取代码片段,加入 text 数组;
  • intervals 数组中的区域用 text 数组中的片段替换,并加入 ret 数组中。

在模糊测试的过程中 fuzz 函数会遍历这个 ret 数组,获得本次的输入信息。

参考资料