Optimal solutions for variants of graph coverage-related problems in software test design.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 184628060 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Optimal solutions for variants of graph coverage-related problems in software test design. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Polański%2C+Artur%22">Polański, Artur</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> artur.polanski@uj.edu.pl</i><br /><searchLink fieldCode="AR" term="%22Roman%2C+Adam%22">Roman, Adam</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> adam.roman@uj.edu.pl</i><br /><searchLink fieldCode="AR" term="%22Zelek%2C+Jakub%22">Zelek, Jakub</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> jakub.zelek@doctoral.uj.edu.pl</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Expert+Systems+with+Applications%22">Expert Systems with Applications</searchLink>. Jun2025, Vol. 277, pN.PAG-N.PAG. 1p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Flowgraphs%22">Flowgraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Test+design%22">Test design</searchLink><br /><searchLink fieldCode="DE" term="%22Software+architecture%22">Software architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Design+software%22">Design software</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=184628060 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.eswa.2025.127216 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 1 StartPage: N.PAG Subjects: – SubjectFull: Polynomial time algorithms Type: general – SubjectFull: Flowgraphs Type: general – SubjectFull: Test design Type: general – SubjectFull: Software architecture Type: general – SubjectFull: Design software Type: general Titles: – TitleFull: Optimal solutions for variants of graph coverage-related problems in software test design. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Polański, Artur – PersonEntity: Name: NameFull: Roman, Adam – PersonEntity: Name: NameFull: Zelek, Jakub IsPartOfRelationships: – BibEntity: Dates: – D: 05 M: 06 Text: Jun2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 09574174 Numbering: – Type: volume Value: 277 Titles: – TitleFull: Expert Systems with Applications Type: main |
| ResultId | 1 |
