Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithmic complexity attacks and libc qsort()

calmerthanyouare.org

Post reply on HN
Print view View original

31–40 of 55 posts

Re: Algorithmic complexity attacks and libc qsort()

#31

Post by bcoates »

lelf wrote: post #20
Jabbles wrote: post #14

In comparison, the Go standard sort function is not vulnerable to this, and references the same paper as this article: http://golang.org/src/pkg/sort/sort.go#L168

Huh? And by what black magic its qsort is not O(n^2) (worst)?

It sets a stack limit proportional to log(n) and gives up and heapsorts the subproblem if the limit is exceeded. You get no more than n log(n) quicksort operations, plus heapsorting any partition of the input which is also n log(n)

In other words, they use the worst-case n log(n) heapsort with an optimization to use the much faster quicksort for non-pathological inputs, which is almost always.

Re: Algorithmic complexity attacks and libc qsort()

#33

Post by Malus »

mzs wrote: post #24

"Inspecting a diff between the qsort() of 4.4BSD-Lite and that of current day FreeBSD reveals that very little has changed since 1994." That reminds me :) $ expr \( -2147483648 \) \* -1 -2147483648 $ expr \( -2147483648 \) / -1 Floating point exception: 8 (core dumped) $ uname -srm FreeBSD 8.4-RELEASE-p9 i386

Looks like it is fixed now:

  $ expr \( -2147483648 \) \* -1

  2147483648

  $ expr \( -2147483648 \) / -1 

  2147483648

  $ uname -srm

  FreeBSD 10.0-RELEASE amd64
Or maybe it doesn't work on i386?

Re: Algorithmic complexity attacks and libc qsort()

#34

Post by mzs »

Malus wrote: post #33
mzs wrote: post #24

"Inspecting a diff between the qsort() of 4.4BSD-Lite and that of current day FreeBSD reveals that very little has changed since 1994." That reminds me :) $ expr \( -2147483648 \) \* -1 -2147483648 $ expr \( -2147483648 \) / -1 Floating point exception: 8 (core dumped) $ uname -srm FreeBSD 8.4-RELEASE-p9 i386

Looks like it is fixed now: $ expr \( -2147483648 \) \* -1 2147483648 $ expr \( -2147483648 \) / -1 2147483648 $ uname -srm FreeBSD 10.0-RELEASE amd64 Or maybe it doesn't work on i386?

It's likely an i386 thing:

  $ echo | awk '{ print 2 ** 31 }'
  2147483648
Make sure you are using /bin/expr and maybe give -9223372036854775808 a whirl too.

Re: Algorithmic complexity attacks and libc qsort()

#36

Post by haberman »

chowells wrote: post #23
haberman wrote: post #17

A similar DoS-with-degenerate-input these days is hash flooding. In the same way that quicksort can degrade from O(n lg n) to O(n^2) with degenerate input, so can hash tables degrade from O(1) to O(n) when all of the keys have hash collisions. This is the main motivation behind SipHash, a new hash function that is designed to be cryptographically collision-resistant but fast enough to use in hash tables: https://1310…

You mean the one mentioned in the article? Though you and the article both are perpetuating the lie that hash table operations are O(1). What magical hash function distributes n inputs into O(n) buckets in O(1) time? (Hint: distributing into O(n) buckets requires looking at O(log n) bits.)

> Though you and the article both are perpetuating the lie that hash table operations are O(1).

Hash table operations are O(1) on average, assuming a uniform hash function, and assuming that the number of buckets is kept greater than the number of elements. More info here: http://en.wikipedia.org/wiki/Hash_table#Performance_analysis

Computing the hash function itself is not usually factored into this analysis, probably because it's an orthogonal concern (ie. hash functions and hash table implementations can be mixed and matched), and because computing the hash function for every operation is not strictly required (the hash of the key can be cached).

But even if you are factoring in computation of the hash function, this is a strange argument:

> Hint: distributing into O(n) buckets requires looking at O(log n) bits.

Computers can look at O(log n) bits in a single operation for any "n" that can reasonably be held in memory.

For example, if your hash table has less than 4B entries, "log n" is less than 32. Any 32 bit computer can "look at" 32 bits in a single operation. So I can't see why you think that "log n" needs to be a factor in the complexity analysis.

Re: Algorithmic complexity attacks and libc qsort()

#37

Post by CJefferson »

Just in case anyone is curious, this does not effect any implementation of std::sort in C++ I am aware of.

They all use introsort -- basically use quicksort until you have done some number of partitions, then switch to heapsorting the cells of the partition. This ensures fast quick-sort performance while guaranteeing O(n log n) worst case.

Re: Algorithmic complexity attacks and libc qsort()

#38

Post by mzs »

tedunangst wrote: post #29
matslina wrote: post #26

Earlier quoted context omitted.

Mergesort would be a poor choice for qsort() due to the linear space complexity. With N bytes of RAM, you'd only be able to sort (a bit less than) N/2 bytes of data. An in-place algorithm is preferable. Glibc is the only libc I'm aware of that implements mergesort. It still falls back to quicksort for large inputs though.

All BSD derived libcs contains mergesort(), and heapsort() as well.

True, but parent meant used in the qsort and qsort_r implementations.

Re: Algorithmic complexity attacks and libc qsort()

#39

Post by boomzilla »

astrada wrote: post #16
j2kun wrote: post #10

Earlier quoted context omitted.

I've always liked mergesort for this reason. It's easier to understand and there's no wondering about complexity.

Well, sometimes you have space constraints. The O(n) extra-space required by mergesort isn't always available. But if you don't have space constraints, mergesort is a very good choice because you can easily write a highly scalable parallel version of the algorithm.

You can implement merge sort in place too:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....

Looks like the algo is more complicated, but surely implementable. In most modern architectures, the key for performance is how one exploits the caching behavior. Quicksort is very cache friendly, as well as the common implementation of merge sort. Not so for heapsort.

Re: Algorithmic complexity attacks and libc qsort()

#40

Post by samsamoa »

nicknash wrote: post #15

One semi-interesting thing here is that the "killer adversary" described on that page requires knowing that the algorithm you're trying to exploit is quicksort. Long ago, I wrote adversaries that attempt to force _any_ algorithm that is extracting a partial or total order from data to approach their worst case. These adversaries, like McIlroy's adversary, sits in the compare() function, but it asks itself "what answe…

Very interesting writeup. How did you determine the number of topological sortings for your "Yes" and "No" examples? I'm getting 360 and 144, rather than 120 and 48 that you wrote.
Post reply on HN