Sem vložte zadání Vaší práce

Sem vložte zadání Vaší práce.

České vysoké učení technické v Praze Fakulta informačních technologií Katedra počítačových systémů

Diplomová práce

Distribuované prolamování hesel v PDF na svazku GPU Bc. Martin Bak

Vedoucí práce: Ing. Tomáš Zahradnický, EUR ING, Ph.D.

9. května 2012

Poděkování Díky panu Ing. Tomášovi Zahradnickému, EUR ING, Ph.D. za odborné vedení diplomové práce, podnětné nápady a pečlivý přístup. Díky pánům Ing. Ivanovi Šimečkovi, Ph.D., Ing. Jakubovi Hladíkovi a především Ing. Milanovi Václavíkovi za správu školního clusteru a obětavou pomoc při závěrečném měření. Díky mému nadřízenému Ing. Václavovi Pokludovi za velmi tolerantní přístup k mým studiím. Díky všem, kteří věřili, že se dostanu až sem a všem, kteří věří, že se dostanu ještě o kus dál.

Prohlášení Prohlašuji, že jsem předloženou práci vypracoval samostatně a že jsem uvedl veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona, ve znění pozdějších předpisů, zejména skutečnost, že České vysoké učení technické v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle § 60 odst. 1 autorského zákona.

V Praze dne 9. května 2012

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

České vysoké učení technické v Praze Fakulta informačních technologií c 2012 Martin Bak. Všechna práva vyhrazena.

Tato práce vznikla jako školní dílo na Českém vysokém učení technickém v Praze, Fakultě informačních technologií. Práce je chráněna právními předpisy a mezinárodními úmluvami o právu autorském a právech souvisejících s právem autorským. K jejímu užití, s výjimkou bezúplatných zákonných licencí, je nezbytný souhlas autora.

Odkaz na tuto práci Martin Bak. Distribuované prolamování hesel v PDF na svazku GPU: Diplomová práce. Praha: ČVUT v Praze, Fakulta informačních technologií, 2012.

Abstract The diploma thesis deals with optimization of existing software for cracking passwords in PDF documents and adapting it to run on GPU devices. It describes the entire process from analysis, through design and optimizations of individual components, to the final implementation. New application supports computing on GPU devices, active load balancing and provides reliable PDF parser. Last part of the thesis compares newly created appliaction with the original solution. Keywords PDF, password cracking, load balancing, GPU

Abstrakt Diplomová práce se zabývá optimalizací existujícího řešení pro prolamování hesel v PDF souborech, zejména pak jeho úpravou pro běh na svazcích GPU. Popisuje celý proces od analýzy, přes návrh a optimalizaci jednotlivých částí až po samotnou implementaci nové aplikace. Ta kromě podpory běhu na GPU implementuje aktivní vyvažování zátěže a disponuje spolehlivým PDF parserem. V závěru práce je výsledná aplikace srovnávána s původním řešením. Klíčová slova PDF, prolamování hesel, vyvažování zátěže, GPU

ix

Obsah 1 Úvod

1

2 Analýza 2.1 Popis řešení z bakalářské práce . . . . . . . . . . 2.1.1 POSIX verze . . . . . . . . . . . . . . . . 2.1.2 MPI verze . . . . . . . . . . . . . . . . . . 2.2 Dostupné aplikace pro prolamování hesel v PDF 2.2.1 GuaPDF . . . . . . . . . . . . . . . . . . 2.2.2 Advanced PDF Password Recovery . . . . 2.2.3 PDF Password Cracker . . . . . . . . . . 2.2.4 PDFCrack . . . . . . . . . . . . . . . . . . 2.2.5 Shrnutí . . . . . . . . . . . . . . . . . . . 2.3 CUDA . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Jazyková rozšíření . . . . . . . . . . . . . 2.4 GPULab — školní cluster . . . . . . . . . . . . . 2.4.1 HW konfigurace uzlů . . . . . . . . . . . . 2.4.2 SW prostředí . . . . . . . . . . . . . . . . 2.4.2.1 Meziprocesní komunikace . . . . 2.4.2.2 Šifrovací algoritmy . . . . . . . . 2.5 Vyvažování zátěže . . . . . . . . . . . . . . . . . 2.5.1 Statické vyvažování . . . . . . . . . . . . 2.5.2 Dynamické vyvažování . . . . . . . . . . . 2.6 Shrnutí . . . . . . . . . . . . . . . . . . . . . . . 3 Návrh 3.1 Komunikační model . . . . . . . . 3.2 Architektura aplikace . . . . . . . 3.2.1 Vyvažování zátěže . . . . . 3.2.2 Parsování PDF souborů . . 3.2.3 Ukládání stavu do souboru 3.2.4 Návrh optimalizací . . . . .

. . . . . .

xi

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

. . . . . .

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

3 3 4 4 5 5 6 7 7 7 8 10 12 12 13 13 14 14 15 15 16

. . . . . .

17 17 18 18 19 19 20

. . . .

. . . .

. . . .

. . . .

20 21 22 23

4 Implementace a testování 4.1 Popis finální aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Komunikační část . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1.1 Master část . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1.2 Slave část . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Výpočetní část . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2.1 Struktura výpočetního vlákna . . . . . . . . . . . . . . 4.1.3 Vyvažování zátěže . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.4 Parsování PDF souborů . . . . . . . . . . . . . . . . . . . . . . . 4.1.5 Ukládání stavu do souboru . . . . . . . . . . . . . . . . . . . . . 4.2 Optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Výsledky profilování . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Výpočet šifrovacích funkcí . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Práce s pamětí grafické karty . . . . . . . . . . . . . . . . . . . . 4.2.4 Popis spouštění aplikace . . . . . . . . . . . . . . . . . . . . . . . 4.3 Měření a výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Způsob měření . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Naměřené hodnoty . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2.1 Porovnání čistého výkonu šifrovacích algoritmů na CPU 4.3.2.2 Porovnání výkonu clusteru pouze na CPU . . . . . . . . 4.3.2.3 Vliv počtu vláken na rychlost výpočtu na GPU . . . . 4.3.2.4 Porovnání plného výkonu na clusteru . . . . . . . . . . 4.4 Shrnutí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

25 25 25 25 26 27 28 28 30 30 30 30 31 32 32 33 33 34 34 35 36 37 39

3.3

3.2.4.1 3.2.4.2 3.2.4.3 Shrnutí . . . .

Profilování . . . . . Šifrovací algoritmy . CUDA optimalizace . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 Závěr

41

Literatura

43

A Implementované šifrovací algoritmy na GPU 45 A.1 MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 A.2 RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 B Obsah přiloženého CD

49

xii

Seznam obrázků 2.1 2.2 2.3 2.4 2.5

POSIX implementace: komunikační model [1] . . . . MPI implementace: komunikační model [1] . . . . . Porovnání klasického a grafického procesoru [11] . . Možné způsoby organizace bloků vláken na GPU [11] Topologie školního clusteru . . . . . . . . . . . . . .

. . . . .

4 5 8 9 12

3.1 3.2 3.3

Master-Slave model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hrubá architektura aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Příklad grafu volání funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 18 20

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9

Komunikační část — Master . . . . . . . . . . . . . . . Komunikační část — Slave . . . . . . . . . . . . . . . . Výpočetní část . . . . . . . . . . . . . . . . . . . . . . . Struktura výpočetního vlákna . . . . . . . . . . . . . . . Porovnání čistého výkonu šifrovacích algoritmů na CPU Porovnání výkonu clusteru pouze na CPU . . . . . . . . Vliv počtu vláken na rychlost výpočtu na GPU . . . . . Porovnání plného výkonu aplikace na clusteru . . . . . . Porovnání plného výkonu aplikace a pouze CPU části .

. . . . . . . . .

26 26 27 28 35 36 37 38 38

A.1 MD5: jeden krok algoritmu [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 RC5: generování šifrovací posloupnosti [20] . . . . . . . . . . . . . . . . . . . . .

46 47

xiii

. . . . .

. . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

Seznam tabulek 2.1 2.2 2.3 2.4 2.5 2.6

GuaPDF — verze programu . . . . . . . . . Advanced PDF Password Recovery — verze PDF Password Cracker — verze programu . Rozdělení pamětí na grafické kartě . . . . . HW konfigurace školního clusteru . . . . . . Grafické karty v školním clusteru . . . . . .

4.1 4.2 4.3 4.4 4.5

Porovnání Porovnání Porovnání Porovnání Porovnání

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6 6 7 9 12 13

funkce MD5 z IPP a OpenSSL . . . . . . . . funkce RC4 z IPP a OpenSSL . . . . . . . . čistého výkonu šifrovacích algoritmů na CPU výkonu clusteru pouze na CPU . . . . . . . . plného výkonu aplikace na clusteru . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

31 32 34 35 37

xv

. . . . . . programu . . . . . . . . . . . . . . . . . . . . . . . .

Kapitola

Úvod V rámci bakalářské práce [1] byl vytvořen nástroj pro distribuované prolamování hesel v PDF (Portable Document Format [3]) souborech, který je možné spouštět buďto ve více vláknech na jednom stroji, nebo distribuovaně na CPU clusterech pomocí komunikační knihovny MPI (Message Passing Interface [4]). Cílem diplomové práce je přepsat existující řešení tak, aby jej bylo možno spouštět na GPU kartách, zachovat MPI komunikaci a tudíž možnost spouštět program distribuovaně na clusterech a celkově jednotlivé algoritmy optimalizovat, aby byly dostupné výpočetní prostředky maximálně využity. Grafické karty již delší dobu slouží nejen pouze svému původnímu účelu, a to zpracování obrazu a grafiky, ale stále častěji jsou používány také pro obecné výpočty. Na rozdíl od klasických procesorů, které v současné době nabízí jednotky až desítky jader (ať už fyzických nebo virtuálních), procesory grafických karet obsahují jader stovky, přičemž každé jádro je schopné zpracovat v jednom okamžiku desítky vláken. Specifické úlohy lze pak díky této masivní paralelizaci vykonat v časech o několik řádu nižších, než na klasických procesorech. Útok na heslo hrubou silou je velmi snadno paralelizovatelný, neboť jde o aplikaci stále téhož algoritmu nad různými, na sobě navzájem nezávislými, vstupními daty. Důležitou částí diplomové práce tedy bude přizpůsobení algoritmů pro spouštění na GPU procesoru. Neméně důležité bude úprava CPU implementace řešení z bakalářské práce. V současném řešení se v MPI verzi počítá na každém uzlu pouze v jednom vlákně. Proto bude spojena vícevláknová a MPI verze tak, že v rámci clusteru bude maximálně využit každý uzel — vytíženy budou oba procesory — GPU i CPU. V neposlední řadě by všechny algoritmy měly projít revizí a být optimalizovány pokud možno pro co nejvyšší rychlost.

1

1

Kapitola

Analýza Kapitola popisuje stávající řešení z bakalářské práce. Stručně rozebírá jeho strukturu, komunikační model a vyjmenovává možné optimalizace, s ohledem na zadání této práce. Dále se zabývá analýzou dostupných komerčních a nekomerčních nástrojů pro prolamování hesel v PDF souborech. Jednotlivé nástroje jsou krátce popsány a zhodnoceny podle dostupných možností paralelizace. Vzhledem k tomu, že podstatná část práce se bude zabývat implementací algoritmů na grafické kartě, následuje popis architektury CUDA (Compute Unified Device Architecture [2]), pro kterou bude aplikace vyvíjena. Spolu s tím souvisí i popis prostředí, ve kterém bude vývoj probíhat — tedy popis školního GPU clusteru, a to jak po hardwarové, tak softwarové stránce. Z popsaných prostředků následně vyplyne, co bude při návrhu a následné implementaci k dispozici.

2.1

Popis řešení z bakalářské práce

Stávající aplikace je určena pro linuxový operační systém a nabízí rozhraní pouze pro příkazovou řádku. Existují dvě verze, a to vláknová, určená pro běh na jednom stroji s vícejadrovými procesory (nebo i s více procesory) a verze clusterová, určená pro spouštění na výpočetních clusterech. Obě verze se liší v komunikačních modelech a dalších detailech, jejich bližší popis je v kapitolách 2.1.1 a 2.1.2. Samotná výpočetní část — tedy ta, která běží v jednotlivých vláknech respektive uzlech a stará se o výpočet hesel — je ale u obou verzí stejná. Aplikace příjímá na vstupu několik parametrů. Lze zadat typ hesla, který se bude hledat, jeho maximální délka a abeceda, ze které se budou hesla generovat. Dále lze zadat počet vláken/uzlů, na kterých výpočet poběží. Aplikace také umožňuje při násilném ukončení uložit aktuální stav hledání do souboru a následně výpočet z tohoto souboru obnovit. Ukládá se stav každého vlákna/uzlu v okamžiku ukončení. Tuto funkcionalitu lze do jisté míry také využít pro paralelizaci výpočtu — uložený stav v souboru je možné upravit (jde o jednoduchý textový soubor s definovaným formátem) a následně spustit výpočet na jiném stroji nebo v jiném procesu. Implementace algoritmů použitých pro šifrování hesel odpovídá přesně specifikaci PDF formátu [3]. Optimalizace je omezená jen na předvypočítání konstantních dat, která jsou závislá pouze na atributech z daného PDF souboru a nikoli na vstupních datech (tzn. zkoušených heslech).

3

2

2. Analýza

2.1.1

POSIX verze

Existující řešení nabízí dvě různé implementace. POSIX (Portable Operating System Interface [5]) verzi lze spouštět pouze na jednom stroji a využívá dostupná procesorová jádra. Výpočet běží ve vláknech, jejichž počet lze zadat jako argument při spuštění. Na obrázku 2.1 je znázorněn komunikační model této aplikace. Algoritmus je vcelku přímočarý. Stavový prostor se rozdělí rovnoměrně na tolik části, kolik bylo požadováno vláken. Každé vlákno pak zpracovává svoji část, pokud nalezne heslo, nastaví stavovou proměnnou a skončí. Ostatní vlákna během výpočtu pravidelně tuto proměnnou kontrolují a pokud je nastavená, skončí také. Podřízené vlákno n

Hlavní proces vstupní data

nastavení parametrů hledání

rozdělení stavového prostoru

další heslo?

probíhá samotné hledání specifická data pro vlákno

heslo bylo nalezeno

vytvoření vláken a předání specifických dat vlákno ukončí všechna ostatní podřízená vlákna vlákno se uspí (zavolá pthread_join na podřízená vlákna)

heslo nebylo nalezeno

konec funkce vlákna

konec

Obrázek 2.1: POSIX implementace: komunikační model [1]

2.1.2

MPI verze

Architektura MPI verze je o poznání složitější. Obrázek 2.2 představuje její komunikační model. Na každém uzlu běží dvě vlákna. Jedno se stará o MPI komunikaci. Jednou za čas kontroluje, zda přišla nějaká zpráva od hlavního uzlu, jinak spí a nevytěžuje procesor. Ve druhém vlákně probíhá samotný výpočet. Hlavní uzel má na starosti načtení potřebných dat z PDF souboru a předání těchto dat spolu se vstupními parametry ostatním uzlům. Hlavní uzel následně rozdělí stavový prostor na tolik částí, na kolika uzlech je program spuštěný. Každému uzlu předá informace o jeho části a tím dojde keupštění výpočtu na všech uzlech, včetně hlavního. Jakmile je heslo nalezeno, příslušný uzel předá tuto informaci hlavnímu uzlu. Ten poté

4

2.2. Dostupné aplikace pro prolamování hesel v PDF

Hlavní proces

Podřízený proces n

vstupní data

přijetí broadcastu

rozeslání informací o PDF, požadovaných heslech a abecedě pomocí broadcastu

nastavení parametrů hledání

uvedená data

vytvoření vlákna pro hledání hesla

rozdělení stavového prostoru informace o stav. prostoru

odeslání příslušných dat

vytvoření vlákna pro hledání hesla

heslo bylo nalezeno

heslo nebylo nalezeno

přijetí zprávy o nalezení hesla

ukončení ostatních procesů

zvýšení stavové proměnné o 1, pokud dosáhne počtu podřízených procesů, pak

čekání na ostatní procesy

heslo bylo nalezeno

nalezené heslo

odeslání nalezeného hesla

přijetí zprávy o ukončení hledání

heslo nebylo nalezeno

oznámení o nenalezení hesla

konec

přijetí zprávy o nenalezení hesla

zachycen signál SIGINT

zachycen signál SIGINT

odeslání počtu vyzkoušených hesel

konec

uložení stavu hledání do souboru

Obrázek 2.2: MPI implementace: komunikační model [1]

rozešle všem ostatním uzlům pokyn k ukončení výpočtu a po obdržení potvrzující zprávy od každého z nich se sám ukončí.

2.2

Dostupné aplikace pro prolamování hesel v PDF

V bakalářské práci je soupis dostupných nástrojů na prolamování hesel v PDF souborech. K uvedeným programům následuje nyní krátký popis, zohledňující možnosti paralelizace, případně využítí GPU procesorů. Uvedené ceny jsou aktuální k datu sepsání diplomové práce.

2.2.1

GuaPDF

Podle popisu na stránkách [6] programu jde o první program pro prolamování hesel v PDF souborech vůbec. Nabízí široké možnosti, jak narušit ochranu PDF souborů, co se týka odstranění uživatelských omezení. Prolamovat hesla umí pouze uživatelská, a to pouze pro soubory šifrované 40bitovým klíčem. Stejně jako existující řešení z bakalářské práce, také GuaPDF podporuje pouze standardní PDF šifrování. V nejnovější verzi nabízí podporu pro výpočet na grafických kartách, a to jak CUDA, tak OpenCL (Open Computing Language [8]).

5

2. Analýza

Program je nabízen pro mnoho platforem, poskytuje grafické rozhraní, ale dokáže pracovat i z příkazové řádky. Nabízen je v několika verzích, které nabízejí stejnou funkcionalitu (omezení se týkají jen velikosti souboru — v případě demo verze), ale liší se svou výkoností. Tabulka 2.1 shrnuje tyto verze spolu s podstatnými rozdíly. Tabulka 2.1: GuaPDF — verze programu Verze Demo Local Quad Version Distributed 20 clients Unlimited

2.2.2

Distribuovatelnost lze spouštět pouze na jednom stroji, omezení na 2 CPU jádra lze spouštět pouze na jednom stroji, omezení na 4 CPU jádra

CPU

GPU

Cena

ANO

ANO

zdarma

ANO

ANO

e25

podpora až pro 20 uzlů

ANO

ANO

e39

bez omezení počtu uzlů

ANO

ANO

e150

Advanced PDF Password Recovery

Program od firmy Elcomsoft Co. Ltd. je součástí balíku nástrojů pro obnovu a prolamování hesel v mnoha aplikacích [7]. Nabízí prolomení hesel v PDF souborech pomocí několika způsobů. Podle typu šifrování daného souboru buď útočí na šifrovací klíč, případně provádí útok hrubou silou nebo slovníkový útok. Dále umožňuje urychlit prolomení hesel pomocí předvypočítaných tabulek1 (pouze v nejvyšší verzi). Tabulka 2.2: Advanced PDF Password Recovery — verze programu Verze Standard Professional Enterprise

Distribuovatelnost pouze ručně úpravou konfiguračního souboru pouze ručně úpravou konfiguračního souboru pouze ručně úpravou konfiguračního souboru

CPU

GPU

Cena

NE

NE

e49

ANO

ANO

e99

ANO

ANO

e399

Program bohužel nelze přímo spustit distribuovaně na více strojích, podporuje ale uložení aktuálního stavu. Lze tak upravit příslušný konfigurační soubor a spustit program na jiném stroji s jinou částí stavového prostoru. Nejnižší verze nabízí pouze odstranění omezení z PDF 1 Jde pravděpodobně o tzv. rainbow tabulky, které obsahují předvypočítaná data pro určitý algoritmus. Velikost se pohybuje v řádech GB. Následně ale dokáží významně urychlit další výpočty, které není třeba znovu provádět (nebo některé jejich části) a pouze se výsledek vyhledá v těchto tabulkách.

6

2.2. Dostupné aplikace pro prolamování hesel v PDF

souborů, prolomení hesel nepodporuje. Nejvyšší verze Enterprise zase oproti Professional nabízí „pouze“ předvypočítané tabulky pro urychlení výpočtu. K dispozici je zkušební verze zdarma s omezením délky hesla na maximálně 4 znaky.

2.2.3

PDF Password Cracker

Program [9] nabízí jak odstranění uživatelských omezení, tak prolomení obou druhů hesel. Implementuje jak útok hrubou silou, tak slovníkový útok. V poslední verzi pro PC platformu umožňuje distribuovaný výpočet na více strojích. Program dokáže nainstalovat vzdáleně na ostatní stroje klientský software, kterému pak předává data pro výpočet. Stroje jsou identifikovány svojí IP adresou. Lze si tak snadno vytvořit vlastní výpočetní cluster i v rámci internetu. Výpočet na každém stroji je paralelizován podle počtu dostupných CPU jader. Akceleraci pomocí GPU program bohužel nenabízí. Tabulka 2.3: PDF Password Cracker — verze programu Verze PC Mac

2.2.4

Distribuovatelnost je distribuovatelný na PC strojích nelze spouštět distribuovaně

CPU

GPU

Cena

ANO

NE

e29.95

ANO

NE

e29.95

PDFCrack

Open source nástroj určený pro linuxové operační systémy nabízí jak slovníkový útok, tak útok hrubou silou na oba druhy hesel. Jde o jednoduchou utilitu pro příkazový řádek, jejíž vývoj v současné době už pravděpodobně nepokračuje (poslední verze je z roku 2008). Program neumožňuje paralelizovat výpočet na více CPU jádrech, stejně tak nepodporuje ani GPU akceleraci. Umí ale ukládat stav hledání do souboru, lze tak výpočet distribuovat alespoň takto — úpravou uloženého stavu a spuštěním ve více procesech na jednom nebo více strojích. Na svých stránkách [10] autor zmiňuje, že pokud je známo uživatelské heslo, lze tím urychlit prolomení hesla vlastníka. Bohužel ale bez bližších podrobností.

2.2.5

Shrnutí

Trh nabízí množství programů pro prolomení hesel v PDF souborech. Obvykle tyto programy nabízí i další možnosti, jak obejít ochranu PDF souborů — za určitých podmínek dokáží soubor dešifrovat i bez nutnosti prolomení hesla, a to útokem na použitou šifrovací funkci s malou délkou klíče. Až na výjimky jsou k dispozici i zkušební verze zdarma, které mají ale podstatná omezení, například na maximální délku hesla. Jediný open source program bohužel nenabízí možnost spouštění na clusterech a prolamování provádí pouze na CPU. Na trhu tedy chybí zdarma dostupný program, který by k prolamování využíval jak CPU jádra, tak výpočetní výkon grafických karet a který by bylo zároveň možno provozovat na výpočetních clusterech. Takovýto program by měl být výsledkem této diplomové práce.

7

2. Analýza

2.3

CUDA

CUDA [2] je hardwarová a softwarová architektura, sloužící pro snadné provádění obecných výpočtů na procesorech grafických karet. Autorem je společnost NVIDIA Corporation (dále jen NVIDIA), a proto je CUDA podporována pouze jejími grafickými kartami. Vedle této technologie existují ještě další, jako např. OpenCL, což je průmyslový standard pro paralelní programování a je podporován jak grafickými kartami (a to od obou nejvýznamnějších výrobců — NVIDIA a Advanced Micro Devices, Inc., dále jen AMD), tak moderními procesory s podporou instrukcí SSE3 (Streaming SIMD Extensions, rev. 3), aj. CUDA nabízí rozšíření pro programovací jazyk C/C++ (a další), které usnadňují implementaci obecných výpočtů na grafické kartě. Protože výpočty na GPU probíhají v rámci paměti umístěné na grafické kartě, poskytuje CUDA funkce pro kopírování dat mezi pamětí počítače a pamětí grafické karty. Pamětí na grafické kartě je několik druhů, liší se svým umístěním, možností využití, velikostí a především přístupovými dobami. Pro snazší pochopení, k čemu který druh paměti slouží je třeba nejprve popsat architekturu samotného procesoru GPU.

Obrázek 2.3: Porovnání klasického a grafického procesoru [11]

Na obrázku 2.3 je porovnání architektury klasického a grafického procesoru. CPU procesor sestává z několika (řádově jednotek až desítek) jader se společnou cache pamětí (případně má každé jádro vlastní cache nízké úrovně) a společnou globální operační pamětí. GPU procesor naopak sestává obyčejně z několika multiprocesorů2 , z nichž každý obsahuje desítky jader a je schopný zpracovávat stovky vláken najednou. Jedná se tak o SIMT (Single Instruction, Multiple Threads) architekturu, kdy cílem je, aby každé vlákno zpracovalo jeden nebo několik málo výsledků z dat, která jsou navzájem nezávislá. Soubor právě aktivních vláken na jednom multiprocesoru se nazývá „warp“, přičemž v jednom warpu má každé vlákno vlastní čítač instrukcí a je tak možné, aby různá vlákna větvila svůj kód nezávisle na ostatních na základě svých dat. Z pohledu programátora jsou pak vlákna organizována do bloků a bloky vláken do mřížky bloků. Velikost bloku — tedy počet vláken v něm — určuje programátor, stejně jako počet bloků — tedy velikost mřížky. CUDA umožňuje adresovat jednotlivé bloky ve více dimenzích, velikost je pak dána součinem těchto dimenzí. Tím je usnadněno adresování speciálně organizovaných dat, typicky například matice. Počet paralelně zpracovávaných bloků na GPU 2

8

Někdy také označovány jako SM - streaming procesory.

2.3. CUDA

Obrázek 2.4: Možné způsoby organizace bloků vláken na GPU [11]

je pak určen schopnostmi daného grafického procesoru. Pokud je bloků více, než procesor zvládne zpracovat najednou, pak ostatní bloky čekají až se dopočítají aktuální bloky na procesoru. Je tak usnadněno škálování algoritmu do budoucna — při příchodu nového grafického procesoru se zvýší počet paralelně zpracovávaných bloků a tím se adekvátně zrychlí výpočet bez nutnosti jakýchkoliv změn v kódu, viz obrázek 2.4. Tabulka 2.4: Rozdělení pamětí na grafické kartě Typ

Umístění

Operace

Registry Lokální

na GPU mimo GPU

R/W R/W

Sdílená

na GPU

R/W

Globální

mimo GPU

R/W

Konstantní

mimo GPU

R

Přístup jedno vlákno jedno vlákno vlákna jednoho bloku všechna vlákna + host (CPU) všechna vlákna + host (CPU)

Přístupová doba nejnižší vysoká velmi nízká vysoká nízkávysoká

S organizací vláken do bloků a jednotlivých bloků do mřížek souvisí také organizace dostupných pamětí. V tabulce 2.4 jsou přehledně popsány jednotlivé typy pamětí, spolu

9

2. Analýza

se základními parametry. Konkrétní hodnoty přístupových dob závisí na konkrétním modelu grafické karty. Uvedné hodnoty jsou tedy orientační a slouží spíše pro vzájemné porovnání přístupových dob jednotlivých typů pamětí. Registry jsou umístěny na čipu a mají nejnižší přístupovou dobu. Pokud se při překladu nepovede umístit proměnnou do registru, neboť počet registrů je omezen (tzn. počet dostupných registrů pro vláknu je určen počtem registrů daného procesoru a velikostí bloku), umístí se proměnná do lokální paměti. Lokální paměť je ale vyhrazená část z globální DRAM paměti, proto je její přístupová doba o mnoho vyšší. Do globální paměti mají přístup všechna vlákna všech bloků. Globální paměť má sice vysokou kapacitu, ale také vysokou přístupovou dobu. Konstantní paměť je také vyhrazená část z globální paměti, přístup k ni je ale ukládán do zvláštní cache paměti. Pokud pak vlákna přistupují k jedná hodnotě z konstantní paměti, tato hodnota se uloží do cache a přístup k této cache je už velmi rychlý. Proto se přístupová doba konstantní paměti mění v závislosti na datech z ní načítaných. Vlákna na GPU mohou z této paměti pouze číst, zapisovat do ní může jen CPU. Sdílená paměť je umístěná na čipu a každý procesor má k dispozici vlastní, proto je přístup k ní rozdělen podle bloků — tedy vlákna z jednoho bloku přistupují do jedné sdílené paměti, ale nemohou přistup do sdílené paměti vláken jiného bloku. Přístup k této paměti je řádově rychlejší, než do globální, její velikost je ale omezená na desítky kilobytů. Navíc existují techniky pro zrychlení přístupu jak ke sdílené, tak ke globální paměti, budou popsány dále v sekci 3.2.4.3.

2.3.1

Jazyková rozšíření

Jak bylo zmíněno, CUDA poskytuje rozšíření programovacích jazyků o vybraná klíčová slova a přidává další vlastní funkce. Aby bylo možné takový kód přeložit, CUDA poskytuje vlastní překladač — nvcc. Mezi nejdůležitější patří klíčová slova __global__ a __device__: • __global__ – Vkládá se před deklaraci funkce a označuje funkci jako tzv. kernel. Kernel je funkce volaná z běžného kódu aplikace, která bude ale spuštěna na grafickém procesoru. Z pohledu aplikace jde tedy o jakýsi vstupní bod pro výpočet na grafické kartě. Kód kernelu bude vykonáván všemi vlákny tzn. — jak již bylo zmíněno — jde o model SIMT. Protože je nutné nějakým způsobem definovat v kolika vláknech výpočet poběží, má volání kernelu zvláštní syntaxi: kernel<<>>(par1, par2, ...) ∗ kernel — název funkce definované jako kernel ∗ grid — velikost mřížky, tedy počet bloků. Počet bloků lze zadat ve třech rozměrech, proměnná je typu dim3 a jde vlastně o strukturu se složkami x, y a z. Ve skutečnosti jde ale pouze o usnadnění způsobu adresace jednotlivých bloků pro programátora. Pro procesor je důležitý pouze celkový počet bloků, který se získá vynásobením jednotlivých složek. Na dobu výpočtu tedy nemá vliv, pokud se rozměr zadá například jako {10, 1, 1}, nebo {5, 2, 1}.

10

2.3. CUDA

∗ block — velikost bloku, tedy počet vláken v jednom bloku. Proměnná je opět typu dim3 a platí pro ni totéž, co pro grid. ∗ reqSharedMem — velikost požadované sdílené paměti. Sdílenou paměť lze alokovat buď dynamicky za běhu programu, nebo staticky před spuštěním kernelu. Pokud už je před spuštěním jasné, že bude potřeba určitá velikost paměti, lze ji takto zadat. Je třeba myslet na to, že jde o velikost sdílené paměti pro jeden blok — je to tedy parametr závislý na velikosti bloku. Pokus o alokaci více sdílené paměti, než je fyzicky k dispozici, skončí chybou. V rámci kernelu jsou pak definovany proměnné gridDim, blockIdx, blockDim a threadIdx. Všechny jsou typu dim3 a slouží pro jednoznačnou identifikaci konkrétního vlákna přes všechny multiprocesory. • __device__ – Pokud je potřeba z kernelu volat jiné funkce, je nutné překladači naznačit, že daná funkce bude také spouštěna na grafické kartě. K tomu slouží toto klíčové slovo, kterým se také uvozuje deklarace funkce. Pro deklaraci funkce jako inline 3 , respektive zakázání4 takové deklarace, slouží klíčová slova __forceinline__ a __noinline__. Další důležitá klíčová slova jsou uváděna při deklaraci proměnných a určují typ paměti, kde mají být tyto proměnné umístěny. Pokud není uvedeno žádné, předpokládá se umístění proměnné v lokální paměti vlákna: • __constant__ — deklaruje umístění proměnné v konstantní paměti. Do takové proměnné může zapisovat pouze hostitelský kód. Kód spouštěný na grafické kartě má k takové proměnné přístup pouze ke čtení. • __shared__ — deklaruje umístění proměnné ve sdílené paměti. Ta může být alokována staticky v okamžiku spuštění kernelu, jak bylo popsáno výše, případně dynamicky za běhu programu. • register — označuje proměnnou jako vhodnou pro umístění do registru. Finální umístění proměnné ale určuje vždy překladač. Pokud nebude mít dostatek registrů, proměnná může zůstat v lokální paměti. Jazykových rozšíření poskytuje CUDA samozřejmě více, popsána byla pouze některá pro lepší pochopení celé architektury a způsobu programování pro ni. 3

Inline funkce je taková, jejíž volání bude při překladu nahrazeno kódem funkce. Definovat funkci jako inline je vhodné u malých funkcí na několik řádků, které se často volají, například v cyklech. Odpadne tak režie s voláním funkce. Na druhou stranu výsledný přeložený soubor bude větší. Proto se nedoporučuje deklarovat jako inline větší funkce, které jsou volány na více místech v programu. 4 Podle CUDA revize se mění výchozí přístup překladače. Pro revize 1.x jsou všechny funkce brány jako inline, pro revize 2.x a vyšší se rozhoduje překladač během překladu, zda danou funkci označí jako inline.

11

2. Analýza

2.4

GPULab — školní cluster

Fakulta má k dispozici výpočetní cluster osazený stroji s výkonnými vícejádrovými procesory a grafickými kartami podporujícími CUDA architekturu. Následuje zevrubný popis clusteru spolu s dostupnými softwarovými prostředky.

2.4.1

HW konfigurace uzlů

Implementace, testování a závěrečné měření bude probíhat na malém školním clusteru o pěti uzlech. Jednotlivé uzly jsou pojmenovány písmeny řecké abecedy. Uzel alpha má v clusteru výsadní postavení. Jako jediný je dostupný z vnější sítě, zbylé stroje jsou pak dostupné pouze z něj a samozřejmě navzájem mezi sebou. Propojeny jsou pomocí klasické sítě Ethernet, a to přes centrální switch. Fyzická topologie je tedy hvězda, jak je vidět z obrázku 2.5. beta

gamma

delta

epsilon

internet switch

alpha

Obrázek 2.5: Topologie školního clusteru Hardwarovou konfiguraci jednotlivých uzlů shrnuje tabulka 2.5. Tabulka 2.5: HW konfigurace školního clusteru

12

Uzel

Paměť

alpha

4 GB

beta

4 GB

gamma

4 GB

delta

3.5 GB

epsilon

24 GB

Procesor frekvence jader Intel i5 760 2.8 GHz 4 Intel i5 760 2.8 GHz 4 Intel i5 760 2.8 GHz 4 Intel Core2 Quad Q8200 2.33 GHz 4 Intel i5 950 3.07 GHz 8

Grafická karta nVidia GeForce GTX480 nVidia GeForce GTX480 nVidia GeForce GTX470 nVidia GeForce GTX470 nVidia GeForce GTX590

2.4. GPULab — školní cluster

Všechny instalované grafické karty mají architekturu Fermi [21]. Fermi je nejnovější architektura grafických čipů, která ještě více než kdy předtím usnadňuje spouštění obecných výpočtů na grafických kartách. Oproti předchozí architektuře disponuje větší sdílenou pamětí, přidává vyrovnávací cache paměti L1 a L2, přidává podporu ECC u pamětí5 , obsahuje přesnější a rychlejší aritmetické jednotky, atd. V tabulce 2.6 jsou uvedeny základní rozdíly mezi instalovanými kartami. Tabulka 2.6: Grafické karty v školním clusteru

Frekvence GPU Globální paměť CUDA verze Maximální počet aktivních vláken Lokální paměť (pro vlákno) Sdílená paměť (pro blok) Počet registrů (pro blok)

2.4.2

GTX 480 1.4 GHz 1.5 GB

GTX470 1.2 GHz 1.2 GB 2.0

1536

GTX590 1.2 GHz 3 GB 3072

512 KB 48 KB 32768

SW prostředí

Na strojích je nainstalován linuxový operační systém Ubuntu 11.04 (kódové označení Natty Narwhal) s jádrem ve verzi 2.6.38. Jak existující program z bakalářské práce, tak program psaný v rámci diplomové práce jsou oba určeny pro linuxový operační systém. Jediný požadavek je na implementaci vláken a semaforů podle POSIX6 standardu, což je v tomto případě splněno. 2.4.2.1

Meziprocesní komunikace

Na všech strojích je nainstalována knihovna OpenMPI ve verzi 1.5.4, která se stará o MPI7 komunikaci. Knihovna nabízí množství funkcí pro komunikaci a synchronizaci procesů pro celou řadu programovacích jazyků. Komunikace je založena na posílání zpráv mezi procesy (odtud název knihovny), přičemž odesílání a příjem může být jak synchronní, tak asynchronní a 5

Error Checking and Correcting — technologie umožňující zjistit a opravit chybu. Čím větší je kapacita paměti, tím je pravděpodobnější riziko, že dojde náhodně ke změně nějakého bitu. Technologie ECC pomocí použití nějakého kódu s redundancí (tedy přidáním několika kontrolních bitů) umožňuje takové chyby zjistit a opravit a zabránit tak např. provedení nesprávného kódu, apod. 6 Portable Operating System Interface — standard definující rozhraní a způsob systémových volání, knihovnách funkcí, apod. 7 Message Passing Interface — ve skutečnosti jde o standard, podle něhož jsou napsány jednotlivé implementace. Vedle OpenMPI tak existuje ještě například MPICH, LAM/MPI, WMPI, aj.

13

2. Analýza

zprávy mohou být určeny buď pro jeden konkrétní uzel, nebo např. pro všechny uzly v rámci určené skupiny (broadcast). K dispozici jsou také funkce pro měření času.

2.4.2.2

Šifrovací algoritmy

Největší část výpočtu tráví algoritmy výpočtem dvou šifrovacích funkcí, a sice MD5 (viz příloha A.1) a RC4 (viz příloha A.2). Hlavním cílem této práce je výpočet optimalizovat, proto má smysl zaměřit se na implementace těchto dvou funkcí a najít co možná nejrychlejší. V existujícím řešení z bakalářské práce se používají funkce z balíčku OpenSSL. Balíček poskytuje mimojiné množství kryptografických funkcí, MD5 a RC4 nevyjímaje. Bez pochyby jde o odladěnou knihovnu, co se týče bezpečnosti, tak i výkonu, vývoj byl zahájen již roku 1998. Přesto ale nemusí jít o optimální implementaci. Společnost Intel nabízí soubor C/C++ knihoven, které se nazývají Intel Integrated Performance Primitives (dále jen IPP [13]) a jsou přímo určené pro běh na moderních procesorech. Nabízí optimalizované algoritmy pro různé oblasti, jako je práce s grafikou, komprimace a zpracování dat a v neposlední řadě také kryptografii. Obsahuje implementaci obou používaných funkcí. RC4 se zde z licenčních důvodů nazývá ARCFOUR. Mohlo by být tedy zajímavé v kódu programu nahradit volání obou šifrovacích funkcí jejich implementacemi z balíčku IPP a porovnat jejich výkon s původními z balíčku OpenSSL. Licence pro použití IPP knihoven dovoluje vyzkoušení zdarma, pro reálné nasazení je však placená.

2.5

Vyvažování zátěže

Jedním ze základních požadavků na výkonný paralelizovaný program by mělo být i vyvažování zátěže. Výhodné je hned z několika různých důvodů. Homogenita prostředí, kde program poběží není vždy zaručena. Pokud nebudou brány v potaz profesionální clustery složené z mnoha identických serverů, mnohem běžnější jsou clustery, kdy jednotlivé uzly tvoří stroje s různou hardwarovou konfigurací. Může jít například o starší vyřazené stroje, které ale při zapojení do clusteru mohou ještě dobře posloužit. V takových clusterech jsou potom jednotlivé uzly různě výkonné a výpočet tudíž na každém z nich poběží jinak dlouho. V případě, že program předpokládá homogenní prostředí, rozdělí svůj stavový prostor na tolik částí, kolik je k dispozici uzlů. Výkonnější stroje skončí výpočet dané velikosti podprostoru dříve, než pomalejší a zbytek času jsou nevyužity. I v případě homogenního prostředí ale může nastat situace, kdy přijde vyvažování zátěže vhod. Na některých strojích mohou být spuštěny ještě jiné úlohy a tyto stroje potom musejí přepínat mezi více výpočty. Jejich výkon (z pohledu naší aplikace) pak samozřejmě poklesne a v tu chvíli se stávají pomalejšími uzly. Celková doba výpočtu je tak dána rychlostí nejpomalejšího uzlu v clusteru8 . Nehledě na skutečnost, že během výpočtu může dojít například k výpadku některého z uzlů — jemu přidělená část stavového prostoru pak zůstane nespočítána. Vyvažování zátěže může být statické, nebo dynamické. 8 A tudíž zůstane potenciál takového clusteru nevyužit — výpočet by trval stejně dlouho, jako kdyby byl spuštěn na celkově méně výkonném, ale homogenním clusteru, který by byl složen z uzlů o stejné konfiguraci jako nejpomalejší uzel.

14

2.5. Vyvažování zátěže

2.5.1

Statické vyvažování

Při statickém vyvažování je nejprve potřeba zjistit výkon jednotlivých uzlů (což je možné udělat buďto algoritmicky — jednoduchým benchmarkem spuštěným na všech uzlech, nebo ručně — předem danou konfigurací, kterou si program načte) a stavový prostor se potom rozdělí poměrně k zjištěným výkonům. Rychlejší uzel tedy dostane větší část stavového prostoru, analogicky pomalejší uzel dostane část menší. Tento přístup si ale neporadí se změnou výkonu uzlů při jejich zatížení jinými procesy, stejně jako si neporadí s výpadky.

2.5.2

Dynamické vyvažování

Dynamické vyvažování bere ohled na výkon, respektive aktuální vytížení jednotlivých uzlů clusteru. V závislosti na zvoleném přístupu se liší i kvalita vyvažování. Kvalitou je zdě míněna flexibilita, s jakou se program adaptuje na aktuální podmínky — tedy jak rychle se přizpůsobí změně výkonu nějakého z uzlů. Způsobů, jak implementovat dynamické vyvažování je samozřejmě více, následuje popis několika možných:

1. Nejjednodušším způsobem je rozdělit stavový prostor na více menších částí, které se pak postupně vydávají uzlům. Když uzel spočítá přidělenou část, řekne si o další, pokud je ještě nějaká k dispozici. Počet částí ovlivňuje efektivitu využití clusteru. Čím více menších částí, tím efektivněji jsou jednotlivé uzly využity. S počtem částí ale zároveň roste komunikační zátěž sítě a tedy doba, kdy uzel nepočítá, ale čeká na přidělení další části stavového prostoru. Počet částí je tedy třeba nastavit experimentálně. 2. Druhý způsob je pouze malým vylepšením předchozího, bere ale v úvahu výkon uzlů clusteru. Počet částí se nestanoví experimentálně, ale na začátku se provede benchmark všech uzlů (nebo se jejich výkon určí pomocí konfigurace). Velikost jedné části by pak měla odpovídat rychlosti nejvýkonnějšího uzlu. Tedy například úměrně tomu, kolik je schopný nejrychlejší uzel spočítat za jednotku času. Nicméně i v tomto případě je vhodné počet částí ještě vynásobit nějakou konstantou (a tím zmenšit velikost jedné části), pro lepší adaptaci v případě změny výkonu nějakého z uzlů. Pokud by velikost jedné části odpovídala rychlosti nejpomalejšího uzlu (tzn. jedna část by byla v tomto případě menší a celkový počet částí větší), vzrostla by neúměrně komunikační zátěž na síti. Nejvýkonnější uzel by si neustále říkal o další části stavového prostoru a plýtvalo by se tak jeho výkonem. Cílem by mělo být maximální využití nejvýkonnějších uzlů v clusteru. 3. Nejkomplikovanější, ale nejefektivnější způsob vyvažování je takový, kdy se velikost přidělovaného stavového podprostoru určuje podle aktuálního výkonu daného uzlu. V takovém případě se výpočet automaticky přizpůsobuje aktuálnímu vytížení celého clusteru. Pokud začne být nějaký uzel vytížen jinými procesy, bude dostávat menší části stavového prostoru a jakmile jeho vytíženost klesne, začne dostávat opět větší části. Celkově tak budou všechny uzly počítat jim přidělené části podobně dlouho a dostupný výkon bude efektivně využit.

15

2. Analýza

2.6

Shrnutí

Aplikací pro prolamování hesel PDF souborů je na trhu dostatek. K dispozici jsou jak komerční, tak nekomerční. Až na výjimky se jednotlivé programy svými funkcemi mnoho neliší. Všechny umožňují zjištění obou typů hesel a přidávají další možnosti, jak obejít zabezpečení PDF souborů. Čím se ale liší významně, jsou možnosti paralelizace, a tudíž výsledným výkonem. Bohužel žádný z nich v bezplatné verzi nepodporuje přímou distribuovatelnost na clusterech. Nepřímo to některé programy umožňují, a sice pomocí uložení stavu hledání do souboru, úpravou tohoto souboru a spuštění nové instance programu s upraveným souborem. Ručně takto distribuovat výpočet na desítky a stovky uzlů by bylo ale velmi zdlouhavé, nehledě na nutnost ověřovat na všech uzlech, zda nějaká instance programu už náhodou heslo nenašla. Kromě toho jde o plýtvání výkonu, neboť jednotlivé instance ví pouze odkud mají začít, ale už neví, kdy mají skončit — ukončování takového výpočtu bude také velmi složité. Pouze jediný komerční nástroj — GuaPDF 2.2.1 — podporuje jak paralelní výpočet na GPU a CPU, tak i umožňuje výpočet distribuovat na clusteru. S omezením na 20 uzlů stojí tato verze e39, bez omezení potom e150. Oproti existujícímu řešení z bakalářské práce, které distribuje výpočet pouze na jednotlivé uzly — a na jednotlivých uzlech běží výpočet pouze sériově v jednom vlákně — přidává CPU a GPU paralelizaci. Má tedy smysl zabývat se optimalizací řešení z bakalářské práce a vyvinout nástroj, který bude paralelizovat výpočet na všech dostupných úrovních — CPU, GPU a již existující podpora clusterů. Z analýzy kódu stávající aplikace vyplynulo, že bude třeba jej od základu přepsat. Implementovaný parser dat z PDF souboru není spolehlivý, neboť vnitřní formát PDF souborů z různých zdrojů se může podstatně lišit9 . Bude nutné buď najít knihovnu s podporou parsování šifrovaných PDF souborů, případně napsat vlastní parser přesně podle specifikace [3]. Použitelné jsou implementované algoritmy pro šifrování hesla a načítání vstupních parametrů. Především bude ale třeba celý kód rozdělit do více tříd a funkcí, a tím usnadnit nejen orientaci v kódu, ale také jeho udržovatelnost. K vývoji optimalizované verze existuje dostatečně výkonné prostředí, které navíc není homogenní — skládá se z uzlů s různými konfiguracemi. To je ideální podmínka pro využití a otestování jednoho z požadavku zadání, a sice vyvažování zátěže. Grafické karty, které jsou ve školním clusteru instalovány jsou poměrně moderní a díky své architektuře Fermi velmi dobře připraveny pro obecné výpočty. Výsledný program paralelizovaný na GPU by tak měl podávat řádově lepší výsledky, než existující řešení.

9 Implementovaný PDF parser z bakalářské práce funguje na podobném principu jako regulární výrazy. Nepokrývá ale zdaleka všechny varianty, které se v souborech z různých zdrojů mohou objevit. V takovém případě pak program buď získá nesprávná data, nebo při parsování souboru selže.

16

Kapitola

Návrh Tato kapitola sleduje návrh implementace nové aplikace. Nabízí popis jak hrubé architektury, tak nově navrženého komunikačního modelu s ohledem na požadované vyvažování zátěže. V některých bodech je připraveno více možných variant, z nichž bude při následné implementaci vybrána ta nejvhodnější. Návrh aplikace začne nejprve návrhem modelu z hlediska celého clusteru. Z navrženého komunikačního modelu pak vyplynou některé požadavky, které bude potřeba vzít v úvahu při návrhu architektury aplikace.

3.1

Komunikační model

Komunikační model zůstane stejně jako v původním řešení typu Master-Slave. Master (alpha)

Slave (beta)

Slave (gamma)

Slave (delta)

Slave (epsilon)

Obrázek 3.1: Master-Slave model Tedy proces spuštěný na hlavním uzlu clusteru bude Master a bude mít na starosti interakci s uživatelem. To mimo jiné zahrnuje analýzu vstupních dat — zadaných parametrů a PDF souboru. Hlavním důvodem pro tento model je jednak jeho jednoduchost, neboť centrální řízení je vždy jednodušší, než distribuované, ale také je zbytečné distribuovat PDF soubor na všechny uzly. Hlavní uzel přiděluje práci všem ostatním uzlům. Podřízené (tedy

17

3

3. Návrh

Slave) uzly pak komunikují pouze s Master uzlem, mezi sebou nikoliv. Virtuální topologii takového modelu vykresluje obrázek 3.1.

3.2

Architektura aplikace

Na všech uzlech, včetně hlavního, poběží identický kód. Hlavní uzel ale ještě navíc musí obstarávat distribuci práce ostatním uzlům a řízení celého výpočtu. Na jednotlivých uzlech pak bude část, která bude mít na starosti vyžádání práce (tzn. část stavového prostoru) od hlavního uzlu a předání práce výpočetní části. Ta se bude skládat z části pro CPU — tedy sady výpočetních vláken a řízení těchto vláken — a z části pro GPU — opět nějaké řízení a sada vláken na grafické kartě. Popsaná struktura je znázorněna na obrázku 3.2

komunikační vlákno

komunikace s hlavním uzlem

vstup aplikace (parametry, PDF soubor)

řídící vlákno CPU

pool výpočetních vláken na CPU

řídící vlákno GPU

pool výpočetních vláken na GPU

jádro aplikace

hlavní komunikační vlákno (pouze hlavní uzel)

komunikace s podřízenými uzly

Obrázek 3.2: Hrubá architektura aplikace

3.2.1

Vyvažování zátěže

Co se týká vyvažování zátěže, z analýzy vyplynulo, že statické vyvažování prakticky nemá smysl. Statické vyvažování ani neodpovídá požadavku ze zadání — to požaduje implementaci aktivního vyvažování zátěže. Rozhodování tedy bude probíhat mezi různými způsoby dynamického vyvažování. Nejjednodušší na implementaci je první varianta 2.5.2, kdy se stavový prostor rozdělí na více částí, než je k dispozici uzlů — pravděpodobně na nějaký násobek počtu uzlů. Z popsaných způsobů je ale nejméně efektivní a nebere v úvahu výkon jednotlivých uzlů. Zbylé dvě varianty dynamického vyvažování předpokládají implementaci nějakého benchmarku výkonu uzlů. Tedy alespoň pokud u druhé varianty nebudeme brát v úvahu zadání výkonu uzlů pomocí nějaké konfigurace. To může být pro velké clustery velmi nepohodlné a kromě toho to předpokládá také nějaký benchmark uzlů. Ten sice může být libovolný, tzn. nemusí měřit výkon při prolamování hesel, pak ale také nemusí podávat relevantní výsledky.

18

3.2. Architektura aplikace

Pokud už se tedy bude implementovat benchmark, stálo by za to implementovat nejkomplexnější metodu dynamického vyvažování. To s sebou přináší také komplikovanější dělení stavového prostoru. Ten nebude možné rozdělit na začátku podle nějakých parametrů, ale bude se rozdělovat postupně, jak si budou jednotlivé uzly říkat o práci.

3.2.2

Parsování PDF souborů

Parser PDF souborů implementovaný v řešení z bakalářské práce je velmi primitivní. Přestože předkládané soubory odpovídají specifikaci [3] a běžné prohlížeče PDF souborů nemají problém s otevřením těchto souborů, parser z bakalářské práce na nich selhává. Funguje jako jednoduchý lexikální analyzér, ale předpokládá přítomnost pouze několika konkrétních posloupností bytů. Pokud se předložený PDF soubor liší například pouze nepřítomností konce řádku nebo mezery tam, kde ji parser z bakalářské práce očekává, výsledkem jsou nevalidní hodnoty, které parser načítá. To vede samozřejmě k nevalidním výpočtům a takové prolamování nemůže nikdy skončit úspěchem. Parser PDF souborů tak bude třeba implementovat úplně jinak. Existují dva způsoby. Buďto existuje už hotová knihovna, kterou bude možno využít pro načtení všech potřebných hodnot z PDF souboru, nebo bude potřeba celý parser implementovat tak, aby soubor načítal dle specifikace. Využití existující knihovny je samozřejmě mnohem jednodušší varianta. Důležitým požadavkem ale je, aby knihovna umožnila přistupovat k hodnotám, které je potřeba pro prolamování hesel načíst. Jde zejména o hodnoty z tzv. „Encryption dictionary“, viz [3], [1]. Dalším požadavkem na knihovnu je, aby hodnoty zpřístupnila i v případě, že nebylo zadáno heslo pro otevření souboru. Implementace parseru vlastními silami by byl o poznání náročnější úkol. Bylo by potřeba načíst celou strukturu PDF souboru, zjistit, kde se nachází konkrétní objekty a z nich načíst potřebné hodnoty. Je ale velmi pravděpodobné, že existují knihovny, které umí PDF soubory parsovat. A tak pokud by nebylo možné využít přímo tyto knihovny, určitě poslouží jako vzor pro vlastní implementaci parseru. Samozřejmě v případě, že budou k dispozici zdrojové kódy těchto knihoven.

3.2.3

Ukládání stavu do souboru

Upravit bude třeba i implementaci ukládání aktuálního stavu hledání do souboru při předčasném ukončení běhu programu. V existujícím řešení z bakalářské práce se v případě přerušení uloží nejprve parametry daného hledání, tedy typ a délka hledaných hesel a použitá abeceda. Následně se ukládá stav hledání každého uzlu clusteru. Kód, který má toto celé na starosti je poměrně komplikovaný. Signál o přerušení je třeba předat z hlavního uzlu všem podřízeným a ty musí přerušit výpočet a odeslat informaci o své aktuální pozici v jejich části stavového prostoru. Až pak se může běh programu na celém clusteru zastavit. V případě obnovení výpočtu z uloženého souboru je zase třeba všem uzlům předat spolu s informací o jejich části stavového prostoru také informaci o tom, odkud mají začít výpočet. Z principu to ani jinak nejde, stavový prostor je rozdělen rovnoměrně mezi všechny uzly, a tak je opravdu potřeba ukládat pozici každého z nich. Ale v případě, že je nutné rychle ukončit výpočet například z důvodu výpadku elektřiny (a tudíž omezené doby běhu strojů na záložní zdroje), může se stát, že informace z některého uzlu nepřijde včas a danou část stavového prostoru bude potřeba prohledat znovu celou (případně odhadem určit přibližnou pozici).

19

3. Návrh

Díky tomu, že nový program bude implementovat nějaký způsob dynamického vyvažování, bude možné vyřešit ukládání do souboru jiným způsobem. Hlavní uzel je správcem celého stavového prostoru, má tak přehled o tom, který uzel počítá jakou jeho část. Ukládání stavu do souboru by tak bylo možné zjednodušit — ukládat pouze informace, které má k dispozici hlavní uzel a nezatěžovat tím uzly podřízené. Těm by se už jen poslalo oznámení o ukončení.

3.2.4

Návrh optimalizací

V této části jsou nastíněny varianty optimalizací, které je možné ve stávajícím kódu provést. Popisuje, jak je možné lokalizovat neefektivní části kódu a jaké nástroje jsou pro to vhodné. V případě nového kódu, a to zejména pro GPU část, pak zmiňuje na co je třeba dbát, aby výsledný kód běžel na grafické kartě optimálně a efektivně využíval dostupná jádra. 3.2.4.1

Profilování

Profilování je způsob, jakým lze zjistit délku trvání jednotlivých částí programu a určit, kde (tzn. na kterém místě v kódu) program tráví nejvíce svého času10 . Na tyto části kódu je potom potřeba se zaměřit, zjistit příčinu jejich časové náročnosti a upravit je. Po úpravě se program znovu profiluje, zjišťuje se, zda byla úprava úspěšná a v případě že ano, pokračuje se analogicky s další nejnáročnější částí programu. Jde tedy o iterativné proces, v každé iteraci proběhne úprava nejpomalejší části kódu tak, aby daná část běžela na procesoru rychleji. Při všech úpravách je třeba dbát na to, aby se nezměnila sémantika kódu. Proces profilování končí ve chvíli, kdy už program běží dostatečně rychle, žádné další úpravy kódu už nejsou možné, případně nepřinášejí dostatečné zrychlení s ohledem na náročnost úprav (a s tím většinou související určité znepřehlednění kódu). start_thread 83 949 190

83 949 190 (1x)

Thread_t::entryPoint(void*) 83 949 190

83 949 190 (1x)

CpuWorkerThread_t::work() 83 949 190

46 259 347 (1 000 001x)

BruteForceGenerator_t::actual(... 46 259 347

30 681 304 (1 000 001x)

BruteForceGenerator_t::next() 30 681 304

Obrázek 3.3: Příklad grafu volání funkce 10 Oblíbené Paretovo pravidlo, nebo Paretův princip tvrdí, že 80% času tráví program ve 20% kódu — odtud se také někdy označuje pravidlo 80/20. Toto pravidlo je obecné a dá se aplikovat na spoustu oblastí lidského zkoumání. Neplatí samozřejmě vždy, ale jako hrubý odhad, a to i z praxe, víceméně funguje.

20

3.2. Architektura aplikace

Metod, jak profilovat je mnoho. Je například možné program spouštět v debuggeru, pravidelně přerušovat jeho běh a třeba výpisem obsahu zásobníku zaznamenávat, na jakém místě v kódu se právě nachází. Mnohem jednodušší je ale použít nějaký profilovací nástroj. Ověřeným nástrojem pro linuxový operační systém je program Valgrind, který bude použit i pro profilování výsledného kódu této práce. Valgrind je ve skutečnosti sada několika nástrojů. Obsahuje nástroj pro kontrolu práce s pamětí, nástroje pro profilování kódu, pro kontrolu práce s vlákny (tzn. např. detekce možných souběhů, apod.) a další. Valgrind, nehledě na použitý nástroj, vytvoří pro program virtuální prostředí, ve kterém pak spouští kód programu a je tak schopný analyzovat běh na úrovni těch nejnižších instrukcí. Díky tomu je běh v tomto prostředí několikrát pomalejší, než pokud by program běžel přímo na procesoru, podle použitého nástroje i 10x až 100x. Nástroj pro profilování kódu, který bude použit, se jmenuje callgrind. Po spuštění zaznamenává volání jednotlivých funkcí a ukládá je tzv. grafu volání, ze kterého je následně patrné, jak na sobě funkce závisí — tzn. kterými funkcemi je volaná daná funkce a naopak, které daná funkce volá. Příklad vizualizace takového grafu je možné vidět na obrázku 3.3. Callgrind kromě tohoto grafu zaznamenává také počet volání jednotlivých funkcí a počet provedených instrukcí. Posbíraná data uloží do textového souboru, který je sice možné analyzovat ručně, ale pouze u velmi malých a jednoduchých programů. U větších už je nutné použít jiné nástroje, které umějí data v souboru interpretovat do čitelné podoby, případně dokonce vizualizovat, jak již bylo ukázáno. Pro analýzu dat z Callgrindu existuje asi jediný použitelný vizualizátor, a to KCachegrind — původně linuxový program (podle písmene K na začátku určený pouze pro grafické prostředí KDE), následně portovaný i pro Windows. Z tohoto programu pochází i ukázka vizualizace na obrázku 3.3. Jak je vidět, u každé volané funkce je vidět počet jejího volání a doba v procentech, po kterou tato funkce byla vykonávána procesorem. KCachegrind umí interpretovat data buď lokálně — tedy jak dlouho trvala funkce vzhledem ke své volající funkci, ale také globálně — tedy jak dlouho trvala funkce v rámci celého běhu programu. Funkce lze navíc organizovat například s ohledem na zdrojový soubor, ve kterém jsou definovány, případně na binární objekt, kde jsou umístěny (tedy např. přeložená sdílená knihovna). Díky tomu se lze snadno zaměřit pouze na funkce profilovaného programu a separovat je od systémových volání. Je potřeba ještě zmínit, že proces profilování (a vůbec jakékoliv optimalizace) by měl přijít na řadu až po dokončené implementaci. Předčasná optimalizace vede často k nepřehlednému kódu a tím pádem zvyšuje riziko vzniku obtížně zjistitelných chyb. Nejenže pak naroste celkový čas o dobu strávenou optimalizací částí kódu během implementace, ale významně také o dobu strávenou laděním takového kódu. Nehledě na to, že během implementace se často stává, že se některé kusy kódu zahodí a nahradí jinými a veškeré optimalizace by tak přišly vniveč. 3.2.4.2

Šifrovací algoritmy

V rámci analýzy byly zmíněny IPP knihovny 2.4.2.2 obsahující algoritmy MD5 a RC4 optimalizované pro běh na moderních procesorech s využitím rozšíření instrukčních sad MMX, SSE, a dalších. Protože vývoj diplomové práce bude probíhat převážně na moderních procesorech od firmy Intel, má smysl se tímto balíčkem zabývat. Bude ale potřeba ověřit, zda je tato implementace šifrovacích funkcí výkonnější, než v současné době používané funkce

21

3. Návrh

z balíčku OpenSSL. Pro obě funkce se dají snadno sestavit všecny kombinace jejich použití v algoritmech šifrování hesel. Jinými slovy — jaké jsou možné délky vstupních dat a šifrovacího klíče v případě funkce RC4, v případě MD5 pouze velikost vstupních dat. Tyto scénaře použití se potom otestují s oběma implementacemi a vybere se výkonnější varianta. 3.2.4.3

CUDA optimalizace

V této sekci nejde ani tak o samotné optimalizace, ale spíš o to, jakým způsobem psát kód pro běh na GPU, aby běžel co nejrychleji a optimálně využíval grafický procesor. Co nejrychlejší běh na grafické kartě předpokládá dvě věci. Jednak správné nastavení počtu bloků a počtu vláken v rámci bloků, jednak správnou práci s různými druhy pamětí na grafické kartě. Obě věci spolu částečně souvisí. Od nastavení počtu vláken se odvíjí množství dostupných registrů a velikost sdílené paměti dostupná pro jednotlivá vlákna daného bloku. Snahou samozřejmě je mít co nejvyšší počet aktivních vláken na grafickém procesoru a zároveň využít všechny dostupné registry a sdílenou paměť. Pro určení správného počtu vláken je možné použít buď hrubou sílu, kdy se daný algoritmus spouští na zvyšujícím se počtu vláken a vybere se takové nastavení, které podalo nejlepší výsledky. Pro lepší odhad je ale možné využít speciální nástroj, který je k dispozici v rámci vývojářských nástrojů pro CUDA. Jde o tzv. „occupancy calculator“ [12] — soubor pro Microsoft Excel, který poskytuje množství vzorců pro výpočet různých parametrů. Stačí zadat několika základních hodnot, jako je dostupná verze CUDA architektury, zvolený počet vláken, počet alokovaných registrů a velikost potřebné sdílené paměti. Soubor pak dopočítá počet aktivních vláken, počet aktivních warpů, využití procesorů, atp. Potřebné hodnoty lze zjistit pomocí speciálního přepínače pro CUDA překladač — nvcc –ptxas-options=-v. Při překladu se pak na výstupu objeví počet alokovaných registrů a staticky alokované sdílené paměti. Neměné důležitá je práce s dostupnými typy pamětí na grafické kartě. Primárně je cílem co nejvíce proměnných alokovat do registrů, neboť přístup k nim je jednoznačně nejrychlejší. Konstantní hodnoty je potřeba alokovat v konstantní paměti, která je vybavena vyrovnávací pamětí a přístup k ní je tak také velmi rychlý. Hodnoty, ke kterým se často přistupuje a není možné je alokovat v registrech je pak vhodné umístit do sdílené paměti. Ideálním stavem je mít ve sdílené paměti vše, ale její velikost je velmi omezená. Samotná alokace hodnot ve sdílené paměti ale nestačí. Její přístupová doba je sice kratší, než u paměti globální, ale je potřeba ještě optimalizovat přístup jednotlivých vláken do této paměti. Procesor totiž umožňuje při dodržení určitých podmínek výrazně zrychlit přístup vláken do sdílené paměti. Procesor umožňuje přistupovat půlce vláken ve warpu (tedy půlce aktivních vláken na procesoru) přistoupit ke sdílené paměti zároveň, pokud: • všechna vlákna přistupují ke stejnému paměťovému místu • každé vlákno přistupuje k jinému paměťovému místu Pokud jsou dodrženy tyto podmínky, přistoupí do sdílené paměti všechna vlákna dané půlky warpu najednou, v opačném případě je přístup serializován. Data ve sdílené paměti je tedy třeba organizovat tak, aby nedocházelo ke konfliktním přístupům. Zároveň,

22

3.3. Shrnutí

protože průběh vykonávání kódu jednotlivých vláken se může měnit11 , je potřeba vlákna před přístupem ke sdílené paměti synchronizovat. K tomu CUDA nabízí jednoduchou funkci __syncthreads(), která funguje stejně jako bariéra. Účastní se jí ale pouze vlákna daného bloku, nejde o synchronizaci vláken napříč celým grafickým procesorem. Podobně lze optimalizovat přístup ke globální paměti. Opět se podmínky týkají jedné půlky vláken ve warpu a jsou následující: • velikost paměťového místa musí být 4, 8 nebo 16 bytů • každé vlákno přistupuje pouze k jednomu paměťovému místu • pořadí vláken odpovídá pořadí paměťových míst — tedy první vlákno přistupuje prvnímu místu, druhé ke druhému, atd. • všechna paměťová místa jsou uložena v rámci jednoho segmentu paměti a adresa prvního místa musí být zarovnána na 16-ti násobek velikosti paměťového místa Za dodržení těchto podmínek může půlka vláken ve warpu přistoupit ke globální paměti zároveň, jinak je přístup serializován.

3.3

Shrnutí

V rámci návrhu byla určena základní architektura výsledné aplikace. Definován byl i komunikační model, a to typu Master-Slave. Podle zadání má aplikace implementovat nějaký způsob vyvažování zátěže. Mělo by jít o dynamické vyvažování, neboť statické vyvažování nesplňuje požadavky a nedosahuje takových výsledků, jako vyvažování dynamické. Implementovat bude potřeba nový parser PDF souborů, případně bude využita nějaká již existující knihovna. Stejně tak projdou revizí i další části aplikace, jako ukládání stavu do souboru při předčasném ukončení a použité šifrovací funkce. V závěru kapitoly byl naznačen způsob optimalizace finální aplikace, a to její profilování. Zmíněny byly i nástroje pro profilování a jeho následnou analýzu. Pro implementaci výpočtů na GPU bylo zmíněno několik pravidel, kterých je potřeba se držet, aby výsledný kód optimálně pracoval s dostupnými typy pamětí na grafické kartě a efektivně využíval grafický procesor.

11 Přestože vykonávají vlákna stejný kód, každé vlákno pracuje s jinými daty. Například porovnání řetězců může jedno vlákno vyhodnotit na základě prvního bytu, zatímco jiné vlákno bude muset porovnat bytů více. Od té chvíle tak vlákna v jeden okamžik vykonávají jiný kód.

23

Kapitola

Implementace a testování Tato kapitola sleduje implementaci aplikace s ohledem na navrženou architekturu a komunikační model. V některých oblastech bylo v předchozí kapitole navrženo více variant, například různé způsoby vyvažování zátěže. V této kapitole budou jednotlivé varianty porovnány (tam, kde je to možné) z hlediska výkonu a nejlepší varianta bude zanesena do finálního řešení. Po popisu implementace následuje způsob optimalizování aplikace a výčet použitých optimalizací. Druhá polovina kapitoly se věnuje popisu aplikace z pohledu uživatele, nabízí tedy popis spouštění aplikace a jednotlivých parametrů. Poslední část kapitoly patří testování aplikace a měření jejího výkonu.

4.1

Popis finální aplikace

Aplikace je složena z několika částí. Základní struktura odpovídá navržené architektuře z obrázku 3.2. Jednotlivé části, tak jak spolu souvisí, jsou popsány dále. Jde především o komunikační část, skládající se z Master a Slave částí a výpočetní část, která se zase štěpí do částí pro CPU a pro GPU.

4.1.1

Komunikační část

Komunikační část je s ohledem na navržený komunikační model rozdělená na Master a Slave. Následuje proto popis obou částí. 4.1.1.1

Master část

Tato část komunikačního modelu je implementovaná jako samostatné vlákno na hlavním uzlu. Vlákno má na starosti řízení všech podřízených uzlů a svým způsobem je tak jádrem celé aplikace. Funkci vlákna znázorňuje obrázek 4.1. Vlákno spravuje celý stavový prostor. Po obdržení požadavku o práci nejprve spočítá velikost stavového podprostoru, který přidělí žádajícímu uzlu. Informace o dané části následně uzlu předá a danou část považuje za hotovou. Pokud vyčerpá celý stavový prostor, na další požadavky o práci odpovídá zprávou oznamující ukončení výpočtu. Žádající uzel se tak dozví, že již pro něj nezbývá další část stavového prostoru a ukončí se. V případě,

25

4

4. Implementace a testování

správa stavového prostoru

zpracování signálu o ukončení

- přidělení práce - zpráva u ukončení Master řídící vlákno

podřízený uzel - požadavky o práci (s informací o rychlosti) - nalezené heslo

uložení informací o stavu hledaní

Obrázek 4.1: Komunikační část — Master

že vlákno obdrží signál o předčasném ukončení, uloží aktuální stav do souboru a přestane vydávat další části stavového prostoru. Podřízené uzly tak dopočítají své části a následně se dozví, že pro ně není další práce a ukončí se.

4.1.1.2

Slave část

Slave část běží na všech uzlech včetně hlavního. Má na starosti zasílání požadavků o přidělení práce od hlavního uzlu a jejich předání výpočetní části na daném uzlu. Následně předává případné nalezené heslo zpět hlavnímu uzlu. - přidělená práce - zpráva u ukončení

část stavového prostoru

sdílená vstupní fronta

nalezené heslo (příp. prázdný řetězec)

sdílená výstupní fronta

podřízené komunikační vlákno

hlavní uzel - požadavky o práci (s informací o rychlosti) - nalezené heslo

Obrázek 4.2: Komunikační část — Slave Protože veškerá komunikace mezi uzly probíhá prostřednictvím MPI, hlavní uzel tak tímto způsobem vlastně komunikuje sám se sebou. Na první pohled je to zbytečné, neboť Slave část na hlavním uzlu by mohla spolupracovat s Master částí prostřednictvím nějaké lokální sdílené fronty. Znamenalo by to ale implementovat tuto část na hlavním uzlu úplně odlišně než na podřízených uzlech. Ale pokud i Slave část na hlavním uzlu bude komunikovat s Master pomocí MPI, může hlavní uzel vykonávat naprosto totožný kód, jako všechny ostatní uzly. Implementace bude jednodušší a čistší. Kromě toho, situace, kdy uzel komunikuje prostřednictvím MPI sám se sebou, by mohla ošetřovat samotná implementace MPI.

26

4.1. Popis finální aplikace

V takových případech by mohla zprávy předávat vnitřně právě pomocí nějakých lokálních sdílených paměťových struktu12 . Obrázek 4.2 znázorňuje schéma komunikační části. Stejně jako výpočetní, i tato je v systému dvakrát. Díky tomu se pak každý stroj pro hlavní uzel tváří jako dva samostatné uzly, kterým přiděluje práci.

4.1.2

Výpočetní část

Část aplikace, která se stará o samotný výpočet — prolamování hesel. Je samozřejmě rozdělená na část pro CPU a pro GPU. Základní princip je ale totožný u obou částí a je znázorněn na obrázku 4.3 přidělená část stav. prostoru rozdělená pro daný počet výpočetních vláken sdílená vstupní fronta

část stavového prostoru výpočetní vlákna

řídící vlákno sdílená výstupní fronta

nalezené heslo (příp. prázdný řetězec) nalezené heslo (příp. prázdný řetězec)

Obrázek 4.3: Výpočetní část

V rámci implementace vyvažování zátěže, které popisuje kapitola 4.1.3, je každý fyzický stroj v clusteru reprezentován jako dva uzly. Jak CPU, tak GPU část si totiž o přidělení práce (tedy části stavového prostoru) žádá samostatně. Jak je vidět na obrázku 4.3, řídící vlákno vybírá ze sdílené vstupní fronty přidělenou část stavového prostoru. Tu rozdělí na tolik částí, kolik má k dispozici výpočetních vláken a informace o těchto jednotlivých částech předá výpočetním vláknům. Každé vlákno tak dostane informaci o prvním a posledním heslu, které má otestovat. Pokud vlákno nalezne heslo, skončí výpočet a nalezené heslo předá řídícímu vláknu. Pokud část přidělená vláknu neobsahovala správné heslo, vrátí výpočetní vlákno řídícímu prázdný řetězec. Stejným způsobem se řídící vlákno zachová vzhledem k výstupní sdílené frontě. Pokud obdrželo od výpočetních vláken heslo, předá jej do výstupní fronty, jinak předá prázdný řetězec. Obě fronty jsou sdílené s komunikačním vláknem, které je popsáno v kapitole 4.1.1.2. Jak bylo zmíněno, výpočetní část je rozdělená pro CPU i GPU. Instance výše popsaného je tedy v systému dvakrát, liší se pouze v samotných výpočetních vláknech. Pro CPU část jde o klasická POSIX vlákna. V případě GPU části je zde volání kernelu, které způsobí spuštění příslušného počtu vláken na GPU. 12

Například MPICH2 a také poslední verze OpenMPI používá speciální modul pro linuxové jádro, které implementuje MPI komunikaci v rámci jednoho uzlu [14].

27

4. Implementace a testování

informace o přiděleném stavovém prostoru

generátor hesel vygenerované heslo

otestování hesla byla vygenerována všechna hesla daného stav. prostoru ne

prošlo heslo testem?

ano konec

Obrázek 4.4: Struktura výpočetního vlákna

4.1.2.1

Struktura výpočetního vlákna

Implementace algoritmů pro samotné prolamování hesel se pro CPU i GPU vlákna samozřejmě liší. Snahou ale bylo, aby jejich struktura byla co nejpodobnější. Nejzásadnějším rozdílem tak je, že CPU část je implementovaná objektově, kdežto GPU část je pouze ve funkcích. Princip obou částí je ale stejný a je zachycen na obrázku 4.4. Pro GPU část bylo nutno implementovat šifrovací funkce MD5 a RC4 vlastními silami, neboť žádná vhodná implementace neexistuje. Pro RC4 nebyla nalezena žádná, pro MD5 byla nalezena implementace [15], která byla ale založena na původní specifikaci MD5 algoritmu od jejího autora Ronalda L. Rivesta. Popis obou algoritmů je k dispozici v přílohách A.1 a A.2.

4.1.3

Vyvažování zátěže

V kapitole 3.2.1 bylo naznačeno, že smysl mají pouze poslední dvě varianty dynamického vyvažování popsané v kapitole 2.5. Nakonec bylo rozhodnuto implementovat poslední popsanou variantu. Je sice nejsložitější, ale přináší nejvíce výhod. Kromě toho, celý proces byl navržený tak, aby nebylo třeba psát speciální výkonnostní test. Výkon jednotlivých uzlů je na začátku výpočtu shodně nastaven na nějakou počáteční hodnotu — všechny uzly tak dostanou při prvním požadavku shodný díl stavového prostoru. Podle rychlosti zpracování

28

4.1. Popis finální aplikace

dané části prohledají se upraví výkon uzlů a při dalším požadavku už dostávají uzly příslušně velké části stavového prostoru. Dělení stavového prostoru se děje ve dvou úrovních. Z hlediska celého clusteru se dělí stavový prostor dynamicky tak, jak si jednotlivé uzly žádají o práci. Každý uzel si pak ještě lokálně dělí přidělenou část dále, podle počtu výpočetních vláken. Vyvažování zátěže je tak svým způsobem hybridní. Z globálního pohledu je plně dynamické, z lokálního pohledu je statické13 . Výkon jednotlivých uzlů se určuje po zpracování přidělené části. Uzel sám si spočítá svojí rychlost, tzn. kolik zpracuje hesel za jednotku času. Tuto informaci předá hlavnímu uzlu spolu s požadavkem o další práci. Hlavní uzel pak žádajícímu uzlu poskytne tak velkou část stavového prostoru, aby doba zpracování odpovídala nějaké nastavené době. Pro názornost jednoduchý příklad. Podřízený uzel zpracuje přidělenou část stavového prostoru rychlostí 200 000 hesel / s. Tuto informaci předá hlavnímu uzlu. Ten má nastaveno, aby vydával tak velké části stavového prostoru, aby jejich zpracování trvalo alespoň 10 s. Žádajícímu uzlu tedy poskytne ke zpracování část o velikosti 2 000 000 hesel. Nastavením těchto hodnot lze určit jemnost, s jakou bude vyvažování zátěže probíhat. Čím jemnější a tedy flexibilnější vyvažování bude, tím ale zároveň poroste komunikační zátěž na síti, neboť se budou uzlům předávat menší části stavového prostoru. Co se týká lokálního dělení stavového prostoru na uzlech — CPU část si přidělený stavový podprostor rozdělí na řádově jednotky menších částí, kdy každou zpracuje jedno výpočetní vlákno. GPU část ale přidělený podprostor rozděluje na řádově tisíce částí, a to už může znamenat určité zdržení. Informace o podprostorech pro jednotlivá vlákna je potřeba zkopírovat do paměti grafické karty, a to znamená zdržení, kdy GPU část nepočítá hesla. Pokud bude nastavené vyvažování příliš jemné a uzly budou dostávat malé části stavového prostoru ke zpracování, bude se toto kopírování významně podílet na celkové době běhu programu. I zde je tedy potřeba nalézt rovnováhu mezi počtem GPU vláken a nastavením vyvažování zátěže. Ještě jedna poznámka k vyvažování. Při spouštění aplikace je třeba zadat požadovaný počet CPU vláken a požadovaný počet bloků a vláken na GPU. Počet vláken na CPU lze zadat buď přímo, pokud ale cluster není homogenní, mohou zůstat některé stroje nevyužity — to se týká například školního clusteru — jeden z uzlů má osmijádrový procesor, všechny ostatní mají procesory pouze čtyřjádrové. Parametr je tedy možné zadat tak, že se počet dostupných jader zjistí automaticky na konkrétním uzlu. Pro GPU toto není možné, ale není to ani třeba. Stačí nastavit počet bloků a vláken tak, aby byla využita nejvýkonnější karta v clusteru, všechny ostatní budou pracovat na plný výkon automaticky. V případě, že nějaký uzel není vybaven grafickou kartou, pošle o tom informaci hlavnímu uzlu, který potřebuje vědět, kolik uzlů je aktivních. Jediné omezení se týká počtu grafických karet. Program umí využít pouze jednu přítomnou kartu. Pokud je stroj vybaven více kartami, zbylé zůstanou nevyužité.

13 Ve skutečnosti z lokálního pohledu o žádné vyvažování zátěže nejde, přidělená část stavového prostoru se rozdělí na stejně velké části podle počtu vláken. Protože ale vlákna běží na stejně výkonných jádrech, výsledek je stejný jakoby šlo o statické vyvažování.

29

4. Implementace a testování

4.1.4

Parsování PDF souborů

Po dlouhém hledání a v průběhu započaté implementace vlastního parseru byla objevena knihovna QPDF [16]. Původně je patrně projekt zamýšlen jako jednoduchý nástroj pro transformaci PDF souborů do PDF souborů s jednodušší strukturou. Zároveň ale poskytuje samostatnou knihovnu i s příslušnými hlavičkovými soubory pro možnost použití knihovny ve vlastních projektech. Knihovna poskytuje objekt PDF parseru. Ten sice při pokusu o otevření zaheslovaného souboru bez poskytnutí hesla vyhodí výjimku, po jejím odchycení ale zůstane objekt k dispozici, a poskytuje přístup ke všem potřebným hodnotám. Nebylo tak potřeba implementovat celý parser vlastními silami. Knihovna přinesla ještě jedno zlepšení. Tím, že korektně načte všechny hodnoty z PDF souboru, došlo k mírnému vylepšení prolamovacích algoritmů. Při výpočtu šifrovacícho klíče pro funkci RC4 se v řešení z bakalářské práce předpokládala výchozí hodnota jednoho z atributů PDF souboru. Pokud byl ale předložen PDF soubor s jinou hodnotou, než výchozí, šifrovací algoritmus tak nepracoval správně. Knihovna nyní umožňuje načíst i hodnotu tohoto atributu a šifrovací algoritmus byl opraven tak, aby bral na tento atribut ohled.

4.1.5

Ukládání stavu do souboru

S ohledem na implementované vyvažování zátěže byl zvolen způsob ukládání stavu do souboru při předčasném ukončení programu. Jak bylo řečeno, při dynamickém vyvažování je správcem stavového prostoru hlavní uzel. Ten vydává jednotlivé části a pamatuje si aktuální pozici — což je konkrétně zde počet vydaných částí. Při odchycení signálu pro ukončení tak hlavní uzel uloží do souboru parametry hledání (typ hledaného hesla, jeho délku a abecedu) a tuto pozici. Podřízeným uzlům od té chvíle na požadavky o práci odpovídá, že další práce již není k dispozici, což vede k ukončení činnosti žádajícího uzlu.

4.2

Optimalizace

Tato sekce popisuje optimalizování výsledné aplikace a některé zajímavé provedené optimalizace. Přináší srovnání šifrovacích funkcí z knihoven IPP a OpenSSL a výslednou volbu pro výpočty na CPU. Zaměřuje se také na práci s pamětí na grafické kartě.

4.2.1

Výsledky profilování

Po provedení profilování nebyly výsledky příliš překvapivé. Drtivou většinu času trávila aplikace výpočtem obou šifrovacích funkcí, příslu. Profilování bylo prováděno pro prolamování uživatelského hesla na souboru s nízkým zabezpečením. Pohledem do kódu to znamená jedno volání funkce MD5 a jedno volání funkce RC4 s klíčem o délce 40 bitů. S vyšším zabezpečením se obě funkce volají v několika cyklech. I přesto byl podíl jakéhokoliv jiného kódu na celkový čas zanedbatelný. Z toho vyplývá, že má smysl vyzkoušet alternativní implementace použitých šifrovacích funkcí, například pomocí již zmíněné knihovny IPP. Přesto bylo možné v kódu provést úpravy pro jeho urychlení, a to hlavně díky tomu, že byl pro prolamování použit původní kód z bakalářské práce. Obsahoval několik zbytečných kopírování bloků paměti mezi dočasnými proměnými.

30

4.2. Optimalizace

Nejdůležitější provedená optimalizace ale byla při výpočtu klíče pro funkci RC4, který se volá pro každé testované heslo. Při jeho výpočtu se nejprve složí vstupní řetězec pro funkci MD5. Ten na začátku obsahuje testované heslo, zbytek řetězce je ale složen z konstant — mění se tak pouze jejich umístění v řetězci podle délky hesla. Pro sadu hesel o stejné délce tak nemá cenu tyto konstanty při každém výpočtu znovu kopírovat na totéž místo. Pokud se tedy testuje heslo o stejné délce, jako bylo to předešlé, použije se řetězec z minulého běhu a pouze se na jeho začátku změní testované heslo.

4.2.2

Výpočet šifrovacích funkcí

Výsledky profilování potvrdily původní domněnku, že má smysl poohlédnout se po jiných implementacích šifrovacích funkcí. Navrženým kandidátem je balíček IPP. Šifrovací funkce z obou balíčků (tedy IPP a OpenSSL) bude potřeba ale nejprve porovnat z hlediska výkonu. Pro tento účel byl napsán jednoduchý výkonnový test. Testuje obě šifrovací funkce, a to stejným způsobem, jakým jsou funkce použity při hledání hesel. To znamená: • MD5: – při výpočtu šifrovacího klíče se počítá haš z dat o velikosti 84 (respektive 88) bytů – při testování hesla vlastníka se počítá haš z dat o velikosti 32 bytů – pokud je použito vysoké zabezpečení, počítá se 50x za sebou haš z dat o velikosti 16 bytů • RC4: – délka klíče může být buď 40 nebo 128 bitů (jiné se prakticky nepoužívají) – při testu obou typů hesel mají vstupní data délku 32 bytů – pokud je použito vysoké zabezpečení, počítá se 19x za sebou, v každém cyklu se znovu nastaví klíč a vstupní data mají velikost 16 bytů při testu uživatelského hesla, 32 bytů při testu hesla vlastníka Výkonnový test byl přeložen s přepínači -msse4 -msse3 -msse2 -msse -mmmx, aby měl přístup k těmto sadám instrukcí. Výsledky jsou patrné z tabulek 4.1 a 4.2. Tabulka 4.1: Porovnání funkce MD5 z IPP a OpenSSL Vstup 16 B 32 B 88 B

IPP počet/s 6.63 mil. 6.65 mil. 3.87 mil.

OpenSSL počet/s 4.43 mil. 4.41 mil. 3.08 mil.

Výsledky jsou poměrně překvapivé. Zatímco MD5 z balíčku IPP je rychlejší než z OpenSSL, u funkce RC4 je to naopak, a to výrazně. OpenSSL implementace funkce RC4 je cca o 60% rychlejší, než ta z balíčku IPP. Test byl přeložen a spouštěn jak na moderním procesoru

31

4. Implementace a testování

Tabulka 4.2: Porovnání funkce RC4 z IPP a OpenSSL Vstup 16 16 32 32

B B B B

Klíč 5B 16 B 5B 16 B

IPP počet/s 615.12 tis. 615.67 tis. 599.39 tis. 599.85 tis.

OpenSSL počet/s 1010.95 tis. 1010.67 tis. 972.00 tis. 971.99 tis.

jednoho z uzlů clusteru (Intel Core i5 760), tak na dnes už výrazně starším procesoru Intel Core 2 Duo 6300 a na obou se choval stejně. Nakonec tedy došlo k výměně pouze funkce MD5, výpočet RC4 se stále provádí pomocí implementace z balíčku OpenSSL.

4.2.3

Práce s pamětí grafické karty

Při implementaci kódu pro grafickou kartu byl brán zřetel na pravidla zmíněná v sekci 3.2.4.3. Zanedbán byl pouze přístup ke globální paměti, to by se ale nemělo výrazně projevit, neboť ke globální paměti se přistupuje pouze jednou pro každý přidělený podprostor danému uzlu. A to při spouštění kernelu, kdy si vlákna kopírují z globální paměti do sdílené informace o jejich části stavového prostoru. Ke globální paměti se přistupuje následně už jen při kontrole proměnné, která je sdílená přes všechna vlákna na grafickém procesoru a která určuje, zda nějaké vlákno již našlo heslo a tudíž se mají ostatní vlákna ukončit. Tato proměnná se kontroluje ale pouze každých cca 64 tisíc cyklů algoritmu, významné zpomalení tedy také nezpůsobí. Práce se sdílenou pamětí pak už je podle všech pravidel. Hodnoty v ní jsou organizovány tak, aby nedocházelo k žádným konfliktům a před přístupem do sdílené paměti jsou vlákna synchronizována. Bylo ověřeno, že samotná organizace dat ve sdílené paměti nestačí. Doba běhu bez synchronizace vláken byla několikanásobně delší, než se synchronizací.

4.2.4

Popis spouštění aplikace

Sluší se uvést ještě způsob spouštění aplikace, respektive popis parametrů, které aplikace přijímá na svém vstupu. Pro běh na clusteru je potřeba aplikaci spustit pomocí programu mpirun. Například pro spuštění na dvou uzlech host1 a host2 vypadá příkaz takto: mpirun -host host1,host2 -np 2 program <argumenty> Kde program je přeložený binární soubor přeložené aplikace a <argumenty> jsou argumenty předané aplikaci. Tyto argumenty mohou být z následujícího seznamu: • -f soubor — cesta k zaheslovanému PDF souboru. • -o — požadavek na prolomení hesla vlastníka. • -u — požadavek na prolomení uživatelského hesla. Nemá smysl hledat oba druhy hesla, v případě požadavku na hledání obou se hledá pouze heslo vlastníka (s jeho znalostí pozbývá uživatelské heslo smysl).

32

4.3. Měření a výsledky

• -l delka — maximální délka hledaného hesla. • -a abeceda — abeceda, ze které se budou hesla generovat. Pokud není tento parametr uvedený, používá se výchozí abeceda složená z malých a velkých písmen anglické abecedy a číslic 0 až 9. • -r soubor — cesta k souboru s uloženým stavem. • -t pocet — počet vláken pro CPU. Pokud není uveden, nebo je hodnota 0, na CPU výpočet neprobíhá. Pokud je uvedená hodnota -1, počet vláken se zjistí automaticky. • -g pocet — počet bloků na GPU (tedy velikost mřížky). • -b pocet — počet vláken v jednom bloku na GPU. Pokud není uveden, nebo je hodnota 0, na GPU výpočet neprobíhá. • -h — zobrazí nápovědu — vysvětlivky k jednotlivým argumentům.

4.3

Měření a výsledky

Poslední část kapitoly se věnuje měření aplikace a srovnání s původním řešením z bakalářské práce. Měření bakalářské práce provázely obtíže, a to zejména kvůli nefunkčnímu PDF parseru. V některých případech tak bylo potřeba upravit kód bakalářské práce a některé hodnoty doplnit do kódu natvrdo. Vše ale naštěstí bez újmy na přesnosti měření.

4.3.1

Způsob měření

Pro změření výkonu bylo nejprve potřeba připravit testovací data. Omezujícími podmínkami byly schopnosti algoritmu — v úvahu přicházely tedy pouze soubory šifrované pomocí funkce RC4. Specifikace umožňuje šifrovat i pomocí funkce AES, to ale implementované algoritmy neumí. Všechny vyzkoušené nástroje pro tvorbu PDF souborů nabízely pouze dva typy zabezpečení — nízké a vysoké. Nízké znamenalo délku klíče pro RC4 40 bitů, vysoké 128 bitů. Vysoké zabezpečení navíc mělo za následek zmíněné 4.2.2 opakování volání šifrovacích funkcí. Vygenerovány tedy byly dva PDF soubory: • low.pdf – délka klíče pro RC4: 40 bitů – číslo revize zabezpečení: 2 – heslo vlastníka: „olow“ – uživatelské heslo: „ulow“ • high.pdf – délka klíče pro RC4: 128 bitů – číslo revize zabezpečení: 4 (tzn. opakované volání obou používaných šifrovacích funkcí)

33

4. Implementace a testování

– heslo vlastníka: „ohigh“ – uživatelské heslo: „uhigh“ Tyto dva soubory pak byly prolamovány jak na heslo vlastníka, tak na uživatelské heslo. Celkem tedy byly připraveny čtyři scénáře, vyjmenované a očíslované níže. Dále na ně bude odkazováno podle příslušného čísla: 1. prolamovaní uživatelského hesla v souboru low.pdf 2. prolamovaní hesla vlastníka v souboru low.pdf 3. prolamovaní uživatelského hesla v souboru high.pdf 4. prolamovaní hesla vlastníka v souboru high.pdf Jednotlivá měření byla prováděna nad různě velkými vzorky dat — tak, aby dané měření doběhlo v rozumném čase. Níže uvedené výsledky jsou přepočítané a vyjadřují rychlost aplikace v daném scénáři. Pro měření času byla využita MPI funkce MPI_Wtime, která vrací skutečný uplynulý čas ve vteřinách jako desetinné číslo. Pouze v případě měření výkonnosti grafické karty v závislosti na nastaveném počtu vláken se používá měření času pomocí funkcí, které nabízí CUDA, a sice cutCreateTimer a dalších přidružených pro nastartování měření času (cutStartTimer), ukončení (cutStopTimer) a získání změřené hodnoty (cutGetTimerValue). Podává přesnější výsledky pro měření samotného výpočtu na GPU.

4.3.2

Naměřené hodnoty

Každé měření bylo provedeno desetkrát a pro každé byla stanovena směrodatná odchylka. Popis jednotlivých měření následuje. 4.3.2.1

Porovnání čistého výkonu šifrovacích algoritmů na CPU

První měření porovnává čistý výkon aplikace běžící v jednom vlákně bez jakéhokoliv vyvažování. Jak řešení z bakalářské práce, tak nová aplikace byla spuštěna v jednom vlákně, tomuto vláknu byl předán celý stavový prostor a byl změřen čas, za který vlákno přidělený stavový prostor zpracovalo. Jde tedy o přímé porovnání samotných šifrovacích algoritmů bez jakýchkoliv okolních vlivů. Tabulka 4.3: Porovnání čistého výkonu šifrovacích algoritmů na CPU Scénář 1 2 3 4

34

počet/s 655 356.1 354 285.3 33 439.1 16 244.1

BP směr. odch. 1 018.5 1 062.1 25.7 31.4

počet/s 744 147.5 393 215.2 35 769.8 17 411.6

DP směr. odch. 499.3 360.2 63.3 16.7

4.3. Měření a výsledky

Měření byla prováděna na uzlu alpha. Výsledky jsou vidět na obrázku 4.5, hodnoty spolu se směrodatnými odchylkami v tabulce 4.3. Jak je vidět, ve všech scénářích je nové řešení rychlejší, než původní program z bakalářské práce. Rozdíly u posledních dvou scenářů již nejsou tak výrazné, přesto je nová aplikace stále výkonnější. V dalších měřeních výkon přepočtený na jedno vlákno pravděpodobně klesne, a to vlivem vyvažování a tedy zvýšené komunikační zátěže, na úkor té výpočetní. 800000

700000

600000

počet hesel / s

500000

400000 BP DP 300000

200000

100000

0 1

2

3

4

scénář

Obrázek 4.5: Porovnání čistého výkonu šifrovacích algoritmů na CPU

4.3.2.2

Porovnání výkonu clusteru pouze na CPU

Druhá úloha měřila výkon aplikace spuštěné na celém clusteru pouze na CPU. GPU část nové aplikace byla nyní vypnutá. Tabulka 4.4: Porovnání výkonu clusteru pouze na CPU Scénář 1 2 3 4

BP počet/s směr. odch. 1 666 612.8 2.9 1 111 079.9 0.9 111 107.9 0.4 55 554.1 0.1

DP počet/s směr. odch. 11 421 281.0 165 597.7 6 047 650.6 76 877.3 501 606.8 1 818.8 244 932.4 290.8

V případě nové aplikace tak výslednou rychlost ovlivňuje proces vyvažování, kdy uzly nepočítají nonstop, ale pravidelně žádají hlavní uzel o práci. Původní řešení z bakalářské

35

4. Implementace a testování

práce pouze rozdělí stavový prostor a ten zpracuje najednou na všech uzlech. Na druhou stranu je nutné připomenout, že řešení z bakalářské práce počítá na každém uzlu pouze v jednom vlákně, zatímco nová aplikace využívá všechna dostupná jádra na každém uzlu. Jak je vidět, nová aplikace pouze s aktivní CPU částí je několikanásobně rychlejší, než původní řešení z bakalářské práce. 12000000

10000000

počet hesel / s

8000000

6000000 BP DP 4000000

2000000

0 1

2

3

4

scénář

Obrázek 4.6: Porovnání výkonu clusteru pouze na CPU Poměrně velké hodnoty směrodatných odchylek u nové aplikace jsou způsobeny rozdílem nejhoršího a nejlepšího času cca 4 s. U tak vysokých rychlostí se ale i sebemenší rozdíl na směrodatné odchylce významně projeví. 4.3.2.3

Vliv počtu vláken na rychlost výpočtu na GPU

Následující měření zkoumá vliv nastavených počtu vláken, respektive bloků, na rychlost výpočtu na grafické kartě. Primárně slouží ke zjištění optimálního nastavení pro další měření. Zvyšující se počet bloků by od určité hranice neměl mít na rychlost pozitivní vliv. Jak bylo už zmíněno, počtem bloků lze výkon škálovat pro nové, výkonnější grafické karty, které dokáží zpracovat více bloků současně. Počty bloků byly proto nastaveny na tři různé hodnoty, a to 24, 48 a 96. Počet vláken byl postupně zvyšován od 1 do 256. Grafická karta vždy dostala ke zpracování 2 000 000 hesel. Naměřené časy pro jednotlivé kombinace počtu bloků a vláken jsou vidět na obrázku 4.7. Měření byla prováděna na uzlu beta. Zobrazeny jsou hodnoty počtu vláken od 10, nižší hodnoty mají za následek výrazně vyšší časy a tím pádem zkreslí měřítko celého grafu. Skoky v době počítání jsou způsobeny tím, že se při určité konfiguraci povede optimálně obsadit grafický procesor a zvýšit tak počet současně aktivních vláken. S ohledem na teoretické hodnoty (tzn. maximální počet aktivních

36

4.3. Měření a výsledky

2500

Doba běhu [ms]

2000

1500 24 48 1000 96

500

0 10

50

90

130

170

210

250

počet vláken na blok

Obrázek 4.7: Vliv počtu vláken na rychlost výpočtu na GPU

vláken na procesoru 1536), dobrou škálovatelnost, ale zároveň ne příliš velký počet vláken (aby nenarostla režie okolo předávání informací o stavových podprostorech) byla pro další měření zvolena konfigurace 48 bloků a 63 vláken na blok, což dává dohromady 3 024 vláken. 4.3.2.4

Porovnání plného výkonu na clusteru

V posledním měření dojde k porovnání plného výkonu aplikace, tj. s aktivní CPU i GPU částí, s řešením z bakalářské práce. Vzhledem k tomu, že samotný výpočet na grafické kartě byl ještě rychlejší, než na samotném CPU, očekává se ještě propastnější rozdíl mezi novou a původní aplikací. Velká škoda je, že na uzlu epsilon po dobu několika týdnů (a i v době měření) nefungovala grafická karta, která byla papírově nejvýkonnější na celém clusteru. Tabulka 4.5: Porovnání plného výkonu aplikace na clusteru Scénář 1 2 3 4

BP počet/s směr. odch. 1 666 612.8 2.9 1 111 079.9 0.9 111 107.9 0.4 55 554.1 0.1

DP počet/s směr. odch. 17 509 670.9 170 485.5 9 123 840.6 73 968.9 711 565.9 6 128.6 341 797.6 1 833.6

Plný výkon aplikace drtivě poráží původní řešení a několikanásobně jej překonává ve všech scénářích. Obrázek 4.8 ukazuje rozdíl mezi novou aplikací a původním řešením.

37

4. Implementace a testování

20000000 18000000 16000000

počet hesel / s

14000000 12000000 10000000 BP DP

8000000 6000000 4000000 2000000 0 1

2

3

4

scénář

Obrázek 4.8: Porovnání plného výkonu aplikace na clusteru

Na obrázku 4.9 je pak vidět rozdíl mezi během plně aktivní aplikace a během s aktivní pouze CPU částí. Příspěvek páté grafické karty by posunul celý výkon ještě o něco výše, takto jsou aktivní „pouze“ čtyři grafické karty na pět procesorů (a z toho jeden procesor má navíc dvojnásobný výkon oproti ostatním). 20000000 18000000 16000000

počet hesel / s

14000000 12000000 10000000 DP - CPU DP - CPU + GPU

8000000 6000000 4000000 2000000 0 1

2

3

4

scénář

Obrázek 4.9: Porovnání plného výkonu aplikace a pouze CPU části

38

4.4. Shrnutí

4.4

Shrnutí

V rámci implementaci byla vytvořena nová verze celé aplikace. Z původního kódu zbyla pouze kostra šifrovacích algoritmů, zbytek byl celý přepsán, respektive napsán znovu od začátku. To je dané tím, že na aplikaci byla kladeny poměrně jasné požadavky, které s původním kódem nešly dobře dohromady. Aplikace je výrazně strukturovaná do jednotlivých tříd, které spolů tvoří výše popsané logické celky, které navzájem spolupracují. Bylo implementované navržené dynamické vyvažování zátěže, které je navíc velmi dobře konfigurovatelné. Kód aplikace prošel procesem profilování a byl optimalizován tak, aby se neprováděly zbytečné operace. Nejnáročnější část výpočtu — šifrovací funkce MD5 a RC4 — byly podrobeny výkonnostní analýze a funkce MD5 byla nahrazena rychlejší implementací z balíčku knihoven IPP. Přepsán byl PDF parser, který nyní využívá k parsování externí knihovnu QPDF. Parsování PDF souborů je teď mnohem spolehlivější a díky tomu se povedlo upravit šifrovací algoritmus tak, aby lépe odpovídal specifikaci. Nová aplikace byla následně podrobena důkladnému měření a byla srovnávána s původním řešením z bakalářské práce. Ve všech testech byla nová aplikace výkonnější. Ve své nejsilnější konfiguraci překonávala původní řešení podle zvoleného scénáře i více než 10x.

39

Kapitola

Závěr Zadání diplomové práce ukládá optimalizovat existující software pro distribuované prolamování hesel v souborech PDF tak, aby běžel na svazcích GPU a implementoval aktivní vyvažování zátěže. Následně je potřeba provést měření a srovnání s již existujícím programem. V rámci analýzy bylo existující řešení z bakalářské práce prozkoumáno z hlediska funkčnosti, teoretických výkonnostních možností a uživatelského rozhraní. Zároveň byla provedena analýza dostupných komerčních i volně dostupných nástrojů pro prolamování hesel v PDF souborech. Pouze některé ze zkoumaných nástrojů umožňují distribuovat výpočet na cluster a zároveň nabízí urychlení výpočtu použitím grafických karet. Na trhu chybí volně dostupné řešení, které by využívalo jak CPU tak GPU paralelizace a zároveň umožňovalo distribuovaný běh na clusteru. Základním požadavkem je upravit existující řešení tak, aby bylo možné jej spouštět na grafických kartách. Zvolená architektura byla CUDA, mimojiné i proto, že nově vytvořená aplikace bude spouštěna a testována na školním clusteru GPULab, který je vybaven grafickými kartami od společnosti NVIDIA. Ta je autorem architektury CUDA, která usnadňuje provádění obecných výpočtů na grafických kartách. Dalším požadavkem bylo implementovat aktivní vyvažování zátěže. Jednotlivé způsoby byly v rámci analýzy popsány a následně při návrhu aplikace bylo zvoleno dynamické vyvažování zátěže. S tím souvisí i zvolený komunikační model, který je stejně jako v původním řešení typu Master-Slave. Byly navrženy různé optimalizace, mimojiné byla navržena výměna šifrovacích funkcí z balíčku OpenSSL, které se v původním řešení používaly, za nějaké jiné, výkonnější. V rámci návrhu bylo také zmíněno, jakým způsobem by měl probíhat vývoj části pro grafický procesor, aby následný běh kódu na GPU byl co nejefektivnější. Zdůrazněna byla také potřeba implementovat funkční PDF parser, neboť ten z původního řešení byl značně nespolehlivý, což se ukázalo i později během měření. Navržené optimalizace byly implementovány. Aplikace z bakalářské práce byla v podstatě celá přepsána znovu. A to především kvůli požadavku na vyvažování zátěže. To si vyžádalo zcela jiný přístup, neslučitelný s kódem z bakalářské práce. Implementované vyvažování zátěže umožňuje přizpůsobit běh program aktuálním podmínkám na jednotlivých uzlech, navíc vyvažuje CPU i GPU části nezávisle na sobě. Umí si poradit i s uzly, které nejsou vybaveny grafickou kartou. Požadavek na aktivní vyvažování zátěže byl tedy splněn.

41

5

5. Závěr

Implementovány byly algoritmy pro šifrování hesel pro grafickou kartu. Kód byl optimalizován s ohledem na přístup do různých typů pamětí na grafické kartě. Protože v době psaní této práce neexistovala použitelná implementace šifrovacích funkcí MD5 a RC4 pro architekturu CUDA, bylo nutné tyto funkce implementovat vlastními silami. Výsledkem je funkční kód, který umožňuje prolamovat hesla na grafické kartě. I tento bod zadání byl splněn. Výsledná aplikace byla změřena různými způsoby a porovnána s původním řešením. Byly vytvořeny různé scénáře, lišící se jinými vstupními daty a parametry. Ve všech scénářích byla nová aplikace výrazně výkonnější, než původní řešení. Například při srovnání původního řešení a nové aplikace, která využívala paralelizaci jak na CPU, tak na GPU, byla nová aplikace v případě prvního měřeného scénáře více než 10x rychlejší (a to nebyly grafické karty k dispozici na všech uzlech). Poslední bod zadání byl tímto také splněn. Povedlo se vytvořit aplikaci pro distribuované prolamování hesel v PDF souborech, která využívá dostupných CPU i GPU prostředků v maximálné možné míře. Aplikace aktivně rozkládá zátěž na jednotlivé uzly clusteru podle jejich aktuálního zatížení. V případě předčasného ukončení umí uložit aktuální stav do souboru a následně z něj hledání obnovit.

42

Literatura (1) BAK, Martin: Distribuované prolamování hesel v PDF: Bakalářská práce Praha: ČVUT v Praze, Fakulta elektrotechnická, 2007 (2) NVIDIA Corporation: Compute Unified Device Architecture Dostupné z WWW: (3) Adobe Systems, Inc.: Portable Document Format Dostupné z WWW: (4) Argonne National Laboratory: Message Passing Interface Dostupné z WWW: (5) IEEE Standards Association: Portable Operating System Interface 1c. Dostupné z WWW: (6) SEMJANOV, Pavel: GuaPDF Dostupné z WWW: (7) Elcomsoft Co. Ltd.: Advanced PDF Password Recovery Dostupné z WWW: (8) Khronos Group: Open Computing Language Dostupné z WWW: (9) Eltima Software: PDF Password Cracker Dostupné z WWW: (10) NOREN, Henning: PDFCrack Dostupné z WWW: (11) NVIDIA Corporation: CUDA C Programming Guide Dostupné z WWW:

43

Literatura

(12) NVIDIA Corporation: CUDA Occupany calculator Dostupné z WWW: (13) Intel Corporation: Integrated Performance Primitives Dostupné z WWW: (14) Inria Runtime Team-Project and co.: KNEM Dostupné z WWW: (15) JURIC, Mario: CUDA MD5 Hashing Experiments Dostupné z WWW: (16) BERKENBILT, Jay: QPDF Dostupné z WWW: (17) RIVEST, Ronald: The MD5 Message-Digest Algorithm Dostupné z WWW: (18) KAUKONEN, K., THAYER, R.: A Stream Cipher Encryption Algorithm „Arcfour“ Dostupné z WWW: (19) Wikimedia Foundation: Zdroj obrázku pro znázornění funkce MD5 Dostupné z WWW: (20) Wikimedia Foundation: Zdroj obrázku pro znázornění funkce RC4 Dostupné z WWW: (21) NVIDIA Corporation: Fermi Compute Architecture Whitepaper Dostupné z WWW:

44

Příloha

Implementované šifrovací algoritmy na GPU A.1

MD5

Algoritmy použité pro šifrování hesel používají dvě kryptografické funkce, MD5 a RC4. Vzhledem k tomu, že pro architekturu CUDA neexistuje oficiální implementace hašovací funkce MD5, bylo nutné provést implementaci vlastními silami. Na internetu sice lze nalézt již hotová řešení, ale buď nebyla vhodná pro použití v této práci nebo byla jen ukázkovou implementací dle specifikace. Následuje proto stručný popis obou funkcí. MD514 je hašovací funkce, která ze vstupních dat o libovolné délce vypočítá haš o fixní délce 128 bitů. Vytvořena byla v letech 1991 — 1992 [17] profesorem Ronaldem L. Rivestem. Funkce měla sloužit především jako krátký otisk původních dat, umožňující podobnou funkčnost jako kontrolní součet15 , případně jako bezpečné uložení citlivých dat, např. hesel. O několik let později však byl ukázan postup, jak nalézt kolize a posléze byla funkce prohlášena jako málo bezpečná a od jejího používání se v kritických aplikacích upouští. Algoritmus pracuje následovně. Vstupní data se rozdělí do bloků po 512 bitech. Pokud délka vstupních dat není násobkem 512, doplní se na konec jeden bit s hodnotou 1, dále bity s hodnotou 0, a to takový počet, aby do násobku 512 zbývalo 64 bitů. Těchto 64 bitů bude obsahovat číslo reprezentující délku původních vstupních dat v bitech. Algoritmus poté zpracovává data po jednotlivých blocích. Nejprve inicializuje čtyři interní 32 bitové registry. Každý blok pak rozdělí na šestnáct 32 bitových podbloků a ty ve čtyřech rundách po 16 krocích transformuje a aplikuje na čtyři vnitřní registry. Jeden takový krok ukazuje obrázek A.1. A, B, C a D jsou vnitřní registry algoritmu. F reprezentuje funkci aplikovanou na vstupní data, která se liší pro každou rundu. Mi představuje jeden 32 bitový podblok vstupních dat. Ki je předem daná konstanta (určená pro konkrétní i-tý krok). ≪s představuje rotaci doleva o s bitů (opět pro každý krok je hodnota s jiná, předem daná). Symbol sčítání reprezentuje sčítání modulo 232 . 14

Message-Digest algorithm Kontrolní součet je krátká informace vypočtená známým algoritmem ze vstupních dat a slouží k ověření, že data jsou např. po přenosu bez chyby — po přijetí se spočítá kontrolní součet přijatých dat a porovná se s přijatým kontrolním součtem 15

45

A

A. Implementované šifrovací algoritmy na GPU

Obrázek A.1: MD5: jeden krok algoritmu [19]

Konkrétní hodnoty konstant, velikosti rotací a rundové funkce lze nalézt v implementaci algoritmu v přiložených zdrojových kódech.

A.2

RC4

RC416 je proudová šifra navržená také profesorem Ronaldem L. Rivestem v roce 1987. Šifra je majetkem RSA Security, Inc., která nikdy oficiálně algoritmus nezveřejnila a drží obchodní známku na název šifry. Ta byla ale v roce 1994 anonymně zveřejněna a bývá označována jako ARCFOUR17 . RC4 se snadno implementuje jak softwarově, tak hardwarově, vyniká svoji rychlostí a jednoduchostí. Proto se běžně používá např. v algoritmech pro zabezpečení přenosu dat ve Wi-Fi sítích, aj. Šifrování se řídí klíčem, tím je potřeba algoritmus inicializovat. Alokuje se pole o 256 bytech, označuje se jako S-box. Pole se naplní čísly od 0 do 255. Alokuje se druhé pole — S-box2 o stejné délce a naplní se opakováním klíče. Pak se prvky původního pole promíchají podle následujícího algoritmu: for (i = 0; i < 256; ++i) { j = (j + S[i] + S2[i]) % 256 prohod prvky S[i] a S[j] } Takto inicializovaný S-box pak slouží ke generování pseudonáhodné šifrovací posloupnosti. Algoritmus šifrování je velmi podobný inicializaci klíče. Vstupní data se zpracovávájí po jednotlivých bytech. Z S-boxu se vygeneruje šifrovací byte a pomocí operace XOR se 16 17

46

Oficiálně Rivest Cipher, někdy se také zkratka vykládá jako Ron’s Code Nebo ARC4 — od alleged RC4

A.2. RC4

aplikuje na byte vstupních dat. Během generování se mění obsah S-boxu a proto i pokud by na vstupu byla posloupnost stejných bytů, výsledkem bude pseudonáhodná posloupnost. Generování bytů znázorňuje obrázek A.2.

Obrázek A.2: RC5: generování šifrovací posloupnosti [20] Indexy i a j jsou na začátku oba nulové, v dalších krocích se index i počítá jako (i + 1) mod 256, index j potom jako (j +S[i]) mod 256. Zvýrazněný prvek K na obrázku představuje generovaný byte šifrovací posloupnosti. Protože jde o symetrickou šifru, dešifrování probíhá naprosto stejným způsobem. Stejným šifrovacím klíčem se inicializuje S-box a generované šifrovací byty se XOR-ují s byty zašifrovaných dat. Výsledkem jsou originální vstupní data.

47

Příloha

Obsah přiloženého CD / program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . zdrojové kódy implementované aplikace. include . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . hlavičkové soubory aplikace. src . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . zdrojové soubory aplikace. cuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . zdrojové soubory GPU části aplikace. data . . . . . . . . . . . . . . . . . . . . . . . . . . . testovací data — PDF soubory — viz 4.3.1. cmakemodules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . moduly pro překladač. howto.txt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . popis překladu zdrojových kódů. text src . . . . . . . . . . . . . . . . . . . . . . . . . . . zdrojová forma textu práce ve formátu LATEX. DP_Martin_Bak_2012.pdf . . . . . . . . . . . . . . . . . . . . text práce ve formátu PDF. readme.txt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . stručný popis obsahu CD.

49

B