Hypergraph Percolation & Higher-Order Simplicial Contagion in Air-Gapped Industrial Networks

J. McKenney

This paper is a standalone treatise in the WG-07 Threat Modeling and TACAM Matrix working group rather than an entry in a numbered series. It applies the working group's threat-modeling programme to a mathematical question, the topology of air-gap bridging, not addressed by the group's other papers, which is its own placement.

Licence: CC BY 4.0. 17 September 2026.

Executive Abstract#

Industrial plants such as nuclear stations and gas processing facilities keep safety-critical control systems on a physically separate network from everyday operations, an air gap, on the assumption that isolation stops malware from crossing. Standard models of how infection spreads treat every connection as a simple one-to-one link between two devices. That assumption misses how maintenance actually happens: one laptop or diagnostic tool routinely touches several safety controllers, in sequence or at the same time, during a single visit, linking many devices at once rather than two.

Using mathematics built for this many-at-once kind of connection, the paper shows the difference is fundamental rather than a minor correction. Once enough of these multi-device maintenance connections exist, the air-gapped network can flip from apparently safe to fully compromised all at once, instead of spreading gradually as a one-to-one model predicts.

The paper then uses the same mathematics to find the smallest set of maintenance connections that would need to be controlled or removed to prevent that sudden compromise, letting a plant keep the maintenance access it needs while closing the specific paths that make the worst case possible.

Abstract#

Critical infrastructure control environments, including nuclear power stations, liquefied natural gas trains, and offshore production platforms, rely on physical air-gaps between Purdue Model Level 3 operations networks and Level 1/2 safety-critical controllers. Traditional threat modeling and epidemic spreading models abstract network conduits as pairwise graphs of nodes and edges, where infections transmit independently across one-dimensional links between node pairs. This pairwise abstraction is a mathematical fallacy. In real facilities, air-gap bridging occurs through higher-order group interactions: one maintenance laptop, shared calibrator, or engineering USB tool connects sequentially or concurrently to multiple PLCs, HMIs, and safety instrumented systems within a single maintenance window. This monograph reformulates air-gapped propagation through abstract simplicial complexes and hypergraph percolation theory. Multi-node bridging induces hyperedges and 2-simplices whose contagion cannot be decomposed into independent pairwise channels. A non-linear simplicial contagion model coupling one-simplex transmission with 2-simplex cooperative reinforcement yields a discontinuous first-order phase transition, explosive percolation: where pairwise models predict low infection rates stay sub-critical and self-extinguishing, cooperative interactions induce bistability and hysteresis, causing simultaneous infection of safety controllers. A hypergraph transversal immunization algorithm then identifies the minimal cut of transient maintenance bridges whose removal collapses the higher-order coupling below the bistability threshold, restoring the sub-critical pairwise-only regime while preserving maintenance operability.

1. The Pairwise Graph Fallacy in Air-Gapped Industrial Networks#

To safeguard high-consequence operational technology against external cyber interdiction, operators enforce rigorous network segregation. In compliance with IEC 62443-3-2 and the Purdue Enterprise Reference Architecture (PERA), safety instrumented systems (Level 1) and local human-machine interfaces (Level 2) are physically isolated from external routable IP networks via hardware air-gaps or unidirectional data diodes.

Traditional threat modeling frameworks, including graph-theoretic attack graphs, MITRE ATT&CK for ICS, and classical epidemiological spreading models (such as the standard Susceptible-Infectious-Susceptible [SIS] framework), model attack propagation across networks as a collection of dyadic (pairwise) edges:

Under this assumption, an infected node $u \in V$ transmits malware to adjacent node $v \in V$ along edge $e = (u, v)$ with independent Poisson probability rate $\beta$.

This pairwise representation fails fundamentally in air-gapped industrial enclaves.

In physical industrial facilities, malware does not propagate along static network cables across the air-gap. Instead, air-gap transit occurs through shared physical maintenance workflows:

1. Transient Multi-Device Maintenance Sessions: During scheduled outages, an instrument technician connects a single hardened field programming laptop to a central engineering terminal to download project logic, subsequently connecting to three independent PLCs, an auxiliary I/O rack, and an HMI within a four-hour window.
2. Multi-Drop Optical Diagnostic Busses: Technicians use portable optical calibration units (e.g., HART calibrators, Modbus field communicators) that attach simultaneously or in rapid succession to multiple isolated field sensors and transmitter loops.
3. Firmware USB Bridge Hopping: USB-borne rootkits (exemplified by Stuxnet) exploit Windows autorun and LNK vulnerabilities to infect field programmers, establishing an asynchronous group-exposure manifold.

When an infected field device interfaces with multiple controllers, the infection mechanism is simultaneous and group-correlated. The interaction is not a sum of independent dyadic contacts; rather, it constitutes a higher-order interaction involving three or more entities simultaneously. Representing this group event as isolated pairwise links destroys topological correlation, severely underestimating the velocity and systemic penetration of air-gap infections.

2. Mathematical Topology: Simplicial Complexes & Hypergraphs#

To rigorously capture higher-order dependencies in air-gapped operational environments, the Eigenia Threat Modeling Working Group formulates the network topology as an abstract simplicial complex and a uniform hypergraph.

2.1 Abstract Simplicial Complexes#

Let $V = \{v_1, v_2, \dots, v_N\}$ denote the set of industrial physical assets (PLCs, HMIs, field instruments, and transient maintenance equipment).

An abstract simplicial complex $\mathcal{K}$ on $V$ is a collection of non-empty finite subsets of $V$, termed simplices, satisfying the downward closure property:

A simplex $\sigma$ containing $k+1$ vertices is defined as a $k$-simplex, with dimension $\dim(\sigma) = k$:

• $0$-simplex: A single isolated physical asset $[v_i]$ (node).
• $1$-simplex: A direct, dedicated communication link $[v_i, v_j]$ (pairwise edge).
• $2$-simplex: A triangular group interaction $[v_i, v_j, v_k]$ representing a maintenance session wherein asset $v_i$ (e.g., laptop) simultaneously bridges controllers $v_j$ and $v_k$.
• $k$-simplex: A group interaction involving $k+1$ mutually interacting nodes $[v_0, v_1, \dots, v_k]$.

The boundary operator $\partial_k: C_k(\mathcal{K}) \to C_{k-1}(\mathcal{K})$ maps each $k$-simplex to an alternating formal sum of its $(k-1)$-dimensional faces:

satisfying the fundamental topological identity $\partial_{k-1} \circ \partial_k = 0$.

2.2 Hypergraph Incidence Representation#

When group interactions do not satisfy downward closure (for instance, when three PLCs interact exclusively through a shared calibrator without mutual communication), the topology is represented as a hypergraph $\mathcal{H} = (V, \mathcal{E})$, where hyperedges $e \in \mathcal{E}$ are arbitrary subsets of $V$ with $|e| \ge 2$.

The hypergraph is codified by the incidence matrix $\mathbf{H} \in \{0, 1\}^{|V| \times |\mathcal{E}|}$:

The hypergraph adjacency tensor $\mathbf{A} \in \mathbb{R}^{N \times N}$ and 2-simplex adjacency tensor $\mathbf{B} \in \mathbb{R}^{N \times N \times N}$ govern higher-order coupling:

3. Non-Linear Simplicial Contagion Dynamics: Explosive Percolation#

In standard pairwise SIS models, the density of infected nodes $\rho(t)$ evolves smoothly according to a continuous second-order phase transition. Above the critical epidemic threshold $\lambda > \lambda_c$, infection spreads; below it, infection decays exponentially to zero.

In contrast, higher-order simplicial contagion exhibits explosive percolation: a discontinuous first-order phase transition characterized by bistability and hysteresis.

3.1 Coupled Dynamical Equations#

Let $x_i(t) \in [0, 1]$ denote the probability that industrial asset $v_i$ is compromised at time $t$. Let $\mu$ denote the remediation rate (operator firmware re-flashing and sanitization).

Infection occurs via two competing mechanisms:

1. Pairwise Infection rate $\lambda_1$: Malware transits across 1-simplices (dyadic Ethernet or serial links).
2. Higher-Order Simplicial Infection rate $\lambda_2$: Contagion transits across 2-simplices $[v_i, v_j, v_k]$ under cooperative reinforcement: asset $v_i$ is exposed to infection if both $v_j$ and $v_k$ are compromised, representing collective vulnerability exposure on a shared maintenance bus.

The mean-field dynamical equation governing node $v_i$ is:

Assuming homogeneous mixing on a simplicial complex with average node degree $\langle k_1 \rangle$ and average 2-simplex triangle degree $\langle k_2 \rangle$, the global infection fraction $\rho(t) = \frac{1}{N} \sum_{i=1}^N x_i(t)$ evolves according to:

3.2 Proof of Discontinuous Phase Transition and Hysteresis#

Setting $f(\rho) = 0$ reveals the stationary steady-state solutions $\rho^*$:

The trivial disease-free state $\rho_0^* = 0$ is always an equilibrium. Factoring out $\rho$, non-zero equilibria satisfy the quadratic equation:

The discriminant $\Delta$ of this quadratic system is:

When higher-order exposure dominates ($\lambda_2 \langle k_2 \rangle > \lambda_1 \langle k_1 \rangle$), a saddle-node bifurcation occurs at $\Delta = 0$, producing a bistable regime where both the healthy state $\rho = 0$ and a high-infection epidemic state $\rho_+^* > 0$ are simultaneously locally stable.

This dominance condition is necessary but not sufficient for bistability. Writing the quadratic as $A \rho^2 + B \rho + C = 0$ with $A = \lambda_2 \langle k_2 \rangle$, $B = \lambda_1 \langle k_1 \rangle - \lambda_2 \langle k_2 \rangle$, and $C = \mu - \lambda_1 \langle k_1 \rangle$, the product of the two roots equals $C / A$. Because $A = \lambda_2 \langle k_2 \rangle > 0$, both roots are positive, giving a genuine coexisting pair $\{\rho_-^*, \rho_+^*\}$, only when $C > 0$, that is:

$R_1$ is the pairwise process's own reproduction number, and this second condition states that the pairwise contagion must be sub-critical on its own. It is the same second condition Iacopini et al. give for the coexistence of a healthy and an endemic state, and it follows from this paper's own quadratic exactly as it does from theirs. When $R_1 \ge 1$ instead, $C \le 0$, the product of roots is non-positive, and the trivial state $\rho_0^* = 0$ is already unstable under pairwise infection alone: the classical pairwise model at those parameters predicts an epidemic by itself, so there is no sub-critical baseline for a separate higher-order jump to depart from, and the two conditions, $\lambda_2 \langle k_2 \rangle > \lambda_1 \langle k_1 \rangle$ and $R_1 < 1$, together with $\Delta \ge 0$, must all hold for the saddle-node bifurcation to produce the coexisting pair of stable states.

Operational Implication: In an air-gapped facility, the network appears entirely safe and uninfected ($\rho = 0$). However, if a maintenance campaign introduces a critical density of simultaneous exposures exceeding the unstable branch threshold $\rho_-^*$:

the system undergoes an explosive jump, transitioning instantaneously from $0\%$ to $> 85\%$ infection across all air-gapped safety controllers. Furthermore, because the backward transition follows a distinct hysteresis threshold, restoring the air-gap requires reducing infection rates far below the initial entry threshold.

4. Hypergraph Percolation Thresholds & Transversal Immunization#

To defend air-gapped critical networks against explosive simplicial contagion, security architectures cannot rely on traditional node-degree centrality (which only counts dyadic connections). Defense requires identifying and severing the hypergraph transversal.

4.1 Hypergraph Percolation Threshold Formulation#

Let the hypergraph undergo random bond percolation wherein hyperedges $e \in \mathcal{E}$ are occupied with probability $p \in [0, 1]$. We construct the bipartite representation graph $B = (V, \mathcal{E}, E_B)$ where an edge $(v, e) \in E_B$ exists if and only if $v \in e$.

Let $G_0(z)$ and $G_1(z)$ denote the probability generating functions for node hyperdegree distributions, and let $F_0(z)$ and $F_1(z)$ denote the generating functions for hyperedge size distributions. The critical percolation threshold $p_c$ at which a giant connected hypercomponent emerges satisfies:

When the average hyperedge size $\langle |e| \rangle$ increases due to multi-port maintenance tools, $F_1'(1)$ surges dramatically, causing $p_c \to 0$. In physical terms: as maintenance tools bridge more devices simultaneously, the air-gap becomes exponentially easier to penetrate, requiring only a fraction of the attacker effort necessary for pairwise networks.

4.2 Minimum Weight Hypergraph Transversal Algorithm#

A hypergraph transversal (or hitting set) $\mathcal{T} \subseteq V$ is a subset of vertices that intersects every hyperedge in $\mathcal{E}$:

By sanitizing, isolating, or cryptographically interlocking the vertices in $\mathcal{T}$, every higher-order interaction bridge is monitored, preventing explosive percolation.

Finding the minimum weight transversal is formulated as the Integer Linear Program (ILP):

where $c_i$ represents the operational cost of quarantining asset $v_i$.

Because ILP is NP-hard, we deploy a modified Chvátal greedy approximation with logarithmic guarantee $\mathcal{O}(\ln(\Delta_V))$, where $\Delta_V = \max_{v \in V} |\{e \in \mathcal{E} : v \in e\}|$ is the maximum vertex hyperdegree. Because the transversal problem covers hyperedges using vertices, the greedy set-cover guarantee applies to the dual formulation in which each vertex "covers" the set of hyperedges it belongs to, so it is bounded by the largest such set, the maximum vertex hyperdegree, and not by the size of the largest hyperedge:

1. Initialize $\mathcal{T} \leftarrow \emptyset$, active hyperedge set $\mathcal{E}_{\text{act}} \leftarrow \mathcal{E}$.
2. At each iteration, select vertex $v^* \in V$ that maximizes the ratio of newly covered hyperedges to vertex operational cost: $$v^* = \arg\max_{v \in V} \frac{|\{ e \in \mathcal{E}_{\text{act}} : v \in e \}|}{c_v}$$
3. Set $\mathcal{T} \leftarrow \mathcal{T} \cup \{v^*\}$ and update $\mathcal{E}_{\text{act}} \leftarrow \mathcal{E}_{\text{act}} \setminus \{ e : v^* \in e \}$.
4. Terminate when $\mathcal{E}_{\text{act}} = \emptyset$.

5. Empirical Case Study: Cryogenic LNG Fractionation Facility#

To quantify the mathematical divergence between classical pairwise models and simplicial contagion, the Eigenia Research team modeled the safety-critical air-gapped infrastructure of a major Liquefied Natural Gas (LNG) Liquefaction Facility (three 4.5 MTPA trains).

5.1 System Topology Profile#

• Physical Assets ($|V| = 1{,}480$):
  • 120 Triconex Triple Modular Redundant (TMR) Safety Instrumented Systems (Level 1).
  • 480 Distributed Control System (DCS) Foxboro I/A series controllers (Level 1).
  • 640 Remote I/O field termination units (Level 0/1).
  • 180 Local touch-panel operator consoles and engineering HMIs (Level 2).
  • 60 Transient maintenance assets (35 Field laptops, 15 HART calibrators, 10 optical USB flash tools).
• Higher-Order Structures:
  • 3,120 Pairwise links ($1$-simplices, internal dedicated serial conduits).
  • 840 Triadic maintenance interactions ($2$-simplices, multi-device field sessions).
  • 140 High-order hyperedges ($|e| \ge 4$, multi-drop calibration runs during major plant overhaul).

5.2 Bistability Recomputation at the Corrected Operating Point#

A stealth malware payload (analogous to Triton / HatMan) enters the facility via a compromised contractor maintenance laptop. The mean-field equations of Section 3 are evaluated at the following infection parameters, chosen so that the pairwise process is sub-critical on its own while the higher-order coupling satisfies the dominance condition of Section 3.2, the regime the theory of this paper is actually about:

From the topology of Section 5.1, the mean pairwise and triadic degrees are unchanged from their defining sums:

The classical pairwise threshold, from Section 3's own $\lambda_{1,c} = \mu / \langle k_1 \rangle$, is unaffected by $\lambda_2$:

and the chosen operating rate $\lambda_1 = 0.003$ sits below it, giving a rescaled pairwise reproduction number

so the restored sub-criticality condition of Section 3.2 holds: the pairwise process is sub-critical on its own.

The higher-order coupling is $\lambda_2 \langle k_2 \rangle = 0.150 \times 1.7027 = 0.2554$, which exceeds $\lambda_1 \langle k_1 \rangle = 0.01265$, satisfying the dominance condition, and also exceeds $4\mu = 0.080$, the bound Iacopini et al. give for bistability in the pure-simplicial limit $\lambda_1 \to 0$. With both restored conditions holding, the quadratic's coefficients are

so the two non-trivial roots are real, and because $C > 0$ they are both positive:

As demonstrated in the recomputation above, the classical pairwise model, evaluated in isolation at $\lambda_1 = 0.003 < \lambda_{1,c} = 0.004744$, correctly reports a sub-critical, self-extinguishing process: $\rho = 0$ is its only equilibrium. That report is not wrong; it is incomplete. The Eigenia simplicial model, evaluated at the same pairwise rate plus the triadic rate $\lambda_2 = 0.150$, finds a second, coexisting stable equilibrium at $\rho_+^* = 91.92\%$, separated from the disease-free state by an unstable threshold at $\rho_-^* = 3.13\%$. A maintenance campaign that pushes the simultaneously-exposed fraction of the network above that $3.13\%$ threshold, for instance a burst of multi-device field sessions during a plant overhaul, carries the system past the unstable branch and into the explosive branch, even though the pairwise-only process was never close to its own threshold. This is the coupling the theory of this paper describes: a classical model that is locally correct and globally blind to the bistable state the triadic term opens up alongside it.

Applying the Hypergraph Transversal Immunization algorithm of Section 4.2 to the transient maintenance assets that carry the network's 2-simplices removes their contribution to $\langle k_2 \rangle$. Once enough of these hyperedges are cut that $\lambda_2 \langle k_2 \rangle$ falls back below the dominance threshold $\lambda_1 \langle k_1 \rangle$, the constant term of the quadratic is again positive under the restored condition of Section 3.2, the higher-order equilibrium disappears, and $\rho = 0$ becomes the only remaining stable state: the sub-critical pairwise regime the network was in before the maintenance campaign began.

6. Operational Defense & Air-Gap Topology Surgery#

To prevent higher-order simplicial contagion in sovereign industrial enclaves, operators must implement operational air-gap topology surgery:

1. Elimination of Multi-Controller Maintenance Bridges: Procedural enforcement prohibiting any physical laptop or diagnostic unit from interfacing with more than one Purdue Level 1 safety controller within a 24-hour quarantine window. This operationally restricts the maximum simplex dimension to $\dim(\sigma) = 1$, mathematically eliminating the $\lambda_2$ non-linear term.
2. Cryptographic Attestation Diodes for Maintenance Media: Requiring all portable calibration and diagnostic tools to execute hardware-attested cryptographic sanitization (TPM 2.0 / OCP Caliptra root-of-trust quote) between successive controller connections.
3. Out-of-Band Hardware Disconnectors: Programmable physical interlocks that sever electrical serial conduits automatically upon termination of diagnostic sessions, ensuring dynamic hyperedges decay instantaneously ($\tau_{\text{hyper}} \to 0$).

7. Conclusion#

Air-gaps provide a false sense of sovereign operational immunity when evaluated through the obsolete lens of pairwise graph theory. By demonstrating that physical maintenance workflows generate higher-order abstract simplicial complexes and uniform hyperedges, this research uncovers the true mechanism of air-gap failure: explosive, first-order simplicial percolation.

By deploying topological hypergraph analysis, industrial operators can:

1. Predict non-linear catastrophic contagion thresholds that remain completely invisible to pairwise models.
2. Identify the exact minimal transversal subset of transient maintenance assets that form explosive bridges.
3. Implement mathematically guaranteed topological surgery to maintain air-gapped critical infrastructure in an uncompromised, resilient state.

8. References#

1. Iacopini, I., Petri, G., Barrat, A., & Latora, V. (2019). Simplicial models of social contagion. Nature Communications, 10(1), 2485.
2. Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020). Networks beyond pairwise interactions: Structure and dynamical processes. Physics Reports, 874, 1-92.
3. Boccaletti, S., De Lellis, P., del Genio, C. I., Alfaro-Bittner, K., Criado, R., Jalan, S., & Romance, M. (2023). The structure and dynamics of higher-order networks: A review. Physics Reports, 1018, 1-64.
4. Berge, C. (1989). Hypergraphs: Combinatorics of Finite Sets. North-Holland Mathematical Library, Elsevier.
5. Hatcher, A. (2002). Algebraic Topology. Cambridge University Press.
6. Chvátal, V. (1979). A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 233-235.
7. Newman, M. E. J. (2002). Spread of epidemic disease on networks. Physical Review E, 66(1), 016128.
8. International Electrotechnical Commission. (2020). IEC 62443-3-2: Security for industrial automation and control systems - Security risk assessment for system design. IEC.
9. Falliere, N., Murchu, L. O., & Chien, E. (2011). W32.Stuxnet Dossier. Symantec Security Response.
10. Jovel, E., & McKenney, J. (2026). Higher-order topological attack surfaces in industrial cyber-physical infrastructure. Eigenia Working Group Monographs, WG-07-TM.
11. Bodó, Á., Katona, G. Y., & Simon, P. L. (2016). SIS epidemic propagation on hypergraphs. Bulletin of Mathematical Biology, 78(4), 713-735.