Parsing format string precision intends to validate for overflow but the check does not work

[GSPP]

In #47353 the way format strings are validated was changed. This resulted in this code:

runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs

Lines 1705 to 1718 in 5707668

	// Fallback for symbol and any length digits. The digits value must be >= 0 && <= 99,
	// but it can begin with any number of 0s, and thus we may need to check more than two
	// digits. Further, for compat, we need to stop when we hit a null char.
	int n = 0;
	int i = 1;
	while (i < format.Length && (((uint)format[i] - '0') < 10))
	{
	int temp = ((n * 10) + format[i++] - '0');
	if (temp < n)
	{
	throw new FormatException(SR.Argument_BadFormatSpecifier);
	}
	n = temp;
	}

The temp < 0 check does not catch all forms of overflow. It is possible to overflow but to create a positive value. Roughly, the argument goes like this: At about n == int.MaxValue / 10 overflow starts to happen and it results in negative results. But then, the remaining value range is stepped through in increments of 10. This quickly leads to crossing into the positive numbers.

An example of this can be found with this code:

public static void StandardFormatStringParsingOverflowRepro()
{
    for (int n = 0; n < int.MaxValue; n++)
    {
        var temp = n * 10;
        if (temp < n && temp >= 0)
        {
            Debugger.Break();
        }
    }
}

The first number is 429496730 (roughly int.MaxValue * 2 / 10) and temp becomes 4. This should work as a repro, although I have not tested it on the live code.

I also wonder how this code guards against characters being other than 0-9. Maybe that is being validated elsewhere.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

In #47353 the way format strings are validated was changed. This resulted in this code:

runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs

Lines 1705 to 1718 in 5707668

	// Fallback for symbol and any length digits. The digits value must be >= 0 && <= 99,
	// but it can begin with any number of 0s, and thus we may need to check more than two
	// digits. Further, for compat, we need to stop when we hit a null char.
	int n = 0;
	int i = 1;
	while (i < format.Length && (((uint)format[i] - '0') < 10))
	{
	int temp = ((n * 10) + format[i++] - '0');
	if (temp < n)
	{
	throw new FormatException(SR.Argument_BadFormatSpecifier);
	}
	n = temp;
	}

Bug: The temp < 0 check does not catch all forms of overflow. It is possible to overflow but to create a positive value. Roughly, the argument goes like this: At about n == int.MaxValue / 10 overflow starts to happen and it results in negative results. But then, the remaining value range is stepped through in increments of 10. This quickly leads to crossing into the positive numbers.

An example of this can be found with this code:

public static void StandardFormatStringParsingOverflowRepro()
{
    for (int n = 0; n < int.MaxValue; n++)
    {
        var temp = n * 10;
        if (temp < n && temp >= 0)
        {
            Debugger.Break();
        }
    }
}

The first number is 429496730 (roughly int.MaxValue * 2 / 10) and temp becomes 4. This should work as a repro, although I have not tested it on the live code.

I also wonder how this code guards against characters being other than 0-9. Maybe that is being validated elsewhere.

Author:	GSPP
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[tannergooding]

@GSPP, you're missing that n is reassigned each iteration:

int n = 0; 
int i = 1; 
while (i < format.Length && (((uint)format[i] - '0') < 10)) 
{ 
    int temp = ((n * 10) + format[i++] - '0'); 
    if (temp < n) 
    { 
        throw new FormatException(SR.Argument_BadFormatSpecifier); 
    }
    n = temp;
}       

This isn't checking is it positive/negative but rather is the new temp less than the previous temp.

For 4294967300 it would:

• n = 0, temp = 4
• n = 4, temp = 42
• ...
• n = 42949673, temp = 429496730
• n = 429496730, temp = 4
• FormatException

[GSPP]

OK, let me see. It's definitely not possible to check the expression n * 10 for overflow if you're just checking for a less-than result. Multiplication overflow can result in a value from the entire 32 bit range. It can be more or less, positive or negative. For 1 in 10 x, I can give you an n so that n * 10 = x, evenly spaced through the entire int32 range.

OK, what I was getting wrong was that you're not checking for a negative result (which I mistakenly did in my brute force loop). You're checking for the result to be less than the input. That's not sufficient, either, because there are n for which n * 10 > n and there's overflow. The times ten expands the range of possible outcomes to many times the total value range of an int. You can use *10 to reach any part of the value range, positive, negative and bigger than the input.

Am I incorrect, that checking for a result less than the input cannot determine overflow of a *10 operation? I cannot see how that would be a reliable check given that the whole int value range can be reached.

I'll try a different approach. I'll try to find a value that passes the check in the production code but that triggers the built-in overflow check:

	for (int n = 0; n < int.MaxValue; n++)
	{
		var temp = n * 10;
		if (temp >= n) //The reverse of the condition in the live code
		{
			var _ = checked(n * 10); //This throws at n == 477218589
		}
	}

So it seems that 477218589 * 10 results in a greater-than outcome but triggers an overflow check. This means that the live code is not identifying an actual overflow.

I can reproduce it as follows. I copied out the ParseFormatSpecifier routine to a console app and ran it like this:

    ParseFormatSpecifier("G4772185890", out var digits); //Results in 477218594

This result is a wrong number, and it should throw instead.

Notice, how the new repro input is bigger than the wrong one that I mistakenly submitted at first. This is because we need to step further through the 32 bit range to not just reach a positive overflow result, but also one that is bigger than temp.

Also note, that during the initial non-overflowing loop iterations, we can set up n to be anything positive we like. And then, then next iteration will multiply by ten giving us a nearly arbitrary result of out choosing.

[tannergooding]

Yeah, that looks to be a problematic case. We should really just limit this to like 214 million or so, because there is really no reason for it to be bigger

[GSPP]

My suggested fix would be to checked multiply, catch and convert to FormatException. The JIT should generate optimal code for that overflow check. Would the try-catch itself impose a performance cost? If no or negligible, this would be a performant and easy to maintain fix.

This would be simpler to understand and verify than to derive some upper bound ("214 million"). You'd need to think through the edge cases and document this and so on.

[tannergooding]

The additional cost of try-catch or checked may be more significant then desired for the "happy path".

Ideally this is limited to a much more trivial check where possible that continues to minimize the cost around processing the format string or only incurs the cost in the rare case (format string is more than 5 digits, etc).

[GSPP]

I'm actually curious what costs a try-catch imposes if the catch is not taken. I looked at a sharplab simplified test case and the asm looks rather benign:

https://sharplab.io/#v2:EYLgtghglgdgNAFxBAzmAPgAQEwEYCwAUJgMwAEOZAwmQN5FmMXma4BsZsC1AFgKYBjANZ8AJgAouZCAEoGTeoSbKyCAE4BPeSrradTTAHYyA/sLHiIZAFRlcABhkBuPcoC+rpgIgJTZcQDyAG58agBmADYA9gDuAKIAHgJ8AA4IUFEwckr6ivoqCDxqsWQwfDFkAGJRapAIiclpGTDizp6MHjkdenqkFOycMNwAqjCmgiISUrJ6efpBEGpkanwoAK4R3AC80jZ29i5dKlBh/ivrm2QAPNIyZAD09wCSYzUrAghwZABWayjcYRqJiiYBSiygKEy7QKRRKZQq1VqPgaqXSmVah3yfAiKD40OURmWqw2CExTE6yl6LAGUheCDYABZJENbrNoQslucSWQduI1lwZFZbA4yToTmdiZcAIS8jaZADmgr2Dmy+WUhWKFXhVRqdRRTXRbSOymxuPxBmMzIQMi5m1FZE6biAA===

I see some stack setup and some branching.

[tannergooding]

It prevents a number of optimizations, makes the overall assembly nearly twice as large, and impacts the general inner loop performance negatively.

There is no real benefit to allowing formats this big and the actual case of overflow could be detected by if (n >= 214748364) at the top of the loop rather than being after the multiply.

This technically disallows 2147483640 through 2147483647 but that's a reasonable limitation (and could still be handled in a "slow path" otherwise). As would just limiting it to 9 digits (999999999) or other similar setups.

[dakersnar]

I think the comment above the source code loop should be updated, as The digits value must be >= 0 && <= 99 is no longer true https://docs.microsoft.com/en-us/dotnet/standard/base-types/standard-numeric-format-strings.