Skip to content

Generators and stop conditions

Jump to bottom Edit New page
Kristian Karl edited this page Sep 28, 2022 · 4 revisions

Path generators together with stop conditions will decide what strategy is used when generating a path through a model, and when to stop generating that path. Path generators can be daisy chained one after another. Multiple stop conditions can be set using logical OR, AND, ||, &&.

Generators

A generator is an algorithm that decides how to traverse a model. Different generators will generate different test sequences, and they will navigate in different ways. Multiple generators can be daisy chained, concatenated.

random( some stop condition(s) )

Navigate through the model in a completely random manner, also called "Drunkard’s walk", or "Random walk". This algorithm selects an out-edge from a vertex by random, and repeats the process in the next vertex.

weighted_random( some stop condition(s) )

Same as the random path generator (see above), but will use the weight keyword when generating a path. The weight is assigned to edges only, and it represents the probability of an edge getting chosen.

quick_random( some stop condition(s) )

Tries to run the shortest path through a model, but in a fast way. This is how the algorithm works:

  1. Choose an edge not yet visited by random.
  2. Select the shortest path to that edge using Dijkstra's algorithm
  3. Walk that path, and mark all the executed edges as visited.
  4. When reaching the selected edge in step 1, start all over, repeating steps 1-4.
  5. The algorithm works well for very large models, and generates reasonably short sequences. The downside is when used in conjunction with EFSM, the algorithm can choose a path which is blocked by a guard.

predefined_path( predefined_path )

Enables the user to define an edge sequence that GraphWalker will use when executing. Currently a predefined path can only be specified in the GraphWalker JSON file.

Graph input format

To define an edge sequence, the model has to contain an array element called predefinedPathEdgeIds containing the edge IDs in the sequence.

The generator and stop condition has to be specified in the generator element.

Example:

{
    "models": [
        {
            "generator": "predefined_path(predefined_path)",
            ...
            "edges": [
                { "id": "e0", ... },
                { "id": "e1", ... },
                { "id": "e2", ... }
            ],
            "predefinedPathEdgeIds": [ "e0", "e1", "e2", "e0" ]
        }
    ]
}

a_star( a stop condition that names a vertex or an edge )

Will generate the shortest path to a specific vertex or edge.

shortest_all_paths ==> (Not released yet)

Will calculate and generate the shortest path through the model. The cost for every edge is set to 1. This algorithm is not recommended because for larger models, and using data in the model EFSM, it will take a considerable time to calculate.

Stop conditions

A stop condition is condition that decides when a path is completed. The generator will generate a new step in the path until the stop condition is fulfilled.

edge_coverage( an integer representing percentage of desired edge coverage )

The stop condition is a percentage. When, during execution, the percentage of traversed edges is reached, the test is stopped. If an edge is traversed more than once, it still counts as 1 when calculating the percentage coverage.

vertex_coverage( an integer representing percentage of desired vertex coverage )

The stop condition is a percentage. When, during execution, the percentage of traversed states is reached, the test is stopped. If a vertex is traversed more than once, it still counts as 1 when calculating the percentage coverage.

requirement_coverage( an integer representing percentage of desired requirement coverage )

The stop condition is a percentage. When, during execution, the percentage of traversed requirements is reached, the test is stopped. If a requirement is traversed more than once, it still counts as 1 when calculating the percentage coverage.

dependency_edge_coverage( an integer representing dependency threshold )

The stop condition is a percentage. When, during execution, all of the traversed edges with dependency higher or equal to the dependency threshold are reached, the test is stopped. If an edge is traversed more than once, it still counts as 1, when calculating the percentage coverage.

reached_vertex( the name of the vertex to reach )

The stop condition is a named vertex. When, during execution, the vertex is reached, the test is stopped.

reached_edge( the name of the edge to reach )

The stop condition is a named edge. When, during execution, the edge is reached, the test is stopped.

time_duration( an integer representing the number of seconds to run )

The stop condition is a time, representing the number of seconds that the test generator is allowed to execute.

Please note that the time is compared with the execution for the whole test. This means that if you for example have:

  • 2 models
  • with common shared states
  • both having time_duration stop condition set to 60 seconds

Then both models will stop executing after 60 seconds, even if one of the models have not been visited.

length( an integer )

The stop condition is a number, representing the total numbers of edge-vertex pairs generated by a generator. For example, if the number is 110, the test sequence would be 220 do-check actions (110 pairs of edges and vertices).

never

This special stop condition will never halt the generator.

Examples

Will never stop generating a path sequence. Executes forever in a random fashion.

random(never)

Walk randomly until the vertex coverage has reached 100%.

random(vertex_coverage(100))

Walk randomly until the edge coverage has reached 50%.

random(edge_coverage(50))

Walk randomly until the vertex v_SomeVertex is reached.

random(reached_vertex(v_SomeVertex))

Walk the shortest path to the edge e_SomeEdge and then stop.

a_star(reached_edge(e_SomeEdge))

Walk randomly until the requirement coverage has reached 100%.

random(requirement_coverage(100))

Walk randomly for 500 seconds.

random(time_duration(500))

Walk randomly until the path sequence has reached a length of 24 elements of edges and vertices.

random(length(24))

Walk randomly until the edge coverage has reached 100%, or we have executed for 500 seconds.

random(edge_coverage(100) or time_duration(500))

Walk randomly until the edge coverage has reached 100%, or we have executed for 500 seconds (same as above).

random(edge_coverage(100) || time_duration(500))

Walk randomly until the edge coverage has reached 100%, and we have reached the vertex v_SomeVertex.

random(reached_vertex(v_SomeVertex) and edge_coverage(100))

Walk randomly until the edge coverage has reached 100%, and we have reached the vertex v_SomeVertex (same as above).

random(reached_vertex(v_SomeVertex) && edge_coverage(100))

Walk randomly until we have executed for 500 seconds, or we have both reached vertex v_SomeVertex and reached 100% vertex coverage.

random((reached_vertex(v_SomeVertex) and vertex_coverage(100)) || time_duration(500))

Walk randomly until the edge coverage has reached 100% and we have reached the vertex v_SomeVertex. Then start using the next strategy: walk randomly for 1 hour.

random(reached_vertex(v_SomeVertex) and edge_coverage(100)) random(time_duration(3600))

Walk randomly until all the edges with dependency higher or equal to 85% are reached.

random(dependency_edge_coverage(85))
Add a custom footer
Clone this wiki locally