Misplaced Pages

Address space layout randomization: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 09:51, 31 May 2008 edit83.195.145.195 (talk) External links← Previous edit Latest revision as of 00:04, 1 January 2025 edit undoLaura240406 (talk | contribs)Extended confirmed users886 editsm Cleaned up using AutoEd 
(462 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
{{Short description|Computer security technique}}
'''Address space layout randomization''' (ASLR) is a ] technique which involves randomly arranging the positions of key data areas, usually including the base of the ] and position of ], ], and ], in a ]'s ].
{{Use dmy dates|date=May 2019|cs1-dates=y}}
{{More citations needed|date=January 2018}}

'''Address space layout randomization''' ('''ASLR''') is a ] technique involved in preventing ] of ] ].<ref>{{Cite journal |last1=Marco-Gisbert |first1=Hector |last2=Ripoll Ripoll |first2=Ismael |date=2019-07-22 |title=Address Space Layout Randomization Next Generation |journal=Applied Sciences |language=en |volume=9 |issue=14 |pages=2928 |doi=10.3390/app9142928 |issn=2076-3417|doi-access=free |hdl=10251/144813 |hdl-access=free }}</ref> In order to prevent an attacker from reliably redirecting code execution to, for example, a particular exploited function in memory, ASLR randomly arranges the ] positions of key data areas of a ], including the base of the ] and the positions of the ], ] and ].

== History ==
The Linux ] project first coined the term "ASLR", and published the first design and ] in July 2001 as a ] for the ]. It is seen as a complete implementation, providing a patch for kernel stack randomization since October 2002.<ref>{{cite web |title=PaX: The Guaranteed End of Arbitrary Code Execution |url=https://grsecurity.net/PaX-presentation.pdf |at=Slides 22 through 35 |author=Brad Spengler |date=October 2003 |access-date=20 August 2015 |website=grsecurity.net |archive-date=2020-10-25 |archive-url=https://web.archive.org/web/20201025160038/https://www.grsecurity.net/PaX-presentation.pdf |url-status=live }}</ref>

The first mainstream operating system to support ASLR by default was ] version ] in 2003,<ref name="OpenBSD-firstASLR"/><ref name="OpenBSD_Innovations-ASLR-PIE">{{cite web|title=OpenBSD Innovations|url=https://www.openbsd.org/innovations.html|publisher=The OpenBSD project|access-date=12 September 2016|archive-date=2016-09-09 |archive-url=https://web.archive.org/web/20160909033305/http://www.openbsd.org/innovations.html|url-status=live}}</ref> followed by Linux in 2005.


== Benefits == == 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 ] attacks must locate the code to be executed; while other attackers trying to execute ] 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. Address space randomization hinders some types of security attacks by making it more difficult for an attacker to predict target addresses. For example, attackers trying to execute ]s must locate the code to be executed, while other attackers trying to execute ] injected on the stack have to find the stack first. In both cases, the system makes related memory-addresses unpredictable from the attackers' point of view. These values have to be guessed, and a mistaken guess is not usually recoverable due to the application crashing.


=== Effectiveness === === 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 ] is present in the random offsets. Entropy is increased by either raising the amount of ] 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. Address space layout randomization is based upon the low chance of an attacker guessing the locations of randomly placed areas. Security is increased by increasing the search space. Thus, address space randomization is more effective when more ] is present in the random offsets. Entropy is increased by either raising the amount of ] 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, 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 ]s 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 ]s are injected onto the stack and a library is returned into. 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 ]s 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 ]s are injected onto the stack and a library is returned into.


The following variables can be declared:
To begin, let us declare the following variables:
* <math>E_s</math> (entropy bits of stack top)
* <math>E_m</math> (entropy bits of <code>mmap()</code> base)
* <math>E_x</math> (entropy bits of main executable base)
* <math>E_h</math> (entropy bits of heap base)
* <math>A_s</math> (attacked bits per attempt of stack entropy)
* <math>A_m</math> (attacked bits per attempt of <code>mmap()</code> base entropy)
* <math>A_x</math> (attacked bits per attempt of main executable entropy)
* <math>A_h</math> (attacked bits per attempt of heap base entropy)
* <math>\alpha</math> (attempts made)
* <math>N</math> (total amount of entropy: <math>N = (E_s-A_s) + (E_m-A_m) + (E_x-A_x) + (E_h-A_h)\,</math>)


To calculate the probability of an attacker succeeding, a number of attempts {{mvar|α}} carried out without being interrupted by a signature-based IPS, law enforcement, or other factor must be assumed; in the case of brute forcing, the daemon cannot be restarted. The number of relevant bits and how many are being attacked in each attempt must also be calculated, leaving however many bits the attacker has to defeat.
:<math>E_s = \mbox{entropy bits of stack top}\,</math>
:<math>E_m = \mbox{entropy bits of mmap() base}\,</math>
:<math>E_x = \mbox{entropy bits of main executable base}\,</math>
:<math>E_h = \mbox{entropy bits of heap base}\,</math>
:<math>A_s = \mbox{attacked bits per attempt of stack entropy}\,</math>
:<math>A_m = \mbox{attacked bits per attempt of mmap() base entropy}\,</math>
:<math>A_x = \mbox{attacked bits per attempt of main executable entropy}\,</math>
:<math>A_h = \mbox{attacked bits per attempt of heap base entropy}\,</math>
:<math>\alpha = \mbox{attempts made}\,</math>
:<math>N = E_s-A_s + E_m-A_m + E_x-A_x + E_h-A_h\,</math>


The following formulas represent the probability of success for a given set of {{mvar|α}} attempts on {{mvar|N}} bits of entropy.
To calculate the probability of an attacker succeeding, we have to assume a number of attempts <math>\alpha</math> 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.
* <math>g \left ( \alpha\, \right ) = 1 - { \left ( 1 - {2^{-N}} \right ) ^ \alpha\,} \,\text{ if } 0 \le \, \alpha\,</math> (isolated guessing; address space is re-randomized after each attempt)
* <math>b \left ( \alpha\, \right ) = \frac{\alpha\,}{{2^N}} \,\text{ if } 0 \le \, \alpha\, \le \, {2^N}</math> (systematic brute forcing on copies of the program with the same address space)


In many systems, <math>2^N</math> can be in the thousands or millions. On 32-bit systems, a typical amount of entropy ''N'' is 8 bits.<ref name=offset2lib>{{cite web|last1=Marco-Gisbert|first1=Hector|first2=Ismael|last2=Ripoll|url=http://cybersecurity.upv.es/attacks/offset2lib/offset2lib-paper.pdf|title=On the Effectiveness of Full-ASLR on 64-bit Linux|date=20 November 2014|access-date=2016-03-29 |archive-date=2015-05-08 |archive-url=https://web.archive.org/web/20150508073303/http://cybersecurity.upv.es/attacks/offset2lib/offset2lib-paper.pdf|url-status=dead}}</ref> For 2004 computer speeds, Shacham and co-workers state "... 16 bits of address randomization can be defeated by a ] within minutes."<ref>{{cite conference|title=On the Effectiveness of Address-Space Randomization|last1=Shacham|first1=H.|last2=Page|first2=M.|last3=Pfaff|first3=B.|last4=Goh|first4=E.J.|last5=Modadugu|first5=N.|last6=Boneh|first6=D|conference=11th ACM conference on Computer and communications security|pages=298–307|year=2004}}</ref> (The authors' statement depends on the ability to attack the same application multiple times without any delay. 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.) On {{as of | 2009 | alt = modern}} ] systems, these numbers typically reach the millions at least.{{cn|date=March 2024}}
The following formulas represent the probability of success for a given set of <math>\alpha\,</math> attempts on <math>N</math> bits of entropy.


Android,<ref name=android-llor>{{cite web |title=Implement Library Load Order Randomization |url=https://android-review.googlesource.com/178130 |access-date=26 June 2017 |archive-date=2023-08-11 |archive-url=https://web.archive.org/web/20230811031655/https://android-review.googlesource.com/c/platform/bionic/+/178130/ |url-status=live }}</ref>{{Primary source inline|date=March 2016}} and possibly other systems,{{which|date=October 2015}} implement ''Library Load Order Randomization'', a form of ASLR which randomizes the order in which libraries are loaded. 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. Attackers usually need only one library; the math is more complex with multiple libraries, and shown below as well. The case of an attacker using only one library is a simplification of the more complex formula for <math>l = 1</math>.
:<math>g \left ( \alpha\, \right ) = \mbox{isolated guessing; address space is re-randomized after each attempt}\,</math>
* {{mvar|l}} (number of libraries loaded)
:<math>g \left ( \alpha\, \right ) = 1 - { \left ( 1 - {2^{-N}} \right ) ^ \alpha\,} : 0 \le \, \alpha\,</math>
* {{mvar|β}} (number of libraries used by the attacker)
* <math>
E_m = \begin{cases} \log_2 \left (l \right ) &\text{ if } \beta\, = 1, l \ge \, 1 \\
\sum_{i=l}^{l - \left ( \beta\, - 1 \right )} \log_2 \left (i \right ) &\text{ if } \beta\, \ge \, 1, l \ge \, 1
\end{cases}
</math>


These values tend to be low even for large values of {{mvar|l}}, most importantly since attackers typically can use only the ] and thus one can often assume that <math>\beta\, = 1</math>. 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. These extra bits of entropy will not apply to other mmap() segments, only libraries.
:<math>b \left ( \alpha\, \right ) = \mbox{systematic brute forcing on copies of the program with the same address space}</math>
:<math>b \left ( \alpha\, \right ) = \frac{\alpha\,}{{2^N}} : 0 \le \, \alpha\, \le \, {2^N}</math>


==== Reducing entropy ====
In many systems, <math>2^N</math> can be in the thousands or millions; on modern ] systems, these numbers typically reach the millions at least. For 32-bit systems at 2004 computer speeds which have 16 bits for address randomisation, Shacham and co workers state "... 16 bits of address randomization can be defeated by a brute force attack within minutes."<ref>On the Effectiveness of Address-Space Randomization,Shacham, H. and Page, M. and Pfaff, B. and Goh, E.J. and Modadugu, N. and Boneh, D,Proceedings of the 11th ACM conference on Computer and communications security,pp 298--307, 2004</ref> It should be noted that the authors' statement depends on the ability to attack the same application multiple times without any delay. Proper implementations of ASLR, like that included in ], 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.
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 ]). There is little that can be done about this.


It is possible to leak information about memory layout using ]. Format string functions such as ] use a ] 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 eliminate library and stack randomization as an obstacle to an attacker.
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 <math>l = 1</math>.


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 4096 bytes. When attempting an attack, it is possible to align duplicate attacks with these intervals; a ] may be used with ], and the string '{{code|/bin/sh}}' can be replaced with '{{code|////////bin/sh}}' for an arbitrary number of slashes when attempting to return to ''system''. The number of bits removed is exactly <math>\log_2\!\left (n \right )</math> for {{mvar|n}} intervals attacked.
:<math> l = \mbox{number of libraries loaded}</math>
:<math> \beta\, = \mbox{number of libraries used by the attacker}</math>


Such decreases are limited due to the amount of data in the stack or heap. The stack, for example, is typically limited to {{val|8|u=]}}<ref name="Prefix2">{{BDprefix|p=b}}</ref> and grows to much less; this allows for at most {{val|19|u=bits}}, although a more conservative estimate would be around 8–{{val|10|u=bits}} corresponding to 4–{{val|16|u=]}}<ref name="Prefix2"/> of stack stuffing. The heap on the other hand is limited by the behavior of the memory allocator; in the case of ], allocations above 128&nbsp;KB are created using ], limiting attackers to 5&nbsp;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 ]s.
:<math>E_m = \log_2 \left (n \right ) : \beta\, = 1, l \ge \, 1</math>
:<math>E_m = \sum_{i=l}^{l - \left ( \beta\, - 1 \right )} \log_2 \left (i \right ) : \beta\, \ge \, 1, l \ge \, 1</math>


=== Limitations ===
These values tend to be low even for large values of <math>l</math>, most importantly since attackers typically can use only the ] and thus it can often be assumed <math>\beta\, = 1</math>. 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.


ASLR-protected addresses can be leaked by various side channels, removing mitigation utility. Recent attacks have used information leaked by the CPU branch target predictor buffer (BTB) or memory management unit (MMU) walking page tables. It is not clear if this class of ASLR attack can be mitigated. If they cannot, the benefit of ASLR is reduced or eliminated.
==== 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. There is little that can be done about this.


=== Empirical analysis ===
It is possible to leak information about memory layout using ]. Format string functions such as ]() use a ] 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.


In August 2024 a paper <ref name=ilofrand>{{cite arXiv |title=The Illusion of Randomness: An Empirical Analysis of Address Space Layout Randomization Implementations |eprint=2408.15107 |last1=Binosi |first1=Lorenzo |last2=Barzasi |first2=Gregorio |last3=Carminati |first3=Michele |last4=Zanero |first4=Stefano |last5=Polino |first5=Mario |date=2024 |class=cs.CR }}</ref> was published with an empirical analysis of major desktop platforms, including Linux, macOS, and Windows, by examining the variability in the placement of memory objects across various processes, threads, and system restarts. The results show that while some systems as of 2024, like Linux distributions, provide robust randomization, others, like Windows and macOS, often fail to adequately randomize key areas like executable code and libraries. Moreover, they found a significant entropy reduction in the entropy of libraries after the Linux 5.18 version and identify correlation paths that an attacker could leverage to reduce exploitation complexity significantly.
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 ] 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 <math>log_2 \left (n \right )</math> for <math>n</math> intervals attacked.


== Implementations ==
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 ], allocations above 128KiB are created using ](), 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 ].
Several mainstream, general-purpose operating systems implement ASLR.


== History == === Android ===
] 4.0 Ice Cream Sandwich provides address space layout randomization (ASLR) to help protect system and third-party applications from exploits due to memory-management issues. Position-independent executable support was added in Android 4.1.<ref>{{cite web|title=Android Security|url=http://source.android.com/tech/security/index.html#memory-management-security-enhancements|publisher=Android Developers|access-date=7 July 2012|archive-date=2011-10-12 |archive-url=https://web.archive.org/web/20111012153320/http://source.android.com/tech/security/index.html#memory-management-security-enhancements|url-status=live}}</ref> Android 5.0 dropped non-PIE support and requires all dynamically linked binaries to be position independent.<ref>{{cite web|title=oss-security|url=http://www.openwall.com/lists/oss-security/2015/03/13/1|access-date=4 October 2015|archive-date=2015-10-05 |archive-url=https://web.archive.org/web/20151005085845/http://www.openwall.com/lists/oss-security/2015/03/13/1|url-status=live}}</ref><ref>{{cite web |title=Revert "Reenable support for non-PIE executables" |url=https://android-review.googlesource.com/100254 |access-date=26 June 2017 |archive-date=2023-08-11 |archive-url=https://web.archive.org/web/20230811031655/https://android-review.googlesource.com/c/platform/bionic/+/100254/ |url-status=live }}</ref> Library load ordering randomization was accepted into the Android open-source project on 26 October 2015,<ref name=android-llor />{{Primary source inline|date=March 2016}} and was included in the Android 7.0 release.
The first design and implementation (and indeed the coining of the term ASLR) was made public in July, 2001 by the ] project. It remains the most complete implementation, providing also kernel stack randomization from October 2002 onward. It also continues to provide the most entropy for each randomized layout compared to other implementations.<ref>Comparison of PaX to ExecShield and W^X</ref>


== Implementations == === DragonFly BSD ===
] has an implementation of ASLR based upon OpenBSD's model, added in 2010.<ref> {{Webarchive|url=https://web.archive.org/web/20140201171118/http://gitweb.dragonflybsd.org/dragonfly.git/commit/911e30e25724984efec56accba87f739cfca2937 |date=2014-02-01}}, DragonFly Gitweb, 25 November 2010.</ref> It is off by default, and can be enabled by setting the sysctl vm.randomize_mmap to 1.
Several mainstream, general purpose operating systems implement ASLR.


=== FreeBSD ===
In ], a weak form of ASLR has been enabled by default since kernel version 2.6.12. The ] and ] patchsets to the Linux kernel provide more complete implementations. Various Linux distributions including Adamantix, ], and Hardened Linux From Scratch come with PaX's implementation of ASLR by default.
Support for ASLR appeared in ] 13.0.<ref>{{cite web|url=https://svnweb.freebsd.org/base?view=revision&revision=r343964|title=Implement Address Space Layout Randomization (ASLR)|access-date=10 February 2019|archive-date=2019-05-07 |archive-url=https://web.archive.org/web/20190507015239/https://svnweb.freebsd.org/base?view=revision&revision=r343964|url-status=live}}</ref><ref>{{cite web|url=https://wiki.freebsd.org/ASLR|title=ASLR - FreeBSD Wiki|access-date=17 May 2021|archive-date=2021-05-17 |archive-url=https://web.archive.org/web/20210517164743/https://wiki.freebsd.org/ASLR|url-status=dead}}</ref> It is enabled by default since 13.2.<ref>{{cite web|url=https://www.freebsd.org/releases/13.2R/relnotes/|title=FreeBSD 13.2-RELEASE Release Notes|access-date=2023-04-11 |archive-date=2023-04-11 |archive-url=https://web.archive.org/web/20230411130022/https://www.freebsd.org/releases/13.2R/relnotes/|url-status=live}}</ref>


=== iOS (iPhone, iPod touch, iPad) ===
The ] patch 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.
] introduced ASLR in ] 4.3 (released March 2011).<ref> {{Webarchive|url=https://web.archive.org/web/20120502121557/http://arstechnica.com/security/news/2011/03/pwn2own-day-2-iphone-blackberry-beaten-chrome-firefox-no-shows.ars |date=2012-05-02}}, ], 11 March 2011</ref>


KASLR was introduced in iOS 6.<ref>{{cite web|url=https://www.slideshare.net/i0n1c/csw2013-stefan-esserios6exploitation280dayslater/19-KASLR_iOS_6_introduces_KASLR|title=iOS 6 Exploitation 280 Days Later|author=Stefan Esser|at=Slide 19, "iOS 6 introduces KASLR"|date=7 March 2013|access-date=2018-04-25 |archive-date=2019-05-07 |archive-url=https://web.archive.org/web/20190507015239/https://www.slideshare.net/i0n1c/csw2013-stefan-esserios6exploitation280dayslater/19-KASLR_iOS_6_introduces_KASLR|url-status=live}}</ref> The randomized kernel base is {{code|0x01000000 + ((1+0xRR) * 0x00200000)}}, where {{code|0xRR}} is a random byte from SHA1 (random data) generated by iBoot (the 2nd-stage iOS Boot Loader).<ref>{{cite web|url=https://papers.put.as/papers/ios/2013/NISlecture201303.pdf|title=Attacking the iOS Kernel: A Look at 'evasi0n'|author=Tarjei Mandt|access-date=2023-07-23 |archive-date=2020-12-13 |archive-url=https://web.archive.org/web/20201213023331/https://papers.put.as/papers/ios/2013/NISlecture201303.pdf|url-status=live}}</ref>
The ] tool implements randomization at prelink time rather than runtime, 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.


=== Linux ===
Microsoft's ] and ] have ASLR enabled by default, although only for executables which are specifically linked to be ASLR enabled.
The ] enabled a weak form of ASLR by default since the kernel version 2.6.12, released in June 2005.<ref>{{cite web |first1=Alan |last1=Dang |first2=<!-- interviewee -->Charlie |last2=Miller |url=http://www.tomshardware.com/reviews/pwn2own-mac-hack,2254-4.html |title=The NX Bit And ASLR |website=] |date=25 March 2009 |access-date=2010-03-20 |archive-date=2023-08-11 |archive-url=https://web.archive.org/web/20230811031701/https://www.tomshardware.com/reviews/pwn2own-mac-hack,2254-4.html |url-status=live }}</ref> The ] and ] patchsets to the Linux kernel provide more complete implementations. The Exec Shield patch for ] 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 8&nbsp;MB wide containing 524,288 possible positions, and the mmap base in an area 1&nbsp;MB wide containing 256 possible positions.


ASLR can be disabled for a specific process by changing its execution domain, using <code>personality(2)</code>.<ref>{{man|2|personality|Linux}}</ref> A number of ] options control the behavior of mainline ASLR. For example, {{code|kernel.randomize_va_space}} controls ''what'' to randomize; the strongest option is 2. {{code|vm.mmap_rnd_bits}} controls how many bits to randomize for ].<ref>{{multiref|1={{cite web |title=Documentation for /proc/sys/kernel/ — The Linux Kernel documentation |url=https://www.kernel.org/doc/html/latest/admin-guide/sysctl/kernel.html |website=www.kernel.org}}|2={{cite web |title=Documentation for /proc/sys/vm/ — The Linux Kernel documentation |url=https://www.kernel.org/doc/html/latest/admin-guide/sysctl/vn |website=www.kernel.org}}}}</ref>
] also supports ASLR.


] (PIE) implements a random base address for the main executable binary and has been in place since April 18, 2004. It provides the same address randomness to the main executable as being used for the shared libraries. The PIE feature cannot be used together with the ] feature for the same executable. 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.
Apple introduced randomization of some library offsets in ]<ref>See "Library Randomization" at http://www.apple.com/macosx/features/300.html#security</ref>, presumably as a stepping stone to fully implementing ASLR at a later date. Their implementation does not provide complete protection against attacks which ASLR is designed to defeat<ref></ref><ref></ref><ref></ref><ref></ref>.


In 2014, Marco-Gisbert and Ripoll disclosed ''offset2lib'' technique that weakens Linux ASLR for PIE executables. Linux kernels load PIE executables right after their libraries; as a result, there is a fixed offset between the executable and the library functions. If an attacker finds a way to find the address of a function in the executable, the library addresses are also known. They demonstrated an attack that finds the address in fewer than 400 tries. They proposed a new {{code|1=randomize_va_space=3}} option to randomize the placement of the executable relative to the library,<ref name=offset2lib/> but it is yet to be incorporated into the upstream as of 2024.<ref>{{cite web |title= ASLRv3: randomize_va_space=3 preventing offset2lib attack |url=https://lore.kernel.org/lkml/5480F756.90106@upv.es/T/ |website=lore.kernel.org}}</ref>
==References==
{{reflist}}


The Linux kernel 5.18 released May 2022 reduced the effectiveness of both 32-bit and 64-bit implementations. Linux filesystems call <code>thp_get_unmapped_area</code> to respond to a file-backed ]. With a change in 5.18, files greater than 2&nbsp;MiB are made to return 2&nbsp;MiB-aligned addresses, so they can be potentially backed by ]s. (Previously, the increased alignment only applied to Direct Access (DAX) mappings.) In the meantime, the C library (libc) has, over time, grown in size to exceed this 2&nbsp;MiB threshold, so instead of being aligned to a (typically) 4&nbsp;KiB page boundary as before, these libraries are now 2&nbsp;MiB-aligned: a loss of 9 bits of entropy. For 32-bit Linux, many distributions show no randomization ''at all'' in the placement of the libc. For 64-bit Linux, the 28 bits of entropy is reduced to 19 bits. In response, Ubuntu has increased its {{code|mmap_rnd_bits}} setting.<ref>{{Cite web |last=Miller |first=Justin |date=8 January 2024 |title=ASLRn't: How memory alignment broke library ASLR |url=https://zolutal.github.io/aslrnt/ |access-date=13 January 2024 |website=zolutal's blog}}</ref> Martin Doucha added a ] testcase to detect this issue.<ref>{{cite web |title= Add test for ASLRn't bug - Martin Doucha |url=https://lore.kernel.org/all/20240117173006.31521-2-mdoucha@suse.cz/ |website=lore.kernel.org}}</ref>
==External links==
*
*
*
*
*
*
*
*
*


===={{Anchor|KASLR|FGKASLR}}Kernel address space layout randomization====
]
Kernel address space layout randomization (KASLR) enables address space randomization for the Linux kernel image by randomizing where the kernel code is placed at boot time.<ref>{{cite web | url = https://lwn.net/Articles/569635/ | title = Kernel address space layout randomization | date = 9 October 2013 | access-date = 2 April 2014 | author = Jake Edge | publisher = ] | archive-date = 2014-04-04 | archive-url = https://web.archive.org/web/20140404040108/http://lwn.net/Articles/569635/ | url-status = live }}</ref> KASLR was merged into the ] in kernel version 3.14, released on 30 March 2014.<ref>{{cite web | url = http://kernelnewbies.org/Linux_3.14#head-192cae48200fccde67b36c75cdb6c6d8214cccb3 | title = Linux kernel 3.14, Section 1.7. Kernel address space randomization | date = 30 March 2014 | access-date = 2 April 2014 | website = kernelnewbies.org | archive-date = 2021-01-15 | archive-url = https://web.archive.org/web/20210115101454/https://kernelnewbies.org/Linux_3.14#head-192cae48200fccde67b36c75cdb6c6d8214cccb3 | url-status = live }}</ref> When compiled in, it can be disabled at boot time by specifying {{Mono|nokaslr}} as one of the kernel's boot parameters.<ref>{{cite web | url = https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=8ab3820fd5b2896d66da7bb2a906bc382e63e7bc | title = kernel/git/torvalds/linux.git: x86, kaslr: Return location from decompress_kernel (Linux kernel source tree) | date = 13 October 2013 | access-date = 2 April 2014 | publisher = ] | archive-date = 2023-08-11 | archive-url = https://web.archive.org/web/20230811031618/https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=8ab3820fd5b2896d66da7bb2a906bc382e63e7bc | url-status = live }}</ref>
]


There are several ]s in x86 processors that could leak kernel addresses.<ref name=":1">{{Cite conference|date=24 June 2017|title=KASLR is Dead: Long Live KASLR|url=https://gruss.cc/files/kaiser.pdf|conference=Engineering Secure Software and Systems 2017}}</ref><ref>{{Cite conference |last1=Jang |first1=Yeongjin |last2=Lee |first2=Sangho |last3=Kim |first3=Taesoo |book-title=Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security |title=Breaking Kernel Address Space Layout Randomization with Intel TSX |date=2016 |url=http://people.oregonstate.edu/~jangye/assets/papers/2016/jang:drk-bh.pdf |series=CCS '16 |location=New York |publisher=Association for Computing Machinery |pages=380–392 |doi=10.1145/2976749.2978321 |isbn=9781450341394 |s2cid=6293725 |doi-access=free |access-date=2017-12-29 |archive-date=2020-09-21 |archive-url=https://web.archive.org/web/20200921035559/http://people.oregonstate.edu/~jangye/assets/papers/2016/jang:drk-bh.pdf |url-status=live }}</ref> In late 2017, ] (KPTI aka KAISER) was developed to defeat these attacks.<ref>{{Cite news |url=https://lwn.net/Articles/741878/ |title=The current state of kernel page-table isolation |last=Corbet |first=Jonathan |date=20 December 2017 |work=Linux Weekly News |access-date=2018-01-04 |archive-date=2018-01-04 |archive-url=https://web.archive.org/web/20180104192446/https://lwn.net/Articles/741878/ |url-status=live }}</ref><ref name=":0">{{Cite news |url=https://lwn.net/Articles/738975/ |title=KAISER: hiding the kernel from user space |last=Corbet |first=Jonathan |date=15 November 2017 |work=Linux Weekly News |access-date=2017-12-29 |archive-date=2020-12-08 |archive-url=https://web.archive.org/web/20201208004347/https://lwn.net/Articles/738975/ |url-status=live }}</ref> However, this method cannot protect against side-channel attacks utilizing collisions in ] structures.<ref name="jump-over-aslr">{{Cite conference |url=http://www.cs.ucr.edu/~nael/pubs/micro16.pdf |doi=10.1109/MICRO.2016.7783743 |isbn=978-1-5090-3508-3 |title=Jump over ASLR: Attacking branch predictors to bypass ASLR |conference=2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) |pages=1–13 |year=2016 |last1=Evtyushkin |first1=Dmitry |last2=Ponomarev |first2=Dmitry |last3=Abu-Ghazaleh |first3=Nael |s2cid=3801142}}</ref>
]

]
{{as of|2021}}, finer grained kernel address space layout randomization (or function granular KASLR, FGKASLR) is a planned extension of KASLR to randomize down to the function level by placing functions in separate sections and reordering them at boot time.<ref>{{Cite web|url=https://www.phoronix.com/scan.php?page=news_item&px=Linux-5.16-Preps-For-FGKASLR|title=Linux 5.16 Has Early Preparations For Supporting FGKASLR - Phoronix|website=www.phoronix.com|access-date=2021-11-10 |archive-date=2021-11-10 |archive-url=https://web.archive.org/web/20211110173106/https://www.phoronix.com/scan.php?page=news_item&px=Linux-5.16-Preps-For-FGKASLR|url-status=live}}</ref>

=== Microsoft Windows ===
{{Update section|date=August 2018}}
Microsoft's ] (released January 2007) and later have ASLR enabled only for executables and ] that are specifically linked to be ASLR-enabled.<ref>{{cite web |url=http://msdn.microsoft.com/en-us/library/bb430720.aspx |title=Windows ISV Software Security Defenses |date=6 December 2010 |publisher=Msdn.microsoft.com |access-date=10 April 2012 |archive-date=2012-04-18 |archive-url=https://web.archive.org/web/20120418055828/http://msdn.microsoft.com/en-us/library/bb430720.aspx |url-status=live }}</ref> For compatibility, it is not enabled by default for other applications. Typically, only older software is incompatible and ASLR can be fully enabled by editing a registry entry {{code|HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management\MoveImages}},<ref>Windows Internals: Including Windows Server 2008 and Windows Vista, Fifth Edition (PRO-Developer) {{ISBN|978-0-7356-2530-3}}</ref> or by installing Microsoft's ].

The locations of the ], ], Process Environment Block, and ] are also randomized. A security whitepaper from Symantec noted that ASLR in 32-bit Windows Vista may not be as robust as expected, and Microsoft has acknowledged a weakness in its implementation.<ref>{{cite web |url=http://www.symantec.com/avcenter/reference/Address_Space_Layout_Randomization.pdf |title=An Analysis of Address Space Layout Randomization on Windows Vista |author=Ollie Whitehouse |date=February 2007 |access-date=18 January 2009 |archive-url=https://web.archive.org/web/20190715102700/http://www.symantec.com/avcenter/reference/Address_Space_Layout_Randomization.pdf |archive-date=15 July 2019 |url-status=dead }}</ref>

Host-based ]s such as ''WehnTrust''<ref>{{cite web |url=http://www.codeplex.com/wehntrust |title=WehnTrust |publisher=Codeplex.com |access-date=10 April 2012 |archive-date=2009-12-25 |archive-url=https://web.archive.org/web/20091225114459/http://www.codeplex.com/wehntrust |url-status=live }}</ref> and ''Ozone''<ref>{{cite web |url=http://www.secarch.com/products.html |title=Security Architects' Ozone |publisher=Security Architects |access-date=10 April 2012 |archive-date=2016-03-04 |archive-url=https://web.archive.org/web/20160304115626/http://www.secarch.com/products.html |url-status=live }}</ref> also offer ASLR for ] and ] operating systems. WehnTrust is open-source.<ref>{{cite web |url=http://wehntrust.codeplex.com/ |title=WehnTrust source code |access-date=15 November 2013 |archive-date=2013-11-28 |archive-url=https://web.archive.org/web/20131128032117/http://wehntrust.codeplex.com/ |url-status=dead }}</ref> Complete details of Ozone's implementation are not available.<ref>{{cite web |url=http://seclab.cs.sunysb.edu/seclab/pubs/acsac06.pdf |title=Address-Space Randomization for Windows Systems |access-date=10 April 2012 |archive-date=2010-08-05 |archive-url=https://web.archive.org/web/20100805060216/http://seclab.cs.sunysb.edu/seclab/pubs/acsac06.pdf |url-status=live }}</ref>

It was noted in February 2012<ref>{{cite web |author=Ollie |url=http://recxltd.blogspot.co.uk/2012/03/partial-technique-against-aslr-multiple.html |title=Research, Develop, Assess, Consult & Educate &#124; Recx: A Partial Technique Against ASLR – Multiple O/Ss |publisher=Recxltd.blogspot.co.uk |date=2 March 2012 |access-date=10 April 2012 |archive-date=2013-03-23 |archive-url=https://web.archive.org/web/20130323224909/http://recxltd.blogspot.co.uk/2012/03/partial-technique-against-aslr-multiple.html |url-status=live }}</ref> that ASLR on 32-bit Windows systems prior to ] can have its effectiveness reduced in low memory situations. A similar effect also had been achieved on Linux in the same research. The test code caused the Mac OS X 10.7.3 system to ], so it was left unclear about its ASLR behavior in this scenario.

=== NetBSD ===
Support for ASLR in userland appeared in ] 5.0 (released April 2009),<ref>{{cite web|url=https://netbsd.org/releases/formal-5/NetBSD-5.0.html|title=Announcing NetBSD 5.0|access-date=25 April 2016|archive-date=2016-04-21 |archive-url=https://web.archive.org/web/20160421055559/https://www.netbsd.org/releases/formal-5/NetBSD-5.0.html|url-status=live}}</ref> and was enabled by default in NetBSD-current in April 2016.<ref>{{cite web|url=https://mail-index.netbsd.org/current-users/2016/04/10/msg029186.html|title=PIE binaries and ASLR are on in the default build for amd64|author=Christos Zoulas|year=2016|access-date=25 April 2016|archive-date=2016-04-22 |archive-url=https://web.archive.org/web/20160422184410/http://mail-index.netbsd.org/current-users/2016/04/10/msg029186.html|url-status=live}}</ref>

Kernel ASLR support on amd64 was added in NetBSD-current in October 2017, making NetBSD the first BSD system to support KASLR.<ref>{{cite web|url=https://blog.netbsd.org/tnf/entry/kernel_aslr_on_amd64|title=Kernel ASLR on amd64|year=2017|access-date=16 October 2017|archive-date=2017-10-16 |archive-url=https://web.archive.org/web/20171016175156/https://blog.netbsd.org/tnf/entry/kernel_aslr_on_amd64|url-status=live}}</ref>

=== {{anchor|OpenBSD}} OpenBSD ===
In 2003, ] became the first mainstream operating system to support a strong form of ASLR and to activate it by default.<ref name="OpenBSD-firstASLR">{{cite web
|url=http://www.openbsd.org/papers/ven05-deraadt/index.html
|title=Exploit Mitigation Techniques (updated to include random malloc and mmap) at OpenCON 2005
|author=Theo De Raadt
|year=2005
|access-date=26 August 2009
|archive-date=2012-07-16
|archive-url=https://web.archive.org/web/20120716182141/http://www.openbsd.org/papers/ven05-deraadt/index.html
|url-status=live
}}</ref>
OpenBSD completed its ASLR support in 2008 when it added support for ] binaries.<ref name="OpenBSD-PIE">{{cite web|url=http://www.openbsd.org/papers/nycbsdcon08-pie/|title=OpenBSD's Position Independent Executable (PIE) Implementation|author=Kurt Miller|year=2008|access-date=22 July 2011| archive-url= https://web.archive.org/web/20110612150147/http://openbsd.org/papers/nycbsdcon08-pie/| archive-date= 12 June 2011 | url-status= live}}</ref> OpenBSD 4.4's ] was designed to improve security by taking advantage of ASLR and gap page features implemented as part of OpenBSD's <code>mmap</code> ], and to detect use-after-free bugs.<ref name="malloc.c">{{cite web |url=http://bxr.su/OpenBSD/lib/libc/stdlib/malloc.c |title=libc/stdlib/malloc.c |website=BSD Cross Reference, OpenBSD src/lib/ |access-date=2016-09-12 |archive-date=2014-12-26 |archive-url=https://web.archive.org/web/20141226233129/http://bxr.su/OpenBSD/lib/libc/stdlib/malloc.c |url-status=live }}</ref> Released in 2013, OpenBSD 5.3 was the first mainstream operating system to enable position-independent executables by default on multiple ]s, and OpenBSD 5.7 activated position-independent static binaries (Static-PIE) by default.<ref name="OpenBSD-PIE"/>

=== macOS ===
In ] 10.5 (released October 2007), Apple introduced randomization for system libraries.<ref>{{cite web|url=https://www.apple.com/macosx/security/#sixtyfour |title=Mac OS X – Security – Keeps safe from viruses and malware |publisher=Apple |access-date=10 April 2012|archive-url=https://web.archive.org/web/20110525190329/http://www.apple.com/macosx/security/#sixtyfour |archive-date=25 May 2011 }}</ref>

In ] 10.7 (released July 2011), Apple expanded their implementation to cover all applications, stating "address space layout randomization (ASLR) has been improved for all applications. It is now available for 32-bit apps (as are heap memory protections), making 64-bit and 32-bit applications more resistant to attack."<ref>{{cite web|url=https://www.apple.com/macosx/whats-new/features.html#security|title=Security|publisher=Apple Inc.|access-date=6 June 2011| archive-url= https://web.archive.org/web/20110606235315/http://www.apple.com/macosx/whats-new/features.html#security| archive-date= 6 June 2011}}</ref>

As of ] 10.8 (released July 2012) and later, the entire system including the kernel as well as ] and zones are randomly relocated during system boot.<ref>{{cite web|url=http://movies.apple.com/media/us/osx/2012/docs/OSX_MountainLion_Core_Technologies_Overview.pdf|title=OS X Mountain Lion Core Technologies Overview|date=June 2012|access-date=25 July 2012|archive-date=2012-07-10 |archive-url=https://web.archive.org/web/20120710081931/http://movies.apple.com/media/us/osx/2012/docs/OSX_MountainLion_Core_Technologies_Overview.pdf|url-status=live}}</ref>

=== Solaris ===
ASLR has been introduced in ] beginning with Solaris 11.1 (released October 2012). ASLR in Solaris 11.1 can be set system-wide, per zone, or on a per-binary basis.<ref> {{Webarchive|url=https://web.archive.org/web/20130620212020/http://docs.oracle.com/cd/E26502_01/html/E29015/concept-13.html#concept-aslr-1 |date=2013-06-20}}, Oracle Information Library, 26 October 2012.</ref>

==Exploitation==
A ] utilizing ] was demonstrated to bypass ASLR protection.<ref name="jump-over-aslr" /> In 2017, an attack named "ASLR⊕Cache" was demonstrated which could defeat ASLR in a web browser using JavaScript.<ref> {{Webarchive|url=https://web.archive.org/web/20170316055626/https://www.vusec.net/projects/anc/ |date=2017-03-16}} VUSec, 2017</ref>

== See also ==
* ]
* ]
* ]
* ]

== References ==
{{Reflist}}

== External links ==
* {{Webarchive|url=https://web.archive.org/web/20140220032702/http://tech.yandex.com/events/ruBSD/2013/talks/103/ |date=2014-02-20}} in OpenBSD
*
*
*
*
*
*
*
*

{{DEFAULTSORT:Address space layout randomization}}
]

Latest revision as of 00:04, 1 January 2025

Computer security technique

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Address space layout randomization" – news · newspapers · books · scholar · JSTOR (January 2018) (Learn how and when to remove this message)

Address space layout randomization (ASLR) is a computer security technique involved in preventing exploitation of memory corruption vulnerabilities. In order to prevent an attacker from reliably redirecting code execution to, for example, a particular exploited function in memory, ASLR randomly arranges the address space positions of key data areas of a process, including the base of the executable and the positions of the stack, heap and libraries.

History

The Linux PaX project first coined the term "ASLR", and published the first design and implementation of ASLR in July 2001 as a patch for the Linux kernel. It is seen as a complete implementation, providing a patch for kernel stack randomization since October 2002.

The first mainstream operating system to support ASLR by default was OpenBSD version 3.4 in 2003, followed by Linux in 2005.

Benefits

Address space randomization hinders some types of security attacks by making it more difficult for an attacker to 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 find the stack first. In both cases, the system makes related memory-addresses unpredictable from the attackers' point of view. These values have to be guessed, and a mistaken guess is not usually recoverable due to the application crashing.

Effectiveness

Address space layout randomization is based upon the low chance of an attacker guessing the locations of randomly placed areas. 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 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.

The following variables can be declared:

  • E s {\displaystyle E_{s}} (entropy bits of stack top)
  • E m {\displaystyle E_{m}} (entropy bits of mmap() base)
  • E x {\displaystyle E_{x}} (entropy bits of main executable base)
  • E h {\displaystyle E_{h}} (entropy bits of heap base)
  • A s {\displaystyle A_{s}} (attacked bits per attempt of stack entropy)
  • A m {\displaystyle A_{m}} (attacked bits per attempt of mmap() base entropy)
  • A x {\displaystyle A_{x}} (attacked bits per attempt of main executable entropy)
  • A h {\displaystyle A_{h}} (attacked bits per attempt of heap base entropy)
  • α {\displaystyle \alpha } (attempts made)
  • N {\displaystyle N} (total amount of entropy: N = ( E s A s ) + ( E m A m ) + ( E x A x ) + ( E h A h ) {\displaystyle N=(E_{s}-A_{s})+(E_{m}-A_{m})+(E_{x}-A_{x})+(E_{h}-A_{h})\,} )

To calculate the probability of an attacker succeeding, a number of attempts α carried out without being interrupted by a signature-based IPS, law enforcement, or other factor must be assumed; in the case of brute forcing, the daemon cannot be restarted. The number of relevant bits and how many are being attacked in each attempt must also be calculated, 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.

  • g ( α ) = 1 ( 1 2 N ) α  if  0 α {\displaystyle g\left(\alpha \,\right)=1-{\left(1-{2^{-N}}\right)^{\alpha }\,}\,{\text{ if }}0\leq \,\alpha \,} (isolated guessing; address space is re-randomized after each attempt)
  • b ( α ) = α 2 N  if  0 α 2 N {\displaystyle b\left(\alpha \,\right)={\frac {\alpha \,}{2^{N}}}\,{\text{ if }}0\leq \,\alpha \,\leq \,{2^{N}}} (systematic brute forcing on copies of the program with the same address space)

In many systems, 2 N {\displaystyle 2^{N}} can be in the thousands or millions. On 32-bit systems, a typical amount of entropy N is 8 bits. For 2004 computer speeds, Shacham and co-workers state "... 16 bits of address randomization can be defeated by a brute force attack within minutes." (The authors' statement depends on the ability to attack the same application multiple times without any delay. 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.) On modern 64-bit systems, these numbers typically reach the millions at least.

Android, and possibly other systems, implement Library Load Order Randomization, a form of ASLR which randomizes the order in which libraries are loaded. 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. Attackers usually need only one library; the math is more complex with multiple libraries, and shown below as well. The case of an attacker using only one library is a simplification of the more complex formula for l = 1 {\displaystyle l=1} .

  • l (number of libraries loaded)
  • β (number of libraries used by the attacker)
  • E m = { log 2 ( l )  if  β = 1 , l 1 i = l l ( β 1 ) log 2 ( i )  if  β 1 , l 1 {\displaystyle E_{m}={\begin{cases}\log _{2}\left(l\right)&{\text{ if }}\beta \,=1,l\geq \,1\\\sum _{i=l}^{l-\left(\beta \,-1\right)}\log _{2}\left(i\right)&{\text{ if }}\beta \,\geq \,1,l\geq \,1\end{cases}}}

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 one can often assume that β = 1 {\displaystyle \beta \,=1} . 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. These extra bits of entropy will not apply to other mmap() segments, only libraries.

Reducing entropy

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 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 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 log 2 ( n ) {\displaystyle \log _{2}\!\left(n\right)} for n intervals attacked.

Such decreases are limited due to the amount of data in the stack or heap. The stack, for example, is typically limited to 8 MB 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–16 KB 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 128 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.

Limitations

ASLR-protected addresses can be leaked by various side channels, removing mitigation utility. Recent attacks have used information leaked by the CPU branch target predictor buffer (BTB) or memory management unit (MMU) walking page tables. It is not clear if this class of ASLR attack can be mitigated. If they cannot, the benefit of ASLR is reduced or eliminated.

Empirical analysis

In August 2024 a paper was published with an empirical analysis of major desktop platforms, including Linux, macOS, and Windows, by examining the variability in the placement of memory objects across various processes, threads, and system restarts. The results show that while some systems as of 2024, like Linux distributions, provide robust randomization, others, like Windows and macOS, often fail to adequately randomize key areas like executable code and libraries. Moreover, they found a significant entropy reduction in the entropy of libraries after the Linux 5.18 version and identify correlation paths that an attacker could leverage to reduce exploitation complexity significantly.

Implementations

Several mainstream, general-purpose operating systems implement ASLR.

Android

Android 4.0 Ice Cream Sandwich provides address space layout randomization (ASLR) to help protect system and third-party applications from exploits due to memory-management issues. Position-independent executable support was added in Android 4.1. Android 5.0 dropped non-PIE support and requires all dynamically linked binaries to be position independent. Library load ordering randomization was accepted into the Android open-source project on 26 October 2015, and was included in the Android 7.0 release.

DragonFly BSD

DragonFly BSD has an implementation of ASLR based upon OpenBSD's model, added in 2010. It is off by default, and can be enabled by setting the sysctl vm.randomize_mmap to 1.

FreeBSD

Support for ASLR appeared in FreeBSD 13.0. It is enabled by default since 13.2.

iOS (iPhone, iPod touch, iPad)

Apple introduced ASLR in iOS 4.3 (released March 2011).

KASLR was introduced in iOS 6. The randomized kernel base is 0x01000000 + ((1+0xRR) * 0x00200000), where 0xRR is a random byte from SHA1 (random data) generated by iBoot (the 2nd-stage iOS Boot Loader).

Linux

The Linux kernel enabled a weak form of ASLR by default since the kernel version 2.6.12, released in June 2005. The PaX and Exec Shield patchsets to the Linux kernel provide more complete implementations. 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 4096 bytes. This places the stack base in an area 8 MB wide containing 524,288 possible positions, and the mmap base in an area 1 MB wide containing 256 possible positions.

ASLR can be disabled for a specific process by changing its execution domain, using personality(2). A number of sysctl options control the behavior of mainline ASLR. For example, kernel.randomize_va_space controls what to randomize; the strongest option is 2. vm.mmap_rnd_bits controls how many bits to randomize for mmap.

Position-independent executable (PIE) implements a random base address for the main executable binary and has been in place since April 18, 2004. It provides the same address randomness to the main executable as being used for the shared libraries. The PIE feature cannot be used together with the prelink feature for the same executable. 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.

In 2014, Marco-Gisbert and Ripoll disclosed offset2lib technique that weakens Linux ASLR for PIE executables. Linux kernels load PIE executables right after their libraries; as a result, there is a fixed offset between the executable and the library functions. If an attacker finds a way to find the address of a function in the executable, the library addresses are also known. They demonstrated an attack that finds the address in fewer than 400 tries. They proposed a new randomize_va_space=3 option to randomize the placement of the executable relative to the library, but it is yet to be incorporated into the upstream as of 2024.

The Linux kernel 5.18 released May 2022 reduced the effectiveness of both 32-bit and 64-bit implementations. Linux filesystems call thp_get_unmapped_area to respond to a file-backed mmap. With a change in 5.18, files greater than 2 MiB are made to return 2 MiB-aligned addresses, so they can be potentially backed by huge pages. (Previously, the increased alignment only applied to Direct Access (DAX) mappings.) In the meantime, the C library (libc) has, over time, grown in size to exceed this 2 MiB threshold, so instead of being aligned to a (typically) 4 KiB page boundary as before, these libraries are now 2 MiB-aligned: a loss of 9 bits of entropy. For 32-bit Linux, many distributions show no randomization at all in the placement of the libc. For 64-bit Linux, the 28 bits of entropy is reduced to 19 bits. In response, Ubuntu has increased its mmap_rnd_bits setting. Martin Doucha added a Linux Test Project testcase to detect this issue.

Kernel address space layout randomization

Kernel address space layout randomization (KASLR) enables address space randomization for the Linux kernel image by randomizing where the kernel code is placed at boot time. KASLR was merged into the Linux kernel mainline in kernel version 3.14, released on 30 March 2014. When compiled in, it can be disabled at boot time by specifying nokaslr as one of the kernel's boot parameters.

There are several side-channel attacks in x86 processors that could leak kernel addresses. In late 2017, kernel page-table isolation (KPTI aka KAISER) was developed to defeat these attacks. However, this method cannot protect against side-channel attacks utilizing collisions in branch predictor structures.

As of 2021, finer grained kernel address space layout randomization (or function granular KASLR, FGKASLR) is a planned extension of KASLR to randomize down to the function level by placing functions in separate sections and reordering them at boot time.

Microsoft Windows

This section needs to be updated. Please help update this article to reflect recent events or newly available information. (August 2018)

Microsoft's Windows Vista (released January 2007) and later have ASLR enabled only for executables and dynamic link libraries that are specifically linked to be ASLR-enabled. For compatibility, it is not enabled by default for other applications. Typically, only older software is incompatible and ASLR can be fully enabled by editing a registry entry HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management\MoveImages, or by installing Microsoft's Enhanced Mitigation Experience Toolkit.

The locations of the heap, stack, Process Environment Block, and Thread Environment Block are also randomized. A security whitepaper from Symantec noted that ASLR in 32-bit Windows Vista may not be as robust as expected, and Microsoft has acknowledged a weakness in its implementation.

Host-based intrusion prevention systems such as WehnTrust and Ozone also offer ASLR for Windows XP and Windows Server 2003 operating systems. WehnTrust is open-source. Complete details of Ozone's implementation are not available.

It was noted in February 2012 that ASLR on 32-bit Windows systems prior to Windows 8 can have its effectiveness reduced in low memory situations. A similar effect also had been achieved on Linux in the same research. The test code caused the Mac OS X 10.7.3 system to kernel panic, so it was left unclear about its ASLR behavior in this scenario.

NetBSD

Support for ASLR in userland appeared in NetBSD 5.0 (released April 2009), and was enabled by default in NetBSD-current in April 2016.

Kernel ASLR support on amd64 was added in NetBSD-current in October 2017, making NetBSD the first BSD system to support KASLR.

OpenBSD

In 2003, OpenBSD became the first mainstream operating system to support a strong form of ASLR and to activate it by default. OpenBSD completed its ASLR support in 2008 when it added support for PIE binaries. OpenBSD 4.4's malloc(3) was designed to improve security by taking advantage of ASLR and gap page features implemented as part of OpenBSD's mmap system call, and to detect use-after-free bugs. Released in 2013, OpenBSD 5.3 was the first mainstream operating system to enable position-independent executables by default on multiple hardware platforms, and OpenBSD 5.7 activated position-independent static binaries (Static-PIE) by default.

macOS

In Mac OS X Leopard 10.5 (released October 2007), Apple introduced randomization for system libraries.

In Mac OS X Lion 10.7 (released July 2011), Apple expanded their implementation to cover all applications, stating "address space layout randomization (ASLR) has been improved for all applications. It is now available for 32-bit apps (as are heap memory protections), making 64-bit and 32-bit applications more resistant to attack."

As of OS X Mountain Lion 10.8 (released July 2012) and later, the entire system including the kernel as well as kexts and zones are randomly relocated during system boot.

Solaris

ASLR has been introduced in Solaris beginning with Solaris 11.1 (released October 2012). ASLR in Solaris 11.1 can be set system-wide, per zone, or on a per-binary basis.

Exploitation

A side-channel attack utilizing branch target buffer was demonstrated to bypass ASLR protection. In 2017, an attack named "ASLR⊕Cache" was demonstrated which could defeat ASLR in a web browser using JavaScript.

See also

References

  1. Marco-Gisbert, Hector; Ripoll Ripoll, Ismael (2019-07-22). "Address Space Layout Randomization Next Generation". Applied Sciences. 9 (14): 2928. doi:10.3390/app9142928. hdl:10251/144813. ISSN 2076-3417.
  2. Brad Spengler (October 2003). "PaX: The Guaranteed End of Arbitrary Code Execution" (PDF). grsecurity.net. Slides 22 through 35. Archived (PDF) from the original on 2020-10-25. Retrieved 2015-08-20.
  3. ^ Theo De Raadt (2005). "Exploit Mitigation Techniques (updated to include random malloc and mmap) at OpenCON 2005". Archived from the original on 2012-07-16. Retrieved 2009-08-26.
  4. "OpenBSD Innovations". The OpenBSD project. Archived from the original on 2016-09-09. Retrieved 2016-09-12.
  5. ^ Marco-Gisbert, Hector; Ripoll, Ismael (2014-11-20). "On the Effectiveness of Full-ASLR on 64-bit Linux" (PDF). Archived from the original (PDF) on 2015-05-08. Retrieved 2016-03-29.
  6. Shacham, H.; Page, M.; Pfaff, B.; Goh, E.J.; Modadugu, N.; Boneh, D (2004). On the Effectiveness of Address-Space Randomization. 11th ACM conference on Computer and communications security. pp. 298–307.
  7. ^ "Implement Library Load Order Randomization". Archived from the original on 2023-08-11. Retrieved 2017-06-26.
  8. ^ Transistorized memory, such as RAM, ROM, flash and cache sizes as well as file sizes are specified using binary meanings for K (1024), M (1024), G (1024), etc.
  9. Binosi, Lorenzo; Barzasi, Gregorio; Carminati, Michele; Zanero, Stefano; Polino, Mario (2024). "The Illusion of Randomness: An Empirical Analysis of Address Space Layout Randomization Implementations". arXiv:2408.15107 .
  10. "Android Security". Android Developers. Archived from the original on 2011-10-12. Retrieved 2012-07-07.
  11. "oss-security". Archived from the original on 2015-10-05. Retrieved 2015-10-04.
  12. "Revert "Reenable support for non-PIE executables"". Archived from the original on 2023-08-11. Retrieved 2017-06-26.
  13. mmap - add mmap offset randomization Archived 2014-02-01 at the Wayback Machine, DragonFly Gitweb, 25 November 2010.
  14. "Implement Address Space Layout Randomization (ASLR)". Archived from the original on 2019-05-07. Retrieved 2019-02-10.
  15. "ASLR - FreeBSD Wiki". Archived from the original on 2021-05-17. Retrieved 2021-05-17.
  16. "FreeBSD 13.2-RELEASE Release Notes". Archived from the original on 2023-04-11. Retrieved 2023-04-11.
  17. Pwn2Own day 2: iPhone, BlackBerry beaten; Chrome, Firefox no-shows Archived 2012-05-02 at the Wayback Machine, Ars Technica, 11 March 2011
  18. Stefan Esser (2013-03-07). "iOS 6 Exploitation 280 Days Later". Slide 19, "iOS 6 introduces KASLR". Archived from the original on 2019-05-07. Retrieved 2018-04-25.
  19. Tarjei Mandt. "Attacking the iOS Kernel: A Look at 'evasi0n'" (PDF). Archived (PDF) from the original on 2020-12-13. Retrieved 2023-07-23.
  20. Dang, Alan; Miller, Charlie (2009-03-25). "The NX Bit And ASLR". Tom's Hardware. Archived from the original on 2023-08-11. Retrieved 2010-03-20.
  21. personality(2) – Linux Programmer's Manual – System Calls
  22. "[PATCH] ASLRv3: randomize_va_space=3 preventing offset2lib attack". lore.kernel.org.
  23. Miller, Justin (2024-01-08). "ASLRn't: How memory alignment broke library ASLR". zolutal's blog. Retrieved 2024-01-13.
  24. "[LTP] [PATCH 2/2] Add test for ASLRn't bug - Martin Doucha". lore.kernel.org.
  25. Jake Edge (2013-10-09). "Kernel address space layout randomization". LWN.net. Archived from the original on 2014-04-04. Retrieved 2014-04-02.
  26. "Linux kernel 3.14, Section 1.7. Kernel address space randomization". kernelnewbies.org. 2014-03-30. Archived from the original on 2021-01-15. Retrieved 2014-04-02.
  27. "kernel/git/torvalds/linux.git: x86, kaslr: Return location from decompress_kernel (Linux kernel source tree)". kernel.org. 2013-10-13. Archived from the original on 2023-08-11. Retrieved 2014-04-02.
  28. KASLR is Dead: Long Live KASLR (PDF). Engineering Secure Software and Systems 2017. 2017-06-24.
  29. Jang, Yeongjin; Lee, Sangho; Kim, Taesoo (2016). "Breaking Kernel Address Space Layout Randomization with Intel TSX" (PDF). Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. CCS '16. New York: Association for Computing Machinery. pp. 380–392. doi:10.1145/2976749.2978321. ISBN 9781450341394. S2CID 6293725. Archived (PDF) from the original on 2020-09-21. Retrieved 2017-12-29.
  30. Corbet, Jonathan (2017-12-20). "The current state of kernel page-table isolation". Linux Weekly News. Archived from the original on 2018-01-04. Retrieved 2018-01-04.
  31. Corbet, Jonathan (2017-11-15). "KAISER: hiding the kernel from user space". Linux Weekly News. Archived from the original on 2020-12-08. Retrieved 2017-12-29.
  32. ^ Evtyushkin, Dmitry; Ponomarev, Dmitry; Abu-Ghazaleh, Nael (2016). Jump over ASLR: Attacking branch predictors to bypass ASLR (PDF). 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). pp. 1–13. doi:10.1109/MICRO.2016.7783743. ISBN 978-1-5090-3508-3. S2CID 3801142.
  33. "Linux 5.16 Has Early Preparations For Supporting FGKASLR - Phoronix". www.phoronix.com. Archived from the original on 2021-11-10. Retrieved 2021-11-10.
  34. "Windows ISV Software Security Defenses". Msdn.microsoft.com. 2010-12-06. Archived from the original on 2012-04-18. Retrieved 2012-04-10.
  35. Windows Internals: Including Windows Server 2008 and Windows Vista, Fifth Edition (PRO-Developer) ISBN 978-0-7356-2530-3
  36. Ollie Whitehouse (February 2007). "An Analysis of Address Space Layout Randomization on Windows Vista" (PDF). Archived from the original (PDF) on 2019-07-15. Retrieved 2009-01-18.
  37. "WehnTrust". Codeplex.com. Archived from the original on 2009-12-25. Retrieved 2012-04-10.
  38. "Security Architects' Ozone". Security Architects. Archived from the original on 2016-03-04. Retrieved 2012-04-10.
  39. "WehnTrust source code". Archived from the original on 2013-11-28. Retrieved 2013-11-15.
  40. "Address-Space Randomization for Windows Systems" (PDF). Archived (PDF) from the original on 2010-08-05. Retrieved 2012-04-10.
  41. Ollie (2012-03-02). "Research, Develop, Assess, Consult & Educate | Recx: A Partial Technique Against ASLR – Multiple O/Ss". Recxltd.blogspot.co.uk. Archived from the original on 2013-03-23. Retrieved 2012-04-10.
  42. "Announcing NetBSD 5.0". Archived from the original on 2016-04-21. Retrieved 2016-04-25.
  43. Christos Zoulas (2016). "PIE binaries and ASLR are on in the default build for amd64". Archived from the original on 2016-04-22. Retrieved 2016-04-25.
  44. "Kernel ASLR on amd64". 2017. Archived from the original on 2017-10-16. Retrieved 2017-10-16.
  45. ^ Kurt Miller (2008). "OpenBSD's Position Independent Executable (PIE) Implementation". Archived from the original on 2011-06-12. Retrieved 2011-07-22.
  46. "libc/stdlib/malloc.c". BSD Cross Reference, OpenBSD src/lib/. Archived from the original on 2014-12-26. Retrieved 2016-09-12.
  47. "Mac OS X – Security – Keeps safe from viruses and malware". Apple. Archived from the original on 2011-05-25. Retrieved 2012-04-10.
  48. "Security". Apple Inc. Archived from the original on 2011-06-06. Retrieved 2011-06-06.
  49. "OS X Mountain Lion Core Technologies Overview" (PDF). June 2012. Archived (PDF) from the original on 2012-07-10. Retrieved 2012-07-25.
  50. Controlling Access to Machine Resources Archived 2013-06-20 at the Wayback Machine, Oracle Information Library, 26 October 2012.
  51. AnC Archived 2017-03-16 at the Wayback Machine VUSec, 2017

External links

Category: