Tuesday, January 10, 2012

LINQ sorting is also vulnerable

This is a follow-up post to .Net's Sort Is Not Secure. Don't Use It. Here's a Better One.

A reader asked if LINQ's sort has the same vulnerability. I added tests for sorting an array using LINQ's 'orderby' clause. Another reader wondered if the Sort() method for generic lists had the same problem so I added that test as well.

Time required for sorting one million items provided by an adversary:

AlgorithmSorting Time
Zimbry Introsortone-half second
.Net CLR (Array)1,588 seconds
.Net CLR (LINQ)1,916 seconds
.Net CLR (List)1,588 seconds

Detailed benchmark results are here: Sorting up to 1 million items (with an adversary)

Notes on the test:

All tests were run under .Net framework version 4.0

The times reported in the table are an average of the times taken for one ascending sort and one descending sort.

3 comments:

  1. It's worth noting that nearly all cases of sorting 1 million items with LINQ in production code use a LINQ provider which delegates the sort to SQL, such as LINQ to Entities or LINQ to SQL.

    Sorting 1M (or any non-trivial number) objects in LINQ to Objects would be an obvious bug to anyone who bothers to profile their app that even with a very efficient sort it would be regarded as a bug.

    ReplyDelete
  2. Craig, I disagree. Perhaps in database applications, it's uncommon to keep a million or more objects in memory. But many types of applications that work with large amounts of data don't use SQL at all. Our apps, for example, get their data from a custom repository stream, from crawling the Web, and from sequential files of all types. We don't even have a SQL server. We're not exactly mainstream, true, but applications like ours aren't exactly rare, either.

    The LINQ sort, by the way, is particularly bad. Whereas the standard array sort has a median-of-three pivot selection and type-specific optimizations for base types, the LINQ sort is a standard naive QuickSort. Array.Sort won't exhibit pathological behavior with a sorted array. LINQ's sort will.

    ReplyDelete
  3. Jim, you're blaming the wrong code. It's not "LINQ" that's the problem here, it's "LINQ to Objects," which is a popular LINQ provider, indeed, but not 100% of LINQ, especially for "large-ish" results.

    ReplyDelete