Novel Algorithm to Solve the Constrained Path-Based Testing Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00388269" target="_blank" >RIV/68407700:21230/25:00388269 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/ICSTW64639.2025.10962488" target="_blank" >https://doi.org/10.1109/ICSTW64639.2025.10962488</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ICSTW64639.2025.10962488" target="_blank" >10.1109/ICSTW64639.2025.10962488</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Novel Algorithm to Solve the Constrained Path-Based Testing Problem

Popis výsledku v původním jazyce

Constrained Path-based Testing (CPT) is a technique that extends traditional path-based testing by adding constraints on the order or presence of specific sequences of actions in the tests of System Under Test (SUT) processes. Through such an extension, CPT enhances the ability of the model to capture more real-life situations. In CPT, we define four types of constraints that either enforce or prohibit the use of a pair of actions in the resulting test set. We propose a novel Constrained Path-based Testing Composition (CPC) algorithm to solve the Constrained Path-based Testing Problem. We compare the results returned by the CPC algorithm with two alternatives, (1) the Filter algorithm, which solves the CPT problem in a greedy manner, and (2) the Edge algorithm, which generates a set of test cases that satisfy edge coverage. We evaluated the algorithms on 200 problem instances, with the CPC algorithm returning test sets (T) that have, on average, 350 edges, which is 2.4% and 11.1% shorter than the average number of edges in T returned by the Filter algorithm and the Edge algorithm, respectively. Regarding the compliance of the generated T with the constraints, the CPC algorithm produced T that satisfied the constraints in 95% of the cases, the Filter algorithm in 45% cases, and the Edge algorithm returned T that satisfied the constraints only for 6% SUT instances. Regarding the coverage of edges, the CPC algorithm returned test sets that contained, on average, 91.5% of edges in the graphs, while for T returned by the Filter algorithm, it was 90.8% edges. When comparing the average results of the edge coverage criterion and the fulfillment of the constraint criterion by individual algorithms, we consider the incomplete edge coverage achieved by the CPC algorithm and, at the same time, 95% fulfillment of the graph constraints to be a reasonable compromise.

Název v anglickém jazyce

Novel Algorithm to Solve the Constrained Path-Based Testing Problem

Popis výsledku anglicky

Constrained Path-based Testing (CPT) is a technique that extends traditional path-based testing by adding constraints on the order or presence of specific sequences of actions in the tests of System Under Test (SUT) processes. Through such an extension, CPT enhances the ability of the model to capture more real-life situations. In CPT, we define four types of constraints that either enforce or prohibit the use of a pair of actions in the resulting test set. We propose a novel Constrained Path-based Testing Composition (CPC) algorithm to solve the Constrained Path-based Testing Problem. We compare the results returned by the CPC algorithm with two alternatives, (1) the Filter algorithm, which solves the CPT problem in a greedy manner, and (2) the Edge algorithm, which generates a set of test cases that satisfy edge coverage. We evaluated the algorithms on 200 problem instances, with the CPC algorithm returning test sets (T) that have, on average, 350 edges, which is 2.4% and 11.1% shorter than the average number of edges in T returned by the Filter algorithm and the Edge algorithm, respectively. Regarding the compliance of the generated T with the constraints, the CPC algorithm produced T that satisfied the constraints in 95% of the cases, the Filter algorithm in 45% cases, and the Edge algorithm returned T that satisfied the constraints only for 6% SUT instances. Regarding the coverage of edges, the CPC algorithm returned test sets that contained, on average, 91.5% of edges in the graphs, while for T returned by the Filter algorithm, it was 90.8% edges. When comparing the average results of the edge coverage criterion and the fulfillment of the constraint criterion by individual algorithms, we consider the incomplete edge coverage achieved by the CPC algorithm and, at the same time, 95% fulfillment of the graph constraints to be a reasonable compromise.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LUABA24101" target="_blank" >LUABA24101: DeepMBT: Nová generace testování sofwarových systémů založeného na modelech s využitím umělé inteligence</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

IEEE International Conference on Software Testing Verification and Validation Workshops

ISBN

979-8-3315-3467-7

ISSN

2159-4848

e-ISSN

—

Počet stran výsledku

9

Strana od-do

41-49

Název nakladatele

IEEE Xplore

Místo vydání

—

Místo konání akce

Naples

Datum konání akce

31. 3. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001483187700007