Stack Analysis of x86 Executables
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.
Benjamin Schwarz
Computer Science Division
University of California, Berkeley
Berkeley, CA 94720
Binary rewriting is becoming increasingly popular for a variety of low-level code manipulation purposes. One of the difficulties encountered in this context is that machine-language programs typically have much less semantic information compared to source code, which makes it harder to reason about the program's runtime behavior. This problem is especially acute in the widely used Intel x86 architecture, where the paucity of registers often makes it necessary to store values on the runtime stack. The use of memory in this manner affects many analyses and optimizations because of the possibility of indirect memory references, which are difficult to reason about. This paper describes a simple analysis of some basic aspects of the way in which programs manipulate the runtime stack. The information so obtained can be very helpful in enhancing and improving a variety of other dataflow analyses that reason about and manipulate values stored on the runtime stack. Experiments indicate that the analyses are efficient and useful for improving optimizations that need to reason about the runtime stack.