Suggest edit — falsification

Title

Name

Note

---
title: "falsification"
type: concept
related: [Falsification, Monte Carlo Tree Search, Reinforcement Learning, Gradient Descent, Exploration And Exploitation]
source: https://www.jemoka.com/posts/kbhfalsification/
confidence: high
status: active
---

falsification is the process of systematically finding failures of a particular system to inform future design decisions.
Goals:
enhance system sensors change the agent&rsquo;s policy revise the system requirements adapt the training of human operators recognize a system as having limitations &hellip;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&rsquo;t work super well for rare events
&hellip;how bad is it \begin{equation} p_{fail} = \text{probability of failure} \end{equation}
we typically don&rsquo;t know this! But suppose we did. Let&rsquo;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&rsquo;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&rsquo;ll do this for everything
\begin{equation} s&rsquo; \sim T \qty(\cdot | s,a) \implies s&rsquo; = T(s,a,x_{s}), x_{s} \sim D_{s}\qty(\cdot | s,a) \end{equation}
&hellip;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&rsquo;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 &ldquo;observation noise&rdquo; 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 &mdash; 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 &ldquo;nominal trajectory distribution&rdquo; .
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} &amp;\ f\qty(\tau) \\ s.t. &amp;\ \tau = RO(s,x) \end{align}
where $f(\tau)$ represents &ldquo;closeness to failure&rdquo;. Problem, though, using robustness alone isn&rsquo;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 &hellip;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}} &amp;\ f(\tau) \\ s.t. &amp;\ \tau = RO\qty(s,x) \end{align}
High level goal&mdash;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 select a node which is the state 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 &ldquo;goal state&rdquo;, 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 &ldquo;distance&rdquo; 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&rsquo;s time for alternative objectives. To do this, let&rsquo;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: &ldquo;direct distance to the goal&rdquo; 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&rsquo;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&hellip; 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 =&gt; reward to adversary adversary =&gt; 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.