Slashdot Mirror
Denial of Service via Algorithmic Complexity
dss902 writes "We (Department of Computer Science, Rice University) present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures... Using bandwidth less than a typical dialup modem, we can bring a dedicated Bro server to its knees; after six minutes of carefully chosen packets, our Bro server was dropping as much as 71% of its traffic and consuming all of its CPU. We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks."
I agree that DoS attacks are really lame, but at least this is fairly complex and has some interesting technological implications. Most DoS attacks are just floods of packets, and can't really be defended against. This attack can be prevented, and maybe will help improve security in other ways. I'd rather see 10 people who can pull off a preventable algorithmic complexity attack than 10,000 who just packet a server to death. People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
So this is like humans - you don't need a lot of information, just something seemingly complex/intricate, and their brains shutdown for a while?
;-)
(Or maybe this only happens to me?
If you RTFA you'd see they also present ways in which to AVOID this problem, and that's the real goal.
yes, they should, because they're also researching how to protect against them. better we find out now from a university that also mentions how to prevent these attacks than on some random day when al queda or some random hacker collective decide to take down the internet and bring a growing part of the world economy to a screeching halt.
well, maybe they're figuring out how to fix them. Would you rather a University figuring out how to do it, or some random black hat/chinese hacker?
With this information it shouldn't be too big of a deal to redesign the software to not be vulnerable anymore.
What they did is little more than algorithm analysis. They looked at all the different links in the chain then merely decided which algorithms were the weakest links and exploited them.
This is good because we can now fix those. Robustness abound.
I understand your question, but it, IMO, is like asking if "the people" should be free to speak about the bad things their King does, and wouldn't that just be bad for the Kingdom?
This doesn't sit well with me. Should students at a University be studying, developing, and releasing improved methods with which to launch DOS attacks..?
Most certainly yes. Others are studying it with purely malevolent intentions. The incentive of the University is benevolent. Carefully consider the consequences of not having public knowledge reflecting the capabilities of those with malicious intentions.
The onus is now upon the vendors to adhere to adequate standards, rather than resting upon public conformity and goodwill (which we both know is non-existent).
Compared to many DoS attacks, these guys do something that actually requires some matter of knowing, whereas others (read scriptkiddies) use things they've downloaded themselves. Most DoS attacks invlolve less sophisticated means, which is why this could be interesting for someone who does not know much about them.
Please excuse any bad grammar/spelling, I am quite drunk atm.
That is something that the paper said, but they also gave specific examples of software that was vulnerable to that kind of attack. They determined that the Bro intrusion detection was highly vulnerable to this kind of attack, and mentioned different versions of Perl and Python that also experienced a significant perfrormance decrease given their input specifically made to bring down systems that use hash tables.
I don't know if anyone has *published* this before, but it's certainly not new.
It has been done. They mentioned similar related work where it was found that input to quicksort makes it take O(n^2) time instead of O(n lg n) and a that there was a vulnerability in the hash tables of the Linux route-table cache. The concept isn't new, it's just that different software has been found to have this sort of vulnerability.
And I just couldn't help but laugh at the irony of their PDF file on DOS attack prevention being the victim of the /. effect.
Fine. Identify the problem
Step one complete. Now they're soliciting interaction on developing a solution.
funny munging
This DoS relies on the server being wide open on all ports. Simply putting the server behind a router that does NAT (Network Address Translation) or stateful packet inspection solves the problem of stray packets wandering in. Also note, this DoS does not crash any of the applications it just degrades performance. I would classify this DoS as "mostly harmless".
Worst case, this was a good excercise in analyzing algorithmic complexity and "Big O" notation for the CS students. Speaking of "Big O", I can't wait to check out the O(1) scheduler in the 2.5 Linux kernel.
But consider a commercial app where customers can send requests to a J2EE app server running within a JVM. That's a very popular, very common setup (JBoss, BEA Weblogic, IBM WebSphere, etc.). The JVM is a single process. It is not CPU-capped because it's designed to stay up and running. When a Java thread handles a request and bumps into a CPU-hogging attack, it is not going to be terminated by the J2EE app server.
So this is potentially a problem, because you currently do not have a CPU-capping parameter in the most popular J2EE app servers. A response to this kind of attacks would require monitoring the amount of CPU consumed by threads processing incoming requests, which is always delicate.
CPU-capping shouldn't be done lightly. It can lead to disastrous failures. For instance, I once tried to use a graphical web application rendering some do-it-yourself tee-shirt lettering. The application was running on an older IIS and apparently had a CPU-time cap, because I got a message "sorry, your request took too long to process" when my design became a bit involved. Needless to say, my business went to a competitor. So CPU-capping isn't even a sure-fire solution.
In summary: Sorry, it is an issue.
--
Mad science! Robots! Underwear! Cute girls! Full comic online! http://www.girlgeniusonline.com/
>It's scary to me to think that people who write code in the first style get to submit code to important projects like Apache. It looks like a Basic programmer writing in C syntax. Even for a string with no double slashes it is far less efficient than the second style.
: ...
:
Actually this is one of the fundamental methodologies used in software development, dating back to the early Slow-Machineazoic period
In theory it goes like this
1. On paper, design the flow of data, what is hoped to be accomplished.
2. Prototype the functionality as a proof of concept, insure that the tools you are using to program the solution are sufficient to do it. Usually this code is pretty gnarly and uses O(n^2) or worse routines (cut and paste in a bubblesort, anybody?), just quick and dirty, screw memory leaks, etc
3. Test the functionality.
4. Using the prototype as a blueprint, rewrite the project using your most awesome coding techniques (replace the bubblesort with a quicksort, etc.)
5. Test the release candidate.
6. Ship it!
The (yes, it is documented) problem with this methodology is that it generally devolves to this
1. On paper, design the flow of data, what is hoped to be accomplished.
2. Prototype the functionality as a proof of concept, using routines that suck and are slow and leak memory like a fish net.
3. Test the functionality.
4. Somebody watching the calendar sees you are already over schedule.
5. Some bean counter over-rules your demands to rewrite the entire package, given that he watched it work.
6. Ship it!
Glonoinha the MebiByte Slayer