FACTOID # 20: Statistically, Delaware bears more cost of the US Military than any other state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Address space layout randomization

Address space layout randomization (ASLR) is a computer security technique which involves arranging the positions of key data areas, usually including the base of the executable and position of libraries, heap, and stack, randomly in a process' address space. Many current computer systems have limited security precautions in place. ... Illustration of an application which may use libvorbisfile. ... In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In computing, a process is a running instance of a program, including all variables and other state. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...

Contents

Benefits

Address space randomization hinders some types of security attack by preventing an attacker being able to easily predict target addresses. For example attackers trying to execute return-to-libc attacks must locate the code to be executed; while other attackers trying to execute shellcode injected on the stack have to first find the stack. 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. 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 function in the program. ... A shellcode is a relocatable piece of machine code used as the payload in the exploitation of a software bug which allows an unauthorised user to communicate with the computer via the operating systems command line as a result of exploiting a vulnerability in software running on the machine. ...


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 is present in the random offsets. Entropy is increased by either raising the amount of virtual memory area space the randomization occurs over, or reducing the period the randomization occurs over; the period is typically implemented as small as possible, so most systems must increase VMA space randomization. see also: Entropy (disambiguation) Ice melting - classic example of entropy increasing[1] described in 1862 by Rudolf Clausius as an increase in the disgregation of the molecules of the body of ice. ... It has been suggested that this article be split into multiple articles. ...


To defeat the randomization, an attacker must successfully guess the positions of all areas he is attacking. 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 slides 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. Oftentimes these areas are mixed, for example stack frames are injected onto the stack and a library is returned into. In computing, a stack frame is a data structure used to create temporary storage for data and saved state in functions. ...


To begin, let us declare the following variables:

Es = entropy bits of stack top
Em = entropy bits of mmap() base
Ex = entropy bits of main executable base
Eh = entropy bits of heap base
As = attacked bits per attempt of stack entropy
Am = attacked bits per attempt of mmap() base entropy
Ax = attacked bits per attempt of main executable entropy
Ah = attacked bits per attempt of heap base entropy
N = EsAs + EmAm + ExAx + EhAh

To calculate the probability of an attacker succeeding, we have to assume a number of attempts are to be 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 N bits of entropy.

In many systems, 2N can be in the thousands or millions; on modern 64-bit systems, these numbers typically reach the millions at least. In computing, a 64-bit component is one in which data are processed or stored in 64-bit units (words). ...


Some systems implement Library Load Order Randomization, a form of ASLR where the order in which libraries are loaded is randomized. 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 l = 1.

l = number of libraries loaded

These values tend to be low even for large values of l, most importantly since attackers typically can use only the C standard library and thus it can often be assumed . 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. The C standard library is a now-standardised collection of header files and library routines used to implement common operations, such as input/output and string handling, in the C programming language. ...


Reducing entropy

There are several ways for an attacker to reduce the entropy present in a randomized address space, ranging from simple information leaks to attacking multiple bits of entropy per attack. We have unfortunately little control over this.


It is possible to leak information about memory layout using format string vulnerabilities. Format string functions such as printf() 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. Format string attacks are a new class of vulnerabilities discovered around 1999, previously thought harmless. ... Several programming languages implement a printf function, to output a formatted string. ... In computer programming, a variadic function is a function of variable arity; that is, one which can take different numbers of arguments. ...


It is also possible to 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 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 n intervals attacked.


Such decreases are limited due to the amount of data that can be stuffed in the stack or heap. The stack, for example, is typically limited to 8MiB 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-16KiB 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 128KiB are created using mmap(), 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 anomalous to intrusion detection systems. Glibc is the GNU projects C standard library, licensed under the LGPL. The lead contributor and maintainer is Ulrich Drepper. ... In computing, mmap() is a POSIX-compliant Unix system call that maps files or devices into memory. ... An Intrusion Detection System or IDS is a software tool used to detect unauthorised access to a computer system or network. ...


Implementations

Several security systems implement ASLR, notably OpenBSD; PaX and Exec Shield for Linux (but in most linux distributions it's not installed). Under Adamantix and Hardened Gentoo, ASLR protection, SSP protection Stack-Smashing Protector and PaX Page eXecution Hardened Linux From Scratch also features PaX ASLR. OpenBSD is a freely available Unix-like computer operating system descended from Berkeley Software Distribution (BSD), a Unix derivative developed at the University of California, Berkeley. ... In computer security, PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. ... Exec-shield is a kernel patch enabling new security features in the Linux operating system. ... Linux, or GNU/Linux, refers to any Unix-like computer operating system which uses the Linux kernel. ... Adamantix, also known as Trusted Debian, is a security focused operating system based on Debian GNU/Linux. ... Hardened Gentoo is a version of Gentoo Linux that has been enhanced with security addons. ... The Stack-Smashing Protector (sometimes called SSP, formerly known as ProPolice) is an extension to the GNU Compiler Collection that helps mitigate the damage that can be done by buffer overflow-based attacks. ... In computer security, PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. ... In computer security, PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. ...


Mainline Linux since version 2.6.12 has included the Exec Shield code for address space layout randomization, which 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 8MiB wide containing 524288 possible positions; and the mmap() base in an area 1MiB wide containing 256 possible positions.


The prelink tool implements randomization at prelink time due to a deficiency of the design of prelink. The goal of prelink is to handle relocating libraries before the dynamic linker has to, which allows the relocation to occur once for many runs of the program. Because of this, real address space randomization would defeat the purpose of prelinking. prelink is a Free program written by Jakub Jelinek of Red Hat for POSIX-compliant operating systems, principally Linux (because it modifies ELF executables). ...


Windows Vista has ASLR enabled by default - however only for binaries which are linked to be ASLR enabled. ‹ The template below has been proposed for deletion. ...


References


  Results from FactBites:
 
Address space layout randomization - Wikipedia, the free encyclopedia (1213 words)
Address space layout randomization (ASLR) is a computer security technique which involves arranging the positions of key data areas, usually including the base of the executable and position of libraries, heap, and stack, randomly in a process' address space.
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.
Entropy is increased by either raising the amount of virtual memory area space the randomization occurs over, or reducing the period the randomization occurs over; the period is typically implemented as small as possible, so most systems must increase VMA space randomization.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m