Teste de aleatoriedade

Um teste de aleatoriedade (ou teste para aleatoriedade ) é um teste usado para analisar a distribuição de um conjunto de dados, de modo a verificar se ele pode ser descrito como aleatório. Na modelagem estocástica, como em algumas simulações de computador, a aleatoriedade esperada de dados de entrada potenciais pode ser verificada por um teste formal de aleatoriedade, para mostrar que os dados são válidos para uso em execuções de simulação. Se um conjunto selecionado de dados falhar nos testes, os parâmetros podem ser alterados ou outros dados aleatórios podem ser usados para passar nos testes de aleatoriedade.

Fundamentos

A questão da aleatoriedade é uma questão teórica muito importante. Testes de aleatoriedade podem ser usados para determinar se um conjunto de dados tem um padrão reconhecível, o que indicaria que o processo que o gerou é significativamente não aleatório. Na prática, a análise estatística tem se preocupado muito mais em verificar regularidades nos dados do que em no teste da aleatoriedade em si. Muitos "geradores de números aleatórios" em uso hoje são definidos por algoritmos e, portanto, são, na verdade, geradores de números pseudoaleatórios. As sequências que eles produzem são chamadas de sequências pseudoaleatórias, o que pode ocasionar que nem sempre essas sequências serão suficientemente aleatórias, podendo produzir sequências que contêm padrões. Por exemplo, a rotina RANDU falha em muitos testes de aleatoriedade, incluindo o teste espectral.

Stephen Wolfram usou testes de aleatoriedade na saída da Regra 30 para examinar seu potencial para gerar números aleatórios,[1] embora tenha demonstrado ter um tamanho de chave efetivo muito menor do que seu tamanho real[2] e ter um desempenho ruim em um teste qui-quadrado.[3] O uso de um gerador de números aleatórios mal concebido pode colocar a validade de um experimento em dúvida, violando suposições estatísticas. Embora existam técnicas de testes estatísticos comumente usadas, como os padrões NIST, Yongge Wang mostrou que os padrões NIST não são suficientes. Além disso, Yongge Wang[4] projetou técnicas de teste baseadas em distância estatística e na lei do logaritmo iterado. Usando esta técnica, Yongge Wang e Tony Nicol[5] detectaram a fraqueza em geradores pseudoaleatórios comumente usados, como a conhecida versão Debian do gerador pseudoaleatório OpenSSL, que foi corrigido em 2008.

Testes específicos para aleatoriedade

Há diferentes tipos de geradores de números (pseudo-)aleatórios usados na prática, agrupados em famílias de acordo com o algoritmo que utilizam. Eles podem ser encontrados na lista de geradores de números aleatórios e incluem:

  • Gerador congruencial linear e registrador de deslocamento de feedback linear
  • Gerador de Fibonacci generalizado
  • Geradores criptográficos
  • Gerador congruencial quadrático
  • Geradores de autômatos celulares
  • Sequência binária pseudoaleatória

Esses diferentes geradores têm diferentes graus de sucesso na aprovação nos conjuntos de testes. Vários geradores amplamente utilizados falham nos testes de alguma forma pouco grave, enquanto outros geradores "melhores" e anteriores (no sentido de que passaram em todas as baterias de testes atuais e já existiam) foram amplamente ignorados.

Existem muitas medidas práticas de aleatoriedade para uma sequência binária . Isso inclui medidas baseadas em testes estatísticos, transformações e complexidade ou uma mistura destes. Uma coleção de testes bem conhecida e amplamente utilizada foi a Diehard Battery of Tests, introduzida por Marsaglia; isso foi estendido ao conjunto TestU01 por L'Ecuyer e Simard. O uso da transformada de Hadamard para medir a aleatoriedade foi proposto por S. Kak e desenvolvido posteriormente por Phillips, Yuen, Hopkins, Beth e Dai, Mund e Marsaglia e Zaman.[6]

Vários desses testes, que são de complexidade linear, fornecem medidas espectrais de aleatoriedade. T. Beth e ZD. Dai pretendia mostrar que a complexidade de Kolmogorov e a complexidade linear são praticamente equivalentes,[7] embora Y. Wang tenha mostrado mais tarde que estão alegações podem ser consideradas incorretas.[8] No entanto, Wang também demonstrou que, para sequências aleatórias de Martin-Löf, a complexidade de Kolmogorov é essencialmente a mesma que a complexidade linear.

Esses testes práticos permitem comparar a aleatoriedade de strings binárias. Em termos probabilísticos, todas as sequências de um determinado comprimento têm a mesma aleatoriedade. Entretanto, diferentes strings têm uma complexidade de Kolmogorov diferente. Por exemplo, considere as duas sequências de bits a seguir.

Sequência 1: 0101010101010101010101010101010101010101010101010101010101010101
Sequência 2: 1100100001100001110111101110110011111010010000100101011110010110

A sequência 1 admite a descrição informal: "32 repetições da sequência de bit 01". A string 2 não tem nenhuma descrição simples óbvia além de escrever a string em si, que tem 64 caracteres,  e não tem representação de função base comparativamente eficiente. Usando testes espectrais lineares de Hadamard (veja transformada de Hadamard ), a primeira dessas sequências será considerada muito menos aleatoriedade do que a segunda, o que concorda com a intuição.

Implementações notáveis em software

  • Testes Diehard
  • TesteU01
  • Utilitário ENT da Fourmilab[9]
  • Conjunto de testes estatísticos do NIST[10][11]

Ver também

Notas

  1. ↑ Wolfram, Stephen (2002). A New Kind of ScienceRegisto grátis requerido. [S.l.]: Wolfram Media, Inc. pp. 975–976. ISBN 978-1-57955-008-0 
  2. ↑ Willi Meier; Othmar Staffelbach (1991). «Analysis of Pseudo Random Sequences Generated by Cellular Automata». Advances in Cryptology — EUROCRYPT '91. Col: Lecture Notes in Computer Science. 547. [S.l.: s.n.] pp. 186–199. ISBN 978-3-540-54620-7. doi:10.1007/3-540-46416-6_17 
  3. ↑ Moshe Sipper; Marco Tomassini (1996), «Generating parallel random number generators by cellular programming», International Journal of Modern Physics C, 7 (2): 181–190, Bibcode:1996IJMPC...7..181S, doi:10.1142/S012918319600017X .
  4. ↑ Yongge Wang. On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results, http://webpages.uncc.edu/yonwang/, 2014
  5. ↑ Yongge Wang; Tony Nicol (2014), «Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL», Esorics 2014, LNCS 8712: 454–471 
  6. ↑ Terry Ritter, "Randomness tests: a literature survey", webpage: CBR-rand.
  7. ↑ Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology – EUROCRYPT '89. 533-543. Springer-Verlag
  8. ↑ Yongge Wang 1999. Linear complexity versus pseudorandomness: on Beth and Dai's result. In: Proc. Asiacrypt 99, pages 288--298. LNCS 1716, Springer Verlag
  9. ↑ ENT: A Pseudorandom Number Sequence Test Program, Fourmilab, 2008.
  10. ↑ A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Special Publication 800-22 Revision 1a, National Institute of Standards and Technology, 2010.
  11. ↑ Implementation of the NIST Statistical Test Suite

Ligações externas

  • Testes de aleatoriedade incluídos no Cryptographic Toolkit do NIST
  • George Marsaglia, Wai Wan Tsang (2002), " Alguns testes de aleatoriedade difíceis de passar ", Journal of Statistical Software, Volume 7, Edição 3
  • DieHarder: Um conjunto de testes de números aleatórios por Robert G. Brown, Duke University
  • Análise do gerador de números aleatórios online da CAcert.org