View in EDS

Optimal solutions for variants of graph coverage-related problems in software test design.

Saved in:
Bibliographic Details
Title: Optimal solutions for variants of graph coverage-related problems in software test design.
Authors: Polański, Artur1 (AUTHOR) artur.polanski@uj.edu.pl, Roman, Adam1 (AUTHOR) adam.roman@uj.edu.pl, Zelek, Jakub1 (AUTHOR) jakub.zelek@doctoral.uj.edu.pl
Source: Expert Systems with Applications. Jun2025, Vol. 277, pN.PAG-N.PAG. 1p.
Subjects: Polynomial time algorithms, Flowgraphs, Test design, Software architecture, Design software
Abstract: Graph-based coverage criteria, such as Edge Coverage or N-Switch Coverage are widely used in software testing. Classical problem of designing a set of test cases that achieves a given coverage criterion concentrates on providing the minimum number of test cases and ignores different types of costs that arise in real-world scenarios. In this paper, we describe some natural factors that affect the cost of testing. We define six optimization criteria based on these factors, and for each of them, we either construct a polynomial algorithm providing an optimal solution to the test design problem, or we prove that a criterion makes the problem NP-complete. For the polynomial cases, we show how to modify the Control Flow Graph so that a classical Chinese Postman Problem can be applied to achieve a given optimization criterion for the Edge Coverage. We also show how to use the deBruijn graphs to make the solution work for a generalized, N-Switch Coverage criterion. We implement all the algorithms and empirically verify their performance in a series of experiments, comparing our approach with the existing tools against several optimization criteria. • Six optimality criteria defined for test case design considering real-world cost factors. • For each criterion we provide either polynomial-time algorithm or proof of NP-completeness. • For polynomial cases we design solutions optimal in the sense of corresponding criterion. • We provide Python implementation for polynomial cases. • Empirical results confirm the effectiveness of our solution. [ABSTRACT FROM AUTHOR]
Copyright of Expert Systems with Applications is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Graph-based coverage criteria, such as Edge Coverage or N-Switch Coverage are widely used in software testing. Classical problem of designing a set of test cases that achieves a given coverage criterion concentrates on providing the minimum number of test cases and ignores different types of costs that arise in real-world scenarios. In this paper, we describe some natural factors that affect the cost of testing. We define six optimization criteria based on these factors, and for each of them, we either construct a polynomial algorithm providing an optimal solution to the test design problem, or we prove that a criterion makes the problem NP-complete. For the polynomial cases, we show how to modify the Control Flow Graph so that a classical Chinese Postman Problem can be applied to achieve a given optimization criterion for the Edge Coverage. We also show how to use the deBruijn graphs to make the solution work for a generalized, N-Switch Coverage criterion. We implement all the algorithms and empirically verify their performance in a series of experiments, comparing our approach with the existing tools against several optimization criteria. • Six optimality criteria defined for test case design considering real-world cost factors. • For each criterion we provide either polynomial-time algorithm or proof of NP-completeness. • For polynomial cases we design solutions optimal in the sense of corresponding criterion. • We provide Python implementation for polynomial cases. • Empirical results confirm the effectiveness of our solution. [ABSTRACT FROM AUTHOR]
ISSN:09574174
DOI:10.1016/j.eswa.2025.127216