Opened 3 years ago

Closed 2 years ago

Last modified 14 months ago

#13104 closed defect (fixed)

[patch] Arithmetic undef behaviour: sscanf, memeq, scale array, fmt exit status

Reported by: teor Owned by: teor
Priority: Medium Milestone: Tor: 0.2.7.x-final
Component: Core Tor/Tor Version: Tor: 0.2.5.5-alpha
Severity: Keywords: tor-router, 025-backport, needs-test, 2016-bug-retrospective
Cc: nickm Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

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

Child Tickets

Attachments (4)

01-sscanf-arith-undef.patch (9.0 KB) - added by teor 3 years ago.
Avoid overflows and underflows in sscanf and friends
03-scale-array-arith-undef.patch (2.0 KB) - added by teor 3 years ago.
Avoid divide by zero and NaNs in scale_array_elements_to_u64
04-fmt-exit-status-arith-undef.patch (2.4 KB) - added by teor 3 years ago.
Avoid an overflow on negation in format_helper_exit_status
02-tor-memeq-arith-undef.patch (1.6 KB) - added by teor 3 years ago.
Even more exhaustively test tor_memeq and tor_memcmp - no tor code changes

Download all attachments as: .zip

Change History (21)

Changed 3 years ago by teor

Avoid overflows and underflows in sscanf and friends

Changed 3 years ago by teor

Avoid divide by zero and NaNs in scale_array_elements_to_u64

Changed 3 years ago by teor

Avoid an overflow on negation in format_helper_exit_status

comment:1 Changed 3 years ago by nickm

What's wrong with the underflow in tor_memeq? I thought unsigned integer underflow was defined.

comment:2 Changed 3 years ago by nickm

  • Keywords 025-backport added
  • Milestone set to Tor: 0.2.6.x-final
  • Status changed from new to needs_review

comment:3 Changed 3 years ago by teor

Yes, you're right, unsigned integer underflow is defined in C11 as modulo (UINT_TYPE_MAX + 1):

6.3.1.3, paragraph 2 [ISO/IEC 9899:2011]:
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

I think this was probably a build configuration issue on my end. It looks like I managed to slip in -fsanitize=unsigned-integer-overflow in my tests on di_ops.c, then remove it again shortly afterwards. I can't reproduce the same error with the original code and my current build flags.

I'm sorry about that, I'll replace the di_ops patch with one that simply adds the new tests, and doesn't change any tor code.

comment:4 Changed 3 years ago by teor

I can't seem to work out how to change the attachment name or bug description, so they'll just have to stay there.

comment:5 Changed 3 years ago by nickm

The other patches look fine to me. I'll merge once I can write up some commit messages and changes/ files.

comment:6 Changed 3 years ago by nickm

  • Milestone changed from Tor: 0.2.6.x-final to Tor: 0.2.5.x-final

I made a branch "bug13104_025" and merged it to master. Marking this ticket for possible backport to 0.2.5

Changed 3 years ago by teor

Even more exhaustively test tor_memeq and tor_memcmp - no tor code changes

comment:7 Changed 3 years ago by teor

Nick, I've updated the tor_memeq test so it tests the same combinations that tor_memcmp does.

comment:8 Changed 3 years ago by nickm

Accidentally committed that as part of 0bd220adcb82670893c85b1cc24d64e615855b4f . But it looks okay to me

comment:9 Changed 3 years ago by teor

Ok to close this, Nick?

comment:10 Changed 3 years ago by nickm

  • Resolution set to fixed
  • Status changed from needs_review to closed

I think so, yes.

comment:11 Changed 3 years ago by teor

  • Keywords needs-test added
  • Resolution fixed deleted
  • Status changed from closed to reopened

03 scale_array_elements_to_u64 could do with unit tests for zero values (or do we have these already). I'll check.

comment:12 Changed 3 years ago by teor

  • Owner set to teor
  • Status changed from reopened to assigned

comment:13 Changed 2 years ago by nickm

  • Milestone changed from Tor: 0.2.5.x-final to Tor: 0.2.7.x-final

Not an 0.2.5 backport candidate, but new tests can go in at any time.

comment:14 Changed 2 years ago by teor

  • Resolution set to fixed
  • Status changed from assigned to closed

The last few tests in test_dir_scale_bw already check zero values: one checks no values, the next checks a single zero, and the final one checks two zeroes.

This appears sufficient for testing any regressions to this bug.

comment:15 Changed 14 months ago by nickm

  • Keywords 2016-bug-retrospective added

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

comment:16 Changed 14 months ago by nickm

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

comment:17 Changed 14 months ago by nickm

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

Note: See TracTickets for help on using tickets.