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 ()
Version: master
Hardware: All All
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
Depends on:
Reported: 2012-04-07 12:40 UTC by Nicholas Frechette
Modified: 2012-04-07 12:40 UTC (History)
1 user (show)

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

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.

Please create a new report for Bug 4328 on GitHub or Developer Community if you have new information to add and do not yet see a matching new report.

If the latest results still closely match this report, you can use the original description:

  • Export the original title and description: GitHub Markdown or Developer Community HTML
  • Copy the title and description into the new report. Adjust them to be up-to-date if needed.
  • Add your new information.

In special cases on GitHub you might also want the comments: GitHub Markdown with public comments

Related Links:

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:

This is a very common problem with binary search implementations.