tests/arc4random.c

   1 /*-
   2  * Copyright (c) 2011 David Schultz
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <stdint.h>
  30 #include <string.h>
  31 #include <math.h>
  32 #include <unistd.h>
  33 #include <pthread.h>
  34 #include <sys/cdefs.h>
  35 #include <sys/types.h>
  36 #include <sys/mman.h>
  37 #include <sys/wait.h>
  38
  39 #include <darwintest.h>
  40 #include <darwintest_utils.h>
  41
  42 #define LEN (1024 * 32)
  43 static void * stress(void *ptr __unused)
  44 {
  45         uint32_t value;
  46         uint8_t buf[LEN + 1];
  47         buf[LEN] = 0;
  48         for (int i = 0; i < LEN; i++){
  49                 value = arc4random();
  50                 if (value % 100 == 0)
  51                         arc4random_stir();
  52                 if ((value & 0x70) == 0)
  53                         arc4random_uniform(value);
  54                 if ((value & 0x7) == 0)
  55                         arc4random_buf(buf, (size_t)i);
  56         }
  57         T_ASSERT_EQ(buf[LEN], 0, NULL);
  58
  59         return NULL;
  60 }
  61
  62 T_DECL(arc4random_stress, "arc4random() stress")
  63 {
  64         const int ncpu = dt_ncpu();
  65
  66         pthread_t thr[ncpu];
  67         for (int i = 0; i < ncpu; i++){
  68                 T_ASSERT_POSIX_ZERO(pthread_create(&thr[i], NULL, stress, NULL), NULL);
  69         }
  70         for (int i = 0; i < ncpu; i++){
  71                 T_ASSERT_POSIX_ZERO(pthread_join(thr[i], NULL), NULL);
  72         }
  73 }
  74
  75 /*
  76  * BUFSIZE is the number of bytes of rc4 output to compare.  The probability
  77  * that this test fails spuriously is 2**(-BUFSIZE * 8).
  78  */
  79 #define BUFSIZE         8
  80
  81 T_DECL(arc4random_fork, "arc4random() shouldn't return the same sequence in child post-fork()")
  82 {
  83         struct shared_page {
  84                 char parentbuf[BUFSIZE];
  85                 char childbuf[BUFSIZE];
  86         } *page;
  87         pid_t pid;
  88         char c;
  89
  90         page = mmap(NULL, sizeof(struct shared_page), PROT_READ | PROT_WRITE,
  91                     MAP_ANON | MAP_SHARED, -1, 0);
  92         T_ASSERT_NE(page, MAP_FAILED, "mmap()");
  93
  94         arc4random_buf(&c, 1);
  95
  96         pid = fork();
  97         if (pid < 0) {
  98                 T_ASSERT_FAIL("fork() failed");
  99         } else if (pid == 0) {
 100                 /* child */
 101                 arc4random_buf(page->childbuf, BUFSIZE);
 102                 exit(0);
 103         } else {
 104                 /* parent */
 105                 int status;
 106                 arc4random_buf(page->parentbuf, BUFSIZE);
 107                 T_ASSERT_EQ(wait(&status), pid, "wait() returns child pid");
 108         }
 109         T_EXPECT_NE(memcmp(page->parentbuf, page->childbuf, BUFSIZE), 0, "sequences are distinct");
 110 }
 111
 112 #define  ARC4_EXPECTATION ((2u << 31)  - 1)/2
 113 #define  ITER 10000000
 114 #define  PROB_THRESH sqrt(6*log2(ITER)/(ITER*1.0))
 115 /* Simple randomness test using a chernoff bound
 116  * If this fails with probability (1 - 2/(ITER)^{4})
 117  *  arc4random is NOT a uniform distribution between
 118  *  0 and 2**32 - 1. Note that this test does not guarantee
 119  *  that arc4random. Is correct, just that it isn't terribly
 120  *  wrong.
 121  * */
 122 T_DECL(arc4random_stats, "ensure arc4random() is random")
 123 {
 124         int i;
 125         int total = 0;
 126         for (i = 0; i < ITER; i++) {
 127                 total += arc4random() > ARC4_EXPECTATION;
 128         }
 129         double prob = total/(ITER*1.0);
 130         T_EXPECT_LT(fabs(prob - 0.5), PROB_THRESH, "probability is within threshold");
 131 }