“Highly Unlikely” is not the same as “Impossible”

One of my programs crashed the other day in a very unexpected place:  inside the runtime library.  The exception stack trace is pretty clear on where the error occurred:

System.OverflowException: Negating the minimum value of a twos complement number is invalid.
   at System.Math.AbsHelper(Int32 value)
   at System.Random..ctor(Int32 Seed)
   at System.Threading.Collections.ConcurrentQueue`1.TryDequeueCore(T& result)
   at System.Threading.Collections.ConcurrentQueue`1.TryDequeue(T& result)
   at MyProgram.ThreadProc() in c:\MyProgram\Main.cs:line 118
   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
   at System.Threading.ThreadHelper.ThreadStart()

The documentation for the Random constructor says that this exception will be thrown if the Seed parameter is equal to Int32.MinValue.  Curious, I thought I’d disassemble the ConcurrentQueue class to see what’s going on.  No problem there, as it’s calling the default (parameterless) Random constructor.  So I took a look at that.

.method public hidebysig specialname rtspecialname
        instance void  .ctor() cil managed
{
  // Code size       12 (0xc)
  .maxstack  8
  IL_0000:  ldarg.0
  IL_0001:  call       int32 System.Environment::get_TickCount()
  IL_0006:  call       instance void System.Random::.ctor(int32)
  IL_000b:  ret
} // end of method Random::.ctor

That code gets the current tick count and then passes that value as a seed to the constructor.  So, what’s wrong with this?  Take a look at the documentation for System.Environment.TickCount:

The value of this property is derived from the system timer and is stored as a 32-bit signed integer. Consequently, if the system runs continuously, TickCount will increment from zero to Int32.MaxValue for approximately 24.9 days, then jump to Int32.MinValue, which is a negative number, then increment back to zero during the next 24.9 days.

What all this means is that if your program calls the Random constructor during that one millisecond (after the system has been up for Int.MaxValue milliseconds), the value returned by System.Environment.TickCount is going to be equal to Int.MinValue, and passing that value as the seed will result in an exception.

I’ll be the first to admit that encountering this bug is highly unlikely.  Your computer has to be up and running for almost 25 days, and there’s a one-millisecond window when it’s vulnerable.  But the fact that my program crashed is proof that it is possible for this error to cause a problem.

This is a huge oversight on the part of Microsoft’s runtime library team.  I’ve reported the bug and hope they manage to get it fixed before they release .NET 4.0.

Update 2009/07/21:  Microsoft’s Base Class Library team has said that the issue has been resolved for the next major release.

3 comments to “Highly Unlikely” is not the same as “Impossible”

  • Crazy. The very definition of a heisenbug.

    Why does .NET’s Random not accept Int32.MinValue? Java’s java.util.Random handles Integer.MIN_VALUE (and .MAX_VALUE) without any problem.

  • Jim

    The immediate reason that Random doesn’t accept Int32.MinValue is because the constructor calls Math.Abs, and you can’t take the absolute value of Int32.MinValue. There’s no positive two’s complement representation of 0x80000000. Now, one could ask why they call Math.Abs rather than just ANDing with 0x7FFFFFFF. Who knows? Whatever the case, the bug is in the default constructor, which doesn’t take that documented behavior into account.

  • […] in Prev/Next Posts « “Highly Unlikely” is not the same as “Impossible” | Home Tuesday, July 21st, 2009 at 1:00 […]

Categories

A sample text widget

Etiam pulvinar consectetur dolor sed malesuada. Ut convallis euismod dolor nec pretium. Nunc ut tristique massa.

Nam sodales mi vitae dolor ullamcorper et vulputate enim accumsan. Morbi orci magna, tincidunt vitae molestie nec, molestie at mi. Nulla nulla lorem, suscipit in posuere in, interdum non magna.