Test delle unità di algoritmi intrinsecamente casuali / non deterministici

40

Il mio progetto attuale, in breve, comporta la creazione di "eventi casualmente vincolanti". Fondamentalmente sto generando un programma di ispezioni. Alcuni di essi sono basati su rigidi vincoli di programma; effettui un'ispezione una volta alla settimana il venerdì alle 10:00. Altre ispezioni sono "casuali"; ci sono requisiti configurabili di base come "un'ispezione deve avvenire 3 volte a settimana", "l'ispezione deve avvenire tra le 9.00 e le 21.00" e "non ci dovrebbero essere due ispezioni entro lo stesso periodo di 8 ore", ma all'interno di qualsiasi vincolo configurato per una particolare serie di ispezioni, le date e le ore risultanti non dovrebbero essere prevedibili.

I test unitari e TDD, IMO, hanno un grande valore in questo sistema in quanto possono essere utilizzati per crearlo in modo incrementale mentre il suo set completo di requisiti è ancora incompleto, e assicurarsi che non lo stia "sovra-ingegnerizzando" cose che attualmente non so di cui ho bisogno. Gli orari rigidi erano un pezzo di torta per TDD. Tuttavia, trovo difficile definire veramente quello che sto testando quando scrivo test per la parte casuale del sistema. Posso affermare che tutte le volte prodotte dallo scheduler devono rientrare nei vincoli, ma potrei implementare un algoritmo che superi tutti questi test senza che i tempi effettivi siano molto "casuali". In realtà è esattamente quello che è successo; Ho trovato un problema in cui i tempi, sebbene non prevedibili esattamente, rientravano in un piccolo sottoinsieme degli intervalli di date / orari consentiti. L'algoritmo superava ancora tutte le asserzioni che pensavo di poter fare ragionevolmente, e non potevo progettare un test automatico che avrebbe fallito in quella situazione, ma passare quando si davano risultati "più casuali". Ho dovuto dimostrare che il problema è stato risolto ristrutturando alcuni test esistenti per ripetersi un certo numero di volte e verificando visivamente che i tempi generati rientrassero nell'intervallo consentito.

Qualcuno ha qualche consiglio per progettare test che dovrebbero aspettarsi un comportamento non deterministico?

EDIT: Grazie a tutti per i suggerimenti. L'opinione principale sembra essere che ho bisogno di un test deterministico per ottenere risultati deterministici, ripetibili e attendibili . Ha senso.

Ho creato una serie di test "sandbox" che contengono algoritmi candidati per il processo di limitazione (il processo mediante il quale un array di byte che potrebbe essere lungo può diventare un lungo tra un minimo e un massimo). Quindi eseguo quel codice attraverso un ciclo FOR che fornisce all'algoritmo diversi array di byte noti (valori da 1 a 10.000.000 solo per iniziare) e ha l'algoritmo che vincola ciascuno a un valore compreso tra 1009 e 7919 (sto usando numeri primi per garantire un l'algoritmo non passerebbe da un GCF fortuito tra gli intervalli di input e output). I valori vincolati risultanti vengono contati e viene prodotto un istogramma. Per "passare", tutti gli input devono essere riflessi all'interno dell'istogramma (sanità mentale per assicurarsi di non averli "persi") e la differenza tra due bucket nell'istogramma non può essere maggiore di 2 (dovrebbe essere davvero < = 1, ma rimanete sintonizzati). L'algoritmo vincitore, se esiste, può essere tagliato e incollato direttamente nel codice di produzione e un test permanente messo in atto per la regressione.

Ecco il codice:

    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;
    }

... ed ecco i risultati:

IlrifiutodiLSB(bitchespostailnumerofinchénonrientranell'intervallo)eraTERRIBILE,perunaragionemoltofaciledaspiegare;quandodividiunnumeroqualsiasiper2finoaunvaloreinferioreaunmassimo,escinonappenaloè,eperqualsiasiintervallononbanale,questoinfluenzeràirisultativersoilterzosuperiore(comeèstatoosservatoneirisultatidettagliatidell'istogramma).Questoeraesattamenteilcomportamentochehovistodalledatefinite;tuttelevolteeranonelpomeriggio,ingiornimoltospecifici.

IlrifiutodiMSB(rimuovendoilbitpiùsignificativodalnumerounoallavoltafinchénonrientranell'intervallo)èmigliore,maancoraunavolta,poichéstaitagliandonumerimoltograndiconognibit,nonèdistribuitouniformemente;èimprobabilechesiottenganonumerinelleestremitàsuperioreeinferiore,quindisiottieneunpregiudizioversoilterzomedio.Ciòpotrebbeavvantaggiarequalcunochecercadi"normalizzare" i dati casuali in una curva campana, ma una somma di due o più numeri casuali più piccoli (simili ai dadi da lancio) ti darebbe una curva più naturale. Per i miei scopi, fallisce.

L'unico che ha superato questo test è stato vincolato dalla divisione modulo, che si è rivelata anche la più veloce delle tre. Modulo, per sua definizione, produce una distribuzione il più uniforme possibile, dati gli input disponibili.

    
posta KeithS 02.02.2012 - 21:16
fonte

14 risposte

16

Ciò che in realtà vuoi testare qui, presumo, è che, dato un insieme specifico di risultati del randomizzatore, il resto del tuo metodo funzioni correttamente.

Se questo è ciò che stai cercando, metti sul randomiser, per renderlo deterministico all'interno dei reami del prova.

Generalmente ho oggetti finti per tutti i tipi di dati non deterministici o imprevedibili (al momento della scrittura del test), inclusi i generatori GUID e DateTime.Now.

Modifica, dai commenti: Devi prendere in giro il PRNG (quel termine mi è sfuggito ieri sera) al livello più basso possibile - cioè. quando genera la matrice di byte, non dopo averli trasformati in Int64s. O anche a entrambi i livelli, quindi è possibile testare la conversione in un array di Int64 come previsto e quindi verificare separatamente che la conversione in un array di DateTimes funzioni come previsto. Come ha detto Jonathon, puoi farlo semplicemente dandogli un seme set, o puoi dargli l'array di byte da restituire.

Preferisco il secondo perché non si romperà se l'implementazione del framework di un PRNG cambia. Tuttavia, un vantaggio nel dare il seme è che se trovi un caso in produzione che non ha funzionato come previsto, devi solo aver registrato un numero per poterlo replicare, a differenza dell'intero array.

Tutto ciò detto, è necessario ricordare che si chiama un generatore di numeri casuali Pseudo per un motivo. Potrebbero esserci alcuni bias anche a quel livello.

    
risposta data 02.02.2012 - 21:53
fonte
21

Sembrerà una risposta stupida, ma lo lancerò perché è così che l'ho visto fare prima:

Dissocia il tuo codice dal PRNG - passa il seme della randomizzazione in tutto il codice che usa la randomizzazione. Quindi puoi determinare i valori "di lavoro" da un singolo seme (o più semi che ti faranno sentire meglio). Questo ti darà la possibilità di testare adeguatamente il tuo codice senza dover fare affidamento sulla legge dei grandi numeri.

Sembra strano, ma è così che lo fanno i militari (o che usano una "tabella casuale" che non è affatto casuale)

    
risposta data 02.02.2012 - 23:19
fonte
5

"È casuale (abbastanza)" si rivela essere una domanda incredibilmente sottile. La risposta breve è che un test unitario tradizionale non lo taglierà: dovrai generare una serie di valori casuali e inviarli a vari test statistici che ti danno la certezza che sono abbastanza casuali per le tue esigenze.

Ci sarà un pattern - stiamo usando generatori di numeri random psuedo dopo tutto. Ma a un certo punto le cose saranno "abbastanza buone" per la tua applicazione (dove abbastanza buono varia un LOT tra i giochi ad una estremità, dove bastano generatori relativamente semplici, fino alla crittografia in cui hai davvero bisogno di sequenze per essere impossibile da determinare da un attaccante determinato e ben equipaggiato).

L'articolo di Wikipedia link e i suoi link di follow-up hanno più informazioni.

    
risposta data 03.02.2012 - 18:44
fonte
3

Per i test unitari, sostituisci il generatore casuale con una classe che genera risultati prevedibili che coprono tutti i casi d'angolo . Cioè assicurati che il tuo pseudo-randomizer generi il valore più basso possibile e il valore più alto possibile, e lo stesso risultato più volte di seguito.

Non vuoi che i tuoi test unitari trascurino ad es. bug fuori dall'ambito in cui Random.nextInt (1000) restituisce 0 o 999.

    
risposta data 03.02.2012 - 08:27
fonte
3

Ho due risposte per te.

=== PRIMA RISPOSTA ===

Non appena ho visto il titolo della tua domanda, sono venuto per saltare e proporre la soluzione. La mia soluzione era la stessa che molti altri hanno proposto: prendere in giro il tuo generatore di numeri casuali. Dopotutto, ho costruito diversi programmi che richiedevano questo trucco per scrivere buoni test unitari, e ho iniziato a rendere l'accesso mockable ai numeri casuali una pratica standard in tutta la mia codifica.

Ma poi ho letto la tua domanda. E per il particolare problema che descrivi, questa non è la risposta. Il tuo problema non era che dovevi rendere prevedibile un processo che usava numeri casuali (quindi sarebbe testabile). Piuttosto, il tuo problema consisteva nel verificare che il tuo algoritmo mappasse in modo uniforme l'output casuale dal tuo RNG all'output uniforme all'interno dei vincoli dal tuo algoritmo - che se l'RNG sottostante fosse uniforme ne risulterebbe un tempo di ispezione uniformemente distribuito (soggetto al vincoli di problemi).

Questo è un problema davvero difficile (ma abbastanza ben definito). Il che significa che è un problema INTERESSANTE. Cominciai immediatamente a pensare ad alcune idee veramente grandi su come risolvere questo problema. Quando ero un programmatore hotshot avrei potuto iniziare a fare qualcosa con queste idee. Ma non sono più un programmatore hotshot ... mi piace che ora sono più esperto e più abile.

Quindi, invece di immergermi nel difficile problema, ho pensato tra me: qual è il valore di questo? E la risposta è stata deludente. Il bug è già stato risolto e in futuro sarai diligente su questo problema. Le circostanze esterne non possono innescare il problema, solo le modifiche al tuo algoritmo. L'UNICA ragione per affrontare questo interessante problema era per soddisfare le pratiche del TDD (Test Driven Design). Se c'è una cosa che ho imparato è che aderisce ciecamente a qualsiasi pratica quando non è un problema di cause di valore. Il mio suggerimento è questo: Non scrivere un test per questo e andare avanti.

=== SECONDO RISPOSTO ===

Wow ... che bel problema!

Quello che devi fare qui è scrivere un test che verifichi che il tuo algoritmo per la selezione delle date e dei tempi dell'ispezione produca un output distribuito uniformemente (entro i limiti del problema) se l'RNG che usa produce numeri distribuiti uniformemente. Qui ci sono diversi approcci, ordinati per livello di difficoltà.

  1. È possibile applicare la forza bruta. Basta eseguire l'algoritmo un sacco di volte, con un vero RNG come input. Ispezionare i risultati di output per vedere se sono distribuiti uniformemente. Il tuo test dovrà fallire se la distribuzione varia da perfettamente uniforme di più di una certa soglia, e per assicurarti di avere problemi, la soglia non può essere impostata su TOO low. Ciò significa che avrai bisogno di un numero enorme di corse per essere sicuro che la probabilità di un falso positivo (un fallimento del test per caso) sia molto piccola (beh < 1% per una base di codice di medie dimensioni; ancora meno per una grande base di codice).

  2. Considera il tuo algoritmo come una funzione che accetta la concatenazione di tutti gli output RNG come input, quindi produce tempi di ispezione come output. Se sai che questa funzione è a tratti continua, allora c'è un modo per testare la tua proprietà. Sostituire l'RNG con un RNG mockable ed eseguire l'algoritmo numerose volte, producendo output RNG uniformemente distribuito. Quindi se il tuo codice richiede 2 chiamate RNG, ciascuna nell'intervallo [0..1], potresti avere il test eseguire l'algoritmo 100 volte, restituendo i valori [(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)]. Quindi è possibile verificare se l'output delle 100 esecuzioni è stato (approssimativamente) distribuito uniformemente all'interno dell'intervallo consentito.

  3. Se VERAMENTE hai bisogno di verificare l'algoritmo in modo affidabile e non puoi fare ipotesi sull'algoritmo O eseguire un gran numero di volte, allora puoi ancora attaccare il problema, ma potresti aver bisogno di alcuni vincoli su come si programma l'algoritmo. Dai un'occhiata a PyPy e ai loro Spazio oggetto si avvicina come esempio. È possibile creare uno spazio oggetto che invece di eseguire l'esecuzione dell'algoritmo, invece, ha appena calcolato la forma della distribuzione di output (presupponendo che l'input RNG sia uniforme). Ovviamente, ciò richiede che tu costruisca un tale strumento e che il tuo algoritmo sia compilato in PyPy o in qualche altro strumento in cui è facile apportare modifiche drastiche al compilatore e utilizzarlo per analizzare il codice.

risposta data 03.02.2012 - 18:59
fonte
2

Potresti dare un'occhiata a Sevcikova et al: "Test automatizzati di sistemi stocastici: un approccio statisticamente fondato" ( PDF ).

La metodologia è implementata in vari casi di test per la UrbanSim piattaforma di simulazione.

    
risposta data 03.02.2012 - 00:58
fonte
2

Un semplice approccio dell'istogramma è un buon primo passo, ma non è sufficiente a dimostrare la casualità. Per un PRNG uniforme si dovrebbe anche (almeno) generare un grafico a dispersione bidimensionale (dove x è il valore precedente e y è il nuovo valore). Anche questa trama dovrebbe essere uniforme. Questo è complicato nella tua situazione perché ci sono non-linearità intenzionali nel sistema.

Il mio approccio sarebbe:

  1. convalidare (o prendere come dato) che il PRNG di origine è sufficientemente casuale (utilizzando misure statistiche standard)
  2. verificare che una conversione PRNG-to-datetime non vincolata sia sufficientemente casuale sullo spazio di output (ciò verifica una mancanza di bias nella conversione). Il tuo semplice test di uniformità del primo ordine dovrebbe essere sufficiente qui.
  3. verificare che i casi vincolati siano sufficientemente uniformi (un semplice test di uniformità del primo ordine sui contenitori validi).

Ciascuno di questi test è statistico e richiede un numero elevato di punti di campionamento per evitare falsi positivi e falsi negativi con un elevato grado di sicurezza.

Per quanto riguarda la natura dell'algoritmo di conversione / vincolo:

Dato: metodo per generare valore pseudo-casuale p dove 0 < = p < = M

Necessario: output y nell'intervallo (possibilmente discontinuo) 0 < = y < = N < = M

Algoritmo:

  1. calcola r = floor(M / N) , ovvero il numero di intervalli di output completi che rientrano nell'intervallo di input.
  2. calcola il valore massimo accettabile per p : p_max = r * N
  3. genera valori per p fino a quando viene trovato un valore inferiore o uguale a p_max
  4. calcola y = p / r
  5. se y è accettabile, restituiscilo, altrimenti ripeti con il passaggio 3

La chiave è di scartare valori inaccettabili anziché piegarli in modo non uniforme.

in pseudo-codice:

# 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)
    
risposta data 03.02.2012 - 22:23
fonte
1

A parte la convalida che il tuo codice non fallisce, o getta le giuste eccezioni nelle giuste posizioni puoi creare coppie di input / risposte valide (anche calcolando questo manualmente), alimenta l'input nel test e assicurati che restituisca la risposta attesa . Non eccezionale, ma questo è praticamente tutto quello che puoi fare, imho. Tuttavia, nel tuo caso non è davvero casuale, una volta creato il tuo programma puoi testare la conformità alle regole - devono avere 3 ispezioni a settimana, tra 9-9; non vi è alcuna reale necessità o capacità di testare per i tempi esatti in cui si è verificato l'ispezione.

    
risposta data 02.02.2012 - 21:31
fonte
1

Non c'è davvero modo migliore di eseguirlo un po 'di volte e vedere se si ottiene la distribuzione desiderata. Se hai 50 programmi di ispezione potenziali consentiti, esegui il test 500 volte e assicurati che ogni pianificazione venga utilizzata circa 10 volte. Puoi controllare i tuoi semi di generatore casuali per renderlo più deterministico, ma ciò renderà anche i tuoi test più strettamente accoppiati ai dettagli di implementazione.

    
risposta data 02.02.2012 - 23:53
fonte
1

Non è possibile testare una condizione nebulosa che non ha una definizione concreta. Se le date generate superano tutti i test, in teoria l'applicazione funziona correttamente. Il computer non può dirti se le date sono "abbastanza casuali" perché non può riconoscere i criteri per tale test. Se tutti i test passano ma il comportamento dell'applicazione non è ancora adatto, la copertura del test è empiricamente inadeguata (da una prospettiva TDD).

Dal mio punto di vista, la cosa migliore da fare è implementare alcuni vincoli di generazione di date arbitrari in modo che la distribuzione superi un test dell'odore umano.

    
risposta data 03.02.2012 - 05:57
fonte
0

Basta registrare l'output del tuo randomizer (sia esso pseudo o quantico / caotico o mondo reale). Quindi salva e ripeti quelle sequenze "casuali" che si adattano ai tuoi requisiti di test o che espongono potenziali problemi e bug, mentre sviluppi i casi di test unitario.

    
risposta data 03.02.2012 - 06:45
fonte
0

Questo caso sembra l'ideale per Test basato su proprietà .

In poche parole, è una modalità di test in cui il framework di test genera input per il codice in prova e asserzioni di test convalidare proprietà degli output. Il framework può quindi essere abbastanza intelligente da "attaccare" il codice sotto test e provare ad inserirlo in un errore. Il framework di solito è anche abbastanza intelligente da dirottare il seed del generatore di numeri casuali. In genere è possibile configurare il framework per generare al massimo N casi di test o eseguire al massimo N secondi, e ricordare i casi di test non riusciti dall'ultima esecuzione e rieseguire questi contro la versione più recente del codice. Ciò consente un ciclo di iterazione veloce durante lo sviluppo e un test lento e completo fuori banda / in CI

Ecco un esempio (stupido, inefficace) che prova la funzione sum :

@given(lists(floats()))
def test_sum(alist):
    result = sum(alist)
    assert isinstance(result, float)
    assert result > 0
  • framework di test genererà un elenco alla volta
  • il contenuto dell'elenco sarà in virgola mobile
  • sum è chiamato e le proprietà del risultato sono validate
  • result è sempre float
  • il risultato è positivo

Questo test troverà un sacco di "bug" in sum (commenta se sei riuscito a indovinare tutti di questi da soli):

  • sum([]) is 0 (int, non un float)
  • sum([-0.9]) è negativo
  • sum([0.0]) non è strettamente positivo
  • sum([..., nan]) is nan che non è positivo

Con le impostazioni predefinite, hpythesis interrompe il test dopo che è stato trovato 1 input "cattivo", il che è positivo per TDD. Ho pensato che fosse possibile configurarlo per segnalare molti / tutti gli input "cattivi", ma ora non riesco a trovare le opzioni.

Nel caso dell'OP, le proprietà convalidate saranno più complesse: tipo di ispezione A presente, tipo di ispezione Tre volte a settimana, tempo di ispezione B sempre alle 12pm, tipo di ispezione C da 9 a 9, [dato il programma è per una settimana] ispezioni dei tipi A, B, C tutti presenti, ecc.

La libreria più conosciuta è QuickCheck per Haskell, vedi la pagina di Wikipedia qui sotto per un elenco di tali librerie in altre lingue:

link

Ipotesi (per Python) ha una buona opinione su questo tipo di test:

link

    
risposta data 15.11.2018 - 02:44
fonte
-1

ciò che puoi testare è la logica che determina se le date casuali sono valide o se è necessario selezionare un'altra data casuale.

Non c'è modo di testare un generatore di date casuali per ottenere un sacco di date e decidere se sono opportunamente casuali.

    
risposta data 02.02.2012 - 22:46
fonte
-1

Il tuo obiettivo non è scrivere test unitari e passarli, ma assicurarti che il tuo programma soddisfi i suoi requisiti. L'unico modo per farlo è quello di definire con precisione le tue esigenze in primo luogo. Ad esempio, hai citato "tre ispezioni settimanali a orari casuali". Direi che i requisiti sono: (a) 3 ispezioni (non 2 o 4), (b) in momenti che non sono prevedibili da persone che non vogliono essere ispezionate inaspettatamente, e (c) non troppo vicine tra loro - due ispezioni a cinque minuti di distanza sono probabilmente inutili, forse non troppo distanti.

Quindi scrivi i requisiti più precisamente di me. (a) e (c) sono facili. Per (b), potresti scrivere un codice il più intelligente possibile che cerchi di prevedere l'ispezione successiva, e per superare il test unitario, quel codice non deve essere in grado di prevedere meglio di una semplice ipotesi.

E ovviamente devi essere consapevole che se le tue ispezioni sono veramente casuali, qualsiasi algoritmo di predizione potrebbe essere corretto per puro caso, quindi devi essere sicuro che tu e i tuoi test unitari non panico se ciò accade. Forse esegui qualche altro test. Non mi preoccuperei di testare il generatore di numeri casuali, perché alla fine è il programma di ispezione che conta, e non importa come è stato creato.

    
risposta data 25.03.2014 - 19:55
fonte

Leggi altre domande sui tag