Abstract

In this paper, we develop a combinatorial testing technique for tree-structured test models. First, we generalize our previous test models for combinatorial testing based on AND-XOR trees with constraints limited to a syntactic subset of propositional logic, to allow for constraints in full propositional logic. We prove that the generalized test models are strictly more expressive than the limited ones. Then we develop an algorithm for combinatorial testing for the generalized models, and show its correctness and computational complexity. We apply a tool based on our algorithm to an actual ticket gate system that is used by several large transportation companies in Japan. Experimental results show that our technique outperforms existing techniques.

BibTeX

@inproceedings{Kitamura15,
author    = "Takashi Kitamura and Akihisa Yamada and Goro Hatayama and
             Cyrille Artho and Eun-Hye Choi and Ngoc Thi Bich Do and
             Yutaka Oiwa and Shinya Sakuragi",
title     = "Combinatorial Testing for Tree-Structured Test Models with
             Constraints",
booktitle = "Proceedings of the 2015 IEEE International Conference on
             Software Quality, Reliability & Security (QRS 2015)",
pages     = "141--150",
year      = 2015
}