[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 teor):

 Replying to [comment:11 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.

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