Ottawa–Carleton
Discrete Mathematics Group

3 December 2008, 11.30am
TB202, Carleton

Covering arrays and context-free grammars have seen extensive use in software test generation. A covering-array algorithm takes a list of domains and generates a subset of the cartesian product of the domains. A grammar-based test generation (GBTG) algorithm takes a grammar G and generates a subset of the language accepted by G. Covering arrays and GBTG are usually applied independently. In this talk, we show that CFG rules and covering array specifications can be freely intermixed, with precise, intuitive semantics and efficient generation. The potential benefits for automated test generation are significant. We present a novel approach for ``tagging'' grammars with specifications for mixed-strength covering arrays, a generalization of conventional covering arrays. We have developed algorithms for test generation and implemented a tool for generating test cases from tagged grammars.