Looking For Novelty in Search-Based Software Product Line Testing

• Published in: IEEE transactions on software engineering 2022-07, Vol.48 (7), p.2317-2338
• Main Authors: Xiang, Yi, Huang, Han, Li, Miqing, Li, Sizhe, Yang, Xiaowei
• Format: Article
• Language: English
• Subjects: <named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="kwd" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX"> t</tex-math> <mml:math> <mml:mi>t</mml:mi> </mml:math> <inline-graphic xlink:href="xiang-ieq8-3057853.gif" xlink:type="simple"/> </inline-formula> </named-content>-wise coverage; Algorithms; Correlation; Correlation analysis; Empirical analysis; Fault detection; Frequency modulation; Genetic algorithms; Measurement; novelty search; Product lines; product sampling; Searching; Similarity; similarity-based testing; Software; Software development; Software product line testing; Software product lines; Testing
• ISSN: 0098-5589; 1939-3520
• DOI: 10.1109/TSE.2021.3057853

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 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 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 t -wise coverage. We find that similarity metrics generally have significantly positive correlations with the t t -wise coverage. This well explains why similarity-based testing works, as the improvement on similarity metrics will potentially increase the t 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 t -wise coverage than previ