Trigger edge-cases with randomized testing

[mratsim]

Constantine is currently using randomized testing vs a reference implementation (GMP) and property-based testing which uncovered edge cases (tagged heisenbugs):

• Modular Square Root (spurious?) failure for FKM12_447 #30
• Fused modular square root on 32-bit - wrong "isSquare" result #42
• Fused modular square root on 32-bit - wrong "isSquare" result #43

We need to trigger those edge cases more reliably.
5 years ago, on the release of libsecp256k1, the bitcoin developers described a technique they use to test the library that uncovered a carry bug in OpenSSL CVE-2014-3570. The same kind of carry bug was deemed only discoverable by auditing in TweetNaCL: https://gist.github.com/CodesInChaos/8374632 as it happens with probability 2^-60

The way it works is having the RNG produce long strings of 1 or 0 to trigger carries which when using 2^64 words would happen only with 2^-64 * 2^-64 probability (?).

The incorrectly squared numbers would be expected to be found randomly with probability around one in 2^128, and so when one of the reference implementations of ed25519 had a very similar mistake some described it as "a bug that can only be found by auditing, not by randomized tests". But when we found this weren't auditing OpenSSL (the issue was burred deep in optimized code). Our tests used specially formed random numbers that were intended to explore a class of rare corner cases, a technique I'd previously used in the development of the Opus audio codec. Since our 'random' testing in libsecp256k1 was good enough to find one-in-a-{number too big to name} chance bugs which could "only be found by auditing" I'm a least a little bit proud of the work we've been doing there. (Obviously, we also use many other approaches than random testing on our own code.).

Part of our testing involves an automatic test harness that verifies agreement of our code with other implementations with random test data, including OpenSSL; though to reduce the chance of an uncontrolled disclosure we backed out some of the low level testing after discovering this bug.

This randomized testing revealed the flaw in OpenSSL. I suppose it's also a nice example of statistical reasoning (p=2^-128 that a uniform input triggers the misbehaviour) doesn't itself express risk, since while we've put enormous amounts of CPU cycles into tests we've certainly not done 2^128 work. In this case the reason our testing revealed the issue was because we used non-uniform numbers specifically constructed with low transition probability to better trigger improbable branches like carry bugs (https://github.com/bitcoin/secp256k1/blob/master/src/testrand_impl.h#L45). I used the same technique in the development of the Opus audio codec to good effect.

(Whitebox fuzzing tools like Klee or AFL, or branch coverage analysis, while good tools, seem to not be as effective for errors where the code completely omits a condition rather than having a wrong condition which was not exercised by tests.)

Looking into Fiat-Crypto paper (formally verified crypto primitives) a significant of bugs in cryptographic libraries are related to carries: http://adam.chlipala.net/papers/FiatCryptoSP19/FiatCryptoSP19.pdf

[mratsim]

I think we can close this as a success with #59, I triggered more bugs in 6 hours, while participating in NimConf than I ever triggered since the library was restarted in February (Some of the credit is due to #29 and #63 as it doubled the number of test runs, but still compared to edge cases with 2^-64 probability this is actually a small contribution.

Contributions: #60, #61, #62, #64, #65, #67

#59 actually introduce 2 different skewed RNGs:

1. Like describe by the bitcoin/libsecp256k1 team that creates long strings of 1111... and 000....
2. A RNG with a skewed distribution with an average Hamming Weight of 0.83 instead of 0.5.