|
|
Analýza a oznámení o nových ResultCloud výsledcích
Iakymets, Bohdan ; Vojnar, Tomáš (oponent) ; Šimková, Hana (vedoucí práce)
Většinou výsledky testů aplikace jsou stejné a proto nenesou žádnou užitečnou informaci. Vývojáři musejí neustále probírat velké množství zbytečných informací, aby našli něco za jímavého. Tedy vývojář potřebuje nástroj pro analýzu testovacích výsledků a v případě nalezení zajimavé informace to oznámí uživateli. Tento nástroj ušetří spoustu času. Zadání této bakalářské práce je navrhnout a implementovat, mechanismus pro analýzu a oznámení uživateli o zajímavých změnách v výsledcích sady testů. Mechanismy musejí být snadno rozšiřitelné a dobře integrovatelné v ResultCloud. Součástí této práce je prostu dování ResultCloud a na základě získaných znalostí rozšíření ResultCloud o analyzátor a oznamovatele. Nástroj je implementován pomocí AngularJS a PHP.
|
|
|
Automata in Decision Procedures and Performance Analysis
Fiedor, Tomáš ; Barnat, Jiří (oponent) ; Radu, Iosif (oponent) ; Vojnar, Tomáš (vedoucí práce)
This thesis focuses on improving the state of the art of automata-based formal analysis and verification techniques for systems with an infinite state space. In the first part of the thesis, we develop two efficient decision procedures for the WS1S logic, both of them exploiting the correspondence between formulae of WS1S logic and finite automata. We start by proposing a novel antichain-based decision procedure which is, however, limited to formulae in the prenex normal form. Later, we generalize the approach to arbitrary formulae by defining the so-called language terms and constructing an on-the-fly procedure dealing with the terms using lazy techniques. In order to achieve an efficient implementation, we propose numerous optimizations (some of these optimization are not limited to our approaches only). We evaluated both our methods with other recent state-of-the art tools. The achieved results are encouraging and show we can extend the usage of WS1S to wider classes of formulae. The second part of the thesis focuses on resource bounds analysis of heap-manipulating programs. We propose a new class of shape norms based on lengths of paths between distinct points in the heap, which we derive automatically from the analysed program. For this class of norms, we introduce a calculus capable of precisely inferring changes of the analysed norms and use it to generate a corresponding integer representation of an input program followed by dedicated state-of-the art resource bounds analysis. We implemented our approach over the shape analysis based on forest-automata, implemented in the Forester tool, and using a well-established resource bounds analyser, implemented in the Loopus tool. In our experimental evaluation, we show that we indeed obtained a powerful analyser that is able to handle some showcase examples that were never analysed fully automatically before.
|
|
|
Statická analýza v nástroji Meta Infer zaměřená na detekci souběhu nad daty
Svobodová, Lucie ; Fiedor, Jan (oponent) ; Vojnar, Tomáš (vedoucí práce)
Modern software systems often use concurrent programs to improve performance and increase efficiency. However, ensuring the reliability and safety of such systems can be challenging due to the increased potential for bugs, including data races, to arise. In this thesis, we introduce a new static data race detector, DarC, designed for programs written in C using the Pthreads library. The proposed detector is implemented as an analyser plugin in Meta Infer, a static analysis framework with an emphasis on compositional, incremental, and consequently highly-scalable analysis. Our approach involves recording a set of accesses that occur in the analysed program along with information about the set of locks held during these accesses. The tool then identifies pairs of accesses that may lead to data races and reports them to the user. Our tool was successfully evaluated on a set of benchmarking programs as well as on real-life projects, showing its potential for effectively detecting data races in C programs.
|
|
|
Pokročilá statická analýza výkonnosti v nástroji Meta Infer
Pavela, Ondřej ; Rogalewicz, Adam (oponent) ; Vojnar, Tomáš (vedoucí práce)
Looper is a static complexity analysis tool for inference of tight upper bounds on the exe- cution cost of programs. It is based on the previously existing Loopus tool which used abstract program model of difference constraints (inequalities of the form + ), which allows for natural abstraction of common loop counter updates = + + and = + 0. Looper was initially proposed and implemented in author’s bachelor’s thesis as a checker for the Meta Infer framework but the tool failed to meet the expectations when tested on real-world code. This master’s thesis proposes a new improved version of Looper that aims at solving the main limitations of the original tool, namely through introduction of interprocedural analysis. Additionally, various extensions target- ing improved precision of the intraprocedural analysis, such as new abstraction algorithm, handling of compound loop conditions and more, were implemented. Moreover, logging, issue reporting and collection of results has been significantly improved. Finally, through extensive experiments with the new Looper version, the ability to analyze real-world code in a more general, scalable and precise way was shown.
|
|
|
Automatické generování šablon změn kódu
Kříž, Daniel ; Vašíček, Ondřej (oponent) ; Vojnar, Tomáš (vedoucí práce)
The aim of this thesis is to propose a method for automatic generation of custom code change patterns in LLVM IR language for DiffKemp, a tool for analyzing semantic differences between version of large scale projects. The goal is to enable automatic generation of changes between versions of a project with values, global variables or structure types. This has been achieved by finding the common pattern between changes and then generating its variants, which differ in usage of global variables and types. The proposed solution was implemented as an extension of DiffKemp and our experimentation on small programs shows that out proposed method is able to yield at least partially satisfactory results.
|
|
|
Vizualizace výsledků statického porovnávání sémantické ekvivalence různých verzí software v jazyce C
Petr, Lukáš ; Fiedor, Tomáš (oponent) ; Vojnar, Tomáš (vedoucí práce)
Cílem této práce je vytvořit přehlednější prezentaci výsledků nástroje DiffKemp sloužícího pro statickou analýzu sémantických rozdílů ve velkých projektech napsaných v jazyce C. V současnosti DiffKemp zobrazuje všechny informace o nalezených rozdílech v nestrukturované textové podobě, což je pro uživatele mnohdy nepřehledné. Pro vyřešení tohoto problému byl v této práci vytvořen nový výstup nástroje DiffKemp, který poskytuje výsledky v serializované podobě pomocí formátu YAML. Tento výstup je následně zpracován a zobrazen pomocí nově vytvořeného prohlížeče výsledků, realizovaného jako webová aplikace pomocí knihovny React, frameworku Bootstrap a balíčku react-diff-view. Dále se práce zaměřila na poskytnutí uživateli dodatečného kontextu ve formě zdrojových kódů analyzovaných funkcí a usnadnění navigace a orientace v nalezených rozdílech a k nim poskytovaných informací jako jsou zásobníky volání. Provedené srovnání nově vytvořeného prohlížeče ukázalo, že usnadňuje uživateli oproti původnímu řešení rozpoznat změny v poskytovaných zásobnících volání a umožňuje mu rychlejší navigaci ve výsledcích a také mezi vztahy nalezených rozdílů a analyzovaných částí.
|
|
|
A Decision Procedure for Strong-Separation Logic
Dacík, Tomáš ; Rogalewicz, Adam (oponent) ; Vojnar, Tomáš (vedoucí práce)
Separation logic (SL) is one of the most successful tools for verification of programs that manipulate dynamically allocated memory. Its expressive power, however, comes at a cost of undecidability when several of its features are combined, especially separating implications. To circumvent this problem, the recently introduced strong-separation logic (SSL) uses a stricter definition of the semantics, making it decidable, while remaining suitable for verification. However, there is currently no implementation of a decision procedure for SSL. In this work, we propose a decision procedure for SSL based on a translation to first-order formulae that can be later solved by a specialised solver. Our experimental results on restricted fragments where SL and SSL coincide show that our approach can effectively solve formulae obtained from verification tools based on SL and also outperform all other existing translation-based decision procedures. Moreover, during our experiments, we found cases of unsoundness of the heuristics implemented in the decision procedure for SL that is a part of the well-known cvc5 SMT solver. Based on our reports, those heuristics has been fixed.
|
|
|
Chaos Testing of the Strimzi Project Using the Litmus Platform
Zrnčík, Henrich ; Smrčka, Aleš (oponent) ; Vojnar, Tomáš (vedoucí práce)
The last decade in software engineering has seen a trend towards automation and abstraction with increasing use of micro-service architecture. The trend towards micro-service architecture has brought with it a need to rethink how we implement software quality assurance. Running micro-services in the cloud with multiple distributed components requires additional management of shared and inter dependent components. This in turn requires additional testing of the system's resilience. A possible answer is chaos engineering, which is often considered the next logical step after end-to-end and integration testing. This thesis will focus on the gaps in testing created by the move to micro-service architecture and how chaos engineering can fill them. In particular it will focus on Apache Kafka deployed onto a kubernetes platform (Strimzi) and how the Litmus framework can be used to implement Chaos testing against this deployment. As our use-case was to have long running Kafkas deployed on kubernetes we had to adapt and extend the Litmus framework and build experiments that could test both long running kafkas and long running kubernetes. This thesis will demonstrate how we did this.
|
|
|
Improvements of the ASMA Tool for Analysis of String Manipulating Programs via Symbolic Automata
Kmenta, Martin ; Lengál, Ondřej (oponent) ; Vojnar, Tomáš (vedoucí práce)
In this work we deal with regular model checking which is a technique for analyzing programs whose state space can be infinite due to dealing with, e.g. unbounded queues, parameters, dynamically linked data structures, recursive procedures, or strings. The goal of this work was to implement improvements to the existing prototype tool ASMA implementing regular model checking over the Microsoft Automata library. We analysed the source code of ASMA and reran analyses of all available benchmark programs. We identified some bottlenecks and have tackled several of them. In particular, we integrated a library containing additional reduction algorithms into ASMA, created several new versions of the reverse concatenation operation, which tuned out to be very costly in the benchmarks, improved the command line interface of ASMA, and implemented some other optimizations for ASMA. The computation time was reduced by 90 % when analysing bigger programs.
|
|
|
Static Analysis Using Facebook Infer Focused on Errors in RCU-Based Synchronisation
Marek, Daniel ; Malík, Viktor (oponent) ; Vojnar, Tomáš (vedoucí práce)
Read Copy Update (RCU) is a synchronization mechanism, found mostly in the Linux kernel. Its sought-after features include almost zero overhead and high speed when reading shared memory. RCU has a set of rules of use, which need to be followed in order for the synchronization to work properly. To the best of our knowledge, there is no analyzer that sufficiently verifies if the RCU rules of use are adhered to. To overcome this, we propose a new analyzer, with the focus on finding violations in the use of RCU rules. The analyzer is based on static analysis and implemented as a module for the static analysis framework Facebook/Meta Infer. This platform was chosen because it provides scalability, which is needed when dealing with such an extensive software as the Linux kernel. The designed analyzer is capable of detecting multiple different ways in which the RCU usage rules can be broken, each causing either a race condition or a deadlock. It is also capable of generating warnings for situations when a deprecated function call is used or when the use of incompatible RCU reader and writer primitives is detected. The analyzer is the first of its kind. It may become a basis for future analyzer development in the field of Read Copy Update. Furthermore, it may be used as a test tool in the Linux kernel development cycle.
|
host ::
RSS.