Opened 21 months ago

Closed 17 months ago

Last modified 16 months ago

#17983 closed enhancement (implemented)

Build tor with -ftrapv by default

Reported by: teor Owned by: nickm
Priority: High Milestone: Tor: 0.2.9.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-sponsorS-orphan, TorCoreTeam201605, TorCoreTeam-postponed-201604, review-group-1
Cc: gk, mikeperry Actual Points: 3
Parent ID: Points: 1
Reviewer: special Sponsor: SponsorS-can

Description (last modified by teor)

If the CFLAGS passed to tor don't contain -ftrapv (or the undefined behaviour sanitiser), let's build with -ftrapv.

This resolves #13538 non-intrusively, and prevents an entire class of integer safety bugs. (That said, wrapping can hide some issues rather than resolving them.)

Child Tickets

TicketTypeStatusOwnerSummary
#13538defectclosedStop signed left shift overflows in curve25519-donna (non-64-bit)
#17682defectclosednickmsafe_timer_diff is unsafe under wrapping
#18901defectclosednickmShould we stop appling --enable-expensive-hardening to constant-time code ?

Attachments (1)

donna32-asm.tar.gz (41.2 KB) - added by nickm 18 months ago.
assembly for donna32, with wrapv and trapv, on gcc and clang

Download all attachments as: .zip

Change History (34)

comment:1 Changed 21 months ago by teor

UBSan is -fsanitize=undefined, but it can also be used like -fsanitize=address,undefined, or using the integer sanitizer only.

We could build with -fwrapv when -fsanitize does not appear on the command-line. If they are used together, this could hide undefined behaviour when people are explicitly checking for it. But suddenly switching off -fwrapv could also cause subtle bugs.

So let's make -fwrapv it a ./configure option that's on by default, and people can turn it off if they don't want it.

comment:2 Changed 21 months ago by nickm

What's the performance impact?

My only other concern here would be that programmers would start assuming -fwrapv semantics, with dangerous results when -fwrapv is missing.

Otherwise sounds reasonable

comment:3 in reply to:  2 Changed 21 months ago by teor

Replying to nickm:

What's the performance impact?

It disables certain optimisations in both gcc and clang.
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

That said, the Linux kernel does it.

My only other concern here would be that programmers would start assuming -fwrapv semantics, with dangerous results when -fwrapv is missing.

Wrapping (whether via -fwrapv or compiler/processor-specific behaviour) can also cause dangerous results by itself.

The conformant way to resolve this issue is to:

  • replace signed integers by unsigned integers (where possible)
    • we'll need to be careful of C's integer promotion rules here, as unsigned integers can be promoted to a larger signed integer type
  • modify code that uses signed integers so it doesn't overflow (where possible)
  • add -fwrapv to CFLAGS for files which upstream doesn't want to modify (like the donna sources)
  • always check for signed integer wrapping (before invoking potentially undefined behaviour), and check for unsigned integer wrapping where it's undesirable. In these cases, if the calculation wraps, we can:
    • implement explicit wrapping for signed integers (unsigned integers implicitly wrap)
    • replace an overflow/underflow by a default value
    • implement saturated add/subtract, where an overflow/underflow simply stays at the max/min value for the type
    • log a warning or assert

comment:4 Changed 21 months ago by nickm

Hm. With all this, -fwrapv is starting to sound pretty reasonable.

We should also treat any unmarked sign integer overflow as a bug, though, IMO.

comment:5 in reply to:  4 Changed 21 months ago by teor

Replying to nickm:

Hm. With all this, -fwrapv is starting to sound pretty reasonable.

Yes. And we can still check for overflows in the code when we need to.

We should also treat any unmarked sign integer overflow as a bug, though, IMO.

I agree - signed integer overflows often lead to unexpected behaviour. (They can be detected using -ftrapv.)

comment:6 Changed 21 months ago by nickm

I've just heard an alternative proposal: that we should build (most of?) Tor with -ftrapv rather than -fwrapv.

Rationale: Chandler from the LLVM project looked at wrapping signed arithmetic in some really huge codebases, to see if there was much buggy code that assumed that wrapping would happen. What he found instead: that in (nearly?) every case, no overflow behavior would have been correct: the code was buggy for any possible semantics of signed overflow. In these cases, using -fwrapv turns buggy undefined behavior into other buggy (but defined) behavior, rather than making any code correct.

comment:7 in reply to:  6 ; Changed 21 months ago by teor

Replying to nickm:

I've just heard an alternative proposal: that we should build (most of?) Tor with -ftrapv rather than -fwrapv.

Rationale: Chandler from the LLVM project looked at wrapping signed arithmetic in some really huge codebases, to see if there was much buggy code that assumed that wrapping would happen. What he found instead: that in (nearly?) every case, no overflow behavior would have been correct: the code was buggy for any possible semantics of signed overflow. In these cases, using -fwrapv turns buggy undefined behavior into other buggy (but defined) behavior, rather than making any code correct.

I think this is an excellent idea!

In 0.2.6 and 0.2.7, I built with -ftrapv regularly, and reported the resulting integer overflow issues as they crashed my tor instances.

However, -ftrapv might cause crashes in 0.2.8-stable if we don't test it well enough.

It's also worth noting that --enable-gcc-hardening and the hardened Tor Browser series both build with -fwrapv. Maybe we should come up with a consistent approach?

comment:8 in reply to:  7 Changed 21 months ago by teor

Replying to teor:

Replying to nickm:

I've just heard an alternative proposal: that we should build (most of?) Tor with -ftrapv rather than -fwrapv.

Rationale: Chandler from the LLVM project looked at wrapping signed arithmetic in some really huge codebases, to see if there was much buggy code that assumed that wrapping would happen. What he found instead: that in (nearly?) every case, no overflow behavior would have been correct: the code was buggy for any possible semantics of signed overflow. In these cases, using -fwrapv turns buggy undefined behavior into other buggy (but defined) behavior, rather than making any code correct.

I think this is an excellent idea!

...

It's also worth noting that --enable-gcc-hardening and the hardened Tor Browser series both build with -fwrapv. Maybe we should come up with a consistent approach?

--enable-gcc-hardening (including -fwrapv) is the default in the tor configure script.

So we're going to replace the current use of -fwrapv with -ftrapv?

When I build master on OS X 10.11.2 with clang Apple LLVM version 7.0.2 (clang-700.1.81) with:

./configure ... --disable-gcc-hardening CC="clang -ftrapv", or
./configure ... --disable-gcc-hardening CC="clang -arch i386 -ftrapv":

  • all the unit tests pass with no traps
  • all the chutney tests in make test-network-all pass with no traps

So I think we can add -ftrapv with low impact on the current tor codebase.

(Now do we do this as part of --enable-expensive-hardening, or as part of --enable-gcc-hardening, or as the default?)

comment:9 Changed 21 months ago by nickm

I have no strong preference between gcc-hardening or default. What do you think?

comment:10 in reply to:  9 Changed 21 months ago by teor

Replying to nickm:

I have no strong preference between gcc-hardening or default. What do you think?

I think --enable-gcc-hardening, because then -ftrapv on by default, but can be disabled with --disable-gcc-hardening if needed.

This is the simplest change, too: just replace the -fwrapv in --enable-gcc-hardening with -ftrapv. (And it avoids confusion between some builds having an implicit -fwrapv, and others having an implicit -ftrapv.)

We should let the TBB people (mikeperry?) know when we do this, because in their hardened series TBB uses -fwrapv.

comment:11 Changed 21 months ago by nickm

Cc: gk mikeperry added

comment:12 Changed 21 months ago by nickm

Owner: set to nickm
Status: newaccepted

comment:13 Changed 20 months ago by teor

If we had set -ftrapv on all builds, #18162 would not have been exploitable, it would have crashed instead.

comment:14 Changed 20 months ago by cypherpunks

This ticket is a bad idea, ftrapv should be used:
https://trac.torproject.org/projects/tor/ticket/18296

comment:15 in reply to:  14 Changed 20 months ago by teor

Description: modified (diff)
Summary: Build tor with -fwrapv by defaultBuild tor with -ftrapv by default

Replying to cypherpunks:

This ticket is a bad idea, ftrapv should be used:
https://trac.torproject.org/projects/tor/ticket/18296

Yes, we've worked that out already. Please read comments 6 onwards.

comment:16 Changed 19 months ago by nickm

Milestone: Tor: 0.2.8.x-finalTor: 0.2.9.x-final

These seem like features, or like other stuff unlikely to be possible this month. Bumping them to 0.2.9

comment:17 Changed 18 months ago by isabela

Sponsor: SponsorS-can

comment:18 Changed 18 months ago by nickm

Points: small

comment:19 Changed 18 months ago by nickm

Priority: MediumHigh

comment:20 Changed 18 months ago by nickm

Keywords: TorCoreTeam201604 added

These are infrastructure that will help out other projects, and should go in early. Marking them for April.

comment:21 Changed 18 months ago by nickm

Note that this issue has a potential conflict with this known issue in curve25519-donna:

https://github.com/agl/curve25519-donna/issues/31

(Tracked here with #13538).

We'll need to make the curve25519-donna code get fixed, or make it get built with -fwrapv and without -ftrapv.

comment:22 Changed 18 months ago by nickm

Status: acceptedneeds_review

I have a branch called ftrapv that makes everything besides donna32 compile with trapv, and makes donna32 compile with wrapv.

One more thing before we can merge, though: I want to know the effect of ftrapv on whether our generated signed-integer-using crypto is still constant-time. In particular this includes: ed25519 signatures, curve25519, keccak, di_ops.c, and I hope not too much else.

Changed 18 months ago by nickm

Attachment: donna32-asm.tar.gz added

assembly for donna32, with wrapv and trapv, on gcc and clang

comment:23 Changed 18 months ago by nickm

I've attached the generated assembly for donna32, in case anybody likes reading that kind of thing

comment:24 Changed 18 months ago by nickm

Keywords: tor-sponsorS-orphan added

comment:25 Changed 17 months ago by nickm

Status: needs_reviewneeds_revision

update: I've asked around in #llvm, and I've asked some crypto implementers if they have any thoughts here.

So far the safest option seems to be to use fwrapv on the code that should be constant-time, and ftrapv elsewhere. Additionally, out of an abundance of caution, we should change --enable-expensive-hardening so that the constant-time code is not built with any of the compiler sanitizers in that case.

(I have not seen a conclusive argument that that the untaken branches added by trapv and the sanitizers mess with constant-time properties, but it does seem that the diversity of branch predictors is so great that it is hard for me to call these branches "always harmless" with much certainty. Maybe given more information.)

I've added a ticket to write testing logic to verify that our operations run in constant time. (#18896) I've added another ticket about the sanitizers (#18901). I'm going to needs_revision this ticket, with the plan to use fwrapv on all constant-time modules, and trapv elsewhere.

comment:26 Changed 17 months ago by nickm

Status: needs_revisionneeds_review

I now have a branch 'ftrapv_v2' that implements this. To make sure that things built with the right flags, I used "make V=1 >build_log", and then a bunch of grep. Needs review.

comment:27 Changed 17 months ago by nickm

Keywords: TorCoreTeam201605 TorCoreTeam-postponed-201604 added; TorCoreTeam201604 removed

April is over; calling these april tickets postponed into may.

comment:28 Changed 17 months ago by nickm

ftrapv_v2 now works. And includes a real fix for the failure of test-memwipe under expensive hardening.

comment:29 Changed 17 months ago by nickm

Keywords: review-group-1 added

comment:30 Changed 17 months ago by nickm

I've updated the branch containing this a little. It's now ftrapv_v3

comment:31 Changed 17 months ago by special

Reviewer: special
Status: needs_reviewneeds_revision

Seems like a good plan to me. I trust and did not check that you've found all of the code that must be constant time. The /bin/true problem is the only real issue I see.

ce854a8d22d5056cc1a47a0d4d4251f93a0c667c

OS X doesn't know /bin/true, and warns about this. Can you use the 'true' builtin instead?

+ src/common/libor-ctime.a \

These lines in src/common/include.am use space indent, but the surrounding lines are tab indented.

b1dce55b8236cc7ecf66f87c0bd96b0dcf874fcc

Why does src_test_test_memwipe_LDFLAGS use @CFLAGS_BUGTRAP@ if it's excluded from CFLAGS?

comment:32 Changed 17 months ago by nickm

Actual Points: 3
Resolution: implemented
Status: needs_revisionclosed

Fixed those things up and merged. Thanks! I bet something will break someplace, since these are build changes; We'll see how it goes.

comment:33 Changed 16 months ago by isabela

Points: small1
Note: See TracTickets for help on using tickets.