arXiv CSopen access

DJPlus: Generating minimal test suites for strong coverage criteria in graph models

Graphical Abstract

arXiv:2609.08953v1 [cs.SE] 8 Sep 2026

DJPlus: Generating minimal test suites for strong coverage criteria in graph models

Yavuz Köroğlu , Mutlu Beyazıt , Onur Kılınççeker , Serge Demeyer , Franz Wotawa

The model of a system under test (SUT)

METHOD

State-of-the-art test generation methods Random, QRandom, DJ

The novel DJPlus method

Generates a minimized flow

Main Algorithmic Contribution: Novel acyclic unrolling of cycles to reduce the number of test steps

Experiments on four realistic SUTs

EMPIRICAL EVALUATION

Four SUTs: Two hardware, two web applications SUT

Vertices

Edges

TLC RISC-V Parabank Testinium

10 16 75 129

18 36 144 259

Edge Prime pairs paths 27 115 501 1,033

Varying model sizes.

60 690 7,457 > 1M

SUT

Method

Avg. Steps

Testinium

Random/EC DJ/EPC DJPlus/EPC DJ/EC QRandom/EC DJPlus/EC

17,312 12,817 2,744 1,130 585 222

Method

Redundancy Factor

Relative Redundancy

Random DJ QRandom DJPlus

4.32 0.49 0.28 0.17

2,621% 424% 206% --

Prime paths are NOT scalable.

Edge-pair criterion is feasible with DJPlus.

DJPlus generates the smallest test suites.

!

Other methods are 2x-26x more redundant

Highlights DJPlus: Generating minimal test suites for strong coverage criteria in graph models

Yavuz Köroğlu , Mutlu Beyazıt , Onur Kılınççeker , Serge Demeyer , Franz Wotawa

• The novel DJPlus method generates minimal number of test cases for strong coverage.

• Alternative methods generate 2 to 26 times more redundant test steps.

• The edge-pair criterion is shown to be feasible for realistic SUTs using DJPlus.

• The prime path criterion is shown to pose significant scalability issues in experiments.

• DJPlus decreases test execution times by reducing the number of test steps.

DJPlus: Generating minimal test suites for strong coverage criteria in graph models Yavuz Köroğlu a,∗∗, Mutlu Beyazıt b,∗, Onur Kılınççeker b,∗, Serge Demeyer b,∗, Franz Wotawa c,∗ a Department of Computer Engineering, İstanbul Technical University, Ayazağa, Maslak, 34469, İstanbul, Türkiye b University of Antwerp and Flanders Make vzw, Middelheimlaan 1, Antwerpen, 2020, Belgium

c Institute of Software Engineering and Artificial Intelligence, Graz University of Technology, Inffeldgasse 16b/2, Graz, 8010, Steiermark, Austria

Abstract Automated test generation from graph models is essential to model-based testing. In this type of testing, graph coverage ensures test suite strength but also results in long test cases that take time to execute on the system under test. We propose a novel optimizationdriven method, DJPlus, which generates reduced test suites while satisfying given graph-based test requirements. We implement DJPlus and show the feasibility of edge-pair criterion, a stronger coverage criterion than vertex or edge criteria, on four realistic systems, while prime path criterion poses scalability issues. Our evaluation reveals that the alternative methods generate 2 to 26 times more redundant test steps than DJPlus and DJPlus decreases test execution times by reducing the number of test steps. These results show that DJPlus is a positive step towards tackling the challenges of model-based testing at an industrial scale. Keywords: Model-based testing, Graph coverage, Test generation, Test minimization 2020 MSC: 68M15, 2020 MSC: 68N30, 2020 MSC: 68R10 1. Introduction Model-based testing (MBT) is a software testing approach that uses models to generate test cases for a system under test (SUT). As a research subject, it is more than 50 years old (Elmendorf, 1970). Benefits of MBT include a high degree of test automation, high-quality tests, and reduced manual testing effort (Dalal et al., 1999). However, the complexity of MBT approaches allow industrial adoption only in small steps (Janicki et al., 2012). Test cases quickly explode especially in coverage directed testing (Mlynarski et al., 2012). So, there is a tradeoff between MBT complexity and its scalability (Utting et al., 2016). Although a model of an SUT (SUT model) can be any abstract representation that captures some system behavior, a graph (a transition system) is a typical model in MBT (Alégroth et al., 2022), where a path in the graph constitutes a test case and the elements of this path are test steps. A test generation method produces a set of test cases, i.e., a test suite, from the graph model. One way to assess the strength of a test suite is coverage-based criteria (Masri and Zaraket, 2016). While many MBT methods use the vertex or edge criteria (Köroğlu et al., 2025), the literature also features the edge-pair and prime path criteria, which ensure stronger tests (Ammann and Offutt, ∗ Corresponding author.

∗∗ Principal corresponding author.

Email addresses: [email protected] (Yavuz Köroğlu ), [email protected] (Mutlu Beyazıt ), [email protected] (Onur Kılınççeker ), [email protected] (Serge Demeyer ), [email protected] (Franz Wotawa )

2016, Part 2, Ch. 7). We call a criterion stronger than another if achieving the former guarantees achieving the latter. MBT methods often resort to relatively weaker criteria due to scalability concerns caused by the execution times of the generated test suite. Still, according to an experience report, the time to satisfy the edge criterion via fully-automated test generation and execution on a web application was six hours (Garousi et al., 2021), revealing some scalability issues even under weak criteria. This result aligns well with the conclusions of another study that MBT practice leads to large test suites even for weak criteria and proposes test selection techniques to minimize the test suite after the generation phase (Hemmati et al., 2010). In this study, we focus on a method to generate a test suite for a graph coverage criterion whose total number of test cases are minimized first and then its test steps (Li et al., 2012). The Dwarakanath and Jankiti (DJ) method is the state-of-the-art approach that generates a minimal number of test cases from a graph model (Dwarakanath and Jankiti, 2014), but it does not optimize the number of test steps within the test cases, leaving room for improvement in terms of scalability. To the best of our knowledge, popular MBT approaches do not yet utilize the DJ method. GraphWalker1 is a typical example of an open-source graph-based MBT tool, which provides the functionality to create graph models, generate abstract test cases from these graphs, and execute them on the SUT. We focus on GraphWalker throughout this study because the literature indicates widespread use of GraphWalker in many domains, including electronic circuits (Darwish et al., 2017), com1 See https://graphwalker.github.io.

mand-line tools (de Castro-Cabrera et al., 2022), mobile applications (Gudmundsson et al., 2016), and safety-critical systems (Zafar et al., 2023). GraphWalker comes with two builtin random test generation methods, Random and QRandom (a variant of Random utilizing shortest paths), and does not implement the DJ method. In light of all the above discussion, we present the following contributions to the literature.

Since none of the known test generation methods we investigate are optimal, including DJPlus, all of them generate test steps that are redundant in terms of their target criteria. However, these test steps could still have some utility in terms of fault detection or satisfying a stronger coverage criterion. In this study, we define a redundancy measure called edge-pair redundancy and use it as an indicator of the redundancy of test steps that target the vertex and the edge criteria.

1. Algorithmic novelty: We present DJPlus, an improvement to the state-of-the-art DJ method. DJPlus, like DJ, generates the minimum number of test cases but also reduces the number of test steps. We explain DJPlus in detail, with examples. 2. GraphWalker integration: We implement the state-of-theart DJ and our novel DJPlus methods to generate test cases for the popular GraphWalker environment. We name this implementation GWPlus, which replaces GraphWalker’s built-in random test generation. With this implementation, we bridge the gap between the most recent theoretical developments and a practical MBT tool. 3. Empirical evaluation: We perform experiments on four realistic SUTs: two web applications (Parabank and Testinium) and two hardware applications (TLC and RISCV), and show that DJPlus achieves the same coverage with fewer steps. We also show that other methods are 2 to 26 times more redundant than DJPlus, while DJPlus decreases the test execution times by reducing the number of test steps.

RQ4: (Reduction of test execution times) Does DJPlus decrease test execution times? DJPlus attempts to indirectly decrease test execution times by reducing the number of test steps. With this RQ, we explore whether reducing the number of test steps cause a decrease in test execution times, through an effect size analysis between our empirical results. We organize the rest of this paper starting with a discussion of the related work in Section 2. In Section 3, we explain the concepts necessary to understand our method. We describe our method, pose and address research questions, elaborate on the results, and conclude with a summary in Sections 4 to 7. 2. Related work We now motivate our focus on MBT with graph models, generating minimal number tests from graphs, graph coverage, and GraphWalker in the following sections. 2.1. MBT with graph models

Along with our contributions to the literature, we answer the following research questions (RQs):

Graph models in MBT are as old as MBT itself (Elmendorf, 1970). One systematic mapping study reports that most MBT tools use diagrams, charts, or finite state machines, which are all graph models (Dias Neto et al., 2007). Some graph models, like unified model diagrams, have the added benefit of visualization and interpretability, facilitating software development (Rumpe, 2016). Overall, graph models remain central to MBT and model-driven engineering.

RQ1: (Feasibility) Is the edge-pair criterion feasible for realistic systems? With this RQ, we investigate the costs associated with targeting the edge-pair criterion instead of the vertex or the edge criteria. To answer this RQ, we first compare the number of test requirements as the model grows under different criteria. Then, we compare the number of test steps generated by the established state-of-the-art, GraphWalker, for the edge criterion and by our proposed method, DJPlus, for the edge-pair criterion. We argue that any number of test steps comparable to the established state-of-the-art should remain feasible.

2.2. Minimal test generation from graphs Minimal test generation for a graph coverage criterion has a history comparable to MBT (Ntafos and Hakimi, 1979). Table 1 provides a non-comprehensive comparison of previous minimal test generation approaches for graph models. According to this table, one of the earliest methods invented for this purpose targets only vertex criterion (Aho and Lee, 1987). Another method targets prime path criterion but does not attempt to minimize the test cases (Ammann and Offutt, 2016, Part 2, Ch. 7). The latest development in this area is the DJ method, which generates the fewest test cases and targets any set of test requirements rather than a specific coverage criterion (Dwarakanath and Jankiti, 2014). However, DJ-generated test cases still contain many redundant test steps. To the best of our knowledge, ours is the first work to tackle both minimizing the number of test cases and reducing the number of test steps while satisfying any given set of test requirements.

RQ2: (Improvement to the state-of-the-art) Does DJPlus generate test suites with fewer test steps than DJ? DJPlus does not always generate the minimal number of test steps to satisfy a criterion. So, we perform an empirical evaluation of Random, QRandom, DJ, and DJPlus to show that DJPlus generates fewer test steps compared to its alternatives. RQ3: (Redundancy) Are DJ, Random, and QRandom redundant compared to DJPlus, and by how much? 2

Table 1 A comparison of minimal test generation approaches for graph models.

Method (Aho and Lee, 1987) (Ammann and Offutt, 2016, Part 2, Ch. 7) DJ (Dwarakanath and Jankiti, 2014) DJPlus (Our proposed approach)

VC ✓ ✓ ✓

Criterion EC EPC

PPC

✓ ✓

✓ ✓ ✓

✓ ✓

Minimization # Test Cases # Test Steps ✓ ✓ ✓ ✓ ✓

VC: Vertex Criterion, EC: Edge Criterion, EPC: Edge-Pair Criterion, PPC: Prime Path Criterion

2.3. Graph coverage v0

The literature includes several coverage criteria for graph models and defines a subsumption relation among these depending on their test strengths (Ammann and Offutt, 2016, Part 2, Ch. 7). The vertex and edge criteria are weak in this relation, while the edge-pair and prime path criteria are stronger. The prime path criterion has the added benefit of subsuming dataflow criterion and facilitating logic coverage (Kaminski et al., 2010). To the best of our knowledge, ours is the first MBT approach targeting the edge-pair and prime path criteria with a reduced number test steps and a minimized number of test cases.

v1 v2

v3

v4 v5

v6

v7 v8

Fig. 1. An example graph that models the behaviors of a system under test (SUT).

their contributions to edge-pair coverage, reporting that the cost of an additional percent of edge-pair coverage increases exponentially in terms of the number of test steps. Thus, the study concludes that a deterministic, optimization-based test generation method is necessary to avoid the test execution costs while satisfying a strong graph coverage criterion.

2.4. GraphWalker GraphWalker is a popular MBT tool for modeling or test generation within a diverse set of domains, including the testing of programmable logic controllers (Frey et al., 2012), web applications (Schur et al., 2013), graphical user interfaces (Kılınççeker et al., 2021), data access tools (Lindvall et al., 2015), electronic control circuitry (Darwish et al., 2017), service orchestrations (Leal et al., 2020), mobile applications (Karlsson et al., 2021), command-line tools (de CastroCabrera et al., 2022), information and communications technology supply chains (Bicchierai et al., 2023), ground system software (Gudmundsson et al., 2015), and autonomous vehicles (Chetouane and Wotawa, 2023). One study performs model checking in a GraphWalker environment using UPPAAL (Tiwari et al., 2022). Further than its apparent popularity, one experience report found GraphWalker to be only one of two tools out of ten that features all the essential criteria for MBT, while the other candidate, TestOptimal, unlike GraphWalker, is not open-source and easily modifiable (Garousi et al., 2021). However, the same study also shows a case where the total test execution time of an SUT was six hours to satisfy the edge criterion with GraphWalker, revealing potential scalability problems of test generation from graph models as the model grows in size. Some studies focus on the costs of GraphWalker-generated test cases, where one study reports that they contain many more test steps than manually crafted test cases that reach the same coverage (Karlsson et al., 2022). A more recent study demonstrates that GraphWalker-generated test cases contain many redundant test steps, i.e., test steps that do not increase vertex or edge coverage (Köroğlu et al., 2025). This study investigates the possible benefits of these redundant test steps by measuring

3. Background We now explain how the state-of-the-art DJ method generates the minimal number of test cases but how it fails to eliminate redundancies within these test cases, on an example graph. We provide more rigorous definitions to facilitate the understanding the DJ methodology in Appendix A.The concepts used in this section are aligned with the original DJ study Dwarakanath and Jankiti (2014). They also closely follow the wider graph-based testing theory established in the literature (Ammann and Offutt, 2016). Fig. 1 depicts an example graph model we designed solely to facilitate our explanations. It features nine vertices representing nine different SUT behaviors, where v0 is the entry vertex. Twelve edges connect these behaviors. Notice that every vertex is reachable from v0 , and v4 has a loop. An example path of length four of this graph is p = (v8 , v0 , v4 , v4 ). A test case (see Appendix A.2) is a non-empty path starting from the entry vertex. For example, t1 = (v0 ) and t2 = (v0 , v6 ) are test cases but t3 = (v6 ) and t4 = () are not. An SUT automatically executes a test case by triggering the behaviors in the order of the test case’s vertex sequence. Then, every trigger, i.e., vertex, is equivalent to a test step , which takes some time to execute. A test suite is a collection of test cases, e.g., T = {t1 , t2 }. In MBT practice, developers or testers generate and execute test suites to ensure the software quality. For example, suppose r is the splice of p = (v0 ) and q = (v5 ). Then r could either be (v0 , v3 , v5 ) or (v0 , v4 , v5 ). The splice can 3

Table 2 The test requirements (TR) of the VC, EC, EPC, and EPC, derived for the graph model in Fig. 1.

#

TRvc

TRec

TRepc

TRppc

tr1 tr2 tr3 tr4 tr5 tr6 tr7 tr8 tr9 tr10 tr11 tr12 tr13 tr14

(v0 ) (v1 ) (v2 ) (v3 ) (v4 ) (v5 ) (v6 ) (v7 ) (v8 )

(v8 , v0 ) (v0 , v1 ) (v2 , v1 ) (v1 , v2 ) (v0 , v3 ) (v0 , v4 ) (v4 , v4 ) (v3 , v5 ) (v4 , v5 ) (v0 , v6 ) (v0 , v7 ) (v7 , v8 )

(v7 , v8 , v0 ) (v8 , v0 , v1 ) (v1 , v2 , v1 ) (v0 , v1 , v2 ) (v2 , v1 , v2 ) (v8 , v0 , v3 ) (v8 , v0 , v4 ) (v0 , v4 , v4 ) (v0 , v3 , v5 ) (v0 , v4 , v5 ) (v4 , v4 , v5 ) (v8 , v0 , v6 ) (v8 , v0 , v7 ) (v0 , v7 , v8 )

(v0 , v7 , v8 , v0 ) (v1 , v2 , v1 ) (v2 , v1 , v2 ) (v7 , v8 , v0 , v1 , v2 ) (v4 , v4 ) (v7 , v8 , v0 , v3 , v5 ) (v7 , v8 , v0 , v4 , v5 ) (v7 , v8 , v0 , v6 ) (v7 , v8 , v0 , v7 ) (v8 , v0 , v7 , v8 )

(v0 ) tr1 tr7

tr6

tr4 tr10

tr5

tr2 tr3

Fig. 2. The splice graph of the PPC test requirements from Table 2.

(v0 ) h2 ∼ (tr1 , tr9 , tr10 ) tr5

Highlighted: An edge pair that is not a subpath of any tr ∈ TRppc .

tr8

tr4

tr6

Fig. 3. The acyclic hypergraph generated by iteratively replacing the cycles of the splice graph in Fig. 2 with hypervertices.

which is the shortest test case that covers the selected three of the ten prime path test requirements. The DJ method comprises the following steps. 1. Construction of a splice graph of test requirements. 2. Construction of an acyclic hypergraph from the splice graph. 3. Constrained flow minimization of the hypergraph, which minimizes the number of test cases. 4. Unwinding hyperpaths to test cases. We already discussed the first step, which is splice graph construction. Dwarakanath and Jankiti provide the algorithm for splice graph construction Dwarakanath and Jankiti (2014). We also describe this algorithm in Appendix B.3. In the following sections, we explain the remaining steps of DJ. In the final section, we discuss DJ’s suboptimality.

3.1. The DJ method There are two key strategies behind the test case minimization of the DJ method, splicing of the test requirements and flow minimization, which covers these splices with the as few test cases as possible. A splice (see Appendix A.4) of two paths is a shortest path such that,

3.1.1. Hypergraph construction Since minimum flow optimization is inapplicable over cyclic graphs, the DJ method repeatedly finds cycles in the splice graph and combines them into hypervertices, obtaining an acyclic hypergraph as in Fig. 3. We denote our example hypervertices as h1 ∼ (tr2 , tr3 ) and h2 ∼ (tr1 , tr9 , tr10 ). Note that these hypervertices are cycles according to Fig. 2.

1. Starts with the first vertex of the former, 2. Ends with the last vertex of the latter, and 3. Both paths are subpaths of the splice. Fig. 2 illustrates the splice graph for the prime path criterion (TRppc ) in Table 2 and the example graph model in Fig. 1. To motivate the strategy behind splicing, we take a path out of this splice graph, starting from the entry vertex. Suppose ((v0 ), tr1 , tr4 , tr2 ) is such a path. By chain-splicing the sequence of this path, we get

3.1.2. Flow minimization The acyclicity of the hypergraph enables DJ to use a constrained minimum flow variant of the Ford-Fulkerson algorithm to minimize the number of test cases (Ford and Fulkerson, 1956). The DJ method constrains the minimum flow algorithm

tr4

z }| { (v0 ) ⊙ tr1 ⊙ tr4 ⊙ tr2 = (v0 , v7 , v8 , v0 , v1 , v2 , v1 ) | {z } | {z }

tr7

h1 ∼ (tr2 , tr3 )

be shorter than the sum of the spliced paths’ lengths, e.g., the splice of (v0 , v7 , v8 ) and (v7 , v8 , v0 ) is (v0 , v7 , v8 , v0 ). Finally, the splice may not exist, e.g., for (v0 , v6 ) and (v7 , v8 ). With the help of a shortest path algorithm, computing a splice is straightforward (see Appendix B.1). In Table 2, we present the test requirements for the vertex (VC), edge (EC), edge-pair (EPC), and prime path (PPC) criteria under the example graph model in Fig. 1. While generating the requirements for VC, EC, and EPC are straightforward, algorithms that generate a minimal set of requirements for the PPC are well-known (see Appendix B.2). According to Table 2, the example graph in Fig. 1 yields ten test requirements for the PPC. Note that the EPC is stronger than the VC and the EC, but the PPC is not stronger than EPC; the edge-pair (v0 , v4 , v4 ) is not a subpath of any PPC test requirement.

tr1

tr9

tr8

(1)

tr2

4

Algorithm 1 Unwinding hyperpaths

tr5 : 1 (v0 ) : 5

tr4 : 1 h2 : 4

1: Input: A splice graph, a hypergraph, and a sequence of hypervertex sequences 2: Output: A sequence of paths of the splice graph 3: for every hypervertex sequence do 4: Add the sequence to the sequence of paths. 5: if the sequence contains an hypervertex then 6: Replace the hypervertex with its cycle. 7: repeat 8: Rotate and splice the cycle between the predecessor and the successor of the hypervertex. 9: until the sequence is the shortest path 10: end if 11: end for

h1 : 1 tr6 : 1

() : 0

tr7 : 1 tr8 : 1 Fig. 4. A minimal flow network from (v0 ) to () that traverses every vertex of the hypergraph in Fig. 3 at least once.

to visit every hypervertex at least once, so the algorithm does not remove any test requirements. We now describe the essentials of the algorithm, as its intrinsic details are an active subject of research (Chen et al., 2025). The minimum flow algorithm performs minimization from a source vertex to a sink. These vertices correspond to the beginning and the end of a test case, respectively. In an hypergraph, the entry path, a path that comprises only the entry vertex, represents the beginning, but the end remains implicit; the test case could end with any vertex. Thus, the DJ method creates a new empty hypervertex that represent test termination and connects every other vertex to it. Then, it assigns a positive integer, called flow, representing the number of test cases that cover it, to every edge. Finally, it minimizes the total flow from the entry path to the empty hyperpath, such that every vertex except the sink in the hypergraph has a positive outgoing flow. In Fig. 4, we present a minimized flow network of the hypergraph in Fig. 3. This network’s vertices are the same as the hypergraph, with the addition of a sink vertex at the end. Every vertex has a number, corresponding to its total outgoing flow. The sink vertex naturally has zero outgoing flow; it does not have any outgoing edges. All the other vertices have positive total flow. The source has the highest total outgoing flow, five, which is the minimum number of test cases required to cover all test requirements. Some edges of the hypergraph do not appear in the flow network because they carry zero flow, e.g., ((v0 ), h1 ). As a result, generating five distinct paths from the source to the sink becomes straightforward. A sequence of these paths is

test cases must start from the entry vertex. In the end, DJ obtains five sequences as π2 = (((v0 ), tr5 ), ((v0 ), h2 , tr4 , h1 ), ((v0 ), tr6 ), ((v0 ), tr7 ), ((v0 ), tr8 )) where the multiple occurences of the source vertex (the entry path) is unavoidable because this is the minimum number of test cases required for the prime path criterion. 3.1.3. Unwinding Unwinding refers to the production of test cases from the hypervertex sequences coming from the flow network. If these sequences contained no hypervertices and only test requirements, obtaining test cases is only a matter of chain-splicing, as in Eq. (1). Then, unwinding boils down to reconstructing the cycles represented by hypervertices. We present the steps of the DJ method to unwind hypervertex sequences in Algorithm 1. This algorithm traverses every element of each sequence and replaces every hypervertex with its cycle. Note that the order of hypervertex sequences is arbitrary, and trying every ordering would not minimize the test steps as we discuss in Section 3.1.4. Then, it rotates the cycle until the chain-splice of its predecessor, itself, and its successor is the shortest. One rotation of a cycle moves its last vertex to the front, as defined in Appendix A.4. Determining the shortest path is straightforward; DJ rotates the cycle as many times as the cycle’s element count, and takes the rotation that yields the shortest splice. For the example sequences in Eq. (3), Algorithm 1 replaces h2 and h1 , as these are the only vertices foreign to the splice graph in Fig. 2. Suppose the algorithm reconstructs h2 ’s cycle as (tr9 , tr10 , tr1 ). Considering the predecessor (v0 ) and the successor tr4 , the algorithm gets the shortest splice after rotating this cycle, like (tr1 , tr9 , tr10 ). Then, the chain-splice becomes ((v0 ), tr1 , tr9 , tr10 , tr1 , tr4 ). Note that since Fig. 2 does not have

π1 = (((v0 ), tr5 ), ((v0 ), h2 , tr4 , h1 ), ((v0 ), h2 , tr6 ),

(3)

(2)

((v0 ), h2 , tr7 ), ((v0 ), h2 , tr8 )) where we omit the sink since it represents an empty path. Every vertex of the network occurs as many times as its total outgoing flow number in these paths. The DJ method removes the extraneous occurrences of these vertices because the splice of their predecessor and successors will contain all the necessary test steps and traversing every step of the same test requirement would be redundant. Naturally, the DJ method never removes the extraneous occurences of the source vertex since all 5

one it selects. For example, if it removes h1 from the second sequence, the resulting test suite is

v0 v1

v2

T 1 = {(v0 , v1 , v0 , v2 ),

v2

v3

v0

(a) Graph model A.

v1

(v0 , v3 )}

v3

but if it removes h1 from the first sequence, the resulting test suite is T 2 = {(v0 , v2 ), (8) (v0 , v1 , v3 )} which has fewer test steps in total than the test suite in Eq. (7).

v4

(b) Graph model B.

Fig. 5. Two example graph models.

an edge between test requirements tr10 and tr4 , an extra tr1 appears between them during splicing. As h1 ∼ (tr2 , tr3 ) has no successor, the algorithm only considers its predecessor (tr4 ). After removing the extraneous occurence of tr1 , the resulting sequence is

For graph B. Even if we consider all orderings of hypervertex sequences, DJ produces suboptimal results because it does not consider the cases where the elements of a hypervertex could have been traversed in different parts of a test suite. For example, after processing graph B and minimizing its flow, DJ obtains π1 = (((v0 ), h2 , (v4 ))) (9)

π3 = (((v0 ), tr5 ), ((v0 ), tr1 , tr9 , tr10 , tr4 , tr2 , tr3 ), ((v0 ), tr6 ),

where h2 ∼ (h1 , v2 ). Unwinding h2 , DJ gets

(4)

π2 = (((v0 ), h1 , (v2 ), h1 , (v4 )))

((v0 ), tr7 ), which contains every prime path test requirement from Table 2 exactly once. Finally, through chain-splicing, DJ obtains the test suite as

π3 = (((v0 ), h1 , (v2 ), (v4 ))), π4 = (((v0 ), (v1 ), (v3 ), (v1 ), (v2 ), (v4 ))),

(v0 , v7 , v8 , v0 , v7 , v8 , v0 , v1 , v2 , v1 , v2 ),

(12)

and finally removes the extraneous occurence of (v1 ) as (5)

π5 = (((v0 ), (v1 ), (v3 ), (v2 ), (v4 ))).

(v0 , v7 , v8 , v0 , v4 , v5 ),

(13)

From Eq. (13), DJ generates the test suite

(v0 , v7 , v8 , v0 , v6 )} with a total length of 31 test steps.

T 1 = {(v0 , v1 , v3 , v1 , v2 , v3 , v4 )}

(14)

T 2 = {(v0 , v1 , v2 , v3 , v4 )}

(15)

where the minimal test suite was

3.1.4. Suboptimality of DJ In this section, we demonstrate the following causes of suboptimality in the DJ method, all stemming from the hypervertices.

which is impossible for DJ to generate because the elements of h1 ∼ (v1 , v3 ) must be traversed in separate parts of the test case.

1. Selection of extraneous occurrences of hypervertices and 2. Prevented piecemeal traversal of an hypervertex’s cycle, i.e., interrupting the traversal of the cycle in the middle and making a detour before completing the cycle.

4. Method In the following sections, we explain our novel test generation method, DJPlus, demonstrate how it solves the suboptimalities presented in Section 3.1.4, show why DJPlus still fails to generate the absolute minimum number of test steps on an example, discuss our approach to DJPlus’ implementation challenges within the popular GraphWalker environment, and elaborate on its computational complexity. We show an comparative overview of DJ and DJPlus in Fig. 6. Both DJ and DJPlus generate an hypergraph in the same way. Then, DJ uses an approach we call unwinding to obtain test cases. Unwinding introduces cycles back to the hypergraph, and therefore flow minimization is possible only at the beginning. DJPlus, however, replaces unwinding with a novel approach that we call unrolling, which keeps the graph acyclic and allows flow minimization at every iteration.

We provide two example graph models, A and B, in Fig. 5a and 5b, exposing these suboptimalities, respectively. In both these examples, we use the VC. So, test requirements are length-one paths, e.g., (v3 ). For graph A. After processing graph A and minimizing the flow, the DJ method obtains ((v0 ), h1 , (v3 )))

(11)

performs one more iteration of unwinding to produce

T = {(v0 , v4 , v4 ),

π = (((v0 ), h1 , (v2 )),

(10)

where h1 ∼ (v1 , v3 ). Then, DJ removes one of the extraneous occurrences of h1 to obtain

((v0 ), tr8 ))

(v0 , v7 , v8 , v0 , v3 , v5 ),

(7)

(6)

where h1 ∼ ((v0 ), (v1 )). DJ removes one of h1 ’s occurrences arbitrarily, but the minimality of the test suite depends on which 6

SUT

Simple Graph

Test Requirement Generator

(v0 ) (v1 )

Test Requirements (TR) Hypergraph Generator

Splice Graph

Splice Graph Generator

Hypergraph Hypergraph One-Time Flow Minimization + Unwinding

(v0 ) : 2

(v0 )′

h1 : 2

(v1 )′

(v3 ) : 1

Repetitive Flow Minimization + Unrolling

(v2 ) : 1

() : 0

(v0 ) : 2

Fig. 6. The differences between the DJ and the DJPlus approaches, common components in black, DJ’s components in red, and DJPlus’ novel approach is in blue.

(v3 ) ()

(a) Graph A’s flow network.

Test Case(s)

(v2 )

(v1 ) : 1

(b) After unrolling h1 .

(v3 ) : 1 (v2 ) : 1

() : 0

(c) The RFG after minimization.

Fig. 7. RFG generation on graph A from Fig. 5a.

Algorithm 2 Unrolling hyperpaths 1: Input: A flow network 2: Output: A requirement flow graph (RFG) 3: for every hypervertex hi from i = n to 1 do 4: Add hi ’s cycle to RFG. 5: Add an apostrophe (′ ) decorated vertex for every vertex in hi ’s cycle. 6: Connect every h[ j] and h′ [ j] to the sink. 7: Reconstruct the edges from and to the hypervertex’s cycle. 8: Reconstruct the edges within the hypervertex’s cycle without completing the cycle. 9: Remove hi and its edges. 10: Re-minimize the flow. 11: end for

minimizes the flow, with the following constraints.

4.1. DJPlus

4.2. Motivating examples We now demonstrate how DJPlus, unlike DJ, generates test suites with fewer steps for the example graphs A and B depicted in Fig. 5.

1. The sink vertex and every second occurrence of the unrolled elements, decorated by an apostrophe (′ ), must have zero or more outgoing flow. 2. The rest must have at least one outgoing flow. Algorithm 2 terminates when there are no undecorated hypervertices left to unroll. Note that the algorithm does not unroll decorated hypervertices. Notice that we unroll hypervertices in the reverse order of their creation, which ensures every selected hypervertex is not hidden in another hypervertex at the time of unrolling. We present the other details regarding this algorithm in Appendix B.6.

Our general strategy to reduce the number of test steps is to eliminate all hypervertices before generating the test cases, obtaining a flow graph free of hypervertices. We call such a graph a requirement flow graph (RFG) because all the vertices are test requirements, except the source and the sink vertices. Our novel strategy to generate an RFG is to replace every hypervertex with its cycle, one at a time, and re-minimize the flow after every replacement. Re-minimization of the flow was normally impossible because replacing a hypervertex with its cycle makes the graph cyclic. In Algorithm 2, we present an unrolling procedure that avoids introducing cycles while reconstructing the elements of hypervertices. Algorithm 2 unrolls the cycle of the hyperpath twice in lines 4 and 5. The double unrolling means that now every element of the hypervertex appears twice on the flow graph. The algorithm reconnects every edge from and to these unrolled elements but avoids making connections that form a cycle. Thus, it preserves the acyclicity of the flow network. Finally, it re-

Graph A. Fig. 7a illustrates an automatically generated and minimized flow network for graph A from Fig. 5a. Algorithm 2 unrolls h1 twice to produce the intermediate graph in Fig. 7b. Then, it performs a re-minimization to generate the RFG in Fig. 7c, which automatically gets rid of the second occurrences of (v0 ) and (v1 ). From this RFG, DJPlus produces the minimal test suite in Eq. (8). In contrast, DJ obtained this test suite only when it arbitrarily selected the correct hypervertex to remove, which is not always the case. Graph B. Fig. 8a is a minimized flow network for graph B from Fig. 5b. Algorithm 2 unrolls h2 as in Fig. 8b and minimizes the flow as in Fig. 8c. The algorithm managed to remove h2 but introduced another hypervertex h1 because the graph model B in Fig. 5b contains nested cycles, i.e., cycles within cycles. 7

(v0 ) h1

(v0 ) : 1

(v2 )

h1 : 1

(v0 ) : 1

h′1

(v2 ) : 1

h2 : 1

(v2 )′

h′1 : 1

(v4 ) : 1

(v4 )

() : 0

(v0 )

(v3 ) (v2 )

v0

(a) A graph with nested cycles.

(v0 )

h′1

(v2 ) : 1

(v3 ) : 1

(v0 )

(v3 )

(b) The splice graph of Fig. 9a.

h1 h2

(c) After combining h1 ∼ ((v1 ), (v2 )))

(v3 )

(d) After combining h2 ∼ ((v0 ), h1 )

(v3 )′ : 0 h′2 : 0

(c) Minimization #1.

(v0 ) : 1

() : 0

(v3 ) : 1 h2 : 1 (e) Unrolling of h3 ∼ (h2 , (v3 )).

(v0 ) : 1

(v1 )′ (v4 )

()

(v4 ) : 1

h2 : 1

(v3 ) : 1

() : 0

(f) After removing zero flows.

Fig. 9. DJPlus’s execution on an graph model with nested cycles.

(d) After unrolling h1 .

(v1 ) : 1

(v2 )

(v3 )

(v3 )′ (v0 ) : 1

v3

() : 0

(b) After unrolling h2 .

(v1 )

v2

(v4 ) : 1

()

(a) Graph B’s flow.

(v1 )

v1

the other choice would have yielded (v0 , v3 , v2 , v1 ), which was shorter. To make DJPlus optimal, one could conduct a search through alternative minimum flows. But, in the worst case, such a search could lead DJPlus to unroll an exponential number of alternatives. In this study, we avoided this case by letting DJPlus select an arbitrary minimum flow and not perform a search. Note that workarounds like changing the selection order of cycles that are combined into hypervertices cannot guarantee one unique minimum flow at every iteration. So, alternative minimum flows are unavoidable, and are the primary cause of suboptimality in DJPlus. Due to this suboptimality, we opted to empirically evaluate DJPlus’ number of test steps and its redundancies.

() : 0

(e) The RFG after minimization.

Fig. 8. RFG generation on graph B from Fig. 5b.

So, it unrolls h1 as in Fig. 8d and then re-minimizes to get the RFG in Fig. 8e. Thus, DJPlus obtains the minimal test suite in Eq. (15), which was impossible for DJ. 4.3. Suboptimality of DJPlus Although DJPlus manages to find shorter test cases than DJ, the number of test steps are still not the absolute minimum. In this section, we step-by-step demonstrate the suboptimality of DJPlus on an example. In this example, we also show how DJPlus handles nested cycles. We present the execution steps of DJPlus on an example graph with nested cycles in Fig. 9. DJPlus starts by taking the graph model in Fig. 9a as input. Suppose the VC is chosen for this case. Then, the splice graph DJPlus constructed looks very similar to the graph model, as in Fig. 9b. DJPlus repeatedly finds the shortest cycle and replaces it with a hypervertex, as in Figs. 9c and 9d. We omit showing the insertion of the final hypervertex, h3 ∼ (h2 , (v3 )), as that case is trivial. DJPlus then (v0 ) to () that passes through h3 , unrolls h3 , and re-minimizes the flow to obtain the graph in Fig. 9e. Finally, it removes the zero flows to obtain the graph in Fig. 9f. However, in this case, the minimum flow was not unique, the other alternative being ((v0 ), (v3 ), h′2 , ()), which also covers all test requirements. DJPlus ignores that, unrolls every hypervertex starting from its chosen flow, and it gets the test case (v0 , v1 , v2 , v0 , v3 ), whereas

4.4. Implementation challenges We implement DJ and DJPlus for the popular MBT tool, GraphWalker, which features a graphical user interface (GUI) to design graph models, generate a test case, and execute it on the SUT. It features two random test generation algorithms, Random and QRandom. We refer to our implementations on top of GraphWalker as GWPlus. We now discuss practical implementation challenges of our approach within the GraphWalker framework, regarding model conversion, coverage measurements and infinite loops. We explain how we addressed these issues in the following sections. 4.4.1. Model conversion The popular GraphWalker environment uses graph models similar to the ones described by Dwarakanath and Jankiti, albeit with the following key differences. 1. A GraphWalker model comprises many graphs connected by shared vertices, instead of just one. 8

2. Each graph is a multigraph , i.e., allows multiple edges between vertices. 3. The entry element can be either a vertex or an edge. Our practical implementation, GWPlus, takes a GraphWalker model as input and implements both the state-of-the-art DJ and our proposed DJPlus methods. To be able to use the test requirement generation, splice graph construction, hypergraph creation, and the unwinding algorithms of DJ as is, GWPlus employs the strategy to automatically convert GraphWalker models rather than designing variants of these algorithms adapted to GraphWalker. GWPlus first creates a unified graph by taking the union of all the vertices and the edges of the GraphWalker model, respectively. The unified graph is still a multigraph, which poses a problem for DJ, DJPlus, and any other deterministic graphbased test generator. Such test generators generate vertex pairs as test requirements for the EC, missing some of the extraneous edges between vertices in the process. GWPlus converts the unified multigraph to a simple graph, where the conversion method depends on the test criterion. For the VC, removing all extraneous edges is sufficient. For the EC and the EPC, GWPlus takes the unified multigraph’s line graph , i.e., a graph whose vertices are the edges of the original. For the PPC, GWPlus allows edge removal or line graphs. We name the resulting criteria prime1 and prime2 , respectively. Line graph conversion affects test criterion, e.g., the VC of the line graph is equivalent to the EC of the GraphWalker model. Similarly, the EC of the line graph is equivalent to the EPC of the GraphWalker model. The PPC of the line graph (prime2 ) is stronger than the PPC of the GraphWalker model with extraneous edges removed (prime1 ). Further discussion on line graphs is available in Appendix D. The final conversion step addresses the entry element of a GraphWalker model, which is either a vertex or an edge. For the VC, if the entry element is an edge, the entry vertex is the successor of that edge. If the entry element is a vertex, the graph satisfies DJ’s requirements with no modifications. For other criteria, if the entry element is an edge, the entry vertex is the corresponding vertex in the line graph. Otherwise, GWPlus has to add a dummy vertex to represent the entry vertex. Figs. 10a and 10b depict screenshots of a GraphWalker model’s multigraphs we designed in GraphWalker’s GUI to demonstrate our conversion procedure. The green colored vertex c in Fig. 10a is the entry element of this model. The orange colored vertex d is shared by both multigraphs of the model. Notice that there are two edges from b to c. GWPlus generates a unified line graph from the GraphWalker model as in Fig. 10c, where ve is the dummy entry vertex. This line graph is a simple graph thanks to the uniqueness of its edges. So, GWPlus moves on to test generation.

(a) Multigraph MGA .

(b) Multigraph MGB .

ca ve

ab bc1

bc2

df

ae

bd

cd

ff fd

(c) Unified line graph of the GraphWalker model.

Fig. 10. An example GraphWalker model with two multigraphs. Table 3 The worst-case time complexities of DJPlus algorithms.

Splice Graph Construction Hypergraph Construction Unrolling

O(|TR|3 ) O(|H||TR|) O(|H||TR|2 )

|H|: The number of hypervertices, i.e., cycles in the splice graph. |TR|: The number of test requirements.

ing the percentage of corresponding test requirements that are subpaths of at least one test case within the generated test suite. 4.4.3. Infinite loops GraphWalker’s Random method starts from the entry element and concatenates random successors until the generated test case alone satisfies the target criterion. The QRandom method is similar, but splices random unvisited elements instead of concatenating random successors. Sometimes, the target criterion is unsatisfiable with only one test case. Then, both Random and QRandom enter an infinite loop. To avoid infinite loops, the designer must add extra edges to the model. For this purpose, connecting some vertices back to the entry vertex is typical, representing a restart of the SUT. Note that none of the realistic GraphWalker models we used in our experiments required extra edges to avoid infinite loops. 4.5. Computational complexity of unrolling in DJPlus In this section, we discuss the time complexities of DJ and DJPlus. Dwarakanath and Jankiti provide a rigorous analysis for DJ, and show that the computational complexity is dominated by the splice graph construction (Dwarakanath and Jankiti, 2014). According to their work, assuming |TR| > |E|, the worst-case time complexity is O(|TR|2 max(|TR|, |E|)) = O(|TR|3 ), i.e., proportional to the cube of the number of test requirements. We derive the worst-case time complexity of hypergraph construction as follows. For every hypervertex, i.e., cycle in the

4.4.2. Coverage measurements To evaluate coverage, we must first measure it. GraphWalker already measures VC and EC, but does not support the other criteria. GWPlus measures VC, EC, EPC, and PPC by calculat9

splice graph, the algorithm finds that cycle and replaces it. The complexity of finding a cycle is |V s | + |E s |, where the vertices of the splice graph is the set of test requirements (V s = TR). Assuming that |V s | is linearly proportional to |E s |, the overall complexity could be written as O(|H||T R|), where |H| stands for the number of hypervertices, i.e., cycles in the splice graph. Finally, DJPlus, on top of DJ, introduces unrolling. For every hypervertex, the algorithm unrolls its cycle twice and performs one minimum flow optimization. The minimum flow optimization is tha same as DJ’s, whose worst-case complexity is O(|V||E|). Using our assumptions, we rewrite that complexity as O(|TR|2 ). Since unlike DJ, DJPlus performs flow minimization not just once but for every hypervertex, the overall complexity becomes O(|H||TR|2 ). We summarize the worst-case time complexities we analyzed so far for DJPlus in Table 3. From this table, the time required for unrolling clearly dominates the time needed for hyperpath construction. However, it remains unclear if splice graph construction remains the bottleneck as in DJ, or unrolling is costlier. A study published three years after DJ shows that, in the worst-case, a graph comprises 1.44|E| cycles (Arman and Tsaturian, 2017). Using this information, the worst-case time complexity of hypergraph construction and unrolling would become exponential. With the absence of a polynomial flow minimization technique directly applicable to cyclical graphs, the only way to keep the complexity of DJ and DJPlus polynomial is to keep the number of cycles low by design of the model. We analyze the experimental SUTs and further discuss our empirical results for test generation times in Section 5.2.2.

3. Test generation method (Random, QRandom, DJ, or DJPlus). 4. Random seed (One of 30 pre-generated random positive integers). An experimental configuration is a combination of experimental settings. Not every one of the 4 × 4 × 4 × 30 = 1,920 combinations is a valid experimental configuration, e.g., Random cannot target edge-pair criterion. We now explain our experimental settings in detail and identify some invalid configurations. 5.1.1. Systems under test (SUTs) For our experimental setup, we found four realistic SUTs with GraphWalker models. These models have varying sizes ranging up to 129 vertices. Two of them are hardware systems, and the other two are web systems. Hardware systems. TLC2 is a Verilog traffic light controller for a four-way road instersection, featuring a GraphWalker model with ten vertices and 18 edges (Kılınççeker et al., 2022). We executed test cases on TLC through a simulation environment provided by the Vivado Design Suite. In accordance with the requirements of the Vivado Design Suite, we carried out the simulations on a PC (Intel Core i7-7500U, 2 Cores, 8 GB Memory) with a Windows 10 operating system. RISC-V 3 is a finite-state machine Verilog controller of a 32bit central processing unit developed by the OpenHW Group, with a small GraphWalker model of 16 vertices and 36 edges (Gautschi et al., 2017). Like in TLC, we used the Vivado Design Suite to execute RISC-V test cases on the same PC. Web systems. Parabank4 is an open-source online banking application from Parasoft. A recent study used it to evaluate a scriptless method that generates tests on the fly (Hufkens et al., 2024). It features a sizable GraphWalker model with 75 vertices and 144 edges. For executing Parabank test cases in headless mode of Chromium version 124, we used the Selenium framework with a GraphWalker 4.3.3 snapshot customized to support the web system on a 10-core 16 GB Apple M1 Pro with macOS Sonoma 14.5. Testinium5 is a cloud web application for test automation and management developed by the Testinium company. One study used it to compare MBT tools like TestOptimal and GraphWalker (Garousi et al., 2021). It boasts the largest GraphWalker model in our experimental setup, with 129 vertices and 259 edges. We noticed substantial changes in the Testinium interface and its GraphWalker model became outdated. So, we were unable to execute Testinium test cases to obtain results for RQ4.

5. Evaluation In the following sections, describe our experimental setup, empirical evaluation of our research questions, and final notes on the test generation times we observed during these experiments. 5.1. Experimental setup We now discuss the experimental setup we used to answer the research questions. In this setup, an experimental run has three phases; 1. Test requirement generation, 2. Test generation, and 3. Test execution, where GWPlus automatically generate the test requirements, and we use the command-line interface of GraphWalker 4.3.2, the latest GraphWalker version at the time, for test generation. The test execution procedure depends on the SUT, so we discuss every SUT’s test execution specifics in Section 5.1.1. Every variable of an experimental run is an experimental setting. In our experimental setup, we have four experimental settings.

5.1.2. Target criteria Our experimental configurations allow the VC, EC, EPC, and PPC. Random and QRandom support only VC and EC, while DJ and DJPlus support all four criteria. 2 See https://github.com/kilincceker/MBIT4HW.

3 See https://github.com/openhwgroup/cv32e40p.

1. SUT (TLC, RISC-V, Parabank, or Testinium). 2. Test criterion (VC, EC, EPC, PPC).

4 See https://github.com/parasoft/parabank.

5 See https://github.com/vgarousi/MBTofTestinium.

10

EPC 27 115 501 1,033

prime1 60 690 7,457 > 1M

prime2 134 > 1M > 1M > 1M

VC: vertex criterion, EC: edge criterion, EPC: edge-pair criterion

5.1.3. Random seeds Random and QRandom are not deterministic due to their dependence on pseudo-random number generators. For the sake of reproducibility, we fixed 30 random seed values. Executing Random or QRandom with these random seeds allows us to average the results to mitigate the random noise while generating the same tests whenever we rerun the experiments. Seed values are useless for DJ and DJPlus because these methods are entirely deterministic.

64 53

RND/EC DJPlus/EPC QRND/EC

251 258 58

RND/EC DJPlus/EPC QRND/EC

1,346 346

RND/EC DJPlus/EPC QRND/EC

2,744 585

TLC

EC 18 36 144 259

RISC-V

VC 10 16 75 129

RND/EC DJPlus/EPC QRND/EC

3,124

Parabank

SUT TLC RISC-V Parabank Testinium

# Test steps 5K 10K 15K 20K 25K 30K 35K 40K 1,076

0

17,312

Testinium

Table 4 The number of test requirements for SUT-criterion pairs, generated by GWPlus.

Fig. 11. The number of test steps by Random (RND) and QRandom (QRND) for EC and DJPlus for EPC, where the numbers next to the boxplots show the average values.

RQ1. We consider the PPC to be infeasible because it is not scalable as described in Section 5.2.1. A recent study stated that the EC with GraphWalker for Testinium, the largest SUT model in our experiments, is feasible (Garousi et al., 2021). Considering the feasibility of the EPC, we atypically compare the test steps DJPlus generates for the EPC against the test steps generated by the state-of-the-art tools for EC, and argue that any number of test steps that is below the number of test steps used for the EC should be feasible. Since the DJPlus test suite for the EPC is betweeen Random and QRandom’s test suites for the EC,

5.2. Empirical results In the following sections, we discuss the results from running the three phases of our experimental setup with different configurations, while addressing the research questions in the process. 5.2.1. Phase 1: Test requirement generation We present the number of GWPlus-generated test requirements for our experimental SUTs and target criteria in Table 4. Note that the number of test requirements for VC and EC is the same as the number of vertices and edges of the SUT model. From Table 4, as the model grows in size, we observe that the number of test requirements for the PPC exceeds a million, which is a significant scalability problem for the PPC, whereas the EPC remained within comparatively reasonable boundaries. Thus, the PPC does not scale well, while the other criteria are relatively more scalable. Therefore, we discard the PPC setting for the rest of our experiments.

The EPC is feasible with DJPlus for realistic SUT models. RQ2. We present the number of test steps generated by DJ and DJPlus for all SUTs and test criteria in Fig. 12, where both methods are entirely deterministic and exhibit zero variance. The gap between DJ and DJPlus grows as the model sizes grow. The most significant gap occurs when both methods target the EPC on Testinium. For all experimental configurations in Fig. 12, DJPlus either generated the same number of test steps as or fewer than DJ. Thus,

5.2.2. Phase 2: Test generation Fig. 11 shows, with boxplots, for all the four SUT models from the smallest to the largest, the distributions of the number of steps of three experimental configurations. These configurations are Random for the EC (RND/EC), DJPlus for the EPC, and QRandom for the EC (QRND/EC). The boxplots represent the distribution of the number of test steps for all 30 seed values, with the numbers adjacent to the boxplots indicating the average, denoted by a bullet within the box. According to Fig. 11, Random’s variance in the number of test steps grows as the model size grows. DJPlus has zero variance because it is a deterministic method. So, the average of DJPlus is the number of test steps it always generates. Surprisingly, QRandom’s variance is nonzero but almost negligible compared to Random.

DJPlus generates test suites with fewer test steps than the state-of-the-art method, DJ. Test Generation Times. We provide the test generation times of our experiments in Table 5. According to these results, for small models, like TLC and RISC-V, the test generation time of any configuration, regardless of its method or test criterion strength, was below three seconds. However, our largest model, Testinium, when the test criterion is the EPC, required two to three minutes with the available tools. DJPlus particularly appears to have the worst scalability, as it took around 186 seconds for it to generate the Testinium test suite for the EPC. On the other hand, a previous study reported that it took six hours to execute the tests for Testinium (Garousi et al., 2021). So, for 11

0

DJ/VC DJPlus/VC DJ/EC DJPlus/EC DJ/EPC DJPlus/EPC

33 23 122 54 973 258

DJ/VC DJPlus/VC DJ/EC DJPlus/EC DJ/EPC DJPlus/EPC

157 133 390 222

DJ/VC DJPlus/VC DJ/EC DJPlus/EC DJ/EPC DJPlus/EPC

347 285 1,130 386

Method Random QRandom DJ DJPlus Method Random QRandom DJ DJPlus

Parabank

9 9 54 54 67 64

TLC

4K

DJ/VC DJPlus/VC DJ/EC DJPlus/EC DJ/EPC DJPlus/EPC

RISC-V

2K

Table 5 Average test generation times for all SUTs and test criteria, in seconds.

# Test steps 6K 8K 10K 12K 14K

4,419 1,346

Method Testinium

12,817

DJ DJPlus

Vertex Criterion (VC) System Under Test (SUT) TLC RISC-V Parabank Testinium 1.252 1.221 1.450 2.037 1.189 1.246 1.315 1.410 1.168 1.213 1.345 3.078 1.205 1.183 1.375 1.443 Edge Criterion (EC) System Under Test (SUT) TLC RISC-V Parabank Testinium 1.292 1.278 1.633 2.561 1.210 1.260 1.378 1.423 1.186 1.237 1.561 4.401 1.202 1.237 1.625 3.983 Edge-Pair Criterion (EPC) System Under Test (SUT) TLC RISC-V Parabank Testinium 1.208 2.647 9.866 122.635 1.227 2.605 14.775 186.631

Table 6 Average redundancy factors (RF) and relative redundancies (RR) over DJPlus.

2,744

Test Generation Method (T ) Random DJ QRandom DJPlus

Fig. 12. The number of test steps by DJ and DJPlus for all test criteria.

our experimental SUTs, we identified the test execution time as the bottleneck, not the test generation time. To comment more on the test generation times, models much larger than our largest, Testinium, are necessary.

RF(T ) 4.32 0.49 0.28 0.17

RR(T, DJPlus) 26.21x 4.24x 2.06x −

factor; a test suite can be many times redundant than the theoretical optimal. We define the relative redundancy of a test suite (T ) over another (U) as ! RF(T ) −1 . (17) RR(T, U) = RF(U)

RQ3. Since Random, QRandom, and DJ all satisfy the same test requirements with more test steps, the utility provided by their extra steps comes into question. We recognize the fact that these extra steps are unnecessary in terms of the test criterion but may still make a difference under a stronger criterion. In light of the above perspective on redundancy, we define the edge-pair redundancy factor of a test suite as P t∈T,|t|>2 (|t| − 2) RF(T ) = −1 (16) Cepc (T )|TRepc |

We express relative redundancy such that it shows how many times more redundant T is than U. Unlike the redundancy factor, relative redundancy can be negative, meaning that T is less redundant than U. We present the average redundancy factors and relative redundancies of Random, DJ, QRandom, and DJPlus in Table 6, which we explain further in Appendix C. According to these results, on average, DJPlus is the least redundant method and

where the numerator is the total number of edge pairs in the test suite and the denominator is the total number of distinct edge pairs the test suite covers. We calculate the denominator by multiplying the test suite’s edge-pair coverage ratio6 (Cepc (T )) and the total number of edge pairs in the graph model (|TRepc |). After subtracting one from the ratio, we obtain a nonnegative redundancy factor (RF(T )). If the redundancy factor is zero, the test suite is optimal, i.e., cannot be further minimized without sacrificing coverage. There is no upper limit to the redundancy

QRandom, DJ, and Random generate between 2 to 26 times more redundant test steps than DJPlus. 5.2.3. Phase 3: Test execution We present log-log plots of the average test execution time versus the number of test steps for TLC, RISC-V, and Parabank in Fig. 13, where an average execution time is the average of ten re-executions of the same test suite. To produce these plots, we

6 A coverage ratio is a coverage percentage divided by 100. Multiplying the coverage ratio (Cepc (T )) and the total number of edge-pairs (|TRepc |) gives us exactly the number of distinct edge-pairs covered by T .

12

TLC

# Steps

RISC-V

Parabank

PCC ≈ 0.999999

PCC = 1.000000

103

PCC ≈ 0.998508

102 101 102

103

104 105 Time (ns)

106

102

103

104 105 Time (ns)

106

102

103

104 105 Time (s)

106

Fig. 13. Log-log plots of average test execution time vs. number of test steps for TLC, RISC-V, and Parabank (PCC: Pearson Correlation Coefficient).

The redundancy of some test steps in a test suite with respect to a coverage criterion does not mean they are redundant for other purposes. A good example is stress testing, where a test case repeatedly re-executes the same parts of an SUT to wear it down. The redundant test steps also have some potential to facilitate fault detection. To the best of our knowledge, an evaluation of GraphWalker’s coverage-redundant test steps with respect to these criteria is an open question in the literature. A recent study investigates the possibility of redundant GraphWalker test steps increasing edge-pair coverage, finding that the cost of a unit increase in edge-pair coverage through redundant GraphWalker steps grows exponentially (Köroğlu et al., 2025).

used the DJ and DJPlus test suites, and the medians of the Random and QRandom test suites for all the percentages of vertex and edge coverage. Finally, PCC stands for Pearson Correlation Coefficient, which is an effect size metric. A PCC value close to one indicates a positive linear correlation. RQ4. All the PCC values for TLC, RISC-V, and Parabank indicated a strong linear correlation, meaning that in our experiments, few test steps resulted in low execution times and vice versa. Thus, DJPlus decreases the execution times by reducing the number of test steps.

6.3. Reproducibility In the first two phases (test requirement and test generation), we control the sources of randomness, so our experiments are fully reproducible. However, the last phase involves measuring test execution times that depend on the environment and therefore suffer from random noise. By re-executing the same test ten times, we decreased the effects of random noise. So, even if the exact test execution times we obtained are not reproducible, their trends are replicable.

6. Discussion We discuss the issues regarding the impact, redundancy, reproducibility, generalizability, and correlation analysis of our method, DJPlus, and its evaluation in the following sections. 6.1. Impact The impact of decreasing test execution times depends on the testing practice. Minimization is not critical if test execution is a one-off. The same is not the case with coverage-based testing, in which developers maintain test cases to ensure software quality and re-execute them whenever an SUT is updated. Thus,

6.4. Generalizability With a limited number of SUTs to evaluate testing methods, the generalizability of our results to an arbitrary SUT is always a question. To mitigate bias, we selected realistic SUTs with existing models of varying sizes and implementations from two distant domains, hardware and web applications.

a reduced test suite for strong coverage is highly desirable in coverage-based testing, where the adoption of an MBT approach in an industrialscale continuous integration / continuous development process depends on the approach being affordable within a limited testing budget.

6.5. Correlation In Section 5.2.3, we show that the number of test steps and the execution time of a test suite are strongly correlated. We get these results from our controlled experiments, where the number of test steps is the only independent variable, i.e, the only factor that we change to produce the scatter plots in Fig. 13. Thus,

6.2. Redundancy The topography of a graph model limits the minimum attainable redundancy factor due to critical components, which are subgraphs that a test case cannot avoid traversing multiple times to achieve a coverage target.

reducing test steps “causes” a decrease in test execution times. 13

6.6. Graph coverage

identify the shortest detours that pass the guarded edges. Also, we plan to revise the test requirement generation method to obtain minimal test suites for coverage percentages below 100%. Finally, we will use mutation analysis to measure the fault detection capabilities of DJPlus-generated tests.

The test criteria we use throughout this paper correspond to metrics that measure the coverage of the model and not the implementation of the SUT. Therefore, the increased strength that comes with replacing the VC and the EC with the EPC does not necessarily translate to code coverage. Moreover, the completeness of the model is crucial to observe the positive effects of the increased strength; if a graph does not model a key SUT behavior, no test criterion can cover that behavior. For this paper, we assume that the model sufficiently captures the relevant SUT behaviors, leaving the verification of the model as a separate topic.

Appendix A. Graph models in DJ In this section, we describe the necessary definitions for graph models to understand DJ and the motivating examples related to DJ / DJPlus. DJ, and its improved version, DJPlus, generate tests from graph models.

6.7. Test oracles

Appendix A.1. Graph models with simple graphs

DJPlus only generates the executable tests for our experimental SUTs. The GraphWalker environment allows the automation of the test execution. The test oracles are implemented as assertions related to the elements of the graph model, where a test oracle indicates pass if no assertion is violated and fail, otherwise. In this work, the coverage of a test set is measured by counting the number of targeted model elements it covers. Therefore, our experimental results are not affected by the absence of a specific test oracle.

A graph model M = (G, ve ) in DJ is a pair of a simple graph G = (V, E), E ⊆ V 2 and an entry vertex ve ∈ V, where V is a set of vertices and E ⊆ V 2 is a set of edges connecting pairs of vertices. The model’s graph is called simple because it does not allow different edges connecting the same vertex pair. Appendix A.2. Test cases A test case (test path) t is a vertex sequence whose first vertex is the entry vertex t[0] = ve , and every consecutive vertex pair is an edge. The last vertex of a test case t is its target, defined def as tgt(t) = t[|t| − 1], where |t| denotes the length of the test case, calculated as the total number of its vertices. We also say that a test case t contains |t| many test steps, where every step corresponds to a vertex. We formally define a path as a subset of vertex sequences P(G) that satisfy the edge property as

6.8. Feasibility To determine the feasibility of the test steps generated by DJPlus to achieve EPC, we compare them against the test steps generated by Graphwalker to achieve EC. This is not a like-forlike comparison because EPC is a stronger criterion and tend to require longer test suites. However, since Graphwalker test suites achieving EC for Testinium (the largest SUT in our study) are shown to be feasible (Garousi et al., 2021), any smaller or equally large test suite achieving EC or stronger coverage can be said to be feasible as well.

P(G) = {p : p ∈ V ∗ , ∀i ∈ N, 1 ≤ i < |p|, (p[i − 1], p[i]) ∈ E}. def

Appendix A.3. Loops and cycles A path p is a loop iff it has exactly two vertices and its vertices are the same, i.e., |p| = 2, p[0] = tgt(p). A cycle, on the other hand, is a non-empty path whose target vertex has an edge def to its first vertex, i.e., ⃝p ↔ |p| ≥ 1, (tgt(p), p[0]) ∈ E. A simple graph G = (V, E), E ⊆ V 2 is acyclic if it has no cycles, i.e., def ⃝G ↔ ∀p ∈ P(G), ⃝p.

7. Conclusions In this paper, we proposed a novel method, DJPlus, that generates reduced amount of test steps within a minimized number of test cases for graph-based models. We gave the reasons behind generating minimal test suites, demonstrated the suboptimalities with examples, and provided a detailed description of DJPlus. Then, we presented experimental results on four realistic SUTs within the popular GraphWalker environment. We showed that DJPlus generated the fewest test steps for the same coverage target, while the other methods generated 2 to 26 times more redundant test steps. We revealed that the prime path criterion does not scale well, but the edge-pair criterion is feasible with DJPlus on our four experimental SUTs. Finally, we measured test execution times and performed an effect size analysis to show that DJPlus-generated test suites indeed reduce test execution costs. In the future, we seek to expand DJPlus to graphs with conditional edges, where the edge is enabled only if its condition holds. These conditions are called guards and are already available as a feature in GraphWalker. We aim to modify DJPlus to

Appendix A.4. Sequence operations Throughout the paper, we use several operations on vertex sequences. The first is taking the prefix (history) of a sequence. The prefix of a vertex sequence sq is the subsequence of sq that excludes only the target vertex, i.e.,   |sq| < 2 () def  pre(sq) =     |sq| ≥ 2 sq 0 . . . |sq|92

14

where () is an empty sequence. ⟲) a vertex sequence sq removes its target vertex Rotating (⟲ and puts it in front, as in   |sq| = 0 () def  ⟲ sq =   |sq| > 0 (tgt(sq)) · pre(sq)

where · denotes the concatenation of two sequences. In this paper, rotation involves cycles, which remain valid paths after any number of rotations. Finally, the splice of two paths p ⊙ q is the set of shortest paths that start with p[0] and end with tgt(q), as in

Algorithm 3 Path splicing (p ⊙G q) 1: Input: 2: G = (V, E), E ⊆ V 2 3: p ∈ P(G) \ V 0 4: q ∈ P(G) \ V 0 5: Output: 6: R ⊆ P(G) \ V 0 7: i ← min(|p|, |q|) 8: while i > 0 and p[|p|9i . . . |p|91] , q[0 . . . i91] do i ← i − 1 9: if i > 0 then R ← {p · q[i . . . |q|91]} 10: else R ← {} foreach c ∈ CG (p, q) do R ← R ∪ {p · c · q}

def

p ⊙ q = {r : r ∈ SP, ∀s ∈ SP, |r| ≤ |s|} where SP = {r : r ∈ P(G)\V 0 , p ⊑ r, q ⊑ r, r[0] = p[0], tgt(r) = tgt(q)} def

and ⊑ denotes the subpath relation between two paths. The literature leaves path splicing unnamed and denotes it with the set union symbol, like p ∪ q (Dwarakanath and Jankiti, 2014). For convenience, we named it and used the p⊙q notation to avoid confusion with set union.

Generating each test requirement of the vertex criterion is straightforward; take every vertex of the graph as a separate test requirement. The edge criterion (TRec ) is the set of all test requirements with a history up to length one. A test suite that satisfies the edge criterion reaches a target vertex from every possible predecessor. The edge criterion is stronger than the vertex criterion. To get the test requirements for the edge criterion, one must take every edge of the graph as a separate test requirement. The edge-pair criterion (TRepc ) is the set of all test requirements with a history up to length two. A straightforward way to generate these test requirements is to compute all non-empty paths up to length three and then remove the redundant ones, i.e., the paths that are strict subpaths of others. The edge-pair criterion is stronger than both edge and vertex criteria. The prime path criterion (TRppc ) is the set of all test requirements with a unique history of arbitrary length, where a unique history contains no vertex more than once, and can include the target vertex only at the beginning. The prime path criterion is stronger than vertex and edge criteria, but not edge-pair criterion. As a final note, algorithms that generate a minimal set of requirements for therime path criterion are well-known (see Appendix B.2).

Appendix A.5. Strong connectivity We assume the reachability of every vertex v ∈ V from the entry vertex ve , and say that ve is strongly connected to every other vertex. We denote this fact as ∀v ∈ V, ve ⇝ v and define it as def ve ⇝ v ↔ ∃r, r ∈ (ve ) ⊙ (v). Appendix A.6. Test suites, requirements, and criteria A test suite T is a set of test cases. We define test requirements and criteria to measure the strength of a test suite. A test requirement tr is a path that must be covered by a test suite7 . So, the test suite must be generated such that every test requirement must be a subpath of at least one of the test cases. A test criterion is a set of test requirements. Formally, we define a test criterion TR as a subset of all possible test requiredef ments TR(G) such that TR(G) = P(G) \ V 0 , where we exclude 0 empty paths, i.e., V . The literature defines general sets of test requirements known as graph coverage criteria (Ammann and Offutt, 2016, Part 2, Ch. 7). A test requirement is redundant iff it is a subpath of at least one of the other test requirements. A minimal test criterion is free of redundant requirements. From now on, whenever we discuss a test criterion, we refer to a minimal one. A criterion TR1 subsumes another criterion TR2 iff every requirement tr2 ∈ TR2 is a subpath of a tr1 ∈ TR1 . Under this relation, we say that the criterion TR1 is stronger than TR2 . In this study, we focus on vertex, edge, edge-pair, and prime path criteria8 . The vertex criterion (TRvc ) of a graph model is the set of all test requirements with an empty history. A test suite that satisfies the vertex criterion covers every vertex at least once .

Appendix B. Known algorithms To make this paper self-contained, we present the known algorithms we used in this section. Appendix B.1. Computing a splice We present the steps to splice two paths in Algorithm 3. In lines 7-8, we compute the length of overlap between p and q, i.e., the last i vertices of p that are equal to the first i vertices of q. If there is an overlap (i > 0), the only splice is the concatenation of p with the remainder of q, as in line 9. Else, we concatenate p with c and then q, where c ∈ CG (p, q) is every shortest path that connects p and q. Computing c is equivalent to computing all shortest paths from tgt(p) to q[0]. Another option is to compute all-pairs shortest paths beforehand, which is useful from the MBT perspective. We refer to the literature for the ever-growing research to accomplish these tasks (Thorup,

7 Broadly, a test requirement is a specific element of a software artifact that a test case must cover (Ammann and Offutt, 2016). The definition a test requirement we use here is specific to graph models. The literature also uses testing target to refer to this concept Arcuri et al. (2012). 8 We refer to the literature for a comprehensive list of graph coverage criteria (Ammann and Offutt, 2016, Part 2, Ch. 7).

15

Algorithm 4 Prime path generator

Algorithm 6 Hypergraph generation

1: Input: 2: G = (V, E), E ⊆ V 2 3: Output: 4: TRppc ⊆ TR(G) 5: TRppc ← E 6: repeat 7: c ← 0, U ← TRppc 8: foreach tr1 ∈ U s.t. ⃝tr1 do 9: foreach (v, tr1 [0]) ∈ E s.t. v < pre(tr1 ) do 10: c←1 11: foreach tr2 ∈ TRppc s.t. tr2 ⊑ (v) · tr1 do 12: TRppc ← TRppc \ tr2 13: end foreach 14: TRppc ← TRppc ∪ {(v) · tr1 } 15: end foreach 16: end foreach 17: until c = 0

1: Input: 2: G = (V, E), E ⊆ V 2 3: S = (VS , ES ), VS ⊆ P(G), ES ⊆ VS2 4: Output: 5: H ∈ (S ∪ H(S ) ∪ H(H(S )) ∪ . . .)∗ s.t. H[0] = S , ⃝tgt(H), ∀i[i ∈ N, 0 < i < |H|] → H[i] = 2 (VH[i] , E H[i] ), VH[i] ⊆ P(H[i91]), E H[i] ⊆ VH[i] 6: H ← (S ), i ← 0 7: repeat 8: i ← i + 1, H[i] ← H[i91], s ← () for e ∈ E H[i] do s ← s · (e) 9: while |s| > 0 and H[i91] = H[i] do 10: p ← tgt(s), s ← pre(s) 11: if ⃝p then 12: VH[i] ← VH[i] ∪ {(hi )} 13: foreach v ∈ VH[i] \ {(hi )} s.t. v < p do 14: if ∃ j, j ∈ N, j < |p|, (v, p[ j]) ∈ E H[i] then 15: E H[i] ← E H[i] \ (v, p[ j]) 16: E H[i] ← E H[i] ∪ (v, hi ) 17: end if 18: if ∃ j, j ∈ N, j < |p|, (p[ j], v) ∈ E H[i] then 19: E H[i] ← E H[i] \ (p[ j], v) 20: E H[i] ← E H[i] ∪ (hi , v) 21: end if 22: end foreach 23: foreach v ∈ p do VH[i] ← VH[i] \ {v} 24: else 25: foreach v ∈ VH[i] s.t. v < pre(p), (v, p[0]) ∈ E H[i] do 26: s ← s · ((v) · p) 27: end foreach 28: end if 29: end while 30: H ← H · (H[i]) 31: until H[i91] = H[i] 32: H ← pre(H)

Algorithm 5 Splice graph generation 1: Input: 2: M = (G, ve ), G = (V, E), E ⊆ V 2 , ve ∈ V 3: TR ⊆ TR(G) 4: Output: 5: S = (VS , ES ), VS ⊆ P(G), ES ⊆ VS2 6: VS ← {(ve )} ∪ TR, ES ← {} 7: foreach v ∈ VS do 8: foreach y ∈ TR \ {v} do 9: ES ← ES ∪ {(v, y)} 10: foreach r ∈ v ⊙G y and while (v, y) ∈ ES do 11: if ∃z, z ∈ TR\{v, y}, z ⊑ r then ES ← ES \{(v, y)} 12: end foreach 13: end foreach 14: end foreach 15: S ← (VS , ES )

Appendix B.3. Computing splice graphs We present the formal steps to generate a splice graph in Algorithm 5. We modify the original algorithm to cover the case when there are more than one splice v ⊙G y. For more details, we refer to the literature that first presented this algorithm (Dwarakanath and Jankiti, 2014, Algorithm 2).

2004; Williams, 2018). Finally, if a path that connects p to q does not exist, then the splice remains an empty set. The original authors of path splicing did not consider the fact that there could be multiple splices of two vertices, probably because the test requirement pairs from vertex, edge, edge-pair, and prime path coverages all generate at most one splice (Dwarakanath and Jankiti, 2014). Our variant of path splicing enables the test generation to work with any set of test requirements, even manually crafted ones.

Appendix B.4. Computing hypergraphs We present the formal steps to generate hypergraphs in Algorithm 6. Notice that in this variant, we chose to remove the shortest cycle first because finding the shortest cycle is computationally cheaper and relatively easier to implement than a longest-simple-cycle-first heuristic. We refer to the literature for an algorithm that finds the longest simple cycle in a graph (Anaqreh et al., 2023).

Appendix B.2. Computing prime paths Algorithms that compute a minimal set of test requirements for prime paths are well-known (Ammann and Offutt, 2016, Part 2, Ch. 7). The literature also features equivalent variants of the same algorithm (Dwarakanath and Jankiti, 2014). We provide our variant in Algorithm 4, which follows our definition of the prime path criterion closely.

Appendix B.5. Unwinding We present the formal steps of unwinding hyperpaths in Algorithm 7. This algorithm takes a sequence of hypergraphs H, and a sequence of vertex sequences of the final hypergraph, e.g., Eq. (3). It outputs a sequence of paths of the first hypergraph. 16

Algorithm 7 Unwinding hyperpaths

Algorithm 8 Unrolling hyperpaths

1: Input: 2 2: H[0] = (VH[0] , E H[0] ), E H[0] ⊆ VH[0] 3: ∀i[i ∈ N, 0 < i < |H|] → H[i] = (VH[i] , E H[i] ), VH[i] ⊆ 2 P(H[i91]), E H[i] ⊆ VH[i] ∗∗ 4: π ∈ Vtgt(H) 5: Output: 6: p ∈ P(H[0])∗ 7: for i = |H| − 1 to 1 do 8: p←π 9: for j = 0 to |π| − 1 do 10: π[ j] ← () 11: for k = 0 to |π[ j]| − 1 do 12: if p[ j][k] ∈ VH[i91] then π[ j] ← π[ j] · (p[ j][k]) 13: else 14: q ← (v) s.t. v ∈ VH[i91] \ VH[i] 15: while ⃝q do 16: q ← (v) · q s.t. v ∈ VH[i91] \VH[i] , (v, q[0]) ∈ E H[i91] 17: end while 18: r ← pre(q), s1 ← s s.t. s ∈ π[ j]⊙H[i−1] r⊙H[i−1] p[ j][k+1 . . . |p[ j]|91] 19: repeat |r| − 1 times 20: r ← ⟲r 21: s2 ← s s.t. s ∈ π[ j]⊙H[i−1] r⊙H[i−1] p[ j][k+1 . . . |p[ j]|91] 22: if |s2 | < |s1 | then s1 ← s2 23: end repeat 24: π[ j] ← pre(s1 ) 25: end if 26: end for 27: end for 28: end for

1: Input: 2 2: H[0] = (VH[0] , E H[0] ), E H[0] ⊆ VH[0] 3: ∀i[i ∈ N, i < |H|] → H[i] = (VH[i] , E H[i] ), VH[i] ⊆ 2 , ⃝tgt(H) P(H[i91]), E H[i] ⊆ VH[i] 4: Output: 2 5: RFG = (VRFG , ERFG ), ERFG ⊆ VRFG , ⃝RFG 6: VRFG ← Vtgt(H) , ERFG ← Etgt(H) 7: RFG ← minimize(VRFG , ERFG ) 8: for i = |H| − 1 to 1 do 9: h ∼ h[0 . . . |h|], h′ ∼ h′ [0 . . . |h|] s.t. h ∈ VH[i]\VH[i91] , ∀j[ j ∈ N, j < |h|] → h[ j] ∈ VH[i91]\VH[i] 10: for j = 0 to |h| − 1 do 11: VRFG ← VRFG ∪ {h[ j], h′ [ j]} 12: ERFG ← ERFG ∪ {(h[ j], ()), (h′ [ j], ())} 13: foreach v ∈ VH[i91] ∩VH[i] s.t. (v, h[ j]) ∈ E H[i91] do 14: ERFG ← ERFG ∪ {(v, h[ j]), (v, h′ [ j])} 15: end foreach 16: foreach v ∈ VH[i91] ∩VH[i] s.t. (h[ j], v) ∈ E H[i91] do 17: ERFG ← ERFG ∪ {(h[ j], v)} 18: if (v, h′ ) < ERFG then ERFG ← ERFG ∪ {(h′ [ j], v)} 19: end foreach 20: if j > 0 then 21: ERFG ← ERFG ∪ {(h[ j91], h[ j]), (h′ [ j91], h′ [ j])} 22: end if 23: end for 24: ERFG ← ERFG ∪ {(tgt(h), h′ [0])} 25: foreach v ∈ VRFG do 26: ERFG ← ERFG \ {(h, v), (v, h)} 27: end foreach 28: VRFG ← VRFG \ {h} 29: RFG ← minimize(VRFG , ERFG ) 30: end for

Algorithm 7 converts the vertex sequences of an hypergraph to vertex sequences of the preceding hypergraph until there is no preceding hypergraph. In line 12, it copies the elements that are in both hypergraphs. Otherwise, it reconstructs the cycle represented by the hyperpath in lines 14-17. Then, finds the rotation of this cycle’s prefix that generates the shortest splice in lines 18-23. This shortest splice replaces the path in line 24.

adds one hyperpath per new hypergraph. The reconstruction is arbitrary, e.g., h = (h[0], h[1], h[2]) could be reconstructed as h = (h[2], h[0], h[1]) because it corresponds to a cycle of the preceding hypergraph H[i − 1]. The arbitrariness is irrelevant because the order of the vertices is not important. For every reconstructed vertex h[ j], the algorithm also constructs h′ [ j]. Algorithm 8 adds every vertex of h’s cycle to RFG in line 11. Note that it adds every vertex twice, like h[ j] and h′ [ j]. Then, it connects every added vertex to the sink in line 12. In line 14, the algorithm reconstructs the hyperpath’s incoming edges. In lines 17 and 18, the algorithm reconstructs the hyperpath’s outgoing edges, where the if statement preserves the acyclicity of RFG, e.g., in Fig. 8d, ((v1 ), (v2 )) is an edge, so technically, ((v1 )′ , (v2 )) is also valid. Thanks to this if statement, the algorithm ignores that edge to avoid introducing cycles. Every consecutive vertex pair in the cycle forms a valid edge, so the algorithm makes these connections in line 21. Finally, it connects the last vertex of the cycle tgt(h) to h′ [0] in line 24. Notice that the algorithm refrains from connecting (tgt(h), h[0]), (tgt(h′ ), h[0]), and (tgt(h′ ), h′ [0]), all of which would introduce a cycle. As a result, the algorithm preserves the acyclicity of RFG. Algorithm 8 removes all the edges to and from h in line 26

Appendix B.6. Unrolling We present the formal steps of our novel unrolling algorithm in Algorithm 8. The input is a sequence of hypergraphs, starting from H[0]. Each successor hypergraph’s vertices are some paths of the predecessor. The final hypergraph tgt(H) is acyclic. The output (RFG) is an acyclic simple graph. Algorithm 8 starts by copying the final hypergraph tgt(H) to RFG in line 6. tgt(H) is acyclic, so the algorithm performs flow minimization on RFG in line 7, which removes some of the edges. In line 8, Algorithm 8 loops through all hyperpaths in the reverse order of their construction. At every iteration, it reconstructs the vertices of the hyperpath h ∈ VH[i] \ VH[i91] in line 9. There is only one such hyperpath because Algorithm 6 17

Table C.7 Redundancy factors and relative redundancies of two test suites for Testinium.

Test suite (τ) DJPLUS/VC QRND/VC/16

||τ|| 285 537

|τ| 1 1

more redundancies than the DJPlus-generated test suite. We calculate its relative redundancy as

Cepc (τ) |TRepc | RF(τ) RR(τ, U) 0.25 1,033 0.0958 − 0.35 1,033 0.0797 4.006x ||τ||: Total number of test steps in τ. |τ|: Total number of test cases in τ.

0.4797 − 1 ≈ 4.006 0.0958 which means that QRandom was 4 times more redundant than DJPlus for this configuration, while getting only 10% more edge-pair coverage for this cost. Overall, we calculate the average across all vertex and edge coverage percentages, all SUTs, and all seed values to obtain one redundancy factor and one relative redundancy percentage per test generation method. RR(τ, U) =

and finally removes h in line 28. It does not remove h′ because that is the only way to traverse the same vertex thrice or more times in the test suite, whenever it is necessary. As the resulting RFG remains acyclic, the algorithm performs a re-minimization in line 29, where every vertex decorated with an apostrophe must have at least zero outgoing flow. Every other vertex must have at least one outgoing flow. Thus, re-minimization removes some edges and some of the decorated vertices. In the end, the resulting RFG contains only test requirements along with the source and sink vertices.

Appendix D. Line graphs In this section, we formally define line graphs and show the relationship between test criteria over a graph and its line graph. First formally define a multigraph whose line graph is utilized in Section 4.4. A multigraph MG is a triple such that MG = (V, EL, E), E ⊆ V × EL × V, where EL is a set of edge labels that enable multiple edges between the same vertex pair in the set of edges E. A line graph L(MG) of a multigraph MG = (V, EL, E), E ⊆ V × EL × V is a simple graph L(MG) = (VL , E L ), E L ⊆ VL2 , such that 1. VL = EL and 2. ∃(v0 , a, v1 ) ∈ E, ∃(v1 , b, v2 ) ∈ E ↔ (a, b) ∈ E L .

Appendix C. Computing redundancies To calculate the averages in Table 6, we start by rewriting Eq. (16) as RF(T ) = RF(τ) =

||τ|| − 2|τ| − 1, where Cepc (τ)|TRepc |

1. τ = {t : t ∈ T, |t| > 2}, P 2. ||τ|| = t∈τ |t|, and 3. Cepc (T ) = Cepc (τ); as no test case t ∈ T \ τ has edge pairs.

We prove the equivalence between the VC of L(MG) and the EC of MG by using the fact that VL = EL. From this fact, it follows that covering all the vertices in the line graph must cover all the edge labels in the multigraph, and vice versa. We prove the equivalence between the EC of L(MG) and the EPC of MG by considering the set of all edge pairs in MG, which can be shown as EL2 . Since VL = EL, the set of all vertex pairs in the line graph VL2 must be the same as EL2 . Therefore, the EC of the line graph is equivalent to the EPC of the multigraph.

The redundancy factor is undefined for empty test suites and graphs with no edge pairs. Thankfully, τ is never empty and all graphs have some edge pairs in our experiments. We compute the relative redundancy of τ over U, where U corresponds to the test suite with the same experimental settings but generated by DJPlus. The relative redundancy RR(τ, U) is undefined when RF(U) = 0; we compare relative redundancies only when DJPlus also has some redundancy. The two rows in Table C.7 illustrate the computation of the redundancy factor and the relative redundancy for two arbitrary experimental configurations in Testinium. The redundancy factor for the test suite generated by DJPlus for the vertex criterion (DJPlus/VC) is RF(τ) =

CRediT authorship contribution statement Yavuz Köroğlu: Conceptualization, Methodology, Software, Investigation, Data curation, Formal analysis, Writing – original draft, Writing – review & editing, Funding acquisition, Visualization; Mutlu Beyazıt: Conceptualization, Validation, Investigation, Resources, Writing – original draft, Writing – review & editing; Onur Kılınççeker: Conceptualization, Validation, Investigation, Resources, Writing – original draft, Writing – review & editing; Serge Demeyer: Writing – review & editing, Supervision, Funding acquisition, Project administration; Franz Wotawa: Writing – review & editing, Supervision, Funding acquisition, Project administration;

285 − 2(1) − 1 ≈ 0.0958 > 0 (0.25)(1,033)

which means that τ covers some edge pairs more than once. For this configuration, τ = U, so the relative redundancy is ! ! RF(τ) RF(U) RR(τ, U) = −1 = − 1 = 0% RF(U) RF(U) which is meaningless, so we do not report it. The relative redundancy is useful for test suites generated by other methods. The second test suite comes from QRandom, targeting vertex coverage, using the 16th experimental seed value. This configuration results in a higher redundancy factor, meaning that τ has

Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. 18

Bicchierai, I., Araniti, E., Matheu-García, S.N., Gil, J.F.M., 2023. Validating the BIECO security evaluation methodology within a smart grid monitoring SW, in: 34th International Symposium on Software Reliability Engineering, ISSRE - Workshops, IEEE, Florence, Italy. pp. 166–173. doi:10.1109/ISSREW60843.2023.00069.

Acknowledgments The work described in this paper is supported by (a) the İstanbul Technical University Scientific Research Project (BAP) under identification number 47709, (b) the Austrian Science Fund (FWF) Cluster of Excellence Bilateral AI under contract number 10.55776/COE12, (c) the European Union under Horizon Europe via the “INNO2MARE” project under grant number 101087348, (d) the Research Foundation Flanders (FWO) via the project “Basecamp Zero” under grant number S000323N, and (e) the Agency for Innovation & Entrepreneurship (VLAIO) via the project “TTRUST” under grant number HBC20230612.

de Castro-Cabrera, M.C., Garcia-Dominguez, A., MedinaBulo, I., 2022. A case study on combining model-based testing and constraint programming for path coverage, in: ICSEA 2022 The Seventeenth International Conference on Software Engineering Advances, ICSEA 2022 Editors Lugi Lavazza, University of Insubria at Varese, Italy. pp. 41–45. URL: https://personales.upv.es/thinkmind/dl/c onferences/icsea/icsea_2022/icsea_2022_1_70_10 048.pdf.

Data availability

Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S., 2025. Maximum flow and minimum-cost flow in almost-linear time. J. ACM 72, 19:1–19:103. doi:10.114 5/3728631.

The dataset and the replication package are available at ht tps://doi.org/10.5281/zenodo.15556723 (Version v2). This package includes instructions on how to replicate our experiments. GWPlus is available at https://zenodo.org/records /15556723/files/gwplus.zip?download=1, so it can be used on other models.

Chetouane, N., Wotawa, F., 2023. Generating concrete test cases from vehicle data using models obtained from clustering, in: IEEE International Conference on Software Testing, Verification and Validation, ICST 2023 - Workshops, Dublin, Ireland, April 16-20, 2023, IEEE. pp. 70–77. doi:10.1109/ ICSTW58534.2023.00024.

References Aho, A.V., Lee, D., 1987. Efficient algorithms for constructing testing sets, covering paths, and minimum flows. AT&T Bell Laboratories Tech. Memo. CSTR159, pp. 1–15. URL: http s://tuhs.v6sh.org/UnixArchiveMirror/Documentat ion/TechReports/Bell_Labs/CSTRs/159.pdf.

Dalal, S.R., Jain, A., Karunanithi, N., Leaton, J.M., Lott, C.M., Patton, G.C., Horowitz, B.M., 1999. Model-based testing in practice, in: Boehm, B.W., Garlan, D., Kramer, J. (Eds.), Proceedings of the 1999 International Conference on Software Engineering, ICSE’ 99, Los Angeles, CA, USA, May 16-22, 1999, ACM. pp. 285–294. doi:10.1145/302405.3 02640.

Alégroth, E., Karl, K., Rosshagen, H., Helmfridsson, T., Olsson, N., 2022. Practitioners’ best practices to adopt, use or abandon model-based testing with graphical models for software-intensive systems. Empir. Softw. Eng. 27, 103. doi:10.1007/S10664-022-10145-2.

Darwish, R., Gwosuta, L.N., Torkar, R., 2017. A controlled experiment on coverage maximization of automated modelbased software test cases in the automotive industry, in: 2017 IEEE International Conference on Software Testing, Verification and Validation, ICST 2017, Tokyo, Japan, March 1317, 2017, IEEE Computer Society. pp. 546–547. doi:10.110 9/ICST.2017.65.

Ammann, P., Offutt, J., 2016. Introduction to Software Testing. Cambridge University Press. doi:10.1017/978131677127 3.

Dias Neto, A.C., Subramanyan, R., Vieira, M., Travassos, G.H., 2007. A survey on model-based testing approaches: a systematic review, in: Proceedings of the 1st ACM International Workshop on Empirical Assessment of Software Engineering Languages and Technologies: Held in Conjunction with the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE) 2007, Association for Computing Machinery, New York, NY, USA. p. 31–36. doi:10.1145/1353673.1353681.

Anaqreh, A.T., G.-Tóth, B., Vinkó, T., 2023. Exact methods for the longest induced cycle problem. CoRR abs/2311.15899. doi:10.48550/ARXIV.2311.15899, arXiv:2311.15899. Arcuri, A., Iqbal, M.Z.Z., Briand, L.C., 2012. Random testing: Theoretical results and practical implications. IEEE Trans. Software Eng. 38, 258–277. URL: https://doi.org/10 .1109/TSE.2011.121, doi:10.1109/TSE.2011.121. Arman, A., Tsaturian, S., 2017. The maximum number of cycles in a graph with fixed number of edges. CoRR abs/1702.02662. URL: https://arxiv.org/abs/ 170 2. 0 26 62, doi:10 . 48 55 0 /A RX IV . 17 02 . 02 66 2, arXiv:1702.02662.

Dwarakanath, A., Jankiti, A., 2014. Minimum number of test paths for prime path and other structural coverage criteria, in: Merayo, M.G., de Oca, E.M. (Eds.), Testing Software and Systems - 26th IFIP WG 6.1 International Conference, 19

ICTSS 2014, Madrid, Spain, September 23-25, 2014. Proceedings, Springer. pp. 63–79. doi:10.1007/978-3-662-4 4857-1_5.

Janicki, M., Katara, M., Pääkkönen, T., 2012. Obstacles and opportunities in deploying model-based GUI testing of mobile software: a survey. Softw. Test. Verification Reliab. 22, 313–341. URL: https://doi.org/10.1002/stvr.460, doi:10.1002/STVR.460.

Elmendorf, W.R., 1970. Automated design of program test libraries. IBM Technial Report TR 00.2089. URL: https: //www.benderrbt.com/Automated%20Design%20of%20 Program%20Test%20Libraries%20-%201970.pdf.

Kaminski, G.K., Praphamontripong, U., Ammann, P., Offutt, J., 2010. An evaluation of the minimal-mumcut logic criterion and prime path coverage, in: Arabnia, H.R., Reza, H., Deligiannidis, L., Cuadrado-Gallego, J.J., Schmidt, V., Solo, A.M.G. (Eds.), Proceedings of the 2010 International Conference on Software Engineering Research & Practice, SERP 2010, July 12-15, 2010, Las Vegas, Nevada, USA, 2 Volumes, CSREA Press. pp. 205–211. URL: https://www.ac ademia.edu/download/30711986/mumcut-prime.pdf.

Ford, L.R., Fulkerson, D.R., 1956. Maximal flow through a network. Canadian Journal of Mathematics 8, 399–404. doi:10.4153/CJM-1956-045-5. Frey, G., Drath, R., Schlich, B., Eschbach, R., 2012. "safety automata" - A new specification language for the development of PLC safety applications, in: Proceedings of 2012 17th International Conference on Emerging Technologies & Factory Automation, ETFA, IEEE, Krakow, Poland. pp. 1–8. doi:10.1109/ETFA.2012.6489536.

Karlsson, S., Causevic, A., Sundmark, D., Larsson, M., 2021. Model-based automated testing of mobile applications: An industrial case study, in: 14th IEEE International Conference on Software Testing, Verification and Validation Workshops, ICST Workshops 2021, Porto de Galinhas, Brazil, April 1216, 2021, IEEE. pp. 130–137. doi:10.1109/ICSTW52544.2 021.00033.

Garousi, V., Keleş, A.B., Balaman, Y., Özdemir Güler, Z., Arcuri, A., 2021. Model-based testing in practice: An experience report from the web applications domain. Journal of Systems and Software 180, 111032. doi:https: //doi.org/10.1016/j.jss.2021.111032.

Karlsson, V.A., Almasri, A., Enoiu, E.P., Afzal, W., Charbachi, P., 2022. Automation of the creation and execution of system level hardware-in-loop tests through model-based testing, in: Proceedings of the 13th International Workshop on Automating Test Case Design, Selection and Evaluation, Association for Computing Machinery, New York, NY, USA. p. 9–16. doi:10.1145/3548659.3561313.

Gautschi, M., Schiavone, P.D., Traber, A., Loi, I., Pullini, A., Rossi, D., Flamand, E., Gürkaynak, F.K., Benini, L., 2017. Near-threshold RISC-V core with DSP extensions for scalable iot endpoint devices. IEEE Trans. Very Large Scale Integr. Syst. 25, 2700–2713. doi:10.1109/TVLSI.2017.265 4506. Gudmundsson, V., Lindvall, M., Aceto, L., Bergthorsson, J., Ganesan, D., 2016. Model-based testing of mobile systems - an empirical study on quizup android app, in: Aceto, L., Francalanza, A., Ingólfsdóttir, A. (Eds.), Proceedings First Workshop on Pre- and Post-Deployment Verification Techniques, PrePost@IFM 2016, Reykjavík, Iceland, 4th June 2016, pp. 16–30. doi:10.4204/EPTCS.208.2.

Kılınççeker, O., Silistre, A., Belli, F., Challenger, M., 2021. Model-based ideal testing of GUI programs-approach and case studies. IEEE Access 9, 68966–68984. doi:10.110 9/ACCESS.2021.3077518. Kılınççeker, O., Türk, E., Belli, F., Challenger, M., 2022. Model-based ideal testing of hardware description language (HDL) programs. Softw. Syst. Model. 21, 1209–1240. doi:10 .1007/S10270-021-00934-6.

Gudmundsson, V., Schulze, C., Ganesan, D., Lindvall, M., Wiegand, R., 2015. Model-based testing of nasa’s gmsec, a reusable framework for ground system software. Innovations in Systems and Software Engineering 11, 217–232. doi:10.1007/s11334-015-0254-6.

Köroğlu, Y., Beyazıt, M., Kılınççeker, O., Demeyer, S., Wotawa, F., 2025. Towards improving automated testing with graphwalker, in: IEEE International Conference on Software Testing, Verification and Validation, ICST 2025 - Workshops, Naples, Italy, March 31 - April 4, 2025, IEEE. pp. 54–58. doi:10.1109/ICSTW64639.2025.10962480.

Hemmati, H., Briand, L.C., Arcuri, A., Ali, S., 2010. An enhanced test case selection approach for model-based testing: an industrial case study, in: Roman, G., van der Hoek, A. (Eds.), Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2010, Santa Fe, NM, USA, November 7-11, 2010, ACM. pp. 267– 276. doi:10.1145/1882291.1882331.

Leal, L., Montecchi, L., Ceccarelli, A., Martins, E., 2020. Using metamodels to improve model-based testing of service orchestrations, in: 25th Pacific Rim International Symposium on Dependable Computing, PRDC, IEEE, Perth, Australia. pp. 130–139. doi:10.1109/PRDC50213.2020.000 24.

Hufkens, L.V., Ricós, F.P., Marín, B., Vos, T.E.J., 2024. Grammar-based action selection rules for scriptless testing, in: Lonetti, F., Guerriero, A., Saadatmand, M., Budnik, C.J., Li, J. (Eds.), Proceedings of the 5th International Conference on Automation of Software Test (AST), ACM, Lisbon, Portugal. pp. 56–65. doi:10.1145/3644032.3644446.

Li, N., Li, F., Offutt, J., 2012. Better algorithms to minimize the cost of test paths, in: Antoniol, G., Bertolino, A., Labiche, Y. (Eds.), Fifth IEEE International Conference on Software Testing, Verification and Validation, ICST 2012, Montreal, 20

QC, Canada, April 17-21, 2012, IEEE Computer Society. pp. 280–289. doi:10.1109/ICST.2012.108.

Evaluation of Novel Approaches to Software Engineering, ENASE 2023, Prague, Czech Republic, April 24-25, 2023, SCITEPRESS. pp. 293–305. doi:10.5220/001175680000 3464.

Lindvall, M., Ganesan, D., Ardal, R., Wiegand, R.E., 2015. Metamorphic model-based testing applied on NASA DAT an experience report, in: Bertolino, A., Canfora, G., Elbaum, S.G. (Eds.), 37th International Conference on Software Engineering, ICSE, IEEE Computer Society, Florence, Italy. pp. 129–138. doi:10.1109/ICSE.2015.348.

Yavuz Köroğlu is an assistant professor at İstanbul Technical University. He received B.Sc., M.Sc., and Ph.D. degrees from Boğaziçi University, Türkiye, in 2014, 2016, and 2023, respectively, and continued his postdoctoral research studies at Graz University of Technology until 2025. His research interests include model-based testing, fuzzing, formal methods, artificial intelligence, bug prediction, and machine learning.

Masri, W., Zaraket, F.A., 2016. Coverage-based software testing: Beyond basic test requirements. Adv. Comput. 103, 79– 142. doi:10.1016/BS.ADCOM.2016.04.003. Mlynarski, M., Güldali, B., Weißleder, S., Engels, G., 2012. Model-based testing: Achievements and future challenges. Adv. Comput. 86, 1–39. URL: https://doi.org/10.101 6/B978-0-12-396535-6.00001-6, doi:10.1016/B978 -0-12-396535-6.00001-6.

Mutlu Beyazıt received a master’s degree from İzmir Institute of Technology, and a Ph.D. degree from the University of Paderborn. After completing his Ph.D. study, he was employed as a full-time Faculty Member of the Department of Computer Engineering, Yaşar University. Currently, he is working as a senior researcher at the University of Antwerp.

Ntafos, S.C., Hakimi, S.L., 1979. On path cover problems in digraphs and applications to program testing. IEEE Trans. Software Eng. 5, 520–529. doi:10.1109/TSE.1979.23421 3. Rumpe, B., 2016. Modeling with UML. Springer. doi:10.100 7/978-3-319-33933-7.

Onur Kılınççeker received a master’s degree from Ege University, and a Ph.D. degree from the University of Paderborn. During his master’s and Ph.D. studies, he was also employed as a research assistant at the Muğla Sıtkı Koçman University and Ege University and then as a researcher at the University of Antwerp. Currently, he is working as a senior researcher at the University of Antwerp. His research interests include software testing, model-based testing, and mutation testing.

Schur, M., Roth, A., Zeller, A., 2013. Mining behavior models from enterprise web applications, in: Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, Association for Computing Machinery, New York, NY, USA. pp. 422–432. doi:10.1145/2491411.2491426. Thorup, M., 2004. Integer priority queues with decrease key in constant time and the single source shortest paths problem. Journal of Computer and System Sciences 69, 330– 353. doi:10.1016/j.jcss.2004.04.003. special Issue on STOC 2003.

Serge Demeyer is a professor at the University of Antwerp and the spokesperson for the NEXOR research consortium on cyber-physical systems. He directs a research lab investigating the theme of “Software Reengineering” (LORE - Lab On REengineering). Serge Demeyer received a “Best Teachers Award" from the Faculty of Sciences at the University of Antwerp and is still very active in all matters related to teaching quality. His main research interest concerns software test automation and how this helps in striking the right balance between reliability (striving for perfection) and agility (optimising for adaptability). He is an active member of the corresponding international research communities, serving in various conference organization and program committees. He has written a book entitled “Object-Oriented Reengineering” and edited a book on “Software Evolution”. He also authored numerous peer reviewed articles, many of them in top conferences and journals.

Tiwari, S., Iyer, K., Enoiu, E.P., 2022. Combining modelbased testing and automated analysis of behavioural models using graphwalker and UPPAAL, in: 29th Asia-Pacific Software Engineering Conference, APSEC, IEEE, Virtual Event, Japan. pp. 452–456. doi:10.1109/APSEC57359.2022.00 061. Utting, M., Legeard, B., Bouquet, F., Fourneret, E., Peureux, F., Vernotte, A., 2016. Recent advances in model-based testing. Adv. Comput. 101, 53–120. URL: https://doi.org/10 .1016/bs.adcom.2015.11.004, doi:10.1016/BS.ADCOM .2015.11.004. Williams, R.R., 2018. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput. 47, 1965–1985. doi:10.113 7/15M1024524. Zafar, M.N., Afzal, W., Enoiu, E.P., 2023. An empirical evaluation of system-level test effectiveness for safety-critical software, in: Kaindl, H., Mannion, M., Maciaszek, L.A. (Eds.), Proceedings of the 18th International Conference on

Franz Wotawa received an M.Sc. in Computer Science (1994) and a Ph.D. in 1996, both from the Vienna University of Technology. He is currently a professor of software engineering at 21

the Graz University of Technology and the head of the Institute of Software Engineering and Artifical Intelligence. His research interests include model-based and qualitative reasoning, theorem proving, mobile robots, verification and validation, and

software testing and debugging.

22