Who invented aslr

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 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 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. Often these areas are mixed, for example stack frames are injected onto the stack and a library is returned into.

Where is the total amount of entropy:. 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 modern [update] bit systems, these numbers typically reach the millions at least. Proper implementations of ASLR, like that included in grsecurity , 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.

This supplies very little entropy. An approximation of the number of bits of entropy supplied per needed library appears 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 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. 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 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 bytes. 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 heap on the other hand is limited by the behavior of the memory allocator; in the case of glibc , allocations above KB 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 apparent to intrusion detection systems. This remains the most complete implementation, providing also kernel stack randomization from October onward.

It also continues to provide the most entropy for each randomized layout compared to other implementations. Linux has enabled a weak form of ASLR by default since kernel version 2. 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 bytes. This places the stack base in an area 8 MB wide containing possible positions; and the mmap base in an area 1 MB wide containing possible positions.

Position-independent executable PIE implements a random base address for the main executable binary and has been in place since It provides the same address randomness to the main executable as being used for the shared libraries. The prelink 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. ASLR in Solaris A security whitepaper from Symantec noted that ASLR in bit Windows Vista may not be as robust as expected, and Microsoft has acknowledged a weakness in its implementation.

A program may utilize computer memory to store data. The memory may be provided as physical memory e. An operating system OS may include a memory management functionality to allocate and manage a program address space for the program For example, in some embodiments, the OS may allocate one or more program code regions, one or more program data regions, a stack region, and one or more heap regions.

In some embodiments, the OS may restrict the program's memory access to the program address space In some embodiments, the program may access external functions, data, and other resources provided by shared libraries. The computer system and, in particular, the OS may implement various memory protection techniques to prevent an attacker from corrupting the address space used by program In general, it may be impractical or even impossible to prevent memory disclosures in arbitrary programs provided as commodity binary executables.

As a result, it can be assumed that an attacker is able to determine the location and contents of program memory regions, even if the region locations are randomized using ASLR.

In the embodiment of FIG. As will be described in more detail below, the re-randomizer component may be configured to re-randomize the location of code regions within the program address space at certain points throughout the program's execution.

In some embodiments, the re-randomizer component may include a kernel portion and a userspace portion. In certain embodiments, the re-randomizer component may be implemented, at least in part, as a kernel module e. In other embodiments, the re-randomizer component may be included directly in the kernel code e.

In other embodiments, the re-randomizer component may be provided as a userspace library. It is appreciated herein that output calls are a means by which an attacker can disclose vital memory, and that input calls are a means by which an attacker can influence the internal logical of the program. Accordingly, in some embodiments, the re-randomizer component keys re-randomization off one or more output calls followed by an input call.

The address space may be the same as or similar to program address space shown in FIG. The address space may include one or more regions, generally denoted In other embodiments, a program address space may include multiple instances of a given type of memory region, for example multiple program data regions e.

It will be appreciated that the various regions are exaggerated in size and relative positioning for illustrative reasons. In practice, a given memory region may be much smaller inside a vastly larger address space Each of the memory regions a - f has a base address that can be expressed as a value relative to the program address space In some embodiments, Address Space Layout Randomization ASLR may be used to determine an initial random location of one or more of the memory regions e.

In various embodiments, the location of one or more code regions may be randomly relocated at every output-input call pair. For example, as shown in FIG. By re-randomizing the program memory layout after one or more output system calls and before processing an input system call, the impact of memory disclosures may be mitigated because any information about the layout of memory that an attacker obtains at output time is stale by the time there is an opportunity to use that information e.

The computer system includes a compiler component and a memory space divided into kernel space and userspace regions. The annotated binary includes computer instructions and associated data that can be executed by an OS instance of the program i. The memory space corresponds to the full memory space used by the process, and may include a program code region in userspace and a re-randomizer component a , b generally denoted split between user and kernel space, as shown.

In addition, the compiler component may be configured to analyze the source code and generate information that can be used by the re-randomizer component to re-randomize the program's address space at arbitrary points throughout the program's runtime.

In some embodiments, the annotation information may be stored within a new section e. The additional section within the binary can be used by computer systems enabled with a re-randomizer component and ignored by other systems. In certain embodiments, the annotation information is sufficient to enable the re-randomizer component to randomly relocate one or more regions of program code , without affecting the program's correctness or causing it to crash.

In various embodiments, the compiler component uses techniques described below in conjunction with FIGS. In some embodiments, the source code may be provided as one or more files comprising program source code, and the annotated binary may be generated in the form of an executable file. In particular embodiments, the source code includes may include ISO C source code.

In one embodiment, the generated ELF file may include a debugging section in DWARF format to store annotation information used by the re-randomizer component In some embodiments, the compiler component may be provided as commercial or open source compiler that is modified or extended to generate annotation information.

The re-randomizer component , which may be the same as or similar to the re-randomizer component shown in FIG. In one embodiment, the kernel module may be provided as a Linux kernel module. The kernel component a may be configured to control the timing of re-randomization and handles certain other bookkeeping tasks, whereas the userspace component b may be configured to update the program state in response to a re-randomization.

In various embodiments, the kernel component a triggers re-randomization of the program's address space when an output-input call pair is detected.

When a re-randomization is triggered, the kernel component a may determine which regions of program memory should be relocated, In certain embodiments, the kernel component a checks each region within the program's address space in order to determine if it should be re-randomized.

In some embodiments, only code regions are relocated e. In particular embodiments, the kernel component a may perform this check once i. Once the list of memory regions to be relocated is determined, the kernel component a may select a new random memory address for each region.

The kernel component a may then make this addressing information available to the userspace component b , along with a copy of the current register set and other information that required by the userspace component b to update the program's state.

In certain embodiments, the kernel component a injects such information into the program's address space e. The kernel component a may then inject and transfer control to the userspace component b , which may perform various processing described below. After the userspace component b has completed its processing, control may return to the kernel component a. The kernel component a may update the register set of the original process if required and perform the actual move of the memory regions in question.

In certain embodiments, the program memory regions are moved by updating virtual memory page tables rather than by copying the contents of memory from one location to another. In various embodiments, when the kernel component b moves a code region, it may also move a corresponding GOT such that relative references from the code region to the GOT remain valid.

In certain embodiments, the kernel component a may update any kernel-stored references to the program's memory that may be affected by re-randomization. For example, the kernel component a may update the location of any signal handling functions set by the program if program code regions are relocated so that the kernel-stored code references remain valid. In various embodiments, kernel component a may perform various initialization and cleanup tasks as part of re-randomization.

To perform such tasks, the kernel component a may allocate and initialize data structures at program startup and destroyed them at shutdown. In some embodiments, the kernel component a determines whether re-randomization should be performed for a given program based on the presence of a special section within the binary For example, as discussed further below in conjunction with FIG.

The kernel component a may attempt to detect the presence of this special data section to determine if re-randomization should be performed.

Advantageously, the annotated binary can be executed by a computer system that does not include the re-randomizer component The userspace component b is configured to update the program's state in response to a re-randomization event. In some embodiments, the userspace component b updates code reference e. In various embodiments, the userspace component b uses techniques described below in conjunction with FIGS.

After the userspace component b has completed its work e. Thus, the userspace component b may be logically separate from the target program, but treated as part of the process for the duration of its existence and given full access to the program's memory. In particular embodiments, the kernel component a may inject a code region and a data region into the program's address space when re-randomization is triggered.

The code region may be populated with code corresponding to the userspace component b , and the data region may be populated with information required by the userspace component b to update code references e. Any memory regions injected into the program's address space may be removed after code references are updated.

In one embodiment, no state other than that used by the program itself is maintained within userspace between re-randomizations. In some embodiments, the re-randomizer component takes control over the program's execution when a re-randomization is triggered and does not return to the control to normal program flow until re-randomization is complete and the program's state is updated accordingly.

Each of the figures shows a program address space e. For clarity in the drawings, not all program memory regions are shown in the FIGS. Code references can be divided into three major categories: 1 references to code residing within the same compilation unit; 2 references to code residing in other compilation units; and 3 references to code that are assigned at runtime. Position-independent code uses relative offsets to access code within the same unit, rather than absolute references.

Because each code region moves as a block, relative offsets do not change and there are no references that require updating. Similarly, references to code residing in other compilation units may require no special action beyond standard compilation and linking options. References to code in other compilation units are generally not resolvable at the time of compilation, and thus are not assigned absolute addresses using standard compilation. Instead, references are made by relative offset into a GOT.

In various embodiments, each code region includes or is associated with a corresponding GOT. When a code region is randomly relocated, the re-randomizer component FIG. In certain embodiments, code references residing within the GOT itself may be updated, as subsequently described.

Unlike the first two categories of code references, it may be necessary to update runtime-assignable code references when program memory is re-randomized. To achieve this, the compiler component FIG. Function pointers can be manipulated, set, and explicitly invoked at will within program source code The compiler component may generate sufficient annotation information within the program binary to enable the re-randomization component to identify and update such references at arbitrary points during the program's execution.

Runtime-assignable code references can be divided into three sub-categories: a global variables, b local variables and return addresses residing on the stack, and c dynamic allocations.

Techniques for handling sub-categories a , b , and c are described below in conjunction with FIGS. Referring to FIG. The program has a global variable code reference e.

Global variables reside at fixed locations within the program data region , selected during compilation. Thus, in some embodiments, the compiler component FIG. The userspace component b FIG. In the example shown, the program includes a stack-based code reference that may be assigned a value within the code region , as shown. Stack-based code references can be identified at compilation time and exist in calculable locations.

The compiler component FIG. In certain embodiments, the compiler component uses existing compiler options that compute the locations at which variables are stored for each instruction, and that information is carried through the compilation process and emitted within the annotated binary e. In some embodiments, userspace component b may also update stack-based code references that happen to be stored within a register at the time re-randomization is triggered.

To allow for this, the kernel component a may make a copy of the register set when re-randomization commences, pass this copy to the userspace component b for updating, and then restore the register set from the updated copy when re-randomization completes and control is returned to the program.

Referring to FIGS. To address this issue, in certain embodiments, the compiler component FIG. A tagged union incorporates an extra data field to label the present data type stored in the union, and at each union assignment, the label is updated to mark it as storing a code reference or some other data type.

In one embodiment, the compiler component implements tagged unions based on the teaches of Rafkind, J. The DWARF debugging information may include a complete reference to all global and stack-based code references. At runtime, this data structure can be used in conjunction with stack unwinding to step back through each stack frame of the process and determine what variables were in use during each frame.

For each stack frame, the instruction pointer is used to query the interval tree and return a complete list of code references in use, and the memory addresses or registers in which they are located at that time.

Each pointer is updated in turn. Global variables and other global references, which reside at static locations, may also be queried via the DWARF interval tree but do not depend on the current instruction pointer. In the example shown, the program includes a dynamically allocated code reference e.

Unlike global and stack-based code references, the location of dynamically allocated code references cannot be determined at compilation time. Thus, in various embodiments, the compiler component FIG. In some embodiments, the compiler component generates instructions to record the memory locations of dynamically allocated code references within a table or other suitable data structure.

During runtime, as code references are dynamically allocated and deallocated, entries may be added and removed from the table. The userspace component b can iterate through this table to update the value of dynamically allocated code references whenever the code region is relocated.

In certain embodiments, the compiler component FIG. It some embodiments, the function signature of the custom allocator may be added to various stages of the compilation process to properly convey necessary information between compilation stages. For example, the statement:. In one embodiment, the compiler component generates a warning if a dynamic memory allocation does not use the sizeof operator.

For example, as shown, code region may include a relative reference to data region As discussed above, according to existing compiler techniques, external data references are automatically routed through a GOT In addition to data reference, the GOT may also store code references. In some embodiments, the re-randomization component may update code references stored within the GOT when the corresponding code regions are relocated.

Within the flow diagrams, rectangular elements typified by element in FIG. Alternatively, the processing blocks may represent steps performed by functionally equivalent circuits such as a digital signal processor DSP circuit or an application specific integrated circuit ASIC.