lib/asn1/README-template.md

   1
   2 #Notes on Heimdal's ASN.1 compiler's "template" backend
   3
   4 ```bash
   5 size .libs/libasn1.dylib
   6 size .libs/libasn1base.a | awk '{sum += $1} END {print sum}' | sed 's/^/TEXT baselib: /'
   7 size .libs/asn1_*.o | awk '{sum += $1} END {print sum}' | sed 's/^/generated code stubs: /'
   8 size *_asn1-template.o | awk '{sum += $1} END {print sum}' | sed 's/^/TEXT stubs: /'
   9 ```
  10
  11 Notes about the template parser:
  12
  13  - assumption: code is large, tables smaller
  14
  15  - size scales better as features as added:
  16
  17     - adding encoding rules, textual value parsers, comparators, and so on, are
  18       just new template interpreter, and generally that means no change to
  19       templates.
  20
  21     - so template sizing scales like `O(M + N)` where `M` is the size of the
  22       modules and `N` is the size of the interpreters
  23
  24     - but codegen sizing scales like `O(M * N)`
  25
  26     - as we add interpreters the size advantage of templates increases
  27
  28  - smaller tables and code, more memory sharing, smaller cache footprint,
  29    should lead to better performance
  30
  31     - templates are shared for encode/decode/free/copy/print interpreters,
  32       whereas none of those operations as generated by the codegen backend
  33       share any code
  34
  35  - very compressible -- we waste a lot of space in `struct asn1_template` on
  36    64-bit systems, and still it's smaller than the code generated by the
  37    codegen backend
  38
  39    Note that the template backend does currently dedup templates, though that
  40    is a quadratic operation that we may eventually have to make optional (right
  41    now it's not a problem).
  42
  43    If we made the `ptr` field a `uint32_t` instead of a pointer, and wrote a
  44    linker for templates, and squeezed out some bits of `tt` and `offset` (we'll
  45    never need even 8 bits for tags, let alone 20!, and we'll never need 32 bits
  46    for struct sizes and field offsets either, maybe not even 16-bits), we could
  47    cut the size of `struct asn1_template` in half.
  48
  49    Also, once we add OER/JER we could have an option to not support TLV ERs and
  50    then drop a lot of the tag-related parts of the minified AST that templates
  51    are, further shrinking the templates.
  52
  53    The smaller the templates, the faster interpreting will be.
  54
  55  - use explicit stack instead of recursion in template interpreter to reduce
  56    stack use and increase speed
  57
  58    The code generated by the codegen backend is also recursive, though the
  59    compiler could inline some calls.  Using an explicit stack in an iterative
  60    interpreter would likely be a big win.
  61
  62  - how to generate template based stubs
  63
  64    (Note: it's now the default for Heimdal itself.)
  65
  66    Use the `--template` option to `asn1_compile` to use the template backend,
  67    or leave it off to use the codegen backend.
  68
  69  - the template backend now has more functionality than the codegen backend
  70
  71  - much easier to extend!  adding new encoding rules is just adding a few
  72    functions to template.c, one set of length/encode/decode functions per ER,
  73    so we could add OER/PER/XDR/GSER/JER with very little work outside that one
  74    file and `gen_template.c` (to generate stub functions and possibly slight
  75    alterations to templates) and gen.c (to generate declarations of those stub
  76    functions).
  77
  78  - template decoding has been fuzzed extensively with American Fuzzy Lop (AFL)
  79
  80 TODO:
  81
  82  - Generate templates for enumerations, with their names and values, so that
  83    values of enumerated types can be printed.
  84
  85  - Remove old fuzzer.  Rely on AFL only.
  86
  87  - Fuzzing tests, always more fuzzing:
  88
  89     - Instructions:
  90
  91 ```
  92     $ git clone https://github.com/heimdal/heimdal
  93     $ cd heimdal
  94     $ srcdir=$PWD
  95     $ autoreconf -fi
  96     $
  97     $ mkdir build
  98     $ cd build
  99     $
 100     $ ../configure --srcdir=$srcdir ...
 101     $ make -j4
 102     $
 103     $ cd lib/asn1
 104     $ make clean
 105     $ AFL_HARDEN=1 make -j4 asn1_print check CC=afl-gcc # or CC=afl-clang
 106     $
 107     $ # $srcdir/lib/asn1/fuzz-inputs/ has at least one minimized DER value
 108     $ # produced by taking an EK certificate and truncating the signatureValue
 109     $ # and tbsCertificate.subjectPublicKeyInfo fields then re-encoding, thus
 110     $ # cutting down the size of the certificate by 45%.  AFL finds interesting
 111     $ # code paths much faster if the input corpus is minimized.
 112     $
 113     $ mkdir f
 114     $ ../../libtool --mode=execute afl-fuzz -i $srcdir/lib/asn1/fuzz-inputs -o $PWD/f ./asn1_print '@@' Certificate
 115     $
 116     $ # Or
 117     $ ../../libtool --mode=execute afl-fuzz -i $srcdir/lib/asn1/fuzz-inputs -o $PWD/f ./asn1_print -A '@@'
 118     $
 119     $ # Examine crash reports, if any.  Each crash report consists of an input
 120     $ # that caused a crash, so run valgrind on each such input:
 121     $
 122     $ for i in f/crashes/id*; do
 123     >   echo $i
 124     >   ../../libtool --mode=execute valgrind --num-callers=64 ./asn1_print $i \
 125     >        Certificate IOSCertificationRequest >/dev/null 2> f/crashes/vg-${i##*/}
 126     > done
 127     $
 128     $ # then review the valgrind output:
 129     $ $PAGER f/crashes/vg-*
 130 ```
 131
 132     - Here's a screenshot of AFL running on the previous commit:
 133
 134 ```
 135                      american fuzzy lop 2.52b (asn1_print)
 136
 137 ┌─ process timing ─────────────────────────────────────┬─ overall results ─────┐
 138 │        run time : 1 days, 22 hrs, 39 min, 51 sec     │  cycles done : 18     │
 139 │   last new path : 0 days, 0 hrs, 38 min, 5 sec       │  total paths : 2310   │
 140 │ last uniq crash : none seen yet                      │ uniq crashes : 0      │
 141 │  last uniq hang : none seen yet                      │   uniq hangs : 0      │
 142 ├─ cycle progress ────────────────────┬─ map coverage ─┴───────────────────────┤
 143 │  now processing : 997* (43.16%)     │    map density : 2.19% / 8.74%         │
 144 │ paths timed out : 0 (0.00%)         │ count coverage : 3.25 bits/tuple       │
 145 ├─ stage progress ────────────────────┼─ findings in depth ────────────────────┤
 146 │  now trying : interest 16/8         │ favored paths : 319 (13.81%)           │
 147 │ stage execs : 13.1k/13.4k (98.18%)  │  new edges on : 506 (21.90%)           │
 148 │ total execs : 91.9M                 │ total crashes : 0 (0 unique)           │
 149 │  exec speed : 576.2/sec             │  total tmouts : 2158 (180 unique)      │
 150 ├─ fuzzing strategy yields ───────────┴───────────────┬─ path geometry ────────┤
 151 │   bit flips : 565/5.60M, 124/5.60M, 74/5.59M        │    levels : 19         │
 152 │  byte flips : 4/699k, 17/375k, 15/385k              │   pending : 552        │
 153 │ arithmetics : 323/20.7M, 8/10.6M, 1/517k            │  pend fav : 0          │
 154 │  known ints : 85/1.76M, 148/9.98M, 175/16.8M        │ own finds : 2308       │
 155 │  dictionary : 0/0, 0/0, 12/6.62M                    │  imported : n/a        │
 156 │       havoc : 757/6.35M, 0/0                        │ stability : 100.00%    │
 157 │        trim : 14.30%/336k, 46.60%                   ├────────────────────────┘
 158 └─────────────────────────────────────────────────────┘          [cpu000:196%]
 159 ```
 160
 161     - TODO: Make building with AFL a ./cofigure option.
 162
 163     - TODO: Make fuzzing with AFL a make target.
 164
 165     - Fuzz decode round-tripping (don't just decode, but also encoded the
 166       decoded).
 167
 168  - Performance testing
 169
 170  - `ASN1_MALLOC_ENCODE()` as a function, replaces `encode_` and `length_`
 171
 172  - Fix SIZE constraits
 173
 174  - Proper implementation of `SET { ... }`
 175
 176  - Compact types that only contain on entry to not having a header.
 177
 178
 179 SIZE - Futher down is later generations of the template parser
 180
 181 ```
 182         code:
 183         ==================
 184         __TEXT  __DATA  __OBJC  others  dec     hex
 185         462848  12288   0       323584  798720  c3000 (O2)
 186
 187         trivial types:
 188         ==================
 189         __TEXT  __DATA  __OBJC  others  dec     hex
 190         446464  12288   0       323584  782336  bf000 (O2)
 191
 192         OPTIONAL
 193         ==================
 194         __TEXT  __DATA  __OBJC  others  dec     hex
 195         425984  16384   0       323584  765952  bb000 (O2)
 196
 197         SEQ OF
 198         ==================
 199         __TEXT  __DATA  __OBJC  others  dec     hex
 200         368640  32768   0       327680  729088  b2000 (O2)
 201         348160  32768   0       327680  708608  ad000 (Os)
 202
 203         BOOLEAN
 204         ==================
 205         339968  32768   0       327680  700416  ab000 (Os)
 206
 207         TYPE_EXTERNAL:
 208         ==================
 209         331776  32768   0       327680  692224  a9000 (Os)
 210
 211         SET OF
 212         ==================
 213         327680  32768   0       327680  688128  a8000 (Os)
 214
 215         TYPE_EXTERNAL everywhere
 216         ==================
 217         __TEXT  __DATA  __OBJC  others  dec     hex
 218         167936  69632   0       327680  565248  8a000 (Os)
 219
 220         TAG uses ->ptr (header and trailer)
 221         ==================
 222         229376  102400  0       421888  753664  b8000 (O0)
 223
 224         TAG uses ->ptr (header only)
 225         ==================
 226         221184  77824   0       421888  720896  b0000 (O0)
 227
 228         BER support for octet string (not working)
 229         ==================
 230         180224  73728   0       417792  671744  a4000 (O2)
 231
 232         CHOICE and BIT STRING missign
 233         ==================
 234         __TEXT  __DATA  __OBJC  others  dec     hex
 235         172032  73728   0       417792  663552  a2000 (Os)
 236
 237         No accessor functions to global variable
 238         ==================
 239         __TEXT  __DATA  __OBJC  others  dec     hex
 240         159744  73728   0       393216  626688  99000 (Os)
 241
 242         All types tables (except choice) (id still objects)
 243         ==================
 244         __TEXT  __DATA  __OBJC  others  dec     hex
 245         167936  77824   0       421888  667648  a3000
 246         base lib: 22820
 247
 248         __TEXT  __DATA  __OBJC  others  dec     hex
 249         ==================
 250         167936  77824   0       421888  667648  a3000 (Os)
 251         baselib: 22820
 252         generated code stubs: 41472
 253         TEXT stubs: 112560
 254
 255         All types, id still objects
 256         ==================
 257         __TEXT  __DATA  __OBJC  others  dec     hex
 258         155648  81920   0       430080  667648  a3000 (Os)
 259         TEXT baselib: 23166
 260         generated code stubs: 20796
 261         TEXT stubs: 119891
 262
 263         All types, id still objects, dup compression
 264         ==================
 265         __TEXT  __DATA  __OBJC  others  dec     hex
 266         143360  65536   0       376832  585728  8f000 (Os)
 267         TEXT baselib: 23166
 268         generated code stubs: 20796
 269         TEXT stubs: 107147
 270
 271         All types, dup compression, id vars
 272         ==================
 273         __TEXT  __DATA  __OBJC  others  dec     hex
 274         131072  65536   0       352256  548864  86000
 275         TEXT baselib: 23166
 276         generated code stubs: 7536
 277         TEXT stubs: 107147
 278 ```