Test unitaire d'algorithmes intrinsèquement aléatoires / non déterministes

Mon projet actuel consiste, de manière succincte, à créer des "événements aléatoires contraignants". Je génère essentiellement un calendrier d'inspections. Certaines d'entre elles sont basées sur des contraintes de planning strictes; vous effectuez une inspection une fois par semaine le vendredi à 10h00. Les autres inspections sont "aléatoires"; il existe des exigences de base configurables telles que "une inspection doit avoir lieu 3 fois par semaine", "l'inspection doit avoir lieu entre 9 h et 21 h" et "il ne devrait pas y avoir deux inspections dans la même période de 8 heures", mais quelles que soient les contraintes configurées pour un ensemble particulier d’inspections, les dates et heures qui en résultent ne doivent pas être prévisibles.

Les tests unitaires et TDD, IMO, ont une grande valeur dans ce système car ils peuvent être utilisés pour le construire de manière incrémentielle alors que son ensemble complet d'exigences est encore incomplet, et assurez-vous que je ne le "sur-ingère" pas pour faire des choses que je ne fais pas. Je ne sais pas pour le moment qu'il me faut. Les horaires stricts étaient une pièce maîtresse pour TDD. Cependant, j'ai du mal à définir vraiment ce que je teste lorsque j'écris des tests pour la partie aléatoire du système. Je peux affirmer que tous les temps produits par le planificateur doivent respecter les contraintes, mais je pourrais mettre en œuvre un algorithme qui passe tous ces tests sans que les temps réels soient très "aléatoires". En fait, c'est exactement ce qui s'est passé. J'ai trouvé un problème dans lequel les heures, bien que non prévisibles exactement, entraient dans un petit sous-ensemble des plages de date / heure autorisées. L'algorithme a quand même réussi toutes les affirmations que je pouvais raisonnablement formuler et je ne pouvais pas concevoir de test automatique qui échouerait dans cette situation, mais qui réussirait s'il était donné des résultats "plus aléatoires". Je devais démontrer que le problème avait été résolu en restructurant certains tests existants pour qu'ils se répètent plusieurs fois et en vérifiant visuellement que les temps générés se situaient dans les limites de la plage autorisée.

Quelqu'un a-t-il des conseils pour concevoir des tests qui devraient s'attendre à un comportement non déterministe?

Merci à tous pour les suggestions. L’opinion principale semble être que j’ai besoin d’un test déterministe pour obtenir des résultats déterministes, répétables et assertables . Logique.

J'ai créé un ensemble de tests "bac à sable" contenant des algorithmes candidats pour le processus contraignant (processus par lequel un tableau d'octets pouvant être long devient long entre min et max). J'exécute ensuite ce code via une boucle FOR qui donne à l'algorithme plusieurs tableaux d'octets connus (valeurs comprises entre 1 et 10 000 000 juste pour commencer) et qui contraint l'algorithme à une valeur comprise entre 1009 et 7919 (j'utilise des nombres premiers pour assurer une algorithme ne passerait pas par un GCF fortuit entre les plages d’entrée et de sortie). Les valeurs contraintes résultantes sont comptées et un histogramme est généré. Pour "réussir", toutes les entrées doivent être reflétées dans l'histogramme (pour nous assurer de ne pas en "perdre"), et la différence entre deux compartiments de l'histogramme ne peut pas être supérieure à 2 (elle doit réellement être <= 1 , mais restez à l’écoute). L'algorithme gagnant, le cas échéant, peut être coupé et collé directement dans le code de production et un test permanent mis en place pour la régression.

Voici le code:

    private void TestConstraintAlgorithm(int min, int max, Func<byte[], long, long, long> constraintAlgorithm)
    {
        var histogram = new int[max-min+1];
        for (int i = 1; i <= 10000000; i++)
        {
            //This is the stand-in for the PRNG; produces a known byte array
            var buffer = BitConverter.GetBytes((long)i);

            long result = constraintAlgorithm(buffer, min, max);

            histogram[result - min]++;
        }

        var minCount = -1;
        var maxCount = -1;
        var total = 0;
        for (int i = 0; i < histogram.Length; i++)
        {
            Console.WriteLine("{0}: {1}".FormatWith(i + min, histogram[i]));
            if (minCount == -1 || minCount > histogram[i])
                minCount = histogram[i];
            if (maxCount == -1 || maxCount < histogram[i])
                maxCount = histogram[i];
            total += histogram[i];
        }

        Assert.AreEqual(10000000, total);
        Assert.LessOrEqual(maxCount - minCount, 2);
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionMSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByMSBRejection);
    }

    private long ConstrainByMSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length-1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;
        //Apply a bitmask to the value, removing the MSB on each loop until it falls in the range.
        var mask = long.MaxValue;
        while (result > max - min)
        {
            mask >>= 1;
            result &= mask;
        }
        result += min;

        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionLSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByLSBRejection);
    }

    private long ConstrainByLSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length - 1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;

        //Bit-shift the number 1 place to the right until it falls within the range
        while (result > max - min)
            result >>= 1;

        result += min;
        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionModulus()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByModulo);
    }

    private long ConstrainByModulo(byte[] buffer, long min, long max)
    {
        buffer[buffer.Length - 1] &= 0x7f;
        var result = BitConverter.ToInt64(buffer, 0);

        //Modulo divide the value by the range to produce a value that falls within it.
        result %= max - min + 1;

        result += min;
        return result;
    }

... et voici les résultats:

Le rejet de LSB (le nombre de bits transférés jusqu’à ce qu’il se situe dans la plage) était horrible, pour une raison très facile à expliquer; lorsque vous divisez un nombre par 2 jusqu'à ce qu'il soit inférieur à un maximum, vous quittez dès qu'il est, et pour toute plage non triviale, les résultats sont biaisés vers le tiers supérieur (comme indiqué dans les résultats détaillés de l'histogramme). ) C'était exactement le comportement que j'ai vu des dates finies; toutes les heures étaient l'après-midi, des jours très spécifiques.

Le rejet de MSB (supprimer le bit le plus significatif du nombre un à la fois jusqu'à ce qu'il soit dans la plage) est préférable, mais encore une fois, étant donné que vous coupez de très grands nombres avec chaque bit, il n'est pas distribué de manière égale; il est peu probable que vous obteniez des chiffres dans les extrémités supérieure et inférieure, vous avez donc un parti pris pour le tiers central. Cela pourrait être avantageux pour quelqu'un qui cherche à "normaliser" des données aléatoires en une courbe en cloche, mais une somme de deux nombres aléatoires ou plus plus petits (similaire à un jet de dés) vous donnerait une courbe plus naturelle. Pour mes besoins, cela échoue.

Le seul qui a réussi ce test a été de contraindre par la division modulo, qui s'est également révélée être la plus rapide des trois. Selon sa définition, Modulo produira une distribution aussi uniforme que possible en fonction des entrées disponibles.

Je suppose que ce que vous voulez réellement tester ici, c’est qu’étant donné un ensemble spécifique de résultats de l’aléodiseur, le reste de votre méthode fonctionne correctement.

Si c'est ce que vous cherchez, alors simulez le randomiseur pour le rendre déterministe dans les limites du test.

J'ai généralement des objets fictifs pour toutes sortes de données non déterministes ou imprévisibles (au moment de l'écriture du test), y compris les générateurs GUID et DateTime.Now.

Edit, from comments: Vous devez vous moquer du PRNG (ce terme m’a échappé la nuit dernière) au niveau le plus bas possible - c.-à-d. lorsqu'il génère le tableau d'octets, pas après que vous les avez convertis en Int64. Ou même aux deux niveaux, vous pouvez donc tester votre conversion en un tableau de Int64 comme prévu et ensuite vérifier séparément que votre conversion en un tableau de DateTimes fonctionne comme prévu. Comme Jonathon l'a dit, vous pouvez simplement le faire en lui donnant une graine définie ou lui donner le tableau d'octets à renvoyer.

Je préfère ce dernier parce que cela ne casse pas si la mise en œuvre du cadre d'un PRNG change. Cependant, l’un des avantages de lui donner le germe est que si vous trouvez un cas en production qui ne fonctionne pas comme prévu, il vous suffit d’avoir enregistré un seul numéro pour pouvoir le répliquer, par opposition à l’ensemble du tableau.

Tout cela étant dit, vous devez vous rappeler qu'il s'appelle un générateur de nombres pseudo aléatoires pour une raison. Il peut y avoir des préjugés même à ce niveau.

Cela va sembler une réponse stupide, mais je vais le dire parce que c'est comme ça que je l'ai vu auparavant:

Découplez votre code du fichier PRNG - transmettez le germe de randomisation à tout le code qui utilise la randomisation. Ensuite, vous pouvez déterminer les valeurs de «travail» à partir d'une seule graine (ou plusieurs graines qui vous feraient sentir mieux). Cela vous donnera la possibilité de tester correctement votre code sans avoir à vous fier à la loi des grands nombres.

Cela semble absurde, mais c'est comme ça que les militaires le font (ou bien ils utilisent un "tableau aléatoire" qui n'est pas vraiment aléatoire du tout)

"Est-ce aléatoire (assez)" s'avère être une question incroyablement subtile. La réponse courte est qu'un test unitaire traditionnel ne suffira tout simplement pas. Vous devrez générer un ensemble de valeurs aléatoires et les soumettre à différents tests statistiques vous garantissant qu'ils sont suffisamment aléatoires pour répondre à vos besoins.

Il y aura un modèle - nous utilisons des générateurs de nombres pseudo-aléatoires, après tout. Mais à un moment donné, les choses seront "assez bonnes" pour votre application (où assez bonnes varient BEAUCOUP entre des jeux à une extrémité, où des générateurs relativement simples suffisent, jusqu’à la cryptographie où il faut vraiment que les séquences soient impossibles à déterminer. par un attaquant déterminé et bien équipé).

L'article de Wikipedia http://fr.wikipedia.org/wiki/Randomness_tests et ses liens de suivi contiennent davantage d'informations.

J'ai deux réponses pour vous.

=== PREMIÈRE RÉPONSE ===

Dès que j'ai vu le titre de votre question, je suis venu intervenir et proposer la solution. Ma solution était la même que celle proposée par plusieurs autres: simuler votre générateur de nombres aléatoires. Après tout, j'ai construit plusieurs programmes différents nécessitant cette astuce pour pouvoir écrire de bons tests unitaires, et j'ai commencé à faire de l'accès fictif à des nombres aléatoires une pratique standard dans tous mes codages.

Mais ensuite j'ai lu votre question. Et pour le problème particulier que vous décrivez, ce n'est pas la réponse. Votre problème n’était pas que vous deviez rendre prévisible un processus utilisant des nombres aléatoires (pour que ce soit vérifiable). Votre problème consistait plutôt à vérifier que votre algorithme mappait la sortie uniformément aléatoire de votre RNG à la sortie uniforme de votre algorithme dans les contraintes, à savoir que si le RNG sous-jacent était uniforme, il en résulterait des temps d’inspection uniformément répartis contraintes du problème).

C'est un problème vraiment difficile (mais assez bien défini). Ce qui signifie que c'est un problème intéressant. J'ai immédiatement commencé à réfléchir à de très bonnes idées pour résoudre ce problème. À l'époque où j'étais un grand programmeur, j'aurais peut-être commencé à utiliser ces idées. Mais je ne suis plus un programmeur expérimenté… J'aime le fait que je sois plus expérimenté et plus compétent maintenant.

Ainsi, au lieu de plonger dans le problème difficile, je me suis dit: quelle est la valeur de cela? Et la réponse était décevante. Votre bogue a déjà été résolu et vous serez diligent à ce sujet à l'avenir. Des circonstances externes ne peuvent pas déclencher le problème, seulement des modifications de votre algorithme. La SEULE raison pour s’attaquer à ce problème intéressant était de satisfaire les pratiques du TDD (Test Driven Design). S'il y a une chose que j'ai apprise, c'est qu'adhérer aveuglément à une pratique lorsqu'elle n'est pas précieuse cause des problèmes. Ma suggestion est la suivante: n'écrivez pas de test pour cela, et continuez.

=== DEUXIEME REPONSE ===

Wow ... quel problème cool!

Ce que vous devez faire ici est d’écrire un test qui vérifie que votre algorithme de sélection des dates et heures d’inspection produira une sortie uniformément distribuée (dans les limites du problème) si le GNA utilisé utilise des nombres uniformément distribués. Voici plusieurs approches, classées par niveau de difficulté.

1. Vous pouvez appliquer la force brute. Il suffit d’exécuter l’algorithme plusieurs fois, avec un véritable GNA comme entrée. Inspectez les résultats de sortie pour voir s'ils sont uniformément répartis. Votre test devra échouer si la distribution varie parfaitement uniforme de plus d'un seuil, et pour vous assurer d'attraper des problèmes, le seuil ne peut pas être réglé trop bas. Cela signifie que vous aurez besoin d'un nombre ÉNORME de tests pour être sûr que la probabilité d'un faux positif (échec du test par hasard) est très faible (bien <1% pour une base de code de taille moyenne; encore moins pour une grande base de code).

2. Considérez votre algorithme comme une fonction qui prend la concaténation de toutes les sorties RNG en entrée, puis génère les temps d’inspection en sortie. Si vous savez que cette fonction est continue par morceaux, il existe un moyen de tester votre propriété. Remplacez le RNG par un RNG modulable et exécutez l'algorithme plusieurs fois pour obtenir une sortie RNG uniformément répartie. Donc, si votre code nécessite 2 appels RNG, chacun dans la plage [0..1], vous pouvez faire exécuter le test 100 fois par l’algorithme, en renvoyant les valeurs [(0.0.0.0), (0.0.0.1), (0.0, 0,2), ... (0,0,0,9), (0,1,0,0), (0,1,0,1), ... (0,9,0,9)]. Ensuite, vous pouvez vérifier si la sortie des 100 exécutions est (approximativement) uniformément distribuée dans la plage autorisée.

3. Si vous devez VRAIMENT vérifier l'algorithme de manière fiable et que vous ne pouvez pas formuler d'hypothèses à son sujet ni exécuter un grand nombre de fois, vous pouvez toujours attaquer le problème, mais vous aurez peut-être besoin de contraintes pour la programmation de l'algorithme. . Découvrez PyPy et son approche de l' espace objet à titre d'exemple. Vous pouvez créer un espace objet qui, au lieu d' exécuter réellement l'algorithme, calcule simplement la forme de la distribution de sortie (en supposant que l'entrée du générateur de réseau de base est uniforme). Bien sûr, cela nécessite que vous construisiez un tel outil et que votre algorithme soit construit avec PyPy ou un autre outil où il est facile d'apporter des modifications drastiques au compilateur et de l'utiliser pour analyser le code.

Pour les tests unitaires, remplacez le générateur aléatoire par une classe générant des résultats prévisibles couvrant tous les cas critiques . C'est-à-dire que votre pseudo-randomiseur génère la valeur la plus basse possible et la plus haute valeur possible, ainsi que le même résultat plusieurs fois de suite.

Vous ne voulez pas que vos tests unitaires négligent, par exemple, des bugs qui se produisent une à une lorsque Random.nextInt (1000) renvoie 0 ou 999.

Vous voudrez peut-être jeter un coup d'œil à Sevcikova et al: "Test automatisé de systèmes stochastiques: une approche statistiquement fondée" ( PDF ).

La méthodologie est mise en œuvre dans divers cas de test pour la plate-forme de simulation UrbanSim .

Une approche par histogramme simple est une bonne première étape, mais ne suffit pas pour prouver le caractère aléatoire. Pour un PRNG uniforme, vous généreriez également (à tout le moins) un nuage de points en 2 dimensions (où x est la valeur précédente et y la nouvelle valeur). Ce complot devrait également être uniforme. Cela est compliqué dans votre situation car il existe des non-linéarités intentionnelles dans le système.

Mon approche serait:

1. valider (ou considérer comme acquis) que le PRNG source est suffisamment aléatoire (à l'aide de mesures statistiques standard)
2. vérifiez qu'une conversion PRNG à date-heure non contrainte est suffisamment aléatoire dans l'espace de sortie (cela vérifie l'absence de biais dans la conversion). Votre simple test d'uniformité de premier ordre devrait suffire ici.
3. vérifier que les cas contraints sont suffisamment uniformes (un simple test d'uniformité du premier ordre sur les casiers valides).

Chacun de ces tests est statistique et nécessite un grand nombre de points d’échantillonnage pour éviter les faux positifs et les faux négatifs avec un degré de confiance élevé.

Concernant la nature de l'algorithme de conversion / contrainte:

Étant donné: méthode pour générer une valeur pseudo-aléatoire p où 0 <= p <= M

Besoin: sortie y dans (éventuellement discontinue) plage 0 <= y <= N <= M

Algorithme:

1. calculer r = floor(M / N), c’est-à-dire le nombre de plages de sortie complètes qui correspondent à la plage d’entrée.
2. calculer la valeur maximale acceptable pour p :p_max = r * N
3. générer des valeurs pour p jusqu'à p_maxtrouver une valeur inférieure ou égale à
4. calculer y = p / r
5. si y est acceptable, renvoyez-le, sinon répétez l'opération à l'étape 3

La clé est de supprimer les valeurs inacceptables plutôt que de plier de manière non uniforme.

en pseudo-code:

# assume prng generates non-negative values
def randomInRange(min, max, prng):
    range = max - min
    factor = prng.max / range

    do:
        value = prng()
    while value > range * factor
    return (value / factor) + min

def constrainedRandom(constraint, prng):
    do:
        value = randomInRange(constraint.min, constraint.max, prng)
    while not constraint.is_acceptable(value)

En plus de valider que votre code n'échoue pas ou de jeter les bonnes exceptions aux bons endroits, vous pouvez créer une paire entrée / réponse valide (même en la calculant manuellement), alimenter l'entrée dans le test et s'assurer qu'elle renvoie la réponse attendue. Pas génial, mais c'est à peu près tout ce que vous pouvez faire, à mon humble avis. Toutefois, dans votre cas, ce n'est pas vraiment aléatoire. Une fois que vous avez créé votre programme, vous pouvez tester la conformité des règles. Vous devez effectuer 3 inspections par semaine, entre 9 et 9; il n'y a pas vraiment besoin ou capacité de tester les heures exactes où l'inspection a eu lieu.

Il n'y a vraiment pas de meilleur moyen que de l'exécuter plusieurs fois et de voir si vous obtenez la distribution souhaitée. Si vous avez 50 programmes d'inspection potentiels autorisés, exécutez le test 500 fois et assurez-vous que chaque programme est utilisé près de 10 fois. Vous pouvez contrôler vos germes générateurs aléatoires pour le rendre plus déterministe, mais cela rendra également vos tests plus étroitement couplés aux détails d'implémentation.

Il n'est pas possible de tester une condition nébuleuse sans définition concrète. Si les dates générées réussissent tous les tests, alors théoriquement, votre application fonctionne correctement. L'ordinateur ne peut pas vous dire si les dates sont "suffisamment aléatoires" car il ne peut pas reconnaître les critères d'un tel test. Si tous les tests réussissent mais que le comportement de l'application n'est toujours pas adapté, la couverture de vos tests est empiriquement inadéquate (du point de vue du TDD).

À mon avis, le mieux est de mettre en œuvre des contraintes de génération de date arbitraires afin que la distribution passe avec succès le test d’odeur humaine.

Enregistrez simplement la sortie de votre randomiseur (pseudo, quantique / chaotique ou réel). Enregistrez ensuite et relisez ces séquences "aléatoires" qui répondent à vos exigences de test ou exposent des problèmes et des bugs potentiels lors de la création de vos scénarios de test unitaire.

Cette affaire semble idéale pour tests basés sur les propriétés .

En bref, il s’agit d’un mode de test dans lequel la structure de test génère des entrées pour le code sous test et les assertions de test valident les propriétés des sorties. Le framework peut alors être assez intelligent pour "attaquer" le code sous test et essayer de le coincer dans une erreur. Le framework est généralement assez intelligent pour détourner votre graine de générateur de nombres aléatoires. En règle générale, vous pouvez configurer la structure de manière à générer au plus N cas de test ou à exécuter au plus N secondes. Vous pouvez également vous souvenir des cas de test ayant échoué de la dernière exécution et les réexécuter en premier avec la version de code la plus récente. Cela permet un cycle d'itération rapide pendant le développement et des tests lents et complets hors bande / dans le CI.

Voici un exemple (stupide, en échec) testant la sumfonction:

@given(lists(floats()))
def test_sum(alist):
    result = sum(alist)
    assert isinstance(result, float)
    assert result > 0

• cadre de test va générer une liste à la fois
• le contenu de la liste sera constitué de nombres à virgule flottante
• sum est appelé et les propriétés du résultat sont validées
• le résultat est toujours float
• le résultat est positif

Ce test trouvera un tas de "bugs" dans sum(si vous avez pu deviner tout cela par vous-même):

• sum([]) is 0 (int, pas un float)
• sum([-0.9]) est négatif
• sum([0.0]) n'est pas strictement positif
• sum([..., nan]) is nan ce qui n'est pas positif

Avec les paramètres par défaut, hpythesisle test échoue après 1 "mauvaise" entrée trouvée, ce qui est bon pour TDD. Je pensais qu'il était possible de le configurer pour signaler de nombreuses / toutes les "mauvaises" entrées, mais je ne trouve pas cette option pour le moment.

Dans le cas du PO, les propriétés validées seront plus complexes: type de contrôle A présent, type de contrôle A trois fois par semaine, temps de contrôle B toujours à 12 heures, type de contrôle C de 9 à 9, [horaire prévu une semaine] contrôles de types A, B, C tous présents, etc.

La bibliothèque la plus connue est QuickCheck pour Haskell. Voir la page Wikipedia ci-dessous pour obtenir une liste de ces bibliothèques dans d’autres langues:

https://en.wikipedia.org/wiki/QuickCheck

Hypothesis (pour Python) a une bonne rédaction de ce type de test:

https://hypothesis.works/articles/what-is-property-based-testing/

ce que vous pouvez tester par unité est la logique qui détermine si les dates aléatoires sont valides ou si une autre date aléatoire doit être sélectionnée.

Il n’existe aucun moyen de tester un générateur de date aléatoire à moins d’obtenir un tas de dates et de décider s’ils sont convenablement aléatoires.

Votre objectif n'est pas d'écrire des tests unitaires et de les réussir, mais de vous assurer que votre programme répond à ses exigences. La seule façon de procéder consiste à définir précisément vos besoins. Par exemple, vous avez mentionné "trois inspections hebdomadaires à des heures aléatoires". Je dirais que les exigences sont les suivantes: (a) 3 inspections (pas 2 ou 4), (b) à des moments qui ne sont pas prévisibles par des personnes qui ne veulent pas être inspectées inopinément, et (c) pas trop rapprochées - deux inspections à cinq minutes d'intervalle sont probablement inutiles, peut-être pas trop éloignées l'une de l'autre.

Donc, vous écrivez les exigences plus précisément que moi. (a) et (c) sont faciles. Pour (b), vous pouvez écrire du code aussi astucieux que possible pour tenter de prédire l'inspection suivante, et pour réussir le test unitaire, ce code ne doit pas être capable de prédire mieux qu'une conjecture pure.

Et bien sûr, vous devez savoir que si vos inspections sont vraiment aléatoires, tout algorithme de prédiction pourrait être correct par hasard. Vous devez donc vous assurer que vos tests unitaires ne paniquez pas si cela se produit. Peut-être effectuer quelques tests supplémentaires. Je ne prendrais pas la peine de tester le générateur de nombres aléatoires, car au final, c'est le programme d'inspection qui compte et peu importe la façon dont il a été créé.