smartlist functions contain bogus overflow checks
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.
Activity
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.
Trac:
Username: mansour-
Trac:
Username: mansour
Cc: N/A to mansourmoufid@gmail.com -
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.
Trac:
Username: mansour -
Trac:
Username: mansour0001-Prevent-integer-overflows-in-smartlist_ensure_capaci.patch
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?
Trac:
Status: new to needs_review
In a x86-64 system, SIZEOF_SIZE_T == SIZEOF_INT and MAX_CAPACITY becomes (int) (UINT_MAX / 8) == 2^29, and MAX_CAPACITY/2 == 2^27.
If you pass a
sizebigger than 2^29 or INT_MAX/4, it will get in theif (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {and hit thetor_assert(size <= MAX_CAPACITY);.I'm not sure if this is in the function's threat model, since you have to pass an enormous
sizeand it would in any case probably OOM from therealloc(), but even the original overflow of this ticket needed a hugesize.-
In a x86-64 system,
SIZEOF_SIZE_T == SIZEOF_INTandMAX_CAPACITYbecomes (int) (UINT_MAX / 8) == 2^29^, and MAX_CAPACITY/2 == 2^27^.If you pass a size bigger than 2^29^ or INT_MAX/4, it will get in the
if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {and hit thetor_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. -
Replying to asn:
In a x86-64 system,
SIZEOF_SIZE_T == SIZEOF_INTandMAX_CAPACITYbecomes (int) (UINT_MAX / 8) == 2^29^, and MAX_CAPACITY/2 == 2^27^.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 2^29^ . It's 536870911, which is 2^29^ -1. So MAX_CAPACITY/2 will be 2^27^ - 1.
(The -1s aren't relevant to your argument, I think. But just in case.)
If you pass a size bigger than 2^29^ or INT_MAX/4, it will get in the
if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {and hit thetor_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. mentioned in issue #4899 (closed)
moved to tpo/core/tor#4230 (closed)
