Using graph theory to identify critical nodes within computer networks

In an already under-resourced cyber security industry, demand for talent is currently much greater than supply. While understaffed and under-resourced blue teams try to defend increasingly large networks, the red teams that might have the insight to direct the resource allocation are infrequently used because red-team exercises are expensive and non-exhaustive. The result is a blue team that becomes decreasingly effective over time but periodically (and non-exhaustively) corrected by expensive insights from external red teams.

One way to overcome these problems is to model attack paths in real-time. That way, blue teams would have continual insight and may continuously adapt their approach to defending the most critical network assets without the need for expensive external input. In short, the solution is to automate an internal red team.

Our method constructs two weighted graphs to show pair-wise relations between network entities that might be compromised, such as devices and user accounts.

First, a graph is drawn with directed edge weights representing the estimated probability of rapid lateral movement from the source to the destination entity. For example, if a device has well-established communication pathways to a server with a high CVSS score, then the edge weight will be closer to one. Edges also consider intrinsic mechanisms that enhance security, such as multi-factor authentication, endpoint-protection agents, or even just a more security-aware user.

Then, to form a second graph, objective importance scores are either manually or automatically seeded and propagated through the graph via edges weighted according to shared access or trust relationships. For example, if the CEO of an organization has access to a file shared with only one other employee—some of the importance associated with the CEO is propagated to this other user.

If the CEO has access to a file that many other users can access, the importance of the CEO is diluted amongst the many users, suggesting that this file is not especially important. When available, the graph also includes email communication patterns.

We use these graphs to simulate the compromise of all potential network entry points—including any human with access to the internet, as well as externally-facing infrastructure. The simulation yields impact scores that correlate to path lengths to high-importance nodes. The scores can be modulated according to how exposed an entry point is to an outsider.

This results in a dynamic list of network nodes, ordered by the potential damage to the organization if compromised at the current time. The paths to these nodes were also highlighted, allowing the blue team to remediate accordingly. Compared to traditional red team exercises, this method is continuous, rigorous, and cost-effective.