Security

Prelink and address space randomization

Prelink (PDF) is a popular tool used to decrease program load time, shortening system boot time and making applications start faster. Developed by Jakob Jelinek at Red Hat, prelink relocates libraries on disk to save dynamic linking time.

When the dynamic linker loads a dynamically linked ELF binary, it has to also load and link all of the libraries before executing the program's entry point, _main(). This process involves relocating libraries—changing all addresses referenced in the library to reflect the actual addresses in memory. Relocating libraries involves iterating through each address in the library and replacing it with the real address as determined by the library's location in the process's virtual address space. Most relocations happen in the symbol table and PLT; but in rare cases there are also .text relocations which require fixed-position executable code to be patched in a slightly slower process.

The relocation process will slow down an application's launch. In order to speed up the process, prelink relocates the libraries ahead of time. This is done by scanning every executable to be prelinked, generating a graph of libraries that will be loaded at the same time as other libraries, and then calculating target addresses for each library at such that it will never be loaded at the same address as other libraries. These offsets are then stored in the shared object files themselves, and the symbol tables and segment addresses are all adjusted to reflect addresses based on the chosen base address.

Once prelink has done its job, the dynamic linker no longer has to concern itself with relocation. Libraries are loaded at the address specified in the library header and the symbol table is already correct. If anything forces the library to be loaded at a different address, then the library is relocated appropriately as usual; otherwise we can say goodbye to the load-time overhead of relocating libraries.

Kernel facilities supplying address space layout randomization for libraries cannot be used in conjunction with prelink; to do so would require relocating the libraries, defeating the purpose of prelinking. Address space randomization is a core feature of secure systems such as OpenBSD, Adamantix, Hardened Gentoo, Fedora Core, and Red Hat Enterprise Linux. It has appeared as part of PaX as well as part of Ingo Molnar's Exec Shield, and has been accepted into the mainline kernel as of 2.6.12 after submission by Arjan van de Ven.

The simple purpose of address space randomization is to make it more difficult to perform certain classes of attacks by changing where in memory important segments for the attack are loaded. If an attacker wants to execute injected shell code or manipulate the program to execute out of order, he obviously has to know where that code is. By shuffling memory segments around, these attacks become quite difficult; the chances of successful attack are mathematically described in the PaX documentation and Wikipedia.

In an attempt to restore some of the benefits of address space randomization, prelink is capable of randomly selecting the addresses used for prelinking. This makes it more difficult to perform certain attacks on a system, because the addresses used are unique to that system. This approach is, however, less effective than per-process randomization because the addresses stay constant until prelink is run again.

There is another implication that has to be examined with prelink. To understand this implication, let us first review a feature of prelink by examining the load address of the C standard library in two processes: a user-owned 'cat' and a root-owned 'bash'. The C standard library is interesting because, in practice, virtually all return-to-libc attacks utilize it exclusively.

 user@icebox:~$ cat /proc/self/maps | grep libc | grep r-xp
 4df2e000-4e053000 r-xp 00000000 08:07 81197      /lib/tls/i686/cmov/libc-2.3.6.so
 user@icebox:~$ sudo -s
 root@icebox:/home/user# cat /proc/$$/maps | grep libc | grep r-xp
 4df2e000-4e053000 r-xp 00000000 08:07 81197      /lib/tls/i686/cmov/libc-2.3.6.so

Closely examining these quickly verifies that the address of glibc's executable code is the same between these two processes; this is consistent with the behavior of prelink. Because the library itself is relocated ahead of time, there is a preference for the dynamic linker to load it at that address. Examination of libc itself yields the below.

 user@icebox:~$ readelf -S /lib/tls/i686/cmov/libc-2.3.6.so | head -n 6
 There are 64 section headers, starting at offset 0x12d114:
 
 Section Headers:
   [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
   [ 0]                   NULL            00000000 000000 000000 00      0   0  0
   [ 1] .note.ABI-tag     NOTE            4df2e154 000154 000020 00   A  0   0  4

Computing 4df2e154 - 154, the address and offset taken from any given non-NULL segment, yields 4df2e000, the base address of libc. This makes sense; prelink rewrites the segment and symbol addresses for the library based on a specific load address, and the dynamic linker loads the library at that address to avoid relocating it. Further, any program that links with libc has to be able to read libc, and will thus be able to derive the same information.

All of this means that any program on the system using any prelinked library will be able to leak information about higher privileged tasks using the same library. This allows any attacker able to gain any form of local access—or more directly any ability to read libc—to gain information about the address space layout of higher privileged processes, including the load address of libc. As we know, this information is extremely valuable to an attacker wanting to exploit a privileged process without brute forcing library load addresses.

This vulnerability only applies to attackers with local access; but this is not an unreasonable requirement. Many web hosting companies give local shell access or allow PHP; either of these can be used to remotely fetch a copy of libc. Due to the nature of the dynamic linker and sane security design, the dynamic linker is exactly as privileged as the process it is starting; therefor, even the most stringent mandatory access policies on systems such as SELinux, grsecurity, or AppArmor cannot prevent this attack.

Besides avoiding prelinking, there is one other way to prevent this information leak from being exploited. All processes linked to a prelinked library need access to the library file and load that library at the same address; the point of exposure is the use of the same copy of the library. In order to prevent information leaking, then, you must have separate copy of each library common between any two programs you don't want to leak information about each other. This can be done with Xen, chroot jails, UML, or simply isolated machines, as long as the directory hierarchies are individually prelinked with prelink randomization. Each system will have a different set of addresses from every other system in this scheme. This of course requires more hardware, more disk space, more management, more memory, and more work.

The direct implications of this information leak depend on your exact security concerns. A web hosting company, for example, may not want to run prelink on its servers, given the risk of effectively losing the benefit of address space randomization. A home desktop, on the other hand, may only have to worry about a trojan using the information leak to stage an attack on a system service such as cups or dbus—and should probably worry about /proc/PID/maps first. While these are both essentially the concern of an attacker with local access, the likelihood of attack and the value of potential damages are different.

The prelink tool gives a useful decrease in program load time, and can help users reach their desktop and the programs they need to run more quickly. It does however have some unfortunate repercussions that must be examined, especially in security-sensitive environments relying on address space randomization.

Comments (16 posted)

New vulnerabilities

acroread: unspecified security problems

Comments (1 posted)

kernel: denial of service

Comments (none posted)

kiax: arbitrary code execution

Comments (none posted)

openoffice.org: several vulnerabilities

Comments (none posted)

opera: integer overflow and SSL spoof

Comments (none posted)

tikiwiki: multiple vulnerabilities

Comments (none posted)

Updated vulnerabilities

asterisk: buffer overflow

Comments (none posted)

binutils: buffer overflow

Comments (none posted)

busybox: insecure password generation

Comments (2 posted)

bzip2: race condition and infinite loop

Comments (2 posted)

ktools: buffer overflow

Comments (none posted)

courier: denial of service

Comments (none posted)

cpio: arbitrary code execution

Comments (none posted)

vixie-cron: privilege escalation

Comments (1 posted)

Cyrus-SASL: DIGEST-MD5 Pre-Authentication Denial of Service

Comments (none posted)

EnergyMech: denial of service

Comments (none posted)

freetype: integer overflows

Comments (none posted)

gdb: multiple vulnerabilities

Comments (5 posted)

gdm: improper file permissions

Comments (none posted)

gnupg: remote denial of service

Comments (1 posted)

gzip: arbitrary command execution

Comments (2 posted)

Hashcash: possible heap overflow

Comments (none posted)

horde: missing input sanitizing

Comments (none posted)

ImageMagick: heap overflow vulnerability

Comments (none posted)

kdebase: local root vulnerability

Comments (none posted)

kdebase: privilege escalation

Comments (none posted)

kdelibs: kate backup file permission leak

Comments (none posted)

kernel: multiple vulnerabilities

Comments (none posted)

kernel: netfilter memory corruption

Comments (none posted)

kernel: multiple vulnerabilities

Comments (none posted)

kernel: information disclosure

Comments (none posted)

libgadu: memory alignment bug

Comments (none posted)

libgd2: denial of service

Comments (none posted)

libmms: buffer overflows

Comments (none posted)

libpam-ldap: authentication bypass

Comments (none posted)

libtiff: buffer overflow

Comments (none posted)

mozilla products have multiple vulnerabilities

Comments (none posted)

mpg123: buffer overflows

Comments (none posted)

mutt: IMAP namespace buffer overflow

Comments (none posted)

mysql: denial of service

Comments (none posted)

MySQL: logging bypass

Comments (2 posted)

ntp: uses wrong gid

Comments (none posted)

openmotif: buffer overflows

Comments (none posted)

OpenSSH: double shell expansion

Comments (none posted)

shadow: privilege escalation

Comments (none posted)

perl: setuid vulnerabilities

Comments (none posted)

php: multiple vulnerabilities

Comments (none posted)

phpbb2: missing input sanitizing

Comments (none posted)

phpbb2: multiple vulnerabilities

Comments (none posted)

phpMyAdmin: multiple vulnerabilities

Comments (none posted)

pinball: privilege escalation

Comments (none posted)

png: buffer overflow

Comments (none posted)

postgresql: SQL injection