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