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)

diff --git a/INSTALL b/INSTALL
index 88425a8c81156528aef4bd5e40694b2a1ca099f2..605f1d4cdb73b78623830d21366889e4fdf504f6 100644 (file)
--- a/INSTALL
+++ b/INSTALL
@@ -1200,6 +1200,11 @@
 
  $ make TESTS='[89]? -90'
 
 
  $ make TESTS='[89]? -90'
 

+To stochastically verify that the algorithm that produces uniformly distributed
+random numbers is operating correctly (with a false positive rate of 0.01%):
+
+ $ ./util/shlib_wrap.sh test/bntest -stochastic
+

  Note on multi-threading
  -----------------------
 
  Note on multi-threading
  -----------------------
 

diff --git a/test/bn_rand_range.h b/test/bn_rand_range.h
new file mode 100644 (file)
index 0000000..2a63ef7
--- /dev/null
+++ b/test/bn_rand_range.h
@@ -0,0 +1,58 @@
+/*
+ * WARNING: do not edit!
+ * Generated by statistics/bn_rand_range.py in the OpenSSL tool repository.
+ *
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+static const struct {
+    unsigned int range;
+    unsigned int iterations;
+    double critical;
+} rand_range_cases[] = {
+    {     2,     200,     3.841459 },
+    {     3,     300,     5.991465 },
+    {     4,     400,     7.814728 },
+    {     5,     500,     9.487729 },
+    {     6,     600,    11.070498 },
+    {     7,     700,    12.591587 },
+    {     8,     800,    14.067140 },
+    {     9,     900,    15.507313 },
+    {    10,    1000,    16.918978 },
+    {    11,    1100,    18.307038 },
+    {    12,    1200,    19.675138 },
+    {    13,    1300,    21.026070 },
+    {    14,    1400,    22.362032 },
+    {    15,    1500,    23.684791 },
+    {    16,    1600,    24.995790 },
+    {    17,    1700,    26.296228 },
+    {    18,    1800,    27.587112 },
+    {    19,    1900,    28.869299 },
+    {    20,    2000,    30.143527 },
+    {    30,    3000,    42.556968 },
+    {    40,    4000,    54.572228 },
+    {    50,    5000,    66.338649 },
+    {    60,    6000,    77.930524 },
+    {    70,    7000,    89.391208 },
+    {    80,    8000,   100.748619 },
+    {    90,    9000,   112.021986 },
+    {   100,   10000,   123.225221 },
+    {  1000,   10000,  1073.642651 },
+    {  2000,   20000,  2104.128222 },
+    {  3000,   30000,  3127.515432 },
+    {  4000,   40000,  4147.230012 },
+    {  5000,   50000,  5164.598069 },
+    {  6000,   60000,  6180.299514 },
+    {  7000,   70000,  7194.738181 },
+    {  8000,   80000,  8208.177159 },
+    {  9000,   90000,  9220.799176 },
+    { 10000,  100000, 10232.737266 },
+};
+
+static const int binomial_critical = 29;
+

diff --git a/test/bntest.c b/test/bntest.c
index 2043e43e2708a7b92a3746135605b0a6ce56e688..8df6e0f34cc5231b7a34c3c19b2fcf4779d6a5bc 100644 (file)
--- 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
 
 /*
  * 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;
     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;
 {
     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]++;
     }
 
         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;
     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);
 err:
     BN_free(rng);
     BN_free(val);


@@ -2021,6 +2021,19 @@ err:
     return res;
 }
 
     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;
 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;
 }
 
     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)
 {
 const OPTIONS *test_get_options(void)
 {

-    enum { OPT_TEST_ENUM };

     static const OPTIONS test_options[] = {
         OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
     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 }
         { 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 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;
 
     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));
 #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);
     }
     } else {
         ADD_ALL_TESTS(run_file_tests, n);
     }