Test of uniformity of BN_rand_range output.

Rework the test so that it fails far less often.

A number of independent tests are executed and 5% are expected to fail.
The number of such failures follows a binomial distribution which permits
a statistical test a 0.01% expected failure rate.

There is a command line option to enable the stochastic range checking.
It is off by default.

Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/8830)

1 files changed, 60 insertions, 24 deletions

diff --git a/test/bntest.c b/test/bntest.c
index 2043e43e27..8df6e0f34c 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -1956,25 +1956,27 @@ static int test_rand(void)
 
 /*
  * Run some statistical tests to provide a degree confidence that the
- * BN_rand_range() function works as expected.  The critical value
- * is computed using the R statistical suite:
+ * BN_rand_range() function works as expected.  The test cases and
+ * critical values are generated by the bn_rand_range script.
  *
- *      qchisq(alpha, df=iterations - 1)
+ * Each individual test is a Chi^2 goodness of fit for a specified number
+ * of samples and range.  The samples are assumed to be independent and
+ * that they are from a discrete uniform distribution.
  *
- * where alpha is the significance level (0.95 is used here) and iterations
- * is the number of samples being drawn.
+ * Some of these individual tests are expected to fail, the success/failure
+ * of each is an independent Bernoulli trial.  The number of such successes
+ * will form a binomial distribution.  The count of the successes is compared
+ * against a precomputed critical value to determine the overall outcome.
  */
-static const struct {
+struct rand_range_case {
     unsigned int range;
     unsigned int iterations;
     double critical;
-} rand_range_cases[] = {
-    { 2,    100,    123.2252 /* = qchisq(.95, df=99)    */ },
-    { 12,   1000,   1073.643 /* = qchisq(.95, df=999)   */ },
-    { 1023, 100000, 100735.7 /* = qchisq(.95, df=99999) */ },
 };
 
-static int test_rand_range(int n)
+#include "bn_rand_range.h"
+
+static int test_rand_range_single(size_t n)
 {
     const unsigned int range = rand_range_cases[n].range;
     const unsigned int iterations = rand_range_cases[n].iterations;
@@ -1998,22 +2000,20 @@ static int test_rand_range(int n)
         counts[v]++;
     }
 
-    TEST_note("range %u  iterations %u  critical %.4f", range, iterations,
-              critical);
-    if (range < 20) {
-        TEST_note("frequencies (expected %.2f)", expected);
-        for (i = 0; i < range; i++)
-            TEST_note("    %2u  %6zu", i, counts[i]);
-    }
     for (i = 0; i < range; i++) {
         const double delta = counts[i] - expected;
         sum += delta * delta;
     }
     sum /= expected;
-    TEST_note("test statistic %.4f", sum);
 
-    if (TEST_double_lt(sum, critical))
-        res = 1;
+    if (sum > critical) {
+        TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical);
+        TEST_note("test case %zu  range %u  iterations %u", n + 1, range,
+                  iterations);
+        goto err;
+    }
+
+    res = 1;
 err:
     BN_free(rng);
     BN_free(val);
@@ -2021,6 +2021,19 @@ err:
     return res;
 }
 
+static int test_rand_range(void)
+{
+    int n_success = 0;
+    size_t i;
+
+    for (i = 0; i < OSSL_NELEM(rand_range_cases); i++)
+        n_success += test_rand_range_single(i);
+    if (TEST_int_ge(n_success, binomial_critical))
+        return 1;
+    TEST_note("This test is expeced to fail by chance 0.01%% of the time.");
+    return 0;
+}
+
 static int test_negzero(void)
 {
     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
@@ -2448,11 +2461,18 @@ static int run_file_tests(int i)
     return c == 0;
 }
 
+typedef enum OPTION_choice {
+    OPT_ERR = -1,
+    OPT_EOF = 0,
+    OPT_STOCHASTIC_TESTS,
+    OPT_TEST_ENUM
+} OPTION_CHOICE;
+
 const OPTIONS *test_get_options(void)
 {
-    enum { OPT_TEST_ENUM };
     static const OPTIONS test_options[] = {
         OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
+        { "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" },
         { OPT_HELP_STR, 1, '-',
           "file\tFile to run tests on. Normal tests are not run\n" },
         { NULL }
@@ -2462,7 +2482,22 @@ const OPTIONS *test_get_options(void)
 
 int setup_tests(void)
 {
-    int n = test_get_argument_count();
+    OPTION_CHOICE o;
+    int n, stochastic = 0;
+
+    while ((o = opt_next()) != OPT_EOF) {
+        switch (o) {
+        case OPT_STOCHASTIC_TESTS:
+            stochastic = 1;
+            break;
+        case OPT_TEST_CASES:
+           break;
+        default:
+        case OPT_ERR:
+	    return 0;
+        }
+    }
+    n  = test_get_argument_count();
 
     if (!TEST_ptr(ctx = BN_CTX_new()))
         return 0;
@@ -2499,7 +2534,8 @@ int setup_tests(void)
 #endif
         ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
         ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
-        ADD_ALL_TESTS(test_rand_range, OSSL_NELEM(rand_range_cases));
+        if (stochastic)
+            ADD_TEST(test_rand_range);
     } else {
         ADD_ALL_TESTS(run_file_tests, n);
     }