Review of Introduction to Combinatorial Testing

I received a copy of this book from ACM SIGsoft Software Engineering Notes (SEN) in exchange for reviewing it.

Introduction to Combinatorial Testing
 Written by D. Richard Kuhn, Raghu N. Kacker, and Yu Lei
and published by CRC Press, ©2013, (paperback), 978-1466552296, 319 pp., $71.95.

The book is the most comprehensive introduction to the technique of combinatorial testing I’ve seen.  It’s an interesting amalgamation of academic and very practical test guidance for using combinatorial testing.  The book is actually a compendium from several authors. The examples can require a bit of study to actually glean what the authors are expressing.  Some chapters could easily be skipped by practitioners focused just on using the technique.

Most chapters have figures, tables of inputs, outputs, or tests, and sometimes pseudocode.  Each chapter ends with review questions and answers which help the reader judge their understanding of the material.

Even if the literature is inconsistent, it would have been nice if the authors had chosen a single nomenclature across the book, instead of for each chapter.  For example, Chapter 1 defines “covering array CA(N, n, s, t)”  while Chapter 14 defines “a fixed-value covering array denoted by CA(N,v^k,t)”.  Similarly, Chapter 14 states “Methods for constructing CAs can be put into three categories: (1) algebraic methods … (2) metaheuristic methods … (3) greedy search methods”, while Chapter 15 tells us “covering array construction can be classified as either computational or algebraic”, and later breaks algebraic into “computing a mathematical function” and “recursive construction”.

The first four chapters introduce the concept and illustrate combinatorial testing. Chapter 1 introduces a lot of foundation quickly which may be overwhelming for those not used to formalism and mathematics.  Appendix A also provides some of the mathematical background.  Chapter 2 gives examples and rationale, along with Appendix B’s empirical data on software failures.  Chapters 3 and 4 illustrate configuration testing and input testing with the free ACTS tool from NIST. ACTS is also further described in Appendix D.

Chapter 5, Test Parameter Analysis, uses classification tree method (CTM) for this critical step before being able to do combinatorial testing.  It also addresses the number of tests versus known error patterns. It points to the practical need to identify “missing, infeasible, and ineffectual combinations”, and points out “There are few bad tests – but a lot of unproductive ones”.

Chapter 6, Managing System State, introduces yet another notation, direct product block (DPB) which is more understandable to computers than to humans.  This input mechanism for the commercial TestCover tool helps illustrate multiple models for testing UML state machines.

Chapter 7 on measuring combinatorial coverage seems more theoretical (proposed measures), than practical (which measure helps most in empirical testing).  It also makes reference to the Best Choice Strategy papers that discounted the effects of fault masking as described elsewhere in this book.

Chapter 8, Test Suite Prioritization, presents the method and empirical results from ordering tests based on combinatorial covering.  The Combinatorial-based Prioritization for User-session-based Testing (CPUT) tool is described for creating test suites from user logs of real behavior.

Chapter 9 gives practical guidance about when to choose random values versus covering arrays.  Chapter 10 describes covering subsets for the factorial combination of sequences, but without evidence of the error finding effectiveness of this approach.

Chapter 11, Assertion-based Testing, and Chapter 12, Model-based Testing, attempt to address the oracle problem and are not specific to combinatorial testing.  If you go to the trouble of using a symbolic model verifier (SMV), you generally can do advanced test generation, rather than just predicting output from combinatorial input as described here.

Chapter 13 “introduces the fault localization problem, describes the basic framework for fault localization using adaptive testing, and discusses how some of these approaches might be implemented.”  Unfortunately, no empirical data comparing these various approaches, or for delta debugging, are given to guide the practitioner in which to choose.

Chapter 14 gives a nice bit of history and helps distinguish the sometimes-confused orthogonal arrays from covering arrays.

Chapter 15 is background for those who want to understand the algorithms used in the tools.

While Appendix C gives pointers to several tools, I would like to have seen more pointers to practical materials, such as the list of tools at http://www.pairwise.org/tools.asp, and the Domain Testing Workbook by Cem Kaner which complements the multiple, short introductions given to equivalence classes, boundary value analysis, etc.  The examples are sometimes small and can thus be misleading, e.g., Table 6.2 “valid calendar dates” does not appropriately account for century leap years such as 1900 and 2100.

The authors have done little to reduce the burden on the reader of having different nomenclatures in different chapters, but overall I liked the book, and it provided me greater depth and breadth of understanding combinatorial testing.