Journal Hasard 0.8 : bibliothèque de génération des nombres aléatoires

Posté par  (site web personnel) .
Étiquettes : aucune
21
12
mai
2009
Hasard est une bibliothèque de génération de nombres (pseudo) aléatoires.

Simplicité

Elle offre une API simple avec des fonctions de haut niveau et une distribution uniforme. Elle embarque de nombreux algorithmes (Mersenne Twister, ISAAC, RC4, etc.) et peut réutiliser des bibliothèques existantes (OpenSSL, GSL, GMP, glib).

Sécurité

Hasard choisit le meilleur générateur selon vos besoins et votre environnement (Linux, Windows, ...) en utilisant des « profils » (ex: « @fast » ou « @secure »). Le générateur est initialisée automatiquement en utilisant une entropie de bonne qualité (ex: /dev/urandom sous Linux). Les fonctions sont réentrantes et on peut utiliser des verrous pour les processus légers. La graine du générateur est regénérée lors d'un fork.

Tests

La bibliothèque inclut de nombreux tests (unitaires, régression, etc.) et également de nombreux outils pour stocker puis tester un générateur. Un format texte simple a été défini pour pouvoir stocker les nombres générés puis tester la qualité de ces nombres (mesure basique de l'entropie, génération d'images pour un contrôle visuel, etc.).

Hasard est distribué sous licence BSD, écrit en C et un binding Python est disponible. La version 0.8 fonctionne sous Linux, FreeBSD, Windows, sur i386 et x86_64. Voir le site du Projet Hasard pour les détails.

--

Générer des nombres aléatoires avec un ordinateur est un problème difficile, et à la moindre mégarde on peut introduire un biais dans la distribution (certains nombres seront plus fréquents que d'autres). Par exemple, « rand() % 10 » n'est pas la bonne méthode pour tirer un nombre entre 0 et 9, car elle est biaisée. Avec Hasard, hasard_int(rng, 0, 9) va garantir que chaque nombre tiré aura la même probabilité d'apparition.

De même, la graine des générateurs est souvent mal choisie et certaines séries de nombres seront alors plus fréquentes ou bien un attaquant pourra deviner les nombres qui vont être générés. Hasard utilise alors une source d'entropie fiable comme /dev/urandom (ou /dev/random pour le profil @secure).

De nombreux logiciels et bibliothèques ont connus des bugs dans leurs générateurs de nombres pseudo-aléatoires. Hasard n'est pas meilleur, mais possède de nombreux tests et est dédié à cette tâche. Exemples de bug :
* Python : randint() était toujours pair
* PHP : rand() et mt_rand() réinitialisent le générateur à chaque appel (le vrai problème étant que l'initialisation utilise une source d'entropie de mauvaise qualité)
* glibc : strfry() gives skewed distributions
* BIND9 : BIND 9 DNS Cache Poisoning (bugs dans les algorithmes LFSR implémentés)
* etc.

Lire le document doc/real_world.rst du projet Hasard pour d'autres exemples.

--

Journal précédent : Sortie de la bibliothèque Hasard version 0.2 (mai 2008)

  • # Et sinon il existe aussi...

    Posté par  (site web personnel) . Évalué à 10.

    Pourquoi se prendre la tête ? C'est tellement simple de faire un générateur aléatoire !
    http://www.xkcd.com/221/

  • # Place d'Hasard par rapport à GSL, OpenSSL & cie

    Posté par  (site web personnel) . Évalué à 10.

    (rah merde, j'ai posté mon journal alors que je voulais faire une prévisualisation... tant pis, le texte était presque terminé)

    Comme Hasard 0.8 peut maintenant se « brancher » sur OpenSSL et gcrypt, une application qui a des besoins cryptographiques peut utiliser Hasard pour s'abstraire de la bibliothèque sous-jacente : utilisez OpenSSL ou gcrypt, selon vos envies ou vos contraintes (ex: licence).

    Pour GSL par contre, je pense qu'il faudrait que ça soit l'inverse : GSL devrait réutiliser Hasard pour générer la graine des différents algorithmes, voir peut-être aussi pour gsl_rng_uniform_int() et gsl_rng_uniform(). Actuellement, GSL n'offre aucun moyen d'initialiser la graine d'un algorithme :-/

    Hasard pourrait aussi être utilisé directement dans les applications ou dans un langage de programme. Il serait utile à pwgen par exemple (qui utilise /dev/urandom ou drand48 actuellement).

    Les générateurs gmp_mt et glib d'Hasard me servent à tester Hasard et à tester les bibliothèques GMP et glib.

    --

    Comme l'indique son numéro de version (0.8 : 80%), Hasard n'est pas encore terminé et l'API risque encore de changer avant la version 1.0. Il est fort probable que l'API hasard_double() change car elle pose des problèmes pour l'intégration des autres bibliothèques.

  • # .

    Posté par  . Évalué à 5.

    Bonjour,

    >Par exemple, « rand() % 10 » n'est pas la bonne méthode pour tirer un nombre entre 0 et 9, car elle est biaisée.

    Est-ce que tu as plus d'explications ou un lien quelconque ? Ça m'intéresse. Merci.

    • [^] # Re: .

      Posté par  . Évalué à 5.

      man 3 rand

      voir les problèmes de bits de poids forts et faibles.

    • [^] # Re: .

      Posté par  . Évalué à 10.

      Imaginons (pour l'exemple) que la sortie de rand() soit un entier non signé sur 4 bits. Il va donc de 0 à 15. Il y a donc, pour tous les tirages de rand(), 2 possibilités que le résultat soit [0, 5] et une seule pour que le résultat soit [6, 9]. Si les possibilités de rand() sont équiprobable (ce qu'on espère généralement), il y a donc 2 fois plus de chances d'avoir un nombre du premier groupe.
      pour tout x € [0, 5], p(res = x) = 2/16
      pour tout x € [6, 9], p(res = x) = 1/16

      Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

      • [^] # Re: .

        Posté par  (site web personnel) . Évalué à 1.

        Rah j'ai eu du mal à comprendre. Le symbole que tu voulais utiliser, c'est [[∈]], l'appartenance à un ensemble et non [[€]], la monnaie européenne.

        Sinon merci pour ton explication.

      • [^] # Re: .

        Posté par  (site web personnel) . Évalué à 4.

        C'est bluffant (enfin c'est tout à fait logique finalement).

        Pour résumer, la méthode du modulo n'est pas biaisée si et seulement si (on se croirait en cours de maths au lycée tient) la sortie du générateur de nombre aléatoire % l'entier maximum que vous souhaitez obtenir + 1 = 0

        Exemple :
        Vous voulez un entier entre 0 et 31 et votre générateur de nombre aléatoire sort des nombre sur 6 bits non signé.

        64 % (31+1) = 0 donc la technique du modulo peut s'appliquer.

        Par contre si vous voulez un nombre entre 0 et 9, la technique du modulo ne fonctionne plus car 64 % (9+1) = 4


        Question subsidiaire : Y'a-t-il une méthode non biaisée pour obtenir un chiffre entre 0 et 9 avec la sortie de la méthode rand()?

        • [^] # Re: .

          Posté par  . Évalué à 3.

          je pense que oui :)
          par contre il ne faut pas utiliser l'algorithme que je vais utiliser en cas de contrainte temps réels

          l'idée de de relancer le générateur si il a trouvé une réponse dans la partie problématique.
          pour reprendre l'exemple ci dessus si le générateur tire de 1 à 35 et qu'on veut un nombre allant de 1 à 10

          rand1-10(){
          while( a=rand1-35() > 30 );
          return a%10+1;
          }

          Le truc c'est qu'avec l'aléatoire, on n'est jamais garanti de ne pas avoir une succession de cent fois un nombre entre 31et 35, ce qui donne un temps d'exécution aléatoire, mais toutes les durées ne sont pas équiprobable
          (ie durée 1 => 30/35 => 6/7)

          Il ne faut pas décorner les boeufs avant d'avoir semé le vent

          • [^] # Re: .

            Posté par  (site web personnel) . Évalué à 4.

            Ue autre solution qui te garanti un temps constant est d'utiliser des rééls :
            return (double)rand() / rand_max * borne_sup

            a condition que borne_sup soit suffisament inferrieur à rand_max, ce qui est général est le cas puisque typiquement rand_max est égale à , 2^31, 2^32 ou 2^64 et que borne_sup est souvent relativement petit.

            • [^] # Re: .

              Posté par  (site web personnel) . Évalué à 3.

              J'avais d'abord utilisé des nombres flottants, mais cette solution est bancale. Elle fonctionne à peu près sur un entier de 32 bits et un flottant de 64 bits. Mais avec des entiers de 64 bits (type long sur une machine x86_64), la conversion vers/depuis les flottants fait perdre les bits de poids faible et est donc largement biaisée.

              C'est justement pour éviter que chacun recode sa fonction randrange(a,b), un peu biaisée voir complètement fausse, que j'ai codé Hasard.

              La fonction hasard_engine_ulong() a subi de nombreuses réécritures et corrections :

              * Hasard 0.1 : utilisation des flottants mais avec un arrondi foireux, les bornes (min/max) étaient 2x moins fréquentes :-/
              * Hasard 0.3 : correction pour les bornes
              * Hasard 0.4 : support des générateurs dont l'intervalle de sortie est plus petit que celui demandé par l'utilisateur
              * Hasard 0.5 : réécriture de l'algorithme, utilise GMP et uniquement des nombres entiers (pour supporter les CPU 64 bits)
              * Hasard 0.6 : réécriture de l'algorithme, basé sur celui de GSL, pour se passer de GMP (pour limiter les dépendances)

              Je pense que l'algorithme actuel est bon. Il reste juste à gérer un dernier cas : quand ULONG+1 n'est pas un multiple de l'intervalle de sortie du générateur (cas rare, arrive pour certains générateurs peu utilisés et déconseillés).

          • [^] # Re: .

            Posté par  . Évalué à 4.

            Effectivement, rand() % 10 est biaisé, mais tellement peu que ça n'a pas d'importance : ça peut dépendre des machines, mais RAND_MAX doit tourner dans les 2^32. Donc la probabilité de tomber dans un cas problématique (pour %10, entre RAND_MAX arondi à la dizaine inférieure et RAND_MAX) est de l'ordre de 10/RAND_MAX, ce qui doit tourner dans les 10^-10. Du coup, la différence de probabilités est de cet ordre : c'est largement négligeable pour la majorité des applications (voire toutes ?). Ca serait dangereux si on voulait, disons, un nombre entre 0 et RAND_MAX / 1.5, vu que là ça fausse carrément les probabilités (celles de la moitié inférieure ont deux fois plus de chance de sortir que celles de la moitié supérieure)

            Je ne connais pas d'algorithmes qui combinent l'équiprobabilité de la méthode de relance et un temps d'éxécution déterministe (et raisonnable, sinon c'est trop facile), mais ça doit exister.

        • [^] # Re: .

          Posté par  . Évalué à 2.

          Il me semble quand même que ce n'est pas le seul problème, et que les algos des générateurs pseudo-aléatoires sont parfois un peu biaisés en ce qui concerne les bits de poid faible.

          • [^] # Re: .

            Posté par  (site web personnel) . Évalué à 3.

            C'est vrai principalement dans le cas des générateurs congruentiels linéaires qui ont des bits de poids faible vraiment pourris. Dans le cas d'un générateur un poil plus moderne ce problème n'existe plus.

            Le problème c'est que la majoritée des fonctions rand sont des GCL...

            Dans le cas d'un générateur correct qui te produit des vrais entiers 32bits, si ta borne sup est relativement basse, du style 0..100, la solution du modulo est même très bonne. Elle est téoriquement biasée mais en pratique le biai est inexistant.
            Le problème c'est quand ta borne est plus grande ou quand tu ne la connais pas à l'avance, dans ce cas la ça deviens plus génant et il faut utiliser de meilleure solutions.

            Ce qui est important c'est de clairement cerner ses besoin. Le méthode avec rejet peuvent être andicapantes en pratique sans apporter vraiment plus de surtée.

      • [^] # Re: .

        Posté par  . Évalué à 3.

        Euh... Je sens que je vais passer pour une quiche ouiche en math, mais pourrais-tu expliquer cette phrase : "Il y a donc, pour tous les tirages de rand(), 2 possibilités que le résultat soit [0, 5] et une seule pour que le résultat soit [6, 9]." ?
        Merci

        • [^] # Re: .

          Posté par  . Évalué à 2.

          il manque deux « dans » ?

        • [^] # Re: .

          Posté par  . Évalué à 10.

          Si les nombres aléatoires vont de 0 à 15 et que tu veux un nombre entre 0 et 9 (modulo 10):
          - Si le nombre tiré est entre 0 à 5, tu obtiens un nombre entre 0 et 5
          - Si le nombre tiré est entre 6 et 9, tu obtiens un nombres entre 6 et 9
          - Si le nombre tiré est entre 10 et 15, tu obtiens à nouveau un nombre entre 0 et 5.

          Au final, tu as deux fois plus de chances d'obtenir un nombre entre 0 et 5 en utilisant le modulo.

          • [^] # Re: .

            Posté par  . Évalué à 2.

            Ah ben oui ! J'avais zappé le coup du modulo...
            Oki, je m'en vais, plein de honte, me flageller avec des orties fraîches !

    • [^] # Ne pas utiliser modulo

      Posté par  (site web personnel) . Évalué à 2.

      Est-ce que tu as plus d'explications ou un lien quelconque ?

      J'ai écrit ce document qui présente les erreurs courantes :
      http://haypo.hachoir.org/hasard?file/tip/doc/common_errors.r(...)

      Disons que l'intervalle de sortie du générateur soit [a; b] et celui que veut l'utilisateur est [x; y]. On peut utiliser le modulo à condition que :
      * [a; b] soit plus grand (ou de même taille) que [x; y] : (b-a+1) >= (y-x+1)
      * (b-a+1) soit multiple de (y-x+1)

      Exemple : générateur : [0; 99] (100 nombres), utilisateur : [0; 9]. Si le générateur est uniforme, rand() % 10 sera aussi uniforme.

      --

      Hasard réutilise l'idée de l'algorithme de GSL, mais tire plusieurs nombres si l'intervalle du générateur est plus petit que celui de l'utilisateur. L'algorithme général est :
      1. tirer un nombre au hasard
      2. diviser ce nombre par un facteur (pour limiter le nombre d'itérations)
      3. si le nombre est plus grand que ce que veut l'utilisateur, recommencer (retour en 1.)

      Voir lib/randint.c pour les détails :
      http://haypo.hachoir.org/hasard?file/tip/lib/randint.c

      --

      Autre document utile : présentations des implémentations de PRNG existantes, avec quelques bugs que j'ai noté :
      http://haypo.hachoir.org/hasard?file/tip/doc/real_world.rst

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.