1/*	$NetBSD: fuzzer.c,v 1.2 2017/01/28 21:31:45 christos Exp $	*/
2
3/*
4 * Copyright (c) 2009 Kungliga Tekniska H��gskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Portions Copyright (c) 2009 - 2010 Apple Inc. All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 *
17 * 2. Redistributions in binary form must reproduce the above copyright
18 *    notice, this list of conditions and the following disclaimer in the
19 *    documentation and/or other materials provided with the distribution.
20 *
21 * 3. Neither the name of the Institute nor the names of its contributors
22 *    may be used to endorse or promote products derived from this software
23 *    without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38#include "der_locl.h"
39#include <krb5/com_err.h>
40
41enum trigger_method { FOFF, FRANDOM, FLINEAR, FLINEAR_SIZE };
42
43#ifdef ASN1_FUZZER
44static enum trigger_method method = FOFF;
45
46/* FLINEAR */
47static unsigned long fnum, fcur, fsize;
48#endif
49
50int
51asn1_fuzzer_method(const char *mode)
52{
53#ifdef ASN1_FUZZER
54    if (mode == NULL || strcasecmp(mode, "off") == 0) {
55	method = FOFF;
56    } else if (strcasecmp(mode, "random") == 0) {
57	method = FRANDOM;
58    } else if (strcasecmp(mode, "linear") == 0) {
59	method = FLINEAR;
60    } else if (strcasecmp(mode, "linear-size") == 0) {
61	method = FLINEAR_SIZE;
62    } else
63	return 1;
64    return 0;
65#else
66    return 1;
67#endif
68}
69
70void
71asn1_fuzzer_reset(void)
72{
73#ifdef ASN1_FUZZER
74    fcur = 0;
75    fsize = 0;
76    fnum = 0;
77#endif
78}
79
80void
81asn1_fuzzer_next(void)
82{
83#ifdef ASN1_FUZZER
84    fcur = 0;
85    fsize = 0;
86    fnum++;
87#endif
88}
89
90int
91asn1_fuzzer_done(void)
92{
93#ifndef ASN1_FUZZER
94    abort();
95#else
96    /* since code paths */
97    return (fnum > 10000);
98#endif
99}
100
101#ifdef ASN1_FUZZER
102
103static int
104fuzzer_trigger(unsigned int chance)
105{
106    switch(method) {
107    case FOFF:
108	return 0;
109    case FRANDOM:
110	if ((rk_random() % chance) != 1)
111	    return 0;
112	return 1;
113    case FLINEAR:
114	if (fnum == fcur++)
115	    return 1;
116	return 0;
117    case FLINEAR_SIZE:
118	return 0;
119    }
120    return 0;
121}
122
123static int
124fuzzer_size_trigger(unsigned long *cur)
125{
126    if (method != FLINEAR_SIZE)
127	return 0;
128    if (fnum == (*cur)++)
129	return 1;
130    return 0;
131}
132
133static size_t
134fuzzer_length_len (size_t len)
135{
136    if (fuzzer_size_trigger(&fsize)) {
137	len = 0;
138    } else if (fuzzer_size_trigger(&fsize)) {
139	len = 129;
140    } else if (fuzzer_size_trigger(&fsize)) {
141	len = 0xffff;
142    }
143
144    if (len < 128)
145	return 1;
146    else {
147	int ret = 0;
148	do {
149	    ++ret;
150	    len /= 256;
151	} while (len);
152	return ret + 1;
153    }
154}
155
156static int
157fuzzer_put_length (unsigned char *p, size_t len, size_t val, size_t *size)
158{
159    if (len < 1)
160	return ASN1_OVERFLOW;
161
162    if (fuzzer_size_trigger(&fcur)) {
163	val = 0;
164    } else if (fuzzer_size_trigger(&fcur)) {
165	val = 129;
166    } else if (fuzzer_size_trigger(&fcur)) {
167	val = 0xffff;
168    }
169
170    if (val < 128) {
171	*p = val;
172	*size = 1;
173    } else {
174	size_t l = 0;
175
176	while(val > 0) {
177	    if(len < 2)
178		return ASN1_OVERFLOW;
179	    *p-- = val % 256;
180	    val /= 256;
181	    len--;
182	    l++;
183	}
184	*p = 0x80 | l;
185	if(size)
186	    *size = l + 1;
187    }
188    return 0;
189}
190
191static int
192fuzzer_put_tag (unsigned char *p, size_t len, Der_class class, Der_type type,
193		unsigned int tag, size_t *size)
194{
195    unsigned fcont = 0;
196
197    if (tag <= 30) {
198	if (len < 1)
199	    return ASN1_OVERFLOW;
200	if (fuzzer_trigger(100))
201	    *p = MAKE_TAG(class, type, 0x1f);
202	else
203	    *p = MAKE_TAG(class, type, tag);
204	*size = 1;
205    } else {
206	size_t ret = 0;
207	unsigned int continuation = 0;
208
209	do {
210	    if (len < 1)
211		return ASN1_OVERFLOW;
212	    *p-- = tag % 128 | continuation;
213	    len--;
214	    ret++;
215	    tag /= 128;
216	    continuation = 0x80;
217	} while(tag > 0);
218	if (len < 1)
219	    return ASN1_OVERFLOW;
220	if (fuzzer_trigger(100))
221	    *p-- = MAKE_TAG(class, type, 0);
222	else
223	    *p-- = MAKE_TAG(class, type, 0x1f);
224	ret++;
225	*size = ret;
226    }
227    return 0;
228}
229
230static int
231fuzzer_put_length_and_tag (unsigned char *p, size_t len, size_t len_val,
232			   Der_class class, Der_type type,
233			   unsigned int tag, size_t *size)
234{
235    size_t ret = 0;
236    size_t l;
237    int e;
238
239    e = fuzzer_put_length (p, len, len_val, &l);
240    if(e)
241	return e;
242    p -= l;
243    len -= l;
244    ret += l;
245    e = fuzzer_put_tag (p, len, class, type, tag, &l);
246    if(e)
247	return e;
248
249    ret += l;
250    *size = ret;
251    return 0;
252}
253
254static int
255fuzzer_put_general_string (unsigned char *p, size_t len,
256			   const heim_general_string *str, size_t *size)
257{
258    size_t slen = strlen(*str);
259
260    if (len < slen)
261	return ASN1_OVERFLOW;
262    p -= slen;
263    if (slen >= 2 && fuzzer_trigger(100)) {
264	memcpy(p+1, *str, slen);
265	memcpy(p+1, "%s", 2);
266    } else if (slen >= 2 && fuzzer_trigger(100)) {
267	memcpy(p+1, *str, slen);
268	memcpy(p+1, "%n", 2);
269    } else if (slen >= 4 && fuzzer_trigger(100)) {
270	memcpy(p+1, *str, slen);
271	memcpy(p+1, "%10n", 4);
272    } else if (slen >= 10 && fuzzer_trigger(100)) {
273	memcpy(p+1, *str, slen);
274	memcpy(p+1, "%n%n%n%n%n", 10);
275    } else if (slen >= 10 && fuzzer_trigger(100)) {
276	memcpy(p+1, *str, slen);
277	memcpy(p+1, "%n%p%s%d%x", 10);
278    } else if (slen >= 7 && fuzzer_trigger(100)) {
279	memcpy(p+1, *str, slen);
280	memcpy(p+1, "%.1024d", 7);
281    } else if (slen >= 7 && fuzzer_trigger(100)) {
282	memcpy(p+1, *str, slen);
283	memcpy(p+1, "%.2049d", 7);
284    } else if (fuzzer_trigger(100)) {
285	memset(p+1, 0, slen);
286    } else if (fuzzer_trigger(100)) {
287	memset(p+1, 0xff, slen);
288    } else if (fuzzer_trigger(100)) {
289	memset(p+1, 'A', slen);
290    } else {
291	memcpy(p+1, *str, slen);
292    }
293    *size = slen;
294    return 0;
295}
296
297
298struct asn1_type_func fuzzerprim[A1T_NUM_ENTRY] = {
299#define fuzel(name, type) {				\
300	(asn1_type_encode)fuzzer_put_##name,		\
301	(asn1_type_decode)der_get_##name,		\
302	(asn1_type_length)der_length_##name,		\
303	(asn1_type_copy)der_copy_##name,		\
304	(asn1_type_release)der_free_##name,		\
305	sizeof(type)					\
306    }
307#define el(name, type) {				\
308	(asn1_type_encode)der_put_##name,		\
309	(asn1_type_decode)der_get_##name,		\
310	(asn1_type_length)der_length_##name,		\
311	(asn1_type_copy)der_copy_##name,		\
312	(asn1_type_release)der_free_##name,		\
313	sizeof(type)					\
314    }
315#define elber(name, type) {				\
316	(asn1_type_encode)der_put_##name,		\
317	(asn1_type_decode)der_get_##name##_ber,		\
318	(asn1_type_length)der_length_##name,		\
319	(asn1_type_copy)der_copy_##name,		\
320	(asn1_type_release)der_free_##name,		\
321	sizeof(type)					\
322    }
323    el(integer, int),
324    el(integer64, int64_t),
325    el(heim_integer, heim_integer),
326    el(integer, int),
327    el(unsigned, unsigned),
328    el(uninteger64, uint64_t),
329    fuzel(general_string, heim_general_string),
330    el(octet_string, heim_octet_string),
331    elber(octet_string, heim_octet_string),
332    el(ia5_string, heim_ia5_string),
333    el(bmp_string, heim_bmp_string),
334    el(universal_string, heim_universal_string),
335    el(printable_string, heim_printable_string),
336    el(visible_string, heim_visible_string),
337    el(utf8string, heim_utf8_string),
338    el(generalized_time, time_t),
339    el(utctime, time_t),
340    el(bit_string, heim_bit_string),
341    { (asn1_type_encode)der_put_boolean, (asn1_type_decode)der_get_boolean,
342      (asn1_type_length)der_length_boolean, (asn1_type_copy)der_copy_integer,
343      (asn1_type_release)der_free_integer, sizeof(int)
344    },
345    el(oid, heim_oid),
346    el(general_string, heim_general_string),
347#undef fuzel
348#undef el
349#undef elber
350};
351
352
353
354int
355_asn1_encode_fuzzer(const struct asn1_template *t,
356		    unsigned char *p, size_t len,
357		    const void *data, size_t *size)
358{
359    size_t elements = A1_HEADER_LEN(t);
360    int ret = 0;
361    size_t oldlen = len;
362
363    t += A1_HEADER_LEN(t);
364
365    while (elements) {
366	switch (t->tt & A1_OP_MASK) {
367	case A1_OP_TYPE:
368	case A1_OP_TYPE_EXTERN: {
369	    size_t newsize;
370	    const void *el = DPOC(data, t->offset);
371
372	    if (t->tt & A1_FLAG_OPTIONAL) {
373		void **pel = (void **)el;
374		if (*pel == NULL)
375		    break;
376		el = *pel;
377	    }
378
379	    if ((t->tt & A1_OP_MASK) == A1_OP_TYPE) {
380		ret = _asn1_encode_fuzzer(t->ptr, p, len, el, &newsize);
381	    } else {
382		const struct asn1_type_func *f = t->ptr;
383		ret = (f->encode)(p, len, el, &newsize);
384	    }
385
386	    if (ret)
387		return ret;
388	    p -= newsize; len -= newsize;
389
390	    break;
391	}
392	case A1_OP_TAG: {
393	    const void *olddata = data;
394	    size_t l, datalen;
395
396	    data = DPOC(data, t->offset);
397
398	    if (t->tt & A1_FLAG_OPTIONAL) {
399		void **el = (void **)data;
400		if (*el == NULL) {
401		    data = olddata;
402		    break;
403		}
404		data = *el;
405	    }
406
407	    ret = _asn1_encode_fuzzer(t->ptr, p, len, data, &datalen);
408	    if (ret)
409		return ret;
410
411	    len -= datalen; p -= datalen;
412
413	    ret = fuzzer_put_length_and_tag(p, len, datalen,
414					    A1_TAG_CLASS(t->tt),
415					    A1_TAG_TYPE(t->tt),
416					    A1_TAG_TAG(t->tt), &l);
417	    if (ret)
418		return ret;
419
420	    p -= l; len -= l;
421
422	    data = olddata;
423
424	    break;
425	}
426	case A1_OP_PARSE: {
427	    unsigned int type = A1_PARSE_TYPE(t->tt);
428	    size_t newsize;
429	    const void *el = DPOC(data, t->offset);
430
431	    if (type > sizeof(fuzzerprim)/sizeof(fuzzerprim[0])) {
432		ABORT_ON_ERROR();
433		return ASN1_PARSE_ERROR;
434	    }
435
436	    ret = (fuzzerprim[type].encode)(p, len, el, &newsize);
437	    if (ret)
438		return ret;
439	    p -= newsize; len -= newsize;
440
441	    break;
442	}
443	case A1_OP_SETOF: {
444	    const struct template_of *el = DPOC(data, t->offset);
445	    size_t ellen = _asn1_sizeofType(t->ptr);
446	    heim_octet_string *val;
447	    unsigned char *elptr = el->val;
448	    size_t i, totallen;
449
450	    if (el->len == 0)
451		break;
452
453	    if (el->len > UINT_MAX/sizeof(val[0]))
454		return ERANGE;
455
456	    val = malloc(sizeof(val[0]) * el->len);
457	    if (val == NULL)
458		return ENOMEM;
459
460	    for(totallen = 0, i = 0; i < el->len; i++) {
461		unsigned char *next;
462		size_t l;
463
464		val[i].length = _asn1_length(t->ptr, elptr);
465		val[i].data = malloc(val[i].length);
466
467		ret = _asn1_encode_fuzzer(t->ptr, DPO(val[i].data, val[i].length - 1),
468					  val[i].length, elptr, &l);
469		if (ret)
470		    break;
471
472		next = elptr + ellen;
473		if (next < elptr) {
474		    ret = ASN1_OVERFLOW;
475		    break;
476		}
477		elptr = next;
478		totallen += val[i].length;
479	    }
480	    if (ret == 0 && totallen > len)
481		ret = ASN1_OVERFLOW;
482	    if (ret) {
483		do {
484		    free(val[i].data);
485		} while(i-- > 0);
486		free(val);
487		return ret;
488	    }
489
490	    len -= totallen;
491
492	    qsort(val, el->len, sizeof(val[0]), _heim_der_set_sort);
493
494	    i = el->len - 1;
495	    do {
496		p -= val[i].length;
497		memcpy(p + 1, val[i].data, val[i].length);
498		free(val[i].data);
499	    } while(i-- > 0);
500	    free(val);
501
502	    break;
503
504	}
505	case A1_OP_SEQOF: {
506	    struct template_of *el = DPO(data, t->offset);
507	    size_t ellen = _asn1_sizeofType(t->ptr);
508	    size_t newsize;
509	    unsigned int i;
510	    unsigned char *elptr = el->val;
511
512	    if (el->len == 0)
513		break;
514
515	    elptr += ellen * (el->len - 1);
516
517	    for (i = 0; i < el->len; i++) {
518		ret = _asn1_encode_fuzzer(t->ptr, p, len,
519				   elptr,
520				   &newsize);
521		if (ret)
522		    return ret;
523		p -= newsize; len -= newsize;
524		elptr -= ellen;
525	    }
526
527	    break;
528	}
529	case A1_OP_BMEMBER: {
530	    const struct asn1_template *bmember = t->ptr;
531	    size_t size = bmember->offset;
532	    size_t elements = A1_HEADER_LEN(bmember);
533	    size_t pos;
534	    unsigned char c = 0;
535	    unsigned int bitset = 0;
536	    int rfc1510 = (bmember->tt & A1_HBF_RFC1510);
537
538	    bmember += elements;
539
540	    if (rfc1510)
541		pos = 31;
542	    else
543		pos = bmember->offset;
544
545	    while (elements && len) {
546		while (bmember->offset / 8 < pos / 8) {
547		    if (rfc1510 || bitset || c) {
548			if (len < 1)
549			    return ASN1_OVERFLOW;
550			*p-- = c; len--;
551		    }
552		    c = 0;
553		    pos -= 8;
554		}
555		_asn1_bmember_put_bit(&c, data, bmember->offset, size, &bitset);
556		elements--; bmember--;
557	    }
558	    if (rfc1510 || bitset) {
559		if (len < 1)
560		    return ASN1_OVERFLOW;
561		*p-- = c; len--;
562	    }
563
564	    if (len < 1)
565		return ASN1_OVERFLOW;
566	    if (rfc1510 || bitset == 0)
567		*p-- = 0;
568	    else
569		*p-- = bitset - 1;
570
571	    len--;
572
573	    break;
574	}
575	case A1_OP_CHOICE: {
576	    const struct asn1_template *choice = t->ptr;
577	    const unsigned int *element = DPOC(data, choice->offset);
578	    size_t datalen;
579	    const void *el;
580
581	    if (*element > A1_HEADER_LEN(choice)) {
582		printf("element: %d\n", *element);
583		return ASN1_PARSE_ERROR;
584	    }
585
586	    if (*element == 0) {
587		ret += der_put_octet_string(p, len,
588					    DPOC(data, choice->tt), &datalen);
589	    } else {
590		choice += *element;
591		el = DPOC(data, choice->offset);
592		ret = _asn1_encode_fuzzer(choice->ptr, p, len, el, &datalen);
593		if (ret)
594		    return ret;
595	    }
596	    len -= datalen; p -= datalen;
597
598	    break;
599	}
600	default:
601	    ABORT_ON_ERROR();
602	}
603	t--;
604	elements--;
605    }
606
607    if (fuzzer_trigger(1000)) {
608	memset(p + 1, 0, oldlen - len);
609    } else if (fuzzer_trigger(1000)) {
610	memset(p + 1, 0x41, oldlen - len);
611    } else if (fuzzer_trigger(1000)) {
612	memset(p + 1, 0xff, oldlen - len);
613    }
614
615    if (size)
616	*size = oldlen - len;
617
618    return 0;
619}
620
621size_t
622_asn1_length_fuzzer(const struct asn1_template *t, const void *data)
623{
624    size_t elements = A1_HEADER_LEN(t);
625    size_t ret = 0;
626
627    t += A1_HEADER_LEN(t);
628
629    while (elements) {
630	switch (t->tt & A1_OP_MASK) {
631	case A1_OP_TYPE:
632	case A1_OP_TYPE_EXTERN: {
633	    const void *el = DPOC(data, t->offset);
634
635	    if (t->tt & A1_FLAG_OPTIONAL) {
636		void **pel = (void **)el;
637		if (*pel == NULL)
638		    break;
639		el = *pel;
640	    }
641
642	    if ((t->tt & A1_OP_MASK) == A1_OP_TYPE) {
643		ret += _asn1_length(t->ptr, el);
644	    } else {
645		const struct asn1_type_func *f = t->ptr;
646		ret += (f->length)(el);
647	    }
648	    break;
649	}
650	case A1_OP_TAG: {
651	    size_t datalen;
652	    const void *olddata = data;
653
654	    data = DPO(data, t->offset);
655
656	    if (t->tt & A1_FLAG_OPTIONAL) {
657		void **el = (void **)data;
658		if (*el == NULL) {
659		    data = olddata;
660		    break;
661		}
662		data = *el;
663	    }
664	    datalen = _asn1_length(t->ptr, data);
665	    ret += der_length_tag(A1_TAG_TAG(t->tt)) + fuzzer_length_len(datalen);
666	    ret += datalen;
667	    data = olddata;
668	    break;
669	}
670	case A1_OP_PARSE: {
671	    unsigned int type = A1_PARSE_TYPE(t->tt);
672	    const void *el = DPOC(data, t->offset);
673
674	    if (type >= sizeof(asn1_template_prim)/sizeof(asn1_template_prim[0])) {
675		ABORT_ON_ERROR();
676		break;
677	    }
678	    ret += (asn1_template_prim[type].length)(el);
679	    break;
680	}
681	case A1_OP_SETOF:
682	case A1_OP_SEQOF: {
683	    const struct template_of *el = DPOC(data, t->offset);
684	    size_t ellen = _asn1_sizeofType(t->ptr);
685	    const unsigned char *element = el->val;
686	    unsigned int i;
687
688	    for (i = 0; i < el->len; i++) {
689		ret += _asn1_length(t->ptr, element);
690		element += ellen;
691	    }
692
693	    break;
694	}
695	case A1_OP_BMEMBER: {
696	    const struct asn1_template *bmember = t->ptr;
697	    size_t size = bmember->offset;
698	    size_t elements = A1_HEADER_LEN(bmember);
699	    int rfc1510 = (bmember->tt & A1_HBF_RFC1510);
700
701	    if (rfc1510) {
702		ret += 5;
703	    } else {
704
705		ret += 1;
706
707		bmember += elements;
708
709		while (elements) {
710		    if (_asn1_bmember_isset_bit(data, bmember->offset, size)) {
711			ret += (bmember->offset / 8) + 1;
712			break;
713		    }
714		    elements--; bmember--;
715		}
716	    }
717	    break;
718	}
719	case A1_OP_CHOICE: {
720	    const struct asn1_template *choice = t->ptr;
721	    const unsigned int *element = DPOC(data, choice->offset);
722
723	    if (*element > A1_HEADER_LEN(choice))
724		break;
725
726	    if (*element == 0) {
727		ret += der_length_octet_string(DPOC(data, choice->tt));
728	    } else {
729		choice += *element;
730		ret += _asn1_length(choice->ptr, DPOC(data, choice->offset));
731	    }
732	    break;
733	}
734	default:
735	    ABORT_ON_ERROR();
736	    break;
737	}
738	elements--;
739	t--;
740    }
741    return ret;
742}
743
744#endif /* ASN1_FUZZER */
745