Test case for Coverity finding on shift amount in gf2n.cpp

[Jeffrey Walton]

Hi Everyone,

We cleared nearly all of the Coverity findings located at .

We have one left, but I am not sure how to proceed. Here is the text from the finding: "CID 147829 (#1 of 1): Bad bit shift operation (BAD_SHIFT)33. large_shift: In expression ((temp >> j) & 1ULL) << this->t1 + j, left shifting by more than 63 bits has undefined behavior. The shift amount, this->t1 + j, is as much as 64."

Here is the source code and line (just below line 710): http://www.cryptopp.com/docs/ref/gf2n_8cpp_source.html#l00710 .

I have not been able to duplicate it in practice, which means we can't test the fix and we risk breaking things.

My question is, how can we craft a test case to tickle that finding?

Jeff

[Jean-Pierre Münch]

Am 16.11.2015 um 19:13 schrieb Jeffrey Walton:

Hi Everyone,

We cleared nearly all of the Coverity findings located at .

good job with that one :)

We have one left, but I am not sure how to proceed. Here is the text from the finding: "CID 147829 (#1 of 1): Bad bit shift operation (BAD_SHIFT)33. large_shift: In expression ((temp >> j) & 1ULL) << this->t1 + j, left shifting by more than 63 bits has undefined behavior. The shift amount, this->t1 + j, is as much as 64."

Here is the source code and line (just below line 710): http://www.cryptopp.com/docs/ref/gf2n_8cpp_source.html#l00710 .

I have not been able to duplicate it in practice, which means we can't test the fix and we risk breaking things.

My question is, how can we craft a test case to tickle that finding?

I've looked at the issue and my conclusion is that the system is making a mistake (may be wrong though).

It assumes that t1 may get up to 63 in step 27, it then goes through a standard-for-loop, noticing that j=0 < 1 = 64 - 63 in step 28 and 29, meaning we get back to the start of the loop (step 30) but now we increment to j=1 (step 31) and check if j = 1 < 1 = 64 - 63 (step 32), which is obviously false, so t1 + j couldn't get 63 + 1 (which results undefined behavior) but only 63 + 0 (which is allowed).

BR

JPM

Jeff

--
--
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-user...@googlegroups.com.
More information about Crypto++ and this group is available at http://www.cryptopp.com.
---
You received this message because you are subscribed to the Google Groups "Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptopp-user...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jeffrey Walton]

My question is, how can we craft a test case to tickle that finding?

I've looked at the issue and my conclusion is that the system is making a mistake (may be wrong though).

It assumes that t1 may get up to 63 in step 27, it then goes through a standard-for-loop, noticing that j=0 < 1 = 64 - 63 in step 28 and 29, meaning we get back to the start of the loop (step 30) but now we increment to j=1 (step 31) and check if j = 1 < 1 = 64 - 63 (step 32), which is obviously false, so t1 + j couldn't get 63 + 1 (which results undefined behavior) but only 63 + 0 (which is allowed).

OK, thanks. I'm still not clear on it. Its not your analysis, my analysis or Coverity's analysis... Its simply error'ing on the side of caution.

Here's what we are interested int:

        for (unsigned int j=0; j<WORD_BITS-t1; j++)
                temp ^= ((temp >> j) & 1) << (t1 + j);

temp ^= ((temp >> j) & 1) << (t1 + j) reduces to:

        x << (t1 + j);

Here's the equality we are interested in:

        (t1 + j) < WORD_BITS-t1

And it must be less than WORD_BITS. So we should be able to assert on:

        2 * t1 + j < WORD_BITS

Does that sound about right?

Jeff

[Jeffrey Walton]

This assert fires:

    EC2N validation suite running...

    Assertion failed: (2*t1+j < WORD_BITS), function MultiplicativeInverse, file gf2n.cpp, line 720.
    Abort trap: 6

We have to get to the bottom of this so we can clear the finding. I can't let Dr. Guttman's Cryptlib exceed us (http://scan.coverity.com/projects/cryptlib).

Dr. Guttman is a good guy. He's writes some of the tightest, cleanest code I have seen. He also writes self-debugging code, which is rare in the open source world. It probably explains why his defect rate is so low: his code alerts him of problems, so he does not have to waste time tracking problems down.

Jeff

[Jean-Pierre Münch]

Am 17.11.2015 um 10:38 schrieb Jeffrey Walton:

My question is, how can we craft a test case to tickle that finding?

I've looked at the issue and my conclusion is that the system is making a mistake (may be wrong though).

It assumes that t1 may get up to 63 in step 27, it then goes through a standard-for-loop, noticing that j=0 < 1 = 64 - 63 in step 28 and 29, meaning we get back to the start of the loop (step 30) but now we increment to j=1 (step 31) and check if j = 1 < 1 = 64 - 63 (step 32), which is obviously false, so t1 + j couldn't get 63 + 1 (which results undefined behavior) but only 63 + 0 (which is allowed).

OK, thanks. I'm still not clear on it. Its not your analysis, my analysis or Coverity's analysis... Its simply error'ing on the side of caution.

Here's what we are interested int:

        for (unsigned int j=0; j<WORD_BITS-t1; j++)
                temp ^= ((temp >> j) & 1) << (t1 + j);

temp ^= ((temp >> j) & 1) << (t1 + j) reduces to:

        x << (t1 + j);

Here's the equality we are interested in:

        (t1 + j) < WORD_BITS-t1

close. We're interested in t1 + j < WORD_BITS and we know t1 + (WORD_BITS-1) - t < WORD_BITS (from j<WORD_BITS-t1 <=> j<=WORD_BITS-1-t1), which is obviously always true. (Again: only AFAICT)

And it must be less than WORD_BITS. So we should be able to assert on:

        2 * t1 + j < WORD_BITS

if you want to assert, why not t1 + j < WORD_BITS (as coverity suggests).

As to more properly show why the 2*t1 is false here, simply plug-in t1=32 and j=0, this will trigger your assert, but t1+ j clearly is smaller than 64 meaning we're not experiencing undefined behavior.

BR

JPM

Does that sound about right?

Jeff