|
|
Efektivnost datových strukur v implementaci automatů
Koval, Milan ; Smrčka, Aleš (referee) ; Holík, Lukáš (advisor)
Tato Prace se soustředí na optimalizaci knihovny Mata, která je součastným leaderem na poli vykonu v oblasti operací nad automaty. Výrazdné zlepšení výkonu je dosáhnuto pomocí modifikovaného lineárního alokátoru, využitím append-only vlastnosti reprezentace automatu umozňue bleskově rychlé konstrukce a bleskově rychlým pristupúm do paměti díky prostorove lokalitě. Nálezem této práce není pouze rychlejší už ta nejrychlejší knihovna Mata ale take použitelnost lineárních alokátorů jako normálně používaná praxe při append-only strukturách, speciálně v výkonově kritických případech.
|
|
|
Transducers in Automata Library Mata
Chocholatý, David ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Implementujeme konečné převodníky do nové rychlé a jednoduché automatové knihovny Mata. Konečné převodníky jsou konečné stavové stoje modelující regulární relace. Naše hlavní použití pro konečné převodníky je kódovaní operací nahrazení (nahrazení slova nebo regulárního vzoru řetězcem). Nový SMT nástroj pro řešení formulí s omezeními nad řetězci Z3-Noodler používá knihovnu Mata jako základ pro jeho rozhodovací proceduru. Noodler potřebuje konečné převodníky k analýze programů manipulujících s řetězci s operacemi nahrazení. Analýzou zmíněných programů používaných ve webových aplikacích se zabrání útokům jako cross-site scripting (XSS) nebo vložení kódu. Hlavní odlišující vlastnosti knihovny Mata zahrnují jednoduchost (jednoduchá k užívání, úpravě a rozšíření) a efektivitu (pracuje rychle). Reprezentaci a algoritmy pro konečné převodníky jsme navrhli s ohledem na tyto vlastnosti knihovny. K reprezentaci konečných převodníků a jejich algoritmů znovupoužijeme a rozšíříme existující datové struktury a algoritmy pro konečné automaty v knihovně Mata. Reprezentace pro konečné převodníky slouží jako společná reprezentace pro konečné převodníky a budoucí reprezentaci automatů využívajících multi-terminálních binárních rozhodovacích diagramů pro práci s velkými abecedami. Navíc rozšíříme návrh o algoritmy pro konstrukci konečných převodníků modelujících operace nahrazení definovaných v SMT-LIB. Nakonec experimentálně vyhodnotíme efektivitu konečných převodníků v knihovně Mata na nové sadě příkladů s operacemi nahrazení z běhů nástroje Z3-Noodler a z řešení problémů nalezení vzoru.
|
|
|
String Constraint Solving Through Parikh Images
Bartoš, Petr ; Havlena, Vojtěch (referee) ; Holík, Lukáš (advisor)
Tato bakalářská práce si klade za cíl implementovat alternativní způsob řešení řetězcových omezení pomocí takzvaného flattening algoritmu, který pomocí Parikhových obrazů a parametrických plochých automatů transformuje řetězcová omezení na lineární vzorce. Takto vyjádřené omezení je možné řešit pomocí výkonných SMT solverů a předchází problémům spjatým s tradičně používanými metodami založených na automatech, jako je například exploze stavového prostoru. Práce popisuje teoretické znalosti potřebné k pochopení algoritmu pro řešení a představuje další state of the art způsoby řešení. Výsledky implementace jsou poté porovnány s ostatnímy solvery na klasických soutěžních benchmarcích. Provedené experimenty ukazují smíšené výsledky – ač navržené řešení nedosahuje podobné rychlosti jako state-of-the-art solvery, přesnost podaproximačního přístupu je relativně příznivá.
|
|
|
Deciding Logic with Automata
Hečko, Michal ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
Tato práce se zaměřuje na rozhodování kvantifikované lineární celočíselné aritmetiky pomocí konečných automatů. Představujeme novou implementaci klasické rozhodovací procedury založené na automatech, která podporuje vstupní formát SMT-LIB. Naše souhrnná prezentace vyvinutého nástroje se zaměřuje na různé aspekty a návrhová rozhodnutí, která hrají významnou roli při výkonu implementace. Za hlavní příčinu celkově slabého výkonu rozhodovací procedury označujeme nedostatek uvažování založeného na teorii a uvádíme řadu levných heuristik, které výrazně zvyšují její rychlost. Představujeme také novou reformulace klasické procedury pracující způsobem shora dolů, která umožňuje provádět uvažování založené na teorii již během konstrukce automatů. Náš nástroj také porovnáváme s nejmodernějšími SMT řešiči a ukazujeme, že naše prototypová implementace je srovnatelná a dokonce překonává současný stav techniky.
|
|
|
Optimizing Inductive Controller Synthesis Methods for POMDPs with Discounted Rewards Properties
Kříž, Ondřej ; Holík, Lukáš (referee) ; Češka, Milan (advisor)
Pravděpodobnostní kontrola modelů je nezbytnou součástí verifikace systémů v různých prostředích. Klíčová limitace nástroje PAYNT, který syntetizuje pravděpodobnostní programy splňující danou specifikaci, leží v jeho zacházení s diskontními vlastnostmi. Tato práce rozšiřuje rámec nástroje STORM, na němž je postaven PAYNT, implementací diskontní iterace hodnot v rámci procesu induktivní syntézy. Diskontní iterace hodnot byla implementována v rámci STORMu, včetně identifikace vhodného prostředí pro řešitele, rozhodovacích segmentů v kódu a Gauss-Seidelovým násobením pro vylepšené výpočetní schopnosti. Nezbytnost použití vzorce v jazyce PRISM v rámci kontroly modelů v PAYNTu představuje problém pro vynechání diskontní transformace, která ztěžuje kontrolu modelu. Proto byla diskontní transformace ponechána s diskontním faktorem blízkým k jedné, a jsou porovnávány hodnoty potenciálních optim, které vrací diskontní a nediskontní iterace hodnot. Tato práce zlepšuje práci PAYNTu a STORMu s diskontními hodnotami a poskytuje základ pro další pokroky ve vývoji PAYNTu a STORMu.
|
|
|
Repetitive Substructures for Efficient Representation of Automata
Šedý, Michal ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Nedeterministické konečné automaty (NKA) jsou široce využívány napříč mnoha odvětvími počítačové vědy, například pro reprezentaci regulárních výrazů, při monitorování vysoko rychlostních sítí, v abstraktním regulárním model checkingu, k verifikaci programů, k rozhodování procedur logik WS1S a WS2S, lineární aritmetiky celých čísel, temporálních logik, nebo dokonce v bioinformatice při vyhledávání sekvencí nukleotidů v DNA. Automaty s velkým množstvím stavů mohou v řadě algoritmů vést k exponenciálnímu nárůstu stavového prostoru. Tento problém lze zmírnit použitím minimalizačních technik slučování stavů a prořezávání hran přechodů. Tyto metody však mohou i přes svou značnou efektivitu zanechat ve výsledných automatech duplicitní podstruktury s ekvivalentními přechody. Existují dokonce typy automatů, které nelze těmito standardními technikami minimalizovat vůbec. Tato práce představuje nový přístup k minimalizaci automatů založený na transformaci NKA na nedeterministický zásobníkový automat (NZA). Tato transformace identifikuje skupinu podobných podstruktur a nahradí ji jednou společnou strukturou (procedurou). Tímto způsobem jsme byli schopni zredukovat automaty až o dalších 67.3%. Myšlenka transformace NKA na NZA lze přirovnat k transformaci sekvenčního programu na program, který využívá funkce a zásobníkem volání.
|
|
|
Automata in Verification
Šmahlíková, Barbora ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
Regulární model checking je technika pro verifikaci nekonečněstavových systémů založená na automatech. Konfigurace systému jsou dány konečným automatem a přechody mezi nimi konečným převodníkem. Algoritmus pro verifikaci libovolných vlastností parametrických systémů specifikovaných v temporální logice LTL(MSO) již existuje. V této práci představíme rozšíření tohoto algoritmu, které umožňuje verifikaci hypervlastností parametrických systémů, tedy vlastností, ve kterých lze explicitně kvantifikovat nad několika cestami v systému. Specifikujeme podmínky, které musí platit pro dvojici tzv. advice bitů (složené z konečného automatu a konečného převodníku), která slouží jako svěděk toho, že je daná vlastnost v systému splněna. Algoritmus představený v této práci je implementovaný v nástroji ParaHyper - jediném existujícím nástroji pro verifikaci hypervlastností parametrických systémů. Tento nástroj využívá SAT solveru pro generování automatů a převodníků. Pokud je nalezen takový pár, který vyhovuje podmínkám pro advice bity, vlastnost je v systému splněna. Bylo provedeno experimentální vyhodnocení představeného algoritmu a bylo zjištěno, že ParaHyper je schopen generovat advice bity pro formule s abecedou až o 4 symbolech, pokud mají automat i převodník nejvýše 2 stavy. Pokud jsou však automat i převodník zadány uživatelem, ParaHyper umí efektivně zkontrolovat, zda vyhovují podmínkám i v případě větších abeced a většího počtu stavů.
|
|
|
Using Reinforcement learning and inductive synthesis for designing robust controllers in POMDPs
Hudák, David ; Holík, Lukáš (referee) ; Češka, Milan (advisor)
Jednou ze současných výzev při sekvenční rozhodováním je práce s neurčitostí, která je způsobena nepřesnými senzory či neúplnou informací o prostředích, ve kterých bychom chtěli dělat rozhodnutí. Tato neurčitost je formálně popsána takzvanými částečně pozorovatelnými Markovskými rozhodovacími procesy (POMDP), které oproti Markovským rozhodovacím procesům (MDP) nahrazují informaci o konkrétním stavu nepřesným pozorováním. Pro rozhodování v takových prostředích je nutno nějakým způsobem odhadovat současný stav a obecně tvorba optimálních politik v takových prostředích není rozhodnutelná. K vyrovnání se s touto výzvou existují dva zcela odlišné přístupy, kdy lze k problému přistupovat úplnými formálními metodami, a to buď s pomocí výpočtu beliefů či syntézou konečně stavových kontrolérů, nebo metodami založenými na nepřesné aproximaci současného stavu, reprezentované především hlubokým zpětnovazebným učením. Zatímco formální přístupy jsou schopné dělat verifikovatelná a robustní rozhodnutí pro malá prostředí, tak zpětnovazebné učení je schopné škálovat na reálné problémy. Tato práce se pak soustředí na spojení těchto dvou odlišných přístupů, kdy navrhuje různé metody jak pro interpretaci výsledku, tak pro vzájemné předávání nápověd. Experimenty v této práci ukazují, že z této symbiózy mohou těžit oba přístupy, ale také že zvolený přístup ke trénování agentů už sám o sobě řádově překonává současné systémy pro trénování agentů na podobných úlohách.
|
|
|
Automata Learning for Fast Detection of Anomalies in Network Traffic
Hošták, Viliam Samuel ; Matoušek, Petr (referee) ; Holík, Lukáš (advisor)
The focus of this thesis is the fast network anomaly detection based on automata learning. It describes and compares several chosen automata learning algorithms including their adaptation for the learning of network characteristics. In this work, various network anomaly detection methods based on learned automata are proposed which can detect sequential as well as statistical anomalies in target communication. For this purpose, they utilize automata's mechanisms, their transformations, and statistical analysis. Proposed detection methods were implemented and evaluated using network traffic of the protocol IEC 60870-5-104 which is commonly used in industrial control systems.
|
|
|
Entrepreneurial Project
Holík, Lukáš ; Smolíková,, Lenka (referee) ; Heralecký, Tomáš (advisor)
The goal of this dissertation is to create a business plan for mr. David Mokrý - owner of café Blue Queen in Boskovice. In a short time he would like to make his business bigger and found another café - pub (Black King).The needed data for creating a project of new successful cafe, which should become the most popular in selected location, I'm going to get by many market analyses, respective by analyses of internal and external neighborhood.
|
guest ::
RSS feed.