|
|
Test Optimization by Search-Based Algorithms
Starigazda, Michal ; Holík, Lukáš (referee) ; Letko, Zdeněk (advisor)
Testing of multi-threaded programs is a demanding work due to the many possible thread interleavings one should examine. The noise injection technique helps to increase the number of tested thread interleavings by noise injection to suitable program locations. This work optimizes meta-heuristics search techniques in the testing of concurrent programs by utilizing deterministic heuristic in the application of genetic algorithms in a space of legal program locations suitable for the noise injection. In this work, several novel deterministic noise injection heuristics without dependency on the random number generator are proposed in contrary to the most of currently used heuristic. The elimination of the randomness should make the search process more informed and provide better, more optimal, solutions thanks to increased stability in the results provided by novel heuristics. Finally, a benchmark of programs, used for the evaluation of novel noise injection heuristics is presented.
|
|
|
Application of Genetic Algorithms and Data Mining in Noise-based Testing of Concurrent Software
Šimková, Hana ; Kofroň, Jan (referee) ; Lourenco, Joao (referee) ; Vojnar, Tomáš (advisor)
Tato práce navrhuje zlepšení výkonu testování programů použitím technik dolování z dat a genetických algoritmů při testování paralelních programů. Paralelní programování se v posledních letech stává velmi populárním i přesto, že toto programování je mnohem náročnějsí než jednodušší sekvenční a proto jeho zvýšené používání vede k podstatně vyššímu počtu chyb. Tyto chyby se vyskytují v důsledku chyb v synchronizaci jednotlivých procesů programu. Nalezení takových chyb tradičním způsobem je složité a navíc opakované spouštění těchto testů ve stejném prostředí typicky vede pouze k prohledávání stejných prokládání. V práci se využívá metody vstřikování šumu, která vystresuje program tak, že se mohou objevit některá nová chování. Pro účinnost této metody je nutné zvolit vhodné heuristiky a též i hodnoty jejich parametrů, což není snadné. V práci se využívá metod dolování z dat, genetických algoritmů a jejich kombinace pro nalezení těchto heuristik a hodnot parametrů. V práci je vedle výsledků výzkumu uveden stručný přehled dalších Technik testování paralelních programů.
|
|
|
Testing of Concurrent Software with Noise
Kotyz, Jan ; Smrčka, Aleš (referee) ; Letko, Zdeněk (advisor)
The aim of this bachelor thesis is to create a tool for testing of concurrent software written in Python. This testing tool monitors run of the concurrent program with bytecode instrumentation and performs noise injection at selected locations. This results in a dramatic increase in the probability of bug manifestation and therefore allows more efficient detection of bugs typical for concurrent software. The result of this thesis is concurrency testing tool for Python.
|
|
|
Performance Analysis Based on Noise Injection
Liščinský, Matúš ; Malík, Viktor (referee) ; Fiedor, Tomáš (advisor)
Táto práca predstavuje nástroj Perun-Blower, využívajúci perfblowing techniku: vkladanie šumu do funkcií testovaného programu a nasledovné vyhodnotenie vplyvu šumu na výkon programu na základe zozbieraných časových údajov týchto funkcií z behu programu. Implementácia je postavená na dynamickej binárnej inštrumentácii nástroja Pin. Zameriavame sa na hľadanie funkcií, ktoré majú vysoký vplyv na výkon a rovnako tak aj odhad potenciálneho zrýchlenia behu vlákna pri optimalizácii konkrétnej funkcie. Naviac sme rozšírili existujúci Trace collector používaný v nástroji Perun na zbieranie časových dát funkcií, o nový tzv. engine, ktorý je založený práve na nástroji Pin. Funkčnosť implementácie sme otestovali na dvoch netriviálnych projektoch, kde sme dokázali nájsť funkcie (1) so značným vplyvom na výkon, (2) s najvýznamnejším optimalizačným prínosom a (3) funkcie, ktorých degradácia spôsobí, že vykonávanie programu sa neskončí ani po niekoľkých hodinách.
|
|
|
Practical Methods of Automated Verification of Concurrent Programs
Fiedor, Jan ; Arcaini, Paolo (referee) ; Farchi, Eitan (referee) ; Vojnar, Tomáš (advisor)
V dnešní době jsou vícevláknové programy běžné a s nimi i chyby v souběžnosti. Během posledních let bylo vytvořeno mnoho technik pro detekci takovýchto chyb, a i přesto mají vývojáři softwaru problém nalézt správné nástroje pro analýzu svých programů. Důvod je jednoduchý, fungující neznamená vždy praktický. Hodně nástrojů implementujících detekční techniky je obtížně použitelných, přizpůsobených pro konkrétní typy programů nebo synchronizace, nebo špatně škálují, aby zvládly analyzovat rozsáhlý software. Pro některé typy chyb v souběžnosti dokonce ani neexistují nástroje pro jejich detekci, i přesto že vývojáři softwaru na tyto chyby často narážejí ve svých programech. Hlavním cílem této práce je navrhnout nové techniky pro detekci chyb ve vícevláknových programech. Tyto techniky by měly být schopny analyzovat rozsáhlé programy, umožnit detekci méně studovaných typů chyb v souběžnosti, a podporovat širokou škálu programů s ohledem na to, jaké programové konstrukce používají.
|
|
|
Analysis and Testing of Concurrent Programs
Letko, Zdeněk ; Lourenco, Joao (referee) ; Sekanina, Lukáš (referee) ; Vojnar, Tomáš (advisor)
V disertační práci je nejprve uvedena taxonomie chyb v souběžném zpracování dat a přehled technik pro jejich dynamickou detekci. Následně jsou navrženy nové metriky pro měření synchronizace a souběžného chování programů společně s metodologií jejich odvozování. Tyto techniky se zejména uplatní v testování využívajícím techniky prohledávání prostoru a v saturačním testování. Práce dále představuje novou heuristiku vkládání šumu, jejímž cílem je maximalizace proložení instrukcí pozorovaných během testování. Tato heuristika je porovnána s již existujícími heuristikami na několika testech. Výsledky ukazují, že nová heuristika překonává ty existující v určitých případech. Nakonec práce představuje inovativní aplikaci stochastických optimalizačních algoritmů v procesu testování vícevláknových aplikací. Principem metody je hledání vhodných kombinací parametrů testů a metod vkládání šumu. Tato metoda byla prototypově implementována a otestována na množině testovacích příkladů. Výsledky ukazují, že metoda má potenciál vyznamně vylepšit testování vícevláknových programů.
|
|
|
Fine-Grain Noise-Injection Heuristics for SearchBestie Infrastructure
Kozák, David ; Smrčka, Aleš (referee) ; Křena, Bohuslav (advisor)
The main topic of this thesis is testing of concurrent Java programs. Concurrency errors often manifest rarely. To increase a chance to spot such errors, a technique called noise injection can be used. This technique inserts extra instruction into the application under test to disturb the scheduler and thus to explore less common thread scheduling. Because noise injection can be parameterized in many ways, a tool called SearchBestie was created to handle noise-based testing as a search problem. SearchBestie used a tool called Contest for bytecode instrumentation and test execution. However, the development of ConTest has been discontinued and therefore an alternative tool was necessary. In the first part of this thesis, SearchBestie was connected with a tool called RoadRunner, which replaced ConTest. Afterwards new fine-grain noise-injection heuristics have been proposed and implemented. Experiments proved that these heuristics achieve better results in most cases.
|
|
|
Performance Analysis Based on Noise Injection
Liščinský, Matúš ; Malík, Viktor (referee) ; Fiedor, Tomáš (advisor)
Táto práca predstavuje nástroj Perun-Blower, využívajúci perfblowing techniku: vkladanie šumu do funkcií testovaného programu a nasledovné vyhodnotenie vplyvu šumu na výkon programu na základe zozbieraných časových údajov týchto funkcií z behu programu. Implementácia je postavená na dynamickej binárnej inštrumentácii nástroja Pin. Zameriavame sa na hľadanie funkcií, ktoré majú vysoký vplyv na výkon a rovnako tak aj odhad potenciálneho zrýchlenia behu vlákna pri optimalizácii konkrétnej funkcie. Naviac sme rozšírili existujúci Trace collector používaný v nástroji Perun na zbieranie časových dát funkcií, o nový tzv. engine, ktorý je založený práve na nástroji Pin. Funkčnosť implementácie sme otestovali na dvoch netriviálnych projektoch, kde sme dokázali nájsť funkcie (1) so značným vplyvom na výkon, (2) s najvýznamnejším optimalizačným prínosom a (3) funkcie, ktorých degradácia spôsobí, že vykonávanie programu sa neskončí ani po niekoľkých hodinách.
|
|
|
Application of Genetic Algorithms and Data Mining in Noise-based Testing of Concurrent Software
Šimková, Hana ; Kofroň, Jan (referee) ; Lourenco, Joao (referee) ; Vojnar, Tomáš (advisor)
Tato práce navrhuje zlepšení výkonu testování programů použitím technik dolování z dat a genetických algoritmů při testování paralelních programů. Paralelní programování se v posledních letech stává velmi populárním i přesto, že toto programování je mnohem náročnějsí než jednodušší sekvenční a proto jeho zvýšené používání vede k podstatně vyššímu počtu chyb. Tyto chyby se vyskytují v důsledku chyb v synchronizaci jednotlivých procesů programu. Nalezení takových chyb tradičním způsobem je složité a navíc opakované spouštění těchto testů ve stejném prostředí typicky vede pouze k prohledávání stejných prokládání. V práci se využívá metody vstřikování šumu, která vystresuje program tak, že se mohou objevit některá nová chování. Pro účinnost této metody je nutné zvolit vhodné heuristiky a též i hodnoty jejich parametrů, což není snadné. V práci se využívá metod dolování z dat, genetických algoritmů a jejich kombinace pro nalezení těchto heuristik a hodnot parametrů. V práci je vedle výsledků výzkumu uveden stručný přehled dalších Technik testování paralelních programů.
|
|
|
Practical Methods of Automated Verification of Concurrent Programs
Fiedor, Jan ; Arcaini, Paolo (referee) ; Farchi, Eitan (referee) ; Vojnar, Tomáš (advisor)
V dnešní době jsou vícevláknové programy běžné a s nimi i chyby v souběžnosti. Během posledních let bylo vytvořeno mnoho technik pro detekci takovýchto chyb, a i přesto mají vývojáři softwaru problém nalézt správné nástroje pro analýzu svých programů. Důvod je jednoduchý, fungující neznamená vždy praktický. Hodně nástrojů implementujících detekční techniky je obtížně použitelných, přizpůsobených pro konkrétní typy programů nebo synchronizace, nebo špatně škálují, aby zvládly analyzovat rozsáhlý software. Pro některé typy chyb v souběžnosti dokonce ani neexistují nástroje pro jejich detekci, i přesto že vývojáři softwaru na tyto chyby často narážejí ve svých programech. Hlavním cílem této práce je navrhnout nové techniky pro detekci chyb ve vícevláknových programech. Tyto techniky by měly být schopny analyzovat rozsáhlé programy, umožnit detekci méně studovaných typů chyb v souběžnosti, a podporovat širokou škálu programů s ohledem na to, jaké programové konstrukce používají.
|
guest ::
