PaX
|
|
In computer security, PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. This approach allows computer programs to do only what they have to be able to do to execute properly, and nothing more. PaX was first released in 2000.
PaX flags data memory as non-executable and program memory as non-writable, and randomly arranges the program memory. This effectively prevents many security exploits, such as those stemming from buffer overflows. The former prevents direct code injection absolutely, while the latter makes so-called return-to-libc (ret2libc) attacks indeterminate, relying on luck to succeed.
PaX was written by The PaX Team. The principal author of PaX currently wishes to remain anonymous; the reasoning for this decision is not known.
| Contents |
Why PaX is significant
Many, and perhaps even most, computer insecurities are due to errors in programs that make it possible to alter the function of the program, effectively allowing a program to be "rewritten" while running. The first 44 Ubuntu Linux Security Notices can be categorized (https://www.ubuntulinux.org/wiki/USNAnalysis) to show that 41% of vulnerabilities stem from buffer overflows, 11.4% from integer overflows, and 15.9% from other bad handling of malformed data. These types of bugs often open the possibility to inject and execute foreign code, or execute existing code out of order, and make up 61.4% of the sample group, discarding overlap. This analysis is very crude; a more comprehensive analysis of individual vulnerabilities would likely give very different numbers, possibly higher or lower.
Many worms, viruses, and attempts to take over a machine rely on changing the contents of memory so that the malware code is executed; or on executing "data" contents by misdirection. If execution of such malware could be blocked, it could do little or even no damage even after being installed on a computer; many, such as the Sasser worm, could be prevented from being installed at all.
PaX was designed to do just that for a large number of possible attacks, and to do so in a very generally applicable way. It prevents execution of improper code by controlling access to memory (read, write, or execute access; or combinations thereof) and is designed to do so without interfering with execution of proper code. At the cost of a small amount of overhead, PaX reduces many security exploits to a denial of service (DoS); exploits which would normally give attackers root access, allow access to important information on a hard drive, or cause other damage will instead cause the affected program or process to crash with little effect on the rest of the system.
A DoS attack (or its equivalent) is generally an annoyance, and may in some situations cause loss of time or resources (e.g. lost sales for a business whose website is affected); however, no data should be compromised when PaX intervenes, as no information will be improperly copied elsewhere. Nevertheless, the equivalent of a DoS attack is in some environments unacceptable; some businesses have level of service contracts or other conditions which make successful intruder entry a less costly problem than loss of or reduction in service. The PaX approach is thus not well suited to all circumstances; however, in many cases, it is an acceptable method of protecting confidential information by preventing successful security breaches.
Many, but not all, programming bugs cause memory corruption. Of those that do, and are triggerable by intent, some will make it possible to induce the program to do various things it wasn't meant to, such as give a high-privileged shell. The focus of PaX is not on the finding and fixing of such bugs, but rather on prevention and containment of exploit techniques which may stem from such programmer error. A subset of these bugs will be reduced in severity; programs terminate, rather than improperly provide service.
PaX does not directly prevent buffer overflows; instead, it effectively prevents many of these and related programming bugs from being used to gain unauthorized entry into a computer system. Other systems such as Stack-smashing Protector and StackGuard do attempt to directly detect buffer overflows, and kill the offending program when identified; this approach is called stack-smashing protection, and attempts to block such attacks before they can be made. PaX's more general approach, on the other hand, prevents damage after the attempt begins. Although both approaches can achieve some of the same goals, they are not entirely redundant. Therefore, employing both will, in principle, make an operating system more secure. Some Linux distributions already use the PaX with Stack Smash Protection combination.
As of mid 2004, PaX has not been submitted for the mainline kernel tree because The PaX Team does not think it yet appropriate; although PaX is fully functional on many CPU architectures, including the popular x86 architecture used by most, it still remains partially or fully unimplemented on some architectures. Those that PaX is effective on include IA-32 (x86), AMD64, IA-64, Alpha, PA-RISC, and 32 and 64 bit MIPS, PowerPC, and Sparc architectures.
Limitations of PaX
PaX cannot block fundamental design flaws in either executable programs or in the kernel that allow an exploit to abuse supplied services, as these are in principle undetectable. For example, a script engine which allows file and network access may allow malicious scripts to steal confidential data through privileged users' accounts. PaX also cannot block some format string bug based attacks, which may allow arbitrary reading from and writing to data locations in memory using already existing code; the attacker does not need to know any internal addresses or inject any code into a program to execute these types of attacks.
The PaX documentation [1] (http://pax.grsecurity.net/docs/pax.txt), maintained on the PaX Web site, describes three classes of attacks which PaX attempts to protect against. The documentation discusses both attacks for which PaX will be effective in protecting a system and those for which it will not. All assume a full, position independent executable base with full Executable Space Protections and full Address Space Layout Randomization. Briefly, then, blockable attacks are:
- Those which introduce and execute arbitrary code. These types of attacks frequently involve shellcode.
- Those which attempt to execute existing program code out of the original order intended by the computer programmer(s). This is commonly called a return-to-libc attack, or ret2libc for short.
- Those which attempt to execute existing program code in the intended order with arbitrary data. This issue existed in zlib versions before 1.1.4 -- a corrupt compressed stream could cause a double-free.
Because PaX is aimed at preventing damage from such attacks rather than finding and fixing the bugs that permit them, it is not yet possible to prevent all attacks; indeed, it is likely that nothing can ever do that.
The third class of attacks is still possible with 100% reliability in spite of using PaX if the attacker does not need advance knowledge of addresses in the attacked task.
The second and third classes of attacks are also possible with 100% reliability, if the attacker needs advance knowledge of address space layout and can derive this knowledge by reading the attacked task's address space. This is possible if the target has a bug which leaks information, eg, if the attacker has access to /proc/(pid)/maps. There is an obscurity patch which NULLs out the values for the address ranges and inodes in every information source accessible from userland to close most of these holes; however, it is not currently included in PaX.
The second and third classes of attacks are possible with a small probability if the attacker needs advance knowledge of address space layout, but cannot derive this knowledge without resorting to guessing or to a brute force search. The ASLR documentation[2] (http://pax.grsecurity.net/docs/aslr.txt) describes how one can further quantify the "small probability" these attacks have of success.
The first class of attacks is possible if the attacker can have the attacked task create, write to, and mmap() a file. This in turn requires the second attack method to be possible, so an analysis of that applies here as well. Note that although not part of PaX per se, it is recommended — among other things — that production systems use an access control system that prevents this type of attack.
Responsible system administration is still required even on PaXified systems. PaX prevents or blocks attacks which exploit memory corruption bugs, such as those leading to shellcode and ret2libc attacks. Most attacks that PaX can prevent are related to buffer overflow bugs. This group includes the most common schemes used to exploit memory management problems. Still, PaX cannot prevent all of such attacks.
What PaX offers
PaX offers executable space protections, using (or emulating in operating system software) the functionality of an NX bit (i.e., built-in CPU/MMU support for memory contents execution privilege tagging). It also provides address space layout randomization to defeat ret2libc attacks and all other attacks relying on known structure of a program's virtual memory.
Executable space protections
Missing image
Pax_no_exec_prot.png
No Protections
Fig. 1 A hypothetical x86 process run might have this virtual address space without executable space protections enabled, in which case the executable could modify itself.
- Blue: Executable memory
- Green: Writable memory
- Red: Writable AND executable memory
- White: Unmapped memory
Missing image
Pax_aslr_noaslr.png
No ASLR
Fig. 2 Executable space protections protect the same process as above from modification. The AMD64 offers similar protections without PaX, though the program can override default protections.
The major feature of PaX is the executable space protection it offers. These protections take advantage of the NX bit on certain processors to prevent the execution of arbitrary code. This staves off attacks involving code injection or shellcode. On CPUs where there is no NX bit, PaX can emulate the functionality of one in various ways.
At right are two schematic views of the same hypothetical program (or process, to be more precise), run first without, and then with, Executable Space Protections enabled. This diagram is done based on the popular 32 bit x86 architecture. The color key for both diagrams is seen below the first.
Many operating systems, Linux included, take advantage of existing NX functionality in hardware to apply proper restrictions to memory. In normal cases, the address space on AMD64 and other such processors will by default look more like Fig. 2; however, Linux by default does not prohibit an application from changing any of its memory protections, allowing a program to intentionally make its address space look in whole or in part similar to Fig. 1. PaX prevents such changes, as well as guaranteeing the most restrictive default set suitable for typical operation.
When the Executable Space Protections are enabled, including the mprotect() restrictions, PaX guarantees that no memory mappings will be marked in any way in which they may be executed as program code after it has been possible to alter them from their original state. The effect of this is that it becomes impossible to execute memory during and after it has been possible to write to it, until that memory is destroyed; and thus, that code cannot be injected into the application, malicious or otherwise, from an internal or external source.
The fact that programs cannot themselves execute data they originated as program code poses an impassable problem for applications that need to generate code at runtime as a basic function, such as just-in-time compilers for Java; however, most programs that have difficulty functioning properly under these restrictions can be debugged by the programmer and fixed so that they do not rely on this functionality. For those that simply need this functionality, or those that haven't yet been fixed, the program's executable file can be marked by the system administrator so that it does not have these restrictions applied to it.
The PaX team had to make some design decisions about how to handle the mmap() system call. This function is used to either map shared memory, or to load shared libraries. Because of this, it needs to supply writable or executable RAM, depending on the conditions it is used under.
The current implementation of PaX supplies writable anonymous memory mappings by default; file backed memory mappings are made writable only if the mmap() call specifies the write permission. The mmap() function will never return mappings that are both writable and executable, even if those permissions are explicitly requested in the call.
Enforced non-executable pages
By default, Linux does not supply the most secure usage of non-executable memory pages, via the NX bit. Furthermore, some architectures do not even explicitly supply a way of marking memory pages non-executable. PaX supplies a policy to take advantage of non-executable pages in the most secure way possible.
In addition, if the CPU does not provide an explicit NX bit, PaX can emulate (supply) an NX bit by one of several methods. This degrades performance of the system, but increases security greatly. Further more, the performance loss in some methods may be low enough to be ignored.
PAGEEXEC
PAGEEXEC uses or emulates an NX bit. On processors which do not support a hardware NX, each page is given an emulated NX bit. The method used to do this is based on the architecture of the CPU. If a hardware NX bit is available, PAGEEXEC will use it instead of emulating one, incurring no performance costs.
PAGEEXEC has the advantage of not dividing the memory address space in half; tasks still each get a 3 GB virtual ramspace rather than a 1.5/1.5 split. However, for emulation, it is slower than SEGMEXEC and caused a severe performance detriment in some cases.
Since May 2004, the newer PAGEEXEC code for IA-32 in PaX tracks the highest executable page in virtual memory, and marks all higher pages as user pages. This allows data pages above this limit to be handled as normal, with no performance loss. Everything below this area is still handled as before. This change is similar to the Exec Shield NX implementation, and the OpenBSD W^X implementation.
SEGMEXEC
SEGMEXEC emulates the functionality of an NX bit on IA-32 (x86) CPUs by splitting the address space in half and mirroring the code mappings across the address space. When there is an instruction fetch, the fetch is translated across the split. If the code isn't mapped there, then the program is killed.
SEGMEXEC cuts the task's virtual memory space in half. Under normal circumstances, programs get a VM space 3GiB wide, which has physical memory mapped into it. Under SEGMEXEC, this becomes a 1.5/1.5 GiB split, with the top half used for the mirroring. Despite this, it does increase performance if emulation must be done on IA-32 (x86) architectures. Also, it is good to note that the mapping in the upper and lower half of the memory space is to the same physical memory page, and so does not double RAM usage.
Restricted mprotect()
PaX is supposed to guarantee that no RAM is both writable and executable. One function, the mprotect() function, changes the permissions on a memory area. The Single UNIX Specification defines mprotect() with the following note in its description:
- If an implementation cannot support the combination of access types specified by prot, the call to mprotect() shall fail.
The PaX implementation does not allow a memory page to have permissions PROT_WRITE and PROT_EXEC both enabled when mprotect() restrictions are enabled for the task; any call to mprotect() to set both (PROT_WRITE | PROT_EXEC) at the same time will fail due to EACCESS (Permission Denied). This guarantees that pages will not become W|X, and thus fertile ground for simple code injection attacks.
Similar failure occurs if mprotect(...|PROT_EXEC) occurs on a page that does not have the PROT_EXEC restriction already on. The failure here is justified; if a PROT_WRITE page has code injected into it, and then is made PROT_EXEC, a later retriggering of the exploit allowing code injection will allow the code to be executed. Without this restriction, a three step exploit is possible: Inject code, ret2libc::ret2mprotect(), execute code.
With mprotect() restrictions enabled, a program can no longer violate the non-executable pages policy that PaX initially sets down on all memory allocations; thus, restricted mprotect() could be considered to be strict enforcement of the security policy, whereas the "Enforced non-executable pages" without these restrictions could be considered to be a looser form of enforcement.
Trampoline emulation
Trampolines are usually implemented by gcc as small pieces of code generated at runtime on the stack. Thus, they require executing memory on the stack, which triggers PaX to kill the program.
Because trampolines are runtime generated code, they trigger PaX and cause the program using them to be killed. PaX is capable of identifying the setup of trampolines and allowing their execution. This is, however, considered to produce a situation of weakened security.
Address space layout randomization
Address space layout randomization, or ASLR, is a technique of countering arbitrary execution of code, or ret2libc attacks. These attacks involve executing already existing code out of the order intended by the programmer.
Missing image
Pax_aslr_aslr00.png
ASLR enabled
Fig. 3 ASLR alters the relative memory locations of parts of our hypothetical process.
Missing image
Pax_aslr_aslr01.png
ASLR enabled
ASLR as provided in PaX shuffles the stack base and heap base around in virtual memory when enabled. It also optionally randomizes the mmap() base and the executable base of programs. This makes attacks requiring the known location of these areas into a probability function of high magnitude.
To the left are several qualitative views of a process' address space, across multiple runs of the same program. These can be compared to the layouts shown in the executable space protections section. Linux Magazine also features an article (http://www.linux-mag.com/2002-03/compile_01.html) containing a colorful representation of a process' normal virtual address space layout.
During the course of a program's life, the heap, also called the data segment or .bss, will grow up; the heap expands towards the highest memory address available. Conversely, the stack grows down, towards the lowest memory address, 0.
It is extremely uncommon for a program to require a large percent of the address space for either of these. When program libraries are dynamically loaded at the start of a program by the operating system, they are placed before the heap; however, there are cases where the program will load other libraries, such as those commonly referred to as plug-ins, during run. The operating system or program must chose an acceptable offset to place these libraries at.
PaX leaves a portion of the addresses, the MSBs, out of the randomization calculations. This helps assure that the stack and heap are placed so that they do not collide with each other, and that libraries are placed so that the stack and heap do not collide with them.
The effect of the randomization depends on the CPU. 32 bit CPUs will have 32 bits of virtual address space, allowing access to 4 GB of memory. Because Linux uses the top 1 GB for the kernel, this is shortened to 3 GB. SEGMEXEC supplies a split down the middle of this 3GiB address space, restricting randomization down to 1.5 GB. Pages are 4 kB (4/1024 MB) in size, and randomizations are page aligned. The top four MSBs are discarded in the randomization, so that the heap exists at the beginning and the stack at the end of the program. This computes down to having the stack and heap exist at one of several million positions (23 and 24 bit randomization), and all libraries existing in any of approximately 65,000 positions.
On 64 bit CPUs, the virtual address space supplied by the MMU may be wider, allowing access to more memory. The randomization will be more entropic in such situations, further reducing the probability of a successful attack in the lack of an information leak.
Randomized mmap() base
When Randomized mmap() base is enabled, PaX randomly chooses an offset for all mmap() calls made without a specific offset, and for all non-fixed mmap() calls made with a specific offset which cannot be satisfied at that offset. This causes all dynamically linked code, i.e. shared objects, to be mapped at a different, randomly selected offset every time. Attackers requiring a function in a certain library must guess where that library is loaded in virtual memory space to call it.
When ET_DYN executables—that is, executables compiled with position independent code in the same way as shared libraries—are loaded, their base is also randomly chosen, as they are mmap()ed into RAM just like regular shared objects.
Randomized ET_EXEC base
PaX is able to map non-position-independent code randomly into RAM; however, this poses a few problems. First, it incurs some extra performance overhead. Second, on rare occasions it causes false alarms, bringing PaX to kill the process for no reason. It is strongly recommended that executables be compiled ET_DYN, so that they are 100% position independent code.
Binary markings
PaX allows executable files in the Executable and Linkable Format to be marked with reduced restrictions via the chpax and paxctl tools. These markings exist in the ELF header, and thus are both filesystem independent and part of the file object itself. This means that the markings are retained through packaging, copying, archiving, encrypting, and moving of the objects. The chpax tool is deprecated in favor of paxctl.
PaX allows individual markings for both PAGEEXEC and SEGMEXEC; randomizing the mmap(), stack, and heap base; randomizing the executable base for ET_EXEC binaries; restricting mprotect(); and emulating trampolines.
It is important to note that in the case of chpax, certain tools such as strip may lose the markings; using paxctl to set the PT_PAX_FLAGS is the only reliable method. The paxctl tool uses a new ELF program header specifically created for PaX flags. These markings can be explicitly on, off, or unset. When unset, the decision on which setting to use is made by the PaX code in the kernel, and is influenced by the system-wide PaX softmode setting.
Distributions that use PaX
PaX has been in development since October 1, 2000. The Adamantix project implements a secure Debian-based Linux distribution with several technologies, including PaX. It combines PaX with an ET_DYN and ProPolice protected base to ensure maximum protection.
The grsecurity project supplies several Linux kernel security enhancements, and supplies PaX along with those features unique to grsecurity.
The Hardened Gentoo subproject of the Gentoo Linux project uses PaX along with many other technologies to provide a secure base system. As with Adamantix, Hardened Gentoo supplies an ET_DYN and ProPolice protected base.
The Hardened Debian project is working to bring PaX, ProPolice, Position independent executables, and several other enhancements to Debian and Ubuntu Linux.
History
This is an incomplete history of PaX to be updated as more information is located. Notably, it does not indicate when the mprotect() restrictions and default memory protections for newly allocated memory were put in; when address space layout randomization was added; how ASLR progressed; when exactly SEGMEXEC and RANDEXEC appeared; or when EI_PAX was replaced with PT_PAX_FLAGS.
- October, 2000: PaX first released with basic PAGEEXEC method
- September, 2002: VMA Mirroring implemented to form the basis of RANDEXEC and SEGMEXEC
- May, 2004: PAGEEXEC augmented with code segment limit tracking for enhanced performance
- March 4, 2005: VMA Mirroring vulnerability announced, new versions of PaX and GrSecurity released, all prior versions utilizing SEGMEXEC and RANDEXEC have a privilege elevation vulnerability
- April 1, 2005: Due to that vulnerability, PaX project officially terminated, control of source code passed to Brad Spengler of GrSecurity
See also
External links
- RSBAC homepage (http://www.rsbac.org/)
- Adamantix homepage (http://adamantix.org/)
- grsecurity Homepage (http://grsecurity.net/)
- Hardened Gentoo Homepage (http://hardened.gentoo.org/)
- Hardened Debian homepage (http://debian-hardened.org/)
- PaX Homepage (http://pax.grsecurity.net/)
- Future of PaX (http://pax.grsecurity.net/docs/pax-future.txt)
- Presentation on PaX (http://grsecurity.net/PaX-presentation_files/frame.htm)
- Trampolines for Nested Functions (http://gcc.gnu.org/onlinedocs/gccint/Trampolines.html)
- Exploit Mitigation Techniques (http://cvs.openbsd.org/papers/auug04/index.html)
- Ubuntu Linux USN Analysis (http://www.ubuntulinux.org/wiki/USNAnalysis)
- PaX privilege elevation security bug (http://lists.netsys.com/pipermail/full-disclosure/2005-March/032240.html)