ASLR
Needs ReviewPublic

Authored by kib on Mar 10 2016, 3:55 PM.

Details

Reviewers
emaste
Summary

With this change, randomization is applied to all non-fixed mappings.
By randomization I mean the base address for the mapping is selected
with a guaranteed amount of entropy (bits). If the mapping was
requested to be superpage aligned, the randomization honours
the superpage attributes.

The randomization is done on a best-effort basis - that is, the
allocator falls back to a first fit strategy if fragmentation
prevents entropy injection. It is trivial to implement a strong mode
where failure to guarantee the requested amount of entropy results in
mapping request failure, but I do not consider that to be usable.

I have not fine-tuned the amount of entropy injected right now. It is
only a quantitive change that will not change the implementation.
The current amount is controlled by aslr_pages_rnd.

To not spoil coalescing optimizations, to reduce the page table
fragmentation inherent to ASLR, and to keep the transient superpage
promotion for the malloced memory, the locality is implemented for
anonymous private mappings, which are automatically grouped until
fragmentation kicks in. The initial location for the anon group range
is, of course, randomized.

The default mode keeps the sbrk area unpopulated by other mappings,
but this can be turned off, which gives much more breathing bits on
the small AS architectures (funny that 32bits is considered small).
This is tied with the question of following an application's hint
about the mmap(2) base address. Testing shows that ignoring the hint
does not affect the function of common applications, but I would expect
more demanding code could break. By default sbrk is preserved and mmap
hints are satisfied, which can be changed by using the
kern.elf{32,64}.aslr_care_sbrk sysctl.

Stack gap, W^X, shared page randomization, KASLR and other techniques
are explicitely out of scope of this work.

The paxtest results for the run with the patch applied and aggresively
tuned can be seen at the https://www.kib.kiev.ua/kib/aslr/paxtest.log .
For comparision, the run on Fedora 23 on the same machine is at
https://www.kib.kiev.ua/kib/aslr/fedora.log .

ASLR is enabled on per-ABI basis, and currently it is only enabled on
native i386 and amd64 (including compat 32bit) ABIs. I expect to test
and enable ASLR for armv6 and arm64 as well, later.

The procctl(2) control for ASLR is implemented, by I have not provided
a userspace wrapper around the syscall. In fact, the most reasonable
control needed is per-image and not per-process, but we have no
tradition to put the kernel-read attributes into the extattrs of binary,
so I am still pondering that part and this also explains the non-written
tool.

Diff Detail

Repository
rS FreeBSD src repository
Lint
Lint Skipped
Unit
Unit Tests Skipped
Build Status
Buildable 7853
There are a very large number of changes, so older changes are hidden. Show Older Changes
emaste added a subscriber: emaste.Mar 10 2016, 4:04 PM
sys/kern/imgact_elf.c
917

One of the reservations FreeBSD had about HardenedBSD's patch was that it was setting this particular variable multiple times. I guess that's not a concern anymore?

sys/vm/vm_map.c
1621

If I'm reading this correctly (and forgive me if I'm not), does this mean that if an attacker puts too much pressure on the VM subsystem (via heap spraying or other attacks), the attacker could effectively disable ASLR?

Things that are missing from this patch to make this ASLR implementation complete:

  1. True stack randomization + stack gap
  2. VDSO randomization

Kostik mentioned that both of those are outside the scope of this patch. However, I disagree. If the address space isn't fully randomized, ASLR is ineffective. Especially the VDSO, which contains executable code that can be used with ROP and its variants.

feld added a subscriber: feld.Mar 10 2016, 4:51 PM
emaste added inline comments.Mar 10 2016, 5:01 PM
sys/kern/imgact_elf.c
917

The comment was about minimizing diffs, not about setting the variable multiple times per se. I suspect the comment in D473 was motivated by the size of that review, based on a desire to minimize the scale of changes in order to ease the review.

That said, this change and and other non-functional changes in this review could be committed separately too.

sys/kern/kern_procctl.c
452

FreeBSD users should know that an attacker can abuse this API to disable ASLR.

emaste added inline comments.Mar 10 2016, 6:59 PM
sys/kern/kern_procctl.c
452

This also raises the point that PROC_ASLR_CTL needs to be documented in procctl(2)

sys/vm/vm_map.c
1596

What is the performance penalty of calling arc4random() on each call to mmap(NULL, MAP_ANON), sometimes multiple times?

sys/vm/vm_map.c
1596

How much does calling arc4random() cost in address space fragmentation on each call to mmap(NULL, MAP_ANON) when coalescing cannot happen?

sys/kern/imgact_elf.c
944

This changes the underlying meaning of the et_dyn_addr variable. Though I don't object to it, I just thought it is worth the note. The author of later modifications to this code will need to keep that in mind. Maybe a comment in the code would be a good idea?

bdrewery added inline comments.
sys/kern/kern_procctl.c
452

Perhaps it should be sysctl+securelevel protected.

kib added inline comments.Mar 11 2016, 5:58 PM
sys/kern/kern_procctl.c
452

Why ? Did you read the code ? It only affects the policy for the new address space after exec.

That said, to successfully call procctl(2), you must have debugging privilege on the target process. So you can either debug the target, or you are doing it against yourself (which means that malicious code is already executing in this address space). Why do you need to disable something similar to ASLR at all, then ?

https://blogs.msdn.microsoft.com/oldnewthing/20071031-00/?p=24633/

op added a subscriber: op.Mar 11 2016, 11:18 PM
op added inline comments.Mar 11 2016, 11:51 PM
sys/kern/imgact_elf.c
141

The current implementation is an ASR and not ASLR, please correct them and the word of ASLR is an acronym, so please convert them to upper case.

944

Could you please use a defined name here instead of a raw value?

For example #define ET_DYN_LOAD_RAND_ADDR or something similar?

982

Why you need two arc4random() call on 64 bit systems?

This is the arc4random()'s implementation:

uint32_t
arc4random(void)
{
        uint32_t ret;

        arc4rand(&ret, sizeof ret, 0);
        return ret;
}

Just change this two call to simple one:

arc4rand(&rbase, sizeof(rbase), 0) or arc4rand(&rbase, __ELF_WORD_SIZE / NBBY, 0)

sys/vm/vm_map.c
1474

Missing description.

1479

Here too.

1569

Typo here, you should write ASR in the comment instead of ASLR.

1596

You should not generate new random number on every mmap call, you should just generate one at exec() time, and apply them all the times when mmap called.

The relevant parts from the original ASLR author's design documentation:

PaX can apply ASLR to tasks that are created from ELF executables and
use ELF libraries. The randomized layout is determined at task creation
time in the load_elf_binary() function in fs/binfmt_elf.c where three per
task (or more precisely, mm_struct) variables are initialized with random
numbers: delta_exec, delta_mmap and delta_stack.
The last set of side effects of ASLR is address space fragmentation and
entropy pool exhaustion. Since randomization shifts entire ranges of memory,
it will also randomly change the gaps between them (which were constant
before). This in turn will change the maximum size of memory mappings that
will fit in there and applications expecting to be able to create them will
fail. Finally, ASLR increases the consumption of the system's entropy pool
since every task creation (through the execve() system call) requires some
bits of randomness to determine the new address space layout. Depending on
the system's threat model however a given implementation can relax the
requirements for the quality of this entropy. In particular, if only remote
attacks are considered, then ASLR does not need cryptographically secure
random bits as a remote attacker cannot observe them (or if he can, he does
not need to care about ASLR at all).

https://pax.grsecurity.net/docs/aslr.txt

emaste added inline comments.Mar 12 2016, 2:19 AM
sys/kern/imgact_elf.c
141

The current implementation is an ASR and not ASLR

I'm not sure how to parse this statement.

the word of ASLR is an acronym, so please convert them to upper case.

No, by convention sysctl notes are lower case - e.g net.inet.tcp, not net.inet.TCP. On my system, of 3397 sysctls only 42 have upper case characters, and those are programmatically generated from existing names (e.g. kern.timecounter.tc.TSC-low.quality).

944

I agree with avoiding an uncommented magic number.

sys/vm/vm_map.c
1596

You should not generate new random number on every mmap call

Why is it preferable to have mappings at fixed offsets from each other?

Also, "entropy pool exhaustion" is not a relevant concept here.

sys/vm/vm_map.c
1596

Why is it preferable to have mappings at fixed offsets from each other?

because that's the 'L' in ASLR :). per-mapping randomization is ASR as mentioned somewhere above already, see also KASLR: An Exercise in Cargo Cult Security. in practice libc and other common and big enough libraries contain a Turing complete gadget set so it makes no difference to an attacker whether everything else is randomized independently or not. on the other hand ASR has the drawback (that @kib incorrectly associated with ASLR) of unnecessarily fragmenting the virtual address space (a real issue on 32 bit archs even back in 2001) and thus increase page table usage for no net gain in security.

emaste added inline comments.Mar 12 2016, 8:35 PM
sys/vm/vm_map.c
1596

because that's the 'L' in ASLR

That seems like a circular justification. The layout of objects in the address space is being randomized, regardless of whether or not they remain at fixed offsets to each other.

There's another axis to consider when we evaluate any change like this and that's the complexity; all else being equal errors are more likely in larger and more complex changes, and that's an argument in favour of a smaller change, regardless of whether or not it has any other benefit.

kib added inline comments.Mar 12 2016, 9:02 PM
sys/vm/vm_map.c
1596

Correctly implementing something which keeps fixed offsets between mappings (same as they happen to occur in the address space layout without any snake oil spread over) is actually not trivial if ever possible.

Thing is, some mappings must appear at the ABI-fixed locations. E.g., if you have non-PIE binary, it is mapped where the linker loaded it. Main stack must be contiguously mapped from top of the user memory down, code which crawls around ps_strings expect that etc. The result is that the anchors affect the allocator if you provide tilted hint to the mapping base. And, of course, you cannot just do (hint + offset) mod size, because of that mappings.

In other words, so proclaimed 'simple shift' actually is not that simple. Then you have to note that there is very little available shift values for small (32bit) address spaces, when you also must not destroy the superpage-friendly alignment. So while you could somewhat get away with shift on large AS (64bit), although you sacrifice significant portion of the address space to be unused, you cannot get away with it on 32bit.

At the end, doing proper randomization of each mapping appear to be both simpler from the architectural PoV (resulting in concise code) and ease to reason (as in, not only observing) to verify correctness.

Of course, issue of AS and page tables fragmentation is there, but mitigated by the anon coalescing. Numbers might come.

sys/vm/vm_map.c
1596

The layout of objects in the address space is being randomized, regardless of whether or not they remain at fixed offsets to each other.

given that i coined the term ASLR in the first place, allow me to know better than you what it actually means. the Layout in ASLR explicitly refers to how a typical process virtual address space is laid out based on regions (roughly main executable+brk, mmap region, stack) and how it is enough to randomize the base address of those regions for the purposes of ASLR.

as for complexity, ASLR (as implemented in PaX) would be similar amount of code to what you're discussing here.

1596

Correctly implementing something which keeps fixed offsets between mappings (same as they happen
to occur in the address space layout without any snake oil spread over) is actually not trivial if ever possible.

it is not only possible but trivial, the living example is PaX and its ASLR implementation that hasn't changed in any fundamental ways for 15 years.

Thing is, some mappings must appear at the ABI-fixed locations.

there's exactly one such rule that one must obey (MAP_FIXED), everything else can be freely randomized.

Main stack must be contiguously mapped from top of the user memory down,

no, there's no such ABI rule, in fact it's trivial to map the main stack anywhere in the address space.

code which crawls around ps_strings expect that etc.

that's a bug/feature in your implementation, nothing to do with any ABI 'rule'. fix it and you can move even the main stack around in arbitrary ways (though ASLR still observes the layout in that it tries to keep the primary stack as the highest map during execve, it's just not enforced later).

In other words, so proclaimed 'simple shift' actually is not that simple.

why is that? have you tried to implement it? have you looked at existing implementations? the thing is, there's nothing complex with region base address randomization, all you need is a per address space random constant to use for address space hole lookups in mmap (see mm_struct.mmap_base and delta_mmap in PaX).

Then you have to note that there is very little available shift values for small (32bit) address spaces,
when you also must not destroy the superpage-friendly alignment.

superpage allocations are orthogonal to ASLR. aligned allocations will be aligned with correspondingly less randomization, the rest will be randomized as much as the region base address and previous allocations (all depends on the 'find the requested address space hole' algo) allow.

At the end, doing proper randomization of each mapping appear to be both simpler from the architectural
PoV (resulting in concise code)

you could make this claim only after you have implemented ASLR as well, then you'd have a basis for comparison. till then it's pure speculation (unfounded too, as far as i can tell based on my own experience).

and ease to reason (as in, not only observing) to verify correctness.

what is 'correctness' here? your current code and explicit omission of stack/etc randomization, no words on brute force prevention, no handling of address space exhaustion attacks, etc show that you're very far from anything that i'd consider correct.

as for observation, your use of paxtest to show numbers of your ASR implementation is fundamentally wrong because its measurement algo was written specifically for ASLR, it cannot and will not produce correct values for ASR.

given that i coined the term ASLR in the first place, allow me to know better than you what it actually means.

My comment is based only on the term ASLR having been used generically for some time to refer to many related implementations. For better or worse I think absent a specific phrase like "PaX ASLR" there is no conclusion to be drawn about the nature of the implementation.

Anyway, the naming (and descriptions) of these sysctls is a relatively inconsequential point for consideration later on if or when the patch in this review is ready to be committed.

My comment is based only on the term ASLR having been used generically for some time to refer to many related implementations. For better or worse I think absent a specific phrase like "PaX ASLR" there is no conclusion to be drawn about the nature of the implementation.

Anyway, the naming (and descriptions) of these sysctls is a relatively inconsequential point for consideration later on if or when the patch in this review is ready to be committed.

nomen est omen. it's important to know what the terms you use mean otherwise you will end up with a cargo cult implementation only (wouldn't be the first one, see OpenBSD), not actual security. at least i assume this is why you asked about ASR vs. ASLR and which can only be explained if you go back to their roots.

nomen est omen. it's important to know what the terms you use mean

Fair enough, names indeed have meaning. Anyway, a small issue for later on.

swills added a subscriber: swills.Mar 13 2016, 11:09 PM
sys/kern/imgact_elf.c
141

No, by convention sysctl notes are lower case

Sigh, that should have been 'nodes' are lower case. The sysctl description here should indeed be a capitalized ASLR.

as for observation, your use of paxtest to show numbers of your ASR implementation is fundamentally wrong because its measurement algo was written specifically for ASLR, it cannot and will not produce correct values for ASR.

It calculates the number of bits which change after repeating the same measurement (e.g. of a shared library load address) in a loop. Can you explain how that produces an incorrect result for the patch in this review?

It calculates the number of bits which change after repeating the same measurement (e.g. of a shared library load address) in a loop. Can you explain how that produces an incorrect result for the patch in this review?

the paxtest algo does not only count the number of changing bits, but it also assumes that the randomness is uniformly distributed among those bits which is true for a per-region ASLR (inasmuch we trust the kernel's prng to produce uniformly distributed numbers and ignore variable length maps) but it's not true for per-mmap randomization (because the distribution of a sum of uniformly distributed random variables is not uniformly distributed but anneals a gaussian one according to the central limit theorem, and the code you have here is even more complicated than a mere sum of random variables due to the coalescing of anon maps tweak). in other words, just because N bits are changing in addresses doesn't mean that all of those values are equally likely (or possible at all) thus you need a more general measurement algo than what paxtest has (and even paxtest doesn't accurately measure ASLR in certain corner cases).

xmj added a subscriber: xmj.Mar 23 2016, 7:28 AM
danilo added a subscriber: danilo.Apr 9 2016, 6:51 PM

It has been a little over a month and a half. Just checking in. Any updates to this ASR patch?

garga added a subscriber: garga.Aug 16 2016, 9:19 AM
emaste requested changes to this revision.Oct 3 2016, 7:44 PM
emaste added a reviewer: emaste.

Needs a rebase to apply cleanly

sys/compat/freebsd32/freebsd32_misc.c
2991–2994

Perhaps keep these in alpha order?

This revision now requires changes to proceed.Oct 3 2016, 7:44 PM
kib updated this revision to Diff 21000.Oct 3 2016, 8:55 PM

Rebased after TRAPCAP changes and import of proccontrol.

Should the various macros, variables, and enums reflect ASR instead of ASLR?

emaste added a comment.Oct 4 2016, 1:10 AM

Should the various macros, variables, and enums reflect ASR instead of ASLR?

I'm indifferent on this point. Terms have a tendency to become generic, like thermos or dumpster, and ASLR is arguably in the same state. I don't see complaints over references to ASLR with respect to other operating systems that don't follow the PaX implementation, and I think that for the vast majority of users it is not a meaningful distinction.

Are you aware of a useful reference that compares the ASL?R implementations of different operating systems?

Should the various macros, variables, and enums reflect ASR instead of ASLR?

I'm indifferent on this point. Terms have a tendency to become generic, like thermos or dumpster, and ASLR is arguably in the same state. I don't see complaints over references to ASLR with respect to other operating systems that don't follow the PaX implementation, and I think that for the vast majority of users it is not a meaningful distinction.

So, I'm not saying that following the PaX model is required in order to be able to call an implementation ASLR instead of ASR. The main technical difference between ASLR and ASR comes down to the use of deltas computed at execve time. More differences are below.

There are technical differences. ASR has a measurable performance hit; ASLR does not. ASR randomizes every call to mmap (with certain conditions, like !MAP_FIXED); ASLR uses deltas. Address Space (AS) fragmentation can become a real problem with ASR; not so with ASLR. In this specific implementation, if the AS becomes too fragmented, ASR is disabled for the lifetime of the process; ASLR wouldn't have that issue.

From a non-technical standpoint, I think it'd work in FreeBSD's best interest to show those technical differences by calling this patch ASR as it truly is instead of ASLR. FreeBSD would be telling the world "we think ASR is better."

emaste added a comment.Oct 4 2016, 1:40 PM

So, I'm not saying that following the PaX model is required in order to be able to call an implementation ASLR instead of ASR. The main technical difference between ASLR and ASR comes down to the use of deltas computed at execve time. More differences are below.

I understand that, my point is that like it or not, it seems ASLR has come to be used to encompass a number of different techniques for randomizing the location of objects in the address space of a process. Either way, any user-facing interface (sysctls, procctl args, etc.) provided for controlling aspects of the memory address randomization system should not change if the implementation details do.

kib updated this revision to Diff 21029.Oct 4 2016, 3:46 PM

Re-merge after r306674.

emaste added a comment.Oct 4 2016, 6:16 PM

ASR has a measurable performance hit; ASLR does not.

I'd be quite interested in the detail here if you can provide a link or reference to this.

ASR has a measurable performance hit; ASLR does not.

I'd be quite interested in the detail here if you can provide a link or reference to this.

How expensive is pulling from the entropy pool at least once, at most five times, per call to mmap?

emaste added a comment.Oct 4 2016, 6:26 PM

How expensive is pulling from the entropy pool at least once, at most five times, per call to mmap?

You said it has a measurable performance hit, so I'm curious what that is.

How expensive is pulling from the entropy pool at least once, at most five times, per call to mmap?

You said it has a measurable performance hit, so I'm curious what that is.

Once I'm done with the latest package builds for HardenedBSD, I'd be happy to do exp-runs with this patch.

emaste added inline comments.Oct 6 2016, 7:09 PM
sys/kern/imgact_elf.c
141

the acronym should probably be expanded; aslr_enabled with a description "enable alsr" doesn't provide any extra information. maybe "enable map address randomization"?

150

aslr_care_sbrk seems strange. perhaps honor_sbrk?

944

Can you #define or at least comment this 1

kib updated this revision to Diff 21125.Oct 6 2016, 7:46 PM

Emaste' notes.

jmallett added inline comments.
sys/kern/imgact_elf.c
995

The assertion description would be clearer if this said ET_DYN_ADDR_RAND instead of et_dyn_addr.

kib updated this revision to Diff 21262.Oct 11 2016, 5:22 PM

Improve assertion message.

For reference Illumos' initial implementation landed in https://github.com/illumos/illumos-gate/commit/d2a70789f056fc6c9ce3ab047b52126d80b0e3da

One interesting part of their change is the DT_SUNW_ASLR dyn tag. If it's set to 1 it enables randomization for the process, if set to 0 it disables, and if the tag is not present it uses the system default.

kib added a comment.Oct 18 2016, 10:12 AM

One interesting part of their change is the DT_SUNW_ASLR dyn tag. If it's set to 1 it enables randomization for the process, if set to 0 it disables, and if the tag is not present it uses the system default.

This is quite close to what I want to do for us, but not same. I plan to have a note in the binaries which specifies imgact flags. We already have note parser in kernel, so the addition should be natural. Of course, a tool which parses and modifies the note should be written as well, probably using libelf.

But I do not see much sense to do it until the current patch is reviewed and committed. For testing purposes, proccontrol(1) is good enough.

emaste added inline comments.Oct 20 2016, 8:36 PM
sys/kern/kern_procctl.c
561–562

Absent a need for a specific order I think we should prefer alphabetical ordering for lists like this.

I had sorted them in my local tree, and have put that change in D8304.

usr.bin/proccontrol/proccontrol.c
66

The usage at least should be in alpha order, which will match the eventual man page.

kib updated this revision to Diff 21582.Oct 21 2016, 8:15 AM

Applied D8304.

emaste requested changes to this revision.Wed, Mar 1, 9:44 PM

Needs to be rebased after conflicts in at least rS314489

This revision now requires changes to proceed.Wed, Mar 1, 9:44 PM
kib added a comment.Thu, Mar 2, 11:35 AM

Needs to be rebased after conflicts in at least rS314489

I am in the process of merging minor self-contained fuzz from the patch, so it will be in disturbance for some time.

kib updated this revision to Diff 25878.Thu, Mar 2, 11:35 AM

Current diff.