Black-Box Stress Testing

7.7 μs

Unhide for installation (waiting on Julia registry).

6.6 μs

xxxxxxxxxx
 
using Distributions, Parameters, POMDPStressTesting, Latexify, PlutoUI

2.9 ms

To find failures in a black-box autonomous system, we can use the POMDPStressTesting package which is part of the POMDPs.jl ecosystem.

Various solvers—which adhere to the POMDPs.jl interface—can be used:

MCTSPWSolver (MCTS with action progressive widening)
TRPOSolver and PPOSolver (deep reinforcement learning policy optimization)
CEMSolver (cross-entropy method)
RandomSearchSolver

13.6 μs

Simple Problem: One-Dimensional Walk

We define a simple problem for adaptive stress testing (AST) to find failures. This problem, called Walk1D, samples random walking distances from a standard normal distribution $N (0, 1)$ and defines failures as walking past a certain threshold (which is set to $\pm 10$ in this example). AST will either select the seed which deterministically controls the sampled value from the distribution (i.e. from the transition model) or will directly sample the provided environmental distributions. These action modes are determined by the seed-action or sample-action options. AST will guide the simulation to failure events using a notion of distance to failure, while simultaneously trying to find the set of actions that maximizes the log-likelihood of the samples.

15 μs

Gray-Box Simulator and Environment

The simulator and environment are treated as gray-box because we need access to the state-transition distributions and their associated likelihoods.

5.6 μs

Parameters

First, we define the parameters of our simulation.

4.2 μs

xxxxxxxxxx
 
@with_kw mutable struct Walk1DParams
    startx::Float64 = 0   # Starting x-position
    threshx::Float64 = 10 # +- boundary threshold
    endtime::Int64 = 30   # Simulate end time
end;

2.7 ms

Simulation

Next, we define a GrayBox.Simulation structure.

4.5 μs

xxxxxxxxxx
 
@with_kw mutable struct Walk1DSim <: GrayBox.Simulation
    params::Walk1DParams = Walk1DParams() # Parameters
    x::Float64 = 0 # Current x-position
    t::Int64 = 0 # Current time ±
    distribution::Distribution = Normal(0, 1) # Transition distribution
end;

2.6 ms

GrayBox.environment

Then, we define our GrayBox.Environment distributions. When using the ASTSampleAction, as opposed to ASTSeedAction, we need to provide access to the sampleable environment.

9.5 μs

xxxxxxxxxx
 
GrayBox.environment(sim::Walk1DSim) = GrayBox.Environment(:x => sim.distribution)

16.3 μs

GrayBox.transition!

We override the transition! function from the GrayBox interface, which takes an environment sample as input. We apply the sample in our simulator, and return the log-likelihood.

6.9 μs

xxxxxxxxxx
 
function GrayBox.transition!(sim::Walk1DSim, sample::GrayBox.EnvironmentSample)
    sim.t += 1 # Keep track of time
    sim.x += sample[:x].value # Move agent using sampled value from input
    return logpdf(sample)::Real # Summation handled by `logpdf()`
end

27.7 μs

Black-Box System

The system under test, in this case a simple single-dimensional moving agent, is always treated as black-box. The following interface functions are overridden to minimally interact with the system, and use outputs from the system to determine failure event indications and distance metrics.

7.1 μs

BlackBox.initialize!

Now we override the BlackBox interface, starting with the function that initializes the simulation object. Interface functions ending in ! may modify the sim object in place.

6.6 μs

xxxxxxxxxx
 
function BlackBox.initialize!(sim::Walk1DSim)
    sim.t = 0
    sim.x = sim.params.startx
end

23 μs

BlackBox.distance

We define how close we are to a failure event using a non-negative distance metric.

6.6 μs

xxxxxxxxxx
 
BlackBox.distance(sim::Walk1DSim) = max(sim.params.threshx - abs(sim.x), 0)

22.1 μs

BlackBox.isevent

We define an indication that a failure event occurred.

6.3 μs

xxxxxxxxxx
 
BlackBox.isevent(sim::Walk1DSim) = abs(sim.x) ≥ sim.params.threshx

18.3 μs

BlackBox.isterminal

Similarly, we define an indication that the simulation is in a terminal state.

5.3 μs

xxxxxxxxxx
 
function BlackBox.isterminal(sim::Walk1DSim)
    return BlackBox.isevent(sim) || sim.t ≥ sim.params.endtime
end

44.4 μs

BlackBox.evaluate!

Lastly, we use our defined interface to evaluate the system under test. Using the input sample, we return the log-likelihood, distance to an event, and event indication.

5.6 μs

xxxxxxxxxx
 
function BlackBox.evaluate!(sim::Walk1DSim, sample::GrayBox.EnvironmentSample)
    logprob::Real = GrayBox.transition!(sim, sample) # Step simulation
    d::Real       = BlackBox.distance(sim) # Calculate miss distance
    event::Bool   = BlackBox.isevent(sim) # Check event indication
    return (logprob::Real, d::Real, event::Bool)
end

34.7 μs

AST Setup and Running

Setting up our simulation, we instantiate our simulation object and pass that to the Markov decision proccess (MDP) object of the adaptive stress testing formulation. We use Monte Carlo tree search (MCTS) with progressive widening on the action space as our solver. Hyperparameters are passed to MCTSPWSolver, which is a simple wrapper around the POMDPs.jl implementation of MCTS. Lastly, we solve the MDP to produce a planner. Note we are using the ASTSampleAction.

6.4 μs

xxxxxxxxxx
 
function setup_ast(seed=0)
    # Create gray-box simulation object
    sim::GrayBox.Simulation = Walk1DSim()
​
    # AST MDP formulation object
    mdp::ASTMDP = ASTMDP{ASTSampleAction}(sim)
    mdp.params.debug = true # record metrics
    mdp.params.top_k = 10   # record top k best trajectories
    mdp.params.seed = seed  # set RNG seed for determinism
​
    # Hyperparameters for MCTS-PW as the solver
    solver = MCTSPWSolver(n_iterations=1000,        # number of algorithm iterations
                          exploration_constant=1.0, # UCT exploration
                          k_action=1.0,             # action widening
                          alpha_action=0.5,         # action widening
                          depth=sim.params.endtime) # tree depth
​
    # Get online planner (no work done, yet)
    planner = solve(solver, mdp)
​
    return planner
end;

66.4 μs

Searching for Failures

After setup, we search for failures using the planner and output the best action trace.

6.4 μs

xxxxxxxxxx
 
planner = setup_ast();

218 ms

action_trace

ASTAction1

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(0.015328, -0.919056)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(0.28838, -0.96052)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(1.19606, -1.63422)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(0.609811, -1.10487)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(0.843249, -1.27447)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(1.47323, -2.00414)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(2.37764, -3.74553)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(1.23179, -1.67759)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(1.14347, -1.5727)))

ASTSampleAction(Dict{Symbol,POMDPStressTesting.AST.GrayBox.Sample}(:x=>Sample{Float64}(1.31136, -1.77877)))

2.6 s

Playback

We can also playback specific trajectories and print intermediate $x$ -values.

5.3 μs

playback_trace

Any1

0.0

0.015328

0.303708

1.49977

2.10958

2.95283

4.42605

6.8037

8.03549

9.17896

10.4903

xxxxxxxxxx
 
playback_trace = playback(planner, action_trace, sim->sim.x, return_trace=true)

205 ms

failure_rate

0.8159216715195341

xxxxxxxxxx
 
failure_rate = print_metrics(planner)

120 ms

Other Solvers: Cross-Entropy Method

We can easily take our ASTMDP object (planner.mdp) and re-solve the MDP using a different solver—in this case the CEMSolver.

6.5 μs

xxxxxxxxxx
 
mdp = planner.mdp; # reused from above

1.6 ms

cem_solver

CEMSolver
  n_iterations: Int64 1000
  episode_length: Int64 30
  num_samples: Int64 100
  min_elite_samples: Int64 10
  max_elite_samples: Int64 9223372036854775807
  elite_thresh: Float64 -0.99
  weight_fn: #16 (function of type POMDPStressTesting.var"#16#22")
  add_entropy: #17 (function of type POMDPStressTesting.var"#17#23")
  show_progress: Bool true
  verbose: Bool false

xxxxxxxxxx
 
cem_solver = CEMSolver(n_iterations=1000, episode_length=mdp.sim.params.endtime)

31 ms

xxxxxxxxxx
 
cem_planner = solve(cem_solver, mdp);

6.3 ms

xxxxxxxxxx
 
cem_action_trace = search!(cem_planner);

5.5 s

Notice the failure rate is about 10x of MCTSPWSolver.

2.9 μs

cem_failure_rate

12.882493795314756

xxxxxxxxxx
 
cem_failure_rate = print_metrics(cem_planner)

3.3 ms

AST Reward Function

The AST reward function gives a reward of $0$ if an event is found, a reward of negative distance if no event is found at termination, and the log-likelihood during the simulation.

6.8 μs

$R (p, e, d, τ) = {\begin{cases} 0 & if τ \land e \\ - d & if τ \land \neg e \\ \log (p) & otherwise \end{cases}$

xxxxxxxxxx
 
@latexify function R(p,e,d,τ)
    if τ && e
        return 0
    elseif τ && !e
        return -d
    else
        return log(p)
    end
end

1.8 s

References

Robert J. Moss, Ritchie Lee, Nicholas Visser, Joachim Hochwarth, James G. Lopez, and Mykel J. Kochenderfer, "Adaptive Stress Testing of Trajectory Predictions in Flight Management Systems", Digital Avionics Systems Conference, 2020.

6 μs

POMDPStressTesting.jl

Black-Box Stress Testing

Simple Problem: One-Dimensional Walk

Gray-Box Simulator and Environment

GrayBox.environment

GrayBox.transition!

Black-Box System

BlackBox.initialize!

BlackBox.distance

BlackBox.isevent

BlackBox.isterminal

BlackBox.evaluate!

AST Setup and Running

Searching for Failures

Playback

Other Solvers: Cross-Entropy Method

AST Reward Function

References

x
 
PlutoUI.TableOfContents("POMDPStressTesting.jl")

13.7 μs