Looking for novelty in search-based software product line testing

Yi Xiang, Han Huang, Miqing Li, Sizhe Li, Xiaowei Yang

Research output: Contribution to journalArticlepeer-review

152 Downloads (Pure)


Testing software product lines (SPLs) is difficult due to a huge number of possible products to be tested. Recently, there has been a growing interest in similarity-based testing of SPLs, where similarity is used as a surrogate metric for the t-wise coverage. In this context, one of the primary goals is to sample, by optimizing similarity metrics using search-based algorithms, a small subset of test cases (i.e., products) as dissimilar as possible, thus potentially making more t-wise combinations covered. Prior work has shown, by means of empirical studies, the great potential of current similarity-based testing approaches. However, the rationale of this testing technique deserves a more rigorous exploration. To this end, we perform correlation analyses to investigate how similarity metrics are correlated with the t-wise coverage. We find that similarity metrics generally have significantly positive correlations with the t-wise coverage. This well explains why similarity-based testing works, as the improvement on similarity metrics will potentially increase the t-wise coverage. Moreover, we explore, for the first time, the use of the novelty search (NS) algorithm for similarity-based SPL testing. The algorithm rewards “novel” individuals, i.e., those being different from individuals discovered previously, and this well matches the goal of similarity-based SPL testing. We find that the novelty score used in NS has (much) stronger positive correlations with the t-wise overage than previous approaches relying on a genetic algorithm (GA) with a similarity-based fitness function. Experimental results on 31 software product lines validate the superiority of NS over GA, as well as other state-of-the-art approaches, concerning both t-wise coverage and fault detection capacity. Finally, we investigate whether it is useful to combine two satisfiability solvers when generating new individuals in NS, and how the performance of NS is affected by its key parameters. In summary, looking for novelty provides a promising way of sampling diverse test cases for SPLs.
Original languageEnglish
Article number9350184
Pages (from-to)2317-2338
Number of pages22
JournalIEEE Transactions on Software Engineering
Issue number7
Early online date8 Feb 2021
Publication statusPublished - 1 Jul 2022

Bibliographical note

Publisher Copyright:


  • Correlation
  • Fault detection
  • Frequency modulation
  • Measurement
  • Software
  • Software product line testing
  • Software product lines
  • Testing
  • correlation analysis
  • novelty search
  • product sampling
  • similarity-based testing
  • t-wise coverage

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Looking for novelty in search-based software product line testing'. Together they form a unique fingerprint.

Cite this