6 de noviembre de 2017

Testing the random numbers in Racket with Random Sanity

Introduction

A few days ago I was looking at the Random Sanity project. It is a web service where you send a string of numbers supposedly at random, to see how bad is the random number generator. It doesn’t make a very exhaustive check, so it only detects cases where the generator is very bad, or cases in which the string of random numbers has already been sent.

The string consists of 64 bytes encoded in hexadecimal. For example

and the result is "
true" or "false".

The idea is to use it to test the random number generation functions in Racket and see if they pass this test.

Auxiliary constructions

random-bytes

Generates a string of bytes of length n. It is similar to crypto-random-bytes, but it uses pseudorandom numbers instead of cryptographically secure numbers. (Strange: There is no for/bytes.)

(define (random-bytes n)
  (list->bytes
   (for/list ([i (in-range n)])
     (random 256))))

with-random-seed

The seed of the pseudorandom numbers in Racket is initialized with the milliseconds near the beginning of the program. It is sometimes convenient to locally modify the seed of pseudorandom numbers without affecting the pseudorandom numbers of the rest of the program. This macro allows us to evaluate the body, fixing the seed, and after that continue with the normal pseudorandom sequence.

(define-syntax-rule (with-random-seed seed body ...)
  (parameterize ([current-pseudo-random-generator (make-pseudo-random-generator)])
    (random-seed seed)
    body ...))

Let’s try some examples

(displayln (random 10))                   ; ==> maybe 3
(with-random-seed 1234567890
  (displayln (random 10))                 ; ==>        1
  (displayln (random 10)))                ; ==>        5
(displayln (random 10))                   ; ==> maybe 2
(with-random-seed 1234567890
  (displayln (random 10))                 ; ==>        1
  (displayln (random 10)))                ; ==>        5
(displayln (random 10))                   ; ==> maybe 5

The tester

The main function is the tester, which uses a bytes string. The tester formats it and sends it via hppt to Random Sanity. Then it reads the test result and transforms it into #t or #f, which are more idiomatic. The function has very few error checks, for simplicity and for laziness.

#;(require net/http-client
           file/sha1)
 (define (test-random-bytes b)
  (let-values ([(status headers content)
                (http-sendrecv "rest.randomsanity.org"
                               (string-append "/v1/q/"
                                              (bytes->hex-string b)))])
    (let ([text (port->string content)])
      (cond
        [(string=? text "true") #t]
        [(string=? text "false") #f]
        [else (raise-result-error 'test-random-bytes
                                  "true or false"
                                  text)]))))

Some tests

All zeros # "000 ... 000"

It is not a good example of random numbers and obviously the result is #f.

(test-random-bytes (make-bytes 64 0))  ; ==> #f

Pseudo-random numbers with a fixed seed

The first time someone uses one seed the result is #t (it was me, believe me, I saw a #t) but when someone runs the program again with the same seed the sequence of pseudorandom numbers is repeated, so in all subsequent retries the result is #f. If you test another seed, you should be able to see a #t once and then #f. (Using the same seed 1234567890 in other languages will probably get a string of different bytes, so you can probably see another "true" once. More details.)

(with-random-seed 1234567890
  (test-random-bytes (random-bytes 64)))   ; ==> #f (except the first time)

Fixed seed pseudorandom numbers

Racket initializes the seed of random numbers with the milliseconds at some point near the start of the execution of the program. So every time you will get a different sequence, probably never seen before. Unless this article is an absolute success and millions of people try to run the program, it is very unlikely to be so unlucky to get a repeated seed. So you almost certainly will get #t.

(test-random-bytes (random-bytes 64))   ; ==> #t (almost sure)

Cryptographically secure numbers

For some applications it is a risk that someone else guesses the sequence. In the previous example someone could estimate when the program was run and test all the possible values of the milliseconds in a nearby range until finding the match. For these cases you can use crypto-random-bytes that generates cryptographically safe numbers. If there is no problem in the operating system or in Racket it should be (almost) impossible to find a match, and get a result that is not #t. (This is precisely the goal of Random Sanity, to detect that a serious error was accidentally introduced into the random number generator.)

#;(require racket/random)
(test-random-bytes (crypto-random-bytes 64))  ;  ==> #t

The complete program

It is necessary to use some modules, so for convenience I’ll repeat the complete program. (Some parts of the program that don´t use internet connections can be tested in PasteRack.)

#lang racket

(require net/http-client
         file/sha1
         racket/random)

(define (random-bytes n)
  (list->bytes
   (for/list ([i (in-range n)])
    (random 256))))

(define-syntax-rule (with-random-seed seed body ...)
  (parameterize ([current-pseudo-random-generator (make-pseudo-random-generator)])
    (random-seed seed)
    body ...))

(define (test-random-bytes b)
  (let-values ([(status headers content)
                (http-sendrecv "rest.randomsanity.org"
                               (string-append "/v1/q/"
                                              (bytes->hex-string b)))])
    (let ([text (port->string content)])
      (cond
        [(string=? text "true") #t]
        [(string=? text "false") #f]
        [else (raise-result-error 'test-random-bytes
                                  "true or false"
                                  text)]))))

(test-random-bytes (make-bytes 64 0))        ; ==> #f
(with-random-seed 1234567890
  (test-random-bytes (random-bytes 64)))     ; ==> #f
(test-random-bytes (random-bytes 64))        ; ==> #t
(test-random-bytes (crypto-random-bytes 64)) ; ==> #t