Detecting Privilege Escalation with Temporal Braid Groups

This paper proposes using the Burau Lyapunov exponent as an algebraic probe within temporal Cloud permission graphs to distinguish between dispersed and focused risk regimes for automating privilege escalation detection and remediation, demonstrating that non-commutative properties outperform traditional Abelian statistics in identifying these boundaries.

The Gist

Imagine you are the security guard for a massive, futuristic city made entirely of digital permissions. In this city, people (or computer programs) move between different zones, and sometimes they pick up new keys (permissions) that let them open more doors.

The problem is: Just because someone has a lot of keys right now doesn't mean they are dangerous. Some people just shuffle keys back and forth safely. Others are on a one-way escalator, constantly picking up new keys to climb higher and higher, eventually breaking into the "God Mode" room.

This paper introduces a new, super-smart way to tell the difference between a safe shuffler and a dangerous climber, using a concept called "Temporal Braid Groups."

Here is the breakdown in simple terms:

1. The Two Types of "Climbers" (Ratchets)

The authors first identify that some parts of the city are "Ratchets." A ratchet is a mechanism that only moves one way (up). Once you go up, you can't easily go back down.

• The Safe Ratchet (Focused): Imagine a single, narrow hallway. If someone tries to climb, they are funneled through one specific door. If you change the lock on that one door, the climb stops.
• The Dangerous Ratchet (Dispersed): Imagine a giant hub with hundreds of roads leading to the top. Even if you block one road, they just take another. To stop them, you have to tear up the whole map and rebuild the roads.

The Goal: We need to know which type of ratchet we are dealing with so we know whether to just change a lock (easy fix) or rebuild the city (hard fix).

2. The Old Way: Counting Steps (Abelian Statistics)

For a long time, security teams tried to guess the danger by counting.

• "How many times did they go up a door?"
• "How many keys did they gain?"

The paper argues this is like trying to predict a storm by counting raindrops. It misses the pattern.

• The Flaw: If two people walk up stairs in a different order, they might end up in the same place, but the risk is totally different.
• The Math Problem: In math, if you swap the order of two simple numbers (like 2 + 3 vs. 3 + 2), the answer is the same. This is called "Abelian." But in our permission city, the order matters! Going Up-Left-Down is different from Up-Down-Left. The old counting methods treat them as the same, so they miss the danger.

3. The New Way: The "Braided Rope" (Temporal Braid Groups)

The authors propose a new method: Imagine the people climbing are strands of rope.

• As they move through the city, they cross over and under each other.
• If they cross in a simple, repetitive way, the rope stays loose (Safe/Focused).
• If they cross in a complex, tangled way, the rope gets tight and knotted (Dangerous/Dispersed).

They use a mathematical tool called the Burau Representation to turn these crossings into a giant matrix (a grid of numbers).

• The Magic Number (Lyapunov Exponent): They calculate how fast this "rope" stretches and tangles.
  • Low Stretch: The rope is just moving around; it's safe.
  • High Stretch: The rope is tightening into a knot; it's dangerous.

4. Why This Matters: The "Magic" of Order

The paper proves something amazing: You cannot calculate this "stretching" just by counting how many times the rope crosses. You have to know the order of the crossings.

• Analogy: Imagine a dance.
  • Old Method: Counting how many times the dancers spin. (Result: "They spun 50 times, looks chaotic!")
  • New Method: Watching the sequence of spins. (Result: "They spun in a perfect circle, it's actually a calm waltz." OR "They spun in a chaotic knot, it's a mosh pit!")

The authors tested this on nearly 50,000 different scenarios. They found that the old counting method was wrong about 6% of the time.

• Sometimes it screamed "DANGER" when it was actually safe (causing panic).
• Sometimes it said "SAFE" when it was actually a ticking time bomb (missing a real threat).

5. The Real-World Impact

This isn't just theory; it changes how security teams fix problems:

• If it's a "Focused" Ratchet: The system says, "Hey, the danger is just because of how we assigned permissions. Let's just reassign the keys." (Cheap, fast fix).
• If it's a "Dispersed" Ratchet: The system says, "The danger is built into the structure of the network. We can't just change keys; we need to redesign the network." (Expensive, structural fix).

Summary

Think of this paper as inventing a new kind of metal detector.

• The old detector just beeped if there was any metal (counted permissions).
• The new detector listens to the shape of the metal (the order of permissions).
• It can tell you if the metal is a harmless paperclip (Focused) or a dangerous shiv (Dispersed), even if they are made of the exact same amount of metal.

By using this "braided rope" math, security teams can stop wasting time on false alarms and start fixing the real, structural dangers before hackers exploit them.

Technical Summary

Here is a detailed technical summary of the paper "Detecting Privilege Escalation with Temporal Braid Groups" by Christophe Parisel.

1. Problem Statement

Cloud identity security is not static; it depends on the temporal trajectory of permissions. Two non-human identities (NHIs) may hold identical permissions at a snapshot but diverge in risk over time: one may oscillate within safe bounds, while the other ratchets irreversibly toward broader access.

Existing detection methods rely on Abelian statistics (commutative measures) such as:

• Edge counts.
• Net privilege flow (Directed WAR Sum, DWS).
• Gate-firing rates (counting how often permissions escalate).

The paper argues that these Abelian metrics are fundamentally insufficient because they cannot capture non-commutative cancellations. In complex permission graphs, the order in which edges are traversed matters. Two deployments with identical edge counts and firing rates can have vastly different risk profiles if the sequence of traversals leads to spectral growth (dispersed risk) or cancellation (focused risk). The core problem is distinguishing between these two regimes without a tool capable of measuring non-commutative algebraic structure.

2. Methodology

The authors propose a framework using Temporal Braid Groups and the Burau Representation to model permission flows as algebraic objects.

A. Graph Decomposition and Classification

• SCCs (Strongly Connected Components): The permission graph is decomposed into SCCs.
• Primorial Invariant (Pre-screening): A companion method classifies SCCs as either Oscillators (topologically safe, no directed paths for escalation) or Ratchets (contain directed paths capable of irreversible escalation). This paper focuses exclusively on Ratchets.
• Ratchet Sub-classification: Within Ratchets, the goal is to distinguish between:
  • Focused Regime: Escalation is channeled through few paths; non-commutative cancellations moderate growth. Remediation: Reassigning privileges (WAR).
  • Dispersed Regime: Hub-rich topology with multiple independent paths; crossings accumulate without cancellation. Remediation: Topology surgery (adding/reversing edges).

B. The Braid Construction

1. NHI Walkers: Simulate $n$ independent random walkers on the SCC.
2. Strand Ordering: At each time step, walkers are ordered by their current privilege weight (WAR).
3. Gate Condition: A "gate" fires when two adjacent walkers (in WAR order) simultaneously traverse directed, ascending edges.
4. Injection Word: When a gate fires, a specific braid generator word is injected into the product: $\sigma_i^2 \sigma_{i+1}^{-1}$.
   • This word is chosen because it has a high spectral radius ($2+\sqrt{3} \approx 3.732$) and includes a negative exponent to enable cross-epoch cancellations that Abelian counts miss.
5. Burau Representation: The sequence of injected words forms a braid word. This is mapped to a matrix product using the Burau representation at $t = -1$ (yielding integer matrices).

C. The Risk Metric: Lyapunov Exponent (LE)

The Lyapunov Exponent (LE) is calculated as the exponential growth rate of the spectral radius of the accumulated Burau matrix product over time.

• High LE: Indicates exponential growth (Dispersed regime).
• Low LE: Indicates bounded growth due to cancellations (Focused regime).

3. Key Contributions

1. Impossibility Theorem (Theorem 6.2)

The paper proves that no Abelian statistic (including edge counts, DWS, or firing rates) can determine the Lyapunov Exponent.

• Proof Mechanism: The LE depends on the joint distribution of the matrix sequence (the order of generators), not just the marginal counts.
• Telescoping Blindness (Theorem 6.3): Directed cycles in an SCC contribute exactly zero to the DWS (net privilege flow) for any WAR assignment due to telescoping sums. However, these cycles can still fire gates and inject non-commuting generators, driving spectral growth. Abelian metrics are permanently blind to this escalation channel.

2. Two-Regime Classification

The authors define a boundary (median LE $\approx 0.5847$) separating Focused and Dispersed regimes.

• Focused: Remediable by reassigning WAR (privilege levels).
• Dispersed: Requires structural changes to the permission graph (topology surgery).
• Actionable Insight: The Abelian firing rate systematically over-calls the Dispersed regime (false positives) because it cannot account for the cancellations that keep the LE low in Focused scenarios.

3. The Shuffling Experiment

To prove the signal is non-commutative and not just noise, the authors shuffled the temporal order of gate injections.

• Result: Temporal braids had significantly lower Spectral Radii (SR) than shuffled braids (84% of cases).
• Implication: The temporal ordering creates systematic cancellations. Abelian counts, which ignore order, fail to detect this, confirming that the "non-Abelian correction" is a genuine structural signal.

4. Empirical Validation

• Dataset: 49,972 (SCC, WAR) pairs from a corpus of 1,000 synthetic 6-vertex SCCs.
• Disagreement Rate: 5.7% of pairs showed regime disagreement between the Burau LE and the Abelian rate.
• Correlation: After controlling for firing rate, Temporal LE retained a partial correlation of $r = 0.175$ with deployment structure ($p < 10^{-3}$), whereas the Abelian proxy collapsed to $r = 0.001$ ($p = 0.98$).

4. Results and Case Studies

The paper analyzes four specific ratchet topologies to illustrate failure modes:

1. Ratchet 205 (Sink Hub): Pure FD (False Dispersed) failures. The Abelian rate sees high flow, but Burau sees a single repeated generator causing cancellation.
2. Ratchet 207 (Directed-Heavy): Dominant FD failures due to a hub concentrating crossings, but some DF (False Focused) cases where diverse paths emerge.
3. Ratchet 143 (Bidir Junction): Balanced FD/DF split. Shows how bidirectional edges at a junction can switch the regime based on WAR assignment.
4. Ratchet 116 (Directed 4-Cycle): Pure DF failures. The cycle has zero DWS (Abelian sees no risk) but generates diverse non-commuting generators that drive high LE. This proves the Abelian metric is blind to cycle-based escalation.

5. Significance and Operational Impact

• Theoretical Breakthrough: Establishes that privilege escalation risk is inherently non-commutative. Simple counting metrics are mathematically incapable of detecting specific high-risk topologies (like directed cycles).
• Remediation Guidance: The framework prevents wasted effort.
  • If Focused: Security teams should reassign permissions (cheaper, faster).
  • If Dispersed: Security teams must redesign the permission graph architecture (harder, structural).
• Pipeline Architecture: Proposes a two-stage pipeline:
  1. Primorial Invariant: Filters out safe oscillators.
  2. Temporal Braid LE: Classifies remaining ratchets into Focused/Dispersed.
• Limitations: The Burau representation is unfaithful for $n \ge 5$ (distinct braids may map to the same matrix), meaning the LE is a lower bound on complexity. However, this bias is conservative (underestimating risk), and the method remains robust for detection.

Conclusion

The paper demonstrates that detecting privilege escalation requires moving beyond commutative statistics. By leveraging the Burau Lyapunov Exponent as a non-Abelian probe, security systems can distinguish between manageable (focused) and structural (dispersed) risks, a distinction that is provably impossible to make using traditional edge-counting or flow-analysis methods.