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