Závěrečné práce

Mgr. Martin Jureček, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

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ů.

Práce na DSpace

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Jan Janoušek, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

Ing. Petr Máj

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

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í.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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í.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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ě.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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)).

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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ů.

Práce na DSpace

doc. Ing. Jan Janoušek, Ph.D.

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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).

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

prof. Ing. Bořivoj Melichar, DrSc.

doc. Ing. Jan Janoušek, Ph.D.

Katedra teoretické informatiky