[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 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.

 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.

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