This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

qsort O(n^2) could be DoS attack


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]