AA228V Lectures 05/06: Falsification Through Optimization

Falsification = Systematically Finding Failures

Why find failures?

To inform future design decisions.

Enhance system sensors

Change agent’s policy

Revise system requirements

Adapt training of human operators

Recognize as limitations

Abandon the project

Direct Samplingmay perform poorly for systems with rare failure events.

Geometric distribution:

P (k) = (1 - p_{fail})^{k - 1} p_{fail}

P_{fail} = 0.2

The expected value of this distribution is

E [k] = 1/ P_{fail}

In other words, it should require

1/ P_{fail}

simulations on average to find a single
failure event.

Direct Samplingmay perform poorly for systems with rare failure events.

In other words, it should require

1/ P_{fail}

simulations on average to find a single
failure event.

For systems with rare failure events,

P_{fail}

is really low.

e.g. imagine an aircraft collision avoidance system with

P_{fail} \approx 1 0^{- 9}

We would need an average of

1

billion simulations to observe a single failure!

🤔

We are going to need a better way.

🤔

Direct Samplingmay perform poorly for systems with rare failure events.

We can instead systematically search for failures by taking control of the sources of randomness in a system using

Disturbances

To incorporate disturbances into a system, we need to rewrite its agent, environment, and sensor models:

a \sim π (\cdot ∣ o)

s^{'} \sim T (\cdot ∣ s, a)

, and

o \sim O (\cdot ∣ s)

To incorporate disturbances into a system, we need to rewrite its agent, environment, and sensor models:

a \sim π (\cdot ∣ o)

s^{'} \sim T (\cdot ∣ s, a)

, and

o \sim O (\cdot ∣ s)

To incorporate disturbances into a system, we need to rewrite its agent, environment, and sensor models:

a \sim π (\cdot ∣ o)

s^{'} \sim T (\cdot ∣ s, a)

, and

o \sim O (\cdot ∣ s)

o \sim O (\cdot ∣ s)

To incorporate disturbances into a system, we need to rewrite its agent, environment, and sensor models:

a \sim π (\cdot ∣ o)

s^{'} \sim T (\cdot ∣ s, a)

, and

o \sim O (\cdot ∣ s)

o \sim O (\cdot ∣ s)

rewrite

o =

O (s, x_{o}),

deterministic
function

x_{o}

\sim

D_{o} (\cdot ∣ s)

disturbance
distribution

disturbance

o \sim O (\cdot ∣ s)

rewrite

o =

O (s, x_{o}),

x_{o}

\sim

D_{o} (\cdot ∣ s)

Example

Recall the inverted pendulum observation model:

o \sim N (\cdot ∣ s, Σ)

We can rewrite with disturbances as follows:

o = s + x_{o}, x_{o} \sim N (\cdot ∣ 0, Σ)

In this case, the disturbance represents the “observation noise” added to the true state.

The observation noise is sampled from a disturbance distribution centered at zero (no
noise) with covariance

Σ

x_{o}

Note: the model with disturbances still represents the same process. We have just
separated out the stochastic components so that we can control them!

Sensor

o \sim O (\cdot ∣ s)

rewrite

o =

O (s, x_{o}),

x_{o}

\sim

D_{o} (\cdot ∣ s)

Agent

a \sim π (\cdot ∣ o)

rewrite

a =

π (o, x_{a}),

x_{a}

\sim

D_{a} (\cdot ∣ o)

Environment

s^{'} \sim T (\cdot ∣ s, a)

rewrite

s^{'} =

T (s, a, x_{s}),

x_{s}

\sim

D_{s} (\cdot ∣ s, a)

Sensor

o \sim O (\cdot ∣ s)

rewrite

o =

O (s, x_{o}),

x_{o}

\sim

D_{o} (\cdot ∣ s)

Agent

a \sim π (\cdot ∣ o)

rewrite

a =

π (o, x_{a}),

x_{a}

\sim

D_{a} (\cdot ∣ o)

Environment

s^{'} \sim T (\cdot ∣ s, a)

rewrite

s^{'} =

T (s, a, x_{s}),

x_{s}

\sim

D_{s} (\cdot ∣ s, a)

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

“disturbution”

Sensor

o \sim O (\cdot ∣ s)

rewrite

o =

O (s, x_{o}),

x_{o}

\sim

D_{o} (\cdot ∣ s)

Agent

a \sim π (\cdot ∣ o)

rewrite

a =

π (o, x_{a}),

x_{a}

\sim

D_{a} (\cdot ∣ o)

Environment

s^{'} \sim T (\cdot ∣ s, a)

rewrite

s^{'} =

T (s, a, x_{s}),

x_{s}

\sim

D_{s} (\cdot ∣ s, a)

o \sim N (\cdot ∣ s, Σ)

o = s + x_{o}, x_{o} \sim N (\cdot ∣ 0, Σ)

π (a ∣ o) = {10 if a = - 15.0 θ - 8.0 ω otherwise

a = - 15.0 \hat{θ} - 8.0 \overset{ω}{^}

*Note: no

x_{a}

because the
agent is deterministic!

T (s^{'} ∣ s, a) = ⎩ ⎨ ⎧ 10 if s^{'} = [θ + ω Δ t ω + (\frac{3 g}{2 l} sin θ + \frac{3 a}{m l ^{2}}) Δ t] otherwise

s^{'} = [θ + ω Δ t ω + (\frac{3 g}{2 l} sin θ + \frac{3 a}{m l ^{2}}) Δ t]

*Note: no

x_{s}

because the
environment is deterministic!

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

θ

ω

s = [0.3, 0.1]

o = s + x_{o},

x_{o} \sim N (\cdot ∣ 0, Σ)

x_{θ}

x_{ω}

x_{o} = [0.2, 0.25]

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

θ

ω

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = s + x_{o},

x_{o} \sim N (\cdot ∣ 0, Σ)

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = s + x_{o},

x_{o} \sim N (\cdot ∣ 0, Σ)

θ + x_{θ}

ω + x_{ω}

o = [0.5, 0.35]

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = [0.5, 0.35]

deterministic for the pendulum!

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = [0.5, 0.35]

deterministic for the pendulum!

a = - 15.0 \hat{θ} - 8.0 \overset{ω}{^}

a = - 15.0 (0.5) - 8.0 (0.35) = - 9.9

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = [0.5, 0.35]

deterministic for the pendulum!

a = - 15.0 (0.5) - 8.0 (0.35) = - 9.9

deterministic for the pendulum!

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = [0.5, 0.35]

deterministic for the pendulum!

a = - 15.0 (0.5) - 8.0 (0.35) = - 9.9

deterministic for the pendulum!

s^{'} = [θ + ω Δ t ω + (\frac{3 g}{2 l} sin θ + \frac{3 a}{m l ^{2}}) Δ t]

s^{'} = [0.31, - 1.38]

Disturbance

x

x_{a}

x_{s}

x_{o}

Disturbance distribution

D

D_{o} (\cdot ∣ s)

D_{a} (\cdot ∣ o)

D_{s} (\cdot ∣ s, a)

s = [0.3, 0.1]

x_{o} = [0.2, 0.25]

o = [0.5, 0.35]

deterministic for the pendulum!

a = - 15.0 (0.5) - 8.0 (0.35) = - 9.9

deterministic for the pendulum!

s^{'} = [0.31, - 1.38]

record everything
that happened

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

Trajectory Distribution

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

Trajectory Distribution

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

Trajectory Distribution

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

Trajectory Distribution

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

the initial state

the disturbance applied at each time step

Trajectory Distribution

Sampling a Trajectory Distribution: Rollout

We can use the idea of disturbances to explicitly define the distribution over trajectories for a system.

There are two sources of randomness in a trajectory rollout:

Trajectory Distribution

Sampling a Trajectory Distribution: Rollout

🤔

Wait.. didn’t we already see a different algorithm for rollout in the intro lecture?

Sampling a Trajectory Distribution: Rollout

Rollout from Introduction Lecture

This version of rollout is
implicitly sampling from the
nominal trajectory distribution
for the system.

Thenominal trajectory distributionrepresents the distribution over trajectories that we expect to observe in the real world.

Note:

Every agent has a nominal $D_{a}$ implemented
Every environment has a nominal $P_{s}$ and $D_{s}$ implemented
Every sensor has a nominal $D_{o}$ implemented

The nominal models come from data/expert knowledge from
the real world (see chapter 2!).

Pendulum example: the nominal trajectory distribution

P_{s}

U ([- \frac{π}{16}, \frac{π}{16}]) \times U ([- 1, 1])

D_{a} (\cdot ∣ o)

Deterministic

D_{s} (\cdot ∣ s, a)

Deterministic

D_{o} (\cdot ∣ s)

N (0, 0. 1^{2} I)

🤔

Wait.. didn’t we already see a different algorithm for rollout in the intro lecture?

Sampling a Trajectory Distribution: Rollout

Rollout from Introduction Lecture

This version of rollout is
implicitly sampling from the
nominal trajectory distribution
for the system.

=

Fuzzing

Input a different (not nominal) trajectory distribution into this
function — one that is more likely to cause failures.

e.g. for the inverted pendulum, we could use a disturbance distribution with
higher perception noise than the nominal distribution

Optimization

Our goal is to systematically search over initial states and sequences of disturbances to find failure trajectories.

s

, x

minimize

f (τ)

subject to

τ = Rollout (s, x)

objective function that represents
“closeness to failure”

Optimization

Our goal is to systematically search over initial states and sequences of disturbances to find failure trajectories.

s

, x

minimize

f (τ)

subject to

τ = Rollout (s, x)

objective function that represents
“closeness to failure”

Optimization

Our goal is to systematically search over initial states and sequences of disturbances to find failure trajectories.

f (τ)

f (τ)

objective function that represents
“closeness to failure”

🤔

What metric from chapter 3 reminds you of “closeness to failure”?

Robustness!

(or if our optimization algorithm needs gradients, smooth robustness)

Optimization

Our goal is to systematically search over initial states and sequences of disturbances to find failure trajectories.

f (τ)

objective function that represents
“closeness to failure”

🤔

What metric from chapter 3 reminds you of “closeness to failure”?

Robustness!

(or if our optimization algorithm needs gradients, smooth robustness)

f (τ)

= ρ (τ, ψ)

🤔

What might be a problem with the robustness objective?

We might get very unlikely trajectories…

Optimization

Our goal is to systematically search over initial states and sequences of disturbances to find failure trajectories.

🤔

What might be a problem with the robustness objective?

We might get very unlikely trajectories…

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

D (x_{2} ∣ s_{2}, a_{2}, o_{2})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

D (x_{2} ∣ s_{2}, a_{2}, o_{2})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

D (x_{2} ∣ s_{2}, a_{2}, o_{2})

\dots

D (x_{d} ∣ s_{d}, a_{d}, o_{d})

incorporate likelihood
into the objective

How do we evaluate the likelihood of a trajectory?

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

p (τ) =

p (s_{1})

D (x_{1} ∣ s_{1}, a_{1}, o_{1})

D (x_{2} ∣ s_{2}, a_{2}, o_{2})

\dots

D (x_{d} ∣ s_{d}, a_{d}, o_{d})

D (x ∣ s, a, o) = D_{a} (x_{a} ∣ o) D_{s} (x_{s} ∣ s, a) D_{o} (x_{o} ∣ s)

lo g

lo g

incorporate likelihood
into the objective

New Objective:

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

The trajectory

τ

is a failure.

“Make the failure trajectory more likely”

The trajectory

τ

is not a failure.

“Move the trajectory closer to a failure”

incorporate likelihood
into the objective

Previous Objective:

f (τ) = ρ (τ, ψ)

New Objective:

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

Iteration 1

Iteration 5

Iteration 8

Converged

incorporate likelihood
into the objective

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

Some Notes on This Objective

We must ensure that failures never have a
higher objective value than successes.

No problem!

ρ (τ, ψ) \geq 0

for successes
and

- p (τ)

is always less than

0

…but

p (τ)

is often really small causing
numerical stability issues

…so we want to use log-likelihood instead, but
this breaks the first requirement because log
likelihood can be less than

0

…so sometimes a different objective works
better in practice (see next slide)

incorporate likelihood
into the objective

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) =

ρ (τ, ψ)

robustness

-

λ

lo g (p (τ))

*tends to be more numerically stable

incorporate likelihood
into the objective

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) =

ρ (τ, ψ)

-

λ

lo g (p (τ))

log likelihood

*tends to be more numerically stable

incorporate likelihood
into the objective

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) =

ρ (τ, ψ)

-

λ

weighting
parameter

lo g (p (τ))

*tends to be more numerically stable

Then we optimize!

Objective Function

Optimizer

f (τ) = ρ (τ, ψ)

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) = ρ (τ, ψ) - λ lo g (p (τ))

Then we optimize!

Objective Function

Optimizer

f (τ) = ρ (τ, ψ)

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) = ρ (τ, ψ) - λ lo g (p (τ))

Optimization
Algorithm

Objective

Parameters

Optimum

Optimization
Algorithm

Objective

Parameters

Optimum

s, x

Local Descent Methods

Population Methods

x

f (x)

x

f (x)

first-order and
second-order

e.g. gradient descent,
ADAM, LBFGS

gradients
required!

zero-order
(direct methods)

e.g. Hooke-Jeeves,
Nelder-Mead

work for black-
box systems!

Optimization
Algorithm

Objective

Parameters

Optimum

s, x

Local Descent Methods

Population Methods

x

f (x)

x

f (x)

first-order and
second-order

e.g. gradient descent,
ADAM, LBFGS

gradients
required!

zero-order
(direct methods)

e.g. Hooke-Jeeves,
Nelder-Mead

work for black-
box systems!

Optimization
Algorithm

Objective

Parameters

Optimum

s, x

Local Descent Methods

Population Methods

x

f (x)

x

f (x)

first-order and
second-order

e.g. gradient descent,
ADAM, LBFGS

gradients
required!

zero-order
(direct methods)

e.g. Hooke-Jeeves,
Nelder-Mead

work for black-
box systems!

Then we optimize!

Objective Function

Optimizer

f (τ) = ρ (τ, ψ)

f (τ) = {- p (τ) ρ (τ, ψ) if τ \in / ψ otherwise

f (τ) = ρ (τ, ψ) - λ lo g (p (τ))

Optimization
Algorithm

Objective

Parameters

Optimum

Take AA222/CS361 for more details!!!

Plan for Today

Direct Sampling

Disturbances

Fuzzing

Optimization

This is what I would start with for Project 1!

This (and/or what we learn Thursday) is what I would do to
improve my leaderboard score.