Pet project mentioned on calmerthanyouare.org
http://code.google.com/p/awib/ "Awib is a brainfuck compiler written in brainfuck. "
Algorithmic complexity attacks and libc qsort()
11–20 of 55 posts
Re: Algorithmic complexity attacks and libc qsort()
#12Some historic quick-sort mis-implementations had O(n^2) runtime when trying to sort constant data (all keys equal, the effect was due to not picking the partition carefully in that case). See: http://www.win-vector.com/blog/2008/04/sorting-in-anger/
Re: Algorithmic complexity attacks and libc qsort()
#13I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input". I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".
If you are ever handling input data from basically anything outside of the program. Its better to use a constant speed algorithm like merge sort. Just because of attacks like this, I'm really surprised algorithm exploits attacks like this haven't come to the forefront of attacks recently.
Application level DDoS's leave the kernel/network/sockets layers exposed for exploitation. Since their tasks will take priority over user's applications.
Re: Algorithmic complexity attacks and libc qsort()
#14In comparison, the Go standard sort function is not vulnerable to this, and references the same paper as this article:
Re: Algorithmic complexity attacks and libc qsort()
#15One 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 answer can I give, consistent with the data so far, to force the algorithm to ask me the largest number of subsequent questions?"
For non-introspective quicksorts this will be O(n^2), but it should also bring out the worst constant factors in O(n\logn) worst case time algorithms.
I did some experiments: http://nicknash.me/2012/07/31/adversaries/
A proper reference is the Kahn's "Sorting and Entropy", IIRC.
Re: Algorithmic complexity attacks and libc qsort()
#16I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input". I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".
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.
Re: Algorithmic complexity attacks and libc qsort()
#17A 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://131002.net/siphash/
Re: Algorithmic complexity attacks and libc qsort()
#18I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input". I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".
If you are ever handling input data from basically anything outside of the program. Its better to use a constant speed algorithm like merge sort. Just because of attacks like this, I'm really surprised algorithm exploits attacks like this haven't come to the forefront of attacks recently. Application level DDoS's leave the kernel/network/sockets layers exposed for exploitation. Since their tasks will take priority ov…
> Application level DDoS's leave the kernel/network/sockets layers exposed for exploitation. Since their tasks will take priority over user's applications.
So what's the benefit of that, just that you can maximize the chaos you cause by attacking in two different ways?
Re: Algorithmic complexity attacks and libc qsort()
#19In 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
I don't see it, seems just a median of three quick sort - the median of three for the partition selection is to mitigate poor performance of quick sort on sorted and reverse sorted inputs.
edit: I'm an idiot, totally glossed-over the switch to heap sort logic.
Re: Algorithmic complexity attacks and libc qsort()
#20In 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)?