Opened 8 years ago

Closed 8 years ago

Last modified 6 years ago

#4230 closed defect (fixed)

smartlist functions contain bogus overflow checks

Reported by: rransom Owned by:
Priority: High Milestone:
Component: Core Tor/Tor Version:
Severity: Keywords: tor-client
Cc: mansourmoufid@… Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

In smartlist_ensure_capacity, in src/common/container.c:

  if (size > sl->capacity) {
    int higher = sl->capacity * 2;
    while (size > higher)
      higher *= 2;
    tor_assert(higher > 0); /* detect overflow */

Overflow of a signed integer produces undefined results. I would be surprised if GCC doesn't optimize this comparison out, just for the sake of conjuring nasal demons at people who don't code with a copy of the C ‘standard’ at hand.

Child Tickets

Attachments (1)

0001-Prevent-integer-overflows-in-smartlist_ensure_capaci.patch (1.3 KB) - added by mansour 8 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 8 years ago by rransom

Summary: smartlist_ensure_capacity contains bogus overflow checksmartlist functions contain bogus overflow checks

Looks like there are other scary overflow (not-quite-)checks, too.

comment:2 Changed 8 years ago by mansour

I could give this a shot, unless someone else has already started.

It might take me a while, though, since I'd go through everything line by line.

comment:3 Changed 8 years ago by Sebastian

aren't we good here because we ensure that we're using 2s complement?

comment:4 in reply to:  3 Changed 8 years ago by mansour

Replying to Sebastian:

aren't we good here because we ensure that we're using 2s complement?

If the assert had been within the while loop, perhaps.

For example, if the variable size == INT_MAX/2+1, and sl->capacity == size+1. The variable higher is assigned a negative off the bat; gets doubled; underflows; and the loop breaks. Then the assert passes essentially by accident.

But that's just this particular instance.

comment:5 Changed 8 years ago by mansour

Cc: mansourmoufid@… added

comment:6 Changed 8 years ago by nickm

Fortunately, I think the only overflow check to worry about is smartlist_ensure_capacity; everything else calls that when it wants to grow the smartlist.

comment:7 in reply to:  6 Changed 8 years ago by mansour

Replying to nickm:

Fortunately, I think the only overflow check to worry about is smartlist_ensure_capacity; everything else calls that when it wants to grow the smartlist.

I've attached a quick fix for this function. Tests fine but it needs review.

The idea is to just use INT_MAX in case of potential overflow.

comment:8 Changed 8 years ago by karsten

Milestone: Tor: 0.2.1.x-final

Removing the milestone, because 0.2.1.x-final has been released long ago. (Also marking that milestone as closed.)

comment:9 Changed 8 years ago by karsten

Milestone: Tor: 0.2.1.x-final

Putting the milestone back in. I thought it was a milestone for the stable release. Marking the milestone as open again. Ooops. :)

comment:10 Changed 8 years ago by nickm

Status: newneeds_review

Looking at the patch, I think it's just going to overflow again. Sure, it caps sl->capacity at INT_MAX, but look at the tor_realloc() call: it reallocates the buffer to be equal to sizeof(void*)*sl->capacity. So on a 32-bit system, that'll be ((size_t)4)*INT_MAX , which isn't a sensible thing to say.

Have a look at branch "bug4230" in my public repository; does that look okay to you?

comment:11 in reply to:  10 ; Changed 8 years ago by rransom

Replying to nickm:

Have a look at branch "bug4230" in my public repository; does that look okay to you?

There is a TAB character in your commit message.

comment:12 in reply to:  11 ; Changed 8 years ago by nickm

Replying to rransom:

Replying to nickm:

Have a look at branch "bug4230" in my public repository; does that look okay to you?

There is a TAB character in your commit message.

Other than that, looks ok?

comment:13 in reply to:  12 Changed 8 years ago by rransom

Replying to nickm:

Replying to rransom:

Replying to nickm:

Have a look at branch "bug4230" in my public repository; does that look okay to you?

There is a TAB character in your commit message.

Other than that, looks ok?

Yes.

comment:14 Changed 8 years ago by nickm

ok; pushed an updated version. I'd appreciate a look from whoever else has time before I merge; this kind of stuff has a way of getting tricky.

comment:15 Changed 8 years ago by asn

In a x86-64 system, SIZEOF_SIZE_T == SIZEOF_INT and MAX_CAPACITY becomes (int) (UINT_MAX / 8) == 229, and MAX_CAPACITY/2 == 227.

If you pass a size bigger than 229 or INT_MAX/4, it will get in the if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { and hit the tor_assert(size <= MAX_CAPACITY);.

I'm not sure if this is in the function's threat model, since you have to pass an enormous size and it would in any case probably OOM from the realloc(), but even the original overflow of this ticket needed a huge size.

comment:16 Changed 8 years ago by asn

In a x86-64 system, SIZEOF_SIZE_T == SIZEOF_INT and MAX_CAPACITY becomes (int) (UINT_MAX / 8) == 229, and MAX_CAPACITY/2 == 227.

If you pass a size bigger than 229 or INT_MAX/4, it will get in the if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { and hit the tor_assert(size <= MAX_CAPACITY);.

I'm not sure if this is in the function's threat model, since you have to pass an enormous size and it would in any case probably OOM from the realloc(), but even the original overflow of this ticket needed a huge size.

comment:17 in reply to:  16 Changed 8 years ago by nickm

Replying to asn:

In a x86-64 system, SIZEOF_SIZE_T == SIZEOF_INT and MAX_CAPACITY becomes (int) (UINT_MAX / 8) == 229, and MAX_CAPACITY/2 == 227.

Actually, on most X86_64 systems, SIZEOF_SIZE_T is 8 an SIZEOF_INT is 4. But it's allowable for them to be the same depending on the weirdness of the API, so let's go with it.

In this case, UINT_MAX/8 is actually not 229 . It's 536870911, which is 229 -1. So MAX_CAPACITY/2 will be 227 - 1.

(The -1s aren't relevant to your argument, I think. But just in case.)

If you pass a size bigger than 229 or INT_MAX/4, it will get in the if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { and hit the tor_assert(size <= MAX_CAPACITY);.

Yup. We have to hit that point. Our response to OOM is a tor_assert() failure throughout the rest of the code. We literally cannot allocate an array of more than MAX_CAPACITY elements in this case: to do so, we would need to pass a value larger than SIZE_MAX as an argument to tor_realloc, which is impossible, since SIZE_MAX is the largest SIZE_T value there can be.

I'm not sure if this is in the function's threat model, since you have to pass an enormous size and it would in any case probably OOM from the realloc(), but even the original overflow of this ticket needed a huge size.

comment:18 Changed 8 years ago by arma

Fix looks plausible to me. (But I'm not an expert on this level of stuff.)

I suggest we should merge it in at 022, and then tell weasel about it so he can decide whether he wants to put it into his 021 debs.

comment:19 Changed 8 years ago by nickm

Resolution: fixed
Status: needs_reviewclosed

Merged; sending mail to weasel

comment:20 Changed 7 years ago by nickm

Keywords: tor-client added

comment:21 Changed 7 years ago by nickm

Component: Tor ClientTor

comment:22 Changed 6 years ago by nickm

Milestone: Tor: 0.2.1.x-final

Milestone Tor: 0.2.1.x-final deleted

Note: See TracTickets for help on using tickets.