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)

diff --git a/checksum.c b/checksum.c
index 4bb97f1e33f4f23b0c080e751be1dc9a8dc44d44..bb07664dcec7962ec70bc933d8bcd14af176524c 100644 (file)
--- 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 c9dca05d79065ef9e25fb12a4462972349fde5da..86d8fc5b4aba3906f39e192ee51ff0d0969203c1 100644 (file)
--- a/tests/TESTLIST
+++ b/tests/TESTLIST
@@ -1000,6 +1000,7 @@ 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
 
 # AccECN tests
 accecn_handshake       accecn_handshake.pcap           accecn_handshake.out    -v

diff --git a/tests/fletcher-checksum-negative-shift.out b/tests/fletcher-checksum-negative-shift.out
new file mode 100644 (file)
index 0000000..36134a5
--- /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 (file)
index 0000000..63c39f3
Binary files /dev/null and b/tests/fletcher-checksum-negative-shift.pcap differ