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