|
|
Cluster Data Visualization for InfiSpector
Hais, Vratislav ; Lengál, Ondřej (referee) ; Šimková, Hana (advisor)
Tato bakalářská práce je zaměřena na rozšíření projektu InfiSpector a to o přidání nového grafu, který bude sloužit pro výběr časového intervalu a o úpravu open-source grafů pro sledování provozu mezi servery, které jsme zakomponovali do našeho projektu. Teorie o vizualizaci dat je popsána hned ve druhé kapitole a popisuje hlavní cíle vizualizace dat, základní typy grafů a pravidla, jimiž je vhodné se řídit při vytváření grafu. Dále jsou v této kapitole popsány knihovny, které je možné použít pro vytvoření grafu. Projekt InfiSpector je představen v sekci 3.1, kde je popsán hlavní cíl projektu, použité technologie a knihovny, o kterých jsme uvažovali. Následuje popis implemenetace jednotlivých částí, na jejichž vývoji jsem se přímo podílel. Hlavní část této kapitoly tvoří implementace výše zmiňovaných nových grafů. Závěr obsahuje zhodnocení dosažených výsledků, návrh možných zlepšení a plány do budoucna.
|
|
|
Server for Continuous Integration
Šajdík, Michal ; Fiedor, Tomáš (referee) ; Lengál, Ondřej (advisor)
Tato práce obsahuje popis následujících témat: jaké technologie a principy jsou potřebné pro vytvoření kontinuálního integračního serveru, již existující řešení, proč je potřeba jeden vytvořit a jak integrovat kontinuální integrační server, který byl vytvořen během této práce, na základě informací uvedených v této práci, do pracovního prostředí. Tato práce také ukazuje efekty a některé vedlejší účinky způsobené správnou a nesprávnou konfiguraci uvedeného serveru pro kontinuální integraci. Uvedený server pro kontinuální integraci je také schopen běžet na MS Windows 10 a Linuxu, aniž by bylo nutné přizpůsobit konfiguraci pro konkrétní operační systém.
|
|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
|
|
|
Web Application for Ebook Library Management
Kocman, Radim ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
The aim of this work is to create a web application for ebook library management which builds a web interface around Calibre. A particular focus was given to extensibility and accessibility for a large spectrum of users. The base of the system is the PHP programming language and the Nette Framework library. The text of this thesis describes the complete development process from the analysis of current situation, requirements analysis, system design and user interface design to implementation details and the analysis of testing on a sample of users.
|
|
|
Automata in Infinite-state Formal Verification
Lengál, Ondřej ; Jančar, Petr (referee) ; Veith, Helmut (referee) ; Esparza, Javier (referee) ; Vojnar, Tomáš (advisor)
Tato práce se zaměřuje na konečné automaty nad konečnými slovy a konečnými stromy, a použití těchto automatů při formální verifikaci nekonečně stavových systémů. Práce se nejdříve věnuje rozšíření existujícího přístupu pro verifikaci programů které manipulují s haldou (konkrétně programů s dynamickými datovými strukturami), jenž je založen na stromových automatech. V práci je navrženo několik rozšíření tohoto přístupu, jako například jeho plná automatizace či jeho rozšíření o podporu uspořádaných dat. V práci jsou popsány nové rozhodovací procedury pro dvě logiky, které jsou často používány ve formální verifikaci: pro separační logiku a pro slabou monadickou druhořádovou logiku s následníkem. Obě tyto rozhodovací procedury jsou založeny na převodu jejich problému do automatové domény a následné manipulaci v této cílové doméně. Posledním přínosem této práce je vývoj nových algoritmů k efektivní manipulaci se stromovými automaty, s důrazem na testování inkluze jazyků těchto automatů a manipulaci s automaty s velkými abecedami, a implementace těchto algoritmů v knihovně pro obecné použití. Tyto vyvinuté algoritmy jsou použity jako klíčová technologie, která umožňuje použití výše uvedených technik v praxi.
|
|
|
Data Structure Visualization for Verification Tools
Holubec, Michael ; Lengál, Ondřej (referee) ; Peringer, Petr (advisor)
The aim of my bachelor thesis is an object-oriented design and implementation of a library which will provide a unified interface to a verification tool Predator and other tools for making a vizualization of data structures primarily for debuging purposes. This work analyses some qualities of the verification tool Predator, Forester and CPAchecker. The library offers not only a graphic but also a text-based output in DOT language. The result has been tested by connecting to the verification tool Predator.
|
|
|
Static Analyzer for List Manipulating Programs
Kotoun, Michal ; Lengál, Ondřej (referee) ; Vojnar, Tomáš (advisor)
Creating a software verification tool is a complex task -- one must implement source code parsing, instruction representation, value abstraction, user interface, ... and the analysis itself. Therefore, we decided to create a static analysis framework to prevent unnecessary wheel reinventing by an analyses implementers. We propose a general design of the framework called Angie with a primary focus on usability, and describe a prototype implementation of the framework, including a model analysis based on symbolic memory graphs. Angie is implemented in C++ and uses the LLVM toolchain as the front-end for parsing the source code of analysed programs.
|
|
|
Efficient Algorithms for Counting Automata
Mikšaník, David ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
Čítací automaty (CA) jsou klasické konečné automaty rozšířené o omezené čítače. CA stále reprezentují třídu regulárních jazyků, ale kompaktněji než konečné automaty. Jelikož jsou CA nedávným modelem, chybějí zde efektivní algoritmy implementující různé operace nad nimi. V této práci se primárně soustředíme na existující podtřídu CA zvanou monadické čítací automaty (MCA). Jsou to CA s čítacími smyčkami na třídě znaků, které se často vyskytují v praxi (např. při detekci paketů v síťovém provozu nebo analýze log souborů). Pro tuto podtřídu efektivně vyřešíme problémy prázdnosti a inkluze. Navíc poskytneme dvě rozšíření třídy MCA, které jsou stále podtřídou CA, a vyřešíme pro ně efektivně problém prázdnosti. MCA přirozeně vznikají z regulárních výrazů, které jsou rozšířené o čítací operátory vyskytující se pouze na třídě znaků. Náš algoritmus řešící problém inkluze MCA tedy může být použit jako základ nové metody pro testování inkluze takových regulárních výrazů. Tento přístup jsme experimentálně vyhodnotili na regulárních výrazech z praxe a porovnali s naivní metodou. Experimenty ukazují, že metoda používající náš algoritmus je více odolná proti stavové explozi. Také překonává naivní metodu, pokud regulární výrazy obsahují čítací operátory s velkými mezemi. Podle očekávání, pro jednoduché případy je naivní metoda stále rychlejší než metoda používající náš algoritmus.
|
|
|
Efficient Algorithms for Finite Automata
Hruška, Martin ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Nondeterministic finite automata are used in many areas of computer science, including, but not limited to, formal verification, the design of digital circuits or for the representation of a regular language. Their advantages over deterministic finite automata is that they may represent a language in even exponentially conciser way. However, this advantage may be lost if a naive approach to some operations is taken, in particular for checking language inclusion of a pair of automata, the naive implementation of which performs an explicit determinization of one of the automata. Recently, several new techniques for this operation that avoid explicit determinization (using the so-called antichains or bisimulation up to congruence) have been proposed. The main goal of the presented work is to efficiently implement these techniques as a new extension of the VATA library. The implementation has been evaluated and is superior to other implementations in over 90% of tested cases by the factor of 2 to 100.
|
|
|
A Bit-Vector Compiler for Data-Flow Graphs
Sušovský, Tomáš ; Lengál, Ondřej (referee) ; Smrčka, Aleš (advisor)
The principal goal of this bachelor thesis is to design and implement a tool for compiling data-flow graph models to SMT-LIB format. This thesis builds on the research project HADES developed by VeriFIT research group of the Faculty of Information Technology, Brno University of Technology. The solution uses compiler for generating object model from original graph. Object model can be converted to a SMT-LIB format description including assertions of the desired system properties. Loop unrolling method (with user defined boundary for unrollment) is used for verification of system properties depending on changes in state of model. Capabilities of the developed tool are demonstrated on set of data-flow graphs models. Models cover usage of all elements defined in VAM language (input format) and their combinations. Result of this thesis presents new ways of processing data-flow graphs in VAM format and their verification.
|
guest ::
