[patch] Arithmetic undef behaviour: sscanf, memeq, scale array, fmt exit status
I've been running a build of tor configured to detect undefined behaviours at runtime (see end for flags).
I have discovered and patched the following commonly executed undefined behaviours in arithmetic operations. I have also expanded the existing unit tests to ensure they test the cases fixed by these patches. (The unit test changes are part of each patch.)
Behavioural Changes
Assuming the original version was compiled using un-optimised (!), wrapping, 2's complement arithmetic; the changes in behaviour after each patch are:
- 01 no overflows, same results (fix test typo)
- 02 no overflows, same results
- 03 avoid creating, multiplying by, and rounding NaNs when n_entries or total are 0; no floating point exceptions, no unspecified results
- 04 no overflows, same results
Code Changes
01 tor_sscanf (util.c 2837 & 2875):
- check for overflow before potentially overflowing computation (post-overflow checks could be optimised out by a compiler: use -fwrapv with gcc/clang to avoid this)
- perform negation without overflowing (scan_signed util.c 2875)
- consolidate and expand unit tests to test formats: u, d, x; flags: (none), l; bit widths: consistently test 4/8 byte ints/longs.
- fix typo in textual UINT32_MAX + 1 in unit tests
02 tor_memeq (di_ops.c 120):
- perform subtraction without underflowing by casting to int32_t first
- update comments to explain why this works regardless of sign-extension on right-shifts of signed negative integers, as long as sizeof(any_difference) > 1
- expand unit tests to exhaustively white-box test all 1-byte bit-pattern differences (256) for tor_memeq (this ensures the cast hasn't broken anything)
- while we're at it, exhaustively test all 1-byte bit-pattern differences (2x256) for tor_memcmp
03 scale_array_elements_to_u64 (routerlist.c 1806):
- if total is 0.0, don't divide by it (this avoids creating, multiplying by, and rounding NaNs - rounding result is unspecified)
- expand unit tests to test cases when n_entries is 0, and when all entries are 0.0 (and therefore total is 0)
- while we're at it, check that we don't read any entries when n_entries is 0 (is this paranoid?)
04 format_helper_exit_status (util.c 3577 [line # after patch 01]):
- perform negation without overflowing (similar to 01 scan_signed util.c 2875)
- expand tests to test 8 byte ints.
Testing
I've tested these changes by running tor as a directory cache; as a client; with a controller (TBB & Vidalia); and as a router (but not an authority). However, I'm convinced there is still some undefined behaviour lurking in less commonly used code. To comprehensively test, we'd need broader test coverage, a tor fuzzer, and/or broad usage with undefined behaviour logging. (Or an excellent, constraint-checking static analyser?)
FYI - these issues were discovered using a tor built with: clang -fsanitize=undefined-trap -fsanitize-undefined-trap-on-error -ftrapv
Version: tor 0.2.6.?-alpha git 781b477b