Graphs are widely used in model-based test generation. A commonly used family of coverage criteria is based on covering edge sequences of length for ≥ 1 . A near-optimal test generation algorithm (which based on solving Chinese postman problem) has a known algorithmic complexity of (| | While we cannot change the inherent complexity of the algorithm, heuristics can heavily improve upon
3 ). the actual runtime of the algorithm. In this paper, for the purpose of developing such a heuristic, we illustrate the potential points of improvement by means of an experimental analysis. Our results suggest that the good coverage properties displayed by the algorithm are prone to being exploited to improve its runtime performance at least for certain types of graphs.
Model-based testing is the activity of testing a (software) system based on the abstractions
called models or specifications. It is commonly used for functional testing of the system [
There are diferent types of graph-based models, which difer from each other in terms
of expressive power and the elements on which they put the focus. Two of these types are
state-based models, such as finite state machines [
Test generation is an important part of model-based testing. For graph-based models, the
idea is in general to extract edge sequences. Extracted sequences are supposed to satisfy some
coverage criteria based on, for example, coverage of certain faults or coverage of edge sequences
of diferent lengths [
This paper studies a commonly used near-optimal graph-based test generation algorithm [
This section gives a brief background on graphs, graph-based coverage criteria and the graphbased test generation algorithm of interest.
We start by giving the definition of a graph.
Definition 1. A directed multigraph is a tuple = ( , ) where ≠ ∅ is a finite set of vertices, and is a finite multiset of edges where each edge is an order pair in × . A walk 1, 2, … , in is a sequence of vertices where each ( , +1 ) ∈ .
Depending on the context, it is possible to enrichen the semantics of a graph-based model by distinguishing between diferent types of vertices and/or by labeling the vertices or edges with diferent elements. For example, in state-based models, vertices represent states and edges represent transitions where each transition is also labeled by inputs or input-output pairs. In event-based models, on the other hand, vertices represents events, and edges have no labels; they define a ”follows” relation on events. Of course, it is always possible to define extensions by introducing guards, quiescence, time, hiearchy, etc. Figure 1a shows an example graph.
Regardless of the type of the graph-based model, a common purpose is to extract or generate subgraphs from the given graph to be used as test cases. The way the test cases are generated is dependent on the model elements. For example, a model with guards is harder to work with than one without guards because it is more expressive. Still, in many practical applications, the generated subgraphs are linear and, thus, walks in the graph are used as test cases.
In the generation of test cases, coverage criteria of diferent strengths are defined and used. One way to do this is to utilize -edges. A -edge is a walk of length where ≥ 1 , and -edges are used as coverage targets. The associated coverage criterion is given in Definition 2. (a) Example graph
(b) Graph with pseudovertices (c) One-time transformed graph Definition 2. Given a graph and a set of test cases , is said to cover a -edge in if appears in one of the the test cases in . is said to achieve -edge coverage if it covers all -edges in .
Note that, if it is possible to extend each walk in a given graph to a longer walk, the set of -edges is always a subset of the set of ( + 1) -edges for each ≥ 1 . Consequently, ( + 1) -edge coverage is stronger than -edge coverage. Thus, parameter is used to assess the strength of the set of test cases .
In certain contexts or, generally, for generation of test cases, certain vertices in the graph can be marked as inital/start/entry or final/finish/exit vertices. Furthermore, the graph model may be required to satisfy certain properties such as consistency where each vertex is reachable from an entry vertex and an exit vertex is reachable from each vertex.
The test generation algorithm we consider in this work has the following assumptions. • The graph has at least one entry vertex and one exit vertex. • The graph is consistent. • Each test case is a walk from an entry vertex to an exit vertex.
Without any loss of generality, we use one pseudostart vertex denoted by ”[” to mark the entry vertices and one pseudofinish vertex denoted by ” ]” to mark the exit vertices. Each entry vertex has an incoming edge from the pseudostart vertex and each exit vertex has an outgoing edge to the pseudofinish vertex. Figure 1b shows inclusion of pseudo vertices to the graph in Figure 1a assuming that ”1” and ”2” are entry vertices, and ”3” and ”4” are exit vertices.
The main steps of the test generation algorithm is given in Algorithm 1 in two parts. In
”graph transformation” part of the algorithm (See Part 1 in Algorithm 1), is transformed
− 1 times to obtain a graph such that, when the edges of are covered, -edges of are
covered. In other words, each edge in corresponds to consecutive edges in . It has the
time complexity of ( 2| | 2 ); details can be found in [
Algorithm 1 Algorithm to Generate Test Cases Achieving k-Edge Coverage Require: A consistent graph = ( , ) and coverage parameter ≥ 1 Ensure: Generated set of test cases achieves -edge coverage 1: /* Part 1: Graph transformation */ 2: ← 3: ← 1 4: while < do 5: ← Transform using 6: ← + 1 7: end while 8: /* Part 2: Euler path generation */ 9: ← Add the edge (], [) to 10: ← Add proper paths until degree of each vertex is 0 11: ← Compute Euler paths from [ to ] in
Once the transformed graph is computed, ”Euler path generation” part of the algorithm
(see Part 2 in Algorithm 1) works on solving the Chinese postman problem [
Note that Algorithm 1 may yield infeasible paths depending on the semantics of the actual graph model. In this paper, we assume that all paths are feasible.
In this section, we perform experiments to collect data on the test generation algorithm given in 1 using randomly generated graph models. Our aim is to identify possible opportunities to improve the near-optimal algorithm in terms of runtime time.
In order to identify possible points of improvements for Algorithm 1, we formulate the following research questions.
RQ1 Can we confirm that Euler path generation part of Algorithm 1 is the most time consuming part? RQ2 Given a test set achieving -edge coverage generated by Algorithm 1, what factors afect the coverage of -edges and how well does the test set cover -edges where > ? RQ2 is formulated to see whether test cases achieving -edge coverage ( ≥ 1 ) show good coverage properties for also the coverage targets which are out of their scope. This is an indication of possibility of utilizing -edge covering test cases in generation of the test cases achieving -edge coverage for > . However, this possibility is also dependent on the change in the runtime of diferent parts of Algorithm 1 when is increased. Thus, we also define RQ1 to investigate which of the two main parts of the algorithm takes more time: graph transformation part or Euler path generation part.
In order to collect data, we used randomly generated and consistent graph models satisfying the following conditions.
• Each graph has one entry vertex and one exit vertex. This is done to reduce the possible efects of multiple pseudoedges on the the test generation. Although there is no detailed study on the subject, Algorithm 1 may yield non-optimal results if the number of pseudoedges is greater than 1. • All vertices in a graph have the same number of outgoing edges. This is done to control the model size properly, to increase the probability of generating a consistent graph, and to ensure that each edge takes part in − edges in a more uniform manner.
We use the following parameter values in our experiments.
• Number of vertices in a graph, or simply vertex
5, 10, 15, 20, 25, 30, 35, 40, 45, 50 • Number of outgoing edges of a vertex, or simply out degree: = 3, 4, 5 • -edge coverage parameter: = 1, 2, 3 • Parameter for coverage targets: = 1, 2, 3, 4, 5 count: = For each ( , , ) triple, we generate 10 random graphs and perform 3 test generation runs to collect data in a feasible time period. All runs are executed on a MacBook Pro 14 with Apple M1 Pro CPU, 16GB RAM and macOS Monterey operating system. (a) / values for = 3 (b) / values for = 4 (c) / values for = 5
Let denote the time it takes to generate the Eulerian paths and and denote the time to perform the graph transformation part of Algorithm 1. To see how and values compare with respect to each other, we give bar plots which include / values for = 2, 3 and = 3, 4, 5 in Figures 2a, 2b and 2c. Note that values for = 1 are not included since no transformation takes place to cover 1-edges.
RQ1 can be answered by using these plots. It is clear that Eulerian path generation part of Algorithm 1 is far more time consuming than its graph transformation part. The diference increases for increasing values and increasing values.
The results of coverage analysis of -edge covering test sets for = 1, 2, 3 are given in Figures 3a, 3b and 3c for = + 1, … , 5 . While plotting the graphs, average of the values obtained over 10 random graphs with 3 runs for each graph are used.
To answer RQ2, let (, , ) denote the ratio of -edges covered by the test set achieving -edge coverage for a given value of . Figures 3a, 3b and 3c show that, when and − are ifxed, (, , ) values obtained using diferent are very similar and they are not dependent on . Also, promisingly high (, , ) values are observed especially when = + 1 and is small: (, + 1, 3) = 43% , (, + 1, 4) = 32% and (, + 1, 5) = 25% . Thus, there is a decreasing trend for (, , ) when is increased; however, more data is required to make further comments on the nature of this trend. On the other hand, (, , ) shows a faster-than-linear decrease for increasing for diferent values of when is fixed.
Our results have both positive and negative implications for improvement of the near optimal graph-based test generation algorithm given in Algorithm 1.
On the positive side, we have the following.
• A test set achieving -edge coverage covers a significant portion of + 1 -edges already.
Therefore, it might be possible to develop heuristics utilizing test set achieving -edge coverage in the generation of test sets achieving + 1 -edge coverage. This my cause a considerable speed-up in test generation, because a test achieving -edge coverage can be generated much faster than a tet set achieving + 1 -edge coverage, especially when increases. • Part 2 (Eulerian path generation) of the algorithm consumes significantly more time than Part 1 (graph transformation). This is a positive result, because if Part 1 is a combinatorial algorithm which is based on generating a graph containing coverage targets. Thus, it is not likely to make use of the good coverage properties displayed by the test sets to improve this part.
On the negative side, the results suggest that the portion of + 1 -edges covered by test sets achieving -edge coverage may decrease fast when the average outgoing degree of the graphbased model increases. Thus, heuristics developed based on the properties discussed above may not work under certain conditions.