Adding upstream version 2:4.17.12+dfsg.upstream/2%4.17.12+dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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 0000000..9f1b60f
--- /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
+```