Fuzzing contro l'esecuzione simbolica: qual è la differenza?

1

Lo sfarfallio, secondo una definizione attuale di Wikipedia, è definito nel modo seguente:

Fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exceptions such as crashes, failing built-in code assertions, or potential memory leaks. Typically, fuzzers are used to test programs that take structured inputs.

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

L'esecuzione simbolica, al contrario, è definita nel modo seguente, anche prendendo da Wikipedia:

In computer science, symbolic execution (also symbolic evaluation) is a means of analyzing a program to determine what inputs cause each part of a program to execute. An interpreter follows the program, assuming symbolic values for inputs rather than obtaining actual inputs as normal execution of the program would, a case of abstract interpretation.

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

Quello che sto cercando di capire è la differenza funzionale tra questi due metodi. Vedo la linea che dice che l'esecuzione simbolica determina "quali input fanno sì che ogni parte di un programma venga eseguita", quindi potresti differenziare ciascun metodo dall'obiettivo che un ricercatore della sicurezza ha in mente. I documenti che ho letto hanno recentemente differenziato l'esecuzione simbolica dalla confusione dicendo che il primo ha un sovraccarico significativamente maggiore / eseguito più lentamente.

Dal mio punto di vista, l'esecuzione simbolica utilizza una forma di "fuzzing mirato" che colpisce in modo specifico determinati valori simbolici. Ho anche sentito dire che l'esecuzione simbolica è solo "una confusione più sofisticata".

Qualcuno può chiarire qual è la vera differenza tra i due e perché o quando dovremmo preferire un metodo all'altro?

    
posta Bradley Evans 01.11.2018 - 21:47
fonte

2 risposte

3

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

L'esecuzione simbolica (dinamica) viene talvolta denominata "fuzzing whitebox", ad esempio SAGE . Il fuzzing può essere raggruppato in categorie:

  • Blackbox fuzzing: non richiede alcuna informazione sul sistema in prova (SUT). Esistono due strategie per generare input: generate da una grammatica / modello o mutate da quelle esistenti.
  • Whitebox fuzzing: richiede all le informazioni sul SUT, comprese le API, l'ambiente, ecc. Ha bisogno di sapere quale istruzione è eseguita, in modo che possa sostituire la semantica dell'istruzione con la semantica simbolica .
  • Greybox fuzzing: richiede di conoscere un po ' informazioni sul SUT, ovvero la transizione di blocco di base. Attualmente è il più riuscito, vedi ad esempio questo caso di trofeo .

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

Considera un programma con un input x , con la seguente condizione: if (x > 5 && x < 10) abort();
Supponiamo che x sia un numero intero, cioè il suo dominio è 2 32 . La probabilità di generare in modo casuale un input x che attiva l'errore è 4/2 32 . Questa probabilità è un po 'più alta in una greybox fuzzing intelligente, ma in generale succhiano questo tipo di condizione.

D'altro canto, whitebox fuzzing esegue il programma con un simbolo x = X , e usa un risolutore di vincoli, ad es. Z3 , per risolvere il problema. Z3 può risolvere X > 5 ∧ X < 10 in mili o nano secondo.

Tuttavia, non c'è il pranzo gratis, questo potere viene fornito con un prezzo costoso.

  • Un documento recente mostra che per un solo percorso, vale a dire nessun vincolo risolvendo, un'esecuzione in KLEE è 3000 volte più lenta di quella nativa, mentre angr è 300.000 volte più lento. Poiché è molto lento, non è realistico ottenere una copertura del 100%.
  • Il risolutore di vincoli è utile solo per l'aritmetica lineare. Non esiste un risolutore efficiente per la teoria della stringa, aritmetica in virgola mobile ecc.
  • Non è realistico conoscere tutte le informazioni su API, ambiente ecc.

L'attuale stato dell'arte è fuzzing ibrido , che combina sia greybox che whitebox. L'idea è di usare greybox fuzzer come ricerca globale per campionare rapidamente lo spazio degli stati. Quando si blocca, usa la casella dei pesi massimi come ricerca locale . Questa è la tecnica utilizzata da tutto il team nella Cyber Grand Challenge . L'ibrido fuzzer QSym , in esecuzione su una macchina modesta, ha scoperto alcuni CVE che Google impossibile trovare i fuzzer di greybox in esecuzione sul cloud.

    
risposta data 02.11.2018 - 07:32
fonte
2

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

Proprio come una mazza da baseball, la differenza è nell'obiettivo della persona che la detiene - Barry Bonds lo userà diversamente da un criminale di strada.

Sia Fuzzing che Symbolic Execution stanno alimentando input in un programma per imparare qualcosa. In questo senso, sono la stessa cosa esatta. Puoi usare molti degli stessi strumenti per fare entrambi.

Quando qualcuno lo chiama Fuzzing, si sta concentrando su un'ampia varietà di input sintetici, con l'obiettivo di trovare input che possano violare le cose in un modo che può essere abusato. C'è una maggiore attenzione sugli input "non validi", perché vedere gli input validi gestiti validamente non è interessante per la persona che sta effettuando il Fuzzing.

Quando qualcuno lo chiama Esecuzione simbolica, è probabile che abbia un insieme più piccolo e più coerente di input sintetici. Molti di questi saranno input "validi" e verificheranno il comportamento del programma come previsto. Alcuni di essi saranno input "non validi" e verificheranno che il programma li abbia gestiti senza fallire.

Il fuzzing viene utilizzato per trovare i modi in cui i programmi si interromperanno (sia per trarre vantaggio da, o per risolvere).

L'esecuzione simbolica viene utilizzata per garantire la correttezza di un programma - per misurare come gestisce gli stessi ingressi e per vedere che le prestazioni / stabilità migliorano, non peggio, nel tempo.

    
risposta data 02.11.2018 - 00:30
fonte

Leggi altre domande sui tag