[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 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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs