Publication detail

Multi-objective Genetic Optimization for Noise-Based Testing of Concurrent Software

DUDKA, V. KŘENA, B. LETKO, Z. PLUHÁČKOVÁ, H. VOJNAR, T.

Original Title

Multi-objective Genetic Optimization for Noise-Based Testing of Concurrent Software

English Title

Multi-objective Genetic Optimization for Noise-Based Testing of Concurrent Software

Type

conference paper

Language

en

Original Abstract

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 thread interleavings examined during repeated test executions provided that a~suitable setting of noise injection heuristics is used. The problem of finding such a~setting, i.e., the so called test and noise configuration search problem (TNCS problem), is not easy to solve. In this paper, we show how to apply a~multi-objective genetic algorithm (MOGA) to the TNCS problem. In particular, we focus on generation of TNCS solutions that cover a~high number of distinct interleavings (especially those which are rare) and provide stable results at the same time. To achieve this goal, we study suitable metrics and ways how to suppress effects of non-deterministic thread scheduling on the proposed MOGA-based approach. We also discuss a~choice of a~concrete MOGA and its parameters suitable for our setting.  Finally, we show on a~set of benchmark programs that our approach provides better results when compared to the commonly used random approach as well as to the sooner proposed use of a~single-objective genetic approach.

English abstract

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 thread interleavings examined during repeated test executions provided that a~suitable setting of noise injection heuristics is used. The problem of finding such a~setting, i.e., the so called test and noise configuration search problem (TNCS problem), is not easy to solve. In this paper, we show how to apply a~multi-objective genetic algorithm (MOGA) to the TNCS problem. In particular, we focus on generation of TNCS solutions that cover a~high number of distinct interleavings (especially those which are rare) and provide stable results at the same time. To achieve this goal, we study suitable metrics and ways how to suppress effects of non-deterministic thread scheduling on the proposed MOGA-based approach. We also discuss a~choice of a~concrete MOGA and its parameters suitable for our setting.  Finally, we show on a~set of benchmark programs that our approach provides better results when compared to the commonly used random approach as well as to the sooner proposed use of a~single-objective genetic approach.

Keywords

Concurrent programs, testing, noise injection, genetic algorithm, multi-objective

RIV year

2014

Released

25.08.2014

Publisher

Springer Verlag

Location

Heidelberg

ISBN

978-3-319-09939-2

Book

SSBSE'14

Edition

Lecture Notes in Computer Science

Edition number

NEUVEDEN

Pages from

107

Pages to

122

Pages count

16

BibTex


@inproceedings{BUT111622,
  author="Vendula {Dudka} and Bohuslav {Křena} and Zdeněk {Letko} and Hana {Šimková} and Tomáš {Vojnar}",
  title="Multi-objective Genetic Optimization for Noise-Based Testing of Concurrent Software",
  annote="
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 thread
interleavings examined during repeated test executions provided that a~suitable
setting of noise injection heuristics is used. The problem of finding such
a~setting, i.e., the so called test and noise configuration search problem (TNCS
problem), is not easy to solve. In this paper, we show how to apply
a~multi-objective genetic algorithm (MOGA) to the TNCS problem. In particular,
we focus on generation of TNCS solutions that cover a~high number of distinct
interleavings (especially those which are rare) and provide stable results at
the same time. To achieve this goal, we study suitable metrics and ways how to
suppress effects of non-deterministic thread scheduling on the proposed
MOGA-based approach. We also discuss a~choice of a~concrete MOGA and its
parameters suitable for our setting.  Finally, we show on a~set of benchmark
programs that our approach provides better results when compared to the commonly
used random approach as well as to the sooner proposed use of a~single-objective
genetic approach.",
  address="Springer Verlag",
  booktitle="SSBSE'14",
  chapter="111622",
  doi="10.1007/978-3-319-09940-8_8",
  edition="Lecture Notes in Computer Science",
  howpublished="print",
  institution="Springer Verlag",
  year="2014",
  month="august",
  pages="107--122",
  publisher="Springer Verlag",
  type="conference paper"
}