Comment tester en unité un générateur de nombres pseudo-aléatoires ?

Question

J'ai une classe de générateur de nombres pseudo-aléatoires (PRNG) que je veux soumettre à des tests unitaires. Il existe deux approches :

1. écrivez un scénario de test qui prend une grande quantité d'échantillons et testez s'ils sont correctement distribués. Cette approche peut conduire à un temps d'exécution assez long pour le scénario de test ;
2. calculer une petite série d'échantillons "à la main" et vérifier si l'algorithme PRNG la reproduit. Cette approche peut conduire à la génération d'une séquence non aléatoire sans être remarquée ;

Je dirais que la première approche n'est pas vraiment un test unitaire car elle n'effectue pas un test boîte blanche du générateur, mais d'un autre côté elle teste correctement la responsabilité de la classe. La deuxième approche ressemble plus à un véritable test unitaire, en se concentrant sur l'algorithme, mais elle ne fournit pas autant de preuves pour savoir si la classe remplit sa responsabilité.

Quelle approche préférez-vous, et pourquoi ?

---

Answer 1

Obtenez une autre implémentation du même algorithme PRNG, générez un petit nombre de cas de test longs basés sur des graines connues, et vérifiez que votre implémentation de l'algorithme correspond aux implémentations de tous les autres. Plus vous testez de données, plus il y a de chances que ce soit le cas. Si vous voulez être sérieux, cherchez à savoir comment la validation FIPS est effectuée pour l'algorithme.

Il n'est pas nécessaire de vérifier si la sortie est aléatoire, car d'autres personnes ont effectué beaucoup plus de recherches sur cet algorithme que vous n'êtes capable de reproduire.

Si vous avez inventé votre propre algorithme PRNG, votre problème est tout autre, car en plus de tester votre code, vous devez également tester votre nouvel algorithme. Il y a plusieurs choses à faire - je pense que les plus importantes sont les tests statistiques sur la sortie, et l'examen par les pairs par d'autres cryptographes. Fondamentalement, si vous concevez un algorithme PRNG sans avoir suffisamment de connaissances dans le domaine pour savoir comment le tester, il sera nul.

Answer 2

Pour tester un PRNG, j'utiliserais ENT qui est une suite de tests statistiques vous indiquant les performances de votre PRNG. Je suppose que c'est l'approche 1.

Answer 3

J'imagine qu'en fin de compte, vous voulez les deux tests, car vous voulez être sûr que les deux éléments suivants sont vrais :

(1) les nombres sont correctement distribués et (2) l'algorithme spécifique fonctionne comme prévu.

Peut-être le premier test ne pourrait-il être exécuté qu'occasionnellement, tandis que le second pourrait être utilisé pour vérifier que les modifications du code n'ont pas cassé l'algorithme.

Answer 4

Je pense que votre premier point (#1) vise davantage à tester la qualité des nombres aléatoires générés, qui est dictée par l'algorithme utilisé. Le deuxième point (#2) vise plus à tester la qualité de l'algorithme. mise en œuvre de l'algorithme. Si vous avez conçu l'algorithme, les deux tests sont importants. Si vous avez implémenté un algorithme dont les performances ont été démontrées, le n°2 devrait suffire. Cependant, je testerais probablement plus que quelques graines et les séquences qui en résultent en utilisant une certaine connaissance de la structure de votre générateur particulier.

Answer 5

Le "caractère aléatoire" d'un générateur de nombres pseudo-aléatoires est généralement exprimé comme le nombre moyen d'itérations avant qu'un nombre ne se répète. Il existe de nombreux algorithmes dont le "caractère aléatoire" et les performances varient. Random.org a une bonne explication de certaines analyses faites sur leurs algorithmes. Regardez les images au milieu de la page. Il est facile de voir dans les images statiques à quel point les deux algorithmes sont aléatoires.

L'une des caractéristiques d'un PRNG (une vraie caractéristique, pas un bug déguisé en caractéristique) est qu'il est prévisible. Pour une graine donnée, la même séquence de nombres devrait être produite. Ceci est extrêmement important et nécessaire pour tester et déboguer les programmes qui utilisent des méthodes stochastiques (alias aléatoires).

La séquence de chiffres doit se rapprocher d'une certaine distribution statistique. Testez votre PRNG en générant une grande séquence (disons 10^6 nombres) et effectuez plusieurs tests statistiques sur la séquence, en particulier le test du chi carré (si la distribution est normale). Faites un histogramme de votre échantillon et voyez s'il ressemble à ce que vous attendez.

Si vous contrôlez la façon dont la graine est définie, la séquence générée devrait être la même à chaque fois, ce qui convient pour les tests en boîte blanche. Lorsque vous effectuez vos tests, il est également conseillé de "chauffer" le générateur en l'exécutant pendant une centaine d'itérations avant de collecter votre échantillon.