[Dailydave] Algorithmic Bugs

[Matt]

On Wed, 10 Jan 2007, Randy Smith wrote:

> Linearizing hash tables is a trick that has been known about for a
> while.  I do believe it could be considered the "classic attack", as you
> suggest.
>
> Of course, in our paper we showed the same kinds of effects (denial of
> service) using entirely different techniques (excessive backtracking).
> We also proposed and implemented a solution that fairly effectively
> neutralizes the attack.

When developing the buffer interation bug detection in BugScan, we hit
excessive backtracking issues in our testing that we have to creatively
work around. Through a combination of really shitty code (wu-imapd from
redhat 5.2, some components of adobe acrobat, all of oracle, etc) and
possibly poor but definitely strange optimization, the iteration analysis
would take many, many orders of magnitude longer than it should have --
even for small (depth of 50) bounded graphs. I suspect that this kind of attack
could be used to make vulnerability analysis on binary code (or source
code, actually) more difficult.

By more difficult, I mean that analysis developers will have to think of
creative ways to color the graph like we did. By the end we were
analyzing iterations with a block depth in the hundreds very quickly and
with no known false positives. It took a while due to running the
analysis on thousands of binaries in system tests, and
developing the unit testing framework to make it easy to test, to get
there, though. The upside was once we moved forward, we never moved back.
Much appreciated by customers :)

--
tangled strands of DNA explain the way that I behave.
http://www.clock.org/~matt