I have to throw my personal favorites into the ring: decompilation and deobfuscation.
In either case, after a certain amount of analysis you'll end up with a set of nodes (typically basic blocks) which connect to each other, but they'll be what I call 'immature' nodes. You know they connect, but they all effectively end with gotos. To make any sense of them, you have to make them into mature nodes: if, if-else, while, do-while, for, etc. Via graph reduction this is possible.
For instance, a few years back I was reverse-engineering Apple's Fairplay DRM and ran into an odd obfuscation scheme. There were dozens of functions which had the same structure: a switch inside a while statement; a state machine. After some hand-analysis, I figured out that at the end of each state, it'd set the state variable to either a constant value (a jump) or one of two conditional values (a conditional branch). At this point, it became clear that they were simply taking basic blocks and turning them into a big obfuscated state machine.
To make this into something worthwhile, I wrote a script that would go through the function and 'execute' it, to determine the state connections automatically. Then from there, I wired them up into a big graph, with two types of nodes: Fallthrough (no conditional) and Branch (conditional). Now, that helps a lot in terms of showing you what's happening, but not nearly as much so as control flow structures do, so the battle was only half over.
Now, if you look at common control flow structures from a graph perspective, they all look pretty straightforward (using something like dot graph notation):
A; if(X) {B} else {C} D becomes A -> B, A -> C, B -> D, C -> D.
A; if(X) {B} C becomes A -> B, A -> C, B -> C
A; while(X) {B} C becomes A -> B, A -> C, B -> C
So if you walk over the graph looking for these patterns (only looking at single nodes, mind you), replacing them with their mature equivalents, and recursively do that until you don't change anything, you can end up with a fully deobfuscated, cleanly readable result.
Great story. Worth pointing out here that reversers have been running with this idea full speed since ~2000. For instance, Halvar Flake and his team at Zynamics use graph isomorphisms of basic blocks in BinDiff, which is the industry standard tool for reversing security patches back to vulnerabilities.
Obviously, anyone who's ever used IDA Pro is familiar with control flow graphs and bblocks; hit the space bar in IDA and you get it graphically.
Yea, there's a lot of interesting things that have been done with graphs. I'm currently working on a reversing platform, and one of the core things I'm doing is elegant graph manipulation. It's amazing how much you can do when you have nice graphs, e.g. native pattern matching over graphs.
Most of these examples are either naturally graphs already, or on the contrary, can be presented as graphs through ingenious reductions (e.g. coloring as an approach to register optimization). So transforming the domain problem to a graph theory problem is either trivial or hard.
I found that a huge benefit of knowing some graph theory lies in being able to approach problems where this transformation is easy - neither trivial nor hard, but easy once you have some experience and intuition working with graphs. Every time you have a bunch of entities, and you can kinda think of their interdependencies as a binary relationship of some sort, there's a warning bulb going off in your brain - "is this a graph problem?". And if it is, then very possibly you immediately get lots of insight into your problem, basically for free.
This occurred to me a few weeks ago as I was thinking about this puzzle: design a circuit that inverts three inputs, but uses only two NOT gates (plus arbitrary amount of ORs and ANDs). It's an interesting puzzle to solve manually, but I also wanted to quickly write a program to find the solution. Circuits are trivially graphs, but there're too many of them (an infinity) to iterate over. Once you see the problem as a reachability problem in a certain fixed graph, however (easy, but not trivial), the code writes itself. Someone with no exposure to graph theory might easily just balk at this easy problem, not knowing how to proceed.
I can get the circuit with 4 XORs and 1 NOT, or 3 XORs and 1 XNOR. I can't see a way to simplify to just ANDs, ORs and 2 NOTs. It's an interesting problem, were you able to find a AND, OR and 2 NOT solution? Or did you wind up using XORs?
On a related note, Graph Theory is one of the top reasons to learn Linear Algebra. All graphs (included directed, weighted, and multi-graphs) can be represented intuitively by adjacency matrices, and matrix operations often end up being meaningful in terms of the graph they represent. Seeing the connections between a graph and its matrix helps to understand both of them, and being able to switch back and forth between mental models is often useful. For example, Markov Chains are the go-to tool in many fields of modeling, are most easily thought of as weighted graphs, and are most easily manipulated as matrices.
Graph theory was easily the most practical thing I learned from programming contests. Most of the applications are "obvious", but only if you play with enough graphs.
He misunderstood the circuits problem. It's not a graph planarity problem - anything significant is not going to be planar. Only very simple circuits are wireable with less than two layers (and then by, for instance, sneaking a couple of lines under a resistor, etc. - not planar).
But you do get to use graphs to solve the component placement problem, in heuristics that try to minimize total wire length. That hopefully means that wiring delays are smaller, and routing more feasible. One of the classic heuristics involved successive bipartions on the min-cut of the graph.
If this is the same Dover book we used in our graph theory class, I found it difficult to learn from without a professor explaining the unclear sections. Not just doing the exercises, but some of the things they presented as trivial had some important steps missing.
Good summary list. For most developers, there is a nice abstraction barrier for graph theory because tools like neo4j, efficient RDF stores, search libraries, etc. make it fairly easy to build apps without getting one's hands dirty in the details. (But knowing the details makes it more likely to get creative and novel apps.)
Off topic, but: since so many things are well described as graphs, the GraphViz tool is great for communication: few lines of code to write your data to a 'dot' file, and a few seconds later you have a visual representation of your data.
What's a good curriculum / reading list for learning graph theory? What kind of things do you need to understand before you can check it off the "things to learn more about" list?
Not sure what it would be like to learn from - certainly you would have to "Read Like Math" and not "Read Like Prose". You would be strongly advised to do the exercises properly and not just skim.
I agree with his assessment. Any data representation can be construed as a graph - this is the basis of garbage collection. Besides the areas where graphs (or networks) are explicit in a problem, the most powerful use comes in analyzing a given model/algorithm. If you don't take that step to the meta-level, you might not see the use for graph theory.
I'm the blog post author. I just uploaded the reply to the language speed article. I was actually very surprised when I woke up today and saw thousands of entries in my access log and referrals from social news sites.
A few things require true genius, but most things can be done by anyone with enough effort. But few people put in the effort so when someone does and produces good results, they deserve the credit.
One very cool thing I learned today is that knowledge amongst a number of people, with the help of modal logic and Kripke possible world semantics, essentially reduces to a graph reachability problem.
In either case, after a certain amount of analysis you'll end up with a set of nodes (typically basic blocks) which connect to each other, but they'll be what I call 'immature' nodes. You know they connect, but they all effectively end with gotos. To make any sense of them, you have to make them into mature nodes: if, if-else, while, do-while, for, etc. Via graph reduction this is possible.
For instance, a few years back I was reverse-engineering Apple's Fairplay DRM and ran into an odd obfuscation scheme. There were dozens of functions which had the same structure: a switch inside a while statement; a state machine. After some hand-analysis, I figured out that at the end of each state, it'd set the state variable to either a constant value (a jump) or one of two conditional values (a conditional branch). At this point, it became clear that they were simply taking basic blocks and turning them into a big obfuscated state machine.
To make this into something worthwhile, I wrote a script that would go through the function and 'execute' it, to determine the state connections automatically. Then from there, I wired them up into a big graph, with two types of nodes: Fallthrough (no conditional) and Branch (conditional). Now, that helps a lot in terms of showing you what's happening, but not nearly as much so as control flow structures do, so the battle was only half over.
Now, if you look at common control flow structures from a graph perspective, they all look pretty straightforward (using something like dot graph notation):
So if you walk over the graph looking for these patterns (only looking at single nodes, mind you), replacing them with their mature equivalents, and recursively do that until you don't change anything, you can end up with a fully deobfuscated, cleanly readable result.