21–30 of 55 posts
Was anyone able to view the linked research paper on Hash Table exploits?
You gotta dig a bit. But here: https://www.usenix.org/legacy/publications/library/proceedin...
[1] http://events.ccc.de/congress/2011/Fahrplan/attachments/2007...
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)?
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…
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.)
That reminds me :)
$ expr \( -2147483648 \) \* -1
-2147483648
$ expr \( -2147483648 \) / -1
Floating point exception: 8 (core dumped)
$ uname -srm
FreeBSD 8.4-RELEASE-p9 i386Earlier quoted context omitted.
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?
Basically its the old, can't see the forest past the trees routine.
Its more gaming the operators then the system.
I'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".
Glibc is the only libc I'm aware of that implements mergesort. It still falls back to quicksort for large inputs though.
I'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".
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.
Also, nice little write-up, thanks. I also dig the extracted sort implementations you dug-out: https://github.com/matslina/qsort
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.
I'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".
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.
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.
Heapsort