Function Granular KASLR

This patch makes /proc/kallsyms display in a random order, rather than sorted by address in order to hide the newly randomized address layout.

Signed-off-by Kristen Carlson Accardi <[email protected]>

Reviewed-by Tony Luck <[email protected]>

Tested-by Tony Luck <[email protected]>

---
 kernel/kallsyms.c | 163 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 162 insertions(+), 1 deletion(-)

kernel/kallsyms.c +108 -1

index bb14e64f62a4..45d147f7f10e 100644
@@ -446,6 +446,12 @@ struct kallsym_iter {
 	int show_value;
 };
 
+struct kallsyms_shuffled_iter {
+	struct kallsym_iter iter;
+	loff_t total_syms;
+	loff_t shuffled_index[];
+};
+
 int __weak arch_get_kallsym(unsigned int symnum, unsigned long *value,
 			    char *type, char *name)
 {

@@ -661,7 +667,7 @@ bool kallsyms_show_value(const struct cred *cred)
 	}
 }
 
-static int kallsyms_open(struct inode *inode, struct file *file)
+static int __kallsyms_open(struct inode *inode, struct file *file)
 {
 	/*
 	 * We keep iterator in m->private, since normal case is to

@@ -682,6 +688,161 @@ static int kallsyms_open(struct inode *inode, struct file *file)
 	return 0;
 }
 
+/*
+ * When function granular kaslr is enabled, we need to print out the symbols
+ * at random so we don't reveal the new layout.
+ */
+#if defined(CONFIG_FG_KASLR)
+static int update_random_pos(struct kallsyms_shuffled_iter *s_iter,
+			     loff_t pos, loff_t *new_pos)
+{
+	loff_t new;
+
+	if (pos >= s_iter->total_syms)
+		return 0;
+
+	new = s_iter->shuffled_index[pos];
+
+	/*
+	 * normally this would be done as part of update_iter, however,
+	 * we want to avoid triggering this in the event that new is
+	 * zero since we don't want to blow away our pos end indicators.
+	 */
+	if (new == 0) {
+		s_iter->iter.name[0] = '\0';
+		s_iter->iter.nameoff = get_symbol_offset(new);
+		s_iter->iter.pos = new;
+	}
+
+	*new_pos = new;
+	return 1;
+}
+
+static void *shuffled_start(struct seq_file *m, loff_t *pos)
+{
+	struct kallsyms_shuffled_iter *s_iter = m->private;
+	loff_t new_pos;
+
+	if (!update_random_pos(s_iter, *pos, &new_pos))
+		return NULL;
+
+	return s_start(m, &new_pos);
+}
+
+static void *shuffled_next(struct seq_file *m, void *p, loff_t *pos)
+{
+	struct kallsyms_shuffled_iter *s_iter = m->private;
+	loff_t new_pos;
+
+	(*pos)++;
+
+	if (!update_random_pos(s_iter, *pos, &new_pos))
+		return NULL;
+
+	if (!update_iter(m->private, new_pos))
+		return NULL;
+
+	return p;
+}
+
+/*
+ * shuffle_index_list()
+ * Use a Fisher Yates algorithm to shuffle a list of text sections.
+ */
+static void shuffle_index_list(loff_t *indexes, loff_t size)
+{
+	int i;
+	unsigned int j;
+	loff_t temp;
+
+	for (i = size - 1; i > 0; i--) {
+		/* pick a random index from 0 to i */
+		get_random_bytes(&j, sizeof(j));
+		j = j % (i + 1);
+
+		temp = indexes[i];
+		indexes[i] = indexes[j];
+		indexes[j] = temp;
+	}
+}
+
+static const struct seq_operations kallsyms_shuffled_op = {
+	.start = shuffled_start,
+	.next = shuffled_next,
+	.stop = s_stop,
+	.show = s_show
+};
+
+static int kallsyms_random_open(struct inode *inode, struct file *file)
+{
+	loff_t pos;
+	struct kallsyms_shuffled_iter *shuffled_iter;
+	struct kallsym_iter iter;
+	bool show_value;
+
+	/*
+	 * If privileged, go ahead and use the normal algorithm for
+	 * displaying symbols
+	 */
+	show_value = kallsyms_show_value(file->f_cred);
+	if (show_value)
+		return __kallsyms_open(inode, file);
+
+	/*

Quoted 4 lines · Kristen Carlson Accardi

This patch makes /proc/kallsyms display in a random order, rather than sorted by address in order to hide the newly randomized address
layout.

Ah! Much nicer. Is there any reason not to just do this unconditionally,
regardless of FGKASLR? It's a smallish dynamic allocation, and displaying kallsyms is hardly fast-path...

Quoted 162 lines

Signed-off-by Kristen Carlson Accardi <[email protected]>

Reviewed-by Tony Luck <[email protected]>

Tested-by Tony Luck <[email protected]>

---
 kernel/kallsyms.c | 163
+++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 162 insertions(+), 1 deletion(-)

kernel/kallsyms.c +3 -0

index bb14e64f62a4..45d147f7f10e 100644
@@ -446,6 +446,12 @@ struct kallsym_iter {
 	int show_value;
 };
 
+struct kallsyms_shuffled_iter {
+	struct kallsym_iter iter;
+	loff_t total_syms;

Quoted 2 lines

(I need to go read how kallsyms doesn't miscount in general when

the

Quoted 3 lines

symbol table changes out from under it...)

kernel/kallsyms.c +3 -0

+	loff_t shuffled_index[];
+};
+
 int __weak arch_get_kallsym(unsigned int symnum, unsigned long

*value,

kernel/kallsyms.c +1 -1

 			    char *type, char *name)
 {

@@ -661,7 +667,7 @@ bool kallsyms_show_value(const struct cred
 *cred)
 	}
 }
 
-static int kallsyms_open(struct inode *inode, struct file *file)
+static int __kallsyms_open(struct inode *inode, struct file *file)
 {
 	/*

kernel/kallsyms.c +2 -0

 	 * We keep iterator in m->private, since normal case is to

@@ -682,6 +688,161 @@ static int kallsyms_open(struct inode *inode,
 struct file *file)
 	return 0;
 }
 
+/*
+ * When function granular kaslr is enabled, we need to print out

the symbols
+ * at random so we don't reveal the new layout.
+ */

kernel/kallsyms.c +2 -0

+#if defined(CONFIG_FG_KASLR)
+static int update_random_pos(struct kallsyms_shuffled_iter

*s_iter,

kernel/kallsyms.c +13 -0

+			     loff_t pos, loff_t *new_pos)
+{
+	loff_t new;
+
+	if (pos >= s_iter->total_syms)
+		return 0;
+
+	new = s_iter->shuffled_index[pos];
+
+	/*
+	 * normally this would be done as part of update_iter, however,
+	 * we want to avoid triggering this in the event that new is
+	 * zero since we don't want to blow away our pos end

indicators.

kernel/kallsyms.c +23 -0

+	 */
+	if (new == 0) {
+		s_iter->iter.name[0] = '\0';
+		s_iter->iter.nameoff = get_symbol_offset(new);
+		s_iter->iter.pos = new;
+	}
+
+	*new_pos = new;
+	return 1;
+}
+
+static void *shuffled_start(struct seq_file *m, loff_t *pos)
+{
+	struct kallsyms_shuffled_iter *s_iter = m->private;
+	loff_t new_pos;
+
+	if (!update_random_pos(s_iter, *pos, &new_pos))
+		return NULL;
+
+	return s_start(m, &new_pos);
+}
+
+static void *shuffled_next(struct seq_file *m, void *p, loff_t

*pos)

kernel/kallsyms.c +18 -0

+{
+	struct kallsyms_shuffled_iter *s_iter = m->private;
+	loff_t new_pos;
+
+	(*pos)++;
+
+	if (!update_random_pos(s_iter, *pos, &new_pos))
+		return NULL;
+
+	if (!update_iter(m->private, new_pos))
+		return NULL;
+
+	return p;
+}
+
+/*
+ * shuffle_index_list()
+ * Use a Fisher Yates algorithm to shuffle a list of text

sections.
+ */

kernel/kallsyms.c +25 -0

+static void shuffle_index_list(loff_t *indexes, loff_t size)
+{
+	int i;
+	unsigned int j;
+	loff_t temp;
+
+	for (i = size - 1; i > 0; i--) {
+		/* pick a random index from 0 to i */
+		get_random_bytes(&j, sizeof(j));
+		j = j % (i + 1);
+
+		temp = indexes[i];
+		indexes[i] = indexes[j];
+		indexes[j] = temp;
+	}
+}
+
+static const struct seq_operations kallsyms_shuffled_op = {
+	.start = shuffled_start,
+	.next = shuffled_next,
+	.stop = s_stop,
+	.show = s_show
+};
+
+static int kallsyms_random_open(struct inode *inode, struct file

*file)

kernel/kallsyms.c +22 -0

+{
+	loff_t pos;
+	struct kallsyms_shuffled_iter *shuffled_iter;
+	struct kallsym_iter iter;
+	bool show_value;
+
+	/*
+	 * If privileged, go ahead and use the normal algorithm for
+	 * displaying symbols
+	 */
+	show_value = kallsyms_show_value(file->f_cred);
+	if (show_value)
+		return __kallsyms_open(inode, file);
+
+	/*
+	 * we need to figure out how many extra symbols there are
+	 * to print out past kallsyms_num_syms
+	 */
+	pos = kallsyms_num_syms;
+	reset_iter(&iter, 0);
+	do {
+		if (!update_iter(&iter, pos))

kernel/kallsyms.c static int kallsyms_open(struct inode *inode, struct file *file) · line 801

Quoted 3 lines

kernel/kallsyms.c +3 -0

+			break;
+		pos++;
+	} while (1);

Can this be tracked separately instead of needing to search for it every
time? (Looks like it's modules and ftrace? Could they each have a *_num_sysms?)

Introduce a new config option to allow modules to be re-ordered by function. This option can be enabled independently of the kernel text KASLR or FG_KASLR settings so that it can be used by architectures that do not support either of these features. This option will be selected by default if CONFIG_FG_KASLR is selected.

If a module has functions split out into separate text sections (i.e. compiled with the -ffunction-sections flag), reorder the functions to provide some code diversification to modules.

Signed-off-by Kristen Carlson Accardi <[email protected]>

Reviewed-by Kees Cook <[email protected]>

Acked-by Ard Biesheuvel <[email protected]>

Tested-by Ard Biesheuvel <[email protected]>

Reviewed-by Tony Luck <[email protected]>

Tested-by Tony Luck <[email protected]>

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
---------------------------------------------------------------------

This patch set is an implementation of finer grained kernel address space randomization. It rearranges your kernel code at load time
on a per-function level granularity, with only around a second added to boot time.

Background
----------
KASLR was merged into the kernel with the objective of increasing the difficulty of code reuse attacks. Code reuse attacks reused existing code snippets to get around existing memory protections. They exploit software bugs which expose addresses of useful code snippets to control the flow of execution for their own nefarious purposes. KASLR moves the entire kernel code text as a unit at boot time in order to make addresses less predictable. The order of the code within the segment is unchanged - only the base address is shifted. There are a few shortcomings to this algorithm.

1. Low Entropy - there are only so many locations the kernel can fit in. This means an attacker could guess without too much trouble.
2. Knowledge of a single address can reveal the offset of the base address, exposing all other locations for a published/known kernel image.
3. Info leaks abound.

Finer grained ASLR has been proposed as a way to make ASLR more resistant to info leaks. It is not a new concept at all, and there are many variations possible. Function reordering is an implementation of finer grained ASLR which randomizes the layout of an address space on a function level granularity. We use the term "fgkaslr" in this document to refer to the technique of function reordering when used with KASLR, as well as finer grained KASLR in general.

Proposed Improvement
--------------------
This patch set proposes adding function reordering on top of the existing KASLR base address randomization. The over-arching objective is incremental improvement over what we already have. It is designed to work in combination with the existing solution. The implementation is really pretty simple, and there are 2 main area where changes occur:

* Build time

GCC has had an option to place functions into individual .text sections for many years now. This option can be used to implement function reordering at load time. The final compiled vmlinux retains all the section headers, which can be used to help find the address ranges of each function. Using this information and an expanded table of relocation addresses, individual text sections can be suffled immediately after decompression. Some data tables inside the kernel that have assumptions about order require re-sorting after being updated when applying relocations. In order to modify these tables, a few key symbols are excluded from the objcopy symbol stripping process for use after shuffling the text segments.

Some highlights from the build time changes to look for:

The top level kernel Makefile was modified to add the gcc flag if it is supported. Currently, I am applying this flag to everything it is possible to randomize. Anything that is written in C and not present in a special input section is randomized. The final binary segment 0 retains a consolidated .text section, as well as all the individual .text.* sections. Future work could turn off this flags for selected files or even entire subsystems, although obviously at the cost of security.

The relocs tool is updated to add relative relocations. This information previously wasn't included because it wasn't necessary when moving the entire .text segment as a unit.

A new file was created to contain a list of symbols that objcopy should keep. We use those symbols at load time as described below.

* Load time

The boot kernel was modified to parse the vmlinux elf file after decompression to check for our interesting symbols that we kept, and to look for any .text.* sections to randomize. The consolidated .text section is skipped and not moved. The sections are shuffled randomly, and copied into memory following the .text section in a new random order. The existing code which updated relocation addresses was modified to account for not just a fixed delta from the load address, but the offset that the function section was moved to. This requires inspection of each address to see if it was impacted by a randomization. We use a bsearch to make this less horrible on performance. Any tables that need to be modified with new addresses or resorted are updated using the symbol addresses parsed from the elf symbol table.

In order to hide our new layout, symbols reported through /proc/kallsyms will be displayed in a random order.

Security Considerations
-----------------------
The objective of this patch set is to improve a technology that is already merged into the kernel (KASLR). This code will not prevent all attacks, but should instead be considered as one of several tools that can be used. In particular, this code is meant to make KASLR more effective in the presence of info leaks.

How much entropy we are adding to the existing entropy of standard KASLR will depend on a few variables. Firstly and most obviously, the number of functions that are randomized matters. This implementation keeps the existing .text section for code that cannot be randomized - for example, because it was assembly code. The less sections to randomize, the less entropy. In addition, due to alignment (16 bytes for x86_64), the number of bits in a address that the attacker needs to guess is reduced, as the lower bits are identical.

Modules
-------
Modules are randomized similarly to the rest of the kernel by shuffling the sections at load time prior to moving them into memory. The module must also have been build with the -ffunction-sections compiler option.

Although fgkaslr for the kernel is only supported for the X86_64 architecture, it is possible to use fgkaslr with modules on other architectures. To enable this feature, select

CONFIG_MODULE_FG_KASLR=y

This option is selected automatically for X86_64 when CONFIG_FG_KASLR is set.

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables fgkaslr. It is also possible to disable fgkaslr separately by booting with fgkaslr=off on the commandline.

Let me CC live-patching ML, because from a quick glance this is something which could impact live patching code. At least it invalidates assumptions which "sympos" is based on.

Quoted 3 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something which could impact live patching code. At least it invalidates assumptions which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

Quoted 9 lines · Kees Cook

Quoted 3 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something which could impact live patching code. At least it invalidates assumptions which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

Hi Kees,

I don't think any of the in-tree tests currently exercise the kallsyms/sympos end of livepatching.

Quoted 13 lines · Joe Lawrence

Quoted 11 lines · Kees Cook

Quoted 5 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something
which could impact live patching code. At least it invalidates assumptions
which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

Quoted 5 lines

Hi Kees,

I don't think any of the in-tree tests currently exercise the kallsyms/sympos end of livepatching.

On second thought, I mispoke.. The general livepatch code does use it:

klp_init_object
klp_init_object_loaded
klp_find_object_symbol

in which case any of the current kselftests should exercise that.

% make -C tools/testing/selftests/livepatch run_tests

-- Joe

Quoted 3 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something which could impact live patching code. At least it invalidates assumptions which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

Quoted 8 lines · Kees Cook

Quoted 3 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something which could impact live patching code. At least it invalidates assumptions which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

The problem is duplicate symbols. If there are two static functions named 'foo' then livepatch needs a way to distinguish them.

Our current approach to that problem is "sympos". We rely on the fact that the second foo() always comes after the first one in the symbol list and kallsyms. So they're referred to as foo,1 and foo,2.

Quoted 16 lines · Josh Poimboeuf

Quoted 10 lines · Kees Cook

Quoted 5 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something
which could impact live patching code. At least it invalidates assumptions
which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

The problem is duplicate symbols. If there are two static functions
named 'foo' then livepatch needs a way to distinguish them.

Quoted 5 lines

Our current approach to that problem is "sympos". We rely on the fact
that the second foo() always comes after the first one in the symbol
list and kallsyms. So they're referred to as foo,1 and foo,2.

Ah. Fun. In that case, perhaps the LTO series has some solutions. I think builds with LTO end up renaming duplicate symbols like that, so it'll be back to being unique.

Quoted 23 lines · Kees Cook

Quoted 16 lines · Josh Poimboeuf

Quoted 10 lines · Kees Cook

Quoted 5 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is something
which could impact live patching code. At least it invalidates assumptions
which "sympos" is based on.

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good selftest for live-patching?

The problem is duplicate symbols. If there are two static functions
named 'foo' then livepatch needs a way to distinguish them.

Quoted 5 lines

Our current approach to that problem is "sympos". We rely on the fact
that the second foo() always comes after the first one in the symbol
list and kallsyms. So they're referred to as foo,1 and foo,2.

Quoted 4 lines

Ah. Fun. In that case, perhaps the LTO series has some solutions. I think builds with LTO end up renaming duplicate symbols like that, so it'll be back to being unique.

Well, glad to hear there might be some precendence for how to solve this, as I wasn't able to think of something reasonable off the top of my head. Are you speaking of the Clang LTO series?
https://lore.kernel.org/lkml/[email protected]/

Quoted 36 lines · Kristen Carlson Accardi

Quoted 28 lines · Kees Cook

Quoted 20 lines · Josh Poimboeuf

Quoted 10 lines · Kees Cook

Quoted 7 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is
something
which could impact live patching code. At least it invalidates
assumptions
which "sympos" is based on.

Quoted 4 lines

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good
selftest for live-patching?

The problem is duplicate symbols. If there are two static functions
named 'foo' then livepatch needs a way to distinguish them.

Quoted 6 lines

Our current approach to that problem is "sympos". We rely on the
fact
that the second foo() always comes after the first one in the symbol
list and kallsyms. So they're referred to as foo,1 and foo,2.

Quoted 6 lines

Ah. Fun. In that case, perhaps the LTO series has some solutions. I
think builds with LTO end up renaming duplicate symbols like that, so
it'll be back to being unique.

Quoted 5 lines

Well, glad to hear there might be some precendence for how to solve this, as I wasn't able to think of something reasonable off the top of
my head. Are you speaking of the Clang LTO series?
https://lore.kernel.org/lkml/[email protected]/

I'm not sure how LTO does it, but a few more (half-brained) ideas that
could work:

1) Add a field in kallsyms to keep track of a symbol's original offset
before randomization/re-sorting. Livepatch could use that field
to
determine the original sympos.

2) In fgkaslr code, go through all the sections and mark the ones which
have duplicates (i.e. same name). Then when shuffling the
sections,
skip a shuffle if it involves a duplicate section. That way all
the
duplicates would retain their original sympos.

3) Livepatch could uniquely identify symbols by some feature other than
sympos. For example:

Symbol/function size - obviously this would only work if
duplicately
named symbols have different sizes.

Checksum - as part of a separate feature we're also looking at
giving
each function its own checksum, calculated based on its
instruction
opcodes. Though calculating checksums at runtime could be complicated by IP-relative addressing.

I'm thinking #1 or #2 wouldn't be too bad. #3 might be harder.

Quoted 70 lines · Josh Poimboeuf

Quoted 36 lines · Kristen Carlson Accardi

Quoted 28 lines · Kees Cook

Quoted 20 lines · Josh Poimboeuf

Quoted 10 lines · Kees Cook

Quoted 7 lines · Miroslav Benes

Let me CC live-patching ML, because from a quick glance this is
something
which could impact live patching code. At least it invalidates
assumptions
which "sympos" is based on.

Quoted 4 lines

In a quick skim, it looks like the symbol resolution is using kallsyms_on_each_symbol(), so I think this is safe? What's a good
selftest for live-patching?

The problem is duplicate symbols. If there are two static functions
named 'foo' then livepatch needs a way to distinguish them.

Quoted 6 lines

Our current approach to that problem is "sympos". We rely on the
fact
that the second foo() always comes after the first one in the symbol
list and kallsyms. So they're referred to as foo,1 and foo,2.

Quoted 6 lines

Ah. Fun. In that case, perhaps the LTO series has some solutions. I
think builds with LTO end up renaming duplicate symbols like that, so
it'll be back to being unique.

Quoted 5 lines

Well, glad to hear there might be some precendence for how to solve this, as I wasn't able to think of something reasonable off the top of
my head. Are you speaking of the Clang LTO series?
https://lore.kernel.org/lkml/[email protected]/

I'm not sure how LTO does it, but a few more (half-brained) ideas that
could work:

1) Add a field in kallsyms to keep track of a symbol's original offset
before randomization/re-sorting. Livepatch could use that field
to
determine the original sympos.

2) In fgkaslr code, go through all the sections and mark the ones which
have duplicates (i.e. same name). Then when shuffling the
sections,
skip a shuffle if it involves a duplicate section. That way all
the
duplicates would retain their original sympos.

3) Livepatch could uniquely identify symbols by some feature other than
sympos. For example:

Symbol/function size - obviously this would only work if
duplicately
named symbols have different sizes.

Quoted 9 lines

Checksum - as part of a separate feature we're also looking at
giving
each function its own checksum, calculated based on its
instruction
opcodes. Though calculating checksums at runtime could be complicated by IP-relative addressing.

I'm thinking #1 or #2 wouldn't be too bad. #3 might be harder.

Hi there! I was trying to find a super easy way to address this, so I thought the best thing would be if there were a compiler or linker switch to just eliminate any duplicate symbols at compile time for vmlinux. I filed this question on the binutils bugzilla looking to see if there were existing flags that might do this, but H.J. Lu went ahead and created a new one "-z unique", that seems to do what we would need it to do.

https://sourceware.org/bugzilla/show_bug.cgi?id=26391

When I use this option, it renames any duplicate symbols with an extension - for example duplicatefunc.1 or duplicatefunc.2.

You could
either match on the full unique name of the specific binary you are trying to patch, or you match the base name and use the extension to determine original position. Do you think this solution would work?

If
so, I can modify livepatch to refuse to patch on duplicated symbols if CONFIG_FG_KASLR and when this option is merged into the tool chain I can add it to KBUILD_LDFLAGS when CONFIG_FG_KASLR and livepatching should work in all cases.

Quoted 26 lines

I'm not sure how LTO does it, but a few more (half-brained) ideas that
could work:

1) Add a field in kallsyms to keep track of a symbol's original offset
before randomization/re-sorting. Livepatch could use that field
to
determine the original sympos.

2) In fgkaslr code, go through all the sections and mark the ones which
have duplicates (i.e. same name). Then when shuffling the
sections,
skip a shuffle if it involves a duplicate section. That way all
the
duplicates would retain their original sympos.

3) Livepatch could uniquely identify symbols by some feature other than
sympos. For example:

Symbol/function size - obviously this would only work if
duplicately
named symbols have different sizes.

Quoted 9 lines

Checksum - as part of a separate feature we're also looking at
giving
each function its own checksum, calculated based on its
instruction
opcodes. Though calculating checksums at runtime could be complicated by IP-relative addressing.

I'm thinking #1 or #2 wouldn't be too bad. #3 might be harder.

Hi there! I was trying to find a super easy way to address this, so I thought the best thing would be if there were a compiler or linker switch to just eliminate any duplicate symbols at compile time for vmlinux. I filed this question on the binutils bugzilla looking to see if there were existing flags that might do this, but H.J. Lu went ahead and created a new one "-z unique", that seems to do what we would need it to do.

https://sourceware.org/bugzilla/show_bug.cgi?id=26391

When I use this option, it renames any duplicate symbols with an extension - for example duplicatefunc.1 or duplicatefunc.2. You could either match on the full unique name of the specific binary you are trying to patch, or you match the base name and use the extension to determine original position. Do you think this solution would work?

If
so, I can modify livepatch to refuse to patch on duplicated symbols if CONFIG_FG_KASLR and when this option is merged into the tool chain I can add it to KBUILD_LDFLAGS when CONFIG_FG_KASLR and livepatching should work in all cases.

Quoted 8 lines

Hi there! I was trying to find a super easy way to address this, so I thought the best thing would be if there were a compiler or linker switch to just eliminate any duplicate symbols at compile time for vmlinux. I filed this question on the binutils bugzilla looking to see if there were existing flags that might do this, but H.J. Lu went ahead and created a new one "-z unique", that seems to do what we would need it to do.

Quoted 7 lines

https://sourceware.org/bugzilla/show_bug.cgi?id=26391

When I use this option, it renames any duplicate symbols with an extension - for example duplicatefunc.1 or duplicatefunc.2. You could either match on the full unique name of the specific binary you are trying to patch, or you match the base name and use the extension to determine original position. Do you think this solution would work?

Yes, I think so (thanks, Joe, for testing!).

It looks cleaner to me than the options above, but it may just be a matter of taste. Anyway, I'd go with full name matching, because -z unique-symbol would allow us to remove sympos altogether, which is appealing.

Quoted 5 lines

If
so, I can modify livepatch to refuse to patch on duplicated symbols if CONFIG_FG_KASLR and when this option is merged into the tool chain I can add it to KBUILD_LDFLAGS when CONFIG_FG_KASLR and livepatching should work in all cases.

Ok.

Josh, Petr, would this work for you too?

Quoted 28 lines · Miroslav Benes

Quoted 8 lines

Hi there! I was trying to find a super easy way to address this, so I thought the best thing would be if there were a compiler or linker switch to just eliminate any duplicate symbols at compile time for vmlinux. I filed this question on the binutils bugzilla looking to see if there were existing flags that might do this, but H.J. Lu went ahead and created a new one "-z unique", that seems to do what we would need it to do.

Quoted 7 lines

https://sourceware.org/bugzilla/show_bug.cgi?id=26391

When I use this option, it renames any duplicate symbols with an extension - for example duplicatefunc.1 or duplicatefunc.2. You could either match on the full unique name of the specific binary you are trying to patch, or you match the base name and use the extension to determine original position. Do you think this solution would work?

Yes, I think so (thanks, Joe, for testing!).

It looks cleaner to me than the options above, but it may just be a matter of taste. Anyway, I'd go with full name matching, because -z unique-symbol would allow us to remove sympos altogether, which is appealing.

Quoted 5 lines

If
so, I can modify livepatch to refuse to patch on duplicated symbols if CONFIG_FG_KASLR and when this option is merged into the tool chain I can add it to KBUILD_LDFLAGS when CONFIG_FG_KASLR and livepatching should work in all cases.

Quoted 3 lines

Ok.

Josh, Petr, would this work for you too?

Sounds good to me. Kristen, thanks for finding a solution!

This works great after randomization because it always receives the current address at runtime rather than relying on any kind of buildtime address. The issue with with the live-patching code's algorithm for resolving duplicate symbol names. If they request a symbol by name from the kernel and there are 3 symbols with the same name, they use the symbol's position in the built binary image to select the correct symbol.

Quoted 29 lines · Josh Poimboeuf

Quoted 28 lines · Miroslav Benes

Quoted 8 lines

Hi there! I was trying to find a super easy way to address this, so I thought the best thing would be if there were a compiler or linker switch to just eliminate any duplicate symbols at compile time for vmlinux. I filed this question on the binutils bugzilla looking to see if there were existing flags that might do this, but H.J. Lu went ahead and created a new one "-z unique", that seems to do what we would need it to do.

Quoted 7 lines

https://sourceware.org/bugzilla/show_bug.cgi?id=26391

When I use this option, it renames any duplicate symbols with an extension - for example duplicatefunc.1 or duplicatefunc.2. You could either match on the full unique name of the specific binary you are trying to patch, or you match the base name and use the extension to determine original position. Do you think this solution would work?

Yes, I think so (thanks, Joe, for testing!).

It looks cleaner to me than the options above, but it may just be a matter of taste. Anyway, I'd go with full name matching, because -z unique-symbol would allow us to remove sympos altogether, which is appealing.

Quoted 5 lines

If
so, I can modify livepatch to refuse to patch on duplicated symbols if CONFIG_FG_KASLR and when this option is merged into the tool chain I can add it to KBUILD_LDFLAGS when CONFIG_FG_KASLR and livepatching should work in all cases.

Quoted 5 lines

Quoted 3 lines

Ok.

Josh, Petr, would this work for you too?

Sounds good to me. Kristen, thanks for finding a solution!

(I am not subscribed. I came here via https://sourceware.org/bugzilla/show_bug.cgi?id=26391 (ld -z unique-symbol))

Quoted 7 lines

This works great after randomization because it always receives the current address at runtime rather than relying on any kind of buildtime address. The issue with with the live-patching code's algorithm for resolving duplicate symbol names. If they request a symbol by name from the kernel and there are 3 symbols with the same name, they use the symbol's position in the built binary image to select the correct symbol.

If a.o, b.o and c.o define local symbol 'foo'.
By position, do you mean that

* the live-patching code uses something like (findall("foo")[0], findall("foo")[1], findall("foo")[2]) ?

* shuffling a.o/b.o/c.o will make the returned triple different

Local symbols are not required to be unique. Instead of patching the toolchain, have you thought about making the live-patching code smarter?

(Depend on the duplicates, such a linker option can increase the link time/binary size considerably

AND I don't know in what other cases such an option will be useful)

For the following example,

https://sourceware.org/bugzilla/show_bug.cgi?id=26822

# RUN: split-file %s %t
# RUN: gcc -c %t/a.s -o %t/a.o
# RUN: gcc -c %t/b.s -o %t/b.o
# RUN: gcc -c %t/c.s -o %t/c.o
# RUN: ld-new %t/a.o %t/b.o %t/c.o -z unique-symbol -o %t.exe #--- a.s
a: a.1: a.2: nop
#--- b.s
a: nop
#--- c.s
a: nop

readelf -Ws output:

Symbol table '.symtab' contains 13 entries:

   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND      1:
0000000000000000     0 FILE    LOCAL  DEFAULT  ABS a.o
     2: 0000000000401000     0 NOTYPE  LOCAL  DEFAULT    1 a
     3: 0000000000401000     0 NOTYPE  LOCAL  DEFAULT    1 a.1
     4: 0000000000401000     0 NOTYPE  LOCAL  DEFAULT    1 a.2
     5: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS b.o
     6: 0000000000401001     0 NOTYPE  LOCAL  DEFAULT    1 a.1
     7: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS c.o
     8: 0000000000401002     0 NOTYPE  LOCAL  DEFAULT    1 a.2
     9: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _start
    10: 0000000000402000     0 NOTYPE  GLOBAL DEFAULT    1 __bss_start
    11: 0000000000402000     0 NOTYPE  GLOBAL DEFAULT    1 _edata
    12: 0000000000402000     0 NOTYPE  GLOBAL DEFAULT    1 _end

Note that you have STT_FILE SHN_ABS symbols.
If the compiler does not produce them, they will be synthesized by GNU ld.

https://sourceware.org/bugzilla/show_bug.cgi?id=26822
ld.bfd copies non-STT_SECTION local symbols from input object files. If an object file does not have STT_FILE symbols (no .file directive) but has non-STT_SECTION local symbols, ld.bfd synthesizes a STT_FILE symbol

The filenames are usually base names, so "a.o" and "a.o" in two directories will be indistinguishable. The live-patching code can possibly work around this by not changing the relative order of the two "a.o".

Quoted 8 lines

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
---------------------------------------------------------------------

This patch set is an implementation of finer grained kernel address space randomization. It rearranges your kernel code at load time
on a per-function level granularity, with only around a second added to boot time.

[...]

Quoted 5 lines

Modules
-------
Modules are randomized similarly to the rest of the kernel by shuffling the sections at load time prior to moving them into memory. The module must also have been build with the -ffunction-sections compiler option.

There are at least 2 places where high-order memory allocations might happen during module loading. Such allocations may fail if memory is fragmented, while physically contiguous memory areas are not really needed there. I suggest to switch to kvmalloc/kvfree there.

Quoted 4 lines · Evgenii Shatokhin

There are at least 2 places where high-order memory allocations might happen during module loading. Such allocations may fail if memory is fragmented, while physically contiguous memory areas are not really needed there. I suggest to switch to kvmalloc/kvfree there.

While this does seem to be the right solution for the extant problem, I do want to take a moment and ask if the function sections need to be exposed at all? What tools use this information, and do they just want to see the bounds of the code region? (i.e. the start/end of all the .text* sections) Perhaps .text.* could be excluded from the sysfs section list?

Quoted 6 lines

While this does seem to be the right solution for the extant problem, I do want to take a moment and ask if the function sections need to be exposed at all? What tools use this information, and do they just want to see the bounds of the code region? (i.e. the start/end of all the .text* sections) Perhaps .text.* could be excluded from the sysfs section list?

[[cc += FChE, see [0] for Evgenii's full mail ]]

It looks like debugging tools like systemtap [1], gdb [2] and its add-symbol-file cmd, etc. peek at the /sys/module/<MOD>/section/ info. But yeah, it would be preferable if we didn't export a long sysfs representation if nobody actually needs it.

Hi -

Quoted 8 lines

Quoted 6 lines

While this does seem to be the right solution for the extant problem, I do want to take a moment and ask if the function sections need to be exposed at all? What tools use this information, and do they just want to see the bounds of the code region? (i.e. the start/end of all the .text* sections) Perhaps .text.* could be excluded from the sysfs section list?

[[cc += FChE, see [0] for Evgenii's full mail ]]

Thanks!

Quoted 4 lines

It looks like debugging tools like systemtap [1], gdb [2] and its add-symbol-file cmd, etc. peek at the /sys/module/<MOD>/section/ info. But yeah, it would be preferable if we didn't export a long sysfs representation if nobody actually needs it.

Systemtap needs to know base addresses of loaded text & data sections, in order to perform relocation of probe point PCs and context data addresses. It uses /sys/module/...., kind of under protest, because there seems to exist no MODULE_EXPORT'd API to get at that information some other way.

[...]

Quoted 5 lines

Systemtap needs to know base addresses of loaded text & data sections, in order to perform relocation of probe point PCs and context data addresses. It uses /sys/module/...., kind of under protest, because there seems to exist no MODULE_EXPORT'd API to get at that information some other way.

Wouldn't /proc/kallsysms entries cover this? I must be missing something...

Hi -

Quoted 9 lines · Kees Cook

[...]

Quoted 5 lines

Systemtap needs to know base addresses of loaded text & data sections, in order to perform relocation of probe point PCs and context data addresses. It uses /sys/module/...., kind of under protest, because there seems to exist no MODULE_EXPORT'd API to get at that information some other way.

Wouldn't /proc/kallsysms entries cover this? I must be missing something...

We have relocated based on sections, not some subset of function symbols accessible that way, partly because DWARF line- and DIE- based probes can map to addresses some way away from function symbols, into function interiors, or cloned/moved bits of optimized code. It would take some work to prove that function-symbol based heuristic arithmetic would have just as much reach.

Quoted 6 lines

We have relocated based on sections, not some subset of function symbols accessible that way, partly because DWARF line- and DIE- based probes can map to addresses some way away from function symbols, into function interiors, or cloned/moved bits of optimized code. It would take some work to prove that function-symbol based heuristic arithmetic would have just as much reach.

Interesting. Do you have an example handy?

It seems like something like that would reference the enclosing section, which means we can't just leave them out of the sysfs list... (but if such things never happen in the function-sections, then we *can* remove them...)

Quoted 5 lines · Evgenii Shatokhin

Quoted 4 lines

There are at least 2 places where high-order memory allocations might happen during module loading. Such allocations may fail if memory is fragmented, while physically contiguous memory areas are not really needed there. I suggest to switch to kvmalloc/kvfree there.

Quoted 6 lines

While this does seem to be the right solution for the extant problem, I do want to take a moment and ask if the function sections need to be exposed at all? What tools use this information, and do they just want to see the bounds of the code region? (i.e. the start/end of all the .text* sections) Perhaps .text.* could be excluded from the sysfs section list?

[[cc += FChE, see [0] for Evgenii's full mail ]]

It looks like debugging tools like systemtap [1], gdb [2] and its add-symbol-file cmd, etc. peek at the /sys/module/<MOD>/section/ info.

But yeah, it would be preferable if we didn't export a long sysfs representation if nobody actually needs it.

[0] https://lore.kernel.org/lkml/[email protected]/
[1] https://fossies.org/linux/systemtap/staprun/staprun.c
[2] https://www.oreilly.com/library/view/linux-device-drivers/0596005903/ch04.html#linuxdrive3-CHP-4-SECT-6.1

-- Joe

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
---------------------------------------------------------------------

This patch set is an implementation of finer grained kernel address space randomization. It rearranges your kernel code at load time
on a per-function level granularity, with only around a second added to boot time.

Changes in v4:
-------------
* dropped the patch to split out change to STATIC definition in x86/boot/compressed/misc.c and replaced with a patch authored by Kees Cook to avoid the duplicate malloc definitions
* Added a section to Documentation/admin-guide/kernel-parameters.txt to document the fgkaslr boot option.
* redesigned the patch to hide the new layout when reading /proc/kallsyms. The previous implementation utilized a dynamically allocated linked list to display the kernel and module symbols in alphabetical order. The new implementation uses a randomly shuffled index array to display the kernel and module symbols in a random order.

Changes in v3:
-------------
* Makefile changes to accommodate CONFIG_LD_DEAD_CODE_DATA_ELIMINATION
* removal of extraneous ALIGN_PAGE from _etext changes
* changed variable names in x86/tools/relocs to be less confusing
* split out change to STATIC definition in x86/boot/compressed/misc.c
* Updates to Documentation to make it more clear what is preserved in .text
* much more detailed commit message for function granular KASLR patch
* minor tweaks and changes that make for more readable code
* this cover letter updated slightly to add additional details

Changes in v2:
--------------
* Fix to address i386 build failure
* Allow module reordering patch to be configured separately so that arm (or other non-x86_64 arches) can take advantage of module function reordering. This support has not be tested by me, but smoke tested by Ard Biesheuvel <[email protected]> on arm.
* Fix build issue when building on arm as reported by
Ard Biesheuvel <[email protected]>

Patches to objtool are included because they are dependencies for this patchset, however they have been submitted by their maintainer separately.

Background
----------
KASLR was merged into the kernel with the objective of increasing the difficulty of code reuse attacks. Code reuse attacks reused existing code snippets to get around existing memory protections. They exploit software bugs which expose addresses of useful code snippets to control the flow of execution for their own nefarious purposes. KASLR moves the entire kernel code text as a unit at boot time in order to make addresses less predictable. The order of the code within the segment is unchanged - only the base address is shifted. There are a few shortcomings to this algorithm.

1. Low Entropy - there are only so many locations the kernel can fit in. This means an attacker could guess without too much trouble.
2. Knowledge of a single address can reveal the offset of the base address, exposing all other locations for a published/known kernel image.
3. Info leaks abound.

Finer grained ASLR has been proposed as a way to make ASLR more resistant to info leaks. It is not a new concept at all, and there are many variations possible. Function reordering is an implementation of finer grained ASLR which randomizes the layout of an address space on a function level granularity. We use the term "fgkaslr" in this document to refer to the technique of function reordering when used with KASLR, as well as finer grained KASLR in general.

Proposed Improvement
--------------------
This patch set proposes adding function reordering on top of the existing KASLR base address randomization. The over-arching objective is incremental improvement over what we already have. It is designed to work in combination with the existing solution. The implementation is really pretty simple, and there are 2 main area where changes occur:

* Build time

GCC has had an option to place functions into individual .text sections for many years now. This option can be used to implement function reordering at load time. The final compiled vmlinux retains all the section headers, which can be used to help find the address ranges of each function. Using this information and an expanded table of relocation addresses, individual text sections can be suffled immediately after decompression. Some data tables inside the kernel that have assumptions about order require re-sorting after being updated when applying relocations. In order to modify these tables, a few key symbols are excluded from the objcopy symbol stripping process for use after shuffling the text segments.

Some highlights from the build time changes to look for:

The top level kernel Makefile was modified to add the gcc flag if it is supported. Currently, I am applying this flag to everything it is possible to randomize. Anything that is written in C and not present in a special input section is randomized. The final binary segment 0 retains a consolidated .text section, as well as all the individual .text.* sections. Future work could turn off this flags for selected files or even entire subsystems, although obviously at the cost of security.

The relocs tool is updated to add relative relocations. This information previously wasn't included because it wasn't necessary when moving the entire .text segment as a unit.

A new file was created to contain a list of symbols that objcopy should keep. We use those symbols at load time as described below.

* Load time

The boot kernel was modified to parse the vmlinux elf file after decompression to check for our interesting symbols that we kept, and to look for any .text.* sections to randomize. The consolidated .text section is skipped and not moved. The sections are shuffled randomly, and copied into memory following the .text section in a new random order. The existing code which updated relocation addresses was modified to account for not just a fixed delta from the load address, but the offset that the function section was moved to. This requires inspection of each address to see if it was impacted by a randomization. We use a bsearch to make this less horrible on performance. Any tables that need to be modified with new addresses or resorted are updated using the symbol addresses parsed from the elf symbol table.

In order to hide our new layout, symbols reported through /proc/kallsyms will be displayed in a random order.

Security Considerations
-----------------------
The objective of this patch set is to improve a technology that is already merged into the kernel (KASLR). This code will not prevent all attacks, but should instead be considered as one of several tools that can be used. In particular, this code is meant to make KASLR more effective in the presence of info leaks.

How much entropy we are adding to the existing entropy of standard KASLR will depend on a few variables. Firstly and most obviously, the number of functions that are randomized matters. This implementation keeps the existing .text section for code that cannot be randomized - for example, because it was assembly code. The less sections to randomize, the less entropy. In addition, due to alignment (16 bytes for x86_64), the number of bits in a address that the attacker needs to guess is reduced, as the lower bits are identical.

Performance Impact
------------------
There are two areas where function reordering can impact performance: boot time latency, and run time performance.

* Boot time latency
This implementation of finer grained KASLR impacts the boot time of the kernel in several places. It requires additional parsing of the kernel ELF file to obtain the section headers of the sections to be randomized. It calls the random number generator for each section to be randomized to determine that section's new memory location. It copies the decompressed kernel into a new area of memory to avoid corruption when laying out the newly randomized sections. It increases the number of relocations the kernel has to perform at boot time vs. standard KASLR, and it also requires a lookup on each address that needs to be relocated to see if it was in a randomized section and needs to be adjusted by a new offset. Finally, it re-sorts a few data tables that are required to be sorted by address.

Booting a test VM on a modern, well appointed system showed an increase in latency of approximately 1 second.

* Run time
The performance impact at run-time of function reordering varies by workload. Using kcbench, a kernel compilation benchmark, the performance of a kernel build with finer grained KASLR was about 1% slower than a kernel with standard KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied results. Some workloads performed significantly worse under FGKASLR, while others stayed the same or were mysteriously better. In general, it will depend on the code flow whether or not finer grained KASLR will impact your workload, and how the underlying code was designed. Because the layout changes per boot, each time a system is rebooted the performance of a workload may change.

Future work could identify hot areas that may not be randomized and either leave them in the .text section or group them together into a single section that may be randomized. If grouping things together helps, one other thing to consider is that if we could identify text blobs that should be grouped together to benefit a particular code flow, it could be interesting to explore whether this security feature could be also be used as a performance feature if you are interested in optimizing your kernel layout for a particular workload at boot time. Optimizing function layout for a particular workload has been researched and proven effective - for more information read the Facebook paper "Optimizing Function Placement for Large-Scale Data-Center Applications" (see references section below).

Image Size
----------
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. With a standard distro config, the resulting vmlinux was increased by about 3%. The compressed image is also increased due to the header files, as well as the extra relocations that must be added. You can expect fgkaslr to increase the size of the compressed image by about 15%.

Memory Usage
------------
fgkaslr increases the amount of heap that is required at boot time, although this extra memory is released when the kernel has finished decompression. As a result, it may not be appropriate to use this feature on systems without much memory.

Building
--------
To enable fine grained KASLR, you need to have the following config options set (including all the ones you would use to build normal KASLR)

CONFIG_FG_KASLR=y

In addition, fgkaslr is only supported for the X86_64 architecture.

Modules
-------
Modules are randomized similarly to the rest of the kernel by shuffling the sections at load time prior to moving them into memory. The module must also have been build with the -ffunction-sections compiler option.

Although fgkaslr for the kernel is only supported for the X86_64 architecture, it is possible to use fgkaslr with modules on other architectures. To enable this feature, select

CONFIG_MODULE_FG_KASLR=y

This option is selected automatically for X86_64 when CONFIG_FG_KASLR is set.

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables fgkaslr. It is also possible to disable fgkaslr separately by booting with fgkaslr=off on the commandline.

References
----------
There are a lot of academic papers which explore finer grained ASLR. This paper in particular contributed the most to my implementation design as well as my overall understanding of the problem space:

Selfrando: Securing the Tor Browser against De-anonymization Exploits, M. Conti, S. Crane, T. Frassetto, et al.

For more information on how function layout impacts performance, see:

Optimizing Function Placement for Large-Scale Data-Center Applications, G. Ottoni, B. Maher

Kees Cook (2):
x86/boot: Allow a "silent" kaslr random byte fetch x86/boot/compressed: Avoid duplicate malloc() implementations

Kristen Carlson Accardi (8):
objtool: Do not assume order of parent/child functions
x86: tools/relocs: Support >64K section headers
x86: Makefile: Add build and config option for CONFIG_FG_KASLR
x86: Make sure _etext includes function sections x86/tools: Add relative relocs for randomized functions
x86: Add support for function granular KASLR
kallsyms: Hide layout
module: Reorder functions

 .../admin-guide/kernel-parameters.txt         |   7 +
 Documentation/security/fgkaslr.rst            | 172 ++++
 Documentation/security/index.rst              |   1 +
 Makefile                                      |   6 +-
 arch/x86/Kconfig                              |   4 +
 arch/x86/Makefile                             |   5 +
 arch/x86/boot/compressed/Makefile             |   9 +-
 arch/x86/boot/compressed/fgkaslr.c            | 811 ++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c              |   4 -
 arch/x86/boot/compressed/misc.c               | 157 +++-
 arch/x86/boot/compressed/misc.h               |  30 +
 arch/x86/boot/compressed/utils.c              |  11 +
 arch/x86/boot/compressed/vmlinux.symbols      |  17 +
 arch/x86/include/asm/boot.h                   |  15 +-
 arch/x86/kernel/vmlinux.lds.S                 |  17 +-
 arch/x86/lib/kaslr.c                          |  18 +-
 arch/x86/tools/relocs.c                       | 143 ++-
 arch/x86/tools/relocs.h                       |   4 +-
 arch/x86/tools/relocs_common.c                |  15 +-
 include/asm-generic/vmlinux.lds.h             |  18 +-
 include/linux/decompress/mm.h                 |  12 +-
 include/uapi/linux/elf.h                      |   1 +
 init/Kconfig                                  |  26 +
 kernel/kallsyms.c                             | 163 +++-
 kernel/module.c                               |  81 ++
 tools/objtool/elf.c                           |   8 +-
 26 files changed, 1670 insertions(+), 85 deletions(-)
 create mode 100644 Documentation/security/fgkaslr.rst
 create mode 100644 arch/x86/boot/compressed/fgkaslr.c
 create mode 100644 arch/x86/boot/compressed/utils.c
 create mode 100644 arch/x86/boot/compressed/vmlinux.symbols

base-commit: 11ba468877bb23f28956a35e896356252d63c983

Signature · 1 line

2.20.1

Quoted 415 lines · Kristen Carlson Accardi

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
-----------------------------------------------------------------
----

This patch set is an implementation of finer grained kernel address space
randomization. It rearranges your kernel code at load time on a per-function level granularity, with only around a second added to
boot time.

Changes in v4:
-------------
* dropped the patch to split out change to STATIC definition in x86/boot/compressed/misc.c and replaced with a patch authored by Kees Cook to avoid the duplicate malloc definitions
* Added a section to Documentation/admin-guide/kernel- parameters.txt
to document the fgkaslr boot option.
* redesigned the patch to hide the new layout when reading /proc/kallsyms. The previous implementation utilized a
dynamically
allocated linked list to display the kernel and module symbols in alphabetical order. The new implementation uses a randomly shuffled index array to display the kernel and module symbols in a random order.

Changes in v3:
-------------
* Makefile changes to accommodate CONFIG_LD_DEAD_CODE_DATA_ELIMINATION
* removal of extraneous ALIGN_PAGE from _etext changes
* changed variable names in x86/tools/relocs to be less confusing
* split out change to STATIC definition in x86/boot/compressed/misc.c
* Updates to Documentation to make it more clear what is preserved in .text
* much more detailed commit message for function granular KASLR patch
* minor tweaks and changes that make for more readable code
* this cover letter updated slightly to add additional details

Changes in v2:
--------------
* Fix to address i386 build failure
* Allow module reordering patch to be configured separately so that arm (or other non-x86_64 arches) can take advantage of module
function
reordering. This support has not be tested by me, but smoke
tested by
Ard Biesheuvel <[email protected]> on arm.
* Fix build issue when building on arm as reported by Ard Biesheuvel <[email protected]>

Patches to objtool are included because they are dependencies for this
patchset, however they have been submitted by their maintainer separately.

Background
----------
KASLR was merged into the kernel with the objective of increasing the
difficulty of code reuse attacks. Code reuse attacks reused existing code
snippets to get around existing memory protections. They exploit software bugs
which expose addresses of useful code snippets to control the flow of
execution for their own nefarious purposes. KASLR moves the entire kernel
code text as a unit at boot time in order to make addresses less predictable.
The order of the code within the segment is unchanged - only the base address
is shifted. There are a few shortcomings to this algorithm.

1. Low Entropy - there are only so many locations the kernel can fit in. This
means an attacker could guess without too much trouble.
2. Knowledge of a single address can reveal the offset of the base address,
exposing all other locations for a published/known kernel image.
3. Info leaks abound.

Finer grained ASLR has been proposed as a way to make ASLR more resistant
to info leaks. It is not a new concept at all, and there are many variations
possible. Function reordering is an implementation of finer grained ASLR
which randomizes the layout of an address space on a function level granularity. We use the term "fgkaslr" in this document to refer to the
technique of function reordering when used with KASLR, as well as finer grained
KASLR in general.

Proposed Improvement
--------------------
This patch set proposes adding function reordering on top of the existing
KASLR base address randomization. The over-arching objective is incremental
improvement over what we already have. It is designed to work in combination
with the existing solution. The implementation is really pretty simple, and
there are 2 main area where changes occur:

* Build time

GCC has had an option to place functions into individual .text sections for
many years now. This option can be used to implement function reordering at
load time. The final compiled vmlinux retains all the section headers, which
can be used to help find the address ranges of each function. Using this
information and an expanded table of relocation addresses, individual text
sections can be suffled immediately after decompression. Some data tables
inside the kernel that have assumptions about order require re- sorting
after being updated when applying relocations. In order to modify these tables,
a few key symbols are excluded from the objcopy symbol stripping process for
use after shuffling the text segments.

Some highlights from the build time changes to look for:

The top level kernel Makefile was modified to add the gcc flag if it
is supported. Currently, I am applying this flag to everything it is
possible to randomize. Anything that is written in C and not present in a
special input section is randomized. The final binary segment 0 retains a
consolidated .text section, as well as all the individual .text.* sections.
Future work could turn off this flags for selected files or even entire
subsystems, although obviously at the cost of security.

The relocs tool is updated to add relative relocations. This information
previously wasn't included because it wasn't necessary when moving the
entire .text segment as a unit.

A new file was created to contain a list of symbols that objcopy should
keep. We use those symbols at load time as described below.

* Load time

The boot kernel was modified to parse the vmlinux elf file after decompression to check for our interesting symbols that we kept, and to
look for any .text.* sections to randomize. The consolidated .text section
is skipped and not moved. The sections are shuffled randomly, and copied
into memory following the .text section in a new random order. The existing
code which updated relocation addresses was modified to account for not just a fixed delta from the load address, but the offset that the function
section was moved to. This requires inspection of each address to see if
it was impacted by a randomization. We use a bsearch to make this less
horrible on performance. Any tables that need to be modified with new
addresses or resorted are updated using the symbol addresses parsed from the
elf symbol table.

In order to hide our new layout, symbols reported through /proc/kallsyms
will be displayed in a random order.

Security Considerations
-----------------------
The objective of this patch set is to improve a technology that is already
merged into the kernel (KASLR). This code will not prevent all attacks,
but should instead be considered as one of several tools that can be used.
In particular, this code is meant to make KASLR more effective in the presence
of info leaks.

How much entropy we are adding to the existing entropy of standard KASLR will
depend on a few variables. Firstly and most obviously, the number of functions
that are randomized matters. This implementation keeps the existing .text
section for code that cannot be randomized - for example, because it was
assembly code. The less sections to randomize, the less entropy. In addition,
due to alignment (16 bytes for x86_64), the number of bits in a address that
the attacker needs to guess is reduced, as the lower bits are identical.

Performance Impact
------------------
There are two areas where function reordering can impact
performance: boot
time latency, and run time performance.

* Boot time latency
This implementation of finer grained KASLR impacts the boot time of the kernel
in several places. It requires additional parsing of the kernel ELF file to
obtain the section headers of the sections to be randomized. It calls the
random number generator for each section to be randomized to determine that
section's new memory location. It copies the decompressed kernel into a new
area of memory to avoid corruption when laying out the newly randomized
sections. It increases the number of relocations the kernel has to perform at
boot time vs. standard KASLR, and it also requires a lookup on each address
that needs to be relocated to see if it was in a randomized section and needs
to be adjusted by a new offset. Finally, it re-sorts a few data tables that
are required to be sorted by address.

Booting a test VM on a modern, well appointed system showed an increase in
latency of approximately 1 second.

* Run time
The performance impact at run-time of function reordering varies by workload.
Using kcbench, a kernel compilation benchmark, the performance of a kernel
build with finer grained KASLR was about 1% slower than a kernel with standard
KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied
results. Some workloads performed significantly worse under FGKASLR, while
others stayed the same or were mysteriously better. In general, it will
depend on the code flow whether or not finer grained KASLR will impact
your workload, and how the underlying code was designed. Because the layout
changes per boot, each time a system is rebooted the performance of a workload
may change.

Future work could identify hot areas that may not be randomized and either
leave them in the .text section or group them together into a single section
that may be randomized. If grouping things together helps, one other thing to
consider is that if we could identify text blobs that should be grouped together
to benefit a particular code flow, it could be interesting to explore
whether this security feature could be also be used as a performance
feature if you are interested in optimizing your kernel layout for a
particular workload at boot time. Optimizing function layout for a particular
workload has been researched and proven effective - for more information
read the Facebook paper "Optimizing Function Placement for Large- Scale
Data-Center Applications" (see references section below).

Image Size
----------
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. With a standard distro config, the resulting vmlinux was increased by
about 3%. The compressed image is also increased due to the header files,
as well as the extra relocations that must be added. You can expect fgkaslr
to increase the size of the compressed image by about 15%.

Memory Usage
------------
fgkaslr increases the amount of heap that is required at boot time, although this extra memory is released when the kernel has finished decompression. As a result, it may not be appropriate to use this feature on
systems without much memory.

Building
--------
To enable fine grained KASLR, you need to have the following config options
set (including all the ones you would use to build normal KASLR)

CONFIG_FG_KASLR=y

In addition, fgkaslr is only supported for the X86_64 architecture.

Modules
-------
Modules are randomized similarly to the rest of the kernel by shuffling
the sections at load time prior to moving them into memory. The module must
also have been build with the -ffunction-sections compiler option.

Although fgkaslr for the kernel is only supported for the X86_64 architecture,
it is possible to use fgkaslr with modules on other architectures. To enable
this feature, select

CONFIG_MODULE_FG_KASLR=y

This option is selected automatically for X86_64 when CONFIG_FG_KASLR is set.

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables
fgkaslr. It is also possible to disable fgkaslr separately by booting with
fgkaslr=off on the commandline.

References
----------
There are a lot of academic papers which explore finer grained ASLR.
This paper in particular contributed the most to my implementation design
as well as my overall understanding of the problem space:

Selfrando: Securing the Tor Browser against De-anonymization Exploits,
M. Conti, S. Crane, T. Frassetto, et al.

For more information on how function layout impacts performance, see:

Optimizing Function Placement for Large-Scale Data-Center Applications,
G. Ottoni, B. Maher

Kees Cook (2):
x86/boot: Allow a "silent" kaslr random byte fetch x86/boot/compressed: Avoid duplicate malloc() implementations

Kristen Carlson Accardi (8):
objtool: Do not assume order of parent/child functions
x86: tools/relocs: Support >64K section headers
x86: Makefile: Add build and config option for CONFIG_FG_KASLR
x86: Make sure _etext includes function sections x86/tools: Add relative relocs for randomized functions
x86: Add support for function granular KASLR
kallsyms: Hide layout
module: Reorder functions

 .../admin-guide/kernel-parameters.txt         |   7 +
 Documentation/security/fgkaslr.rst            | 172 ++++
 Documentation/security/index.rst              |   1 +
 Makefile                                      |   6 +-
 arch/x86/Kconfig                              |   4 +
 arch/x86/Makefile                             |   5 +
 arch/x86/boot/compressed/Makefile             |   9 +-
 arch/x86/boot/compressed/fgkaslr.c            | 811
++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c              |   4 -
 arch/x86/boot/compressed/misc.c               | 157 +++-
 arch/x86/boot/compressed/misc.h               |  30 +
 arch/x86/boot/compressed/utils.c              |  11 +
 arch/x86/boot/compressed/vmlinux.symbols      |  17 +
 arch/x86/include/asm/boot.h                   |  15 +-
 arch/x86/kernel/vmlinux.lds.S                 |  17 +-
 arch/x86/lib/kaslr.c                          |  18 +-
 arch/x86/tools/relocs.c                       | 143 ++-
 arch/x86/tools/relocs.h                       |   4 +-
 arch/x86/tools/relocs_common.c                |  15 +-
 include/asm-generic/vmlinux.lds.h             |  18 +-
 include/linux/decompress/mm.h                 |  12 +-
 include/uapi/linux/elf.h                      |   1 +
 init/Kconfig                                  |  26 +
 kernel/kallsyms.c                             | 163 +++-
 kernel/module.c                               |  81 ++
 tools/objtool/elf.c                           |   8 +-
 26 files changed, 1670 insertions(+), 85 deletions(-)
 create mode 100644 Documentation/security/fgkaslr.rst
 create mode 100644 arch/x86/boot/compressed/fgkaslr.c
 create mode 100644 arch/x86/boot/compressed/utils.c
 create mode 100644 arch/x86/boot/compressed/vmlinux.symbols

Quoted 4 lines

base-commit: 11ba468877bb23f28956a35e896356252d63c983

Signature · 1 line

2.20.1

Apologies in advance if this has already been discussed elsewhere, but I
did finally get around to testing the patchset against the livepatching
kselftests.

The livepatching kselftests fail as all livepatches stall their transitions. It appears that reliable (ORC) stack unwinding is broken
when fgkaslr is enabled.

Relevant config options:

CONFIG_ARCH_HAS_FG_KASLR=y
CONFIG_ARCH_STACKWALK=y
CONFIG_FG_KASLR=y
CONFIG_HAVE_LIVEPATCH=y
CONFIG_HAVE_RELIABLE_STACKTRACE=y
CONFIG_LIVEPATCH=y
CONFIG_MODULE_FG_KASLR=y
CONFIG_TEST_LIVEPATCH=m
CONFIG_UNWINDER_ORC=y

The livepatch transitions are stuck along this call path:

klp_check_stack

    stack_trace_save_tsk_reliable
      arch_stack_walk_reliable
  
          /* Check for stack corruption */
          if (unwind_error(&state))
                  return -EINVAL;

where the unwinder error is set by unwind_next_frame():

arch/x86/kernel/unwind_orc.c
bool unwind_next_frame(struct unwind_state *state)

sometimes here:

  	/* End-of-stack check for kernel threads: */
  	if (orc->sp_reg == ORC_REG_UNDEFINED) {
  		if (!orc->end)
  			goto err;
  
  		goto the_end;
  	}

or here:

/* Prevent a recursive loop due to bad ORC data:
*/

if (state->stack_info.type == prev_type
&&

on_stack(&state->stack_info, (void *)state->sp,
sizeof(long))
&&
state->sp <= prev_sp)
{

orc_warn_current("stack going in the wrong direction?
at %pB\n",
(void
*)orig_ip);

goto
err;

  	}

(and probably other places the ORC unwinder gets confused.)

It also manifests itself in other, more visible ways. For example, a kernel module that calls dump_stack() in its init function or even /proc/<pid>/stack:

(fgkaslr on)
------------

Call Trace:
 ? dump_stack+0x57/0x73
 ? 0xffffffffc0850000
 ? mymodule_init+0xa/0x1000 [dumpstack]
 ? do_one_initcall+0x46/0x1f0
 ? free_unref_page_commit+0x91/0x100
 ? _cond_resched+0x15/0x30
 ? kmem_cache_alloc_trace+0x14b/0x210
 ? do_init_module+0x5a/0x220
 ? load_module+0x1912/0x1b20
 ? __do_sys_finit_module+0xa8/0x110
 ? __do_sys_finit_module+0xa8/0x110
 ? do_syscall_64+0x47/0x80
 ? entry_SYSCALL_64_after_hwframe+0x44/0xa9

% sudo cat /proc/$$/stack

[<0>] do_wait+0x1c3/0x230
[<0>] kernel_wait4+0xa6/0x140

fgkaslr=off
-----------

Call Trace:
 dump_stack+0x57/0x73
 ? 0xffffffffc04f2000
 mymodule_init+0xa/0x1000 [readonly]
 do_one_initcall+0x46/0x1f0
 ? free_unref_page_commit+0x91/0x100
 ? _cond_resched+0x15/0x30
 ? kmem_cache_alloc_trace+0x14b/0x210
 do_init_module+0x5a/0x220
 load_module+0x1912/0x1b20
 ? __do_sys_finit_module+0xa8/0x110
 __do_sys_finit_module+0xa8/0x110
 do_syscall_64+0x47/0x80
 entry_SYSCALL_64_after_hwframe+0x44/0xa9

% sudo cat /proc/$$/stack

[<0>] do_wait+0x1c3/0x230
[<0>] kernel_wait4+0xa6/0x140
[<0>] __do_sys_wait4+0x83/0x90
[<0>] do_syscall_64+0x47/0x80
[<0>] entry_SYSCALL_64_after_hwframe+0x44/0xa9

I would think fixing and verifying these latter cases would be easier than
chasing livepatch transitions (but would still probably fix klp case, too).
Perhaps Josh or someone has other ORC unwinder tests that could be used?

-- Joe

Thanks for testing. Yes, Josh and I have been discussing the orc_unwind issues. I've root caused one issue already, in that objtool places an orc_unwind_ip address just outside the section, so my algorithm fails to relocate this address. There are other issues as well that I still haven't root caused. I'll be addressing this in v5 and plan to have something that passes livepatch testing with that version.

Quoted 10 lines · Kristen Carlson Accardi

Thanks for testing. Yes, Josh and I have been discussing the orc_unwind
issues. I've root caused one issue already, in that objtool places an
orc_unwind_ip address just outside the section, so my algorithm fails
to relocate this address. There are other issues as well that I still
haven't root caused. I'll be addressing this in v5 and plan to have something that passes livepatch testing with that version.

FWIW, I'm okay with seeing fgkaslr be developed progressively. Getting
it working with !livepatching would be fine as a first step. There's value in getting the general behavior landed, and then continuing to improve it.

Quoted 415 lines · Kristen Carlson Accardi

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
-----------------------------------------------------------------
----

This patch set is an implementation of finer grained kernel address space
randomization. It rearranges your kernel code at load time on a per-function level granularity, with only around a second added to
boot time.

Changes in v4:
-------------
* dropped the patch to split out change to STATIC definition in x86/boot/compressed/misc.c and replaced with a patch authored by Kees Cook to avoid the duplicate malloc definitions
* Added a section to Documentation/admin-guide/kernel- parameters.txt
to document the fgkaslr boot option.
* redesigned the patch to hide the new layout when reading /proc/kallsyms. The previous implementation utilized a
dynamically
allocated linked list to display the kernel and module symbols in alphabetical order. The new implementation uses a randomly shuffled index array to display the kernel and module symbols in a random order.

Changes in v3:
-------------
* Makefile changes to accommodate CONFIG_LD_DEAD_CODE_DATA_ELIMINATION
* removal of extraneous ALIGN_PAGE from _etext changes
* changed variable names in x86/tools/relocs to be less confusing
* split out change to STATIC definition in x86/boot/compressed/misc.c
* Updates to Documentation to make it more clear what is preserved in .text
* much more detailed commit message for function granular KASLR patch
* minor tweaks and changes that make for more readable code
* this cover letter updated slightly to add additional details

Changes in v2:
--------------
* Fix to address i386 build failure
* Allow module reordering patch to be configured separately so that arm (or other non-x86_64 arches) can take advantage of module
function
reordering. This support has not be tested by me, but smoke
tested by
Ard Biesheuvel <[email protected]> on arm.
* Fix build issue when building on arm as reported by Ard Biesheuvel <[email protected]>

Patches to objtool are included because they are dependencies for this
patchset, however they have been submitted by their maintainer separately.

Background
----------
KASLR was merged into the kernel with the objective of increasing the
difficulty of code reuse attacks. Code reuse attacks reused existing code
snippets to get around existing memory protections. They exploit software bugs
which expose addresses of useful code snippets to control the flow of
execution for their own nefarious purposes. KASLR moves the entire kernel
code text as a unit at boot time in order to make addresses less predictable.
The order of the code within the segment is unchanged - only the base address
is shifted. There are a few shortcomings to this algorithm.

1. Low Entropy - there are only so many locations the kernel can fit in. This
means an attacker could guess without too much trouble.
2. Knowledge of a single address can reveal the offset of the base address,
exposing all other locations for a published/known kernel image.
3. Info leaks abound.

Finer grained ASLR has been proposed as a way to make ASLR more resistant
to info leaks. It is not a new concept at all, and there are many variations
possible. Function reordering is an implementation of finer grained ASLR
which randomizes the layout of an address space on a function level granularity. We use the term "fgkaslr" in this document to refer to the
technique of function reordering when used with KASLR, as well as finer grained
KASLR in general.

Proposed Improvement
--------------------
This patch set proposes adding function reordering on top of the existing
KASLR base address randomization. The over-arching objective is incremental
improvement over what we already have. It is designed to work in combination
with the existing solution. The implementation is really pretty simple, and
there are 2 main area where changes occur:

* Build time

GCC has had an option to place functions into individual .text sections for
many years now. This option can be used to implement function reordering at
load time. The final compiled vmlinux retains all the section headers, which
can be used to help find the address ranges of each function. Using this
information and an expanded table of relocation addresses, individual text
sections can be suffled immediately after decompression. Some data tables
inside the kernel that have assumptions about order require re- sorting
after being updated when applying relocations. In order to modify these tables,
a few key symbols are excluded from the objcopy symbol stripping process for
use after shuffling the text segments.

Some highlights from the build time changes to look for:

The top level kernel Makefile was modified to add the gcc flag if it
is supported. Currently, I am applying this flag to everything it is
possible to randomize. Anything that is written in C and not present in a
special input section is randomized. The final binary segment 0 retains a
consolidated .text section, as well as all the individual .text.* sections.
Future work could turn off this flags for selected files or even entire
subsystems, although obviously at the cost of security.

The relocs tool is updated to add relative relocations. This information
previously wasn't included because it wasn't necessary when moving the
entire .text segment as a unit.

A new file was created to contain a list of symbols that objcopy should
keep. We use those symbols at load time as described below.

* Load time

The boot kernel was modified to parse the vmlinux elf file after decompression to check for our interesting symbols that we kept, and to
look for any .text.* sections to randomize. The consolidated .text section
is skipped and not moved. The sections are shuffled randomly, and copied
into memory following the .text section in a new random order. The existing
code which updated relocation addresses was modified to account for not just a fixed delta from the load address, but the offset that the function
section was moved to. This requires inspection of each address to see if
it was impacted by a randomization. We use a bsearch to make this less
horrible on performance. Any tables that need to be modified with new
addresses or resorted are updated using the symbol addresses parsed from the
elf symbol table.

In order to hide our new layout, symbols reported through /proc/kallsyms
will be displayed in a random order.

Security Considerations
-----------------------
The objective of this patch set is to improve a technology that is already
merged into the kernel (KASLR). This code will not prevent all attacks,
but should instead be considered as one of several tools that can be used.
In particular, this code is meant to make KASLR more effective in the presence
of info leaks.

How much entropy we are adding to the existing entropy of standard KASLR will
depend on a few variables. Firstly and most obviously, the number of functions
that are randomized matters. This implementation keeps the existing .text
section for code that cannot be randomized - for example, because it was
assembly code. The less sections to randomize, the less entropy. In addition,
due to alignment (16 bytes for x86_64), the number of bits in a address that
the attacker needs to guess is reduced, as the lower bits are identical.

Performance Impact
------------------
There are two areas where function reordering can impact
performance: boot
time latency, and run time performance.

* Boot time latency
This implementation of finer grained KASLR impacts the boot time of the kernel
in several places. It requires additional parsing of the kernel ELF file to
obtain the section headers of the sections to be randomized. It calls the
random number generator for each section to be randomized to determine that
section's new memory location. It copies the decompressed kernel into a new
area of memory to avoid corruption when laying out the newly randomized
sections. It increases the number of relocations the kernel has to perform at
boot time vs. standard KASLR, and it also requires a lookup on each address
that needs to be relocated to see if it was in a randomized section and needs
to be adjusted by a new offset. Finally, it re-sorts a few data tables that
are required to be sorted by address.

Booting a test VM on a modern, well appointed system showed an increase in
latency of approximately 1 second.

* Run time
The performance impact at run-time of function reordering varies by workload.
Using kcbench, a kernel compilation benchmark, the performance of a kernel
build with finer grained KASLR was about 1% slower than a kernel with standard
KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied
results. Some workloads performed significantly worse under FGKASLR, while
others stayed the same or were mysteriously better. In general, it will
depend on the code flow whether or not finer grained KASLR will impact
your workload, and how the underlying code was designed. Because the layout
changes per boot, each time a system is rebooted the performance of a workload
may change.

Future work could identify hot areas that may not be randomized and either
leave them in the .text section or group them together into a single section
that may be randomized. If grouping things together helps, one other thing to
consider is that if we could identify text blobs that should be grouped together
to benefit a particular code flow, it could be interesting to explore
whether this security feature could be also be used as a performance
feature if you are interested in optimizing your kernel layout for a
particular workload at boot time. Optimizing function layout for a particular
workload has been researched and proven effective - for more information
read the Facebook paper "Optimizing Function Placement for Large- Scale
Data-Center Applications" (see references section below).

Image Size
----------
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. With a standard distro config, the resulting vmlinux was increased by
about 3%. The compressed image is also increased due to the header files,
as well as the extra relocations that must be added. You can expect fgkaslr
to increase the size of the compressed image by about 15%.

Memory Usage
------------
fgkaslr increases the amount of heap that is required at boot time, although this extra memory is released when the kernel has finished decompression. As a result, it may not be appropriate to use this feature on
systems without much memory.

Building
--------
To enable fine grained KASLR, you need to have the following config options
set (including all the ones you would use to build normal KASLR)

CONFIG_FG_KASLR=y

In addition, fgkaslr is only supported for the X86_64 architecture.

Modules
-------
Modules are randomized similarly to the rest of the kernel by shuffling
the sections at load time prior to moving them into memory. The module must
also have been build with the -ffunction-sections compiler option.

Although fgkaslr for the kernel is only supported for the X86_64 architecture,
it is possible to use fgkaslr with modules on other architectures. To enable
this feature, select

CONFIG_MODULE_FG_KASLR=y

This option is selected automatically for X86_64 when CONFIG_FG_KASLR is set.

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables
fgkaslr. It is also possible to disable fgkaslr separately by booting with
fgkaslr=off on the commandline.

References
----------
There are a lot of academic papers which explore finer grained ASLR.
This paper in particular contributed the most to my implementation design
as well as my overall understanding of the problem space:

Selfrando: Securing the Tor Browser against De-anonymization Exploits,
M. Conti, S. Crane, T. Frassetto, et al.

For more information on how function layout impacts performance, see:

Optimizing Function Placement for Large-Scale Data-Center Applications,
G. Ottoni, B. Maher

Kees Cook (2):
x86/boot: Allow a "silent" kaslr random byte fetch x86/boot/compressed: Avoid duplicate malloc() implementations

Kristen Carlson Accardi (8):
objtool: Do not assume order of parent/child functions
x86: tools/relocs: Support >64K section headers
x86: Makefile: Add build and config option for CONFIG_FG_KASLR
x86: Make sure _etext includes function sections x86/tools: Add relative relocs for randomized functions
x86: Add support for function granular KASLR
kallsyms: Hide layout
module: Reorder functions

 .../admin-guide/kernel-parameters.txt         |   7 +
 Documentation/security/fgkaslr.rst            | 172 ++++
 Documentation/security/index.rst              |   1 +
 Makefile                                      |   6 +-
 arch/x86/Kconfig                              |   4 +
 arch/x86/Makefile                             |   5 +
 arch/x86/boot/compressed/Makefile             |   9 +-
 arch/x86/boot/compressed/fgkaslr.c            | 811
++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c              |   4 -
 arch/x86/boot/compressed/misc.c               | 157 +++-
 arch/x86/boot/compressed/misc.h               |  30 +
 arch/x86/boot/compressed/utils.c              |  11 +
 arch/x86/boot/compressed/vmlinux.symbols      |  17 +
 arch/x86/include/asm/boot.h                   |  15 +-
 arch/x86/kernel/vmlinux.lds.S                 |  17 +-
 arch/x86/lib/kaslr.c                          |  18 +-
 arch/x86/tools/relocs.c                       | 143 ++-
 arch/x86/tools/relocs.h                       |   4 +-
 arch/x86/tools/relocs_common.c                |  15 +-
 include/asm-generic/vmlinux.lds.h             |  18 +-
 include/linux/decompress/mm.h                 |  12 +-
 include/uapi/linux/elf.h                      |   1 +
 init/Kconfig                                  |  26 +
 kernel/kallsyms.c                             | 163 +++-
 kernel/module.c                               |  81 ++
 tools/objtool/elf.c                           |   8 +-
 26 files changed, 1670 insertions(+), 85 deletions(-)
 create mode 100644 Documentation/security/fgkaslr.rst
 create mode 100644 arch/x86/boot/compressed/fgkaslr.c
 create mode 100644 arch/x86/boot/compressed/utils.c
 create mode 100644 arch/x86/boot/compressed/vmlinux.symbols

Quoted 4 lines

base-commit: 11ba468877bb23f28956a35e896356252d63c983

Signature · 1 line

2.20.1

Apologies in advance if this has already been discussed elsewhere, but I
did finally get around to testing the patchset against the livepatching
kselftests.

The livepatching kselftests fail as all livepatches stall their transitions. It appears that reliable (ORC) stack unwinding is broken
when fgkaslr is enabled.

Relevant config options:

CONFIG_ARCH_HAS_FG_KASLR=y
CONFIG_ARCH_STACKWALK=y
CONFIG_FG_KASLR=y
CONFIG_HAVE_LIVEPATCH=y
CONFIG_HAVE_RELIABLE_STACKTRACE=y
CONFIG_LIVEPATCH=y
CONFIG_MODULE_FG_KASLR=y
CONFIG_TEST_LIVEPATCH=m
CONFIG_UNWINDER_ORC=y

The livepatch transitions are stuck along this call path:

klp_check_stack

    stack_trace_save_tsk_reliable
      arch_stack_walk_reliable
  
          /* Check for stack corruption */
          if (unwind_error(&state))
                  return -EINVAL;

where the unwinder error is set by unwind_next_frame():

arch/x86/kernel/unwind_orc.c
bool unwind_next_frame(struct unwind_state *state)

sometimes here:

  	/* End-of-stack check for kernel threads: */
  	if (orc->sp_reg == ORC_REG_UNDEFINED) {
  		if (!orc->end)
  			goto err;
  
  		goto the_end;
  	}

or here:

/* Prevent a recursive loop due to bad ORC data:
*/

if (state->stack_info.type == prev_type
&&

on_stack(&state->stack_info, (void *)state->sp,
sizeof(long))
&&
state->sp <= prev_sp)
{

orc_warn_current("stack going in the wrong direction?
at %pB\n",
(void
*)orig_ip);

goto
err;

  	}

(and probably other places the ORC unwinder gets confused.)

It also manifests itself in other, more visible ways. For example, a kernel module that calls dump_stack() in its init function or even /proc/<pid>/stack:

(fgkaslr on)
------------

Call Trace:
 ? dump_stack+0x57/0x73
 ? 0xffffffffc0850000
 ? mymodule_init+0xa/0x1000 [dumpstack]
 ? do_one_initcall+0x46/0x1f0
 ? free_unref_page_commit+0x91/0x100
 ? _cond_resched+0x15/0x30
 ? kmem_cache_alloc_trace+0x14b/0x210
 ? do_init_module+0x5a/0x220
 ? load_module+0x1912/0x1b20
 ? __do_sys_finit_module+0xa8/0x110
 ? __do_sys_finit_module+0xa8/0x110
 ? do_syscall_64+0x47/0x80
 ? entry_SYSCALL_64_after_hwframe+0x44/0xa9

% sudo cat /proc/$$/stack

[<0>] do_wait+0x1c3/0x230
[<0>] kernel_wait4+0xa6/0x140

fgkaslr=off
-----------

Call Trace:
 dump_stack+0x57/0x73
 ? 0xffffffffc04f2000
 mymodule_init+0xa/0x1000 [readonly]
 do_one_initcall+0x46/0x1f0
 ? free_unref_page_commit+0x91/0x100
 ? _cond_resched+0x15/0x30
 ? kmem_cache_alloc_trace+0x14b/0x210
 do_init_module+0x5a/0x220
 load_module+0x1912/0x1b20
 ? __do_sys_finit_module+0xa8/0x110
 __do_sys_finit_module+0xa8/0x110
 do_syscall_64+0x47/0x80
 entry_SYSCALL_64_after_hwframe+0x44/0xa9

% sudo cat /proc/$$/stack

[<0>] do_wait+0x1c3/0x230
[<0>] kernel_wait4+0xa6/0x140
[<0>] __do_sys_wait4+0x83/0x90
[<0>] do_syscall_64+0x47/0x80
[<0>] entry_SYSCALL_64_after_hwframe+0x44/0xa9

I would think fixing and verifying these latter cases would be easier than
chasing livepatch transitions (but would still probably fix klp case, too).
Perhaps Josh or someone has other ORC unwinder tests that could be used?

-- Joe

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
---------------------------------------------------------------------

This patch set is an implementation of finer grained kernel address space randomization. It rearranges your kernel code at load time
on a per-function level granularity, with only around a second added to boot time.

In order to hide our new layout, symbols reported through /proc/kallsyms will be displayed in a random order.

Performance Impact
------------------

* Run time
The performance impact at run-time of function reordering varies by workload. Using kcbench, a kernel compilation benchmark, the performance of a kernel build with finer grained KASLR was about 1% slower than a kernel with standard KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied results. Some workloads performed significantly worse under FGKASLR, while others stayed the same or were mysteriously better. In general, it will depend on the code flow whether or not finer grained KASLR will impact your workload, and how the underlying code was designed. Because the layout changes per boot, each time a system is rebooted the performance of a workload may change.

Future work could identify hot areas that may not be randomized and either leave them in the .text section or group them together into a single section that may be randomized. If grouping things together helps, one other thing to consider is that if we could identify text blobs that should be grouped together to benefit a particular code flow, it could be interesting to explore whether this security feature could be also be used as a performance feature if you are interested in optimizing your kernel layout for a particular workload at boot time. Optimizing function layout for a particular workload has been researched and proven effective - for more information read the Facebook paper "Optimizing Function Placement for Large-Scale Data-Center Applications" (see references section below).

Image Size
----------
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. With a standard distro config, the resulting vmlinux was increased by about 3%. The compressed image is also increased due to the header files, as well as the extra relocations that must be added. You can expect fgkaslr to increase the size of the compressed image by about 15%.

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables fgkaslr. It is also possible to disable fgkaslr separately by booting with fgkaslr=off on the commandline.

 arch/x86/boot/compressed/Makefile             |   9 +-
 arch/x86/boot/compressed/fgkaslr.c            | 811 ++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c              |   4 -
 arch/x86/boot/compressed/misc.c               | 157 +++-
 arch/x86/boot/compressed/misc.h               |  30 +
 arch/x86/boot/compressed/utils.c              |  11 +
 arch/x86/boot/compressed/vmlinux.symbols      |  17 +
 arch/x86/include/asm/boot.h                   |  15 +-
 arch/x86/kernel/vmlinux.lds.S                 |  17 +-
 arch/x86/lib/kaslr.c                          |  18 +-
 arch/x86/tools/relocs.c                       | 143 ++-
 arch/x86/tools/relocs.h                       |   4 +-
 arch/x86/tools/relocs_common.c                |  15 +-
 include/asm-generic/vmlinux.lds.h             |  18 +-
 include/linux/decompress/mm.h                 |  12 +-
 include/uapi/linux/elf.h                      |   1 +
 init/Kconfig                                  |  26 +

 kernel/kallsyms.c                             | 163 +++-
 kernel/module.c                               |  81 ++
 tools/objtool/elf.c                           |   8 +-
 26 files changed, 1670 insertions(+), 85 deletions(-)
 create mode 100644 Documentation/security/fgkaslr.rst
 create mode 100644 arch/x86/boot/compressed/fgkaslr.c
 create mode 100644 arch/x86/boot/compressed/utils.c
 create mode 100644 arch/x86/boot/compressed/vmlinux.symbols

Quoted 11 lines · Kristen Carlson Accardi

Function Granular Kernel Address Space Layout Randomization (fgkaslr)
-----------------------------------------------------------------
----

This patch set is an implementation of finer grained kernel address space
randomization. It rearranges your kernel code at load time on a per-function level granularity, with only around a second added to
boot time.

This is a very nice feature IMO, and it should be far more effective at randomizing the kernel, due to the sheer number of randomization bits that kernel function granular randomization presents.

If this is a good approximation of fg-kaslr randomization depth:

thule:~/tip> grep ' [tT] ' /proc/kallsyms | wc -l 88488

... then that's 80K bits of randomization instead of the mere handful
of kaslr bits we have today. Very nice!

Quoted 2 lines

In order to hide our new layout, symbols reported through /proc/kallsyms will be displayed in a random order.

Neat. :-)

Quoted 15 lines

Performance Impact
------------------
* Run time
The performance impact at run-time of function reordering varies by workload.
Using kcbench, a kernel compilation benchmark, the performance of a kernel
build with finer grained KASLR was about 1% slower than a kernel with standard
KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied
results. Some workloads performed significantly worse under FGKASLR, while
others stayed the same or were mysteriously better. In general, it

Quoted 8 lines

will
depend on the code flow whether or not finer grained KASLR will impact
your workload, and how the underlying code was designed. Because the layout
changes per boot, each time a system is rebooted the performance of a workload
may change.

I'd guess that the biggest performance impact comes from tearing apart
'groups' of functions that particular workloads are using.

In that sense it might be worthwile to add a '__kaslr_group' function
tag to key functions, which would keep certain performance critical functions next to each other.

This shouldn't really be a problem, as even with generous amount of grouping the number of randomization bits is incredibly large.

Quoted 14 lines

Future work could identify hot areas that may not be randomized and either
leave them in the .text section or group them together into a single section
that may be randomized. If grouping things together helps, one other thing to
consider is that if we could identify text blobs that should be grouped together
to benefit a particular code flow, it could be interesting to explore
whether this security feature could be also be used as a performance
feature if you are interested in optimizing your kernel layout for

Quoted 8 lines

a
particular workload at boot time. Optimizing function layout for a particular
workload has been researched and proven effective - for more information
read the Facebook paper "Optimizing Function Placement for Large- Scale
Data-Center Applications" (see references section below).

I'm pretty sure the 'grouping' solution would address any real slowdowns.

I'd also suggest allowing the passing in of a boot-time pseudo- random
generator seed number, which would allow the creation of a pseudo-randomized but repeatable layout across reboots.

Quoted 12 lines

Image Size
----------
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. With a standard distro config, the resulting vmlinux was increased by
about 3%. The compressed image is also increased due to the header files,
as well as the extra relocations that must be added. You can expect fgkaslr
to increase the size of the compressed image by about 15%.

What is the increase of the resulting raw kernel image? Additional relocations might increase its size (unless I'm missing something) - it would be nice to measure this effect. I'd expect this to be really
low.

vmlinux or compressed kernel size doesn't really matter on x86-64, it's a boot time only expense well within typical system resource limits.

Quoted 7 lines

Disabling
---------
Disabling normal KASLR using the nokaslr command line option also disables
fgkaslr. It is also possible to disable fgkaslr separately by booting with
fgkaslr=off on the commandline.

I'd suggest to also add a 'nofgkaslr' boot option if it doesn't yet exist, to keep usage symmetric with kaslr.

Likewise, there should probably be a 'kaslr=off' option as well.

The less random our user interfaces are, the better ...

Quoted 18 lines

 arch/x86/boot/compressed/Makefile             |   9 +-
 arch/x86/boot/compressed/fgkaslr.c            | 811
++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c              |   4 -
 arch/x86/boot/compressed/misc.c               | 157 +++-
 arch/x86/boot/compressed/misc.h               |  30 +
 arch/x86/boot/compressed/utils.c              |  11 +
 arch/x86/boot/compressed/vmlinux.symbols      |  17 +
 arch/x86/include/asm/boot.h                   |  15 +-
 arch/x86/kernel/vmlinux.lds.S                 |  17 +-
 arch/x86/lib/kaslr.c                          |  18 +-
 arch/x86/tools/relocs.c                       | 143 ++-
 arch/x86/tools/relocs.h                       |   4 +-
 arch/x86/tools/relocs_common.c                |  15 +-
 include/asm-generic/vmlinux.lds.h             |  18 +-
 include/linux/decompress/mm.h                 |  12 +-
 include/uapi/linux/elf.h                      |   1 +
 init/Kconfig                                  |  26 +

Quoted 8 lines

 kernel/kallsyms.c                             | 163 +++-
 kernel/module.c                               |  81 ++
 tools/objtool/elf.c                           |   8 +-
 26 files changed, 1670 insertions(+), 85 deletions(-)
 create mode 100644 Documentation/security/fgkaslr.rst
 create mode 100644 arch/x86/boot/compressed/fgkaslr.c
 create mode 100644 arch/x86/boot/compressed/utils.c
 create mode 100644 arch/x86/boot/compressed/vmlinux.symbols

This looks surprisingly lean overall.

Quoted 4 lines · Kristen Carlson Accardi

[...]
Performance Impact
------------------

Quoted 12 lines

* Run time
The performance impact at run-time of function reordering varies by workload. Using kcbench, a kernel compilation benchmark, the performance of a kernel build with finer grained KASLR was about 1% slower than a kernel with standard KASLR. Analysis with perf showed a slightly higher percentage of L1-icache-load-misses. Other workloads were examined as well, with varied results. Some workloads performed significantly worse under FGKASLR, while others stayed the same or were mysteriously better. In general, it will depend on the code flow whether or not finer grained KASLR will impact your workload, and how the underlying code was designed. Because the layout changes per boot, each time a system is rebooted the performance of a workload may change.

I'd guess that the biggest performance impact comes from tearing apart 'groups' of functions that particular workloads are using.

In that sense it might be worthwile to add a '__kaslr_group' function tag to key functions, which would keep certain performance critical functions next to each other.

I'd also suggest allowing the passing in of a boot-time pseudo-random generator seed number, which would allow the creation of a pseudo-randomized but repeatable layout across reboots.