BT
x Your opinion matters! Please fill in the InfoQ Survey about your reading habits!

Critical Security Vulnerability Found in Quicksort

by Ryan Slobojan on Apr 01, 2009 |

In what is sure to become one of the most wide-reaching security vulnerabilities yet known, a researcher with L0pht Heavy Industries has uncovered a flaw in the standard implementation of the Quicksort algorithm. InfoQ spoke with Dildog of L0pht to learn more about this vulnerability and it's ramifications.

Dildog explained the vulnerability as being of a class of vulnerabilities known as buffer overflow exploits. In these sorts of vulnerabilities, a malicious program is able to execute arbitrary code using the permissions of the user which is executing the given process.

In the case of Quicksort, the source of the vulnerability has not yet been made public, however it has been confirmed by two external security analysis firms as being present in the standard implementation of the Quicksort algorithm. Pseudocode for this algorithm, as found on Wikipedia, is:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

This vulnerability has been confirmed as affecting the following libraries, runtimes and products:

  • Several implementations of the JVM (including those of Sun, IBM, Oracle/BEA and Apache)
  • The .Net CLR up to and including version 3.5 SP1
  • The Microsoft Visual C Runtime up to and including version 9.0
  • The Adobe Flash runtime up to and including version 10.0
  • glibc up to and including version 2.6
  • Apache HTTPD up to and including version 2.2.13
  • Numerous hubs, switches and routers including some from Cisco, Juniper, D-Link, Netgear and Linksys

According to Dildog, this vulnerability was first discovered while performing forensics upon a system which had been compromised by a previously unknown exploit. This exploit caused the computer in question to change all system sounds to clips of an 80s pop song, and replaced all system images and icons with pictures of assorted Lolcats. Although there have been no other reports of this exploit being seen, we advise all InfoQ readers to keep alert and report any unexpected appearances of either Rick Astley or Lolcats to the proper authorities.

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Re: Oh Noes ! by Jim Nasium

I just looked at how many machines we have that are compromised... it's over 9000.

Similar to bug in binarySearch by Thomas Mueller

Similar to this bug:
bugs.sun.com/bugdatabase/view_bug.do?bug_id=504...
(however this bug didn't affect that many applications)

Happy April Fool's Day? by rubem azenha

It's probably an April Fool's joke...

Re: Happy April Fool's Day? by Jim Nasium

Do you think? ;)

Re: Happy April Fool's Day? by Hermann Schmidt

No, it's true! Our credit card billing database has just quicksorted itself and everything is gone, because some exploit moved it to Youtube. We are bancrupt!

No doubt April fools by Lou Marco

But a pretty good one. I'm curious if anyone at the ranch bites.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

7 Discuss

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT