[tor-bugs] #13104 [Tor]: [patch] Arithmetic undef behaviour: sscanf, memeq, scale array, fmt exit status

[Tor Bug Tracker & Wiki]

#13104: [patch] Arithmetic undef behaviour: sscanf, memeq, scale array, fmt exit
status
------------------------+------------------------------------
 Reporter:  teor        |          Owner:
     Type:  defect      |         Status:  new
 Priority:  normal      |      Milestone:
Component:  Tor         |        Version:  Tor: 0.2.5.5-alpha
 Keywords:  tor-router  |  Actual Points:
Parent ID:              |         Points:
------------------------+------------------------------------
 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 781b477bc8af868661450473cdebb5d70312fd61

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/13104>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online