Friday, January 6, 2012

Quicksort: Is picking a pivot at random secure?

Eric offered this suggestion:
Another way to harden quicksort is to select the elements used in the pivot calculation randomly. This makes it nearly impossible for an attacker to cause worst case performance, and doesn't require you to also implement multiple sort algorithms.
This is well-worth considering. A single sort algorithm is simpler than combining multiple algorithms so there has to be a compelling benefit gained to justify the additional complexity.

I've done some testing and benchmarks but before we jump to the conclusion take a few minutes to ponder this with me and let's see just how far down this rabbit hole goes.

Hardening quicksort is a thorny problem and for an interesting reason. Quicksort's soft spot is in the method used to estimate the median. The risk that a sequence of partitionings will be unbalanced and lead to degenerate performance depends directly on the quality of the estimate. So why bother with a questionable estimate when it's easy to pick the actual median and have a perfectly secure quicksort? Ah, because there's a catch. Finding the actual median requires almost as much effort as it would to perform the sort itself. So, the only way that quicksort is viable is by making estimates and, as such, most quicksort algorithms are defined by their estimating technique: first item, random item, median-of-three, median-of-N, median-of-random-three, median-of-medians-of-three... you name it and it's probably been tried.

As long as we are estimating the median we have to accept that we are, in effect, rolling the dice and hoping a rare series of bad choices does not happen. And if an attacker is present they are only too happy to hand us loaded dice to ensure the worst possible outcome.

But wait... For an attack to work the attacker must be able to anticipate our method of estimating a median. What happens if we choose it at random? Does this defeat the attacker?

First, what exactly do we mean by 'random'? The pseudo-random number generator provided by most frameworks (the Random class in .Net is a good example) is highly predictable. It won't slow down an attacker. Alternatively, you could use a cryptographically secure random number generator but that comes at a performance penalty that almost certainly makes it unworkable. That cost will come down soon, though. Intel has new CPUs coming this year that offer fast, high-quality random number generation in hardware.

Let's assume we have that CPU today and it delivers fast and cryptogaphically secure random values. We are probably(1) not at risk from an attacker.

Not so fast. There are still two problems we can't erase:

1. Although highly unlikely, it doesn't eliminate the risk of a series of low-probability but catastrophic choices. I have seen quicksorts go quadratic on natural data, without the presence of an attacker, even when using the median-of-three method. Choosing at random should be more resilient. Whether this risk is acceptable or not depends on whether the sort is part of tax preparation software or whether it's running the auto-pilot of a jumbo jet.

2. It makes low-quality estimates of the median. Partitions will be less balanced and performance will suffer for it.

There is only one way I know of to reliably harden quicksort against both an attacker and an unlucky series of choices: Set an upper limit on how much effort quicksort is allowed to spend before abandoning it entirely.

Introsort is secure because it limits how many bad partitions it can accept before dropping out of quicksort and switching to heapsort to finish the job.

Of course, we could throw away all the complexity and just use heapsort. It has no degenerate cases and is secure against an attacker. But there's a catch. The reason we don't embrace heapsort so quickly is it tends to be significantly slower than quicksort in the average case.(2)

Let's look at the benchmarks: Sorting up to 100 million items (with no adversary)

The final algorithm, Zimbry_PureQuicksortFatPivotR1, is a pure quicksort (does not fall back to an insertion sort on tiny partitions) that uses a pseudo-random number generator to choose the pivot. It's what Eric suggests: A single quicksort algorithm that chooses a pivot at random. Introsort is 19% faster on average and is not vulnerable to either an attacker or at risk of degenerating on a bad series of random pivot choices.

So, here we are, at the bottom of the rabbit hole, and we find ourselves surrounded by trade-offs:

1. We can have a pure quicksort if we're willing to accept slower performance and the highly unlikely chance of bad behavior.

2. We can be invulnerable to both attackers and bad luck by choosing heapsort but that armor comes at a severe average performance cost compared to quicksort.

3. We can "have our performance cake and eat it too" by building a quicksort that falls back to heapsort in an emergency. We get good performance on average and no bad behavior to worry about but it comes at the cost of additional engineering complexity.

Engineering is all about trade-offs.

                                                                                                                                                            

(1) A motivated attacker won't give up so easily. If there is a flaw in Intel's random number generator it will be found and exploited. It's best to give the community (both the good guys and bad guys) time to stress-test any new security software or hardware before adopting it for your own use.

(2) Ball-park comparison: A well-implemented heapsort is typically three to five times slower than a well-implemented quicksort.

19 comments:

  1. If you found any common issue like installation error, connectivity error. company file issue, PDF related error and printing issues in your Quickbooks software, you can download Quickbooks Tool Hub to fix all issues. This tool is the compilation of all tools in one application.
    Quickbooks Repair Tool

    ReplyDelete
  2. I have been a writer all my life – I get paid a decent amount when my clients buy white paper writing service from me. But I have been inclined to venture into the programming, and my friend, who is an expert in programming, has asked me to save pages where I can find such information, and he will teach me on the weekends and clear my confusions – this one looks better than the previous three I have saved. I am saving this one for sure!

    ReplyDelete
  3. Hyderabad Escorts Service INDEPENDENT Call Girls Full sex satisfaction Night Service Book
    Name 23 years old Girls independent escorts Hyderabad Call Girls Russian Women Only Thank you very much for
    visiting Hyderabad.If you have come to Hyderabad and you have a very good business then you will have to spend a
    lot of money and that is why you will feel very good in your life.

    Call Girls in Banjara Hills
    Call Girls in Lucknow
    Escorts Services in Hyderabad
    Hyderabad Escorts Service
    Hyderabad Escort Service
    Voltas Ac Service Centre in Delhi
    LG LED TV Service Center in Delhi
    Chennai Escort Service
    Escorts Services in Chennai

    ReplyDelete
  4. Windows 10 is upheld on the 123 HP com design printer. Search and discover your HP Printer's best programming and driver on our site. 123 hp setup In the event that you have any issues while running Windows 10 with your 123 HP Setup printer, you can use HP Print and Scan Doctor to dissect and resolve the issue. [ Software and Drivers] 123.hp.com setupHP Experts on this site will help you screen your network by prescribing the right programming and driver to stay up with the latest. Adhere to bit by bit directions accommodated extra subtleties on 123.hp.com/setup.Take from the shipment box the 123 HP Setup Printer and spot it on a level inflexible surface. Eliminate from it the bundling materials.Included in the bundle are the using handbook, power line, USB link and CD-establishment driver and Ink cartridges.Remove from the gadget all tapes and pressing materials. The devices is bundled near keep the printer's parts from moving during shipment.Keep the transportation box and other reused pressing materials to the side.

    ReplyDelete
  5. So, despite the busy schedule, the professional assignment help are there to finish your assignments on time. Below- given are many further advantages of these expert assignment pens, which scholars might mileage themselves for the services.

    1. Timely service
    Time is the most precious asset in the academic lives of scholars. Unfortunately, utmost of them fail to do their tasks only due to lack of time after feeding to other imperative liabilities.

    ReplyDelete
  6. Thanks for providing such useful information. I have been looking for this type of information for a long time. Thank you, and best of luck! You might be interested in checking out my typing speed test profile on this website. Then you can see how fast or accurately you type by visiting my profile.

    ReplyDelete
  7. You have got some great posts in your blog. Keep up with the good work.
    apply for debt relief order online

    ReplyDelete




  8. apply for a dro online

    We are a group of volunteers and starting a new initiative in a community. Your blog provided us valuable information to work on. You have done a marvelous job!

    ReplyDelete
  9. Hi I am Alex and I work as a pro advisor in a multinational organization. I specialize in performing QuickBooks file backups and repairs to get you back up and running. I’m a QuickBooks expert and I know what to do when your QuickBooks is not opening up. Technology and accounting are my specialties. I'll get your QuickBooks up and running on time! We provide technical support to users by virtual calls and chats using QuickBooks.

    ReplyDelete
  10. We are aware that when students are in university, for them money is hard to come by. Because of this, the cost of the service kept the do my homework online reasonable. They're just thinking about your career, and getting your degree is challenging enough. Online assistance with statistics assignments should be simple. They are unable to provide free homework assistance because their excellent staff of experts must be paid. Despite this, it's a beneficial move because it establishes their legitimacy. They also maintain simplicity. No danger, no recurring fees, and no extra costs are included in their prices. You won't be charged if you're dissatisfied with the statistics homework assistance they offer. With their assistance, you have the finest possible security.

    ReplyDelete
  11. Assignment help online that assists with writing research papers are only available to students; therefore, they make their prices as low as possible. They frequently make fair offers, which aids in getting hired by students. As a result, the majority of services, including proofreading, are reasonably priced.

    ReplyDelete
  12. Hi, I’m Alex working in a Quickbooks team in a renowned organization. When you send them to your employee they will need an intuit paystub password. I’m a QuickBooks paystub password expert. So if you face any issues regarding the quickbooks paystub password and how to reset paystub password you can contact my team.

    ReplyDelete

  13. Learn everything about do my online class . Classdoer is the best platform for those expectations. Whether you call it distant learning, online learning, or cold learning, school aspects unlike during the COVID-19 pandemic. While some scholars are flourishing with this way of knowledge, many scholars don’t seem to be attractive in it. Some students may not be present at all. Others may be in presence, but they aren’t revolving in work or doing additional than the bare least.

    ReplyDelete

  14. Biz Talks is the top business magazines in India for Business Leaders, Decision Makers, Senior Executives, CEOs, CFO, Startups and Entrepreneurs. We focus on business, finance, technology, healthcare,entrepreneurship, leadership, and lifestyle.

    ReplyDelete
  15. Healing Buddha not only offers healing but empowers individuals to take control of their well-being. They provide guidance and tools for self-care, enabling clients to continue their healing journey independently.
    pranic healing

    ReplyDelete