[tor-bugs] #18296 [Tor]: Potential integer overflow and memory corruption in smartlist_heapify

[Tor Bug Tracker & Wiki]

#18296: Potential integer overflow and memory corruption in smartlist_heapify
-------------------------+------------------------------------
 Reporter:  cypherpunks  |          Owner:  nickm
     Type:  defect       |         Status:  needs_review
 Priority:  Medium       |      Milestone:  Tor: 0.2.8.x-final
Component:  Tor          |        Version:
 Severity:  Normal       |     Resolution:
 Keywords:               |  Actual Points:
Parent ID:               |         Points:
  Sponsor:               |
-------------------------+------------------------------------

Comment (by cypherpunks):

 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.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/18296#comment:14>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online