Symbolické provedení - Symbolic execution
v počítačová věda, symbolické provedení (taky symbolické hodnocení nebo symbex) je prostředek k analýze programu k určení, jaké vstupy způsobí provedení každé části programu. Tlumočník se řídí programem a předpokládá symbolické hodnoty pro vstupy, nikoli získávání skutečných vstupů, jak by to bylo při běžném provádění programu. Dosahuje tedy výrazů, pokud jde o tyto symboly pro výrazy a proměnné v programu, a omezení, pokud jde o tyto symboly, pro možné výsledky každé podmíněné větve.
Pole symbolická simulace aplikuje stejný koncept na hardware. Symbolický výpočet aplikuje tento koncept na analýzu matematických výrazů.
Příklad
Zvažte níže uvedený program, který načte hodnotu a selže, pokud je vstup 6.
1 int F() { 2 ... 3 y = číst(); 4 z = y * 2; 5 -li (z == 12) { 6 selhat(); 7 } jiný { 8 printf("OK"); 9 }10 }Během normálního provádění („konkrétní“ provedení) by program načetl konkrétní vstupní hodnotu (např. 5) a přiřadil ji y. Provedení by pak pokračovalo s násobením a podmíněnou větví, které by se vyhodnotilo jako nepravdivé a tisklo by OK.
Během symbolického spuštění program načte symbolickou hodnotu (např. λ) a přiřadí jej y. Program by pak pokračoval s násobením a přiřazením λ * 2 na z. Při dosažení -li prohlášení, vyhodnotilo by to λ * 2 == 12. V tomto bodě programu by λ mohlo mít jakoukoli hodnotu, a symbolické provádění proto může pokračovat podél obou větví „rozvětvením“ dvou cest. Každá cesta dostane přiřazenou kopii stavu programu v instrukci větve a také omezení cesty. V tomto příkladu je omezení cesty λ * 2 == 12 pro pak pobočka a λ * 2! = 12 pro jiný větev. Obě cesty lze symbolicky provést nezávisle. Když cesty končí (např. V důsledku provedení selhat() nebo jednoduše opuštění), symbolické provedení vypočítá konkrétní hodnotu pro λ řešením nahromaděných omezení cesty na každé cestě. Tyto konkrétní hodnoty lze považovat za konkrétní testovací případy, které mohou například pomoci vývojářům reprodukovat chyby. V tomto příkladu řešitel omezení by to určilo za účelem dosažení selhat() prohlášení, λ by se musel rovnat 6.
Omezení
Cesta exploze
Symbolické provádění všech možných cest programů se neomezuje na velké programy. Počet proveditelných cest v programu exponenciálně roste s nárůstem velikosti programu a může být dokonce nekonečný v případě programů s neomezenými smyčkovými iteracemi.[1] Řešení cesta exploze problém obecně používá buď heuristiku pro hledání cesty ke zvýšení pokrytí kódu,[2] zkrátit dobu provádění paralelizací nezávislých cest,[3] nebo sloučením podobných cest.[4]
Účinnost závislá na programu
Symbolické provedení se používá k uvažování o cestě programu po cestě, což je výhoda oproti uvažování o vstupu programu po vstupu, jak to používají jiné testovací paradigmy (např. Dynamická analýza programu ). Pokud však několik vstupů prochází stejnou cestou programem, existuje malá úspora při testování každého ze vstupů samostatně.
Aliasing paměti
Symbolické provedení je těžší, když lze ke stejnému umístění v paměti přistupovat pomocí různých jmen (aliasing ). Aliasing nelze vždy rozpoznat staticky, takže symbolický spouštěcí modul nedokáže rozpoznat, že změna hodnoty jedné proměnné změní i druhou.[5]
Pole
Vzhledem k tomu, že pole je kolekcí mnoha odlišných hodnot, musí symboličtí exekutoři považovat celé pole za jednu hodnotu nebo považovat každý prvek pole za samostatné umístění. Problém se zpracováním každého prvku pole samostatně spočívá v tom, že odkaz jako „A [i]“ lze zadat pouze dynamicky, když má hodnota pro i konkrétní hodnotu.[5]
Interakce prostředí
Programy interagují se svým prostředím prováděním systémových volání, přijímáním signálů atd. Problémy s konzistencí mohou nastat, když se spuštění dostane ke komponentám, které nejsou pod kontrolou symbolického nástroje pro provádění (např. Jádro nebo knihovny). Zvažte následující příklad:
1 int hlavní() 2 { 3 SOUBOR *fp = fopen(„doc.txt“); 4 ... 5 -li (stav) { 6 fputs("nějaká data", fp); 7 } jiný { 8 fputs(„nějaká další data“, fp); 9 }10 ...11 data = fgets(..., fp);12 }Tento program otevře soubor a na základě určitých podmínek do něj zapíše jiný druh dat. To pak později přečte zpět zapsaná data. Teoreticky by symbolická exekuce rozvětvila dvě cesty na řádku 5 a každá cesta odtamtud dále by měla svou vlastní kopii souboru. Příkaz na řádku 11 by proto vrátil data, která jsou konzistentní s hodnotou „podmínky“ na řádku 5. V praxi jsou operace se soubory implementovány jako systémová volání v jádře a jsou mimo kontrolu nástroje pro symbolické provádění. Hlavní přístupy k řešení této výzvy jsou:
Přímé provádění hovorů do prostředí. Výhodou tohoto přístupu je, že se snadno implementuje. Nevýhodou je, že vedlejší účinky takových volání způsobí ztrátu všech stavů spravovaných symbolickým spouštěcím modulem. Ve výše uvedeném příkladu by instrukce na řádku 11 vrátila „nějaká jiná data“ nebo „nějaká jiná data“ v závislosti na postupném řazení stavů.
Modelování prostředí. V tomto případě motorové nástroje, které systém volá, s modelem, který simuluje jejich účinky a který udržuje všechny vedlejší účinky v úložišti jednotlivých stavů. Výhodou je, že při symbolickém provádění programů, které interagují s prostředím, by člověk získal správné výsledky. Nevýhodou je, že je třeba implementovat a udržovat mnoho potenciálně složitých modelů systémových volání. Nástroje jako KLEE,[6] Cloud9 a Vydra[7] zaujměte tento přístup implementací modelů pro operace souborového systému, soketů, IPC atd.
Rozvětvení stavu celého systému. Symbolické spouštěcí nástroje založené na virtuálních strojích řeší problém s prostředím rozvětvením celého stavu virtuálního počítače. Například v S2E[8] každý stav je nezávislý snímek virtuálního počítače, který lze provést samostatně. Tento přístup zmírňuje potřebu psaní a údržby složitých modelů a umožňuje symbolicky provádět prakticky jakýkoli binární program. Má však vyšší režijní náklady na využití paměti (snímky VM mohou být velké).
Nástroje
Starší verze nástrojů
Dějiny
Koncept symbolického provedení byl akademicky představen s popisem: systému Select,[11]systém EFFIGY,[12]systém DISSECT,[13]a Clarkův systém.[14]Vidět bibliografie více technických článků publikovaných o symbolickém provedení.
Viz také
- Abstraktní interpretace
- Symbolická simulace
- Symbolický výpočet
- Concolic testování
- Kontrolní vývojový graf
- Dynamická rekompilace
Reference
- ^ Anand, Saswat; Patrice Godefroid; Nikolai Tillmann (2008). „Poptávkové kompoziční symbolické provedení“. Nástroje a algoritmy pro konstrukci a analýzu systémů. Přednášky z informatiky. 4963. 367–381. doi:10.1007/978-3-540-78800-3_28. ISBN 978-3-540-78799-0.
- ^ Ma, Kin-Keng; Khoo Yit Phang; Jeffrey S. Foster; Michael Hicks (2011). „Řízené symbolické provedení“. Sborník z 18. mezinárodní konference o analýze statistik. str. 95–111. ISBN 9783642237010. Citováno 2013-04-03.
- ^ Staats, Matt; Corina Pasareanu (2010). Msgstr "Paralelní symbolické provedení pro generování strukturálních testů". Sborník 19. mezinárodního sympozia o testování a analýze softwaru. 183–194. doi:10.1145/1831708.1831732. ISBN 9781605588230. S2CID 9898522.
- ^ Kuzněcov, Volodymyr; Kinder, Johannes; Bucur, Stefan; Candea, George (01.01.2012). "Efektivní sloučení státu při symbolickém provedení". Sborník z 33. konference ACM SIGPLAN o návrhu a implementaci programovacího jazyka. New York, NY, USA: ACM. 193–204. CiteSeerX 10.1.1.348.823. doi:10.1145/2254064.2254088. ISBN 978-1-4503-1205-9. S2CID 135107.
- ^ A b DeMillo, Rich; Offutt, Jeff (01.09.1991). "Automatické generování testovacích dat na základě omezení". Transakce IEEE v softwarovém inženýrství. 17 (9): 900–910. doi:10.1109/32.92910.
- ^ Cadar, Cristian; Dunbar, Daniel; Engler, Dawson (01.01.2008). „KLEE: Bez asistence a automatické generování testů s vysokým pokrytím pro programy komplexních systémů“. Sborník příspěvků z 8. konference USENIX o návrhu a implementaci operačních systémů. OSDI'08: 209–224.
- ^ Turpie, Jonathan; Reisner, Elnatan; Foster, Jeffrey; Hicks, Michael. "MultiOtter: Symbolické spuštění s více procesy" (PDF).
- ^ Chipounov, Vitaly; Kuzněcov, Volodymyr; Candea, George (01.02.2012). „Platforma S2E: design, implementace a aplikace“. ACM Trans. Comput. Syst. 30 (1): 2:1–2:49. doi:10.1145/2110356.2110358. ISSN 0734-2071. S2CID 16905399.
- ^ Sharma, Asankhaya (2014). "Využití nedefinovaných chování pro efektivní symbolické provedení". ICSE Companion 2014: Companion Proceedings of the 36.th International Conference on Software Engineering. 727–729. doi:10.1145/2591062.2594450. ISBN 9781450327688. S2CID 10092664.
- ^ Cadar, Cristian; Ganesh, Vijay; Pawlowski, Peter M .; Dill, David L .; Engler, Dawson R. (2008). "EXE: Automatické generování vstupů smrti". ACM Trans. Inf. Syst. Secur. 12: 10:1–10:38. doi:10.1145/1455518.1455522. S2CID 10905673.
- ^ Robert S. Boyer a Bernard Elspas a Karl N. Levitt SELECT - formální systém pro testování a ladění programů symbolickým provedením, Proceedings of the International Conference on Reliable Software, 1975, strana 234-245, Los Angeles, Kalifornie
- ^ James C. King, Symbolické provedení a testování programu, Komunikace ACM, svazek 19, číslo 7, 1976, 385-394
- ^ William E. Howden, Experimenty se symbolickým systémem hodnocení, Proceedings, National Computer Conference, 1976.
- ^ Lori A. Clarke, Systém pro testování programů, ACM 76: Proceedings of the Annual Conference, 1976, strany 488-491, Houston, Texas, USA