Quali sono le differenze tra esecuzione simbolica e risolutori satelliti?

Question

La mia comprensione è che l'esecuzione simbolica si occupa solo di percorsi specifici e dei motivi cattivi, mentre SAT SOLVERS o SOD SOLLUS o soddisfabilità le teorie del modulo in generale, forniscono un'analisi molto più robusta del programma.

Qualcuno potrebbe convalidare la dichiarazione sopra e (brevemente) spiegare le differenze tra queste due metodologie di verifica formale?

Answer 1

TL; DR: Differiscono nel loro ingresso e produzione di base. SAT e SMT SOLVERS non sanno quali programmi sono; Sono strumenti che rispondono sì o nessuna domanda sulle formule matematiche. L'esecuzione simbolica, d'altra parte, è un metodo per analizzare i programmi. L'esecuzione simbolica di solito si basa su solutori SAT e SMT, ma non il contrario.

---

.

SAT e SMT SOLVERS Non hanno nulla a che fare con i programmi. Invece, un solver SAT o SMT prende come input una "formula" descritta matematicamente descritta, e risposte, approssimativamente, se è vero o falso. (Spesso è consentita una terza opzione, sconosciuto , per i casi in cui il risolutore non è in grado di capire una risposta.)

Ad esempio, un possibile ingresso a un risolutore satellitare è (a and not b) or (not a and c). Cioè, è una formula matematica, dove a, b e c qui sono costanti booleani (0 o 1). Il risolutore satellitare dovrebbe decidere se è possibile che la formula sia vera, scegliendo valori di a, b e c. I solver SMT sono simili, ma a, b, e c verranno sostituiti da formule più complesse utilizzando numeri interi, stringhe, funzioni, ecc., Ad esempio x + 3 = y^2.

---

.

Esecuzione simbolica è un modo elegante di eseguire un programma, ma non come il programma fosse destinato a essere eseguito. Invece, il programma è eseguito utilizzando i cosiddetti valori "simbolici", che sono un tipo di segnaposto. Per un esempio di ciò che significa, supponiamo di avere una funzione come f(x) = if x > 0 then 1 else 0. Ora, normalmente, eseguirei il programma inserendo, diciamo, generanodicetagcode e ottenere 3, poiché f(3) = 1 è maggiore di 3. Con l'esecuzione simbolica, eseguo il programma immettendo una variabile segnaposto, 0 e valuto il programma per ottenere due casi: input o input > 0 and answer = 1. Questo può sembrare inutile, ma finisce per essere un potente modo di analizzare i programmi.

---

.

La connessione tra i due è che l'esecuzione simbolica spesso si basa su solvi SMT durante l'esecuzione, per capire se un determinato percorso è effettivamente possibile, o se deve essere scartato. Ad esempio, è possibile utilizzare un solver SMT per determinare se è possibile input <= 0 and answer = 0 (la risposta è sì, ad esempio se input <= 0 and answer = 0). In questo modo, SMT è un po 'la "forza trainante" dietro ciò che rende l'esecuzione simbolica fattibile.