2009-taic-part-k.md

plugin: "pathcrawler"
authors: "Nikolai Kosmatov"
title: "On Complexity of All-Paths Test Generation. From Practice to Theory"
book: "Testing: Academic and Industrial Conference - Practice and Research Techniques (TAIC PART)"
link: "https://ieeexplore.ieee.org/document/5381631"
doi: "10.1109/TAICPART.2009.26"
year: 2009
category: other

Automatic structural testing of programs becomes more and more popular in software engineering. Among the most rigorous structural coverage criteria, all-paths coverage re-quires to generate a set of test cases such that every fea-sible execution path of the program under test is executed by one test case. This article addresses different aspects of computability and complexity of constraint-based all-paths test generation for C programs from the practitioner's point of view, and tries to bridge the gap between mathematical theory and practical computation problems arising in this domain. We focus on two particular classes of programs impor-tant for practice. We show first that for a class containing the simplest programs with strong restrictions, all-paths test generation in polynomial time is possible. For a wider class of programs in which inputs may be used as array indices (or pointer offsets), all-paths test generation is shown to be NP-hard. Some experimental results illustrating test gener-ation time for programs of these classes are provided.