Optimal string edit distance based test suite reduction for SDL specifications

Gábor Kovács, Gábor Árpád Németh, Mahadevan Subramaniam, Zoltán Pap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We propose a test selection method that provides efficient test sets for systems based on SDL specifications. Our approach builds on previous results of Voung et al. and Feijs et al. on string edit distance based coverage metrics. The method reduces a set of test cases represented in the MSC (Message Sequence Chart) notation, while maintaining the highest possible distance between all pairs of traces defined by the given test set. The algorithm is tunable by a parameter representing the threshold distance for test redundancy. We show that the algorithm runs in polynomial time of the size of the input test set and that it is independent of the size of the system. We implemented and incorporated the algorithm into our SDL-based test selection framework, and evaluated against existing symbol coverage and fault coverage based test selection approaches by conducting experiments on the well-known INRES and Conference Protocol. Results indicate that the string edit distance based method yields similar results in terms of reduction-capability and coverage as the other approaches, but with significantly less complexity.

Original languageEnglish (US)
Title of host publicationSDL 2009
Subtitle of host publicationDesign for Motes and Mobiles - 14th International SDL Forum, Proceedings
Pages82-97
Number of pages16
DOIs
StatePublished - 2009
Event14th International System Design Languages Forum, SDL 2009 - Bochum, Germany
Duration: Sep 22 2009Sep 24 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5719 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International System Design Languages Forum, SDL 2009
CountryGermany
CityBochum
Period9/22/099/24/09

Keywords

  • MSC test cases
  • SDL based test selection
  • String edit distance

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal string edit distance based test suite reduction for SDL specifications'. Together they form a unique fingerprint.

  • Cite this

    Kovács, G., Németh, G. Á., Subramaniam, M., & Pap, Z. (2009). Optimal string edit distance based test suite reduction for SDL specifications. In SDL 2009: Design for Motes and Mobiles - 14th International SDL Forum, Proceedings (pp. 82-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5719 LNCS). https://doi.org/10.1007/978-3-642-04554-7_6