John Rushby, 2017, updated September 2024

Added Speculation on Autonomous Systems February 2019,
And What about the Boeing 737 MAX? March 2019.

See also information about Assurance 2.0

History and Overview

My current thinking is that the leaves and the interior parts of an assurance case argument (viewed as a tree) should be interpreted differently from each other. The leaves concern evidence about the system and are best evaluated using methods from epistemology, whereas the interior nodes document reasoning (based on the evidence) and should be evaluated by the methods of logic. This idea is first adumbrated in my SafeComp 2013 paper.

Evidential and Reasoning Steps

Natural Language Deductivism, NLD

Note that NLD is not the same as formal verification even though both are tantamount to proof. Formal verification establishes that one formal model (typically for an implementation) is consistent with another (typically for a specification). Within an assurance case, that's an item of evidence. Other parts of the assurance case must establish that the lower model actually conforms to the real implementation and that the upper one accurately formalizes the specification used elsewhere in the case. And yet other parts of the case must ensure that the versions verified are the same as those used, and that our method of verification (tools, theorem prover etc.) are sound, and that our assumptions are discharged etc.

The evidential claims in an assurance case are not formal statements but statements about "big" parts of the overall development: e.g., "this specification is correct wrt. its intended use". And its reasoning steps are not intricate proofs but simple conjunctions that (indefeasibly) entail their parent claim.

From Assurance to Certification: Few Faults to Rare Failures

However, the degree of confidence in the absence of faults can be expressed as a subjective probability, and a little arithmetic then allows us to calculate the probability that the system will survive n independent demands (e.g., hours of flight) without failure, given some estimate for the probability that it fails if (despite our assurance) it is faulty. Prior experience (e.g., failure-free tests) gives us some handle on the latter, and the overall problem is then one of Bayesian inference: given m successful demands and our confidence (as a probability) that the system is free of faults, what is the probability of surviving n-m future demands without failure? To perform this calculation, we need some prior distribution for the probability of failure if faulty, and this will be hard to obtain and hard to justify. However, Strigini and Povyakalo have shown that there is a worst possible distribution and this allows calculation of estimates that are guaranteed to be conservative. If assurance gives us 90% confidence that the system is free of faults and we have observed m failure-free demands, then we can be reasonably confident of surviving another 10×m demands without failure (whereas without the confidence derived from assurance we can barely expect another m). At the end of that period, we have a lot more observations, and that gives us confidence for another 10-fold increase in exposure and so we can "bootstrap" our way to the (FAA required) lifetime of the fleet. This is a remarkable result (again due to Povyakalo and Strigini plus Bishop) and, in my opinion, the best explanation we have for how assurance actually works.

Assurance 2.0

Tool Support and Applications

For autonomous systems, see below

Please note that many of the papers here are slightly updated from their published form--so it's always best to get my papers from my bibliography page.

What about the Boeing 737 MAX?

In fact, I think tools similar to those used for software assurance (model checkers, static analyzers) might help the designers of those highly integrated and complex systems get their requirements right.

What About Autonomous Systems?

But what about new systems, such as self-driving cars and "increasingly autonomous" (IA) airplanes where some of the software is generated by opaque methods like machine learning implemented in deep neural nets? I participated in a NASA study on this topic: Considerations in Assuring Safety of Increasingly Autonomous Systems but my thinking has evolved somewhat since then and is described in this paper on Model-Centered Assurance For Autonomous Systems with Susmit Jha and Shankar. A more recent and comprehensive study, written with Robin Bloomfield, is this 2024 technical report on Assurance of AI Systems From a Dependability Perspective, which develops the points below in more detail.

The Big Picture Remains The Same

1. We develop an assurance case to provide confidence that our system is free of faults
2. We apply this in the Bayesian worst-case model of Strigini and Povyakalo
3. So that failure-free experience (initially tests, then real-life) provides confidence that significantly greater exposure will also be failure-free.

For human-driven cars, the fatal accident rate in the USA is a bit over 10 per billion miles. We intend that self-driving cars should be safer than humans, so a target of 5 per billion miles might be reasonable. That is 5×10^-9 per mile or 10^-7 per hour, if we assume 20 mph. So that's a factor of about 100 less than airplanes. The main impact is that we do not expect the experience in step 3 to be failure-free, but we do expect it to be within the rate that society considers acceptable, and we do not expect our confidence in assurance at step 1 to be as high as for conventional systems.

But At Present It's All Experience and No Prior Assurance

Here, it seem that confidence is developed by huge quantities of simulation tests and real experience: this approach is sometimes referred to as "collecting miles". The tests need to cover many possible scenarios and so there is much current research in the specification, generation, and curation of scenarios. One difficulty is that of "fat tails": I heard of one set of scenarios where 26 cases covered half of all pedestrian accidents, and the other half required 5,287 cases.

But more fundamentally, the problem with purely "collecting miles" is that with no prior confidence from assurance, exposure of n units (miles, or hours) gives you merely weak confidence in the safety of another n, whereas with prior confidence from assurance you could be good for as many as 10×n.

Assurance For Autonomous Systems: World Model plus Actions

For traditional software, there are well established and historically effective methods for developing assurance, as documented in guidelines like ARP 4754A and DO-178C (for aircraft) and ISO 26262 (for cars), or as formulated in assurance cases. But, as we know, autonomous systems are full of deep learning and other elements that are not amenable to traditional assurance, so what can we do?

Typically, the deep learning components are concerned with perception: for an autonomous car, this will include finding the traffic lanes, identifying and locating other cars and obstacles around us, reading road signs and so on. The car uses its interpretation and integration of these perceptions in planning its next steps. The exact path from perception to plan seems to be part of the "secret sauce" of each system.

I propose a somewhat different approach: the task of deep learning and other perception components is to build a model of the (local) world. This is not a new idea: Josh Tenenbaum and his colleagues at MIT and NYU say much the same in their paper "Building Machines that Learn and Think Like People" (PDF). However, Tenenbaum is explicitly concerned with human-like AI and learning, whereas I am interested in assurable autonomy. Tenenbaum takes his inspiration from the way the human brain seems to work, while I think that this is a good design, independently of any biological precedents.

The reason I think this is a good design is that it separates the autonomous system into two simpler parts:

1. One is concerned with building a model of the world
2. The other is concerned with planning and delivering actions, based on that model

1. How good is the model of the world?
2. How safe are the actions, given the model?

In the words of my former boss, Brian Randell, "we have succeeded in reducing the problem to a previously unsolved problem". That's progress!

Before I discuss assurance for world models, I'll take an excursion to describe a plausible and attractive architecture for constructing these models. This architecture seems to be the one used by the human brain, but that is not the reason I advocate it: as with model building as the goal, I think there are independent reasons for considering this architecture a good one.

Cognitive Architecture for Model Construction

What is new is that the model is built by machine learning.

Now part of the inspiration for machine learning and neural nets is to reproduce in simplified form some of the mechanisms that are believed to operate in the human brain. So let us take this a bit further and look a little more deeply into what is known or conjectured about the operation of the brain.

The best current explanation (in my opinion) for how the brain works is called predictive processing (PP) or sometimes predictive coding or predictive error minimization. I'll explain it in terms of a self-driving car.

One thing the autonomy system of the car has to do is locate its traffic lane and stay in it. A camera is one important element in performing this task. Now, the array of numbers indicating light and color intensities at each pixel of the camera field does not directly indicate traffic lanes. Instead, we have to bring the idea of traffic lanes to the image and invent some algorithm (e.g., based on the Hough transform, invented here at SRI) for interpreting it so that it reveals the lanes.

It is rather wasteful to interpret each camera frame ab-initio--the lane in this frame is surely going to be related to the lane in the previous one--so we could seed our lane detector with information gleaned from previous frames and start our interpretation of this frame with our best guess where the lane is going to be. Not only is this computationally more efficient, it is more accurate and robust (e.g., it can deal with a few frames of scuffed or missing lane markings, where an ab-initio algorithm might fail). There will be uncertainty in our detection of the lanes and we should manage this explicitly and record our confidence in lane location as a probability distribution function (pdf).

In its completed form, this approach to lane detection is a Bayesian estimator: we have a "prior" pdf representing our best estimate (based on previous frames) where we expect the lanes to be, we obtain new information (a new camera frame) and we update our estimate according to Bayes' rule to give us the best "posterior" pdf for the lane locations (so it is like a Kalman filter for images).

The parts of the brain concerned with interpretation of the senses work like this (as first proposed by Helmholtz in the 1860s). Contrary to naive expectations of a bottom-up flow of sense data, there are more neural pathways going from upper to lower levels of the brain than vice versa, and this is because predictions are flowing down, and only corrections are flowing up. The upper levels of the sensory interpretation systems of the brain maintain a best guess (i.e., a model) of the way the world is, and the senses and (approximations to) Bayesian estimation provide corrections that minimize prediction error.

There's a rather difficult extended version of predictive processing known as "Free Energy" ("free" as in "available"; it comes from Hamiltonian mechanics). Here's a hagiography of its founder Karl Friston. Free Energy extends the theory to include actions: the brain "predicts" that the hand, say, is in a certain place and to minimize prediction error the hand actually moves there. Prediction error can be partitioned between that in sensing and that in acting. I have a hunch that my proposal for assurance can be cast in this framework by assuming zero action error (because in this specific context, we can verify correct action, given the model, so all prediction error is in the model).

Assurance for Constructed Models of the World

The idea of a model is that it allows us to perform calculations and experiments: i.e., to make predictions about future courses of action. Provided our model (and method of calculating on it) are accurate, our predictions will be accurate and, presumably, safe.

The attraction of PP is that it allows for integration of different "points of view" so that the model likely to be both more robust and more accurate. For example, above the camera interpretation component of the lane detector we could have a component that observes the locations and movements of the cars around us, and above that we may have mapping and GPS information that tells us where the road is, if not the individual lanes. And if we've driven the road before, some of that experience may be recorded in another component. The goal is to develop a federation of components (it does not have to be a linear hierarchy) that collectively constructs a model of the road and its lanes.

The components that contribute to a PP model need not all be based on perception. Some could be based on general knowledge about the world. For example, if a certain item in the scene is classified as a chicken, that component might check that it is less then 2 feet tall, or if another item is said to be a boat, it could check there is water.

How can we develop assurance that the model constructed by an autonomous system accurately reflects the real world? We do not have much insight into its method of construction (other than selecting the training set) since it is produced by components that were generated by machine learning. So it seems the best we can do are tests and experiments. We have to be cautious about tests, since they can turn into collecting miles and will not deliver the independent assurance we need.

One possibility is to start with a modeled world, generate scenarios from that, run the system under test against those, and compare the world model that it constructs against the one we started with. We can then introduce perturbations (e.g., obscured lane markings) into the scenario generation until the constructed model departs from the original and thereby learn something of its robustness.

The first two steps are the same as for collecting miles, but then they run the complete system and check for hazardous outcomes. In effect, they are confounding the actions and the model, whereas we explicitly focus on the model.

Redundancy: Ensembles and Runtime Monitors

There are two ways of using the diverse components: one is to "sum" their outputs, the other is to use them as runtime monitors.

Many of the most effective AI systems (e.g., competition winners) use the "summing" approach to create ensembles built from multiple diverse components. One of the attractions of the PP architecture is that it naturally lends itself to this approach. Both within a level and up and down the hierarchy, different systems and different "points of view" are combined to construct a robust and accurate model of the world.

We can imagine that some of the diverse components are explicitly constructed to deliver a different "point of view": for example, we can imagine a "safety conscious" lane detector that is more conservative in its judgments; that is, the main system has a "best guess" model for where the lanes are, whereas the "safety conscious" component has a higher threshold ("certainty") on a weaker model.

Such "safety conscious" components could alternatively be used as runtime monitors rather than folded into the overall PP architecture: that is actions are derived from the regular model but then checked against the safety model.

Conclusion