On Combinatorial Design-based Test Generation




Journal Title

Journal ISSN

Volume Title




Combinatorial testing (CT) is a testing technique that focuses on testing the interactions between the various factors of a given system. CT shows great potential for detecting faults, especially those that can only be detected by the specific value combinations of multiple factors (multi-factor faults). However, CT has not been widely adopted as a standard testing technique in the industry, which raises three main research questions that need to be answered: 1) how does CT perform in the real world; 2) can CT be applied to IoT systems – one of the most complicated types of systems need to be tested in the modern era; and 3) how should CT input models1 be constructed to ensure the superior fault detection effectiveness, especially when the testing budget is limited. This dissertation presents an empirical study of CT’s real-world effectiveness and proposes two approaches2 – CT-IoT and CT-Star – to answer the questions above. In the conducted empirical study, the performance of CT in terms of fault detection effectiveness was evaluated on eleven functionalities of five industrial systems with real faults using real-world settings. We compared the faults detected by CT with those detected by the techniques used by the in-house testing teams to evaluate whether CT can outperform industrial favored techniques. The results suggest that, despite some challenges, CT is an effective technique to detect faults, especially multi-factor faults, of software systems in industrial settings. Regarding applying CT to test IoT systems, a comprehensive literature review is conducted to evaluate the state-of-the-art approaches. It is discovered that applying CT to test IoT systems is challenging because CT cannot model IoT systems for testing. Moreover, the inability to handle complex constraints of IoT systems also hinders CT’s application to IoT systems. In response, a combinatorial testing path selection framework for IoT systems called CT-IoT is proposed. CTIoT systematically identifies and recommends testing paths in IoT systems for effective testing. Four coverage criteria that can help testers evaluate the testing thoroughness for IoT systems are also proposed. CT-IoT is evaluated on two real-world IoT systems in terms of coverage achievements. The results show the superiority of CT-IoT over a random approach. Last but not least, CT can be ineffective in detecting faults. If specific fault-triggering values are not included in the input model, the faults that can only be detected by the combinations of those values will remain undetected. If a systematic approach is not used to construct effective input models, the tester may struggle with mediocre testing results against real-world systems. A CT input model construction approach, called CT-Star, is proposed to create superior input models that can detect faults systematically. CT-Star includes various testing techniques to help practitioners create superior input models. It can also automatically tune the input model to reduce the number of test cases generated, helping practitioners meet limited testing budgets.



Computer Science