[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #18296 [Tor]: Potential integer overflow and memory corruption in smartlist_heapify
#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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs