In their work, computer security people rely terms such as: “vulnerability chaining”, “horizontal/lateral movement”, “escalation”, etc. These terms describe events and techniuqes involved in a multi-step computer system breach. If there’s some satisfaction in using those terms, it’s because they refer to the processes’ internal structure. This internal structure of the process attackers follow is very intuitive, even if it isn’t noted down explicitly.

We look at what this underlying structure looks like. We identify two “axioms”: (1) the process is cumulative in nature and (2) the attacker’s capability undergoes sudden changes. Given that we’re modeling a real-world process using Direct Acyclic Graphs (DAGs), we’re in a position to say a few words on DAGs in general.

What mathematical description best describes this process? Think before reading, how would you represent cumulativeness and sudden changes over time with all details removed.

1. Attackers don’t play Mahjong

In the Mahjong Solitaire game, the goal is to identify duplicate pieces on the board, after which they’re removed. The process is repeated until there are no pieces on the board. Mahjong can be seen as trimming a DAG. A leaf node of a DAG is removed which “frees up” other nodes, allowing their removal in one of the next steps.

One could consider that a privilege escalation process encountered in computer system hacking follows this pattern. After all, it is true that the process is tedious and requires lots attention, so that basic thing does check out. One may also consider the hacking process to involve acquiring “gadgets”, or “capabilities”, similar to piece in the game.

However, Mohjang Solitaire follows a certain steady pace; unlocking Mahjong pieces does not include rapid state changes. This is where the Mahjong Solitaire analogy with the computer hacking fails. As mentioned, the privilege escalation process follows a specific dynamic, not followed by some other processes out there. It can be described as such:

  • It’s usually cumulative in terms of attacker’s capability
  • it includes sudden, dramatic changes

2. Rapid privilege escalation

The first thing that comes to mind when representing a process with rapid changes is a transformation, over some state. The mapping is monotone, as in bits only activate, they do not deactivate. Consider the following state trail:

time         state
0     -------------------- 
1     x-------------------
2     x-------------------
3     xx------------------
4     xx------------------
5     xx------------------
6     xx------------------
7     xx--------x---------
8     xxxxxxxxxxx---------
9     xxxxxxxxxxx--------x
10    xxxxxxxxxxxxxxxxxxxx
   ...

The “avalanche” effect is the rule that a flip in bit k results in bit flips in all bits j < k. Avalanche is present in steps 8 and 10. A computer hack involves capabilities; for example the capability to authenticate as a system user or the capability to read an arbitrary file on disk. For a given system, we’re looking at a set of capabilities:

p1, p2, p3, ... p_n

Bit position k corresponds to p_k and - means that the actor does not yet posess the capability. An attack on say a Windows network progresses with the attacker’s capability of running commands in a Docker container (step 1 on the picture), then expanding the capability to running code on a host in the network (2), access to internal services keys repository (step 7) and finally step 10 establishing control at the domain controller of the network, which allows access to all capabilities.

3. Inside the Boolean hypercube

The problem with the previous section is that it requires a p_i => p_i-1 for all p_i. This does not correspond to reality; there may be multiple independent paths to the full capability or privilege set. To represent this, we use a “power set” (a set of all subsets) of the set of capabilities.

The power set or Boolean cube graph

The power set forms a graph in which movement from the bottom towards the top of the graph signifies privilege escalation. For example, a file read on the local system may provide the attacker the ability to read a configuration file and authenticate to related database; this is represented as movement from a to {a,b}.

A general note about graphs: each movement the power-set graph is “coordinate-wise” in the sense that from every node it’s possible to “choose” a capability and add it to the set. This is is why Boolean hyper-cubes are a good alternative way of representing power sets. Capabilities are identified with positions in an n-tuple and from each capability set. It’s possible to independently “unlock” or “lock” any capability from any node in the graph.

3. Deleting impossible edges

It should be noted that the possibility of privilege escalation is probabilstic in nature. For example, an XSS payload may or may not execute. A phishing attempt succeeds with a certian probability. An ASLR bypass such as a sprayed heap may yield to a desired outcome, or may not. An LLM may or may not identify an exploit that allows escalation.

That also means that some privilege escalations are known to be impossible, or simply don’t make any sense in reality. A pair of capabilities may refer to completely independent system parts. In practice, these routes will simply be uninhabited over different attack attempts.

Such edges can be removed from the picture. You could say this simplifies the graph, but you could also say deleted edges make the graph more complicated. The latter is probably true, as the graph is not the Boolean hypercube anymore and dependencies are introduced. The corresponding monotone Boolean function is more unpredictable.

4. Capability merge supernodes

Our previous partitive set graph fails to capture the “avalanche” property. A full (or large) set of capabilities is often times gained suddenly, in one passage. Paradoxically, in order to gain a single capability (such as, a read from a database), often times, the attacker gains the full set of capabilities.

For that, we add some back-propagations to the system. A capability “back-propagates” a number of other capabilities. For example, running code on the host system implies access to all application users, administrators as well as access to secrets in configuration files (three capabilities). This is represented as a => b, a => c, a => d in the picture above.

In the partitive set model, back-propagation dictates that nodes should be merged (see the notion of Strongly Connectected Component (SCC) quotient graph). Since a => c, d, each node with just a and any subset of {c, d} is merged into one node. Another merge that follows from this implication is a node that contains both a, b and any subset of {c, d}.

Merging nodes to get a more accurate graph

If the back-propagation is of the form X, a => B, where X and B are capability subsets, each subset of X will correpsond to a node with all {a} U B elements. Examples of super node in practice would be code execution, master key extraction

5. Capabilities are not limited to network vantage points

The neat thing about this approach is that it’s versatile. Traditionally, computer security deals with notions such as “user access to host X”, “foothold in internal network Y”. However, “capability” is very expressive and it also includes for example the following:

  • The ability to leak i-th bit from j-th round of a cryptographic primitive vs. the ability to extract a bit of a cryptographic key
  • Ability to run code in a browser sandbox on a mobile device vs. ability to run code in userland or kernel
  • Knowledge of exploitation of certain platform

The choice of the initial set of capabilities is always subjective; there’s no single “correct” choice. For example, it’s always possible for capabilities to be more coarse or detailed. Some capabilities may be completely omitted from the system, which impacts how the graph looks like.

6. Summary

We started with Boolean hypercubes over a set of capabilities {c1, .. cn}. We then “edited” the hypercube, in order to add information specific to a given system. “Capabilities” are not limited to computer system or network access, they encode “capability as such”, for example “the ability to leak bit N from round X of a cryptographic protocol run”.

A threat modeling process that humans (or LLMs) may run in practice (independent of the method shown in this blog post) roughly follows the structure shown here. How succesful this process is will be determined by how realistic is the initial chosen set of capabilities is and how realistic the branches and trails considered turn out to be.

Some general notes on DAGs and partial orders:

  • The interesting aspect here is that the process is “cumulative”, which leads to partial order graphs, which in turn leads us to Boolean hypercubes
  • The Boolean hypercube DAG allows “choosing” movements at each level, which is a strong DAG restriction
  • It is also a sort of “blank” DAG, to which information is added, to have a system containing actual information
  • Specifically, DAG complexity increases when edges are removed (or added at unexpected locations), as that removes the independence assumption
  • Any graph can be converted to a DAG (with information loss) where nodes that participate in cycles are collapsed into single nodes (see SCC quotient graphs)
  • As such, every graph encodes at least some amount of “time” in itself
  • Order theory is a theory which studies partial orders, it overlaps with basic category theory (see e.g. this book).

Thank you for reading!