The "Check change note" check failed, reminding us that this PR should have a brief change note, explaining that there should be fewer false positive results in the three queries you mentioned.

The "Check change note" check failed, reminding us that this PR should have a brief change note, explaining that there should be fewer false positive results in the three queries you mentioned.

Fixed in aa52585.

I assume convertedExprMightOverflowNegatively is cached and there's a minimal effect on performance? I see about a 10% slowdown locally but that's in the context of a cleared cache.

convertedExprMightOverflowNegatively is indeed cached and already evaluated as part of the code-scanning suite, so I think everything should be fine wrt. performance.

I tried these on a samate snapshot and we lose some results:

cpp/uncontrolled-arithmetic 2709 -> 2080 results
cpp/arithmetic-with-extreme-values 1770 -> 1606 results
cpp/tainted-arithmetic 4281 -> 3067 results

These appear to be [mostly?] results in 'bad' cases, i.e. they're cases we should flag as far as SAMATE is concerned. This might be a price we're prepared to pay if we can actually use the queries in code scanning, but it would be good to know what's going on here.

I was confused by that as well. Looking at the results for cpp/uncontrolled-arithmetic on main I noticed that we sometimes flag the same result as both a possible underflow and an overflow. However, by adding range analysis we exclude the false result and keep the one that's actually relevant. This makes it seem like we're losing results we want to keep (as they are in 'bad' functions), but it's really removing false positives in those 'bad' functions.

As an example of this, consider this one which we flag on main as both an overflow and an underflow:

void CWE190_Integer_Overflow__char_rand_multiply_01_bad()
{
    char data;
    data = ' ';
    /* POTENTIAL FLAW: Use a random value */
    data = (char)RAND32();
    if(data > 0) /* ensure we won't have an underflow */
    {
        /* POTENTIAL FLAW: if (data*2) > CHAR_MAX, this will overflow */
        char result = data * 2;
        printHexCharLine(result);
    }
}

and with this PR we flag it as a potential overflow only.

SimpleRangeAnalysis doesn't seem to cope with some of the multiplications very well. Take this one:

void CWE190_Integer_Overflow__int64_t_max_square_01_bad()
{
    int64_t data;
    data = 0LL;
    /* POTENTIAL FLAW: Use the maximum size of the data type */
    data = LLONG_MAX;
    {
        /* POTENTIAL FLAW: if (data*data) > LLONG_MAX, this will overflow */
        int64_t result = data * data;
        printLongLongLine(result);
    }
}

It isn't considered multiplication by a constant, and the UnsignedMulExpr case doesn't apply either because the types are signed, so range analysis doesn't give a result. Presumably a case for SignedMulExpr isn't present in range analysis because we'd need to know the upper and lower bounds of the operands to calculate either bound of the result, so we'd get [possibly negative?] recursion between getUpperBoundsImpl and getLowerBoundsImpl.

It isn't considered multiplication by a constant, and the UnsignedMulExpr case doesn't apply either because the types are signed, so range analysis doesn't give a result. Presumably a case for SignedMulExpr isn't present in range analysis because we'd need to know the upper and lower bounds of the operands to calculate either bound of the result, so we'd get [possibly negative?] recursion between getUpperBoundsImpl and getLowerBoundsImpl.

We ruled out general multiplication in range analysis because it involves too many recursive calls (no negative recursion, fortunately). See here for the discussion regarding this.

You're right in that this is a problem. I actually thought exprMightOverflowPositively was trivially true for unanalyzable expressions, but that doesn't appear to be the case. I actually think this should be the case, but I don't want to make such a change in this PR. As a first step, I'll fix it in missingGuardAgainstOverflow (and missingGuardAgainstUnderflow) to also have a result when we can't use range analysis.

We ruled out general multiplication in range analysis because it involves too many recursive calls (no negative recursion, fortunately). See here for the discussion regarding this.

I don't think we'd quite need a general case, just the case of positive number * positive number multiplication. This would use getLowerBoundsImpl in getUpperBoundsImpl to check that both inputs are non-negative, but there would be no use of getUpperBoundsImpl in getLowerBoundsImpl so a mutual recursion wouldn't be created.

I'll fix it in missingGuardAgainstOverflow (and missingGuardAgainstUnderflow) to also have a result when we can't use range analysis.

Sounds good to me.

bb447d7 fixes the problems, @geoffw0. Unfortunately, the results look a lot less impressive now. But at least it's (more) correct!

It isn't considered multiplication by a constant, and the UnsignedMulExpr case doesn't apply either because the types are signed, so range analysis doesn't give a result.

Slack discussion.

Presumably a case for SignedMulExpr isn't present in range analysis because we'd need to know the upper and lower bounds of the operands to calculate either bound of the result, so we'd get [possibly negative?] recursion between getUpperBoundsImpl and getLowerBoundsImpl.

More or less, yes. It leads to non-linear recursion (which is tolerable but a bit slow) and sometimes an explosion in the number of candidate bounds. Because of how abstract interpretation in QL works (the only lattice is the powerset lattice), we store candidate bounds until the end of the main range-analysis recursion, even if they're no longer relevant.

I'm happy with the PR as it is now (results are fine), but I'd prefer to have a more principled solution using #5678 (if that works out).

I'm happy with the PR as it is now (results are fine), but I'd prefer to have a more principled solution using #5678 (if that works out).

I agree. I think it's fine to merge this one as-is, though. How about I create a backlog issue that says something along the lines of "Fixup bb447d7 if we end up merging #5678"?

I agree. I think it's fine to merge this one as-is, though. How about I create a backlog issue that says something along the lines of "Fixup bb447d7 if we end up merging #5678"?

Sounds good. Or just write yourself a reminder on #5678 if that works for you.

Merging this now...