AUTOMATIZOVANÉ METODY HLEDÁNÍ

ˇ ´ UCEN Í TECHNICKE´ V BRNEˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ´ ´ U ˚ USTAV INTELIGENTNÍCH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS

´ Í AUTOMATIZOVANE´ METODY HLEDAN ˇ ÍCH ˇ CHYB V PREKLADA C

´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS

´ AUTOR PRACE AUTHOR

BRNO 2008

¨ PETR MULLER

ˇ ´ UCEN Í TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ´ ´ U ˚ USTAV INTELIGENTNÍCH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS

´ Í AUTOMATIZOVANE´ METODY HLEDAN ˇ ÍCH ˇ CHYB V PREKLADA C AUTOMATED METHODS OF FINDING BUGS IN COMPILERS

ˇ ´ PRACE ´ BAKALA´ RSK A BACHELOR’S THESIS

´ AUTOR PRACE

¨ PETR MULLER

AUTHOR

´ VEDOUCÍ PRACE SUPERVISOR

BRNO 2008

ˇ VOJNAR, Ph.D. ´S doc. Ing. TOMA

Abstrakt Tato práce se zab´ yvá aplikac´ı metody fuzz testing k testován´ı pˇrekladaˇc˚ u a interpret˚ u. V prvn´ı ˇcásti pojednává o pˇrekladaˇc´ıch, optimalizac´ıch a chybách typick´ ych pro optimalizuj´ıc´ı pˇrekladaˇc. Analyzuje vhodnost metod statické a dynamické anal´ yzy pro hledán´ı tˇechto chyb a jako vhodnou navrhuje dynamickou metodu fuzz testován´ı. V rámci práce byl implementován nástroj pro testován´ı pˇrekladaˇc˚ u pouˇz´ıvaj´ıc´ı tuto metodu, kter´ y byl aplikov´ an na nˇekolik pˇr´ıpad˚ u, pˇriˇcemˇz se podaˇrilo nalézt sérii chyb v rozˇs´ıˇren´ ych pˇrekladaˇc´ıch, a to vˇcetnˇe napˇr. GCC.

Kl´ıˇ cov´ a slova pˇrekladaˇce, testován´ı, generátor náhodn´ ych vˇet, gramatiky, Python, jazyk C

Abstract This thesis discusses an application of the fuzz testing method for testing compilers and interpreters. In the first part, it deals with compilers, optimizations, and bugs typical for an optimizing compiler. It analyzes applicability of static and dynamic analysis methods for searching such bugs and proposes dynamic fuzz testing as suitable for this task. A compiler testing tool suite using this method was implemented within this thesis and applied on several real compilers, including GCC, in which the tool revealed a series of bugs.

Keywords compilers, testing, random sentence generator, grammars, Python, C language

Citace Petr M¨ uller: Automatizované metody hledán´ı chyb v pˇrekladaˇc´ıch, bakaláˇrská práce, Brno, FIT VUT v Brnˇe, 2008

Automatizovan´ e metody hled´ an´ı chyb v pˇ rekladaˇ c´ıch Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakaláˇrskou práci vypracoval samostatnˇe pod veden´ım doc. Ing. Tomáˇse Vojnara, Ph.D. Uvedl jsem vˇsechny literárn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... Petr M¨ uller 14. kvˇetna 2008

Podˇ ekov´ an´ı Dˇekuji doc. Tomáˇsi Vojnarovi za veden´ı této práce a mnoho podnˇetn´ ych rad a pˇripom´ınek. Rád bych také podˇekoval panu Benovi Levensonovi za podporu a veden´ı mé práce v oboru testov´ an´ı pˇrekladaˇc˚ u.

c Petr M¨

uller, 2008. Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysokém uˇcen´ı technickém v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorským z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonné, s výjimkou z´ akonem definovaných pˇr´ıpad˚ u.

Obsah ´ 1 Uvod

3

2 Pˇ rekladaˇ ce a optimalizace 2.1 Pˇrekladaˇce a interprety . . . . 2.1.1 Pˇrekladaˇce . . . . . . . 2.1.2 Interprety . . . . . . . . 2.2 Principy konstrukce pˇrekladaˇc˚ u 2.2.1 Front-end . . . . . . . . 2.2.2 Middle-end . . . . . . . 2.2.3 Back-end . . . . . . . . 2.3 Optimalizace . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4 4 4 4 4 5 6 6 6

3 Chyby v pˇ rekladaˇ c´ıch a metody jejich hled´ an´ı 3.1 Chyby v pˇrekladaˇc´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Obecné chyby v programech . . . . . . . . . . . . . . . . . . . . 3.1.2 Chyby typické pro pˇrekladaˇce . . . . . . . . . . . . . . . . . . . 3.2 Hledán´ı a testovac´ı pokryt´ı r˚ uzn´ ych typ˚ u chyb . . . . . . . . . . . . . 3.2.1 Statická anal´ yza . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Dynamická anal´ yza . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Metody testován´ı pˇrekladaˇc˚ u c´ılené na jejich typické problémy

. . . . . . .

. . . . . . .

. . . . . . .

7 7 7 7 9 10 10 11

. . . . . . . . .

12 12 13 15 15 15 20 21 22 22

. . . . . . . . . . . . . . . . . . .

23

5 Aplikace na re´ aln´ e pˇ r´ıpady 5.1 Metodika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Testované pˇrekladaˇce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Klasifikace v´ ysledk˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 26 26

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4 N´ avrh syst´ emu pro testov´ an´ı pˇ rekladaˇ c˚ u 4.1 Principy metody fuzz testing . . . . . . . 4.2 Celkov´ y návrh a implementace . . . . . . 4.3 Spitter . . . . . . . . . . . . . . . . . . . . 4.3.1 Generátor . . . . . . . . . . . . . . 4.3.2 Director . . . . . . . . . . . . . . . 4.3.3 Pˇr´ıklad celého procesu . . . . . . . 4.3.4 Pomocné moduly . . . . . . . . . . 4.4 Builder . . . . . . . . . . . . . . . . . . . 4.5 Comparator . . . . . . . . . . . . . . . . . 4.6 Pokryt´ı pro pˇrekladaˇce specifick´ ych chyb navrˇzen´ ym systémem . . . . . . . . . . . .

1

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5.4

5.5

5.6 5.7

5.8

Pˇr´ıpad 1: gcc s r˚ uzn´ ymi optimalizacemi 5.4.1 Prostˇred´ı a podm´ınky . . . . . . 5.4.2 Spitter . . . . . . . . . . . . . . . 5.4.3 Randprog . . . . . . . . . . . . . 5.4.4 fuzz . . . . . . . . . . . . . . . . 5.4.5 Zhodnocen´ı experimentu . . . . . Pˇr´ıpad 2: GCC, TCC . . . . . . . . . . . 5.5.1 Prostˇred´ı a podm´ınky . . . . . . 5.5.2 Spitter . . . . . . . . . . . . . . . 5.5.3 Randprog . . . . . . . . . . . . . 5.5.4 fuzz . . . . . . . . . . . . . . . . Zhodnocen´ı experimentu . . . . . . . . . Pˇr´ıpad 3: icc, gcc . . . . . . . . . . . . . 5.7.1 Prostˇred´ı a podm´ınky . . . . . . 5.7.2 Spitter . . . . . . . . . . . . . . . 5.7.3 Randprog . . . . . . . . . . . . . 5.7.4 fuzz . . . . . . . . . . . . . . . . 5.7.5 Zhodnocen´ı experimentu . . . . . Pˇr´ıpad 4: gcc-stable, gcc-bleeding edge . 5.8.1 Prostˇred´ı a podm´ınky . . . . . . 5.8.2 Spitter . . . . . . . . . . . . . . . 5.8.3 Randprog . . . . . . . . . . . . . 5.8.4 fuzz . . . . . . . . . . . . . . . . 5.8.5 Zhodnocen´ı experimentu . . . . .

6 Z´ avˇ er 6.1 Zhodnocen´ı v´ ysledk˚ u . . . . . . . . . 6.1.1 Generátory náhodného kódu 6.1.2 Systém pro testován´ı . . . . . 6.2 Zhodnocen´ı pouˇzitelnosti metody . . 6.3 Dalˇs´ı v´ yvoj . . . . . . . . . . . . . . A Nalezen´ e chyby A.1 Chyba 1 . . . A.2 Chyba 2 . . . A.3 Chyba 3 . . . A.4 Chyba 4 . . . A.5 Chyba 5 . . . A.6 Chyba 6 . . . A.7 Chyba 7 . . . A.8 Chyba 8 . . . A.9 Chyba 9 . . . A.10 Chyba 10 . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

2

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

27 27 27 27 27 29 29 29 29 29 30 30 30 30 31 31 31 33 33 33 34 34 34 34

. . . . .

36 36 36 37 37 37

. . . . . . . . . .

38 38 39 40 41 42 43 44 45 46 47

Kapitola 1

´ Uvod Neodmyslitelnou souˇcást´ı ˇretˇezce nástroj˚ u pro v´ yvoj modern´ıch poˇc´ıtaˇcov´ ych program˚ u jsou pˇrekladaˇce a interprety programovac´ıch nebo jin´ ych jazyk˚ u. V´ yvoj aplikac´ı v assemblerech je v souˇcasnosti záleˇzitost´ı vestavˇen´ ych platforem a vysoce optimalizovan´ ych operac´ı. Naprostá vˇetˇsina program˚ u je psána v kompilovan´ ych nebo interpretovan´ ych programovac´ıch jazyc´ıch. Ty umoˇzn ˇuj´ı programátorovi formulovat program na vysokém stupni abstrakce a obstarávaj´ı mnoho automatizovan´ ych u ´kol˚ u, kter´ ymi se potom programátor nemus´ı zab´ yvat. Pˇrekladaˇce jsou velmi komplexn´ı nástroje a poskytuj´ı sv´ ym uˇzivatel˚ u stále dokonalejˇs´ı a sloˇzitˇejˇs´ı sluˇzby, napˇr. automatickou paralelizaci pro v´ıceprocesorové ˇci v´ıcej´ adrové systémy, masivn´ı optimalizace apod. Vˇetˇsina programátor˚ u je na tˇechto sluˇzbách z´ avisl´ a, protoˇze je mimo jejich moˇznosti tvoˇrit ruˇcnˇe stejnˇe v´ ykonné programy, jako je tomu s pouˇzit´ım pˇrekladaˇc˚ u a dalˇs´ıch modern´ıch nástroj˚ u. Zároveˇ n je tvorba program˚ u bez tˇechto nástroj˚ u neefektivn´ı a nákladná. Jako kaˇzd´ y program, i pˇrekladaˇce obsahuj´ı chyby. Modern´ı pˇrekladaˇce jsou typicky velmi sloˇzité systémy, které bˇehem aˇz stovek pr˚ ubˇeh˚ u kódem mohou naprosto zmˇenit jeho podobu. Vzhledem k v´ ysadn´ımu postaven´ı pˇrekladaˇc˚ u v ˇretezci v´ yvoje program˚ u je tedy velmi podstatná jejich správná funkˇcnost. Tato práce si klade za c´ıl zhodnotit moˇznosti automatizace testován´ı pˇrekladaˇc˚ u, na základˇe tˇechto znalost´ı implementovat systém pro hledán´ı chyb v nich a otestovat jeho aplikaci v praxi. Tato práce se zamˇeˇruje na testován´ı pˇrekladaˇc˚ u jazyka C, ale obecné principy zde popsané je moˇzné aplikovat i na testován´ı nejen pˇrekladaˇce kompilovan´ ych jazyk˚ u, ale i pro hledán´ı chyb v interpretech. Prvn´ı ˇcást práce obsahuje teoretick´ y základ pro testovan´ı pˇrekladaˇc˚ u a zahrnuje z´ akladn´ı definice z oblasti. Dále pojednává o chybách, které se v pˇrekladaˇc´ıch vyskytuj´ı a metod´ ach, které je moˇzné pˇri jejich hledán´ı pouˇz´ıt. Druhá ˇcást obsahuje návrh a popis implementace systému, kter´ y tyto metody popsané v prvn´ı ˇcásti uvád´ı v rámci této práce do praxe pˇriˇcemˇz vyuˇz´ıvá fakt, které byly zjiˇstˇeny v prvn´ı ˇcásti, k u ´plnému a efektivnˇejˇs´ımu testovac´ıho pokryt´ı pˇrekladaˇce. Ve tˇret´ı ˇcásti byl implementovan´ y prototyp systému aplikován na nˇekteré rozˇs´ıˇrené pˇrekladaˇce jazyka C. Je zde popsána metodika testován´ı, jeho pr˚ ubˇeh a analyzovány v´ ysledky testován´ı.

3

Kapitola 2

Pˇ rekladaˇ ce a optimalizace Tato kapitola zpracovává teoretick´ y základ pro oblast pˇrekladaˇc˚ u. Uvád´ı základn´ı principy konstrukce pˇrekladaˇce, jeho obvyklé souˇcásti a jejich funkci. Zab´ yvá se také optimalizacemi, které modern´ı pˇrekladaˇce nad kódem provádˇej´ı pro vyˇsˇs´ı efektivitu pˇreloˇzeného programu.

2.1 2.1.1

Pˇ rekladaˇ ce a interprety Pˇ rekladaˇ ce

Pˇrekladaˇc [6] (téˇz kompilátor, z angl. compiler ) je program, schopn´ y ˇc´ıst program v jednom jazyce – zvaném zdrojovém – a pˇreloˇzit ho do ekvivalentn´ıho programu zapsaném v jiném jazyce – c´ılovém. Pojem pˇrekladaˇc je typicky pouˇz´ıván pro programy prov´ adˇej´ıc´ı pˇreklad programu zapsaného ve vyˇsˇs´ım programovac´ım jazyce do jazyka niˇzˇs´ıho, nejˇcastˇeji strojového kódu poˇc´ıtaˇce. Pˇr´ıkladem jazyk˚ u, které jsou obvykle pˇr´ımo pˇrekládány jsou C, C++ nebo rodina jazyk˚ u Fortran. C´ılem je z abstraktn´ıho zápisu algoritmu z´ıskat spustiteln´ y program. Programy provádˇej´ıc´ı opaˇcn´ y pˇreklad se naz´ yvaj´ı dekompil´ atory. Existuj´ı i programy, které provádˇej´ı pˇreklad mezi jazyky zhruba stejné u ´rovnˇe abstrakce.

2.1.2

Interprety

Interpret je naproti tomu program, kter´ y m´ısto pˇrekladu programy napsané ve vyˇsˇs´ım programovac´ım jazyce pˇr´ımo spouˇst´ı, tj. interpretuje. Interpret b´ yvá obvykle postaven jako virtuáln´ı stroj pˇr´ımo provádˇej´ıc´ı pˇr´ıkazy programovac´ıho jazyka nebo instrukce vnitˇrn´ıho mezik´ odu. V´ yhodou tohoto pˇr´ıstupu je vyˇsˇs´ı abstrakce od hardwaru a operaˇcn´ıho systému, coˇz s sebou nese vˇetˇs´ı pohodl´ı, robustnost, menˇs´ı náchylnost k chybám a lepˇs´ı moˇznosti diagnostiky. Naproti tomu b´ yvá program pˇreloˇzen´ y do strojového k´ odu pˇrekladaˇcem mnohem rychlejˇs´ı neˇz ekvivalentn´ı program provádˇen´ y interpretem, a to z d˚ uvodu vyˇsˇs´ıho mnoˇzstv´ı reˇzijn´ıho kódu. Typick´ ymi zástupci interpretovan´ ych jazyk˚ u jsou modern´ı dynamické programovac´ı jazyky, tedy napˇr. Python, Ruby nebo Lua.

2.2

Principy konstrukce pˇ rekladaˇ c˚ u

Zp˚ usob˚ u konstrukce pˇrekladaˇc˚ u je v´ıce, ale nejˇcastˇeji se uplatˇ nuje dˇelen´ı programu na dvˇe ˇcásti. Prvn´ım je front-end, kter´ y je orientovan´ y na zdrojov´ y jazyk, a back-end, orientovan´ y na c´ılov´ y jazyk. Nˇekteré pˇrekladaˇcové systémy, jako napˇr´ıklad GCC, které maj´ı rozs´ ahlou 4

ˇcást optimalizac´ı nad mezikódem, s touto ˇcást´ı pracuj´ı jako se samostatnou [16] a naz´ yvaj´ı ji middle-end.

2.2.1

Front-end

V ˇcásti pˇrekladaˇce nazvané front-end se obvykle provádˇej´ı tyto kroky: lexikáln´ı anal´ yza, syntaktická anal´ yza, sémantická anal´ yza a pˇreklad do mezikódu. Konstrukce front-endu je silnˇe vázána na zdrojov´ y jazyk a mˇela by b´ yt nezávislá na c´ılovém jazyce. Lexik´ aln´ı anal´ yza ˇ ast pˇrekladaˇce provádˇej´ıc´ı lexik´ C´ aln´ı anal´ yzu se naz´ yvá lexikáln´ı analyzátor (angl. scanner ). Lexikáln´ı anal´ yza je u ´vodn´ı krok pˇrekladu, kter´ y v ˇcistém textu rozeznává tzv. lexémy (angl. tokeny) – prvky zdrojového jazyka. Ty následnˇe pˇredává syntaktickému analyz´ atoru. Lexik´ aln´ı analyzátory b´ yvaj´ı implementovány obvykle pomoc´ı regulárn´ıch v´ yraz˚ u. Pro tvorbu scanner˚ u jsou bˇeˇznˇe pouˇz´ıvané automatizované nástroje, napˇr. Lex [13]. Syntaktick´ a anal´ yza Syntaktická anal´ yza rozeznává v sekvenci lexikáln´ıch symbol˚ u syntaktickou strukturu podle pravidel gramatiky pˇr´ısluˇsného jazyka. V´ ystup této ˇcásti pˇrekladaˇce zachycuje strukturu programu ve tvaru vhodném k dalˇs´ımu zpracován´ı, typicky ve tvaru derivaˇcn´ıho stromu. ˇ asti pˇrekladaˇce provádˇej´ıc´ı syntaktickou anal´ C´ yzu se ˇr´ıká syntaktick´ y analyzátor (angl. parser ). Metod sestrojen´ı syntaktického analyzátoru je v´ıce. Základn´ımi dvˇema pˇr´ıstupy (které se pak dále dˇel´ı) jsou pˇr´ıstup shora-dol˚ u a zdola-nahoru. R˚ uzné pˇr´ıstupy [10] k sestrojen´ı syntaktického analyzátoru produkuj´ı parsery schopné zpracovat r˚ uznˇe sloˇzité gramatiky. Parsery se ˇcasto generuj´ı automatizovan´ ymi nástroji, napˇr. Yacc [12]. S´ emantick´ a anal´ yza Sémantick´ y analyzátor v derivaˇcn´ım stromu rozeznává a zpracovává informace o v´ yznamu pˇr´ıkaz˚ u. Uplatˇ nuje sémantická omezen´ı a oznamuje chyby v sémantice programu. Pˇ reklad do mezik´ odu Vˇetˇsina pˇrekladaˇc˚ u nepˇrekládá pˇr´ımo z jednoho jazyka do druhého (i kdyˇz i takové pˇrekladaˇce existuj´ı), ale pouˇz´ıvaj´ı jeˇstˇe tˇret´ı intern´ı reprezentaci. Existuj´ı dva základn´ı typy intern´ı reprezentace: [6] • Syntaktické a jiné stromy. V tomto pˇr´ıpadˇe je intern´ı reprezentace generov´ ana jako v´ ystup fáz´ı syntaktické a sémantické anal´ yzy. • Serializovaná reprezentace. V´ ystup sémantické anal´ yzy se pˇrevede na posloupnost instrukc´ı jazyka intern´ı reprezentace. Typick´ ym pˇr´ıkladem je tˇr´ıadresov´ y kód. Sloˇzité pˇrekladaˇce mohou m´ıt i nˇekolik intern´ıch reprezentac´ı kódu [16]. V tom pˇr´ıpadˇe se ˇcást obsluhuj´ıc´ı mezikód obvykle neˇrad´ı do pˇredn´ı (front-end ), ale do stˇredn´ı vrstvy (middle-end ). Pˇrevody mezi intern´ımi reprezentacemi pˇredstavuj´ı sloˇzité ˇcásti pˇrekladaˇc˚ u, psané obvykle ruˇcnˇe.

5

2.2.2

Middle-end

Middle-end se naz´ yvá ta ˇcást pˇrekladaˇce, kde se na u ´rovni intern´ı reprezentace prov´ adˇej´ı optimalizace a jiné zmˇeny pˇr´ımo v logice programu. Jen nˇekteré projekty naz´ yvaj´ı tuto ˇca´st pˇrekladaˇce middle-end, jiné tento term´ın nepouˇz´ıvaj´ı a operuj´ı jen s dvˇema ˇcástmi. V této práci je term´ın middle-end pouˇz´ıván. Kromˇe operac´ı nad intern´ı reprezentac´ı programu prob´ıhaj´ı v této ˇcásti optimalizace, které maj´ı za u ´kol upravit program pro nˇejak´ y u ´ˇcel – obvykle k vyˇsˇs´ımu v´ ykonu nebo k minimalizaci velikosti v´ ysledného programu. Optimalizacemi se bl´ıˇze zab´ yvá ˇcást 2.3.

2.2.3

Back-end

Back-end je ˇcást vázaná na c´ılov´ y jazyk, obvykle strojov´ y kód nebo kód v aassembleru V´ ysledná podoba intern´ı reprezentace programu se zde pˇrevád´ı do c´ılového jazyka. Problémy ˇreˇsené v této fázi jsou velmi r˚ uzné, ale pˇr´ıkladem mohou b´ yt následuj´ıc´ı, které jsou nejobvyklejˇs´ı: • Efektivn´ı vyuˇzit´ı instrukˇcn´ı sady c´ılového procesoru, vˇcetnˇe sloˇzit´ ych a specializovan´ ych instrukc´ı. • Alokace registr˚ u. Vzhledem k v´ ykonu je vhodné maximum dat umist’ovat do registr˚ u m´ısto do pamˇeti. • Paralelizace. Vyuˇzit´ı moˇznost´ı c´ılové architektury k paraleln´ımu bˇehu vhodn´ ych ˇca´st´ı programu na multi/hyperskalárn´ıch procesorech, popˇr. systémech s v´ıce jádry nebo procesory.

2.3

Optimalizace

Rozˇs´ıˇrené programovac´ı jazyky a jejich sémantické konstrukce nejsou ze své podstaty vytvoˇrené pro optimáln´ı vyuˇzit´ı zdroj˚ u programy, které jsou v nich napsány. Jsou uzp˚ usobené primárnˇe k snadnému vyjádˇren´ı algoritmu ˇclovˇekem a jeho následnému pˇrekladu do strojového kódu. Pokud bychom pˇrekládali program jen jako sekvenci na sobˇe nezávisl´ ych pˇr´ıkaz˚ u a kaˇzd´ y pˇr´ıkaz doslovnˇe pˇreloˇzili do strojov´ ych instrukc´ı, vznikne mnoˇzstv´ı neefektivn´ıho kódu. Pro optimáln´ı vyuˇzit´ı zdroj˚ u (ˇcas, pamˇet’, m´ısto na disku) je tedy nutné program zefektivnit. Toto m˚ uˇze b´ yt provedeno bud’ programátorem, pokud pˇrizp˚ usob´ı svuj program poˇzadavk˚ um na optimáln´ı vyuˇzit´ı zdroj˚ u, nebo automaticky pˇrekladaˇcem. Pr´ avˇe v pˇrekladaˇc´ıch se skryvá velk´ y potenciál pro zefektivnˇen´ı programu. Bˇehem pˇrekladu m´ a pˇrekladaˇc k dispozici velmi detailn´ı informace o podobˇe pˇrekládaného programu. Tyto informace lze analyzovat a na základˇe této anal´ yzy automaticky rozeznávat instrukce, které lze vypustit nebo nahradit jin´ ymi bez zmˇeny funkce programu. Modern´ı pˇrekladaˇce obsahuj´ı rozsáhlou sadu ˇcasto velmi sloˇzit´ ych optimalizac´ı. Obecnˇe se optimalizac´ı naz´ yv´ a jak´ ykoliv proces na kterékoliv u ´rovni tvorby programu, kter´ y zefektivˇ nuje jeho vyuˇzit´ı kritick´ ych zdroj˚ u. V této práci se z d˚ uvodu jej´ıho zamˇeˇren´ı na pˇrekladaˇce pouˇz´ıvá term´ın “optimalizace” pro zmˇeny kódu, které automaticky vykon´ av´ a kompilátor pˇri pˇrekladu programu. Konkrétn´ım pˇr´ıkladem optimalizac´ı [6], které m˚ uˇze pˇrekladaˇc nad kódem provádˇet m˚ uˇze b´ yt eliminace mrtvého kódu, ˇs´ıˇren´ı konstant, nebo pˇr´ım´ y v´ ypoˇcet v´ yraz˚ u, jejichˇz v´ ysledek je znám uˇz v dobˇe pˇrekladu.

6

Kapitola 3

Chyby v pˇ rekladaˇ c´ıch a metody jejich hled´ an´ı Jako vˇsechny programy, i pˇrekladaˇce obsahuj´ı chyby. Tato kapitola se zab´ yvá chybami, které se vyskytuj´ı v pˇrekladaˇc´ıch, d˚ usledky jejich v´ yskytu, a metodami jejich hledán´ı.

3.1

Chyby v pˇ rekladaˇ c´ıch

Pˇrekladaˇc je d˚ uleˇzitou souˇcást´ı v´ yvojového ˇretˇezce. Chyby v nˇem tedy mohou m´ıt masivn´ı d˚ usledky. Takov´ ym m˚ uˇze b´ yt napˇr´ıklad zbrˇzdˇen´ı v´ yvoje programu, kdy mus´ı b´ yt k´ od, kter´ y pˇrekladaˇc nedokáˇze pˇreloˇzit, nahrazen jin´ ym. Jin´ ym pˇr´ıkladem m˚ uˇze b´ yt zanáˇsen´ı chyb vznikl´ ych ˇspatn´ ym pˇrekladem do programu, popˇr´ıpadˇe tich´ y pˇreklad neplatného k´ odu s nedefinovan´ ym chován´ım. Takové chyby se zvláˇstˇe ˇspatnˇe diagnostikuj´ı, protoˇze vyplynou na povrch v pˇreloˇzeném programu, nikoliv pˇrekladaˇci samém. Samotnému urˇcen´ı zdroje chyby v pˇrekladaˇci tedy pˇredch´ az´ı fáze, kdy se chyba hledá na nesprávném m´ıstˇe, coˇz zbyteˇcnˇe spotˇrebovává zdroje a pˇri pokusu o opravu m˚ uˇze zp˚ usobit zanesen´ı dalˇs´ı chyby.

3.1.1

Obecn´ e chyby v programech

Pˇrekladaˇce, zvláˇstˇe modern´ı pˇrekladaˇcové systémy pro vˇetˇs´ı mnoˇzstv´ı jazyk˚ u a architektur, jsou typicky velmi komplexn´ı programy. Jako takové jsou pochopitelnˇe náchylné pro v´ yskyt bˇeˇzn´ ych programátorsk´ ych chyb, stejn´ ych jako v jakémkoli jiném programu. Pro jazyk C jsou takov´ ymi typick´ ymi chybami napˇr´ıklad ˇspatná práce s ukazateli, ignorován´ı moˇzn´ ych chybov´ ych stav˚ u nebo nedostateˇcná opatˇren´ı pˇri práci s polemi koneˇcné délky. Rozˇs´ıˇrené pˇrekladaˇce (GCC, Visual C++ Compiler) tyto bˇeˇzné chyby, které by u obyˇcejného programu obvykle vedly ke zhroucen´ı nebo nedefinovanému chován´ı, zachytávaj´ı vnitˇrn´ımi mechanismy (zachytáván´ı signál˚ u, makra assert a jiné) a interpretuj´ı je jako tzv. ICE – Internal Compiler Error.

3.1.2

Chyby typick´ e pro pˇ rekladaˇ ce

Kromˇe bˇeˇzn´ ych chyb se v pˇrekladaˇc´ıch vyskytuj´ı chyby, které jsou pro nˇe specifické. Jedn´ a se obvykle o sémantické chyby – pˇrekladaˇc funguje tak, jak byl naprogramován, ale byl naprogramován ˇspatnˇe. Tyto chyby se daj´ı roztˇr´ıdit do nˇekolika kategori´ı a následnˇe klasifikovat. Open-source komunita zab´ yvaj´ıc´ı se pˇrekladaˇci obvykle pouˇz´ıvá kategorie, které definuje projekt GCC [1], nebo alespoˇ n kategorie velmi podobné. 7

Klasifikace chyb dle projektu GCC Accepts-invalid Pˇrekladaˇc tiˇse akceptuje a pˇreloˇz´ı neplatn´ y kód, i kdyˇz by ho mˇel odm´ıtnout. Chován´ı neplatného k´ odu nen´ı definováno a v´ ysledkem je nepˇredv´ıdatelné chov´ an´ı preloˇzeného programu. Jedná se o velmi váˇznou chybu – chyba se projev´ı vadn´ ym chován´ım pˇreloˇzeného programu a proces urˇcován´ı zdroje chyby je dlouh´ y a n´ aroˇcn´ y. Assemble-failure Pˇrekladaˇc selˇze pˇri generován´ı v´ ysledného kódu. D˚ uvody mohou b´ yt r˚ uzné, napˇr. dvojitá definice jednoho symbolu. Protoˇze se tento typ chyby projev´ı uˇz pˇri pˇrekladu, a to aˇz po fázi pˇrijet´ı kódu, jedná se o nepˇr´ıliˇs závaˇzn´ y typ chyby. Compile-time-hog Pˇreklad trvá neadekvátnˇe dlouho, nebo se nezastav´ı. Pˇr´ıˇcinou b´ yv´ a neoptimalizovav´ y pr˚ ubˇeh k´ odem, kdy se vlivem podoby vnitˇrn´ı reprezentace pˇrekladaˇc zacykl´ı nebo zvol´ı velmi neoptimáln´ı cestu. Jedná se o málo závaˇzn´ y typ chyby, vyvstane uˇz pˇri pouˇzit´ı pˇrekladaˇce a pomoc´ı profilovac´ıch n´ astroj˚ u nebo vnitˇrn´ı introspekce pˇrekladaˇce je moˇzné relativnˇe snadno neoptimáln´ı m´ısto programu odhalit. Diagnostic Selhán´ı diagnostického hláˇsen´ı. Pˇrekladaˇc nezobraz´ı chybové hláˇsen´ı nebo varován´ı, kdyˇz by mˇel, popˇr. je takové hláˇsen´ı chybné nebo zavádˇej´ıc´ı. ICE-on-invalid Pˇrekladaˇc se zhrout´ı pˇri zpracován´ı neplatného kódu. Jedná se o nepˇr´ıliˇs závaˇznou chybu. Neplatn´ y kód by mˇel b´ yt stejnˇe odm´ıtnut, takˇze zhroucen´ı pˇrekladaˇce je pouze chyba robustnosti pˇri oˇsetˇrován´ı neplatného kódu. ICE m˚ uˇze b´ yt zp˚ usobeno i bˇeˇznou programátorskou chybou. ICE-on-valid Pˇrekladaˇc se zhrout´ı pˇri zpracováván´ı platného kódu. Jedná se o z´ avaˇznou chybu. Platn´ y kód by mˇel b´ yt pˇreloˇzen, a selhán´ı v tomto u ´kolu je tedy selh´ an´ı základn´ıho u ´ˇcelu pˇrekladaˇce. Diagnostika b´ yvá obvykle nepˇr´ıliˇs obt´ıˇzná, s pouˇzit´ım modern´ıch programátorsk´ ych nástroj˚ u m˚ uˇze b´ yt pomˇernˇe snadné identifikovat m´ısto kde ke zhroucen´ı doˇslo a data nebo instrukce, které ho zp˚ usobily. ICE m˚ uˇze b´ yt zp˚ usobeno i bˇeˇznou programátorskou chybou. Link-failure Pˇrekladaˇc vygeneruje objekt, kter´ y nejde sestavit (slinkovat) s jin´ ym k´ odem. Jedná se o ménˇe závaˇznou variantu chyby wrong-code, protoˇze vyjde najevo uˇz pˇri linkován´ı programu, coˇz následuje obvykle hned po pˇrekladu. D˚ uvody selhán´ı sestaven´ı jsou podobné jako u chyby assemble-failure. Memory-hog Pˇrekladaˇc spotˇrebovává pˇri bˇehu neadekvátn´ı mnoˇzstv´ı pamˇeti. Pˇr´ıˇciny a ostatn´ı znaky jsou podobné jako u chyby compile-time-hog. Missed-optimization Pˇrekladaˇc nezaregistruje ˇcást kódu, kterou by mohl optimalizovat. Velmi ˇspatnˇe odhalitelná chyba, zejména z toho d˚ uvodu, ˇze se projevuje aˇz v niˇzˇs´ım v´ ykonu pˇreloˇzeného programu, coˇz je zpozorovatelné jen pˇri d˚ ukladném testov´ an´ı nebo opravdu v´ yrazném sn´ıˇzen´ı v´ ykonu. Závaˇznost závis´ı na velikosti sn´ıˇzen´ı v´ ykonu aplikac´ı. Register-allocator Chyba typu missed-opimization zp˚ usobená vadnou funkc´ı alok´ atoru registr˚ u. Pˇrekladaˇc v tomto pˇr´ıpadˇe nevyuˇzije moˇznosti uloˇzit hodnotu do registru m´ısto do pamˇeti, i kdyˇz by to v danou chv´ıli bylo moˇzné. Rejects-valid Pˇrekladaˇc odm´ıtne platn´ y kód. Jedná se o stˇrednˇe závaˇznou chybu, kter´ a brán´ı pouˇzit´ı kompilátoru. Diagnostika nen´ı nároˇcná, chyba se projevuje uˇz pˇri pˇrekladu. 8

Wrong-code Pˇrekladaˇc generuje vadn´ y kód – kód s jin´ ym v´ yznamem neˇz mˇel p˚ uvodn´ı platn´ y zdrojov´ y kód. Jedn´ a se o nejzávaˇznˇejˇs´ı chybu pˇrekladaˇce. Chyba se projevuje aˇz vadn´ ym chován´ım pˇreloˇzeného programu, pˇriˇcemˇz nen´ı moˇzné ve zdrojovém k´ odu vystopovat chybu – protoˇze tam ˇzádná nen´ı. Chybu je nutné izolovat a objevit na u ´rovni c´ılového jazyka pˇreloˇzeného programu, coˇz je zdlouhavé a nároˇcné. Klasifikace z´ avaˇ znosti chyb Tabulka 3.1 uvád´ı klasifikaci závaˇznosti chyb v pˇrekladaˇc´ıch, vypracovanou v rámci této práce. V u ´vahu byla brána tˇri hlediska – dopad na uˇzivatele, zp˚ usob, jak´ ym se chyba projev´ı, a diagnostika. Dopad na uˇzivatele byl rozdˇelen do tˇr´ı u ´rovn´ı: • N´ızký : Dopad na uˇzivatele je n´ızk´ y, nebrán´ı mu ve správném pouˇzit´ı pˇrekladaˇce. • Stˇredn´ı: Omezuje moˇznosti uˇzivatele a nut´ı jej pouˇz´ıvat nestandardn´ı ˇreˇsen´ı. Pˇreklad´ a programy které funguj´ı spr´ avnˇe, ale s urˇcit´ ymi omezen´ımi. • Vysoký : Zabraˇ nuje uˇzivateli v pouˇzit´ı pˇrekladaˇce, nebo generuje neplatné programy. Zp˚ usob, kter´ ym se chyba projev´ı, je také troj´ı: • Pˇri pˇrekladu: Chyba se objev´ı jiˇz pˇri pˇrekladu. • Po pˇrekladu: Chyba se projev´ı bezprostˇrednˇe po pouˇzit´ı v´ ystupu pˇrekladaˇce. • Neprojev´ı: Chyba se neprojev´ı v souvislosti s pˇrekladaˇcem. Diagnostiku dˇel´ıme také do tˇr´ı u ´rovn´ı: • Zjevné : Zjevnˇe se jedná o chybu pˇrekladaˇce. • Maskované : Chyba se objevuje pˇri pouˇzit´ı pˇrekladaˇce, ale zdá se, ˇze pˇrekladaˇc je v poˇrádku. • Skryté : Chyba je skrytá a projevuje se pˇri pouˇzit´ı v´ ysledného programu. Souvislost se ˇspatnou funkc´ı pˇrekladaˇce vyjde najevo aˇz pˇri d˚ ukladné anal´ yze defektu.

3.2

Hled´ an´ı a testovac´ı pokryt´ı r˚ uzn´ ych typ˚ u chyb

Obecné metody hledán´ı chyb v pˇrekladaˇc´ıch se v zásadˇe neliˇs´ı od metod pouˇz´ıvan´ ych pro jiné programy. Obt´ıˇz spoˇc´ıvá ve faktu, ˇze pˇrekladaˇce jsou programy s nekoneˇcn´ ym prostorem moˇzn´ ych vstup˚ u, a nav´ıc nen´ı moˇzné dopˇredu jednoznaˇcnˇe urˇcit, jak má pˇreklad vypadat – pro jeden vstupn´ı program P obvykle existuje v´ıce moˇzn´ ych ekvivalentn´ıch reprezentac´ı v c´ılovém kódu. To v´ yraznˇe sniˇzuje moˇznosti testován´ı správnosti v´ ystupu.

9

Tabulka 3.1: Klasifikace typ˚ u chyb v pˇrekladaˇc´ıch Typ chyby accepts-invalid assemble-failure compile-time-hog diagnostic ice-on-invalid ice-on-valid link-failure memory-hog missed-optimization register-allocator rejects-valid wrong-code

3.2.1

Dopad na uˇ zivatele Vysok´ y Vysok´ y Stˇredn´ı N´ızk´ y N´ızk´ y Vysok´ y Vysok´ y Stˇredn´ı/N´ızká Stˇredn´ı Stˇredn´ı Vysok´ y Vysok´ y

Zp˚ usob projevu Neprojev´ı se Po pˇrekladu Pˇri pˇrekladu Pˇri pˇrekladu Pˇri pˇrekladu Pˇri pˇrekladu Po pˇrekladu Pˇri pˇrekladu Neprojev´ı se Neprojev´ı se Pˇri pˇrekladu Neprojev´ı se

Diagnostika Skryté Maskované/Zjevné Zjevné Maskované Zjevné Zjevné Maskované/Zjevné Maskované Skryté Skryté Maskované/zjevné Skryté

Statick´ a anal´ yza

Statická anal´ yza je proces, kdy se zjiˇst’uj´ı informace o programu bez jeho spuˇstˇen´ı. M˚ uˇze se jednat o sbˇer dat anal´ yzou zdrojového kódu, reprezentace v mezikódu bˇehem pˇrekladu nebo anal´ yzu objektového a binárn´ıho tvaru pˇreloˇzeného programu. Konkrétn´ı metody jsou r˚ uzné – nejbˇeˇznˇejˇs´ı jsou nástroje, které analyzuj´ı zdrojov´ y kód a hledaj´ı vzorce indikuj´ıc´ı typické programátorské chyby, nebo nástroje typu lint, které hledaj´ı podezˇrelé sémantické konstrukce. Takové nástroje také dok´ aˇz´ı napˇr´ıklad nalézt vˇetve programu, které se nikdy neprovedou, nebo naopak takové, které se provedou vˇzdy, pˇrestoˇze jsou zanoˇreny v podm´ınˇeném pˇr´ıkazu. Moˇznost´ı hledan´ ych vzor˚ u je mnoho a je moˇzné staticky hledat i chyby, které nejsou jen obecné sémantické chyby, ale chyby v logice programu. Moˇznosti metod statické anal´ yzy pro testován´ı pˇrekladaˇc˚ u jsou omezené na hled´ an´ı chyb typu ICE, které jsou ˇcasto zp˚ usobeny bˇeˇzn´ ymi programátorsk´ ymi chybami.

3.2.2

Dynamick´ a anal´ yza

Dynamickou anal´ yzou se naz´ yvá proces, kdy o programu z´ıskáváme informace jeho spouˇstˇen´ım. Spuˇstˇen´ım programu v prostˇred´ı virtuáln´ıho procesoru m˚ uˇzeme napˇr´ıklad detekovat chyby, které z kódu nemus´ı b´ yt zcela zjevné a tud´ıˇz je obt´ıˇzné je odhalit statick´ ymi metodami. Typick´ ym problémem, kter´ y je moˇzné odhalit pomoc´ı spuˇstˇen´ı jsou problémy soubˇehu (angl. race condition), popˇr´ıpadˇe problémy vzniklé nesprávn´ ym pouˇzit´ım pamˇeti v jazyce C. Pˇr´ıkladem nástroje pro dynamickou anal´ yzu program˚ u je soubor utilit valgrind. Obsahuje nástroje urˇcené pro detekci pamˇet’ov´ ych chyb, chyb spojen´ ych s vlákny, detektor soubˇeh˚ u, a profilovac´ı nástroje volán´ı funkc´ı a vyuˇzit´ı hromady (heapu). Valgrind [9] pouˇz´ıv´ a právˇe pˇr´ıstup virtuáln´ıho procesoru, kter´ y provád´ı testované instukce, ke kter´ ym jednotlivé nástroje pˇridávaj´ı svoje vlastn´ı informace pro anal´ yzu.

10

3.2.3

Metody testov´ an´ı pˇ rekladaˇ c˚ u c´ılen´ e na jejich typick´ e probl´ emy

Vˇsechny obecné nástroje pro zajiˇstˇen´ı kvality softwaru lze samozˇrejmˇe pouˇz´ıt i k hled´ an´ı chyb v pˇrekladaˇc´ıch – je to také software. Sofistikované nástroje dokáˇz´ı naj´ıt mnoho chyb, ale nejsou c´ılené. Vzhledem k nejednoznaˇcnosti správného v´ ystupu pˇrekladaˇce obecné metody selhávaj´ı v detekci sémantick´ ych chyb, zejména správnˇe implementovan´ ych ˇspatn´ ych princip˚ u. Tyto chyby lze naj´ıt jen velmi ˇspatnˇe. Neexistuje mnoho metod, kter´ ymi je moˇzné urˇcit, zda pˇrekladaˇc pro nˇejak´ y vstup vytvoˇril správn´ y v´ ystup. Jednou z cest je pokr´ yt kaˇzdou metodu nebo funkci uvnitˇr pˇrekladaˇce, která nˇejak manipuluje s kódem, kvalitn´ımi jednotkov´ ymi testy. Pokud jsou jednotlivé ˇcásti pˇrekladaˇce navrˇzeny dostateˇcnˇe ortogonálnˇe, a kaˇzdá metoda nebo funkce má jasnˇe definované vstupy, v´ ystupy a ˇcinnost, pak je moˇzné jednotkov´ ymi testy zjiˇst’ovat, zda kaˇzd´ y takov´ y u ´sek kódu dˇelá to, co je definováno. Zde plat´ı, ˇze správná ˇcinnost systému tvoˇreného mnoha menˇs´ımi jednotkami (které musej´ı b´ yt co nejv´ıce ortogonáln´ı) se ovˇeˇruje snadnˇeji [11], pokud ovˇeˇrujeme ˇcinnost jednotliv´ ych souˇcást´ı, neˇz pokud bychom ovˇeˇrovali chován´ı celého systému. Jinou metodou, jej´ımˇz pouˇzit´ım je moˇzné se zamˇeˇrit právˇe na správn´ y v´ ystup pˇrekladaˇce, je tzv. fuzz testing, na kterém byl zaloˇzen systém dále navrˇzen´ y v této práci. Princip této medody a jej´ı praktická implementace pro toto pouˇzit´ı je popsán v následuj´ıc´ı kapitole.

11

Kapitola 4

N´ avrh syst´ emu pro testov´ an´ı pˇ rekladaˇ c˚ u V této kapitole pˇredstav´ıme návrh metody pro testován´ı správnosti v´ ystupu pˇrekladaˇce a implementaci systému, kter´ y tuto metodu vyuˇz´ıvá.

4.1

Principy metody fuzz testing

Základem celého systému je metoda zvaná fuzz testing. Jedná se o metodu testován´ı typu u, které jsou black-box 1 , kdy se pro program generuje velké mnoˇzstv´ı testovac´ıch vstup˚ programem zpracovány. Chován´ı programu se poté analyzuje. Je jasné, ˇze zcela n´ ahodnˇe generovan´ y vstup bude pravdˇepodobnˇe neplatn´ y, a proto se za selhán´ı povaˇzuje zhroucen´ı programu. Pokud program dokáˇze náhodná data jakkoliv zpracovat, v´ ysledkem testu je u ´spˇech. V´ yhodou této metody je jej´ı aˇz triviáln´ı implementace a automatizace. Je snadné generovat testovac´ı pˇr´ıpady, pˇredkládat je program˚ um a zjiˇst’ovat, zda se zhrout´ı. Velk´ a rychlost generován´ı testovac´ıch pˇr´ıpad˚ u znamená, ˇze je moˇzné otestovat mnoho pˇr´ıpad˚ uv relativnˇe krátkém ˇcase. To zvyˇsuje pravdˇepodobnost, ˇze nˇekterá náhodná data aktivuj´ı dosud skrytou chybu v programu, kterou spust´ı jen data s urˇcit´ ymi charakteristikami. Z´ aroveˇ n tato metoda dokáˇze program vystavovat podm´ınkám, jaké by ˇclovˇek-tester pravdˇepodobnˇe nevytvoˇril. ´ celem testu samozˇrejmˇe nen´ı zjiˇst’ovat prost´ Uˇ y fakt, zda program dokáˇze zvládnout libovoln´ y neplatn´ y vstup. Prav´ ym d˚ uvodem je, ˇze zhroucen´ı programu na jak´ ychkoliv datech m˚ uˇze ukazovat na neoˇsetˇrenou speciáln´ı situaci, zpravidla typu pˇreteˇcen´ı zásobn´ıku (buffer overflow ).2 Vzhledem k tomu, ˇze chyby tohoto typu jsou hlavn´ım zdrojem bezpeˇcnostn´ıch problém˚ u, je vhodné takto testovat zejména pro s´ıt’ové sluˇzby a jiné programy, které dost´ avaj´ı data ke zpracován´ı po s´ıti nebo z jiného ned˚ uvˇeryhodného zdroje. Schopnost zhroutit server s´ıt’ové sluˇzby pouh´ ym pˇredloˇzen´ım speciáln´ıch dat je bezpeˇcnostn´ı chyba sama o sobˇe [15]. Fuzz testing je moˇzné pouˇz´ıt velmi c´ılenˇe, a to i na pˇrekladaˇce. Pˇr´ıkladem m˚ uˇze b´ yt práce Christiana Lindiga [14], kter´ y vytvoˇril program, testuj´ıc´ı dodrˇzován´ı volac´ıch konvenc´ı pˇrekladaˇci jazyka C pro r˚ uzné architektury. Pˇri testován´ı samotném dokázal velmi rychle naj´ıt chyby ve zpracován´ı sloˇzitˇejˇs´ıch struktur v pˇr´ıpadˇe, ˇze byly pouˇzity jako variadick´ y 1 black-box je testovac´ı metoda zamˇeˇren´ a na zkoum´ an´ı chov´ an´ı systému na z´ akladˇe jeho vnˇejˇs´ıch projev˚ u, bez znalosti vnitˇrn´ı implementace. 2 buffer overflow je chyba, kdy se program pokouˇs´ı zapsat data za hranice m´ısta v pamˇeti, které je jim vyhrazeno [8]

12

argument [18]. Zde navrˇzen´ y systém pro testován´ı pˇrekladaˇc˚ u se zamˇeˇruje na schopnost pˇrekladaˇce dodat správnou reprezentaci programu v c´ılovém jazyce. Vzhledem k tomuto zámˇeru je nutné jednoduchou koncepci fuzz testován´ı rozˇs´ıˇrit. V pˇr´ıpadˇe, ˇze bychom generovali zcela náhodná data, byla by naprostá vˇetˇsina vstupn´ıch dat neplatn´ ym kódem, kter´ y by pˇrekladaˇc mˇel odm´ıtnout. Byla by tedy testována pouze ta ˇcást kódu pˇrekladaˇce, která odm´ıt´ a neplatné vstupy. Je nutné sestrojit generátor n´ ahodného platného kódu zdrojového jazyka, kter´ y pˇrekladaˇc nebude m´ıt problém pˇreloˇzit. T´ım se pokr´ yvá cel´ y proces pˇrekladu programu a je tak moˇzné aktivovat chyby v kaˇzdém kódu, kter´ y je zapojen do procesu pˇrekladu. Dalˇs´ım problémem, kter´ y je pak zapotˇreb´ı rozˇreˇsit, je zjiˇst’ován´ı, zda je v´ ystup pˇrekladaˇce platn´ y. Jak bylo ˇreˇceno v ˇcásti 3.2, pro jeden program obvykle existuje v´ıce platn´ ych pˇreklad˚ u, v závislosti napˇr. na pouˇzitém pˇrekladaˇci, optimalizaˇcn´ıch procesech, nebo na u ´rovni, s jakou pˇrekladaˇc dokáˇze vyuˇz´ıt specializovan´ ych instrukc´ı c´ılového jazyka (instrukc´ı procesoru). Nen´ı tedy moˇzné porovnávat samotn´ y v´ ystup, protoˇze nem˚ uˇzeme jednoznaˇcnˇe urˇcit, zda je pˇreklad správn´ y nebo ne. Pˇr´ıstup naˇseho systému je pˇreloˇzit program dvakr´ at nebo v´ıcekrát v odliˇsn´ ych podm´ınkách, coˇz m˚ uˇze b´ yt pˇreloˇzen´ı jin´ ym pˇrekladaˇcem, nebo pˇreloˇzen´ı stejn´ ym pˇrekladaˇcem s odliˇsn´ ym nastaven´ım. Pˇreloˇzené programy se spust´ı a zaznamená se jejich v´ ystup. Program by mˇel produkovat stejn´ y v´ ystup bez ohledu na to, jak´ ym pˇrekladaˇcem byl preloˇzen. Testem je tedy srovnán´ı obou v´ ystup˚ u, popˇr´ıpadˇe jin´ a pomocná kritéria (porovnán´ı u ´spˇeˇsnosti pˇrekladu nebo zp˚ usobu ukonˇcen´ı programu). Pokud je u ´spˇeˇsnost pˇrekladu a v´ ystup pˇreloˇzeného programu stejn´ y, pak je v´ ysledkem testu u ´spˇech. Pokud se liˇs´ı, pak to m˚ uˇze indikovat chybu v jednom z pˇrekladaˇc˚ u, protoˇze je nepravdˇepodobné, ˇze by stejná chyba byla pˇr´ıtomná v obou na sobˇe nezávisl´ ych pˇrekladaˇc´ıch. Tomuto pˇr´ıstupu mus´ı b´ yt pˇrizp˚ usoben i generátor testovac´ıcho kódu, kter´ y by mˇel produkovat programy s deterministick´ ym chován´ım. Programy by mˇely také poskytovat na v´ ystup dostatek informac´ı o svém vnitˇrn´ım stavu, aby bylo moˇzné zjistit anomálie.

4.2

Celkov´ y n´ avrh a implementace

Navrˇzen´ y systém pro testován´ı je rozdˇelen na tˇri ˇcásti, spojené dohromady jednoduch´ ym rámcem. Prvn´ı a nejd˚ uleˇzitˇejˇs´ı ˇc´ ast´ı je generátor testovac´ıho zdrojového kódu. Systém je navrˇzen tak, aby se dal pouˇz´ıt jak´ ykoliv program, kter´ y vyprodukuje pouˇziteln´ y vstup. Obsahuje ale sv˚ uj vlastn´ı generátor kódu, jménem Spitter. V´ ystup generátoru je poté vstupem pro modul Builder, kter´ y vyprodukuje vˇsechny v´ ystupy k anal´ yze. Tyto v´ ystupy jsou poté analyzovány modulem Comparator, kter´ y rozhoduje, zda byla nalezena anomálie nebo ne. V pˇr´ıpadˇe ˇze ano, pak se zdrojov´ y kód a vˇsechny v´ ystupy uschovaj´ı k pozdˇejˇs´ı anal´ yze. Jeden test probˇehne velmi rychle, a proto je moˇzné v krátkém ˇcase otestovat velké mnoˇzstv´ı testovac´ıch pˇr´ıpad˚ u. T´ım je dosaˇzeno vˇetˇs´ıho pokryt´ı kódu testovan´ ych pˇrekladaˇc˚ u. Vˇetˇsina kódu v celém systému je napsána ve skriptovac´ım jazyce Python, ˇcást utilit je napsána v jazyce pˇr´ıkazového interpretu BASH. Oba interpretované jazyky byly zvoleny z d˚ uvodu snazˇs´ı implementace, zejména v pˇr´ıpadˇe generátoru testovac´ıho kódu jazyka C. Cel´ y systém je pˇrehlednˇe graficky znázornˇen na obrázku 4.1.

13

Obrázek 4.1: Schéma systému

14

4.3

Spitter

V´ ystupem Spitteru je program v jazyce C, kter´ y je v pozdˇejˇs´ıch fáz´ıch pˇrekládán a analyzován. Jedná se o ˇr´ızen´ y generátor náhodn´ ych vˇet jazyka C. Skládá se ze dvou hlavn´ıch ˇcást´ı, pojmenovan´ ych Director a Generator, a dalˇs´ıch tˇr´ı menˇs´ıch. Podrobnˇejˇs´ı popis vˇsech ˇcást´ı je uveden v této sekci.

4.3.1

Gener´ ator

Gener´ ator je modul, obsahuj´ıc´ı jednu tˇr´ıdu. Jediné, co generator provád´ı je tvorba náhodn´ ych vˇet podle gramatiky. Princip generátoru je totoˇzn´ y [17] s konstrukc´ı syntaktického analyzátoru pomoc´ı techniky rekurzivn´ıho sestupu, jen postup je obrácen´ y. Parser uˇz´ıvaj´ıc´ı rekurzivn´ı sestup je program, kter´ y se skládá ze vzájemnˇe rekurzivn´ıch funkc´ı, které rozeznávaj´ı jednotlivé jazykové konstrukce. Schéma syntaktického analyzátoru pak kop´ıruje podobu gramatiky jazyka. Generátor je implementován podobnˇe. Implementuje metodu generate(symbol), kter´ a z´ısk´ a od Directoru seznam moˇzn´ ych rozvoj˚ u. Z nich se náhodnˇe vybere jeden rozvoj. N´ ahodn´ y v´ ybˇer je ovlivnˇen váhami, které mohou b´ yt jednotliv´ ym rozvoj˚ um v seznamu pˇriˇrazeny. Rozvoj je reprezentován dalˇs´ım seznamem, kter´ y obsahuje vˇsechny symboly v rozvoji. Pro kaˇzd´ y symbol v rozvoji se provede následuj´ıc´ı operace: pokud se jedná o terminál, pak se pˇr´ımo zap´ıˇse do v´ ystupn´ıho bufferu, kter´ y udrˇzuje jiˇz vygenerované symboly. V pˇr´ıpadˇe, ˇze se jedná o neterminál, pak se pro nˇej rekurzivnˇe zavolá metoda generate a návratov´ a hodnota se zap´ıˇse do bufferu. V pˇr´ıpadˇe ˇze se jedná o voliteln´ y terminál, pak se n´ ahodnˇe zjist´ı, zda se bude symbol generovat a v pˇr´ıpadˇe ˇze ano, pak je postup stejn´ y jako u netery princip, kter´ y minálu. Pˇrehlednˇe to ukazuje pseudokód 4.3.1. Jedná se o velmi zjednoduˇsen´ znázorˇ nuje jen samotné generován´ı. Skuteˇcná implementace je sloˇzitˇejˇs´ı, obsahuje dalˇs´ı obsluˇzn´ y kód (logován´ı a oˇsetˇrován´ı speciáln´ıch situac´ı), a nav´ıc funkci návratu k pˇredchoz´ım verz´ım, pokud nˇejak´ y symbol z nˇejakého d˚ uvodu nemohl b´ yt vygenerován (tzv. backtracking). Tato funkce, pˇrestoˇze je v generátoru implementována, nen´ı systémem vyuˇz´ıv´ ana, protoˇze s n´ı nedokáˇze korektnˇe pracovat vrstva Director. Pokud by toto omezen´ı bylo odstranˇeno, umoˇznilo by to pouˇz´ıt agresivnˇejˇs´ı potlaˇcován´ı rekurzivn´ıch problém˚ u popsan´ ych n´ıˇze, protoˇze by jiˇz nebylo nutné ponechávat kaˇzdému symbolu alespoˇ n jeden rozvoj i v pˇr´ıpadˇe, ˇze i ten by byl za normáln´ıch okolnost´ı podle konfigurace vypuˇstˇen. Jednoduch´ y generátor sestrojen´ y v´ yˇse popsan´ ym zp˚ usobem trp´ı v´ yrazn´ ymi problémy v pˇr´ıpadˇe, ˇze generovaná gramatika obsahuje pravidla, která jsou rekurzivn´ı. V programovac´ıch jazyc´ıch jde zejména o pravidla popisuj´ıc´ı v´ yrazy, kdy operandem vˇetˇsiny oper´ ator˚ u mohou b´ yt znovu dalˇs´ı v´ yrazy. V gramatice jazyka C [18] jsou v´ yrazy popsány vˇetˇs´ım mnoˇzstv´ım pravidel, jejichˇz hierarchie vyjadˇruje prioritu operátor˚ u. Vˇsechna tato pravidla jsou rekurzivn´ı, a pravidlo na nejniˇzˇs´ı u ´rovni obsahuje rozvoj se symbolem v´ yrazu opˇet na u ´rovni nejvyˇsˇs´ı. V tomto konkrétn´ım pˇr´ıpadˇe bˇehem generován´ı docházelo k masivn´ımu zanoˇrován´ı generovan´ ych v´ yraz˚ u a k dosaˇzen´ı maximáln´ı hloubky rekurzivn´ıch volán´ı funkc´ı v interpretu jazyka Python. Tyto problémy byly vyˇreˇseny ve vrstvˇe Director pomoc´ı nˇekolika technik b´l´ıˇze popsan´ ych v sekci 4.3.2.

4.3.2

Director

´ Director je nejrozsáhlejˇs´ı modul z celého systému. Ukolem Directoru je ˇr´ıdit funkci generátoru takov´ ym zp˚ usobem, aby v´ ystupem byl validn´ı a semánticky správn´ y kód. Funkce directoru jsou zaloˇzeny na tzv. sémantick´ ych jednotkách. 15

Obrázek 4.2: Pseudokód principu metody generate def generate ( symbol ): director . reportStart ( symbol ) productions = director . getSymbol ( symbol ) selected = w e ig ht e dR a nd om S el e ct io n ( productions ) buffer = "" for symbol in selected : if symbol . type == TERMINAL : buffer += symbol . value elif symbol . type == OPTIONAL_NONTERMINAL and rand (0 ,1) < symbol . probability : buffer += generate ( symbol ) elif symbol . type == NONTERMINAL : buffer += generate ( symbol ) buffer = director . reportFinish ( symbol , buffer ) return buffer

S´ emantick´ e jednotky Sémantická jednotka je struktura, která udrˇzuje informace o podobˇe jedné sémantické konstrukce jazyka C. Sémantickou konstrukc´ı rozum´ıme ˇcást programu, která nese nˇejakou informaci, která mus´ı b´ yt dostupná i jin´ ym sémantick´ ym jednotkám (napˇr. pˇr´ıkaz deklarace promˇenné nese informaci, ˇze v nadˇrazeném bloku je moˇzné pouˇz´ıt identifikátor promˇenné ve v´ yrazech, jejichˇz typ je s typem promˇenné kompatibiln´ı). Director buduje zásobn´ık takov´ ychto sémantick´ ych jednotek a na základˇe informac´ı, které jsou v nˇem obsaˇzeny, ˇr´ıd´ı generován´ı. Jednotlivé vlastnosti sémantick´ ych jednotek jsou urˇcovány ihned, jak jsou generátorem vytvoˇreny a metodou reportFinish pˇredány pˇr´ısluˇsné symboly. Pˇresn´ y princip a informace o jednotliv´ ych sémantick´ ych jednotkách budou pops´ any n´ıˇze. Sémantická jednotka udrˇzuje následuj´ıc´ı informace: Promˇ enn´ e Udrˇzuje informaci, zda daná sémantická jednotka vytváˇr´ı rámec (scope) pro definici promˇenn´ ych. Implementován je jako slovn´ık, jehoˇz kl´ıˇcem je datov´ y typ a hodnotou je seznam identifikátor˚ u oznaˇcuj´ıc´ıch promˇenné tohoto typu v tomto r´ amci. Hodnota None znamená, ˇze tato sémantická jednotka vlastn´ı rámec nevytváˇr´ı. Identifik´ ator Udrˇzuje informaci, zda daná sémantická jednotka má vlastn´ı identifik´ ator. Implementován je jako ˇretˇezec, obsahuj´ıc´ı pˇr´ısluˇsn´ y identifikátor. Pokud mu zat´ım identifikátor nebyl pˇriˇrazen (coˇz je pˇr´ıpad napˇr. sémantické jednotky deklarace pˇredt´ım, neˇz je vygenerován symbol urˇcuj´ıc´ı identifikátor), je ˇretˇezec prázdn´ y. Hodnota None znamená, ˇze daná sémantická jednotka nem˚ uˇze m´ıt pˇriˇrazen identifikátor. Typ Datov´ y typ sémantické jednotky, kter´ y zároveˇ n omezuje datov´ y typ jej´ıch podsymbol˚ u. M˚ uˇze nab´ yvat tˇechto hodnot: • True. Znamená “jak´ ykoliv typ”. Tato sémantická jednotka nijak neomezuje typ sv´ ych podsymbol˚ u.

16

• False. Tato sémantická jednotka omezuje typ sv´ ych podsymbol˚ u, ale jeˇstˇe j´ı nebyl pˇriˇrazen pˇr´ısluˇsn´ y typ. • None. Znamená “nezaj´ımá se o typ”. Tyto jednotky jsou z hlediska typu zcela ignorovány. Pˇrej´ımaj´ı tak vlastnˇe typ sv´ ych nadˇrazen´ ych sémantick´ ych jednotek. • . Sémantická jednotka omezuje typy sv´ ych podsymbol˚ u na datové typy kompatibiln´ı se sv´ ym datov´ ym typem. N´ avratov´ y typ Podobnˇe jako typ, jen udrˇzuje informaci o návratovém typu funkce a niˇc´ım neomezuje generován´ı podsymbolu, kromˇe urˇcen´ı typu v´ yrazu v pˇr´ıkazu return. Funkce Informace a jejich reprezentace jsou podobné, jako je tomu u rámce pro promˇenné. Rámec pro funkce vytváˇr´ı pouze nejvyˇsˇs´ı semantická jednotka (Program). Kromˇe identifikátoru a návratového typu se uchovává jeˇstˇe informace o poˇctu a datov´ ych typech parametr˚ u. Parametry Opˇet sémantická informace specifická pro funkce. Uchovává se v podobˇe seznamu dvojic (datov´ y typ, identifik´ ator). Funkce Directoru Director slouˇz´ı jako vrstva mezi abstraktn´ı reprezentac´ı gramatiky v programu a samotn´ ym gener´ atorem, která modifikuje podobu gramatick´ ych pravidel pˇredt´ım, neˇz je gener´ atoru pˇredá. Obsahuje dvˇe základn´ı vnitˇrn´ı struktury, ve kter´ ych udrˇzuje aktuáln´ı podobu sémantiky programu: Z´ asobn´ık symbol˚ u Udrˇzuje podobu aktuáln´ı vˇetve derivaˇcn´ıho stromu generovaného programu. Tato data jsou pouˇzita k omezen´ı problém˚ u spojen´ ych s rekurz´ı nˇekter´ ych gramatick´ ych symbol˚ u. Z´ asobn´ık s´ emantick´ ych jednotek Udrˇzuje podobu aktuáln´ı vˇetve stromu sémantick´ ych jednotek. Princip sémantick´ ych jednotek je popsán n´ıˇze. Tato data slouˇz´ı k zaznamenáván´ı sémantické podoby programu a ˇr´ızen´ı generován´ı na jej´ım základˇe. Funkce directoru spoˇc´ıvá v poskytován´ı sluˇzby pro samotn´ y generátor. Cel´ y proces pro jeden symbol funguje následovnˇe: 1. Director pˇrijme od generátoru volán´ı metody reportStart(symbol). Director zaˇrad´ı symbol na zásobn´ık symbol˚ u. V pˇr´ıpadˇe ˇze se jedná o symbol, kter´ y vytváˇr´ı sémantickou jednotku, pak ji vytvoˇr´ı, pˇriˇrad´ı j´ı pˇr´ısluˇsné parametry a zaˇrad´ı na z´ asobn´ık sémantick´ ych jednotek. 2. Director pˇrijme od generátoru volán´ı metody getSymbol(symbol), kterou gener´ ator ˇzádá o váˇzen´ y seznam moˇzn´ ych rozvoj˚ u pro symbol. Director zjist´ı tento seznam z gramatického pravidla, které z´ıská od modulu 4.3.4. Poté analyzuje aktuáln´ı vrcholy obou vnitˇrn´ıch zásobn´ık˚ u, a na jejich základˇe m˚ uˇze do seznamu pˇridat nové rozvoje nebo nˇekteré odebrat. Je také moˇzné zmˇenit podobu nebo v´ ahu nˇekter´ ych pravidel. Takto zmˇenˇen´ y seznam poté vrát´ı generátoru. Zmˇeny, které Director provád´ı, jsou pro kaˇzdou sémantickou jednotku jiné, coˇz je d˚ uvod, proˇc je Director jako modul z´ avisl´ y na jazyce, kter´ y se má generovat – algoritmus provádˇen´ ych zmˇen je popsán pˇr´ımo programem, nikoliv vstupem programu nebo metadaty.

17

3. Director dále provád´ı tento proces pro vˇsechny podsymboly aktuálnˇe generovaného symbolu. Pro nˇekteré sémantické jednotky oˇcekává konkrétn´ı vygenerované podsymboly. Jejich hodnotami pak nastavuje vlastnosti takové sémantické jednotky. 4. Director pˇrijme od generátoru volán´ı metody reportFinish(symbol, expanded), kterou generátor oznamuje ukonˇcen´ı generován´ı jednoho symbolu, a také pˇred´ av´ ak posledn´ım u ´pravám podobu vygenerovaného symbolu v parametru expanded. Director vyjme pˇr´ısluˇsn´ y symbol ze zásobn´ıku a v pˇr´ıpadˇe, ˇze se jedná o symbol vytv´ aˇrej´ıc´ı sémantickou jednotku, i ze zásobn´ıku sémantick´ ych jednotek. Pˇr´ıpadnou sémantickou jednotku zpracuje (m˚ uˇze napˇr. definovat nebo zmˇenit vlastnost nˇekteré jiné, existuj´ıc´ı hloubˇeji v zásobn´ıku). V´ yslednou podobu symbolu m˚ uˇze poté jeˇstˇe zmˇenit a nakonec ji jako uˇz zcela koneˇcnou vrát´ı generátoru. I zde jsou zpracován´ı a provedené zmˇeny specifické pro kaˇzdou sémantickou jednotku. Jednotlivé provádˇené akce jsou pops´ any v´ yˇse u popisu samotn´ ych sémantick´ ych jednotek. Implementovan´ e s´ emantick´ e jednotky pro jazyk C Implementace generátoru v této práci pokr´ yvá pomˇernˇe omezenou mnoˇzinu prostoru jazyka C. Pokryty byly základn´ı konstrukce jazyka C, jako jsou pˇriˇrazovac´ı pˇr´ıkaz, r˚ uzná vˇetven´ı a cykly, a v´ yrazy zahrnuj´ıc´ı operace s promˇenn´ ymi a funkcemi. Podporovány jsou aritmetické a relaˇcn´ı v´ yrazy. Nejsou podporovány vˇsechny operátory a také operace se sloˇzen´ ymi (struct, union) nebo uˇzivatelsk´ ymi datov´ ymi typy. Také nejsou implementovány operace zahrnuj´ıc´ı pole a ukazatele. Náhodné generován´ı takového kódu vnáˇs´ı do chován´ı programu velké mnoˇzstv´ı entropie a sloˇzitost generátoru by v pˇr´ıpadˇe implementace vˇsech tˇechto vlastnost´ı jazyka C vzrostla do m´ıry, která je pro p˚ uvodn´ı u ´ˇcel (prototypová implementace urˇcen´ ak experimentáln´ı aplikaci fuzz testingu na pˇrekladaˇce) zbyteˇcná. Implementovány byly tedy sémantické jednotky uvedené v n´ asleduj´ıc´ım seznamu. V závorce za názvem jsou uvedeny symboly, které iniciuj´ı vznik této sémantické jednotky. Program (<program>) Sémantická jednotka reprezentuj´ıc´ı cel´ y program. Tvoˇr´ı rámec pro definici promˇenn´ ych i funkc´ı. Pˇri ukonˇcen´ı generován´ı se na zaˇcátek v´ ysledku pˇripoj´ı seznam deklarac´ı, které inicializuj´ı promˇenné, které nebyly inicializovány v samotném programu. Function () Sémantická jednotka reprezentuj´ıc´ı definici funkce. Netvoˇr´ı rámec pro definici promˇenn´ ych, pouze parametr˚ u. Pokud je na vrcholu z´ asobn´ıku sémantick´ ych jednotek a nemá jeˇstˇe definovanou pˇr´ısluˇsnou hodnotu, pak se prvn´ı následuj´ıc´ı vygenerovan´ y datov´ y typ pˇriˇrad´ı jako návratov´ y typ, identifikátor jako název funkce, a uloˇz´ı se vygenerované identifikátory parametr˚ u s datov´ ymi typy. V okamˇziku, kdyz se zaˇcne generovat blok funkce, jsou promˇenné reprezentuj´ıc´ı parametry pˇridány do rámce promˇenn´ ych v tomto bloku, takˇze je moˇzné s nimi v tˇele funkce pracovat. Po skonˇcen´ı generován´ı se funkce pˇridá do nejbliˇzˇs´ıho rámce funkc´ı v zásobn´ıku sémantick´ ych jednotek, aby mohla b´ yt v tomto rámci také volána. SimpleDeclaration (<declaration>) Reprezentuje jednoduchou deklaraci promˇenné bez jej´ı inicializace. Director pˇri jej´ım generován´ı oˇcekáv´ a vygenerované symboly typu a identifikátoru a pˇriˇrad´ı je do odpov´ıdaj´ıc´ıch pol´ı. Po ukonˇcen´ı se promˇenn´ a pˇrid´ a do nejbliˇzˇs´ıho rámce pro promˇenné a také do vnitˇrn´ıho seznamu neinicializovan´ ych promˇenn´ ych.

18

AssigningDeclaration ( : Reprezentuje deklaraci promˇenné s jej´ı inicializac´ı. Postup je stejn´ y jako v pˇr´ıpadˇe sémantické jednotky SimpleDeclaration, jen se po vygenerován´ı identifikátoru vygeneruje jeˇstˇe oper´ ator pˇriˇrazen´ı a v´ yraz, kter´ y má typ omezen na datové typy kompatibiln´ı s datov´ ym typem deklarované promˇenné. Block (, ) Reprezentuje blok, pouˇzit´ y jako tˇelo funkce, cyklu, nebo podmiˇ novac´ıho pˇr´ıkazu. Tvoˇr´ı rámec pro definice promˇenn´ ych. Tˇri symboly definuj´ıc´ı bloky se od sebe liˇs´ı pouˇzit´ım ukonˇcovac´ıch pojistek, coˇz je zajiˇstˇen´ı v´ ystupu a opuˇstˇen´ı bloku. Zachytávaj´ı se následuj´ıc´ı symboly: • , kter´ y zajist´ı vygenerován´ı pˇr´ıkaz˚ u pro vypsán´ı obsahu vˇsech promˇenn´ ych definovan´ ych v rámci bloku na jeho konci. Tento symbol se vyskytuje pro vˇsechny tˇri symboly tvoˇr´ıc´ı blok. • zajist´ı pˇr´ıkaz break pro opuˇstˇen´ı bloku v pˇr´ıpadˇe, ˇze tento uˇz probˇehl v´ıcekrát, neˇz je konfigurovatelná hodnota. To slouˇz´ı k zabr´ anˇen´ı v´ yskytu nekoneˇcn´ ych smyˇcek. Tento pˇr´ıkaz je vygenerov´ an na konci bloku v cyklech. • zajist´ı vygenerován´ı pˇr´ıkazu return pro opuˇstˇen´ı bloku v pˇr´ıpadˇe, ˇze tento uˇz probˇehl v´ıcekrát, neˇz je konfigurovateln´ a hodnota. To slouˇz´ı k zabr´ anˇen´ı v´ yskytu nekoneˇcn´ ych smyˇcek pˇri rekurzivn´ım vol´ an´ı funkce. Návratová hodnota v pˇr´ıpadˇe tohoto ukonˇcen´ı jen poˇcet pr˚ ubˇeh˚ u funkc´ı. Tento pˇr´ıkaz je vygenerován na zaˇcátku bloku funkce. Main (<main function>) Reprezentuje blok funkce main(). Vytváˇr´ı rámec pro definici promˇenn´ ych. V zásadˇe se jedná o stejnou sémantickou jednotku jako Block, ale na konci se kromˇe v´ ypisu promˇenn´ ych v rámci bloku vyp´ıˇs´ı také globáln´ı promˇenné. Assignment () Reprezentuje pˇriˇrazovac´ı pˇr´ıkaz. Pˇri generován´ı identifik´ atoru Director zjist´ı seznam vˇsech promˇenn´ ych, viditeln´ ych v aktuáln´ım rámci, a pro generátor vytvoˇr´ı seznam rozvoj˚ u, které je obsahuj´ı jako jedin´ y termináln´ı symbol. V pˇr´ıpadˇe ˇze neexistuje ˇzádná promˇenná, kterou by bylo moˇzné na levé stranˇe pˇriˇrazovac´ıho pˇr´ıkazu pouˇz´ıt, se pˇriˇrazovavac´ı pˇr´ıkaz zmˇen´ı na deklaraci nové promˇenné s inicializac´ı. V´ yraz na pravé stranˇe pˇriˇrazovac´ıho pˇr´ıkazu má datov´ y typ omezen na typ promˇenné na levé stranˇe. Expression (<expression>) Nejsloˇzitˇejˇs´ı sémantická jednotka, reprezentuj´ıc´ı v´ yraz. Obsahuje omezen´ı typu sv´ ych podsymbol˚ u, nˇekdy dané sémantikou pˇredem (parametr funkce), nˇekdy se urˇcuje aˇz po zjiˇstˇen´ı typu prvn´ı vygenerované konstanty, funkce, nebo promˇenné v nˇem (pˇr´ıkladem je operand v relaˇcn´ıch v´ yrazech). Pˇri jeho zpracován´ı Director provád´ı nˇekolik zmˇen pro zajiˇstˇen´ı pouˇzit´ı konstant, jiˇz vygenerovan´ ych promˇenn´ ych a funkc´ı, a také pro omezen´ı rekurzivity, kdy se nˇekteré symboly maj´ı sklony generovat donekoneˇcna. Provádˇej´ı se následuj´ıc´ı akce: • Generován´ı konstant ve v´ yrazu. V pˇr´ıpadˇe, ˇze je typ nadˇrazené sémantické jednotky omezen, je vylouˇcené generován´ı konstant, se kter´ ymi nen´ı typ v´ yrazu kompatibiln´ı. Rozsah ˇc´ıseln´ ych konstant nen´ı nijak oˇsetˇrován, protoˇze návratovou hodnotu v´ yrazu stejnˇe nelze urˇcit pˇredem vzhledem k funkc´ım, u kter´ ych nen´ı moˇzné zajistit, ˇze budou vracet hodnoty z platného rozsahu. Norma jazyka C pro celoˇc´ıselné datové typy definuje pravidlo, ˇze pouˇzit´ım hodnoty vyˇsˇs´ı neˇz rozsah datového typu se hodnota potichu urˇc´ı jako hodnota modulo rozsah, takˇze 19

chován´ı r˚ uzn´ ych pˇrekladaˇc˚ u by mˇelo v tˇechto pˇr´ıpadech b´ yt na stejném stroji stejné [18]. Pro datové typy float a double jsou nelegáln´ı hodnoty interpretovány jako INF nebo NaN, a také by mˇely b´ yt stejné. • Generován´ı promˇenn´ ych ve v´ yrazu. Pˇri tvorbˇe seznamu moˇzn´ ych rozvoj˚ u jsou zjiˇstˇeny vˇsechny viditelné promˇenné, které maj´ı typ kompatibiln´ı s typem v´ yrazu. Pro kaˇzdou promˇennou je poté vytvoˇren rozvoj s pravdˇepodobnost´ı generov´ an´ı rovnou jedné, kter´ y obsahuje indetifikátor promˇenné jako termináln´ı symbol. • Generován´ı volán´ı funkc´ı ve v´ yrazu. Pˇri tvorbˇe seznamu moˇzn´ ych rozvoj˚ u pro operandy jsou zjiˇstˇeny vˇsechny funkce s návratov´ ym typem kompatibiln´ım s typem v´ yrazu. Pro kaˇzdou funkci je poté vygenerován rozvoj obsahuj´ıc´ı identifikátor funkce jako terminál, a poté v závorkách uzavˇren´ y seznam umˇel´ ych neterminál˚ u. Kaˇzd´ y takov´ y neterminál má tvar <param/function/index>, napˇr pro volán´ı funkce double D(int,double,char) bude m´ıt pˇr´ısluˇsn´ y rozvoj podobu D(<param/D/0>, <param/D/1>, <param/D/2>). Generátor nev´ı, ˇze tyto neterminály jsou pouˇzity pouze ve vnitˇrn´ım mechanismu Directoru a norm´ alnˇe poˇzádá o jejich rozvoje. Kdyˇz o nˇe poˇzádá, Director gener´ atoru vrát´ı jedin´ y rozvoj obsahuj´ıc´ı symbol <expression>. Typ sémantické jednotky, vytvoˇrené pro tento v´ yraz, bude nastaven na datov´ y typ index-tého parametru funkce function. Tyto informace Director zjist´ı v sémantické jednotce, v jej´ımˇz r´ amci je function definována. Vzhledem k tomu, ˇze je zbyteˇcné volat jednu funkci v´ıcekrát, je pouˇzit´ı vol´ an´ı funkce omezeno. Jakmile je jej´ı volán´ı pouˇzito v´ıcekr´ at neˇz je hodnota v konfiguraci, pak se uˇz jej´ı dalˇs´ı volán´ı generovat nebudou. • Omezen´ı rekurzivity. V´ yraz je ze své podstaty rekurzivn´ı – kaˇzd´ ym operandem m˚ uˇze b´ yt zase dalˇs´ı v´ yraz. To m˚ uˇze pˇri ˇspatné konfiguraci vést k neukonˇcen´ı procesu generován´ı, nebo jeho selhán´ı. Pro oˇsetˇren´ı této situace si Director udrˇzuje hloubku hierarchie aktuálnˇe generovan´ ych v´ yraz˚ u a od urˇcité konfigurovatelné hloubky zaˇcne pˇri generován´ı operand˚ u pravdˇepodobnostnˇe preferovat hodnoty pˇred dalˇs´ımi v´ yrazy. Se vzr˚ ustaj´ıc´ı hloubkou v´ yrazu také zvyˇsuje pravdˇepodobnost vygenerován´ı literáln´ı konstanty pˇred generován´ım promˇenn´ ych nebo funkc´ı.

4.3.3

Pˇ r´ıklad cel´ eho procesu

Director má na vrcholu zásobn´ıku sémantickou jednotku Block, která obsahuje jiˇz definované promˇenné int A, float B. V sémantické jednotce Program na dnˇe zásobn´ıku je také definována funkce int C(int). Director pˇrijme volán´ı reportStart(’assgn declaration’). Tento symbol vytváˇr´ı sémantickou jednotku AssigningDeclaration, Director ji vytvoˇr´ı a vloˇz´ı na zásobn´ık. Na následuj´ıc´ı volán´ı getSymbol(’assgn declaration’) vrát´ı rozvoj = <expression>. Následuje generován´ı typu, kter´ y nevytváˇr´ı sémantickou jednotku a jako rozvoje jsou pro nˇej vráceny jednotlivé datové typy. Director registruje volán´ı reportFinish(’type’, ’int’), zjist´ı ˇze SJ na vrcholu zásobn´ıku je AssigningDeclaration, a pˇriˇrad´ı j´ı vygenerovan´ y datov´ y typ, tedy ’int’. Dále je vygenerován identifik´ ator, a Director opˇet registruje aˇz volán´ı reportFinish(’identifier’, ’IDEN’). Stejn´ ym zp˚ usobem jako v pˇr´ıpadˇe typu pˇriˇrad´ı SJ na vrcholu zásobn´ıku identifikátor IDEN. Pˇri vol´ an´ı metody reportStart(’expression’) zjist´ı, ˇze aktuáln´ı sémantická jednotka je AssigningDeclaration s jiˇz urˇcen´ ym typem, kter´ ym je ’int’. Vytvoˇr´ı tedy SJ Expression, rovnou j´ı pˇriˇrad´ı typ ’int’ a zaˇrad´ı ji na zásobn´ık. Pˇri generován´ı podsymbol˚ u v´ yrazu je vˇzdy zjiˇstˇeno, ˇze nadˇrazená SJ má typ int a v nadˇrazen´ ych SJ, které vytváˇrej´ı rámce pro promˇenné jsou 20

definovány promˇenné A,B a funkce C. Director zjist´ı základn´ı pravidlo pro rozvoj operandu, které vypadá takto: ::= | | . Z tohoto rozvoje vyˇrad´ı rozvoj se symbolem floating constant, protoˇze nen´ı kompatibiln´ı s datov´ ym typem int. K rozvoji dále pˇriˇrad´ı rozvoj s identifikátorem A, ale ne identifikátorem B, opˇet z d˚ uvodu nekompatibiln´ıho typu. Nakonec pˇriˇrad´ı jeˇstˇe rozvoj obsahuj´ıc´ı volán´ı funkce C. V´ ysledn´ y seznam rozvoj˚ u vypadá takto: ::= | | | A | C(<param/A/0>. Na pˇr´ıpadné volán´ı metody reportStart(’param/A/0’) vytvoˇr´ı director SJ Expression s datov´ ym typem nultého parametru funkce A. Tyto informace jsou pˇr´ıtomné v sémantické jednotce Program na dnˇe zásobn´ıku. Dále se v tomto pˇr´ıpadˇe postupuje zase jako pˇri generován´ı v´ yrazu. Nakonec celého procesu je vol´ ana metoda reportFinish(’assgn declaration’, ’int IDEN = 168 + C(0/A)’). Pˇri vol´ an´ı této metody Director vyhledá v zásobn´ıku nejbliˇzˇs´ı SJ, která vytváˇr´ı rámec pro promˇenné, a vloˇz´ı do n´ı informaci o pˇr´ıtomnosti promˇenné IDEN s datov´ ym typem ’int’. Znamená to, ˇze následuj´ıc´ı SJ, které budou v rámci stejného bloku generovány, mohou s promˇennou IDEN pracovat.

4.3.4

Pomocn´ e moduly

Souˇcást´ı programu Spitter jsou také tˇri pomocné moduly. Tyto moduly obsluhuj´ı specifické ˇcásti programu, které pˇr´ımo nesouvisej´ı s generován´ım vˇet. Modul Grammar tvoˇr´ı abstraktn´ı vrstvu, ve které jsou uchovávány informace o gramatice. Modul Logger se star´ a o v´ ystup. Modul BNF Parser rozeznává v textovém souboru pravidla gramatiky definovan´ a v Backus-Naurovˇe Formˇe. Grammar Modul Grammar pˇredstavuje abstraktn´ı vrstvu uchovávaj´ıc´ı podobu gramatiky generovaného jazyka. Obsahuje tyto tˇr´ıdy reprezentuj´ıc´ı r˚ uzné elementy, pouˇzité pro popis gramatiky: • Element je bázová tˇr´ıda pro vˇsechny prvky gramatiky. Obsahuje pouze metody pro logován´ı, které mohou vyuˇz´ıvat modul Logger. • Symbol reprezentuje jeden symbol gramatiky. Jeho prvky jsou jméno a typ. Typ m˚ uˇze b´ yt terminál nebo neterminál. Pokud je typ symbolu terminál, pak se nevyuˇz´ıv´ a vlastnost jméno. • OptSymbol je potomkem tˇr´ıdy Symbol. Reprezentuje symbol, kter´ y má nav´ıc volitelnou moˇznost generován´ı, coˇz je ˇc´ıslo s plovouc´ı desetinnou ˇcárkou v intervalu < 0, 1 >. • Production reprezentuje jeden moˇzn´ y rozvoj neterminálu. Obsahuje pouze seznam symbol˚ u v poˇrad´ı, v jakém se maj´ı vygenerovat. 21

• Rule reprezentuje pravidlo. Obsahuje jméno neterminálu, pro kter´ y je urˇceno, a také seznam moˇzn´ ych rozvoj˚ u. Rozvoje mohou m´ıt váhu, která urˇcuje pomˇer pravdˇepodobnost´ı s jakou se vygeneruj´ı. • Grammar reprezentuje celou gramatiku. Obsahuje seznam neterminál˚ u, pro které existuj´ı pravidla. Obsahuje také seznam pravidel. Implementuje nav´ıc metodu pro ovˇeˇren´ı korektnosti gramatiky – zda pro kaˇzd´ y neterminál pouˇzit´ y na pravé stranˇe pravidla existuje pravidlo pro jeho generován´ı. Logger Modul Logger obsluhuje v´ ystup a logován´ı programu. Podstatnou vlastnost´ı je konfigurovatelnost smˇerován´ı obou v´ ystup˚ u. Vzhledem k povaze logován´ı ˇcinnosti generátoru umoˇzn ˇuje odsazován´ı v´ ystupu podle aktuáln´ı hloubky v derivaˇcn´ım stromu a také volbu u ´rovnˇe logován´ı. BNF Parser Modul BNF Parser obsluhuje ˇcten´ı a rozeznáván´ı pravidel gramatiky z textového vstupu a pˇredává je modulu Grammar. Jedná se o velmi jednoduch´ y modul, vyuˇz´ıvaj´ıc´ı lexik´ aln´ı a syntaktick´ y Ply [7].

4.4

Builder

Builder je ˇcást systému, která se stará o vytvoˇren´ı vˇsech v´ ystup˚ u, které se budou pozdˇeji Comparatorem analyzovat. Jedn´ a se o velmi jednoduch´ y skript, kter´ y jako parametr bere cestu k souboru a seznam znaˇcek konfigurac´ı pˇrekladaˇc˚ u, pro které se testovac´ı kód zkompiluje. Ze souboru s nastaven´ım potom naˇc´ıtá konfigurace pro spouˇstˇen´ı jednotliv´ ych pˇrekladaˇc˚ u. Kaˇzdá konfigurace mus´ı m´ıt unikátn´ı znaˇcku, podle které je moˇzné ji identifikovat. Konfigurace dále obsahuje znaˇcky, podle kter´ ych se urˇcuj´ı pozice zdrojového souboru a v´ ystupu v pˇr´ıkazu, kter´ y volá pˇrekladaˇc. Pˇreloˇzen´ y program je Builderem spuˇstˇen a jeho v´ ystup zaznamenán. Pokud se program sám neukonˇc´ı do nastaveného poˇctu vteˇrin, je mu odesl´ an signál SIGTERM. V´ ystupem builderu jsou soubory: • TAG.build obsahuje zprávy, které pˇrekladaˇc bˇehem zpracováván´ı zdrojového k´ odu vypsal na standardn´ı nebo chybov´ y v´ ystup. • TAG.buildresult obsahuje v´ ysledek pˇrekladu, tj. informaci, zda byl pˇreklad u ´spˇeˇsn´ y. • TAG je vlastn´ı spustiteln´ y soubor. • TAG.termination obsahuje informaci, zda se pˇreloˇzen´ y program ukonˇcil standardnˇe, nebo zda musel b´ yt ukonˇcen signálem. • TAG.output obsahuje v´ ystup pˇreloˇzeného programu po spuˇstˇen´ı.

4.5

Comparator

Comparator je jednoduch´ y modul, jehoˇz u ´kolem je porovnat v´ ystupy, které vytvoˇril modul Builder, a na jejich základˇe rozhodnout o tom, zda bude v´ ysledek testu to ˇze testované 22

pˇrekladaˇce uspˇely, nebo nˇekter´ y selhal. Selhán´ı dˇel´ı na nˇekolik druh˚ u, které se pozdˇeji uchovávaj´ı a reportuj´ı oddˇelenˇe. Tato selhán´ı jsou oznaˇcena jako anomálie. Existuj´ı tˇri druhy anomáli´ı: anomálie pˇrekladu (rozd´ılná u ´spˇeˇsnost pˇrekladu), anomálie ukonˇcen´ı (rozd´ıln´ y zp˚ usob ukonˇcen´ı) a koneˇcnˇe anomálie v´ ystupu (spuˇstˇené programy maj´ı odliˇsn´ y v´ ystup). Comparator nejprve porovná v´ ysledky pˇreklad˚ u. Pokud jsou odliˇsné, pak se v´ ysledek testu náhlás´ı jako anomálie pˇrekladu. Pˇr´ıpad kdy oba pˇreklady selˇzou je moˇzné nastavit jako anomálii i jako platn´ y v´ ysledek. Pokud pouˇz´ıváme generátor, o kterém v´ıme, ˇze produkuje vˇzdy jen naprosto validn´ı kód, pak je jakékoliv selhán´ı anomáli´ı a vˇsechny v´ ysledky se zachovaj´ı k anal´ yze ˇclovˇekem. Pro generátor produkuj´ıc´ı neplatn´ y kód je odm´ıtnut´ı pˇrekladu správnˇe funguj´ıc´ım pˇrekladaˇcem oˇcekávané a proto se za anomálii nepovaˇzuje. V pˇr´ıpadˇe ˇze nebyla objevena anomálie ve v´ ysledku pˇrekladu, porovná se zp˚ usob ukonˇcen´ı programu. Pokud se liˇs´ı, pak jsou prohláˇseny za anomálii ukonˇcen´ı. Stejnˇe jako u v´ ysledk˚ u pˇrekladu, i zde je moˇzné nastavit, jak´ ym zp˚ usobem se bude nakládat se stejn´ ymi, ale negativn´ımi v´ ysledky (pro tento pˇr´ıpad je to násilné ukonˇcen´ı). I v tomto pˇr´ıpadˇe, pokud m´ ame jistotu, ˇze generátor tvoˇr´ı programy, které by se mˇely ukonˇcit samy, je násilné ukonˇcen´ı pˇreloˇzeného programu anomáli´ı. Pokud nen´ı objevena anomálie ve dvou pˇredchoz´ıch kroc´ıch, pak se porovnávaj´ı v´ ystupy spuˇstˇen´ ych program˚ u. Zde se za anomálii povaˇzuj´ı uˇz jen rozd´ılné v´ ystupy. Oba v´ ystupy jsou volitelnˇe provˇeˇreny na pˇr´ıtomnost znak˚ u faleˇsného selhán´ı, kdy systém nahlás´ı anom´ alii, ’ která ale m˚ uˇze b´ yt zp˚ usobena bud jiˇz známou chybou, nebo jin´ ym znám´ ym nedeterministick´ ym chován´ım generovan´ ych program˚ u. Takov´ ym typick´ ym znakem je ukonˇcen´ı programu signálem SIGFPE3 , kter´ y nastává v pˇr´ıpadˇe dˇelen´ı nulou [15]. Toto dˇelen´ı nulou se ale m˚ uˇze nacházet ve v´ yrazu, kter´ y pˇrekladaˇc odoptimalizuje a potom se m˚ uˇze st´ at, ˇze jeden pˇreklad selˇze se signálem SIGFPE, ale druh´ y dobˇehne v poˇrádku. Ovˇeˇrován´ı na faleˇsné selhán´ı je moˇzno konfigurovat. V´ ystupem Comparatoru je návratov´ y kód, kter´ y urˇcuje, zda byla nalezena nˇejaká anom´ alie, a jej´ı typ v pˇr´ıpadˇe ˇze ano.

4.6

Pokryt´ı pro pˇ rekladaˇ ce specifick´ ych chyb navrˇ zen´ ym syst´ emem

V pˇr´ıpadˇe optimáln´ı implementace celého systému je moˇzné pˇredpokládat, ˇze dos´ ahneme takového pokryt´ı typ˚ u chyb v pˇrekladaˇc´ıch, jaké uvád´ı tabulka 4.1. Z tabulky je vidˇet, ˇze kvalitn´ı pokryt´ı pˇrináˇs´ı uˇz prvn´ı fáze porovnáván´ı, ihned pˇri pˇrekladu. Pro dobré pokryt´ı nen´ı tedy potˇreba generátor deterministického kódu, staˇc´ı platn´ y kód. Deterministick´ y v´ ystup je ale tˇreba pro detekci chyb typu wrong-code, na nˇeˇz je tato práce zamˇeˇrena. Pro pokryt´ı nˇekter´ ych chyb, které jsou oznaˇceny jako “Moˇzné” by byly tˇreba modifikace jednotliv´ ych ˇcást´ı.

3

sign´ al Floating Point Exception, indikuj´ıc´ı obecnou chybu pˇri operaci s ˇc´ıslem s plovouc´ı desetinnou ˇc´ arkou

23

Tabulka 4.1: Pokryt´ı typ˚ u chyb v pˇrekladaˇc´ıch navrˇzen´ ym systémem Typ chyby accepts-invalid assemble-failure compile-time-hog diagnostic ice-on-invalid ice-on-valid link-failure memory-hog missed-optimization register-allocator rejects-valid wrong-code

Pokryt´ı Moˇzné (s generátorem neplatného kódu) Ano Moˇzné Ne Moˇzné (s generátorem neplatného kódu) Ano Ano Ne Ne Ne Ano Ano

24

Typ anom´ alie Anomálie pˇrekladu Anomálie pˇrekladu Anomálie pˇrekladu ˇ adná Z´ Anomálie pˇrekladu Anomálie pˇrekladu Anomálie pˇrekladu ˇ adná Z´ ˇ adná Z´ ˇ adná Z´ Anomálie pˇrekladu Anomálie v´ ystupu/ukonˇcen´ı

Kapitola 5

Aplikace na re´ aln´ e pˇ r´ıpady Cel´ y systém byl podroben ˇctyˇrem experiment˚ um, porovnávaj´ıc´ım r˚ uzné konfigurace r˚ uzn´ ych pˇrekladaˇc˚ u. Tato kapitola popisuje jejich nastaven´ı, pr˚ ubˇeh a v´ ysledky.

5.1

Metodika

Systém byl testován na ˇctyˇrech r˚ uzn´ ych pˇr´ıpadech, které pokr´ yvaj´ı spektrum moˇzn´ ych pouˇzit´ı systému. Tˇemito pˇr´ıpady jsou: • produkˇcn´ı pˇrekladaˇc v r˚ uzn´ ych konfigurac´ıch, • produkˇcn´ı pˇrekladaˇc proti pˇrekladaˇci, kter´ y jeˇstˇe nedosáhl verze 1, • open-source produkˇcn´ı pˇrekladaˇce proti produkˇcn´ımu proprietárn´ımu, • produkˇcn´ı pˇrekladaˇc ve stabiln´ı verzi proti stejnému pˇrekladaˇci ve v´ yvojové verzi. P˚ uvodnˇe bylo u ´myslu testovat v´ıce open-source neprodukˇcn´ıch pˇrekladaˇc˚ u proti produkˇcn´ımu, ale nepodaˇrilo se zprovoznit jiné open-source pˇrekladaˇce neˇz GCC a TCC. Pro kaˇzdou variantu byl systém testován se tˇremi r˚ uzn´ ymi generátory, pouˇzit´ ymi pro tvorbu testovac´ıho vstupu. Tento pˇr´ıstup byl zvolen kv˚ uli objektivitˇe. Pokud by mnou implementovan´ y generátor (Spitter popsan´ y v sekci 4.3) nemˇel vlastnosti potˇrebné pro u ´spˇeˇsné vyhledáván´ı chyb, pak je tˇreba zjistit chován´ı systému s jin´ ym generátorem. Pokud by ani tento generátor nemˇel poˇzadované v´ ysledky, pak by bylo moˇzné tuto metodu prohl´ asit za neefektivn´ı a vyvodit z toho z´ avˇery. Pouˇzité generátory jsou tyto: • Spitter je mnou implementovan´ y generátor. Dokáˇze generovat omezenou podmnoˇzinu jazyka C. Programy jsou validn´ı a ukonˇcuj´ı se. Implementaˇcn´ım jazykem je Python. • Randprog je generátor n´ ahodn´ ych program˚ u jazyka C, implementovan´ y Bryanem Turnerem [19]. Dokáˇze generovat omezenou podmnoˇzinu jazyka C. Programy jsou validn´ı, a aˇckoliv program obsahuje kód kter´ y má zabránit nekoneˇcn´ ym cykl˚ um, programy musej´ı b´ yt obˇcas ukonˇceny signálem. Implementaˇcn´ım jazykem je C++. • fuzz pˇredstavuje ˇcistˇe náhodn´ y vstup o délce 1000 byte, realizovan´ y pˇr´ıkazem dd if=/dev/urandom. Tento generátor byl zvolen z d˚ uvodu zámˇeru porovnán´ı ˇcistého fuzz testingu s variantou navrˇzenou v této práci. 25

Vzhledem k relativn´ı rychlosti jednoho testu byl pro jednu variantu zvolen poˇcet 5000 test˚ u. V pˇr´ıpadˇe, ˇze bˇehem testován´ı jedné varianty byly testovány r˚ uzné konfigurace pˇrekladaˇc˚ u (napˇr. optimalizac´ı), pak byl pro kaˇzdou konfiguraci proveden pomˇern´ y poˇcet test˚ u (napˇr. pro dvˇe konfigurace bylo s kaˇzdou provedeno 2500 test˚ u). Pro odliˇsné konfigurace byly generovány odliˇsné testovac´ı pˇr´ıpady. Po ubˇehnut´ı vˇsech test˚ u byly analyzov´ any v´ ysledky, a objevené anomálie byly klasifikovány jako faleˇsné nebo pravé.

5.2

Testovan´ e pˇ rekladaˇ ce

Testovány byly pˇrekladaˇce uvedené v následuj´ıc´ım seznamu. Dalˇs´ı podm´ınky v testovac´ım prostˇred´ı se v jednotliv´ ych variantách testován´ı liˇsily, a jsou uvedeny u kaˇzdého pˇr´ıpadu ’ zvláˇst . y systém vyv´ıjen´ y jako souˇca´st • GCC (GNU Compiler Collection)[2] je pˇrekladaˇcov´ projektu GNU. Jedná se o nejrozˇs´ıˇrenˇejˇs´ı pˇrekladaˇc aplikac´ı v open-source komunitˇe pouˇz´ıvaj´ıc´ı systém GNU/Linux[4]. Obsahuje front-endy pro jazyky C, C++, ObjC, Fortran, Java a Ada. Je dostupn´ y pod licenc´ı GPLv3. • TCC (Tiny C Compiler)[5] je pˇrekladaˇc jazyka C, zamˇeˇren´ y na kompaktnost a rychlost. Obsahuje vlastn´ı assembler a linker, a implementuje dvˇe zaj´ımavé vlastnosti: schopnost interpretovat zdrojov´ y kód jazyka C jako skript, a zabudované testy na nˇekteré programátoské sémantické chyby (bound checker ). TCC zat´ım nedos´ ahl stabiln´ı verze. Je dostupn´ y pod licenc´ı BSD. u C, C++ a Fortran pro platformy firmy • ICC (Intel C Compiler)[3] je pˇrekladaˇc jazyk˚ Intel, kterou je také vyv´ıjen. V´ yhodou jsou vynikaj´ıc´ı optimalizace na nativn´ıch platformách. Jedná se o komerˇcn´ı, proprietárn´ı pˇrekladaˇc dostupn´ y zdarma pro nekomerˇcn´ı vyuˇzit´ı. Akademické vyuˇzit´ı nen´ı povaˇzováno za nekomerˇcn´ı, bylo tedy vyuˇzito instalace tohoto pˇrekladaˇce na ˇskoln´ıch serverech s patˇriˇcnou licenc´ı.

5.3

Klasifikace v´ ysledk˚ u

• Anomálie pˇrekladu znamen´ a, ˇze v´ ysledek pˇrekladu byl u obou pˇrekladaˇc˚ u odliˇsn´ y. • Anomálie ukonˇcen´ı znamená, ˇze jeden program byl ukonˇcen signálem, zat´ımco druh´ y korektnˇe dobˇehl. • Anomálie v´ ystupu oznaˇcuje pˇr´ıpad, kdy se v´ ystupy spuˇstˇen´ ych program˚ u liˇs´ı. • Selhán´ı pˇrekladu oznaˇcuje pˇr´ıpad, kdy pˇri pˇrekladu selˇzou oba pˇrekladaˇce. • Ignorované v´ ysledky byly takové, kdy alespoˇ n jeden program byl ukonˇcen sign´ alem SIGFPE. Anomálie byly následnˇe ruˇcnˇe analyzovány a klasifikovány jako pravé chyby, nebo ˇ y byl pˇr´ıpad, kdy byla jedna chyba nahláˇsena nˇekolikrát. V takovém faleˇsn´ a hláˇsen´ı. Cast´ pˇr´ıpadˇe je zapoˇc´ıtána pouze jednou, stejnˇe jako nˇekolik faleˇsn´ ych hláˇsen´ı, které byly zp˚ usobeny stejnou chybou v testovac´ım systému.

26

5.4

Pˇ r´ıpad 1: gcc s r˚ uzn´ ymi optimalizacemi

V této ˇcásti byl systém aplikován na open-source produkˇcn´ı pˇrekladaˇc s vypnut´ ymi optimalizacemi jako referenˇcn´ı a stejn´ y pˇrekladaˇc s r˚ uzn´ ymi u ´rovnˇemi optimalizac´ı.

5.4.1

Prostˇ red´ı a podm´ınky

Testovan´ y pˇ rekladaˇ c Testovan´ y pˇrekladaˇc byl GNU Compiler Collection ve verzi 4.1.2-33, dodávan´ y v RPM bal´ıˇcku distribuce Fedora gcc-4.1.2-33.fc8.rpm. Bylo provedeno 1500 experiment˚ u pro tˇri r˚ uzné u ´rovnˇe optimalizac´ı – optimalizace v´ ykonu -O2, silnˇejˇs´ı optimalizace v´ ykonu -O3 a optimalizace velikosti v´ ysledného kódu -Os. Referenˇ cn´ı pˇ rekladaˇ c Referenˇcn´ım pˇrekladaˇcem byl v tomto experimentu rovnˇeˇz GNU Compiler Collection ve verzi 4.1.2-33, dodávan´ y v RPM bal´ıˇcku distribuce Fedora gcc-4.1.2-33.fc8.rpm, s explicitnˇe deaktivovan´ ymi optimalizacemi (volba -O0). Prostˇ red´ı Testován´ı prob´ıhalo v následuj´ıc´ım prostˇred´ı. • Procesor: AMD Athlon(tm) 64 Processor 3800+ • Operaˇ cn´ı syst´ em: Fedora 8 • J´ adro: Linux 2.6.24.4-64.fc8 #1 SMP i686 athlon i386 GNU/Linux • Linker: GNU ld verze 2.17.50.0.18-1 20070731 • Knihovna C: glibc-2.7-2

5.4.2

Spitter

V´ ysledky jsou uvedeny v tabulce 5.1. Bˇehem tohoto testován´ı nebyly nalezeny ˇzádné chyby v testovaném pˇrekladaˇci. Selhán´ı pˇrekladu byla zp˚ usobena nedokonal´ ym generován´ım Spitteru, kdy je jeden identifikátor, nejˇcastˇeji jednoznakov´ y, pouˇzit v programu v´ıcekr´ at.

5.4.3

Randprog

V´ ysledky jsou uvedeny v tabulce 5.2. Vysok´ y poˇcet anomáli´ı ukonˇcen´ı je dán podobou program˚ u generovan´ ych programem Randprog. Programy j´ım generované maj´ı obˇcas pomˇernˇe dlouhou dobu trván´ı, a proto byla ˇcasto anomálie vyvolaná t´ım, ˇze po uplynut´ı limitu 5 sekund byl takov´ y program umˇele zabit. Byla nalezena jedna chyba (demonstrovan´ a v doy v´ ysledek bitové datc´ıch A.1 a A.2) , kdy byl v optimalizovaném kódu ˇspatnˇe vypoˇc´ıtan´ operace.

5.4.4

fuzz

V´ ysledky uvád´ı tabulka 5.3. Test dopadl zcela dle oˇcekáván´ı, vˇsechny náhodné vstupy byly pˇrekladaˇcem korektnˇe odm´ıtnuty. Nebylo zjiˇstˇeno ani jedno zhroucen´ı pˇrekladaˇce. 27

Tabulka 5.1: GCC -O0 vs. GCC -O2, -O3, -Os, Spitter Testy -O2 -O3 -Os Celkem 1500 1500 1500 OK 1456 1457 1460 Anomálie pˇrekladu 0 0 0 Anomálie ukonˇcen´ı 0 0 0 Anomálie v´ ystupu 0 0 0 Selhán´ı pˇrekladu 15 3 11 Ignorované v´ ysledky 29 40 29 Poˇcet skuteˇcn´ ych chyb 0 0 0 Poˇcet faleˇsn´ ych chyb 0 0 0

Tabulka 5.2: GCC -O0 vs. GCC -O2, -O3, -Os, Randprog Testy -O2 -O3 -Os Celkem 1500 1500 1500 OK 1345 1335 1349 Anomálie pˇrekladu 0 0 0 Anomálie ukonˇcen´ı 155 162 151 Anomálie v´ ystupu 0 3 0 Selhán´ı pˇrekladu 0 0 0 Ignorované v´ ysledky 0 0 0 Poˇcet skuteˇcn´ ych chyb 0 2 0 Poˇcet faleˇsn´ ych chyb 0 0 0

Tabulka 5.3: GCC -O0 vs. GCC -O2, -O3, Testy -O2 -O3 Celkem 1500 1500 OK 0 0 Selhán´ı pˇrekladu 1500 1500 Poˇcet skuteˇcn´ ych chyb 0 0 Poˇcet faleˇsn´ ych chyb 0 0

28

-Os, fuzz -Os 1500 0 1500 0 0

5.4.5

Zhodnocen´ı experimentu

Naproti oˇcekáván´ı nebyly nalezeny témˇeˇr ˇzádné chyby. D˚ uvodem m˚ uˇze b´ yt fakt, ˇze pˇrekladaˇc GCC verze 4.1.2 je uˇz´ıván jiˇz pomˇernˇe dlouhou dobu a zjevné chyby byly jiˇz objeveny. Je také moˇzné, ˇze pˇri vˇetˇs´ım poˇctu testovac´ıch pˇr´ıpad˚ u by k nalezen´ı chyby mohlo doj´ıt. Zaj´ımav´ y bude tento experiment aplikovan´ y na v´ yvojovou verzi pˇrekladaˇce GCC.

5.5

Pˇ r´ıpad 2: GCC, TCC

V této ˇcásti byl systém aplikov´ an na open-source produkˇcn´ı pˇrekladaˇc jako referenˇcn´ı a open-source nedospˇel´ y pˇrekladaˇc jako testovan´ y.

5.5.1


Testovan´ y pˇ rekladaˇ c Testovan´ y pˇrekladaˇc byl Tiny C Compiler ve verzi 0.9.24, pˇreloˇzen´ y a sestaven´ y ze zdrojov´ ych kód˚ u dostupn´ ych na webov´ ych stránkách projektu, pˇreloˇzen´ y standardn´ım GNU v´ yvojov´ ym ˇretˇezcem (pˇrekladaˇc GCC 4.1.2-33, linker ld 2.17.50.0.18-1, knihovna C glibc glibc-2.7-2). Referenˇ cn´ı pˇ rekladaˇ c Referenˇcn´ım pˇrekladaˇcem byl v tomto experimentu GNU Compiler Collection ve verzi 4.1.233, dodávan´ y v RPM bal´ıˇcku distribuce Fedora gcc-4.1.2-33.fc8.rpm. Prostˇ red´ı • Procesor: AMD Athlon(tm) 64 Processor 3800+ • Operaˇ cn´ı syst´ em: Fedora 8 • J´ adro: Linux 2.6.24.4-64.fc8 #1 SMP i686 athlon i386 GNU/Linux • Linker: GNU ld verze 2.17.50.0.18-1 20070731 • Knihovna C: glibc-2.7-2

5.5.2

Spitter

V tomto pˇr´ıpadˇe bylo nalezeno velké mnoˇzstv´ı anomáli´ı. V´ ysledky jsou uvedeny v tabulce 5.4. Vˇsechny anomálie pˇrekladu jsou zp˚ usobeny r˚ uzn´ ymi variantami chyby uvedené v pˇr´ıloze A.5, kdy pˇrekladaˇc TCC neodm´ıtne kód, kde jsou pˇredefinovány symboly na jin´ y typ, popˇr´ıpadˇe jdou definovány jako jin´ y typ symbolu. Velké mnoˇzstv´ı anomáli´ı v´ ystupu je zp˚ usobeno variantami chyby A.9 a dalˇs´ımi. Objevily se také nˇekteré faleˇsné chyby, zejména ve spojitosti s pˇresnost´ı operac´ı velmi vysok´ ych ˇc´ısel s plovouc´ı ˇrádovou ˇcárkou, kdy se ztrác´ı pˇresnost tohoto datového typu a pˇrekladaˇce se s t´ım vyrovnávaj´ı r˚ uzn´ ym zp˚ usobem.

5.5.3

Randprog

V´ ysledky jsou uvedeny v tabulce 5.4. Pˇr´ıˇciny anomáli´ı nebyly do detailu vyˇsetˇrovány, vzhledem k velikosti pˇr´ıpad˚ u generovan´ ych programem Randprog. 29

Tabulka 5.4: Testy Celkem OK Anomálie pˇrekladu Anomálie ukonˇcen´ı Anomálie v´ ystupu Selhán´ı pˇrekladu Ignorované v´ ysledky Poˇcet skuteˇcn´ ych chyb Poˇcet faleˇsn´ ych chyb

5.5.4

GCC vs. TCC Spitter Randprog 5000 5000 4083 4427 14 0 0 514 680 59 7 0 216 0 7 0 2 0

fuzz 5000 0 0 0 0 5000 0 0 0

fuzz

ˇ e fuzz testován´ı nenalezlo v obou pˇrekladaˇc´ıch V´ ysledky jsou uvedeny v tabulce 5.4. Cist´ ˇzádnou chybu.

5.6


V této kombinaci bylo testován´ı nej´ uspˇeˇsnˇejˇs´ı. V pomˇeru k relativnˇe lehkému testov´ an´ı bylo nalezeno sedm r˚ uzn´ ych chyb, coˇz potvrzuje vhodnost metody pro testován´ı nedospˇelého pˇrekladaˇce. Zároveˇ n se ukázala v´ yrazná nevhodnost program˚ u generovan´ ych programem Randprog pro testován´ı. I v pˇr´ıpadˇe, ˇze byla nalezena anomálie, vyˇsetˇrován´ı pˇr´ıˇciny v generovaném kódu by bylo velmi obt´ıˇzné a namáhavé, protoˇze Randprog generuje velmi obsáhlé programy s extrémnˇe sloˇzit´ ym pr˚ ubˇehem kódem.

5.7

Pˇ r´ıpad 3: icc, gcc

Tato ˇcást se zab´ yvá experimentem, kdy byl systém testován na kombinaci produkˇcn´ıho open-source pˇrekladaˇce a produkˇcn´ıho proprietárn´ıho pˇrekladaˇce. Jako referenˇcn´ı pˇrekladaˇc byl zvolen open-source pˇrekladaˇc GCC, jako testovan´ y pˇrekladaˇc proprietárn´ı. Testy probˇehly ve dvou variantách nastaven´ı optimalizac´ı testovaného pˇrekladaˇce.

5.7.1


Testovan´ y pˇ rekladaˇ c Testovan´ y pˇrekladaˇc byl Intel C++ Compiler ve verzi 10.0, nainstalovan´ y na poˇc´ıtaˇci merlin.fit.vutbr.cz. Bylo provedeno 2500 experiment˚ u pro dvˇe r˚ uzné u ´rovnˇe optimalizac´ı – optimalizace v´ ykonu -O2 a explicitnˇe deaktivované optimalizace -O0. Referenˇ cn´ı pˇ rekladaˇ c Referenˇcn´ım pˇrekladaˇcem byl v tomto experimentu GNU Compiler Collection ve verzi 4.2.3, nainstalovan´ y na poˇc´ıtaˇci merlin.fit.vutbr.cz. Optimalizace byly explicitnˇe deaktivovány (volba -O0).

30

Prostˇ red´ı • Procesor: Dual-Core AMD Opteron(tm) Processor 2216 • Operaˇ cn´ı syst´ em: CentOS verze 5 • J´ adro: Linux 2.6.16.60 #2 SMP x86 64 x86 64 x86 64 GNU/Linux • Linker: GNU ld verze 2.18 • Knihovna C: glibc-2.5-18

5.7.2

Spitter

V´ ysledky uvád´ı tabulka 5.5. Tento experiment ukázal mnoho chyb a nedostateˇcn´ ych zajiˇstˇen´ı implementovaného generátoru, coˇz vy´ ustilo ve velk´ y poˇcet r˚ uzn´ ych faleˇsn´ ych hláˇsen´ı. D˚ uvodem byl fakt, ˇze ICC je pˇrekladaˇc, jehoˇz funkcionalita je v´ yraznˇeji odliˇsná od GCC, i kdyˇz jeˇstˇe stále v rámci normy. ICC dokázal na rozd´ıl od GCC odhalit pˇr´ıliˇs velkou konstantu uˇz v dobˇe pˇrekladu (jediná anomálie p´rekladu). Byly odhaleny dva druhy faleˇsn´ ych chyb. Jedn´ım d˚ uvodem byla schopnost pˇrekladaˇce ICC odhalit nedostateˇcnou pˇresnost promˇenné s hodnotou s plovouc´ı ˇrádovou ˇcárkou, pokud byly zapnuté optimalizace. V tomto pˇr´ıpadˇe pˇrekladaˇc zmˇenil datov´ y typ float na datov´ y typ double, coˇz se odrazilo na v´ ystupu odliˇsném od GCC, kter´ y tuto optimalizaci nezvládá. Za chybu to ale nelze povaˇzovat v ani jednom pˇr´ıpadˇe. Druh´ ym faleˇsn´ ym hláˇsen´ım byl odliˇsn´ y obsah promˇenné typu long long (nebo jiného celoˇc´ıselného typu niˇzˇs´ı velikosti) v pˇr´ıpadˇe, ˇze do n´ı byla pˇriˇrazena hodnota typu s plovouc´ı ˇrádovou ˇcárkou, která byla vˇetˇs´ı neˇz maximáln´ı hodnota typu long long. Pˇr´ıklad viz. pseudokód 5.7.2. Program pˇreloˇzen´ y GCC do takové promˇenné pˇriˇradil hodnotu LLONG MAX. Program pˇreloˇzen´ y ICC do n´ı pˇriˇradil hodnotu o jedna vyˇsˇs´ı, coˇz zp˚ usob´ı pˇreteˇcen´ı na nejniˇzˇs´ı hodnotu v rozsahu pˇr´ısluˇsného datového typu. Autorovi se nepodaˇrilo v normˇe jazyka C nalézt definici, které by toto chován´ı odporovalo, takˇze nemohla b´ yt prohl´ aˇsena za chybu.

5.7.3

Randprog

V´ ysledky uvád´ı tabulka 5.6. V tomto experimentu se prokázala relativn´ı nevhodnost generátoru Randprog pro u ´ˇcely fuzz testován´ı r˚ uzn´ ych pˇrekladaˇc˚ u. Vysoké ˇc´ıslo anom´ ali´ı ukonˇcen´ı znamená fakt, ˇze mnoho test˚ u nebylo ukonˇceno do stanoveného ˇcasu. Testovac´ı pˇr´ıpady, které prob´ıhaj´ı dlouhou dobu, nejsou pro fuzz testován´ı vhodné, protoˇze se t´ım ztrác´ı v´ yrazná v´ yhoda – moˇznost zpracovat velké mnoˇzstv´ı test˚ u bˇehem krátké doby. Zároveˇ n v tomto pˇr´ıpadˇe nebyly analyzovány chyby ve v´ ystupu. Randprog obˇcas generuje i skuteˇcnˇe velmi rozsáhlé programy, v ˇrádu desetitis´ıc˚ u ˇrádk˚ u. Zároveˇ n jedin´ y jeho v´ ystup (a jeho v´ ypoˇcet) je proveden aˇz zcela na konci programu, a je tak velmi obt´ıˇzné nalézt m´ısto, ve kterém se funkcionalita liˇs´ı od referenˇcn´ıho pˇrekladu. Vzhledem k náchylnosti kombinace GCC/ICC na rozd´ılnost v´ ystupu popsaného v sekci 5.7.2 je také velmi pravdˇepodobné, ˇze tyto anomálie jsou zp˚ usobeny pr´ avˇe takov´ ym rozd´ıln´ ym v´ ysledkem pˇriˇrazen´ı.

5.7.4

fuzz

V´ ysledky uvád´ı tabulka 5.7. Ani v této kombinaci nebyla ˇcist´ ym fuzz testován´ım nalezena ˇzádná chyba. Vˇsechny neplatné vstupy byly korektnˇe odm´ıtnuty obˇema pˇrekladaˇci. 31

Tabulka 5.5: GCC vs. ICC, Spitter Testy -O0 -O2 Celkem 2500 2500 OK 2455 2411 Anomálie pˇrekladu 1 0 Anomálie ukonˇcen´ı 0 0 Anomálie v´ ystupu 13 28 Selhán´ı pˇrekladu 18 13 Ignorované v´ ysledky 13 48 Poˇcet skuteˇcn´ ych chyb 0 0 Poˇcet faleˇsn´ ych chyb 1 1

Tabulka 5.6: GCC vs. ICC, Randprog Testy -O0 -O2 Celkem 2500 2500 OK 2203 2249 Anomálie pˇrekladu 0 0 Anomálie ukonˇcen´ı 277 232 Anomálie v´ ystupu 20 19 Selhán´ı pˇrekladu 0 0 Ignorované v´ ysledky 0 0 Poˇcet skuteˇcn´ ych chyb 0 0 Poˇcet faleˇsn´ ych chyb 0 0

Tabulka 5.7: GCC vs. Testy Celkem OK Selhán´ı pˇrekladu Ignorované v´ ysledky Poˇcet skuteˇcn´ ych chyb Poˇcet faleˇsn´ ych chyb

32

ICC, fuzz -O0 -O2 2500 2500 0 0 2500 2500 0 0 0 0 0 0

$ cat testcase . c # include < stdio .h > int main (){ unsigned long long a = 0 x1 . P +150000; signed long long b = 0 x1 . P +150000; printf (" Unsigned : % llu \ n " , a ); printf (" Signed : % lli \ n " , b ); }

// > ULLONG_MAX // > LLONG_MAX

$ gcc testcase . c ; ./ a . out Unsigned : 18446744073709551615 Signed : 9223372036854775807

// ULLONG_MAX // LLONG_MAX

$ icc testcase . c ; ./ a . out Unsigned : 0 Signed : -9223372036854775808

// ULLONG_MIN // LLONG_MIN

Obrázek 5.1: Pˇr´ıklad chován´ı konverze typu pro vysoké hodnoty

5.7.5


V´ ystupy tohoto experimentu byly velmi sloˇzité na vyhodnocen´ı. Objevilo se mnoho anom´ ali´ı, které byly zp˚ usobeny rozd´ıln´ ym chován´ım popsan´ ym v´ yˇse, a mezi jejich velk´ ym mnoˇzstv´ım bylo obt´ıˇzné a pracné hledat jakékoliv jiné vadné chován´ı, coˇz vy´ ustilo ve fakt, ˇze nebyla nalezena jediná opravdová chyba. Zároveˇ n také teto experiment ukázal na nepohodlnost práce s anomáliemi v pˇr´ıpadˇe, ˇze jich je vˇetˇs´ı mnoˇzstv´ı, zp˚ usobené jednou pˇr´ıˇcinou.

5.8

Pˇ r´ıpad 4: gcc-stable, gcc-bleeding edge

Posledn´ı experiment se zab´ yval testován´ım posledn´ı v´ yvojové verze pˇrekladaˇce GCC, jehoˇz zdrojov´ y kód byl staˇzen pˇr´ımo ze systému správy verz´ı. Tato kombinace byla zvolena pro otestován´ı moˇznosti pouˇz´ıt systém pˇri regresn´ım testován´ı pˇrekladaˇce.

5.8.1


Testovan´ y pˇ rekladaˇ c Testovan´ y pˇrekladaˇc byl GCC ve verzi 4.4.0, jehoˇz zdrojov´ y kód byl z´ıskán z vˇetve HEAD systému správy verz´ı dne 28.4.2008. Pˇreloˇzen byl proveden´ım plného 3-fázového bootstrapu [2], coˇz dokazuje, ˇze pˇrekladaˇc je alespoˇ n tak kvalitn´ı, aby pˇreloˇzil sám sebe. Referenˇ cn´ı pˇ rekladaˇ c Referenˇcn´ım pˇrekladaˇcem byl v tomto experimentu GNU Compiler Collection ve verzi 4.1.233, dodávan´ y v RPM bal´ıˇcku distribuce Fedora gcc-4.1.2-33.fc8.rpm.

33

Prostˇ red´ı • Procesor: AMD Athlon(tm) 64 Processor 3800+ • Operaˇ cn´ı syst´ em: Fedora 8 • J´ adro: Linux 2.6.24.4-64.fc8 #1 SMP i686 athlon i386 GNU/Linux • Linker: GNU ld verze 2.17.50.0.18-1 20070731 • Knihovna C: glibc-2.7-2

5.8.2

Spitter

V´ ysledky uvád´ı tabulka 5.8. Toto testován´ı objevilo jednu chybu typu ICE-on-valid, kter´ a byla pˇr´ıtomná v obou pˇrekladaˇc´ıch a projevovala se jen s vypnut´ ymi optimalizacemi. Podrobnosti jsou uvedeny v dodatku A.3. Tato chyba byla nalezena pˇri zbˇeˇzném proch´ azen´ı logu selhan´ ych pˇreklad˚ u a pˇrinesla nápad na moˇzné rozˇs´ıˇren´ı systému pro zachyt´ av´ an´ı a hláˇsen´ı tˇechto pˇr´ıpad˚ u jako anomálie. Faleˇsné hláˇsen´ı má svuj p˚ uvod ve vlastnosti jazyka C, kdy nen´ı urˇceno v jakém poˇrad´ı jsou vyhodnocovány jednotlivé ˇcásti v´ yrazu. Obˇe anomálie obsahovaly v´ yraz, ve kterém je jedna funkce volána dvakr´ at s r˚ uzn´ ymi argumenty a v´ ysledkem je rozd´ıln´ y v´ ystup v pˇr´ıpadˇe rozd´ılného poˇrad´ı volán´ı funkce.

5.8.3

Randprog

V´ ysledky uvád´ı tabulka 5.9. Objevena byla jedna chyba typu ICE-on-invalid (pops´ ana ystupu nebyly analyv dodatku A.4) v pˇr´ıpadˇe, ˇze byly vypnuté optimalizace. Anomálie v´ zovány vzhledem k velikosti pˇr´ıpad˚ u, které selhaly. Ve vˇsech pˇr´ıpadech se jednalo o n´ ahodné programy s v´ıce neˇz 4000 ˇrádky a v´ıce neˇz dvaceti funkcemi.

5.8.4

fuzz

Nebyla nalezena ˇzádná chyba. V´ ysledky uvád´ı tabulka 5.10.

5.8.5


Tento experiment ukázal na nedokonalost systému v pˇr´ıpadˇe, ˇze pˇreklad nestandardnˇe (ICE) selˇze u obou pˇrekladaˇc˚ u. Takov´ y pˇr´ıpad je zaˇrazen jako Selhán´ı pˇrekladu a m˚ uˇze tak b´ yt pˇrehlédnut´ y, pokud jsou analyzovány jen anomálie. Toto by mˇelo b´ yt v budoucnosti oˇsetˇreno lépe. Nalezeny byly dvˇe chyby, coˇz je niˇzˇs´ı v´ ysledek, neˇz se oˇcekávalo u HEAD vˇetve projektu.

34

Tabulka 5.8: GCC 4.1.2 vs. GCC 4.4.0, Spitter Testy -O0 -O2 Celkem 2500 2500 OK 2476 2370 Anomálie pˇrekladu 0 0 Anomálie ukonˇcen´ı 0 0 Anomálie v´ ystupu 2 0 Selhán´ı pˇrekladu 13 13 Ignorované v´ ysledky 9 117 Poˇcet skuteˇcn´ ych chyb 1 0 Poˇcet faleˇsn´ ych chyb 1 0

Tabulka 5.9: GCC 4.1.2 vs. GCC 4.4.0, Randprog Testy -O0 -O2 Celkem 2500 2500 OK 2249 2234 Anomálie pˇrekladu 1 0 Anomálie ukonˇcen´ı 250 261 Anomálie v´ ystupu 0 5 Selhán´ı pˇrekladu 0 0 Ignorované v´ ysledky 0 0 Poˇcet skuteˇcn´ ych chyb 1 0 Poˇcet faleˇsn´ ych chyb 0 0

Tabulka 5.10: GCC 4.1.2 vs. Testy Celkem OK Selhán´ı pˇrekladu Ignorované v´ ysledky Poˇcet skuteˇcn´ ych chyb Poˇcet faleˇsn´ ych chyb

35

GCC 4.4.0, fuzz -O0 -O2 2500 2500 0 0 2500 2500 0 0 0 0 0 0

Kapitola 6

Z´ avˇ er V závˇeru jsou zhodnoceny dosaˇzené v´ ysledky a také nast´ınˇen dalˇs´ı moˇzn´ y v´ yvoj projektu.

6.1

Zhodnocen´ı v´ ysledk˚ u

V této práci byla popsána problematika chyb v pˇrekladaˇcich, se zamˇeˇren´ım na typické problemy s nimi spojené. Byl navrˇzen pˇr´ıstup k testován´ı pˇrekladaˇc˚ u pomoc´ı automatizace metody fuzz testing. Podle tohoto pˇr´ıstupu byl implementován prototyp systému pro testován´ı pˇrekladaˇc˚ u, se kter´ ym byly provedeny experimenty na tˇrech rozˇs´ıˇren´ ych pˇrekladaˇc´ıch v r˚ uzn´ ych verz´ıch. Ve dvou ze tˇr´ı takto testovan´ ych pˇrekladaˇc˚ u byly bˇehem experiment˚ u nalezeny chyby. Následuje zhodnocen´ı jednotliv´ ych ˇcást´ı projektu.

6.1.1

Gener´ atory n´ ahodn´ eho k´ odu

Byly prostudovány moˇznosti sestrojen´ı generátoru náhodn´ ych vˇet platného kódu v jazyce C. Jeden generátor byl implementován autorem této práce, a pro lepˇs´ı zhodnocen´ı byly provedeny experimenty s generátorem kódu jiného autora. Spitter Generátor implementovan´ y jako souˇcást této práce. Podaˇrilo se dosáhnout relativnˇe sluˇsné u ´rovnˇe pouˇzitelnosti generovan´ ych vˇet pro testován´ı. Generované vˇety byly rychle pˇreloˇzitelné a také s n´ızk´ ym trván´ım bˇehu. Avˇsak byly také zjiˇstˇeny chyby a problémy, které s sebou nese zvolené ˇreˇsen´ı. V pr˚ ubˇehu experiment˚ u se vyskytovaly dva vˇetˇs´ı problémy, které byly zdrojem faleˇsn´ ych chybov´ ych hláˇsen´ı: • Nedefinované poˇrad´ı vyhodnocován´ı podv´ yraz˚ u v jednom v´ yrazu. V pˇr´ıpadˇe, ˇze byla napˇr. jedna funkce volána v jednom v´ yrazu v´ıcekrát s r˚ uzn´ ymi parametry, pak se v´ ystup programu liˇsil v pˇr´ıpadˇe, ˇze pˇrekladaˇce zvolily odliˇsné poˇrad´ı vyhodnocen´ı v´ yraz˚ u. • Pˇr´ıliˇs vysoké hodnoty konstant a v´ ysledk˚ u v´ yraz˚ u. Zejména pˇri operac´ıch s velmi vysok´ ymi ˇc´ısly typu float ˇci double, které ztrácej´ı pˇresnost, se vyskytovaly problémy s odliˇsn´ ym v´ ystupem. Gener´ ator také dokázal produkovat jen velmi omezenou podmnoˇzinu jazyka C.

36

Randprog Tento generátor vol´ı jin´ y pˇr´ıstup k v´ ypisu v´ ystupu generovan´ ych program˚ u. V´ ystup je pouze jeden, a jsou do nˇej prom´ıtnuty vˇsechny operace provedené pˇri bˇehu programu. Tento pˇr´ıstup s sebou nese znaˇcné obt´ıˇze pˇri zjiˇst’ován´ı m´ısta, kde doˇslo k chybˇe. V´ yrazné jsou zvl´ aˇstˇe v kombinaci s druhou vlastnost´ı generátoru, kterou je ˇcasto velmi dlouh´ y vygenerovan´ y program – ˇcasto v ˇrádu tis´ıc˚ u aˇz desetitis´ıc˚ u ˇrádk˚ u, obsahuj´ıc´ıch mnoho dlouh´ ych cykl˚ ua rekurzivn´ıch volán´ı. Programy maj´ı velmi dlouhou dobu bˇehu, coˇz neguje zásadn´ı v´ yhodu testovac´ı metody – moˇznost testovat velké mnoˇzstv´ı pˇr´ıpad˚ u za krátk´ y ˇcas. V´ yhodou Randprogu bylo, ˇze neprodukoval neplatn´ y kód. Fakt, ˇze j´ım vytvoˇrené programy se velmi ˇspatnˇe analyzuj´ı, ale zabránil nalezen´ı moˇzn´ ych chyb v programech, coˇz velmi sniˇzuje moˇznost jeho pouˇzit´ı pro tuto metodu testován´ı.

6.1.2

Syst´ em pro testov´ an´ı

Cel´ y systém fungoval pomˇernˇe spolehlivˇe. S jeho pomoc´ı bylo nalezeno nˇekolik chyb v pˇrekladaˇc´ıch. V´ yhodou bylo snadné pouˇzit´ı r˚ uzn´ ych generátor˚ u testovac´ıch pˇr´ıpad˚ u. Ponˇekud nepohodlná je práce s nalezen´ ymi anomáliemi, kdy je tˇreba ruˇcnˇe analyzovat vytvoˇren´ y zdrojov´ y kód a hledat m´ısto, kde se chyba vytváˇr´ı. Je to také pracné a zdlouhavé v pˇr´ıpadˇe vˇetˇs´ıho mnoˇzstv´ı anomáli´ı, které jsou následkem jediné chyby. Systém by také mohl lépe zvládat situace, kdy dojde k ukonˇcen´ı programu násilnˇe z d˚ uvodu ˇcasového limitu, nebo doruˇcen´ım nˇekterého ze signál˚ u zp˚ usobuj´ıc´ıch ukonˇcen´ı programu.

6.2

Zhodnocen´ı pouˇ zitelnosti metody

V této práci byla zkoumána pouˇzitelnost metody fuzz testing k testován´ı pˇrekladaˇc˚ u. Bylo dosaˇzeno pozitivn´ıch v´ ysledk˚ u, ale negativem z˚ ustáv´ a obt´ıˇzná anal´ yza samotného selhávaj´ıc´ıho testovac´ıho pˇr´ıpadu. Ve srovnán´ı se statick´ ymi metodami také tato dynamická metoda produkuje velké mnoˇzstv´ı faleˇsn´ ych upozornˇen´ı. Nepˇr´ıjemn´ y je také fakt, ˇze jedna chyba m˚ uˇze zp˚ usobit velké mnoˇzstv´ı selhán´ı, a v takovém mnoˇzstv´ı se obt´ıˇznˇe hledaj´ı jiné chyby. V pˇr´ıpadˇe, ˇze by tyto problémy byly odstranˇeny, pak je dle názoru autora tuto metodu moˇzné pouˇz´ıt k u ´spˇeˇsnému a snazˇs´ımu testován´ı pˇrekladaˇc˚ u.

6.3

Dalˇ s´ı v´ yvoj

Pro systém byl zaloˇzen projekt, um´ıstˇen´ y na http://code.googlecode.com/p/fucc/, kde bude pokraˇcovat jeho v´ yvoj. Z této pr´ ace vypl´ yvá pomˇernˇe jednoznaˇcn´ y postup pro dalˇs´ı v´ yvoj projektu. Je potˇreba se zamˇeˇrit zejména na generátor, kde je nutné opravit chyby, které zp˚ usobuj´ı generován´ı neplatného nebo nedeterministického kódu. Bylo by také dobré zvˇetˇsit podmnoˇzinu jazyka C, kterou Spitter dokáˇze generovat. Dále je nutné refaktorovat nebo rozdˇelit tˇr´ıdu Director generátoru, je pˇr´ıliˇs rozsáhlá a nepˇrehledná. V neposledn´ı ˇradˇe je také tˇreba poskytnout programu moˇznost konfigurac´ı a vˇetˇs´ı robustnost. Velk´ ym pˇr´ınosem by také bylo zhotoven´ı jednoduchého uˇzivatelského rozhran´ı, které by zjednoduˇsilo pouˇzit´ı systému. Pro anal´ yzu by byl velmi pˇr´ınosn´ y nástroj, kter´ y by dokázal z pˇredloˇzeného zdrojového kódu odstranit vˇsechno, co neovlivn´ı v´ ystup programu. V dlouhodobém horizontu by mohlo b´ yt zaj´ımavé zamˇeˇren´ı na Director, kter´ y byl ménˇe vázán na konkrétn´ı jazyk.

37

Dodatek A

Nalezen´ e chyby V této ˇcásti jsou uvedeny chyby v pˇrekladaˇc´ıch, nalezené ve fázi testován´ı vytvoˇreného systému. Jedná se o ruˇcnˇe vyextrahované testovac´ı pˇr´ıpady, které jsou upraveny tak, aby obsahovaly co nejmenˇs´ı mnoˇzstv´ı kódu potˇrebného pro demonstraci defektu.

A.1

Chyba 1

Um´ıstˇ en´ı chyby

GCC 4.1.2-33 se zapnut´ ymi optimalizacemi

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat tc1052.c #include int main(){ long var = 0x19DF1618; printf("var: %i\n", printf("var*var: %i\n", printf("(var*var) << var: %i\n", printf("LONG_MAX: %i\n", return 0; } $ gcc -O3 tc1052.c ; ./a.out var: 434050584 var*var: 800596544 (var*var) << var: 0 LONG_MAX: 2147483647

var); var*var); (var*var) << var); LONG_MAX);

Pˇ redpokl´ adan´ e chov´ an´ı $ gcc -O3 tc1052.c ; ./a.out var: 434050584 var*var: 800596544 (var*var) << var: 1073741824 LONG_MAX: 2147483647 38

A.2

Chyba 2


GCC 4.1.2-33 se zapnut´ ymi optimalizacemi

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat tc661.c int main (int argc, void *argv[]) { unsigned long l_40452115 = 0x027F1A57; printf ("l_40452115: %i\n", l_40452115); printf ("l_40452115 >> l_40452115: %i\n", l_40452115 >> l_40452115); return 0; } $ gcc -O3 tc661.c ; ./a.out l_40452115: 41884247 l_40452115 >> l_40452115: 0 Pˇ redpokl´ adan´ e chov´ an´ı $ gcc -O3 tc661.c ; ./a.out l_40452115: 41884247 l_40452115 >> l_40452115: 4

39

A.3

Chyba 3


GCC 4.1.2-33, a GCC 4.4.0, s vypnut´ ymi optimalizacemi

Typ chyby ICE-on-valid Zdrojov´ y k´ od a reprodukce $ cat tc250.c int main(){ float c2 = 1.0; if ( ! ! c2 * 07ll == 0 ){ printf("BOGUS!\n"); } else{ printf("PASS\n"); } } $ gcc tc250.c && ./a.out tc250.c: In function ‘main’: tc250.c:11: internal compiler error: in simplify_subreg, at simplify-rtx.c:3818 Pˇ redpokl´ adan´ e chov´ an´ı $ gcc tc250.c && ./a.out PASS

40

A.4

Chyba 4


GCC 4.4.0, s vypnut´ ymi optimalizacemi

Typ chyby ICE-on-invalid Zdrojov´ y k´ od a reprodukce $ cat tc1047.c func_86234633 (unsigned long p_27126309) { unsigned char l_20121738 = 0xF9; if ((l_20121738 >> 0x97B05850)) { } } $ gcc tc1047.c -O0 -c tc1047.c: In function ‘func_86234633’: tc1047.c:4: warning: right shift count >= width of type tc1047.c:7: error: unrecognizable insn: (insn 6 5 7 3 tc1047.c:4 (set (reg:QI 60) (const_int -1750050736 [0x97b05850])) -1 (nil)) tc1047.c:7: internal compiler error: in extract_insn, at recog.c:1983 Pˇ redpokl´ adan´ e chov´ an´ı $ gcc tc1047.c -O0 -c tc1047.c: In function ‘func_86234633’: tc1047.c:4: warning: right shift count >= width of type

41

A.5

Chyba 5


TCC 0.9.24

Typ chyby accepts-invalid Zdrojov´ y k´ od a reprodukce $ cat aaa.c int aaa(int P, long P, short P, double P){ int a = P; } $ tcc aaa.c -c && echo PASS || echo FAIL PASS Pˇ redpokl´ adan´ e chov´ an´ı $ tcc aaa.c -c && echo PASS || echo FAIL FAIL

42

A.6

Chyba 6


TCC 0.9.24

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat 1536.c int main (int argc, char *argv[]) { int m1D = ’K’; double FT = 61.11; long ct = 0xB466; if ( (3795ll) % (long long)(FT) - FT > (long long)(L’\xaD’ + ct ) % (int)m1D){ printf ("NONE"); return 1; } return 0; } $ tcc 1536.c $ ./a.out && echo PASS Neopr´ avnˇ en´ y pˇ rı ´stup do pamˇ eti (SIGSEGV) Pˇ redpokl´ adan´ e chov´ an´ı $ tcc 1536.c $ ./a.out && echo PASS PASS

43

A.7

Chyba 7


TCC 0.9.24

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat 16.c long long P4 = 1; int main (int argc, char *argv[]) { unsigned long long aaa = ((((long long)(0007Lu)) % ((long long)(0x81)))+P4); unsigned long long bbb = (17l); printf("aaa: %i\n", aaa); printf("bbb: %i\n", bbb); if (aaa >= bbb) printf ("--- This is under aaa >= bbb block from variables \n"); } $ tcc 16.c; ./a.out aaa: 8 bbb: 17 --- This is under (aaa >= bbb) block from variables Pˇ redpokl´ adan´ e chov´ an´ı $ tcc 16.c; ./a.out aaa: 8 bbb: 17

44

A.8

Chyba 8


TCC 0.9.24

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat 16.c unsigned int B (short K) { K = (2 + ’U’); printf("K397L5: %i\n", K); if ((K - K) <= K) printf ("THIS IS IN ((%i-%i) <= %i BLOCK\n", K, K, K); else printf ("THIS IS IN ((%i-%i) <= %i ELSE BLOCK\n", K, K, K); return L’g’ + ((((long long) (L’~’)) % ((long long) (L’\?’ + (’g’))))); }; int main (int argc, char *argv[]) { B (L’\v’-2979u); } $ tcc 232.c; ./a.out K397L5: 87 THIS IS IN ((87-87) <= 87 ELSE BLOCK Pˇ redpokl´ adan´ e chov´ an´ı $ tcc 232.c; ./a.out K397L5: 87 THIS IS IN ((87-87) <= 87 BLOCK

45

A.9

Chyba 9


TCC 0.9.24

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat try.c double a =1; int main(){ printf("%f\n",a); return 0; } $ cat try2.c long long Q = 1; int main (int argc, char *argv[]) { printf("Global long long Q: %llu\n", Q); } $ tcc try.c; ./a.out 0.000000 $ tcc try2.c; ./aout Global long long Q: 629445874048565249 Pˇ redpokl´ adan´ e chov´ an´ı $ tcc try.c; ./a.out 1.000000 $ tcc try2.c; ./aout Global long long Q: 1

46

A.10

Chyba 10


TCC 0.9.24

Typ chyby wrong-code Zdrojov´ y k´ od a reprodukce $ cat tc551.c long long D = 1; int main(int argc, char *argv[]){ printf("LEFT : %u\n", (D)); printf("RIGHT: %u\n", (’+’ - 0l) + ’;’ - D + 0234620 ); if ( (D) <= (’+’ - 0l) + ’;’ - D + 0234620 ){ printf("PASS - WE ARE IN (LEFT <= RIGHT) IF BLOCK\n"); } } $ tcc tc551.c; ./a.out LEFT : 1 RIGHT: 80373 Pˇ redpokl´ adan´ e chov´ an´ı LEFT : 1 RIGHT: 80373 PASS - WE ARE IN (LEFT <= RIGHT) IF BLOCK

47

Literatura [1] GCC bugzilla keyword descriptions [online]. 2008 [cit. 2008-04-15]. Dostupn´ yz WWW: . [2] GCC online documentation [online]. 2008 [cit. 2008-05-13]. Dostupn´ y z WWW: . R C++ compiler documentation [online]. c2008 [cit. 2008-05-13]. [3] Intel, Inc. Intel Dostupn´ y z WWW: .

[4] Ohloh. Ohloh.net : Open Source, revealed [online]. 2008 [cit. 2008-05-13]. Dostupn´ yz WWW: . [5] Tiny C Compiler Reference Documentation [online]. 2008 [cit. 2008-05-13]. Dostupn´ y z WWW: . [6] AHO, Alfred V., et al. Compilers : Principles, Techniques, and Tools. 2nd edition. [s.l.] : Addison-Wesley, 2007. 964 s. [7] BEAZLEY, David M. PLY : Python Lex-Yacc [online]. [2007] [cit. 2008-04-12]. Dostupn´ y z WWW: . [9] Valgrind User Manual [online]. 2008 [cit. 2008-04-18]. Dostupn´ y z WWW: . [10] GRUNE, Dick, JACOBS, Ceriel J.H. Parsing techniques: A practical guide. Chichester, Anglie : Ellis Horwood Limited, 1990. [11] THOMAS, David, HUNT, Andrew. Program´ ator Pragmatik. Brno : Computer Press, 2007. 219 s. [12] JOHNSON, Stephen C. Yacc : Yet Another Compiler-Compiler [online]. [2007] [cit. 2008-04-12]. Dostupn´ y z WWW:
[14] LINDIG, Cristian. Random testing if C calling conventions. Sixth International Symposium on Automated and Analysis-Driven Debugging (AADEBUG) [s.l.] : [s.n.], 2003. Dostupn´ y z WWW: <www.st.cs.uni-sb.de/ lindig/papers/lindig-aadebug-2005.pdf>. [15] MITCHELL, Mark, OLDHAM, Jeffrey, SAMUEL, Alex. Pokroˇcilé programov´ an´ı v operaˇcn´ım systému Linux. Praha : Softpress, c2002. 265 s. ISBN 80-86497-29-1. [16] NOVILLO, Diego. From source to binary. Red Hat Magazine [online]. 2004, no. 2 [cit. 2008-03-23]. Dostupn´ y z WWW: . [17] SCHWARTZ, R. Writing nonsense with perl. Linux Magazine [online]. 1999, no. 9 [cit. 2008-03-23]. Dostupn´ y z WWW: . ˇ ycarsko, 1999. [18] ISO 9899 TC3. Programming Languages - C. ISO, Geneva, Sv´ [19] TURNER, Bryan. Random C Program Generator [online]. [2007] [cit. 2008-04-24]. Dostupn´ y z WWW: .

49

AUTOMATIZOVANÉ METODY HLEDÁNÍ

Recommend Documents