Potential integer overflow and memory corruption in smartlist_heapify

The LEFT_CHILD/RIGHT_CHILD macros used in container.c::smartlist_heapify() can overflow.

This can potentially result in using a negative array index in the smartlist memory block and writing to some out of bounds memory location.

This is probably not currently exploitable, given the limited usage of smartlist_heapify. The places where it is used look hard to control for an attacker and the amount of memory required would likely be too much for Tor to be able to allocate.

Tor should be built with ftrapv. Ticket 17983 looks like a bad idea.

changed milestone to %Tor: 0.2.8.x-final

added component::core tor/tor milestone::Tor: 0.2.8.x-final owner::nickm priority::medium resolution::fixed severity::normal status::closed type::defect labels

Trac:
Milestone: N/A to Tor: 0.2.8.x-final

Replying to cypherpunks:

Tor should be built with ftrapv. Ticket 17983 looks like a bad idea.

Ticket #17983 (moved) is about building with -ftrapv. Please read the discussion on that ticket.

Replying to teor:

Ticket #17983 (moved) is about building with -ftrapv. Please read the discussion on that ticket.

Good, the ticket description is changed now. It wasn't clear from the discussion that the decision to use ftrapv had been made, in particular with regards to TBB builds.

Replying to cypherpunks:

Replying to teor:

Ticket #17983 (moved) is about building with -ftrapv. Please read the discussion on that ticket.

Good, the ticket description is changed now. It wasn't clear from the discussion that the decision to use ftrapv had been made, in particular with regards to TBB builds.

#17983 (moved) is for Tor. Please open another ticket against "Tor Browser" if you want it to be built with -ftrapv. Tor Browser is larger, so it could be more difficult. (Getting tor to run when built under -ftrapv involved some work in 2014-2015.)

Replying to teor:

#17983 (moved) is for Tor. Please open another ticket against "Tor Browser" if you want it to be built with -ftrapv. Tor Browser is larger, so it could be more difficult. (Getting tor to run when built under -ftrapv involved some work in 2014-2015.)

I'm not talking about Firefox. I'm talking about the Tor that's bundled with TBB.

Replying to cypherpunks:

Replying to teor:

#17983 (moved) is for Tor. Please open another ticket against "Tor Browser" if you want it to be built with -ftrapv. Tor Browser is larger, so it could be more difficult. (Getting tor to run when built under -ftrapv involved some work in 2014-2015.)

I'm not talking about Firefox. I'm talking about the Tor that's bundled with TBB.

Please file a ticket against Tor Browser, as they may need to modify their tor build process, depending on exactly how we implement #17983 (moved).

assign the actual bugfix here to me.

Trac:
Status: new to accepted
Owner: N/A to nickm

Branch bug18296 has a simple-ish fix for this. Is it right?

Trac:
Status: accepted to needs_review

HAS_CHILDREN is a bad name for your check, since it checks for possible index overflow and not if the children exist.

Replying to nickm:

Branch bug18296 has a simple-ish fix for this. Is it right?

This check avoids overflow, but only once we get to the end of the list. If it's a long list, that could take a while.

I wonder if we should just check smartlist_len() <= (INT_MAX/2 - 2) instead?

Also, should we tor_assert() rather than returning? The resultant heap is not valid, and might cause more subtle issues later on.

Have another look at the algorithm? It starts with an idx that possibly violates the heap property by being larger than one or both of its children. If it does, it swaps a child into the current idx, and then looks to see whether the heap property is now violated at the child's old position. If HAS_CHILDREN(idx) is false, it is impossible for idx to have a pair of children -- though hm, when I wake up I should see whether it can have only a single child.

Note also that idx is monotonically increasing here, and it approximately doubles each time through the loop. So at worse we're doing a small number of iterations.

Replying to nickm:

Have another look at the algorithm? It starts with an idx that possibly violates the heap property by being larger than one or both of its children. If it does, it swaps a child into the current idx, and then looks to see whether the heap property is now violated at the child's old position. If HAS_CHILDREN(idx) is false, it is impossible for idx to have a pair of children -- though hm, when I wake up I should see whether it can have only a single child.

If HAS_CHILDREN is false, idx can;t have any children.

Note also that idx is monotonically increasing here, and it approximately doubles each time through the loop. So at worse we're doing a small number of iterations.

That makes more sense.

Should we tor_assert() rather than returning? I can't understand how returning yields a valid heap.

I can't understand how returning yields a valid heap.

Remember, the only way that the heap property can be invalid is that the value at idx may be larger than one or both of its children. If we reach a value of idx that is too large to have any children, then we know that the heap property cannot be violated.

I've tried to explain things a little better on the branch; does it make more sense now?

Your comment is wrong.

/* Largest IDX in the smartlist which might have children whose indices
 * fit inside an int.
 * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-1;
 * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX;
 * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX + 1 // overflow.

Assuming INT_MAX==2147483647, MAX_PARENT_IDX works out to 1073741822. The max left child idx is 2147483645==INT_MAX-2, the max right child idx is 2147483646==INT_MAX-1.

INT_MAX is not a valid index. The maximum list size is INT_MAX, so the maximum valid index is INT_MAX-1.

Trac:
Status: needs_review to needs_revision

Thanks for the correction! I've added a fixup commit, squashed, and merged.

Trac:
Status: needs_revision to closed
Resolution: N/A to fixed

closed

moved to tpo/core/tor#18296 (closed)