✓ Human-authored analysis; AI used for formatting and proofreading.
Two Questions, One Graph
Cloud security scanners answer: does a path exist from the internet to the crown jewels? Run a reachability algorithm — BFS, DFS, or a Datalog transitive closure over the graph of permissions, network routes, and trust relationships. If a path exists, emit a finding. Scanner does it. It's graph traversal, and it's solved.
The harder question that almost nobody answers is: what is the smallest set of changes that eliminates all paths?
Finding paths is cheap. There might be twelve paths from the internet to a production database, through different combinations of public subnets, overpermissioned IAM roles, VPC peering connections, and misconfigured security groups. A scanner that finds all twelve produces twelve findings. The engineer reads twelve findings and has to figure out, manually, which three changes would eliminate all twelve paths simultaneously. That reasoning — which edges to cut, where cutting one edge collapses multiple paths, where the graph has structural bottlenecks is not done by a scanner.
This is the minimum cut problem. Ford and Fulkerson solved it in 1956.
Max-Flow Min-Cut, Stripped Down
The Max-Flow Min-Cut Theorem says: in a flow network with a source and a sink, the maximum flow from source to sink equals the total capacity of the minimum cut. The smallest set of edges when removed disconnects the source from the sink.
In a network engineering context, source is the sender, sink is the receiver, edges are links with bandwidth capacity, and the theorem tells you the bottleneck throughput. In cloud security, the mapping is different and the theorem tells you something more useful.
Source. The untrusted origin. The public internet, a compromised employee workstation, a stolen credential used from an external account — wherever the attacker starts.
Sink. The crown jewels. An S3 bucket with PII, a production RDS database, a Secrets Manager secret, a KMS key that encrypts everything else. In a real environment there are hundreds or thousands of sensitive resources. The standard technique is the super-sink: a virtual node connected to every crown jewel by an edge with infinite capacity. Computing the min-cut from source to super-sink produces the minimum set of changes that disconnects the attacker from the entire high-value asset class simultaneously, not just from one resource. This is a single computation, not one per target. Cutting the path to the super-sink solves the remediation for every sensitive resource at once. The same technique works on the source side: a super-source connected to every entry point (public IPs, external trust relationships, compromised credential origins) computes the min-cut across all attack origins simultaneously.
Edges. The connections between resources that an attacker can traverse. A security group rule permitting ingress. An IAM policy granting s3:GetObject. A VPC peering connection with an overly broad route. A trust policy allowing role assumption from an external account. An event source mapping that triggers a Lambda function. Each edge is a step in the attack path.
The graph is directed. Edge direction matters. An IAM policy granting s3:GetObject is a unidirectional edge: it lets the principal read from the bucket but says nothing about traffic flowing the other way. A security group ingress rule on port 443 is also unidirectional: it permits inbound connections but the response traffic flows on the established connection, not through a separate edge. Max-Flow Min-Cut works correctly on directed graphs, but the implementation requires careful direction modeling because some AWS constructs look bidirectional. VPC peering is the primary example: a peering connection permits traffic in both directions, but the route table entries that use it are directional (subnet A routes to subnet B's CIDR through the peering). Model VPC peering as two directed edges (one per direction), each governed by its own route table entry and security group. The peering connection is the physical link; the routes are the directed edges in the graph. Getting the direction wrong inflates the path count. The algorithm finds paths that traffic can't traverse.
Capacity. In network engineering, capacity is measured in megabits per second. In cloud security, it's almost always binary. The permission exists or it doesn't. The security group rule allows the traffic or it doesn't. The trust policy permits assumption or it doesn't. A path is open (capacity 1) or blocked (capacity 0).
The theorem says: the maximum flow of attack paths from the internet to the database equals the total capacity of the minimum cut. Since capacity is binary, this simplifies to: the number of edge-disjoint attack paths equals the minimum number of edges you need to remove to disconnect the attacker from the data.
That minimum set of edges is the remediation plan.
Why Min-Cut Beats Path Enumeration
A scanner that finds twelve paths gives you twelve findings. You read them and notice that paths 1, 4, 7, and 11 all traverse the same overpermissioned IAM role. Paths 2, 5, and 9 all pass through the same security group rule. Paths 3, 6, 8, 10, and 12 all use the same VPC peering connection. Three changes — scope the role, tighten the security group, remove the peering route — eliminate all twelve paths. But the scanner didn't tell you that. It told you twelve things are broken. You did the graph theory in your head.
The min-cut algorithm does this automatically. It takes the full graph (every resource, every permission, every network route), sets the source (internet) and sink (database), and computes the minimum set of edges when removed disconnects them. The output isn't twelve paths. It's three edges. Those three edges are the remediation plan. The smallest set of changes that eliminates all reachability between the attacker and the target.
This is also why path enumeration scales badly. A complex environment might have hundreds of paths between the internet and a sensitive data store. Enumerating them all is computationally expensive and produces an overwhelming list. The min-cut is small — often three to five edges — regardless of how many paths exist. The remediation plan stays manageable even when the attack surface is enormous.
Menger's Theorem: The Binary Case
Since cloud permissions are almost always binary (the edge exists or it doesn't, with no partial capacity), the operative theorem is often Menger's rather than Ford-Fulkerson. Menger's Theorem states: the maximum number of edge-disjoint paths between two nodes equals the minimum number of edges whose removal disconnects them.
Edge-disjoint means the paths share no edges. If three edge-disjoint paths exist between the internet and the database, the minimum cut must include at least three edges — one from each disjoint path. Cutting two isn't enough because the third path survives intact.
This gives you a lower bound on the remediation effort without computing the full min-cut. Count the edge-disjoint paths and you know the minimum number of changes required. If there are five disjoint paths, five is the floor. No clever combination of three changes can eliminate all five.
For cloud security, Menger's Theorem answers: "how resilient is this attack surface?" A target reachable by one path is fragile — one fix eliminates access. A target reachable by five disjoint paths is robust (from the attacker's perspective). The defender needs at least five changes. The disjoint path count is a severity metric: higher disjoint count means more work to remediate and more ways for the attacker to maintain access.
Nodes Versus Edges
Ford-Fulkerson computes an edge cut: which connections should be severed? In cloud security, you're often looking for a vertex cut: which resource is the bottleneck?
If a single EC2 instance is the only path between the public subnet and the private data subnet, removing that instance disconnects the graph. That's a vertex cut. If a single IAM role is the only identity that bridges two otherwise-separated permission domains, revoking that role disconnects them. Also a vertex cut.
The two formulations are mathematically interchangeable. Any vertex cut problem converts to an edge cut problem by splitting each node into two nodes connected by a single edge. The capacity of that edge represents the cost of removing the resource. After splitting, Ford-Fulkerson computes the answer in edge-cut form, and you translate back to the vertex cut.
In practice, this is the difference between "which security group rule should I remove?" (edge cut) and "which IAM role is the choke point?" (vertex cut). Both are useful. The edge cut tells you the specific remediation. The vertex cut tells you the structural bottleneck. The resource whose compromise would open the most paths.
This is why per-resource scanners miss the compound risk. They evaluate each resource independently (each node in isolation) and can detect that a security group rule is too permissive or an IAM role has wildcard permissions. What they can't detect is that this specific security group rule is the choke point through which all twelve attack paths flow, or that this specific IAM role is the vertex whose removal disconnects the internet from the database. That's graph-level analysis, not node-level analysis. The scanner sees trees. The min-cut sees the forest.
The Weighted Version
Binary capacity (exists or doesn't exist) is the clear case. Real environments are messier. Not all edges are equally easy to exploit or equally easy to remediate.
Assigning weights to edges captures this. Two possible weight schemes, each answering a different question:
Exploitability weights (the attacker's perspective). An unpatched critical CVE on a public-facing instance has a high-capacity edge — easy for the attacker to traverse. An MFA-protected, IP-restricted, session-limited login has a low-capacity edge — hard to traverse. The max-flow computation finds the path of least resistance through the graph. The min-cut identifies where the defender can impose the most friction on the attacker with the fewest changes. This answers: "where do I get the most security gain per unit of effort?"
Remediation cost weights (the defender's perspective). Removing a VPC peering connection might break a production workflow — high remediation cost. Scoping an overpermissioned IAM role might be free — low cost. The min-cut with remediation cost weights finds the cheapest set of changes that disconnects the graph. This answers: "what is the least-disruptive remediation plan that eliminates all attack paths?"
The two weight schemes can be combined. The min-cut with combined weights finds the remediation plan that maximizes security improvement per unit of operational disruption — the economically optimal defense.
The Temporal Dimension
Here's where the min-cut connects to temporal consistency, the subject of the previous article in this series.
A min-cut computation takes a graph as input and produces a set of edges as output. The graph is constructed from a configuration snapshot — the IAM policies, security group rules, VPC routes, and trust relationships captured at a point in time. If the snapshot is temporally inconsistent — different parts captured at different times with configuration changes in between — the graph describes a system state that may never have existed.
Run Ford-Fulkerson on an inconsistent graph and the results are unreliable in three ways:
The ghost path. The scanner sees an IAM permission captured at 14:00 and a security group rule captured at 14:07. Ford-Fulkerson finds a path through both. The min-cut suggests removing the security group rule. But the IAM permission was revoked at 14:04. It doesn't exist at the same time as the security group rule. The path never existed. The remediation targets a choke point for an attack surface that was never real.
The phantom cut. The min-cut identifies three edges to remove. One of them is a VPC route that was already removed at 14:05, between when the source-side and sink-side resources were captured. The remediation plan includes a change that's already been made. The engineer "fixes" something that's already fixed and misses the remaining exposure.
The missing path. A new IAM permission was added at 14:03, after the identity group was captured but before the network group was captured. The identity snapshot doesn't include it. The graph is missing an edge. Ford-Fulkerson computes a min-cut that doesn't account for the new path. The remediation plan has a hole. It addresses the paths the scanner saw but misses the path that appeared mid-collection.
All three are consequences of computing over an inconsistent cut (in the Chandy-Lamport sense) of the distributed system. The configuration snapshot is a cut through the execution history of the cloud infrastructure. If the cut is inconsistent, the graph it produces is fictional, and the min-cut of a fictional graph is a fictional remediation plan.
The fix is the same consistency check described in the Lamport article: verify that no relevant change event falls between the capture times of the snapshot's service groups. If the cut is consistent, the graph is real, and the min-cut is the optimal remediation plan. If the cut is inconsistent, the min-cut computation should be qualified: "this remediation plan is based on a temporally inconsistent graph — re-collect for a consistent analysis."
What This Implies for Tooling
A scanner that enumerates paths is doing BFS/DFS. Useful, but produces a finding list that doesn't aggregate into a remediation plan.
A scanner that computes the min-cut is doing Ford-Fulkerson (or Edmonds-Karp, or push-relabel). It produces a remediation plan directly: the minimum set of changes that disconnects the attacker from the target. The plan is optimal by construction — no smaller set of changes achieves the same disconnection.
A scanner that computes the min-cut and verifies temporal consistency is doing Ford-Fulkerson over a provably consistent graph. The remediation plan is both optimal and trustworthy — it addresses attack paths that exist simultaneously, not paths assembled from observations at different moments.
The computational cost is modest. Ford-Fulkerson on a graph with V vertices and E edges runs in O(VE²) for Edmonds-Karp. A cloud environment with 10,000 resources and 50,000 edges (permissions, routes, trust relationships) is well within reach. The min-cut computation adds seconds, not hours, to the evaluation.
The implementation maps naturally to the fact-export architecture. The configuration snapshot produces a graph of resources (nodes) and permissions/routes/trust (edges). The graph is exported to an engine that computes reachability (Soufflé/Datalog for path enumeration) and min-cut (a flow algorithm). The engine returns both the paths (the findings) and the min-cut (the remediation plan). The temporal consistency layer verifies the graph before the computation begins and qualifies the results if verification fails.
One Question, Not Twelve
The scanner that finds twelve paths produces twelve findings. The engineer reads twelve findings, reasons about shared edges, identifies three choke points, and implements three changes. The reasoning the engineer did — manually, in their head, possibly incorrectly — is a min-cut computation.
The scanner that computes the min-cut produces three changes. The engineer reads three changes and implements them. The reasoning happened in the algorithm, where it's provably correct, instead of in the engineer's head, where it's approximated.
Twelve findings and the hope that the engineer will figure it out. Or three changes and the proof that they're sufficient. The math to get from the first to the second has been available since 1956. Ford and Fulkerson solved it. Menger characterized the lower bound. Chandy and Lamport told us how to verify the graph. The algorithms exist and they're efficient. The missing specification is applying them.
This is the second in a series on formal methods applied to cloud security. The first, "Your Scanner Doesn't Know What Time It Is," covers temporal consistency of configuration snapshots. The tools and examples reference Stave, an open-source cloud security tool (Apache 2.0, early-stage) that exports structured facts for external reasoning engines. The graph theory is general — it applies to any scanner that evaluates reachability across a configuration graph, regardless of which cloud provider or tool you use.
Top comments (0)