InfoQ

News

Critical Security Vulnerability Found in Quicksort

Posted by Ryan Slobojan on Apr 01, 2009

Community
Agile,
Java,
Architecture,
.NET,
Ruby,
SOA
Topics
Security
Tags
Frameworks ,
Virtual Machines

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.

Related Sponsor

VersionOne is recognized by Agile practitioners as the leader in Agile project management tools. Companies such as Adobe, BBC, CNN, Dow, HP, IBM, Sony and 3M have turned to VersionOne to help deliver greater value to their customers.

Oh Noes ! by Michael Neale Posted Apr 1, 2009 12:03 AM
Re: Oh Noes ! by Jim Nasium Posted Apr 1, 2009 2:13 AM
Similar to bug in binarySearch by Thomas Mueller Posted Apr 1, 2009 4:48 AM
Happy April Fool's Day? by rubem azenha Posted Apr 1, 2009 8:32 AM
Re: Happy April Fool's Day? by Jim Nasium Posted Apr 1, 2009 9:13 AM
Re: Happy April Fool's Day? by Hermann Schmidt Posted Apr 1, 2009 9:55 AM
No doubt April fools by Lou Marco Posted Apr 1, 2009 2:58 PM
  1. Back to top

    Oh Noes !

    Apr 1, 2009 12:03 AM by Michael Neale

  2. Back to top

    Re: Oh Noes !

    Apr 1, 2009 2:13 AM by Jim Nasium

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

  3. Back to top

    Similar to bug in binarySearch

    Apr 1, 2009 4:48 AM 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)

  4. Back to top

    Happy April Fool's Day?

    Apr 1, 2009 8:32 AM by rubem azenha

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

  5. Back to top

    Re: Happy April Fool's Day?

    Apr 1, 2009 9:13 AM by Jim Nasium

    Do you think? ;)

  6. Back to top

    Re: Happy April Fool's Day?

    Apr 1, 2009 9:55 AM 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!

  7. Back to top

    No doubt April fools

    Apr 1, 2009 2:58 PM by Lou Marco

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

Educational Content

Brian Marick on 4 Challenges and 5 Guiding Values of Agile Software Development

Brian Marick takes us through a quick tour of the most important values and challenges to adopting Agile successfully (they aren't the typical challenges and values we hear in the community).

Are You a Software Architect?

The line between development and architecture is tricky. Does it exist at all? Is an ivory tower actually needed? There's a balance in the middle, but how do you move from developer to architect?

Agile – A Way of Life and Pragmatic Use of Authority

The word 'authority' sometimes produces an allergic response in hard-line agilists. Freedom and authority – both are bad if misused and both are good if used in right spirit for a noble cause.

Getting Started with Grails, Second Edition

"Getting Started with Grails" brings you up to speed on this modern web framework. Companies as varied as LinkedIn, Wired, and Taco Bell are all using Grails. Are you ready to get started as well?

Using ITIL V3 as a Foundation for SOA Governance

Those familiar with only ITIL V2 often scoff at the thought that ITIL could serve as a governance framework for SOA. With ITIL V3, the focus of the framework shifted towards service-orientation.

Adrian Colyer on AspectJ, tc Server and dm Server

SpringSource CTO Adrian Colyer discusses AspectJ, SpringSource's dm Server and tc Server products, OSGi and Scrum.

Adam Wiggins on Heroku

Heroku's Adam Wiggins talks about Rails, Background Jobs, Add-Ons, Ruby, and how Heroku manages to work around Ruby's inefficiencies using Erlang and other languages.

SOA as an Architectural Pattern: Best Practices in Software Architecture

For Grady Booch the foundation of a good architecture is patterns, SOA being just one of many patterns. In this Second Life presentation, Booch attempts to bring more clarity on what architecture is.