The state enumeration trap in Attack Graphs

Here are two numbers from the same system, measured over the same period.

Computing the attack graph for a tenant can take anywhere from minutes to hours, depending on the size and structure of the environment. Reading an individual attack path back out is consistently fast, with latency staying in the millisecond range even across the largest environments.

That gap is the whole design.

I got it wrong the first time, in a way worth describing, because the wrong version is the one almost everyone builds first.

The graph, and what it is for

I work on a graph that models cloud infrastructure, Kubernetes, identity
providers, source control, CI/CD and SaaS as one connected structure (cf. cartography.dev). On some customers Iit holds more than 15 million nodes and 65 million edges. It changes all day, because people deploy, grant, revoke and integrate all day.

The question it exists to answer is whether an attacker who gets in somewhere can reach something that matters. Not in theory. On this infrastructure, right now.

What I built first

The first engine modeled attacker states. A state is what an attacker holds at a point in time: credentials, sessions, positions, assets. A transition takes one state and produces the next.

That design is the obvious one, because it is how everyone tells the story of a breach. Someone phished a developer, the developer had a token, the token pushed to a repo, the repo deployed to a cluster, the cluster had a role. States and transitions, in order. You draw it that way on a whiteboard, so you build it that way.

It works, and then it stops working. The way it stops is the interesting part,
because the size of the graph is not what breaks it.

Where it breaks

Take an attacker with code execution on one workload. From there, in a normal setup, they may be able to:

• read the pod’s service account token,
• read a static credential mounted from config,
• write to the pipeline that deploys the workload,
• assume the cloud role attached to the node.

Four capabilities. None of them is hard to model. None of them needs the others first. That last point is what costs money: they are independent, so an attacker can hold any subset.

A state based engine does not have four things to reason about here. It has
sixteen. Every subset is a distinct state, and the subsets are not interchangeable, because a transition can require two capabilities at once. So the engine cannot collapse them, and it enumerates.

With n independent capabilities in one blast radius you get 2^n states. Ten of them around a single workload is 1024. Adding one independent capability doubles the state space.

That is the trap in the title. It does not track the size of your infrastructure.
It tracks how many attacker capabilities are reachable independently of each other, which is a property of how permissions are shaped, not of how many resources you own.

I rediscovered a 2002 result the expensive way

This trap has a bibliography, and I did not read it before walking into it.

Sheyner, Haines, Jha, Lippmann and Wing generated attack graphs with a model checker in 2002 and encountered the same fundamental state-space problem described above. The same year, Ammann, Wijesekera and Kaushik published Scalable, Graph-Based Network Vulnerability Analysis, showing how monotonicity can avoid explicit state enumeration. Three years later, Ou, Govindavajhala and Appel built MulVAL on Datalog, using a logical attack graph where nodes are facts and edges represent derivations.

I found the same wall and then the same way around it, twenty years later, with a much larger bill.

So the model below is not new. What is new is where it has to run. Those papers assumed a network of hosts with vulnerabilities, described by one scanner, sitting still. My input is AWS, GCP, Azure, Entra, Okta, Kubernetes, GitHub, GitLab, OpenAI, Spacelift, Tailscale and a set of detection findings, each with its own permission model, and the graph changes while the analysis runs. Applying monotone derivation there raises two problems those papers did not have: keeping the rule set finite when every vendor invents new primitives, and being honest about what monotonicity costs in an environment where credentials rotate.

Capabilities as facts

The change is small to describe. Stop representing what an attacker holds as a state. Start representing what an attacker can do as independent facts attached to graph nodes.

There are several capabilities in the engine: CAN_ACCESS, CAN_READ, CAN_WRITE, CAN_DELETE, CAN_EXEC, CAN_USE, and CAN_ADMIN. A capability represents an operation an attacker can perform against a node in the graph.

Rules derive new capabilities from existing ones. Conceptually, a rule looks like this:

internet_entry_point = AttackPathTransition(
    kind=TransitionType.INET_EXPOSURE,
    granted_capacities=[
        AttackerCapacity("resource", "CloudResource", Capacity.CAN_ACCESS)
    ],
    required_capacities=[],
    confidence=Confidence.HIGH,
    difficulty=Difficulty.TRIVIAL,
    query="""
        MATCH (public:PublicEndpoint)-[:EXPOSES]->(resource:CloudResource)
        WHERE public.internet_exposed = true
        RETURN public, resource
    """
)

An empty required_capacities makes the transition an entry point: the granted capability starts at depth 0. Every subsequent rule declares both the capabilities it requires and the capabilities it grants. Each derived fact records the prerequisites that led to it, and those prerequisites were established earlier in the derivation.

The important part is that the engine does not simply enumerate vulnerabilities. It composes these capability transitions into an attack graph, allowing independently modeled permissions and exposures to form multi-step attack paths.

Then you run all the rules over the graph until nothing new appears. Forward propagation to a fixpoint, which is what a bottom up Datalog engine does. The implementation also has explicit convergence guards, so pathological rule interactions fail loudly rather than running indefinitely.

The difference in growth is the point. A state model grows by combination: every new capability multiplies with the ones already there, because the engine has to consider holding them together. A capability model grows by derivation: once a fact exists it is just there, available to any rule that mentions it, and it never needs to be paired with anything to be stored. Four independent capabilities on that workload are four facts, not sixteen states. Ten are ten facts, not 1,024 states.

The two numbers from the top

This is where the opening comes from.

The fixpoint is expensive, but its cost is highly uneven. The compute phase dominates the pipeline and can vary substantially depending on the size and complexity of the graph being processed. On smaller graphs, refreshes complete in minutes; on the largest ones, they can take hours. The important point is that compute accounts for the overwhelming majority of the pipeline’s runtime, while the remaining stages are comparatively negligible.

Reading a path back is a very different problem. Once the fixpoint has been computed, retrieving an attack path through the API is consistently fast, and aggregation operations such as listing and scoring remain in the millisecond range. More importantly, read latency does not exhibit the same growth pattern as compute time.

Get jychp’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This distinction matters. If read cost scaled directly with graph size, we would expect the latency distribution for path retrieval to inherit the long tail observed during computation. It does not.

That is what choosing this representation buys you. The cost moves from query time to propagation time, where it is paid during a refresh rather than repeatedly for every question.

What “acyclic” actually means here

I have seen this claim stated loosely, including by me, and it is worth getting right because it is the first thing a reviewer will poke.

The rule dependency graph can absolutely contain cycles. That is not inherently a problem. The important property is that derivation is monotone: the engine only adds facts and never retracts them. Even when rules depend on each other indirectly, the computation continues until no new facts can be derived, at which point it reaches a fixpoint.

What is acyclic is the derivation trace.

Each derived fact records the prerequisites that produced it. Those prerequisites have strictly smaller derivation depth, so following derivation edges always moves toward a lower depth. The trace therefore cannot contain a cycle.

That trace is what a user sees as an attack path, and it forms a DAG by construction.

Two graphs, two claims. The rule dependency graph describes how rules can interact; the derivation graph describes how a particular result was actually reached. Conflating the two is how you end up promising a property the system does not actually guarantee.

What monotonicity costs

The assumption that makes all of this work is false in the real world. Pretending otherwise would be dishonest, and the limitations are fundamental.

Credentials expire and rotate. A monotone model effectively treats a capability once obtained as remaining available. Real systems do not behave that way: sessions expire, credentials rotate, and access can be revoked. We keep the assumption because modeling every temporal state would bring back the state-space explosion we are trying to avoid. The resulting output should therefore be interpreted as “was reachable within the modeled window”, rather than “is reachable right now”.

Actions are free. The model does not account for detection, side effects, or actions that consume or invalidate access. Some real-world actions change the environment in ways that affect subsequent reachability. Monotone reasoning cannot represent those transitions, so some paths may appear cleaner or more feasible than they would be in an actual execution.

Joint realizability is not guaranteed. The fixpoint establishes that individual capabilities are derivable. It does not necessarily establish that a single attacker can hold every prerequisite simultaneously, because different derivations may depend on conditions that are mutually exclusive.

This is a fundamental trade-off of dependency-based attack graphs. Avoiding explicit state enumeration makes the problem tractable at large scale, but it means that some reported paths may be individually valid without being jointly executable in a single concrete attack.

The cost does not vanish, it moves

Escaping (2^n) does not make the engine cheap. It relocates the expensive part into individual rules, and that failure mode is the one I spend most of my time on now.

Three examples illustrate the problem.

One rule materializing a Cartesian product. A lateral-movement rule effectively compared every eligible source with every eligible target within a shared scope, producing a large intermediate result before deduplication. A single unusually large scope was enough to generate more capabilities than a substantial fraction of the rest of the graph combined.

The fix was to reduce the source side before the fan-out and constrain the target side to resources that could actually participate in the transition. The important lesson is that the asymptotic behavior of a rule matters independently of the size of the overall graph.

One dense origin. In another case, a highly privileged origin could reach a very large number of identities. Expressed as a single transition, that created a dense set of capabilities, and path reconstruction subsequently had to consider a huge number of distinct derivations from the same origin.

The fix was to avoid modeling that administrative relationship as a standalone transition and instead compose it into the rules that actually consume the resulting privilege. Most of the capabilities produced by the original representation were dead ends that would eventually be pruned anyway.

Facts that outlive the rule that made them. Incremental cleanup introduces another class of failure. If derived facts are associated too tightly with the identity of the rule that produced them, changing or replacing a rule can leave previously materialized facts behind without a corresponding producer.

Those orphaned facts are particularly problematic because they do not necessarily look broken locally. They can persist in the graph, consume memory, and participate in subsequent processing even though their original derivation is no longer part of the active rule set.

None of these problems are state explosion. They are cardinality problems inside individual rules. That is why measuring per-rule cost is just as important as measuring the overall fixpoint.

In practice, most rules are cheap. A small number of pathological transitions dominate the long tail and account for a disproportionate share of total compute. Finding those rules, understanding why their intermediate cardinality grows, and changing their representation is a large part of making the engine scale.

Finite rules, infinite contexts

The last piece is what keeps the rule set from exploding the way the state space did.

If rules are written directly against provider-specific objects, every new provider creates pressure for another set of rules. In that model, I have simply traded state explosion for vendor explosion.

Instead, rules are written against an ontology: identities, resources, permissions, trust relationships, execution contexts, and other concepts that remain relatively stable across infrastructure providers. I built that abstraction layer in Cartography before this reasoning engine existed, for unrelated reasons, and wrote about it at the time. It turned out to be a prerequisite.

The result is that infrastructure can keep growing without requiring the rule set to grow at the same rate. Attacker behavior is comparatively stable; infrastructure is not. Vendors continuously introduce new services and abstractions, but most of those are new ways of exposing facts that existing attacker behaviors already consume.

The onboarding pattern reflects that. New providers generally require only a small number of additional transitions because the underlying attacker behaviors are already represented by the ontology. The integration work is primarily about mapping provider-specific facts onto concepts the existing rules understand.

The same pattern appears in the rule catalog itself. The rule set has grown substantially as the engine matured, but growth has not been proportional to the number of integrations or infrastructure types being modeled. Rules are also removed and consolidated as the model becomes more expressive.

I want to be careful about interpreting the growth curve. The observation window is still relatively short, and a recent flattening is not enough to call the catalog stable.

The signal I trust more is the combination of additions and removals. Rules are increasingly being consolidated or deleted as more general rules subsume specialized ones. The set is starting to densify rather than simply grow, which is the behavior you want from a model that is intended to remain finite while the infrastructure it describes does not.

The part that does not scale

The initial rule set was written by hand.

That is the honest state of how the system started. The reasoning model stopped growing with the environment, but the bottleneck initially moved to the human authoring the model. A new attacker technique meant someone had to understand the behavior, express it against the ontology, and make sure the resulting rule composed correctly with everything that already existed.

That process does not scale indefinitely. It just fails more slowly, and less visibly.

The next article is about what happened when I started putting an agent on that job, and why my first attempt produced rules that were technically correct but practically useless.