Download Enhancing Non-determinism in Operating Systems A Thesis

many buffer overflow exploits. Unfortunately, no concrete metrics are provided to
quantify the level of effective diversity.
The most prominent approach that has evolved is Address Space Layout
Randomization (ASLR), developed by the Linux PaX team [32] and later used in
many other operating systems including variants of Windows. This technique
introduces diversity by randomly relocating the base address of libraries, program
text, stack, and heap, at runtime, though it does not attempt to perform any
reordering or randomization within these memory segments. This removes the
ability for attackers to statically pre-determine the address of functions and
gadgets used to build exploits or arbitrary code fragments – denying surveillance,
rather than eliminating the vulnerabilities themselves.
ASLR is believed to be effective against both return-to-libc attacks and
return-oriented programming. Unfortunately, a minimal level of entropy is
required to protect against brute-force attacks [33]. Early analytical work to
quantify the impact on attacker workload has already been conducted; it
concludes that approximately 16-bits of entropy, corresponding to 65,536 unique
code addresses within a process image, are required to protect against brute force
attacks within reasonable timeframes i.e. 20 minutes. There also exist methods to
eliminate address space randomness through techniques that bypass the ASLR
implementation altogether using specially crafted format strings [34]. It is
interesting to note that ASLR was developed before the advent of return-oriented
programming as a general mitigation against static analysis. This speaks well of
the general approach of introducing diversity to deny surveillance.
13