lundi 9 juin 2008
Développement de la bibliothèque Hasard
Par haypo, lundi 9 juin 2008 à 13:57 :: Sécurité informatique
Suite au bug OpenSSL de Debian, je me suis à nouveau intéressé de près aux générateurs de nombres pseudo-aléatoires (PRNG). J'ai commencé à écrire la bibliothèque Hasard qui contient plusieurs algorithmes pour générer des nombres et des fonctions de haut niveau : int(min, max), bool(), bytes(size), etc.
Outils ENT et Dieharder
J'ai utilisé le programme ENT pour tester la qualité des algorithmes. ENT utilise :
- Test d'entropie,
- Test du χ²,
- Estimation de PI par la méthode de Monte-Carlo avec calcul de l'erreur en pourcentage
- Calcul de la moyenne arithmétique : (x1+x2+...+xn) / n. La valeur parfaite est 255 / 2 = 127,5.
- Coefficient de corrélation en série (?)
ENT n'accepte en entrée que des fichiers contenant des octets (pseudo-)aléatoires. On ne peut donc pas tester la qualité d'un générateur de nombre flottants par exemple. Exemple de sortie (algorithme RANDU avec l'opérateur pow2(8)) :
Entropy = 6.000000 bits per byte. Optimum compression would reduce the size of this 262144 byte file by 25 percent. Chi square distribution for 262144 samples is 786432.00, and randomly would exceed this value 0.01 percent of the times. Arithmetic mean value of data bytes is 126.0000 (127.5 = random). Monte Carlo value for Pi is 2.999862669 (error 4.51 percent). Serial correlation coefficient is 0.322338 (totally uncorrelated = 0.0).
Il existe également le programme Dieharder qui accepte en entrée des nombres de 32 bits non signés dans un fichier binaire ou un fichier texte. Il utilise des tests bien plus rigoureux, mais comme je ne sais pas les interpréter, je ne vais pas commenter.
Représentation visuelle
C'est pas très rigolo tout ça, alors voyons un peu des dessins et schémas qui permettent de distinguer le bon chasseur du mauvais chasseur. Image générée à partir des 8 bits de poids faible de l'algorithme RANDU :
Chaque pixel utilise une valeur du générateur comme couleur. On voit clairement que l'algorithme n'est pas du tout aléatoire ! Pour reproduire l'image :
$ cd tests $ ./gen_files.py --rng=randu --op=pow2 --bits=8 randu.dat $ ./draw_pil.py --width=300 --height=300 randu.dat
Une autre façon de représenter des nombres est d'utiliser un axe 2D avec x=random() et y=random() :
On voit qu'il existe très peu de combinaisons (x, y) : j'en dénombre 16. Pour reproduire cette image :
$ ./gnuplot.py randu.dat --point=2
La page web graphics présente d'autres images.
Script de tests de la bibliothèque Hasard
Le script gen_files.py génère un fichier au format texte plat qui contient les nombres générés par l'algorithme RANDU pour l'opérateur pow2(8) (génère un nombre dans l'intervalle [0; 255]). Lire file_format.rst pour voir le format de ce fichier. Le script file_info.py calcule l'entropie des nombres générés, la valeur maximale et la valeur minimale.
$ ./file_info.py randu.dat Engine: randu Seed: linux_urandom Range: 0..255 Operation: pow2 Count: 262144 Minimum: 1 Maximum: 251 Entropy: quality=75.00%, value=6.0000/8.0000
On voit que seul 6 bits sur 8 sont réellement aléatoires (2 bits sont invariants) et que l'intervalle annoncé est incorrect : 0..255 versus 1..251.
J'aime bien l'algorithme RANDU car il est vraiment mauvais et il permet donc de tester l'outillage de test :-)
Pour la suite
Ma bibliothèque est encore en chantier. J'ai beaucoup travaillé sur l'outillage pour tester la sortie des algorithmes en comparant avec d'autres bibliothèques comme Python, PHP ou la libc. La version 0.2 n'inclut par encore ce travail, ça sera le cas pour la prochaine version 0.3 qui n'est pas encore publiée. En attendant, vous pouvez utiliser le dépôt Mercurial.
Je ne sais pas trop ce qu'Hasard va donner au final, mais en tout cas ça avance :-)