This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
qsort O(n^2) could be DoS attack
- From: Ondřej Bílka <neleai at seznam dot cz>
- To: libc-alpha at sourceware dot org
- Date: Sat, 10 Feb 2018 17:37:03 +0100
- Subject: qsort O(n^2) could be DoS attack
- Authentication-results: sourceware.org; auth=none
Like was argumented in other functions main problem with deterministic
worst case is when attacker sends input to web server that makes it
unresponsive because of processing O(n^2) requests.
Here we deleted mergesort and kept simple qsort without addressing it.
Here O(n ln n) is possible with randomization of pivot for example add
check that if one part has more than 4/5 elements get next pivot as
number from /dev/urandom.