Where's the FEEB?
The Effectiveness of Instruction Set Randomization

Nora Sovarel, David Evans, and Nathanael Paul
14^th USENIX Security Symposium
Baltimore, MD
4 August 2005

Abstract

Instruction Set Randomization (ISR) has been proposed as a promising defense against code injection attacks. It defuses all standard code injection attacks since the attacker does not know the instruction set of the target machine. A motivated attacker, however, may be able to circumvent ISR by determining the randomization key. In this paper, we investigate the possibility of a remote attacker successfully ascertaining an ISR key using an incremental attack. We introduce a strategy for attacking ISR-protected servers, develop and analyze two attack variations, and present a technique for packaging a worm with a miniature virtual machine that reduces the number of key bytes an attacker must acquire to 100. Our attacks can break enough key bytes to infect an ISR-protected server in under six minutes. Our results provide insights into properties necessary for ISR implementations to be secure.

Paper

Full paper (16 pages): [PDF] [HTML]

Talks

USENIX Security Symposium, 4 August 2005 (Ana Nora Sovarel) [PPT, 2.5MB]

CERIAS Security Seminar, 9 March 2005 (David Evans) [PPT, 39 slides] [PDF, 7 pages] [Abstract]

IEEE Security and Privacy Symposium, 5 Minute Talk, 9 May 2005 (Ana Nora Sovarel) [PPT, 6 slides] [PDF (1 page)]

Links

UVa Genesis Project

RISE: Randomized Instruction Set Emulation (University of New Mexico)

David Evans - Publications University of Virginia Department of Computer Science

David Evans evans@virginia.edu