diff options
Diffstat (limited to 'third_party/heimdal/lib/asn1/README-template.md')
| -rw-r--r-- | third_party/heimdal/lib/asn1/README-template.md | 278 |
1 files changed, 278 insertions, 0 deletions
diff --git a/third_party/heimdal/lib/asn1/README-template.md b/third_party/heimdal/lib/asn1/README-template.md new file mode 100644 index 00000000000..9f1b60fa486 --- /dev/null +++ b/third_party/heimdal/lib/asn1/README-template.md @@ -0,0 +1,278 @@ + +#Notes on Heimdal's ASN.1 compiler's "template" backend + +```bash +size .libs/libasn1.dylib +size .libs/libasn1base.a | awk '{sum += $1} END {print sum}' | sed 's/^/TEXT baselib: /' +size .libs/asn1_*.o | awk '{sum += $1} END {print sum}' | sed 's/^/generated code stubs: /' +size *_asn1-template.o | awk '{sum += $1} END {print sum}' | sed 's/^/TEXT stubs: /' +``` + +Notes about the template parser: + + - assumption: code is large, tables smaller + + - size scales better as features as added: + + - adding encoding rules, textual value parsers, comparators, and so on, are + just new template interpreter, and generally that means no change to + templates. + + - so template sizing scales like `O(M + N)` where `M` is the size of the + modules and `N` is the size of the interpreters + + - but codegen sizing scales like `O(M * N)` + + - as we add interpreters the size advantage of templates increases + + - smaller tables and code, more memory sharing, smaller cache footprint, + should lead to better performance + + - templates are shared for encode/decode/free/copy/print interpreters, + whereas none of those operations as generated by the codegen backend + share any code + + - very compressible -- we waste a lot of space in `struct asn1_template` on + 64-bit systems, and still it's smaller than the code generated by the + codegen backend + + Note that the template backend does currently dedup templates, though that + is a quadratic operation that we may eventually have to make optional (right + now it's not a problem). + + If we made the `ptr` field a `uint32_t` instead of a pointer, and wrote a + linker for templates, and squeezed out some bits of `tt` and `offset` (we'll + never need even 8 bits for tags, let alone 20!, and we'll never need 32 bits + for struct sizes and field offsets either, maybe not even 16-bits), we could + cut the size of `struct asn1_template` in half. + + Also, once we add OER/JER we could have an option to not support TLV ERs and + then drop a lot of the tag-related parts of the minified AST that templates + are, further shrinking the templates. + + The smaller the templates, the faster interpreting will be. + + - use explicit stack instead of recursion in template interpreter to reduce + stack use and increase speed + + The code generated by the codegen backend is also recursive, though the + compiler could inline some calls. Using an explicit stack in an iterative + interpreter would likely be a big win. + + - how to generate template based stubs + + (Note: it's now the default for Heimdal itself.) + + Use the `--template` option to `asn1_compile` to use the template backend, + or leave it off to use the codegen backend. + + - the template backend now has more functionality than the codegen backend + + - much easier to extend! adding new encoding rules is just adding a few + functions to template.c, one set of length/encode/decode functions per ER, + so we could add OER/PER/XDR/GSER/JER with very little work outside that one + file and `gen_template.c` (to generate stub functions and possibly slight + alterations to templates) and gen.c (to generate declarations of those stub + functions). + + - template decoding has been fuzzed extensively with American Fuzzy Lop (AFL) + +TODO: + + - Generate templates for enumerations, with their names and values, so that + values of enumerated types can be printed. + + - Remove old fuzzer. Rely on AFL only. + + - Fuzzing tests, always more fuzzing: + + - Instructions: + +``` + $ git clone https://github.com/heimdal/heimdal + $ cd heimdal + $ srcdir=$PWD + $ autoreconf -fi + $ + $ mkdir build + $ cd build + $ + $ ../configure --srcdir=$srcdir ... + $ make -j4 + $ + $ cd lib/asn1 + $ make clean + $ AFL_HARDEN=1 make -j4 asn1_print check CC=afl-gcc # or CC=afl-clang + $ + $ # $srcdir/lib/asn1/fuzz-inputs/ has at least one minimized DER value + $ # produced by taking an EK certificate and truncating the signatureValue + $ # and tbsCertificate.subjectPublicKeyInfo fields then re-encoding, thus + $ # cutting down the size of the certificate by 45%. AFL finds interesting + $ # code paths much faster if the input corpus is minimized. + $ + $ mkdir f + $ ../../libtool --mode=execute afl-fuzz -i $srcdir/lib/asn1/fuzz-inputs -o $PWD/f ./asn1_print '@@' Certificate + $ + $ # Or + $ ../../libtool --mode=execute afl-fuzz -i $srcdir/lib/asn1/fuzz-inputs -o $PWD/f ./asn1_print -A '@@' + $ + $ # Examine crash reports, if any. Each crash report consists of an input + $ # that caused a crash, so run valgrind on each such input: + $ + $ for i in f/crashes/id*; do + > echo $i + > ../../libtool --mode=execute valgrind --num-callers=64 ./asn1_print $i \ + > Certificate IOSCertificationRequest >/dev/null 2> f/crashes/vg-${i##*/} + > done + $ + $ # then review the valgrind output: + $ $PAGER f/crashes/vg-* +``` + + - Here's a screenshot of AFL running on the previous commit: + +``` + american fuzzy lop 2.52b (asn1_print) + +┌─ process timing ─────────────────────────────────────┬─ overall results ─────┐ +│ run time : 1 days, 22 hrs, 39 min, 51 sec │ cycles done : 18 │ +│ last new path : 0 days, 0 hrs, 38 min, 5 sec │ total paths : 2310 │ +│ last uniq crash : none seen yet │ uniq crashes : 0 │ +│ last uniq hang : none seen yet │ uniq hangs : 0 │ +├─ cycle progress ────────────────────┬─ map coverage ─┴───────────────────────┤ +│ now processing : 997* (43.16%) │ map density : 2.19% / 8.74% │ +│ paths timed out : 0 (0.00%) │ count coverage : 3.25 bits/tuple │ +├─ stage progress ────────────────────┼─ findings in depth ────────────────────┤ +│ now trying : interest 16/8 │ favored paths : 319 (13.81%) │ +│ stage execs : 13.1k/13.4k (98.18%) │ new edges on : 506 (21.90%) │ +│ total execs : 91.9M │ total crashes : 0 (0 unique) │ +│ exec speed : 576.2/sec │ total tmouts : 2158 (180 unique) │ +├─ fuzzing strategy yields ───────────┴───────────────┬─ path geometry ────────┤ +│ bit flips : 565/5.60M, 124/5.60M, 74/5.59M │ levels : 19 │ +│ byte flips : 4/699k, 17/375k, 15/385k │ pending : 552 │ +│ arithmetics : 323/20.7M, 8/10.6M, 1/517k │ pend fav : 0 │ +│ known ints : 85/1.76M, 148/9.98M, 175/16.8M │ own finds : 2308 │ +│ dictionary : 0/0, 0/0, 12/6.62M │ imported : n/a │ +│ havoc : 757/6.35M, 0/0 │ stability : 100.00% │ +│ trim : 14.30%/336k, 46.60% ├────────────────────────┘ +└─────────────────────────────────────────────────────┘ [cpu000:196%] +``` + + - TODO: Make building with AFL a ./cofigure option. + + - TODO: Make fuzzing with AFL a make target. + + - Fuzz decode round-tripping (don't just decode, but also encoded the + decoded). + + - Performance testing + + - `ASN1_MALLOC_ENCODE()` as a function, replaces `encode_` and `length_` + + - Fix SIZE constraits + + - Proper implementation of `SET { ... }` + + - Compact types that only contain on entry to not having a header. + + +SIZE - Futher down is later generations of the template parser + +``` + code: + ================== + __TEXT __DATA __OBJC others dec hex + 462848 12288 0 323584 798720 c3000 (O2) + + trivial types: + ================== + __TEXT __DATA __OBJC others dec hex + 446464 12288 0 323584 782336 bf000 (O2) + + OPTIONAL + ================== + __TEXT __DATA __OBJC others dec hex + 425984 16384 0 323584 765952 bb000 (O2) + + SEQ OF + ================== + __TEXT __DATA __OBJC others dec hex + 368640 32768 0 327680 729088 b2000 (O2) + 348160 32768 0 327680 708608 ad000 (Os) + + BOOLEAN + ================== + 339968 32768 0 327680 700416 ab000 (Os) + + TYPE_EXTERNAL: + ================== + 331776 32768 0 327680 692224 a9000 (Os) + + SET OF + ================== + 327680 32768 0 327680 688128 a8000 (Os) + + TYPE_EXTERNAL everywhere + ================== + __TEXT __DATA __OBJC others dec hex + 167936 69632 0 327680 565248 8a000 (Os) + + TAG uses ->ptr (header and trailer) + ================== + 229376 102400 0 421888 753664 b8000 (O0) + + TAG uses ->ptr (header only) + ================== + 221184 77824 0 421888 720896 b0000 (O0) + + BER support for octet string (not working) + ================== + 180224 73728 0 417792 671744 a4000 (O2) + + CHOICE and BIT STRING missign + ================== + __TEXT __DATA __OBJC others dec hex + 172032 73728 0 417792 663552 a2000 (Os) + + No accessor functions to global variable + ================== + __TEXT __DATA __OBJC others dec hex + 159744 73728 0 393216 626688 99000 (Os) + + All types tables (except choice) (id still objects) + ================== + __TEXT __DATA __OBJC others dec hex + 167936 77824 0 421888 667648 a3000 + base lib: 22820 + + __TEXT __DATA __OBJC others dec hex + ================== + 167936 77824 0 421888 667648 a3000 (Os) + baselib: 22820 + generated code stubs: 41472 + TEXT stubs: 112560 + + All types, id still objects + ================== + __TEXT __DATA __OBJC others dec hex + 155648 81920 0 430080 667648 a3000 (Os) + TEXT baselib: 23166 + generated code stubs: 20796 + TEXT stubs: 119891 + + All types, id still objects, dup compression + ================== + __TEXT __DATA __OBJC others dec hex + 143360 65536 0 376832 585728 8f000 (Os) + TEXT baselib: 23166 + generated code stubs: 20796 + TEXT stubs: 107147 + + All types, dup compression, id vars + ================== + __TEXT __DATA __OBJC others dec hex + 131072 65536 0 352256 548864 86000 + TEXT baselib: 23166 + generated code stubs: 7536 + TEXT stubs: 107147 +``` |