User: Password:
Subscribe / Log in / New account


Prelink and address space randomization

July 5, 2006

This article was contributed by John Richard Moser

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/
 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/

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/ | 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

Package(s):acroread CVE #(s):CVE-2006-3093
Created:July 4, 2006 Updated:July 5, 2006
Description: Various unspecified security problems have been fixed in Acrobat Reader version 7.0.8. Adobe does not provide detailed information about the nature of the security problems. Therefore, it is necessary to assume that remote code execution is possible.
SuSE SUSE-SA:2006:041 acroread 2006-07-04

Comments (1 posted)

kernel: denial of service

Package(s):kernel CVE #(s):CVE-2006-2934
Created:July 5, 2006 Updated:July 7, 2006
Description: The netfilter SCTP connection tracking code can crash when faced with a "packet without chunks." This vulnerability was fixed in the kernel release.
Trustix TSLSA-2006-0040 kernel 2006-07-07
Fedora FEDORA-2006-772 kernel 2006-07-05
Fedora FEDORA-2006-769 kernel 2006-07-05

Comments (none posted)

kiax: arbitrary code execution

Package(s):kiax CVE #(s):CVE-2006-2923
Created:June 30, 2006 Updated:July 5, 2006
Description: The iax_net_read function in the iaxclient library fails to properly handle IAX2 packets with truncated full frames or mini-frames. These frames are detected in a length check but processed anyway, leading to buffer overflows.
Gentoo 200606-30 kiax 2006-06-30

Comments (none posted) several vulnerabilities

Package(s) CVE #(s):CVE-2006-2198 CVE-2006-2199 CVE-2006-3117
Created:June 30, 2006 Updated:January 4, 2007
Description: Several vulnerabilities have been discovered in, a free office suite.
  • It turned out to be possible to embed arbitrary BASIC macros in documents in a way that does not see them but executes them anyway without any user interaction. (CVE-2006-2198)
  • It is possible to evade the Java sandbox with specially crafted Java applets. (CVE-2006-2199)
  • Loading malformed XML documents can cause buffer overflows and cause a denial of service or execute arbitrary code. (CVE-2006-3117)
Fedora FEDORA-2007-005 2007-01-03
rPath rPSA-2006-0173-1 2006-09-26
Gentoo 200607-12 openoffice 2006-07-28
Ubuntu USN-313-2 openoffice.org2-amd64, openoffice.org2 2006-07-19
Ubuntu USN-313-1 2006-07-11
Mandriva MDKSA-2006:118 2006-07-07
Debian DSA-1104-2 2006-07-06
Red Hat RHSA-2006:0573-01 2006-07-03
SuSE SUSE-SA:2006:040 OpenOffice_org 2006-07-03
Fedora FEDORA-2006-770 2006-07-03
Fedora FEDORA-2006-764 2006-06-30
Debian DSA-1104-1 2006-06-30

Comments (none posted)

opera: integer overflow and SSL spoof

Package(s):opera CVE #(s):CVE-2006-3198 CVE-2006-3331
Created:July 3, 2006 Updated:July 5, 2006
Description: Opera before version 9.0 has an integer overflow vulnerability due to the improper handling of JPEG files. Also Opera did not reset the SSL security bar after displaying a download dialog from an SSL-enabled website, which could allow remote attackers to spoof a trusted SSL certificate from an untrusted website and facilitate phishing attacks.
SuSE SUSE-SA:2006:038 opera 2006-07-03

Comments (none posted)

tikiwiki: multiple vulnerabilities

Package(s):tikiwiki CVE #(s):CVE-2006-3048 CVE-2006-3047
Created:June 29, 2006 Updated:July 5, 2006
Description: The Tikiwiki content management system has an SQL injection vulnerability due to insufficient input sanitization. An attacker may be able to execute arbitrary SQL statements or inject arbitrary scripts into the user's browser.
Gentoo 200606-29 tikiwiki 2006-06-29

Comments (none posted)

Page editor: Jonathan Corbet
Next page: Kernel development>>

Copyright © 2006, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds