RE: looking for recursion stack overflow exploit

> 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()

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 Received on Mon Nov 25 13:28:38 2002