sleb128 values near INT64_MAX/MIN are not correctly read since: commit 65a211f9028304757df8f4fa7cb3cc77d1501420 Author: Mark Wielaard <mjw@redhat.com> Date: Wed Apr 22 12:28:30 2015 +0200 libdw: Undefined behavior in get_sleb128_step. gcc -fsanitize=undefined pointed out that for too big sleb128 values we could shift into the sign bit. So for sleb128 values that have to fit in a (signed) int64_t variable reduce the max number of steps by one. https://bugzilla.redhat.com/show_bug.cgi?id=1170810#c29 Signed-off-by: Mark Wielaard <mjw@redhat.com> The idea was the we didn't want to shift 1 << (9 * 7) since that would shift 63 places in a signed value (which is undefined behavior). Where 9 is the number of bytes/steps (counting from zero). But sleb128 values near INT64_MIN/MAX are represented by 10 bytes. Where the 10th byte doesn't have its high bit set to indicate it is the last one. So for sleb128 values that use 10 bytes we fail to read all and return INT64_MAX. The reason we haven't seen this before is because normally using data8 is cheaper for representing such values (if we know the type is signed). But with DWARF5 we might be able to share the value between DIEs using DW_FORM_implicit_const (which is represented in the abbrev itself using an sleb128). An example that triggers this is: #include <stdint.h> int foo () { int64_t maxA, maxB, maxC; maxA = maxB = maxC = INT64_MAX - 16; /* 9223372036854775791 */ int64_t minA, minB, minC; minA = minB = minC = INT64_MIN + 16; /* -9223372036854775792 */ return (maxA + maxB + maxC + minA + minB + minC); } compiled with gcc -gdwarf-5 -g -O2 -c consts.c $ eu-readelf --debug-dump=abbrev consts.o DWARF section [ 6] '.debug_abbrev' at offset 0x114: [ Code] Abbreviation section at offset 0: [ 1] offset: 0, children: no, tag: base_type attr: byte_size, form: data1, offset: 0 attr: encoding, form: data1, offset: 0x2 attr: name, form: strp, offset: 0x4 [ 2] offset: 11, children: no, tag: variable attr: name, form: strp, offset: 0xb attr: decl_file, form: implicit_const (1), offset: 0xd attr: decl_line, form: implicit_const (5), offset: 0x10 attr: decl_column, form: data1, offset: 0x13 attr: type, form: ref4, offset: 0x15 attr: const_value, form: implicit_const (9223372036854775807), offset: 0x17 Abbreviation section at offset 40: [ 3] offset: 40, children: no, tag: variable attr: name, form: strp, offset: 0x28 attr: decl_file, form: implicit_const (1), offset: 0x2a attr: decl_line, form: implicit_const (8), offset: 0x2d attr: decl_column, form: data1, offset: 0x30 attr: type, form: ref4, offset: 0x32 attr: const_value, form: implicit_const (9223372036854775807), offset: 0x34 attr: call_origin, form: ??? (0), offset: 0x3f attr: ??? (0), form: block4, offset: 0x41 [...] Note how both values are read as INT64_MAX and that after (what is supposed to be the negative value -9223372036854775792) the rest of the abbrev is read wrongly: $ eu-readelf --debug-dump=info consts.o DWARF section [ 4] '.debug_info' at offset 0x46: [Offset] Compilation unit at offset 0: Version: 5, Abbreviation section offset: 0, Address size: 8, Offset size: 4 Unit type: compile (1) eu-readelf: cannot get tag of DIE at offset [c] in section '.debug_info': invalid DWARF We have to allow reading 10-byte sleb128 values without triggering undefined behavior.
I looked at this a little today. In addition to this bug, I think the _unchecked variants have another bug; namely they do: const size_t max = len_leb128 (int64_t) - 1; This limits the number of bytes read-- but it seems like it maybe ought to read until the first byte without the high bit set. FWIW gdb seems to rely on implementation-defined behavior here. It does all the sleb work in an unsigned type and then casts it to signed on return.
(In reply to Tom Tromey from comment #1) > This limits the number of bytes read-- but it seems like > it maybe ought to read until the first byte without the > high bit set. Beware, golang just dealt with a CVE for reading unlimited varints: https://github.com/golang/go/issues/40618 (But the context is different since that's used in stuff like protocol buffers that may be streamed.)
(In reply to Tom Tromey from comment #1) > I looked at this a little today. > > In addition to this bug, I think the _unchecked variants > have another bug; namely they do: > > const size_t max = len_leb128 (int64_t) - 1; > > This limits the number of bytes read-- but it seems like > it maybe ought to read until the first byte without the > high bit set. Yes, that is the bug (plus the same -1 we do inside __libdw_max_len_sleb128 for the "checked" variant. > FWIW gdb seems to rely on implementation-defined behavior > here. It does all the sleb work in an unsigned type > and then casts it to signed on return. That would probably work. Is the implementation-defined part that it depends on signed numbers being represented as Two's complement? In that case I think we are fine with that as fix.
(In reply to Josh Stone from comment #2) > (In reply to Tom Tromey from comment #1) > > This limits the number of bytes read-- but it seems like > > it maybe ought to read until the first byte without the > > high bit set. > > Beware, golang just dealt with a CVE for reading unlimited varints: > https://github.com/golang/go/issues/40618 > > (But the context is different since that's used in stuff like protocol > buffers that may be streamed.) Note that there are two "limits" in play here. For the normal get_sleb128 (__libdw_get_sleb128) variant we already require that and end pointer is provided, which we won't move past. We require the caller to make sure we can read at least the first byte. For the get_sleb128_unchecked (__libdw_get_sleb128_unchecked) variant we assume the called already knows there is a valid sleb128 at the given address, so we don't require an end pointer and can just read till the end (first byte that doesn't have the high bit set). The other limit is that we only read as many bytes that can "fit" the type. That is the "step limit" which is given by len_leb128 (int64_t) (or __libdw_max_len_uleb128/__libdw_max_len_sleb128 for the unchecked variant). This limits makes sure we don't "overflow" the int64_t or uint64_t. So we normally only read 10 bytes anyway. The bug is in "the other limit". For signed types we subtract 1 to make sure we didn't shift into the sign bit. But that means we can only read up to 9 bytes of the sleb128 and will fail (return INT64_MAX and leave the addr pointer at the last byte instead of consuming it). I think Tom's suggestion to use an unsigned type for the sleb128 calculation and then cast it to int64_t when done is the correct fix.
commit 70343f484481184f9fa216071399690ff833256b Author: Tom Tromey <tom@tromey.com> Date: Wed Oct 28 17:26:42 2020 -0600 Fix leb128 reading PR 26773 points out that some sleb128 values are decoded incorrectly. This version of the fix only examines the sleb128 conversion. Overlong encodings are not handled, and the uleb128 decoders are not touched. The approach taken here is to do the work in an unsigned type, and then rely on an implementation-defined cast to convert to signed. Signed-off-by: Tom Tromey <tom@tromey.com>