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

• DJPlus generates a minimal number of test cases for strong coverage while reducing test steps.Source: Highlights · p. 2
• 2 to 26 times more redundant test steps are generated by alternative methods than by DJPlus.Source: Highlights · p. 2
• The edge-pair criterion is feasible for realistic systems using DJPlus.Source: Highlights · p. 2
• The prime path criterion poses significant scalability issues in experiments.Source: Highlights · p. 2
• DJPlus decreases test execution times by reducing the number of test steps.Source: Highlights · p. 2

1. Introduction

• Test cases can quickly explode in coverage-directed testing, creating a tradeoff between model-based testing complexity and scalability.Source: §1 · p. 3
• DJ minimizes test-case count but does not optimize test steps, leaving a scalability gap for test generation.Source: §1 · p. 3
• DJPlus is implemented in GraphWalker as GWPlus and evaluated on four realistic systems, with the same coverage achieved using fewer steps.Source: §1 · p. 4
• The study asks whether edge-pair coverage is feasible by comparing DJPlus test steps with GraphWalker’s edge-criterion results.Source: §1 · p. 4
• The evaluation examines test-step reduction against DJ, redundancy relative to DJPlus, and whether fewer steps correspond to shorter execution times.Source: §1 · p. 4

2. Related work

• The related-work discussion frames its focus on graph-based model testing, graph coverage, minimal test generation, and GraphWalker.Source: §2 · p. 4

2.1. MBT with graph models

• Graph models remain central to model-based testing and model-driven engineering, with visualization and interpretability among their benefits.Source: §2.1 · p. 4

2.2. Minimal test generation from graphs

• DJ is described as minimizing test-case count for arbitrary requirements, but its test cases can retain redundant steps; this work targets both objectives.Source: §2.2 · p. 4

2.3. Graph coverage

• Edge-pair and prime-path criteria are stronger than vertex and edge criteria, and the paper targets the stronger criteria while reducing test steps and case count.Source: §2.3 · p. 5

2.4. GraphWalker

• GraphWalker is used across diverse domains, while prior work reports lengthy or coverage-redundant generated tests and escalating costs for additional edge-pair coverage.Source: §2.4 · p. 5

3. Background

• A test case is a non-empty path from the entry vertex, and test requirements encode graph coverage criteria including VC, EC, EPC, and PPC.EPC is stronger than VC and EC, but PPC is not stronger than EPC.Source: §3 · pp. 5–6

3.1. The DJ method

• DJ splices test requirements and uses flow minimization to cover those splices with as few test cases as possible.Its four steps are splice-graph construction, acyclic-hypergraph construction, constrained flow minimization, and unwinding hyperpaths into test cases.Source: §3.1 · p. 6

3.1.1. Hypergraph construction

• Because minimum-flow optimization is inapplicable to cyclic graphs, DJ combines splice-graph cycles into hypervertices to create an acyclic hypergraph.The resulting hypergraph retains the cycles in hypervertex form.Source: §3.1.1 · p. 6

3.1.2. Flow minimization

• The constrained flow minimizes test cases from the entry path to an added empty sink while requiring positive outgoing flow from every other hypergraph vertex.In the example, the source flow is five, the minimum number of test cases needed to cover all test requirements; repeated source occurrences are therefore unavoidable.Source: §3.1.2 · p. 7

3.1.3. Unwinding

• Unwinding replaces each hypervertex with its cycle, rotates the cycle for the shortest splice, and removes redundant occurrences while retaining the test requirements.The example suite contains every prime-path requirement exactly once and has 31 test steps.Source: §3.1.3 · pp. 7–8, §3.1.2 · p. 7

3.1.4. Suboptimality of DJ

• DJ’s suboptimalities stem from hypervertices: it may remove the wrong repeated occurrence and cannot interrupt a cycle to traverse its elements piecemeal.These are the two causes identified for suboptimality.Source: §3.1.4 · p. 8
• For graph A, DJ’s arbitrary choice of which hypervertex occurrence to remove affects suite length; removing the first occurrence yields fewer steps than removing the second.The first-occurrence result is compared with the suite in Eq. (7).Source: §3.1.4 · p. 8
• For graph B, DJ remains suboptimal even across all sequence orderings because it cannot distribute a hypervertex’s elements across different parts of the suite.DJ requires the hypervertex’s elements to be traversed in separate parts of the test case.Source: §3.1.4 · p. 8

4.1. DJPlus

• DJPlus replaces unwinding with unrolling that preserves an acyclic graph, enabling flow minimization after each hypervertex replacement.It first eliminates hypervertices to create a requirement flow graph whose vertices, except source and sink, are test requirements.Source: §4 · p. 8, §4.1 · p. 9

4.2. Motivating examples

• Graph A yields DJPlus’s minimal suite despite DJ’s dependence on a favorable hypervertex choice; nested-cycle graph B requires successive unrolling of h2 and h1 for a suite DJ could not obtain.The examples describe DJPlus as producing minimal test suites for both graphs.Source: §4.2 · pp. 9–10

4.3. Suboptimality of DJPlus

• DJPlus can miss shorter suites because it selects an arbitrary minimum flow; searching alternatives could require exponentially many unrollings.In the example, an alternative minimum flow would have produced a shorter test case.Source: §4.3 · p. 10

4.4.1. Model conversion

• GWPlus implements DJ and DJPlus by converting GraphWalker’s multigraph models into simple graphs, using criterion-dependent conversions such as line graphs for EC and EPC.Line-graph conversion makes VC equivalent to EC of the original model, and EC equivalent to EPC.Source: §4.4.1 · p. 11

4.4.2. Coverage measurements

• GWPlus measures VC, EC, EPC, and PPC as the percentage of corresponding requirements appearing as subpaths in at least one generated test case.Source: §4.4.2 · p. 11

4.4.3. Infinite loops

• When a target criterion cannot be satisfied by one test case, GraphWalker’s Random and QRandom methods can loop indefinitely; designers may need to add restart edges.The realistic GraphWalker models used in the experiments did not require such extra edges.Source: §4.4.3 · p. 11

4.5. Computational complexity of unrolling in DJPlus

• Unrolling costs O(|H||TR|^2) and dominates hyperpath construction; worst-case cycle growth can make hypergraph construction and unrolling exponential.Source: §4.5 · p. 12

5.1.3. Random seeds

• The experiments run in requirement-generation, test-generation, and test-execution phases; Random and QRandom use 30 fixed seeds, while DJ and DJPlus are deterministic.Random and QRandom support only vertex and edge criteria; DJ and DJPlus support all four criteria.Source: §5.1 · p. 12, §5.1.2 · p. 12, §5.1.3 · p. 13

5.1. Experimental setup

• The experimental setup used four realistic SUTs with GraphWalker models ranging up to 129 vertices; two were hardware systems and two were web systems.Not all 1,920 possible setting combinations were valid; for example, Random cannot target edge-pair criterion.Source: §5.1.1 · p. 12, §5.1 · p. 12

5.2.1. Phase 1: Test requirement generation

• As models grow, prime-path test requirements exceed a million, while edge-pair requirements remain comparatively reasonable, leading the authors to exclude prime-path coverage from later experiments.Source: §5.2.1 · p. 13

5.2.2. Phase 2: Test generation

• DJPlus’s edge-pair test-step counts fall between Random and QRandom’s edge-criterion counts, which the authors use to argue edge-pair coverage is feasible for realistic SUTs.The comparison is not like-for-like because edge-pair coverage is stronger than edge coverage.Source: §5.2.2 · p. 13, Figure 11 · p. 13
• DJPlus generates the same or fewer test steps than DJ in every tested configuration, and their gap grows with model size, peaking for edge-pair coverage on Testinium.Both methods are deterministic and have zero variance in the reported comparison.Source: §5.2.2 · p. 13, Figure 12 · p. 14
• For small models, every configuration generated tests in under three seconds, while DJPlus took around 186 seconds for Testinium edge-pair coverage; execution time, not generation time, was the bottleneck.The authors note that models larger than Testinium would be needed to comment further on generation-time scalability.Source: §5.2.2 · pp. 13–14, Table 5 · p. 14
• QRandom, DJ, and Random generate 2 to 26 times more redundant test steps than DJPlus, which is least redundant on average.The evaluation also finds DJPlus generates the same or fewer steps than DJ across all tested configurations.Source: §5.2.2 · pp. 13–14

5.2.3. Phase 3: Test execution

• Strong linear correlations across TLC, RISC-V, and Parabank link fewer test steps with lower execution times; the authors conclude DJPlus decreases execution times by reducing steps.Average execution time was calculated from ten re-executions of each test suite.Source: §5.2.3 · p. 15, Figure 13 · p. 15

6.1. Impact

• Reduced strong-coverage suites are especially desirable when tests are maintained and rerun after SUT updates, where industrial adoption depends on fitting a limited testing budget.Source: §6.1 · p. 15

6.2. Redundancy

• Graph topography can impose a minimum redundancy factor because some critical subgraphs must be traversed repeatedly to meet coverage.Coverage-redundant steps may still serve stress testing or fault detection, and their value for those purposes remains an open question for GraphWalker.Source: §6.2 · p. 15

6.3. Reproducibility

• Generation phases are fully reproducible under controlled randomness, but execution-time measurements depend on the environment; ten reruns reduce noise so trends, rather than exact times, are replicable.Source: §6.3 · p. 15

6.4. Generalizability

• Results may not generalize to arbitrary SUTs because only a limited number were evaluated, despite selecting realistic models from hardware and web domains.Source: §6.4 · p. 15

6.5. Correlation

• Test-step count and execution time are strongly correlated in controlled experiments where step count was the only changed variable; the authors describe the reduction as causing lower execution times.Source: §6.5 · p. 15

6.6. Graph coverage

• The criteria measure model coverage, not implementation code coverage, and their benefits assume the graph model captures relevant SUT behavior.Verifying model completeness is left as a separate topic.Source: §6.6 · p. 16

6.7. Test oracles

• Test oracles are model-element assertions, but their absence does not affect these results because coverage is measured by counting targeted model elements.Source: §6.7 · p. 16

6.8. Feasibility

• The feasibility argument compares DJPlus edge-pair suites with GraphWalker edge-coverage suites, so it is not a like-for-like comparison.The argument relies on prior evidence that GraphWalker edge-coverage tests for the largest SUT were feasible.Source: §6.8 · p. 16

7. Conclusions

• DJPlus generated the fewest test steps for the same coverage target, while alternative methods generated 2 to 26 times more redundant steps; edge-pair coverage was feasible on four realistic SUTs, but prime-path coverage did not scale.DJPlus-generated suites also reduced test execution costs.Source: §7 · p. 16

Appendix A.4. Sequence operations

• The paper names path splicing p⊙q to avoid confusing the operation with set union, which prior literature denoted using the union symbol.The operation denotes a set of shortest paths that begin at p[0] and end at tgt(q).Source: Appendix A.4 · p. 17

Appendix A.6. Test suites, requirements, and criteria

• Edge-pair coverage is stronger than edge and vertex coverage, while prime-path coverage is stronger than vertex and edge coverage but not edge-pair coverage.A criterion is stronger when satisfying it guarantees satisfying the other criterion.Source: Appendix A.6 · p. 17

Appendix B.1. Computing a splice

• The splice computation uses an existing overlap when present; otherwise, it connects the paths using shortest paths between their endpoints.If no connecting path exists, the splice is empty.Source: Appendix B.1 · pp. 17–18
• The splice variant supports multiple splices between two vertices, allowing test generation with manually crafted requirement sets.The original path-splicing work did not account for multiple splices.Source: Appendix B.1 · p. 18

Appendix B.2. Computing prime paths

• The appendix presents a prime-path generator that follows the paper’s definition of the prime path criterion.The cited literature also contains known algorithms and equivalent variants.Source: Appendix B.2 · p. 18

Appendix B.3. Computing splice graphs

• The splice-graph algorithm is modified to handle cases where a pair has more than one splice.The earlier algorithm is attributed to Dwarakanath and Jankiti (2014).Source: Appendix B.3 · p. 18

Appendix B.4. Computing hypergraphs

• The hypergraph algorithm removes the shortest cycle first because finding it is computationally cheaper and easier to implement than a longest-simple-cycle-first heuristic.The appendix points to Anaqreh et al. (2023) for an algorithm that finds the longest simple cycle.Source: Appendix B.4 · p. 18

Appendix B.5. Unwinding

• Unwinding converts vertex sequences in a hypergraph into vertex sequences of the preceding hypergraph until reaching the first hypergraph.For reconstructed cycles, the algorithm selects the rotation of the cycle prefix that yields the shortest splice.Source: Appendix B.5 · pp. 18–19

Appendix B.6. Unrolling

• Unrolling takes a sequence of hypergraphs whose final hypergraph is acyclic and outputs an acyclic simple graph.Each successor hypergraph has vertices that are paths of its predecessor.Source: Appendix B.6 · p. 19
• The construction avoids selected connections that would introduce cycles, preserving the acyclicity of the resulting graph.It also reconstructs hyperpath incoming and outgoing edges while avoiding cycle-producing connections.Source: Appendix B.6 · p. 19
• The algorithm retains decorated vertices so test suites can traverse the same vertex three or more times when necessary, then re-minimizes the graph.The resulting graph contains only test requirements and source and sink vertices.Source: Appendix B.6 · p. 20

Appendix C. Computing redundancies

• Relative redundancy is undefined when DJPlus has no redundancy, and the authors compare it only when DJPlus also has some redundancy.The redundancy factor is undefined for empty test suites or graphs with no edge pairs; neither occurred in the experiments.Source: Appendix C · p. 20
• When the compared suites are identical, the relative redundancy is treated as meaningless and not reported.The example states that τ = U for that configuration.Source: Appendix C · p. 20
• QRandom was 4 times more redundant than DJPlus for one configuration, while obtaining only 10% more edge-pair coverage for that cost.The appendix reports averages across coverage percentages, SUTs, and seed values to produce redundancy factors and relative redundancy percentages.Source: Appendix C · p. 20

Appendix D. Line graphs

• A multigraph is defined as vertices, labeled edges, and an edge relation that permits multiple edges between the same vertex pair.The line graph is defined with one vertex per multigraph edge label and adjacency for labels of consecutive edges.Source: Appendix D · p. 20
• Vertex coverage of a line graph is equivalent to edge coverage of its multigraph because the line-graph vertices are the multigraph’s edge labels.The appendix states that covering all line-graph vertices covers all multigraph edge labels, and vice versa.Source: Appendix D · p. 20
• Edge coverage of a line graph is equivalent to edge-pair coverage of its multigraph, since line-graph vertex pairs correspond to multigraph edge pairs.The proof identifies the set of line-graph vertex pairs with the set of multigraph edge pairs.Source: Appendix D · p. 20

CRediT authorship contribution statement

• The authors’ stated contributions range from conceptualization and investigation to writing, with supervision, funding, and project administration attributed to Demeyer and Wotawa.Köroğlu is also credited with methodology, software, data curation, formal analysis, funding acquisition, and visualization.Source: CRediT authorship contribution statement · p. 20

Data availability

• The dataset and replication package are available, and the package includes instructions for replicating the experiments.The passage identifies the package as Version v2.Source: Data availability · p. 21
• GWPlus is available for use on other models.Source: Data availability · p. 21