This article is at once more interesting than the last (in that it has more obvious immediate use cases) and less interesting than it (in that I think it's less novel or clever). Nonetheless, in the spirit of filling the internet with meaningless noise investing time in creating things I think are at least a little interesting, I'll explain how we turned those self-pruned not-actually-trees into attack paths.
Also, I have another post that's taking longer to write than I expected, so this is filler? Filler is good. One of my favorite lines on Buffy was mostly filler. It forces us to be creative instead of just being content. I like being creative.
So, I explained last time that our cyber attack path scope was large. We wanted to cover everything. Every possible, theoretical, conceivable attack path anyone hadn't thought of yet. And, while ultimately we found a smarter mathematical solution to cover that space stochastically, part of describing the space (and part of the government's request) was being able to express it in terms of explicit attack paths. So, our problem here is turning a directed, cyclic graph into a complete set of possible attack paths.
Again, we're not interested in simply the shortest attack path, nor the most likely one. We want to account for every single possibility. Think of it as because once you fix the shortest path, there's a new shortest path. And a failure to mitigate all of the paths for this customer has real consequences.
And that's our problem statement today: how do you turn a directed cyclic graph into an exhaustive set of paths? It's actually really easy, if you've done graph search algorithm stuff before. And even if you haven't, you'll totally be like "oh, duh" in, like, a few paragraphs from now. I promise =].
Let's imagine this is the output we got from the last post:
This graph is visually entertaining (especially when you show it to a senior government program manager who never realized that was even connected to those in his 30+ years working on this system). However, it's not as easy to digest as explicit paths.
An attack path is a great story-telling mechanism. It spins a tail of intrigue, the kind of heist scheme that makes you want to say "you son of a bitch, I'm in". Which is exactly the kind of response you want when trying to convince someone that, yes, in fact, their world-ending technology is actually in danger and maybe they should do something about that that's more effective than just installing patches (it really wasn't a hard sell).
It's literally just a depth-first search with extra steps.
Did you ever learn the "how to solve any maze" algorithm as a kid? Always turn right? Works on any fully-connected graph. If we keep doing that until we reach every dead end and back track over every turn, we'll know that we've travelled every path. As we go, we spit out how we got there each time we hit one of our end targets. We run that full search a few times, starting once at each starting point, and by the end we've spit out every possible path in the graph.
For ECHO-based cyber attack graphs applied to complex, heterogenous weapons systems, it gives us the explicit step-by-step instructions about which interfaces to start at, which steps are gonna be the hardest to find an exploit for, etc. And it churns out a pretty big number of paths. Billions. One of those paths is bound to have at least a handful of steps someone somewhere has already figured out.
Click Go to watch. And that's it, folks. That's the post. Enjoy!
0 paths:
© 2025 Frank Lynam. All Rights Reserved.