Dailydave mailing list archives
Re: Algorithmic Bugs
From: Matt <matt () use net>
Date: Wed, 10 Jan 2007 18:11:10 -0800 (PST)
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 _______________________________________________ Dailydave mailing list Dailydave () lists immunitysec com http://lists.immunitysec.com/mailman/listinfo/dailydave
Current thread:
- Algorithmic Bugs Dave Aitel (Jan 10)
- Re: Algorithmic Bugs Randy Smith (Jan 10)
- Re: Algorithmic Bugs Thomas Ptacek (Jan 10)
- Re: Algorithmic Bugs Randy Smith (Jan 10)
- Re: Algorithmic Bugs Matt (Jan 10)
- Re: Algorithmic Bugs Randy Smith (Jan 10)
- Re: Algorithmic Bugs Matt Beaumont (Jan 10)
- <Possible follow-ups>
- Re: Algorithmic Bugs Steven M. Christey (Jan 10)