efuzz论文笔记

efuzz论文阅读(能量调度部分)

引子：王志等分析僵尸网络控制命令时，提出了BBL覆盖率的概念，用来描述一个BBL被执行路径覆盖的频繁程度。

BBL覆盖率————描述一个BBL被执行路径覆盖的频繁程度

论文《基于覆盖率分析的僵尸网络控制命令发掘方法》部分内容阅读笔记。

基本块的覆盖率与覆盖次数

  • 定义：基本块被执行轨迹的覆盖

如果在程序执行的过程中，某些基本块被执行，则称这些被执行的基本块被执行轨迹覆盖。

  • 基本块被执行轨迹覆盖的信息内容

基本块被执行轨迹覆盖的信息包括两部分：覆盖率和覆盖次数。

  • 覆盖率Pbb

Pbb描述的是一个基本块被执行轨迹覆盖的频繁程度，定义如下：

Pbb = Ncover/Nall

Nall是当前已捕获的执行轨迹总数，Ncover是覆盖该基本块的执行轨迹数量。

  • 覆盖次数VBB

覆盖次数VBB描述的是基本块在不同执行轨迹中被执行的频繁程度，是一个向量：

VBB = (VT1</sub>,VT2</sub>,……,VTn</sub>)

VT1</sub>，VT2</sub>，……，VTn</sub>表示基本块BB在执行轨迹T1，T2，……，Tn中被覆盖的次数。

能量调度算法

受上述思想的启发，文章使用边的热度来描述一条边被所有路径覆盖的次数，并提出了一个新的能量调度算法，如下：

边的热度即边被执行路径覆盖的次数，这里的实现方法：

1
2
3
for (u32 i = 0; i < MAP_SIZE; ++i) {
    g_cov_count[i] += trace_bits[i] ? 1 : 0;
}

g_cov_count[i]保存的内容即分支路线i被覆盖的次数，也就是边i的热度。

边的评分与该边的热度成反比，即该边被覆盖的次数越多，评分越低。每个seed对应一条执行路径，一条执行路径有多条边组成。路径评分为该路径中边的评分之和，p(q)为路径q（种子q）的评分，定义为：

然后就可以根据边的热度（其实就是边被执行路径覆盖的次数）来计算出每个轨迹需要被测试的次数，来达到给低频边更多测试的机会，文章给了一个简单的归一化算法，可以通过调整系数来得到更好的效果：

使用了三个预定的系数¯p_max、¯p_avg、¯p_min来控制测试样例的的测试频次，p_min，p_max，p_avg分别为队列中的对应最低评分，最高评分以及平均评分的值。

具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
if (0.0 != queue_cur->case_score && g_max_score!= g_min_score) {
    if (queue_cur->case_score >= g_max_score)
        p = MAX_P;
    else if (queue_cur->case_score <= g_min_score )
        p = MIN_P;
    else if (queue_cur->cal_failed >= g_avg_score)
        p = AVG_P + (MAX_P - AVG_P) * (queue_cur->case_score - g_avg_score) / (g_max_score - g_avg_score);
    else
        p = MIN_P + (AVG_P - MIN_P) * (queue_cur->cal_failed - g_min_score) / (g_avg_score - g_min_score);
}

stage_max *= p;

想法

论文方案每次得到某个轨迹的测试次数时，都会算均值，会导致内耗较高，因此除了该方案，可以仅通过边热度来得到测试频次：

具体实现：

1
2
3
4
if(calc_score_flag == 0)
    p = ceil(queue_cur->case_score);

stage_max *= p;

实际测试后，fuzzer的分支覆盖情况达到最高值相比原来速度也是更快的。