falsification

falsification is the process of systematically finding failures of a particular system to inform future design decisions.

Goals:

• enhance system sensors
• change the agent’s policy
• revise the system requirements
• adapt the training of human operators
• recognize a system as having limitations
• …or abandon the project

Here are some methods

direct falsification

• rollout to a ceratin depth
• check if any trajectory is a failure and collect
• return them

drawback: this doesn’t work super well for rare events

…how bad is it

\begin{equation} p_{fail} = \text{probability of failure} \end{equation}

we typically don’t know this! But suppose we did. Let’s define:

\begin{equation} p\qty(k): \text{probability we sample a failure on the $k$ th rollout} \end{equation}

Meaning, the probability of \((1-p_{fail})^{k-1} p_{fail}\). This is our distribution over \(k\), and it is a geometric distribution! Meaning, it should require \(\frac{1}{p_{fail}}\) simulations on average before we find a singular failure event.

falsification through optimization

disturbances

goal: systematically search for failures by taking control for the sources of randomness.

For instance, consider our observation model:

\begin{equation} o \sim O\qty(\cdot | s) \end{equation}

let’s re-write:

\begin{equation} o = O(s, x_0), x_{o} \sim D_{o} \qty(\cdot | s) \end{equation}

we are factoring the original model into a deterministic part \(o = O\), and also the stochastic part \(x_{o} \sim D_{o}\). Aesthetically, we typically want \(D\) to be a simple distribution, and perform transformations to the target distribution into \(O\).

we’ll do this for everything

\begin{equation} s’ \sim T \qty(\cdot | s,a) \implies s’ = T(s,a,x_{s}), x_{s} \sim D_{s}\qty(\cdot | s,a) \end{equation}

…and more

We can package all of these \(x,D\) up together, into disturbance \(x\) and disturbance distribution \(D\).

example

Suppose our observation is \(o \sim \mathcal{N} \qty(\cdot | s, \Sigma)\). Let’s factor it:

\begin{equation} o = s + x_0, x_0 \sim \mathcal{N} \qty(\cdot | 0, \Sigma) \end{equation}

that is, the disturbance is the “observation noise” added to the true state. We just have a disturbance distribution centered at zero which helps us add noise to the observation.

rewriting environment

function step(sys::System, s::State, D::DisturbanceDistributino)
    xo = rand(D.Do(s))
    o = sys.sensor(s, xo)
    xa = rand(D.Da(o))
    a = sys.agent(o,xa)
    xs = rand(D.Ds(s,a))
    s′ = sys.env(s,a,xs)

    # storing for bookeeping
    x = Disturbance(xa, xs, xo)

    return (; o, a, s′, x)
end

trajectory distribution

Recall: sources of randomness for a rollout — 1) the initial state, and 2) the disturbance distribution applied at each step.

We can actually then specify this trajectory distribution with the following properties:

abstract type TrajectoryDistribution end
function initial_state_distribution(p::TrajectoryDistribution) end
function distriburbance_distribution, t::Timestamp) end
function depth(p::TrajectoryDistribution) end

we can then roll this system out:

function rollout(p::TrajectoryDistribution; d=depth(p))
    s = rand(initial_state_distribution(p))
    τ = []
    for t = 1:d
        o,a,s′ = step(s, distriburbance_distribution(p,t))
        push!(τ, (s′,o,a,x))
        s = s′
    end
end

a normal rollout can be factored to this via a “nominal trajectory distribution” .

fuzzing

input a non-nominal trajectory distribution to cause failure. Usually, we do this by increasing variance off the nominal distirbution.

disturbance optimization

we want to systematically search over initial states and sequences of disturbances of find failure trajectories.

\begin{align} \min_{s,x} &\ f\qty(\tau) \\ s.t. &\ \tau = RO(s,x) \end{align}

where \(f(\tau)\) represents “closeness to failure”. Problem, though, using robustness alone isn’t super duper likely as a failure case (it will give very unlikely trajectories).

likelihood of a trajectory

The likelihood of a trajectory is the likelihood of the initial state and all disturbances in the trajectory appearing.

\begin{equation} p\qty(\tau) = p\qty(s_{1}) D\qty(x_1 | s_1, a_1, a_1) \dots D\qty(x_d | s_d, a_d, a_d) \end{equation}

Our new objective function, then:

\begin{equation} f\qty(\tau) = \begin{cases}

• p\qty(\tau), \text{if $\tau \not \in \psi$},\\ \rho \qty(\tau, \psi) \end{cases} \end{equation}

if a trajectory is not a failure (\(\tau \in \psi\)), we want to maximize failure; if trajectory is a failure then we want to maximize its likelihood.

properties of the goal + refactoring

• failures should never have a higher objective value than successes
• …but the log-likelihood of the objective above could cause non-failures to be negative error

so, more stably:

\begin{equation} f\qty(\tau) = \rho \qty(\tau, \psi) - \lambda \log \qty(p \qty(\tau)) \end{equation}

how do you optimize?

• local descrent methods: gradient descent, adam (these methods *require th gradient)..
• direct methods: Hooke-Jeeves Search: Nelder-Mead Simplex Method
• population methods

falsification through planning

Recall our optimization objective from above:

\begin{align} \min_{s, \mathbb{X}} &\ f(\tau) \\ s.t. &\ \tau = RO\qty(s,x) \end{align}

High level goal—we want to create iterative methods to find possible areas of errors (i.e. some tree search). This is useful when you have too many states to directly optimize over.

Tree Structure

• nodes: each stage
• edges: tuples of observation, action, disturbance \(\qty(o,a,x)\)

Building the Tree

1. select a node which is the state
2. extend the node by sampling an observation, action, disturbance \(\qty(o,a,x)\)

Various Tree Types

Heuristic Search

Heuristic Search, or Rapidly Exploring Random Trees, we

• select: sample a “goal state”, compute the objective for each node in the tree based on the goal state, select the node with the lowest objective
• extend: select disturbance, take a step using the selected disturbance, add result to the tree

We want our goals to roughly lead us to failure/be around failure; and the objective should be something like “distance” which measures the quality of being at a particular point.

So, revised:

• select: sampling a goal state from the failure region
• extend: select a disturbance that would move us closest to the goal state

But, this will give us failures, but not really likely failures. So, how do we go about doing that? It’s time for alternative objectives. To do this, let’s define a cost function (which must be positive to ensure the search will terminate):

\begin{equation} c = \text{current cost} + \text{cost to go} \end{equation}

the former is just computed from our historical trajectory; the latter is estimated some heuristic \(h\). For instance,

• current cost: distance to the current node in the tree from start
• cost to go: “direct distance to the goal”

For instance, if we wanted to include our likelihood:

• current cost: rescaled negative log likelihood (to keep stuff positive)
• cost to go: distance to the goal, as a proxy for NLL

NOTICE: if a heuristic is admissable and its guaranteed to never overestimate the cost of reaching the goal state, this is \(A^{*}\).

monte-carlo tree search falsification

Let’s use monte-carlo tree search for falsification.

• select: select a node based on a heuristic that balances Exploration and Exploitation. For a given node…
  • is the number of children \(\leq k N^{\alpha}\)?
    • yes! select it and extend
    • no! select a new node which minimizes \(Q_{\text{child}} - c \sqrt{ \frac{\log N}{N_{\text{child}}}}\), which is the Lower Confidence Bound Exploration; the reason why we are picking lowest is because we want to minimize \(Q\), instead of UCB 1 which is trying to maximize \(Q\)

How do we estimate \(Q\)? We can do whatever we want; for instance, we can perform a bunch of roll-outs and estimate the robustness.

reinforcement learning falsification

Technically, falsification is just RL:

• system => reward to adversary
• adversary => action to system

Most RL algorithms are designed to be very sample efficient, which means we can find failures rather quickly.

Using MCTS or reinforcement learning to search for the most likely failure is called adaptive stress testing.

how to pick a falsification method?

• if failure is easy to come by, just do direct falsification
• if you could compute the gradient, then do that
• otherwise, do black box approaches / population approaches / etc.