Comment devrais-je tester le caractère aléatoire?

Considérez une méthode pour mélanger au hasard des éléments dans un tableau. Comment écririez-vous un test unitaire simple mais robuste pour vous assurer que cela fonctionne?

J'ai mis au point deux idées qui présentent toutes deux des défauts évidents:

• Mélangez le tableau, puis assurez-vous que son ordre diffère d'avant. Cela sonne bien, mais échoue si le brassage se trouve dans le même ordre. (Improbable, mais possible.)
• Mélangez le tableau avec une graine constante et comparez-le à la sortie prédéterminée. Cela repose sur la fonction aléatoire renvoyant toujours les mêmes valeurs pour le même germe. Cependant, cela est parfois une hypothèse non valide .

Considérons une deuxième fonction qui simule les jets de dés et renvoie un nombre aléatoire. Comment testeriez-vous cette fonction? Comment vérifierais-tu que la fonction ...

• ne retourne jamais un nombre en dehors des limites données?
• renvoie des nombres dans une distribution valide? (Uniforme pour un dé, normal pour un grand nombre de dés.)

Je cherche des réponses permettant de tester non seulement ces exemples, mais également des éléments de code aléatoires en général. Les tests unitaires sont-ils même la bonne solution ici? Si non, quel genre de tests sont?

Pour soulager tout le monde, je n'écris pas mon propre générateur de nombres aléatoires.

Je ne pense pas que les tests unitaires soient le bon outil pour tester le caractère aléatoire. Un test unitaire doit appeler une méthode et tester la valeur renvoyée (ou l'état de l'objet) par rapport à une valeur attendue. Le problème avec les tests aléatoires est qu’il n’ya pas de valeur attendue pour la plupart des choses que vous souhaitez tester. Vous pouvez tester avec une graine donnée, mais cela ne teste que la répétabilité . Cela ne vous donne aucun moyen de mesurer à quel point la distribution est aléatoire , ou même si elle est aléatoire.

Heureusement, il existe de nombreux tests statistiques que vous pouvez exécuter, tels que la batterie de tests aléatoires Diehard . Voir également:

1. Comment tester à l'unité un générateur de nombres pseudo aléatoires?

   • Steve Jessop vous recommande de rechercher une implémentation testée du même algorithme RNG que vous utilisez et de comparer sa sortie avec les valeurs de départ sélectionnées à votre propre implémentation.
   • Greg Hewgill recommande la suite de tests statistiques ENT .
   • John D. Cook renvoie les lecteurs à l'article de CodeProject intitulé Simple Random Number Generations , qui inclut une implémentation du test de Kolmogorov-Smirnov mentionné dans le volume 2 de Donald Knuth, Algorithmes séminumériques.
   • Plusieurs personnes recommandent de vérifier que la distribution des nombres générés est uniforme, le test du chi carré et que la moyenne et l'écart type se situent dans la plage attendue. (Notez que tester la distribution seule ne suffit pas. [1,2,3,4,5,6,7,8] est une distribution uniforme, mais ce n'est certainement pas aléatoire.)

2. Tests unitaires avec des fonctions qui renvoient des résultats aléatoires

   • Brian Genisio fait remarquer que se moquer de votre RNG est une option pour rendre vos tests répétables, et fournit un exemple de code C #.
   • Encore une fois, plusieurs autres personnes suggèrent d'utiliser des valeurs de départ fixes pour la répétabilité et des tests simples pour une distribution uniforme, le chi carré, etc.

3. Unit Testing Randomness est un article du wiki qui traite de nombreux défis déjà évoqués lors de la tentative de test de ce qui, de par sa nature, ne peut pas être répété. Voici un extrait intéressant de celui-ci:

   J'ai déjà vu winzip utilisé comme un outil pour mesurer le caractère aléatoire d'un fichier de valeurs (évidemment, plus il est petit, moins il est compressé).

1. Testez votre algorithme à l'unité

Pour la première question, je construirais une classe factice dans laquelle vous alimenteriez une séquence de nombres aléatoires pour lesquels vous connaissez le résultat de votre algorithme. De cette façon, vous vous assurez que l'algorithme que vous construisez au-dessus de votre fonction aléatoire fonctionne. Donc, quelque chose comme:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Voir si votre fonction aléatoire est logique

Au test unitaire, vous devez ajouter un test qui s'exécute plusieurs fois et affirme que les résultats

• sont dans les limites que vous définissez (donc, un jet de dés est compris entre 1 et 6) et
• affiche une distribution raisonnable (effectuez plusieurs tests et voyez si la distribution correspond à x% de ce que vous attendiez, par exemple, pour le jet de dés, vous devriez voir une 2augmentation entre 10% et 20% (1/6 = 16,67%) du temps compte tenu que vous l'avez roulé 1000 fois).

3. Test d'intégration de l'algorithme et de la fonction aléatoire

A quelle fréquence pensez-vous que votre tableau est trié dans le tri d'origine? Triez des centaines de fois et affirmez que seulement x% du temps, le tri ne change pas.

C'est en fait déjà un test d'intégration, vous testez l'algorithme avec la fonction aléatoire. Une fois que vous utilisez la fonction aléatoire réelle, vous ne pouvez plus vous échapper avec des tests simples.

Par expérience (j'ai écrit un algorithme génétique), je dirais que la combinaison du test unitaire de votre algorithme, du test de distribution de votre fonction aléatoire et du test d'intégration est la voie à suivre.

Un aspect des PRNG qui semble oublié est que toutes ses propriétés sont de nature statistique: vous ne pouvez pas vous attendre à ce que le brassage d'un tableau entraîne une permutation différente de celle avec laquelle vous avez commencé. Fondamentalement, si vous utilisez un PRNG normal, la seule chose qui vous garantit, c’est qu’il n’utilise pas un modèle simple (espérons-le) et qu’il a une distribution égale entre les nombres qu’il retourne.

Un test approprié pour un PRNG impliquera de l'exécuter au moins 100 fois, puis de vérifier la distribution de la sortie (ce qui constitue une réponse directe à la deuxième partie de la question).

Une réponse à la première question est presque la même: lancez le test environ 100 fois avec {1, 2, ..., n} et comptez le nombre de fois que chaque élément a été à chaque position. Ils devraient être tous à peu près égaux si la méthode de mélange est efficace.

Comment tester les PRNG de qualité cryptographique est tout à fait différent. C’est une question dans laquelle vous ne devriez probablement pas vous attarder, à moins de savoir vraiment ce que vous faites. Les gens sont connus pour détruire (lire: ouvrir des trous catastrophiques dans) de bons cryptosystèmes avec juste quelques «optimisations» ou des modifications triviales.

EDIT: J'ai complètement relu la question, la réponse principale et la mienne. Tant que mes arguments sont toujours valables, j'appuie la réponse de Bill The Lizard. Les tests unitaires sont de nature booléenne - ils échouent ou ils réussissent et ne sont donc pas adaptés pour tester "quelle est la qualité" des propriétés d'un PRNG (ou d'une méthode utilisant un PRNG), car toute réponse à cette question serait quantitative plutôt que polaire.

Cela comporte deux parties: tester la randomisation et tester des choses qui utilisent la randomisation.

Tester la randomisation est relativement simple. Vous vérifiez que la période du générateur de nombres aléatoires est telle que vous vous attendez (pour quelques échantillons utilisant quelques germes un peu aléatoires, dans les limites d’un seuil) et que la distribution de la sortie sur une grande taille d’échantillon est conforme à vos attentes. il soit (dans une certaine limite).

Il est préférable de tester des choses qui utilisent la randomisation avec un générateur déterministe de nombres pseudo-aléatoires. Étant donné que la sortie de la randomisation est connue en fonction de la graine (ses entrées), vous pouvez alors tester les unités normalement, en fonction des entrées par rapport aux sorties attendues. Si votre GNA n'est pas déterministe, alors simulez-le avec un déterministe (ou simplement pas au hasard). Testez la randomisation indépendamment du code qui la consomme.

Laissez-le courir plusieurs fois et visualisez vos données .

Voici un exemple de lecture aléatoire de Coding Horror , vous pouvez voir que l'algorithme est OK ou non:

Il est facile de voir que tous les éléments possibles sont renvoyés au moins une fois (les limites sont correctes) et que la distribution est correcte.

Conseils généraux que j'ai trouvés utiles lorsque vous manipulez du code prenant une entrée aléatoire: Vérifiez les cas extrêmes du caractère aléatoire attendu (valeurs max et min, et les valeurs max + 1 et min-1, le cas échéant). Vérifiez les endroits (au-dessus, au-dessus et au-dessous) où les nombres ont des points d'inflexion (c'est-à-dire -1, 0, 1 ou supérieur à 1, inférieur à 1 et non négatif pour les cas où une valeur fractionnaire pourrait gâcher la fonction). Vérifiez quelques endroits complètement en dehors de l'entrée autorisée. Vérifiez quelques cas typiques. Vous pouvez également ajouter une entrée aléatoire, mais pour un test unitaire qui a pour effet indésirable que la même valeur ne soit pas testée à chaque exécution du test (une approche de graine peut fonctionner, mais testez les 1 000 premiers nombres aléatoires à partir de la graine. S ou quelque chose).

Pour tester la sortie d'une fonction aléatoire, il est important d'identifier l'objectif. Dans le cas des cartes, l'objectif est-il de tester l'uniformité du générateur aléatoire 0-1, afin de déterminer si les 52 cartes apparaissent dans le résultat, ou un autre objectif (peut-être toute cette liste et plus)?

Dans l'exemple spécifique, vous devez supposer que votre générateur de nombres aléatoires est opaque (tout comme il n'est pas logique de tester à l'unité le syscall ou le malloc du système d'exploitation, sauf si vous écrivez des systèmes d'exploitation). Il peut être utile de mesurer le générateur de nombres aléatoires, mais votre objectif n'est pas d'écrire un générateur aléatoire, mais simplement de voir que vous obtenez 52 cartes à chaque fois et qu'elles changent d'ordre.

C'est un long chemin à dire qu'il y a vraiment deux tâches de test ici: vérifier que le GNA produit la bonne distribution et vérifier que le code de lecture aléatoire de votre carte utilise ce GNA pour produire des résultats aléatoires. Si vous écrivez le RNG, utilisez une analyse statistique pour prouver votre distribution. Si vous écrivez le mélangeur de cartes, assurez-vous qu'il y a 52 cartes non répétées dans chaque sortie (c'est un meilleur cas de test par contrôle que vous utilisez le RNG).

Vous pouvez compter sur des générateurs de nombres aléatoires sécurisés

Je viens d'avoir une pensée horrible: vous n'écrivez pas votre propre générateur de nombres aléatoires, n'est-ce pas?

En supposant que ce ne soit pas le cas, vous devriez alors tester le code dont vous êtes responsable , et non le code des autres (tel que l' SecureRandomimplémentation de votre framework).

Tester votre code

Pour vérifier que votre code répond correctement, il est normal d'utiliser une méthode de faible visibilité pour produire les nombres aléatoires, de manière à ce qu'il puisse être facilement remplacé par une classe de test unitaire. Cette méthode surchargée simule efficacement le générateur de nombres aléatoires et vous donne un contrôle total sur ce qui est produit et à quel moment. Par conséquent, vous pouvez pleinement exercer votre code, ce qui est l'objectif des tests unitaires.

Vous allez évidemment vérifier les conditions de bord et vous assurer que le brassage a lieu exactement comme votre algorithme le requiert, en fonction des entrées appropriées.

Test du générateur de nombre aléatoire sécurisé

Si vous n'êtes pas sûr que le générateur de nombres aléatoires sécurisé de votre langue ne soit pas vraiment aléatoire ou soit bogué (fournit des valeurs hors limites, etc.), vous devez effectuer une analyse statistique détaillée de la sortie sur plusieurs centaines de millions d'itérations. Tracer la fréquence d'occurrence de chaque nombre et il devrait apparaître avec une probabilité égale. Si les résultats sont biaisés d'une manière ou d'une autre, vous devez signaler vos résultats aux concepteurs de la structure. Ils seront certainement intéressés à résoudre le problème car les générateurs de nombres aléatoires sécurisés sont fondamentaux pour de nombreux algorithmes de cryptage.

Eh bien, vous ne serez jamais sûr à 100%, alors le mieux que vous puissiez faire est qu'il est probable que les chiffres soient aléatoires. Choisissez une probabilité - disons qu'un échantillon de nombres ou d'éléments apparaîtra x fois pour un million d'échantillons, avec une marge d'erreur. Exécuter la chose un million de fois, et voir si c'est dans la marge. Heureusement, les ordinateurs rendent ce genre de choses facile à faire.

Pour vérifier qu’une source de nombres aléatoires génère quelque chose qui a au moins l’apparence d’aléatoire, je voudrais que le test génère une séquence d'octets assez longue, les écrive dans un fichier temporaire, puis passe à l' outil ent de Fourmilab . Donnez-lui le paramètre -t (terse) pour qu’il génère un fichier CSV facile à analyser. Ensuite, vérifiez les différents numéros pour voir qu'ils sont "bons".

Pour décider quels nombres sont bons, utilisez une source aléatoire connue pour calibrer votre test. Le test devrait presque toujours réussir quand on lui donne un bon ensemble de nombres aléatoires. Parce que même une séquence vraiment aléatoire a une probabilité de générer une séquence qui semble être non aléatoire, vous ne pouvez pas obtenir un test qui sera certain de réussir. Vous ne choisissez que des seuils qui rendent peu probable qu'une séquence aléatoire provoque un échec du test. Le hasard n'est-il pas amusant?

Remarque: Vous ne pouvez pas écrire de test indiquant qu'un PRNG génère une séquence "aléatoire". Vous pouvez uniquement écrire un test qui, s'il réussit, indique une probabilité que la séquence générée par le PRNG soit "aléatoire". Bienvenue dans la joie du hasard!

Cas 1: Tester un mélange:

Considérez un tableau [0, 1, 2, 3, 4, 5], mélangez-le, qu'est-ce qui peut mal tourner? Les choses habituelles: a) pas de mélange du tout, b) mélanger 1-5 mais pas 0, mélanger 0-4 mais pas 5, mélanger et toujours générer le même motif, ...

Un test pour les attraper tous:

Mélangez 100 fois, ajoutez les valeurs dans chaque emplacement. La somme de chaque créneau doit être similaire à chaque autre créneau. Avg / Stddev peut être calculé. (5 + 0) /2=2,5, 100 * 2,5 = 25. La valeur attendue est d'environ 25, par exemple.

Si les valeurs sont en dehors des limites, il y a une petite chance que vous obteniez un faux négatif. Vous pouvez calculer la taille de cette chance. Répétez le test. Eh bien, bien sûr, il y a une petite chance que le test échoue 2 fois de suite. Mais vous n'avez pas de routine qui supprime automatiquement votre source, si le test unitaire échoue, n'est-ce pas? Exécutez-le à nouveau!

Il peut échouer 3 fois de suite? Peut-être devriez-vous tenter votre chance à la loterie.

Cas 2: Lancez un dé

La question des jets de dés est la même question. Lance les dés 6000 fois.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;