The test suite generation problem: Optimal instances and their implications

详细信息    查看全文

• 作者：Christine T. Cheng
• 关键词：Generating test suites ; Mixed covering arrays for hypergraphs ; Orthogonal arrays
• 刊名：Discrete Applied Mathematics
• 出版年：2007
• 出版时间：15 September 2007
• 年：2007
• 卷：155
• 期：15
• 页码：1943-1957
• 全文大小：275 K

文摘

In the test suite generation (TSG) problem for software systems, 304224353954b7ad9e1f4c45103b5d55""> is a set of n input parameters where each has κ(I) data values, and is a collection of subsets of where the interactions of the parameters in each are thought to affect the outcome of the system. A test case for is an n-tuple (t₁,t₂,…,t_n) that specifies the value of each input parameter in 4f13b6b00074b022"">. The goal is to generate a smallest-sized test suite (i.e., a set of test cases) that covers all combinations of each . The decision version of TSG is known to be NP-complete.

In this paper, we present new families of for which optimal test suites can be constructed efficiently. They differ from the ones already known by the way we characterize and κ. We then use these instances to generate test suites for arbitrary software systems. When each has |O|=2, the sizes of the test suite are guaranteed to be at most , matching the current best bound for this problem. Our constructions utilize the structure of and κ; consequently, the less “complex” and κ are, the better are the bounds on the sizes of the test suites.