Monthly Archives: November 2014

Nostalgia, horror, and a very old bug

Posted on by
22

My next article about graph traversal is pre-empted by this breaking news; I’ll pick up that series again soon.

Yesterday morning a coworker forwarded to me an article about a recently patched security hole in Windows, and wondered if I had any thoughts on it. Oh, did I! I read about the exploit with an odd mixture of nostalgia — because I worked on the code in question back in the 1990s — and horror at how long this exploitable bug had been in Windows.

To be clear, I did not write the actual exploitable code; it predates my time at Microsoft. But I was worried while I was reading the article that it might turn out to be my bad! This is the second time that has happened to me, and it is not a pleasant feeling.

Coverity has a research team devoted specifically to security-impacting bugs, and they were kind enough to ask me to write up my thoughts for their blog. You can read about my guess at what the buggy code looked like here.

If you have examples of “missing restore”-style bugs — security-impacting or not — in real-world code in any language, I would love to see them. Please leave examples in the comments here or on the security blog. Thanks!

Graph traversal, part four

Posted on by
19

Let’s return now to our modified Zork graph fragment from a couple episodes back:

zorkmap

It is pretty obvious just from looking at this graph that if you start from the Troll Room and follow the arrows, there are four rooms that you must enter no matter what combination of edges you take: the East-West Passage, the Dam, the Dam Lobby and the Maintenance Room. And moreover, we’ll encounter them in that order. Let’s call these nodes “the inevitable nodes of the Troll Room”. Continue reading →

Graph traversal, part three

Posted on by
7

Last time we made a little recursive algorithm to walk around a directed acyclic graph, or DAG. I made that algorithm a member of the graph class, but did you notice something about it? It did not access any private member of the class. Rather, it only used the public interface to do its work. What information do we need to find all the traversals of a DAG starting from a given node? Only the set of edges which come off that node, which we could determine from a delegate! We could in fact have written this algorithm as the following static method: Continue reading →

Graph traversal, part two

Posted on by
12

Last time we built an immutable structure representing a labeled directed graph, and then built a directed acyclic graph stolen from Zork: (click for larger)

zorkmap

The question at hand is: given a node in a finite DAG, what are all the possible traversals of edges through the graph starting from that node? We know that any traversal of a finite DAG must eventually terminate in a node that has no outgoing edge, and that there are finitely many such traversals. Continue reading →