honggfuzz-v2.X版本变异策略及const_feedback特性分析

前言

honggfuzz在4月21日fuzzbench的性能测试[1]中一骑绝尘，战胜老对手AFL、libfuzzer摘得桂冠。前段时间，google Project Zero 安全研究员也是通过对honggfuzz进行二次开发成功发现苹果闭源图片处理库的多个漏洞[2]。honggfuzz的2.X版本中引入的 const_feedback （使用被 fuzz 程序中的常量整数/字符串值通过动态字典处理输入文件）显著减少运行过程中指令迭代次数[3]，提高了漏洞挖掘效率。

honggfuzz以前也有很多前辈对其进行过分析[5] [6]，但大多数还是2.X版本之前的，本篇文章重点介绍新版本中const_feedback和新变异策略的相关实现。

本次使用的honggfuzz版本为2.2（74e7bc161662269b6ff4cdb3e2fdd2ad0bebd69b）。此版本已经默认打开const_feedback功能。

trace-cmp

使用 hfuzz-clang 编译目标文件代码时，-fsanitize-coverage = trace-pc-guard，indirect-calls，trace-cmp 标志集将自动添加到 clang 的命令行中。新版本中引入了与 trace-cmp 相关的新变异策略，本次重点对其介绍。其余参数之前有文章分析过不再赘述[6]

包含此标志时，编译器在比较指令和switch指令之前插入如下代码：

/* Standard __sanitizer_cov_trace_cmp wrappers */
void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2) 
void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2)
void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2) 
void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2)

/* Standard __sanitizer_cov_trace_const_cmp wrappers */
void __sanitizer_cov_trace_const_cmp1(uint8_t Arg1, uint8_t Arg2)
void __sanitizer_cov_trace_const_cmp2(uint16_t Arg1, uint16_t Arg2) 
void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2) 
void __sanitizer_cov_trace_const_cmp8(uint64_t Arg1, uint64_t Arg2)

之后会调用instrumentAddConstMem()或 instrumentAddConstMemInternal()函数将比较的常量值存入globalCmpFeedback中：

static inline void instrumentAddConstMemInternal(const void* mem, size_t len) {
    if (len == 0) {
        return;
    }
    if (len > sizeof(globalCmpFeedback->valArr[0].val)) {
        len = sizeof(globalCmpFeedback->valArr[0].val);
    }
    uint32_t curroff = ATOMIC_GET(globalCmpFeedback->cnt);
    if (curroff >= ARRAYSIZE(globalCmpFeedback->valArr)) {
        return;
    }

    for (uint32_t i = 0; i < curroff; i++) {//若该常量已存在在列表中，跳过
        if ((len == ATOMIC_GET(globalCmpFeedback->valArr[i].len)) &&
            libc_memcmp(globalCmpFeedback->valArr[i].val, mem, len) == 0) {
            return;
        }
    }

    uint32_t newoff = ATOMIC_POST_INC(globalCmpFeedback->cnt);
    if (newoff >= ARRAYSIZE(globalCmpFeedback->valArr)) {
        ATOMIC_SET(globalCmpFeedback->cnt, ARRAYSIZE(globalCmpFeedback->valArr));
        return;
    }

    memcpy(globalCmpFeedback->valArr[newoff].val, mem, len);
    ATOMIC_SET(globalCmpFeedback->valArr[newoff].len, len);
    wmb();
}

globalCmpFeedback结构体定义如下：

typedef struct {
    uint32_t cnt;//存储常量值个数
    struct {
        uint8_t  val[32];//常量值
        uint32_t len; //常量值长度
    } valArr[1024 * 16];
} cmpfeedback_t;

最后调用 hfuzz_trace_cmpx_internal若输入与待验证比较后相同的位数增加则更新 bitmap。

HF_REQUIRE_SSE42_POPCNT static inline void hfuzz_trace_cmp1_internal(
    uintptr_t pc, uint8_t Arg1, uint8_t Arg2) {
    uintptr_t        pos  = pc % _HF_PERF_BITMAP_SIZE_16M;
    register uint8_t v    = ((sizeof(Arg1) * 8) - __builtin_popcount(Arg1 ^ Arg2));
    uint8_t          prev = ATOMIC_GET(globalCovFeedback->bbMapCmp[pos]);
    if (prev < v) {
        ATOMIC_SET(globalCovFeedback->bbMapCmp[pos], v);
        ATOMIC_POST_ADD(globalCovFeedback->pidNewCmp[my_thread_no], v - prev);
        wmb();
    }
}

变异策略

整体来讲，除了个别新策略如mangle_ConstFeedbackDict、mangle_StaticDict外，还对一些原有策略进行划分，封装。

fuzz策略的实现主要集中在mangle.c中，在循环的fuzzloop函数中，会根据用户的选择的 fuzz 方式来调用 input_prepareDynamicInput 或者input_prepareStaticFile，但最后都是调用mangle_mangleContent来变异文件数据。

mangle_mangleContent函数部分实现如下：

//mangle.c#L840
    if (run->mutationsPerRun == 0U) {//设置变异率为0，仅作打开处理，通常用于验证崩溃
        return;
    }
    if (run->dynfile->size == 0U) { //对空文件赋予随机size
        mangle_Resize(run, /* printable= */ run->global->cfg.only_printable);
    }

    uint64_t changesCnt = run->global->mutate.mutationsPerRun;

    //根据speed_factor大小设置changesCnt值，该值为之后变异的轮数
    if (speed_factor < 5) {
        changesCnt = util_rndGet(1, run->global->mutate.mutationsPerRun);
    } else if (speed_factor < 10) {
        changesCnt = run->global->mutate.mutationsPerRun;
    } else {
        changesCnt = HF_MIN(speed_factor, 12);
        changesCnt = HF_MAX(changesCnt, run->global->mutate.mutationsPerRun);
    }

    //如果最后一次获取覆盖率时间超过5秒，则提高拼接变异的使用概率
    if ((time(NULL) - ATOMIC_GET(run->global->timing.lastCovUpdate)) > 5) {
        if (util_rnd64() % 2) {
            mangle_Splice(run, run->global->cfg.only_printable);
        }
    }

    //随机选择变异函数对输入文件内容进行变异
    for (uint64_t x = 0; x < changesCnt; x++) {
        uint64_t choice = util_rndGet(0, ARRAYSIZE(mangleFuncs) - 1);
        mangleFuncs[choice](run, /* printable= */ run->global->cfg.only_printable);
    }

变异函数列表如下：

这里添加多个 mangle_Shrink 的原因是为了减少其他操作中插入或扩展文件带来的文件大小增大。

//mangle.c#L812
static void (*const mangleFuncs[])(run_t * run, bool printable) = {
        /* Every *Insert or Expand expands file, so add more Shrink's */
        mangle_Shrink,
        mangle_Shrink,
        mangle_Shrink,
        mangle_Shrink,
        mangle_Expand,
        mangle_Bit,
        mangle_IncByte,
        mangle_DecByte,
        mangle_NegByte,
        mangle_AddSub,
        mangle_MemSet,
        mangle_MemSwap,
        mangle_MemCopy,
        mangle_Bytes,
        mangle_ASCIINum,
        mangle_ASCIINumChange,
        mangle_ByteRepeatOverwrite,
        mangle_ByteRepeatInsert,
        mangle_Magic,
        mangle_StaticDict,
        mangle_ConstFeedbackDict,
        mangle_RandomOverwrite,
        mangle_RandomInsert,
        mangle_Splice,
    };

mangle_Shrink

删除随机长度的文件内容。

static void mangle_Shrink(run_t* run, bool printable HF_ATTR_UNUSED) {
    if (run->dynfile->size <= 2U) {
        return;
    }

    size_t off_start = mangle_getOffSet(run);
    size_t len       = mangle_LenLeft(run, off_start);
    if (len == 0) {
        return;
    }
    if (util_rnd64() % 16) {
        len = mangle_getLen(HF_MIN(16, len));
    } else {
        len = mangle_getLen(len);
    }
    size_t off_end     = off_start + len;
    size_t len_to_move = run->dynfile->size - off_end;

    mangle_Move(run, off_end, off_start, len_to_move);
    input_setSize(run, run->dynfile->size - len);
}

mangle_Expand

文件末尾扩展随机长度的空间，用空格填充，然后在随机位置，取前面的随机长度作数据拷贝。

static void mangle_Expand(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    size_t len;
    if (util_rnd64() % 16) {
        len = mangle_getLen(HF_MIN(16, run->global->mutate.maxInputSz - off));
    } else {
        len = mangle_getLen(run->global->mutate.maxInputSz - off);
    }

    mangle_Inflate(run, off, len, printable);
}

static inline size_t mangle_Inflate(run_t* run, size_t off, size_t len, bool printable) {
    if (run->dynfile->size >= run->global->mutate.maxInputSz) {
        return 0;
    }
    if (len > (run->global->mutate.maxInputSz - run->dynfile->size)) {
        len = run->global->mutate.maxInputSz - run->dynfile->size;
    }

    input_setSize(run, run->dynfile->size + len);
    mangle_Move(run, off, off + len, run->dynfile->size);
    if (printable) {
        memset(&run->dynfile->data[off], ' ', len);
    }

    return len;
}

mangle_Bit

取随机位置的数值做位翻转。

static void mangle_Bit(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    run->dynfile->data[off] ^= (uint8_t)(1U << util_rndGet(0, 7));
    if (printable) {
        util_turnToPrintable(&(run->dynfile->data[off]), 1);
    }
}

mangle_IncByte/DecByte/NegByte

随机位置的数据加1/减1/取反。

static void mangle_IncByte(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    if (printable) {
        run->dynfile->data[off] = (run->dynfile->data[off] - 32 + 1) % 95 + 32;
    } else {
        run->dynfile->data[off] += (uint8_t)1UL;
    }
}
static void mangle_DecByte(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    if (printable) {
        run->dynfile->data[off] = (run->dynfile->data[off] - 32 + 94) % 95 + 32;
    } else {
        run->dynfile->data[off] -= (uint8_t)1UL;
    }
}
static void mangle_NegByte(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    if (printable) {
        run->dynfile->data[off] = 94 - (run->dynfile->data[off] - 32) + 32;
    } else {
        run->dynfile->data[off] = ~(run->dynfile->data[off]);
    }
}

mangle_AddSub

取随机位置的1、2、4或8字节的数据长度作加减操作，新版本中对操作数范围进行划分，缩小了选择的范围。

static void mangle_AddSub(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);

    /* 1,2,4,8 */
    size_t varLen = 1U << util_rndGet(0, 3);
    if ((run->dynfile->size - off) < varLen) {
        varLen = 1;
    }

    uint64_t range;
    switch (varLen) {
        case 1:
            range = 16;//1<<4
            break;
        case 2:
            range = 4096;//1<<12
            break;
        case 4:
            range = 1048576;//1<<20
            break;
        case 8:
            range = 268435456;//1<<28
            break;
        default:
            LOG_F("Invalid operand size: %zu", varLen);
    }

    mangle_AddSubWithRange(run, off, varLen, range, printable);
}

static inline void mangle_AddSubWithRange(
    run_t* run, size_t off, size_t varLen, uint64_t range, bool printable) {
    int64_t delta = (int64_t)util_rndGet(0, range * 2) - (int64_t)range;

    switch (varLen) {
        case 1: {
            run->dynfile->data[off] += delta;
            break;
        }
        case 2: {
            int16_t val;
            memcpy(&val, &run->dynfile->data[off], sizeof(val));
            if (util_rnd64() & 0x1) {
                val += delta;
            } else {
                /* Foreign endianess */
                val = __builtin_bswap16(val);
                val += delta;
                val = __builtin_bswap16(val);
            }
            mangle_Overwrite(run, off, (uint8_t*)&val, varLen, printable);
            break;
        }
        case 4: {
            int32_t val;
            memcpy(&val, &run->dynfile->data[off], sizeof(val));
            if (util_rnd64() & 0x1) {
                val += delta;
            } else {
                /* Foreign endianess */
                val = __builtin_bswap32(val);
                val += delta;
                val = __builtin_bswap32(val);
            }
            mangle_Overwrite(run, off, (uint8_t*)&val, varLen, printable);
            break;
        }
        case 8: {
            int64_t val;
            memcpy(&val, &run->dynfile->data[off], sizeof(val));
            if (util_rnd64() & 0x1) {
                val += delta;
            } else {
                /* Foreign endianess */
                val = __builtin_bswap64(val);
                val += delta;
                val = __builtin_bswap64(val);
            }
            mangle_Overwrite(run, off, (uint8_t*)&val, varLen, printable);
            break;
        }
        default: {
            LOG_F("Unknown variable length size: %zu", varLen);
        }
    }
}

mangle_MemSet

取随机位置、随机大小，若为可打印字符用随机生成的可打印字符填充，否则用UINT8_MAX 填充。

static void mangle_MemSet(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    size_t len = mangle_getLen(run->dynfile->size - off);
    int    val = printable ? (int)util_rndPrintable() : (int)util_rndGet(0, UINT8_MAX);

    memset(&run->dynfile->data[off], val, len);
}

mangle_MemSwap

新策略，从文件随机两处取随机大小按这两块长度的最小值进行交换。

static void mangle_MemSwap(run_t* run, bool printable HF_ATTR_UNUSED) {
    size_t off1    = mangle_getOffSet(run);
    size_t maxlen1 = run->dynfile->size - off1;

    size_t off2    = mangle_getOffSet(run);
    size_t maxlen2 = run->dynfile->size - off2;

    size_t   len    = mangle_getLen(HF_MIN(maxlen1, maxlen2));
    uint8_t* tmpbuf = (uint8_t*)util_Malloc(len);
    defer {
        free(tmpbuf);
    };

    memcpy(tmpbuf, &run->dynfile->data[off1], len);
    memmove(&run->dynfile->data[off1], &run->dynfile->data[off2], len);
    memcpy(&run->dynfile->data[off2], tmpbuf, len);
}

mangle_MemCopy

新策略，随机位置取随机大小内容插入/覆盖随机位置。

static void mangle_MemCopy(run_t* run, bool printable HF_ATTR_UNUSED) {
    size_t off = mangle_getOffSet(run);
    size_t len = mangle_getLen(run->dynfile->size - off);

    /* Use a temp buf, as Insert/Inflate can change source bytes */
    uint8_t* tmpbuf = (uint8_t*)util_Malloc(len);
    defer {
        free(tmpbuf);
    };
    memcpy(tmpbuf, &run->dynfile->data[off], len);

    mangle_UseValue(run, tmpbuf, len, printable);
}

static inline void mangle_UseValue(run_t* run, const uint8_t* val, size_t len, bool printable) {
    if (util_rnd64() % 2) {
        mangle_Insert(run, mangle_getOffSetPlus1(run), val, len, printable);
    } else {
        mangle_Overwrite(run, mangle_getOffSet(run), val, len, printable);
    }
}

mangle_Bytes

随机位置插入/覆盖1~2字节数据。

static void mangle_Bytes(run_t* run, bool printable) {
    uint16_t buf;
    if (printable) {
        util_rndBufPrintable((uint8_t*)&buf, sizeof(buf));
    } else {
        buf = util_rnd64();
    }

    /* Overwrite with random 1-2-byte values */
    size_t toCopy = util_rndGet(1, 2);
    mangle_UseValue(run, (const uint8_t*)&buf, toCopy, printable);
}

mangle_ASCIINum

随机位置插入/覆盖 2~8 字节数据。

static void mangle_ASCIINum(run_t* run, bool printable) {
    size_t len = util_rndGet(2, 8);

    char buf[20];
    snprintf(buf, sizeof(buf), "%-19" PRId64, (int64_t)util_rnd64());

    mangle_UseValue(run, (const uint8_t*)buf, len, printable);
}

mangle_ASCIINumChange

新策略，从随机位置起寻找数字，若未找到则执行mangle_Bytes操作，找到则随机对该数字进行加/减/乘/除/取反/替换随机数字。

static void mangle_ASCIINumChange(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);

    /* Find a digit */
    for (; off < run->dynfile->size; off++) {
        if (isdigit(run->dynfile->data[off])) {
            break;
        }
    }
    if (off == run->dynfile->size) {
        mangle_Bytes(run, printable);
        return;
    }

    size_t len        = HF_MIN(20, run->dynfile->size - off);
    char   numbuf[21] = {};
    strncpy(numbuf, (const char*)&run->dynfile->data[off], len);
    uint64_t val = (uint64_t)strtoull(numbuf, NULL, 10);

    switch (util_rndGet(0, 5)) {
        case 0:
            val += util_rndGet(1, 256);
            break;
        case 1:
            val -= util_rndGet(1, 256);
            break;
        case 2:
            val *= util_rndGet(1, 256);
            break;
        case 3:
            val /= util_rndGet(1, 256);
            break;
        case 4:
            val = ~(val);
            break;
        case 5:
            val = util_rnd64();
            break;
        default:
            LOG_F("Invalid choice");
    };

    len = HF_MIN((size_t)snprintf(numbuf, sizeof(numbuf), "%" PRIu64, val), len);
    mangle_Overwrite(run, off, (const uint8_t*)numbuf, len, printable);
}

mangle_ByteRepeatOverwrite

新策略，在随机位置选取随机不大于文件剩余空间大小的长度，覆盖为该随机位置的值。

static void mangle_ByteRepeatOverwrite(run_t* run, bool printable) {
    size_t off     = mangle_getOffSet(run);
    size_t destOff = off + 1;
    size_t maxSz   = run->dynfile->size - destOff;

    /* No space to repeat */
    if (!maxSz) {
        mangle_Bytes(run, printable);
        return;
    }

    size_t len = mangle_getLen(maxSz);
    memset(&run->dynfile->data[destOff], run->dynfile->data[off], len);
}

mangle_ByteRepeatInsert

新策略，在随机位置选取随机不大于文件剩余空间大小的长度，插入该长度大小buffer并用之前选择的随机位置的值填充。

static void mangle_ByteRepeatInsert(run_t* run, bool printable) {
    size_t off     = mangle_getOffSet(run);
    size_t destOff = off + 1;
    size_t maxSz   = run->dynfile->size - destOff;

    /* No space to repeat */
    if (!maxSz) {
        mangle_Bytes(run, printable);
        return;
    }

    size_t len = mangle_getLen(maxSz);
    len        = mangle_Inflate(run, destOff, len, printable);
    memset(&run->dynfile->data[destOff], run->dynfile->data[off], len);
}

mangle_Magic

取各种边界值进行覆写。

static void mangle_Magic(run_t* run, bool printable) {
    uint64_t choice = util_rndGet(0, ARRAYSIZE(mangleMagicVals) - 1);
    mangle_UseValue(run, mangleMagicVals[choice].val, mangleMagicVals[choice].size, printable);
}

mangle_StaticDict

新策略，随机从读入的字典中（--dict参数）选择一个magic，插入或替换。

static void mangle_StaticDict(run_t* run, bool printable) {
    if (run->global->mutate.dictionaryCnt == 0) {
        mangle_Bytes(run, printable);
        return;
    }
    uint64_t choice = util_rndGet(0, run->global->mutate.dictionaryCnt - 1);
    mangle_UseValue(run, run->global->mutate.dictionary[choice].val,
        run->global->mutate.dictionary[choice].len, printable);
}

mangle_ConstFeedbackDict

新策略，从cmpFeedbackMap中随机选取常量值，插入或覆盖随机位置。

static void mangle_ConstFeedbackDict(run_t* run, bool printable) {
    size_t         len;
    const uint8_t* val = mangle_FeedbackDict(run, &len);
    if (val == NULL) {
        mangle_Bytes(run, printable);
        return;
    }
    mangle_UseValue(run, val, len, printable);
}
static inline const uint8_t* mangle_FeedbackDict(run_t* run, size_t* len) {
    if (!run->global->feedback.cmpFeedback) {
        return NULL;
    }
    cmpfeedback_t* cmpf = run->global->feedback.cmpFeedbackMap;
    uint32_t       cnt  = ATOMIC_GET(cmpf->cnt);
    if (cnt == 0) {
        return NULL;
    }
    if (cnt > ARRAYSIZE(cmpf->valArr)) {
        cnt = ARRAYSIZE(cmpf->valArr);
    }
    uint32_t choice = util_rndGet(0, cnt - 1);
    //从cmpFeedbackMap保存的常量值中随机选取一个 
    *len            = (size_t)ATOMIC_GET(cmpf->valArr[choice].len);
    if (*len == 0) {
        return NULL;
    }
    return cmpf->valArr[choice].val;
}

mangle_RandomOverwrite

新策略，随机位置选取随机长度进行覆盖。

static void mangle_RandomOverwrite(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    size_t len = mangle_getLen(run->dynfile->size - off);
    if (printable) {
        util_rndBufPrintable(&run->dynfile->data[off], len);
    } else {
        util_rndBuf(&run->dynfile->data[off], len);
    }
}

mangle_RandomInsert

新策略，随机位置选取随机长度进行插入。

static void mangle_RandomInsert(run_t* run, bool printable) {
    size_t off = mangle_getOffSet(run);
    size_t len = mangle_getLen(run->dynfile->size - off);

    len = mangle_Inflate(run, off, len, printable);

    if (printable) {
        util_rndBufPrintable(&run->dynfile->data[off], len);
    } else {
        util_rndBuf(&run->dynfile->data[off], len);
    }
}

mangle_Splice

新策略，从输入文件中截取随机大小，插入/覆盖到原文件。

static void mangle_Splice(run_t* run, bool printable) {
    const uint8_t* buf;
    size_t         sz = input_getRandomInputAsBuf(run, &buf);
    if (!sz) {
        mangle_Bytes(run, printable);
        return;
    }

    size_t remoteOff = mangle_getLen(sz) - 1;
    size_t len       = mangle_getLen(sz - remoteOff);
    mangle_UseValue(run, &buf[remoteOff], len, printable);
}

总结

可见 honggfuzz 此次新增加的一些变异策略可以对 fuzz 过程中通过 magic number 和一些判断校验起到积极的作用。对于fuzzbench的测试结果[1] [7] 笔者认为，首先 fuzzbench 项目目前正在完善，两次测试中间会对一些fuzzer的参数进行调整，就会出现两次测试间同一fuzzer对同一benchmark 测试效果截然不同，比如3月11日的测试[7] aflplusplus 一类的fuzzer是默认开启 laf 和 instrim 而 4月21日的测试[1] 则是将这两个参数移除了；其次，fuzzbench 只是收集运行24小时内的覆盖率信息作为评估标准，虽然 fuzzbench 也在讨论新的评估方式 [8] ,笔者认为评估维度还是不够丰富。因此 fuzzbench 目前的结果还是仅供参考，与afl、afl++ 众多扩展相比 honggfuzz 还有很多亟待提升的空间。

参考

[1] https://www.fuzzbench.com/reports/2020-04-21/index.html
[2] https://googleprojectzero.blogspot.com/2020/04/fuzzing-imageio.html
[3] https://twitter.com/0xAcid/status/1237405604123115521
[4] https://github.com/google/honggfuzz
[5] https://riusksk.me/2018/10/14/honggfuzz5/
[6] https://www.anquanke.com/post/id/181936
[7] https://www.fuzzbench.com/reports/2020-03-11/index.html
[8] https://github.com/google/fuzzbench/issues/327

正文