Home      Discussion      Topics      Dictionary      Almanac
Signup       Login
Address space layout randomization

Address space layout randomization

Discussion
Ask a question about 'Address space layout randomization'
Start a new discussion about 'Address space layout randomization'
Answer questions from other users
Full Discussion Forum
 
Encyclopedia
Address space layout randomization (ASLR) is a computer security
Computer insecurity
Computer insecurity refers to the concept that a computer system is always vulnerable to attack, and that this fact creates a constant battle between those looking to improve security, and those looking to circumvent security.-Security and systems design:...

 method which involves randomly arranging the positions of key data areas, usually including the base of the executable
Executable
In computing, an executable file causes a computer "to perform indicated tasks according to encoded instructions," as opposed to a data file that must be parsed by a program to be meaningful. These instructions are traditionally machine code instructions for a physical CPU...

 and position of libraries
Library (computer science)
In computer science, a library is a collection of resources used to develop software. These may include pre-written code and subroutines, classes, values or type specifications....

, heap, and stack
Stack-based memory allocation
Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out manner.In most modern computer systems, each thread has a reserved region of memory referred to as its stack. When a function executes, it may add some of its state data to the top of the...

, in a process's address space
Address space
In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.- Overview :...

.

Benefits


Address space randomization hinders some types of security attacks by making it more difficult for an attacker to predict target addresses. For example, attackers trying to execute return-to-libc attack
Return-to-libc attack
A return-to-libc attack is a computer security attack usually starting with a buffer overflow in which the return address on the stack is replaced by the address of another instruction and an additional portion of the stack is overwritten to provide arguments to this function...

s must locate the code to be executed, while other attackers trying to execute shellcode
Shellcode
In computer security, a shellcode is a small piece of code used as the payload in the exploitation of a software vulnerability. It is called "shellcode" because it typically starts a command shell from which the attacker can control the compromised machine. Shellcode is commonly written in...

 injected on the stack have to find the stack first. In both cases, the related memory addresses are obscured from the attackers. These values have to be guessed, and a mistaken guess is not usually recoverable due to the application crashing.

Effectiveness


Address space layout randomization relies on the low chance of an attacker guessing where randomly-placed areas are located. Security is increased by increasing the search space. Thus, address space randomization is more effective when more entropy
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...

 is present in the random offsets. Entropy is increased by either raising the amount of virtual memory
Virtual memory
In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...

 area space over which the randomization occurs or reducing the period over which the randomization occurs. The period is typically implemented as small as possible, so most systems must increase VMA space randomization.

To defeat the randomization, attackers must successfully guess the positions of all areas they wish to attack. For data areas such as stack and heap, where custom code or useful data can be loaded, more than one state can be attacked by using NOP slide
NOP slide
In computer CPUs, a NOP slide, NOP sled or NOP ramp is a sequence of NOP instructions meant to "slide" the CPU's instruction execution flow to its final, desired, destination...

s for code or repeated copies of data. This allows an attack to succeed if the area is randomized to one of a handful of values. In contrast, code areas such as library base and main executable need to be discovered exactly. Often these areas are mixed, for example stack frames are injected onto the stack and a library is returned into.

To begin, let us declare the following variables:


To calculate the probability of an attacker succeeding, we have to assume a number of attempts carried out without being interrupted by a signature-based IPS, law enforcement, or other factor; in the case of brute forcing, the daemon cannot be restarted. We also have to figure out how many bits are relevant and how many are being attacked in each attempt, leaving however many bits the attacker has to defeat.

The following formulas represent the probability of success for a given set of attempts on bits of entropy.



In many systems, can be in the thousands or millions; on 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...

 systems, these numbers typically reach the millions at least. For 32-bit systems at 2004 computer speeds which have 16 bits for address randomization, Shacham and co-workers state "… 16 bits of address randomization can be defeated by a brute force attack
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...

 within minutes." It should be noted that the authors' statement depends on the ability to attack the same application multiple times without any delay. Proper implementations of ASLR, like that included in grsecurity
Grsecurity
grsecurity is a set of patches for the Linux kernel with an emphasis on enhancing security. Its typical application is in computer systems that accept remote connections from untrusted locations, such as web servers and systems offering shell access to its users.Released under the GNU General...

, provide several methods to make such brute force attacks infeasible. One method involves preventing an executable from executing for a configurable amount of time if it has crashed a certain number of times.

Some systems implement Library Load Order Randomization, a form of ASLR which randomizes the order in which libraries are loaded. This supplies very little entropy. An approximation of the number of bits of entropy supplied per needed library is shown below; this does not yet account for varied library sizes, so the actual entropy gained is really somewhat higher. Note that attackers usually need only one library; the math is more complex with multiple libraries, and shown below as well. Note that the case of an attacker using only one library is a simplification of the more complex formula for .



These values tend to be low even for large values of , most importantly since attackers typically can use only the C standard library
C standard library
The C Standard Library is the standard library for the programming language C, as specified in the ANSI C standard.. It was developed at the same time as the C POSIX library, which is basically a superset of it...

 and thus one can often assume that . Interestingly, however, even for a small number of libraries there are a few bits of entropy gained here; it is thus potentially interesting to combine library load order randomization with VMA address randomization to gain a few extra bits of entropy. Note that these extra bits of entropy will not apply to other mmap segments, only libraries.

Reducing entropy


Attackers may make use of several methods to reduce the entropy present in a randomized address space, ranging from simple information leaks to attacking multiple bits of entropy per attack (such as by heap spraying). There is little that can be done about this.

It is possible to leak information about memory layout using format string vulnerabilities. Format string functions such as printf
Printf
Printf format string refers to a control parameter used by a class of functions typically associated with some types of programming languages. The format string specifies a method for rendering an arbitrary number of varied data type parameter into a string...

use a variable argument list to do their job; format specifiers describe what the argument list looks like. Because of the way arguments are typically passed, each format specifier moves closer to the top of the stack frame. Eventually, the return pointer and stack frame pointer can be extracted, revealing the address of a vulnerable library and the address of a known stack frame; this can completely eliminate library and stack randomization as an obstacle to an attacker.

One can also decrease entropy in the stack or heap. The stack typically must be aligned to 16 bytes, and so this is the smallest possible randomization interval; while the heap must be page-aligned, typically 4096 bytes. When attempting an attack, it is possible to align duplicate attacks with these intervals; a NOP slide
NOP slide
In computer CPUs, a NOP slide, NOP sled or NOP ramp is a sequence of NOP instructions meant to "slide" the CPU's instruction execution flow to its final, desired, destination...

 may be used with shellcode injection, and the string '/bin/sh' can be replaced with '////////bin/sh' for an arbitrary number of slashes when attempting to return to system. The number of bits removed is exactly for intervals attacked.

Such decreases are limited due to the amount of data in the stack or heap. The stack, for example, is typically limited to 8 MB
Megabyte
The megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...

 and grows to much less; this allows for at most 19 bits, although a more conservative estimate would be around 8–10 bits corresponding to 4–16 KB
Kilobyte
The kilobyte is a multiple of the unit byte for digital information. Although the prefix kilo- means 1000, the term kilobyte and symbol KB have historically been used to refer to either 1024 bytes or 1000 bytes, dependent upon context, in the fields of computer science and information...

 of stack stuffing. The heap on the other hand is limited by the behavior of the memory allocator; in the case of glibc, allocations above 128 KB are created using mmap
Mmap
In computing, mmap is a POSIX-compliant Unix system call that maps files or devices into memory. It is a method of memory-mapped file I/O. It naturally implements demand paging, because initially file contents are not entirely read from disk and do not use physical RAM at all...

, limiting attackers to 5 bits of reduction. This is also a limiting factor when brute forcing; although the number of attacks to perform can be reduced, the size of the attacks is increased enough that the behavior could in some circumstances become apparent to intrusion detection systems.

History


The PaX
PaX
PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. The least-privilege approach allows computer programs to do only what they have to do in order to be able to execute properly, and nothing more. PaX was first released in 2000.PaX flags data memory as...

 project first coined the term "ASLR". It published the first design and implementation of ASLR in July, 2001. This remains the most complete implementation, providing also kernel stack randomization from October 2002 onward. It also continues to provide the most entropy for each randomized layout compared to other implementations.

OpenBSD


Two years after ASLR was invented and published as part of PaX, a popular security patch for Linux, OpenBSD
OpenBSD
OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...

 became the first mainstream operating system to support partial ASLR (and to activate it by default).
OpenBSD completed its ASLR support after Linux in 2008 when it added support for PIE binaries.

Linux


Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

 has enabled a weak form of ASLR by default since kernel version 2.6.12 (released June 2005). The PaX
PaX
PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. The least-privilege approach allows computer programs to do only what they have to do in order to be able to execute properly, and nothing more. PaX was first released in 2000.PaX flags data memory as...

 and Exec Shield
Exec Shield
Exec Shield is a project started at Red Hat, Inc in late 2002 with the aim of reducing the risk of worm or other automated remote attacks on Linux systems. The first result of the project was a security patch for the Linux kernel that emulates an NX bit on x86 CPUs that lack a native NX...

 patchsets to the Linux kernel provide more complete implementations. Various Linux distributions including Adamantix, Alpine Linux
Alpine Linux
Alpine Linux is a Linux distribution based on uClibc and BusyBox, which has the goal of being lightweight and secure by default while still being useful for general-purpose tasks. Alpine Linux uses PaX and grsecurity patches in the default kernel and compiles all packages with stack-smashing...

, Hardened Gentoo
Hardened Gentoo
Hardened Gentoo is a project of Gentoo Linux that is enhancing the distribution with security addons. Current security enhancements to Gentoo Linux can be:*SELinux**A system of mandatory access controls...

, and Hardened Linux From Scratch come with PaX's implementation of ASLR by default.

The Exec Shield patch for Linux supplies 19 bits of stack entropy on a period of 16 bytes; and 8 bits of mmap base randomization on a period of 1 page of 4096 bytes. This places the stack base in an area 8 MB wide containing 524 288 possible positions; and the mmap base in an area 1 MB wide containing 256 possible positions.

Position-independent executable (PIE) feature implements random base address for the main executable binary since 2003. It provides the same address randomness to the main executable as being used for the shared libraries. The PIE feature is in use only for the network facing daemons – the PIE feature cannot be used together with the prelink
Prelink
prelink is a free program written by Jakub Jelínek of Red Hat for POSIX-compliant operating systems, principally Linux . It is intended to speed up a system by reducing the time a program needs to begin...

 feature for the same executable.

The prelink
Prelink
prelink is a free program written by Jakub Jelínek of Red Hat for POSIX-compliant operating systems, principally Linux . It is intended to speed up a system by reducing the time a program needs to begin...

 tool implements randomization at prelink time rather than runtime, because by design prelink aims to handle relocating libraries before the dynamic linker has to, which allows the relocation to occur once for many runs of the program. As a result, real address space randomization would defeat the purpose of prelinking.

Microsoft Windows


Microsoft's Windows Vista
Windows Vista
Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...

 (released January 2007), Windows Server 2008, Windows 7, and Windows Server 2008 R2
Windows Server 2008 R2
Windows Server 2008 R2 is a server operating system produced by Microsoft. It was released to manufacturing on July 22, 2009 and launched on October 22, 2009. According to the Windows Server Team blog, the retail availability was September 14, 2009. It is built on Windows NT 6.1, the same core...

 have ASLR enabled by default, although only for those executables and dynamic link libraries specifically linked to be ASLR-enabled. This did not include Internet Explorer 7
Internet Explorer 7
Windows Internet Explorer 7 is a web browser released by Microsoft in October 2006. Internet Explorer 7 is part of a long line of versions of Internet Explorer and was the first major update to the browser in more than 5 years...

 on Windows Vista prior to Service Pack 1; ASLR and Data Execution Prevention
Data Execution Prevention
Data Execution Prevention is a security feature included in modern operating systems.It is known to be available in Linux, Mac OS X, and Microsoft Windows operating systems and is intended to prevent an application or service from executing code from a non-executable memory region. This helps...

 (DEP) are both disabled for application compatibility purposes. Newer versions, including Internet Explorer 8
Internet Explorer 8
Windows Internet Explorer 8 is a web browser developed by Microsoft in the Internet Explorer browser series. The browser was released on March 19, 2009 for Windows XP, Windows Server 2003, Windows Vista, Windows Server 2008, and Windows 7. Both 32-bit and 64-bit builds are available...

 (released March 2009), enable these protections. A registry setting is available to forcibly enable or disable ASLR for all executables and libraries, found at "HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management\MoveImages". ASLR can be disabled in Windows 7, by using the Enhanced Mitigation Experience Toolkit provided by Microsoft, (the MoveImages registry setting has no effect in Windows 7).

The locations of the heap, stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...

, Process Environment Block, and Thread Environment Block
Win32 Thread Information Block
In computing, the Win32 Thread Information Block is a data structure in Win32 on x86 that stores info about the currently running thread. This structure is also known as the Thread Environment Block ....

 are also randomized. A security whitepaper from Symantec noted that ASLR in 32-bit Windows Vista may not be as robust as expected, and Microsoft has acknowledged a weakness in its implementation.

Host-based intrusion prevention systems such as WehnTrust and Ozone also offer ASLR for Windows XP
Windows XP
Windows XP is an operating system produced by Microsoft for use on personal computers, including home and business desktops, laptops and media centers. First released to computer manufacturers on August 24, 2001, it is the second most popular version of Windows, based on installed user base...

 and Windows Server 2003
Windows Server 2003
Windows Server 2003 is a server operating system produced by Microsoft, introduced on 24 April 2003. An updated version, Windows Server 2003 R2, was released to manufacturing on 6 December 2005...

 operating systems; however complete details of their implementation are not available.

Mac OS X


Apple introduced randomization of some library offsets in Mac OS X v10.5
Mac OS X v10.5
Mac OS X Leopard is the sixth major release of Mac OS X, Apple's desktop and server operating system for Macintosh computers. Leopard was released on 26 October 2007 as the successor of Tiger , and is available in two variants: a desktop version suitable for personal computers, and a...

 (released October 2007). Their implementation does not provide complete protection against attacks which ASLR is designed to defeat. Mac OS X Lion
Mac OS X Lion
Mac OS X Lion is the eighth and current major release of Mac OS X, Apple's desktop and server operating system for Macintosh computers....

 10.7 has improved ASLR implementation for all applications. Apple explains that "address space layout randomization (ASLR) has been improved for all applications. It is now available for 32-bit apps (as are heap memory protections), making 64-bit and 32-bit applications more resistant to attack."

iOS (iPhone, iPod touch, iPad)


Apple introduced ASLR in iOS
IOS
iOS is an operating system for iPad, iPhone, iPod Touch, and Apple TV.IOS may also refer to:-Companies and organisations:* Illinois Ornithological Society, American state-based bird club...

 4.3. This makes it harder to jailbreak the iDevice, and stops apps from breaking the device accidentally.

Android


The upcoming Android 4.0 Ice Cream Sandwich provides address space layout randomization (ASLR) to help protect system and third party applications from exploits due to memory-management issues.

See also

  • Buffer overflow
    Buffer overflow
    In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....

  • Stack buffer overflow
    Stack buffer overflow
    In software, a stack buffer overflow occurs when a program writes to a memory address on the program's call stack outside of the intended data structure; usually a fixed length buffer....

  • Stack-smashing protection
    Stack-smashing protection
    Buffer overflow protection refers to various techniques used during software development to enhance the security of executable programs by detecting buffer overflows on stack-allocated variables as they occur and preventing them from becoming serious security vulnerabilities...

  • NX bit
    NX bit
    The NX bit, which stands for No eXecute, is a technology used in CPUs to segregate areas of memory for use by either storage of processor instructions or for storage of data, a feature normally only found in Harvard architecture processors...

  • Information entropy
    Information entropy
    In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...

  • Heap spraying

External links