[prev in list] [next in list] [prev in thread] [next in thread] 

List:       vuln-dev
Subject:    RE: looking for recursion stack overflow exploit
From:       Michael Wojcik <Michael.Wojcik () microfocus ! com>
Date:       2002-11-25 16:03:22
[Download RAW message or body]

> 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
[prev in list] [next in list] [prev in thread] [next in thread]