¿Se puede usar una red neuronal para predecir el próximo número pseudoaleatorio?

17

¿Es posible alimentar a una red neuronal la salida de un generador de números aleatorios y esperar que aprenda la función hash (o generador), para que pueda predecir cuál será el próximo número pseudoaleatorio generado ?

¿Ya existe algo como esto? Si ya se ha investigado sobre esto o algo relacionado (a la predicción de números pseudoaleatorios), ¿alguien puede señalarme los recursos correctos?

Actualmente, estoy mirando esta biblioteca y sus enlaces relacionados. https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

AshTyson
fuente

Respuestas:

13

Si estamos hablando de un RNG perfecto, la respuesta es un claro no . Es imposible predecir un número verdaderamente aleatorio, de lo contrario no sería realmente aleatorio.

Cuando hablamos de pseudo RNG, las cosas cambian un poco. Dependiendo de la calidad del PRNG, el problema varía de fácil a casi imposible. Por supuesto, un PRNG muy débil como el que publicó XKCD podría predecirse fácilmente por una red neuronal con poco entrenamiento. Pero en el mundo real las cosas se ven diferentes.

La red neuronal podría ser entrenada para encontrar ciertos patrones en el historial de números aleatorios generados por un PRNG para predecir el siguiente bit. Cuanto más fuerte sea el PRNG, se necesitarán más neuronas de entrada, suponiendo que esté usando una neurona por cada bit de aleatoriedad anterior generado por el PRNG. Cuanto menos predecible sea el PRNG, se necesitarán más datos para encontrar algún tipo de patrón. Para PRNG fuertes esto no es factible.

En una nota positiva, es útil que pueda generar una cantidad arbitraria de patrones de entrenamiento para la red neuronal, suponiendo que tenga control sobre el PRNG y que pueda producir tantos números aleatorios como desee.

Debido a que los PRNG modernos son un componente clave para la criptografía, se ha llevado a cabo una extensa investigación para verificar que son "lo suficientemente aleatorios" para resistir tales ataques de predicción. Por lo tanto, estoy bastante seguro de que no es posible con los recursos informáticos disponibles actualmente construir una red neuronal para atacar con éxito un PRNG que se considera seguro para la criptografía.

También vale la pena señalar que no es necesario predecir exactamente la salida de un PRNG para romper la criptografía; podría ser suficiente para predecir el siguiente bit con una certeza de un poco más del 50% para debilitar significativamente una implementación. Entonces, si puede construir una red neuronal que predice el próximo bit de un PRNG (considerado seguro para la criptografía) con una tasa de éxito del 55%, probablemente saldrá en los titulares de las noticias de seguridad durante bastante tiempo.

Demento
fuente
2
Wow, gracias por la explicación detrás de esto. Estoy tratando de analizar el patrón y predecir el siguiente bit y no es un RNG perfecto, sino un PRNG algo sólido. Pero tampoco es el estado del arte. Creo que con un poco de potencia computacional y una implementación adecuada, podría predecirlo con 60-70%, si no más. Si es posible, ¿puede señalar algún recurso donde pueda leer más sobre esto? No soy de un fondo de investigación y más de un desarrollador.
AshTyson
3

Siendo un novato en el aprendizaje automático, hice este experimento (usando Scikit-learn):

  • Generó un gran número (N) de extracciones pseudoaleatorias, utilizando la función python random.choices para seleccionar N números de 90.

  • Entrenó a un clasificador MLP con datos de entrenamiento compuestos de la siguiente manera:

    • ith muestra: X <- resultados de lotería [i: i + 100], Y <- Resultados de lotería [i]

    En la práctica, apunté a una función que dado N números, podría predecir el siguiente.

  • Pidió al clasificador entrenado que prediga los números restantes.

Resultados:

  • por supuesto, el clasificador obtuvo una puntuación ganadora comparable con la de adivinanzas aleatorias u otras técnicas no basadas en redes neuronales (comparé los resultados con varios clasificadores disponibles en las bibliotecas de aprendizaje de scikit)

  • sin embargo, si genero extracciones de lotería pseudoaleatorias con una función de distribución específica, los números pronosticados por la red neuronal se generan aproximadamente con la misma curva de distribución (si traza las ocurrencias de los números aleatorios y las predicciones de la red neuronal, puedes ver que los dos tienen la misma tendencia, incluso si en la curva de predicciones hay muchos picos, ¿entonces quizás la red neuronal puede aprender sobre distribuciones de números pseudoaleatorios?

  • Si reduzco el tamaño del conjunto de entrenamiento por debajo de cierto límite, veo que el clasificador comienza a predecir siempre los mismos pocos números, que se encuentran entre los más frecuentes en la generación pseudoaleatoria. Por extraño que parezca (o tal vez no), este comportamiento parece aumentar ligeramente la puntuación ganadora.

Francesco Bochicchio
fuente
3

Antigua pregunta, pero pensé que valía una respuesta práctica. Me topé con él justo después de mirar una guía de cómo construir dicha red neuronal, demostrando el eco de la randint de Python como ejemplo . Aquí está el código final sin una explicación detallada, aún bastante simple y útil en caso de que el enlace se desconecte:

from random import randint
from numpy import array
from numpy import argmax
from pandas import concat
from pandas import DataFrame
from keras.models import Sequential
from keras.layers import LSTM
from keras.layers import Dense

# generate a sequence of random numbers in [0, 99]
def generate_sequence(length=25):
    return [randint(0, 99) for _ in range(length)]

# one hot encode sequence
def one_hot_encode(sequence, n_unique=100):
    encoding = list()
    for value in sequence:
        vector = [0 for _ in range(n_unique)]
        vector[value] = 1
        encoding.append(vector)
    return array(encoding)

# decode a one hot encoded string
def one_hot_decode(encoded_seq):
    return [argmax(vector) for vector in encoded_seq]

# generate data for the lstm
def generate_data():
    # generate sequence
    sequence = generate_sequence()
    # one hot encode
    encoded = one_hot_encode(sequence)
    # create lag inputs
    df = DataFrame(encoded)
    df = concat([df.shift(4), df.shift(3), df.shift(2), df.shift(1), df], axis=1)
    # remove non-viable rows
    values = df.values
    values = values[5:,:]
    # convert to 3d for input
    X = values.reshape(len(values), 5, 100)
    # drop last value from y
    y = encoded[4:-1,:]
    return X, y

# define model
model = Sequential()
model.add(LSTM(50, batch_input_shape=(5, 5, 100), stateful=True))
model.add(Dense(100, activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['acc'])
# fit model
for i in range(2000):
    X, y = generate_data()
    model.fit(X, y, epochs=1, batch_size=5, verbose=2, shuffle=False)
    model.reset_states()
# evaluate model on new data
X, y = generate_data()
yhat = model.predict(X, batch_size=5)
print('Expected:  %s' % one_hot_decode(y))
print('Predicted: %s' % one_hot_decode(yhat))

¡Acabo de intentarlo y de hecho funciona bastante bien! Tomó solo un par de minutos en mi viejo netbook lento. Aquí está mi propia salida, diferente del enlace anterior y puede ver que la coincidencia no es perfecta, por lo que supongo que los criterios de salida son demasiado permisivos:

...
 - 0s - loss: 0.2545 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.1845 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.3113 - acc: 0.9500
Expected:  [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 79, 45, 95, 92, 32, 33]
Predicted: [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 95, 45, 95, 92, 32, 33]
isp-zax
fuente
Esto no está aprendiendo a predecir la secuencia aleatoria, está aprendiendo a repetirla. Concretamente, las muestras de entrenamiento, X, consisten en 5 enteros aleatorios, y la salida, y, es el cuarto número entero de 5. Por ejemplo, si X = [15, 33, 44, 30, 3], y = 30. El LSTM está aprendiendo a hacer eco de la cuarta muestra.
thinkki
Si, buen punto. Todavía me parece un ejemplo práctico muy interesante del uso de LSTM. Si sabe cómo aprender algo como Mersenne Twister a partir de la semilla que solo se proporciona como entrada, publíquela aquí, ya que me interesaría mucho verla. Parece posible con suficientes muestras, pero podría estar completamente equivocado.
isp-zax
2

Si un generador de números aleatorios de psuedo está arrojando números, en el análisis de estos números podrá determinar el algoritmo que los produjo porque los números no son aleatorios, están determinados por ese algoritmo y no son casuales. Si el mundo está compuesto de leyes físicas que se pueden entender y replicar, la aparente aleatoriedad que observamos en los eventos se debe a esas leyes físicas. y el generador de psuedo ya no existe, y es una aleatoriedad real que, según su definición, es indeterminable y presenta una paradoja. ¿Cómo pueden las reglas crear aleatoriedad por definición? Nuestra percepción aparente de la aleatoriedad de los eventos que observamos es una alusión y, en realidad, es una certeza que no podemos predecir.

Bobs
fuente
1
Cierto. Aunque bastante filosófico. Esperaba algo de una respuesta técnica. Gracias de todos modos :)
AshTyson
2

Además de lo que dijo Demento, la extensión de la aleatoriedad en el Algoritmo de generación de números aleatorios es la cuestión clave. Los siguientes son algunos diseños que pueden debilitar el RNG:
Secuencias ocultas
Supongamos que se trata de las pocas secuencias de caracteres anteriores generadas: (Solo se usa un ejemplo, para el uso práctico de un rango mayor)

lwjVJA
Ls3Ajg
xpKr+A
XleXYg
9hyCzA
jeFuNg
JaZZoA

Inicialmente, no puede observar ningún patrón en las generaciones, pero al cambiarlos a codificación Base64 y luego a hexadecimal, obtenemos lo siguiente:

9708D524
2ECDC08E
C692ABF8
5E579762
F61C82CC
8DE16E36
25A659A0

Ahora, si restamos cada número del anterior, obtenemos esto:

FF97C4EB6A
97C4EB6A
FF97C4EB6A
97C4EB6A
FF97C4EB6A
FF97C4EB6A

Esto indica que el algoritmo simplemente agrega 0x97C4EB6A al valor anterior, trunca el resultado a un número de 32 bits y Base64 codifica los datos.
Lo anterior es un ejemplo básico. Los algoritmos y sistemas de ML actuales son lo suficientemente capaces de aprender y predecir patrones más complejos.

Dependencia del tiempo
Algunos algoritmos RNG usan el tiempo como la entrada principal para generar números aleatorios, especialmente los creados por los propios desarrolladores para ser utilizados dentro de su aplicación.

Siempre que se implementen algoritmos RNG débiles que parecen ser estocásticos, se pueden extrapolar hacia adelante o hacia atrás con una precisión perfecta en caso de que haya suficiente conjunto de datos disponible.

Ugnes
fuente
Me acabas de demostrar una concepción en mi propia mente entre la cantidad y su comunicación como un método para determinar un patrón que sabía que no estaba lejos de mi intuición :)
Bobs
Pero aún plantea una pregunta inseparable de que la aleatoriedad es un "producto" desconectado de la racionalidad cuando intentamos describirlo a partir de una función del lenguaje que usamos, que se deriva de una humildad en la retención del proceso evolutivo y el método percibido de mantener la cordura humana. jajaja
Bobs
¿Es la aleatoriedad o su percepción una disyunción entre la realidad y la percepción humana y debido a su desunión, solo un residuo de percepción sensible decide la imagen de todos y cada uno de nosotros que observamos y se suma a la aleatoriedad comunicable debido a la desunión intelectual en el factor concéntrico humano en la distribución conceptual.
Bobs
¿Cómo puedes analizar algo sin una base para comenzar su análisis de si su tratando de analizar la aleatoriedad entonces seguramente es a partir de una base de certeza ego entérica lol
Bobs
La seudoaleatoriedad es una propiedad de las personas plásticas que se disfrazan de cualidades reales con las que tienen un desprecio superfluo y una preocupación impía o humana. La determinación conduce a la fe y la certeza de la ocupación y la comunicación saludable del producto de una buena vida, a pesar de los problemas de un equilibrio de dificultades.
Bobs