rndtest.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*      $OpenBSD$       */
    2 
    3 /*-
    4  * Copyright (c) 2002 Jason L. Wright (jason@thought.net)
    5  * All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  * 3. All advertising materials mentioning features or use of this software
   16  *    must display the following acknowledgement:
   17  *      This product includes software developed by Jason L. Wright
   18  * 4. The name of the author may not be used to endorse or promote products
   19  *    derived from this software without specific prior written permission.
   20  *
   21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   23  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   24  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
   25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
   26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
   27  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   29  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   31  * POSSIBILITY OF SUCH DAMAGE.
   32  */
   33 
   34 #include <sys/cdefs.h>
   35 __FBSDID("$FreeBSD: releng/8.4/sys/dev/rndtest/rndtest.c 139749 2005-01-06 01:43:34Z imp $");
   36 
   37 #include <sys/param.h>
   38 #include <sys/systm.h>
   39 #include <sys/bus.h>
   40 #include <sys/callout.h>
   41 #include <sys/kernel.h>
   42 #include <sys/malloc.h>
   43 #include <sys/module.h>
   44 #include <sys/random.h>
   45 #include <sys/sysctl.h>
   46 #include <machine/stdarg.h>
   47 
   48 #include <dev/rndtest/rndtest.h>
   49 
   50 static  void rndtest_test(struct rndtest_state *);
   51 static  void rndtest_timeout(void *);
   52 
   53 /* The tests themselves */
   54 static  int rndtest_monobit(struct rndtest_state *);
   55 static  int rndtest_runs(struct rndtest_state *);
   56 static  int rndtest_longruns(struct rndtest_state *);
   57 static  int rndtest_chi_4(struct rndtest_state *);
   58 
   59 static  int rndtest_runs_check(struct rndtest_state *, int, int *);
   60 static  void rndtest_runs_record(struct rndtest_state *, int, int *);
   61 
   62 static const struct rndtest_testfunc {
   63         int (*test)(struct rndtest_state *);
   64 } rndtest_funcs[] = {
   65         { rndtest_monobit },
   66         { rndtest_runs },
   67         { rndtest_chi_4 },
   68         { rndtest_longruns },
   69 };
   70 
   71 #define RNDTEST_NTESTS  (sizeof(rndtest_funcs)/sizeof(rndtest_funcs[0]))
   72 
   73 SYSCTL_NODE(_kern, OID_AUTO, rndtest, CTLFLAG_RD, 0, "RNG test parameters");
   74 
   75 static  int rndtest_retest = 120;               /* interval in seconds */
   76 SYSCTL_INT(_kern_rndtest, OID_AUTO, retest, CTLFLAG_RW, &rndtest_retest,
   77             0, "retest interval (seconds)");
   78 static struct rndtest_stats rndstats;
   79 SYSCTL_STRUCT(_kern_rndtest, OID_AUTO, stats, CTLFLAG_RD, &rndstats,
   80             rndtest_stats, "RNG test statistics");
   81 static  int rndtest_verbose = 1;                /* report only failures */
   82 SYSCTL_INT(_kern_rndtest, OID_AUTO, verbose, CTLFLAG_RW, &rndtest_verbose,
   83             0, "display results on console");
   84 
   85 struct rndtest_state *
   86 rndtest_attach(device_t dev)
   87 {
   88         struct rndtest_state *rsp;
   89 
   90         rsp = malloc(sizeof (*rsp), M_DEVBUF, M_NOWAIT);
   91         if (rsp != NULL) {
   92                 rsp->rs_begin = rsp->rs_buf;
   93                 rsp->rs_end = rsp->rs_buf + sizeof(rsp->rs_buf);
   94                 rsp->rs_current = rsp->rs_begin;
   95                 rsp->rs_discard = 1;
   96                 rsp->rs_collect = 1;
   97                 rsp->rs_parent = dev;
   98 #if __FreeBSD_version < 500000
   99                 callout_init(&rsp->rs_to);
  100 #else
  101                 callout_init(&rsp->rs_to, CALLOUT_MPSAFE);
  102 #endif
  103         } else
  104                 device_printf(dev, "rndtest_init: no memory for state block\n");
  105         return (rsp);
  106 }
  107 
  108 void
  109 rndtest_detach(struct rndtest_state *rsp)
  110 {
  111         callout_stop(&rsp->rs_to);
  112         free(rsp, M_DEVBUF);
  113 }
  114 
  115 void
  116 rndtest_harvest(struct rndtest_state *rsp, void *buf, u_int len)
  117 {
  118         size_t i;
  119         /*
  120          * If enabled, collect data and run tests when we have enough.
  121          */
  122         if (rsp->rs_collect) {
  123                 for (i = 0; i < len; i++) {
  124                         *rsp->rs_current = ((u_char *) buf)[i];
  125                         if (++rsp->rs_current == rsp->rs_end) {
  126                                 rndtest_test(rsp);
  127                                 rsp->rs_current = rsp->rs_begin;
  128                                 /*
  129                                  * If tests passed, turn off collection and
  130                                  * schedule another test. Otherwise we keep
  131                                  * testing until the data looks ok.
  132                                  */
  133                                 if (!rsp->rs_discard && rndtest_retest != 0) {
  134                                         rsp->rs_collect = 0;
  135                                         callout_reset(&rsp->rs_to,
  136                                                 hz * rndtest_retest,
  137                                                 rndtest_timeout, rsp);
  138                                         break;
  139                                 }
  140                         }
  141                 }
  142         }
  143         /*
  144          * Only stir entropy that passes muster into the pool.
  145          */
  146         if (rsp->rs_discard)
  147                 rndstats.rst_discard += len;
  148         else {
  149 #if __FreeBSD_version < 500000
  150                 /* XXX verify buffer is word aligned */
  151                 u_int32_t *p = buf;
  152                 for (len /= sizeof (u_int32_t); len; len--)
  153                         add_true_randomness(*p++);
  154 #else
  155                 random_harvest(buf, len, len*NBBY, 0, RANDOM_PURE);
  156 #endif
  157         }
  158 }
  159 
  160 static void
  161 rndtest_test(struct rndtest_state *rsp)
  162 {
  163         int i, rv = 0;
  164 
  165         rndstats.rst_tests++;
  166         for (i = 0; i < RNDTEST_NTESTS; i++)
  167                 rv |= (*rndtest_funcs[i].test)(rsp);
  168         rsp->rs_discard = (rv != 0);
  169 }
  170 
  171 static void
  172 rndtest_report(struct rndtest_state *rsp, int failure, const char *fmt, ...)
  173 {
  174         char buf[80];
  175         va_list ap;
  176 
  177         if (rndtest_verbose == 0)
  178                 return;
  179         if (!failure && rndtest_verbose == 1)   /* don't report successes */
  180                 return;
  181         va_start(ap, fmt);
  182         vsnprintf(buf, sizeof (buf), fmt, ap);
  183         va_end(ap);
  184         device_printf(rsp->rs_parent, "rndtest: %s\n", buf);
  185 }
  186 
  187 #define RNDTEST_MONOBIT_MINONES 9725
  188 #define RNDTEST_MONOBIT_MAXONES 10275
  189 
  190 static int
  191 rndtest_monobit(struct rndtest_state *rsp)
  192 {
  193         int i, ones = 0, j;
  194         u_int8_t r;
  195 
  196         for (i = 0; i < RNDTEST_NBYTES; i++) {
  197                 r = rsp->rs_buf[i];
  198                 for (j = 0; j < 8; j++, r <<= 1)
  199                         if (r & 0x80)
  200                                 ones++;
  201         }
  202         if (ones > RNDTEST_MONOBIT_MINONES &&
  203             ones < RNDTEST_MONOBIT_MAXONES) {
  204                 if (rndtest_verbose > 1)
  205                         rndtest_report(rsp, 0, "monobit pass (%d < %d < %d)",
  206                             RNDTEST_MONOBIT_MINONES, ones,
  207                             RNDTEST_MONOBIT_MAXONES);
  208                 return (0);
  209         } else {
  210                 if (rndtest_verbose)
  211                         rndtest_report(rsp, 1,
  212                             "monobit failed (%d ones)", ones);
  213                 rndstats.rst_monobit++;
  214                 return (-1);
  215         }
  216 }
  217 
  218 #define RNDTEST_RUNS_NINTERVAL  6
  219 
  220 static const struct rndtest_runs_tabs {
  221         u_int16_t min, max;
  222 } rndtest_runs_tab[] = {
  223         { 2343, 2657 },
  224         { 1135, 1365 },
  225         { 542, 708 },
  226         { 251, 373 },
  227         { 111, 201 },
  228         { 111, 201 },
  229 };
  230 
  231 static int
  232 rndtest_runs(struct rndtest_state *rsp)
  233 {
  234         int i, j, ones, zeros, rv = 0;
  235         int onei[RNDTEST_RUNS_NINTERVAL], zeroi[RNDTEST_RUNS_NINTERVAL];
  236         u_int8_t c;
  237 
  238         bzero(onei, sizeof(onei));
  239         bzero(zeroi, sizeof(zeroi));
  240         ones = zeros = 0;
  241         for (i = 0; i < RNDTEST_NBYTES; i++) {
  242                 c = rsp->rs_buf[i];
  243                 for (j = 0; j < 8; j++, c <<= 1) {
  244                         if (c & 0x80) {
  245                                 ones++;
  246                                 rndtest_runs_record(rsp, zeros, zeroi);
  247                                 zeros = 0;
  248                         } else {
  249                                 zeros++;
  250                                 rndtest_runs_record(rsp, ones, onei);
  251                                 ones = 0;
  252                         }
  253                 }
  254         }
  255         rndtest_runs_record(rsp, ones, onei);
  256         rndtest_runs_record(rsp, zeros, zeroi);
  257 
  258         rv |= rndtest_runs_check(rsp, 0, zeroi);
  259         rv |= rndtest_runs_check(rsp, 1, onei);
  260 
  261         if (rv)
  262                 rndstats.rst_runs++;
  263 
  264         return (rv);
  265 }
  266 
  267 static void
  268 rndtest_runs_record(struct rndtest_state *rsp, int len, int *intrv)
  269 {
  270         if (len == 0)
  271                 return;
  272         if (len > RNDTEST_RUNS_NINTERVAL)
  273                 len = RNDTEST_RUNS_NINTERVAL;
  274         len -= 1;
  275         intrv[len]++;
  276 }
  277 
  278 static int
  279 rndtest_runs_check(struct rndtest_state *rsp, int val, int *src)
  280 {
  281         int i, rv = 0;
  282 
  283         for (i = 0; i < RNDTEST_RUNS_NINTERVAL; i++) {
  284                 if (src[i] < rndtest_runs_tab[i].min ||
  285                     src[i] > rndtest_runs_tab[i].max) {
  286                         rndtest_report(rsp, 1,
  287                             "%s interval %d failed (%d, %d-%d)",
  288                             val ? "ones" : "zeros",
  289                             i + 1, src[i], rndtest_runs_tab[i].min,
  290                             rndtest_runs_tab[i].max);
  291                         rv = -1;
  292                 } else {
  293                         rndtest_report(rsp, 0,
  294                             "runs pass %s interval %d (%d < %d < %d)",
  295                             val ? "ones" : "zeros",
  296                             i + 1, rndtest_runs_tab[i].min, src[i],
  297                             rndtest_runs_tab[i].max);
  298                 }
  299         }
  300         return (rv);
  301 }
  302 
  303 static int
  304 rndtest_longruns(struct rndtest_state *rsp)
  305 {
  306         int i, j, ones = 0, zeros = 0, maxones = 0, maxzeros = 0;
  307         u_int8_t c;
  308 
  309         for (i = 0; i < RNDTEST_NBYTES; i++) {
  310                 c = rsp->rs_buf[i];
  311                 for (j = 0; j < 8; j++, c <<= 1) {
  312                         if (c & 0x80) {
  313                                 zeros = 0;
  314                                 ones++;
  315                                 if (ones > maxones)
  316                                         maxones = ones;
  317                         } else {
  318                                 ones = 0;
  319                                 zeros++;
  320                                 if (zeros > maxzeros)
  321                                         maxzeros = zeros;
  322                         }
  323                 }
  324         }
  325 
  326         if (maxones < 26 && maxzeros < 26) {
  327                 rndtest_report(rsp, 0, "longruns pass (%d ones, %d zeros)",
  328                         maxones, maxzeros);
  329                 return (0);
  330         } else {
  331                 rndtest_report(rsp, 1, "longruns fail (%d ones, %d zeros)",
  332                         maxones, maxzeros);
  333                 rndstats.rst_longruns++;
  334                 return (-1);
  335         }
  336 }
  337 
  338 /*
  339  * chi^2 test over 4 bits: (this is called the poker test in FIPS 140-2,
  340  * but it is really the chi^2 test over 4 bits (the poker test as described
  341  * by Knuth vol 2 is something different, and I take him as authoritative
  342  * on nomenclature over NIST).
  343  */
  344 #define RNDTEST_CHI4_K  16
  345 #define RNDTEST_CHI4_K_MASK     (RNDTEST_CHI4_K - 1)
  346 
  347 /*
  348  * The unnormalized values are used so that we don't have to worry about
  349  * fractional precision.  The "real" value is found by:
  350  *      (V - 1562500) * (16 / 5000) = Vn   (where V is the unnormalized value)
  351  */
  352 #define RNDTEST_CHI4_VMIN       1563181         /* 2.1792 */
  353 #define RNDTEST_CHI4_VMAX       1576929         /* 46.1728 */
  354 
  355 static int
  356 rndtest_chi_4(struct rndtest_state *rsp)
  357 {
  358         unsigned int freq[RNDTEST_CHI4_K], i, sum;
  359 
  360         for (i = 0; i < RNDTEST_CHI4_K; i++)
  361                 freq[i] = 0;
  362 
  363         /* Get number of occurances of each 4 bit pattern */
  364         for (i = 0; i < RNDTEST_NBYTES; i++) {
  365                 freq[(rsp->rs_buf[i] >> 4) & RNDTEST_CHI4_K_MASK]++;
  366                 freq[(rsp->rs_buf[i] >> 0) & RNDTEST_CHI4_K_MASK]++;
  367         }
  368 
  369         for (i = 0, sum = 0; i < RNDTEST_CHI4_K; i++)
  370                 sum += freq[i] * freq[i];
  371 
  372         if (sum >= 1563181 && sum <= 1576929) {
  373                 rndtest_report(rsp, 0, "chi^2(4): pass (sum %u)", sum);
  374                 return (0);
  375         } else {
  376                 rndtest_report(rsp, 1, "chi^2(4): failed (sum %u)", sum);
  377                 rndstats.rst_chi++;
  378                 return (-1);
  379         }
  380 }
  381 
  382 static void
  383 rndtest_timeout(void *xrsp)
  384 {
  385         struct rndtest_state *rsp = xrsp;
  386 
  387         rsp->rs_collect = 1;
  388 }
  389 
  390 static int
  391 rndtest_modevent(module_t mod, int type, void *unused)
  392 {
  393         switch (type) {
  394         case MOD_LOAD:
  395                 return 0;
  396         case MOD_UNLOAD:
  397                 return 0;
  398         }
  399         return EINVAL;
  400 }
  401 
  402 static moduledata_t rndtest_mod = {
  403         "rndtest",
  404         rndtest_modevent,
  405         0
  406 };
  407 DECLARE_MODULE(rndtest, rndtest_mod, SI_SUB_DRIVERS, SI_ORDER_ANY);
  408 MODULE_VERSION(rndtest, 1);
Cache object: b3ee685c149dfdeb59ca45feaf245f03
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/dev/rndtest/rndtest.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/rndtest/rndtest.c
