6 de noviembre de 2017

Probando los números aleatorios de Racket con Random Sanity

Introducción

Hace unos días estuve mirando el proyecto Random Sanity. Es un servicio web al que uno manda una cadena de números supuestamente al azar, para que vea que tan malo es el generador de números al azar. No hace un chequeo muy exhaustivo, así que sólo detecta casos en que el generador es muy malo, o casos en que la cadena de números al azar ya fue enviada.

La cadena consiste en 64 bytes codificados en hexadecimal. Por ejemplo


y el resultado es "true" o "false".

La idea es usarlo para probar las funciones de generación de números al azar en Racket y ver si pasan este test.

Construcciones auxiliares

random-bytes

Genera una cadena de bytes de largo n. Es parecida a crypto-random-bytes, pero usa números pseudoaleatorios en vez de números criptográficamente seguros. (Extraño: No existe for/bytes.)

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

with-random-seed

La semilla de los números pseudoaleatorios en Racket se inicializa con los milisegundos cerca del comienzo del programa. A veces es cómodo modificar localmente la semilla de los números pseudoaleatorios sin afectar a los números pseudoaleatorios del resto del programa. Esta macro permite evaluar el body fijando la semilla y que después todo vuelva a la normalidad.

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

Probemos algunos ejemplos

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

Testeador

La función principal es el testeador, que usa una cadena de bytes. La formatea y envía por hppt a Random Sanity. Luego lee el resultado del test y lo transforma en #t o #f, que son más idiomáticos. La función tiene muy pocos chequeos de errores, por simplicidad y por pachorra.

#;(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)]))))

Algunos test

Todos ceros #"000...000"

No es un buen ejemplo de números aleatorios y obviamente el resultado es #f.

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

Números pseudoaleatorios con una semilla fija

La primera vez que alguien usa la semilla da #t (fui yo, créanme que vi un #t) pero al ejecutarlo nuevamente con la misma semilla se repite la secuencia de números pseudoalatorios y entonces todas las veces subsiguientes da #f. Probando otra semilla deberían poder ver una vez #t y después #f. (Probando la misma semilla 1234567890 en otros lenguajes probablemente se obtenga una cadena de bytes diferentes, así que probablemente puedan ver una vez el primer "true". Más detalles)

(with-random-seed 1234567890
  (test-random-bytes (random-bytes 64)))   ; ==> #f (salvo la primera vez)

Números pseudoaleatorios sin semilla fija

Racket inicializa la semilla de números aleatorios con los milisegundos en algún momento cerca del inicio de la ejecución del programa. Así que cada vez se obtiene una secuencia diferente, probablemente nunca vista antes. A menos que este artículo sea un éxito desmesurado y millones de personas se pongan a probar el programa es muy poco probable que al ejecutarlo uno tenga tanta mala suerte que se repita la semilla. Así que casi seguramente uno obtiene #t.

(test-random-bytes (random-bytes 64))   ; ==> #t (casi seguro)

Números criptográficamente seguros

Para algunas aplicaciones es un riesgo que alguien adivine la secuencia. En el ejemplo anterior alguien podría estimar cuándo se ejecutó el programa y probar con todos los posibles valores de los milisegundos en un rango cercano hasta encontrar la coincidencia. Para esos casos se puede usar crypto-random-bytes que genera números criptográficamente seguros. Si no hay ningún problema en el sistema operativo o en Racket debería ser (casi) imposible encontrar una coincidencia y que el resultado no sea #t. (Este es justamente el objetivo de Random Sanity, detectar que involuntariamente se introdujo un error grave en el generador de números aleatorios.)

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

El programa completo

Es necesario usar algunos módulos, así que por comodidad repitamos el programa completo. (Algunas partes del programa que no usan conexiones de internet se pueden probar en 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