}w !"#$%&'()+,-./012345
Masarykova univerzita Fakulta informatiky
Detekce programovacích chyb v C/C++ programech pod OS GNU/Linux
bakalářská práce
Lubomír Sedlář
Brno, 2012
Prohlášení Prohlašuji, že tato bakalářská práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
Lubomír Sedlář
Vedoucí práce: Mgr. Marek Grác ii
Poděkování Chtěl bych poděkovat Ondřeji Vašíkovi za cenné rady při tvorbě této práce a za zpřístupnění výsledků analýz nástrojem Coverity.
iii
Shrnutí Cílem této práce je prozkoumat dostupné svobodné nástroje pro statickou analýzu zdrojových kódu v C a C++ dostupné v operačním systému GNU/Linux a porovnat jejich výstupy nad aplikacemi z různých oblastí. Nalezené chyby budou klasifikovány a na jejich základě vytvořeno srovnání dostupných nástrojů.
iv
Klíčová slova statická analýza, analýza toku kódu, časté chyby, GNU/Linux, C, C++, Clang, Cppcheck, Coverity, OpenSSL, Sudo, Epiphany
v
Obsah 1 2
3
4
5
Úvod . . . . . . . . . . . . . . . . . . . . . . . Statická analýza . . . . . . . . . . . . . . . . 2.1 Metody . . . . . . . . . . . . . . . . . . . 2.1.1 Hledání vzorů . . . . . . . . . . . . 2.1.2 Analýza toku kódu . . . . . . . . . 2.2 Zpřesnění analýzy . . . . . . . . . . . . . 2.3 Časté chyby . . . . . . . . . . . . . . . . . 2.3.1 Použití neinicializované proměnné 2.3.2 Dereference ukazatele NULL . . . 2.3.3 Únik paměti . . . . . . . . . . . . 2.3.4 Únik deskriptorů . . . . . . . . . . 2.3.5 Použití paměti po uvolnění . . . . 2.3.6 Mrtvý kód . . . . . . . . . . . . . 2.3.7 Race condition . . . . . . . . . . . 2.3.8 Chyby zámků . . . . . . . . . . . . 2.3.9 Přetečení bufferu . . . . . . . . . . Dostupné nástroje . . . . . . . . . . . . . . . 3.1 GCC . . . . . . . . . . . . . . . . . . . . . 3.2 Sparse . . . . . . . . . . . . . . . . . . . . 3.3 Clang . . . . . . . . . . . . . . . . . . . . 3.4 Splint . . . . . . . . . . . . . . . . . . . . 3.5 Cppcheck . . . . . . . . . . . . . . . . . . 3.6 Coverity . . . . . . . . . . . . . . . . . . . Výsledky analýzy . . . . . . . . . . . . . . . 4.1 OpenSSL . . . . . . . . . . . . . . . . . . 4.1.1 Analýza Clangem . . . . . . . . . . 4.1.2 Analýza Cppcheckem . . . . . . . 4.1.3 Analýza pomocí Coverity . . . . . 4.2 Sudo . . . . . . . . . . . . . . . . . . . . . 4.2.1 Analýza Clangem . . . . . . . . . . 4.2.2 Analýza Cppcheckem . . . . . . . 4.2.3 Analýza pomocí Coverity . . . . . 4.3 Epiphany . . . . . . . . . . . . . . . . . . 4.3.1 Analýza Clangem . . . . . . . . . . 4.3.2 Analýza Cppcheckem . . . . . . . Srovnání nástrojů . . . . . . . . . . . . . . . 5.1 Přesnost . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 5 5 5 6 7 8 8 9 9 9 9 10 10 11 11 12 12 12 13 14 15 15 17 17 17 17 20 20 22 22 23 24 25 25 27 27 1
5.2 Typy chyb . . . . . . . . . . . . . . . . . . . 5.3 Rychlost analýzy . . . . . . . . . . . . . . . 5.4 Další možnosti analyzátorů . . . . . . . . . 6 Závěr . . . . . . . . . . . . . . . . . . . . . . . . A Příklady kódu . . . . . . . . . . . . . . . . . . A.1 Nenahlášené varování v OpenSSL . . . . . . A.2 Idempotentní operace v Sudo . . . . . . . . A.3 Index -1 v Sudo . . . . . . . . . . . . . . . . A.4 Přetečení bufferu detekovatelné při překladu A.5 Cppcheck nedetekuje únik paměti . . . . . . A.6 Příklad pro analýzu toku kódu . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
27 28 30 32 36 36 36 36 36 37 37
2
1 Úvod Už první počítačové programy obsahovaly chyby. Z tohoto důvodu postupně vznikly různé metody, jak chyby detekovat a následně opravit. Nejspolehlivější metodou jsou formální důkazy korektnosti. Ty jsou ale pro většinu programů a hlavně programátorů těžko realizovatelné, protože ne každý programátor je schopen dokázat korektnost svého kódu a i kdyby to dokázal, pro mnoho aplikací se takové důkazy nevyplatí ani finančně, ani časově. Další překážkou na cestě k formální verifikaci je rozsáhlost současných aplikací. Jestliže má například jádro systému Linux téměř 10 milionů řádků kódu1 , zřejmě není v silách jediného člověka dokázat korektnost každého z nich. Je tedy třeba použít automatizovanou, méně formální metodu pro ověřování, zda program funguje správně. Existují zde dva základní přístupy: statická analýza založená na zkoumání nezpracovaných zdrojových kódů a dynamické testování, kdy se ověřuje korektní chování ať už celého programu nebo jen jeho části. V dnešní době se velmi využívá takzvaného jednotkového testování (unit testing), kdy se jednotlivé funkce, třídy a moduly testují samostatně pomocí automatizovaných testů. Pro dosažení nejlepších výsledků je ideální, aby test i testovaný kód psal jiný programátor [25]. Jednotkové testy mají ale zásadní nevýhodu v tom, že neotestují kód, který se během testování nespustí, a i ten, který testují, je spouštěn jenom s předem určenými vstupy. Oproti tomu statická analýza nepotřebuje testovaný kód spouštět. Důsledkem této výhody je například to, že je možné analyzovat i zdroje např. ovladače exotického hardwaru, který fyzicky nevlastníme, a že analýza není závislá na výběru testovacích dat. Postupem času vzniklo velké množství aplikací, které provádějí statickou analýzu. Tyto nástroje se liší použitým rozhraním, vhodností pro různé oblasti vývoje i požadavky na závislosti nutné pro spuštění [3]. Některé nástroje (Splint, Cppcheck) se spouští jako samostatné procesy, kterým se předají soubory s kódem k testování, jiné (Clang, Sparse) obalují kompilátor a analýzu provádějí zároveň s překladem. Velkým problémem nástrojů pro statickou analýzu je hlášení chyb i tam, kde nejsou (tzv. false positives). Tomu se dá zabránit například anotacemi v kódu. Problémem anotací je, že výrazně znepřehledňují kód a každý nástroj používá jiné značení. Obvykle se tedy false positives ignorují a při každé další analýze je analyzátor nahlásí znovu. 1.
http://www.ohloh.net/p/linux
3
1. Úvod Cílem této práce je prozkoumat dostupné nástroje pro operační systém GNU/Linux a jejich vhodnost pro aplikace z různých oblastí. Vybrané nástroje byly testovány na zdrojových kódech vybraných svobodných aplikací. Prvním analyzovaným projektem je knihovna OpenSSL2 . Tato knihovna poskytuje implementaci kryptografických algoritmů a je používána v mnoha aplikacích, převážně serverech jako například Apache pro web, QMail a Postfix pro e-mail nebo OpenSSH pro vzdálenou správu počítačů. Knihovna je napsána v jazyce C. Dalším programem je utilita Sudo, která umožňuje uživatelům spouštět příkazy s právy superuživatele. Pomocí konfiguračního souboru lze nastavit, který uživatel může spouštět jaké příkazy, případně jestli k tomu potřebuje zadávat své heslo. Tento program je napsán převážně v jazyce C. Prvním zkoumaným programem je Epiphany – webový prohlížeč projektu GNOME3 . Tento program je napsaný v jazyku C s využitím knihovny GTK+ a GObject. Využívá tedy objektově orientovaného návrhu. Ukázalo se, že ve výsledcích různých analyzátorů nejsou zásadní rozdíly. Jednotlivé nástroje se liší škálou detekovaných chyb a jejich počtem, žádný ale nevede k výrazně lepší analýze než jiný.
2. 3.
http://www.openssl.org http://projects.gnome.org/epiphany/
4
2 Statická analýza Hlavní myšlenkou statické analýzy je kontrola programu, aniž by byl spuštěn. Existuje mnoho metod, které jsou pro statickou analýzu použitelné. Jednotlivé analyzátory se také liší hloubkou, do jaké program analyzují, od zkoumání jednotlivých příkazů po analýzu toku dat celým programem. Formální metody, které např. kontrolují shodu chování programu se specifikací produktu, nejsou ve světě svobodného softwaru příliš použitelné, neboť vytvoření modelu je velmi obtížné a jeho následné udržování ve shodě s reálným kódem je drahé [10]. Obvyklejší je proto využívání nástrojů, které obětují část formality za snadnou použitelnost a výkonnost, která umožní analýzu spouštět opakovaně a dostatečně rychle. Analyzátory se typicky nesnaží o úplnost. Jejich cílem není důkaz, že zdrojové kódy chyby neobsahují, ale spíše se pokouší detekovat takové problémy,
2.1
Metody
2.1.1 Hledání vzorů Většina zdrojových kódů musí dodržovat určitá pravidla. Příkladem takového pravidla je práce se zámky: před přístupem ke sdílenému zdroji je třeba ho zamknout a po dokončení práce zase odemknout. V jádře systému se systémová volání musí řídit pravidlem ověřovat validitu každého ukazatele z uživatelského prostoru. Tato pravidla mají řadu společných vlastností. Jsou poměrně jednoduše formulovaná, přestože jejich dodržování nemusí být vždy stejně jednoduché. Další příklady jasných pravidel formulovaných přirozeným jazykem jsou „Po zakázání přerušení je nutné zase přerušení povolit“, „Nepoužívat paměť, která byla uvolněna“ nebo „Pokud jsou zakázána přerušení, nesmí se používat funkce, které mohou spát“. Obvykle se tato pravidla dají vyjádřit jako posloupnost akcí, která musí nebo naopak nesmí nastat. Tyto sekvence se ve zdrojovém kódu často objevují jako posloupnosti příkazů a volání funkcí [10]. Pro každou takovou posloupnost je možné sestrojit konečný automat. Tento automat projde zdrojový kód. Příkazy, které vystupují v pravidle, mění stav automatu. Pokud se automat dostane do určitého stavu, případně na konci algoritmu zůstane v nějakém konkrétním stavu, je z této informace možné odvodit, že program dané pravidlo nesplňuje. 5
2. Statická analýza Je třeba mít na paměti, že tato metoda není naprosto spolehlivá. Nemusí vždy najít všechny problémy a pokud už nějaký najde, není to záruka, že je nalezený problém reálný. Problémy, které je možné touto metodou nalézt, jsou například: ∙
špatná práce se zámky (viz 2.3.8)
∙
assert s vedlejšími efekty
∙
nekontrolování přístupových práv před změnou struktury v jádře
2.1.2 Analýza toku kódu Analýza toku kódu (code-flow analysis, někdy i data-flow analysis) se snaží vyhodnocovat možné průchody zdrojovým kódem. Není ale možné projít úplně všechny možné cesty, protože jejich počet je exponenciálně závislý na délce zdrojového kódu. Sekvence 𝑛 podmínek může proběhnout 2𝑛 různými cestami. Počet různých průchodů kódem ale není jediný problém. Další komplikací je množství stavů, do kterých se může program během výpočtu dostat. Jednoduše není možné vyzkoušet všechny průchody kódem pro všechny možné vstupní hodnoty. Kdyby na vstupu bylo jedno celé číslo, bylo by třeba ověřit přes čtyři miliardy1 různých počátečních stavů. To je zjevně nerealizovatelné. Jednou z možností, jak omezit stavový prostor, je omezení stavů proměnných na méně hodnot. Např. pro ukazatele není nutné znát přesnou adresu, stačí pouze vědět, jestli daný ukazatel má hodnotu NULL nebo ne. Podobně pro proměnnou, která vystupuje v podmínce, stačí znát pouze dvě možnosti: buď je podmínka splněná, nebo ne. Aby bylo možné analyzovat jednotlivé cesty kódem, je třeba jej reprezentovat jako graf. Na obrázku 2.1 je jednoduchá reprezentace grafu kódu z příkladu A.6. Tento graf zachycuje přímo vnitřní reprezentaci kódu v nástroji Sparse. Každý očíslovaný2 ovál odpovídá posloupnosti příkazů programu. Jiné nástroje mohou mít samostatné uzly pro každý příkaz objevující se v kódu. Tento graf je možné projít pomocí klasického prohledávání do hloubky. Ověřovanou vlastnost, jako třeba dereferenci nulového ukazatele, je možné vyjádřit jako konečný automat, který pro každý ukazatel sleduje, jestli obsahuje adresu. Každým přiřazením hodnoty do daného ukazatele se změní 1. 2.
předpokládejme 32bitový typ int číslo samotné značí číslo řádku, na kterém začíná daný blok
6
2. Statická analýza cfa/main.c
main() 12 14 cfa/main.c
get_data() 15
5 15
12
7
printf
8
malloc 8
5
strcpy
Obrázek 2.1: Graf toku kódu A.6 stav automatu [15]. Pokud dojde k dereferenci ukazatele, jehož automat je právě ve stavu odpovídajícím hodnotě NULL, byl nalezen potenciální problém. Důležité pozorování je, že procházení grafu je možné výrazně optimalizovat zapamatováním si stavů automatů v každém uzlu grafu. Přestože do mnoha uzlů grafu se dá dostat více cestami, pokud si odpovídají stavy automatů, není nutné daný uzel kontrolovat vícekrát. Pro analýzu podstatné části stavu výpočtu jsou už zachyceny v konečném automatu.
2.2
Zpřesnění analýzy
Jednou z možností, jak zlepšit přesnost statického analyzátoru je jeho kombinace s nástrojem pro formální verifikaci. Statický analyzátor umožní omezit 7
2. Statická analýza množství možných cest v kódu a tím omezí stavovou explozi verifikátoru [2]. Tímto přístupem, kdy analyzátoru navíc programátor poskytne model, podle kterého se daná funkce má chovat, je možné zvýšit přesnost analyzátoru. Jde o iterativní proces, kdy statický analyzátor předává informace o omezení stavového prostoru model checkeru, který s těmito údaji může provádět přesnější kontrolu stavů. Vlastnosti prozkoumaných stavů (například informace o aliasech ukazatelů) zase předává zpět statickému analyzátoru, který tuto informaci může využít k ještě přesnějšímu prořezání možných cest a dalšímu zefektivnění kontroly modelu [2].
2.3
Časté chyby
Pro snažší identifikaci programovacích defektů je praktické mít seznam s jednoznačnými identifikátory. Podobně jako pro bezpečnostní problémy existuje výčet Common Vulnerabilities and Exposures (CVE3 ), vznikl i seznam Common Weakness Enumeration (CWE4 ) spravovaný Mitre Corporation. Tento seznam obsahuje jak možné problémy v implementaci počítačových programů, tak i jejich návrhu a architektuře. Každému defektu je věnována stránka s popisem problému a určením, ve které části vzniku softwaru se chyba objevuje. Dále následuje výčet možných důsledků, příklady chybných programů s vysvětlením, co a proč je v nich špatně, a návrhy, jak tomuto problému předcházet, případně jak ho odhalit. Všechny stránky na webu CWE jsou řazeny do stromové hierarchie, takže je možné se snadno z popisu jednoho defektu dostat k podobným chybám, případně obecnému popisu skupiny chyb. Samotný web by mohl v budoucnu sloužit nejen jako databáze znalostí o programovacích chybách. Jeho potenciál je větší. Pro usnadnění práce s nástroji pro statickou analýzu by bylo velmi vhodné standardizovat sadu anotací, pomocí kterých by bylo možné vyznačit ve zdrojovém kódu problematické úseky a tím dát najevo, že daný řádek kódu nebo funkce opravdu má vypadat tak, jak vypadá, a nejde o chybu. V následujících odstavcích jsou představeny některé z možných problémů. 2.3.1 Použití neinicializované proměnné – CWE-457 V jazyku C i C++ se nově deklarovaným proměnným automaticky nepřiřazuje žádná výchozí hodnota. Obsahují tedy to, co bylo v paměti na jejich adrese 3. 4.
http://cve.mitre.org/ http://cwe.mitre.org/
8
2. Statická analýza uloženo dřív. Tato data jsou jen velmi vzácně k něčemu užitečná a je tedy praktické co nejdříve proměnným přiřadit nějakou jasně definovanou hodnotu. Neinicializované proměnné mohou vést k pádu programu. Pokud by se potenciálnímu útočníkovi podařilo zajistit, aby na adrese neinicializované proměnné byla jím připravená data, mohl by ovlivnit běh programu. 2.3.2 Dereference ukazatele NULL – CWE-476 Dereference ukazatele NULL obvykle vede k pádu programu se signálem SIGSEGV. K této chybě může dojít jak souběhem vláken se špatnou synchronizací, tak i prostým opomenutím programátora. Obvykle se chyba projevuje v částech kódu, které se nepoužívají příliš často a tedy mohou snadněji projít testováním neodhaleny. 2.3.3 Únik paměti – CWE-401 Pokud program korektně nesleduje a neuvolňuje alokovanou paměť, může docházet k postupnému zvyšování spotřeby paměti. To vede k nižší spolehlivosti programu. Pokud by teoretický útočník dokázal program dovést k úniku paměti, mohl by tuto chybu zneužít k útoku typu DoS5 , kdy by mohl využít nepředvídatelného chování v případě vyčerpání paměti. 2.3.4 Únik deskriptorů – CWE-775 Podobný případ neuvolňování paměti je i situace, kdy program otevře např. soubor, ale po skončení práce s ním ho už nezavře. Přestože po skončení programu operační systém všechny otevřené soubory zavře, v případě větších a déle běžících systémů může snadno dojít k vyčerpání všech dostupných deskriptorů a následnému selhání při otevírání dalšího souboru. Tento problém se neprojevuje pouze při nevhodné práci se soubory, ale ve všech případech, kdy se interně používá file descriptor. Jde tedy i o adresáře, odkazy, roury, sockety a znaková i bloková zařízení. 2.3.5 Použití paměti po uvolnění – CWE-416 Použití paměti, která byla uvolněna, může vést k pádu programu, použití neočekávané hodnoty nebo i spuštění libovolného kódu. Při přístupu k uvolněné paměti může dojít k poškození dat, pokud už byla stejná paměť alokována jinde. 5.
Denial of Service
9
2. Statická analýza Tato chyba je obvykle způsobena jednou ze dvou podmínek: ∙
ošetřování chyby a podobné výjimečné stavy
∙
nejistota ohledně toho, která část programu je zodpovědná za uvolňování paměti.
2.3.6 Mrtvý kód – CWE-561 Mrtvý kód (dead code) je takový kód, který se nikdy nevykoná. Přestože se technicky nejedná o chybu a na běh programu nemá vliv, může takový kód komplikovat údržbu programu a tím brzdit opravu jiných, už závažnějších chyb. Důvodem, proč se některá část kódu nikdy neprovede, může být například testování podmínky, která je vždy pravdivá (resp. nepravdivá). Nepoužitá proměnná je podmnožinou mrtvého kódu. Jde o přiřazení do proměnné, která se ale dále nikde nepoužije. To je často nevinné, ale někdy může indikovat použití špatné proměnné. V obou případech vede k nižší čitelnosti kódu. Příklad situace, kdy mrtvé přiřazení indikuje problém, je v příloze A.1. Jedná se o kód knihovny OpenSSL, kde se do proměnné al ukládá kód chyby, ke které došlo, a následně se přejde na návěští f_err, respektive err, pokud není k dispozici podrobnější informace o chybě. Nečtení hodnoty z proměnné al indikuje překlep a přechod na nesprávné návěští. Tím dojde k situaci, že se nezaloguje podrobnější informace o chybě. 2.3.7 Race condition – CWE-362 Race condition6 je situace, kdy výsledek nějaké operace je závislý na pořadí a načasování jednotlivých operací vícevláknových programů. Souběh obvykle bývá způsoben chybným přístupem ke sdílenému prostředku, např. modifikací datové struktury z více vláken zároveň. Souběh může mít mnoho důsledků od pádu programu přes úniky paměti (které mohou vést až k vyčerpání všech zdrojů) až k problémům s únikem citlivých dat. Vzhledem k povaze problému je velice obtížné detekovat souběh testováním. Defekt se může projevovat jenom na určitém typu procesoru, při určité zátěži systému nebo dalších těžko opakovatelných podmínkách. 6.
česky souběh
10
2. Statická analýza 2.3.8 Chyby zámků – CWE-667 Při používání sdíleného zdroje více vlákny programu je obvykle třeba zajistit, aby zdroj mohl být v jednom okamžiku používán pouze jedním vláknem. K tomu je mimo jiné možné používat zámky, mutexy a semafory. Všechny tyto prostředky nabízejí podobné možnosti – lze je zamknout (a tím získat práva k práci s prostředkem) a následně je nutné je odemknout. Existuje mnoho různých konkrétních chyb při práci se zámky: ∙
Zapomenutí nutnosti získat zámek (CWE-414)
∙
Neošetření selhání synchronizační funkce (CWE-413)
∙
Práce s více zámky takovým způsobem, že se dvě nebo více vláken navzájem zablokují – tzv. deadlock (CWE-833)
∙
Vícenásobné zamknutí (CWE-764) způsobuje v některých případech snížení výkonu aplikace, v nejhorším případě může vést až k útoku DoS.
∙
Vícenásobné odemknutí (CWE-765) uvede program do nedefinovaného stavu. Důsledky jsou podobné jako u vícenásobného zamknutí.
Při předcházení posledním dvěma případům je důležité dávat pozor, aby každá cesta v kódu, která zamyká nějaký zámek, také daný zámek odemkla. Typicky ošetření chybových stavů může vést k zapomenutí na nutnost odemknutí zámku. 2.3.9 Přetečení bufferu – CWE-120 K přetečení bufferu dochází tehdy, když program zkopíruje data ze vstupního bufferu do výstupního, aniž by zkontroloval, že velikost vstupního bufferu není větší než velikost výstupního bufferu. Typickým příkladem přetečení je situace, kdy program kopíruje data bez omezení velikosti. Přetečení bufferu může vést k pádu programu. Pokud je ale buffer alokovaný na zásobníku, může dojít i k přepsání další proměnné, která je v paměti uložena za koncem bufferu. V jazyku C existují standardní knihovní funkce, jejichž použití může způsobit přetečení bufferu. Typickým příkladem je funkce gets nebo volání scanf("%s", buffer) bez omezení maximální délky. Dokumentace [20] přímo doporučuje gets nepoužívat.
11
3 Dostupné nástroje Pro operační systém GNU/Linux existuje řada různých nástrojů pro statickou analýzu. Tyto nástroje se liší jak rozhraním, tak i metodami, které využívají. V dalších odstavcích jsou popsány nástroje Sparse, Clang, Cppcheck, Splint a možnosti kompilátoru GCC. Tyto analyzátory jsou dostupné pod svobodnými licencemi. Text také představuje komerční nástroj Coverity.
3.1
GCC
Kompilátor GCC během kompilace dokáže provádět základní statickou analýzu jako třeba detekci nepoužité proměnné nebo funkce nebo neinicializované proměnné. Základní sada těchto varování se dá zapnout přepínačem -Wall [14]. Jde o varování, která je snadné opravit. Přepínač -Wextra zapne další varování. Od roku 2004 překladač GCC podporuje mimo jiné i další kontrolu statických bufferů na zásobníku [16]. Pokud je při překladu definováno makro _FORTIFY_SOURCE s hodnotou 1 nebo 21 , GCC se pokusí detekovat možné přetečení zásobníku (viz. A.4) a pokud je to možné, upozorní na možný problém varováním už v době překladu. Pokud se nepodaří přetečení detekovat během kompilace, přeložený program místo klasických funkcí pro práci s buffery bude používat jejich varianty, které znají velikost daného bufferu a při přetečení ukončí program se signálem SIGABRT. Přestože z uživatelského pohledu toto není zrovna příjemné chování, z hlediska bezpečnosti je to spolehlivé řešení. Protože kontrola přetečení se odehrává především při běhu aplikace, nelze ji zařadit mezi nástroje pro statickou analýzu. Další podobné běhové kontroly lze zapnout pomocí přepínače -fstack-protector, popř. -fstack-protector-all [14].
3.2
Sparse
Sparse (Semantic Parser) je nástroj původně vyvinutý pro hledání chyb v Linuxu. Od ostatních nástrojů se liší především tím, že je navržen tak, aby umožňoval hledat nedostatky typické pro vývoj jádra systému. Sparse je knihovna, která umí parsovat zdrojový kód v C a zpřístupnit načtený strom dalším funkcím. Statický analyzátor využívající Sparse pracuje 1.
zároveň je nutné zapnout alespoň nějaké optimalizace přepínačem -O
12
3. Dostupné nástroje tak, že nejprve převede načtený strom do lineárního bytekódu, ten vyhodnotí a případně vypíše varování. [24] Nad touto knihovnou je možné vytvořit různé nástroje, a jedním z nich je statický analyzátor. Pro zpřesnění analýzy Sparse využívá anotace ve formě atributů u funkcí a především proměnných. K sadě atributů definovaných překladačem přidává několik vlastních, např. address-space pro označení ukazatelů. Pokud jsou ukazatele takto označeny (a při analýze byl zadán přepínač -Waddress-space), Sparse bude zacházet s ukazateli z různých adresovacích prostorů, jako by měly nekompatibilní typ. Pro spouštění Sparse existuje pomůcka cgcc, což je perlový skript, který umožňuje spouštět analýzu zároveň s překladem. Všechny přepínače, kterým Sparse nerozumí, jsou předány kompilátoru. Tím se analýza většiny projektů zjednoduší na zadání příkazu make CC=cgcc.
3.3
Clang
Clang je především kompilátor založený na LLVM2 . Umožňuje kompilovat programy v jazycích C, C++, Objective–C a Objective–C++. Pro C a Objective–C také nabízí statický analyzátor. Tento analyzátor je možné spouštět jako samostatný nástroj z příkazové řádky nebo v rámci rozhraní XCode. Samostatný nástroj je určen ke spouštění zároveň s překladem [4]. Clang umožňuje analýzu pomocí dvou základních metod: flow-sensitive analysis a path-sensitive analysis [18]. Flow-sensitive analýza zkoumá změny hodnot proměnných. Tato analýza probíhá v lineárním čase a je také využita při optimalizacích a pro varování kompilátoru. Path-sensitive analýza na druhou stranu zvažuje veškeré jednotlivé možnosti toků kódu a každé podmínky nebo cyklu. To ovšem v nejhorším případě vede k exponenciální složitosti analýzy. Velkou výhodou Clangu oproti ostatním zmiňovaným nástrojům je podrobný výstup s detaily nalezeného problému. Kromě klasického textového výstupu navíc nabízí detailní postup, kterými podmínkami a jak musí výpočet projít, aby došel k nalezenému problematickému stavu. Tyto výstupy jsou generovány jako sada stránek v HTML. Obsahují seznam všech nalezených defektů, z nichž každému je věnována jedna stránka s původním zdrojovým kódem a zvýrazněnými kroky. V této práci byl použit Clang verze 3.0-6 založený na LLVM verze 3.0. 2.
http://llvm.org/
13
3. Dostupné nástroje
Obrázek 3.1: Příklad detailního výstupu Clangu
3.4
Splint
Splint (dříve LCLint) je odlehčený statický analyzátor jazyka C podle normy ANSI licencovaný pod licencí GNU/GPL. Umožňuje kontrolovat více vlastností než kompilátor. Toho dosahuje ověřováním, že zdrojový kód je konzistentní s anotacemi, které daný kód popisují [13]. Z pohledu jazyka jsou tyto anotace obyčejnými komentáři, vyznačené pomocí znaku zavináče (/*@ anotace */). Tyto anotace jsou doplněny k parametrům a návratovým hodnotám funkcí, globálním proměnným a položkám struktur. Anotacemi je například možné vyznačit, že daná proměnná nesmí nabýt hodnoty NULL. Anotace také mohou označovat dobu života různých objektů. Například /*@only*/ na ukazateli znamená, že jde o jediný ukazatel na daný objekt a tedy je třeba před zánikem ukazatele objekt uvolnit. Nevýhodou Splintu je omezení na verzi jazyka podle normy ANSI a tedy není možné použít žádná rozšíření z pozdějších norem. Pokud navíc Splint narazí na konstrukci, které nerozumí, skončí s hlášením, na kterém řádku k chybě došlo, ale už neposkytne žádné další informace. Samotné anotace představují netriviální zátěž pro programátora při programování. Jejich další nevýhodou je, že znepřehledňují kód a komplikují jeho údržbu, protože je třeba udržovat anotace v souladu s kódem. Tyto 14
3. Dostupné nástroje anotace navíc nejsou srozumitelné pro ostatní nástroje. Splint pro analýzu kódu využívá metodu code flow analysis. Aby předešel problémům s efektivitou, analyzuje samostatně jednotlivé funkce. Také neanalyzuje všechny možné průchody kódem, ale snaží se jednotlivé cesty spojovat. Smyčky jsou analyzovány pomocí heuristik rozeznávajících časté idiomy. Tím je umožněno prozkoumat počet iterací bez potřeby znalosti invariantů.
3.5
Cppcheck
Cppcheck je analyzátor kódu pro C a C++, který se snaží vyhnout falešným varováním. Zároveň ale využívá zjednodušenou metodu analýzy běhu kódu: předpokládá, že každá podmínka je buď pravdivá, nebo nepravdivá. Dále také předpokládá, že všechny příkazy jsou dosažitelné. V důsledku těchto zjednodušení tedy nemusí najít všechny chyby, viz příklad A.5. Vzhledem k uvedenému předpokladu Cppcheck neví, že obě podmínky nemohou platit zároveň a proto nenahlásí žádnou chybu [22]. Cppcheck nabízí jak základní příkazové rozhraní, tak i zásuvné moduly pro Code::Blocks, Eclipse a další IDE3 . Ve výchozím nastavení se pokouší kontrolovat všechny možné kombinace konfigurací preprocesoru [8]. Vzhledem k obvykle vysokému počtu takových maker ve větších projektech, je praktické omezit tyto kontroly pouze na reálné kombinace. Cppcheck přijímá stejné přepínače -D... jako kompilátor GCC. Cppcheck řadí nalezené problémy do šesti kategorií. Jsou to chyby, varování (doporučení pro defenzivní programování), stylistické připomínky (nepoužité proměnné nebo funkce apod.), výkonnostní doporučení, upozornění na nepřenositelné konstrukce a informace o věcech, které by mohly být zajímavé (například nenalezené hlavičkové soubory). Bez doplňujících přepínačů Cppcheck vypisuje pouze nalezené chyby. V této práci byl použit Cppcheck verze 1.54.
3.6
Coverity
Coverity Static Analysis je komerční nástroj pro statickou analýzu programů v C, C++ a dalších jazycích. Dokáže detekovat jak obecné chyby (neinicializovaná paměť nebo problémy souběhu), tak i systémově závislé chyby (např. špatné pořadí funkčních volání) [1]. Coverity se snaží produkovat výsledky, ve kterých se vyskytuje maximálně 20 % falešných hlášení. Důvodem je, že příliš nepřesná analýza k vede možnému ignorování i reálných problémů. Přestože 3.
Integrated Development Environment
15
3. Dostupné nástroje výsledky analýz nástrojem Coverity jsou poměrně dobré, tvrzení o jedné pětině hlášení je spíše reklamním trikem než realitou. Od ostatních nástrojů se Coverity odlišuje také tím, že ve výsledcích analýz používá informace získané z kontextu okolního kódu – např. při nekontrolované návratové hodnotě (CWE-252) hlásí chybu pouze pro ta volání funkcí, která jsou alespoň někde kontrolována. Přestože statický analyzér Coverity je komerční nástroj, pro vývojáře svobodného softwaru je možné se k analýze dostat i zdarma4 . Od roku 2006 společnost Coverity ve spolupráci s US Department of Homeland Security zpřístupňuje statický analyzátor často používaným svobodným programům, jako je Apache, Linux nebo PHP. Analýza je ale dostupná každému programu pod licencí kompatibilní s Open Source Initiative5 . Smyslem této iniciativy bylo zlepšit kvalitu softwaru, který zajišťuje značnou část infrastruktury Internetu. Během prvního roku bylo opraveno přes 6000 chyb [6]. I po vypršení grantu v roce 2009 společnost Coverity pokračuje v poskytování analyzátoru zdarma. Coverity také názorně ukazuje, jak může být statická analýza přínosná pro firmy z oblasti informačních technologií, tak i v jiných oblastech. Mezi uživatele patří např. společnosti Red Hat, Samsung, Adobe nebo NASA [7].
4. 5.
http://scan.coverity.com http://www.opensource.org/docs/definition.php
16
4 Výsledky analýzy V této kapitole shrnu výsledky vybraných nástrojů nad reálnými zdrojovými kódy. Výsledky pro každou analýzu jsou zobrazeny v tabulce, kde sloupec označený TP označuje možné problémy (true positives), sloupec FP značí počet neplatných hlášení (false positives).
4.1
OpenSSL
Knihovna OpenSSL poskytuje různou funkcionalitu týkající se bezpečné síťové komunikace. Nalezení a oprava chyb je tedy důležitá, především v situacích, kdy je možné tyto nedostatky využít k útoku. V roce 2009 byla provedena analýza a detekce chyb v ošetření návratových hodnot [19]. Použit při tom byl nástroj Coccinelle 1 . Nejde přímo o statický analyzátor, ale o nástroj, který na základě sémantických patchů dokáže hledat místa, na kterých dochází k nějakému jevu. V tomto případě byly hledány funkce, které mohou vracet zápornou hodnotu, ale volající kód je ošetřuje podmínkou na rovnost nule. Pro účely této práce byly testovány zdrojové kódy získané z repozitáře CVS 14. března 2012. Jeden nalezený problém jsem spolu s opravou odeslal jako požadavek 2801 do request trackeru2 projektu OpenSSL. 4.1.1 Analýza Clangem Analyzátor Clang najde v knihovně OpenSSL 222 potenciálních chyb. 65 z nich je neplatných. Přestože je ve 157 platných chybách 103 mrtvých přiřazení, jsou v nich skryté zásadnější chyby jako ztracené chybové hlášení, v jednom případě tato chyba byla způsobena duplicitním řádkem kódu. 4.1.2 Analýza Cppcheckem Analyzátor Cppcheck najde ještě více defektů než Clang. Z nalezených 653 problémů je ale 187 neplatných. Ze 466 reálných problémů je 336 (72 %) doporučení omezit rozsah platnosti proměnné. V některých případech oprava tohoto problému směřuje k deklaraci proměnné v hlavičce cyklu for. Vzhledem k tomu, že tato konstrukce byla standardizovaná až standardem ISO/IEC 9899:1999 (neformálně C99), řada překladačů tuto syntaxi nemusí 1. 2.
http://coccinelle.lip6.fr/ http://rt.openssl.org/Ticket/Display.html?id=2801&user=guest&pass=guest
17
4. Výsledky analýzy Tabulka 4.1: Defekty v OpenSSL nalezené pomocí Clangu Defekt
TP
FP
Celkem
Všechny defekty NULL jako argument funkce, která vyžaduje validní ukazatel Idempotentní operace Mrtvé přiřazení Mrtvá inkrementace Mrtvá inicializace Volaný funkční ukazatel je NULL Dereference ukazatele NULL Dělení nulou Argument funkce je neinicializovaná hodnota Výsledek operace je smetí nebo nedefinovaný Výraz v podmínce se vyhodnotí na smetí Přiřazená hodnota je nedefinovaná nebo smetí
157 1
65 6
222 7
5 103 12 1 4 8 1 1 21 0 0
2 33 1 1 0 16 0 3 0 1 2
7 136 13 2 4 24 1 1 21 1 2
podporovat a proto je lepší se na ni nespoléhat. Přesto by v řadě případů bylo vhodné deklarovat proměnné ve vnořeném bloku a ne pro celou funkci. Řada falešných hlášení plyne z konfigurace maker preprocesoru, se kterými byl analyzátor spuštěn, protože některé části kódu byly zakázány. Čarami jsou v tabulce 4.2 ohraničeny postupně chyby, varování a stylistické připomínky. Problém s kombinací ternárního operátoru a operátoru pro modulo je v nedostatečném uzávorkování. V kódu se objevuje konstrukce x%8 ? 0 : -1. Priority definují, že nejprve se provede modulo, potom podmínka. To je v obou případech požadované chování. Přesto má smysl doporučit přidání závorek, aby chování kódu bylo zřejmé na první pohled. Některé z funkcí detekovaných jako nikdy nepoužité jsou pouze příklady a ukázky, jak použít nějakou funkcionalitu. Další nepoužité funkce jsou deklarovány v některém hlavičkovém souboru a jsou určeny pro uživatele knihovny OpenSSL, a i když ona sama je nevolá, jsou nezbytné. Detekovaný problém s funkcí scanf spočívá v hrozícím přetečení bufferu. Protože všechny výskytu dané funkce ale načítají pouze číslo, žádný buffer se v nich nevyskytuje a tedy nemůže přetéct. Cppcheck také považuje konstrukci x = malloc(sizeof *x) za nevhodné použití operátor sizeof. Tento idiom je ale korektní a používaný při alokacích paměti, kde umožňuje nezapisovat typ proměnné dvakrát. 18
4. Výsledky analýzy
Tabulka 4.2: Defekty v OpenSSL nalezené pomocí Cppchecku Defekt
TP
FP
Celkem
Všechny defekty
457
196
653
Možná dereference ukazatele NULL Neinicializovaná proměnná
0 1
6 0
6 1
scanf bez omezení je nebezpečný Použití sizeof s číselnou konstantou Použití proměnné typu char v bitové operaci
0 0 1
12 10 0
12 10 1
0 0 1 0 3 2 6 3 4 2 2 336 41 55
2 2 0 3 5 1 6 0 1 1 129 10 3 5
2 2 1 3 8 3 12 3 5 3 131 346 44 60
Čtení z pole bez kontroly mezí Nejasný výpočet s % a ? Násobný výskyt příkazu pro skok Stejná podmínka ve větvi if i else if Duplicitní větve pro if a else Kontrola zápornosti bezeznaménkové proměnné Stejný výraz na obou stranách operátoru & nebo || Výraz následující return, break nebo goto Položka struktury se nikdy nepoužije Podezřelá podmínka bez závorek Nikdy nepoužitá funkce Rozsah proměnné může být zmenšen Nepoužitá proměnná Hodnota proměnné není přečtena
19
4. Výsledky analýzy Za nedostatek je také považováno použití proměnné typu char v bitové operaci. Standard nedefinuje, jestli je tento typ znaménkový, a ponechává volnost implementaci. Zároveň vyžaduje, aby operandy bitových operací byly bezeznaménkové. Pro znaménkové číselné typy je výsledek nedefinovaný. 4.1.3 Analýza pomocí Coverity Program Coverity byl použit k analýze jiné verze zdrojového kódu než ostatní nástroje. Konkrétně šlo o verzi openssl-1.0.0e-fc17 bez aplikovaných patchů specifických pro distribuci Fedora. Celkem bylo nalezeno 261 možných problémů, z toho v 96 případech nešlo o falešné poplachy. Výsledky jsou shrnuty v tabulce 4.3. Velké počty problémů jsou částečně způsobeny tím, že z důvodů optimalizací jsou některé smyčky ručně rozbalené a tedy se na jejich místě opakuje určitá konstrukce. Jako špatná velikost bufferu je hlášena situace, kdy se pomocí funkce strncpy naplní celý buffer. Toto volání samo o sobě nechá řetězec neukončený bez místa pro koncovou nulu. Kód OpenSSL ale poslední byte přepíše nulou, takže k žádnému problému nedojde. Nalezený výraz s konstantní hodnotou je type | EVP_PKT_SIGN použitý v podmínce. Tento výraz ale bude nabývat vždy nenulové hodnoty. Coverity rozlišuje tři případy dereference ukazatele NULL. Zvlášť jsou detekovány ukazatele vrácené z nějaké funkce bez kontroly (Return NULL), případy, kdy je hodnota ukazatele kontrolována až po použití (Reverse NULL), a případy, kde se ukazatel někde porovnává s konstantou NULL, ale před jiným použitím se netestuje (Forward NULL). Všechny případy nalezeného přetečení statického bufferu jsou způsobeny prací se stejnou strukturou a konstrukcí. V ní se ukazatel na první prvek pole (o velikosti 8 bytů) interpretuje jako ukazatel na celé pole (velikosti 128 bytů). Analyzátor pravděpodobně nerozpozná korektní velikost, protože v poli jsou prvky definované jako union. Jako okamžik kontroly versus okamžik použití (Time-of-check Time-of-use, TOCTOU, CWE-367) je označena situace, kdy program sice kontroluje stav nějakého zdroje, ale v intervalu mezi kontrolou a samotným přístupem ke zdroji se stav může změnit a tedy výsledek kontroly může být znehodnocen.
4.2
Sudo
Sudo je nástroj, který umožňuje uživatelům spouštět programy pod cizí identitou, ať už superuživatele nebo jiného uživatele [23]. Tento nástroj disponuje modulární architekturou, a je tedy možné přidávat další funkcionalitu 20
4. Výsledky analýzy
Tabulka 4.3: Defekty v OpenSSL nalezené pomocí Coverity Defekt Všechny problémy Špatný argument pro sizeof Špatná velikost bufferu Výraz s konstantní hodnotou Mrtvý kód Dereference ukazatele NULL Chybějící kontrola návratové hodnoty Chybějící break Předání záporného čísla funkci, která očekává nezáporný argument Přetečení dynamické paměti Přetečení statické paměti Únik zdroje Použití indexu bez kontroly nezápornosti Podezřelé přetypování mezi znaménkovým a bezeznaménkovým typem Použití sizeof špatného typu Přetečení řetězce Nedostatečná kontrola vstupu Okamžik kontroly vs. okamžik použití Neinicializovaná proměnná Nedosažitelný kód Nepoužitá hodnota proměnné
TP
FP
Celkem
96 0 0 1 24 19 29 0 0
165 1 1 0 11 12 0 8 1
261 1 1 1 35 31 29 8 1
1 0 1 0 0
1 120 1 1 1
2 120 2 1 1
0 1 2 0 1 1 16
1 0 0 2 3 0 1
1 1 2 2 4 1 17
21
4. Výsledky analýzy pomocí pluginů. Jedním z dodávaných pluginů je sudoers umožňující pracovat s konfigurací v souboru se speciálním formátem. Pro účely této práce byly použity zdrojové kódy získané z verzovacího systému Mercurial 10. dubna 2012. 4.2.1 Analýza Clangem Clang najde v programu Sudo pouze 7 možných defektů. Jen jeden z nich ale není falešné hlášení. Ani tento problém ale nemůže působit reálné problémy. Tabulka 4.4: Defekty v Sudo nalezené pomocí Clangu Defekt Všechny problémy Idempotentní operace Mrtvé přiřazení Dělení nulou
TP
FP
Celkem
1 0 0 1
6 3 3 0
7 3 3 1
Všechny tři nalezené idempotentní operace jsou výskyty stejného problému: proměnná je po přetypování porovnávána sama se sebou, viz příklad A.2. V mém systému jsou oba zúčastněné typy identické, ovšem na jiné architektuře nebo v jiném operačním systému se typy z_off64_t a z_off_t mohou lišit. V takovém případě by kód zjišťoval, zda došlo k přetečení a případně vrátil hodnotu -1. Podobně mrtvé přiřazení se projevuje pouze tehdy, když není dostupná funkce ldap_search_st a používá se ldap_search_s. Místo přímého volání funkce je použito makro, které přijímá argumenty potřebné pro obě varianty, ovšem ty, které pro použitou funkci nejsou potřeba, nakonec ignoruje. Nalezené dělení nulou se nachází v testovacím programu, který načítá soubor s definicemi síťových rozhraní a testuje, jestli zadaná IP adresa patří lokálnímu zařízení nebo zda patří do aktuální sítě. V případě, že je soubor s definicemi testů prázdný, dojde k dělení nulou. Dotyčný program ale není určen k přímému užití, a při volání pomocí make check dostane na vstup soubor, který obsahuje 9 testů a k žádné chybě při dělení tedy nedojde. 4.2.2 Analýza Cppcheckem Analyzátor Cppcheck najde 155 možných problémů. Pouze 52 (33,5 %) jsou platné problémy. 25 z nich (48 % platných hlášení) jsou upozornění na omezení 22
4. Výsledky analýzy platnosti proměnné. Pouze jeden nalezený problém by teoreticky mohl vést k nežádoucímu chování – úniku paměti při selhání další alokace. Tabulka 4.5: Defekty v Sudo nalezené pomocí Cppchecku Defekt
TP
FP
Celkem
52
103
155
0 1
1 0
1 1
scanf bez omezení je nebezpečný Porovnání mezi typy bool a int
0 19
1 0
1 19
Stejný výraz na obou stranách operátoru Položka struktury se nikdy nepoužije Nikdy nepoužitá funkce Rozsah proměnné může být zmenšen Nepoužitá proměnná Použití operátoru ++ na proměnné typu bool Hodnota proměnné není přečtena Proměnná nemá přiřazenou hodnotu
0 3 2 25 0 0 1 1
2 7 82 0 1 3 6 0
2 10 84 25 1 3 7 1
Všechny defekty Index -1 je mimo meze pole Neuvolněná pamět při selhání realloc
Přestože problém s indexem -1 na první pohled vypadá jako zásadní problém, ve skutečnosti je kód korektní. Ve zdrojovém kódu se totiž o několik řádků výše ukazatel posunuje tak, aby ukazoval na druhý prvek pole, viz A.3. Funkce realloc umožňuje změnit velikost bloku alokované paměti. Pokud ale není možné blok zvětšit, dojde k alokaci dalšího místa, překopírování dat a uvolnění původního bloku. V případě nedostatku paměti realloc vrátí ukazatel NULL, ale neuvolní původní blok. Proto v programové konstrukci ptr = realloc(ptr, size) může dojít k úniku paměti. Doslovné hlášení o problému s operátorem ++ je „The use of a variable of type bool with the ++ postfix operator is always true and deprecated by the C++ Standard.“ Jednak se tato chyba týká kódů v C++, a navíc je změna hodnoty proměnné na true ve všech nalezených případech požadovaným chováním. 4.2.3 Analýza pomocí Coverity Analyzátor Coverity najde celkem 56 možných defektů. 30 z nich jsou neplatná hlášení. 23
4. Výsledky analýzy Tabulka 4.6: Defekty v Sudo nalezené pomocí Coverity Defekt Všechny defekty Špatné uvolnění paměti Špatná velikost bufferu Mrtvý kód Dereference ukazatele NULL Chybějící break Použití záporného čísla ve funkci, která očekává nezáporný argument Únik zdroje Nesmyslná podmínka Nedostatečná kontrola vstupu Okamžik kontroly vs. okamžik použití Neinicializovaná proměnná Nepoužitá hodnota proměnné Použití po free
TP
FP
Celkem
26 1 7 2 5 0 3
30 1 1 0 4 2 1
56 2 8 2 9 2 4
6 0 0 0 1 1 0
1 6 1 9 0 0 4
7 6 1 9 1 1 4
Nesmyslné podmínky jsou hlášeny jako nadbytečné středníky. Vždy jde o konstrukci tvaru if (...) ;. Protože taková podmínka nemá ani klauzuli then, ani else, jediný její smysl je v provedení v kódu podmínky. Nejjednodušší vysvětlení této konstrukce je tedy nadbytečný středník. Sudo v řadě případů korektně neuvolňuje alokované zdroje, ať už jde o paměť, otevřené soubory nebo otevřené sdílené knihovny.
4.3
Epiphany
Epiphany je webový prohlížeč desktopového prostředí GNOME. Je postaven na renderovacím jádře WebKit a jako i ostatní programy z GNOME využívá knihovnu GTK+ pro vytváření grafického uživatelského rozhraní. Základní myšlenkou tohoto prohlížeče je vytvoření jednoduchého nástroje pro přístup k webovým stránkám, který nenabízí velké množství možností nastavení, ale poskytuje rozumné výchozí hodnoty [12]. V této práci byly analyzovány zdrojové kódy verze 3.4.1-1. Opravy pro řadu nalezených problémů jsem odeslal do bugzilly Gnome jako bug 6758883 . 3.
https://bugzilla.gnome.org/show_bug.cgi?id=675888
24
4. Výsledky analýzy 4.3.1 Analýza Clangem Analyzér Clang našel v Epiphany celkem 17 problémů, z nichž pouze 2 jsou falešným hlášením. Tato nezvyklá přesnost může být způsobena mimo jiné tím, že Epiphany ve verzi 3.4 přišlo s novým uživatelským rozhraním [9], při jehož vytváření bylo nutné upravit značné množství kódu.
Defekt
Tabulka 4.7: Defekty v Epiphany nalezené Clangem TP FP
Všechny problémy NULL jako argument funkce, která vyžaduje validní ukazatel Idempotentní operace Mrtvé přiřazení Výraz v podmínce se vyhodnotí na smetí Dereference ukazatele NULL
Celkem
15 0
2 1
17 1
1 10 1 3
0 0 0 1
1 10 1 4
Jedno nalezené mrtvé přiřazení ve skutečnosti není pouze nevinné opomenutí programátora, ale jde o únik paměti. Clang sice korektně detekuje, že se na daném řádku nachází problém, ovšem bylo by dobré označit ho jako vážnější případ. Takové označení méně pravděpodobně zapadne mezi ostatními. Problém detekovaný jako idempotentní operace je naopak spíše mrtvým přiřazením: do proměnné se dvakrát uloží stejná data. 4.3.2 Analýza Cppcheckem Analyzátor Cppcheck ve webovém prohlížeči našel 67 možných problémů. 35 z nich se ukázalo jako reálné defekty. Problémy s uvolňováním paměti a zavíráním otevřených souborů jsou s výjimkou jednoho případu (také nalezeného pomocí Clangu) způsobeny nevhodným ošetřením chyb – program sice korektně reaguje na selhání volaných funkcí a nespadne, ovšem zdroje už neuvolní. Přestože bylo nalezeno 17 míst, na kterých se údajně porovnává typ bool s nějakým celočíselným typem, ve skutečnosti tomu tak není. Vždy šlo o porovnávání typu gboolean s konstantou TRUE nebo FALSE. Dotyčný typ je sice definovaný v knihovně Glib jako alias pro int, ale v kódu je jasně patrné, že jde o pravdivostní hodnoty.
25
4. Výsledky analýzy
Tabulka 4.8: Defekty v Epiphany nalezené Cppcheckem Defekt TP FP Celkem Všechny problémy
35
32
67
Únik paměti Únik deskriptoru Neinicializovaná proměnná
4 1 1
0 0 0
4 1 1
Použití scanf bez omezení délky Porovnání typu bool s celým číslem
0 0
9 17
9 17
2 24 1 1 1 0 0
0 0 0 2 0 1 3
2 24 1 3 1 1 3
Kontrola nezápornosti bezeznaménkového čísla Rozsah proměnné může být zmenšen Položka struktury se nikdy nepoužije Duplicitní větve pro if a else Násobný výskyt příkazu pro skok Nikdy nepoužitá funkce Hodnota proměnné není přečtena
26
5 Srovnání nástrojů 5.1
Přesnost
Přirozenou metrikou pro posouzení úspěšnosti klasifikace je přesnost jako poměr počtu správně nalezených problémů k počtu všech hlášení. V tabulce 5.1 je tato hodnota spočítána pro každý testovaný analyzátor. Tato metoda ovšem není z principu úplně objektivní. Záleží totiž na klasifikaci nalezených problémů. U některých hlášení je jejich oprávněnost zřejmá, jinde už tak jednoznačná není. Například hlášení o omezení rozsahu platnosti proměnné jsou prakticky všude oprávněná ve smyslu, že proměnná opravdu může být definována pro menší blok kódu, pokud je ale daný styl deklarací dodržován v celém kódu, nejde vyloženě o chybu. Pro účely této práce byly chyby klasifikovány pouze na základě jejich faktické oprávněnosti bez ohledu na styl kódu. Pokud tedy hlášení popisuje problém, ke kterému může dojít, byl zařazen jako pravdivé hlášení. Tabulka 5.1: Přesnost jednotlivých nástrojů TP FP Celkem Přesnost Clang 173 73 246 70,3 % Cppcheck 544 331 875 62,2 % Coverity 122 195 317 38,5 % Tato metoda porovnávání ale není vůči všem nástrojům spravedlivá, protože nebere v úvahu různé typy detekovaných chyb. Například Cppcheck detekuje velké množství stylistických problémů, které ovšem obvykle pro funkci programu nejsou zásadní. Kdybych spočítali jeho přesnost bez těchto hlášení, přesnost by klesla na 29,3 %.
5.2
Typy chyb
Protože nástroje nepoužívají stejné techniky, podle očekávání různé nástroje najdou různé chyby a obecně různé typy chyb. Z provedených analýz plyne, že řada nástrojů má „oblíbený“ defekt, který převládne jako většina nalezených problémů. Ne vždy ale představuje vážný problém. U Cppchecku jde o omezení rozsahu platnosti proměnné, Clangu vadí mrtvá přiřazení, Sparse doporučuje deklaraci funkcí jako statických. Ve všech případech jde sice o stav, který by šlo snadno opravit, ovšem ani neopravené tyto konstrukce nebudou působit závažné problémy. 27
5. Srovnání nástrojů Procentuální zastoupení typů chyb je patrné z grafů 5.1, 5.2 a 5.3. U Clangu i Cppchecku jasně převažuje jeden typ chyb, na rozdíl od Coverity, kde je rozložení rovnoměrnější. Pro snazší porovnání jsem nalezené defekty zařadil do šesti kategorií. Do kategorie logických chyb jsou zařazena dělení nulou, přetečení zásobníku nebo řetězce a nedostatečná kontrola vstupních dat. Paměť a zdroje zahrnují úniky paměti a deskriptorů. Neinicializovaná data obsahují neinicializované proměnné a výrazy, které se vyhodnotí na smetí. V kategorii Ukazatel NULL jsou zahrnuty všechny případy dereference ukazatele NULL, ať už jde o čtení, přiřazování nebo volání funkčního ukazatele. Kategorie Styl kódu obsahuje připomínky k nejasnému zápisu výrazu, omezení rozsahu platnosti proměnné a porovnávání typů int a bool. Do Mrtvého kódu jsou navíc zařazeny nepoužité funkce a položky struktur. Obrázek 5.1: Zastoupení jednotlivých chyb pro Clang
5.3
Mrtvý a duplicitní kód (131) Logická chyba (2) Neinicializová data (22) Ukazatel NULL (16) Paměť a zdroje (1)
Rychlost analýzy
V tabulce 5.2 je shrnuta doba analýzy jednotlivých testovaných nástrojů. Měření času pro Clang a Cppcheck proběhlo na počítači s procesorem Intel Core2 Duo o frekvenci 2,53 GHz vybaveným 4 GB operační paměti. Pro lepší představu jsou v tabulce zařazeny i doba kompilace (kompilátorem GCC) a doba běhu testů. Časy pro Coverity jsou pouze orientační, tato měření proběhla na jiném počítači. Analyzovat zdrojové kódy programu trvá Clangu zhruba čtyřikrát až desetkrát déle samotný překlad bez ohledu na typ analyzovaného kódu. 28
5. Srovnání nástrojů
Obrázek 5.2: Zastoupení jednotlivých chyb pro Cppcheck
Mrtvý a duplicitní kód (122) Paměť a zdroje (6) Neinicializová data (3) Styl kódu (407) Logická chyba (4)
Obrázek 5.3: Zastoupení jednotlivých chyb pro Coverity
OpenSSL Sudo Epiphany
Mrtvý a duplicitní kód (44) Paměť a zdroje (8) Neinicializová data (2) Ukazatel NULL (24) Styl kódu (30) Logická chyba (14)
Tabulka 5.2: Srovnání rychlosti Kompilace Testy Clang 2 m 28 s 24,6 s 17 m 42 s 25 s 1,2 s 5 m 24 s 1 m 59 s 5,4 s 4 m 41 s
analyzérů Cppcheck 37 m 58 s 20 s 171 m 32 s
Coverity 19 m 10 s 1 m 57 s
29
5. Srovnání nástrojů U Cppchecku nejsou výsledky tak rovnoměrné. V případě Suda analýza 130 zdrojových souborů trvá pouze 20 s, u Epiphany se 135 zdrojovými soubory trvá bezmála 3 hodiny. Výrazně delší doba analýzy Epiphany pomocí Cppchecku je pravděpodobně způsobena větším množstvím hlavičkových souborů. Epiphany jakožto program s grafickým rozhraním potřebuje řada dalších knihoven: WebKit, Gtk+, Pango, Cairo, Freetype a další. Při analýze každého souboru Cppcheck znovu a znovu prohledává vkládané hlavičkové soubory a načítá všechny definované typy, funkce a makra. Tuto teorii podporuje fakt, že zatímco průměrná délka zdrojového souboru v Sudo i Epiphany je přibližně stejná (420 vs. 484 řádků), po expanzi preprocesoru se soubory v Sudo zvětší zhruba devětkrát na průměrných 3877 řádků, u Epiphany je tento faktor výrazně větší – průměrně má expandovaný soubor 51048 řádků, což je více než stonásobné zvětšení. Tento rozdíl se u Clangu neprojevil z důvodu jiného zpracování souborů. Clang používá i pro statickou analýzu stejný parser jako v kompilátoru. Cppcheck naproti tomu využívá regulárních výrazů nebo heuristik napsaných v C++ [21].
5.4
Další možnosti analyzátorů
Statické analyzátory je možné také porovnávat podle dalších nabízených možností, které s analýzou zdrojového kódu přímo nesouvisí, ale usnadňují ji. Bohužel v této oblasti svobodné nástroje velmi zaostávají. Jedna z možností, jak zjednodušit provádění analýzy, je poskytnutí rozhraní pro snadnou práci s chybami. Analyzátor Clang kromě vypisování nalezených chyb na standardní chybový výstup generuje rozsáhlé dokumenty v HTML s postupem, jak reprodukovat daný problém. Z této formy výstupu je také možné přímo otevírat dotyčné soubory, případně hlásit nalezené chyby e-mailem. Vytvářený e-mail obsahuje informace o tom, ve kterém souboru a na kterém řádku se chyba nachází, o jakou chybu jde a v příloze e-mailu je soubor s detailním postupem replikace. Cppcheck sice také nabízí více možností prezentovat výsledky (textový výstup, XML, HTML), ovšem pokročilý nástroj pro práci s vytvořenými záznamy neposkytuje. Coverity naopak v této oblasti exceluje. Kromě nástrojů pro statickou analýzu nabízí také rozhraní Coverity Integrity Manager, které umožňuje další práci s nalezenými defekty [5]. Tento nástroj poskytuje rozhraní, ve kterém je možné jednotlivé nalezené defekty klasifikovat, přidávat k nim údaje o důležitosti, případně je přiřazovat určitému vývojáři. 30
5. Srovnání nástrojů Zároveň je v Coverity Integrity Manageru dostupná možnost provádět tzv. inkrementální analýzu. Pokud při prvním spuštění analýzy dojde k nalezení falešného problému, není důvod měnit dotyčné místo v kódu a proto pravděpodobně při dalším spuštění analýzy dojde k opětovnému nálezu toho samého problému, maximálně posunutého o pár řádek výš nebo níž. Nástroj podporující inkrementální analýzu pozná, že jde o opakování už jednou nalezeného a odmítnutého defektu a jako takový jej nebude v seznamu nalezených chyb zobrazovat mezi nově nalezenými problémy.
31
6 Závěr Přestože na první pohled se zdá, že více nalezených problémů je lepší než méně, nelze toto jednoznačně tvrdit. Pokud nástroj najde více problémů, pravděpodobně mezi nimi bude i více falešných hlášení. Navíc u ideálního hlášení je snadné poznat, jestli jde o false positive nebo ne. Pokud např. Clang najde problém na cestě, kde je třeba nejprve vykonat desítky kroků, aby se program dostal do chybného stavu, tak je bez detailní znalosti kódu téměř nemožné zjistit, zda je takový běh opravdu možný. Přesto je statická analýza velice užitečný nástroj pro odhalování problémů v kódu. I kdyby klasifikace nalezených potenciálních defektů zabrala programátorovi několik dní, pořád povede k opravení většího množství problémů, než je možné nalézt bez pomoci automatizovaných nástrojů. Je ovšem dobré mít na paměti, že ne všechny nalezené problémy jsou důležité. Pokud analyzátor vypíše stovky připomínek ke stylu kódu, nemusí se jejich oprava vyplatit například i proto, že během opravy mohou vzniknout další chyby a navíc odčerpají čas vývojářů, který by mohl být investován do užitečnějších úprav kódu [11]. Už jediné spuštění analyzátoru může vést k nalezení relativně velkého počtu problémů. Lepší přístup k analýze spočívá v pravidelném analyzování a opravě chyb co nejdříve je to možné. Tím se zabrání nahromadění problémů a nutnosti procházet a klasifikovat stovky hlášení. Jako ideální možnost se tedy jeví použití nástroje pro continuous integration jako je například Jenkins 1 . Tyto nástroje automaticky sestavují zdrojový kód po každém příspěvku do verzovacího systému a zároveň nad kompilovaným kódem okamžitě spouštějí testy. Pokud dojde k nějakému selhání, autor daného kódu je upozorněn, že svým kódem rozbil ten který test. Přidání statické analýzy k tomuto procesu je tedy přirozený požadavek, který je navíc snadno realizovatelný. Například zmíněný nástroj Jenkins podporuje zásuvné moduly pro řadu statických analyzátorů – Clang, Cppcheck, Coverity a další [17]. Uživatelé statického analyzátoru typicky chtějí nástroj, který najde maximálně pár desítek opravdu zásadních problémů, které se mohou reálně projevit. Bohužel, z dostupných svobodných nástrojů žádný takové výsledky nepodává. Z provedených analýz se nedá jednoznačně říct, že jeden analyzátor je výrazně lepší než jiný. Nejlepší způsob, jak vybrat, který analyzátor použít, je vyzkoušet jich víc a porovnat výsledky na konkrétním programu. 1.
http://jenkins-ci.org/
32
Literatura [1] Bessey, A.; Block, K.; Chelf, B.; aj.: A few billion lines of code later: using static analysis to find bugs in the real world. Commun. ACM, ročník 53, č. 2, Únor 2010: s. 66–75, ISSN 0001-0782, doi:10.1145/1646353.1646374. URL
[2] Brat, G.; Visser, W.: Combining Static Analysis and Model Checking for Software Analysis. In Proc. ASE 2001, IEEE Computer Society, 2001, s. 262–271. [3] Chatzieleftheriou, G.; Katsaros, P.: Test-Driving Static Analysis Tools in Search of C Code Vulnerabilities. Computer Software and Applications Conference Workshops, ročník 0, 2011: s. 96–103, doi:10.1109/COMPSACW.2011.26. [4] Clang Static Analyzer. [online], [cit. 2012-04-17]. URL [5] Coverity Inc.: Coverity Integrity Manager. [cit. 2012-05-12]. URL [6] Coverity Inc.: Coverity Scan. [cit. 2012-05-10]. URL [7] Coverity Inc.: Who Uses Coverity? [cit. 2012-05-10]. URL [8] Cppcheck manual. [cit. 2012-04-16]. URL [9] Day, A.; Klapper, A.; Vitters, O.: GNOME 3.4 Release Notes. [cit. 2012-05-11]. URL [10] Engler, D.; Chelf, B.; Chou, A.: Checking system rules using system-specific, programmer-written compiler extensions. 2000, s. 1–16. [11] Engler, D.; Musuvathi, M.: Static Analysis Versus Software Model Checking for Bug Finding. In In VMCAI, Springer, 2004, s. 191–210. 33
[12] Epiphany: Readme. [cit. 2012-05-10]. URL [13] Evans, D.; Larochelle, D.: Improving Security Using Extensible Lightweight Static Analysis. IEEE Software, ročník 19, 2002: s. 42–51, ISSN 0740-7459, doi:http://doi.ieeecomputersociety.org/10.1109/52.976940. [14] Free Software Foundation: Using the GNU Compiler Collection (GCC). [online], [cit. 2012-03-26]. URL [15] Hallem, S.; Park, D.; Engler, D.: Uprooting Software Defects at the Source. Queue, ročník 1, č. 8, Listopad 2003: s. 64–71, ISSN 1542-7730, doi:10.1145/966712.966722. URL [16] Jelínek, L.: Object size checking to prevent (some) buffer overflows. [online], [cit. 2012-04-16]. URL [17] Kawaguchi, K.; Mansour, M. M.: Jenkins Plugins. [cit. 2012-06-12]. URL [18] Kremenek, T.: Finding Bugs with the Clang Static Analyzer. 2008. URL [19] Lawall, J. L.; Laurie, B.; Hansen, R. R.; aj.: Finding Error Handling Bugs in OpenSSL Using Coccinelle. In Eighth European Dependable Computing Conference, EDCC-8 2010, 2010, ISBN 978-0-7695-4007-8, s. 191–196, doi:10.1109/EDCC.2010.31, http://www.odysci.com/article/1010112984383965. URL [20] Linux man-pages project: gets(3) manual. [cit. 2012-04-18]. [21] Marjamäki, D.: Writing Cppcheck Rules Part 1. [cit. 2012-05-14]. URL 34
[22] Marjamäki, D.: Cppcheck Design. 2010. URL [23] Miller, T. C.: sudo(8) manual. [cit. 2012-05-02]. URL [24] Sparse Source Code. [online], [cit. 2012-04-16]. URL [25] Wells, D.: Unit Tests. [online], 1999, [cit. 2011-11-12]. URL
35
A Příklady kódu A.1
Nenahlášené varování v OpenSSL
al = SSL_AD_DECODE_ERROR; SSLerr(SSL_F_DTLS1_READ_BYTES, SSL_R_BAD_HELLO_REQUEST); goto err; [...] return 0; f_err: ssl3_send_alert(s, SSL3_AL_FATAL, al); err: return -1; }
A.2
Idempotentní operace v Sudo z_off64_t ret; [...] return ret == (z_off_t)ret ? (z_off_t)ret : -1;
A.3
Index -1 v Sudo
int main (int argc, char *argv[], char *envp[]) { [...] argv++; [...] if (argv[-1][0] == ’-’) ... }
A.4
Přetečení bufferu detekovatelné při překladu
char buffer[4]; strcpy(buffer, "Hello");
36
A. Příklady kódu
A.5
Cppcheck nedetekuje únik paměti
void f(int x) { char *a = 0; if (x == 10) a = malloc(10); if (x == 20) free(a); }
A.6
Příklad pro analýzu toku kódu
#include <stdio.h> #include <string.h> #include <stdlib.h> static char * get_data(void) { char *buffer; buffer = malloc(10); if (buffer) strcpy(buffer, "Hello"); return buffer; } int main(int argc, char *argv[]) { char *buffer; buffer = get_data (); if (buffer) printf("%s\n", buffer); return 0; }
37
