Fault tree analysis

Deep dive

How it works

Parts:

• top event — the one undesired system state
• gates — OR (any input), AND (all inputs), k-of-n voting (at least k inputs); k-of-n is shorthand for OR over AND combinations
• basic events — leaves with a probability or rate; one event may appear in several places
• cut sets — basic events whose joint occurrence causes the top event; minimal when no subset suffices
• quantifier — rare-event sum, min-cut upper bound, or exact evaluation

Operations:

1. Define. Fix the top event; draw gates to basic events.
2. Expand (MOCUS, top-down). Keep rows of pending nodes. In a row, replace a gate: AND adds its inputs, OR splits the row into one row per input. A row of only basic events is a cut set.
3. Absorb. Delete any cut set containing a smaller one (A + A.B = A).
4. Quantify. A cut set's probability is the product of its events (independence assumed). Rare-event: their sum, an upper bound. Min-cut upper bound: 1 - prod(1 - P_i). Exact: enumerate event states, use inclusion-exclusion, or walk a BDD.
5. Rank. Birnbaum: P(top | event certain) - P(top | event absent). Fussell-Vesely: share of the top probability in cut sets containing the event.
6. Act. Remove single points and shared causes, recompute.

 hazard ──> TOP ──OR──┬── 2-of-3 sensors ──> {S1,S2} {S1,S3} {S2,S3}
                      ├── power supply  ──> {PSU}
                      └── common cause  ──> {CCF}
 expand + absorb ──> cut sets ──> P(top) ──> importances ──> design change

Common cause: identical redundant parts share design, installation, maintenance and environment, so one cause fails all. The beta-factor model turns a fraction beta of each part's failure probability into a shared event (NASA handbook). FMEA/FMECA (IEC 60812) is the bottom-up complement: per component, failure modes, effects and criticality. It seeds the leaves and checks completeness, but FMEAs cannot be patched into a tree (NASA handbook 4.8). Dynamic gates (priority-AND, spare, functional dependency) capture order and standby behaviour (handbook ch. 8).

Code

A 2-of-3 sensor voter plus one power supply plus a beta-factor common-cause event (q = 0.01, beta = 0.1).

use std::collections::BTreeSet;

pub enum Node {
    Basic(usize),         // index into the probability vector
    And(Vec<Node>),
    Or(Vec<Node>),
    KofN(usize, Vec<Node>), // fails when at least k inputs fail
}
use Node::*;
type Cut = BTreeSet<usize>;

fn combos(n: usize, k: usize) -> impl Iterator<Item = Vec<usize>> {
    (0u32..1 << n)
        .filter(move |m| m.count_ones() as usize == k)
        .map(move |m| (0..n).filter(|j| m >> j & 1 == 1).collect())
}

/// MOCUS: start with the top gate, replace the first gate in a row by its
/// inputs (AND: same row; OR: one row per input), then drop supersets.
pub fn min_cut_sets(top: &Node) -> Vec<Cut> {
    let (mut work, mut done): (Vec<Vec<&Node>>, Vec<Cut>) = (vec![vec![top]], vec![]);
    while let Some(mut row) = work.pop() {
        let Some(i) = row.iter().position(|n| !matches!(n, Basic(_))) else {
            done.push(row.iter().map(|n| if let Basic(e) = n { *e } else { 0 }).collect());
            continue;
        };
        match row.swap_remove(i) {
            And(c) => { row.extend(c); work.push(row) }
            Or(c) => for ch in c { let mut r = row.clone(); r.push(ch); work.push(r) },
            KofN(k, c) => for pick in combos(c.len(), *k) {
                let mut r = row.clone();
                r.extend(pick.into_iter().map(|j| &c[j]));
                work.push(r);
            },
            Basic(_) => unreachable!(),
        }
    }
    done.sort_by_key(|c| c.len());
    let mut min: Vec<Cut> = vec![];
    for c in done { // absorption: A + A.B = A
        if !min.iter().any(|m| m.is_subset(&c)) { min.push(c) }
    }
    min
}

fn fails(n: &Node, s: u32) -> bool { // structure function; bit e of s = event e occurred
    match n {
        Basic(e) => s >> e & 1 == 1,
        And(c) => c.iter().all(|x| fails(x, s)),
        Or(c) => c.iter().any(|x| fails(x, s)),
        KofN(k, c) => c.iter().filter(|x| fails(x, s)).count() >= *k,
    }
}

pub fn exact(top: &Node, p: &[f64]) -> f64 { // sum over all 2^n states
    (0u32..1 << p.len())
        .filter(|&s| fails(top, s))
        .map(|s| (0..p.len()).map(|e| if s >> e & 1 == 1 { p[e] } else { 1.0 - p[e] }).product::<f64>())
        .sum()
}
fn cut_p(c: &Cut, p: &[f64]) -> f64 { c.iter().map(|&e| p[e]).product() }
pub fn rare_event(cs: &[Cut], p: &[f64]) -> f64 { cs.iter().map(|c| cut_p(c, p)).sum() }
pub fn min_cut_upper_bound(cs: &[Cut], p: &[f64]) -> f64 {
    1.0 - cs.iter().map(|c| 1.0 - cut_p(c, p)).product::<f64>()
}
pub fn birnbaum(top: &Node, p: &[f64], e: usize) -> f64 {
    let (mut hi, mut lo) = (p.to_vec(), p.to_vec());
    (hi[e], lo[e]) = (1.0, 0.0);
    exact(top, &hi) - exact(top, &lo)
}
pub fn fussell_vesely(cs: &[Cut], p: &[f64], e: usize) -> f64 {
    cs.iter().filter(|c| c.contains(&e)).map(|c| cut_p(c, p)).sum::<f64>() / rare_event(cs, p)
}

fn main() {
    // events 0..=2 sensors, 3 power supply, 4 sensor common cause
    let names = ["S1", "S2", "S3", "PSU", "CCF"];
    let top = Or(vec![KofN(2, vec![Basic(0), Basic(1), Basic(2)]), Basic(3), Basic(4)]);
    let cs = min_cut_sets(&top);
    for c in &cs { println!("{:?}", c.iter().map(|&e| names[e]).collect::<Vec<_>>()); }
    let probs = |q: f64, beta: f64| [(1.0 - beta) * q, (1.0 - beta) * q, (1.0 - beta) * q, 1e-4, beta * q];
    for q in [1e-2, 0.3] { // sensor failure probability; beta factor 0.1
        let p = probs(q, 0.1);
        let (ex, re, ub) = (exact(&top, &p), rare_event(&cs, &p), min_cut_upper_bound(&cs, &p));
        println!("q={q}: exact {ex:.6e}  rare-event {re:.6e}  min-cut upper bound {ub:.6e}");
        assert!(ex <= ub && ub <= re); // coherent tree: exact <= MCUB <= rare event
    }
    let p = probs(1e-2, 0.1);
    for e in 0..5 {
        println!("{:4} Birnbaum {:.6}  FV {:.4}", names[e], birnbaum(&top, &p, e), fussell_vesely(&cs, &p, e));
    }
    let no_ccf = [1e-2, 1e-2, 1e-2, 1e-4, 0.0]; // same sensors, common cause ignored
    println!("without CCF: {:.6e}", exact(&top, &no_ccf));
    assert_eq!(cs.len(), 5);
    // absorption: T = A + A.B has the single cut set {A}
    let t = Or(vec![Basic(0), And(vec![Basic(0), Basic(1)])]);
    assert_eq!(min_cut_sets(&t), vec![Cut::from([0])]);
}

Run output (measured on this Mac (Apple M4 Pro)): At q = 0.01: exact 1.341176e-3, rare-event 1.343000e-3 (+0.14 %), min-cut bound 1.342613e-3. At q = 0.3: exact 0.2040, min-cut bound 0.2271, rare-event 0.2488. Fussell-Vesely: CCF 0.7446, each sensor 0.1206, PSU 0.0745. Birnbaum: CCF 0.99966, PSU 0.99876, each sensor 0.0178. Without CCF: 3.98e-4.

Complexity and constants

• A k-of-n gate yields C(n,k) cut sets and absorption here is quadratic in them: 5-of-20 gives 15,504 cut sets in 611 ms (measured on this Mac (Apple M4 Pro), release build, one run).
• Exact enumeration is 2^n: 20 events, 30.6 ms (same setup).
• Example tree, mean of 200,000 runs (same setup): rare-event sum 25 ns, exact 340 ns, MOCUS 596 ns.
• BDD size depends on variable order (Rauzy 1993).

Efficiency

• Cost: a few dozen events: microseconds to milliseconds; large plant models can exceed one million cut sets, so tools truncate (NASA handbook). Modelling and data effort dominate.
• Levers:
  • cut-off truncation — drop cut sets below about 1e-12; two significant figures usually kept (NASA handbook) — very large trees
  • BDD quantification — exact, disjoint paths, efficient importances (handbook 6.3) — high-probability events, k-of-n
  • cut-set caching — re-sum stored products, 25 ns vs 340 ns re-enumeration (measured here) — sensitivity sweeps
• Naive → standard → state of the art:
  • multiply gate probabilities bottom-up · wrong when events repeat
  • MOCUS cut sets plus rare-event sum · fast, loose above 0.1
  • BDD exact plus truncation plus Monte Carlo uncertainty · exact, depends on variable order

Implementation notes

• Store cut sets as sorted ids or bitsets; sort by size before absorbing.
• Per basic event keep unit (per hour or per demand) and common-cause group.

Pitfalls

• Common cause ignored: three parts at 1e-3 give 1e-9 independent but 1e-5 with a 1 % common cause (NASA handbook); the example voter is 3.4 times worse.
• Rare-event sum over 0.1: 22 % high at q = 0.3; the handbook advises a better method then.
• Birnbaum ignores the event's own probability (handbook); read it with Fussell-Vesely.
• Patching FMEAs into a tree, or one shared part drawn as two events, hides a single point of failure.
• An integrity level needs more than a probability: process, architecture and systematic-fault rules (from memory).

Variants and alternatives

In production

• Nuclear: NRC's NUREG-0492 (1981), the NASA handbook calls it the "leading technical information source" on fault trees.
• Space: NASA turned to fault trees and PRA after the 1986 Challenger accident (NASA handbook).
• Civil aircraft: SAE ARP4761 lists FTA, FMEA and common-cause analysis for 14 CFR 25.1309; failure class sets the DAL (Wikipedia).
• Automotive: ISO 26262 derives an ASIL from hazard analysis and has a part on safety-oriented analysis (Wikipedia).
• Process and machinery: IEC 61508 SIL bands, PFDavg 1e-5 to 1e-1 for SIL 4 to 1 (itemis summary); the example's 1.34e-3 as PFDavg is in the SIL 2 band.
• A monitor, watchdog or fault detection scheme enters as a basic event with a coverage factor.

Implementations

Sources

• Vesely, Goldberg, Roberts, Haasl, Fault Tree Handbook, NUREG-0492, US NRC, January 1981. record
• Vesely et al., Fault Tree Handbook with Aerospace Applications, Version 1.1, NASA, August 2002. PDF
• Rauzy, New algorithms for fault trees analysis, Reliability Engineering & System Safety 40(3), 1993. DOI
• Fussell, Henry, Marshall, MOCUS: a computer program to obtain minimal sets from fault trees, 1974. DOI
• IEC 61025:2006 Fault tree analysis. IEC · IEC 60812:2018 FMEA and FMECA. IEC · IEC 61508-1:2010. IEC
• Secondary: itemis SIL table, ISO 26262, ARP4761. Model format: Open-PSA MEF 2.0.