Expand Accordant's State-Graph Test Generation

[imnaseer]

Accordant generates test cases by exploring the state graph produced by a specification and a collection of operation inputs.

In this graph:

• each node represents a distinct state;
• each edge represents applying an operation and input from that state;
• and each selected path becomes a test sequence.

Accordant currently includes several graph-walking strategies:

• state coverage, which attempts to visit every discovered state;
• transition coverage, which attempts to exercise every discovered transition;
• and random walks, which sample paths through the graph using a reproducible random seed.

The graph-walking algorithm is also extensible, allowing users to provide their own strategies.

Proposed feature

Expand Accordant’s built-in test-generation strategies to produce more effective and varied test suites from its state graphs.

Choosing useful paths through a state graph is a substantial problem in its own right. A graph may contain a very large number of possible paths, and executing more paths does not necessarily produce a better test suite. Different selection strategies can expose different operation combinations, transitions, and unusual behaviors.

There are many possible directions to explore, including:

• weighted random walks, where some operations are selected more or less frequently;
• prioritizing states or transitions that have not yet been covered;
• generating diverse paths rather than many similar ones;
• targeting particular states, transitions, or operation sequences;
• generating tests within a fixed test-count or path-length budget;
• and reducing a generated suite while retaining a desired level of coverage.

A relatively simple addition could be swarm testing. In swarm testing, each run enables a different subset of the available operations or assigns them different probabilities. Changing the available operations from one run to another can produce a wider variety of sequences than repeatedly generating tests with every operation enabled and weighted equally.

Built-in state-graph generation does not need to solve every test-generation problem. Handwritten test cases and customized fuzz harnesses can also be highly effective. Accordant already separates test-case generation from conformance checking, so sequences produced by these approaches can still be validated against the same specification.

The goal of this feature is to recognize test generation as a rich area where Accordant can offer more useful built-in options. Contributors can begin with a focused addition such as weighted walks or swarm testing, or go deeper into techniques from fuzzing, coverage-guided exploration, search-based testing, and related research.