Bug 4328 - SortedList<>::Find() has possible integer overflow
Summary: SortedList<>::Find() has possible integer overflow
Status: NEW
Alias: None
Product: Class Libraries
Classification: Mono
Component: System (show other bugs)
Version: master
Hardware: All All
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
URL:
Depends on:
Blocks:
 
Reported: 2012-04-07 12:40 UTC by Nicholas Frechette
Modified: 2012-04-07 12:40 UTC (History)
1 user (show)

See Also:
Tags:
Is this bug a regression?: ---
Last known good build:


Attachments

Description Nicholas Frechette 2012-04-07 12:40:29 UTC
If I am not mistaken, when the list gets very large (might require 64bit OS and a large amount of ram), the line calculating the guess can overflow:

int guess = (left + right) >> 1;

For example, if the size is 2^31 - 1, and we provide a key that is in
the top half, the loop will go as follow: left = 0, right = 2^31 - 2,
guess = ~2^30. if cmp < 0, left becomes ~2^30 and on the next
iteration, left + right will be (2^31 - 2 + ~2^30) which is larger
than int.MaxValue (2^31-1) thus causing overflow before the right
shift to divide by 2.

See also this link for a similar issue in a java container method:
http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html

This is a very common problem with binary search implementations.

Note You need to log in before you can comment on or make changes to this bug.