One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All

57 阅读 0 评论 38 点赞

我是靠谱客的博主贤惠小伙，最近开发中收集的这篇文章主要介绍One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

One Fuzzing Strategy to Rule Them All

一、论文阅读

论文出自ICSE（A会）

作者来自南方科技大学

Abstract

以前的工作倾向于采用Havoc作为默认选项，没有探索其性能，本文对Havoc进行实证研究，发现Havoc可以提高边覆盖，而且纯Havoc（应该是指黑盒测试）本身就有很高的边覆盖率，并优于所研究的大多数模糊器。此外，延长Havoc的执行时长可以实现更好的便覆盖，并且不同模糊器之间的覆盖率差距变得很小。文章提出了Havoc_MAB，将Havoc阶段堆叠次数选择以及变异算子选择建模为多臂老虎机模型，动态调整Havoc阶段的选择，进一步提高了边覆盖率。

1. Introduction

通过对一组模糊器应用Havoc广泛研究了性能影响
Havoc可以大大提高边缘覆盖率以及崩溃检测
提出了Havoc_MAB ，相较于Havoc 提升了11.1%
实验地址：https://github.com/MagicHavoc/Havoc-Study
Havoc_MAB地址：https://github.com/Tricker-z/havoc-mab

2. Background

Havoc工作流程如下图：

在这里插入图片描述

对于每一个种子，根据种子的执行速度、覆盖率、队列循环次数以及深度决定变异次数
每次变异都是多个变异算子的叠加，变异算子有15个，叠加次数[2, 128]
如果期间发现了interesting测试用例，则增加变异次数

2.1 Mutators and Mutator Stacking

下图为15种变异算子

在这里插入图片描述

文章将变异算子分为两类：单元变异（红）和块变异（蓝）

在一次变异中，某个变异算子可能被多次选择

2.2 Integration

Havoc集成到模糊器中的方式有两种：顺序方式，如AFL先执行确定性变异（文中称为主要变异策略）再执行Havoc；并行方式，如QSYM启用三个线程分别执行确定性变异、Havoc以及符号执行。

尽管Havoc已被许多模糊器广泛采用，但它只是被用作一种实现选项，而没有一个模糊器明确地探索其潜在功能，例如评估其机制并调整其设置，所以文章对Havoc的机制进行深入研究，以及广泛评估其对模糊器的性能影响。

3. Havoc Impact Study

3.1 Subjects & Benchmarks

Subjects. 选了一些AFL的变体，包括直接应用原始Havoc的模糊器（AFL、AFL++、MOPT、FairFuzz、QSYM）和应用Havoc变体的模糊器（Neuzz、MTFuzz）以及纯Havoc（只用一个种子并且不集成到任何模糊器中，简言之就是黑盒测试）。

Benchmarks. 选了12个程序，不同类型、尺寸范围广、涵盖各种处理功能。

3.2 Evaluation Setups

初始种子集是按照各个论文中的说明构造的。使用afl-showmap统计边覆盖率。

3.3 Research Questions

原始的Havoc在不同的模糊器中的性能表现如何？
在不同的模糊器中，不同的设置下，Havoc的性能表现如何？

3.4 Result Analysis

3.4.1 原始Havoc的影响

执行时间分布如下图：

在这里插入图片描述

Havoc的执行时间相较于确定性变异的执行时间占比很低（QSYM和MOPT除外，QSYM并行，MOPT主要就是变异）。

作者比较了五个带有Havoc的模糊器（AFL、AFL++、FairFuzz、MOPT、QSYM）在原始状态下和删除Havoc后的边覆盖，结果显示，删除Havoc后边覆盖都有明显下降。

作者比较了两个没有Havoc的模糊器（Neuzz、MTFuzz）在原始状态下和集成Havoc后（按照2.2中的顺序方式集成）的边覆盖，结果显示，集成Havoc后边覆盖有明显提升。

结论1：应用Havoc可以提升模糊器的覆盖表现。

结果还显示纯Havoc的边覆盖接近MOPT和QSYM，比其它模糊器高出一大截。

结论2：Havoc本身就是很强大的模糊器。

结果还显示QSYM、MTFuzz以及纯Havoc的覆盖率比其他的模糊器表现好的同时，它们执行Havoc的时间也更长。

结论3：在模糊器上执行较长时间的Havoc可能会有更好的边覆盖表现。

3.4.2 不同设置下Havoc的影响

通过socket实现对Havoc执行时间的控制。原始Havoc不同的是，将动态控制变异次数改为在规定时间内变异。

在主要变异策略和Havoc各执行12小时（单位为1小时，即交叉执行1小时主要变异1小时Havoc共12次），的情况下，边覆盖率和块覆盖率都有显著提升。并且各个模糊器的边覆盖变得很接近，这表明就边覆盖而言，Havoc可能主导许多模糊器。

（这部分的实验结果感觉好诧异，竟然有这种效果，关键是没有理论支持，讲道理黑盒是不会比灰盒覆盖率高这么多，即使变异时间有差异）

结论4：在足够的时间内执行浩劫可以主导所研究的模糊器的性能，并显着减少其性能差距。

又测试了以2、4、12小时为单位时的覆盖率，结果都很接近。

结论5：只要Havoc的总执行时间是固定的，调整单位执行时间对覆盖率影响很小。

虽然集成修改的Havoc能减小覆盖率差距，但是MOPT还是比其它模糊器覆盖率稍好，作者又做了并行实验，即多个线程执行Havoc。

结论6：在执行Havoc上投入更多的计算资源可能会减少其接近性能界限的执行时间，但性价比可能很低。

结论7：将Havoc应用于不同的模糊器可能会探索相同的边，符号执行或神经网络可以很好的补充Havoc。

结论8：Havoc在暴露潜在的程序漏洞方面也起着至关重要的作用。

4. Enhance Havoc

作者研究了变异算子叠加对覆盖性能的影响，并相应的提高其性能

4.1 Performance Imapct of the Matutor Stacking Mechanism

Havoc有两个阶段：确定堆叠次数以及随机选择相应次数的变异算子。作者分别研究了这两步的影响。

对于堆叠次数，作者将随机确定堆叠次数变为固定的堆叠次数（2、4、8、16、32、64、128）结果表明，必须针对不同项目调整堆叠次数，以优化其边覆盖率。

对于变异算子，作者将随机选择变异算子变为随机选择两种突变类型（块变异和单元变异）其中一种，然后从该类型中随机选择变异算子。结果表明，对于不同的项目，调整突变类型的选择以优化边覆盖率也至关重要。

4.2 Approach

将问题建模为多臂老虎机问题，即有限的资源分配（堆叠次数和变异算子选择）获取最大利益（覆盖率）。设计了一个两层的多臂老虎机，堆叠次数层老虎机老虎机（7个臂，即7种次数）和变异算子层老虎机（2个臂，即单元变异和块变异）

采用了UCB1-Tuned 算法来解决提出的多臂老虎机问题

在这里插入图片描述

${x}_j$ 表示到时间 t 时 $arm_j$ 获得的平均奖励， n 表示老虎机的执行次数， $n_j$ 表示 $arm_j$ 的执行次数， $_j$ 表示样本方差。如果生成的测试用例覆盖了新的边，则堆叠次数层和变异算子层都将获得奖励值1，否则为0。

算法流程如下所示：

在这里插入图片描述

4.3 Evaluation

与QSYM比较了边覆盖率，有所提升。

5. Threats to Validity

有效性威胁，即实验结果的可靠性。

内部威胁：研究的模糊器，直接使用各个模糊器的源码。
外部威胁：研究对象和基准，选择都是最先进的模糊器以及经常被其它工作采用的基准。结果的随机性，每个都跑五次。
构建威胁：测量指标，使用AFL的内置工具afl-showmap收集边覆盖。

二、源码分析

需要注意的是：两层老虎机，第一层一个老虎机有七个操作臂（分别对应2、4、8、16、32、64、128七种堆叠次数），第二层有七个老虎机，每个老虎机有两个操作臂（分别对应块变异和单元变异）。在第一层确定堆叠次数后，在第二层对应的老虎机上确定变异算子类型。

1. bandit.h

#include <math.h>
#include <stdlib.h>

#define UCB_PARAM 0.25

#define min(x, y) ((x < y)? x : y)

typedef struct {		// 定义结构体
    int *arms;			// 每个操作臂
    int *reward;		// 每个臂至今的奖励
    int *variance;		// 每个臂的方差
    int *used_times;	// 每个臂被执行次数
    int length;			// 老虎机操作臂的数量
    int total_times;	// 总的被执行次数
    double *ucb_values;	// UCB
} Bandit;

// 初始化老虎机
Bandit* initial_bandit(int length) {	// 根据臂数为各个数组分配空间
    int *current_arms          =  (int *) malloc(sizeof(int) * length);
    int *current_reward        =  (int *) malloc(sizeof(int) * length);
    int *current_variance      =  (int *) malloc(sizeof(int) * length);
    int *current_used_times    =  (int *) malloc(sizeof(int) * length);
    double *current_ucb_values =  (double *) malloc(sizeof(double) * length);

    for (int i = 0; i < length; i ++) {	// 初始化
        current_arms[i]       = i;
        current_reward[i]     = 0;
        current_variance[i]   = 0;
        current_ucb_values[i] = 1000.0;
        current_used_times[i] = 0;
    }

   	// 初始化
    Bandit *bandit   = (Bandit *) malloc(sizeof(Bandit));
    bandit->arms     = current_arms;
    bandit->reward   = current_reward;
    bandit->variance = current_variance;

    bandit->ucb_values  = current_ucb_values;
    bandit->used_times  = current_used_times;
    bandit->length      = length;
    bandit->total_times = 0;

    return bandit;
}


// 选择一个老虎机中UCB最大的操作臂
int select_maximum_arms(Bandit *bandit) {
    double max = -1;
    int max_arms = -1;
    for (int i = 0; i < bandit->length; i ++) {
        if (bandit->ucb_values[i] > max) {
            max = bandit->ucb_values[i];
            max_arms = i;
        }
    }
    return bandit->arms[max_arms];
}


// 求公式中逗号后半部分
double get_variance_ucb(int selected_arms, Bandit *bandit) {

    int arm = bandit->arms[selected_arms];
	
    // 公式中加号右边的部分
    double ucb_component = sqrt((2 * log((double) bandit->total_times)) / bandit->used_times[arm]);
	// 每次选择该臂的平均奖励
    double mean     = (double) bandit->reward[arm] / (bandit->used_times[arm] + 0.0);	// +0.0转为浮点型
    // 公式中加号左半部分
    double variance = (double)bandit->variance[arm] / (bandit->used_times[arm] + 0.0) - mean * mean;

    return variance + ucb_component;
}


// 更新操作臂状态
Bandit *update_arms(int selected_arms, int reward, Bandit *bandit) {
    int arm = bandit->arms[selected_arms];

    bandit->reward[arm]   += reward;	// 更新奖励
    bandit->variance[arm] += reward * reward; 	// 更新求样本方差的变量

    bandit->used_times[arm] ++;	// 更新执行次数
    bandit->total_times ++;
	
    // 公式中min部分 
    double tune_component = min(UCB_PARAM, get_variance_ucb(selected_arms, bandit));
    // 更新UCB
    bandit->ucb_values[arm] =
        sqrt((tune_component * log((double) bandit->total_times)) / bandit->used_times[arm])
        + (double) bandit->reward[arm] / (bandit->used_times[arm] + 0.0); // x
    return bandit;
}

2. havoc stage

// 在块变异中默认去掉了case15、16，即没有token替换和插入了
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    u32 stack_num    = select_maximum_arms(stack_bandit);	// 选择堆叠幂数
    u32 mutator_arm  = select_maximum_arms(mutator_bandit[stack_num]);	// 选择变异算子类型

    u32 use_stacking = 1 << (1 + stack_num);
    stage_cur_val    = use_stacking;
 
    for (i = 0; i < use_stacking; i++) {

      if (!mutator_arm) {
        
        /* Unit mutator */
        
        switch (UR(11)) {

          case 0:
			......
          case 1: 
			......
          case 2:
			......
          case 3:
			......
          case 4:
			......
          case 5:
			......
          case 6:
			......
          case 7:
			......
          case 8:
			......
          case 9:
			......
          case 10:
			......
        }

      } else {
        /* Chunk mutator */
        
        switch(11 + UR(4)) {

          case 11 ... 12:
				......
          case 13:
				......
          case 14: 
				......
          }

      }

    }

    if (common_fuzz_stuff(argv, out_buf, temp_len))
      goto abandon_entry;

    /* out_buf might have been mangled a bit, so let's restore it to its
       original size and shape. */

    if (temp_len < len) out_buf = ck_realloc(out_buf, len);
    temp_len = len;
    memcpy(out_buf, in_buf, len);

    /* If we're finding new stuff, let's run for a bit longer, limits
       permitting. */

    u32 reward = 0;

    if (queued_paths != havoc_queued) {
      /* Insteresting */
      reward = 1;	// 如果有新发现

      if (perf_score <= HAVOC_MAX_MULT * 100) {
        stage_max  *= 2;
        perf_score *= 2;
      }

      havoc_queued = queued_paths;

    }
	
    // 更新两个老虎机的状态
    update_arms(stack_num,  reward, stack_bandit);

    update_arms(mutator_arm,reward, mutator_bandit[stack_num]);

  }

3. log

static int debug_log(char* log_info){
    FILE *fp = fopen(bandit_log_path, "a+");

    fprintf(fp, "[DEBUG]: %sn", log_info);

    fclose(fp);
    return 0;
}

static int bandit_log(Bandit* bandit) {
  sprintf(log_info, "bandit values");

  u32 i;
  for (i =0; i < bandit->length; i++) {
    sprintf(log_info, "%s, %.10f", log_info, bandit->ucb_values[i]);
  }

  debug_log(log_info);
  return 0;
}

最后

以上就是贤惠小伙为你收集整理的One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All的全部内容，希望文章能够帮你解决One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：模糊测试论文阅读
浏览次数：57 次浏览
发布日期：2024-09-18 12:30:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_10_fw_13__7__26_x.html

One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All

概述

One Fuzzing Strategy to Rule Them All

一、论文阅读

Abstract

1. Introduction

2. Background

2.1 Mutators and Mutator Stacking

2.2 Integration

3. Havoc Impact Study

3.1 Subjects & Benchmarks

3.2 Evaluation Setups

3.3 Research Questions

3.4 Result Analysis

3.4.1 原始Havoc的影响

3.4.2 不同设置下Havoc的影响

4. Enhance Havoc

4.1 Performance Imapct of the Matutor Stacking Mechanism

4.2 Approach

4.3 Evaluation

5. Threats to Validity

二、源码分析

1. bandit.h

2. havoc stage

3. log

最后

评论列表共有 0 条评论

发表评论取消回复

One Fuzzing Strategy to Rule Them AllOne Fuzzing Strategy to Rule Them All

概述

One Fuzzing Strategy to Rule Them All

一、论文阅读

Abstract

1. Introduction

2. Background

2.1 Mutators and Mutator Stacking

2.2 Integration

3. Havoc Impact Study

3.1 Subjects & Benchmarks

3.2 Evaluation Setups

3.3 Research Questions

3.4 Result Analysis

3.4.1 原始Havoc的影响

3.4.2 不同设置下Havoc的影响

4. Enhance Havoc

4.1 Performance Imapct of the Matutor Stacking Mechanism

4.2 Approach

4.3 Evaluation

5. Threats to Validity

二、源码分析

1. bandit.h

2. havoc stage

3. log

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复