Tests for OpenPGP WoT search implementations

A generic test framework for "Web of Trust" implementations, based on the wot-network-crate data structures.

This crate is a companion for the OpenPGP Web of Trust documentation in openpgp-wot. It provides two interlinked resources:

1. Test code to evaluate Web of Trust implementations.
2. Test configurations to use with this test code.

Separately, external test configurations can be used easily with the test code in this crate.

Configuration-based testing

The tests in this crate are based on configuration files. See test-configurations.md for more details.

Callers can either use the test cases that are provided in this crate, or run the test code with external test configurations. The test entry point functions take a base path as a parameter. Files in that base path are interpreted as test configurations and run.

Every test configuration file references a WoT network graph file. The test will be run against that network. The filesystem location of the WoT graph is usually specified as a relative path (based on the parent directory of the test base path).

E.g., the test configuration tests/best_path/basic.toml references file = "wot/basic.wot", pointing to the WoT graph definition in tests/wot/basic.wot.

Test code for wot-network::search implementers

This crate offers tests for implementers of the wot-network::search traits:

• ResidualNetworkTrait ("best path" search)
• WotSearchTrait ("flow" search)

These traits act as interfaces for implementations of the "inner" and "outer" part of a WoT graph search algorithm, as outlined in the algorithm.md.

The tests in this crate aim to help implementers of either or both of these traits to validate their implementations.

"Best path" tests on ResidualNetworkTrait (the "inner" algorithm)

The test performs a series of "shortest path" searches on an implementation of ResidualNetworkTrait. The implementation that gets tested is provided by the caller.

This test can be run like this:

test_residual_search::<ResidualNetworkTraitImplementation>("<path_to>/tests/best_path/")?;

To run them, a caller provides the "inner" search algorithm described in [algorithm-md] (a variant of Dijkstra's "shortest paths" algorithm), as an implementation of ResidualNetworkTrait as a generic parameter.

Additionally, a base path to a set of test configurations is required (e.g. the ones in this crate).

Note that this ("inner") part of the WoT lookup algorithm is an implementation detail of the "outer" algorithm (see next section). Ultimately, only the WotSearchTrait is required by applications. However, for implementers who follow the approach outlined in the algorithm.md, it may be useful to use this test to validate their implementation of the "inner" algorithm as a ResidualNetworkTrait separately.

Note: This test don't cover the "flow restrictions" aspect of the residual network implementation (see ResidualNetworkTrait::reduce) at all. This test always starts from a fresh and unrestricted flow network, and perform only one lookup.

"Reduce" tests on ResidualNetworkTrait

The test performs a series of "reduce" calls on an implementation of ResidualNetworkTrait. The implementation that gets tested is provided by the caller.

This test can be run like this:

test_residual_reduce::<ResidualNetworkTraitImplementation>("<path_to>/tests/reduce/")?;

These tests perform a series of ResidualNetworkTrait::reduce calls, and checks if the resulting Ok or Err return values conform to the test expectation.

The functionality that this exercises is a building block of the "outer" search algorithm: Using the flow capacity in a residual network, and thereby producing a new state on which the next run of the "inner" best path search algorithm can run to find additional paths.

Note that the functionality that this test validates is an implementation detail that applications will not normally use - only WotSearchTrait is required by applications.

"Flow" searches on WotSearchTrait (the "outer" algorithm)

This test explores the high-level WoT functionality of finding a list of paths that collectively serve as evidence for a target binding:

test_wot_search::<WotSearchTraitImplementation>("<path_to>/tests/flow/")?;

To run the test, a caller provides an implementation of WotSearchTrait as a generic parameter (and a base path to a set of test configurations, e.g. the ones in this crate).

This test formalizes expectations of an implementation of the "outer" search algorithm described in the algorithm.md (which performs a variant of the Ford-Fulkerson algorithm on top of the "inner" algorithm as implemented by a ResidualNetworkTrait).

(Note that different implementations of WotSearchTrait could reasonably find different subsets of a potentially wide variety of paths that validly connect a set of anchors to a target binding. In addition, these paths do not have an inherently "correct" ordering. However, these tests currently expect a specific list of results, in a fixed ordering, for simplicity ¹. The order that these tests expect follows from the algorithm description in the algorithm.md.)

Test configurations

This crate comes with test configurations that can be used with the test code outlined above. See the tests/ directory.

Users of this crate don't need to know or care about the internals of these test configurations. Still, a description of these configuration formats is available in test-configurations.md.