Thinking in Graphs for Defenders

Bringing clarity to the "Defenders think in lists while Attackers think in graphs” adage

Anyone who has been working in cybersecurity for a while will have heard the adage “Defenders think in lists while Attackers think in graphs” or something similar. This is likely accompanied by a slight smirk and no followup explanation of what that really means.

Working as both an offensive and defensive security engineer I have thought a lot about this and in this blog post I hope to scratch the surface of the implications of this saying and why it’s consequential.

Attacker Networks.

What everyone has always left out in that saying is how “attackers think in graphs”. It may seem obvious that they are operating on the same network as you and so they must be operating on the same graph. This is not quite the case because the graph the attacker cares about is a subgraph of our network.

While our network is rich in complexity consisting of a diverse schema that represent the entire business, attackers see our networks as a simpler graph of assets (nodes) and capabilities (edges). Every asset an attacker is able to accumulate, comes with a series of capabilities.

These capabilities can include making connections to certain assets or authenticating to others. In all scenarios the attacker starts with only their asset or the source of the attack. The goal is to accumulate the capabilities through the compromise of assets in order to access the asset(s) they want.

This can be thought of an attacker building their own network within your network. The attacker is trying to expand their possibility space to a point that that it contains the action they want (i.e. access to sensitive data).

Attack Chains are Markov Chains

We have established that the attacker’s primary goal is to accumulate assets and associated capabilities in order to form an attack chain to reach the target. This attack chain can be characterized mathematically as a Markov chain.

A Markov chain is a simple way to describe how a system moves from one state to another in steps over time, with each move depending only on what the system looks like now (and not its entire history).

A simple example is shown below

Starting with the attacker, there are edges representing a capability from each node with probabilities determining their chance of success. Think of these capabilities as “Send Email”,“SSH Access”, or“Administrative Application Access”. The attacker takes an action at each interval of time and attempts to use the capabilities (edges) to access the asset.

The above example is overly simplistic as it assumes the attacker only has the capabilities present on the asset at a given time t. Thus, the probabilities remain static as the attacker moves through the assets.

In reality, the attacker has the union of all capabilities accumulated through the chain (i.e. compromised credentials on one system can be used on systems later in the chain). This means for each node accessed, the state of the attacker changes, which in turn changes the probability of access to the next node.

For example, at time t, an attacker X_t-1 with capabilities C_Xt-1 may move to asset A with capabilities C_A. This means that the current state attacker, X_{t ,}now has the union of the initial capabilities and the capabilities of asset A ( C_Xt = C_Xt-1 ∪ C_A).

Attacker transition from Asset A to Asset B

Attacker transition from Asset B to Asset C

In our example, the calculation for an attacker moving from asset B to asset C looks like this.

C_B→C = .3

C_A→C = .01

C_X→C = C_B→C ∪ C_A→C

If, C_B→C and C_A→C , are distinct capabilities then:

P(C_X→C) = P( C_B→C) + P(C_A→C)

P(C_X→C) = .31

Conclusion

As defenders, we need to start thinking about our defense strategies in the context of the graph of assets and capabilities and use the properties of Markov chains to our advantage. This is especially useful when we consider that we cannot properly estimate probability, but we can use the fundamentals of Markov chains to service knowledge about the properties of the probability such as relative magnitudes. I plan to go into this in future posts as well as how this fits into machine learning going forward.

Have a great weekend.