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


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
Number of pages16
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


Conference14th International System Design Languages Forum, SDL 2009


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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