Fakulta elektrotechnická. Jan Gahura. Vedoucí práce: Ing. Radim Ballner. Studijní program: Elektrotechnika a informatika dobíhající magisterský

ˇ e vysok´e uˇcen´ı technick´e v Praze Cesk´ Fakulta elektrotechnick´a

ˇ VUT FEL katedra pocˇı´tacˇu˚ C

Diplomov´a pr´ace

Dynamick´ a anal´ yza podezˇ rel´ eho k´ odu Jan Gahura

Vedouc´ı pr´ace: Ing. Radim Ballner

Studijn´ı program: Elektrotechnika a informatika dob´ıhaj´ıc´ı magistersk´ y Obor: Informatika a v´ ypoˇcetn´ı technika leden 2007

ii

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem svou diplomovou pr´aci vypracoval samostatnˇe a pouˇzil jsem pouze podklady uveden´e v pˇriloˇzen´em seznamu. Nem´ am z´avaˇzn´ y d˚ uvod proti uˇzit´ı tohoto ˇskoln´ıho d´ıla ve smyslu §60 Z´akona ˇc. 121/2000 Sb., o pr´avu autorsk´em, o pr´avech souvisej´ıc´ıch s pr´avem autorsk´ ym a o zmˇenˇe nˇekter´ ych z´akon˚ u (autorsk´ y z´akon).

V Praze dne 10.1.2007

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

iii

iv

Abstract Current computer world is becoming more and more dangerous due to increasing amount of viruses, malware, spyware, and other malicious software that is spreading across Internet. Today’s tools for compression, encryption, and morphing of the malicious code make the task of their detection even more complex. The goal of this diploma thesis is to analyze, design, and implement an application (for MS Windows XP) that will be able to examine executable files in PE/COFF format for MS Windows x86 32-bit platform using dynamic analysis. The application should dynamically transform the code and emulate its execution in a guarded environment. During the execution, statistical data will be collected and evaluated by a heuristics module (not covered by this diploma thesis), which can eventually stop the execution. The application should decide whether the code is a self-executable archive, and possibly let the code unpack itself.

Abstrakt Souˇcasn´ y svˇet poˇc´ıtaˇc˚ u je st´ale v´ıce nebezpeˇcn´ y d´ıky vzr˚ ustaj´ıc´ımu mnoˇzstv´ı vir˚ u, malwaru, spywaru a jin´eho z´aludn´eho softwaru, kter´ y se ˇs´ıˇr´ı po Internetu. Dneˇsn´ı n´astroje pro kompresi, k´odov´an´ı a morfov´an´ı nebezpeˇcn´eho k´odu ˇcin´ı jeho detekci sloˇzitˇejˇs´ı. C´ılem t´eto diplomov´e pr´ace je anal´ yza, n´avrh a implementace aplikace (pro MS Windows XP), kter´a bude schopna s pomoc´ı dynamick´e anal´ yzy prozkoumat spustiteln´e soubory v PE/COFF form´ atu pro MS Windows x86 (32-bitovou platformu). Aplikace bude dynamicky transformovat k´od a emulovat jeho vykon´ av´an´ı v chr´anˇen´em prostˇred´ı pˇriˇcemˇz bude tak´e schopna rozpoznat, zda-li se jedn´ a o samorozbalovac´ı archiv a nechat jej pˇr´ıpadnˇe rozbalit. Bˇehem vykon´ av´an´ı zadan´eho souboru budou sb´ır´ ana statistick´a data, kter´a budou vyhodnocov´ana heuristick´ ym modulem (nen´ı souˇc´ast´ı t´eto diplomov´e pr´ace), kter´ y m˚ uˇze v pˇr´ıpadˇe potˇreby vykon´ av´an´ı k´odu ukonˇcit.

v

vi

Obsah Seznam obr´ azk˚ u

ix

Seznam tabulek

xi

´ 1 Uvod 1.1 C´ıl pr´ace . . . . . . . . . . . . . . . . 1.2 Souvisej´ıc´ı pr´ace . . . . . . . . . . . 1.3 Obecn´e pojmy . . . . . . . . . . . . 1.3.1 Emulace . . . . . . . . . . . . 1.3.2 Statick´a a dynamick´a anal´ yza 1.3.3 Sandbox . . . . . . . . . . . . 1.4 Z´aklady emul´ atoru . . . . . . . . . . 1.4.1 Reˇzie emulace . . . . . . . . . 1.4.2 Emulaˇcn´ı smyˇcka . . . . . . . 1.4.3 Disassembler . . . . . . . . . 1.4.4 Emulace operaˇcn´ıho syst´emu

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

2 N´ avrh emul´ atoru 2.1 Emul´ ator jako celek . . . . . . . . . . . . . . . . . . . . . . ˇ 2.1.1 Cinnost emul´ atoru . . . . . . . . . . . . . . . . . . . 2.1.2 Efektivita emulace . . . . . . . . . . . . . . . . . . . 2.2 Emul´ ator v prostˇred´ı operaˇcn´ıch syst´em˚ u Windows . . . . . 2.2.1 Standardn´ı knihovny . . . . . . . . . . . . . . . . . . 2.2.2 Zaveden´ı emulace . . . . . . . . . . . . . . . . . . . . 2.3 Realizace emulaˇcn´ı smyˇcky . . . . . . . . . . . . . . . . . . 2.3.1 Dispatcher a ˇr´ıd´ıc´ı blok . . . . . . . . . . . . . . . . 2.3.2 Kontext emul´ atoru a emulovan´eho programu . . . . 2.3.3 Bloky . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Sklad blok˚ u . . . . . . . . . . . . . . . . . . . . . . . 2.3.5 Z´avislosti mezi bloky . . . . . . . . . . . . . . . . . . 2.3.6 Obsluha vl´ aken . . . . . . . . . . . . . . . . . . . . . 2.4 Emul´ ator operaˇcn´ıho syst´emu . . . . . . . . . . . . . . . . . 2.4.1 Akce emulovan´eho programu z pohledu bezpeˇcnosti 2.4.2 Emulace API operaˇcn´ıho syst´emu . . . . . . . . . . . 2.4.3 Pˇreklad pˇr´ıstupu do pamˇeti . . . . . . . . . . . . . . 2.5 Sbˇer statistick´ ych dat . . . . . . . . . . . . . . . . . . . . . 2.5.1 Data sb´ıran´a prvn´ı verz´ı emul´ atoru . . . . . . . . . . 2.6 Shrnut´ı n´avrhu . . . . . . . . . . . . . . . . . . . . . . . . . 3 Implementace a testov´ an´ı 3.1 Obecnˇe k implementaci a testov´an´ı . . . . . . . 3.1.1 Testov´an´ı emul´ atoru . . . . . . . . . . . 3.1.2 Technick´e prostˇredky pro implementaci 3.2 V´ yznamn´e datov´e struktury . . . . . . . . . . . 3.2.1 Obecn´ y vyhled´ avac´ı strom . . . . . . . . 3.2.2 Implementace mapy z´avislost´ı blok˚ u . . 4 Anal´ yza emulovan´ eho programu

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

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

. . . . . .

. . . . . . . . . . .

1 1 1 2 2 2 3 3 3 4 6 6

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

7 7 7 8 9 10 10 11 11 12 13 16 19 20 24 25 26 28 31 31 31

. . . . . .

32 32 32 33 33 34 36 38

vii

4.1

4.2

4.3

4.4

Konfigurace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Hardware a software . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Testovac´ı sada vstupn´ıch program˚ u. . . . . . . . . . . . . . . . . . . 4.1.3 Popis pouˇzit´e verze emul´ atoru . . . . . . . . . . . . . . . . . . . . . . Pˇr´ıstup do pamˇeti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Dˇelen´ı kl´ıˇce obecn´eho vyhled´ avac´ıho stromu na pole . . . . . . . . . 4.2.2 Velikost cache vyhled´ avac´ıch datov´ ych struktur . . . . . . . . . . . . 4.2.3 Zhodnocen´ı n´avrhu datov´ ych struktur . . . . . . . . . . . . . . . . . Tvorba blok˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Velikosti blok˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Poˇcet blok˚ u, expanze k´odu a procento blok˚ u se statick´ ym ukonˇcen´ım Dynamick´e vlastnosti programu . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Mˇeˇren´ı efektivity emulace . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Efektivita emulace a d´elka bˇehu emulovan´eho programu . . . . . . . 4.4.3 Efektivita emulace a struktura emulovan´eho programu . . . . . . . .

5 Budouc´ı pr´ ace 5.1 Dalˇs´ı v´ yvoj emul´ atoru . . . . . . . . . 5.1.1 Sn´ıˇzen´ı pamˇet’ov´ ych n´arok˚ u . . 5.1.2 Opatˇren´ı proti detekci emulace 5.2 Heuristick´ y modul . . . . . . . . . . . 5.2.1 Moˇznosti detekce malwaru . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

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

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

38 38 38 39 39 39 40 41 43 43 43 44 44 44 45

. . . . .

. . . . .

48 48 48 48 48 48

6 Z´ avˇ er

50

7 Literatura

51

viii

Seznam obr´ azk˚ u 1.1 1.2

Blokov´e sch´ema obecn´eho emul´ atoru vyuˇz´ıvaj´ıc´ıho dynamick´eho pˇrekladu na bloky Pˇr´ıklad blok˚ u ve zdrojov´em k´odu emulovan´eho programu . . . . . . . . . . . .

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17

Aktivita emul´ atoru . . . . . . . . . . . . . . . . . . . . . . . . . Funkˇcn´ı bloky a datov´e struktury pˇri emulaci . . . . . . . . . . Tvorba ˇr´ıd´ıc´ıho bloku . . . . . . . . . . . . . . . . . . . . . . . Pˇrepnut´ı kontextu pˇri vol´an´ı dispatcheru . . . . . . . . . . . . . Pˇreklad na blok . . . . . . . . . . . . . . . . . . . . . . . . . . . Pˇreklad instrukce ret na ukonˇcen´ı bloku . . . . . . . . . . . . . Pˇreklad instrukce jmp s pamˇet’ov´ ym operandem . . . . . . . . . Pˇreklad ukonˇcen´ı bloku pˇred a po zˇretˇezen´ı . . . . . . . . . . . Fragmentace funkce . . . . . . . . . . . . . . . . . . . . . . . . Z´avislosti blok˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . Struktura blok˚ u pˇri emulaci re´aln´eho k´odu x86 . . . . . . . . . Graf z´avislosti blok˚ u k pˇr´ıkladu z obr´ azku 2.11 . . . . . . . . . Stavov´ y diagram vl´ akna pˇri emulaci . . . . . . . . . . . . . . . K´od kontroluj´ıc´ı ˇcasov´e kvantum vl´ akna . . . . . . . . . . . . . Datov´e struktury v kontextu emulace API operaˇcn´ıho syst´emu Form´at instrukce sady x86 . . . . . . . . . . . . . . . . . . . . . Pˇreklad instrukce mov ebx, dword ptr [esi + 0x20] . . . .

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

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

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

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

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

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

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

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

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

7 8 12 13 14 15 15 16 17 19 21 21 24 25 27 29 30

3.1 3.2 3.3 3.4

Pˇr´ıklad vyhled´ avac´ıho stromu . . . . . . . . . . ˇ en´ı kl´ıˇce obecn´eho vyhled´ Clenˇ avac´ıho stromu . Princip u ´spory pamˇeti vyhled´ avac´ım stromem . Zobrazen´ı grafu z´avislost´ı blok˚ u v implementaci

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

34 35 36 37

4.1 4.2 4.3 4.4 4.5 4.6

Rozm´ıstˇen´ı blok˚ u v adresov´em prostoru . . . . . . . . . . . . . . . . . . . . . . Rozm´ıstˇen´ı API funkc´ı v adresov´em prostoru . . . . . . . . . . . . . . . . . . . ´ eˇsnost cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uspˇ Velikosti blok˚ u pro testovan´e programy . . . . . . . . . . . . . . . . . . . . . . . Z´avislost efektivity emulace na d´elce v´ ypoˇctu programu . . . . . . . . . . . . . Z´avislost efektivity emulace na poˇctu vyhled´ an´ı v obecn´em vyhled´ avac´ım stromu

ix

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 5

40 41 42 43 45 47

x

Seznam tabulek 4.1 4.2 4.3

Konfigurace hardware poˇc´ıtaˇce pouˇz´ıt´eho pro testy . . . . . . . . . . . . . . . . Programy testovac´ı sady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hodnoty parametr˚ u mˇeˇren´ ych program˚ u . . . . . . . . . . . . . . . . . . . . . .

xi

38 38 44

xii

´ KAPITOLA 1. UVOD

1

´ 1 Uvod 1.1

C´ıl pr´ ace

C´ılem t´eto pr´ace je anal´ yza, n´avrh a implementace programu, kter´ y pomoc´ı dynamick´e anal´ yzy k´odu (zkoum´an´ı jeho v´ ypoˇctu) umoˇzn ˇuje prozkoumat podezˇrel´ y program aniˇz by doˇslo k poˇskozen´ı operaˇcn´ıho syst´emu, spuˇstˇen´ ych aplikac´ı nebo dat. Motivac´ı pro takov´ y analyz´ ator je mnoˇzstv´ı nebezpeˇcn´ ych program˚ u vyuˇz´ıvaj´ıc´ı metody zakryt´ı sv´eho k´odu pomoc´ı ˇsifrov´an´ı nebo komprese. K odkryt´ı k´odu maskovan´eho programu dojde aˇz pˇri jeho spuˇstˇen´ı pˇriloˇzen´ ym k´odem (analogie se samorozbalovac´ımi archivy), kter´ y nevykazuje zn´ amky nebezpeˇcnosti. Metody ˇsifrov´an´ı nebo komprese je velmi snadn´e modifikovat a dostat tak z pohledu statick´e anal´ yzy1 odliˇsn´ y program. Takto je moˇzn´e v kr´atk´em ˇcase vytvoˇrit napˇr. velmi mnoho nov´ ych vir˚ u, kter´e budou v podstatˇe funkˇcnˇe totoˇzn´e. Pro dynamickou anal´ yzu potˇrebujeme k´od zkouman´eho programu vykonat. K tomuto u ´ˇcelu implementujeme emul´ ator zajiˇst’uj´ıc´ı vykon´ an´ı programu tak, aby nedoˇslo k poˇskozen´ı jin´ ych program˚ u, operaˇcn´ıho syst´emu nebo dat. Nejprve se v t´eto pr´aci zamˇeˇr´ıme na anal´ yzu, n´avrh a implementaci emul´ atoru. D´ale se pak pokus´ıme za pouˇzit´ı jiˇz funkˇcn´ıho emul´ atoru prozkoumat typickou ˇcinnost emulovan´eho programu za u ´ˇcelem pˇr´ıpadn´eho zlepˇsen´ı efektivity emulace.

1.2

Souvisej´ıc´ı pr´ ace

Tato pr´ace nepostihuje zcela novou oblast. Spojen´ı emulace na aplikaˇcn´ı u ´rovni (popisov´ano v [7]) s anal´ yzou komprimovan´ ych vir˚ u je jiˇz u ´spˇeˇsnˇe nasazeno v ˇradˇe komerˇcn´ıch produktech (napˇr. NOD32). Bohuˇzel jsou takov´e implementace cenn´ ym majetkem dotyˇcn´ ych firem a nen´ı tedy moˇzn´e z nich ˇcerpat. Jedin´ ym uˇziteˇcn´ ym v´ ysledkem je fakt, ˇze takov´ y postup funguje. Je tedy tˇreba soustˇredit se na pˇr´ıbuzn´e projekty. Jedn´ım z nich je emulaˇcn´ı syst´em pro dynamickou emulaci a instrumentaci k´odu Valgrind [10] pouˇz´ıvan´ y jako z´aklad testovac´ıch a profilovac´ıch n´astroj˚ u. Vyuˇz´ıv´ a emulaci na aplikaˇcn´ı u ´rovni pod syst´emy x86 Linux. Emulovan´ y k´od je pˇreloˇzen do strojov´eho k´odu fiktivn´ıho RISCov´eho procesoru (strojov´ y k´od je zde nazv´ an UCode), ze kter´eho je pot´e pˇreloˇzen zpˇet na instrukce procesoru Intel x86. Jedn´ a se tedy o emulaci programu pro platformu Intel x86 na platformˇe Intel x86. Pro samotn´ y chod je vyuˇz´ıv´ an princip dˇelen´ı k´odu na line´ arn´ı bloky a princip jejich n´asledn´eho ˇretˇezen´ı. Pouˇzit´ y jednoduch´ y mezik´od umoˇzn ˇuje snadnˇejˇs´ı implementaci n´astroj˚ u pro dynamickou anal´ yzu, kter´e tak nemus´ı zohledˇ novat celou ˇsk´alu instrukc´ı pro Intel x86. Dalˇs´ım velmi zaj´ımav´ ym projektem je QEMU [4]. Jedn´ a se o obecn´ y emul´ ator procesoru jak na aplikaˇcn´ı tak i na syst´emov´e u ´rovni pro mnoˇzstv´ı r˚ uzn´ ych platforem. Emulace se op´ır´ a o pˇreklad strojov´eho k´odu do blok˚ u za pouˇzit´ı mezik´odu stejnˇe jako u Valgrindu. Pro pˇreklad mezik´odu na strojov´ y k´od c´ılov´e platformy pouˇz´ıv´ a zaj´ımavou metodu. Kaˇzd´ a instrukce mezik´odu je implementov´ana v C a n´asledn´ y blok je pak tvoˇren seznamem tˇechto implementac´ı. QEMU disponuje soubory s implementacemi instrukc´ı mezik´odu pro kaˇzdou podporovanou c´ılovou platformu. ˇ Casto zmiˇ novan´ ym projektem zab´ yvaj´ıc´ım se emulac´ı je Bochs [1]. Jeho hlavn´ı odliˇsnost´ı od dvou dˇr´ıve zm´ınˇen´ ych z´astupc˚ u je jeho princip emulace. Emulaˇcn´ı smyˇcka ˇcte periodicky instrukce emulovan´eho programu a vol´a jejich pˇr´ısluˇsn´e implementace. Nen´ı zde tedy obsaˇzen ˇz´adn´ y pˇreklad k´odu a jeho n´asledn´e spuˇstˇen´ı. Nutno poznamenat, ˇze tento pˇr´ımoˇcar´ y pˇr´ıstup je znaˇcnˇe pomal´ y. Kaˇzd´ a jednotliv´a instrukce emulovan´eho programu spotˇrebuje nav´ıc v´ ypoˇcetn´ı ˇcas na sv´e dek´ odov´an´ı a nalezen´ı spr´ avn´e implementace pokaˇzd´e, kdy je vykon´ ana. Prv´e dva zm´ınˇen´e projekty vyuˇz´ıvaj´ı pˇreklad emulovan´eho k´odu do line´ arn´ıch blok˚ u a mezik´od 1

Statick´ a anal´ yza je zaloˇzena na vyhled´ av´ an´ı charakteristick´ ych posloupnost´ı byt˚ u v souboru.

´ KAPITOLA 1. UVOD

2

pro zajiˇstˇen´ı portability nebo lepˇs´ı abstrakce c´ılov´e platformy. Princip pˇrekladu do blok˚ u je jen jeden z moˇzn´ ych pˇr´ıstup˚ u k urychlen´ı emulace nebo interpretace obecn´eho k´odu [7]. Vzhledem k jeho pozitivn´ımu dopadu na rychlost je vyuˇzit v navrhovan´em emul´ atoru stejnˇe jako n´asledn´e ˇretˇezen´ı blok˚ u (pops´ ano v [11]), kter´e d´ale zvyˇsuje rychlost emulace. Na druhou stranu pˇreklad do mezik´odu v emul´ atoru pouˇzit nen´ı. Hlavn´ım rozd´ılem t´eto pr´ace oproti zm´ınˇen´ ym projekt˚ um je snaha o vˇetˇs´ı rychlost za vyuˇzit´ı faktu, ˇze je shodn´a zdrojov´a i c´ılov´a platforma. Pˇreklad do mezik´odu by zv´ yˇsil celkovou sloˇzitost emul´ atoru a podepsal by se nepˇr´ıznivˇe i na velikosti pˇreloˇzen´eho k´odu.

1.3

Obecn´ e pojmy

V t´eto sekci se zamˇeˇr´ıme na hlavn´ı principy pouˇzit´e pˇri n´avrhu emul´ atoru a vysvˇetl´ıme nˇekter´e z´akladn´ı pojmy. 1.3.1

Emulace

Term´ın emulovan´y program oznaˇcuje vstupn´ı aplikaci, jej´ıˇz ˇcinnost m´ a b´ yt emulov´ana. Emulace m´ a za c´ıl precizn´ı modelov´an´ı bˇehu emulovan´e aplikace na pˇr´ısluˇsn´e platformˇe. Zdrojov´ a platforma oznaˇcuje p˚ uvodn´ı platformu (architekturu poˇc´ıtaˇce a pˇr´ısluˇsn´ y operaˇcn´ı syst´em), pro kterou byl emulovan´ y program urˇcen. C´ılov´ a platforma oznaˇcuje platformu pouˇzitou pro emulaci. Vstupem pro emul´ ator je soubor obsahuj´ıc´ı zdrojov´y k´ od v podobˇe k´odu ve strojov´em jazyce pro zdrojovou platformu. Podle vrstvy, na kter´e pracuje emulovan´ y program, rozliˇsujeme emulaci na aplikaˇcn´ı u ´rovni a emulaci na syst´emov´e u ´rovni. V prvn´ı variantˇe se snaˇz´ıme aplikaci poskytnout prostˇredky ekvivalentn´ı tˇem, kter´e pro ni poskytuje operaˇcn´ı syst´em, na kter´em je schopna bˇeˇznˇe fungovat. Druh´a varianta emulace jde d´al a poskytuje aplikaci iluzi hardwarov´ ych prostrˇedk˚ u poˇc´ıtaˇce. Je tedy moˇzn´e emulovat cel´ y operaˇcn´ı syst´em a jako d˚ usledek i aplikace v nˇem spuˇstˇen´e. Emul´ ator obou typ˚ u pˇritom m˚ uˇze fungovat jako aplikace pˇreloˇzen´ a pro odliˇsn´ y operaˇcn´ı syst´em a odliˇsnou platformu neˇz je zdrojov´a. 1.3.2

Statick´ a a dynamick´ a anal´ yza

Anal´ yza v kontextu t´eto pr´ace je ch´ap´ ana jako sbˇer informac´ı o emulovan´em programu a jejich n´asledn´e vyhodnocen´ı. V´ ystup anal´ yzy programu m˚ uˇze b´ yt pouˇzit pro identifikov´an´ı m´ıst kritick´ ych pro rychlost (profiling), z´ısk´ an´ı popisu struktury nebo detekci v´ yskytu nˇekter´ ych chyb v analyzovan´em programu (napˇr. vyhled´ av´an´ı chyb pˇri pr´aci s dynamickou pamˇet´ı). Ot´azkou tedy je, jak tato data z´ıskat. K anal´ yze lze pˇristoupit bud’ staticky nebo dynamicky. Statick´ a anal´yza zkoum´a zdrojov´ y k´od programu (strojov´ y nebo psan´ y ve vyˇsˇs´ım programovac´ım jazyce) a snaˇz´ı se o vlastn´ı interpretaci chov´an´ı programu. Jej´ı hlavn´ı v´ yhodou je n´ahled na program jako celek a moˇznost uvaˇzov´an´ı vˇsech moˇzn´ ych cest vypoˇctu. Nen´ı vˇsak schopna postihnout chov´an´ı programu z´avisl´e na hodnotˇe vstupn´ıch dat (napˇr. generov´an´ı k´odu za bˇehu). Dynamick´ a anal´yza sleduje bˇeh programu tak, jak by prob´ıhal bˇeˇznou cestou a ve vhodn´ ych okamˇzic´ıch do v´ ypoˇctu vstupuje injekc´ı sv´eho vlastn´ıho k´odu. Neinterpretuje zdrojov´ y k´od sama, ale vyuˇz´ıv´ a poˇc´ıtaˇc jako pˇrirozen´ y interpretr a zkoum´a pouze v´ ysledky. Oproti statick´e anal´ yze je schopna postihnout generov´an´ı k´odu za bˇehu. Hlavn´ı nev´ yhoda dynamick´e anal´ yzy je v jej´ı lok´ aln´ı povaze. Emul´ ator m´ a k dispozici pouze mal´ y vhled do k´odu programu a pˇri emulaci zkoum´a jenom ty cesty, kter´e byly skuteˇcnˇe vykon´ any. Nen´ı tedy pˇr´ıliˇs vhodn´ y pro sbˇer dat nad k´odem jako celkem.

´ KAPITOLA 1. UVOD

3

Instrumentace k´ odu pˇ ri dynamick´ e anal´ yze Sbˇer analytick´ ych dat a samotn´e ˇr´ızen´ı emulace mus´ı b´ yt zajiˇst’ov´ano nˇejak´ ym k´odem, kter´ y mus´ı b´ yt vykon´ av´an v pr˚ ubˇehu v´ ypoˇctu emulovan´eho programu a to nav´ıc ve spr´avnou chv´ıli. Pro tyto u ´ˇcely se pouˇz´ıv´ a instrumentace k´ odu. Instrukce emulovan´eho programu jsou prokl´ ad´ any instrukcemi zajiˇst’uj´ıc´ımi bˇeh emul´ atoru a sbˇer pˇr´ısluˇsn´ ych dat. Samotn´a injekce instrukc´ı emul´ atoru m˚ uˇze b´ yt opˇet dynamick´a (za bˇehu programu) nebo statick´a (pˇred samotn´ ym spuˇstˇen´ım emulovan´eho programu). Statick´a instrumentace pˇredpokl´ ad´ a dostupnost zdrojov´eho k´odu emulovan´e aplikace pˇred samotn´ ym zah´ajen´ım dynamick´e anal´ yzy. Toto vˇsak nen´ı z povahy zad´an´ı t´eto pr´ace splnˇeno. Zdrojov´ y k´od bude ˇcasto komprimov´an nebo ˇsifrov´an. Nav´ıc nen´ı zcela zˇrejm´e, co je ve spustiteln´em souboru emulovan´eho programu k´od a co data. Takt´eˇz k´od generovan´ y za bˇehu nen´ı samozˇrejmˇe pˇred samotn´ ym spuˇstˇen´ım k dispozici. 1.3.3

Sandbox

Program se pˇri sv´em bˇehu spol´eh´ a na operaˇcn´ı syst´em, od kter´eho dost´ av´a prostˇredky pro svou ˇcinnost. Chceme-li tedy emulovat program, mus´ıme mu poskytnout stejn´e prostˇredky, jak´e by dostal pˇri bˇeˇzn´em v´ ypoˇctu bez emulace. Vzhledem k tomu, ˇze pˇredpokl´ ad´ ame potenci´alnˇe nebezpeˇcn´ y program, pˇrib´ yv´ a k tˇemto poˇzadavk˚ u nav´ıc nutnost zamezit emulovan´emu programu v neˇz´adouc´ı interakci s okol´ım. Term´ın sandbox oznaˇcuje soubor prostˇredk˚ u nutn´ ych pro bˇeh programu implementovan´ ych tak, aby nedoˇslo k neˇz´adouc´ı interakci s ostatn´ımi programy a daty nebo v´ ykonn´ ym k´odem emul´ atoru samotn´eho. Syst´emov´e prostˇredky jsou pˇrirozenˇe pˇridˇelov´any kaˇzd´emu spuˇstˇen´emu programu operaˇcn´ım syst´emem. V pˇr´ıpadˇe emul´ atoru sd´ıl´ı jednu sadu prostˇredk˚ u dva programy: emul´ ator a emulovan´ y program, protoˇze operaˇcn´ı syst´em spustil pouze program emul´ atoru. Sd´ılen´ı muˇze m´ıt povahu ˇcasov´eho nebo prostorov´eho multiplexu. Pˇr´ıkladem prostˇredku sd´ılen´eho pomoc´ı ˇcasov´eho multiplexu je napˇr. procesorov´ y ˇcas nebo jeho registry (emul´ ator se ve vyuˇz´ıv´ an´ı procesoru stˇr´ıd´ a s emulovan´ ym programem). Prostorov´eho multiplexu je vyuˇz´ıv´ ano u sd´ılen´ı pamˇeti (emulovan´ y program m´ a pomoc´ı pˇrekladu sv´ ych instrukc´ı pˇresmˇerov´any pamˇet’ov´e operace do bezpeˇcn´ ych oblast´ı adresov´eho prostoru). Oba druhy sd´ılen´ı jsou pouˇzity pro implementaci jednotliv´ ych syst´emov´ ych prostˇredk˚ u, kter´e tvoˇr´ı sandbox pro emulovan´ y program.

1.4

Z´ aklady emul´ atoru

Z´akladn´ım poˇzadavkem na emul´ ator je korektn´ı interpretace emulovan´eho programu ve smyslu zachov´an´ı posloupnosti a v´ yznamu operac´ı pozmˇen ˇuj´ıc´ıch stav poˇc´ıtaˇce. Dalˇs´ım nem´enˇe d˚ uleˇzit´ ym poˇzadavkem je zachov´an´ı u ´nosn´eho zpomalen´ı v´ ypoˇctu a rozumn´ ych pamˇet’ov´ ych n´arok˚ u. Pamˇet’ov´e n´aroky obecnˇe nepˇr´ımo z´avis´ı na rychlosti emulace. Z povahy zad´an´ı t´eto pr´ace budeme ˇcasto upˇrednostˇ novat poˇzadavek rychlosti na u ´kor pamˇet’ov´e n´aroˇcnosti. Obecn´ y emul´ ator je tvoˇren emulaˇcn´ı smyˇckou, kter´a pro ˇcten´ı instrukc´ı emulovan´eho programu vyuˇz´ıv´ a disassembler pˇr´ısluˇsn´e platformy. Interakci emulovan´eho programu s operaˇcn´ım syst´emem patˇriˇcn´eho typu pak zajiˇst’uje emul´ ator syst´emu (viz obr´ azek 1.1). 1.4.1

Reˇ zie emulace

D˚ uleˇzit´ ym parametrem emul´ atoru je rychlost. S jej´ım mˇeˇren´ım vˇsak m˚ uˇze b´ yt probl´em. V pˇr´ıpadˇe r˚ uzn´e zdrojov´e a c´ılov´e platformy nast´ av´a probl´em s r˚ uzn´ ym v´ ykonem hardware. Zˇrejmˇe by bylo tˇreba pomoc´ı benchmark˚ u zjistit vz´ ajemnou relativn´ı rychlost obou platforem a na z´akladˇe n´ı potom porovn´avat ˇcasy bˇehu emulovan´e aplikace na p˚ uvodn´ı platformˇe a v emul´ atoru. V naˇsem pˇr´ıpadˇe jsou platformy shodn´e a m˚ uˇzeme tedy porovn´avat pˇr´ımo bˇeh aplikace bez emuˇ lace a s emulac´ı. Cas, kter´ y je pˇri emulaci str´aven nav´ıc oproti norm´aln´ımu v´ ypoˇctu, naz´ yv´ ame reˇzi´ı emulace.

´ KAPITOLA 1. UVOD

4

emulátor operačního systému

disassembler

emulační smyčka

vytvoř blok

vykonej blok

ulož adresu dalšího bloku

Obr´azek 1.1: Blokov´e sch´ema obecn´eho emul´ atoru vyuˇz´ıvaj´ıc´ıho dynamick´eho pˇrekladu na bloky 1.4.2

Emulaˇ cn´ı smyˇ cka

´ celem emulaˇcn´ı smyˇcky je interpretace kaˇzd´e instrukce emulovan´eho programu tak, aby Uˇ emul´ ator neztratil kontrolu nad v´ ypoˇctem a z´aroveˇ n aby dost´ al poˇzadavku na korektn´ı interpretaci. Z´akladn´ım probl´emem je, jak ˇr´ıdit vykon´ an´ı instrukc´ı 2 tak, aby byla reˇzie s t´ım spojen´ a co nejmenˇs´ı. Trivi´aln´ı ˇreˇsen´ı vyuˇz´ıvan´e v emul´ atoru Bochs pouˇz´ıv´ a rozskok podle operaˇcn´ıho k´odu instrukce do pˇr´ısluˇsn´e interpretace. Reˇzie s t´ım spojen´ a obsahuje dek´ odov´an´ı instrukce, zjiˇstˇen´ı adresy zaˇc´atku k´odu interpretace a pˇrenesen´ı v´ ypoˇctu do toho m´ısta. Po dokonˇcen´ı emulace instrukce n´asleduje n´avrat na zaˇc´atek k´odu, kter´ y pˇreˇcte dalˇs´ı instrukci. Pr´ace vykonan´ a nav´ıc k proveden´ı instrukce je tedy znaˇcn´ a. Pˇ reklad na bloky Rozskoku podle operaˇcn´ıho k´odu a n´asledn´eho n´avratu po kaˇzd´e instrukci se zbav´ıme zaveden´ım pˇrekladu na bloky line´ arn´ıho k´odu. Line´ arn´ım k´odem se rozum´ı posloupnost instrukc´ı bezprostˇrednˇe n´asleduj´ıc´ıch za sebou v pamˇeti, kter´e budou po sobˇe vykon´ any bez ohledu na okolnosti. Strojov´ y k´od lze tedy dˇelit na bloky k´odu oddˇelen´e instrukcemi mˇen´ıc´ı linearitu bˇehu (napˇr. instrukce skoku nebo n´avratu z vol´an´ı). Pˇr´ıklad ukazuje obr´ azek 1.2. Emulaˇcn´ı smyˇcka pak pˇreˇcte vˇzdy jeden cel´ y blok dopˇredu a vytvoˇr´ı jeho pˇreloˇzen´ y obraz sloˇzen´ y z implementac´ı p˚ uvodn´ıch instrukc´ı. Na konec pˇripoj´ı k´od zajiˇst’uj´ıc´ı zjiˇstˇen´ı adresy dalˇs´ıho bloku spolu s instrukcemi zajiˇst’uj´ıc´ımi zavol´an´ı procedury pro jeho pˇreˇcten´ı. Tuto posloupnost instrukc´ı naz´ yv´ ame ukonˇcen´ı bloku. Po u ´spˇeˇsn´em vytvoˇren´ı bloku pˇrenese algoritmus emulaˇcn´ı smyˇcky v´ ypoˇcet na jeho prvn´ı instrukci. Toto ˇreˇsen´ı obsahuje mnohem menˇs´ı reˇzii spojenou s interpretac´ı jedn´e instrukce. Nicm´enˇe 2

Vykon´ an´ım instrukce mysl´ıme obecnˇe k´ od, jehoˇz efekt zajist´ı patˇriˇcnou zmˇenu stavu modelu zdrojov´e platformy. M˚ uˇze se jednat o implementaci instrukce pomoc´ı jin´ ych instrukc´ı nebo tˇreba jej´ı pˇr´ım´e vykon´ an´ı. Vˇse z´ aleˇz´ı na zp˚ usobu realizace modelu zdrojov´e platformy.

´ KAPITOLA 1. UVOD

5 směr výpočtu

zdrojový kód

blok 1

změny linearity výpočtu

skoky v programu

blok 2

blok 3

Obr´azek 1.2: Pˇr´ıklad blok˚ u ve zdrojov´em k´odu emulovan´eho programu zust´ av´a nutnost dek´ odov´an´ı instrukce pˇred kaˇzd´ ym jej´ım vykon´ an´ım (tvorba blok˚ u opakovanˇe). Je tedy vhodn´e realizovat nˇejakou formu pamˇeti pro udrˇzov´an´ı jiˇz pˇreloˇzen´ ych blok˚ u. Sklad blok˚ u Pro udrˇzov´an´ı jiˇz vytvoˇren´ ych blok˚ u vyuˇzijeme sklad blok˚ u. Protoˇze se jedn´ a o v´ ykonnostnˇe velmi citlivou ˇc´ast emul´ atoru, je tˇreba jej implementovat s velk´ ym d˚ urazem na rychlost. Typick´ ym pˇr´ıstupem je dvoj´ urovˇ nov´a pamˇet’ (pouˇzito napˇr. ve Valgrindu), kde je prvn´ı u ´roveˇ n ’ realizov´ana jako asociativn´ı cache pro nejpouˇz´ıvanˇejˇs´ı bloky a druh´a jako pamˇet optimalizovan´ a na rychl´e vyhled´ an´ı podle kl´ıˇce s rozumn´ ymi pamˇet’ov´ ymi n´aroky (strom nebo hash tabulka). Jako kl´ıˇc je vyuˇz´ıv´ ana adresa zaˇc´atku bloku v emulovan´em programu. ˇ ezen´ı blok˚ Retˇ u Prozkoum´ame-li bl´ıˇze povahu instrukc´ı ukonˇcuj´ıc´ıch bloky tak zjist´ıme, ˇze na nˇekter´e bloky bude po kaˇzd´em jejich vykon´ an´ı navazovat vˇzdy stejn´ y blok. Takov´e ukonˇcen´ı oznaˇcujeme jako statick´e ukonˇcen´ı bloku. Jeho protikladem je dynamick´e ukonˇcen´ı bloku, kde adresa zaˇc´atku n´asleduj´ıc´ıho bloku z´avis´ı nˇejak´ ym zp˚ usobem na hodnotˇe uloˇzen´e v pamˇeti (operaˇcn´ı pamˇet’ nebo registry procesoru). Princip ˇretˇezen´ı blok˚ u se t´ yk´ a pouze statick´ ych ukonˇcen´ı. Jednoduˇse jde o to, ˇze staticky ukonˇcen´ y blok lze pˇr´ımo nav´azat na jeho n´asledn´ıka pomoc´ı instrukce skoku. Vyhneme se takto vol´an´ı procedury pro jeho nalezen´ı a v´ yznamnˇe sn´ıˇz´ıme reˇzii emulace. Tento mechanismus m´ a bohuˇzel i sv´e nev´ yhody. Z mnoˇziny dˇr´ıve nez´avisl´ ych blok˚ u k´odu se st´av´a sloˇzit´a struktura, kterou lze popsat orientovan´ ym grafem (bl´ıˇze pops´ an v odstavci 2.3.5). Hrana vede vˇzdy proti smˇeru moˇzn´eho pˇrechodu v´ ypoˇctu mezi blokem se statick´ ym ukonˇcen´ım a jeho n´asledn´ıkem. Odstran´ıme-li z pamˇeti blok, ze kter´eho vede alespoˇ n jedna hrana, m˚ uˇze doj´ıt ke kritick´e chybˇe, pokud neodstran´ıme i vˇsechny bloky, do kter´ ych m˚ uˇzeme z odstraˇ novan´eho bloku doj´ıt po hran´ ach ve smˇeru orientace. Pˇr´ıˇcinou chyby je moˇzn´ y skok do pamˇeti, kde jiˇz pˇr´ısluˇsn´ y blok nen´ı a n´asledn´e nepˇredv´ıdateln´e chov´an´ı programu. Pro zachycen´ı tˇechto z´avislost´ı pouˇzijeme mapu z´ avislost´ı blok˚ u. Z´akladn´ı poˇzadavek kladen´ y na jej´ı implementaci je co nejrychlejˇs´ı vkl´ad´ an´ı nov´ ych z´avislost´ı spolu se snadnou realizac´ı vyhled´ av´an´ı souvisl´ ych podgraf˚ u.

´ KAPITOLA 1. UVOD

6 1.4.3

Disassembler

Anal´ yza v´ yzmanu bin´ arn´ıch dat tvoˇr´ıc´ıch spustiteln´ y k´od emulovan´eho programu (disassemblace) je nutn´ ym pˇredpokladem spr´ avn´e funkce emulaˇcn´ı smyˇcky. Z´akladn´ı vod´ıtka k n´avrhu disassembleru jsou podobn´ a tˇem, kter´e plat´ı i pro emulaˇcn´ı smyˇcku. C´ılem je zde vyhledn´an´ı v´ yznamu dat ve formˇe popisu instrukce. Tato operace by mˇela b´ yt co nejrychlejˇs´ı a z´aroveˇ n by nemˇela vyˇzadovat pˇr´ıliˇs mnoho pamˇeti. Opˇet je tˇreba analyzovat reˇzii spojenou s nalezen´ım definice instrukce (u emulaˇcn´ı smyˇcky se jedn´ a o reˇzii spojenou s pˇresunut´ım v´ ypoˇctu na implementaci pˇr´ısluˇsn´e instrukce). I zde plat´ı, ˇze rychlost nepˇr´ımo z´avis´ı na pamˇet’ov´ ych n´aroc´ıch. Dnes velmi hojnˇe vyuˇz´ıvan´ a architektura disassembleru by se dala nejl´epe popsat jako deterministick´ y koneˇcn´ y automat ˇr´ızen´ y tabulkami - tabulkov´y disassembler. Vstupn´ı abecedou takov´eho automatu jsou byty bin´ arn´ıch dat. Podle nich se spust´ı pr˚ uchod tabulkami, kter´e maj´ı za u ´kol nejen vybrat spr´ avnou deklaraci instrukce (operaˇcn´ı znak a form´ at operand˚ u), ale i pˇresun v´ ypoˇctu na funkci, kter´a operandy pˇr´ımo pˇreˇcte. Tabulky pˇrechod˚ u tedy obsahuj´ı ve sv´ ych ˇr´ adc´ıch tak´e pˇr´ımo adresu dek´ odovac´ı funkce. T´ımto opatˇren´ım minimalizujeme reˇzii spojenou s implementac´ı dek´ odov´an´ı operand˚ u pomoc´ı vˇetven´ı v´ ypoˇctu. Vzhledem ke sloˇzitosti instrukˇcn´ı sady procesor˚ u architektury Intel x86 (IA-32) (popis viz. [5], pro procesory AMD je tˇreba zahrnout rozˇs´ıˇren´ı 3DNow! [3]) je tˇreba organizovat tabulku pˇrechod˚ u automatu do v´ıce vz´ ajemnˇe propojen´ ych tabulek podle skupin instrukc´ı. Pomineme-li mechanismus instrukˇcn´ıch prefix˚ u, mohou m´ıt jednotliv´e instrukce aˇz tˇri byty jako sv˚ uj operaˇcn´ı znak, coˇz vede na velmi velk´e tabulky. Nˇekter´e partie instrukc´ı je nav´ıc vhodn´e dek´ odovat sp´ıˇse algoritmycky, neˇz pˇr´ım´ ym v´ ybˇerem ˇr´adku v tabulce. Disassembler navrˇzen´ y pro tento emul´ ator takto ˇreˇs´ı dek´ odov´an´ı operand˚ u popisuj´ıc´ıch ˇcten´ı nebo z´apis do pamˇeti (dek´odov´an´ı tzv. ModRM bytu). 1.4.4

Emulace operaˇ cn´ıho syst´ emu

Prost´ y pˇreklad k´odu emulovan´eho programu na bloky a jejich n´asledn´e vykon´ an´ı nejsou postaˇcuj´ıc´ı pro spr´ avnou emulaci. Probl´emem je kolize emul´ atoru a emulovan´eho programu pˇri pˇr´ıstupu k syst´emov´ ym prostˇredk˚ um. I pˇri velmi opatrn´e implementaci emul´ atoru z˚ ust´av´a napˇr. probl´em pˇri spr´ avˇe dynamick´e pamˇeti. Abychom se vypoˇr´ adali s tˇemito kolizemi, je nutn´e realizovat emul´ ator operaˇcn´ıho syst´emu, kter´ y m´ a za u ´kol implementovat syst´emov´e API. Emulaˇcn´ı smyˇcka pak m˚ uˇze pˇri pˇrekladu blok˚ u zamˇenit vol´an´ı do skuteˇcn´ ych syst´emov´ ych funkc´ı za emulovan´e varianty. V naˇsem pˇr´ıpadˇe implementujeme pro emulovan´ y program sandbox, jehoˇz souˇc´ast´ı je i emul´ ator operaˇcn´ıho syst´emu, na kter´ y jsou kladeny nˇekter´e specifick´e poˇzadavky. Nejde n´am ani tak o pˇresnou, ale o korektn´ı emulaci syst´emov´eho vol´ an´ı. To znamen´a, ˇze emulovan´ a verze vol´an´ı mus´ı realizovat stejn´e zobrazen´ı vstupn´ıch parametr˚ u na v´ ystupn´ı a zohlednit i pˇr´ısluˇsn´e zmˇeny vnitˇrn´ıho stavu operaˇcn´ıho syst´emu ovlivˇ nuj´ıc´ı ostatn´ı funkce resp. jejich n´avratov´e hodnoty. Nen´ı ovˇsem nutn´e tyto zmˇeny stavu implementovat stejnˇe jako p˚ uvodn´ı syst´em. Napˇr. pˇri z´apisu souboru nemus´ı nutnˇe doj´ıt k jeho skuteˇcn´e zmˇenˇe, ale n´asleduj´ıc´ı ˇcten´ı z dotyˇcn´eho souboru mus´ı vr´ati zapsan´ a data. Tento pˇr´ıstup je vynucen bezpeˇcnostn´ı strategii pˇri emulaci potenci´alnˇe nebezpeˇcn´eho k´odu. Pro obecn´ y emul´ ator zamˇeˇren´ y na vykon´ an´ı emulovan´eho programu by byl nejsp´ıˇs neuˇziteˇcn´ y. V naˇsem pˇr´ıpadˇe je ale hlavn´ım c´ılem emulace sbˇer dat o bˇehu programu do t´e doby, neˇz budeme schopni prohl´asit, ˇze dotyˇcn´ y program je z tˇr´ıdy skryt´ ych nebezpeˇcn´ ych k´od˚ u. Velmi pravdˇepodobnˇe tak´e ani nedojde k emulaci cel´eho bˇehu emulovan´e aplikace.

´ ´ KAPITOLA 2. NAVRH EMULATORU

7

2 N´ avrh emul´ atoru Pˇredmˇetem t´eto kapitoly je popis n´avrhu a n´astin implementace emul´ atoru vyuˇz´ıvaj´ıc´ıho dynamickou instrumentaci k´odu a pˇreklad na bloky. Emul´ ator si neklade za c´ıl precizn´ı emulaci bˇehu aplikace, ale sp´ıˇse urˇcitou formu dynamick´e anal´ yzy bˇehu aplikace do doby, neˇz ji oznaˇc´ıme za bezpeˇcnou nebo nebezpeˇcnou. Ned´ılnou souˇc´ast´ı takov´eho emul´ atoru je i realizace sandboxu, kter´ y je zde tvoˇren emul´ atorem operaˇcn´ıho syst´emu.

2.1

Emul´ ator jako celek

Zde uvedeme obecn´e skuteˇcnosti a u ´vahy ˇr´ıd´ıc´ı n´avrh jednotliv´ ych ˇc´ast´ı emul´ atoru.

2.1.1

ˇ Cinnost emul´ atoru

Nejprve bl´ıˇze pop´ıˇseme ˇcinnost emul´ atoru. V´ ystupem emulace jsou data popisuj´ıc´ı pr˚ ubˇeh v´ ypoˇctu emulovan´e aplikace. Vstupem je bin´ arn´ı spustiteln´ y soubor ve form´ atu COFF/PE pro MS Windows (soubor s pˇr´ıponou exe; popis struktury viz. [8]). Akce emul´ atoru v kontextu bezpeˇcnostn´ı anal´ yzy programu ukazuje obr´ azek 2.1. nahraj vstupní exe soubor

najdi první blok

ukončení emulace

heuristický modul

analytická data

emulační smyčka

vykonej blok

aktualizuj bezpečnostní rating programu

najdi další blok

konec emulace

Obr´azek 2.1: Aktivita emul´ atoru Bˇehem sbˇeru dat popisuj´ıc´ıch ˇcinnost emulovan´eho programu vypoˇc´ıt´ av´a heuristick´ y modul bezpeˇcnostn´ı rating emulovan´eho programu. Po vyhodnocen´ı dostateˇcn´eho mnoˇzstv´ı informac´ı m˚ uˇze heuristick´ y modul pˇreruˇsit emulaci. Emulace je ve sv´e podstatˇe v´ ypoˇcet modelu emulovan´eho programu. Emulaˇcn´ı smyˇcka za bˇehu aktualizuje model tak, aby odpov´ıdal skuteˇcn´emu chov´an´ı emulovan´eho programu. Z´akladn´ım stavebn´ım kamenem modelu je blok. Souvislosti mezi bloky popisuj´ı dalˇs´ı datov´e struktury tvoˇr´ıc´ı emulaˇcn´ı smyˇcku. V´ ypoˇcet jednotliv´ ych blok˚ u pak z´avis´ı i na emul´ atoru operaˇcn´ıho ’ syst´emu, kter´ y zajiˇst uje poˇzadovanou interakci s prostˇredky poˇc´ıtaˇce. Funkˇcn´ı bloky, datov´e struktury a jejich vz´ ajemn´e z´avislosti v pr˚ ubˇehu emulace ukazuje obr´ azek 2.2. Jednotliv´e prvky, kter´e se pod´ılej´ı na emulaci, budou podrobnˇeji probr´ any d´ale v t´eto kapitole.

´ ´ KAPITOLA 2. NAVRH EMULATORU

8 emulační smyčka

model emulovaného programu

řídící blok emulační proměnné

blok

sklad bloků

blok blok dispatcher

mapa závislostí bloků

emulátor operačního systému

disassembler

emulované verze API funkcí

mapa API funkcí

mapa stránek adresového prostoru

Obr´azek 2.2: Funkˇcn´ı bloky a datov´e struktury pˇri emulaci 2.1.2

Efektivita emulace

Vu ´vodn´ı ˇc´asti jsme hovoˇrili o reˇzii emulace jako o ˇcase, kter´ y je pˇri v´ ypoˇctu emulovan´e aplikace spotˇrebov´an nav´ıc oproti neemulovan´emu bˇehu. Abychom mohli d´ale v textu mˇeˇrit reˇzii emulace, zavedeme pojem efektivita emulace jako pod´ıl ˇcasu bˇehu programu bez emulace a ˇcasu v´ ypoˇctu stejn´eho programu v emul´ atoru. Pˇr´ım´e srovn´an´ı tˇechto ˇcas˚ u n´am dovoluje shodnost zdrojov´e a c´ılov´e platformy. Jak uvid´ıme d´ale v textu, efektivita emulace je z´avisl´a na struktuˇre emulovan´eho programu a nen´ı tedy konstantou. Nyn´ı se pokus´ıme bl´ıˇze prozkoumat hlavn´ı faktory ovlivˇ nuj´ıc´ı efektivitu emulace. Emul´ ator vytv´aˇr´ı za bˇehu model emulovan´eho programu, kter´ y postupnˇe proch´az´ı shodn´ ymi stavy (z pohledu vstupn´ıch a v´ ystupn´ıch hran myˇslen´eho deterministick´eho koneˇcn´eho stavov´eho automatu), kter´ ymi proch´az´ı za stejn´ ych podm´ınek program pˇri bˇeˇzn´em v´ ypoˇctu. Liˇs´ı se vˇsak akce1 , kter´e jsou pro dosaˇzen´ı tˇechto stav˚ u provedeny. Uspoˇr´ad´ ame-li akce proveden´e emul´ atorem podle ˇcasu do posloupnosti, bude tato posloupnost nadmnoˇzinou stejnˇe uspoˇr´ adan´ ych akc´ı emulovan´eho programu pˇri bˇehu bez emulace. Akce pˇridan´e nav´ıc pˇri emulaci je tˇreba podrobit bliˇzˇs´ımu zkoum´an´ı. Reˇ zie v´ ypoˇ ctu jednoho bloku Pˇri pˇrekladu bloku doch´az´ı k nahrazen´ı jednotliv´ ych instrukc´ı jednou nebo i v´ıce instrukcemi. Doch´az´ı k expanzi p˚ uvodn´ıho k´odu emulovan´e aplikace. Dopad na efektivitu emulace pak z´aleˇz´ı na povaze pˇridan´ ych instrukc´ı a architektuˇre procesoru c´ılov´e platformy. Pˇri v´ ypoˇctu 1 Akc´ı obecnˇe mysl´ıme v´ yznamovˇe ucelenou ˇc´ ast algoritmu (napˇr. otevˇri soubor, pˇrepni kontext atp.). Akce lze pˇritom dˇelit aˇz na samotn´e instrukce, kter´e jsou jiˇz d´ ale nedˇeliteln´ ymi akcemi.

´ ´ KAPITOLA 2. NAVRH EMULATORU

9

zˇretˇezen´eho bloku 2 je pr´avˇe expanze k´odu hlavn´ı pˇr´ıˇcinou ztr´ aty efektivity. Celkov´ y dopad na efektivitu emulace pak z´aleˇz´ı na pomˇeru vykonan´ ych zˇretˇezen´ ych blok˚ u oproti blok˚ um s dynamick´ ym ukonˇcen´ım, coˇz z´avis´ı na struktuˇre emulovan´eho programu. V r´amci bloku jsou pak pro v´ ykon nejz´asadnˇejˇs´ı instrukce pˇristupuj´ıc´ı do pamˇeti. Pˇri pˇrekladu resp. instrumentaci k´odu jsou pr´avˇe pamˇet’ov´e operandy instrukc´ı hojnˇe vyuˇz´ıv´ any, aby nedoˇslo k poˇskozen´ı stavu emulovan´eho programu (nem˚ uˇzeme si dovolit pˇrepsat hodnotu v ˇz´adn´em z registr˚ u). Nezb´ yv´ a tedy neˇz se spolehnout na efektivn´ı mechanismus L1 cache procesoru a udrˇzovat c´ılov´e pamˇet’ov´e buˇ nky co nejv´ıce pohromadˇe. Reˇ zie ˇ r´ızen´ı v´ ypoˇ ctu blok˚ u Pˇri ˇr´ızen´ı emulace je nejd˚ uleˇzitˇejˇs´ı ˇcinnost´ı emul´ atoru poskytov´an´ı n´asledn´ık˚ u pr´avˇe dokonˇcen´ ym blok˚ um. To m˚ uˇze znamenat pouh´e vyhled´ an´ı v pamˇeti blok˚ u, nebo tak´e nutnost vytvoˇren´ı bloku nov´eho. Obecnˇe rozdˇelujeme akce emul´ atoru pˇri ˇr´ızen´ı v´ ypoˇctu blok˚ u podle ˇcetnosti jejich v´ yskytu. ˇ Casovˇ e kritickou akc´ı je napˇr. vyhled´ av´an´ı v pamˇeti blok˚ u. Naopak tvorba nov´ ych blok˚ u je ˇcasovˇe nekritickou akc´ı, protoˇze po urˇcit´e dobˇe v´ ypoˇctu se budou vˇsechny potˇrebn´e bloky nach´azet ve skladu blok˚ u. Toto rozdˇelen´ı je d˚ uleˇzit´ ym vod´ıtkem pˇri n´avrhu implementace jednotliv´ ych akc´ı. ˇ Casovˇe kritick´e akce je tˇreba optimalizovat na rychlost i za cenu vyˇsˇs´ıch pamˇet’ov´ ych n´arok˚ u. U ˇcasovˇe nekritick´ ych operac´ı je tomu naopak.

2.2

Emul´ ator v prostˇ red´ı operaˇ cn´ıch syst´ em˚ u Windows

V tomto odstavci se zm´ın´ıme o probl´emech spojen´ ych s implementac´ı emul´ atoru v prostˇred´ı operaˇcn´ıho syst´emu Windows XP (dokumentace z´akladn´ıch funkc´ı syst´emu napˇr. [13]3 ). Hlavn´ı pˇr´ıˇcinou pot´ıˇz´ı je snaha realizovat dva procesy tam, kde syst´em pˇredpokl´ ad´ a pouze jeden. Snaˇz´ıme se co nejv´ıce vytˇeˇzit ze skuteˇcnosti, ˇze m´ ame k dispozici plnˇe funkˇcn´ı syst´em, kter´ y bychom museli jinak zcela emulovat. Popisovan´ a problematika u ´zce souvis´ı s emul´ atorem operaˇcn´ıho syst´emu popisovan´ ym v odstavci 2.4. Urˇcuje vˇsak i z´akladn´ı pravidla pro implementaci vˇsech ostatn´ıch ˇc´ast´ı emul´ atoru. K´od emul´ atoru mus´ı b´ yt co nejohleduplnˇejˇs´ı ke sv´emu okol´ı a z´aroveˇ n se na nic nespol´ehat. Emul´ ator je aplikace jako kaˇzd´ a jin´ a. Pˇri spuˇstˇen´ı obdrˇz´ı od operaˇcn´ıho syst´emu sadu prostˇredk˚ u, kter´e pak m˚ uˇze pouˇz´ıt pro svou ˇcinnost. Emulovan´ y program vˇsak pˇredpokl´ ad´ a stejn´e prostˇred´ı pro v´ ypoˇcet. Ide´ aln´ı by bylo, kdybychom mohli n´am poskytnut´e prostˇred´ı pˇr´ımo pˇredat emulovan´emu programu. To vˇsak z mnoha d˚ uvod˚ u nelze. V operaˇcn´ım syst´emu Windows XP existuje ˇrada funkc´ı, jejichˇz n´avratov´a hodnota z´avis´ı na modulu spustiteln´eho souboru aplikace (exe souboru), ze kter´e byl proces zaveden. Toto chov´an´ı by se dalo snadno emulovat. Vˇetˇs´ı probl´em je moˇzn´ a kolize pozic modulu emul´ atoru a modulu emulovan´eho programu v adresov´em prostoru. Kaˇzd´ y modul m´ a pˇreddefinovanou pozici v adresov´em prostoru, se kterou poˇc´ıt´ a pˇrekladaˇc pˇri generov´an´ı strojov´eho k´odu. Probl´em nast´ av´a, pokud na m´ıstˇe pˇredpokl´ adan´eho mapov´an´ı jiˇz nˇejak´ y modul je. V takov´em pˇr´ıpadˇe je modul zaveden na jinou pozici spolu s pˇr´ısluˇsnou u ´pravou k´odu modulu. Kolize nast´ av´a bˇeˇznˇe pˇri pouˇzit´ı dynamicky linkovan´ ych knihoven DLL, kter´e jsou pro tento pˇr´ıpad vybaveny relokaˇcn´ımi informacemi4 , kter´e popisuj´ı nutn´e zmˇeny po nahr´ an´ı na jinou pozici. Spustiteln´e soubory exe 2 Ukonˇcen´ı takov´eho bloku je pˇr´ımo nav´ az´ ano na n´ asleduj´ıc´ı blok a nevol´ a se tedy dispatcher. V´ıce viz. odstavec 2.3.1 3 Odkazovan´ a literatura popisuje funkce syst´emu Windows 2000, kter´ y je ale v z´ akladech shodn´ y s Windows XP 4 Relokaˇcn´ı informace v podobˇe tabulek jsou um´ıstˇeny ve speci´ aln´ı sekci DLL souboru. Ud´ avaj´ı pozice um´ıstˇen´ı adres, kter´e mus´ı b´ yt opraveny v d˚ usledku zaveden´ı knihovny na jinou neˇz pˇredpokl´ adanou pozici v adresov´em

´ ´ KAPITOLA 2. NAVRH EMULATORU

10

vˇsak nejsou relokacemi vybaveny. Spr´avnˇe pˇredpokl´ adaj´ı, ˇze budou prvn´ım modulem mapovan´ ym do adresov´eho prostoru, takˇze ke kolizi doj´ıt nem˚ uˇze. Zav´adˇen´ı modulu emulovan´eho programu tedy bude nutn´e ˇreˇsit sofistikovanˇejˇs´ım zp˚ usobem. Dalˇs´ı probl´em spojen´ y se sd´ılen´ım jedn´e sady syst´emov´ ych prostˇredk˚ u se poj´ı k vyuˇzit´ı standardn´ıch knihoven funkc´ı. Jde o probl´em v´ıce implementaˇcn´ı neˇz syst´emov´ y. Nˇekter´e hojnˇe pouˇz´ıvan´e knihovny DLL totiˇz obsahuj´ı vnitˇrn´ı statick´a data charakteru glob´aln´ıch promˇenn´ ych, kter´e obsahuj´ı informace poj´ıc´ı se k dan´emu procesu. Jejich tv˚ urci navrhovali knihovnu jako objekt o jedn´e instanci. Pokud jej vyuˇzijeme v emul´ atoru, mohlo by doj´ıt k neˇz´adouc´ı interakci s emulovan´ ym programem, kter´ y m˚ uˇze potenci´alnˇe tak´e vyuˇz´ıvat stejnou knihovnu. Nyn´ı pop´ıˇseme moˇzn´e zp˚ usoby ˇreˇsen´ı a jejich konkr´etn´ı implementaci v naˇsem emul´ atoru. 2.2.1

Standardn´ı knihovny

Abychom se vyhnuli moˇzn´e kolizi s emulovan´ ym programem pˇri pouˇzit´ı sd´ılen´ ych knihoven, pouˇz´ıv´ a emul´ ator pouze knihovny obsahuj´ıc´ı API operaˇcn´ıho syst´emu Windows XP. Vˇse ostatn´ı je tˇreba dodateˇcnˇe znovu naprogramovat. Knihovnou, kterou budou vyuˇz´ıvat emul´ ator i emulovan´ y program, bude velmi pravdˇepodobnˇe standardn´ı knihovna jazyka C resp. C++. Kolize zde nast´ av´a napˇr´ıklad pˇri vyuˇz´ıv´ an´ı implementace oper´ator˚ u new a delete. Pro u ´ˇcel emul´ atoru implementujeme podmnoˇzinu funkc´ı standardn´ı knihovny C/C++ vlastn´ı staticky linkovanou knihovnou nazvanou RuntimeLib. 2.2.2

Zaveden´ı emulace

C´ılem zaveden´ı emulace je nahr´ at modul emulovan´eho programu do pamˇeti a pˇripravit pro nˇej veˇsker´e syst´emov´e prostˇredky a poˇzadovan´e dynamicky linkovan´e knihovny, kter´e budou nutn´e minim´alnˇe pro tvorbu a v´ ypoˇcet prvn´ıho bloku. Snaˇz´ıme se pˇritom vyhnout moˇzn´e kolizi pozic modulu emul´ atoru a emulovan´eho programu. Nejprve si mus´ıme poloˇzit ot´ azku, zda m´ a b´ yt v pamˇeti prvn´ı nahr´ an modul emulovan´eho programu nebo emul´ atoru. Oba pˇr´ıstupy jsou v prostˇred´ı Windows XP moˇzn´e. Emulovan´ y program jako prvn´ı Proces emulace nastartujeme spuˇstˇen´ım emulovan´eho programu. Pˇred zaˇc´atkem v´ ypoˇctu k´odu programu namapuje zavadˇeˇc operaˇcn´ıho syst´emu Windows do adresov´eho prostoru poˇzadovan´e dynamicky linkovan´e knihovny. Operaˇcn´ı syst´em poskytuje moˇznost zaregistrovat si DLL knihovnu, kter´a bude namapov´ana do vˇsech spouˇstˇen´ ych proces˚ u5 . Kaˇzd´ a DLL knihovna obsahuje vstupn´ı bod (tzv. DllMain), coˇz je funkce, kter´a je vol´ana, mimo jin´e, pˇri nahr´ an´ı knihovny do pamˇeti. Jej´ım u ´kolem b´ yv´ a typicky inicializace knihovny. V naˇsem pˇr´ıpadˇe bychom mohli v r´ amci t´eto funkce zav´est do pamˇeti modul emul´ atoru vybaven´ y relokacemi, a tak zamezit pˇr´ıpadn´e kolizi s modulem emulovan´eho programu. Pˇrepsali bychom tak´e prvn´ı instrukci vstupn´ıho bodu emulovan´eho programu, a tak zajistili zavol´an´ı k´odu emul´ atoru. Toto ˇreˇsen´ı nar´ aˇz´ı na probl´em. Vzhledem k tomu, ˇze syst´em negarantuje poˇrad´ı, ve kter´em budou jednotliv´e knihovny nahr´ any, muˇze se pˇred naˇsi knihovnu dostat jin´ a, jej´ıˇz inicializaˇcn´ı k´od m˚ uˇze prov´est cokoliv. Nen´ı tedy zaruˇcena absolutn´ı kontrola nad v´ ypoˇctem emulovan´eho programu. prostoru. 5 Toto je realizov´ ano API funkc´ı SetWindowsHookEx.

´ ´ KAPITOLA 2. NAVRH EMULATORU

11

Emul´ ator jako prvn´ı Proces emulace nastartujeme spuˇstˇen´ım modulu emul´ atoru. Ten mus´ı s´ am zav´est emulovan´ y program spolu se vˇsemi poˇzadovan´ ymi knihovnami. Velmi d˚ uleˇzitou v´ yhodou je absolutn´ı vl´ ada nad v´ ypoˇctem. Obt´ıˇznˇejˇs´ı je zde ˇreˇsen´ı kolize pozice modulu emul´ ator a emulovan´eho programu v adresov´em prostoru. V naˇsem emul´ atoru nezb´ yv´ a neˇz vyuˇz´ıt toto ˇreˇsen´ı. Pro pˇr´ıpad kolize pozice modulu emulovan´eho programu mus´ıme zaˇr´ıdit jeho relokaci. Vzhledem k tomu, ˇze typick´ y modul programu neobsahuje relokace, mus´ıme adaptaci k´odu na jinou pozici prov´est pˇri pˇrekladu. Absolutn´ı adresy p˚ uvodnˇe ukazuj´ıc´ı do modulu emulovan´eho programu mus´ı b´ yt upraveny tak, aby ukazovaly na jeho novou pozici. Tento postup naz´ yv´ ame dynamick´ a relokace.

2.3

Realizace emulaˇ cn´ı smyˇ cky

Emulaˇcn´ı smyˇcku je potˇreba vybavit mechanismem dˇel´ıc´ım strojov´ y k´od emulovan´eho programu na bloky. Je tedy nutn´e definovat strukturu bloku a z´aroveˇ n navrhnout takovou instrumentaci k´odu, aby emul´ ator pˇri v´ ykonu bloku neztratil kontrolu nad v´ ypoˇctem. Toto nejsou bohuˇzel jedin´e povinnosti, kter´e mus´ı emulaˇcn´ı smyˇcka plnit. Mus´ı se tak´e starat o spr´ avn´e obslouˇzen´ı vˇsech vl´ aken emulovan´eho programu a pˇreklad vol´an´ı funkc´ı ze zn´ am´ ych knihoven na jejich pˇr´ıpadn´e emulovan´e varianty. V naˇs´ı implementaci je emulaˇcn´ı smyˇcka realizov´ana tˇr´ıdou Machine. 2.3.1

Dispatcher a ˇ r´ıd´ıc´ı blok

Pro zajiˇstˇen´ı bˇehu algoritmu emulace je nutn´e udrˇzovat mnoˇzstv´ı u ´daj˚ u (napˇr. adresu n´asleduj´ıc´ıho bloku nebo hodnoty ukazatele z´asobn´ıku pro emulovan´ y program a pro emul´ ator). Tyto u ´daje souhrnnˇe naz´ yv´ ame emulaˇcn´ı promˇenn´e. S emulaˇcn´ımi promˇenn´ ymi pracuje kr´atk´a rutina zvan´ a dispatcher, kter´a zajiˇst’uje prvn´ı kroky emul´ atoru pˇri n´avratu z bloku. Jej´ı zodpovˇednost´ı je hlavnˇe zajiˇstˇen´ı vol´ an´ı funkce pro nalezen´ı resp. vytvoˇren´ı dalˇs´ıho navazuj´ıc´ıho bloku. Mimo jin´e se tak´e star´ a o pˇrep´ın´ an´ı vl´ aken emulovan´eho programu. Emulaˇcn´ı promˇenn´e slouˇz´ı hlavnˇe pro u ´schovu informac´ı o stavu v´ ypoˇctu emulovan´eho programu bˇehem vykon´ av´an´ı k´odu emul´ atoru (tedy v´ ypoˇcet mimo bloky) a nˇekter´e z tˇechto u ´daj˚ u jsou z´avisl´e na aktu´aln´ım vl´ aknu v´ ypoˇctu. Napˇr. adresa n´asleduj´ıc´ıho bloku bude pro kaˇzd´e vl´ akno v´ ypoˇctu emulovan´eho programu jin´ a. Potˇrebujeme tedy udrˇzovat pro kaˇzd´e vl´ akno jednu sadu emulaˇcn´ıch promˇenn´ ych. Aby mohl dispatcher pracovat s emulaˇcn´ımi promˇenn´ ymi, mus´ı nejprve vˇedˇet, kde se nal´ezaj´ı. Vzhledem k tomu, ˇze m´ ame sadu emulaˇcn´ıch promˇenn´ ych pro kaˇzd´e vl´ akno, musel by dispatcher pˇri kaˇzd´em sv´em v´ ypoˇctu vyb´ırat na z´akladˇe aktu´aln´ıho vl´ akna spr´avnou sadu emulaˇcn´ıch promˇenn´ ych. Pro implementaci takov´eho v´ ybˇeru by se hodil mechanismus priv´atn´ı pamˇeti vl´ akna, kter´ y umoˇzn ˇuje poskytnout kaˇzd´emu vl´ aknu vlastn´ı datov´ y prostor, do kter´eho m˚ uˇze pˇristupovat jednotn´ ym zp˚ usobem (vˇsechna vl´ akna tedy mohou vykon´ avat stejn´ y k´od, kter´ y vˇsak bude operovat nad r˚ uzn´ ymi daty). Dispatcher by nejprve pˇreˇcetl adresu zaˇc´atku sady emulaˇcn´ıch promˇenn´ ych a uloˇzil ji do nˇekter´eho z registr˚ u, pˇres kter´ y by pak, za pouˇzit´ı pˇr´ısluˇsn´eho offsetu, k jednotliv´ ym promˇenn´ ym pˇristupoval. Na efektivitu emulace m˚ uˇze m´ıt nepˇr´ızniv´ y vliv pr´avˇe ˇcten´ı ukazatele zaˇc´atku sady emulaˇcn´ıch 6 promˇenn´ ych . Nav´ıc pˇrijdeme o moˇznost vyuˇzit´ı jednoho registru k jin´ ym u ´ˇcel˚ um. Naˇse ˇreˇsen´ı spoˇc´ıv´ a v nahrazen´ı adres emulaˇcn´ıch promˇenn´ ych v k´odu dispatcheru unik´atn´ımi ˇc´ısly, kter´e jsou pˇred prvn´ım pouˇzit´ım dispatcheru pˇreps´any konkr´etn´ımi adresami. Takto mo6

Ve Windows je pˇr´ıstup k priv´ atn´ı pamˇeti vl´ akna relativnˇe rychl´ y. Jedn´ a se vol´ an´ı API funkce TlsGetValue. Implementace je zaloˇzena na vyuˇzit´ı segmentace pˇri adresov´ an´ı. Kaˇzd´e vl´ akno m´ a deskriptor segmentu uloˇzen´ y v registru fs, pˇres kter´ y pak pˇristupuje do sv´eho priv´ atn´ıho datov´eho prostoru.

´ ´ KAPITOLA 2. NAVRH EMULATORU

12

řídící blok adresa 00010000h

emulační proměnné 012f3dcch

00000000h

0ffffffffh

unikátní čísla místo absolutních adres

vzor kódu dispatcheru

dispatcher

mov [09090901h], eax

mov [00010008h], eax

inc [09090902h]

inc [00010004h]

mov esp, [09090903h]

mov esp, [00010000h]

Obr´azek 2.3: Tvorba ˇr´ıd´ıc´ıho bloku difikovan´ y k´od je pak v´az´an na konkr´etn´ı sadu emulaˇcn´ıch promˇenn´ ych a tvoˇr´ı tak spoleˇcnˇe jeden celek nazvan´ y ˇr´ıd´ıc´ı blok. Princip tvorby ˇr´ıd´ıc´ıho bloku je naznaˇcen na obr´ azku 2.3. Kaˇzd´e vl´ akno emulovan´eho programu dostane pˇridˇelen jeden ˇr´ıd´ıc´ı blok (v´ıce o emulaci v´ıcevl´aknov´ ych program˚ u viz odstavec 2.3.6). 2.3.2

Kontext emul´ atoru a emulovan´ eho programu

V´ ypoˇcetn´ı ˇcas emulace se dˇel´ı mezi vykon´ av´an´ı jednotliv´ ych blok˚ u a v´ ypoˇcet podp˚ urn´eho k´odu, kter´ y se star´ a pˇredevˇs´ım o jejich tvorbu. Kaˇzd´ a ˇc´ast v´ ypoˇctu vˇsak pˇredpokl´ ad´ a jin´ y kontext bˇehu. Jako kontext bˇehu oznaˇcujeme stav procesoru (hodnoty registr˚ u vˇcetnˇe registru pˇr´ıznak˚ u). Pˇri pˇrechodu z v´ ypoˇctu bloku do k´odu emul´ atoru je nutn´e pˇrepnout kontext. Pro veˇsker´e operace emul´ atoru v kontextu emulovan´eho programu plat´ı, ˇze mus´ı zachov´avat hodnoty registr˚ u a pˇr´ıznak˚ u procesoru. Toto samozˇrejmˇe plat´ı i pro pˇrep´ın´ an´ı. Pro u ´schovu a obnovu hodnot registr˚ u procesoru pouˇzijeme instrukce pushfd, popfd, pushad a popad. Tyto instrukce uschov´avaj´ı hodnoty na z´asobn´ık jehoˇz pozici udrˇzuje registr esp. Kdybychom pˇri pˇrechodu z bloku do k´odu emul´ atoru kontext nepˇrepnuli, doˇslo by s velkou pravdˇepodobnost´ı k poˇskozen´ı stavu emulovan´eho programu, protoˇze k´od emul´ atoru modifikuje registry i pˇr´ıznaky. Vzhledem k tomu, ˇze pˇredpokl´ ad´ ame potenci´alnˇe nebezpeˇcn´ y k´od, nem˚ uˇzeme pouˇz´ıt z´asobn´ık emulovan´eho programu (hodnotu registru esp v kontextu emulovan´eho programu), protoˇze ten m˚ uˇze b´ yt z´amˇernˇe poˇskozen7 . Je tedy nutn´e nejdˇr´ıve zajistit platn´ y z´asobn´ık (v esp ukazatel do pamˇeti, kde je moˇzn´e zapisovat) a pot´e teprve uloˇzit kontext emulovan´eho programu. Hodnoty 7

Je prakticky moˇzn´e napsat k´ od v instrukc´ıch procesoru x86, kter´ y z´ amˇernˇe vloˇz´ı do esp ukazatel do neplatn´e

´ ´ KAPITOLA 2. NAVRH EMULATORU

13

; uk´ azka konce bloku ; prvn´ ı ˇ ca ´st pˇ repnut´ ı kontextu a skok do Dispatcheru mov dword ptr [UserStackRegisterStorage], esp mov esp, dword ptr [EmulatorStackRegisterStorage] jmp Dispatcher Dispatcher: ; druh´ a ˇ ca ´st pˇ repnut´ ı kontextu - uloˇ zen´ ı stavu procesoru pushfd pushad ; zde n´ asleduje k´ od emul´ atoru - nalezen´ ı resp. tvorba dalˇ sı ´ho ; bloku. Adresa zaˇ ca ´tku dalˇ sı ´ho bloku je v promˇ enn´ e ; NextBlockAddress ; obnoven´ ı stavu procesoru popad popfd ; obnoven´ ı z´ asobn´ ıku a skok na blok mov esp, dword ptr [UserStackRegisterStorage] jmp dword ptr [NextBlockAddress] Obr´azek 2.4: Pˇrepnut´ı kontextu pˇri vol´an´ı dispatcheru ukazatele z´asobn´ıku emulovan´eho programu a emul´ atoru jsou udrˇzov´any v ˇr´ıd´ıc´ım bloku, odkud jsou za pouˇzit´ı instrukce mov8 pˇresunov´any do registru esp. Tato instrukce nemˇen´ı hodnoty ostatn´ıch registr˚ u ani pˇr´ıznaky. Pˇr´ıklad pˇrepnut´ı do kontextu emul´ atoru a zpˇet je na obr´ azku 2.4. Zde je uk´az´ana re´aln´a implementace pˇrepnut´ı na konci kaˇzd´eho bloku pˇri pˇrechodu na dispatcher a n´asledn´ y n´avrat do kontextu emulovan´eho programu pˇri pˇrechodu na dalˇs´ı blok. Za povˇsimnut´ı stoj´ı, ˇze pˇri n´avratu do kontextu emulovan´eho programu nen´ı tˇreba ukl´adat hodnotu ukazatele z´asobn´ıku emul´ atoru, protoˇze ta je z principu stejn´ a jako na zaˇc´atku dispatcheru. 2.3.3

Bloky

Blok, jako spojen´ı implementac´ı pˇr´ısluˇsn´ ych instrukc´ı strojov´eho k´odu emulovan´eho programu, je tvoˇren z tˇela a ukonˇcen´ı. Strukturu bloku ukazuje obr´ azek 2.5. Pˇri tvorbˇe bloku je tedy nutn´e pˇrekl´adat instrukce ˇcten´e z emulovan´eho programu na jejich konkr´etn´ı implementace. Na tuto ˇcinnost lze nahl´ıˇzet bud’ jako na pˇreklad (nˇekter´e instrukce jsou implementov´any tak, ˇze jejich p˚ uvodn´ı podoba v implementaci chyb´ı) nebo jako na dynamickou instrumentaci k´odu (s´ematnika p˚ uvodn´ıch instukc´ı z˚ ust´av´a, jsou pouze prokl´ ad´ any k´odem emul´ atoru). Pro reprezentaci instrukc´ı byla zvolena hierarchie tˇr´ıd, kter´a dovoluje vyuˇz´ıt dˇediˇcnosti a popamˇeti a d´ ale si vystaˇc´ı bez z´ asobn´ıku. Nask´ yt´ a se tak jedna z moˇzn´ ych technik detekce emulace. 8 Pro ukl´ ad´ an´ı a obnovov´ an´ı hodnoty registru esp by se alespoˇ n po s´emantick´e str´ ance l´epe hodila instrukce xchg, kter´ a zamˇen´ı hodnoty ve sv´ ych operandech. Tato instrukce je vˇsak implementov´ ana jako atomick´ a a pˇri v´ ymˇenˇe hodnot uzamkne sbˇernici syst´emu, aby nedoˇslo v pr˚ ubˇehu z´ amˇeny ke zmˇenˇe hodnoty pˇr´ıpadn´eho pamˇet’ov´eho operandu ze strany ostatn´ıch procesor˚ u v syst´emu. Toto uzamˇcen´ı je vzhledem k instrukci mov velmi pomal´e.

´ ´ KAPITOLA 2. NAVRH EMULATORU

14 překlad instrukcí

původní kód

blok přeloženého kódu

překlad instrukce původní instrukce původní instrukce původní instrukce původní instrukce původní instrukce původní instrukce ukončující blok

překlad instrukce překlad instrukce překlad instrukce překlad instrukce ukončení bloku

Obr´azek 2.5: Pˇreklad na blok lymorfismu pˇri realizaci pˇrekladu. Instance tˇr´ıdy reprezentuj´ıc´ı instrukci poskytuje metodu Translate, kter´ a zap´ıˇse implementaci instrukce na specifikovan´e m´ısto. Tvorba bloku pak prob´ıh´ a vol´an´ım metod Translate instanc´ı, kter´e vrac´ı na sv´em v´ ystupu disassembler. Blok je ukonˇcen proveden´ım pˇrekladu instrukce, kter´a mˇen´ı linearitu v´ ypoˇctu. Ta je pˇreloˇzena na odpov´ıdaj´ıc´ı ukonˇcen´ı bloku. Z implementaˇcn´ıch d˚ uvod˚ u je vhodn´e stanovit maxim´ aln´ı velikost bloku, ˇc´ımˇz si stanov´ıme maxim´ aln´ı interval mezi dvˇema vol´an´ımi dispatcheru a podpoˇr´ıme tak mechanismus emulace v´ıcevl´aknov´ ych program˚ u (dispatcher se star´ a o pˇrep´ın´ an´ı vl´ aken; v´ıce viz odstavec 2.3.6). Plobl´emem se tedy st´av´a zach´azen´ı s pˇr´ıliˇs dlouh´ ymi bloky. V pˇr´ıpadˇe, ˇze je ˇcten´ y blok delˇs´ı neˇz je maxim´ aln´ı dovolen´ a d´elka, je nutn´e jej rozdˇelit na dva. V takov´em pˇr´ıpadˇe se prvn´ı ˇc´ast ukonˇc´ı statick´ ym ukonˇcen´ım s adresou dalˇs´ıho bloku odpov´ıdaj´ıc´ı prvn´ı instrukci dalˇs´ı ˇc´asti dlouh´eho bloku.

Ukonˇ cen´ı bloku Ukonˇcen´ı bloku je kr´atk´ y k´od emul´ atoru na konci kaˇzd´eho bloku pracuj´ıc´ı v kontextu emulovan´eho programu. Jeho c´ılem je v prvn´ı ˇradˇe zjiˇstˇen´ı c´ıle zmˇeny linearity v´ ypoˇctu. Podle takto zjiˇstˇen´e adresy Dispatcher nalezne nebo vytvoˇr´ı n´asleduj´ıc´ı blok. Dalˇs´ım krokem kaˇzd´eho ukonˇcen´ı je pˇrepnut´ı do kontextu emul´ atoru a zavol´an´ı Dispatcheru. Uk´azka takov´eho k´odu je na obr´ azku 2.4 Pro implementaci jsou pouˇzity instrukce, kter´e neovlivˇ nuj´ı pˇr´ıznaky ani ostatn´ı registry procesoru a operuj´ı pouze nad pamˇet´ı a pˇr´ım´ ymi ˇc´ıseln´ ymi operandy. S u ´spˇechem lze vyuˇz´ıt pr´avˇe kontextu emulovan´eho programu. Napˇr. pˇri implementaci ukonˇcen´ı bloku instrukc´ı podm´ınˇen´eho skoku se pouze zmˇen´ı operand tak, aby pˇri splnˇen´ı podm´ınky skoku doˇslo k pˇresunu na Dispatcher. Uk´azka k´odu ukonˇcen´ı pro instrukci ret (jej´ı pˇreklad) je na obr. 2.6. Sloˇzitˇejˇs´ım pˇr´ıpadem jsou ukonˇcen´ı, kde se neobejdeme bez instrukc´ı ovlivˇ nuj´ıc´ıch pˇr´ıznaky procesoru nebo pracuj´ıc´ıch se z´asobn´ıkem. V takov´em pˇr´ıpadˇe je nutn´e pˇrepnout na z´asobn´ık emul´ atoru dˇr´ıve. Uk´azka takov´eho ukonˇcen´ı je na obr. 2.7. Jedn´ a se o ukonˇcen´ı bloku pomoc´ı instrukce jmp s pamˇet’ov´ ym operandem. Jak je z pˇr´ıklad˚ u ukonˇcen´ı patrn´e, pouˇzit´e instrukce vyuˇz´ıvaj´ı absolutn´ı adresy emulaˇcn´ıch promˇenn´ ych v ˇr´ıd´ıc´ım bloku. Jsou tedy pˇr´ımo v´az´any na konkr´etn´ı ˇr´ıd´ıc´ı blok a tvoˇr´ı tak ucelen´ y model vl´ akna emulovan´eho programu.

´ ´ KAPITOLA 2. NAVRH EMULATORU

; uloˇ zen´ ı adresy dalˇ sı ´ho bloku pop dword ptr [NextBlockAddress] ; prvn´ ı ˇ ca ´st pˇ repnut´ ı kontextu - druhou realizuje Dispatcher mov dword ptr [UserStackRegisterStorage], esp mov esp, dword ptr [EmulatorStackRegisterStorage] ; skok na Dispatcher jmp Dispatcher Obr´azek 2.6: Pˇreklad instrukce ret na ukonˇcen´ı bloku

; prvn´ ı ˇ ca ´st pˇ repnut´ ı kontextu - druhou realizuje Dispatcher mov dword ptr [UserStackRegisterStorage], esp mov esp, dword ptr [EmulatorStackRegisterStorage] ; vloˇ zı ´me obsah c´ ılov´ eho pamˇ et’ov´ eho m´ ısta na z´ asobn´ ık, odkud ; jej pak pˇ resuneme do promˇ enn´ e NextBlockAddress v ˇ rı ´d´ ıc´ ım ; bloku. push dword ptr[...] pop dword ptr[NextBlockAddress] ; signalizujeme do Dispatcheru typ ukonˇ cen´ ı bloku pushfd or dword ptr[DispatcherFlags], SF_JMP_FLAG popfd ; skok na Dispatcher jmp Dispatcher Obr´azek 2.7: Pˇreklad instrukce jmp s pamˇet’ov´ ym operandem

15

´ ´ KAPITOLA 2. NAVRH EMULATORU

16

; blok ukonˇ cen´ y instrukc´ ı JNE pˇ red zˇ retˇ ezen´ ım ... ... mov dword ptr[UserStackRegisterStorage], esp mov esp, dword ptr[EmulatorStackRegisterStorage] mov dword ptr[NextBlockAddress], jne Dispatcher mov esp, dword ptr[UserStackRegisterStorage] ; stejn´ y blok po zˇ retˇ ezen´ ı ... ... jne jmp

; pˇ reskoˇ cen´ ı nevyuˇ zit´ eho m´ ısta

Obr´azek 2.8: Pˇreklad ukonˇcen´ı bloku pˇred a po zˇretˇezen´ı ˇ ezen´ı blok˚ Retˇ u Pˇri pˇrekladu instrukce ukonˇcuj´ıc´ı blok m˚ uˇzeme snadno podle parametr˚ u poznat, zda se jedn´ a o statick´e nebo dynamick´e ukonˇcen´ı. Kaˇzd´e statick´e ukonˇcen´ı signalizuje moˇznost pˇr´ım´eho nav´az´an´ı bloku na n´asleduj´ıc´ı blok. K samotn´emu zˇretˇezen´ı m˚ uˇze doj´ıt jiˇz pˇri pˇrekladu bloku (pˇreloˇz´ıme rovnou jeho n´asledn´ıka) nebo aˇz pˇri prvn´ım vykon´ an´ı (blok signalizuje pˇri sv´em ukonˇcen´ı dispatcheru moˇznost nav´azat jej na n´asleduj´ıc´ı blok). Prvn´ı varianta vede na vˇetˇs´ı spotˇrebu pamˇeti, kdy se pˇrekl´adaj´ı i ty bloky, kter´e nemus´ı b´ yt nutnˇe vykon´ any. Druh´ y pˇr´ıstup naopak znamen´a potenci´alnˇe vyˇsˇs´ı reˇzii emulace. Probl´emem jsou v tomto pˇr´ıpadˇe instrukce kter´e nemus´ı vˇzdy v´est ke zmˇenˇe linearity v´ ypoˇctu (napˇr. podm´ınˇen´e skoky). Zˇretˇezen´ı probˇehne aˇz ve chv´ıli, kdy je splnˇena podm´ınka zmˇeny skoku. Do t´e doby se vykon´ av´a pˇreklad obsahuj´ıc´ı mnoˇzstv´ı instrukc´ı nav´ıc 9 . Pro n´aˇs emul´ ator jsme vybrali druhou variantu ˇreˇsen´ı. Blok, kter´ y ˇz´ad´ a dispatcher o pˇr´ım´e nav´az´an´ı na sv´eho n´asledn´ıka, uloˇz´ı do emulaˇcn´ı promˇenn´e LinkType typ ukonˇcen´ı a do promˇenn´e LinkStartLocation adresu zaˇc´atku k´odu ukonˇcen´ı. Dispatcher zavol´a statickou metodu LinkBlock pˇr´ısluˇsn´e tˇr´ıdy implementuj´ıc´ı instrukci a pˇred´ a j´ı adresu zaˇc´atku ukonˇcen´ı spolu s adresou navazuj´ıc´ıho bloku. Blok je zˇretˇezen s n´asledn´ıkem pˇrepisem pˇrekladu sv´eho ukonˇcen´ı. Pˇr´ıklad ukonˇcen´ı pˇred a po zˇretˇezen´ı je na obr´ azku 2.8. Ve zˇretˇezen´e variantˇe ukonˇcen´ı na obr´ azku se objevuje instrukce jmp, kter´a slouˇz´ı pro pˇreskoˇcen´ı nevyuˇzit´eho m´ısta v bloku, kter´e zab´ırala pˇredchoz´ı verze ukonˇcen´ı bloku. Toto je ˇcistˇe vˇec´ı implementace. Bylo samozˇrejmˇe moˇzn´e alokovat nov´ y blok o menˇs´ı d´elce, do kter´eho by byl p˚ uvodn´ı pˇresunut tak, aby nevyuˇzit´a m´ısta zmizela. Zaplatili bychom nepatrn´ ym zv´ yˇsen´ım reˇzie emulace se ziskem v podobˇe menˇs´ıch pamˇet’ov´ ych n´arok˚ u. 2.3.4

Sklad blok˚ u

Sklad blok˚ u funguje jako odkl´ adac´ı prostor pro vytvoˇren´e bloky. Jeho hlavn´ı u ´lohou je poskytovat co nejrychleji poˇzadovan´e bloky podle kl´ıˇce – identifik´ atoru bloku. Pro jednoznaˇcnou 9

Pˇredpokl´ ad´ ame, ˇze ukonˇcen´ı bezprostˇrednˇe nav´ azan´e na dalˇs´ı blok je kratˇs´ı neˇz ukonˇcen´ı obsahuj´ıc´ı k´ od pro skok do dispatcheru. Pro instrukce implementovan´e v tomto emul´ atoru pˇredpoklad plat´ı. Zˇretˇezen´ a varianta obsahuje ˇcasto pouze p˚ uvodn´ı ukonˇcuj´ıc´ı instrukci se zmˇenˇenou c´ılovou adresou skoku.

´ ´ KAPITOLA 2. NAVRH EMULATORU funkce

17

fragment 1

fragment 2

fragment 3

je

je

je

jne

jne

jne

ret

ret

ret

ret

dispatcher

Obr´azek 2.9: Fragmentace funkce identifikaci bloku pouˇz´ıv´ ame jeho poˇc´ateˇcn´ı adresu. Datov´a struktura tvoˇr´ıc´ı sklad blok˚ u je navrˇzena jako vyhled´ avac´ı strom, jehoˇz listy jsou jednotliv´e bloky (pro implementaci je vyuˇzita obecn´ a datov´a struktura vyhled´ avac´ıho stromu popsan´ a v odstavci 3.2). Pˇr´ı emulaci se snaˇz´ı dispatcher nejprve nal´ezt blok ve skladu a pak teprve pˇristupuje k jeho pˇr´ıpadn´e tvorbˇe. Parametrem dotazu je adresa poˇc´atku bloku. Nepˇr´ıjemn´ ym d˚ usledkem identifikace bloku podle poˇc´ateˇcn´ı adresy je fragmentace funkc´ı. Fragmentace funkc´ı Pˇr´ıklad fragmentace funkce uk´aˇzeme na jednoduch´e funkci obsahuj´ıc´ı smyˇcku s moˇznost´ı u ´niku10 . Vzhledem k tomu, ˇze je blok identifikov´an pouze poˇc´ateˇcn´ı adresou, nenalezne dispatcher pˇri vykon´ av´an´ı druh´e iterace smyˇcky patˇriˇcn´ y blok, i kdyˇz m´ ame pˇr´ısluˇsn´ y k´od jednou pˇreloˇzen´ y. Dojde k pˇrekladu nov´eho bloku, kter´ y bude tvoˇren pˇr´ıponou bloku jiˇz zn´ am´eho. Situaci ukazuje obr´ azek 2.9. Na zaˇc´atku emulace funkce je vytvoˇren fragment ˇc´ıslo 1. Pokud dojde pouze k jedn´e iteraci smyˇcky, pˇri kter´e nedojde k odskoku, skonˇc´ı emulace funkce bez nutnosti tvorby dalˇs´ıch blok˚ u. Pˇri druh´e iteraci uˇz je tˇreba vyrobit fragment 3, kter´ y postaˇcuje pro emulaci vˇsech dalˇs´ıch pˇr´ıpadn´ ych iterac´ı. Fragment ˇc´ıslo 2 je vytvoˇren pˇri splnˇen´ı podm´ınky pro odskok ze smyˇcky. Nepˇr´ıjemn´ ym d˚ usledkem fragmentace je v´ıcen´asobn´ y pˇreklad k´odu a s t´ım spojen´e pl´ ytv´ an´ı ˇ pamˇet´ı. Reˇsen´ı tohoto probl´emu by si vyˇz´adalo implementaci skladu blok˚ u tak, aby byl schopen na z´akladˇe pˇredloˇzen´e adresy vr´atit blok, kter´ y byl vytvoˇren za pouˇzit´ı k´odu z t´eto adresy. Sklad by tedy neobsahoval poˇc´ateˇcn´ı adresy blok˚ u, ale interval adres, kter´e dotyˇcn´ y blok pokr´ yv´ a. 10 V programovac´ım jazyce C by se jednalo napˇr. o smyˇcku do - while s tˇelem obsahuj´ıc´ım podm´ıneˇcn´e vykon´ an´ı pˇr´ıkazu break.

´ ´ KAPITOLA 2. NAVRH EMULATORU

18

Intervalov´e vyhled´ av´an´ı ve skladu blok˚ u nen´ı bohuˇzel postaˇcuj´ıc´ı pro eliminaci fragmentace. Po z´ısk´ an´ı spr´ avn´eho bloku nast´ av´a ot´ azka, kde v r´ amci jeho tˇela zaˇc´ıt s emulac´ı. Pˇreklady instrukc´ı zab´ıraj´ı obecnˇe r˚ uzn´e mnoˇzstv´ı pamˇeti, a tak nelze jednoduˇse urˇcit vzd´ alenost pˇrekladu urˇcit´e instrukce od poˇc´atku bloku. Museli bychom implementovat nˇejak´ y mechanismus zpˇetn´eho mapov´an´ı pˇrekladu instrukc´ı na koresponduj´ıc´ı adresy zdrojov´ ych instrukc´ı. Opatˇ ren´ı proti fragmentaci Poˇzadavek intervalov´eho vyhled´ av´an´ı spolu se zpˇetn´ ym mapov´an´ım jednotliv´ ych instrukc´ı m˚ uˇzeme uspokojit zmˇenou organizace skladu blok˚ u. V´ yˇse popsan´ a varianta udrˇzuje pouze poˇc´ateˇcn´ı adresy blok˚ u, tj. adresy pˇrekladu prvn´ıch instrukc´ı. Moˇzn´e ˇreˇsen´ı spoˇc´ıv´ a v udrˇzov´an´ı adres zdrojov´ ych instrukc´ı pro kaˇzd´ y jednotliv´ y pˇreklad instrukce v dan´em bloku. Takto upraven´ y sklad blok˚ u by se vyznaˇcoval stejnou rychlost´ı vyhled´ an´ı (jde o shodn´ y pr˚ uchod vyhled´ avac´ım stromem), ale v´ yraznˇe vyˇsˇs´ı spotˇrebou pamˇeti. V pˇr´ıpadˇe ˇreˇsen´ı s moˇznou fragmentac´ı zab´ır´ a jeden blok pouze 4B – adresa prvn´ı instrukce v r´amci modulu emulovan´eho programu. Vylepˇsen´e ˇreˇsen´ı vede na listy o tˇrech adres´ach po ˇctyˇrech bytech (ukazatel na prvn´ı instrukci bloku, ukazatel na dalˇs´ı instrukci a adresa poˇc´atku pˇrekladu instrukce), kde kaˇzd´ y blok obsad´ı tolik list˚ u, kolik obsahuje instrukc´ı zdrojov´eho k´odu emulovan´eho programu. Nen´ı tedy na prvn´ı pohled zˇrejm´e, jestli je z pamˇet’ov´eho hlediska v´ yhodn´e eliminovat fragmentaci. Sloˇzitˇejˇs´ı vnitˇrn´ı struktura skladu blok˚ u nav´ıc vede na sloˇzitˇejˇs´ı implementaci nˇekter´ ych dalˇs´ıch ˇc´ast´ı emulaˇcn´ı smyˇcky (uvolˇ nov´an´ı pˇreplnˇen´eho skladu). Pˇritom rychlost je v obou pˇr´ıpadech stejn´ a. Vzhledem k tomu, ˇze fragmentuj´ıc´ı ˇreˇsen´ı je jak´ ymsi evoluˇcn´ım pˇredstupnˇem nefragmentuj´ıc´ı varianty, je logicky pouˇzito i v naˇsem emul´ atoru. Vhodnost nasazen´ı vylepˇsen´eho skladu blok˚ u je tˇreba zv´ aˇzit aˇz na z´akladˇe anal´ yzy typick´eho emulovan´eho programu. Uvolˇ nov´ an´ı pˇ replnˇ en´ eho skladu blok˚ u Abychom zamezily zahlcen´ı pamˇeti poˇc´ıtaˇce bloky11 , mus´ıme nastavit maxim´ aln´ı velikost pamˇeti pro sklad blok˚ u. Ve chv´ıli, kdy by pr´avˇe vkl´adan´ y blok pˇrekroˇcil tuto hranici, mus´ıme nˇekter´e starˇs´ı bloky vyjmout. M´ ame na v´ ybˇer z ˇsirok´e ˇsk´aly v´ıce ˇci m´enˇe sofistikovan´ ych metod. Od prost´eho vypr´ azdnˇen´ı cel´eho skladu aˇz po podrobn´e sledov´an´ı ˇcetnosti uˇzit´ı jednotliv´ ych blok˚ u. Nalezen´ı optim´aln´ıho ˇreˇsen´ı nen´ı jednoduch´e. Trivi´aln´ı metody vedou na zbyteˇcn´e opˇetovn´e pˇrekl´ad´ an´ı blok˚ u. Propracovan´e metody zase sniˇzuj´ı efektivitu emulace aktualizov´an´ım informac´ı o uˇziteˇcnosti jednotliv´ ych blok˚ u. Uˇzit´ım obecn´eho vyhled´ avac´ıho stromu pro implementaci skladu blok˚ u dost´ av´ame k dispozici ”zadarmo” omezenou informaci o ned´ avno vykonan´ ych bloc´ıch v podobˇe obsahu cache pˇredˇrazen´e samotn´emu vyhled´ avac´ımu stromu (viz. implementace obecn´eho vyhled´ avac´ıho stromu v odstavci 3.2). Myˇslenkou t´eto metody je zachov´an´ı minim´alnˇe tˇech blok˚ u vˇcetnˇe blok˚ u nutn´ ych pro jejich vykon´ an´ı, kter´e se pr´avˇe nach´azej´ı v cache. Vˇsechny uzly grafu z´avislost´ı blok˚ u, kter´e reprezentuj´ı bloky aktu´alnˇe um´ıstˇen´e v cache a bloky nutn´e k jejich vykon´ an´ı oznaˇc´ıme (proch´az´ıme graf z´avislost´ı proti smˇeru orientace hran). Pak projdeme pole uzl˚ u (viz. odstavec 3.2.2) a vˇsechny neoznaˇcen´e uzly odstran´ıme spolu s koresponduj´ıc´ımi bloky. ´ eˇsnost t´eto metody je sloˇzit´e pˇredpov´ıdat pˇredem. Jej´ı nasazen´ı je nutn´e provˇeˇrit Uspˇ patˇriˇcn´ ym testem. Do prvn´ı verze emul´ atoru jsme vyprazdˇ nov´an´ı skladu blok˚ u nezaˇradili, protoˇze nem´a v´ yznamn´ y dopad na rychlost a nepˇredpokl´ ad´ ame emulaci program˚ u snaˇz´ıc´ıch se zahltit emul´ ator bloky. 11

Je moˇzn´e napsat takov´ y program, kter´ y d´ıky fragmentaci donut´ı emul´ ator vytvoˇrit velk´e mnoˇzstv´ı blok˚ u.

´ ´ KAPITOLA 2. NAVRH EMULATORU

jne

7

1 4

jmp

jne

19

2

jmp

5

ret

graf závislostí bloků

jmp

jmp

3

6

ret

1

4

2

5

3

6

7

Obr´azek 2.10: Z´avislosti blok˚ u 2.3.5

Z´ avislosti mezi bloky

Pouˇzit´ı zˇretˇezen´ı zav´ad´ı z´avislosti mezi jednotliv´ ymi bloky. Blok pˇr´ımo nav´azan´ y na sv´eho n´asledn´ıka nevol´a na sv´em konci dispatcher, ale pˇr´ımo navazuj´ıc´ı blok. Pokud navazuj´ıc´ı blok odstran´ıme z pamˇeti, nast´ av´a probl´em s v´ ypoˇctem vˇsech na nˇej nav´azan´ ych blok˚ u. Pˇr´ıklad z´avislost´ı mezi bloky je na obr´ azku 2.10 vlevo (pln´e ˇsipky znaˇc´ı zˇretˇezen´ı, ˇsipky pˇreruˇsovanou ˇcarou znamenaj´ı vol´an´ı dispatcheru pro nalezen´ı n´asledn´ıka). ˇ Sipky na obr´ azku znaˇc´ı moˇzn´e pˇrechody mezi bloky bˇehem emulace. Rozezn´av´ame dva druhy z´avislosti. Blok je pˇr´ımo z´ avisl´y na jin´em, pokud je na nˇej pˇr´ımo nav´az´an zˇretˇezen´ım. Dva bloky jsou nepˇr´ımo z´ avisl´e, jestliˇze je moˇzn´e pˇrej´ıt z jednoho na druh´ y pˇres jeden nebo v´ıce blok˚ u bez vol´an´ı dispatcheru (vˇsechny ukonˇcen´ı jsou statick´e). Pro lepˇs´ı orientaci v z´avislostech zav´ad´ıme graf z´ avislost´ı blok˚ u, kde uzly jsou jednotliv´e bloky a hrany znaˇc´ıc´ı zˇretˇezen´ı vedou vˇzdy od c´ılov´eho ke zdrojov´emu uzlu (jdou tedy proti smˇeru moˇzn´eho pˇrenosu v´ ypoˇctu pˇri emulaci). Tato zd´ anlivˇe opaˇcn´ a orientace byla zvolena proto, aby odpov´ıdala organizaci poloˇzek v mapˇe z´avislost´ı blok˚ u. Pokud v grafu zvol´ıme uzel, snadno najdeme sledov´an´ım hran mnoˇzinu uzl˚ u z´avisl´ ych na zvolen´em. Obr´azek 2.10 ukazuje na prav´e stranˇe pˇr´ısluˇsn´ y graf z´avislost´ı blok˚ u ke struktuˇre zobrazen´e vlevo.Mapa z´ avislost´ı blok˚ u je implementac´ı grafu z´avislost´ı. Jej´ım u ´kolem je rychle poskytovat mnoˇzinu vˇsech blok˚ u, kter´e z´avis´ı na dan´em blok bud’ pˇr´ımo nebo nepˇr´ımo. Struktura grafu z´ avislost´ı a jej´ı vztah ke struktuˇ re programu Motivac´ı ke studiu typick´e struktury grafu z´avislost´ı blok˚ u je n´avrh algoritmu uvolˇ nov´an´ı skladu blok˚ u. Z hlediska uvolˇ nov´an´ı je zaj´ımav´e nal´ez´ an´ı souvisl´ ych podgraf˚ u v grafu z´avislost´ı. Odstranˇen´ı jednoho uzlu v souvisl´em orientovan´em podgrafu vede na odstranˇen´ı cel´eho podgrafu (kaˇzd´e dva uzly souvisl´eho orientovan´eho podgrafu jsou pˇr´ımo nebo nepˇr´ımo z´avisl´e). Souvisl´e orientovan´e podgrafy vznikaj´ı v tˇelech funkc´ı jako v´ ysledek emulace smyˇcek nebo pˇri rekurzi. Dalˇs´ım zaj´ımav´ ym parametrem grafu z´avislost´ı je, na kolik vykazuje vlastnosti stromu. Obecnˇe

´ ´ KAPITOLA 2. NAVRH EMULATORU

20

plat´ı, nahrad´ıme-li souvisl´e orientovan´e podgrafy jedin´ ym uzlem pˇri zachov´an´ı vstupn´ıch a v´ ystupn´ıch hran podgrafu (eliminujeme kruˇznice), vznikne z grafu les (sjednocen´ı strom˚ u). Strukturn´ı vlastnosti grafu z´avislost´ı blok˚ u silnˇe ovlivˇ nuj´ı v´ ypoˇcetn´ı moˇznosti procesoru. Instrukˇcn´ı sada Intel x86 z hlediska ˇr´ızen´ı v´ ypoˇctu podporuje v podstatˇe pouze funkcion´ aln´ı programov´an´ı. V´ ypoˇcet programu m´ a tedy charakter vol´an´ı funkc´ı, kter´e mohou volat opˇet funkce. Na z´asobn´ıku vznikaj´ı postupnˇe aktivaˇcn´ı z´ aznamy pro kaˇzdou funkci, ve kter´e je v´ ypoˇcet pr´avˇe zanoˇren. Tuto strukturu v´ ypoˇctu kop´ıruj´ı i z´avislosti mezi bloky, kter´e jsou pˇri emulaci vytvoˇreny. V ide´aln´ım pˇr´ıpadˇe, kdy by byly vˇsechny ukonˇcen´ı blok˚ u statick´e, by bylo moˇzno zˇretˇezit vˇsechny bloky. Graf z´avislost´ı blok˚ u by byl bˇehem v´ ypoˇctu jednosmˇernˇe zˇretˇezen´ y seznam a to aˇz do doby, kdy by nˇekter´ y z blok˚ u jako sv´eho n´asledn´ıka ˇz´adal jiˇz vytvoˇren´ y blok (v programu by doˇslo ke druh´e iteraci nˇejak´e smyˇcky nebo opakovan´emu vol´an´ı nˇekter´e funkce). V line´ arn´ım seznamu by vznikla smyˇcka. Pˇri opakovan´e emulaci nˇekter´eho jiˇz zn´ am´eho bloku by mohlo doj´ıt k nalezen´ı jin´eho n´asledn´ıka, neˇz je dosud zn´ am´ y (napˇr. vlivem podm´ınˇen´eho skoku). V takov´em pˇr´ıpadˇe by doˇslo k pˇripojen´ı line´ arn´ıho seznamu (jak´esi vˇetve v´ ypoˇctu) s moˇznost´ı tvorby zpˇetn´ ych vazeb v d˚ usledku vol´an´ı jiˇz zn´ am´ ych blok˚ u. V re´aln´em k´od s dynamick´ ymi ukonˇcen´ımi m´ a graf z´avislosti blok˚ u stejn´ y princip vzniku s t´ım rozd´ılem, ˇze nˇekter´e hrany chyb´ı (nalezen´ı n´asledn´ıka dispatcherem v pˇr´ıpadˇe dynamick´eho ukonˇcen´ı). Pˇri n´avrhu algoritmu uvolˇ nov´an´ı m´ısta ve skladu blok˚ u budeme tedy hovoˇrit o sjednocen´ı izolovan´ ych graf˚ u. Pro kaˇzd´ y izolovan´ y podgraf pak bude kl´ıˇcov´ y v´ ybˇer konkr´etn´ıho bloku, pomoc´ı kter´eho definujeme mnoˇzinu blok˚ u k odstranˇen´ı. U tohoto v´ ybˇeru hraje kl´ıˇcovou roli podobnost komponenty (izolovan´eho podgrafu) na strom.

Praktick´ y pˇ r´ıklad vzniku grafu z´ avislost´ı blok˚ u Pˇr´ıklad struktury blok˚ u je na obr´ azku 2.11. Snaˇz´ıme se zde uk´azat dopad funkcion´ aln´ıho ˇ v´ ypoˇcetn´ıho modelu procesoru na strukturu grafu z´avislost´ı blok˚ u. Sipky souvislou ˇcarou ukazuj´ı pˇrechody mezi bloky, kde je moˇzn´e pouˇz´ıt zˇretˇezen´ı. Naopak ˇsipky pˇreruˇsovanou ˇcarou znaˇc´ı dynamick´e ukonˇcen´ı a nutnost pouˇzit´ı dispatcheru. Funkce A obsahuje v jedn´e sv´e moˇzn´e vˇetvi v´ ypoˇctu pˇr´ımou rekurzi. Funkce B demonstruje smyˇcku v programu a tedy fragmentaci k´odu (fragmentace viz. odstavec 2.3.4). V tomto pˇr´ıkladu pˇredpokl´ ad´ ame pouˇzit´ı absolutn´ıch adres u instrukc´ı call. ˇ Pˇr´ısluˇsn´ y graf z´avislost´ı blok˚ u je uk´az´an na obr´ azku 2.12. Sipky pˇreruˇsovanou ˇcarou ukazuj´ı ˇ hrany, kter´e graf neobsahuje z d˚ uvodu dynamick´e povahy ukonˇcen´ı bloku instrukc´ı ret. Sipky tuˇcnou ˇcarou vyznaˇcuj´ı z´avislosti zapˇr´ıˇcinˇen´e intrukcemi call. Vol´an´ı pod procedur b´ yv´ a ˇcasto dynamick´eho charakteru. Jedn´ a se tedy o ˇcast´e m´ısto pˇreruˇsen´ı integrity grafu z´avislost´ı. D´ıky dynamick´e povaze ukonˇcen´ı instrukc´ı ret je graf z´avislosti pravidelnˇe pˇreruˇsov´an n´avraty z funkc´ı. Dobrou uk´azku dopadu t´eto skuteˇcnosti n´am poskytne graf na obr´ azku 2.12, pokud nebudeme uvaˇzovat z´avislost mezi bloky 6 a 3, kter´a je zp˚ usobena podm´ınˇen´ ym skokem. Zvl´aˇstˇe funkce obsahuj´ıc´ı sadu vol´an´ı pod procedur se ve v´ ysledku rozpadnou na nˇekolik izolovan´ ych podgraf˚ u grafu z´avislost´ı blok˚ u.

2.3.6

Obsluha vl´ aken

ˇ sen´ı emulace v´ıcevl´aknov´ Reˇ ych program˚ u je jednou z nˇejtˇeˇzˇs´ıch ˇc´ast´ı cel´eho n´avrhu. Nab´ızej´ı se dva pˇr´ıstupy: paraleln´ı emulace vl´ aken a serializace vl´ aken. Pro u ´ˇcely navrhovan´eho emulatoru pouˇzijeme ˇreˇsen´ı, kter´e kombinuje hlavn´ı v´ yhody obou pˇr´ıstup˚ u s pˇrijateln´ ymi komplikacemi, nazvan´e ˇca ´steˇcn´ a serializace vl´ aken.

´ ´ KAPITOLA 2. NAVRH EMULATORU

21

rekurze volání podprocedury funkce A

funkce B

blok 1

blok 4

jne jmp

blok 5 blok 2 loop

blok 3

loop

ret

call A

ret

jne call B

blok 6

funkce C zde neuvádíme jednotlivé bloky

call C

Obr´azek 2.11: Struktura blok˚ u pˇri emulaci re´aln´eho k´ odu x86

1

3

6

funkce C

2

4

5

Obr´azek 2.12: Graf z´avislosti blok˚ u k pˇr´ıkladu z obr´ azku 2.11

22

´ ´ KAPITOLA 2. NAVRH EMULATORU

Paraleln´ı emulace vl´ aken Prvn´ı z moˇzn´ ych pˇr´ıstup˚ u je paraleln´ı emulace kaˇzd´eho vl´ akna. Kaˇzd´ y poˇzadavek emulovan´eho programu na vytvoˇren´ı nov´eho vl´ akna znamen´a pro emul´ ator nutnost vytvoˇrit dalˇs´ı instanci emulaˇcn´ı smyˇcky. Jednotliv´e instance pak soupeˇr´ı o pˇr´ıstup ke sd´ılen´ ym datov´ ym struktur´ am jako je sklad nebo mapa z´avislost´ı blok˚ u. Nastane tak probl´em se synchronizac´ı pˇr´ıstupu. Vˇetˇs´ım probl´emem je ale emulace k´odu, kter´ y se za bˇehu s´ am modifikuje. Dojde-li k z´apisu do pamˇeti, ze kter´e emulaˇcn´ı smyˇcka pˇreloˇzila blok, je tˇreba jej zneplatnit (vyjmout jej ze skladu a mapy z´avislost´ı blok˚ u). K jeˇstˇe vetˇs´ım probl´em˚ um dojde, pokud nˇekter´e z vl´ aken dan´ y blok pr´avˇe vykon´ av´a. Dalˇs´ı nepˇr´ıjemnost´ı je fakt, ˇze zvolen´ y zp˚ usob pˇrekladu resp. instrumentace k´odu emulovan´eho programu v´aˇze vytv´aˇren´e bloky na konkr´etn´ı instanci ˇr´ıd´ıc´ıho bloku. Bylo by tedy nutn´e vytvoˇrit pro kaˇzd´e vl´ akno vlastn´ı kopii bloku v pˇr´ıpadˇe, ˇze jej vyuˇz´ıv´ a v´ıce vl´ aken nebo zmˇenit zp˚ usob pˇrekladu, kter´ y by vedl nutnˇe ke zvˇetˇsen´ı ˇreˇzie spojen´e s emulac´ı. Z´asadn´ı v´ yhodou tohoto ˇreˇsen´ı je vˇernˇejˇs´ı model v´ ypoˇctu emulovan´eho programu. V syst´emu je skuteˇcnˇe pˇr´ıtomno takov´e mnoˇzstv´ı vl´ aken, kolik by tam bylo pˇri v´ ypoˇctu bez emulace. Odpadaj´ı tak´e probl´emy s emulac´ı synchronizaˇcn´ıch mechanism˚ u operaˇcn´ıho syst´emu, protoˇze se mohou s v´ yhodou pouˇz´ıt tak, jak by je emulovan´ y program vyuˇzil pˇri bˇehu bez emulace. Tento pˇr´ıstup je vhodnˇejˇs´ı pro emul´ ator zac´ılen´ y na aplikace, u kter´ ych se pˇredpokl´ ad´ a masov´e vyuˇzit´ı v´ıce vl´ aken. Vhodnou volbou by byl pro implementaci emul´ atoru s r˚ uznou zdrojovou a c´ılovou platformou kde se pˇredpokl´ ad´ a vyuˇzit´ı pro bˇeˇzn´e pouˇstˇen´ı aplikac´ı.

Serializace vl´ aken Druh´ y pˇristup se snaˇz´ı vyvarovat nutnosti ˇreˇsit synchronizaˇcn´ı ot´ azky nad datov´ ymi strukturami nutn´ ymi pro emulaci za cenu ztr´ aty v´ ykonu v´ıcevlaknov´ ych aplikac´ı na v´ıceprocesorov´em resp. v´ıcevl´aknov´em12 poˇc´ıtaˇci. Existuje jen hlavn´ı emulaˇcn´ı smyˇcka spolu s hlavn´ım ˇr´ıd´ıc´ım ˇ blokem, kter´e m˚ uˇze v jednu chv´ıli vyuˇz´ıvat pouze jedno vl´ akno. Cinnost vl´ aken je tak serializov´ana podobnˇe jako je tomu na syst´emech s jedn´ım (jednovl´ aknov´ ym) procesorem. I toto ˇreˇsen´ı vˇsak m´ a, vedle potenci´aln´ıho v´ ykonnostn´ıho dopadu, ˇradu probl´em˚ u. Vzhledem k tomu, ˇze serializace vl´ aken potlaˇcuje pl´ anovac´ı algoritmus operaˇcn´ıho syst´emu, mus´ıme se o pˇridˇelov´an´ı strojov´eho ˇcasu jednotliv´ ym vl´ akn˚ um postarat sami. Jako jednotku ˇcasu je zde tˇreba vz´ıt ˇcas potˇrebn´ y k vykon´ an´ı jednoho bloku. N´ ami navrˇzen´ y mechanismus dˇelen´ı k´odu na bloky vˇsak vytv´aˇr´ı bloky nestejn´e d´elky, coˇz znamen´a r˚ uzn´e ˇcasov´e kvanta zaloˇzen´e na jejich v´ ypoˇctu. Toto vˇsak nen´ı zdaleka tak oˇzehav´e jako nebezpeˇc´ı hladovˇen´ı13 nˇekter´ ych vl´ aken. Aplikujeme-li totiˇz mechanizmus ˇretˇezen´ı blok˚ u, bude ˇcasto doch´azet ke smyˇck´ am tvoˇren´ ym zˇretˇezen´ ymi bloky. Pˇri vykon´ av´an´ı takov´e smyˇcky nedojde k vol´an´ı Dispatcheru a emul´ ator tedy nebude m´ıt moˇznost napl´anovat ˇcinnost dalˇs´ıho vl´ akna. Emulaˇcn´ı smyˇcka se nav´ıc ocitne bez moˇznosti potenci´alnˇe nekoneˇcn´ y v´ ypoˇcet zastavit. Dalˇs´ı velkou nepˇr´ıjemnost´ı je nutnost emulace synchronizaˇcn´ıch funkc´ı operaˇcn´ıho syst´emu, kter´e d´ıky vlastn´ımu pl´ anovac´ımu mechanismu potlaˇcujeme. Naopak hlavn´ı v´ yhodou tohoto pˇr´ıstupu je snadnˇejˇs´ı zvl´adnut´ı k´odu, kter´ y se za bˇehu s´ am modifikuje. Odpad´a nutnost sledovat, zda nˇekter´a z paraleln´ıch emulaˇcn´ıch smyˇcek nevykon´ av´a blok pˇreloˇzen´ y z k´odu, kter´ y je nˇekterou jinou smyˇckou pr´avˇe modifikov´an. 12 Term´ın v´ıcevl´ aknov´ y poˇc´ıtaˇc oznaˇcuje hardware schopn´ y v´ ykonu v´ıce vl´ aken v´ ypoˇctu najednou. V dneˇsn´ı dobˇe pˇrest´ av´ a platit, ˇze v´ıce vl´ aken najednou znamen´ a nutnˇe v´ıce procesor˚ u. Modern´ı procesory jsou ˇcasto schopn´e urˇcit´e paralelizace v´ ypoˇctu na urˇcit´e u ´rovni. Toto se dosahuje vˇetˇs´ım poˇctem jader, nebo zvˇetˇsen´ım poˇctu funkˇcn´ıch blok˚ u jedin´eho j´ adra - Hyperthreading firmy Intel. 13 Term´ın hladovˇen´ı oznaˇcuje situaci, kdy nedoch´ az´ı k pˇridˇelov´ an´ı strojov´eho ˇcasu vl´ aknu. Toto oznaˇcen´ı v´ ych´ az´ı z probl´emu paraleln´ıch syst´emu zn´ am´eho jako ”Veˇceˇr´ıc´ı filozofov´e”.

´ ´ KAPITOLA 2. NAVRH EMULATORU

23

ˇ asteˇ C´ cn´ a serializace vl´ aken Pˇri bliˇzˇs´ım zkoum´an´ı povahy bˇehu aplikac´ı m˚ uˇzeme vyˇclenit jistou ˇc´ast, kterou tvoˇr´ı v´ ypoˇcet dynamicky linkovan´ ych knihoven. Operaˇcn´ı syst´emy tak zabraˇ nuj´ı zbyteˇcn´e redundanci k´odu, kter´a by nastala, pokud by aplikace nemohla nˇekter´e ˇcasto pouˇz´ıvan´e funkce sd´ılet s ostatn´ımi. Operaˇcn´ı syst´emy firmy Microsoft realizuj´ı sv´e API formou dynamicky linkovan´ ych knihoven. K´od, obsaˇzen´ y v tˇechto knihovn´ach, nem´a smysl emulovat, protoˇze ˇcinnost pˇr´ısluˇsn´ ych funkc´ı je dobˇre zn´ ama. Pˇredmˇetem anal´ yzy je pouze k´od pracuj´ıc´ı nad tˇemito knihovnami. Tato u ´vaha definuje u ´roveˇ n, na kter´e m˚ uˇzeme pˇrenechat v´ ypoˇcet k´odu zcela c´ılov´e platformˇe, pokud je stejn´ a jako zdrojov´a (coˇz je n´aˇs pˇr´ıpad). Tato u ´roveˇ n je z´aroveˇ n m´ıstem, kde zaˇc´ın´ a hr´at svou roli emul´ ator operaˇcn´ıho syst´emu. Hlavn´ım pozitivn´ım dopadem je velk´e zrychlen´ı emulace zp˚ usoben´e zmenˇsen´ım velikosti emulovan´eho k´odu, kter´a tak prob´ıh´ a pouze na k´odu, jehoˇz ˇcinnost dopˇredu nezn´ame. Nab´ız´ı se moˇznost nechat tyto neemulovan´e ˇc´asti v´ ypoˇctu aplikace prob´ıhat paralelnˇe. Po vzoru paraleln´ı emulace dostane kaˇzd´e vl´ akno sv˚ uj ˇr´ıd´ıc´ı blok vyuˇz´ıvan´ y pro paraleln´ı ˇc´ast bˇehu dispatcheru. Pˇriprav´ıme nav´ıc i hlavn´ı ˇr´ıd´ıc´ı blok spolu s jedinou (hlavn´ı) instanc´ı emulaˇcn´ı smyˇcky tak, jak tomu je pˇri serializaci vl´ aken. Pˇri tvorbˇe blok˚ u pak pro pˇreklad instrukc´ı pouˇzijeme pouze hlavn´ı ˇr´ıd´ıc´ı blok. Nebude tedy nutn´e vytv´aˇret v´ıce kopi´ı t´ehoˇz bloku. Vznikne-li v emulovan´e aplikaci nov´e vl´ akno, emul´ ator operaˇcn´ıho syst´emu (v r´amci emulace syst´emov´e funkce pro tvorbu nov´eho vl´ akna) skuteˇcnˇe poˇz´ad´ a syst´em o vytvoˇren´ı vl´ akna, kter´e vˇsak, jako prvn´ı krok sv´e existence, zavol´a dispatcher s adresou zaˇc´atku k´odu, kter´ y by pˇri bˇehu bez emulace vykon´ avalo. Dispatcher na opl´atku zavol´a funkci emulaˇcn´ı smyˇcky AttachThread, kter´a si vyˇz´ad´ a pˇridˇelen´ı emulaˇcn´ı smyˇcky. Do emulaˇcn´ı smyˇcky je tedy dovoleno v jednom ˇcase vstoupit pouze jednomu vl´ aknu. Pokud dojde k vyprˇsen´ı ˇcasu pˇridˇelen´eho vl´ aknu nebo pokud vl´ akno zavol´a funkci nˇekter´e neemulovan´e dynamicky linkovan´e knihovny, postar´ a se dispatcher o zavolan´ı funkce DetachThread, kter´a odpoj´ı vl´ akno od emulaˇcn´ı smyˇcky a dovol´ı tak jin´emu vl´ aknu uˇzit´ı emulace k´odu. Po odpojen´ı jiˇz vl´ akna pracuj´ı paralelnˇe. Vzhledem k tomu, ˇze pˇr´ıstup do datov´ ych struktur nutn´ ych pro emulaci, se dˇeje pouze v emulaˇcn´ı smyˇcce, nen´ı nutn´a ˇz´adn´ a dalˇs´ı synchronizace. Nen´ı tˇreba ani emulovat synchronizaˇcn´ı mechanizmy operaˇcn´ıho syst´emu, protoˇze kaˇzd´e vl´ akno je tvoˇreno skuteˇcn´ ym vl´ aknem a m˚ uˇzeme tedy s u ´spˇechem vyuˇz´ıt sluˇzeb syst´emu, kter´e jsou vol´any paralelnˇe (podobnˇe, jako by tomu bylo pˇri bˇehu bez emulace). Stavov´ y diagram popisuj´ıc´ı stadia, ve kter´ ych se vl´ akna pˇri emulaci nach´azej´ı, ukazuje obr. 2.13. Pˇ ridˇ elov´ an´ı ˇ casov´ eho kvanta Pouˇzit´ım ˇc´asteˇcn´e serializace vznik´ a pro emul´ ator povinnost starat se o pl´ anov´an´ı vl´ aken. Kl´ıˇcovou roli zde hraje urˇcen´ı optim´aln´ıho ˇcasov´eho kvanta, coˇz je nejdelˇs´ı moˇzn´ a doba pˇridˇelen´ı emulaˇcn´ı smyˇcky jednomu vl´ aknu. Mus´ıme tak´e zajistit jeho spr´ avn´e pˇridˇelov´an´ı. Aplikov´an´ım principu zˇretˇezen´ı blok˚ u nast´ av´a moˇznost vzniku smyˇcky tvoˇren´e pouze zˇretˇezen´ ymi bloky. Emulace takov´e smyˇcky pak prob´ıh´ a zcela bez uˇzit´ı dispatcheru a nen´ı ji tedy moˇzn´e jakkoliv pˇreruˇsit. Tento probl´em m˚ uˇzeme ˇreˇsit bud’ zamezen´ım vzniku smyˇcek tvoˇren´ ych zˇretˇezen´ ymi bloky (zamezen´ı vzniku smyˇcek v grafu z´avislost´ı blok˚ u) nebo vynucen´ım vol´an´ı k´odu, kter´ y bude m´ıt moˇznost pˇr´ıpadnˇe volat dispatcher. Zamezen´ı tvorby smyˇcek vede na v´ ypoˇcetnˇe n´aroˇcn´ y algoritmus, kter´ y pˇri poˇzadavku na zˇretˇezen´ı bloku zjist´ı, zda nov´a z´avislost neuzav´ır´ a smyˇcku v grafu z´avislost´ı. Pokud by typick´a smyˇcka obsahovala velk´e mnoˇzstv´ı blok˚ u, bylo by toto ˇreˇsen´ı zˇrejmˇe vhodn´e. Velmi ˇcasto ale vznikaj´ı smyˇcky v r´ amci jednoho bloku (viz. pˇr´ıklad na obr´ azku 2.11, kde funkce B obsahuje smyˇcku pˇri emulaci instrukce loop). Vol´an´ı dispatcheru pˇri kaˇzd´e iteraci by se velmi neblaze

´ ´ KAPITOLA 2. NAVRH EMULATORU

24 start vlákna

paralelní oblast čekání na přidělení emulační smyčky

vykonávání neemulované funkce DLL knihovny

AttachThread

DetachThread

DetachThread

emulace kódu serializovaná oblast

vypršení časového kvanta

Obr´azek 2.13: Stavov´ y diagram vl´ akna pˇri emulaci projevilo na efektivitˇe emulace. M´ısto dispatcheru m˚ uˇzeme do tˇechto smyˇcek vkl´adat mnohem m´enˇe sloˇzit´ y k´od, kter´ y bude pouze kontrolovat ˇcasov´e kvantum a pˇr´ıpadnˇe zavol´a dispatcher. Pˇr´ıklad takov´eho k´odu pracuj´ıc´ıho nav´ıc v kontextu emulovan´eho programu (nen´ı tedy tˇreba pˇrep´ınat kontext) je uk´az´an na obr´ azku 2.14. Vyˇreˇsili jsme probl´em potenci´aln´ıch smyˇcek tvoˇren´ ych zˇretˇezen´ ymi bloky. Nast´av´a vˇsak probl´em s dodrˇzov´an´ım stejn´eho ˇcasov´eho kvanta pro vˇsechna vl´ akna. Vzhledem k tomu, ˇze smyˇcky jsou obecnˇe nestejn´e d´elky, bude m´ıt kaˇzd´ a dekrementace hodnoty zb´ yvaj´ıc´ıho ˇcasov´eho kvanta jinou v´ahu. Nem˚ uˇzeme se bohuˇzel spolehnout na pr˚ umˇernou d´elku smyˇcky, protoˇze pˇri intenzivn´ım v´ ypoˇctu pouˇz´ıvaj´ı programy v mˇeˇr´ıtku d´elky jednoho ˇcasov´eho kvanta nˇekolik m´ alo smyˇcek. Dopad nestejn´e d´elky smyˇcek, a tedy r˚ uzn´e ˇcasov´e n´aroˇcnosti jejich emulace, m˚ uˇzeme zm´ırnit vloˇzen´ım kontroly ˇcasov´eho kvanta na zaˇc´atek kaˇzd´eho bloku. Probl´em tedy pˇren´ aˇs´ıme z pr˚ umˇern´e d´elky smyˇcky na pr˚ umˇernou d´elku bloku. Je zˇrejm´e, ˇze blok˚ u bude vykon´ ano stejnˇe nebo v´ıce neˇz smyˇcek a u ´daj pr˚ umˇern´e d´elky bude m´ıt tedy vˇetˇs´ı vypov´ıdac´ı hodnotu. Dopad na efektivitu emulace by nav´ıc nemusel b´ yt v´ yraznˇe vyˇsˇs´ı oproti ˇreˇsen´ı s jednou kontrolou na smyˇcku. Vˇse z´aleˇz´ı na konkr´etn´ıch d´elk´ach smyˇcek. V r´amci jedn´e funkce vznikaj´ı ˇcasto smyˇcky o jednom bloku. V emul´ atoru implementujeme kontrolu ˇcasov´eho kvanta na zaˇc´atku kaˇzd´eho bloku. V prvn´ı verzi emul´ atoru uˇzit´e pro z´akladn´ı anal´ yzu emulovan´ ych program˚ u kontrola ˇcasov´eho kvanta nen´ı zahrnuta z d˚ uvod˚ u sn´ıˇzen´ı ˇcasov´ ych n´arok˚ u na testov´an´ı.

2.4

Emul´ ator operaˇ cn´ıho syst´ emu

V ˇc´asti vˇenovan´e emulaˇcn´ı smyˇcce se zab´ yv´ ame tvorbou modelu emulovan´eho programu, kter´ y se skl´ ad´ a z jednotliv´ ych blok˚ u a pˇridruˇzen´ ych datov´ ych struktur nutn´ ych pro jejich organizaci. Pˇredstav´ıme-li si emulovan´ y program jako koneˇcn´ y automat, bude pro n´as model pˇredstavovat jeho pˇrechodovou tabulku. Jednotliv´e stavy myˇslen´eho koneˇcn´eho automatu pˇredstavuj´ı stavy emulovan´eho programu tvoˇren´e obsahem pamˇeti (operaˇcn´ı pamˇet´ı, obsahem pevn´eho disku atp.) a stavem procesoru. Pro manipulaci se stavem procesoru a operaˇcn´ı pamˇet´ı pouˇz´ıv´ a emulovan´ y program pˇr´ımo instrukce. Pro pr´aci s jin´ ymi subsyst´emy, kter´e mohou spolutvoˇrit stav emulovan´eho programu (souborov´ y syst´em na disku, syst´emov´a registraˇcn´ı datab´ aze - Windows

´ ´ KAPITOLA 2. NAVRH EMULATORU

25

; uloˇ zen´ ı hodnoty registru ecx mov dword ptr [TemporaryStorage1], ecx ; naˇ cten´ ı zb´ yvaj´ ıc´ ıho kvanta do ecx mov ecx, dword ptr[ThreadTimeSlice] loop

continue

; ˇ casov´ e kvantum vyprˇ selo jmp dispatcher continue: ; uloˇ zen´ ı dekrementovan´ e hodnoty kvanta mov dword ptr[ThreadTimeSlice], ecx ; obnoven´ ı p˚ uvodn´ ı hodnoty registru ecx mov ecx, dword ptr [TemporaryStorage1] Obr´azek 2.14: K´od kontroluj´ıc´ı ˇcasov´e kvantum vl´ akna Registry atp.), mus´ı pouˇz´ıt sluˇzeb operaˇcn´ıho syst´emu. ´ Ukolem emul´ atoru operaˇcn´ıho syst´emu je pr´avˇe modelov´an´ı tˇechto stav˚ u tak, aby neovlivˇ novaly neˇz´adouc´ım zp˚ usobem stav skuteˇcn´eho poˇc´ıtaˇce uˇzit´eho pro emulaci. Emulovan´emu programu mus´ıme v prvn´ı ˇradˇe zamezit pˇr´ıstup ke skuteˇcn´emu poˇc´ıtaˇci. Toho dos´ ahneme nahrazen´ım API operaˇcn´ıho syst´emu emulovanou verz´ı (emulovan´ y program nebude m´ıt pˇr´ıstup k subsyst´em˚ um operaˇcn´ıho syst´emu) a pˇrekladem vˇsech instrukc´ı pˇristupuj´ıc´ıch do operaˇcn´ı pamˇeti. 2.4.1

Akce emulovan´ eho programu z pohledu bezpeˇ cnosti

Vˇenujme se chv´ıli kr´atk´e u ´vaze o obvykl´ ych a neobvykl´ ych (podezˇrel´ ych) akc´ıch emulovan´eho programu. Program, za u ´ˇcelem plnˇen´ı sv´eho u ´kolu, vyuˇz´ıv´ a prostˇredky, kter´e mu operaˇcn´ı syst´em poskytuje. Kl´ıˇcov´ y je ale zp˚ usob, jak tyto prostˇredky vyuˇz´ıv´ a. Operaˇcn´ı syst´em nab´ız´ı jak´ ysi model – abstrakci poˇc´ıtaˇce sloˇzenou z jednotliv´ ych subsyst´em˚ u, kter´e si lze pˇredstavit jako koneˇcn´ y stavov´ y automat s povolen´ ymi operacemi pro kaˇzd´ y stav. Souborov´ y syst´em je dobr´ ym pˇr´ıkladem takov´eho automat. Nem˚ uˇzete pracovat se souborem, dokud jej neotevˇrete. Bˇeˇzn´ ym chov´an´ım programu je nejprve otevˇr´ıt soubor a pak do nˇej zapsat. Lze vˇsak ale postupovat i jinak. Funkce pro z´apis do souboru poˇzaduje jako parametr identifik´ator souboru, kter´ y je ve Windows implementov´an jako cel´e ˇctyˇrbytov´e ˇc´ıslo14 . Pˇr´ısluˇsnou hodnotu ˇc´ısla m˚ uˇzeme z´ıskat r˚ uznˇe. Obvykl´ y zp˚ usob je vol´an´ı funkce operaˇcn´ıho syst´emu. Neobvykl´e je naˇcten´ı ˇc´ısla z nˇejak´e pozice v pamˇeti, kter´a patˇr´ı nav´ıc jin´emu modulu a jeho n´asledn´e uˇzit´ı jako identifik´ator souboru. Jin´e moduly (dynamick´e knihovny) k implementaci sv´ ych funkc´ı mohou uˇz´ıt soubory a pˇri analyzov´an´ı jejich k´odu lze pˇr´ısluˇsnou pozici obsahuj´ıc´ı identifik´ator souboru snadno nal´ezt15 . C´ılem naˇseho emul´ atoru je vytvoˇrit model emulovan´eho program tak, abychom identifikovali takovou neobvyklou ˇcinnost a zamezili jejich dopadu na stav poˇc´ıtaˇce aniˇz by emulovan´ y program detekoval nezdar dotyˇcn´e akce. 14

Jde o zn´ am´ y HANDLE – identifik´ ator objektu v syst´emu. Z hlediska typov´e kontroly se nejedn´ a o ˇc´ıseln´ y typ, ale napˇr. v jazyce C je pˇr´ısluˇsn´e pˇretypov´ an´ı rutinn´ı z´ aleˇzitost´ı. 15 Budeme-li napˇr´ıklad sledovat vol´ an´ı funkc´ı pracuj´ıc´ıch se soubory, m˚ uˇzeme vysledovat pozici, na kterou bude uloˇzen pˇr´ısluˇsn´ y parametr na z´ asobn´ık. Zavol´ ame funkci knihovny, kter´ a se s vyuˇzit´ım naˇseho z´ asobn´ıku vykon´ a a pak uˇz jenom nahrajeme hodnotu identifik´ atoru z pˇr´ısluˇsn´e pozice za vrcholem z´ asobn´ıku.

´ ´ KAPITOLA 2. NAVRH EMULATORU

26

Rozd´ıly sandboxu tvoˇ ren´ eho Windows a emul´ atorem V´ yˇse popsan´ y pˇr´ıklad neobvykl´e a podezˇrel´e ˇcinnosti je z pohledu Windows zcela v poˇr´adku. Jak´akoliv dynamick´a knihovna je pouze pˇridan´ ym k´odem, kter´ y rozˇsiˇruje program a je tedy zcela v jeho reˇzii, jak s t´ımto k´odem naloˇz´ı. Operaˇcn´ı syst´em Windows se star´ a pouze o to, aby nedoˇslo k poˇskozen´ı jin´ ych soubˇeˇznˇe bˇeˇz´ıc´ıch program˚ u. Vytv´ aˇr´ı tedy sandbox, kter´ y je tvoˇren adresov´ ym prostorem a mnoˇzinou dostupn´ ych syst´emov´ ych sluˇzeb. Zodpovˇednost´ı emul´ atoru je vytvoˇrit kompatibiln´ı sandbox tak, aby v nˇem bylo moˇzn´e spustit emulovan´ y program. Oproti origin´ alu tvoˇren´emu operaˇcn´ım syst´emem emul´ ator dovoluje mnohem uˇzˇs´ı mnoˇzinu operac´ı. Emulovan´emu programu v prvn´ı ˇradˇe zamez´ıme pˇr´ıstup do pamˇeti mimo jeho modul a oblasti, kter´e si pˇredt´ım korektnˇe nerezervoval vol´an´ım pˇr´ısluˇsn´e funkce operaˇcn´ıho syst´emu (viz. odstavec 2.4.3). D´ ale budeme emulovat nˇekter´e subsyst´emy operaˇcn´ıho syst´emu, jejichˇz zmˇena by jej mohla nevratnˇe poˇskodit (viz. odstavec 2.4.2). 2.4.2

Emulace API operaˇ cn´ıho syst´ emu

Pro emulaci API operaˇcn´ıho syst´emu je kl´ıˇcov´e rozpozn´an´ı okamˇziku, kdy emulovan´ y program uskuteˇcn ˇuje vol´an´ı do nˇekter´e z procedur tvoˇr´ıc´ı API operaˇcn´ıho syst´emu Windows (dokumentace v [9]). Po detekci n´asleduje pˇr´ıpadn´e vol´an´ı emulovan´e verze pˇr´ısluˇsn´e metody – jde tedy o pˇresmˇerov´ an´ı vol´ an´ı. Vzhledem k tomu, ˇze vol´an´ı procedury (instrukce call) znamen´a konec bloku a vol´an´ı dispatcheru, nask´ yt´ a se moˇznost prov´adˇet detekci vol´an´ı API funkce pr´avˇe na zaˇc´atku dispatcheru. Existuje samozˇrejmˇe v´ıce moˇznost´ı, jak detekovat vol´an´ı API funkce. Jedna s obl´ıben´ ych metod je zaloˇzena na pˇrepisu tabulky import˚ u spustiteln´eho modulu emulovan´eho programu16 . V ˇr´adc´ıch tabulky pˇr´ısluˇsej´ıc´ıch funkc´ım, kter´e chceme pˇresmˇerovat, pˇrep´ıˇseme adresu tak, aby byla vol´ana naˇse verze funkce. Samotn´e vol´an´ı funkce API nen´ı nic jin´eho neˇz prost´e pˇresunut´ı v´ ypoˇctu vol´an´ım instrukce call a jej´ım operandem nemus´ı b´ yt nutnˇe ukazatel nˇekam do tabulky import˚ u. Adresu poˇc´atku API funkce (resp. exportovan´e funkce DLL knihovny obecnˇe) lze z´ıskat napˇr´ıklad vol´an´ım API funkce GetProcAddress nebo nˇejak´ ym spekulativn´ım zp˚ usobem. Jestliˇze chceme postihnout vˇsechny moˇzn´e zp˚ usoby, jak pˇren´est v´ ypoˇcet do API funkce, mus´ıme kontrolovat veˇsker´e instrukce mˇen´ıc´ı bˇeh v´ ypoˇctu. Je tedy zˇrejm´e, ˇze detekce vol´an´ı API funkce na poˇc´atku v´ ypoˇctu dispatcheru je velmi dobr´ ym ˇreˇsen´ım. Samotn´a detekce je zaloˇzena na kontrole adresy, na kterou se emulovan´ y program chyst´a pˇrej´ıt. Jestliˇze se tato adresa shoduje s adresou nˇekter´e z funkc´ı API operaˇcn´ıho syst´emu Windows, je tˇreba ji pˇr´ıpadnˇe nahradit naˇs´ı implementac´ı (nˇekter´e funkce je moˇzn´e ponechat zcela na operaˇcn´ım syst´emu, protoˇze nijak neohroˇzuj´ı ostatn´ı programy nebo data). Kl´ıˇcem pro kontrolu je adresa stejn´eho form´ atu, jako je kl´ıˇc pro hled´an´ı ve skladu blok˚ u. Z v´ yhodou tedy vyuˇzijeme jiˇz hotovou datovou strukturu spolu s pˇridruˇzen´ ymi funkcemi. Mapa zn´ am´ ych API funkc´ı Mapa API funkc´ı je implementaˇcnˇe totoˇzn´ a se skladem blok˚ u. Pˇri inicializaci emul´ atoru syst´emu je tˇreba do mapy vloˇzit informace o zn´ am´ych funkc´ıch. Datov´ y objekt popisuj´ıc´ı zn´ amou funkci 16 Modul spustiteln´eho programu ve form´ atu COFF/PE obsahuje tabulku, jej´ıˇz poloˇzky tvoˇr´ı instrukce jmp s operandem v podobˇe absolutn´ı adresy. Po nahran´ı vˇsech modul˚ u, kter´e dotyˇcn´ y modul vyuˇz´ıv´ a, jsou operandy instrukc´ı jmp nahrazeny konkr´etn´ımi adresami pˇr´ısluˇsn´ ych funkc´ı. Tento mechanizmus umoˇzn ˇuje k´ odu aplikace volat API funkce instrukc´ı call s adresou ukazuj´ıc´ı na poloˇzku v tabulce import˚ u, kde se n´ asledn´ ym proveden´ım instrukce jmp skoˇc´ı na k´ od pˇr´ısluˇsn´e funkce. At’ uˇz je nahr´ an nˇekter´ y z poˇzadovan´ ych modul˚ u kdekoliv v pamˇeti, staˇc´ı modifikovat pouze tabulku import˚ u a ne kaˇzd´e vol´ an´ı funkce modulu zvl´ aˇst’.

´ ´ KAPITOLA 2. NAVRH EMULATORU

27

mus´ı poskytnout dostateˇcn´e mnoˇzstv´ı informac´ı pro spolehlivou lokalizaci poˇc´atku funkce v adresov´em prostoru. V naˇsem emul´ atoru identifikujeme funkci pˇri inicializaci mapy API funkc´ı pomoc´ı offsetu v r´amci modulu, kter´ y funkci obsahuje. Kdybychom spol´ehali na vˇzdy stejnou pozici nahr´ an´ı modul˚ u (DLL knihoven), bylo by moˇzn´e identifikovat jednotliv´e funkce pˇr´ımo jejich adresou. Poˇc´ateˇcn´ı adresa modulu vˇsak nen´ı nemˇenn´ a d´ıky moˇzn´e kolizi mapov´an´ı s jin´ ym modulem a n´asledn´e relokaci (relokaˇcn´ı mechanismus operaˇcn´ıho syst´emu Windows popisujeme tak´e v pozn´amce k odstavci 2.2). V r´amci inicializaˇcn´ıho procesu se vkl´adaj´ı do mapy API jen ty zn´ ame funkce, jejichˇz knihovny jsou nahran´e v pamˇeti. Bˇehem emulace se pak snaˇz´ıme reagovat na nahr´ av´an´ı a vyj´ım´an´ı jednotliv´ ych knihoven z pamˇeti patˇriˇcnou aktualizac´ı dat v mapˇe API funkc´ı. Informace o zn´ am´ ych API funkc´ıch spolu s offsety v r´amci pˇr´ısluˇsn´ ych modul˚ u a adresami jejich emulovan´ ych verz´ı jsou udrˇzov´any v tabulk´ach. Prvn´ı u ´rovn´ı hierarchick´eho seznamu zn´ am´ ych funkc´ı je tabulka jednotliv´ ych zn´ am´ych knihoven spolu s odkazy na tabulky funkc´ı, kter´e tvoˇr´ı druhou u ´roveˇ n. D˚ uleˇzit´e datov´e struktury v kontextu emulace API operaˇcn´ıho syst´emu jsou uk´az´any na obr´ azku 2.15. tabulka známých knihoven jméno advapi32.dll user32.dll kernel32.dll

adresa počátku 0x77dd0000 0x77d40000 0x7c800000

známé funkce

známé funkce

jméno CreateThreadA GetVersionA

známé funkce offset 0x4ed3 0x1e45

implementace SfCreateThreadA NULL

emulovaná funkce (odkaz do kódu emulátoru systému)

adresa

mapa API funkcí

implementace

0x7c804ed3

SfCreateThreadA

0x7c801e45

GetVersionA

neemulovaná funkce (volá se původní funkce OS)

Obr´azek 2.15: Datov´e struktury v kontextu emulace API operaˇcn´ıho syst´emu Pˇri nahr´ an´ı knihovny do pamˇeti (napˇr. API funkc´ı LoadLibrary) se nejprve vyhled´ a pˇr´ısluˇsn´ a knihovna. Pak dojde k vloˇzen´ı z´aznamu do mapy API funkc´ı pro kaˇzdou poloˇzku v tabulce zn´ am´ ych funkc´ı knihovny. Z bezpeˇcnostn´ıho hlediska je probl´emem jednoznaˇcn´ a identifikace knihovny s poloˇzkou v tabulce zn´ am´ ych knihoven. Prost´e porovn´an´ı podle jm´ena nepostihuje pˇr´ıpadn´e r˚ uzn´e verze knihovny

´ ´ KAPITOLA 2. NAVRH EMULATORU

28

resp. jej´ıho obsahu. Pro zajiˇstˇen´ı dostateˇcn´e bezpeˇcnosti by bylo nejsp´ıˇs tˇreba pouˇz´ıt nˇejakou formu bezpeˇcn´eho hash algoritmu (napˇr. SHA nebo MD5). Poˇc´ıt´ an´ı tˇechto algoritm˚ u v pr˚ ubˇehu emulace by se nejsp´ıˇs nepˇr´ıznivˇe projevilo na efektivitˇe emulace. Abychom zachovali co nejvˇetˇs´ı efektivitu emulace, m˚ uˇzeme zajiˇstˇen´ı autenticity knihovny nechat na nˇejak´em extern´ım n´astroji. Lze pˇredpokl´ adat, ˇze n´astroj pro dynamickou anal´ yzu bude zaˇclenˇen do vˇetˇs´ıho bal´ıku bezpeˇcnostn´ıho softwaru, v r´amci kter´eho m˚ uˇzeme zamezit pˇrepisu zn´ am´ ych knihoven 17 . Hash hodnotu tak m˚ uˇzeme spoˇc´ıtat a porovnat jen jednou (v´ ysledek uloˇzit napˇr. do inicializaˇcn´ıho souboru emul´ atoru) a pak uˇz pouze zabr´anit modifikaci dan´e knihovny. V prvn´ı verzi emul´ atoru identifikujeme DLL knihovnu pouze jej´ım jm´enem. Pˇri implementaci byl vˇsak kladen d˚ uraz na snadnou budouc´ı implementaci bezpeˇcnˇejˇs´ıho zp˚ usobu identifikace. Emulovan´ e verze API funkc´ı M´ ame-li zajiˇstˇen´ y mechanismus pro pˇresmˇerov´an´ı jednotliv´ ych vol´an´ı do DLL knihoven, m˚ uˇzeme se zab´ yvat implementac´ı emulovan´ ych verz´ı API funkc´ı. Nejvˇetˇs´ım probl´emem t´eto ˇc´asti n´avrhu a implementace emul´ atoru je pracnost. Kdybychom chtˇeli obs´ ahnout celou ˇsk´alu funkc´ı Windows API, museli bychom v podstatˇe naprogramovat velkou ˇc´ast samotn´eho operaˇcn´ıho syst´emu znovu. Pro implementaci emulovan´ ych verz´ı proto pouˇz´ıv´ ame skuteˇcn´e funkce API, ale db´ame pˇri tom na dodrˇzov´an´ı pravidel vypl´ yvaj´ıc´ıch se sandboxu emulovan´eho programu. ˇ ast funkc´ı nemus´ıme emulovat v˚ C´ ubec a m˚ uˇzeme nechat emulovan´ y program pouˇz´ıt skuteˇcnou API funkci (napˇr. funkce GetVersion). Nˇekter´e funkce naopak nepovol´ıme v˚ ubec vykonat. Napˇr. funkce GetMessage m˚ uˇze pozastavit vykon´ av´an´ı emulovan´eho programu na libovolnˇe dlouhou dobu. Je typicky vol´ana po vytvoˇren´ı okna aplikace a sb´ır´ a vstupy od uˇzivatele. V takov´em pˇr´ıpadˇe je potˇreba emulaci (dynamickou anal´ yzu) ukonˇcit a spokojit s daty, kter´e byly od zaˇc´atku emulace nasb´ır´ any. Na vol´an´ı funkce API budeme tedy reagovat tˇremi zp˚ usoby: emulace vol´ an´ı funkce, povolen´ı vol´ an´ı funkce a zak´ az´ an´ı vol´ an´ı funkce. 2.4.3

Pˇ reklad pˇ r´ıstupu do pamˇ eti

Z pohledu emulaˇcn´ı smyˇcky je pˇreklad pˇr´ıstup˚ u do pamˇeti pˇrekladem zdrojov´e instrukce pˇri tvorbˇe bloku. Na druhou stranu se jedn´ a o formu emulace syst´emov´eho prostˇredku – operaˇcn´ı pamˇeti. Mechanismus pˇrekladu pˇr´ıstupu do pamˇeti tedy leˇz´ı nˇekde na hranici emulaˇcn´ı smyˇcky a emul´ atoru operaˇcn´ıho syst´emu. Motivac´ı k zaveden´ı pˇrekladu pˇr´ıstup˚ u je zamezen´ı voln´eho p˚ usoben´ı emulovan´eho programu v r´amci sv´eho adresov´eho prostoru. Pˇrekladem tak´e realizujeme dynamickou relokaci nutnou k ˇreˇsen´ı kolize um´ıstˇen´ı modulu emul´ atoru a modulu emulovan´eho programu v adresov´em prostoru (bl´ıˇze viz. odstavec 2.2). Strategie ochrany pamˇ eti Ochrana pamˇeti znamen´a zamezen´ı pˇr´ıstupu emulovan´emu programu mimo oblasti, do kter´ ych m´ a na z´akladˇe volan´ ych sluˇzeb operaˇcn´ıho syst´emu pˇr´ıstup. Pro pˇr´ıstup (ˇcten´ı nebo z´apis) si mus´ı emulovan´ y program nejprve pˇr´ısluˇsn´e m´ısto v pamˇeti rezervovat (napˇr. pomoc´ı funkce API VirtualAlloc). Pro emul´ ator to znamen´a nutnost emulovat syst´emov´a vol´an´ı obsluhuj´ıc´ı operace s pamˇet´ı, na jejichˇz z´akladˇe mus´ı upravovat pˇr´ısluˇsn´e datov´e struktury definuj´ıc´ı oblasti, kde m˚ uˇze emulo17 Antivirov´e programy ˇcasto obsahuj´ı i vlastn´ı filtr instalovan´ y nad ovladaˇc syst´emu soubor˚ u, kter´ y umoˇzn ˇuje monitorovat veˇskerou ˇcinnost nad soubory a tedy i pˇr´ıpadnou modifikaci konkr´etn´ıho souboru.

´ ´ KAPITOLA 2. NAVRH EMULATORU

29

van´ y program operovat. Takovou strukturou je mapa str´ anek adresov´eho prostoru. Z n´azvu je patrn´e, ˇze jsme se rozhodli pracovat s adresov´ ym prostorem po jednotliv´ ych str´ank´ach (bloky o 4kB). V r´amci pˇrekladu instrukce pˇristupuj´ıc´ı do pamˇeti se na z´akladˇe absolutn´ı adresy vypoˇc´ıt´ a ˇ c´ılov´a str´anka. C´ıslo str´anky pak slouˇz´ı jako index do mapy str´anek adresov´eho prostoru, kter´ a je organizov´ana jako pole pro pˇr´ım´ y pˇr´ıstup obsahuj´ıc´ı offsety. M˚ uˇzeme tedy snadno pˇresmˇerovat (pˇridat offset) ke vˇsem pˇr´ıstup˚ um do zvolen´e str´anky. Str´anky, do kter´ ych povol´ıme emulovan´emu programu pˇr´ıstup, opatˇr´ıme nulov´ ym offsetem. Ochranu str´anky m˚ uˇzeme napˇr´ıklad prov´est pˇresmˇerov´an´ım na nultou str´anku, kter´a je vˇzdy chr´anˇena proti ˇcten´ı nebo z´apisu18 . Moˇznost´ı je samozˇrejmˇe v´ıce. M˚ uˇzeme napˇr´ıklad vytvoˇrit jak´esi smetiˇstˇe, kde povol´ıme ˇcten´ı i z´apis a pˇresmˇerujeme do nˇej vˇsechny nepovolen´e pamˇet’ov´e operace. Emulovan´ y program pouˇz´ıvaj´ıc´ı nˇejakou formu spekulativn´ıho naˇc´ıt´ an´ı hodnot bude m´ıt pak v´ yraznˇe st´ıˇzenou situaci. V prvn´ı verzi emul´ atoru implementujeme ochranu pˇresmˇerov´an´ım na prvn´ı pamˇet’ovou str´anku, kter´a spad´ a do oblasti se zak´ azan´ ym ˇcten´ım i z´apisem. Jde o ˇreˇsen´ı umoˇzn ˇuj´ıc´ı snadnˇejˇs´ı implementaci emulace API funkc´ı (kaˇzd´e vol´an´ı nezn´am´e API funkce vede na ˇcten´ı dat z modulu nˇekter´e chr´anˇen´e DLL knihovny a zp˚ usob´ı v´ yjimku a ukonˇcen´ı emulace). Pˇ reklad instrukc´ı s pamˇ et’ov´ ym operandem Operandem instrukce sady Intel x86 m˚ uˇze b´ yt registr, ˇc´ıslo nebo odkaz do pamˇeti. Operand tvoˇren´ y odkazem do pamˇeti je zad´an jedn´ım z dovolen´ ych adresaˇcn´ıch m´ od˚ u, na z´akladˇe kter´ ych vypoˇc´ıt´ a procesor konkr´etn´ı pozici v pamˇeti. Adresaˇcn´ı m´ ody jsou definov´any ModR/M a SIB bytem obsaˇzen´ ym v instrukci (form´ at instrukce ukazuje obr´ azek 2.16). Tyto byty jsou v instrukci obsaˇzeny jen v pˇr´ıpadˇe potˇreby. SIB byte je pˇr´ıtomen pouze pˇri pouˇzit´ı komplikovanˇejˇs´ıch adresaˇcn´ıch m´ od˚ u dovoluj´ıc´ıch efektivnˇejˇs´ı pˇr´ıstup k pol´ım. Podrobn´ y v´ yklad k adresov´an´ı je k dispozici v [5]. instrukce má maximálně 17 bytů prefixy

opcode

ModR/M

SIB

0 až 4 byty

1 až 3 byty

0 až 1 byte

0 až 1 byte

offset při adresaci

0, 1, 2 nebo 4 byty

přímá data 0, 1, 2 nebo 4 byty

Obr´azek 2.16: Form´at instrukce sady x86 Z hlediska naˇseho emul´ atoru je velmi d˚ uleˇzit´e, ˇze instrukˇcn´ı sada vyuˇz´ıv´ a unifikovan´ y form´ at in19 strukce a zak´ odov´an´ı adresace pamˇeti je pro drtivou vˇetˇsinu instrukc´ı stejn´e . Pˇri pˇrekladu n´as ani tak nezaj´ım´a konkr´etn´ı operace nad adresovan´ ymi daty, jako adresace samotn´a. Instrukce tedy m˚ uˇzeme pˇrekl´adat jednotn´ ym zp˚ usobem, kde pouze ovlivn´ıme adresaˇcn´ı m´ od. Emulace instrukce s pˇr´ıstupem do pamˇeti prob´ıh´ a ve tˇrech kroc´ıch: nejprve zjist´ıme p˚ uvodn´ı adresu operandu, pak tuto adresu dle potˇreby uprav´ıme a nakonec zavol´ame p˚ uvodn´ı instrukci s pozmˇenˇen´ ym adresaˇcn´ım m´ odem vyuˇz´ıvaj´ıc´ım n´ami pˇredloˇzenou adresu. Pro z´ısk´ an´ı absolutn´ı adresy operandu pouˇz´ıv´ ame instrukci lea, kter´a ji uloˇz´ı do zvolen´eho registru. Registr pro uloˇzen´ı absolutn´ı adresy je tˇreba vyb´ırat z tˇech, kter´e pˇrekl´adan´ a instrukce ´ nepouˇz´ıv´ a. Uprava adresy v registru je pak obyˇcejn´e pˇriˇcten´ı offsetu nalezen´eho v mapˇe str´ anek 18

Jde o bˇeˇzn´e opatˇren´ı proti podteˇcen´ı pamˇeti kter´e zav´ ad´ı operaˇcn´ı syst´em. Nˇekter´e instrukce obsahuj´ı pˇreddefinovan´ y operand v pamˇeti bez pouˇzit´ı ModR/M a SIB byt˚ u. Takov´e instrukce je pak tˇreba pˇrekl´ adat jinak. Pˇr´ıkladem takov´e instrukce je napˇr. xlat nebo operace se z´ asobn´ıkem (push, pop atp.) implicitnˇe pracuj´ıc´ı s adresou uloˇzenou v registru esp. 19

´ ´ KAPITOLA 2. NAVRH EMULATORU

30

adresov´eho prostoru. Zb´ yv´ a zavolat p˚ uvodn´ı instrukci s upraven´ ym adresaˇcn´ım m´ odem, kter´ y zajist´ı pouˇzit´ı upraven´e adresy v registru (adresace pˇres hodnotu v registru). Pˇr´ıklad pˇrekladu ukazuje obr´ azek 2.17.

; uloˇ zen´ ı hodnoty registru uˇ zit´ eho pro operaci s adresou (zde je to ecx) mov dword ptr [TemporaryStorage1], ecx ; do registru ecx uloˇ zı ´me p˚ uvodn´ ı absolutn´ ı adresu operandu lea ecx, dword ptr [esi + 0x20] ; n´ asleduje ´ uprava adresy ; uschov´ an´ ı p˚ uvodn´ ıch hodnot registr˚ u nutn´ ych pro ´ upravu adresy mov dword ptr [TemporaryStorage2], eax mov dword ptr [TemporaryStorage3], edx ; uschov´ an´ ı pˇ rı ´znak˚ u procesoru do registru eax lahf ; vyrob´ ıme index do tabulky offset˚ u - jedn´ a se o ˇ cı ´slo pˇ rı ´sluˇ sn´ e ; str´ anky v pamˇ eti. Proto posuv o 12 bit˚ u. mov edx, ecx shr edx, 12 ; pˇ riˇ cten´ ı offsetu add ecx, dword ptr [PageTable + edx * 4] ; obnoven´ ı pˇ rı ´znak˚ u procesoru z registru eax sahf ; obnoven´ ı p˚ uvodn´ ıch hodnot v pouˇ zit´ ych registrech mov eax, dword ptr [TemporaryStorage2] mov edx, dword ptr [TemporaryStorage3] ; zavol´ ame p˚ uvodn´ ı instrukci se zmˇ enˇ en´ ym adresaˇ cn´ ım m´ odem mov ebx, dword ptr[ecx] ; obnoven´ ı p˚ uvodn´ ı hodnoty registru ecx mov ecx, dword ptr [TemporaryStorage1] Obr´azek 2.17: Pˇreklad instrukce mov ebx, dword ptr [esi + 0x20]

Vzhledem k ˇcetnosti pamˇet’ov´ ych operac´ı v bˇeˇzn´em programu si nem˚ uˇzeme dovolit pˇrepnout kontext, coˇz nutnˇe potˇrebujeme kv˚ uli aritmetick´e operaci pˇriˇcten´ı offsetu mˇen´ıc´ı pˇr´ıznaky procesoru. Proto jsme zde vyuˇzily instrukce lahf a sahf, kter´e ukl´adaj´ı prvn´ıch osm bit˚ u pˇr´ıznakov´eho registru efl do registru eax. Jako miniaturn´ı z´asobn´ık pro uchov´an´ı pouˇzit´ ych registr˚ u zde slouˇz´ı emulaˇcn´ı promˇenn´e TemporaryStorage. Z pˇr´ıkladu je zˇrejm´e, ˇze zaveden´ım pˇrekladu pamˇet’ov´ ych operac´ı znaˇcnˇe vzroste expanze k´odu. Nav´ıc vzroste poˇcet operac´ı pˇristupuj´ıc´ıch do pamˇeti (na jeden pˇr´ıstup v p˚ uvodn´ım k´odu pˇripad´a devˇet pˇr´ıstup˚ u v modelu slouˇz´ıc´ım pro emulaci).

´ ´ KAPITOLA 2. NAVRH EMULATORU

2.5

31

Sbˇ er statistick´ ych dat

V´ ystupem emulace jsou data popisuj´ıc´ı ˇcinnost emulovan´eho programu. Obsah sb´ıran´ ych informac´ı z´avis´ı na konkr´etn´ı aplikaci emul´ atoru. V naˇsem pˇr´ıpadˇe je c´ılem odkryt´ı skryt´eho k´odu uvnitˇr jinak standardn´ıho spustiteln´eho souboru. Sbˇer samotn´ ych dat vyˇzaduje vykon´ an´ı pˇr´ısluˇsn´eho k´odu bˇehem emulace, coˇz m˚ uˇze negativnˇe ovlivnit efektivitu emulace. Abychom proces sbˇeru co nejv´ıce urychlili, omezujeme se u nˇekter´ ych u ´daj˚ u pouze na zaznamen´ an´ı a samotn´e pˇred´ an´ı informace heuristick´emu modulu ˇ prob´ıh´ a v ˇcasov´ ych intervalech. Casov´ e intervaly vol´ıme dostateˇcnˇe dlouh´e, aby operace spojen´e s pˇred´ an´ım informace (form´ atov´an´ı a z´apis) podstatnˇe neovlivnily efektivitu emulace. Emulace n´am d´av´a moˇznost analyzovat emulovanou aplikaci po jednotliv´ ych instrukc´ıch. Hodnotit ˇcinnost emulovan´eho programu podle jednotliv´ ych instrukc´ı m˚ uˇze b´ yt ale obt´ıˇzn´e. Hlavn´ı v´ yhodou emulace je n´ahled na d˚ usledky v´ ypoˇctu instrukc´ı tvoˇr´ıc´ıch emulovan´ y program. Mezi moˇzn´e d˚ usledky v´ ypoˇctu instrukc´ı ˇrad´ıme napˇr. pˇr´ıstupy do pamˇeti, vyvolan´e v´ yjimky nebo volan´e funkce API. 2.5.1

Data sb´ıran´ a prvn´ı verz´ı emul´ atoru

Vzhledem k tomu, ˇze v dobˇe n´avrhu emul´ atoru nen´ı k dispozici heuristick´ y modul, nen´ı jasn´e jak´e informace a v jak´em rozsahu sb´ırat. Nicm´enˇe pro demonstraci funkce emul´ atoru jsme se rozhodli zaznamen´ avat API funkce volan´e emulovan´ ym programem. D´ ale je potˇreba pro u ´ˇcely anal´ yzy struktury emulovan´e aplikace zaˇradit statistick´e informace jako je velikost vˇsech vytvoˇren´ ych blok˚ u, nebo adresy poˇc´atku blok˚ u. Sb´ıran´a data jsou v prvn´ı verzi emul´ atoru zapisov´ana do logovac´ıho souboru ve form´ atu XML. Pˇr´ıklady log˚ u pro programy testovac´ı sady jsou na pˇriloˇzen´em CD.

2.6

Shrnut´ı n´ avrhu

Emul´ ator je aplikace vyuˇz´ıvaj´ıc´ı pouze z´akladn´ı sluˇzby API operaˇcn´ıho syst´emu Windows. Jako vstup slouˇz´ı spustiteln´ y soubor programu ve form´ atu COFF/PE. Emul´ ator po sv´e inicializaci naˇcte modul emulovan´eho programu spolu se vˇsemi nutn´ ymi DLL knihovnami. K´od emulovan´eho programu je postupnˇe pˇrekl´ad´ an na bloky o urˇcit´e maxim´ aln´ı d´elce, kter´e jsou vkl´ad´ any do skladu blok˚ u, odkud mohou b´ yt znovu pouˇzity. Na konci v´ ypoˇctu kaˇzd´eho bloku n´asleduje vol´an´ı dispatcheru, coˇz je kr´atk´a rutina staraj´ıc´ı se o vol´an´ı funkc´ı pro nalezen´ı resp. vytvoˇren´ı navazuj´ıc´ıho bloku, pˇresmˇerov´an´ı API funkc´ı a pˇrep´ın´ an´ı vl´ aken emulovan´eho programu. Pro zv´ yˇsen´ı efektivity v´ ypoˇctu jsou nˇekter´e bloky pˇr´ımo nav´az´any na sv´e n´asledn´ıky a nen´ı tˇreba volat dispatcher. Toto vˇsak zav´ad´ı z´avislosti mezi bloky. Pro ukl´ad´ an´ı z´avislost´ı implementujeme mapu z´avislost´ı blok˚ u. Pˇreklady blok˚ u vyuˇz´ıvaj´ı pro sv˚ uj v´ ypoˇcet sadu emulaˇcn´ıch promˇenn´ ych, kter´e spolu s dispatcherem tvoˇr´ı ˇr´ıd´ıc´ı blok. Pˇri emulaci v´ıcevl´aknov´eho programu m´ a kaˇzd´e vl´ akno pˇridˇelen jeden ˇr´ıd´ıc´ı blok. Do emulaˇcn´ı smyˇcky (ˇc´ast emul´ atoru, kter´e spravuje a vykon´ av´a bloky) m´ a v kaˇzd´em okamˇziku pˇr´ıstup pouze jedno vl´ akno. Mluv´ıme o ˇc´asteˇcn´e serializaci vl´ aken. Pro ochranu operaˇcn´ıho syst´emu a okoln´ıch program˚ u pˇresmˇerujeme vol´an´ı API funkc´ı do pˇr´ısluˇsn´ ych emulovan´ ych verz´ı a zamez´ıme programu (k´ odu um´ıstˇen´emu uvnitˇr spustiteln´eho souboru) pˇr´ıstup mimo korektnˇe rezervovan´ a m´ısta v pamˇeti. Chr´an´ıme DLL knihovny tvoˇr´ıc´ı API a definujeme omezenou mnoˇzinu povolen´ ych m´ıst, na kter´e je moˇzn´e v r´amci vol´an´ı API funkc´ı skoˇcit z k´odu emulovan´eho programu (implementujeme mapu API funkc´ı). V´ ystupem emulace jsou informace o ˇcinnosti emulovan´eho programu (vol´an´ı API funkc´ı atp.), kter´e jsou poskytov´any nadˇrazen´emu heuristick´emu modulu (aktu´ alnˇe nen´ı ˇz´adn´ y takov´ y modul k dispozici, takˇze jsou tato data ukl´ad´ ana do logu ve form´ atu XML).

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

32

3 Implementace a testov´ an´ı Tato kapitola popisuje podstatn´e ˇc´asti implementace emul´ atoru a jeho testov´an´ı testov´an´ım.

3.1

Obecnˇ e k implementaci a testov´ an´ı

Implementace a testov´an´ı jsou dvˇe u ´zce souvisej´ıc´ı ˇcinnosti, kter´e se ˇc´asteˇcnˇe prol´ınaj´ı. Kaˇzd´ a nov´a funkce programu implikuje nov´ y test, stejnˇe jako kaˇzd´ y nov´ y test vede na koresponduj´ıc´ı funkci programu. Obˇe tyto ˇcinnosti zastˇreˇsuje kvalitn´ı dokumentace. Dle naˇseho n´azoru, by z hlediska spr´ avnosti postupu pr´ace mˇel jako prvn´ı vzniknout test, kter´ y definuje vstupy a v´ ystupy nov´e funkce. Bohuˇzel nemaj´ı vˇsechny partie softwaru charakter matematick´eho zobrazen´ı. Zvl´aˇstˇe pˇri syst´emov´em programov´an´ı ˇcasto pˇrevl´ad´ a ˇc´ast procedur´aln´ı nad ˇc´ast´ı funkˇcn´ı. Nˇekter´e operace zkr´ atka nemaj´ı snadno testovateln´ y v´ ystup. Je tedy tˇreba vhodnˇe volit metody testov´an´ı. Implementaˇcn´ı ˇcinnost si klade za c´ıl realizovat funkcionalitu navrˇzenou v analytick´e ˇc´asti s ohledem na dostupn´e technick´e prostˇredky. Samozˇrejmost´ı je dodrˇzov´an´ı pˇr´ısluˇsn´e ˇst´abn´ı kultury pˇri z´apisu zdrojov´eho k´odu. Textov´e soubory obsahuj´ıc´ı zdrojov´ y k´od b´ yvaj´ı pro ˇclovˇeka ˇcasto ˇspatnˇe ˇciteln´e, a proto je tˇreba hojnˇe vyuˇz´ıvat moˇznosti dokumentace. 3.1.1

Testov´ an´ı emul´ atoru

Test se obecnˇe skl´ ad´ a ze dvou logick´ ych ˇc´ast´ı: vyvol´an´ı poˇzadovan´e aktivity a zkoum´an´ı jejich d˚ usledk˚ u. Napˇr. pˇri testov´an´ı funkce nejprve pˇriprav´ıme data, kter´a pak uˇzijeme jako parametry pˇri vol´an´ı testovan´e funkce a n´aslednˇe funkci zavol´ame (zde se vyvol´an´ı poˇzadovan´e aktivity skl´ ad´ a ze dvou krok˚ u). Po n´avratu z vol´an´ı zkoum´ame, zda navr´acen´ a hodnota odpov´ıd´ a specifikaci funkce. Ne vˇzdy je ale moˇzn´e snadno algoritmicky zkontrolovat d˚ usledky testovan´e aktivity. Budemeli napˇr. testovat emul´ ator jako celek, tˇeˇzko preciznˇe zkontrolujeme, zda emulovan´ y program funguje spr´ avnˇe. V takov´em pˇr´ıpadˇe si vybere pouze ˇc´ast v´ ystupu testovan´eho syst´emu a ten zkontrolujeme. Podobn´ y probl´em m˚ uˇze nastat i pˇri pˇr´ıpravˇe vstupn´ıch dat pro testovanou aktivitu. Precizn´ı otestov´an´ı disassembleru by si napˇr´ıklad vyˇz´adalo vytvoˇren´ı programu, kter´ y by obsahoval vˇsechny moˇzn´e instrukce ve vˇsech sv´ ych variant´ach. I zde mus´ıme volit nˇejakou podmnoˇzinu povolen´ ych vstupn´ıch hodnot s ohledem na co nejvˇetˇs´ı pravdˇepodobnost detekce chyby. Pro obˇe logick´e ˇc´asti testu plat´ı velmi d˚ uleˇzit´e pravidlo: sloˇzitost testu (mˇeˇreno napˇr. poˇctem ˇr´adku implementuj´ıc´ıho k´odu) mus´ı b´ yt ˇr´ adovˇe niˇzˇs´ı, neˇz sloˇzitost testovan´eho subsyst´emu. Toto pravidlo vych´az´ı z podstaty p˚ uvodu chyb v programech, kde je hlavn´ım chybuj´ıc´ım ˇcinitelem program´ ator. Unit testy Nejmenˇs´ım testovan´ ym elementem emul´ atoru jsou jednotliv´e datov´e struktury a pˇridruˇzen´e funkce. Jejich testov´an´ı prob´ıh´ a pˇr´ımo v emul´ atoru, kter´ y je pro tento u ´ˇcel sestaven ve speci´aln´ı testovac´ı konfiguraci. Toto n´am dovoluje testovat datov´e struktury v prostˇred´ı jejich pˇr´ım´eho nasazen´ı. Emul´ ator pˇreloˇzen´ y v testovac´ı konfiguraci je spustiteln´ y soubor, kter´ y po startu provede vˇsechny unit testy, v´ ysledky zap´ıˇse do logu a skonˇc´ı. Implementovan´e unit testy:

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

33

• disassembler – TestDasm 1: Emul´ ator otevˇre soubor DasmReferenceImage.exe a vyp´ıˇse k´od v textov´e formˇe do souboru out.tmp. • logov´an´ı – TestLogger 1: Testuje zakl´ad´ an´ı souboru logu. – TestLogger 2: Testuje zapisov´an´ı do logu. • emulaˇcn´ı smyˇcka – TestMachine BlockRelationMap 1: Vytv´ aˇr´ı jednoduch´e grafy a testuje chov´an´ı • vlastn´ı knihovna standardn´ıch funkc´ı – TestRuntime 1: Vol´a jednotliv´e funkce nahrazuj´ıc´ı funkce standardn´ı knihovny jazyka C a testuje jejich chov´an´ı vˇcetnˇe odezvy na neplatn´e parametry. ym vyhled´ avac´ım stromem. – TestRuntime 2: Testuje operace nad obecn´ avac´ıho stromu. – TestRuntime 3: Testuje cache obecn´eho vyhled´ – TestRuntime 4: Testuje odstraˇ nov´an´ı mnoˇziny list˚ u vyhled´ avac´ıho stromu zadan´e intervalem hodnot kl´ıˇc˚ u. Syst´ emov´ e testy Zde se snaˇz´ıme o provˇeˇren´ı celkov´e funkˇcnosti emul´atoru. Jako vstup nejl´epe poslouˇz´ı programy zamˇeˇren´e na v´ ypoˇcet (napˇr. mp3 kod´er, komprimaˇcn´ı nebo ˇsifrovac´ı programy). Volbou velikosti vstupn´ıch dat emulovan´ ych program˚ u m˚ uˇzeme snadno volit d´elku bˇehu emulace. Sesb´ıran´a sada program˚ u nav´ıc poslouˇz´ı i pro testov´an´ı v´ ykonu emul´ atoru. Pˇri tomto druhu testov´an´ı se spol´eh´ ame na to, ˇze chyba pˇri emulaci zp˚ usob´ı p´ad emul´ atoru s patˇriˇcnou odezvou v logu nebo chybnou funkci emulovan´eho programu. V´ ystup emulovan´ ych program˚ u testujeme porovn´an´ım s v´ ystupy z´ıskan´ ymi bez emulace. 3.1.2

Technick´ e prostˇ redky pro implementaci

Pro implementaci emul´ atoru jsme zvolili programovac´ı jazyk C++ z d˚ uvodu jeho snadn´eho propojen´ı s k´odem psan´ ym v assembleru a moˇznostem n´ızko´ urovˇ nov´eho programov´an´ı. Vyjadˇrovac´ı schopnosti jazyka C++ n´am dovoluj´ı snadno organizovat logick´e celky v projektu za pomoc´ı prostor˚ u jmen (namespace). V pˇr´ıpadˇe, kdy by ani tato organizace nepomohla jednoznaˇcnˇe rozliˇsit identifik´atory v projektu emul´ atoru s identifik´atory standardn´ıch knihoven, pˇristupujeme k pouˇzit´ı pˇredpon. Pro projekt emul´ atoru byla zvolena pˇredpona sf (uˇzit´ı napˇr. u pojmenov´an´ı emulovan´ ych verz´ı API funkc´ı – SfCreateThread, nebo u maker SF OPTION ENABLE LOGGING). Zdrojov´ y k´od v jazyce C++ je prokl´ ad´ an pozn´amkami psan´ ymi ve form´ atu kompatibiln´ım se znaˇckov´an´ım pro gener´ ator dokumentace Doxygen [2]. Podrobn´a dokumentace k implementaci generovan´ a n´astrojem Doxygen je k dispozici na pˇriloˇzen´em CD (viz. soubor readme.txt na CD).

3.2

V´ yznamn´ e datov´ e struktury

Pod´ıvejme se nyn´ı podrobnˇeji na nejd˚ uleˇzitˇejˇs´ı datov´e struktury emul´ atoru a jejich implementaci.

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

34

kořen

a0 0x7c

0x77

a1 0x80 a2 0x97 a3 0x01

0xad

0x32

data pro klíč 0x7c809701

data pro klíč 0x7c809732

data pro klíč 0x7c8097ad

Obr´azek 3.1: Pˇr´ıklad vyhled´ avac´ıho stromu 3.2.1

Obecn´ y vyhled´ avac´ı strom

Obecn´ y vyhled´ avac´ı strom je strom (definice viz. [6]) s tˇemito vlastnostmi: • Uzly stejnˇe vzd´ alen´e od koˇrene maj´ı stejn´ y maxim´ aln´ı poˇcet v´ ystupn´ıch hran oznaˇcen´ y ai • Vˇsechny listy maj´ı stejnou vzd´ alenost h od koˇrene stromu. Kl´ıˇcem pro hled´an´ı je cel´e ˇc´ıslo reprezentovan´e datov´ ym typem o m bitech. Pro volbu parametr˚ u ai plat´ı (implementaˇcn´ı omezen´ı): ai = 2ki . . . ki ∈ N h−1 X

ki = m

i=0

ai je tedy vˇzdy mocninou dvou. Logickou organizaci vyhled´ avac´ıho stromu, kde kl´ıˇcem pro hled´an´ı je 32-bitov´a hodnota ukazuje obr´ azek 3.1. Parametry stromu jsou: h=4 ki = 8 . . . i ∈ {0, 1, 2, 3} Pˇri n´avrhu i implementaci vyhled´ avac´ıho stromu byl kladen nejvˇetˇs´ı d˚ uraz na rychlost. Strom je vyuˇzit pro implementaci skladu blok˚ u a mapy API funkc´ı, coˇz jsou operace vyvol´avan´e dispatcherem. Jde tedy o rychlostnˇe velmi citlivou ˇc´ast emul´ atoru. Nejrychlejˇs´ı zp˚ usob, jak vyhledat objekt podle kl´ıˇce, je vytvoˇrit jednorozmˇern´e pole s poloˇzkou pro kaˇzdou moˇznou hodnotu kl´ıˇce. Adresu hledan´eho objektu z´ısk´ ame pˇriˇcten´ım kl´ıˇce k ukazateli poˇc´atku pole. Operace si vyˇz´ad´ a jednu aritmetickou operaci a tˇri ˇcten´ı z pamˇeti (naˇcten´ı kl´ıˇce, naˇcten´ı ukazatele poˇc´atku pole a pˇreˇcten´ı v´ ysledku).

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

35

Nasazen´ı tohoto rychl´eho pˇr´ıstupu br´an´ı jeho pamˇet’ov´e n´aroky. Pokud budeme reprezentovat vyhled´ avan´e objekty ˇctyˇrbytov´ ymi ukazateli, bude velikost pole 4 · 2m B. Pro sklad blok˚ u je kl´ıˇcem ˇctyˇrbytov´a adresa, takˇze by byla velikost vyhled´ avac´ı struktury tvoˇren´e jedn´ım polem 16GB. Myˇslenku pˇr´ım´eho vyhled´ an´ı v jednorozmˇern´em poli jsme ale zcela neopustili. Uzel vyhled´avac´ıho stromu je tvoˇren jednorozmˇern´ ym polem s poloˇzkami o velikosti 4B. Velikost pole je rovna ai . Vyhled´avac´ı kl´ıˇc je rozdˇelen na h pol´ı o k0 , k1 , . . . kh−1 bitech (viz. obr´ azek 3.2). Vyhled´av´an´ı zaˇc´ın´ a v koˇrenu nalezen´ım ukazatele n´asleduj´ıc´ıho uzlu (4B hodnota) podle hodnoty v prvn´ım poli. Po nalezen´ı n´asleduj´ıc´ıho uzlu se opˇet vyhled´ a n´asledn´ık podle hodnoty v dalˇs´ım poli kl´ıˇce. Vyhled´av´an´ı konˇc´ı nalezen´ım listu pomoc´ı posledn´ıho pole. k 0 bitů

k1 bitů

k2 bitů

k h - 1 bitů

pole 0

pole 1

pole 2

pole h - 1

m bitů

ˇ en´ı kl´ıˇce obecn´eho vyhled´ Obr´azek 3.2: Clenˇ avac´ıho stromu Zmenˇsen´ı pamˇet’ov´ ych n´arok˚ u oproti metodˇe s jedn´ım polem se dˇeje na u ´kor rychlosti. Operace vyhled´ an´ı ve stromu vyˇzaduje 2 + h ˇcten´ı z pamˇeti (naˇcten´ı kl´ıˇce, ukazatele koˇrenu a vˇsech uzl˚ u na cestˇe ke listu vˇcetnˇe listu samotn´eho) a h aritmetick´ ych operac´ı. St´ale se vˇsak jedn´ a o velmi rychlou metodu s asymptotickou sloˇzitost´ı O (log n). Pamˇ et’ov´ e n´ aroky vyhled´ avac´ıho stromu Pamˇet’ov´e n´aroky vyhled´ avac´ıho stromu z´avis´ı na rozloˇzen´ı kl´ıˇc˚ u uloˇzen´ ych hodnot a volbˇe ˇclenˇen´ı kl´ıˇce na pole. Pamˇet’ spotˇrebovan´ a vyhled´ avac´ım stromem je: M = (u0 · a0 + u1 · a1 + . . . + uh−1 · ah−1 ) · 4B ui je poˇcet uzl˚ u ve vzd´ alenosti i od koˇrene stromu. Pro minimalizaci v´ yrazu mus´ıme minimalizovat jednotliv´e sˇc´ıtance. Velk´ ych uzl˚ u (velk´e ai ) mus´ı b´ yt m´ alo (mal´e ui ) a naopak. Metoda jednoho velk´eho pole s poloˇzkou pro kaˇzdou moˇznou hodnotu kl´ıˇce trp´ı velk´ ym pl´ ytv´ an´ım pamˇet´ı z d˚ uvodu mal´e obsazenosti v pˇr´ıpadˇe, ˇze vloˇzen´ ych kl´ıˇc˚ u je, v porovn´an´ı s rozsahem jejich moˇzn´ ych hodnot, mnohem m´enˇe. Vyhled´ avac´ı strom ve sv´ ych listech realizuje jakousi podmnoˇzinu velk´eho vyhled´ avac´ıho pole a umoˇzn ˇuje tak vynechat nevyuˇzit´a m´ısta. Princip ukazuje obr´ azek 3.3 Nejvˇetˇs´ı efektivity dos´ ahneme, navrhneme-li velikost pol´ı implementuj´ıc´ıch listy vyhled´ avac´ıho stromu tak, aby co nejv´ıce kop´ırovaly shluky vloˇzen´ ych hodnot. Podobn´ ym zp˚ usobem m˚ uˇzeme postupovat i pˇri n´avrhu velikosti uzl˚ u na cestˇe mezi koˇrenem a listy. Pro uzly na u ´rovni i (navrhujeme velikost pole pi ) je tˇreba zkoumat rozloˇzen´ı hodnot kl´ıˇc˚ u zmenˇsen´ ych o d´elku jiˇz navrˇzen´ ych pol´ı pj kde j > i. Pˇri n´avrhu tedy postupujeme smˇerem od list˚ u ke koˇrenu. Pro aplikaci obecn´eho vyhled´ avac´ıho stromu v prvn´ı verzi naˇseho emul´ atoru jsme zvolili ˇclenˇen´ı kl´ıˇce (32-bitov´eho ˇc´ısla) na ˇctyˇri pole po osmi bitech. Vzhledem k tomu, ˇze rozloˇzen´ı kl´ıˇc˚ u nezn´ame, je naˇse volba urˇcit´ ym odhadem. V kapitole 4 se d´ale vˇenujeme anal´ yze rozloˇzen´ı kl´ıˇc˚ u objekt˚ u ukl´ adan´ ych do datov´ ych struktur za u ´ˇcelem pˇr´ıpadn´eho vylepˇsen´ı ˇclenˇen´ı kl´ıˇce. Zrychlen´ı vyhled´ av´ an´ı uˇ zit´ım cache Volbou pol´ı uvnitˇr kl´ıˇce stanov´ıme poˇcet u ´rovn´ı stromu a t´ım i poˇcet uzl˚ u, kter´e pˇri kaˇzd´em hled´an´ı mus´ıme proj´ıt. V emul´ atoru pouˇz´ıv´ ame dˇelen´ı kl´ıˇce na ˇctyˇri ˇc´asti. Vyhled´an´ı se tedy

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

36 jedno velké pole klíč délky m

vyhledávací strom pole klíče: p1 = m – 3; p2 = 3

kořen

obsazené položky

Obr´azek 3.3: Princip u ´spory pamˇeti vyhled´ avac´ım stromem skl´ ad´ a ze ˇctyˇr pˇr´ıstup˚ u. Pˇredˇrazen´ı cache pˇred samotn´ y vyhled´ avac´ı strom n´ am dovoluje dos´ ahnout ide´aln´ıho stavu, kdy je pro vyhled´ an´ı zapotˇreb´ı pouze jeden pˇr´ıstup. Cache je organizov´ana jako 1-asociativn´ı. Implementujeme ji pomoc´ı pole poloˇzek o dvou 4B ˇc´ıslech. Jedno udrˇzuje kl´ıˇc vloˇzen´eho objektu a druh´e je pˇr´ımo ukazatelem na objekt. Index do pole realizuj´ıc´ıho cache je tvoˇre n nejm´enˇe v´ yznamn´ ymi bity kl´ıˇce. Volbou n stanovujeme velikost cache (ta je 2n ) a v´ yznamnˇe ovlivˇ nujeme pravdˇepodobnost nelezen´ı poloˇzky v cache. ´ eˇsnost nasazen´ı Pro prvn´ı verzi emul´ atoru byla zvolena velikost indexu do cache 10 bit˚ u. Uspˇ cache provˇeˇr´ıme mˇeˇren´ım v kapitole 4. 3.2.2

Implementace mapy z´ avislost´ı blok˚ u

Mapa z´avislost´ı blok˚ u je datov´a struktura popisuj´ıc´ı orientovan´ y graf. Emul´ ator tuto datovou strukturu vyuˇz´ıv´ a pˇri ˇretˇezen´ı blok˚ u, kdy do n´ı vkl´ad´ a novou z´avislost. Nejedn´ a se tedy o ˇcasovˇe kritickou operaci, protoˇze poˇcet operac´ı zˇretˇezen´ı je, pˇri emulaci bˇeˇzn´eho programu, vzhledem k poˇctu vykonan´ ych blok˚ u zanedbateln´ y. Pˇresto se ale pokus´ıme implementovat mapu z´avislost´ı blok˚ u tak, aby se nestala u ´zk´ ym hrdlem emul´ atoru. Podstatou vzniku a typickou strukturou grafu z´avislost´ı blok˚ u jsem se zab´ yvali v odstavci 2.3.5. Uzel grafu m˚ uˇze m´ıt libovoln´ y poˇcet vstupn´ıch i v´ ystupn´ıch hran. Z moˇzn´ ych reprezentac´ı grafu se nab´ız´ı napˇr. incidenˇcn´ı matice. Jej´ımu nasazen´ı vˇsak br´an´ı dynamick´ y charakter grafu. Uzly jsou v pr˚ ubˇehu ˇzivota datov´e struktury pˇrid´ av´any a odeb´ır´ any. Nav´ıc bychom zdaleka nevyuˇzili cel´ y pamˇet’ov´ y prostor zabran´ y incidenˇcn´ı matic´ı, protoˇze je graf z´avislost´ı blok˚ u ˇr´ıdk´ y (poˇcet hran grafu je u ´mˇern´ y poˇctu uzl˚ u). Blok bud’ nen´ı zˇretˇezen v˚ ubec (ˇz´adn´ a vstupn´ı hrana), nebo je zˇretˇezen na konci a v nˇekolika m´ıstech ve sv´em tˇele (statick´e ukonˇcen´ı bloku a podm´ınˇen´e skoky). Pro reprezentaci bylo vybr´ ano sjednocen´ı jednosmˇernˇe zˇretˇezen´ ych seznam˚ u. Smˇery zˇretˇezen´ı v seznamech byly zvoleny tak, aby byla ˇcasov´a sloˇzitost vkl´ad´ an´ı co nejmenˇs´ı. Vyhled´av´an´ı se dˇeje pˇr´ım´ ym pˇr´ıstupem do pole podle indexu uloˇzen´eho v datov´e struktuˇre bloku, takˇze je velmi rychl´e. Inspirac´ı pro implementaci byl souborov´ y syst´em FAT. Uzel grafu je implementov´an datovou strukturou o pˇeti 4B prvc´ıch. Data reprezentuj´ıc´ı uzly jsou udrˇzov´ana v poli uzl˚ u. Pole roste v pr˚ ubˇehu pr´ace s mapou z´avislost´ı blok˚ u podle potˇreby. Pro snadn´e nalezen´ı voln´e poloˇzky v poli udrˇzujeme seznam voln´ ych poloˇzek. Veˇsker´e odkazy na uzly

´ ´I KAPITOLA 3. IMPLEMENTACE A TESTOVAN

37

grafu jsou implementov´any jako indexy do zm´ınˇen´eho pole. Pˇr´ıklad pole uzl˚ u a koresponduj´ıc´ıho grafu ukazuje obr´ azek 3.4 a) a c). Z implementaˇcn´ıch d˚ uvod˚ u jsme omezily poˇcet vstupn´ıch hran uzlu na jednu. Abychom i tak mohli zachytit graf z´avislost´ı, zavedli jsme v r´amci poloˇzek pole uzl˚ u kopie t´ehoˇz uzlu – bloku. Situaci ilustruje obr´ azek 3.4 b) a c). pole uzlů

a)

uzly první volný prvek potomek soused

2

1

3

4

kopie 3

5

rodič

kopie

b)

původní graf 1

2

c)

transformovaný graf 1

2 kopie uzlu 3

3

4

5

3

3

4

5

Obr´azek 3.4: Zobrazen´ı grafu z´avislost´ı blok˚ u v implementaci M´ ame li jeden blok zobrazen v grafu v´ıce uzly, je tˇreba vyˇreˇsit ot´ azku, jak zach´azet s potomky. Na obr´ azku 3.4 b) jsou potomky uzlu 3 uzly 4 a 5. Tento vztah znaˇc´ı, ˇze jsou bloky reprezentovan´e uzly 4 a 5 pˇr´ımo zˇretˇezeny na blok reprezentovan´ y uzlem 3. Vzhledem k tomu, ˇze kaˇzd´ a z kopi´ı obsahuje adresu bloku, ke kter´emu se v´aˇze, poslouˇz´ı n´am tedy kaˇzd´ a stejnˇe dobˇre jako rodiˇcovsk´ y uzel pro uzly 4 a 5 (na dotaz ”Kdo je m˚ uj rodiˇc?” odpov´ı stejnˇe). Komplikovanˇejˇs´ı je odpovˇed’ na dotaz ”Kdo jsou rodiˇce m´eho rodiˇce?”. V takov´e pˇr´ıpadˇe mus´ıme proj´ıt vˇsechny kopie uzlu 3 a vr´atit jejich rodiˇce. Vzhledem k tomu, ˇze je seznam kopi´ı jednosmˇernˇe zˇretˇezen, bude nejvhodnˇejˇs´ı v´ azat vˇsechny potomky na prvn´ı kopii – tedy na origin´ al. Tak´e index obsaˇzen´ y v datov´e struktuˇre bloku ukazuje pouze na origin´ al pˇr´ısluˇsn´eho uzlu.

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

38

4 Anal´ yza emulovan´ eho programu V t´eto kapitole se zamˇeˇr´ıme na zkoum´an´ı vstupu pro emul´ ator. Dosavadn´ı n´avrh a implementace emul´ atoru vych´azela z teoretick´ ych u ´vah. Zde se pokus´ıte formou empirick´ ych pokus˚ u poskytnout n´ahled na typick´ y vstup pro emul´ ator a zhodnotit spr´ avnost u ´vah, kter´e prov´azely n´avrh a implementaci emul´ atoru.

4.1

Konfigurace

Konkretn´ı konfigurace hardware a software ovlivˇ nuje v´ ysledky mˇeˇren´ı. Pro reprodukovatelnost mˇeˇren´ı uv´ad´ıme technick´e prostˇredky pouˇzit´e pro emulaci program˚ u vybran´ ych jako vstup. D´ ale dopln´ıme popis konfigurace mˇeˇren´ı seznamem pouˇzit´ ych vstupn´ıch program˚ u spolu s jejich struˇcnou charakteristikou. Nakonec pop´ıˇseme stav implementace, ve kter´e se nach´azel emul´ ator pˇri prov´adˇen´ ych anal´ yz´ ach. 4.1.1

Hardware a software

Z hlediska bˇehu emulace je d˚ uleˇzit´ ym faktorem procesor. Jmenovitˇe jde o relativn´ı rychlost pˇr´ıstup˚ u do pamˇeti (L1 a L2 cache) v˚ uˇci v´ ypoˇctu funkˇcn´ı ˇc´asti instrukc´ı. Bloky obsahuj´ı v´ yraznˇe v´ıce instrukc´ı pracuj´ıc´ıch s operandy v pamˇeti neˇz p˚ uvodn´ı k´od. S pˇr´ıstupem do operaˇcn´ı pamˇeti u ´zce souvis´ı algoritmus spekulativn´ıho naˇc´ıt´ an´ı dat do L1 nebo L2 cache, pomoc´ı kter´e se procesor snaˇz´ı dopˇredu odhadnout, kter´a data bude program v bl´ızk´e budoucnosti pouˇz´ıvat. Z hlediska poˇc´ıtaˇce jako celku je d˚ uleˇzit´a propustnost operaˇcn´ı pamˇeti a samozˇrejmˇe instalovan´ y operaˇcn´ı syst´em. n´azev procesor operaˇcn´ı pamˇet’ z´akladn´ı deska pevn´ y disk operaˇcn´ı syst´em

typ Intel Pentium M 750 1024MB DDR2, z´akladn´ı frekvence 200MHz Notebook HP, chipset Intel i915PM 2,5 palce, 60GB, 5400 RPM Microsoft Windows XP Professional, Service Pack 2

Tabulka 4.1: Konfigurace hardware poˇc´ıtaˇce pouˇz´ıt´eho pro testy

4.1.2

Testovac´ı sada vstupn´ıch program˚ u

Testovac´ı sada vstupn´ıch program˚ u funguje hlavnˇe jako vzorek re´aln´ ych program˚ u slouˇz´ıc´ıch pro mˇeˇren´ı efektivity emulace. Programy ze sady mus´ı b´ yt schopn´e fungovat bez z´asahu uˇzivatele (programy orientovan´e na v´ ypoˇcet) a mus´ı takt´eˇz minim´alnˇe z´aviset na vnˇejˇs´ıch ud´alostech. To znamen´a, ˇze jedin´a nutn´a vstupn´ı data mus´ı b´ yt ihned k dispozici (napˇr. ve formˇe vstupn´ıho souboru). Tabulka 4.2 uv´ad´ı jednotliv´e programy z testovac´ı sady spolu s kr´atk´ ym popisem. n´azev gzip 7-Zip AxCrypt lame

verze 1.2.4 4.23 1.6.3 3.97

popis Kompresn´ı n´astroj ve verzi pro Windows N´ astroj pro kompresi dat ˇ Sifrovac´ı program Kod´er MPEG Audio Layer III (MP3) Tabulka 4.2: Programy testovac´ı sady

dalˇs´ı informace www.gzip.org www.7-zip.org axcrypt.sourceforge.net www.mp3dev.org

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

39

Nen´ı-li ˇreˇceno jinak, je velikost vstupn´ıch dat pro testovac´ı programy pracuj´ıc´ı s obecn´ ymi soubory (n´astroje pro kompresi a ˇsifrov´an´ı) pˇribliˇznˇe 512kB a jedn´ a se o COFF/PE spustiteln´ y soubor. Pro kod´er lame pouˇz´ıv´ ame vzorek wav souboru o velikosti 800kB. 4.1.3

Popis pouˇ zit´ e verze emul´ atoru

Implementace emul´ atoru je velmi n´aroˇcn´ a na testov´an´ı a kaˇzd´ a nov´a vlastnost vyˇzaduje ˇcasovˇe n´aroˇcn´e testov´an´ı. Proto jsme uˇz ve f´azi n´avrhu ˇradili jednotliv´e funkce emul´ atoru podle jejich d˚ uleˇzitosti a vazby na jin´e funkce. C´ılem bylo m´ıt k dispozici vzorek, kter´ y bude dosahovat pˇribliˇznˇe stejn´e rychlosti jako prvn´ı prakticky nasaditeln´a verze. Rychlost jsme zvolili jako kl´ıˇcovou vlastnost a d˚ uvod k tvorbˇe emul´ atoru samotn´eho. Nejvˇetˇs´ım probl´emem implementace emul´ atoru je z ˇcasov´eho hlediska emulace API operaˇcn´ıho syst´emu Windows. Vybrali jsme proto v´ yˇse uvedenou skupinu program˚ u a implementovali ´ a ˇsk´ala emulaci jen tˇech API funkc´ı, kter´e byly nutn´e pro emulaci vybran´ ych program˚ u. Uzk´ implementovan´ ych API funkc´ı m´ a za pˇr´ıˇcinu nefunkˇcnost dynamick´e relokace modulu emulovan´eho programu. Emulovan´ y program totiˇz vnitˇrnˇe pracuje s adresami tak, jako by byl namapov´an vˇzdy na p˚ uvodn´ı pozici a podle toho i tvoˇr´ı a pˇred´ av´a parametry do funkc´ı API. Velk´e mnoˇzstv´ı API funkc´ı obsahuje parametry ve formˇe ukazatel˚ u. Je tedy nutn´e vˇsechny tyto ukazatele pˇrekl´adat, aby ukazovaly na skuteˇcnou pozici modulu emulovan´eho programu. Tento pˇreklad jsme prozat´ım neimplementovali a vˇetˇsinu API funkc´ı nech´av´ame prov´adˇet bez modifikace. Pˇr´ıpadn´ a relokace tedy nen´ı moˇzn´ a, i kdyˇz ostatn´ı ˇc´asti emul´ atoru uˇz jsou k tomuto pˇripraveny. Z pohledu vˇernosti rychlosti v˚ uˇci fin´aln´ı verzi nen´ı implementov´ano opatˇren´ı proti tvorbˇe potenci´ alnˇe nekoneˇcn´ ych smyˇcek pˇr´ımo zˇretˇezen´ ych blok˚ u. Emul´ ator nebyl optimalizov´an pro sn´ıˇzen´ı spotˇreby pamˇeti. Sklad blok˚ u pojme neomezen´e mnoˇzstv´ı blok˚ u a aplikace obecn´eho vyhled´ avac´ıho stromu pouˇz´ıvaj´ı dˇelen´ı kl´ıˇce na ˇctyˇri osmibitov´a pole. Zdrojov´e k´ody na pˇriloˇzen´em CD odpov´ıdaj´ı t´eto popisovan´e verzi. Jako vstupn´ı soubory doporuˇcujeme pouˇz´ıvat jen programy z tabulky 4.2.

4.2

Pˇ r´ıstup do pamˇ eti

Emulovan´ y program pˇristupuje do operaˇcn´ı pamˇeti za u ´ˇcelem v´ ypoˇctu sv´eho k´odu (ˇcten´ı instrukc´ı) a ˇcten´ı nebo z´apisu dat. Pˇri emulaci pr´ace s operaˇcn´ı pamˇet´ı se pouˇz´ıvaj´ı datov´e struktury implementovan´e pomoc´ı obecn´eho vyhled´ avac´ıho stromu (viz. odstavec 3.2). 4.2.1

Dˇ elen´ı kl´ıˇ ce obecn´ eho vyhled´ avac´ıho stromu na pole

Pomoc´ı dynamick´e anal´ yzy prozkoum´ame rozloˇzen´ı adres pˇr´ıstup˚ u do adresov´eho prostoru za u ´ˇcelem zhodnocen´ı vhodnosti rozdˇelen´ı kl´ıˇce pro vyhled´ an´ı v obecn´em vyhled´ avac´ım stromu na jednotliv´a pole. Rozloˇ zen´ı poˇ c´ ateˇ cn´ıch adres blok˚ u Zdrojov´ y k´od pro tvorbu blok˚ u se nach´az´ı v jednotliv´ ych COFF/PE souborech mapovan´ ych do adresov´eho prostoru. Soubory form´ atu COFF/PE jsou organizov´any do sekc´ı. Kaˇzd´ a sekce m´ a v hlaviˇcce zaps´anu relativn´ı adresu vzhledem k adrese, od kter´e bude soubor namapov´an do pamˇeti. Tato relativn´ı adresa je zarovn´ana na cel´ y n´ asobek velikosti pamˇet’ov´e str´anky (tj. 4kB). Vzhledem k tomu, ˇze jsou i poˇc´ateˇcn´ı adresy mapov´an´ı souboru zarovn´any na pamˇet’ov´e

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

40

str´anky1 , bude i sekce COFF/PE namapov´ana vˇzdy od zaˇc´atku pamˇet’ov´e str´anky. Spustiteln´ y k´od se zpravidla nach´az´ı pouze v jedn´e sekci. Poˇc´ateˇcn´ı adresy blok˚ u tvoˇren´ ych z tohoto k´odu by mˇeli b´ yt situov´any do nˇekolika sousedn´ıch str´anek. Tento pˇredpoklad potvrzuj´ı data z´ıskan´e dynamickou anal´ yzou programu AxCrypt zobrazen´e v grafu na obr´ azku 4.1.

číslo paměťové stránky [105]

5

4

3

2

1

0 0

50

100

150

počet bloků [-]

200

250

Obr´azek 4.1: Rozm´ıstˇen´ı blok˚ u v adresov´em prostoru Jednotliv´e body zde ud´avaj´ı poˇcet blok˚ u vytvoˇren´ ych z dan´e pamˇet’ov´e str´anky. V grafu jsou patrn´e dvˇe oblasti s hust´ ym v´ yskytem blok˚ u. Jedna odpov´ıd´ a mapov´an´ı spustiteln´eho souboru emulovan´e aplikace – oblast str´anek nad str´ankou ˇc´ıslo 1024 (z d˚ uvodu mˇeˇr´ıtka osy y je tato oblast velmi bl´ızko nule). Druh´a oblast hust´eho v´ yskytu blok˚ u odpov´ıd´ a emulovan´ ym syst´emov´ ym knihovn´am. Ty b´ yvaj´ı v adresov´em prostoru ˇcasto mapov´any v oblasti nad adresou 0x70000000, coˇz odpov´ıd´ a str´ank´am s ˇc´ıslem vˇetˇs´ım neˇz 458752. Rozloˇ zen´ı adres API funkc´ı Rozloˇzen´ı adres API funkc´ı m´ a stejnou povahu jako rozloˇzen´ı adres poˇc´atk˚ u bloku. Knihovny vˇsech zat´ım podporovan´ ych API funkc´ı jsou mapov´any do adresov´eho prostoru nad hranici 0x70000000. Rozm´ıstˇen´ı a ˇcetnost vol´an´ı API funkc´ı programu 7-Zip pˇri kompresi testovac´ıho vzorku dat (exe soubor o velikosti cca 512kB) ukazuje graf na obr´ azku 4.2. 4.2.2

Velikost cache vyhled´ avac´ıch datov´ ych struktur

V´ ypoˇcet programu orientovan´eho na zpracov´an´ı dat (komprese, ˇsifrov´an´ı) se d´a rozdˇelit do tˇrech ˇc´ast´ı: rezervace syst´emov´ ych prostˇredk˚ u, zpracov´an´ı samotn´ ych dat a uvolnˇen´ı syst´emov´ ych prostˇredk˚ u. Prvn´ı a posledn´ı ˇc´ast je pˇritom z pohledu v´ ypoˇcetn´ıho ˇcasu zanedbateln´ a proti druh´e ˇc´asti. 1

Ve skuteˇcnosti nemus´ı b´ yt velikost pamˇet’ov´e str´ anky vˇzdy 4kB. Jedn´ a se vˇsak o hodnotu platnou pro drtivou vˇetˇsinu dnes provozovan´ ych syst´em˚ u. Konkr´etn´ı hodnota alokaˇcn´ı granularity syst´emu se d´ a zjistit API funkc´ı GetSystemInfo.

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

41

x1e5

číslo paměťové strákny [-]

5.2

5.0

4.8

4.6

4.4 1

2

3

4

5

6

počet volání [-]

Obr´azek 4.2: Rozm´ıstˇen´ı API funkc´ı v adresov´em prostoru Zpracov´an´ı dat se dˇeje vˇetˇsinou ve smyˇcce, kter´a je v emul´ atoru reprezentov´ana skupinou blok˚ u. C´ılem cache (v tomto pˇr´ıpadˇe cache ve skladu blok˚ u) je obs´ ahnout celou tuto skupinu blok˚ ua pˇredej´ıt tak nutnosti intenzivn´ıho vyhled´ av´an´ı ve stromˇe po vˇetˇsinu ˇcasu. Velikost cache pro sklad blok˚ u a mapu API funkc´ı Graf na obr´ azku 4.3 ukazuje, kolik procent operac´ı vyhled´ an´ı skonˇcilo nalezen´ım hledan´eho objektu v cache. Procentu´aln´ı u ´spˇeˇsnost je uvedena v z´avislosti na velikosti cache, kter´ a je urˇcena poˇctem bit˚ u indexu do pole reprezentuj´ıc´ıho cache. Budeme-li poˇzadovat u ´spˇeˇsnost alespoˇ n 90%, bude odpov´ıdaj´ıc´ı velikost cache pro kaˇzd´ y program jin´ a. Toto je zp˚ usobeno r˚ uznou velikost´ı skupiny blok˚ u, kter´a tvoˇr´ı smyˇcku realizuj´ıc´ı zpracov´an´ı dat. Pro program Lame je tato skupina, dle v´ ysledk˚ u mˇeˇren´ı, menˇs´ı neˇz pro 7-Zip. ˇ Cetnost vyhled´ an´ı v mapˇe API funkc´ı je v´ yraznˇe menˇs´ı neˇz je tomu u skladu blok˚ u. Lze tak´e pˇredpokl´ adat, ˇze skupina API funkc´ı volan´ ych v pr˚ ubˇehu zpracov´av´an´ı dat bude ˇr´adovˇe menˇs´ı, neˇz skupina blok˚ u. Tomuto pˇredpokladu odpov´ıdaj´ı i namˇeˇren´e hodnoty. V nˇekter´ ych pˇr´ıpadech byl poˇcet volan´ ych API funkc´ı tak mal´ y, ˇze ovlivnil u ´spˇeˇsnost cache. Vyhled´avan´ y objekt se totiˇz do cache dostane aˇz po prvn´ım vyhled´ an´ı. Je-li vˇsak kaˇzd´ a API funkce vol´ana pouze jednou, v´ yhody cache se neprojev´ı. Toto se t´ yk´ a napˇr. u ´spˇeˇsnosti cache pro mapu API funkc´ı pro program Lame. 4.2.3

Zhodnocen´ı n´ avrhu datov´ ych struktur

Z proveden´e anal´ yzy testovan´ ych program˚ u vypl´ yv´ a, ˇze pro rozdˇelen´ı kl´ıˇce pro hled´an´ı v obecn´em vyhled´ avac´ım stromˇe hraje v´ yznamnou roli hranice pamˇet’ov´e str´anky resp. alokaˇcn´ı granularity operaˇcn´ı pamˇeti. Bˇeˇzn´ a velikost pamˇet’ov´e str´anky je 4kB, tj. 12 nejm´enˇe v´ yznamn´ ych bit˚ u kl´ıˇce odpov´ıd´ a offsetu ve str´ance a zbyl´ ych 20 bit˚ u tvoˇr´ı ˇc´ıslo str´anky. N´ ami zvolen´e ˇclenˇen´ı kl´ıˇce na pole, 4 pole po 8 bitech, rozdˇeluje str´anku v pamˇeti na 16 ˇc´ast´ı a dovoluje tak uspoˇrit pamˇet’ spotˇrebovanou vyhled´ avac´ım stromem v pˇr´ıpadˇe, ˇze je v´ yskyt kl´ıˇc˚ u

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

42 120

úspěšnost cache [%]

100

80

60

40

20

0

2

3

4

5

6

7

8

9

počet bitů klíče pro cache [b]

10

11

12

13

7-Zip: cache pro sklad bloků 7-Zip: cache pro mapu API funkcí Lame: cache pro sklad bloků Lame: cache pro mapu API funkcí

´ eˇsnost cache Obr´azek 4.3: Uspˇ

v r´amci str´anky ˇr´ıdk´ y. ˇ R´ıdk´ y v´ yskyt kl´ıˇc˚ u lze pˇredpokl´ adat u mapy API funkc´ı, kde jednotliv´e kl´ıˇce oznaˇcuj´ı pouze zaˇc´atky funkc´ı. U skladu blok˚ u je situace jin´ a. Hustota kl´ıˇc˚ u je v´ yraznˇe vyˇsˇs´ı, protoˇze popisuj´ı oblasti line´ arn´ıho toku v´ ypoˇctu k´odu v r´ amci funkc´ı a je jich tedy na stejn´em rozsahu adresov´eho prostoru v´ıce. Pro sklad blok˚ u by bylo pamˇet’ovˇe u ´spornˇejˇs´ı ponechat posledn´ı pole ve velikosti pamˇet’ov´e str´anky a uspoˇrit tak jednu u ´roveˇ n vyhled´ avac´ıho stromu. Sn´ıˇzen´ım hloubky vyhled´ avac´ıho stromu m˚ uˇzeme vyuˇz´ıt ke zrychlen´ı vyhled´ av´an´ı (uspoˇr´ıme jeden krok pˇri proch´azen´ı stromu) nebo pro zmenˇsen´ı uzl˚ u stromu na cestˇe ke koˇrenu. Optim´ aln´ı velikost cache pro datov´e struktury nelze obecnˇe urˇcit. Napˇr. c´ılov´e u ´spˇeˇsnosti cache 90% bude odpov´ıdat jin´ a velikost pro kaˇzdou aplikaci. Je tedy vhodn´e stanovit co nejvˇetˇs´ı cache takovou, jej´ıˇz pamˇet’ov´e n´aroky si m˚ uˇzeme dovolit. Pro obˇe datov´e struktury pouˇz´ıv´ ame cache s indexem o velikosti 10 bit˚ u, coˇz znamen´a velikost jedn´e cache 8kB (poloˇzku cache tvoˇr´ı dvˇe ˇc´ısla o velikosti 4B).

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

4.3

43

Tvorba blok˚ u

Velmi d˚ uleˇzit´ ym ukazatelem struktury programu jsou parametry blok˚ u tvoˇren´ ych z jeho k´odu. Zaj´ım´ame se pˇredevˇs´ım o poˇcet blok˚ u nutn´ ych pro emulaci, velikosti blok˚ u, procento blok˚ u se statick´ ym ukonˇcen´ım (tedy procento ˇretˇeziteln´ ych blok˚ u) a expanze k´odu v d˚ usledku pˇrekladu. 4.3.1

Velikosti blok˚ u

Velikost blok˚ u hraje roli pˇri pˇr´ıpadn´em sn´ıˇzen´ı pamˇet’ov´ ych n´arok˚ u emul´ atoru. Znalost rozloˇzen´ı velikost´ı blok˚ u umoˇzn ˇuje navrhnout co nej´ uspornˇejˇs´ı zp˚ usob alokace pamˇeti. 7-Zip

gzip

1400

250

200

1000

počet bloků [-]

počet bloků [-]

1200

800 600 400

800

0 0

500 1000 1500 2000 2500 3000 3500 4000 4500

velikost bloku [B]

AxCrypt

600

700

počet bloků [-]

počet bloků [-]

500 1000 1500 2000 2500 3000 3500 4000 4500

velikost bloku [B]

lame

500

600 500 400 300 200

400 300 200 100

100 0 0

100 50

200 0 0

150

500 1000 1500 2000 2500 3000 3500 4000 4500

velikost bloku [B]

0 0

500 1000 1500 2000 2500 3000 3500 4000 4500

velikost bloku [B]

Obr´azek 4.4: Velikosti blok˚ u pro testovan´e programy Graf na obr´ azku 4.4 ukazuje histogram velikost´ı blok˚ u. Interval 0 aˇz 4096B je rozdˇelen na 32 stejnˇe velk´ ych podinterval˚ u, do kter´ ych jsou jednotliv´e bloky tˇr´ıdˇeny. Posledn´ı podinterval zahrnuje nav´ıc vˇsechny bloky vˇetˇs´ı neˇz 4096B. Z graf˚ u je patrn´e, ˇze nejv´ıce blok˚ u spad´ a do intervalu okolo velikosti 256B. U program˚ u gzip a lame se dokonce vyskytly bloky o velikosti vˇetˇs´ı neˇz 4kB. 4.3.2

Poˇ cet blok˚ u, expanze k´ odu a procento blok˚ u se statick´ ym ukonˇ cen´ım

Na z´avˇer anal´ yzy blok˚ u uvedeme parametry vypov´ıdaj´ıc´ı o struktuˇre k´odu emulovan´ ych program˚ u, kter´e n´am mohou dopomoci vysvˇetlit pˇr´ıpadn´e rozd´ıly v efektivitˇe emulace jednotliv´ ych program˚ u. Parametry pro testovan´e programy ud´av´a tabulka 4.3.

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

44 program gzip 7-Zip AxCrypt lame

poˇcet blok˚ u % stat. ukonˇcen´ı expanze k´odu 852 60,09% 13,06 5173 66,52% 15,62 2544 64,11% 16,70 2972 70,36% 11,76

Tabulka 4.3: Hodnoty parametr˚ u mˇeˇren´ ych program˚ u Expanzi k´odu ud´av´ame jako pod´ıl velikosti vˇsech blok˚ u ku velikosti k´odu v bytech, ze kter´ ych byly bloky pˇreloˇzeny.

4.4

Dynamick´ e vlastnosti programu

Kl´ıˇcovou dynamickou vlastnost´ı programu je efektivita emulace. V tomto odstavci se vˇenujeme z´avislosti efektivity emulace na r˚ uzn´ ych parametrech emul´ atoru nebo emulovan´eho programu. 4.4.1

Mˇ eˇ ren´ı efektivity emulace

Efektivita emulace je definov´ana jako pomˇer doby bˇehu programu bez emulace a doby bˇehu programu v emulaci. Stejn´ ym zp˚ usobem budeme efektivitu i mˇeˇrit. Abychom vylouˇcili nepˇresnosti zp˚ usoben´e napˇr. naˇc´ıt´ an´ım DLL knihoven z pevn´eho disku2 , budeme kaˇzd´e mˇeˇren´ı doby v´ ypoˇctu programu v emulaci a bez n´ı prov´adˇet tˇrikr´ at. V´ ysledn´a efektivita bude pr˚ umˇerem tˇechto tˇr´ı mˇeˇren´ı. 4.4.2

Efektivita emulace a d´ elka bˇ ehu emulovan´ eho programu

ˇ Casovˇ e nejn´ aroˇcnˇejˇs´ı operac´ı v r´ amci emulace je tvorba bloku. Vliv ˇcasov´e n´aroˇcnosti tvorby blok˚ u na efektivitu emulace je t´ım menˇs´ı, ˇc´ım delˇs´ı je celkov´a doba emulace. Po urˇcit´e dobˇe jsou jiˇz vˇsechny bloky nutn´e pro emulaci k´odu zpracov´avaj´ıc´ıho data vytvoˇreny a uloˇzeny ve skladu blok˚ u. K tvorbˇe blok˚ u uˇz pak nedoch´az´ı. V pˇr´ıpadn´em komerˇcn´ım nasazen´ı emul´ atoru mus´ı dynamick´a anal´ yza programu probˇehnout co nejrychleji. Lze pˇredpokl´ adat, ˇze doba emulace bude shora omezena urˇcit´ ym ˇcasem, po kter´em heuristick´ y modul konstatuje nedostatek informac´ı. Zaj´ım´a n´as tedy hlavnˇe efektivita emulace program˚ u bˇeˇz´ıc´ıch po kr´atkou dobu, kde se projev´ı tvorba blok˚ u. Vybran´ y vzorek testovac´ıch program˚ u je vhodn´ y pr´avˇe pro toto mˇeˇren´ı, protoˇze m˚ uˇzeme ovlivˇ novat dobu bˇehu volbou velikosti vstupn´ıch dat. Graf na obr´ azku 4.5 ukazuje z´avislost efektivity emulace vybran´ ych program˚ u na d´elce bˇehu programu bez emulace. Ani pˇri pouˇzit´ı velmi mal´eho mnoˇzstv´ı vstupn´ıch dat (des´ıtky byt˚ u) se nepodaˇrilo doc´ılit doby emulace kratˇs´ı neˇz 100ms. Mˇeˇren´ı ukazuje, ˇze efektivita s d´elkou v´ ypoˇctu testovan´ ych program˚ u proti pˇredpokladu kles´a. Z mal´eho poˇctu testovan´ ych program˚ u vˇsak nelze usuzovat o glob´aln´ıch vlastnostech emul´ atoru. Efektivita emulace silnˇe z´avis´ı na struktuˇre k´odu programu a to zejm´ena na parametrech blok˚ u tvoˇr´ıc´ıch ˇc´ast emulovan´eho programu, kter´a je zodpovˇedn´ a za zpracov´av´an´ı dat (jde o nejv´ıce uˇz´ıvan´e bloky). Souvislost klesaj´ıc´ı efektivity emulace a struktury emulovan´eho programu provˇeˇr´ıme v odstavci 4.4.3. 2

Probl´em naˇc´ıt´ an´ı DLL knihoven je hlavnˇe v potenci´ alnˇe rozd´ıln´e dobˇe prvn´ıho a kaˇzd´eho dalˇs´ıho naˇcten´ı. Operaˇcn´ı syst´em totiˇz udrˇzuje ˇcasto pouˇz´ıvan´e knihovny v cache. Dvˇe vykon´ an´ı stejn´eho programu mohou tedy trvat r˚ uznou dobu.

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

45

0.6

efektivita emulace [-]

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

1.5

2

doba výpočtu programu bez emulace [s] gzip

7zip

Obr´azek 4.5: Z´avislost efektivity emulace na d´elce v´ ypoˇctu programu 4.4.3

Efektivita emulace a struktura emulovan´ eho programu

V pˇredeˇsl´em mˇeˇren´ı s d´elkou v´ ypoˇctu efektivita emulace klesala. To znamen´a, ˇze pomˇer ˇcasu spotˇrebovan´eho nav´ıc emulac´ı k ˇcasu v´ ypoˇctu programu bez emulace nen´ı konstantn´ı, ale roste na mˇeˇren´em intervalu d´elky bˇehu. Pˇredmˇetem naˇseho z´ajmu je nalezen´ı pˇr´ıˇciny klesaj´ıc´ı efektivity emulace. Jednou z pˇr´ıˇcin zpomalen´ı emulovan´eho programu je expanze k´odu pˇri tvorbˇe blok˚ u a to hlavnˇe zv´ yˇsen´ y poˇcet instrukc´ı pˇristupuj´ıc´ıch do pamˇeti. Toto zpomalen´ı m´ a charakter konstanty vzhledem k d´elce v´ ypoˇctu jednoho bloku. Pˇri v´ ypoˇctu blok˚ u je nav´ıc vol´an podle potˇreby dispatcher ˇ a to vˇzdy po stejn´ ych bloc´ıch. Cas pro v´ ypoˇcet dispatcheru m˚ uˇzeme tedy pˇridat k ˇcasu v´ ypoˇctu pˇr´ısluˇsn´eho bloku. Oznaˇcme ˇcas v´ ypoˇctu pr˚ umˇern´eho bloku volaj´ıc´ıho dispatcher ta a ˇcas v´ ypoˇctu pr˚ umˇern´eho bloku se zˇretˇezen´ım jako tb . Lze pˇredpokl´ adat, ˇze ta > tb . Celkov´ y ˇcas emulace m˚ uˇzeme pak vyj´adˇrit jako: T = n a · ta + n b · tb + tc kde tc je ˇcas potˇrebn´ y pro inicializaci emulace a na , nb jsou poˇcty volan´ ych blok˚ u dan´eho typu. Mˇeˇren´ı hodnoty nb je technicky obt´ıˇzn´e, protoˇze bychom museli kaˇzd´ y pˇr´ımo zˇretˇezen´ y blok ’ opatˇrit k´odem inkrementuj´ıc´ım hodnotu pamˇet ov´eho m´ısta, kter´e reprezentuje nb . Inkrementace (instrukce inc) nastavuje pˇr´ıznaky procesoru, takˇze bychom museli pˇrepnout do kontextu emul´ atoru. V naˇsem mˇeˇren´ı proto hodnotu nb vypust´ıme. Vzhledem k tomu, ˇze nb oznaˇcuje

46

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

poˇcet pr˚ umˇern´ ych blok˚ u (tj. pr˚ umˇern´ ych z pohledu spotˇrebovan´eho v´ ypoˇcetn´ıho ˇcasu), mus´ı b´ yt nb pˇr´ımo u ´mˇern´e dobˇe bˇehu emulovan´eho programu bez emulace. Naopak hodnota na se mˇeˇr´ı snadno pˇrid´ an´ım pˇr´ısluˇsn´e instrukce inkrementace do k´odu dispatcheru a nen´ı nutnˇe pˇr´ımo u ´mˇern´ a dobˇe bˇehu emulovan´eho programu bez emulace. Jedn´ a se o poˇcet volan´ ych blok˚ u s dynamick´ ym ukonˇcen´ım a to je hodnota z´avisl´a na struktuˇre konkr´etn´ıho emulovan´eho programu. Zat´ımco nb roste s ˇcasem line´ arnˇe, na z´avis´ı na konkr´etn´ıch cest´ ach v´ ypoˇctu ve zdrojov´em k´odu emulovan´eho programu. Bude-li napˇr´ıklad program pro jednu instanci vstupn´ıch dat volat API funkce v´ıce neˇz pro jinou, bude efektivita emulace r˚ uzn´ a, i kdyby byly obˇe instance vstupn´ıch dat stejnˇe velk´e. Jedna z moˇzn´ ych metrik pro mˇeˇren´ı obt´ıˇznosti emulace m˚ uˇze b´ yt pr´avˇe hodnota na – tedy poˇcet vol´an´ı dispatcheru. Mˇ eˇ ren´ı z´ avislosti efektivity emulace na poˇ ctu vol´ an´ı dispatcheru V pˇredchoz´ıch u ´vah´ ach jsme uvaˇzovali ˇcas v´ ypoˇctu dispatcheru jako konstantu. Ve skuteˇcnosti toto nen´ı pravda. Pomineme-li prodlouˇzen´ı v´ ypoˇctu dispatcheru n´asledkem tvorby nov´eho bloku (po vytvoˇren´ı vˇsech potˇrebn´ ych blok˚ u pro emulaci v´ ypoˇcetnˇe n´aroˇcn´e ˇc´asti emulovan´eho programu se nov´e bloky nevytv´ aˇrej´ı), existuj´ı dvˇe hlavn´ı varianty pr˚ uchodu dispatcherem. V pˇr´ıpadˇe vol´an´ı dispatcheru v d˚ usledku emulace instrukce jmp resp. call je tˇreba nejprve vyhledat v mapˇe API funkc´ı, zda se nepokouˇs´ı emulovan´ y program volat nˇekterou zn´ amou funkci (v takov´em pˇr´ıpadˇe bychom pˇresmˇerovali vol´an´ı do pˇr´ısluˇsn´e emulovan´e verze) a teprve pak n´asleduje vyhled´ an´ı navazuj´ıc´ıho bloku. Vyhled´ an´ı v mapˇe API funkc´ı nebo ve skladu blok˚ u je implementov´ano stejnˇe (viz. odstavec 3.2 o obecn´em vyhled´ avac´ım stromu). Druh´a varianta pr˚ uchodu dispatcherem zahrnuje pouze vyhled´ an´ı ve skladu blok˚ u. Je tedy vhodnˇejˇs´ı mˇeˇrit poˇcty vyhled´ an´ı v obecn´em vyhled´ avac´ım stromu neˇz pouze poˇcet vykon´ an´ı dispatcheru. Graf na obr´ azku 4.6 dole ukazuje ˇcas spotˇrebovan´ y emulac´ı nav´ıc oproti bˇehu programu bez emulace. Zobrazen´ a z´avislost vykazuje line´ arn´ı charakter. Kdybychom namˇeˇren´e body proloˇzili pˇr´ımkou, dostali bychom ˇcas nutn´ y pro inicializaci emulace jako pr˚ useˇc´ık pˇr´ımky se svislou osou. Rozd´ıln´ y sklon myˇslen´ ych pˇr´ımek pro mˇeˇren´e programy lze vysvˇetlit r˚ uzn´ ym mnoˇzstv´ım pˇridan´ ych instrukc´ı pˇristupuj´ıc´ıch do pamˇeti pˇri tvorbˇe blok˚ u nebo r˚ uzn´ ym poˇctem volan´ ych blok˚ u se statick´ ym ukonˇcen´ım. Dopad na efektivitu emulace je pak zobrazen na grafu nahoˇre na obr´ azku 4.6. Pro efektivitu emulace plat´ı E=

to to 1 = = te to + t∆e 1 + tt∆e o

kde to je d´elka bˇehu programu bez emulace, te je d´elka bˇehu programu pˇri emulaci a t∆e je ˇcas pˇridan´ y nav´ıc emulac´ı oproti bˇehu bez emulace. Efektivita emulace kles´a vinou rostouc´ıho pod´ılu t∆e a to . ˇ pˇridan´ Cas y emulac´ı dle mˇeˇren´ı z´avis´ı line´ arnˇe na poˇctu operac´ı vyhled´ an´ı v obecn´em vyhled´avac´ım stromu. Pokud by efektivita emulace s ˇcasem soustavnˇe klesala, musel by poˇcet operac´ı vyhled´ an´ı na ˇcasovou jednotku neust´ ale r˚ ust, coˇz nen´ı moˇzn´e. Po urˇcit´e dobˇe se poˇcet vyhled´ an´ı na ˇcasovou jednotku ust´al´ı a pod´ıl t∆e a to pˇrestane r˚ ust (nebo m˚ uˇze dokonce klesnout). Toto chov´an´ı dokl´ adaj´ı i grafy na obr. 4.5 a obr. 4.6 nahoˇre, kde lze pozorovat urˇcitou konvergenci efektivity emulace k hodnotˇe odpov´ıdaj´ıc´ı konstantn´ımu pod´ılu t∆e a to . Pozorovan´e kles´an´ı efektivity je tady pˇrechodn´ y jev zp˚ usoben´ y r˚ ustem poˇctu vykonan´ ych operac´ı vyhled´ an´ı v obecn´em vyhled´ avac´ım stromu na jednotku ˇcasu.

´ ´ KAPITOLA 4. ANALYZA EMULOVANEHO PROGRAMU

47

0.7

efektivita emulace [-]

0.6 0.5 0.4 0.3 0.2 0.1 0

0.00E+00

1.00E+06

2.00E+06

3.00E+06

4.00E+06

5.00E+06

6.00E+06

7.00E+06

počet vyhledání v obecném vyhledávacím stromu [-]

čas spotřebovaný navíc při emulaci [s]

7-Zip

8.00E+06

gzip

2.5 2 1.5 1 0.5 0

0.00E+00

1.00E+06

2.00E+06

3.00E+06

4.00E+06

5.00E+06

6.00E+06

7.00E+06

počet vyhledání v obecném vyhledávacím stromu [-] 7-Zip

8.00E+06

gzip

Obr´azek 4.6: Z´avislost efektivity emulace na poˇctu vyhled´ an´ı v obecn´em vyhled´ avac´ım stromu

´ KAPITOLA 5. BUDOUC´I PRACE

48

5 Budouc´ı pr´ ace 5.1

Dalˇ s´ı v´ yvoj emul´ atoru

Dosavadn´ı pr´ace na n´avrhu a implementaci emul´ atoru byly zamˇeˇreny hlavnˇe na efektivitu emulace. D˚ uleˇzit´ ym parametrem emul´ atoru jsou ale i jeho pamˇet’ov´e n´aroky. Implementovan´ a verze emul´ atoru prozat´ım pˇredpokl´ ad´ a jako vstup programy, kter´e nejsou vybaveny opatˇren´ımi proti emulaci, coˇz vyluˇcuje nasazen´ı implementovan´e verze emul´ atoru jako prostˇredku pro anal´ yzu nebezpeˇcn´eho k´odu. Velmi v´ yznamn´ ym u ´kolem do budoucna je i implementace ˇsirˇs´ı mnoˇziny funkc´ı Win32 API. 5.1.1

Sn´ıˇ zen´ı pamˇ et’ov´ ych n´ arok˚ u

Jednou z moˇznost´ı, jak sn´ıˇzit pamˇet’ov´e n´aroky je implementovat vlastn´ı dynamickou pamˇet’ pro alokaci blok˚ u. Na z´akladˇe mˇeˇren´ı typick´ ych velikost´ı blok˚ u rozdˇel´ıme pamˇet’ovou str´anku na nˇekolik ˇc´ast´ı, kter´e budeme d´ale dˇelit na bloky pamˇeti podle typick´ ych velikost´ı pˇreloˇzen´ ych blok˚ u k´odu. Velikost jednotliv´ ych ˇc´ast´ı a t´ım i poˇcet pamˇet’ov´ ych blok˚ u urˇcit´e velikosti pˇrizp˚ usob´ıme rozloˇzen´ı velikost´ı blok˚ u k´odu. T´ımto pˇr´ıstupem lze sn´ıˇzit mnoˇzstv´ı pamˇeti a jej´ı fragmentaci, kter´e je alokov´ano nav´ıc oproti skuteˇcn´e potˇrebˇe, pouˇz´ıv´ ame-li mechanismus alokace dynamick´e pamˇeti poskytnut´ ym 1 operaˇcn´ım syst´emem Windows . Dalˇs´ı u ´spory pamˇeti m˚ uˇzeme dos´ ahnout v´ yhodnˇejˇs´ım rozdˇel´ım kl´ıˇce pro vyhled´ av´an´ı v obecn´em vyhled´ avac´ım stromu a to pro kaˇzd´e jeho pouˇzit´ı zvl´aˇst’ (tj. pro sklad blok˚ u a pro mapu API funkc´ı). 5.1.2

Opatˇ ren´ı proti detekci emulace

Tv˚ urci vir˚ u a malwaru obecnˇe si jsou vˇedomi moˇznosti emulace nebo debugov´an´ı jejich program˚ u, a proto je opatˇruj´ı ochranami. ˇ ala moˇzn´ ´ Sk´ ych opatˇren´ı je ˇsirok´ a. Ulohou emul´ atoru je omezit mnoˇzinu povolen´ ych operac´ı pro emulovan´ y program natolik, aby takov´a ˇcinnost nebyla moˇzn´ a. Nˇekdy je vˇsak tˇreba za u ´ˇcelem odkryt´ı skryt´eho k´odu opatˇren´ı proti emulaci ˇr´adnˇe prov´est, aniˇz by k detekci doˇslo. Mezi nejrozˇs´ıˇrenˇejˇs´ı techniky patˇr´ı pˇresmˇerov´an´ı toku v´ ypoˇctu (skoku v programu) pomoc´ı v´ yjimek, nebo speci´aln´ı pasti nut´ıc´ı emul´ ator vytv´ aˇret napˇr. velk´e mnoˇzstv´ı blok˚ u, coˇz zapˇr´ıˇcin´ı ne´ unosnou d´elku dynamick´e anal´ yzy.

5.2

Heuristick´ y modul

N´ avrh heuristick´eho modulu je z velk´e ˇc´asti v´ yzkumn´ yu ´kol. Pˇredmˇetem v´ yzkumu je nalezen´ı dostateˇcnˇe spolehliv´e metody pro identifikaci programu na z´akladˇe jeho dynamick´eho chov´an´ı. V pˇr´ıpadˇe nezn´am´eho k´odu pak mus´ı b´ yt heuristick´ y modul schopn´ y rozhodnout, na z´akladˇe dat poskytnut´ ych emul´ atorem, o jeho nebezpeˇcnosti. Vstupn´ı informace pro heuristick´ y modul zahrnuj´ı napˇr. vol´an´ı API funkc´ı vˇcetnˇe jejich parametr˚ u, pˇr´ıstupy programu do pamˇeti nebo n´ahled na skuteˇcn´e cesty v´ ypoˇctu k´odu. 5.2.1

Moˇ znosti detekce malwaru

Pˇri statick´e anal´ yze programu se nebezpeˇcn´ y k´od identifikuje pomoc´ı charakteristick´e posloupnosti instrukc´ı – signatury. Pˇri jej´ı tvorbˇe m´ ame k dispozici pouze statick´a data v podobˇe bin´ arn´ıho souboru. 1 OS Windows implementuje mechanismus alokace mal´ ych blok˚ u dynamick´e pamˇeti prostˇrednictv´ım tzv. heap – hromada. V´ıce informac´ı viz. dokumentace k funkc´ım Win32 API HeapCreate

´ KAPITOLA 5. BUDOUC´I PRACE

49

Identifikaci programu m˚ uˇzeme zaloˇzit tak´e na jeho chov´ an´ı; tj. napˇr´ıklad na charakteristick´e posloupnosti vol´an´ı API funkc´ı, nebo pˇr´ıstupu do pamˇeti. Takto z´ıskan´ y identifik´ator se naz´ yv´ a dynamick´ a signatura. Myˇslenkou identifikace malwaru pomoc´ı sekvence vol´an´ı API funkc´ı se zab´ yv´ a napˇr. [14] nebo [12]. Jestliˇze pˇri emulaci naraz´ıme na novou, nebo lehce modifikovanou, verzi malwaru, m˚ uˇze identifikace podle zn´ am´ ych signatur selhat. V takov´em pˇr´ıpadˇe je potˇreba nasadit heuristiku. Napˇr. v pˇr´ıpadˇe skryt´eho k´odu se bude snaˇzit program nejdˇr´ıve rozbalit sv˚ uj ukryt´ y obsah a pak do nˇej pˇresunout v´ ypoˇcet. Bˇehem emulace m˚ uˇzeme tuto ˇcinnost detekovat jako pokus vytvoˇrit blok z pamˇeti, kter´ a neodpov´ıd´ a mapov´an´ı modulu emulovan´eho programu. Heuristika by tedy mˇela detekovat co nejv´ıce takov´ ych nestandardn´ıch operac´ı, pro kter´e v bˇeˇzn´em programu nen´ı ˇz´adn´ y d˚ uvod.

50

´ ER ˇ KAPITOLA 6. ZAV

6 Z´ avˇ er Analyzovali, navrhli a implementovali jsme program pro dynamickou anal´ yzu k´odu, kter´ y umoˇzn ˇuje pomoc´ı emulace prostˇredk˚ u poˇc´ıtaˇce a operaˇcn´ıho syst´emu analyzovat aplikace pro operaˇcn´ı syst´em Microsoft Windows XP na platformˇe Intel x86. Pro analyzov´an´ı obsahu spustiteln´ ych soubor˚ u ve form´ atu COFF/PE jsme implementovali tabulkami ˇr´ızen´ y disassembler umoˇznuj´ıc´ı dek´ odovat instrukce sady Intel x86 v 32-bitov´e verzi vˇcetnˇe rozˇs´ıˇren´ı MMX, SSE1 a SSE2. Samotnou emulaci pak zajiˇst’uje emulaˇcn´ı smyˇcka v souˇcinnosti s emul´ atorem operaˇcn´ıho syst´emu. Emulaˇcn´ı smyˇcka analyzuje k´od a dˇel´ı jej na bloky line´ arn´ıho toku v´ ypoˇctu, kter´e jsou po transformaci vloˇzeny do skladu blok˚ u. Emulace prob´ıh´ a vykon´ av´an´ım k´odu transformovan´ ych blok˚ u, na jejichˇz konci je vol´ana funkce pro nalezen´ı bloku ve skladu nebo vytvoˇren´ı nov´eho bloku. Emulovan´ y program je vloˇzen do sandboxu, kter´ y je tvoˇren emulac´ı Windows API a pˇrekladem pamˇet’ov´ ych operac´ı. Sandbox nedovoluje emulovan´emu programu nedovolenˇe pozmˇen ˇovat stav operaˇcn´ıho syst´emu nebo ostatn´ıch bˇeˇz´ıc´ıch program˚ u. V r´amci emulace m´ ame tedy plnou kontrolu nad volan´ ymi funkcemi Windows API, operacemi s pamˇet´ı i jednotliv´ ymi instrukcemi a m˚ uˇzeme tedy sb´ırat informace o dynamick´em chov´an´ı programu. Pˇri anal´ yze, n´avrhu i implementaci jsme kladli hlavn´ı d˚ uraz na rychlost (efektivitu) emulace. Analyzov´an´ı ˇcinnosti emul´ atoru pˇri emulaci vybran´ ych aplikac´ı uk´azalo, ˇze efektivita emulace z´avis´ı hlavnˇe na struktuˇre emulovan´eho programu. U vybran´ ych aplikac´ı bylo namˇeˇreno pr˚ umˇernˇe trojn´asobn´e zpomalen´ı oproti v´ ypoˇctu bez emulace (pˇri pouˇzit´ı velikosti vstupn´ıch dat emulovan´ ych program˚ u okolo 512kB). Efektivita emulace oproti pˇredpokladu s ˇcasem kles´a vinou nar˚ ustaj´ıc´ıho poˇctu vyhled´ an´ı v datov´ ych struktur´ ach na jednotku ˇcasu. Poˇcet vyhled´ ani z´avis´ı pr´avˇe na struktuˇre emulovan´eho programu a na jeho konkr´etn´ı ˇcinnosti, kter´a je z´avisl´a tak´e na vstupn´ıch datech. Poˇcet operac´ı vyhled´ an´ı v datov´ ych struktur´ ach emul´ atoru na jednotku ˇcasu zˇrejmˇe nem˚ uˇze r˚ ust nade vˇsechny meze. Efektivita emulace proto konverguje k minim´aln´ı hodnotˇe, kter´a je pro kaˇzd´ y emulovan´ y program jin´ a. Nepodaˇrilo se implementovat detekci samorozbalovac´ıho k´odu vinou ˇcasov´ ych n´arok˚ u na implementaci emulace Windows API. D´ ale by bylo nutn´e implementovat alespoˇ n nˇekter´a opatˇren´ı proti detekci emulace, coˇz je opˇet ˇcasovˇe n´aroˇcn´ a ˇcinnost hlavnˇe z hlediska testov´an´ı. Budouc´ı pr´ace v oblasti dynamick´e anal´ yzy podezˇrel´eho k´odu by se mˇela zamˇeˇrit hlavnˇe na zp˚ usob dostateˇcnˇe u ´ˇcinn´e identifikace k´odu na z´akladˇe jeho dynamick´eho chov´an´ı. Dalˇs´ı pr´ace na emul´ atoru budou zahrnovat optimalizaci pamˇet’ov´ ych n´aroku, implementaci vˇetˇs´ı mnoˇziny funkc´ı Windows API a zaveden´ı opatˇren´ı proti detekci emulace.

51

KAPITOLA 7. LITERATURA

7 Literatura [1] Bochs ia-32 emulator project. http://bochs.sourceforge.net/. [2] Doxygen, a documentation system for c++. http://www.stack.nl/ dimitri/doxygen/. [3] Advanced Micro Devices, Inc. 3DNow! Technology Manual, 2000. [4] F. Bellard. QEMU - a generic http://fabrice.bellard.free.fr/qemu/.

and

open

source

processor

emulator.

[5] Intel Corporation, http://www.intel.com/products/processor/manuals/index.htm. IA-32 Intel Architecture Software Developer’s Manual. ˇ [6] J. Kol´ aˇr. Teoretick´ a informatika. CIS, Praha, 1996. [7] P. Magnusson. Partial translation. Technical Report T93-05, 1, 1993. [8] Microsoft Corporation. MSDN Library. [9] Microsoft Corporation, http://msdn2.microsoft.com/en-us/library/default.aspx. Windows API Reference. [10] N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, November 2004. [11] I. Piumarta and F. Riccardi. Optimizing direct-threaded code by selective inlining. In SIGPLAN Conference on Programming Language Design and Implementation, pages 291– 300, 1998. [12] K. Rozinov. Efficient static analysis of executables for detecting malicious behaviors. Master’s thesis, Polytechnic University, Brooklyn, NY, Brooklyn, NY, June 2005. [13] D. A. Solomon and M. E. Russinovich. Inside Microsoft Windows 2000, Third Edition. Microsoft Press, 2000. [14] A. H. Sung, J. Xu, P. Chavez, and S. Mukkamala. Static analyzer of vicious executables. In Annual Computer Security Applications Conference, 2004.