Teoretická informatika (verze pro anglické studenty)

Závěrečné práce

Diplomové práce

Aplikace zpětnovazebního učení na vytváření adversariálních vzorků škodlivého softwaru

Autor
Matouš Kozák
Rok
2023
Typ
Diplomová práce
Vedoucí
Mgr. Martin Jureček, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Strojové učení se díky svým prvotřídním výsledkům v mnoha oblastech stává stále více populárnější pro řešení nejrůznějších problémů. Díky tomu vývojáři antivirů začínají začleňovat modely strojového učení i do svých produktů. I když tyto modely zlepšují schopnosti detekce antivirových programů, mají také své nevýhody v podobě citlivosti na adversariální útoky. Ačkoli tato citlivost byla prokázána u mnoha modelů při white-box útocích, pro oblast detekce malwaru je black-box útok využitelnější v praxi. Proto představujeme black-box útok, kde má útočník k dispozici pouze výsledek predikce a vzdává se jakýchkoli dalších informací o cílovém klasifikátoru. S využitím algoritmů zpětnovazebního učení jsme implementovali útok proti GBDT klasifikátoru natrénovaném na EMBER datasetu. Natrénovali jsme několik zpětnovazebních agentů na datové sadě malwaru pro operační systém Windows. Při modifikování jsme kladli velký důraz na zachování původní funkčnosti škodlivých vzorků. Dosáhli jsme úspěšnosti zmýlení cílového klasifikátoru v 58,92 % s využitím PPO algoritmu. Kromě toho, že jsme cílili na tento detektor, jsme studovali, jak se adversariální útok může přenést na jiné modely. Agent dříve natrénovaný proti GBDT klasifikátoru zaznamenal úspěšnost v 28,91 % případů proti MalConv, což je model založený čistě na strojovém učení. Vygenerované adversariální vzorky jsme také otestovali proti špičkovým AV programům a dosáhli jsme úspěšnosti zmýlení v rozmezí od 10,24 % do 25,7 %. Tyto výsledky dokazují, že nejen modely založené pouze na strojovém učení jsou náchylné k adversariálním útokům a že je třeba přijmout lepší opatření k ochraně našich systémů.

Algoritmy kombinatoriky na slovech

Autor
Martin Rejmon
Rok
2021
Typ
Diplomová práce
Vedoucí
doc. Ing. Štěpán Starosta, Ph.D.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.
Anotace
V této práci je podrobně popsáno několik algoritmů řešících problémy z matematického oboru kombinatorika na slovech. Součástí práce je i jejich implementace v svobodném a otevřeném počítačovém algebraickém systému SageMath za účelem jejich integrace do téhož systému. Mezi zkoumané algoritmy patří: klasifikace rostoucích písmenek morfismu, rozhodování se, zda morfismus je prostý, hledání zjednodušení morfismu, hledání všech nekonečných opakování v D0L systému a hledání všech podřetězců (kratší než zadaná délka) slov jazyka PD0L systému. Dále je v práci diskutován problém rozhodování se, zda morfimus D0L systému je prostý na množině podřetězců slov jazyka toho systému. Není obecně známo, zda tento problém jde rozhodnout, což v této práci není vyřešeno, ale je zde uvedeno, proč je to netriviální problém a kde některé z možných způsobů jeho řešení selžou.

Modulární a rozšiřitelný nástroj pro lokalizaci softwarových chyb

Autor
Petr Nevyhoštěný
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Petr Máj
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Lokalizace chyb je považována za jeden z nejvíce únavných a časově náročných úkolů při vývoji software. Přesto je stále často prováděna manuálně. Lokalizace softwarových chyb (anglická zkratka SFL) je oblast výzkumu zabývající se vývojem automatizovaných technik pro usnadnění této aktivity. Navzdory množství práce, která byla tomuto výzkumu věnována, nesplňují aplikace navržených metod kompletně potřeby praxe. Tato magisterská práce proto popisuje nový nástroj a framework pro lokalizaci softwarových chyb s názvem \emph{Aardwolf}, jehož hlavním cílem je usnadnit použití SFL technik v praxi. Toho je dosaženo velmi modulárním designem, umožňujícím snadnou rozšiřitelnost, a aplikováním doporučení, která lze naleznout v publikovaných uživatelských studiích. Pro demonstraci možností nástroje Aardwolf byla implementována trojice různých SFL technik a frontendy pro programovací jazyky C a Python. Integrace do dvou větších softwarových projektů byla popsána jako ukázka aplikovatelnosti. Předběžné výsledky ukazují, že je efektivita nástroje srovnatelná s literaturou. Zaměření na uživatelskou přívětivost a rozšiřitelnost řešení je ovšem významné zlepšení oproti současnému stavu v tomto odvětví.

Zpětné reference v rozšířených regulárních výrazech

Autor
Martin Hron
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Ondřej Guth, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Zpětné reference (odkazy) jsou rozšíření regulárních výrazů bežně podporované v dnešních nástrojích. Regulární výrazy se zpětnými referencemi mají zvýšenou vyjadřovací sílu, ale jejich vyhledávání (matching) je NP-úplné. Tato práce poskytuje přehled existujících přístupů pro vyhledávání regulárních výrazů se zpětnými referencemi a také teoretického výzkumu na toto téma. V rámci této práce byl implementován nástroj pro vyhledávání regulárních výrazů založený na modelu paměťových automatů (memory automata). Vyhledávání regulárních výrazů s počtem zpětných referencí na různé skupiny omezených konstantou pomocí paměťových automatů má polynomiání časovou složitost. Byla implementována další nedávno zveřejněná metoda založená na paměťových automatech, která poskytuje polynomiální složitost i pro výrazy s neomezeným počtem zpětných referencí splňujících jistou vlastnost. V rámci této práce byl navržen a implementován alternativní algoritmus pro výpočet této vlastnosti. Model paměťového automatu byl dále rozšířen pro podporu kvantifikátorů omezeného počtu opakování a další rozšíření byla implementována. Experimentální vyhodnocení ukázalo, že implementovaný nástroj je mnohem odolnější vůči katastrofickému backtrackování než existující implementace podporující zpětné reference. Žádný z testovaných útoků přes algoritmickou složitost nevyvolal znatelné zpomalení.

Parametrizované algoritmy pro Steinerovské stromy

Autor
Peter Mitura
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Je-li dán vážený graf a podmnožina jeho vrcholů zvaných terminály, problém Steinerova stromu spočívá v nalezení souvislého podgrafu s nejmenší váhou, který obsahuje všechny terminály. Jedná se o známý NP-těžký problém, který nalézá užití kupříkladu v návrhu integrovaných obvodů, nebo počítačových a dopravných sítích. V této práci rozebereme algoritmus od Dreyfuse a Wagnera, od Ericksona, Monmy a Veinotta, a Nederlofův algoritmus, které řeší verzi tohoto problému parametrizovanou počtem terminálů, a algoritmus využívající dynamické programování a matici řezů pro parametrizaci dle stromové šířky. Pro všechny popsané algoritmy vytvoříme optimalizovanou implementaci a pro porovnání s jinými řešeními ukážeme její výsledky v soutěži PACE 2018.

Kombinatorické hry typu Taking and Breaking

Autor
Šimon Lomič
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Anotace
V této práci analyzujeme několik otevřených problémů v oblasti nestranných i stranných her typu Taking and Breaking. Pro nestranné odčítací hry dokážeme existenci hry s aperiodickou nim-sekvencí a periodickou sekvencí výhra-prohra. Analyzujeme ekvivalenční třídy těchto her a nalézáme řešení jedné z těchto tříd. Také představujeme novou hru typu Taking and Breaking, kterou z velké části vyřešíme. V oblasti stranných her provedeme analýzu několika odčítacích her a her typu Pure Breaking. Pro tyto hry také představíme obecnou techniku testování aritmetické periodicity. Pro automatické řešení nestranných her typu Taking and Breaking navrhujeme několik algoritmů. Práci uzavíráme důkazem PSPACE-těžkosti nestranné zobecněné odčítací hry a EXPTIME-těžkosti této hry ve stranné variantě.

Podchycování cest v grafech

Autor
Radovan Červený
Rok
2018
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Problém zvaný d-Path Vertex Cover, d-PVC spočívá v nalezení podmnožiny F vrcholů daného grafu G=(V,E) takové, že G \ F neobsahuje žádnou cestu na d vrcholech. Cesty, které chceme takto podchytit, nemusí být indukované. Je známo, že problém d-PVC je NP-úplný pro každé d >= 2. Dále je známo, že problém 5-PVC parametrizovaný velikostí řešení k je řesitelný v čase O(5^k*n^O(1)). V této práci přicházíme s algoritmem používající iterativní kompresi, který řeší problém 5-PVC v čase O(4^k*n^O(1)).

Algoritmus pro hledání podgrafu založený na barevném kódování

Autor
Josef Malík
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Tato práce popisuje řešení problému izomorfismu podgrafů pomocí techniky barevného kódování. V práci je popsán problém izomorfismu podgrafů, jeho varianty a jeho aplikace. Dále je rozebrán problém tvorby hezkého stromového rozkladu optimální šířky pro zadaný graf, jelikož takováto struktura je pro daný přístup vyžadována. Jako hlavní část práce je popsáno několik modifikací a optimalizací původního algoritmu založeného na barevném kódování. Praktickým výsledkem práce je modul implementovaný v jazyce C, který je navržen pro řešení velkých instancí problému izomorfismu podgrafů včetně výpisu nalezených výsledků.

Indexování XML dokumentů

Autor
Eliška Šestáková
Rok
2015
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Výzkum v oblasti indexování řetězců má již mnoho prezentovaných výsledků, což však neplatí pro ostatní datové struktury, jakými jsou například stromy. Tato práce obsahuje v prvé řadě shrnutí metod pro indexování řetězců a stromů. Dále se podrobně zabývá rešerší existujících řešení indexování XML dokumentů. Představena je zde nová jednoduchá metoda využívající deterministický konečný automat, jež umožňuje efektivně zpracovat XPath dotazy skládající se z libovolné kombinace child (/) a descendant-or-self (//) os, sloužících k navigaci v XML dokumentu. Spolu s touto metodou byly dále navrženy dva další konečné automaty na podporu jednodušších dotazů obsahujících vždy pouze jednu z uvedených os. Ke konstrukci indexu pro daný XML dokument D s n elementy je využit odpovídající XML stromový model T. Zpracování dotazu Q o m elementech proběhne v čase O(m) nezávislém na n. Výsledkem dotazu je poté množina elementů splňujících dané požadavky. Ačkoli automat podporující všechny dotazy s // osou indexuje až O(2^n) různých dotazů, počet stavů vlastního deterministického automatu je O(h^k), kde h je výška XML stromového modelu T a k je počet listů T. Pro běžné XML dokumenty lze navíc tuto mez triviálně snížit až na O(h.2^k).

Inkrementální komprese založená na clusterování

Autor
Luboš Krčál
Rok
2014
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

Vyhledávání a indexování v neseřazených stromech

Autor
Vojtěch Sobota
Rok
2013
Typ
Diplomová práce
Vedoucí
prof. Ing. Bořivoj Melichar, DrSc.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.

Za obsah stránky zodpovídá: Ing. Zdeněk Muzikář, CSc.