Novel Algorithm to Solve the Constrained Path-Based Testing Problem

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Novel Algorithm to Solve the Constrained Path-Based Testing Problem

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/LUABA24101" target="_blank" >LUABA24101: DeepMBT: New Generation of Model-based Software Testing Using Artificial Intelligence</a><br>

Continuities

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

Publication year

2025

Confidentiality

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

Article name in the collection

IEEE International Conference on Software Testing Verification and Validation Workshops

ISBN

979-8-3315-3467-7

ISSN

2159-4848

e-ISSN

—

Number of pages

9

Pages from-to

41-49

Publisher name

IEEE Xplore

Place of publication

—

Event location

Naples

Event date

Mar 31, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001483187700007