[原创]syzkaller源码分析（三） executeHintSeed() Mutate() Generate()-二进制漏洞-看雪-安全社区|安全招聘|kanxue.com

[原创]syzkaller源码分析（三） executeHintSeed() Mutate() Generate()

2021-6-24 20:00 8035

[原创]syzkaller源码分析（三） executeHintSeed() Mutate() Generate()

wx_左撇子

2021-6-24 20:00

8035

说明

fuzz大致的流程在上一篇中已经做了说明，这一篇主要来介绍三个函数：executeHintSeed()、Mutate()和Generate()。

水平有限，有错误的话欢迎指正。自己看的时候花了一些时间，希望对以后也要看syzkaller代码的人能有些许帮助，不过也不知道有没有人能看到这里哈哈哈 :)。

前两篇的链接如下：
syz-manager：https://bbs.pediy.com/thread-268152.htm
syz-fuzzer：https://bbs.pediy.com/thread-268195.htm

md文件会附在最后。

参考：https://xz.aliyun.com/t/5401

https://xz.aliyun.com/t/5223

executeHintSeed()

1	`executeHintSeed()在fuzzer.go的loop()下的smashInput()被调用，属于一个小环节，`

但是看的时候费了些功夫，就写在这里了。

func (proc *Proc) executeHintSeed(p *prog.Prog, call int) {
    //原注释如下:
    //First execute the original program to dump comparisons from KCOV.
    //执行原始的program，把从KCOV获取到的覆盖情况转储到comparisons中。
    info := proc.execute(proc.execOptsComps, p, ProgNormal, StatSeed)
 
    /*
        原注释如下：
        // Then mutate the initial program for every match between
        // a syscall argument and a comparison operand.
        // Execute each of such mutants to check if it gives new coverage.
        然后，对初始program的每一个可以匹配成功的系统调用参数和比较操作数进行变异。
    执行每一次变异后的程序看是否出现新的覆盖情况。
        其中，参数info.Calls[call].Comps表示per-call comparison operands，即
    每一个call的比较操作数。它的数据类型如下：map[uint64]map[uint64]bool，下面是源
    代码给出的例子，把原本的comparisons进行整理，对于每一个match，以前面的值为键，后面
    的值+true为值。
 
    // Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
    // this map will store the following:
    // m = {
    //        op1: {map[op2]: true, map[op3]: true, map[op4]: true},
    //        op2: {map[op1]: true}
    // }.
 
        第三个参数传入的是一个func，用来执行prog，后面将使用到的几个函数也会把func作为参数。
    */
    p.MutateWithHints(call, info.Calls[call].Comps, func(p *prog.Prog) {
        proc.execute(proc.execOpts, p, ProgNormal, StatHint)
    })
 
}

下面进入函数MutateWithHints()

　　这个函数涉及到的内容基本都在syzkaller/prog/hints.go中，所以有必要先介绍一下hint。

　　在hints.go文件的开头有一段介绍，现在贴在这里。

// A hint is basically a tuple consisting of a pointer to an argument
// in one of the syscalls of a program and a value, which should be
// assigned to that argument (we call it a replacer).
 
// A simplified version of hints workflow looks like this:
//        1. Fuzzer launches a program (we call it a hint seed) and collects all
// the comparisons' data for every syscall in the program.
//        2. Next it tries to match the obtained comparison operands' values
// vs. the input arguments' values.
//        3. For every such match the fuzzer mutates the program by
// replacing the pointed argument with the saved value.
//        4. If a valid program is obtained, then fuzzer launches it and
// checks if new coverage is obtained.
// For more insights on particular mutations please see prog/hints_test.go.
 
/*
    简单解释一下：
    一个hint是一个元组，它由一个指向syscall的一个参数的指针和一个value组成，这个值应当被
赋予到对应的参数上，在syzkaller中被称作一个replacer。
    一个简单的hints的工作流程如下：
    1、Fuzzer启动一个程序(这个程序被称为hint种子)并且收集这个程序中每一个syscall的比较数据。
    2、下一步Fuzzer尝试把获得的比较操作数与输入的参数值进行匹配。
    3、对于每一对匹配成功的值，fuzzer通过替换对应指针保存的值来对程序进行变异。
    4、如果能获得一个有效的程序，然后fuzzer启动程序，检查有没有新的覆盖情况生成。
*/

/* 原注释如下：
// Mutates the program using the comparison operands stored in compMaps.
// For each of the mutants executes the exec callback.
     变异程序时使用储存在compMaps里面的对比操作数。
 对于每一个变异回调参数exec。
 
     这个函数主要就调用了一个函数：ForeachArg()。其余出现的execValidate、generateHints()、
 sanitize()都以参数或其他的形式传入，都没有直接调用。
 */
func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(p *Prog)) {
    p = p.Clone()
    c := p.Calls[callIndex]
 
    //把有害的call转化为无害的call，如果失败了就直接返回。
    //然后进行参数、返回值等等的检查；最后执行程序。
    execValidate := func() {
        // Don't try to fix the candidate program.
        // Assuming the original call was sanitized, we've got a bad call
        // as the result of hint substitution, so just throw it away.
        if p.Target.sanitize(c, false) != nil {
            return
        }
        p.debugValidate()
        exec(p)
    }
 
    /*
        ForeachArg()又调用了两次foreachArgImpl()。foreachArgImpl()首先执行参数表
    中的函数func(arg Arg, _ *ArgCtx)，在下面的函数中就是执行generateHints。
        然后再根据arg类型的不同做一些不同的处理，再递归    调用自身foreachArgImpl()。
    比如，如果类型属于*GroupArg，即结构体或者    数组，就先遍历，再进行递归；如果arg是*PointerArg，
    即指针或在虚拟内存空间，就先判断是否为空，如果不为空，赋值再递归；如果是*UnionArg，即联合体，
    就直接进行递归。
    */
    ForeachArg(c, func(arg Arg, _ *ArgCtx) {
        /*
            generateHints()用来生成新的hint。主要来判断arg的类型，如果是通过判断的*ConstArg，
        就调用checkConstArg(a, compMap, exec)；如果是通过判断的*DataArg，就调用
        checkDataArg(a, compMap, exec)。而这两个函数主要都要调用shrinkExpand()来生成
        replacer，也就是hints。checkDataArg()比checkConstArg()多的步骤就是需要进行字节序
        的转换，比较简单。shrinkExpand()是生成hints的核心了，其余部分基本就是为它来判断谁能
        生成hints，把这个函数单独拿出来在下面讲。
        */
        generateHints(comps, arg, execValidate)
    })
}

重点函数 shrinkExpand()

这个函数不太好介绍，就直接上案例，不写代码了。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

/*
    shrinkExpand()用来对integer类型的数据进行强制变窄或变宽。因为不同位数的值不能随意替换，
 所以需要对位数进行统一。例如，
// Motivation for shrink:
// void f(u16 x) {
//        u8 y = (u8)x;
//        if (y == 0xab) {...}
// }
    在上面的程序中，如果调用f(0x1234)，在比较时用的时0xab与0x34进行比较，但是进行替换的时候，却没有可以与0x1234
 进行匹配的值。但是如果只匹配缩减的值（0xab与0x34），就可以进行替换了，用0x12ab来替换0x1234.
 但是，如果把上面的if (y == 0xab) {...}替换为(y == 0xdeadbeef) {...}，我们就放弃比较，因为这时我们
 要拓宽数据，但是我们很难得到有效的值。
 
    再看下面的例子，如果给出下面的程序：
// Motivation for expand:
// void f(i8 x) {
//        i16 y = (i16)x;
//        if (y == -2) {...}
// }
 如果调用f(-1)，这时x=0xff，但是在比较时需要用0xffff与0xfffe进行比较。如果用原始的0xff就不能得到
 有效的匹配，因此我们需要进行拓宽并进行检查。
 
    注1：在进行变窄的操作时忽略变宽的情况。
    注2：变宽时直接变宽到int64. 
 
 
    在syzkaller/prog/hints_test.go里面提供了许多例子。
 
    例一：shrink-16-test
 // Models the following code:
 // void f(u16 w) {
 //        u8 b = (u8) w;
 //        if (b == 0xab) {...}
 //        if (w == 0xcdcd) {...}
 //  }; f(0x1234);
 
 相应的comps如下：
    comps: CompMap{
        0x34:   compSet(0xab),
        0x1234: compSet(0xcdcd),
    }
 
 得到的res:
    res: []uint64{0x12ab, 0xcdcd}
 
    从16位到8位时，高8位用原数的高8位补足。
 
 
 例二：shrink-32-test
 // Models the following code:
 // void f(u32 dw) {
 //        u8 b = (u8) dw
 //        i16 w = (i16) dw
 //        if (b == 0xab) {...}
 //        if (w == 0xcdcd) {...}
 //        if (dw == 0xefefefef) {...}
 //  }; f(0x12345678);
 
 相应的comps：
    comps: CompMap{
        0x78:       compSet(0xab),
        0x5678:     compSet(0xcdcd),
        0x12345678: compSet(0xefefefef),
     }
 得到的res：
    res: []uint64{0x123456ab, 0x1234cdcd, 0xefefefef}
 
 对应的位置替换，不足的用原数补足。
 
 例三：shrink-with-a-wider-replacer-test1
 // Models the following code:
 // void f(i16 w) {
 //        i8 b = (i8) w;
 //        i16 other = 0xabab;
 //        if (b == other) {...}
 //  }; f(0x1234);
 // In such code the comparison will never be true, so we don't
 // generate a hint for it.
 这个例子中if判断不可能为真，就不需要生成新的hint了，直接返回nil。
 
 相应的comps如下：
     comps: CompMap{0x34: compSet(0x1bab)}
 返回值res：
     res:   nil
 
 例四：extend-32-test
 
 // Models the following code:
 // void f(i32 dw) {
 //        i64 qw = (i32) dw;
 //        if (qw == -2) {...};
 // }; f(-1);
 
 再看一下扩展的情况，源代码中的扩展只给了输入为-1的情况，猜测可能是每一个拓展的位都
 有相同的值。其他情况就舍弃了。
 in:    0xffffffff,
 comps: CompMap{0xffffffffffffffff: compSet(0xfffffffffffffffe)},
 res:   []uint64{0xfffffffe},
 
 例五：extend-with-a-wider-replacer-test
 // Models the following code:
 // void f(i8 b) {
 //        i16 w = (i16) b;
 //        if (w == (i16) 0xfeff) {...};
 // }; f(-1);
 // There's no value for b that will make the comparison true,
 // so we don't generate hints.
 
 匹配不到，直接返回nil。
 
 in:    0xff,
 comps: CompMap{0xffffffffffffffff: compSet(0xfffffffffffffeff)},
 res:   nil,
 */

Generate()

Generate()用来生成一个新的程序

// Generate generates a random program with ncalls calls.
// ct contains a set of allowed syscalls, if nil all syscalls are used.
// 这个函数用来生成一个有ncalls个call的随机的程序。
// 另一个参数ct是一个可用的syscalls的集合，如果值为nil就表示所有的syscall都可用。
func (target *Target) Generate(rs rand.Source, ncalls int, ct *ChoiceTable) *Prog {
 
    //初始化
    ...
 
    for len(p.Calls) < ncalls {
        /*
            用generateCall()来生成calls；再调用analyze()对call进行分析，对相应的类型做
        相应的处理。
            generateCall()又顺次调用generateParticularCall()->generateArgs()->
        generateArg()->generateArgImpl()->generate()。而generate()是一个接口，对
        不同类型的数据有不同的实现。
        */
        calls := r.generateCall(s, p, len(p.Calls))
        for _, c := range calls {
            s.analyze(c)
            p.Calls = append(p.Calls, c)
        }
    }
 
    // 下面进行合法检测等等。
    ...
}

Mutate()

//    Mutate()进行变异操作，跟上面提到的MutateWithHints()完全不一样。MutateWithHints()是对能匹配的
// 的值进行替换，这里的变异和AFL的变异操作基本类似。
 
func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) {
    //初始化，省略掉了
    ...
    //所有变异都不是一定发生，都设置了一定的概率。
    for stop, ok := false, false; !stop; stop = ok && len(p.Calls) != 0 && r.oneOf(3) { 
        switch {
        case r.oneOf(5):
            // Not all calls have anything squashable,
            // so this has lower priority in reality.
 
            /*
                原注释如下：
            // Picks a random complex pointer and squashes its arguments into an ANY.
            // Subsequently, if the ANY contains blobs, mutates a random blob.
                选择一个随机的复杂的指针，把它的参数压缩进ANY。然后，如果ANY包含blob对象，变异一个
            随机的blob。
 
            文中给出下面的例子，这是原始的prog：
            foo$any0(&(0x7f0000000000)=
                {0x11, 
                0x11223344,
                0x2233,
                0x1122334455667788,
                {0x1, 0x7, 0x1, 0x1, 0x1bc, 0x4},
                [{@res32=0x0, @i8=0x44, "aabb"}, {@res64=0x1, @i32=0x11223344, "1122334455667788"}]
                })
 
            下面就是经过squashed得到的程序：
            foo$any0(&(0x7f0000000000)=
                ANY=[@ANYBLOB="1100000044332211223300000000000088776655443322117d00bc11", 
                @ANYRES32=0x0, 
                @ANYBLOB="0000000044aabb00",
                @ANYRES64=0x1,
                @ANYBLOB="44332211112233445566778800000000"])
 
                在进行squash时，会调用mutateData()对数据进行变异，所涉及的规则在
            syzkaller/prog/mutations.go的mutateDataFuncs数组中，包括翻转字节、插入随机的字节、
            移除字节、添加一些字节、替换随机的字节、加减一个int8/int16/int32/int64/、把int8/int16/int32/int64
            设置为interesting的值。
            */
            ok = ctx.squashAny()
        case r.nOutOf(1, 100):
            /*
                原注释如下：
            // This function selects a random other program p0 out of the corpus, and
            // mutates ctx.p as follows: preserve ctx.p's Calls up to a random index i
            // (exclusive) concatenated with p0's calls from index i (inclusive).
                这个方法随机选择一个语料库外的程序p0，并对程序ctx.p进行变异。具体操作如下：选一个随机
            数i，保留源程序ctx.p的前i个call（不包括第i个），把p0的call从第i个位置往后接（包括i）;
            换句话说就是把p0的所有call从i的位置往后插，画了下面的图，将就看一下。
 
         ctx.p[0]       ctx.p[i] p0[0] <--插在这里--> p0结束 ctx.p[i+1]
            |-------------------|-------------------------|----------------------|
 
            如果call的总长度超过了总长度ncalls，就从最后往前删除，反正后面是ctx.p的call。            
            */
            ok = ctx.splice()
        case r.nOutOf(20, 31):
            /*
                原注释如下：
            // Inserts a new call at a randomly chosen point (with bias towards the end of
            // existing program). Does not insert a call if program already has ncalls.
                在随机位置插入一个新的call。如果call的数目达到最大值ncalls就不要插入了。
                在选取随机位置时调用了函数biasedRand(n, k int)，此函数会生成一个随机数[0..n)，但是
            获得n-1的概率是0的概率的k倍。
                这个方法跟上面的方法不一样的是：1、这个是插入一个call，splice()是插入一个prog的所有calls；
            2、这个插入的call是新生成的call，splice()插入的是已经存在的prog的calls。
            */
            ok = ctx.insertCall()
        case r.nOutOf(10, 11): 
            // Mutate an argument of a random call.
            // 对一个随机call的参数进行变异。
            // 先判断参数的类型，对不同类型的参数使用不同的变异策略。
            ok = ctx.mutateArg()
        default:
            // Removes a random call from program.
            // 在program中随机移除一个call。
            ok = ctx.removeCall()
        }
    }
 
    ...
}