Skip to contentSkip to conversation

Per-architecture randomization

RFC In review John Richard Moser 2 participants 8 messages Jun 4, 2006

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

RFC 1/1 Per-architecture randomization

Pavel Machek recommended per-architecture randomization defaults when I poked a (very hackish) patch up here. As follow-up, I have taken out the command line parameter code and used the infrastructure I wrote to implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in include/asm-ARCH/processor.h or equivalent. These defines are as follows:

STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
If not defined, stack randomization is carried out to page granularity
ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
If not defined, stack randomization is disabled by defining this as 0.
ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
If not defined, mmap() randomization is disabled by defining this as 0.

I have added these for each of i386 and x86-64. In the case of x86-64, the last two are complex ones similar to how TASK_SIZE is done. Other architectures need these defines, and I am certain I disabled randomization everywhere else doing this; but as far as I can tell, the code only was randomizing the stack at page-granularity anyway everywhere else, since there were no randomized mmap_base() or arch_align_stack() functions.

My arch_align_stack(), now in fs/exec.c, should be portable to all platforms now. Assuming my code works as intended, it's safe to enable this on non-randomized archs; STACK_ALIGN will be PAGE_SIZE and so arch_align_stack() effectively becomes an expensive NOP. This also happens if ARCH_RANDOM_STACK_BITS is 0.

This code probably makes it possible to collapse mmap_base() in arch/x86_64/ia32/mmap32.c into arch_pick_mmap_layout() in arch/x86_64/mm/mmap.c; as far as I can tell, there are 2 functions because one applies 28 bits of entropy and one applies 8. This patch defines ARCH_RANDOM_MMAP_BITS as being based on the task type (32 or 64 bit), so the same function can complete the same randomization (I think...).

As before, this code makes it possible to insert hooks at a few key points to control mmap() and stack entropy per-execution. This could later be added as SELinux policy controls if anyone is interested in doing so.

This patch was coded very at-face and defines too many variables that are used once in a couple functions. I can probably rewrite those sections to do the calculation steps in the same variable, and just note what it's doing in comments.

This has yet to be compile-tested.

Questions? Comments? Flames?

Signature · 11 lines
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
Documentation/aslr.txt +119 -0
diff -urNp linux-2.6.16.16/Documentation/aslr.txt linux-2.6.16.16-randparam/Documentation/aslr.txt
@@ -0,0 +1,119 @@
+Address space layout randomization is randomly selecting the base
+offsets of segments of memory in VMA.  It is used as a security tool
+to prevent sensitive attacks from being carried out by making important
+parameters to those attacks volatile and non-discoverable.
+
+Linux currently employs address space randomization in two places:
+
+1.  mmap() base
+ The base offset of libraries and anonymous mappings.  Randomization is
+ currently taken to the following degrees by default:
+
+  32-bit:  i386
+   Over 1MiB of VMA, giving 8 bits of entropy for 4096 byte pages.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy for 4096 byte pages.
+
+ The maximum is over an area the size of TASK_SIZE / 12
+2.  stack base
+ The base offset of the stack.  Randomization is currently taken to the
+ following degrees by default:
+
+  32-bit:  i386
+   Over 8MiB of VMA, giving 19 bits of entropy, aligned to 16 bytes.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy, aligned to 16 bytes.
+
+ The maximum allowed is over an area the size of TASK_SIZE / 12
+
+Linux does not employ heap randomization.
+
+Randomization is applied in the following places.
+
+
+STACK RANDOMIZATION
+
+fs/exec.c
+unsigned long arch_align_stack(unsigned long sp)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to sub-page granularity.  It applies a portion of the
+ stack entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - page_random_bits = total bits of entropy
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Raise 2^page_random_bits to get random_places
+  - Divide PAGE_SIZE by random_places to get random_interval
+  - (get_random_int() % random_places) * random_interval = offset
+  - Subtract offset from the stack pointer
+
+
+fs/binfmt_elf.c
+static unsigned long randomize_stack_top(unsigned long stack_top)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to page granularity.  It applies a portion of the stack
+ entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - vma_random_bits = 0
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - vma_random_bits =
+               total bits entropy - MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Multiply PAGE_SIZE by 2^random_bits to get random_range
+  - random_variable = get_random_int() % random_range
+  - Offset stack in VMA by random_variable and PAGE_ALIGN() result
+
+
+MMAP RANDOMIZATION
+
+arch/i386/mm/mmap.c
+static inline unsigned long mmap_base(struct mm_struct *mm)
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+ This function is for i386 architectures.
+
+
+arch/x86_64/mm/mmap.c
+void arch_pick_mmap_layout(struct mm_struct *mm)
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+ For IA-32 emulation it will call an IA-32 function.
+
+ This function is for x86-64 architectures.
+
+
+arch/x86_64/ia32/mmap32.c
+static inline unsigned long mmap_base(struct mm_struct *mm)
+
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+ This function is for i386 architecture processes on x86-64.
+
+Also note the following:
+
+ - STACK_ALIGN is defined in include/arch-*/processor.h
+ - include/linux/mm.h defines STACK_ALIGN as PAGE_SIZE if it is not
+   defined
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined in
+   include/arch-*/processor.h
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined as
+   0 in include/linux/mm.h if not otherwise defined
+
arch/i386/kernel/process.c +0 -6
diff -urNp linux-2.6.16.16/arch/i386/kernel/process.c linux-2.6.16.16-randparam/arch/i386/kernel/process.c
@@ -905,9 +905,3 @@ asmlinkage int sys_get_thread_area(struc
 	return 0;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
arch/i386/mm/mmap.c +23 -2
diff -urNp linux-2.6.16.16/arch/i386/mm/mmap.c linux-2.6.16.16-randparam/arch/i386/mm/mmap.c
@@ -40,9 +40,30 @@ static inline unsigned long mmap_base(st
 {
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_bits = ARCH_RANDOM_MMAP_BITS;
+
+	/*XXX:  Place a hook here to adjust mmap() randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 bits of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_MMAP_BITS;
+	if (max_random_bits < random_bits)
+		random_bits = max_random_bits;
+
+	/*
+	 * PAGE_SIZE is 4096 usually.  mmap_random_bits means random bits
+	 * of entropy, not how long the range is.  If pages are suddenly
+	 * bigger some day, we're still randomizing this much....
+	 */
+	if (current->flags & PF_RANDOMIZE && (mmap_random_bits > 0))
+		random_factor = get_random_int() % (PAGE_SIZE << random_bits);
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
arch/um/kernel/process_kern.c +0 -15
diff -urNp linux-2.6.16.16/arch/um/kernel/process_kern.c linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c
@@ -454,18 +454,3 @@ int singlestepping(void * t)
 	return 2;
 }
 
-/*
- * Only x86 and x86_64 have an arch_align_stack().
- * All other arches have "#define arch_align_stack(x) (x)"
- * in their asm/system.h
- * As this is included in UML from asm-um/system-generic.h,
- * we can use it to behave as the subarch does.
- */
-#ifndef arch_align_stack
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
-#endif
arch/x86_64/ia32/mmap32.c +23 -2
diff -urNp linux-2.6.16.16/arch/x86_64/ia32/mmap32.c linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c
@@ -42,9 +42,30 @@ static inline unsigned long mmap_base(st
 {
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_bits = ARCH_RANDOM_MMAP_BITS;
+
+	/*XXX:  Place a hook here to adjust mmap() randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_MMAP_BITS;
+	if (max_random_bits < random_bits)
+		random_bits = max_random_bits;
+
+	/*
+	 * PAGE_SIZE is 4096 usually.  mmap_random_bits means random bits
+	 * of entropy, not how long the range is.  If pages are suddenly
+	 * bigger some day, we're still randomizing this much....
+	 */
+	if (current->flags & PF_RANDOMIZE && (mmap_random_bits > 0))
+		random_factor = get_random_int() % (PAGE_SIZE << random_bits);
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
arch/x86_64/kernel/process.c +0 -6
diff -urNp linux-2.6.16.16/arch/x86_64/kernel/process.c linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c
@@ -839,9 +839,3 @@ int dump_task_regs(struct task_struct *t
 	return 1;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
arch/x86_64/mm/mmap.c +29 -2
diff -urNp linux-2.6.16.16/arch/x86_64/mm/mmap.c linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c
@@ -11,17 +11,44 @@
 
 void arch_pick_mmap_layout(struct mm_struct *mm)
 {
+	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
+
 #ifdef CONFIG_IA32_EMULATION
 	if (current_thread_info()->flags & _TIF_IA32)
 		return ia32_pick_mmap_layout(mm);
 #endif
+
 	mm->mmap_base = TASK_UNMAPPED_BASE;
+	
+	/*XXX:  I *think* this is right, but really I have no fucking
+	 * clue what I'm doing when we get around to 'rnd ='
+	 */
 	if (current->flags & PF_RANDOMIZE) {
-		/* Add 28bit randomness which is about 40bits of address space
+		unsigned rnd;
+		random_bits = ARCH_RANDOM_MMAP_BITS;
+
+		/*XXX:  Place a hook here to adjust mmap()
+		 * randomization; this hook will change the value of
+		 *  random_bits */
+
+		/*
+		 * At most we should shift by 1/12 TASK_SIZE.  This
+		 * is 256M on 3GiB i386; 85M (64M, 14 bits) on 1GiB
+		 * i386; 8TiB (31 bits) on x86-64 with 47 bits of user
+		 *  VMA...
+		 */
+		max_random_bits = MAX_RANDOM_MMAP_BITS;
+		if (max_random_bits < random_bits)
+			random_bits = max_random_bits;
+
+		/* Add our randomness.
+		   28 bits of randomness is about 40bits of address space
 		   because mmap base has to be page aligned.
  		   or ~1/128 of the total user VM
 	   	   (total user address space is 47bits) */
-		unsigned rnd = get_random_int() & 0xfffffff;
+		rnd = get_random_int() % (1 << random_bits);
 		mm->mmap_base += ((unsigned long)rnd) << PAGE_SHIFT;
 	}
 	mm->get_unmapped_area = arch_get_unmapped_area;
fs/binfmt_elf.c +42 -2

51 lines not on this page · raw message

fs/exec.c +63 -0

72 lines not on this page · raw message

include/asm-i386/processor.h +7 -0
diff -urNp linux-2.6.16.16/include/asm-i386/processor.h linux-2.6.16.16-randparam/include/asm-i386/processor.h
@@ -320,6 +320,13 @@ extern int bootloader_type;
  */
 #define TASK_SIZE	(PAGE_OFFSET)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS	19
+#define ARCH_RANDOM_MMAP_BITS	8
+
 /* This decides where the kernel will search for a free chunk of vm
  * space during mmap's.
  */
include/asm-x86_64/processor.h +17 -0
diff -urNp linux-2.6.16.16/include/asm-x86_64/processor.h linux-2.6.16.16-randparam/include/asm-x86_64/processor.h
@@ -172,6 +172,23 @@ static inline void clear_in_cr4 (unsigne
 #define TASK_SIZE 		(test_thread_flag(TIF_IA32) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 #define TASK_SIZE_OF(child) 	((test_tsk_thread_flag(child, TIF_IA32)) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap() in IA-32*/
+#define IA32_ARCH_RANDOM_STACK_BITS	19
+#define IA32_ARCH_RANDOM_MMAP_BITS	8
+
+/* Random bits of stack and mmap() in 64-bit mode.
+ * 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
+ * of the address space. */
+#define ARCH_RANDOM_STACK_BITS64	28
+#define ARCH_RANDOM_MMAP_BITS64		28
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS  (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
+#define ARCH_RANDOM_MMAP_BITS   (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)
+
 #define TASK_UNMAPPED_BASE	PAGE_ALIGN(TASK_SIZE/3)
 
 /*
include/linux/mm.h +32 -0
diff -urNp linux-2.6.16.16/include/linux/mm.h linux-2.6.16.16-randparam/include/linux/mm.h
@@ -23,6 +23,38 @@ struct anon_vma;
 extern unsigned long max_mapnr;
 #endif
 
+/* Any arch not defining this is assumed to not know of
+ * sub-page stack alignment.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef STACK_ALIGN
+# define STACK_ALIGN	PAGE_SIZE
+#endif
+
+/* If these are not defined, disable randomization.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef ARCH_RANDOM_STACK_BITS
+# define ARCH_RANDOM_STACK_BITS	0
+#endif
+#ifndef ARCH_RANDOM_MMAP_BITS
+# define ARCH_RANDOM_MMAP_BITS	0
+#endif
+
+/*
+ * These are the biggest entropies we can have.
+ * Our original MAX_RANDOM_STACK_BITS was as below:
+ * 	long_log2((PAGE_SIZE / STACK_ALIGN) * (TASK_SIZE / 12) / PAGE_SIZE)
+ * This simplifies algebraicly to the below:
+ *   long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+ */
+#define MAX_RANDOM_STACK_BITS \
+	long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+#define MAX_RANDOM_STACK_BITS_PER_PAGE \
+	long_log2(PAGE_SIZE / STACK_ALIGN)
+#define MAX_RANDOM_MMAP_BITS \
+	long_log2((TASK_SIZE / 12) / PAGE_SIZE)
+
 extern unsigned long num_physpages;
 extern void * high_memory;
 extern unsigned long vmalloc_earlyreserve;
#1 lore raw
Quoted 8 lines · John Richard Moser

Pavel Machek recommended per-architecture randomization defaults when I poked a (very hackish) patch up here. As follow-up, I have taken out the command line parameter code and used the infrastructure I wrote to implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in include/asm-ARCH/processor.h or equivalent. These defines are as follows:

Quoted 9 lines

STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
If not defined, stack randomization is carried out to page granularity
ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
If not defined, stack randomization is disabled by defining this as 0.
ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
If not defined, mmap() randomization is disabled by defining this as 0.

eh....

I think you missed a few things..
like
1) This is per architecture already for the most part! arch_align_stack() is obvious per architecture already the mmap randomisation also happens in arch/<foo>/mm and this is per arch by definition as well
2) you missed that the mmap randomization is *ON TOP OF* the stack randomization. So while you say "1Mb" in your doc in practice it is 8Mb

Also your patch is still full of XXX's and "other noise"... Also you probably should explain what the advantage is over the existing per architecture approach. Just stating "it's per architecture" (as you suggest) doesn't cut it since it is per architecture already for the most part.

If all you want to do is turn
- if (current->flags & PF_RANDOMIZE)
- random_variable = get_random_int() % (8*1024*1024);

that 8 into a per architecture thing.. then your patch is awefully big and complex to just achieve that.

#2 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 20 lines · Arjan van de Ven
Quoted 8 lines · John Richard Moser

Pavel Machek recommended per-architecture randomization defaults when I poked a (very hackish) patch up here. As follow-up, I have taken out the command line parameter code and used the infrastructure I wrote to implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in include/asm-ARCH/processor.h or equivalent. These defines are as follows:

Quoted 9 lines

STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
If not defined, stack randomization is carried out to page granularity
ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
If not defined, stack randomization is disabled by defining this as 0.
ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
If not defined, mmap() randomization is disabled by defining this as 0.

Quoted 6 lines

eh....

I think you missed a few things..
like
1) This is per architecture already for the most part! arch_align_stack() is obvious per architecture already

Yes you write a new one for each individual architecture, to tweak a few variables in it. Not that having the same function with the same blob of code with 1 or 2 numbers in it changed matters, since only 1 is generated to code...

Quoted 2 lines

the mmap randomisation also happens in arch/<foo>/mm and this is per arch by definition as well

Yeah, same thing,

Quoted 3 lines

2) you missed that the mmap randomization is *ON TOP OF* the stack randomization. So while you say "1Mb" in your doc in practice it is 8Mb

This is fuzzy. mmap() randomization is only 1MiB in most cases. It's only 9MiB if you don't already need the stack address to perform an attack.

The classical ret2libc attack requires a stack frame to carry out. Your two choices for this are injecting the stack frame into the heap (which is fixed position on Linux), or injecting it into the stack. You may not always have a way to get it into a known position on the heap, so cracking the stack may be the only choice.

Once your problem involves figuring out where the stack is, then the added complexity of figuring out the location of mmap() is only 1MiB. I would dare say the stack's per-page alignment is all that counts*, and this gives 2048 states; the mmap() randomization gives 256 states itself, totaling 524,288 states to crack. If mmap() was by its own 8MiB, this would be 2048 states for mmap() per stack state, giving 4,194,304 states total.

*If you can load 1 page of attack data, you can probably get it down to 2048, assuming a system() stack frame is less than 16 bytes. Note that we can discard the Return Pointer and SFP from the stack frames; they can be filled with garbage. We may be able to discard the local variables as well, since whatever data is there is overwritten anyway. This leaves us aligning the "passed arguments" part to 16 byte boundaries. This leaves 8 bytes "/bin/sh" and 4 bytes pointer to where we hope it lands, 12 bytes. Pad with 4 more bytes and set SFP to the bottom of where you think it'll land, and (if you guessed VMA alignment correct) any sub-page randomization value leads to a successful attack.

Of course without PIE, you can in theory return to an address where there's a 'call system' in the main executable and if stack pointer is pointed in the right direction, it'll complete the call. This of course assumes that the code is 'get_system_from_got; call system;' and not 'get_system_from_got; build_stack_frame; call system;'. If I remember right, actually calling a function from PIC involves jumping into the PLT at the proper offset into a strip of code that does the actual call, rather than retrieving an address out of the GOT based on an offset. That should make this attack feasible.

At any rate, with the PIE attack you still have to crack the stack before you can go anywhere. mmap() randomization is 1MiB, stack randomization is 8MiB, both have to be cracked along the way.

If you load your stack frame into the heap and try to use RETP to hit the function directly, you're going to need to break the stack; as you said, this is 11.17 bits of randomization anyway (2304 possible positions).

If you load your stack frame into the heap and use the main executable attack, you have a known RETP and SFP value to use and randomization is pointless.

Quoted 2 lines

Also your patch is still full of XXX's and "other noise"...

Yeah, that's why I did [RFC] instead of [PATCH] this time. I jumped the gun last time.

My patch is also full of infrastructure like "hey if we have entropy > what we think is sane cut it off." We don't need that for per-arch randomization because we can assume the #define is sane, it's coming from the kernel devs. We need it for i.e. SELinux policy or command line or /proc, but none of that is in this patch.

Quoted 4 lines

Also you probably should explain what the advantage is over the existing per architecture approach. Just stating "it's per architecture" (as you suggest) doesn't cut it since it is per architecture already for the most part.

1. I can get away with exactly 1 mmap() randomization function, instead of 1 function per architecture.
- Less code to maintain
- The entropy levels are #defined per arch instead of hard-coded into functions (more readable in the future)
2. I can get away with exactly 1 arch_align_stack() function, instead of 1 per architecture.
- Less code to maintain
- STACK_ALIGN can be used to figure out sub-page alignment per architecture (more readable in the future)
3. Entropy levels are rather easy to adjust and tweak per-architecture or per-compile or per-execve(). This just leaves adding code to do it, i.e. SELinux hooks.

Quoted 7 lines

If all you want to do is turn

fs/binfmt_elf.c +0 -2
-       if (current->flags & PF_RANDOMIZE)
-               random_variable = get_random_int() % (8*1024*1024);

that 8 into a per architecture thing.. then your patch is awefully big and complex to just achieve that.

Yes, you're right. I will work on making it smaller, it's around 300 lines of code from around 10-15 lines of code.

Part of the bulk stems from the fact that I didn't do randomization based on range, but based on bits of entropy. I became more comfortable with looking at entropy based on entropy instead of period*entropy mostly from reading through the PaX documents**. It doesn't really matter, the code will be a lot less complex if I write it per range; we can always put /*28 bits of entropy on x86-64*/ in processor.h or whatnot.

**But notice the difference between 8MiB and 9MiB randomization is 0.17 bits of entropy; and the difference between 16MiB and 17MiB of entropy is 0.09 bits. The amount of added time between (entropy1) and (entropy2) is 2^(entropy2 - entropy1) times the time it takes to break (entropy1), with entropies in bits. Raw ranges quickly become mostly meaningless, except for use as big numbers to impress people who don't really understand what they're dealing with.

Also like I said, a lot of my calculations are somewhat ugly. I define 4 variables named to show what I'm calculating and then calculate them together to get what I'm after; the kernel isn't elementary mathematics in C, it doesn't need to lead the reader through steps.

I'll work on it a bit. May post a new one today or tomorrow.

Quoted 7 lines

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

- --
All content of all messages exchanged herein are left in the Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be wasted on re-inventing the wheel when there are so many fascinating new problems waiting out there.
-- Eric Steven Raymond

We will enslave their women, eat their children and rape their cattle!
-- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMHAQs1xW0HCTEFAQIBaA//WUjVz2WogaBrn0FNxDOyh59r/Bqp12E9 hqXIbnYwK4ZFWWI15Q2nFwKug9OzWrYDhPWRSa9j/mxuU9Qnfebxna3zNN43l+2F f+VTPG6kMU9AzcMB7+LLGGMCJMk6djoJQUHH9zIK/zUdKz8xXW+tUBtsc0XYfYgq iQ3+nBOpllxU0ORL8FMVjE1QooMTNSJKbd7u0QVms21aR7T0heNuKYGEC3AvpFv1 NAESyoaOBtEAj/q+xOSn4McMsiiKlKTQn0fQ6SeDnL0+TgJ4ACHKBsVpZeU3ic+T HAwMEjpfgI6I8QuS+9diSiccJQWuiC4V8JzV1EgAMu1j3F4O6Sf8VhlOuFzdgQaj 1Ypq9HBWfDERPf3wrb/S7tnR6oDqDY3N8upH5kfYDt2veDADYtXw2MFaCkwVo2eD Yx21MXlKm/+z3ddmMu9yRArxS4XSlwEelxUrx5HXwcMypImg46lTiiZ0QOCPMHzd JmFPa0QhsSLtHGvpJHuU92FO4Y0rSMy6qHAv9flWuyOsnqMo9rWSSrjg90mZa5Ka BYOzvfz3EZXElx/Esu1zz9+vH0mMkOESDG6O075pMzYbc0qh/KIFCSzFWlbjJdYj S3K2c654GP2A94ibNamjS3FVRUZkwyGP65SHq2vTS9SuMztFwyRA29qQwEiV4Rwn 1OiSkiEw/d4=
=9myZ
-----END PGP SIGNATURE-----

#3 lore raw
Quoted 33 lines · John Richard Moser

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 20 lines · Arjan van de Ven
Quoted 8 lines · John Richard Moser

Pavel Machek recommended per-architecture randomization defaults when I poked a (very hackish) patch up here. As follow-up, I have taken out the command line parameter code and used the infrastructure I wrote to implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in include/asm-ARCH/processor.h or equivalent. These defines are as follows:

Quoted 9 lines

STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
If not defined, stack randomization is carried out to page granularity
ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
If not defined, stack randomization is disabled by defining this as 0.
ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
If not defined, mmap() randomization is disabled by defining this as 0.

Quoted 6 lines

eh....

I think you missed a few things..
like
1) This is per architecture already for the most part! arch_align_stack() is obvious per architecture already

Quoted 4 lines

Yes you write a new one for each individual architecture, to tweak a few variables in it. Not that having the same function with the same blob of code with 1 or 2 numbers in it changed matters, since only 1 is generated to code...

well stack alignment IS a per architecture property, and on some architectures it'll be more complex than a single one-liner (think about a 32 bit userspace needing different alignment than 64 bit as a simple example of this).

It's a 2 or 3 line function for the simple cases like x86 so... why bother making it really complex.

Quoted 7 lines
Quoted 4 lines

Also you probably should explain what the advantage is over the existing per architecture approach. Just stating "it's per architecture" (as you suggest) doesn't cut it since it is per architecture already for the most part.

1. I can get away with exactly 1 mmap() randomization function, instead of 1 function per architecture.

which needs to be there for other reasons anyway; VA space layout is a per architecture thing no matter what (just look at ia64 or ppc on how complex things can get), randomization within each region is, as a result of that, also a per architecture thing; with different rules for different part of the VA space sometimes (ia64/ppc64) or on the type of userspace that happens to be running (on all architectures that also have a compat arch)

Quoted 1 line

- Less code to maintain

we're talking less than a handful lines of code again, most of which is NOT shareable.

Quoted 2 lines

- The entropy levels are #defined per arch instead of hard-coded into functions (more readable in the future)

that's a separate thing; if you want to use a define rather than an open coded value, fair enough, but make that a separate patch really; especially since that is basically a "one line to a header + one line code delta" which is then trivial to review for identity.

Quoted 2 lines

2. I can get away with exactly 1 arch_align_stack() function, instead of 1 per architecture.

I don't think that that is fundamentally possible, see above.

Quoted 2 lines

3. Entropy levels are rather easy to adjust and tweak per-architecture or per-compile or per-execve().

this I don't get; you change a per arch thing to.. a per arch thing.

Quoted 2 lines

Part of the bulk stems from the fact that I didn't do randomization based on range, but based on bits of entropy.

I don't understand why you want to do that. It will make code a lot more complex, and at the same time it limits you to powers-of-two in practice.

Quoted 3 lines

I became more comfortable
with looking at entropy based on entropy instead of period*entropy mostly from reading through the PaX documents**.

Using bits-of-entropy in documentation is fine, you can do fractions there as well for example. No objection from me on that, but it shouldn't have to complicate or limit the code. For code, "range" is a native principle much more than "bits of".

#4 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 37 lines · Arjan van de Ven
Quoted 27 lines · John Richard Moser

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 21 lines · Arjan van de Ven
Quoted 8 lines · John Richard Moser

Pavel Machek recommended per-architecture randomization defaults when I poked a (very hackish) patch up here. As follow-up, I have taken out the command line parameter code and used the infrastructure I wrote to implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in include/asm-ARCH/processor.h or equivalent. These defines are as follows:

Quoted 9 lines

STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
If not defined, stack randomization is carried out to page granularity
ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
If not defined, stack randomization is disabled by defining this as 0.
ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
If not defined, mmap() randomization is disabled by defining this as 0.

eh....

Quoted 8 lines
Quoted 4 lines

I think you missed a few things..
like
1) This is per architecture already for the most part! arch_align_stack() is obvious per architecture already

Yes you write a new one for each individual architecture, to tweak a few variables in it. Not that having the same function with the same blob of code with 1 or 2 numbers in it changed matters, since only 1 is generated to code...

Quoted 4 lines

well stack alignment IS a per architecture property, and on some architectures it'll be more complex than a single one-liner (think about a 32 bit userspace needing different alignment than 64 bit as a simple example of this).

I did this already in the patch I sent with bits of entropy. It's also done with TASK_SIZE. The alignment uses STACK_ALIGN and does the calculations on the fly in the code.

Stack and mmap() VMA alignment is based on PAGE_SIZE.

Quoted 4 lines

It's a 2 or 3 line function for the simple cases like x86 so... why bother making it really complex.

Yeah, my mmap() base randomization calculation now is 5 lines (not including variable declarations, comments, or return), mmap_base() from arch/i386/mm/mmap.c is 5 lines (not including etc etc), arch_align_stack() is 5 lines (not including etc etc).

I guess slowing down process start-up by a few tens of nanoseconds is a bit complex though.

Quoted 8 lines
Quoted 7 lines
Quoted 5 lines

Also you probably should explain what the advantage is over the existing per architecture approach. Just stating "it's per architecture" (as you suggest) doesn't cut it since it is per architecture already for the most part.

1. I can get away with exactly 1 mmap() randomization function, instead of 1 function per architecture.

Quoted 7 lines

which needs to be there for other reasons anyway; VA space layout is a per architecture thing no matter what (just look at ia64 or ppc on how complex things can get), randomization within each region is, as a result of that, also a per architecture thing; with different rules for different part of the VA space sometimes (ia64/ppc64) or on the type of userspace that happens to be running (on all architectures that also have a compat arch)

I handled the different types of userspace already. The solution is the same solution x86-64 uses for TASK_SIZE.

Explain "randomization within each region." I thought mmap() randomization just shifted the mmap() base around at process start?

Quoted 6 lines
Quoted 2 lines

- Less code to maintain

we're talking less than a handful lines of code again, most of which is NOT shareable.

The relevant parts are sharable. I just moved this stuff out into fs/exec.c:

/* Produce a random shift for mmap() base
* The output of this function should always be page aligned*/

unsigned long mmap_base_random_factor() {
        unsigned long random_factor = 0;
        unsigned long random_bits = ARCH_RANDOM_MMAP_BITS;

        /*XXX:  Place a hook here to adjust mmap() randomization;
         * this hook will change the value of random_bits */

        if (random_bits > MAX_RANDOM_MMAP_BITS)
                random_bits = MAX_RANDOM_MMAP_BITS;

        /* randomize in range 2^random_bits * PAGE_SIZE */
        if (current->flags & PF_RANDOMIZE)
                random_factor = get_random_int() % (1 << random_bits);
        random_factor *= PAGE_SIZE;

        return PAGE_ALIGN(random_factor);
}

I'm pretty sure that last PAGE_ALIGN() is unnecessary. The guts between variable declaration and return are 5 lines of code. Also, the MAX_RANDOM_MMAP_BITS checks here can probably be removed until someone decides to implement some sort of tunable, such as a LSM hook. Even then we should probably let the tunable do that check... well, that's a design decision that could go either way.

Here's from arch/i386/mm/mmap.c:

static inline unsigned long mmap_base(struct mm_struct *mm)

{
        unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
        unsigned long random_factor = 0;

        random_factor = mmap_base_random_factor();

        if (gap < MIN_GAP)
                gap = MIN_GAP;
        else if (gap > MAX_GAP)
                gap = MAX_GAP;

        return PAGE_ALIGN(TASK_SIZE - gap - random_factor);
}

And from arch/x86_64/mm/mmap.c:

void arch_pick_mmap_layout(struct mm_struct *mm)
{

#ifdef CONFIG_IA32_EMULATION
        if (current_thread_info()->flags & _TIF_IA32)
                return ia32_pick_mmap_layout(mm);

#endif

        mm->mmap_base = TASK_UNMAPPED_BASE;

        if (current->flags & PF_RANDOMIZE) {
                unsigned long random_factor = 0;
                /* Add our randomness. */
                random_factor = mmap_base_random_factor();
                mm->mmap_base += random_factor;
        }
        mm->get_unmapped_area = arch_get_unmapped_area;
        mm->unmap_area = arch_unmap_area;
}

and from include/asm-x86_64/processor.h:

/*Random bits of stack and mmap() in IA-32*/
#define IA32_ARCH_RANDOM_STACK_BITS 19
#define IA32_ARCH_RANDOM_MMAP_BITS 8

/* Random bits of stack and mmap() in 64-bit mode.
* 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
* of the address space. */
#define ARCH_RANDOM_STACK_BITS64 28
#define ARCH_RANDOM_MMAP_BITS64 28

/*Random bits of stack and mmap()*/
#define ARCH_RANDOM_STACK_BITS (test_thread_flag(TIF_IA32) ? \
IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
#define ARCH_RANDOM_MMAP_BITS (test_thread_flag(TIF_IA32) ? \
IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)

Yes, this is the same solution as with TASK_SIZE (which is about 3 lines above this...)

Quoted 8 lines
Quoted 2 lines

- The entropy levels are #defined per arch instead of hard-coded into functions (more readable in the future)

that's a separate thing; if you want to use a define rather than an open coded value, fair enough, but make that a separate patch really; especially since that is basically a "one line to a header + one line code delta" which is then trivial to review for identity.

Easy enough to do for mmap(); for the stack there's ... complexity.

Quoted 4 lines
Quoted 2 lines

2. I can get away with exactly 1 arch_align_stack() function, instead of 1 per architecture.

I don't think that that is fundamentally possible, see above.

Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of entropy, and for stacks that grow up and down. The only situations that I haven't handled are stacks that grow up and down at the same time, and stacks that teleport data to other dimensional planes.

Quoted 6 lines
Quoted 3 lines

3. Entropy levels are rather easy to adjust and tweak per-architecture or per-compile or per-execve().

this I don't get; you change a per arch thing to.. a per arch thing.

I'm thinking ahead to the possibility of tweaking entropy via SELinux policy. Some of us out here would rather apply MASSIVE_LEVEL_OF_ENTROPY to Gaim and Firefox and Apache and TINY_ENTROPY_LEVEL_THAT_WONT_BREAK_ORACLE to Oracle.

The level of stack entropy was definitely not per-architecture; the level of mmap()... well, you had code for it in 3 places (i386, x86_64, x86_64 IA-32 emul) that I found.

Quoted 8 lines
Quoted 3 lines

Part of the bulk stems from the fact that I didn't do randomization based on range, but based on bits of entropy.

I don't understand why you want to do that. It will make code a lot more complex, and at the same time it limits you to powers-of-two in practice.

In practice if you can assume an attacker can reasonably break 17 bits of entropy, then you can assume that he can possibly (but unlikely) double his attack efficiency and break 18 bits. You would want to step it up to 20 bits or so to get a few steps beyond "unlikely" into "we are pretty confident this is impossible."

A fraction of a bit helps as much as a fraction of a slice of bread helps complete a sandwich.

That being said, let me shrink this code down a bit first and then I'll worry about switching to ranges. In any case it's not really any more restrictive than what the kernel currently has-- everything is aligned to powers-of-two already AND HARD CODED.

Quoted 8 lines
Quoted 3 lines

I became more comfortable
with looking at entropy based on entropy instead of period*entropy mostly from reading through the PaX documents**.

Using bits-of-entropy in documentation is fine, you can do fractions there as well for example. No objection from me on that, but it shouldn't have to complicate or limit the code. For code, "range" is a native principle much more than "bits of".

Right now I'm not so sure how to deal with less-than-a-page stack randomization ranges ;) (Handling all possible situations)

Sure VMA is easy to randomize over range and PAGE_ALIGN; but what the hell do I do about sub-page randomization if PAGE_SIZE > RANDOM_RANGE > 0? Complain that someone broke me?

My current thinking on this follows two schools of thought:

1. Something is obviously broken. Ignore it and don't randomize.

2. Randomize to RANDOM_RANGE, divide by STACK_ALIGN, multiply by STACK_ALIGN. With integers this will align the result to STACK_ALIGN.

Quoted 8 lines

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

- --
All content of all messages exchanged herein are left in the Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be wasted on re-inventing the wheel when there are so many fascinating new problems waiting out there.
-- Eric Steven Raymond

We will enslave their women, eat their children and rape their cattle!
-- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMn6gs1xW0HCTEFAQK1+g//S87sCgbqxSdXD/HL2FCiLIDMIH708efb y0xz0DKxnvuWhi5VlnJVcxDwSe+7lhVXp7khE9tRLGq46tQ2sHh+p8ZmwxhfdmQd Bj7NQbk6zU+LXF1R7CqfI0N/FwS5R4te5KnZDe6oZbgvww/vL6bgj7oej+kYQXp1 fdQ4LEhMnqX4fD7C1XNw3cBm6cGtp2TugsiAvJl/yamllRNnJKuMS3Ut1ffA3Cqq r7SfXmgGKaPIYKbk31b1KgC7kPWomP5D0K6mJPDth005TXiC4MbRGldTCCu6SQ6P wATDlAPxl1XHxZ+vBqaRTm4bOrKi9zeSlKPnfe/ik/VvBVFiDfHaDJjJZURYvyE5 7/XAZqHoxcXly1wcqee17EXwcx8AnQTEr+wBCORF1cRnOIDsulT4bcBxYtD745z7 DtjCiZhNqCniHBUjUSijmiAHhp4aDyf3pzrmSZOPcTdSrknoFP3TXWksDXyA+qHr S1Gl+OdbMcbrQv1o6bsi9LXXHLhoFgbfgaJKRutxGUV6V9nu3Iu/tzvVzAEqi1pv phAD/Av1oqKB4AQ5aMFXdCzXQ309JGd3OgM7UxPabWJ0iVgn0i11PaZKY43ekTi6 faXQCPhTwD0CA72AcT7WkN4h1i5qbmEbLb0mjYFc0JliZkr4ogubeTaxggiifSwo TO1w5wlWyGk=
=tezi
-----END PGP SIGNATURE-----

#5 lore raw
Quoted 1 line · John Richard Moser

Stack and mmap() VMA alignment is based on PAGE_SIZE.

which breaks ppc64 for hugetlbs at least.

Quoted 2 lines

Explain "randomization within each region." I thought mmap() randomization just shifted the mmap() base around at process start?

ia64 and iirc also ppc64 have different regions in the VA space for different types of mmaps. Hugetlb, executable, non-cachable etc etc.

Quoted 10 lines
Quoted 7 lines
Quoted 3 lines

- Less code to maintain

we're talking less than a handful lines of code again, most of which is NOT shareable.

The relevant parts are sharable. I just moved this stuff out into fs/exec.c:

... and made it a lot more complex.

Quoted 2 lines

Yes, this is the same solution as with TASK_SIZE (which is about 3 lines above this...)

the rules for mmap_base vary per architecture, and even per binary time. In fact the meaning of it is very much free for the architecture to determine/use.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

2. I can get away with exactly 1 arch_align_stack() function, instead of 1 per architecture.

I don't think that that is fundamentally possible, see above.

Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of entropy, and for stacks that grow up and down. The only situations that I haven't handled are stacks that grow up and down at the same time,

ok so you haven't dealt with ia64 yet ;)

Quoted 2 lines

and
stacks that teleport data to other dimensional planes.

and with stacks that need different alignment based on binary type (mips has 4 or so of those) or .. or ..

Quoted 1 line

The level of stack entropy was definitely not per-architecture;

no but it COULD be. I haven't looked at the ia64 randomization, but I'd not be surprised if it was different

Quoted 8 lines
Quoted 7 lines
Quoted 2 lines

Part of the bulk stems from the fact that I didn't do randomization based on range, but based on bits of entropy.

I don't understand why you want to do that. It will make code a lot more complex, and at the same time it limits you to powers-of-two in practice.

Quoted 5 lines

In practice if you can assume an attacker can reasonably break 17 bits of entropy, then you can assume that he can possibly (but unlikely) double his attack efficiency and break 18 bits. You would want to step it up to 20 bits or so to get a few steps beyond "unlikely" into "we are pretty confident this is impossible."

I think you totally missed the point. *I DON'T CARE ABOUT "BITS OF ENTROPY" IN THE CODE*. The code cares about how much it is in actual bytes. Sure when talking about it in documents or analysis it may make sense to do the bits math. BUT NOT IN THE CODE.

That was my point, and all there was to it. You add complexity and limitations TO THE CODE for no good reason at all.

#6 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 4 lines · Arjan van de Ven
Quoted 1 line · John Richard Moser

Stack and mmap() VMA alignment is based on PAGE_SIZE.

Quoted 8 lines

which breaks ppc64 for hugetlbs at least.

Quoted 2 lines

Explain "randomization within each region." I thought mmap() randomization just shifted the mmap() base around at process start?

ia64 and iirc also ppc64 have different regions in the VA space for different types of mmaps. Hugetlb, executable, non-cachable etc etc.

Whoa.

Looks like I need a little education on this subject before I can come up with a solution to this one.

Quoted 10 lines
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

- Less code to maintain

we're talking less than a handful lines of code again, most of which is NOT shareable.

The relevant parts are sharable. I just moved this stuff out into fs/exec.c:

... and made it a lot more complex.

My mm.h macros are a lot more complex, probably. Although it would help if you pointed out where "complexity" shows up; honestly for the most part it looks clean and neat to me, besides a few rough edges and excessive commenting.

Quoted 6 lines
Quoted 2 lines

Yes, this is the same solution as with TASK_SIZE (which is about 3 lines above this...)

the rules for mmap_base vary per architecture, and even per binary time. In fact the meaning of it is very much free for the architecture to determine/use.

So the base can't just be randomized once?

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines
Quoted 2 lines

2. I can get away with exactly 1 arch_align_stack() function, instead of 1 per architecture.

I don't think that that is fundamentally possible, see above.

Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of entropy, and for stacks that grow up and down. The only situations that I haven't handled are stacks that grow up and down at the same time,

ok so you haven't dealt with ia64 yet ;)

So far IA-64 sounds like "we designed this while on acid," but fair enough. Explain.

Quoted 5 lines
Quoted 2 lines

and
stacks that teleport data to other dimensional planes.

and with stacks that need different alignment based on binary type (mips has 4 or so of those) or .. or ..

Use the same solution as TASK_SIZE, although 4 binary types is going to become painful yes. You can do it with a #define but I'm getting the feeling that these parts may need per-architecture and per-binary-type functions to sort it out (in the same way that there was an mmap_base() for IA-32 and x86-64 in x86-64).

Quoted 6 lines
Quoted 3 lines

The level of stack entropy was definitely not per-architecture;

no but it COULD be. I haven't looked at the ia64 randomization, but I'd not be surprised if it was different

VMA stack entropy was in fs/binfmt_elf.c and rather hard coded.

Quoted 14 lines
Quoted 8 lines
Quoted 8 lines
Quoted 4 lines

Part of the bulk stems from the fact that I didn't do randomization based on range, but based on bits of entropy.

I don't understand why you want to do that. It will make code a lot more complex, and at the same time it limits you to powers-of-two in practice.

Quoted 5 lines

In practice if you can assume an attacker can reasonably break 17 bits of entropy, then you can assume that he can possibly (but unlikely) double his attack efficiency and break 18 bits. You would want to step it up to 20 bits or so to get a few steps beyond "unlikely" into "we are pretty confident this is impossible."

Quoted 4 lines

I think you totally missed the point. *I DON'T CARE ABOUT "BITS OF ENTROPY" IN THE CODE*. The code cares about how much it is in actual bytes. Sure when talking about it in documents or analysis it may make sense to do the bits math. BUT NOT IN THE CODE.

I was only addressing the "it limits you to powers-of-two" part, not code complexity. The point was that strictly speaking it's not that great to be able to do it more fine-grained. This doesn't mean people wouldn't want to (hey I may want my stack and mmap() to move around by a gig on i386, it'll barely work and X will break half the time, but WHY would I want to?).

Quoted 4 lines

That was my point, and all there was to it. You add complexity and limitations TO THE CODE for no good reason at all.

I'll address those in the next pass. It will involve a little integer multiplication/division to provide proper sub-page alignment for the stack; VMA alignment can use PAGE_ALIGN().

Quoted 3 lines

- --
All content of all messages exchanged herein are left in the Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be wasted on re-inventing the wheel when there are so many fascinating new problems waiting out there.
-- Eric Steven Raymond

We will enslave their women, eat their children and rape their cattle!
-- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMwPws1xW0HCTEFAQK5aQ//W9m6h2DbSXP0yrNRKGgv7SCzZDbacsds eXubeG8l1OAnMmsDaAYgnX5g/aAb0md7xNi39CT5x4dgQiM+dyCX7TYIG/TaaN5+ lLLKt/xQZm73hUxk7s4pKiBN7OY8n5YwaEiP5JpfZZi/27KxV0DR8s1VDsRj8xGz 3uuEF6hsZXZZKIuG46pG6nwHphJNQkCZp6G8tZdQWC+LuclulB50PNxNMzUxe31S 13M7q81icGcbHnOvUvA7EHexa1Ru22VCl8NjTwogTwP/eIVcN/acE17EO/m/xfIz g9JXCgeF+soIk3SQTydR70CZwGENxs/mrYTXksWMDRsGmOK2qg5pSo7sr4V98g5P jF6x/044JAKWB/fmlEr5QxFCGFHuPSDSqeZHPiRWQnbn8nH2VB9aSRGK/mpx+rpJ /xIZrJLndFc06CdLe71inrjlBIhAQ58XuSd5pGGmLiKmwXiOGCDaWS5Qb0YChV2i hujNZ4AhuuPT9TiMhi842NR3Dd8NTy/mY1JlqUtao8ofnhQqf6GndDuwTrIn3TOL lm6X7EBuVbhXggsnjnQiaK10k90qU5Pgy9eqJYL8vybbuLu5uOwlxsuBM4ceIUya oyVxOYnySND2FpxhH55IfAnxTC2I1avd+V4vvuIc3hJEWUbugf6iUzX72/0rYo88 HL5S4HK8UbQ=
=zZEn
-----END PGP SIGNATURE-----

#7 lore raw
In reply to John Richard Moser

Alright, trying again. This patch is a bit smaller, easier to read, more streamline. randomize_stack_top() had code pulled out and put into a static inline just before it; and the mmap() randomization calculations are in fs/exec.c now. arch_align_stack() should also work on stack-grows-up architectures like HPPA, not that it'll be used there right now.

I am considering the following changes:

- Base randomization on ranges, as suggested by Arjan van de Ven. That
supersets current functionality, and we can implement entropy in bits abstractly anyway (i.e. range = PAGE_SIZE * powr(2,ENTROPY_IN_BITS)).

- Remove validation like 'if (random_bits > MAX_RANDOM_STACK_BITS)'.
These are not immediately useful; if SELinux hooks are added or such, they would be, but they could also be added into the SELinux code for those policy elements anyway.

- Remove /*XXX: Put SELinux hooks here*/ comments. This isn't hard to
figure out, anyone who wants to add SELinux hooks can figure this out then.

So before doing that, here's the current version. Again, this has not yet been compile tested, it's just scribbled out on paper.

Questions? Comments? Flames? Pictures of your girlfriends?

Signature · 11 lines
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
Documentation/aslr.txt +111 -0
diff -urNp linux-2.6.16.16/Documentation/aslr.txt linux-2.6.16.16-randparam/Documentation/aslr.txt
@@ -0,0 +1,111 @@
+Address space layout randomization is randomly selecting the base
+offsets of segments of memory in VMA.  It is used as a security tool
+to prevent sensitive attacks from being carried out by making important
+parameters to those attacks volatile and non-discoverable.
+
+Linux currently employs address space randomization in two places:
+
+1.  mmap() base
+ The base offset of libraries and anonymous mappings.  Randomization is
+ currently taken to the following degrees by default:
+
+  32-bit:  i386
+   Over 1MiB of VMA, giving 8 bits of entropy for 4096 byte pages.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy for 4096 byte pages.
+
+ The maximum is over an area the size of TASK_SIZE / 12
+2.  stack base
+ The base offset of the stack.  Randomization is currently taken to the
+ following degrees by default:
+
+  32-bit:  i386
+   Over 8MiB of VMA, giving 19 bits of entropy, aligned to 16 bytes.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy, aligned to 16 bytes.
+
+ The maximum allowed is over an area the size of TASK_SIZE / 12
+
+Linux does not employ heap randomization.
+
+Randomization is applied in the following places.
+
+
+STACK RANDOMIZATION
+
+fs/exec.c
+unsigned long arch_align_stack(unsigned long sp)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to sub-page granularity.  It applies a portion of the
+ stack entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - page_random_bits = total bits of entropy
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Raise 2^page_random_bits to get random_places
+  - Divide PAGE_SIZE by random_places to get random_interval
+  - (get_random_int() % random_places) * random_interval = offset
+  + If stack grows down
+   - Subtract offset from the stack pointer
+  + If stack grows up
+   - Add offset to the stack pointer
+
+
+fs/binfmt_elf.c
+static unsigned long randomize_stack_top(unsigned long stack_top)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to page granularity.  It applies a portion of the stack
+ entropy.
+
+ This function gets the number of possible states, i.e. positions the
+ stack can be in, and choses a random number in that range.  It then
+ multiplies the result by PAGE_SIZE to get the stack offset.
+
+
+fs/binfmt_elf.c
+static inline unsigned long randomize_stack_top_states()
+
+ This function is used by randomize_stack_top() to get how many
+ states stack randomization supplies.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - vma_random_bits = 0
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - vma_random_bits =
+               total bits entropy - MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Multiply PAGE_SIZE by 2^random_bits to get random_range
+  - random_variable = get_random_int() % random_range
+  - Offset stack in VMA by random_variable and PAGE_ALIGN() result
+
+
+MMAP RANDOMIZATION
+
+fs/exec.c
+unsigned long mmap_base_random_factor()
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+Also note the following:
+
+ - STACK_ALIGN is defined in include/asm-*/processor.h
+ - include/linux/mm.h defines STACK_ALIGN as PAGE_SIZE if it is not
+   defined
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined in
+   include/arch-*/processor.h
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined as
+   0 in include/linux/mm.h if not otherwise defined
+
arch/i386/kernel/process.c +0 -6
diff -urNp linux-2.6.16.16/arch/i386/kernel/process.c linux-2.6.16.16-randparam/arch/i386/kernel/process.c
@@ -905,9 +905,3 @@ asmlinkage int sys_get_thread_area(struc
 	return 0;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
arch/i386/mm/mmap.c +1 -2
diff -urNp linux-2.6.16.16/arch/i386/mm/mmap.c linux-2.6.16.16-randparam/arch/i386/mm/mmap.c
@@ -41,8 +41,7 @@ static inline unsigned long mmap_base(st
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_factor = mmap_base_random_factor();
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
arch/um/kernel/process_kern.c +0 -15
diff -urNp linux-2.6.16.16/arch/um/kernel/process_kern.c linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c
@@ -454,18 +454,3 @@ int singlestepping(void * t)
 	return 2;
 }
 
-/*
- * Only x86 and x86_64 have an arch_align_stack().
- * All other arches have "#define arch_align_stack(x) (x)"
- * in their asm/system.h
- * As this is included in UML from asm-um/system-generic.h,
- * we can use it to behave as the subarch does.
- */
-#ifndef arch_align_stack
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
-#endif
arch/x86_64/ia32/mmap32.c +1 -2
diff -urNp linux-2.6.16.16/arch/x86_64/ia32/mmap32.c linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c
@@ -43,8 +43,7 @@ static inline unsigned long mmap_base(st
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_factor = mmap_base_random_factor();
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
arch/x86_64/kernel/process.c +0 -6
diff -urNp linux-2.6.16.16/arch/x86_64/kernel/process.c linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c
@@ -839,9 +839,3 @@ int dump_task_regs(struct task_struct *t
 	return 1;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
arch/x86_64/mm/mmap.c +6 -6
diff -urNp linux-2.6.16.16/arch/x86_64/mm/mmap.c linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c
@@ -15,14 +15,14 @@ void arch_pick_mmap_layout(struct mm_str
 	if (current_thread_info()->flags & _TIF_IA32)
 		return ia32_pick_mmap_layout(mm);
 #endif
+
 	mm->mmap_base = TASK_UNMAPPED_BASE;
+	
 	if (current->flags & PF_RANDOMIZE) {
-		/* Add 28bit randomness which is about 40bits of address space
-		   because mmap base has to be page aligned.
- 		   or ~1/128 of the total user VM
-	   	   (total user address space is 47bits) */
-		unsigned rnd = get_random_int() & 0xfffffff;
-		mm->mmap_base += ((unsigned long)rnd) << PAGE_SHIFT;
+		unsigned long random_factor = 0;
+		/* Add our randomness. */
+		random_factor = mmap_base_random_factor();
+		mm->mmap_base += random_factor;
 	}
 	mm->get_unmapped_area = arch_get_unmapped_area;
 	mm->unmap_area = arch_unmap_area;
fs/binfmt_elf.c +31 -2
diff -urNp linux-2.6.16.16/fs/binfmt_elf.c linux-2.6.16.16-randparam/fs/binfmt_elf.c
@@ -500,13 +500,42 @@ out:
 #define INTERPRETER_AOUT 1
 #define INTERPRETER_ELF 2
 
+/* number of states accounted for by the stack, i.e.
+ * the number of random positions it can be in.
+ * Currently we find this via bits of entropy. */
+static inline unsigned long randomize_stack_top_states() {
+	long vma_random_bits = 0;
+	long random_bits = ARCH_RANDOM_STACK_BITS;
+
+	/* XXX: Place a hook here to adjust stack randomization;
+	 * this hook will change the value of random_bits */
+
+	if (random_bits > MAX_RANDOM_STACK_BITS)
+		random_bits = MAX_RANDOM_STACK_BITS;
+
+	/* Cut the bits in the sub-page randomization out */
+	if (random_bits <= MAX_RANDOM_STACK_BITS_PER_PAGE)
+		vma_random_bits = 0;
+	else
+		vma_random_bits = random_bits
+		       	- MAX_RANDOM_STACK_BITS_PER_PAGE;
+
+	/* 2^vma_random_bits */
+	return (1 << vma_random_bits);
+}
 
 static unsigned long randomize_stack_top(unsigned long stack_top)
 {
 	unsigned int random_variable = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_variable = get_random_int() % (8*1024*1024);
+	/*Randomization
+	 * Pick from 0 to how many states there are and multiply
+	 * PAGE_SIZE to get an aligned random stack base.
+	 */
+	if (current->flags & PF_RANDOMIZE) {
+		random_variable = get_random_int() % (randomize_stack_top_states());
+		random_variable *= PAGE_SIZE;
+	}
 #ifdef CONFIG_STACK_GROWSUP
 	return PAGE_ALIGN(stack_top + random_variable);
 #else
fs/exec.c +67 -0

76 lines not on this page · raw message

include/asm-i386/processor.h +7 -0
diff -urNp linux-2.6.16.16/include/asm-i386/processor.h linux-2.6.16.16-randparam/include/asm-i386/processor.h
@@ -320,6 +320,13 @@ extern int bootloader_type;
  */
 #define TASK_SIZE	(PAGE_OFFSET)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS	19
+#define ARCH_RANDOM_MMAP_BITS	8
+
 /* This decides where the kernel will search for a free chunk of vm
  * space during mmap's.
  */
include/asm-x86_64/processor.h +17 -0
diff -urNp linux-2.6.16.16/include/asm-x86_64/processor.h linux-2.6.16.16-randparam/include/asm-x86_64/processor.h
@@ -172,6 +172,23 @@ static inline void clear_in_cr4 (unsigne
 #define TASK_SIZE 		(test_thread_flag(TIF_IA32) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 #define TASK_SIZE_OF(child) 	((test_tsk_thread_flag(child, TIF_IA32)) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap() in IA-32*/
+#define IA32_ARCH_RANDOM_STACK_BITS	19
+#define IA32_ARCH_RANDOM_MMAP_BITS	8
+
+/* Random bits of stack and mmap() in 64-bit mode.
+ * 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
+ * of the address space. */
+#define ARCH_RANDOM_STACK_BITS64	28
+#define ARCH_RANDOM_MMAP_BITS64		28
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS  (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
+#define ARCH_RANDOM_MMAP_BITS   (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)
+
 #define TASK_UNMAPPED_BASE	PAGE_ALIGN(TASK_SIZE/3)
 
 /*
include/linux/mm.h +38 -0
diff -urNp linux-2.6.16.16/include/linux/mm.h linux-2.6.16.16-randparam/include/linux/mm.h
@@ -23,6 +23,44 @@ struct anon_vma;
 extern unsigned long max_mapnr;
 #endif
 
+/* Any arch not defining this is assumed to not know of
+ * sub-page stack alignment.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef STACK_ALIGN
+# define STACK_ALIGN	PAGE_SIZE
+#endif
+
+/* If these are not defined, disable randomization.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef ARCH_RANDOM_STACK_BITS
+# define ARCH_RANDOM_STACK_BITS	0
+#endif
+#ifndef ARCH_RANDOM_MMAP_BITS
+# define ARCH_RANDOM_MMAP_BITS	0
+#endif
+
+/*
+ * These are the biggest entropies we can have.
+ * Our original MAX_RANDOM_STACK_BITS was as below:
+ * 	long_log2((PAGE_SIZE / STACK_ALIGN) * (TASK_SIZE / 12) / PAGE_SIZE)
+ * This simplifies algebraicly to the below:
+ *   long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+ *
+ * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+ * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+ * on x86-64 with 47 bits of user VMA...
+ */
+#define MAX_RANDOM_STACK_BITS \
+	long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+#define MAX_RANDOM_STACK_BITS_PER_PAGE \
+	long_log2(PAGE_SIZE / STACK_ALIGN)
+#define MAX_RANDOM_MMAP_BITS \
+	long_log2((TASK_SIZE / 12) / PAGE_SIZE)
+
+unsigned long mmap_base_random_factor();
+
 extern unsigned long num_physpages;
 extern void * high_memory;
 extern unsigned long vmalloc_earlyreserve;