Detail výsledku

Testing of Concurrent Programs with Genetic Algorithms

DUDKA, V.; KŘENA, B.; LETKO, Z.; UR, S.; VOJNAR, T. Testing of Concurrent Programs with Genetic Algorithms. Lecture Notes in Computer Science, 2012, roč. 2012, č. 7515, s. 152-167. ISSN: 0302-9743.
Typ
článek v časopise
Jazyk
česky
Autoři
Dudka Vendula, Ing., UITS (FIT)
Křena Bohuslav, Ing., Ph.D., UITS (FIT)
Letko Zdeněk, Ing., Ph.D., UITS (FIT)
Ur Shmuel
Vojnar Tomáš, prof. Ing., Ph.D., UITS (FIT)
Abstrakt

Metoda vkládání šumu ovlivňuje plánování vláken za účelem zvýšení počtu legálních proložení těchto vláken během testovacího procesu. Existuje mnoho rozmanitých typů heuristik pro vkládání šumu, často s několika parametry, jejichž nastavení s ohledem na maximální efektivitu šumu je často obtížné. V tomto článku navrhujeme novou aplikaci genetických algoritmů tak, aby hledaly vhodné typy heuristik pro vkládání šumu a jejich parametry s ohledem na daný testovaný software. Tato úloha je definována jako problém nastavení testu a šumu. Následně je diskutována problematika reprezentace instancí tohoto problému, vhodných účelových funkcí a parametrů genetických algoritmů při řešení této úlohy. Navržený přístup je vyhodnocen na několika příkladech. Srovnání ukazuje, že nový přístup poskytuje mnohem lepší výsledky než dosud používaný přístup založený na náhodném nastavování heuristik pro vkládání šumu.

Abstrakt anglicky

Noise injection disturbs the scheduling of program threads in order to increase the probability that more of their different legal interleavings occur during the testing process. However, there exist many different types of noise heuristics with many different parameters that are not easy to set such that noise injection is really efficient. In this paper, we propose a new way of using genetic algorithms to search for suitable types of noise heuristics and their parameters. This task is formalized as the test and noise configuration search problem in the paper, followed by a discussion of how to represent instances of this problem for genetic algorithms, which objectives functions to use, as well as parameter tuning of genetic algorithms when solving the problem. The proposed approach is evaluated on a set of benchmarks, showing that it provides significantly better results than the so far preferred random noise injection.

Klíčová slova anglicky

genetic algorithms, noise injection, testing, multi-threaded programs

URL
Rok
2012
Strany
152–167
Časopis
Lecture Notes in Computer Science, roč. 2012, č. 7515, ISSN 0302-9743
BibTeX
@article{BUT96964,
  author="Vendula {Dudka} and Bohuslav {Křena} and Zdeněk {Letko} and Shmuel {Ur} and Tomáš {Vojnar}",
  title="Testing of Concurrent Programs with Genetic Algorithms",
  journal="Lecture Notes in Computer Science",
  year="2012",
  volume="2012",
  number="7515",
  pages="152--167",
  issn="0302-9743",
  url="http://www.fit.vutbr.cz/~vojnar/Publications/ssbse-12.pdf"
}
Projekty
Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů, GAČR, Doktorské granty, GD102/09/H042, zahájení: 2009-01-30, ukončení: 2012-12-31, ukončen
Pokročilé bezpečné, spolehlivé a adaptivní IT, VUT, Vnitřní projekty VUT, FIT-S-11-1, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Práce se složitými datovými strukturami a paralelismem v prostředí Rich Model Toolkit, MŠMT, COST, OC10009, zahájení: 2010-01-01, ukončení: 2012-12-31, řešení
Statická a dynamická verifikace programů s pokročilými rysy paralelismu a neomezenosti, GAČR, Standardní projekty, GAP103/10/0306, zahájení: 2010-01-01, ukončení: 2013-12-31, řešení
Verifikace a optimalizace počítačových systémů, VUT, Vnitřní projekty VUT, FIT-S-12-1, zahájení: 2012-01-01, ukončení: 2014-12-31, ukončen
Výzkumné skupiny
Pracoviště
Nahoru