RE: looking for recursion stack overflow exploit

[Michael Wojcik <Michael.Wojcik () microfocus com>]

> From: Valdis.Kletnieks () vt edu [mailto:Valdis.Kletnieks () vt edu]
> Sent: Friday, November 22, 2002 9:35 AM

> On the other hand, the Unix libc usually contains the qsort() and ftw()
> routines, which might be interesting.

qsort() is sometimes implemented iteratively rather than recursively.  (For
that matter, it can be implemented with any sorting algorithm that preserves
the semantics in the standard - it needn't be Quicksort.)  Hoare, in his
Turing Award speech, said that his original Quicksort design (it's not clear
he ever implemented it this way) was iterative, not recursive.  Since
qsort() uses a size_t for the number of elements, and the implementation
decides how large a size_t is, the implementation also knows how deep the
qsort() stack can get (log-2 of the maximum value of a size_t, if memory
serves), so it can use a manual fixed-size stack and iterate.

Regardless of qsort() implementation, though, I agree that recursion
overflow doesn't look like a very promising area for vulnerability research.

Michael Wojcik
Principal Software Systems Developer, Micro Focus