State space Exploration of Multidimemsional Boundaries using Adherence Strategies (SEMBAS) is a technique for finding phase transitions in performance for a given search space. The boundary between performance modes can provide useful insight into the characteristics of the system. For example, if the target performance mode is "Safety" (which may be defined by your specific use case) the boundary between safe and unsafe behavior can provide meaningful test cases, whereas the extremes (highly safe and unsafe) may provide no insight at all. Furthermore, these boundaries may be used to analyze probability of performance modes be sampled from (executed by the function under test.)

An example of the boundary exploration process can be found under images/output.gif. Red dots are the explored boundary and blue dots are the samples taken by the adherence algorithm to find the next boundary point. This example explores a simple 3-Dimensional sphere, but SEMBAS can be applied to arbitrarily high dimensions.

Running Examples

Some of the examples require certain features to be enabled. A common feature is sps (synthetic parameter space) which are used to create mock functions under test. You can easily run any example, however, by using the below command:

cargo run --example <example-name> --features all

Adherence

An Adherence strategy is the process of finding a neighboring boundary point. This requires both an initial boundary point, which acts as a pivot to rotate around, and direction of travel, which indicates which direction along the boundary to search for a new boundary point. A displacement vector can then be rotated towards and away from the surface in order to identify new boundary points.

This component of the system influences how efficiently the boundary is acquired, and has the most impact on performance (i.e. the number of times the function under test must be executed.)

Exploration

An Exploration strategy is the process of picking the new directions along the surface. This part of the system determines coverage of the surface, and utilizes an Adherer in order to find the next boundary point.

The FUT and Classifier

The Function Under Test (FUT) is the system whose input search space is being explored. The classifier is a wrapper around this FUT which classifies the FUT's output as either In-Mode or Out-of-Mode for the performance that is begin targeted. In Mode simply refers to the system performing the target behavior of interest, such as unsafe behavior, throwing an error, or breaking a given threshold. This binary classification allows for the boundary between the In-Mode and Out-of-Mode behavior to be explored.

Halfspaces - How the boundary is represented

The boundary has two major components: a position and direction. The position is obvious, it describes where the search space transitions from being within the performance mode to being outside of the performance mode. The surface direction, on the other hand, describes the orientation of the surface, and consequently which side corresponds to the target performance mode. This surface direction is referred to as the Orthonormal Surface Vector (OSV), or surface vector for short.

A halfspace is a single boundary location and OSV pair, which defines the location and orientation of a hyperplane that divides the search space into two halves (thus the name). The boundary is composed of these halfspaces, which carves out a hyper-dimensional polyhedra, where each halfspace represents a face of that polyhedra.

Terminology

Crate Overview

This crate has the goal of providing all the tools necessary for exploring boundaries in high dimensions. This includes identifying the initial in-mode and out-of-mode boundary pairs, finding the initial boundary halfspace, and of course exploring the boundary itself.

This section discusses in detail some of the code you will find in the examples/ directory.

Step 1) Initial Boundary Pair

A boundary pair is any two points in the search space that successfully identifies the existance of a boundary, where one point falls within the target performance and the other falls outside of the target performance. This process will be referred to as Global Search, since the full (global) search domain will be explored.

The sembas::search::global_search module provides tools for this, specifically the MonteCarloSearch Search Factory. This is a simple solution, where the entire search space is randomly sampled. (In the future, more sophisticated global search solutions will be provided, such as gradient descent.)

Below is an example of how to find an initial boundary pair. This function takes in the classifier, the domain to be explored, and the maximum samples cut-off threshold for early termination. The function samples the space until an In-Mode and Out-of-Mode sample has been acquired.

fn find_initial_boundary_pair<const N: usize>(
    classifier: &mut Box<dyn Classifier<N>>,
    domain::Domain<N>,
    max_samples: i32,
) -> Result<BoundaryPair<N>> {
    let mut search = MonteCarloSearch::new(domain, 1);

    // Shorthand for creating a sample and classifying it:
    let mut take_sample = move || {
        let p = search.sample();
        let cls = classifier
            .classify(&p)
            .expect("Invalid sample. Bad global search domain?");
        Sample::from_class(p, cls)
    };

    let mut t0 = None;
    let mut x0 = None;
    let mut i = 0;

    while (t0.is_none() || x0.is_none()) && i < max_samples {
        let sample = take_sample();
        match sample {
            Sample::WithinMode(t) => {
                if t0.is_none() {
                    t0 = Some(t)
                }
            }
            Sample::OutOfMode(x) => {
                if x0.is_none() {
                    x0 = Some(x)
                }
            }
        }

        i += 1;
    }

    if let (Some(t), Some(x)) = (t0, x0) {
        Ok(BoundaryPair::new(t, x))
    } else {
        Err(SamplingError::MaxSamplesExceeded)
    }
}

With this initial boundary pair, we know that a boundary exists. However, the distance between these two points is arbitrarily large, and therefore the error is likely to be very high. As a result, the surface must then be identified by reducing this distance.

Step 2) Surfacing

This process takes an initial boundary pair and returns a halfspace that is within the desired maximum error (i.e. distance from the boundary). The sembas::search::surfacing module provides the binary_surface_search function for this very purpose. This algorithm finds the mid-point between the samples in the boundary pair and classifies it. This midpoint then acts as one of the samples in the boundary pair, and the process repeats until the distance between the samples falls under the $d$ distance, or until the maximum number of samples has been reached. The point that falls within the envelope is the boundary's location vector and the normalized displacement between the pairs is the surface's direction.

Step 3) Setting up the Adherer

Within the sembas::adherers module, two implementations are provided: ConstantAdherer and BinarySearchAdherer. The difference between these two is unimportant to this introduction, but the ConstantAdherer is a good first approach.

In order for an adherer to be used by an Explorer, its corresponding AdhererFactory must be constructed. The factory pattern decouples the initialization of the Adherer from its use, allowing for any Adherer to be used by any Explorer.

There are two parameters unique to the ConstantAdherer: delta_angle: f64 and max_rotations: Option<f64>. The delta_angle ($\Delta \theta$) is the angle to rotate the displacement vector by to find the next boundary point. Experimentally, an angle between $5^\circ$ and $20^\circ$ has been found to work well for most circumstances. Note that the smaller the angle, the more samples it will take to find the boundary. The max rotation parameter defines the maximum rotation can occur before the Adherer fails, throwing a structs::error::BoundaryLostError. The default max angle is $180^\circ$, but an angle smaller than this (between $90^\circ$ and $180^\circ$) can work as well.

let delta_angle = 15.0f64.to_radians();
let max_rotation = 120.0f64.to_radians();
let adherer_f = Box::new(
    ConstantAdhererFactory::new(delta_angle, Some(max_rotation))
);

Step 4) Creating a Classifier

Although the classifier's implementation heavily depends on your specific use case (finding classification boundaries of an image classifier, find the boundary of a failure mode, etc.) we can produce synthetic parameter spaces using geoemtry.

struct Sphere<const N: usize> {
    pub radius: f64,
    pub center: SVector<f64, N>,
    pub domain: Domain<N>,
}

impl<const N: usize> Classifier<N> for Sphere<N> {
    fn classify(&mut self, p: &SVector<f64, N>) -> Result<bool> {
        if !self.domain.contains(p) {
            return Err(SamplingError::OutOfBounds);
        }

        Ok((p - self.center).norm() <= self.radius)
    }
}

This Sphere classifier will return true if the provided point falls within the sphere, otherwise false.

Final note on classifiers: A RemoteClassifier is also provided with the api feature under sembas::api, which allows you to setup a connection to another process that will act as the FUT. The RemoteClassifier will send a normalized point of a given number of dimensions across the TCP connection and wait for a response. The remote FUT will then process the point and transmit a boolean value for the RemoteClassifier to return as its classification result. (This is a work in progress, there are some details that need to be ironed out, but it is in a working state.)

Step 5) Creating the Explorer

Next, we must create the Explorer that will handle the exploration process. The only implementation provided at this time is the sembas::explorers:MeshExplorer. This solution samples each cardinal direction along the surface of the boundary, but prunes branches that sample too close (within a margin of error) to existing boundary points.

The MeshExplorer takes a jump distance d: f64 to describe how far apart to sample the boundary points, a root: Halfspace<N> initial halfspace, a margin: f64 to describe the minimum distance between samples before pruning, and a adherer_f: Box<dyn AdhererFactory>. The margin cannot ever be greater than d, but should be a little smaller than d.

Below is a complete

use nalgebra::vector!;
use sembas::prelude::*;

// ...

let main() {
    let center = vector![0.5, 0.5, 0.5]
    let radius = 0.25;
    let domain = Domain::normalized();
    let mut classifier: Box<dyn Classifier<3>> = Sphere {
        center,
        radius, 
        domain,
    }

    let b_pair = find_initial_boundary_pair(&mut classifier, 32).unwrap();

    let d = 0.05
    let root = binary_surface_search(
        d, &b_pair, 256, &mut classifier).expect("Couldn't find in time?");

    let delta_angle = 15.0f64.to_radians();
    let max_rotation = 120.0f64.to_radians();
    let adherer_f = Box::new(
        ConstantAdhererFactory::new(delta_angle, Some(max_rotation))
    );

    let expl = MeshExplorer::new(d, root, d * 0.9, adherer_f);
}

Step 6) Exploring

Finally, we can begin exploring our function under test. An Explorer has a .step(...) method which takes in the classifier and returns a reference to the Result containing the sample that it took. This result may be a BoundaryLost error or a OutOfBounds error. Under most circumstances, these are not fatal, since the boundary exploration process can proceed without any alteration. Losing the Boundary is very costly, particularly when max_rotation for the ConstantAdherer is large, but is rare.

// ...
fn main() {
    // ...

    let max_boundary_points = 500;
    let max_samples = 1000;
    let mut ble_count = 0;
    let mut oob_count = 0;

    for _ in 0..max_samples {
        // Take samples and handle results
        if let Err(e) = expl.step(&mut classifier) {
            match e {
                SamplingError::BoundaryLost => ble_count += 1,
                SamplingError::OutOfBounds => oob_count += 1,
                _ => (),
            }
        }

        if expl.boundary_count() >= max_boundary_points {
            break;
        }
    }
}

Once this process completes, the explorer will have at most $500$ boundary halfspaces. You can retrieve these halfspaces by the Explorer's .boundary() getter.