首页
论坛
课程
招聘
[原创]syzkaller源码分析(三) executeHintSeed() Mutate() Generate()
2021-6-24 20:00 3403

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

2021-6-24 20:00
3403

说明

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()被调用,属于一个小环节,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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文件的开头有一段介绍,现在贴在这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 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启动程序,检查有没有新的覆盖情况生成。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* 原注释如下:
// 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()

 

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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),在比较时用的时0xab0x34进行比较,但是进行替换的时候,却没有可以与0x1234
 进行匹配的值。但是如果只匹配缩减的值(0xab0x34),就可以进行替换了,用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,但是在比较时需要用0xffff0xfffe进行比较。如果用原始的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()用来生成一个新的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//    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()
        }
    }
 
    ...
}

[注意] 欢迎加入看雪团队!base上海,招聘CTF安全工程师,将兴趣和工作融合在一起!看雪20年安全圈的口碑,助你快速成长!

最后于 2021-6-26 20:58 被wx_左撇子编辑 ,原因:
上传的附件:
收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回