From: Bill Fenner Date: Tue, 11 Oct 2022 20:10:46 +0000 (-0700) Subject: ISO: avoid undefined behavior and integer overflow in the fletcher checksum calculation X-Git-Url: https://git.tcpdump.org/tcpdump/commitdiff_plain/2634bd1c16c3914d7809b925ecaeb3fcf7af65cc ISO: avoid undefined behavior and integer overflow in the fletcher checksum calculation The fletcher checksum calculation would sometimes left-shift a negative number, which is an undefined operation. Rework the code to avoid this. checksum.c:186:20: runtime error: left shift of negative value -36 SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior checksum.c:186:20 Unlike some checksum routines that use the defined semantics of 2's-complement unsigned overflow to their advantage, this one gets the wrong value if it is allowed to overflow, due to the use of mod-255. Convert c1 to uint64_t to avoid overflow. checksum.c:163:16: runtime error: unsigned integer overflow: NNN + NNN cannot be represented in type 'unsigned int' Use integers during subtraction to avoid implicit conversion to unsigned when calculating both x and y checksum.c:172:18: runtime error: unsigned integer overflow: NNN - NNN cannot be represented in type 'unsigned int' checksum.c:172:9: runtime error: implicit conversion from type 'unsigned int' of value NNN (32-bit, unsigned) to type 'int' changed the value to -NNN (32-bit, signed) checksum.c:173:12: runtime error: unsigned integer overflow: NNN - NNN cannot be represented in type 'unsigned int' checksum.c:173:9: runtime error: implicit conversion from type 'unsigned int' of value NNN (32-bit, unsigned) to type 'int' changed the value to -NNN (32-bit, signed) (backported from commit c5b54bfbd68b03f7997feaa277db30d399975a4d) --- diff --git a/checksum.c b/checksum.c index 4bb97f1e..bb07664d 100644 --- a/checksum.c +++ b/checksum.c @@ -106,9 +106,9 @@ create_osi_cksum (const uint8_t *pptr, int checksum_offset, int length) int x; int y; - uint32_t mul; + int32_t mul; uint32_t c0; - uint32_t c1; + uint64_t c1; uint16_t checksum; int idx; @@ -134,21 +134,23 @@ create_osi_cksum (const uint8_t *pptr, int checksum_offset, int length) mul = (length - checksum_offset)*(c0); - x = mul - c0 - c1; - y = c1 - mul - 1; - - if ( y >= 0 ) y++; - if ( x < 0 ) x--; + /* + * Casting c0 and c1 here is guaranteed to be safe, because we know + * they have values between 0 and 254 inclusive. These casts are + * done to ensure that all of the arithmetic operations are + * well-defined (i.e., not mixing signed and unsigned integers). + */ + x = mul - (int)c0 - (int)c1; + y = (int)c1 - mul; x %= 255; y %= 255; - - if (x == 0) x = 255; - if (y == 0) y = 255; + if (x <= 0) x += 255; + if (y <= 0) y += 255; y &= 0x00FF; - checksum = ((x << 8) | y); + checksum = (uint16_t)((x << 8) | y); return checksum; } diff --git a/tests/TESTLIST b/tests/TESTLIST index c8b43ab1..f312035d 100644 --- a/tests/TESTLIST +++ b/tests/TESTLIST @@ -896,3 +896,4 @@ ip6-snmp-oid-unsigned ip6-snmp-oid-unsigned.pcap ip6-snmp-oid-unsigned.out lwres-pointer-arithmetic-ub lwres-pointer-arithmetic-ub.pcap lwres-pointer-arithmetic-ub.out ospf-signed-integer-ubsan ospf-signed-integer-ubsan.pcap ospf-signed-integer-ubsan.out -vv bgp-ub bgp-ub.pcap bgp-ub.out -v +fletcher-checksum-negative-shift fletcher-checksum-negative-shift.pcap fletcher-checksum-negative-shift.out -v diff --git a/tests/fletcher-checksum-negative-shift.out b/tests/fletcher-checksum-negative-shift.out new file mode 100644 index 00000000..36134a5a --- /dev/null +++ b/tests/fletcher-checksum-negative-shift.out @@ -0,0 +1,41 @@ + 1 2022-03-20 13:44:56.520846 IS-IS, length 495 + L2 LSP, hlen: 27, v: 1, pdu-v: 1, sys-id-len: 6 (0), max-area: 3 (0) + lsp-id: 0192.0168.0001.00-00, seq: 0x0000000b, lifetime: 1196s + chksum: 0xc074 (incorrect should be 0xdc23), PDU length: 495, Flags: [ L2 IS ] + Area address(es) TLV #1, length: 4 + Area address (length: 3): 49.0002 + LSP Buffersize TLV #14, length: 2 + LSP Buffersize: 1426 + Area address(es) TLV #1, length: 104 + Area address (length: 0): isonsap_string: illegal length + Area address (length: 1): 00 + Area address (length: 0): isonsap_string: illegal length + Area address (length: 0): isonsap_string: illegal length + Area address (length: 0): isonsap_string: illegal length + Area address (length: 0): isonsap_string: illegal length + Area address (length: 11): c0.7403.0104.0349.0002.0e02 + Area address (length: 5): d4.8102.cc8e + Partition DIS TLV #4, length: 8 + 0000.0180.0000 + unknown TLV #11, length: 32 + 0x0000: 4cee 6b28 4cee 6b28 4cee 6b28 4cee 6b28 + 0x0010: 4cee 6b28 4cee 6b28 4cee 6b28 4cee 6b28 + Authentication TLV #10, length: 4 + unknown Authentication type 0x4c: + 0x0000: ee6b 28 + LSP entries TLV #9, length: 4 + ES Neighbor(s) TLV #3, length: 4 + unknown TLV #32, length: 11 + 0x0000: 3000 0192 0168 0002 0000 12 + Area address(es) TLV #1, length: 146 + Area address (length: 1): 68 + Area address (length: 0): isonsap_string: illegal length + Area address (length: 3): 02.0000 + Area address (length: 63): isonsap_string: illegal length + Area address (length: 3): 04.0000 + Area address (length: 0): isonsap_string: illegal length + Area address (length: 0): isonsap_string: illegal length + Area address (length: 32): isonsap_string: illegal length + Area address (length: 8): 00.0001.8300.0000.00 + Area address (length: 11): 20.4cee.6b28.4cee.6b28.4cee + unknown TLV #76, length: 238 [|isis] diff --git a/tests/fletcher-checksum-negative-shift.pcap b/tests/fletcher-checksum-negative-shift.pcap new file mode 100644 index 00000000..63c39f3e Binary files /dev/null and b/tests/fletcher-checksum-negative-shift.pcap differ