DROPS

Document

SoftwareTesting with Active Learning in a Graph

Authors: Nicolas Baskiotis, Michèle Sebag, and Marie-Claude Gaudel

Published in: Dagstuhl Seminar Proceedings, Volume 8351, Evolutionary Test Generation (2009)

Abstract

Motivated by Structural Statistical Software Testing (SSST), this paper is interested in sampling the feasible execution paths in the control flow graph of the program being tested. For some complex programs, the fraction of feasible paths becomes tiny, ranging in $[10^{-10}, 10^{-5}]$. When relying on the uniform sampling of the program paths, SSST is thus hindered by the non-Markovian nature of the ``feasible path'' concept, due to the long-range dependencies between the program nodes. A divide and generate approach relying on an extended Parikh Map representation is proposed to address this limitation; experimental validation on real-world and artificial problems demonstrates gains of orders of magnitude compared to the state of the art.

Cite as

Nicolas Baskiotis, Michèle Sebag, and Marie-Claude Gaudel. SoftwareTesting with Active Learning in a Graph. In Evolutionary Test Generation. Dagstuhl Seminar Proceedings, Volume 8351, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{baskiotis_et_al:DagSemProc.08351.7,
  author =	{Baskiotis, Nicolas and Sebag, Mich\`{e}le and Gaudel, Marie-Claude},
  title =	{{SoftwareTesting with Active Learning in a Graph}},
  booktitle =	{Evolutionary Test Generation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8351},
  editor =	{Holger Schlingloff and Tanja E. J. Vos and Joachim Wegener},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08351.7},
  URN =		{urn:nbn:de:0030-drops-20149},
  doi =		{10.4230/DagSemProc.08351.7},
  annote =	{Keywords: Structural Statistical Software Testing, Active Learning, Control Flow Graph, Feaisble Paths, Parikh maps.}
}

Document

DOI: 10.4230/DagSemProc.07161.9

Structural Sampling for Statistical Software Testing

Authors: Nicolas Baskiotis and Michele Sebag

Published in: Dagstuhl Seminar Proceedings, Volume 7161, Probabilistic, Logical and Relational Learning - A Further Synthesis (2008)

Abstract

Structural Statistical Software Testing exploits the control flow graph of the program being tested to construct test cases. While test cases can easily be extracted from {em feasible paths} in the control flow graph, that is, paths which are actually exerted for some values of the program input, the feasible path region is a tiny fraction of the graph paths (less than $10^{-5}]$ for medium size programs). The S4T algorithm presented in this paper aims to address this limitation; as an Active Relational Learning Algorithm, it uses the few feasible paths initially available to sample new feasible paths. The difficulty comes from the non-Markovian nature of the feasible path concept, due to the long-range dependencies between the nodes in the control flow graph. Experimental validation on real-world and artificial problems demonstrates significant improvements compared to the state of the art.

Cite as

Nicolas Baskiotis and Michele Sebag. Structural Sampling for Statistical Software Testing. In Probabilistic, Logical and Relational Learning - A Further Synthesis. Dagstuhl Seminar Proceedings, Volume 7161, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{baskiotis_et_al:DagSemProc.07161.9,
  author =	{Baskiotis, Nicolas and Sebag, Michele},
  title =	{{Structural Sampling for Statistical Software Testing}},
  booktitle =	{Probabilistic, Logical and Relational Learning - A Further Synthesis},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7161},
  editor =	{Luc de Raedt and Thomas Dietterich and Lise Getoor and Kristian Kersting and Stephen H. Muggleton},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07161.9},
  URN =		{urn:nbn:de:0030-drops-13875},
  doi =		{10.4230/DagSemProc.07161.9},
  annote =	{Keywords: Active Relational Learning, Software Testing, Autonomic Computing, Parikh Maps}
}

Search Results

Documents authored by Baskiotis, Nicolas

SoftwareTesting with Active Learning in a Graph

Abstract

Cite as

Structural Sampling for Statistical Software Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message