1 /*
2 american fuzzy lop++ - queue relates routines
3 ---------------------------------------------
4
5 Originally written by Michal Zalewski
6
7 Now maintained by Marc Heuse <[email protected]>,
8 Heiko Eißfeldt <[email protected]> and
9 Andrea Fioraldi <[email protected]>
10
11 Copyright 2016, 2017 Google Inc. All rights reserved.
12 Copyright 2019-2024 AFLplusplus Project. All rights reserved.
13 Licensed under the Apache License, Version 2.0 (the "License");
14 you may not use this file except in compliance with the License.
15 You may obtain a copy of the License at:
16
17 https://www.apache.org/licenses/LICENSE-2.0
18
19 This is the real deal: the program takes an instrumented binary and
20 attempts a variety of basic fuzzing tricks, paying close attention to
21 how they affect the execution path.
22
23 */
24
25 #include "afl-fuzz.h"
26 #include <limits.h>
27 #include <ctype.h>
28 #include <math.h>
29
30 #ifdef _STANDALONE_MODULE
minimize_bits(afl_state_t * afl,u8 * dst,u8 * src)31 void minimize_bits(afl_state_t *afl, u8 *dst, u8 *src) {
32
33 return;
34
35 }
36
run_afl_custom_queue_new_entry(afl_state_t * afl,struct queue_entry * q,u8 * a,u8 * b)37 void run_afl_custom_queue_new_entry(afl_state_t *afl, struct queue_entry *q,
38 u8 *a, u8 *b) {
39
40 return;
41
42 }
43
44 #endif
45
46 /* select next queue entry based on alias algo - fast! */
47
select_next_queue_entry(afl_state_t * afl)48 inline u32 select_next_queue_entry(afl_state_t *afl) {
49
50 u32 s = rand_below(afl, afl->queued_items);
51 double p = rand_next_percent(afl);
52
53 /*
54 fprintf(stderr, "select: p=%f s=%u ... p < prob[s]=%f ? s=%u : alias[%u]=%u"
55 " ==> %u\n", p, s, afl->alias_probability[s], s, s, afl->alias_table[s], p <
56 afl->alias_probability[s] ? s : afl->alias_table[s]);
57 */
58
59 return (p < afl->alias_probability[s] ? s : afl->alias_table[s]);
60
61 }
62
compute_weight(afl_state_t * afl,struct queue_entry * q,double avg_exec_us,double avg_bitmap_size,double avg_top_size)63 double compute_weight(afl_state_t *afl, struct queue_entry *q,
64 double avg_exec_us, double avg_bitmap_size,
65 double avg_top_size) {
66
67 double weight = 1.0;
68
69 if (likely(afl->schedule >= FAST && afl->schedule <= RARE)) {
70
71 u32 hits = afl->n_fuzz[q->n_fuzz_entry];
72 if (likely(hits)) { weight /= (log10(hits) + 1); }
73
74 }
75
76 if (likely(afl->schedule < RARE)) { weight *= (avg_exec_us / q->exec_us); }
77 weight *= (log(q->bitmap_size) / avg_bitmap_size);
78 weight *= (1 + (q->tc_ref / avg_top_size));
79
80 if (unlikely(weight < 0.1)) { weight = 0.1; }
81 if (unlikely(q->favored)) { weight *= 5; }
82 if (unlikely(!q->was_fuzzed)) { weight *= 2; }
83 if (unlikely(q->fs_redundant)) { weight *= 0.8; }
84
85 return weight;
86
87 }
88
89 /* create the alias table that allows weighted random selection - expensive */
90
create_alias_table(afl_state_t * afl)91 void create_alias_table(afl_state_t *afl) {
92
93 u32 n = afl->queued_items, i = 0, nSmall = 0, nLarge = n - 1;
94 double sum = 0;
95
96 double *P = (double *)afl_realloc(AFL_BUF_PARAM(out), n * sizeof(double));
97 u32 *Small = (int *)afl_realloc(AFL_BUF_PARAM(out_scratch), n * sizeof(u32));
98 u32 *Large = (int *)afl_realloc(AFL_BUF_PARAM(in_scratch), n * sizeof(u32));
99
100 afl->alias_table =
101 (u32 *)afl_realloc((void **)&afl->alias_table, n * sizeof(u32));
102 afl->alias_probability = (double *)afl_realloc(
103 (void **)&afl->alias_probability, n * sizeof(double));
104
105 if (!P || !Small || !Large || !afl->alias_table || !afl->alias_probability) {
106
107 FATAL("could not acquire memory for alias table");
108
109 }
110
111 memset((void *)afl->alias_probability, 0, n * sizeof(double));
112 memset((void *)afl->alias_table, 0, n * sizeof(u32));
113 memset((void *)Small, 0, n * sizeof(u32));
114 memset((void *)Large, 0, n * sizeof(u32));
115
116 if (likely(afl->schedule < RARE)) {
117
118 double avg_exec_us = 0.0;
119 double avg_bitmap_size = 0.0;
120 double avg_top_size = 0.0;
121 u32 active = 0;
122
123 for (i = 0; i < n; i++) {
124
125 struct queue_entry *q = afl->queue_buf[i];
126
127 // disabled entries might have timings and bitmap values
128 if (likely(!q->disabled)) {
129
130 avg_exec_us += q->exec_us;
131 avg_bitmap_size += log(q->bitmap_size);
132 avg_top_size += q->tc_ref;
133 ++active;
134
135 }
136
137 }
138
139 avg_exec_us /= active;
140 avg_bitmap_size /= active;
141 avg_top_size /= active;
142
143 for (i = 0; i < n; i++) {
144
145 struct queue_entry *q = afl->queue_buf[i];
146
147 if (likely(!q->disabled)) {
148
149 q->weight =
150 compute_weight(afl, q, avg_exec_us, avg_bitmap_size, avg_top_size);
151 q->perf_score = calculate_score(afl, q);
152 sum += q->weight;
153
154 }
155
156 }
157
158 if (unlikely(afl->schedule == MMOPT) && afl->queued_discovered) {
159
160 u32 cnt = afl->queued_discovered >= 5 ? 5 : afl->queued_discovered;
161
162 for (i = n - cnt; i < n; i++) {
163
164 struct queue_entry *q = afl->queue_buf[i];
165
166 if (likely(!q->disabled)) { q->weight *= 2.0; }
167
168 }
169
170 }
171
172 for (i = 0; i < n; i++) {
173
174 // weight is always 0 for disabled entries
175 if (unlikely(afl->queue_buf[i]->disabled)) {
176
177 P[i] = 0;
178
179 } else {
180
181 P[i] = (afl->queue_buf[i]->weight * n) / sum;
182
183 }
184
185 }
186
187 } else {
188
189 for (i = 0; i < n; i++) {
190
191 struct queue_entry *q = afl->queue_buf[i];
192
193 if (likely(!q->disabled)) {
194
195 q->perf_score = calculate_score(afl, q);
196 sum += q->perf_score;
197
198 }
199
200 }
201
202 for (i = 0; i < n; i++) {
203
204 // perf_score is always 0 for disabled entries
205 if (unlikely(afl->queue_buf[i]->disabled)) {
206
207 P[i] = 0;
208
209 } else {
210
211 P[i] = (afl->queue_buf[i]->perf_score * n) / sum;
212
213 }
214
215 }
216
217 }
218
219 // Done collecting weightings in P, now create the arrays.
220
221 for (s32 j = (s32)(n - 1); j >= 0; j--) {
222
223 if (P[j] < 1) {
224
225 Small[nSmall++] = (u32)j;
226
227 } else {
228
229 Large[nLarge--] = (u32)j;
230
231 }
232
233 }
234
235 while (nSmall && nLarge != n - 1) {
236
237 u32 small = Small[--nSmall];
238 u32 large = Large[++nLarge];
239
240 afl->alias_probability[small] = P[small];
241 afl->alias_table[small] = large;
242
243 P[large] = P[large] - (1 - P[small]);
244
245 if (P[large] < 1) {
246
247 Small[nSmall++] = large;
248
249 } else {
250
251 Large[nLarge--] = large;
252
253 }
254
255 }
256
257 while (nSmall) {
258
259 afl->alias_probability[Small[--nSmall]] = 1;
260
261 }
262
263 while (nLarge != n - 1) {
264
265 afl->alias_probability[Large[++nLarge]] = 1;
266
267 }
268
269 afl->reinit_table = 0;
270
271 /*
272 #ifdef INTROSPECTION
273 u8 fn[PATH_MAX];
274 snprintf(fn, PATH_MAX, "%s/introspection_corpus.txt", afl->out_dir);
275 FILE *f = fopen(fn, "a");
276 if (f) {
277
278 for (i = 0; i < n; i++) {
279
280 struct queue_entry *q = afl->queue_buf[i];
281 fprintf(
282 f,
283 "entry=%u name=%s favored=%s variable=%s disabled=%s len=%u "
284 "exec_us=%u "
285 "bitmap_size=%u bitsmap_size=%u tops=%u weight=%f perf_score=%f\n",
286 i, q->fname, q->favored ? "true" : "false",
287 q->var_behavior ? "true" : "false", q->disabled ? "true" : "false",
288 q->len, (u32)q->exec_us, q->bitmap_size, q->bitsmap_size, q->tc_ref,
289 q->weight, q->perf_score);
290
291 }
292
293 fprintf(f, "\n");
294 fclose(f);
295
296 }
297
298 #endif
299 */
300 /*
301 fprintf(stderr, " entry alias probability perf_score weight
302 filename\n"); for (i = 0; i < n; ++i) fprintf(stderr, " %5u %5u %11u
303 %0.9f %0.9f %s\n", i, afl->alias_table[i], afl->alias_probability[i],
304 afl->queue_buf[i]->perf_score, afl->queue_buf[i]->weight,
305 afl->queue_buf[i]->fname);
306 */
307
308 }
309
310 /* Mark deterministic checks as done for a particular queue entry. We use the
311 .state file to avoid repeating deterministic fuzzing when resuming aborted
312 scans. */
313
mark_as_det_done(afl_state_t * afl,struct queue_entry * q)314 void mark_as_det_done(afl_state_t *afl, struct queue_entry *q) {
315
316 char fn[PATH_MAX];
317 s32 fd;
318
319 snprintf(fn, PATH_MAX, "%s/queue/.state/deterministic_done/%s", afl->out_dir,
320 strrchr((char *)q->fname, '/') + 1);
321
322 fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, DEFAULT_PERMISSION);
323 if (fd < 0) { PFATAL("Unable to create '%s'", fn); }
324 close(fd);
325
326 q->passed_det = 1;
327
328 }
329
330 /* Mark as variable. Create symlinks if possible to make it easier to examine
331 the files. */
332
mark_as_variable(afl_state_t * afl,struct queue_entry * q)333 void mark_as_variable(afl_state_t *afl, struct queue_entry *q) {
334
335 char fn[PATH_MAX];
336 char ldest[PATH_MAX];
337
338 char *fn_name = strrchr((char *)q->fname, '/') + 1;
339
340 sprintf(ldest, "../../%s", fn_name);
341 sprintf(fn, "%s/queue/.state/variable_behavior/%s", afl->out_dir, fn_name);
342
343 if (symlink(ldest, fn)) {
344
345 s32 fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, DEFAULT_PERMISSION);
346 if (fd < 0) { PFATAL("Unable to create '%s'", fn); }
347 close(fd);
348
349 }
350
351 q->var_behavior = 1;
352
353 }
354
355 /* Mark / unmark as redundant (edge-only). This is not used for restoring state,
356 but may be useful for post-processing datasets. */
357
mark_as_redundant(afl_state_t * afl,struct queue_entry * q,u8 state)358 void mark_as_redundant(afl_state_t *afl, struct queue_entry *q, u8 state) {
359
360 if (likely(state == q->fs_redundant)) { return; }
361
362 char fn[PATH_MAX];
363
364 q->fs_redundant = state;
365
366 sprintf(fn, "%s/queue/.state/redundant_edges/%s", afl->out_dir,
367 strrchr((char *)q->fname, '/') + 1);
368
369 if (state) {
370
371 s32 fd;
372
373 fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, DEFAULT_PERMISSION);
374 if (fd < 0) { PFATAL("Unable to create '%s'", fn); }
375 close(fd);
376
377 } else {
378
379 if (unlink(fn)) { PFATAL("Unable to remove '%s'", fn); }
380
381 }
382
383 }
384
385 /* check if pointer is ascii or UTF-8 */
386
check_if_text_buf(u8 * buf,u32 len)387 u8 check_if_text_buf(u8 *buf, u32 len) {
388
389 u32 offset = 0, ascii = 0, utf8 = 0;
390
391 while (offset < len) {
392
393 // ASCII: <= 0x7F to allow ASCII control characters
394 if ((buf[offset + 0] == 0x09 || buf[offset + 0] == 0x0A ||
395 buf[offset + 0] == 0x0D ||
396 (0x20 <= buf[offset + 0] && buf[offset + 0] <= 0x7E))) {
397
398 offset++;
399 utf8++;
400 ascii++;
401 continue;
402
403 }
404
405 if (isascii((int)buf[offset]) || isprint((int)buf[offset])) {
406
407 ascii++;
408 // we continue though as it can also be a valid utf8
409
410 }
411
412 // non-overlong 2-byte
413 if (len - offset > 1 &&
414 ((0xC2 <= buf[offset + 0] && buf[offset + 0] <= 0xDF) &&
415 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF))) {
416
417 offset += 2;
418 utf8++;
419 continue;
420
421 }
422
423 // excluding overlongs
424 if ((len - offset > 2) &&
425 ((buf[offset + 0] == 0xE0 &&
426 (0xA0 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
427 (0x80 <= buf[offset + 2] &&
428 buf[offset + 2] <= 0xBF)) || // straight 3-byte
429 (((0xE1 <= buf[offset + 0] && buf[offset + 0] <= 0xEC) ||
430 buf[offset + 0] == 0xEE || buf[offset + 0] == 0xEF) &&
431 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
432 (0x80 <= buf[offset + 2] &&
433 buf[offset + 2] <= 0xBF)) || // excluding surrogates
434 (buf[offset + 0] == 0xED &&
435 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0x9F) &&
436 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF)))) {
437
438 offset += 3;
439 utf8++;
440 continue;
441
442 }
443
444 // planes 1-3
445 if ((len - offset > 3) &&
446 ((buf[offset + 0] == 0xF0 &&
447 (0x90 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
448 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
449 (0x80 <= buf[offset + 3] &&
450 buf[offset + 3] <= 0xBF)) || // planes 4-15
451 ((0xF1 <= buf[offset + 0] && buf[offset + 0] <= 0xF3) &&
452 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
453 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
454 (0x80 <= buf[offset + 3] && buf[offset + 3] <= 0xBF)) || // plane 16
455 (buf[offset + 0] == 0xF4 &&
456 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0x8F) &&
457 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
458 (0x80 <= buf[offset + 3] && buf[offset + 3] <= 0xBF)))) {
459
460 offset += 4;
461 utf8++;
462 continue;
463
464 }
465
466 offset++;
467
468 }
469
470 return (utf8 > ascii ? utf8 : ascii);
471
472 }
473
474 /* check if queue entry is ascii or UTF-8 */
475
check_if_text(afl_state_t * afl,struct queue_entry * q)476 static u8 check_if_text(afl_state_t *afl, struct queue_entry *q) {
477
478 if (q->len < AFL_TXT_MIN_LEN || q->len < AFL_TXT_MAX_LEN) return 0;
479
480 u8 *buf;
481 int fd;
482 u32 len = q->len, offset = 0, ascii = 0, utf8 = 0;
483 ssize_t comp;
484
485 if (len >= MAX_FILE) len = MAX_FILE - 1;
486 if ((fd = open((char *)q->fname, O_RDONLY)) < 0) return 0;
487 buf = (u8 *)afl_realloc(AFL_BUF_PARAM(in_scratch), len + 1);
488 comp = read(fd, buf, len);
489 close(fd);
490 if (comp != (ssize_t)len) return 0;
491 buf[len] = 0;
492
493 while (offset < len) {
494
495 // ASCII: <= 0x7F to allow ASCII control characters
496 if ((buf[offset + 0] == 0x09 || buf[offset + 0] == 0x0A ||
497 buf[offset + 0] == 0x0D ||
498 (0x20 <= buf[offset + 0] && buf[offset + 0] <= 0x7E))) {
499
500 offset++;
501 utf8++;
502 ascii++;
503 continue;
504
505 }
506
507 if (isascii((int)buf[offset]) || isprint((int)buf[offset])) {
508
509 ascii++;
510 // we continue though as it can also be a valid utf8
511
512 }
513
514 // non-overlong 2-byte
515 if (len - offset > 1 &&
516 ((0xC2 <= buf[offset + 0] && buf[offset + 0] <= 0xDF) &&
517 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF))) {
518
519 offset += 2;
520 utf8++;
521 comp--;
522 continue;
523
524 }
525
526 // excluding overlongs
527 if ((len - offset > 2) &&
528 ((buf[offset + 0] == 0xE0 &&
529 (0xA0 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
530 (0x80 <= buf[offset + 2] &&
531 buf[offset + 2] <= 0xBF)) || // straight 3-byte
532 (((0xE1 <= buf[offset + 0] && buf[offset + 0] <= 0xEC) ||
533 buf[offset + 0] == 0xEE || buf[offset + 0] == 0xEF) &&
534 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
535 (0x80 <= buf[offset + 2] &&
536 buf[offset + 2] <= 0xBF)) || // excluding surrogates
537 (buf[offset + 0] == 0xED &&
538 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0x9F) &&
539 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF)))) {
540
541 offset += 3;
542 utf8++;
543 comp -= 2;
544 continue;
545
546 }
547
548 // planes 1-3
549 if ((len - offset > 3) &&
550 ((buf[offset + 0] == 0xF0 &&
551 (0x90 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
552 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
553 (0x80 <= buf[offset + 3] &&
554 buf[offset + 3] <= 0xBF)) || // planes 4-15
555 ((0xF1 <= buf[offset + 0] && buf[offset + 0] <= 0xF3) &&
556 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0xBF) &&
557 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
558 (0x80 <= buf[offset + 3] && buf[offset + 3] <= 0xBF)) || // plane 16
559 (buf[offset + 0] == 0xF4 &&
560 (0x80 <= buf[offset + 1] && buf[offset + 1] <= 0x8F) &&
561 (0x80 <= buf[offset + 2] && buf[offset + 2] <= 0xBF) &&
562 (0x80 <= buf[offset + 3] && buf[offset + 3] <= 0xBF)))) {
563
564 offset += 4;
565 utf8++;
566 comp -= 3;
567 continue;
568
569 }
570
571 offset++;
572
573 }
574
575 u32 percent_utf8 = (utf8 * 100) / comp;
576 u32 percent_ascii = (ascii * 100) / len;
577
578 if (percent_utf8 >= percent_ascii && percent_utf8 >= AFL_TXT_MIN_PERCENT)
579 return 2;
580 if (percent_ascii >= AFL_TXT_MIN_PERCENT) return 1;
581 return 0;
582
583 }
584
585 /* Append new test case to the queue. */
586
add_to_queue(afl_state_t * afl,u8 * fname,u32 len,u8 passed_det)587 void add_to_queue(afl_state_t *afl, u8 *fname, u32 len, u8 passed_det) {
588
589 struct queue_entry *q =
590 (struct queue_entry *)ck_alloc(sizeof(struct queue_entry));
591
592 q->fname = fname;
593 q->len = len;
594 q->depth = afl->cur_depth + 1;
595 q->passed_det = passed_det;
596 q->trace_mini = NULL;
597 q->testcase_buf = NULL;
598 q->mother = afl->queue_cur;
599
600 #ifdef INTROSPECTION
601 q->bitsmap_size = afl->bitsmap_size;
602 #endif
603
604 if (q->depth > afl->max_depth) { afl->max_depth = q->depth; }
605
606 if (afl->queue_top) {
607
608 afl->queue_top = q;
609
610 } else {
611
612 afl->queue = afl->queue_top = q;
613
614 }
615
616 if (likely(q->len > 4)) { ++afl->ready_for_splicing_count; }
617
618 ++afl->queued_items;
619 ++afl->active_items;
620 ++afl->pending_not_fuzzed;
621
622 afl->cycles_wo_finds = 0;
623
624 struct queue_entry **queue_buf = (struct queue_entry **)afl_realloc(
625 AFL_BUF_PARAM(queue), afl->queued_items * sizeof(struct queue_entry *));
626 if (unlikely(!queue_buf)) { PFATAL("alloc"); }
627 queue_buf[afl->queued_items - 1] = q;
628 q->id = afl->queued_items - 1;
629
630 u64 cur_time = get_cur_time();
631
632 if (likely(afl->start_time) &&
633 unlikely(afl->longest_find_time < cur_time - afl->last_find_time)) {
634
635 if (unlikely(!afl->last_find_time)) {
636
637 afl->longest_find_time = cur_time - afl->start_time;
638
639 } else {
640
641 afl->longest_find_time = cur_time - afl->last_find_time;
642
643 }
644
645 }
646
647 afl->last_find_time = cur_time;
648
649 if (afl->custom_mutators_count) {
650
651 /* At the initialization stage, queue_cur is NULL */
652 if (afl->queue_cur && !afl->syncing_party) {
653
654 run_afl_custom_queue_new_entry(afl, q, fname, afl->queue_cur->fname);
655
656 }
657
658 }
659
660 /* only redqueen currently uses is_ascii */
661 if (unlikely(afl->shm.cmplog_mode && !q->is_ascii)) {
662
663 q->is_ascii = check_if_text(afl, q);
664
665 }
666
667 q->skipdet_e = (struct skipdet_entry *)ck_alloc(sizeof(struct skipdet_entry));
668
669 }
670
671 /* Destroy the entire queue. */
672
destroy_queue(afl_state_t * afl)673 void destroy_queue(afl_state_t *afl) {
674
675 u32 i;
676
677 for (i = 0; i < afl->queued_items; i++) {
678
679 struct queue_entry *q;
680
681 q = afl->queue_buf[i];
682 ck_free(q->fname);
683 ck_free(q->trace_mini);
684 if (q->skipdet_e) {
685
686 if (q->skipdet_e->done_inf_map) ck_free(q->skipdet_e->done_inf_map);
687 if (q->skipdet_e->skip_eff_map) ck_free(q->skipdet_e->skip_eff_map);
688
689 ck_free(q->skipdet_e);
690
691 }
692
693 ck_free(q);
694
695 }
696
697 }
698
699 /* When we bump into a new path, we call this to see if the path appears
700 more "favorable" than any of the existing ones. The purpose of the
701 "favorables" is to have a minimal set of paths that trigger all the bits
702 seen in the bitmap so far, and focus on fuzzing them at the expense of
703 the rest.
704
705 The first step of the process is to maintain a list of afl->top_rated[]
706 entries for every byte in the bitmap. We win that slot if there is no
707 previous contender, or if the contender has a more favorable speed x size
708 factor. */
709
update_bitmap_score(afl_state_t * afl,struct queue_entry * q)710 void update_bitmap_score(afl_state_t *afl, struct queue_entry *q) {
711
712 u32 i;
713 u64 fav_factor;
714 u64 fuzz_p2;
715
716 if (likely(afl->schedule >= FAST && afl->schedule < RARE)) {
717
718 fuzz_p2 = 0; // Skip the fuzz_p2 comparison
719
720 } else if (unlikely(afl->schedule == RARE)) {
721
722 fuzz_p2 = next_pow2(afl->n_fuzz[q->n_fuzz_entry]);
723
724 } else {
725
726 fuzz_p2 = q->fuzz_level;
727
728 }
729
730 if (unlikely(afl->schedule >= RARE) || unlikely(afl->fixed_seed)) {
731
732 fav_factor = q->len << 2;
733
734 } else {
735
736 fav_factor = q->exec_us * q->len;
737
738 }
739
740 /* For every byte set in afl->fsrv.trace_bits[], see if there is a previous
741 winner, and how it compares to us. */
742 for (i = 0; i < afl->fsrv.map_size; ++i) {
743
744 if (afl->fsrv.trace_bits[i]) {
745
746 if (afl->top_rated[i]) {
747
748 /* Faster-executing or smaller test cases are favored. */
749 u64 top_rated_fav_factor;
750 u64 top_rated_fuzz_p2;
751
752 if (likely(afl->schedule >= FAST && afl->schedule < RARE)) {
753
754 top_rated_fuzz_p2 = 0; // Skip the fuzz_p2 comparison
755
756 } else if (unlikely(afl->schedule == RARE)) {
757
758 top_rated_fuzz_p2 =
759 next_pow2(afl->n_fuzz[afl->top_rated[i]->n_fuzz_entry]);
760
761 } else {
762
763 top_rated_fuzz_p2 = afl->top_rated[i]->fuzz_level;
764
765 }
766
767 if (unlikely(afl->schedule >= RARE) || unlikely(afl->fixed_seed)) {
768
769 top_rated_fav_factor = afl->top_rated[i]->len << 2;
770
771 } else {
772
773 top_rated_fav_factor =
774 afl->top_rated[i]->exec_us * afl->top_rated[i]->len;
775
776 }
777
778 if (likely(fuzz_p2 > top_rated_fuzz_p2)) { continue; }
779
780 if (likely(fav_factor > top_rated_fav_factor)) { continue; }
781
782 /* Looks like we're going to win. Decrease ref count for the
783 previous winner, discard its afl->fsrv.trace_bits[] if necessary. */
784
785 if (!--afl->top_rated[i]->tc_ref) {
786
787 ck_free(afl->top_rated[i]->trace_mini);
788 afl->top_rated[i]->trace_mini = 0;
789
790 }
791
792 }
793
794 /* Insert ourselves as the new winner. */
795
796 afl->top_rated[i] = q;
797 ++q->tc_ref;
798
799 if (!q->trace_mini) {
800
801 u32 len = (afl->fsrv.map_size >> 3);
802 q->trace_mini = (u8 *)ck_alloc(len);
803 minimize_bits(afl, q->trace_mini, afl->fsrv.trace_bits);
804
805 }
806
807 afl->score_changed = 1;
808
809 }
810
811 }
812
813 }
814
815 /* The second part of the mechanism discussed above is a routine that
816 goes over afl->top_rated[] entries, and then sequentially grabs winners for
817 previously-unseen bytes (temp_v) and marks them as favored, at least
818 until the next run. The favored entries are given more air time during
819 all fuzzing steps. */
820
cull_queue(afl_state_t * afl)821 void cull_queue(afl_state_t *afl) {
822
823 if (likely(!afl->score_changed || afl->non_instrumented_mode)) { return; }
824
825 u32 len = (afl->fsrv.map_size >> 3);
826 u32 i;
827 u8 *temp_v = afl->map_tmp_buf;
828
829 afl->score_changed = 0;
830
831 memset(temp_v, 255, len);
832
833 afl->queued_favored = 0;
834 afl->pending_favored = 0;
835
836 for (i = 0; i < afl->queued_items; i++) {
837
838 afl->queue_buf[i]->favored = 0;
839
840 }
841
842 /* Let's see if anything in the bitmap isn't captured in temp_v.
843 If yes, and if it has a afl->top_rated[] contender, let's use it. */
844
845 afl->smallest_favored = -1;
846
847 for (i = 0; i < afl->fsrv.map_size; ++i) {
848
849 if (afl->top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
850
851 u32 j = len;
852
853 /* Remove all bits belonging to the current entry from temp_v. */
854
855 while (j--) {
856
857 if (afl->top_rated[i]->trace_mini[j]) {
858
859 temp_v[j] &= ~afl->top_rated[i]->trace_mini[j];
860
861 }
862
863 }
864
865 if (!afl->top_rated[i]->favored) {
866
867 afl->top_rated[i]->favored = 1;
868 ++afl->queued_favored;
869
870 if (!afl->top_rated[i]->was_fuzzed) {
871
872 ++afl->pending_favored;
873 if (unlikely(afl->smallest_favored < 0)) {
874
875 afl->smallest_favored = (s64)afl->top_rated[i]->id;
876
877 }
878
879 }
880
881 }
882
883 }
884
885 }
886
887 for (i = 0; i < afl->queued_items; i++) {
888
889 if (likely(!afl->queue_buf[i]->disabled)) {
890
891 mark_as_redundant(afl, afl->queue_buf[i], !afl->queue_buf[i]->favored);
892
893 }
894
895 }
896
897 afl->reinit_table = 1;
898
899 }
900
901 /* Calculate case desirability score to adjust the length of havoc fuzzing.
902 A helper function for fuzz_one(). Maybe some of these constants should
903 go into config.h. */
904
calculate_score(afl_state_t * afl,struct queue_entry * q)905 u32 calculate_score(afl_state_t *afl, struct queue_entry *q) {
906
907 u32 cal_cycles = afl->total_cal_cycles;
908 u32 bitmap_entries = afl->total_bitmap_entries;
909
910 if (unlikely(!cal_cycles)) { cal_cycles = 1; }
911 if (unlikely(!bitmap_entries)) { bitmap_entries = 1; }
912
913 u32 avg_exec_us = afl->total_cal_us / cal_cycles;
914 u32 avg_bitmap_size = afl->total_bitmap_size / bitmap_entries;
915 u32 perf_score = 100;
916
917 /* Adjust score based on execution speed of this path, compared to the
918 global average. Multiplier ranges from 0.1x to 3x. Fast inputs are
919 less expensive to fuzz, so we're giving them more air time. */
920
921 // TODO BUG FIXME: is this really a good idea?
922 // This sounds like looking for lost keys under a street light just because
923 // the light is better there.
924 // Longer execution time means longer work on the input, the deeper in
925 // coverage, the better the fuzzing, right? -mh
926
927 if (likely(afl->schedule < RARE) && likely(!afl->fixed_seed)) {
928
929 if (q->exec_us * 0.1 > avg_exec_us) {
930
931 perf_score = 10;
932
933 } else if (q->exec_us * 0.25 > avg_exec_us) {
934
935 perf_score = 25;
936
937 } else if (q->exec_us * 0.5 > avg_exec_us) {
938
939 perf_score = 50;
940
941 } else if (q->exec_us * 0.75 > avg_exec_us) {
942
943 perf_score = 75;
944
945 } else if (q->exec_us * 4 < avg_exec_us) {
946
947 perf_score = 300;
948
949 } else if (q->exec_us * 3 < avg_exec_us) {
950
951 perf_score = 200;
952
953 } else if (q->exec_us * 2 < avg_exec_us) {
954
955 perf_score = 150;
956
957 }
958
959 }
960
961 /* Adjust score based on bitmap size. The working theory is that better
962 coverage translates to better targets. Multiplier from 0.25x to 3x. */
963
964 if (q->bitmap_size * 0.3 > avg_bitmap_size) {
965
966 perf_score *= 3;
967
968 } else if (q->bitmap_size * 0.5 > avg_bitmap_size) {
969
970 perf_score *= 2;
971
972 } else if (q->bitmap_size * 0.75 > avg_bitmap_size) {
973
974 perf_score *= 1.5;
975
976 } else if (q->bitmap_size * 3 < avg_bitmap_size) {
977
978 perf_score *= 0.25;
979
980 } else if (q->bitmap_size * 2 < avg_bitmap_size) {
981
982 perf_score *= 0.5;
983
984 } else if (q->bitmap_size * 1.5 < avg_bitmap_size) {
985
986 perf_score *= 0.75;
987
988 }
989
990 /* Adjust score based on handicap. Handicap is proportional to how late
991 in the game we learned about this path. Latecomers are allowed to run
992 for a bit longer until they catch up with the rest. */
993
994 if (q->handicap >= 4) {
995
996 perf_score *= 4;
997 q->handicap -= 4;
998
999 } else if (q->handicap) {
1000
1001 perf_score *= 2;
1002 --q->handicap;
1003
1004 }
1005
1006 /* Final adjustment based on input depth, under the assumption that fuzzing
1007 deeper test cases is more likely to reveal stuff that can't be
1008 discovered with traditional fuzzers. */
1009
1010 switch (q->depth) {
1011
1012 case 0 ... 3:
1013 break;
1014 case 4 ... 7:
1015 perf_score *= 2;
1016 break;
1017 case 8 ... 13:
1018 perf_score *= 3;
1019 break;
1020 case 14 ... 25:
1021 perf_score *= 4;
1022 break;
1023 default:
1024 perf_score *= 5;
1025
1026 }
1027
1028 u32 n_items;
1029 double factor = 1.0;
1030 long double fuzz_mu;
1031
1032 switch (afl->schedule) {
1033
1034 case EXPLORE:
1035 break;
1036
1037 case SEEK:
1038 break;
1039
1040 case EXPLOIT:
1041 factor = MAX_FACTOR;
1042 break;
1043
1044 case COE:
1045 fuzz_mu = 0.0;
1046 n_items = 0;
1047
1048 // Don't modify perf_score for unfuzzed seeds
1049 if (!q->fuzz_level) break;
1050
1051 u32 i;
1052 for (i = 0; i < afl->queued_items; i++) {
1053
1054 if (likely(!afl->queue_buf[i]->disabled)) {
1055
1056 fuzz_mu += log2(afl->n_fuzz[afl->queue_buf[i]->n_fuzz_entry]);
1057 n_items++;
1058
1059 }
1060
1061 }
1062
1063 if (unlikely(!n_items)) { FATAL("Queue state corrupt"); }
1064
1065 fuzz_mu = fuzz_mu / n_items;
1066
1067 if (log2(afl->n_fuzz[q->n_fuzz_entry]) > fuzz_mu) {
1068
1069 /* Never skip favourites */
1070 if (!q->favored) factor = 0;
1071
1072 break;
1073
1074 }
1075
1076 // Fall through
1077 case FAST:
1078
1079 // Don't modify unfuzzed seeds
1080 if (!q->fuzz_level) break;
1081
1082 switch ((u32)log2(afl->n_fuzz[q->n_fuzz_entry])) {
1083
1084 case 0 ... 1:
1085 factor = 4;
1086 break;
1087
1088 case 2 ... 3:
1089 factor = 3;
1090 break;
1091
1092 case 4:
1093 factor = 2;
1094 break;
1095
1096 case 5:
1097 break;
1098
1099 case 6:
1100 if (!q->favored) factor = 0.8;
1101 break;
1102
1103 case 7:
1104 if (!q->favored) factor = 0.6;
1105 break;
1106
1107 default:
1108 if (!q->favored) factor = 0.4;
1109 break;
1110
1111 }
1112
1113 if (q->favored) factor *= 1.15;
1114
1115 break;
1116
1117 case LIN:
1118 // Don't modify perf_score for unfuzzed seeds
1119 if (!q->fuzz_level) break;
1120
1121 factor = q->fuzz_level / (afl->n_fuzz[q->n_fuzz_entry] + 1);
1122 break;
1123
1124 case QUAD:
1125 // Don't modify perf_score for unfuzzed seeds
1126 if (!q->fuzz_level) break;
1127
1128 factor =
1129 q->fuzz_level * q->fuzz_level / (afl->n_fuzz[q->n_fuzz_entry] + 1);
1130 break;
1131
1132 case MMOPT:
1133 /* -- this was a more complex setup, which is good, but competed with
1134 -- rare. the simpler algo however is good when rare is not.
1135 // the newer the entry, the higher the pref_score
1136 perf_score *= (1 + (double)((double)q->depth /
1137 (double)afl->queued_items));
1138 // with special focus on the last 8 entries
1139 if (afl->max_depth - q->depth < 8) perf_score *= (1 + ((8 -
1140 (afl->max_depth - q->depth)) / 5));
1141 */
1142 // put focus on the last 5 entries
1143 if (afl->max_depth - q->depth < 5) { perf_score *= 2; }
1144
1145 break;
1146
1147 case RARE:
1148
1149 // increase the score for every bitmap byte for which this entry
1150 // is the top contender
1151 perf_score += (q->tc_ref * 10);
1152 // the more often fuzz result paths are equal to this queue entry,
1153 // reduce its value
1154 perf_score *= (1 - (double)((double)afl->n_fuzz[q->n_fuzz_entry] /
1155 (double)afl->fsrv.total_execs));
1156
1157 break;
1158
1159 default:
1160 PFATAL("Unknown Power Schedule");
1161
1162 }
1163
1164 if (unlikely(afl->schedule >= EXPLOIT && afl->schedule <= QUAD)) {
1165
1166 if (factor > MAX_FACTOR) { factor = MAX_FACTOR; }
1167 perf_score *= factor / POWER_BETA;
1168
1169 }
1170
1171 // MOpt mode
1172 if (afl->limit_time_sig != 0 && afl->max_depth - q->depth < 3) {
1173
1174 perf_score *= 2;
1175
1176 } else if (afl->schedule != COE && perf_score < 1) {
1177
1178 // Add a lower bound to AFLFast's energy assignment strategies
1179 perf_score = 1;
1180
1181 }
1182
1183 /* Make sure that we don't go over limit. */
1184
1185 if (perf_score > afl->havoc_max_mult * 100) {
1186
1187 perf_score = afl->havoc_max_mult * 100;
1188
1189 }
1190
1191 return perf_score;
1192
1193 }
1194
1195 /* after a custom trim we need to reload the testcase from disk */
1196
queue_testcase_retake(afl_state_t * afl,struct queue_entry * q,u32 old_len)1197 inline void queue_testcase_retake(afl_state_t *afl, struct queue_entry *q,
1198 u32 old_len) {
1199
1200 if (likely(q->testcase_buf)) {
1201
1202 u32 len = q->len;
1203
1204 if (len != old_len) {
1205
1206 afl->q_testcase_cache_size = afl->q_testcase_cache_size + len - old_len;
1207 q->testcase_buf = (u8 *)realloc(q->testcase_buf, len);
1208
1209 if (unlikely(!q->testcase_buf)) {
1210
1211 PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len);
1212
1213 }
1214
1215 }
1216
1217 int fd = open((char *)q->fname, O_RDONLY);
1218
1219 if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", (char *)q->fname); }
1220
1221 ck_read(fd, q->testcase_buf, len, q->fname);
1222 close(fd);
1223
1224 }
1225
1226 }
1227
1228 /* after a normal trim we need to replace the testcase with the new data */
1229
queue_testcase_retake_mem(afl_state_t * afl,struct queue_entry * q,u8 * in,u32 len,u32 old_len)1230 inline void queue_testcase_retake_mem(afl_state_t *afl, struct queue_entry *q,
1231 u8 *in, u32 len, u32 old_len) {
1232
1233 if (likely(q->testcase_buf)) {
1234
1235 u32 is_same = in == q->testcase_buf;
1236
1237 if (likely(len != old_len)) {
1238
1239 u8 *ptr = (u8 *)realloc(q->testcase_buf, len);
1240
1241 if (likely(ptr)) {
1242
1243 q->testcase_buf = ptr;
1244 afl->q_testcase_cache_size = afl->q_testcase_cache_size + len - old_len;
1245
1246 }
1247
1248 }
1249
1250 if (unlikely(!is_same)) { memcpy(q->testcase_buf, in, len); }
1251
1252 }
1253
1254 }
1255
1256 /* Returns the testcase buf from the file behind this queue entry.
1257 Increases the refcount. */
1258
queue_testcase_get(afl_state_t * afl,struct queue_entry * q)1259 inline u8 *queue_testcase_get(afl_state_t *afl, struct queue_entry *q) {
1260
1261 u32 len = q->len;
1262
1263 /* first handle if no testcase cache is configured */
1264
1265 if (unlikely(!afl->q_testcase_max_cache_size)) {
1266
1267 u8 *buf;
1268
1269 if (unlikely(q == afl->queue_cur)) {
1270
1271 buf = (u8 *)afl_realloc((void **)&afl->testcase_buf, len);
1272
1273 } else {
1274
1275 buf = (u8 *)afl_realloc((void **)&afl->splicecase_buf, len);
1276
1277 }
1278
1279 if (unlikely(!buf)) {
1280
1281 PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len);
1282
1283 }
1284
1285 int fd = open((char *)q->fname, O_RDONLY);
1286
1287 if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", (char *)q->fname); }
1288
1289 ck_read(fd, buf, len, q->fname);
1290 close(fd);
1291 return buf;
1292
1293 }
1294
1295 /* now handle the testcase cache */
1296
1297 if (unlikely(!q->testcase_buf)) {
1298
1299 /* Buf not cached, let's load it */
1300 u32 tid = afl->q_testcase_max_cache_count;
1301 static u32 do_once = 0; // because even threaded we would want this. WIP
1302
1303 while (unlikely(
1304 afl->q_testcase_cache_size + len >= afl->q_testcase_max_cache_size ||
1305 afl->q_testcase_cache_count >= afl->q_testcase_max_cache_entries - 1)) {
1306
1307 /* We want a max number of entries to the cache that we learn.
1308 Very simple: once the cache is filled by size - that is the max. */
1309
1310 if (unlikely(afl->q_testcase_cache_size + len >=
1311 afl->q_testcase_max_cache_size &&
1312 (afl->q_testcase_cache_count <
1313 afl->q_testcase_max_cache_entries &&
1314 afl->q_testcase_max_cache_count <
1315 afl->q_testcase_max_cache_entries) &&
1316 !do_once)) {
1317
1318 if (afl->q_testcase_max_cache_count > afl->q_testcase_cache_count) {
1319
1320 afl->q_testcase_max_cache_entries =
1321 afl->q_testcase_max_cache_count + 1;
1322
1323 } else {
1324
1325 afl->q_testcase_max_cache_entries = afl->q_testcase_cache_count + 1;
1326
1327 }
1328
1329 do_once = 1;
1330 // release unneeded memory
1331 afl->q_testcase_cache = (struct queue_entry **)ck_realloc(
1332 afl->q_testcase_cache,
1333 (afl->q_testcase_max_cache_entries + 1) * sizeof(size_t));
1334
1335 }
1336
1337 /* Cache full. We neet to evict one or more to map one.
1338 Get a random one which is not in use */
1339
1340 do {
1341
1342 // if the cache (MB) is not enough for the queue then this gets
1343 // undesirable because q_testcase_max_cache_count grows sometimes
1344 // although the number of items in the cache will not change hence
1345 // more and more loops
1346 tid = rand_below(afl, afl->q_testcase_max_cache_count);
1347
1348 } while (afl->q_testcase_cache[tid] == NULL ||
1349
1350 afl->q_testcase_cache[tid] == afl->queue_cur);
1351
1352 struct queue_entry *old_cached = afl->q_testcase_cache[tid];
1353 free(old_cached->testcase_buf);
1354 old_cached->testcase_buf = NULL;
1355 afl->q_testcase_cache_size -= old_cached->len;
1356 afl->q_testcase_cache[tid] = NULL;
1357 --afl->q_testcase_cache_count;
1358 ++afl->q_testcase_evictions;
1359 if (tid < afl->q_testcase_smallest_free)
1360 afl->q_testcase_smallest_free = tid;
1361
1362 }
1363
1364 if (unlikely(tid >= afl->q_testcase_max_cache_entries)) {
1365
1366 // uh we were full, so now we have to search from start
1367 tid = afl->q_testcase_smallest_free;
1368
1369 }
1370
1371 // we need this while loop in case there were ever previous evictions but
1372 // not in this call.
1373 while (unlikely(afl->q_testcase_cache[tid] != NULL))
1374 ++tid;
1375
1376 /* Map the test case into memory. */
1377
1378 int fd = open((char *)q->fname, O_RDONLY);
1379
1380 if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", (char *)q->fname); }
1381
1382 q->testcase_buf = (u8 *)malloc(len);
1383
1384 if (unlikely(!q->testcase_buf)) {
1385
1386 PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len);
1387
1388 }
1389
1390 ck_read(fd, q->testcase_buf, len, q->fname);
1391 close(fd);
1392
1393 /* Register testcase as cached */
1394 afl->q_testcase_cache[tid] = q;
1395 afl->q_testcase_cache_size += len;
1396 ++afl->q_testcase_cache_count;
1397 if (likely(tid >= afl->q_testcase_max_cache_count)) {
1398
1399 afl->q_testcase_max_cache_count = tid + 1;
1400
1401 } else if (unlikely(tid == afl->q_testcase_smallest_free)) {
1402
1403 afl->q_testcase_smallest_free = tid + 1;
1404
1405 }
1406
1407 }
1408
1409 return q->testcase_buf;
1410
1411 }
1412
1413 /* Adds the new queue entry to the cache. */
1414
queue_testcase_store_mem(afl_state_t * afl,struct queue_entry * q,u8 * mem)1415 inline void queue_testcase_store_mem(afl_state_t *afl, struct queue_entry *q,
1416 u8 *mem) {
1417
1418 u32 len = q->len;
1419
1420 if (unlikely(afl->q_testcase_cache_size + len >=
1421 afl->q_testcase_max_cache_size ||
1422 afl->q_testcase_cache_count >=
1423 afl->q_testcase_max_cache_entries - 1)) {
1424
1425 // no space? will be loaded regularly later.
1426 return;
1427
1428 }
1429
1430 u32 tid;
1431
1432 if (unlikely(afl->q_testcase_max_cache_count >=
1433 afl->q_testcase_max_cache_entries)) {
1434
1435 // uh we were full, so now we have to search from start
1436 tid = afl->q_testcase_smallest_free;
1437
1438 } else {
1439
1440 tid = afl->q_testcase_max_cache_count;
1441
1442 }
1443
1444 while (unlikely(afl->q_testcase_cache[tid] != NULL))
1445 ++tid;
1446
1447 /* Map the test case into memory. */
1448
1449 q->testcase_buf = (u8 *)malloc(len);
1450
1451 if (unlikely(!q->testcase_buf)) {
1452
1453 PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len);
1454
1455 }
1456
1457 memcpy(q->testcase_buf, mem, len);
1458
1459 /* Register testcase as cached */
1460 afl->q_testcase_cache[tid] = q;
1461 afl->q_testcase_cache_size += len;
1462 ++afl->q_testcase_cache_count;
1463
1464 if (likely(tid >= afl->q_testcase_max_cache_count)) {
1465
1466 afl->q_testcase_max_cache_count = tid + 1;
1467
1468 } else if (unlikely(tid == afl->q_testcase_smallest_free)) {
1469
1470 afl->q_testcase_smallest_free = tid + 1;
1471
1472 }
1473
1474 }
1475
1476