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
#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;
}

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
// 在块变异中默认去掉了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]);

  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}