1 /*
2 american fuzzy lop++ - redqueen implementation on top of cmplog
3 ---------------------------------------------------------------
4
5 Originally written by Michal Zalewski
6
7 Forkserver design by Jann Horn <jannhorn@googlemail.com>
8
9 Now maintained by by Marc Heuse <mh@mh-sec.de>,
10 Heiko Eißfeldt <heiko.eissfeldt@hexco.de> and
11 Andrea Fioraldi <andreafioraldi@gmail.com>
12
13 Copyright 2016, 2017 Google Inc. All rights reserved.
14 Copyright 2019-2022 AFLplusplus Project. All rights reserved.
15
16 Licensed under the Apache License, Version 2.0 (the "License");
17 you may not use this file except in compliance with the License.
18 You may obtain a copy of the License at:
19
20 https://www.apache.org/licenses/LICENSE-2.0
21
22 Shared code to handle the shared memory. This is used by the fuzzer
23 as well the other components like afl-tmin, afl-showmap, etc...
24
25 */
26
27 #include <limits.h>
28 #include "afl-fuzz.h"
29 #include "cmplog.h"
30
31 //#define _DEBUG
32 //#define CMPLOG_INTROSPECTION
33
34 // CMP attribute enum
35 enum {
36
37 IS_EQUAL = 1, // arithemtic equal comparison
38 IS_GREATER = 2, // arithmetic greater comparison
39 IS_LESSER = 4, // arithmetic lesser comparison
40 IS_FP = 8, // is a floating point, not an integer
41 /* --- below are internal settings, not from target cmplog */
42 IS_FP_MOD = 16, // arithemtic changed floating point
43 IS_INT_MOD = 32, // arithmetic changed interger
44 IS_TRANSFORM = 64 // transformed integer
45
46 };
47
48 // add to dictionary enum
49 // DEFAULT = 1, notTXT = 2, FOUND = 4, notSAME = 8
50 enum {
51
52 DICT_ADD_NEVER = 0,
53 DICT_ADD_NOTFOUND_SAME_TXT = 1,
54 DICT_ADD_NOTFOUND_SAME = 3,
55 DICT_ADD_FOUND_SAME_TXT = 5,
56 DICT_ADD_FOUND_SAME = 7,
57 DICT_ADD_NOTFOUND_TXT = 9,
58 DICT_ADD_NOTFOUND = 11,
59 DICT_ADD_FOUND_TXT = 13,
60 DICT_ADD_FOUND = 15,
61 DICT_ADD_ANY = DICT_ADD_FOUND
62
63 };
64
65 // CMPLOG LVL
66 enum {
67
68 LVL1 = 1, // Integer solving
69 LVL2 = 2, // unused except for setting the queue entry
70 LVL3 = 4 // expensive tranformations
71
72 };
73
74 #define DICT_ADD_STRATEGY DICT_ADD_FOUND_SAME
75
76 struct range {
77
78 u32 start;
79 u32 end;
80 struct range *next;
81 struct range *prev;
82 u8 ok;
83
84 };
85
86 static u32 hshape;
87 static u64 screen_update;
88 static u64 last_update;
89
add_range(struct range * ranges,u32 start,u32 end)90 static struct range *add_range(struct range *ranges, u32 start, u32 end) {
91
92 struct range *r = ck_alloc_nozero(sizeof(struct range));
93 r->start = start;
94 r->end = end;
95 r->next = ranges;
96 r->ok = 0;
97 if (likely(ranges)) ranges->prev = r;
98 return r;
99
100 }
101
pop_biggest_range(struct range ** ranges)102 static struct range *pop_biggest_range(struct range **ranges) {
103
104 struct range *r = *ranges;
105 struct range *rmax = NULL;
106 u32 max_size = 0;
107
108 while (r) {
109
110 if (!r->ok) {
111
112 u32 s = 1 + r->end - r->start;
113
114 if (s >= max_size) {
115
116 max_size = s;
117 rmax = r;
118
119 }
120
121 }
122
123 r = r->next;
124
125 }
126
127 return rmax;
128
129 }
130
131 #ifdef _DEBUG
132 // static int logging = 0;
dump(char * txt,u8 * buf,u32 len)133 static void dump(char *txt, u8 *buf, u32 len) {
134
135 u32 i;
136 fprintf(stderr, "DUMP %s %016llx ", txt, hash64(buf, len, HASH_CONST));
137 for (i = 0; i < len; i++)
138 fprintf(stderr, "%02x", buf[i]);
139 fprintf(stderr, "\n");
140
141 }
142
dump_file(char * path,char * name,u32 counter,u8 * buf,u32 len)143 static void dump_file(char *path, char *name, u32 counter, u8 *buf, u32 len) {
144
145 char fn[4096];
146 if (!path) path = ".";
147 snprintf(fn, sizeof(fn), "%s/%s%d", path, name, counter);
148 int fd = open(fn, O_RDWR | O_CREAT | O_TRUNC, 0644);
149 if (fd >= 0) {
150
151 write(fd, buf, len);
152 close(fd);
153
154 }
155
156 }
157
158 #endif
159
get_exec_checksum(afl_state_t * afl,u8 * buf,u32 len,u64 * cksum)160 static u8 get_exec_checksum(afl_state_t *afl, u8 *buf, u32 len, u64 *cksum) {
161
162 if (unlikely(common_fuzz_stuff(afl, buf, len))) { return 1; }
163
164 *cksum = hash64(afl->fsrv.trace_bits, afl->fsrv.map_size, HASH_CONST);
165
166 return 0;
167
168 }
169
170 /* replace everything with different values but stay in the same type */
type_replace(afl_state_t * afl,u8 * buf,u32 len)171 static void type_replace(afl_state_t *afl, u8 *buf, u32 len) {
172
173 u32 i;
174 u8 c;
175 for (i = 0; i < len; ++i) {
176
177 // wont help for UTF or non-latin charsets
178 do {
179
180 switch (buf[i]) {
181
182 case 'A' ... 'F':
183 c = 'A' + rand_below(afl, 1 + 'F' - 'A');
184 break;
185 case 'a' ... 'f':
186 c = 'a' + rand_below(afl, 1 + 'f' - 'a');
187 break;
188 case '0':
189 c = '1';
190 break;
191 case '1':
192 c = '0';
193 break;
194 case '2' ... '9':
195 c = '2' + rand_below(afl, 1 + '9' - '2');
196 break;
197 case 'G' ... 'Z':
198 c = 'G' + rand_below(afl, 1 + 'Z' - 'G');
199 break;
200 case 'g' ... 'z':
201 c = 'g' + rand_below(afl, 1 + 'z' - 'g');
202 break;
203 case '!' ... '*':
204 c = '!' + rand_below(afl, 1 + '*' - '!');
205 break;
206 case ',' ... '.':
207 c = ',' + rand_below(afl, 1 + '.' - ',');
208 break;
209 case ':' ... '@':
210 c = ':' + rand_below(afl, 1 + '@' - ':');
211 break;
212 case '[' ... '`':
213 c = '[' + rand_below(afl, 1 + '`' - '[');
214 break;
215 case '{' ... '~':
216 c = '{' + rand_below(afl, 1 + '~' - '{');
217 break;
218 case '+':
219 c = '/';
220 break;
221 case '/':
222 c = '+';
223 break;
224 case ' ':
225 c = '\t';
226 break;
227 case '\t':
228 c = ' ';
229 break;
230 case '\r':
231 c = '\n';
232 break;
233 case '\n':
234 c = '\r';
235 break;
236 case 0:
237 c = 1;
238 break;
239 case 1:
240 c = 0;
241 break;
242 case 0xff:
243 c = 0;
244 break;
245 default:
246 if (buf[i] < 32) {
247
248 c = (buf[i] ^ 0x1f);
249
250 } else {
251
252 c = (buf[i] ^ 0x7f); // we keep the highest bit
253
254 }
255
256 }
257
258 } while (c == buf[i]);
259
260 buf[i] = c;
261
262 }
263
264 }
265
colorization(afl_state_t * afl,u8 * buf,u32 len,struct tainted ** taints)266 static u8 colorization(afl_state_t *afl, u8 *buf, u32 len,
267 struct tainted **taints) {
268
269 struct range * ranges = add_range(NULL, 0, len - 1), *rng;
270 struct tainted *taint = NULL;
271 u8 * backup = ck_alloc_nozero(len);
272 u8 * changed = ck_alloc_nozero(len);
273
274 #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION)
275 u64 start_time = get_cur_time();
276 #endif
277
278 u64 orig_hit_cnt, new_hit_cnt, exec_cksum;
279 orig_hit_cnt = afl->queued_items + afl->saved_crashes;
280
281 afl->stage_name = "colorization";
282 afl->stage_short = "colorization";
283 afl->stage_max = (len << 1);
284 afl->stage_cur = 0;
285
286 // in colorization we do not classify counts, hence we have to calculate
287 // the original checksum.
288 if (unlikely(get_exec_checksum(afl, buf, len, &exec_cksum))) {
289
290 goto checksum_fail;
291
292 }
293
294 memcpy(backup, buf, len);
295 memcpy(changed, buf, len);
296 type_replace(afl, changed, len);
297
298 while ((rng = pop_biggest_range(&ranges)) != NULL &&
299 afl->stage_cur < afl->stage_max) {
300
301 u32 s = 1 + rng->end - rng->start;
302
303 memcpy(buf + rng->start, changed + rng->start, s);
304
305 u64 cksum = 0;
306 u64 start_us = get_cur_time_us();
307 if (unlikely(get_exec_checksum(afl, buf, len, &cksum))) {
308
309 goto checksum_fail;
310
311 }
312
313 u64 stop_us = get_cur_time_us();
314
315 /* Discard if the mutations change the path or if it is too decremental
316 in speed - how could the same path have a much different speed
317 though ...*/
318 if (cksum != exec_cksum ||
319 (unlikely(stop_us - start_us > 3 * afl->queue_cur->exec_us) &&
320 likely(!afl->fixed_seed))) {
321
322 memcpy(buf + rng->start, backup + rng->start, s);
323
324 if (s > 1) { // to not add 0 size ranges
325
326 ranges = add_range(ranges, rng->start, rng->start - 1 + s / 2);
327 ranges = add_range(ranges, rng->start + s / 2, rng->end);
328
329 }
330
331 if (ranges == rng) {
332
333 ranges = rng->next;
334 if (ranges) { ranges->prev = NULL; }
335
336 } else if (rng->next) {
337
338 rng->prev->next = rng->next;
339 rng->next->prev = rng->prev;
340
341 } else {
342
343 if (rng->prev) { rng->prev->next = NULL; }
344
345 }
346
347 free(rng);
348
349 } else {
350
351 rng->ok = 1;
352
353 }
354
355 if (++afl->stage_cur % screen_update == 0) { show_stats(afl); };
356
357 }
358
359 rng = ranges;
360 while (rng) {
361
362 rng = rng->next;
363
364 }
365
366 u32 i = 1;
367 u32 positions = 0;
368 while (i) {
369
370 restart:
371 i = 0;
372 struct range *r = NULL;
373 u32 pos = (u32)-1;
374 rng = ranges;
375
376 while (rng) {
377
378 if (rng->ok == 1 && rng->start < pos) {
379
380 if (taint && taint->pos + taint->len == rng->start) {
381
382 taint->len += (1 + rng->end - rng->start);
383 positions += (1 + rng->end - rng->start);
384 rng->ok = 2;
385 goto restart;
386
387 } else {
388
389 r = rng;
390 pos = rng->start;
391
392 }
393
394 }
395
396 rng = rng->next;
397
398 }
399
400 if (r) {
401
402 struct tainted *t = ck_alloc_nozero(sizeof(struct tainted));
403 t->pos = r->start;
404 t->len = 1 + r->end - r->start;
405 positions += (1 + r->end - r->start);
406 if (likely(taint)) { taint->prev = t; }
407 t->next = taint;
408 t->prev = NULL;
409 taint = t;
410 r->ok = 2;
411 i = 1;
412
413 }
414
415 }
416
417 /* temporary: clean ranges */
418 while (ranges) {
419
420 rng = ranges;
421 ranges = rng->next;
422 ck_free(rng);
423 rng = NULL;
424
425 }
426
427 new_hit_cnt = afl->queued_items + afl->saved_crashes;
428
429 #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION)
430 FILE *f = stderr;
431 #ifndef _DEBUG
432 if (afl->not_on_tty) {
433
434 char fn[4096];
435 snprintf(fn, sizeof(fn), "%s/introspection_cmplog.txt", afl->out_dir);
436 f = fopen(fn, "a");
437
438 }
439
440 #endif
441
442 if (f) {
443
444 fprintf(
445 f,
446 "Colorization: fname=%s len=%u ms=%llu result=%u execs=%u found=%llu "
447 "taint=%u ascii=%u auto_extra_before=%u\n",
448 afl->queue_cur->fname, len, get_cur_time() - start_time,
449 afl->queue_cur->colorized, afl->stage_cur, new_hit_cnt - orig_hit_cnt,
450 positions, afl->queue_cur->is_ascii ? 1 : 0, afl->a_extras_cnt);
451
452 #ifndef _DEBUG
453 if (afl->not_on_tty) { fclose(f); }
454 #endif
455
456 }
457
458 #endif
459
460 if (taint) {
461
462 if (afl->colorize_success && afl->cmplog_lvl < 3 &&
463 (positions > CMPLOG_POSITIONS_MAX && len / positions == 1 &&
464 afl->active_items / afl->colorize_success > CMPLOG_CORPUS_PERCENT)) {
465
466 #ifdef _DEBUG
467 fprintf(stderr, "Colorization unsatisfactory\n");
468 #endif
469
470 *taints = NULL;
471
472 struct tainted *t;
473 while (taint) {
474
475 t = taint->next;
476 ck_free(taint);
477 taint = t;
478
479 }
480
481 } else {
482
483 *taints = taint;
484 ++afl->colorize_success;
485
486 }
487
488 }
489
490 afl->stage_finds[STAGE_COLORIZATION] += new_hit_cnt - orig_hit_cnt;
491 afl->stage_cycles[STAGE_COLORIZATION] += afl->stage_cur;
492 ck_free(backup);
493 ck_free(changed);
494
495 return 0;
496
497 checksum_fail:
498 while (ranges) {
499
500 rng = ranges;
501 ranges = rng->next;
502 ck_free(rng);
503 rng = NULL;
504
505 }
506
507 ck_free(backup);
508 ck_free(changed);
509
510 return 1;
511
512 }
513
514 ///// Input to State replacement
515
its_fuzz(afl_state_t * afl,u8 * buf,u32 len,u8 * status)516 static u8 its_fuzz(afl_state_t *afl, u8 *buf, u32 len, u8 *status) {
517
518 u64 orig_hit_cnt, new_hit_cnt;
519
520 orig_hit_cnt = afl->queued_items + afl->saved_crashes;
521
522 #ifdef _DEBUG
523 dump("DATA", buf, len);
524 #endif
525
526 if (unlikely(common_fuzz_stuff(afl, buf, len))) { return 1; }
527
528 new_hit_cnt = afl->queued_items + afl->saved_crashes;
529
530 if (unlikely(new_hit_cnt != orig_hit_cnt)) {
531
532 #ifdef _DEBUG
533 fprintf(stderr, "NEW FIND\n");
534 #endif
535 *status = 1;
536
537 } else {
538
539 *status = 2;
540
541 }
542
543 return 0;
544
545 }
546
547 //#ifdef CMPLOG_SOLVE_TRANSFORM
strntoll(const char * str,size_t sz,char ** end,int base,long long * out)548 static int strntoll(const char *str, size_t sz, char **end, int base,
549 long long *out) {
550
551 char buf[64];
552 long long ret;
553 const char *beg = str;
554
555 if (!str || !sz) { return 1; }
556
557 for (; beg && sz && *beg == ' '; beg++, sz--) {};
558
559 if (!sz) return 1;
560 if (sz >= sizeof(buf)) sz = sizeof(buf) - 1;
561
562 memcpy(buf, beg, sz);
563 buf[sz] = '\0';
564 ret = strtoll(buf, end, base);
565 if ((ret == LLONG_MIN || ret == LLONG_MAX) && errno == ERANGE) return 1;
566 if (end) *end = (char *)beg + (*end - buf);
567 *out = ret;
568
569 return 0;
570
571 }
572
strntoull(const char * str,size_t sz,char ** end,int base,unsigned long long * out)573 static int strntoull(const char *str, size_t sz, char **end, int base,
574 unsigned long long *out) {
575
576 char buf[64];
577 unsigned long long ret;
578 const char * beg = str;
579
580 if (!str || !sz) { return 1; }
581
582 for (; beg && sz && *beg == ' '; beg++, sz--)
583 ;
584
585 if (!sz) return 1;
586 if (sz >= sizeof(buf)) sz = sizeof(buf) - 1;
587
588 memcpy(buf, beg, sz);
589 buf[sz] = '\0';
590 ret = strtoull(buf, end, base);
591 if (ret == ULLONG_MAX && errno == ERANGE) return 1;
592 if (end) *end = (char *)beg + (*end - buf);
593 *out = ret;
594
595 return 0;
596
597 }
598
599 static u8 hex_table_up[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
600 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
601 static u8 hex_table_low[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
602 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
603 static u8 hex_table[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0,
604 0, 0, 0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0,
605 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
606 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15};
607
608 // tests 2 bytes at location
is_hex(const char * str)609 static int is_hex(const char *str) {
610
611 u32 i;
612
613 for (i = 0; i < 2; i++) {
614
615 switch (str[i]) {
616
617 case '0' ... '9':
618 case 'A' ... 'F':
619 case 'a' ... 'f':
620 break;
621 default:
622 return 0;
623
624 }
625
626 }
627
628 return 1;
629
630 }
631
632 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
633 // tests 4 bytes at location
is_base64(const char * str)634 static int is_base64(const char *str) {
635
636 u32 i;
637
638 for (i = 0; i < 4; i++) {
639
640 switch (str[i]) {
641
642 case '0' ... '9':
643 case 'A' ... 'Z':
644 case 'a' ... 'z':
645 case '+':
646 case '/':
647 case '=':
648 break;
649 default:
650 return 0;
651
652 }
653
654 }
655
656 return 1;
657
658 }
659
660 static u8 base64_encode_table[] =
661 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
662 static u8 base64_decode_table[] = {
663
664 62, 0, 0, 0, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 0,
665 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
666 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
667 0, 0, 0, 0, 0, 0, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
668 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51};
669
from_base64(u8 * src,u8 * dst,u32 dst_len)670 static u32 from_base64(u8 *src, u8 *dst, u32 dst_len) {
671
672 u32 i, j, v;
673 u32 len = ((dst_len / 3) << 2);
674 u32 ret = 0;
675
676 for (i = 0, j = 0; i < len; i += 4, j += 3) {
677
678 v = base64_decode_table[src[i] - 43];
679 v = (v << 6) | base64_decode_table[src[i + 1] - 43];
680 v = src[i + 2] == '=' ? v << 6
681 : (v << 6) | base64_decode_table[src[i + 2] - 43];
682 v = src[i + 3] == '=' ? v << 6
683 : (v << 6) | base64_decode_table[src[i + 3] - 43];
684
685 dst[j] = (v >> 16) & 0xFF;
686 ++ret;
687
688 if (src[i + 2] != '=') {
689
690 dst[j + 1] = (v >> 8) & 0xFF;
691 ++ret;
692
693 }
694
695 if (src[i + 3] != '=') {
696
697 dst[j + 2] = v & 0xFF;
698 ++ret;
699
700 }
701
702 }
703
704 return ret;
705
706 }
707
to_base64(u8 * src,u8 * dst,u32 dst_len)708 static void to_base64(u8 *src, u8 *dst, u32 dst_len) {
709
710 u32 i, j, v;
711 u32 len = (dst_len >> 2) * 3;
712
713 for (i = 0, j = 0; i < len; i += 3, j += 4) {
714
715 v = src[i];
716 v = i + 1 < len ? v << 8 | src[i + 1] : v << 8;
717 v = i + 2 < len ? v << 8 | src[i + 2] : v << 8;
718
719 dst[j] = base64_encode_table[(v >> 18) & 0x3F];
720 dst[j + 1] = base64_encode_table[(v >> 12) & 0x3F];
721 if (i + 1 < len) {
722
723 dst[j + 2] = base64_encode_table[(v >> 6) & 0x3F];
724
725 } else {
726
727 dst[j + 2] = '=';
728
729 }
730
731 if (i + 2 < len) {
732
733 dst[j + 3] = base64_encode_table[v & 0x3F];
734
735 } else {
736
737 dst[j + 3] = '=';
738
739 }
740
741 }
742
743 }
744
745 #endif
746
747 //#endif
748
cmp_extend_encoding(afl_state_t * afl,struct cmp_header * h,u64 pattern,u64 repl,u64 o_pattern,u64 changed_val,u8 attr,u32 idx,u32 taint_len,u8 * orig_buf,u8 * buf,u8 * cbuf,u32 len,u8 do_reverse,u8 lvl,u8 * status)749 static u8 cmp_extend_encoding(afl_state_t *afl, struct cmp_header *h,
750 u64 pattern, u64 repl, u64 o_pattern,
751 u64 changed_val, u8 attr, u32 idx, u32 taint_len,
752 u8 *orig_buf, u8 *buf, u8 *cbuf, u32 len,
753 u8 do_reverse, u8 lvl, u8 *status) {
754
755 u64 *buf_64 = (u64 *)&buf[idx];
756 u32 *buf_32 = (u32 *)&buf[idx];
757 u16 *buf_16 = (u16 *)&buf[idx];
758 u8 * buf_8 = &buf[idx];
759 u64 *o_buf_64 = (u64 *)&orig_buf[idx];
760 u32 *o_buf_32 = (u32 *)&orig_buf[idx];
761 u16 *o_buf_16 = (u16 *)&orig_buf[idx];
762 u8 * o_buf_8 = &orig_buf[idx];
763
764 u32 its_len = MIN(len - idx, taint_len);
765
766 if (afl->fsrv.total_execs - last_update > screen_update) {
767
768 show_stats(afl);
769 last_update = afl->fsrv.total_execs;
770
771 }
772
773 // fprintf(stderr,
774 // "Encode: %llx->%llx into %llx(<-%llx) at idx=%u "
775 // "taint_len=%u shape=%u attr=%u\n",
776 // o_pattern, pattern, repl, changed_val, idx, taint_len,
777 // hshape, attr);
778
779 //#ifdef CMPLOG_SOLVE_TRANSFORM
780 // reverse atoi()/strnu?toll() is expensive, so we only to it in lvl 3
781 if (afl->cmplog_enable_transform && (lvl & LVL3)) {
782
783 u8 * endptr;
784 u8 use_num = 0, use_unum = 0;
785 unsigned long long unum;
786 long long num;
787
788 if (afl->queue_cur->is_ascii) {
789
790 endptr = buf_8;
791 if (strntoll(buf_8, len - idx, (char **)&endptr, 0, &num)) {
792
793 if (!strntoull(buf_8, len - idx, (char **)&endptr, 0, &unum))
794 use_unum = 1;
795
796 } else
797
798 use_num = 1;
799
800 }
801
802 #ifdef _DEBUG
803 if (idx == 0)
804 fprintf(stderr, "ASCII is=%u use_num=%u use_unum=%u idx=%u %llx==%llx\n",
805 afl->queue_cur->is_ascii, use_num, use_unum, idx, num, pattern);
806 #endif
807
808 // num is likely not pattern as atoi("AAA") will be zero...
809 if (use_num && ((u64)num == pattern || !num)) {
810
811 u8 tmp_buf[32];
812 size_t num_len = snprintf(tmp_buf, sizeof(tmp_buf), "%lld", repl);
813 size_t old_len = endptr - buf_8;
814
815 u8 *new_buf = afl_realloc((void **)&afl->out_scratch_buf, len + num_len);
816 if (unlikely(!new_buf)) { PFATAL("alloc"); }
817
818 memcpy(new_buf, buf, idx);
819 memcpy(new_buf + idx, tmp_buf, num_len);
820 memcpy(new_buf + idx + num_len, buf_8 + old_len, len - idx - old_len);
821
822 if (new_buf[idx + num_len] >= '0' && new_buf[idx + num_len] <= '9') {
823
824 new_buf[idx + num_len] = ' ';
825
826 }
827
828 if (unlikely(its_fuzz(afl, new_buf, len, status))) { return 1; }
829
830 } else if (use_unum && (unum == pattern || !unum)) {
831
832 u8 tmp_buf[32];
833 size_t num_len = snprintf(tmp_buf, sizeof(tmp_buf), "%llu", repl);
834 size_t old_len = endptr - buf_8;
835
836 u8 *new_buf = afl_realloc((void **)&afl->out_scratch_buf, len + num_len);
837 if (unlikely(!new_buf)) { PFATAL("alloc"); }
838
839 memcpy(new_buf, buf, idx);
840 memcpy(new_buf + idx, tmp_buf, num_len);
841 memcpy(new_buf + idx + num_len, buf_8 + old_len, len - idx - old_len);
842
843 if (new_buf[idx + num_len] >= '0' && new_buf[idx + num_len] <= '9') {
844
845 new_buf[idx + num_len] = ' ';
846
847 }
848
849 if (unlikely(its_fuzz(afl, new_buf, len, status))) { return 1; }
850
851 }
852
853 // Try to identify transform magic
854 if (pattern != o_pattern && repl == changed_val && attr <= IS_EQUAL) {
855
856 u64 b_val, o_b_val, mask;
857 u8 bytes;
858
859 switch (hshape) {
860
861 case 0:
862 case 1:
863 bytes = 1;
864 break;
865 case 2:
866 bytes = 2;
867 break;
868 case 3:
869 case 4:
870 bytes = 4;
871 break;
872 default:
873 bytes = 8;
874
875 }
876
877 // necessary for preventing heap access overflow
878 bytes = MIN(bytes, len - idx);
879
880 switch (bytes) {
881
882 case 0: // cannot happen
883 b_val = o_b_val = mask = 0; // keep the linters happy
884 break;
885 case 1: {
886
887 u8 *ptr = (u8 *)&buf[idx];
888 u8 *o_ptr = (u8 *)&orig_buf[idx];
889 b_val = (u64)(*ptr);
890 o_b_val = (u64)(*o_ptr % 0x100);
891 mask = 0xff;
892 break;
893
894 }
895
896 case 2:
897 case 3: {
898
899 u16 *ptr = (u16 *)&buf[idx];
900 u16 *o_ptr = (u16 *)&orig_buf[idx];
901 b_val = (u64)(*ptr);
902 o_b_val = (u64)(*o_ptr);
903 mask = 0xffff;
904 break;
905
906 }
907
908 case 4:
909 case 5:
910 case 6:
911 case 7: {
912
913 u32 *ptr = (u32 *)&buf[idx];
914 u32 *o_ptr = (u32 *)&orig_buf[idx];
915 b_val = (u64)(*ptr);
916 o_b_val = (u64)(*o_ptr);
917 mask = 0xffffffff;
918 break;
919
920 }
921
922 default: {
923
924 u64 *ptr = (u64 *)&buf[idx];
925 u64 *o_ptr = (u64 *)&orig_buf[idx];
926 b_val = (u64)(*ptr);
927 o_b_val = (u64)(*o_ptr);
928 mask = 0xffffffffffffffff;
929
930 }
931
932 }
933
934 // test for arithmetic, eg. "if ((user_val - 0x1111) == 0x1234) ..."
935 s64 diff = pattern - b_val;
936 s64 o_diff = o_pattern - o_b_val;
937 /* fprintf(stderr, "DIFF1 idx=%03u shape=%02u %llx-%llx=%lx\n", idx,
938 hshape, o_pattern, o_b_val, o_diff);
939 fprintf(stderr, "DIFF1 %016llx %llx-%llx=%lx\n", repl, pattern,
940 b_val, diff); */
941 if (diff == o_diff && diff) {
942
943 // this could be an arithmetic transformation
944
945 u64 new_repl = (u64)((s64)repl - diff);
946 // fprintf(stderr, "SAME DIFF %llx->%llx\n", repl, new_repl);
947
948 if (unlikely(cmp_extend_encoding(
949 afl, h, pattern, new_repl, o_pattern, repl, IS_TRANSFORM, idx,
950 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
951
952 return 1;
953
954 }
955
956 // if (*status == 1) { fprintf(stderr, "FOUND!\n"); }
957
958 }
959
960 // test for XOR, eg. "if ((user_val ^ 0xabcd) == 0x1234) ..."
961 if (*status != 1) {
962
963 diff = pattern ^ b_val;
964 s64 o_diff = o_pattern ^ o_b_val;
965
966 /* fprintf(stderr, "DIFF2 idx=%03u shape=%02u %llx-%llx=%lx\n",
967 idx, hshape, o_pattern, o_b_val, o_diff);
968 fprintf(stderr,
969 "DIFF2 %016llx %llx-%llx=%lx\n", repl, pattern, b_val, diff);
970 */
971 if (diff == o_diff && diff) {
972
973 // this could be a XOR transformation
974
975 u64 new_repl = (u64)((s64)repl ^ diff);
976 // fprintf(stderr, "SAME DIFF %llx->%llx\n", repl, new_repl);
977
978 if (unlikely(cmp_extend_encoding(
979 afl, h, pattern, new_repl, o_pattern, repl, IS_TRANSFORM, idx,
980 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
981
982 return 1;
983
984 }
985
986 // if (*status == 1) { fprintf(stderr, "FOUND!\n"); }
987
988 }
989
990 }
991
992 // test for to lowercase, eg. "new_val = (user_val | 0x2020) ..."
993 if (*status != 1) {
994
995 if ((b_val | (0x2020202020202020 & mask)) == (pattern & mask)) {
996
997 diff = 1;
998
999 } else {
1000
1001 diff = 0;
1002
1003 }
1004
1005 if ((o_b_val | (0x2020202020202020 & mask)) == (o_pattern & mask)) {
1006
1007 o_diff = 1;
1008
1009 } else {
1010
1011 diff = 0;
1012
1013 }
1014
1015 /* fprintf(stderr, "DIFF3 idx=%03u shape=%02u %llx-%llx=%lx\n",
1016 idx, hshape, o_pattern, o_b_val, o_diff);
1017 fprintf(stderr,
1018 "DIFF3 %016llx %llx-%llx=%lx\n", repl, pattern, b_val, diff);
1019 */
1020 if (o_diff && diff) {
1021
1022 // this could be a lower to upper
1023
1024 u64 new_repl = (repl & (0x5f5f5f5f5f5f5f5f & mask));
1025 // fprintf(stderr, "SAME DIFF %llx->%llx\n", repl, new_repl);
1026
1027 if (unlikely(cmp_extend_encoding(
1028 afl, h, pattern, new_repl, o_pattern, repl, IS_TRANSFORM, idx,
1029 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1030
1031 return 1;
1032
1033 }
1034
1035 // if (*status == 1) { fprintf(stderr, "FOUND!\n"); }
1036
1037 }
1038
1039 }
1040
1041 // test for to uppercase, eg. "new_val = (user_val | 0x5f5f) ..."
1042 if (*status != 1) {
1043
1044 if ((b_val & (0x5f5f5f5f5f5f5f5f & mask)) == (pattern & mask)) {
1045
1046 diff = 1;
1047
1048 } else {
1049
1050 diff = 0;
1051
1052 }
1053
1054 if ((o_b_val & (0x5f5f5f5f5f5f5f5f & mask)) == (o_pattern & mask)) {
1055
1056 o_diff = 1;
1057
1058 } else {
1059
1060 o_diff = 0;
1061
1062 }
1063
1064 /* fprintf(stderr, "DIFF4 idx=%03u shape=%02u %llx-%llx=%lx\n",
1065 idx, hshape, o_pattern, o_b_val, o_diff);
1066 fprintf(stderr,
1067 "DIFF4 %016llx %llx-%llx=%lx\n", repl, pattern, b_val, diff);
1068 */
1069 if (o_diff && diff) {
1070
1071 // this could be a lower to upper
1072
1073 u64 new_repl = (repl | (0x2020202020202020 & mask));
1074 // fprintf(stderr, "SAME DIFF %llx->%llx\n", repl, new_repl);
1075
1076 if (unlikely(cmp_extend_encoding(
1077 afl, h, pattern, new_repl, o_pattern, repl, IS_TRANSFORM, idx,
1078 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1079
1080 return 1;
1081
1082 }
1083
1084 // if (*status == 1) { fprintf(stderr, "FOUND!\n"); }
1085
1086 }
1087
1088 }
1089
1090 *status = 0;
1091
1092 }
1093
1094 }
1095
1096 //#endif
1097
1098 // we only allow this for ascii2integer (above) so leave if this is the case
1099 if (unlikely(pattern == o_pattern)) { return 0; }
1100
1101 if ((lvl & LVL1) || attr >= IS_FP_MOD) {
1102
1103 if (hshape >= 8 && *status != 1) {
1104
1105 // if (its_len >= 8)
1106 // fprintf(stderr,
1107 // "TestU64: %u>=8 (idx=%u attr=%u) %llx==%llx"
1108 // " %llx==%llx <= %llx<-%llx\n",
1109 // its_len, idx, attr, *buf_64, pattern, *o_buf_64, o_pattern,
1110 // repl, changed_val);
1111
1112 // if this is an fcmp (attr & 8 == 8) then do not compare the patterns -
1113 // due to a bug in llvm dynamic float bitcasts do not work :(
1114 // the value 16 means this is a +- 1.0 test case
1115 if (its_len >= 8 && ((*buf_64 == pattern && *o_buf_64 == o_pattern) ||
1116 attr >= IS_FP_MOD)) {
1117
1118 u64 tmp_64 = *buf_64;
1119 *buf_64 = repl;
1120 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
1121 #ifdef CMPLOG_COMBINE
1122 if (*status == 1) { memcpy(cbuf + idx, buf_64, 8); }
1123 #endif
1124 *buf_64 = tmp_64;
1125
1126 // fprintf(stderr, "Status=%u\n", *status);
1127
1128 }
1129
1130 // reverse encoding
1131 if (do_reverse && *status != 1) {
1132
1133 if (unlikely(cmp_extend_encoding(afl, h, SWAP64(pattern), SWAP64(repl),
1134 SWAP64(o_pattern), SWAP64(changed_val),
1135 attr, idx, taint_len, orig_buf, buf,
1136 cbuf, len, 0, lvl, status))) {
1137
1138 return 1;
1139
1140 }
1141
1142 }
1143
1144 }
1145
1146 if (hshape >= 4 && *status != 1) {
1147
1148 // if (its_len >= 4 && (attr <= 1 || attr >= 8))
1149 // fprintf(stderr,
1150 // "TestU32: %u>=4 (idx=%u attr=%u) %x==%x"
1151 // " %x==%x <= %x<-%x\n",
1152 // its_len, idx, attr, *buf_32, (u32)pattern, *o_buf_32,
1153 // (u32)o_pattern, (u32)repl, (u32)changed_val);
1154
1155 if (its_len >= 4 &&
1156 ((*buf_32 == (u32)pattern && *o_buf_32 == (u32)o_pattern) ||
1157 attr >= IS_FP_MOD)) {
1158
1159 u32 tmp_32 = *buf_32;
1160 *buf_32 = (u32)repl;
1161 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
1162 #ifdef CMPLOG_COMBINE
1163 if (*status == 1) { memcpy(cbuf + idx, buf_32, 4); }
1164 #endif
1165 *buf_32 = tmp_32;
1166
1167 // fprintf(stderr, "Status=%u\n", *status);
1168
1169 }
1170
1171 // reverse encoding
1172 if (do_reverse && *status != 1) {
1173
1174 if (unlikely(cmp_extend_encoding(afl, h, SWAP32(pattern), SWAP32(repl),
1175 SWAP32(o_pattern), SWAP32(changed_val),
1176 attr, idx, taint_len, orig_buf, buf,
1177 cbuf, len, 0, lvl, status))) {
1178
1179 return 1;
1180
1181 }
1182
1183 }
1184
1185 }
1186
1187 if (hshape >= 2 && *status != 1) {
1188
1189 if (its_len >= 2 &&
1190 ((*buf_16 == (u16)pattern && *o_buf_16 == (u16)o_pattern) ||
1191 attr >= IS_FP_MOD)) {
1192
1193 u16 tmp_16 = *buf_16;
1194 *buf_16 = (u16)repl;
1195 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
1196 #ifdef CMPLOG_COMBINE
1197 if (*status == 1) { memcpy(cbuf + idx, buf_16, 2); }
1198 #endif
1199 *buf_16 = tmp_16;
1200
1201 }
1202
1203 // reverse encoding
1204 if (do_reverse && *status != 1) {
1205
1206 if (unlikely(cmp_extend_encoding(afl, h, SWAP16(pattern), SWAP16(repl),
1207 SWAP16(o_pattern), SWAP16(changed_val),
1208 attr, idx, taint_len, orig_buf, buf,
1209 cbuf, len, 0, lvl, status))) {
1210
1211 return 1;
1212
1213 }
1214
1215 }
1216
1217 }
1218
1219 if (*status != 1) { // u8
1220
1221 // if (its_len >= 1)
1222 // fprintf(stderr,
1223 // "TestU8: %u>=1 (idx=%u attr=%u) %x==%x %x==%x <= %x<-%x\n",
1224 // its_len, idx, attr, *buf_8, (u8)pattern, *o_buf_8,
1225 // (u8)o_pattern, (u8)repl, (u8)changed_val);
1226
1227 if (its_len >= 1 &&
1228 ((*buf_8 == (u8)pattern && *o_buf_8 == (u8)o_pattern) ||
1229 attr >= IS_FP_MOD)) {
1230
1231 u8 tmp_8 = *buf_8;
1232 *buf_8 = (u8)repl;
1233 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
1234 #ifdef CMPLOG_COMBINE
1235 if (*status == 1) { cbuf[idx] = *buf_8; }
1236 #endif
1237 *buf_8 = tmp_8;
1238
1239 }
1240
1241 }
1242
1243 }
1244
1245 // here we add and subract 1 from the value, but only if it is not an
1246 // == or != comparison
1247 // Bits: 1 = Equal, 2 = Greater, 4 = Lesser, 8 = Float
1248 // 16 = modified float, 32 = modified integer (modified = wont match
1249 // in original buffer)
1250
1251 //#ifdef CMPLOG_SOLVE_ARITHMETIC
1252 if (!afl->cmplog_enable_arith || lvl < LVL3 || attr == IS_TRANSFORM) {
1253
1254 return 0;
1255
1256 }
1257
1258 if (!(attr & (IS_GREATER | IS_LESSER)) || hshape < 4) { return 0; }
1259
1260 // transform >= to < and <= to >
1261 if ((attr & IS_EQUAL) && (attr & (IS_GREATER | IS_LESSER))) {
1262
1263 if (attr & 2) {
1264
1265 attr += 2;
1266
1267 } else {
1268
1269 attr -= 2;
1270
1271 }
1272
1273 }
1274
1275 // lesser/greater FP comparison
1276 if (attr >= IS_FP && attr < IS_FP_MOD) {
1277
1278 u64 repl_new;
1279
1280 if (attr & IS_GREATER) {
1281
1282 if (hshape == 4 && its_len >= 4) {
1283
1284 float *f = (float *)&repl;
1285 float g = *f;
1286 g += 1.0;
1287 u32 *r = (u32 *)&g;
1288 repl_new = (u32)*r;
1289
1290 } else if (hshape == 8 && its_len >= 8) {
1291
1292 double *f = (double *)&repl;
1293 double g = *f;
1294 g += 1.0;
1295
1296 u64 *r = (u64 *)&g;
1297 repl_new = *r;
1298
1299 } else {
1300
1301 return 0;
1302
1303 }
1304
1305 changed_val = repl_new;
1306
1307 if (unlikely(cmp_extend_encoding(
1308 afl, h, pattern, repl_new, o_pattern, changed_val, 16, idx,
1309 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1310
1311 return 1;
1312
1313 }
1314
1315 } else {
1316
1317 if (hshape == 4) {
1318
1319 float *f = (float *)&repl;
1320 float g = *f;
1321 g -= 1.0;
1322 u32 *r = (u32 *)&g;
1323 repl_new = (u32)*r;
1324
1325 } else if (hshape == 8) {
1326
1327 double *f = (double *)&repl;
1328 double g = *f;
1329 g -= 1.0;
1330 u64 *r = (u64 *)&g;
1331 repl_new = *r;
1332
1333 } else {
1334
1335 return 0;
1336
1337 }
1338
1339 changed_val = repl_new;
1340
1341 if (unlikely(cmp_extend_encoding(
1342 afl, h, pattern, repl_new, o_pattern, changed_val, 16, idx,
1343 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1344
1345 return 1;
1346
1347 }
1348
1349 }
1350
1351 // transform double to float, llvm likes to do that internally ...
1352 if (hshape == 8 && its_len >= 4) {
1353
1354 double *f = (double *)&repl;
1355 float g = (float)*f;
1356 repl_new = 0;
1357 #if (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1358 memcpy((char *)&repl_new, (char *)&g, 4);
1359 #else
1360 memcpy(((char *)&repl_new) + 4, (char *)&g, 4);
1361 #endif
1362 changed_val = repl_new;
1363 hshape = 4; // modify shape
1364
1365 // fprintf(stderr, "DOUBLE2FLOAT %llx\n", repl_new);
1366
1367 if (unlikely(cmp_extend_encoding(
1368 afl, h, pattern, repl_new, o_pattern, changed_val, 16, idx,
1369 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1370
1371 hshape = 8; // recover shape
1372 return 1;
1373
1374 }
1375
1376 hshape = 8; // recover shape
1377
1378 }
1379
1380 }
1381
1382 else if (attr < IS_FP) {
1383
1384 // lesser/greater integer comparison
1385
1386 u64 repl_new;
1387
1388 if (attr & IS_GREATER) {
1389
1390 repl_new = repl + 1;
1391 changed_val = repl_new;
1392 if (unlikely(cmp_extend_encoding(
1393 afl, h, pattern, repl_new, o_pattern, changed_val, 32, idx,
1394 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1395
1396 return 1;
1397
1398 }
1399
1400 } else {
1401
1402 repl_new = repl - 1;
1403 changed_val = repl_new;
1404 if (unlikely(cmp_extend_encoding(
1405 afl, h, pattern, repl_new, o_pattern, changed_val, 32, idx,
1406 taint_len, orig_buf, buf, cbuf, len, 1, lvl, status))) {
1407
1408 return 1;
1409
1410 }
1411
1412 }
1413
1414 }
1415
1416 //#endif /*
1417 // CMPLOG_SOLVE_ARITHMETIC
1418
1419 return 0;
1420
1421 }
1422
1423 #ifdef WORD_SIZE_64
1424
cmp_extend_encodingN(afl_state_t * afl,struct cmp_header * h,u128 pattern,u128 repl,u128 o_pattern,u128 changed_val,u8 attr,u32 idx,u32 taint_len,u8 * orig_buf,u8 * buf,u8 * cbuf,u32 len,u8 do_reverse,u8 lvl,u8 * status)1425 static u8 cmp_extend_encodingN(afl_state_t *afl, struct cmp_header *h,
1426 u128 pattern, u128 repl, u128 o_pattern,
1427 u128 changed_val, u8 attr, u32 idx,
1428 u32 taint_len, u8 *orig_buf, u8 *buf, u8 *cbuf,
1429 u32 len, u8 do_reverse, u8 lvl, u8 *status) {
1430
1431 if (afl->fsrv.total_execs - last_update > screen_update) {
1432
1433 show_stats(afl);
1434 last_update = afl->fsrv.total_execs;
1435
1436 }
1437
1438 u8 *ptr = (u8 *)&buf[idx];
1439 u8 *o_ptr = (u8 *)&orig_buf[idx];
1440 u8 *p = (u8 *)&pattern;
1441 u8 *o_p = (u8 *)&o_pattern;
1442 u8 *r = (u8 *)&repl;
1443 u8 backup[16];
1444 u32 its_len = MIN(len - idx, taint_len);
1445 #if (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1446 size_t off = 0;
1447 #else
1448 size_t off = 16 - hshape;
1449 #endif
1450
1451 if (its_len >= hshape) {
1452
1453 #ifdef _DEBUG
1454 fprintf(stderr, "TestUN: %u>=%u (len=%u idx=%u attr=%u off=%lu) (%u) ",
1455 its_len, hshape, len, idx, attr, off, do_reverse);
1456 u32 i;
1457 u8 *o_r = (u8 *)&changed_val;
1458 for (i = 0; i < hshape; i++)
1459 fprintf(stderr, "%02x", ptr[i]);
1460 fprintf(stderr, "==");
1461 for (i = 0; i < hshape; i++)
1462 fprintf(stderr, "%02x", p[off + i]);
1463 fprintf(stderr, " ");
1464 for (i = 0; i < hshape; i++)
1465 fprintf(stderr, "%02x", o_ptr[i]);
1466 fprintf(stderr, "==");
1467 for (i = 0; i < hshape; i++)
1468 fprintf(stderr, "%02x", o_p[off + i]);
1469 fprintf(stderr, " <= ");
1470 for (i = 0; i < hshape; i++)
1471 fprintf(stderr, "%02x", r[off + i]);
1472 fprintf(stderr, "<-");
1473 for (i = 0; i < hshape; i++)
1474 fprintf(stderr, "%02x", o_r[off + i]);
1475 fprintf(stderr, "\n");
1476 #endif
1477
1478 if (!memcmp(ptr, p + off, hshape) && !memcmp(o_ptr, o_p + off, hshape)) {
1479
1480 memcpy(backup, ptr, hshape);
1481 memcpy(ptr, r + off, hshape);
1482
1483 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
1484
1485 #ifdef CMPLOG_COMBINE
1486 if (*status == 1) { memcpy(cbuf + idx, r, hshape); }
1487 #endif
1488
1489 memcpy(ptr, backup, hshape);
1490
1491 #ifdef _DEBUG
1492 fprintf(stderr, "Status=%u\n", *status);
1493 #endif
1494
1495 }
1496
1497 // reverse encoding
1498 if (do_reverse && *status != 1) {
1499
1500 if (unlikely(cmp_extend_encodingN(
1501 afl, h, SWAPN(pattern, (hshape << 3)), SWAPN(repl, (hshape << 3)),
1502 SWAPN(o_pattern, (hshape << 3)),
1503 SWAPN(changed_val, (hshape << 3)), attr, idx, taint_len, orig_buf,
1504 buf, cbuf, len, 0, lvl, status))) {
1505
1506 return 1;
1507
1508 }
1509
1510 }
1511
1512 }
1513
1514 return 0;
1515
1516 }
1517
1518 #endif
1519
try_to_add_to_dict(afl_state_t * afl,u64 v,u8 shape)1520 static void try_to_add_to_dict(afl_state_t *afl, u64 v, u8 shape) {
1521
1522 u8 *b = (u8 *)&v;
1523
1524 u32 k;
1525 u8 cons_ff = 0, cons_0 = 0;
1526 for (k = 0; k < shape; ++k) {
1527
1528 if (b[k] == 0) {
1529
1530 ++cons_0;
1531
1532 } else if (b[k] == 0xff) {
1533
1534 ++cons_ff;
1535
1536 } else {
1537
1538 cons_0 = cons_ff = 0;
1539
1540 }
1541
1542 if (cons_0 > 1 || cons_ff > 1) { return; }
1543
1544 }
1545
1546 maybe_add_auto(afl, (u8 *)&v, shape);
1547
1548 u64 rev;
1549 switch (shape) {
1550
1551 case 1:
1552 break;
1553 case 2:
1554 rev = SWAP16((u16)v);
1555 maybe_add_auto(afl, (u8 *)&rev, shape);
1556 break;
1557 case 4:
1558 rev = SWAP32((u32)v);
1559 maybe_add_auto(afl, (u8 *)&rev, shape);
1560 break;
1561 case 8:
1562 rev = SWAP64(v);
1563 maybe_add_auto(afl, (u8 *)&rev, shape);
1564 break;
1565
1566 }
1567
1568 }
1569
1570 #ifdef WORD_SIZE_64
try_to_add_to_dictN(afl_state_t * afl,u128 v,u8 size)1571 static void try_to_add_to_dictN(afl_state_t *afl, u128 v, u8 size) {
1572
1573 u8 *b = (u8 *)&v;
1574
1575 u32 k;
1576 u8 cons_ff = 0, cons_0 = 0;
1577 #if (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1578 u32 off = 0;
1579 for (k = 0; k < size; ++k) {
1580
1581 #else
1582 u32 off = 16 - size;
1583 for (k = 16 - size; k < 16; ++k) {
1584
1585 #endif
1586 if (b[k] == 0) {
1587
1588 ++cons_0;
1589
1590 } else if (b[k] == 0xff) {
1591
1592 ++cons_ff;
1593
1594 } else {
1595
1596 cons_0 = cons_ff = 0;
1597
1598 }
1599
1600 }
1601
1602 maybe_add_auto(afl, (u8 *)&v + off, size);
1603 u128 rev = SWAPN(v, size);
1604 maybe_add_auto(afl, (u8 *)&rev + off, size);
1605
1606 }
1607
1608 #endif
1609
1610 #define SWAPA(_x) ((_x & 0xf8) + ((_x & 7) ^ 0x07))
1611
1612 static u8 cmp_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
1613 u32 len, u32 lvl, struct tainted *taint) {
1614
1615 struct cmp_header *h = &afl->shm.cmp_map->headers[key];
1616 struct tainted * t;
1617 u32 i, j, idx, taint_len, loggeds;
1618 u32 have_taint = 1;
1619 u8 status = 0, found_one = 0;
1620
1621 /* loop cmps are useless, detect and ignore them */
1622 #ifdef WORD_SIZE_64
1623 u32 is_n = 0;
1624 u128 s128_v0 = 0, s128_v1 = 0, orig_s128_v0 = 0, orig_s128_v1 = 0;
1625 #endif
1626 u64 s_v0, s_v1;
1627 u8 s_v0_fixed = 1, s_v1_fixed = 1;
1628 u8 s_v0_inc = 1, s_v1_inc = 1;
1629 u8 s_v0_dec = 1, s_v1_dec = 1;
1630
1631 hshape = SHAPE_BYTES(h->shape);
1632
1633 if (h->hits > CMP_MAP_H) {
1634
1635 loggeds = CMP_MAP_H;
1636
1637 } else {
1638
1639 loggeds = h->hits;
1640
1641 }
1642
1643 #ifdef WORD_SIZE_64
1644 switch (hshape) {
1645
1646 case 1:
1647 case 2:
1648 case 4:
1649 case 8:
1650 break;
1651 default:
1652 is_n = 1;
1653
1654 }
1655
1656 #endif
1657
1658 for (i = 0; i < loggeds; ++i) {
1659
1660 struct cmp_operands *o = &afl->shm.cmp_map->log[key][i];
1661
1662 // loop detection code
1663 if (i == 0) {
1664
1665 s_v0 = o->v0;
1666 s_v1 = o->v1;
1667
1668 } else {
1669
1670 if (s_v0 != o->v0) { s_v0_fixed = 0; }
1671 if (s_v1 != o->v1) { s_v1_fixed = 0; }
1672 if (s_v0 + 1 != o->v0) { s_v0_inc = 0; }
1673 if (s_v1 + 1 != o->v1) { s_v1_inc = 0; }
1674 if (s_v0 - 1 != o->v0) { s_v0_dec = 0; }
1675 if (s_v1 - 1 != o->v1) { s_v1_dec = 0; }
1676 s_v0 = o->v0;
1677 s_v1 = o->v1;
1678
1679 }
1680
1681 struct cmp_operands *orig_o = &afl->orig_cmp_map->log[key][i];
1682
1683 // opt not in the paper
1684 for (j = 0; j < i; ++j) {
1685
1686 if (afl->shm.cmp_map->log[key][j].v0 == o->v0 &&
1687 afl->shm.cmp_map->log[key][j].v1 == o->v1) {
1688
1689 goto cmp_fuzz_next_iter;
1690
1691 }
1692
1693 }
1694
1695 #ifdef _DEBUG
1696 fprintf(stderr, "Handling: %llx->%llx vs %llx->%llx attr=%u shape=%u\n",
1697 orig_o->v0, o->v0, orig_o->v1, o->v1, h->attribute, hshape);
1698 #endif
1699
1700 t = taint;
1701 while (t->next) {
1702
1703 t = t->next;
1704
1705 }
1706
1707 #ifdef WORD_SIZE_64
1708 if (unlikely(is_n)) {
1709
1710 s128_v0 = ((u128)o->v0) + (((u128)o->v0_128) << 64);
1711 s128_v1 = ((u128)o->v1) + (((u128)o->v1_128) << 64);
1712 orig_s128_v0 = ((u128)orig_o->v0) + (((u128)orig_o->v0_128) << 64);
1713 orig_s128_v1 = ((u128)orig_o->v1) + (((u128)orig_o->v1_128) << 64);
1714
1715 }
1716
1717 #endif
1718
1719 for (idx = 0; idx < len; ++idx) {
1720
1721 if (have_taint) {
1722
1723 if (!t || idx < t->pos) {
1724
1725 continue;
1726
1727 } else {
1728
1729 taint_len = t->pos + t->len - idx;
1730
1731 if (idx == t->pos + t->len - 1) { t = t->prev; }
1732
1733 }
1734
1735 } else {
1736
1737 taint_len = len - idx;
1738
1739 }
1740
1741 status = 0;
1742
1743 #ifdef WORD_SIZE_64
1744 if (is_n) { // _ExtInt special case including u128
1745
1746 if (s128_v0 != orig_s128_v0 && orig_s128_v0 != orig_s128_v1) {
1747
1748 if (unlikely(cmp_extend_encodingN(
1749 afl, h, s128_v0, s128_v1, orig_s128_v0, orig_s128_v1,
1750 h->attribute, idx, taint_len, orig_buf, buf, cbuf, len, 1,
1751 lvl, &status))) {
1752
1753 return 1;
1754
1755 }
1756
1757 }
1758
1759 if (status == 1) {
1760
1761 found_one = 1;
1762 break;
1763
1764 }
1765
1766 if (s128_v1 != orig_s128_v1 && orig_s128_v1 != orig_s128_v0) {
1767
1768 if (unlikely(cmp_extend_encodingN(
1769 afl, h, s128_v1, s128_v0, orig_s128_v1, orig_s128_v0,
1770 SWAPA(h->attribute), idx, taint_len, orig_buf, buf, cbuf, len,
1771 1, lvl, &status))) {
1772
1773 return 1;
1774
1775 }
1776
1777 }
1778
1779 if (status == 1) {
1780
1781 found_one = 1;
1782 break;
1783
1784 }
1785
1786 }
1787
1788 #endif
1789
1790 #ifdef _DEBUG
1791 if (o->v0 != orig_o->v0 || o->v1 != orig_o->v1)
1792 fprintf(stderr, "key=%u idx=%u o0=%llu v0=%llu o1=%llu v1=%llu\n", key,
1793 idx, orig_o->v0, o->v0, orig_o->v1, o->v1);
1794 #endif
1795
1796 // even for u128 and _ExtInt we do cmp_extend_encoding() because
1797 // if we got here their own special trials failed and it might just be
1798 // a cast from e.g. u64 to u128 from the input data.
1799
1800 if ((o->v0 != orig_o->v0 || lvl >= LVL3) && orig_o->v0 != orig_o->v1) {
1801
1802 if (unlikely(cmp_extend_encoding(
1803 afl, h, o->v0, o->v1, orig_o->v0, orig_o->v1, h->attribute, idx,
1804 taint_len, orig_buf, buf, cbuf, len, 1, lvl, &status))) {
1805
1806 return 1;
1807
1808 }
1809
1810 }
1811
1812 if (status == 1) {
1813
1814 found_one = 1;
1815 break;
1816
1817 }
1818
1819 status = 0;
1820 if ((o->v1 != orig_o->v1 || lvl >= LVL3) && orig_o->v0 != orig_o->v1) {
1821
1822 if (unlikely(cmp_extend_encoding(afl, h, o->v1, o->v0, orig_o->v1,
1823 orig_o->v0, SWAPA(h->attribute), idx,
1824 taint_len, orig_buf, buf, cbuf, len, 1,
1825 lvl, &status))) {
1826
1827 return 1;
1828
1829 }
1830
1831 }
1832
1833 if (status == 1) {
1834
1835 found_one = 1;
1836 break;
1837
1838 }
1839
1840 }
1841
1842 #ifdef _DEBUG
1843 fprintf(stderr,
1844 "END: %llx->%llx vs %llx->%llx attr=%u i=%u found=%u "
1845 "isN=%u size=%u\n",
1846 orig_o->v0, o->v0, orig_o->v1, o->v1, h->attribute, i, found_one,
1847 is_n, hshape);
1848 #endif
1849
1850 // we only learn 16 bit +
1851 if (hshape > 1) {
1852
1853 if (!found_one || afl->queue_cur->is_ascii) {
1854
1855 #ifdef WORD_SIZE_64
1856 if (unlikely(is_n)) {
1857
1858 if (!found_one ||
1859 check_if_text_buf((u8 *)&s128_v0, SHAPE_BYTES(h->shape)) ==
1860 SHAPE_BYTES(h->shape))
1861 try_to_add_to_dictN(afl, s128_v0, SHAPE_BYTES(h->shape));
1862 if (!found_one ||
1863 check_if_text_buf((u8 *)&s128_v1, SHAPE_BYTES(h->shape)) ==
1864 SHAPE_BYTES(h->shape))
1865 try_to_add_to_dictN(afl, s128_v1, SHAPE_BYTES(h->shape));
1866
1867 } else
1868
1869 #endif
1870 {
1871
1872 if (!memcmp((u8 *)&o->v0, (u8 *)&orig_o->v0, SHAPE_BYTES(h->shape)) &&
1873 (!found_one ||
1874 check_if_text_buf((u8 *)&o->v0, SHAPE_BYTES(h->shape)) ==
1875 SHAPE_BYTES(h->shape)))
1876 try_to_add_to_dict(afl, o->v0, SHAPE_BYTES(h->shape));
1877 if (!memcmp((u8 *)&o->v1, (u8 *)&orig_o->v1, SHAPE_BYTES(h->shape)) &&
1878 (!found_one ||
1879 check_if_text_buf((u8 *)&o->v1, SHAPE_BYTES(h->shape)) ==
1880 SHAPE_BYTES(h->shape)))
1881 try_to_add_to_dict(afl, o->v1, SHAPE_BYTES(h->shape));
1882
1883 }
1884
1885 }
1886
1887 }
1888
1889 cmp_fuzz_next_iter:
1890 afl->stage_cur++;
1891
1892 }
1893
1894 if (loggeds > 3 && ((s_v0_fixed && s_v1_inc) || (s_v1_fixed && s_v0_inc) ||
1895 (s_v0_fixed && s_v1_dec) || (s_v1_fixed && s_v0_dec))) {
1896
1897 afl->pass_stats[key].total = afl->pass_stats[key].faileds = 0xff;
1898
1899 }
1900
1901 if (!found_one && afl->pass_stats[key].faileds < 0xff) {
1902
1903 afl->pass_stats[key].faileds++;
1904
1905 }
1906
1907 if (afl->pass_stats[key].total < 0xff) { afl->pass_stats[key].total++; }
1908
1909 return 0;
1910
1911 }
1912
1913 static u8 rtn_extend_encoding(afl_state_t *afl, u8 entry,
1914 struct cmpfn_operands *o,
1915 struct cmpfn_operands *orig_o, u32 idx,
1916 u32 taint_len, u8 *orig_buf, u8 *buf, u8 *cbuf,
1917 u32 len, u8 lvl, u8 *status) {
1918
1919 #ifndef CMPLOG_COMBINE
1920 (void)(cbuf);
1921 #endif
1922 //#ifndef CMPLOG_SOLVE_TRANSFORM
1923 // (void)(changed_val);
1924 //#endif
1925
1926 if (afl->fsrv.total_execs - last_update > screen_update) {
1927
1928 show_stats(afl);
1929 last_update = afl->fsrv.total_execs;
1930
1931 }
1932
1933 u8 *pattern, *repl, *o_pattern, *changed_val;
1934 u8 l0, l1, ol0, ol1;
1935
1936 if (entry == 0) {
1937
1938 pattern = o->v0;
1939 repl = o->v1;
1940 o_pattern = orig_o->v0;
1941 changed_val = orig_o->v1;
1942 l0 = o->v0_len;
1943 ol0 = orig_o->v0_len;
1944 l1 = o->v1_len;
1945 ol1 = orig_o->v1_len;
1946
1947 } else {
1948
1949 pattern = o->v1;
1950 repl = o->v0;
1951 o_pattern = orig_o->v1;
1952 changed_val = orig_o->v0;
1953 l0 = o->v1_len;
1954 ol0 = orig_o->v1_len;
1955 l1 = o->v0_len;
1956 ol1 = orig_o->v0_len;
1957
1958 }
1959
1960 if (l0 >= 0x80 || ol0 >= 0x80) {
1961
1962 l0 -= 0x80;
1963 l1 -= 0x80;
1964 ol0 -= 0x80;
1965 ol1 -= 0x80;
1966
1967 }
1968
1969 if (l0 == 0 || l1 == 0 || ol0 == 0 || ol1 == 0 || l0 > 31 || l1 > 31 ||
1970 ol0 > 31 || ol1 > 31) {
1971
1972 l0 = ol0 = hshape;
1973
1974 }
1975
1976 u8 lmax = MAX(l0, ol0);
1977 u8 save[40];
1978 u32 saved_idx = idx, pre, from = 0, to = 0, i, j;
1979 u32 its_len = MIN(MIN(lmax, hshape), len - idx);
1980 its_len = MIN(its_len, taint_len);
1981 u32 saved_its_len = its_len;
1982
1983 if (lvl & LVL3) {
1984
1985 u32 max_to = MIN(4U, idx);
1986 if (!(lvl & LVL1) && max_to) { from = 1; }
1987 to = max_to;
1988
1989 }
1990
1991 memcpy(save, &buf[saved_idx - to], its_len + to);
1992 (void)(j);
1993
1994 #ifdef _DEBUG
1995 fprintf(stderr, "RTN T idx=%u lvl=%02x is_txt=%u shape=%u/%u ", idx, lvl,
1996 o->v0_len >= 0x80 ? 1 : 0, hshape, l0);
1997 for (j = 0; j < 8; j++)
1998 fprintf(stderr, "%02x", orig_buf[idx + j]);
1999 fprintf(stderr, " -> ");
2000 for (j = 0; j < 8; j++)
2001 fprintf(stderr, "%02x", o_pattern[j]);
2002 fprintf(stderr, " <= ");
2003 for (j = 0; j < 8; j++)
2004 fprintf(stderr, "%02x", repl[j]);
2005 fprintf(stderr, "\n");
2006 fprintf(stderr, " ");
2007 for (j = 0; j < 8; j++)
2008 fprintf(stderr, "%02x", buf[idx + j]);
2009 fprintf(stderr, " -> ");
2010 for (j = 0; j < 8; j++)
2011 fprintf(stderr, "%02x", pattern[j]);
2012 fprintf(stderr, " <= ");
2013 for (j = 0; j < 8; j++)
2014 fprintf(stderr, "%02x", changed_val[j]);
2015 fprintf(stderr, "\n");
2016 #endif
2017
2018 // Try to match the replace value up to 4 bytes before the current idx.
2019 // This allows matching of eg.:
2020 // if (memcmp(user_val, "TEST") == 0)
2021 // if (memcmp(user_val, "TEST-VALUE") == 0) ...
2022 // We only do this in lvl 3, otherwise we only do direct matching
2023
2024 for (pre = from; pre <= to; pre++) {
2025
2026 if (*status != 1 && (!pre || !memcmp(buf + saved_idx - pre, repl, pre))) {
2027
2028 idx = saved_idx - pre;
2029 its_len = saved_its_len + pre;
2030
2031 for (i = 0; i < its_len; ++i) {
2032
2033 if ((pattern[i] != buf[idx + i] && o_pattern[i] != orig_buf[idx + i]) ||
2034 *status == 1) {
2035
2036 break;
2037
2038 }
2039
2040 buf[idx + i] = repl[i];
2041
2042 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2043
2044 #ifdef CMPLOG_COMBINE
2045 if (*status == 1) { memcpy(cbuf + idx, &buf[idx], i); }
2046 #endif
2047
2048 }
2049
2050 memcpy(&buf[idx], save + to - pre, i);
2051
2052 }
2053
2054 }
2055
2056 if (*status == 1) return 0;
2057
2058 // transform solving
2059
2060 if (afl->cmplog_enable_transform && (lvl & LVL3)) {
2061
2062 u32 toupper = 0, tolower = 0, xor = 0, arith = 0, tohex = 0, fromhex = 0;
2063 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
2064 u32 tob64 = 0, fromb64 = 0;
2065 #endif
2066 u32 from_0 = 0, from_x = 0, from_X = 0, from_slash = 0, from_up = 0;
2067 u32 to_0 = 0, to_x = 0, to_slash = 0, to_up = 0;
2068 u8 xor_val[32], arith_val[32], tmp[48];
2069
2070 idx = saved_idx;
2071 its_len = saved_its_len;
2072
2073 memcpy(save, &buf[idx], its_len);
2074
2075 for (i = 0; i < its_len; ++i) {
2076
2077 xor_val[i] = pattern[i] ^ buf[idx + i];
2078 arith_val[i] = pattern[i] - buf[idx + i];
2079
2080 if (i == 0) {
2081
2082 if (orig_buf[idx] == '0') {
2083
2084 from_0 = 1;
2085
2086 } else if (orig_buf[idx] == '\\') {
2087
2088 from_slash = 1;
2089
2090 }
2091
2092 if (repl[0] == '0') {
2093
2094 to_0 = 1;
2095
2096 } else if (repl[0] == '\\') {
2097
2098 to_slash = 1;
2099
2100 }
2101
2102 } else if (i == 1) {
2103
2104 if (orig_buf[idx + 1] == 'x') {
2105
2106 from_x = 1;
2107
2108 } else if (orig_buf[idx + 1] == 'X') {
2109
2110 from_X = from_x = 1;
2111
2112 }
2113
2114 if (repl[1] == 'x' || repl[1] == 'X') { to_x = 1; }
2115
2116 }
2117
2118 if (i < 16 && is_hex(repl + (i << 1))) {
2119
2120 ++tohex;
2121
2122 if (!to_up) {
2123
2124 if (repl[i << 1] >= 'A' && repl[i << 1] <= 'F')
2125 to_up = 1;
2126 else if (repl[i << 1] >= 'a' && repl[i << 1] <= 'f')
2127 to_up = 2;
2128 if (repl[(i << 1) + 1] >= 'A' && repl[(i << 1) + 1] <= 'F')
2129 to_up = 1;
2130 else if (repl[(i << 1) + 1] >= 'a' && repl[(i << 1) + 1] <= 'f')
2131 to_up = 2;
2132
2133 }
2134
2135 }
2136
2137 if ((i % 2)) {
2138
2139 if (len > idx + i + 1 && is_hex(orig_buf + idx + i)) {
2140
2141 fromhex += 2;
2142
2143 if (!from_up) {
2144
2145 if (orig_buf[idx + i] >= 'A' && orig_buf[idx + i] <= 'F')
2146 from_up = 1;
2147 else if (orig_buf[idx + i] >= 'a' && orig_buf[idx + i] <= 'f')
2148 from_up = 2;
2149 if (orig_buf[idx + i - 1] >= 'A' && orig_buf[idx + i - 1] <= 'F')
2150 from_up = 1;
2151 else if (orig_buf[idx + i - 1] >= 'a' &&
2152 orig_buf[idx + i - 1] <= 'f')
2153 from_up = 2;
2154
2155 }
2156
2157 }
2158
2159 }
2160
2161 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
2162 if (i % 3 == 2 && i < 24) {
2163
2164 if (is_base64(repl + ((i / 3) << 2))) tob64 += 3;
2165
2166 }
2167
2168 if (i % 4 == 3 && i < 24) {
2169
2170 if (is_base64(orig_buf + idx + i - 3)) fromb64 += 4;
2171
2172 }
2173
2174 #endif
2175
2176 if ((o_pattern[i] ^ orig_buf[idx + i]) == xor_val[i] && xor_val[i]) {
2177
2178 ++xor;
2179
2180 }
2181
2182 if ((o_pattern[i] - orig_buf[idx + i]) == arith_val[i] && arith_val[i]) {
2183
2184 ++arith;
2185
2186 }
2187
2188 if ((buf[idx + i] | 0x20) == pattern[i] &&
2189 (orig_buf[idx + i] | 0x20) == o_pattern[i]) {
2190
2191 ++tolower;
2192
2193 }
2194
2195 if ((buf[idx + i] & 0x5a) == pattern[i] &&
2196 (orig_buf[idx + i] & 0x5a) == o_pattern[i]) {
2197
2198 ++toupper;
2199
2200 }
2201
2202 #ifdef _DEBUG
2203 fprintf(stderr,
2204 "RTN idx=%u loop=%u xor=%u arith=%u tolower=%u toupper=%u "
2205 "tohex=%u fromhex=%u to_0=%u to_slash=%u to_x=%u "
2206 "from_0=%u from_slash=%u from_x=%u\n",
2207 idx, i, xor, arith, tolower, toupper, tohex, fromhex, to_0,
2208 to_slash, to_x, from_0, from_slash, from_x);
2209 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
2210 fprintf(stderr, "RTN idx=%u loop=%u tob64=%u from64=%u\n", tob64,
2211 fromb64);
2212 #endif
2213 #endif
2214
2215 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
2216 // input is base64 and converted to binary? convert repl to base64!
2217 if ((i % 4) == 3 && i < 24 && fromb64 > i) {
2218
2219 to_base64(repl, tmp, i + 1);
2220 memcpy(buf + idx, tmp, i + 1);
2221 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2222 // fprintf(stderr, "RTN ATTEMPT fromb64 %u result %u\n", fromb64,
2223 // *status);
2224
2225 }
2226
2227 // input is converted to base64? decode repl with base64!
2228 if ((i % 3) == 2 && i < 24 && tob64 > i) {
2229
2230 u32 olen = from_base64(repl, tmp, i + 1);
2231 memcpy(buf + idx, tmp, olen);
2232 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2233 // fprintf(stderr, "RTN ATTEMPT tob64 %u idx=%u result %u\n", tob64,
2234 // idx, *status);
2235
2236 }
2237
2238 #endif
2239
2240 // input is converted to hex? convert repl to binary!
2241 if (i < 16 && tohex > i) {
2242
2243 u32 off;
2244 if (to_slash + to_x + to_0 == 2) {
2245
2246 off = 2;
2247
2248 } else {
2249
2250 off = 0;
2251
2252 }
2253
2254 for (j = 0; j <= i; j++)
2255 tmp[j] = (hex_table[repl[off + (j << 1)] - '0'] << 4) +
2256 hex_table[repl[off + (j << 1) + 1] - '0'];
2257
2258 memcpy(buf + idx, tmp, i + 1);
2259 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2260 // fprintf(stderr, "RTN ATTEMPT tohex %u result %u\n", tohex,
2261 // *status);
2262
2263 }
2264
2265 // input is hex and converted to binary? convert repl to hex!
2266 if (i && (i % 2) && i < 16 && fromhex &&
2267 fromhex + from_slash + from_x + from_0 > i) {
2268
2269 u8 off = 0;
2270 if (from_slash && from_x) {
2271
2272 tmp[0] = '\\';
2273 if (from_X) {
2274
2275 tmp[1] = 'X';
2276
2277 } else {
2278
2279 tmp[1] = 'x';
2280
2281 }
2282
2283 off = 2;
2284
2285 } else if (from_0 && from_x) {
2286
2287 tmp[0] = '0';
2288 if (from_X) {
2289
2290 tmp[1] = 'X';
2291
2292 } else {
2293
2294 tmp[1] = 'x';
2295
2296 }
2297
2298 off = 2;
2299
2300 }
2301
2302 if (to_up == 1) {
2303
2304 for (j = 0; j <= (i >> 1); j++) {
2305
2306 tmp[off + (j << 1)] = hex_table_up[repl[j] >> 4];
2307 tmp[off + (j << 1) + 1] = hex_table_up[repl[j] % 16];
2308
2309 }
2310
2311 } else {
2312
2313 for (j = 0; j <= (i >> 1); j++) {
2314
2315 tmp[off + (j << 1)] = hex_table_low[repl[j] >> 4];
2316 tmp[off + (j << 1) + 1] = hex_table_low[repl[j] % 16];
2317
2318 }
2319
2320 }
2321
2322 memcpy(buf + idx, tmp, i + 1 + off);
2323 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2324 // fprintf(stderr, "RTN ATTEMPT fromhex %u result %u\n", fromhex,
2325 // *status);
2326 memcpy(buf + idx, save, i + 1 + off);
2327
2328 }
2329
2330 if (xor > i) {
2331
2332 for (j = 0; j <= i; j++)
2333 buf[idx + j] = repl[j] ^ xor_val[j];
2334 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2335 // fprintf(stderr, "RTN ATTEMPT xor %u result %u\n", xor, *status);
2336
2337 }
2338
2339 if (arith > i && *status != 1) {
2340
2341 for (j = 0; j <= i; j++)
2342 buf[idx + j] = repl[j] - arith_val[j];
2343 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2344 // fprintf(stderr, "RTN ATTEMPT arith %u result %u\n", arith,
2345 // *status);
2346
2347 }
2348
2349 if (toupper > i && *status != 1) {
2350
2351 for (j = 0; j <= i; j++)
2352 buf[idx + j] = repl[j] | 0x20;
2353 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2354 // fprintf(stderr, "RTN ATTEMPT toupper %u result %u\n", toupper,
2355 // *status);
2356
2357 }
2358
2359 if (tolower > i && *status != 1) {
2360
2361 for (j = 0; j <= i; j++)
2362 buf[idx + j] = repl[j] & 0x5f;
2363 if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
2364 // fprintf(stderr, "RTN ATTEMPT tolower %u result %u\n", tolower,
2365 // *status);
2366
2367 }
2368
2369 #ifdef CMPLOG_COMBINE
2370 if (*status == 1) { memcpy(cbuf + idx, &buf[idx], i + 1); }
2371 #endif
2372
2373 if ((i >= 7 &&
2374 (i >= xor&&i >= arith &&i >= tolower &&i >= toupper &&i > tohex &&i >
2375 (fromhex + from_0 + from_x + from_slash + 1)
2376 #ifdef CMPLOG_SOLVE_TRANSFORM_BASE64
2377 && i > tob64 + 3 && i > fromb64 + 4
2378 #endif
2379 )) ||
2380 repl[i] != changed_val[i] || *status == 1) {
2381
2382 break;
2383
2384 }
2385
2386 }
2387
2388 memcpy(&buf[idx], save, i);
2389
2390 }
2391
2392 //#endif
2393
2394 return 0;
2395
2396 }
2397
2398 static u8 rtn_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
2399 u32 len, u8 lvl, struct tainted *taint) {
2400
2401 struct tainted * t;
2402 struct cmp_header *h = &afl->shm.cmp_map->headers[key];
2403 u32 i, j, idx, have_taint = 1, taint_len, loggeds;
2404 u8 status = 0, found_one = 0;
2405
2406 hshape = SHAPE_BYTES(h->shape);
2407
2408 if (h->hits > CMP_MAP_RTN_H) {
2409
2410 loggeds = CMP_MAP_RTN_H;
2411
2412 } else {
2413
2414 loggeds = h->hits;
2415
2416 }
2417
2418 for (i = 0; i < loggeds; ++i) {
2419
2420 struct cmpfn_operands *o =
2421 &((struct cmpfn_operands *)afl->shm.cmp_map->log[key])[i];
2422
2423 struct cmpfn_operands *orig_o =
2424 &((struct cmpfn_operands *)afl->orig_cmp_map->log[key])[i];
2425
2426 // opt not in the paper
2427 for (j = 0; j < i; ++j) {
2428
2429 if (!memcmp(&((struct cmpfn_operands *)afl->shm.cmp_map->log[key])[j], o,
2430 sizeof(struct cmpfn_operands))) {
2431
2432 goto rtn_fuzz_next_iter;
2433
2434 }
2435
2436 }
2437
2438 /*
2439 struct cmp_header *hh = &afl->orig_cmp_map->headers[key];
2440 fprintf(stderr, "RTN N hits=%u id=%u shape=%u attr=%u v0=", h->hits, h->id,
2441 hshape, h->attribute);
2442 for (j = 0; j < 8; j++)
2443 fprintf(stderr, "%02x", o->v0[j]);
2444 fprintf(stderr, " v1=");
2445 for (j = 0; j < 8; j++)
2446 fprintf(stderr, "%02x", o->v1[j]);
2447 fprintf(stderr, "\nRTN O hits=%u id=%u shape=%u attr=%u o0=", hh->hits,
2448 hh->id, hshape, hh->attribute);
2449 for (j = 0; j < 8; j++)
2450 fprintf(stderr, "%02x", orig_o->v0[j]);
2451 fprintf(stderr, " o1=");
2452 for (j = 0; j < 8; j++)
2453 fprintf(stderr, "%02x", orig_o->v1[j]);
2454 fprintf(stderr, "\n");
2455 */
2456
2457 t = taint;
2458 while (t->next) {
2459
2460 t = t->next;
2461
2462 }
2463
2464 for (idx = 0; idx < len; ++idx) {
2465
2466 if (have_taint) {
2467
2468 if (!t || idx < t->pos) {
2469
2470 continue;
2471
2472 } else {
2473
2474 taint_len = t->pos + t->len - idx;
2475
2476 if (idx == t->pos + t->len - 1) { t = t->prev; }
2477
2478 }
2479
2480 } else {
2481
2482 taint_len = len - idx;
2483
2484 }
2485
2486 status = 0;
2487
2488 #ifdef _DEBUG
2489 int w;
2490 fprintf(stderr, "key=%u idx=%u len=%u o0=", key, idx, hshape);
2491 for (w = 0; w < hshape; ++w)
2492 fprintf(stderr, "%02x", orig_o->v0[w]);
2493 fprintf(stderr, " v0=");
2494 for (w = 0; w < hshape; ++w)
2495 fprintf(stderr, "%02x", o->v0[w]);
2496 fprintf(stderr, " o1=");
2497 for (w = 0; w < hshape; ++w)
2498 fprintf(stderr, "%02x", orig_o->v1[w]);
2499 fprintf(stderr, " v1=");
2500 for (w = 0; w < hshape; ++w)
2501 fprintf(stderr, "%02x", o->v1[w]);
2502 fprintf(stderr, "\n");
2503 #endif
2504
2505 if (unlikely(rtn_extend_encoding(afl, 0, o, orig_o, idx, taint_len,
2506 orig_buf, buf, cbuf, len, lvl,
2507 &status))) {
2508
2509 return 1;
2510
2511 }
2512
2513 if (status == 1) {
2514
2515 found_one = 1;
2516 break;
2517
2518 }
2519
2520 status = 0;
2521
2522 if (unlikely(rtn_extend_encoding(afl, 1, o, orig_o, idx, taint_len,
2523 orig_buf, buf, cbuf, len, lvl,
2524 &status))) {
2525
2526 return 1;
2527
2528 }
2529
2530 if (status == 1) {
2531
2532 found_one = 1;
2533 break;
2534
2535 }
2536
2537 }
2538
2539 // if (unlikely(!afl->pass_stats[key].total)) {
2540
2541 if ((!found_one && (lvl & LVL1)) || afl->queue_cur->is_ascii) {
2542
2543 // if (unlikely(!afl->pass_stats[key].total)) {
2544
2545 u32 shape_len = SHAPE_BYTES(h->shape);
2546 u32 v0_len = shape_len, v1_len = shape_len;
2547 if (afl->queue_cur->is_ascii ||
2548 check_if_text_buf((u8 *)&o->v0, shape_len) == shape_len) {
2549
2550 if (strlen(o->v0)) v0_len = strlen(o->v0);
2551
2552 }
2553
2554 if (afl->queue_cur->is_ascii ||
2555 check_if_text_buf((u8 *)&o->v1, shape_len) == shape_len) {
2556
2557 if (strlen(o->v1)) v1_len = strlen(o->v1);
2558
2559 }
2560
2561 // fprintf(stderr, "SHOULD: found:%u ascii:%u text?%u:%u %u:%s %u:%s \n",
2562 // found_one, afl->queue_cur->is_ascii, check_if_text_buf((u8 *)&o->v0,
2563 // shape_len), check_if_text_buf((u8 *)&o->v1, shape_len), v0_len,
2564 // o->v0, v1_len, o->v1);
2565
2566 if (!memcmp(o->v0, orig_o->v0, v0_len) ||
2567 (!found_one || check_if_text_buf((u8 *)&o->v0, v0_len) == v0_len))
2568 maybe_add_auto(afl, o->v0, v0_len);
2569 if (!memcmp(o->v1, orig_o->v1, v1_len) ||
2570 (!found_one || check_if_text_buf((u8 *)&o->v1, v1_len) == v1_len))
2571 maybe_add_auto(afl, o->v1, v1_len);
2572
2573 //}
2574
2575 }
2576
2577 rtn_fuzz_next_iter:
2578 afl->stage_cur++;
2579
2580 }
2581
2582 if (!found_one && afl->pass_stats[key].faileds < 0xff) {
2583
2584 afl->pass_stats[key].faileds++;
2585
2586 }
2587
2588 if (afl->pass_stats[key].total < 0xff) { afl->pass_stats[key].total++; }
2589
2590 return 0;
2591
2592 }
2593
2594 ///// Input to State stage
2595
2596 // afl->queue_cur->exec_cksum
2597 u8 input_to_state_stage(afl_state_t *afl, u8 *orig_buf, u8 *buf, u32 len) {
2598
2599 u8 r = 1;
2600 if (unlikely(!afl->pass_stats)) {
2601
2602 afl->pass_stats = ck_alloc(sizeof(struct afl_pass_stat) * CMP_MAP_W);
2603
2604 }
2605
2606 struct tainted *taint = NULL;
2607 if (likely(afl->queue_cur->exec_us)) {
2608
2609 if (likely((100000 / 2) >= afl->queue_cur->exec_us)) {
2610
2611 screen_update = 100000 / afl->queue_cur->exec_us;
2612
2613 } else {
2614
2615 screen_update = 1;
2616
2617 }
2618
2619 } else {
2620
2621 screen_update = 100000;
2622
2623 }
2624
2625 if (!afl->queue_cur->taint || !afl->queue_cur->cmplog_colorinput) {
2626
2627 if (unlikely(colorization(afl, buf, len, &taint))) { return 1; }
2628
2629 // no taint? still try, create a dummy to prevent again colorization
2630 if (!taint) {
2631
2632 #ifdef _DEBUG
2633 fprintf(stderr, "TAINT FAILED\n");
2634 #endif
2635 afl->queue_cur->colorized = CMPLOG_LVL_MAX;
2636 return 0;
2637
2638 }
2639
2640 #ifdef _DEBUG
2641 else if (taint->pos == 0 && taint->len == len) {
2642
2643 fprintf(stderr, "TAINT FULL\n");
2644
2645 }
2646
2647 #endif
2648
2649 } else {
2650
2651 buf = afl->queue_cur->cmplog_colorinput;
2652 taint = afl->queue_cur->taint;
2653
2654 }
2655
2656 struct tainted *t = taint;
2657
2658 while (t) {
2659
2660 #ifdef _DEBUG
2661 fprintf(stderr, "T: idx=%u len=%u\n", t->pos, t->len);
2662 #endif
2663 t = t->next;
2664
2665 }
2666
2667 #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION)
2668 u64 start_time = get_cur_time();
2669 u32 cmp_locations = 0;
2670 #endif
2671
2672 // Generate the cmplog data
2673
2674 // manually clear the full cmp_map
2675 memset(afl->shm.cmp_map, 0, sizeof(struct cmp_map));
2676 if (unlikely(common_fuzz_cmplog_stuff(afl, orig_buf, len))) {
2677
2678 afl->queue_cur->colorized = CMPLOG_LVL_MAX;
2679 while (taint) {
2680
2681 t = taint->next;
2682 ck_free(taint);
2683 taint = t;
2684
2685 }
2686
2687 return 1;
2688
2689 }
2690
2691 if (unlikely(!afl->orig_cmp_map)) {
2692
2693 afl->orig_cmp_map = ck_alloc_nozero(sizeof(struct cmp_map));
2694
2695 }
2696
2697 memcpy(afl->orig_cmp_map, afl->shm.cmp_map, sizeof(struct cmp_map));
2698 memset(afl->shm.cmp_map->headers, 0, sizeof(struct cmp_header) * CMP_MAP_W);
2699 if (unlikely(common_fuzz_cmplog_stuff(afl, buf, len))) {
2700
2701 afl->queue_cur->colorized = CMPLOG_LVL_MAX;
2702 while (taint) {
2703
2704 t = taint->next;
2705 ck_free(taint);
2706 taint = t;
2707
2708 }
2709
2710 return 1;
2711
2712 }
2713
2714 #ifdef _DEBUG
2715 dump("ORIG", orig_buf, len);
2716 dump("NEW ", buf, len);
2717 #endif
2718
2719 // Start insertion loop
2720
2721 u64 orig_hit_cnt, new_hit_cnt;
2722 u64 orig_execs = afl->fsrv.total_execs;
2723 orig_hit_cnt = afl->queued_items + afl->saved_crashes;
2724
2725 afl->stage_name = "input-to-state";
2726 afl->stage_short = "its";
2727 afl->stage_max = 0;
2728 afl->stage_cur = 0;
2729
2730 u32 lvl = (afl->queue_cur->colorized ? 0 : LVL1) +
2731 (afl->cmplog_lvl == CMPLOG_LVL_MAX ? LVL3 : 0);
2732
2733 #ifdef CMPLOG_COMBINE
2734 u8 *cbuf = afl_realloc((void **)&afl->in_scratch_buf, len + 128);
2735 memcpy(cbuf, orig_buf, len);
2736 u8 *virgin_backup = afl_realloc((void **)&afl->ex_buf, afl->shm.map_size);
2737 memcpy(virgin_backup, afl->virgin_bits, afl->shm.map_size);
2738 #else
2739 u8 *cbuf = NULL;
2740 #endif
2741
2742 u32 k;
2743 for (k = 0; k < CMP_MAP_W; ++k) {
2744
2745 if (!afl->shm.cmp_map->headers[k].hits) { continue; }
2746
2747 if (afl->pass_stats[k].faileds >= CMPLOG_FAIL_MAX ||
2748 afl->pass_stats[k].total >= CMPLOG_FAIL_MAX) {
2749
2750 #ifdef _DEBUG
2751 fprintf(stderr, "DISABLED %u\n", k);
2752 #endif
2753
2754 afl->shm.cmp_map->headers[k].hits = 0; // ignore this cmp
2755
2756 }
2757
2758 if (afl->shm.cmp_map->headers[k].type == CMP_TYPE_INS) {
2759
2760 // fprintf(stderr, "INS %u\n", k);
2761 afl->stage_max +=
2762 MIN((u32)(afl->shm.cmp_map->headers[k].hits), (u32)CMP_MAP_H);
2763
2764 } else {
2765
2766 // fprintf(stderr, "RTN %u\n", k);
2767 afl->stage_max +=
2768 MIN((u32)(afl->shm.cmp_map->headers[k].hits), (u32)CMP_MAP_RTN_H);
2769
2770 }
2771
2772 }
2773
2774 for (k = 0; k < CMP_MAP_W; ++k) {
2775
2776 if (!afl->shm.cmp_map->headers[k].hits) { continue; }
2777
2778 #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION)
2779 ++cmp_locations;
2780 #endif
2781
2782 if (afl->shm.cmp_map->headers[k].type == CMP_TYPE_INS) {
2783
2784 if (unlikely(cmp_fuzz(afl, k, orig_buf, buf, cbuf, len, lvl, taint))) {
2785
2786 goto exit_its;
2787
2788 }
2789
2790 } else if ((lvl & LVL1)
2791
2792 //#ifdef CMPLOG_SOLVE_TRANSFORM
2793 || ((lvl & LVL3) && afl->cmplog_enable_transform)
2794 //#endif
2795 ) {
2796
2797 if (unlikely(rtn_fuzz(afl, k, orig_buf, buf, cbuf, len, lvl, taint))) {
2798
2799 goto exit_its;
2800
2801 }
2802
2803 }
2804
2805 }
2806
2807 r = 0;
2808
2809 exit_its:
2810
2811 if (afl->cmplog_lvl == CMPLOG_LVL_MAX) {
2812
2813 afl->queue_cur->colorized = CMPLOG_LVL_MAX;
2814
2815 if (afl->queue_cur->cmplog_colorinput) {
2816
2817 ck_free(afl->queue_cur->cmplog_colorinput);
2818
2819 }
2820
2821 while (taint) {
2822
2823 t = taint->next;
2824 ck_free(taint);
2825 taint = t;
2826
2827 }
2828
2829 afl->queue_cur->taint = NULL;
2830
2831 } else {
2832
2833 afl->queue_cur->colorized = LVL2;
2834
2835 if (!afl->queue_cur->taint) { afl->queue_cur->taint = taint; }
2836
2837 if (!afl->queue_cur->cmplog_colorinput) {
2838
2839 afl->queue_cur->cmplog_colorinput = ck_alloc_nozero(len);
2840 memcpy(afl->queue_cur->cmplog_colorinput, buf, len);
2841 memcpy(buf, orig_buf, len);
2842
2843 }
2844
2845 }
2846
2847 #ifdef CMPLOG_COMBINE
2848 if (afl->queued_items + afl->saved_crashes > orig_hit_cnt + 1) {
2849
2850 // copy the current virgin bits so we can recover the information
2851 u8 *virgin_save = afl_realloc((void **)&afl->eff_buf, afl->shm.map_size);
2852 memcpy(virgin_save, afl->virgin_bits, afl->shm.map_size);
2853 // reset virgin bits to the backup previous to redqueen
2854 memcpy(afl->virgin_bits, virgin_backup, afl->shm.map_size);
2855
2856 u8 status = 0;
2857 its_fuzz(afl, cbuf, len, &status);
2858
2859 // now combine with the saved virgin bits
2860 #ifdef WORD_SIZE_64
2861 u64 *v = (u64 *)afl->virgin_bits;
2862 u64 *s = (u64 *)virgin_save;
2863 u32 i;
2864 for (i = 0; i < (afl->shm.map_size >> 3); i++) {
2865
2866 v[i] &= s[i];
2867
2868 }
2869
2870 #else
2871 u32 *v = (u32 *)afl->virgin_bits;
2872 u32 *s = (u32 *)virgin_save;
2873 u32 i;
2874 for (i = 0; i < (afl->shm.map_size >> 2); i++) {
2875
2876 v[i] &= s[i];
2877
2878 }
2879
2880 #endif
2881
2882 #ifdef _DEBUG
2883 dump("COMB", cbuf, len);
2884 if (status == 1) {
2885
2886 fprintf(stderr, "NEW CMPLOG_COMBINED\n");
2887
2888 } else {
2889
2890 fprintf(stderr, "NO new combined\n");
2891
2892 }
2893
2894 #endif
2895
2896 }
2897
2898 #endif
2899
2900 new_hit_cnt = afl->queued_items + afl->saved_crashes;
2901 afl->stage_finds[STAGE_ITS] += new_hit_cnt - orig_hit_cnt;
2902 afl->stage_cycles[STAGE_ITS] += afl->fsrv.total_execs - orig_execs;
2903
2904 #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION)
2905 FILE *f = stderr;
2906 #ifndef _DEBUG
2907 if (afl->not_on_tty) {
2908
2909 char fn[4096];
2910 snprintf(fn, sizeof(fn), "%s/introspection_cmplog.txt", afl->out_dir);
2911 f = fopen(fn, "a");
2912
2913 }
2914
2915 #endif
2916
2917 if (f) {
2918
2919 fprintf(f,
2920 "Cmplog: fname=%s len=%u ms=%llu result=%u finds=%llu entries=%u "
2921 "auto_extra_after=%u\n",
2922 afl->queue_cur->fname, len, get_cur_time() - start_time, r,
2923 new_hit_cnt - orig_hit_cnt, cmp_locations, afl->a_extras_cnt);
2924
2925 #ifndef _DEBUG
2926 if (afl->not_on_tty) { fclose(f); }
2927 #endif
2928
2929 }
2930
2931 #endif
2932
2933 return r;
2934
2935 }
2936
2937