1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
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
```
|
