Analýza tvaru (programová analýza) - Shape analysis (program analysis)
Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Února 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v programová analýza, tvarová analýza je statická analýza kódu technika, která zjišťuje a ověřuje vlastnosti propojeno, dynamicky přiděleno datové struktury v (obvykle rozkazovací způsob ) počítačové programy. Obvykle se používá v době kompilace k vyhledání softwarových chyb nebo k ověření vlastností správnosti programů na vysoké úrovni. v Jáva programy, lze jej použít k zajištění, že metoda řazení správně seřadí seznam. U programů C může hledat místa, kde není blok paměti správně uvolněn.
Aplikace
Analýza tvaru byla aplikována na řadu problémů:
- Bezpečnost paměti: hledání úniky paměti, dereference visící ukazatele a objevování případů, kdy je blok paměti uvolněn více než jednou.[1][2]
- Hledání chyb mimo pole[Citace je zapotřebí ]
- Probíhá kontrola vlastnosti typu stavu (například zajištění, že soubor je
otevřeno()
než to budečíst()
)[Citace je zapotřebí ] - Zajištění, aby metoda zvrátila a spojový seznam nezavádí cykly do seznamu[2]
- Ověření, že metoda řazení vrátí výsledek, který je v seřazeném pořadí[Citace je zapotřebí ]
Příklad
Analýza tvaru je formou analýza ukazatele, i když je přesnější než obvyklá analýza ukazatele. Analýza ukazatele se pokouší určit sadu objektů, na které může ukazatel ukazovat (nazývá se sada ukazatelů ukazatele). Bohužel jsou tyto analýzy nutně přibližné (protože dokonale přesná statická analýza by mohla vyřešit zastavení problému ). Analýza tvaru může určit menší (přesnější) sady bodů.
Zvažte následující jednoduchý program C ++.
Položka *položky[10];pro (int i = 0; i < 10; ++i) { položky[i] = Nový Položka(...); // řádek [1]}process_items(položky); // řádek [2]pro (int i = 0; i < 10; ++i) { vymazat položky[i]; // řádek [3]}
Tento program vytváří řadu objektů, zpracovává je libovolným způsobem a poté je odstraní. Za předpokladu, že process_items
funkce neobsahuje chyby, je jasné, že program je bezpečný: nikdy neodkazuje na uvolněnou paměť a odstraní všechny objekty, které vytvořil.
Bohužel většina analýz ukazatelů má potíže s přesnou analýzou tohoto programu. Aby bylo možné určit sady bodů, musí být schopna analýza ukazatele název objekty programu. Programy mohou obecně přidělit neomezený počet objektů; ale aby to bylo možné ukončit, může analýza ukazatele použít pouze konečnou sadu jmen. Typickým přiblížením je dát všem objektům přiděleným na daném řádku programu stejný název. Ve výše uvedeném příkladu by všechny objekty konstruované na řádku [1] měly stejný název. Proto, když vymazat
příkaz je analyzován poprvé, analýza určí, že jeden z objektů s názvem [1] je mazán. Podruhé, kdy je příkaz analyzován (protože je ve smyčce), analýza varuje před možnou chybou: protože není schopen rozlišit objekty v poli, může se stát, že druhý vymazat
mazá stejný objekt jako první vymazat
. Toto varování je falešné a cílem analýzy tvaru je vyhnout se takovým varováním.
Shrnutí a materializace
Analýza tvaru překonává problémy analýzy ukazatelů pomocí flexibilnějšího systému pojmenování objektů. Spíše než dávat objektu stejný název v celém programu, mohou objekty měnit názvy v závislosti na akcích programu. Někdy může být několik odlišných objektů s různými názvy shrnuto, nebo sloučeny, aby měly stejný název. Pak, když má program použít souhrnný objekt, může být se zhmotnil- to znamená, že souhrnný objekt je rozdělen na dva objekty se zřetelnými názvy, jeden představuje jeden objekt a druhý představuje zbývající souhrnné objekty. Základní heuristikou tvarové analýzy je, že objekty, které program používá, jsou reprezentovány pomocí jedinečných materializovaných objektů, zatímco objekty, které se nepoužívají, jsou shrnuty.
Pole objektů ve výše uvedeném příkladu je shrnuto odděleně na řádcích [1], [2] a [3]. Na řádku [1] bylo pole zkonstruováno pouze částečně. Prvky pole 0..i-1 obsahují vytvořené objekty. Prvek pole i se má zkonstruovat a následující prvky jsou neinicializované. Analýza tvaru může tuto situaci aproximovat pomocí souhrnu pro první sadu prvků, materializovaného umístění paměti pro prvek i a souhrnu pro zbývající neinicializovaná umístění, a to následovně:
0 .. i-1 | i | i + 1 .. 9 |
ukazatel na zkonstruovaný objekt (souhrn) | neinicializováno | neinicializované (shrnutí) |
Po ukončení smyčky na řádku [2] není třeba nic zhmotňovat. Analýza tvaru v tomto okamžiku určí, že byly inicializovány všechny prvky pole:
0 .. 9 |
ukazatel na zkonstruovaný objekt (souhrn) |
Na řádku [3] však prvek pole i
se znovu používá. Proto analýza rozdělí pole na tři segmenty jako v řádku [1]. Tentokrát však první segment dříve i
byl odstraněn a zbývající prvky jsou stále platné (za předpokladu, že vymazat
prohlášení dosud neprovedeno).
0 .. i-1 | i | i + 1 .. 9 |
zdarma (shrnutí) | ukazatel na zkonstruovaný objekt | ukazatel na zkonstruovaný objekt (souhrn) |
Všimněte si, že v tomto případě analýza rozpozná ukazatel na indexu i
ještě nebyl smazán. Varuje tedy před dvojitým odstraněním.
Viz také
Reference
- ^ Rinetzky, Noam; Sagiv, Mooly (2001). „Interprocedurální analýza tvaru pro rekurzivní programy“ (PDF). Konstrukce kompilátoru. Přednášky z informatiky. 2027. str.133–149. doi:10.1007/3-540-45306-7_10. ISBN 978-3-540-41861-0.
- ^ A b Berdine, Josh; Calcagno, Cristiano; Cook, Byron; Distefano, Dino; o'Hearn, Peter W .; Wies, Thomas; Yang, Hongseok (2007). "Analýza tvaru pro kompozitní datové struktury" (PDF). Ověření pomocí počítače. Přednášky z informatiky. 4590. 178–192. doi:10.1007/978-3-540-73368-3_22. ISBN 978-3-540-73367-6.
Bibliografie
- Neil D. Jones; Steven S. Muchnick (1982). "Flexibilní přístup k interprocedurální analýze toku dat a programům s rekurzivními datovými strukturami". POPL '82 Proceedings of the 9. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM: 66–74. doi:10.1145/582153.582161. ISBN 0897910656.
- Mooly Sagiv; Thomas Reps; Reinhard Wilhelm (Květen 2002). „Parametrická analýza tvaru pomocí 3hodnotové logiky“ (PDF). Transakce ACM v programovacích jazycích a systémech. ACM. 24 (3): 217–298. CiteSeerX 10.1.1.147.2132. doi:10.1145/292540.292552.
- Wilhelm, Reinhard; Sagiv, Mooly; Reps, Thomas (2007). "Kapitola 12: Analýza tvarů a aplikace". In Srikant, Y. N .; Shankar, Priti (eds.). Příručka kompilátoru: Optimalizace a generování strojového kódu, druhé vydání. CRC Press. s. 12–1–12–44. ISBN 978-1-4200-4382-2.