Function Granular KASLR

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 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 and address review feedback
* 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 sorted by name alphabetically rather than by address.

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 (1):
x86/boot: Allow a "silent" kaslr random byte fetch

Kristen Carlson Accardi (9):
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/boot/compressed: change definition of STATIC
x86: Add support for function granular KASLR
kallsyms: Hide layout
module: Reorder functions

 Documentation/security/fgkaslr.rst       | 173 +++++
 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       | 812 +++++++++++++++++++++++
 arch/x86/boot/compressed/kaslr.c         |   4 -
 arch/x86/boot/compressed/misc.c          | 161 ++++-
 arch/x86/boot/compressed/misc.h          |  34 +
 arch/x86/boot/compressed/utils.c         |  12 +
 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/uapi/linux/elf.h                 |   1 +
 init/Kconfig                             |  26 +
 kernel/kallsyms.c                        | 128 ++++
 kernel/module.c                          |  81 +++
 tools/objtool/elf.c                      |   8 +-
 24 files changed, 1627 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: 48778464bb7d346b47157d21ffde2af6b2d39110

2.20.1

If a .cold function is examined prior to it's parent, the link to the parent/child function can be overwritten when the parent is examined. Only update pfunc and cfunc if they were previously nil to prevent this from happening.

---
 tools/objtool/elf.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

index 84225679f96d..f953d3a15612 100644
@@ -434,7 +434,13 @@ static int read_symbols(struct elf *elf)
 			size_t pnamelen;
 			if (sym->type != STT_FUNC)
 				continue;
-			sym->pfunc = sym->cfunc = sym;
+
+			if (sym->pfunc == NULL)
+				sym->pfunc = sym;
+
+			if (sym->cfunc == NULL)
+				sym->cfunc = sym;
+
 			coldstr = strstr(sym->name, ".cold");
 			if (!coldstr)
 				continue;

2.20.1

FYI, this patch is now in the tip tree.

Josh

While the relocs tool already supports finding the total number of section headers if vmlinux exceeds 64K sections, it fails to read the extended symbol table to get section header indexes for symbols, causing incorrect symbol table indexes to be used when there are > 64K symbols.

Parse the elf file to read the extended symbol table info, and then replace all direct references to st_shndx with calls to sym_index(), which will determine whether the value can be read directly or whether the value should be pulled out of the extended table.

---
 arch/x86/tools/relocs.c | 104 ++++++++++++++++++++++++++++++----------
 1 file changed, 78 insertions(+), 26 deletions(-)

index ce7188cbdae5..31b2d151aa63 100644
@@ -14,6 +14,10 @@
 static Elf_Ehdr		ehdr;
 static unsigned long	shnum;
 static unsigned int	shstrndx;
+static unsigned int	shsymtabndx;
+static unsigned int	shxsymtabndx;
+
+static int sym_index(Elf_Sym *sym);
 
 struct relocs {
 	uint32_t	*offset;

@@ -32,6 +36,7 @@ struct section {
 	Elf_Shdr       shdr;
 	struct section *link;
 	Elf_Sym        *symtab;
+	Elf32_Word     *xsymtab;
 	Elf_Rel        *reltab;
 	char           *strtab;
 };

@@ -265,7 +270,7 @@ static const char *sym_name(const char *sym_strtab, Elf_Sym *sym)
 		name = sym_strtab + sym->st_name;
 	}
 	else {
-		name = sec_name(sym->st_shndx);
+		name = sec_name(sym_index(sym));
 	}
 	return name;
 }

@@ -335,6 +340,23 @@ static uint64_t elf64_to_cpu(uint64_t val)
 #define elf_xword_to_cpu(x)	elf32_to_cpu(x)
 #endif
 
+static int sym_index(Elf_Sym *sym)
+{
+	Elf_Sym *symtab = secs[shsymtabndx].symtab;
+	Elf32_Word *xsymtab = secs[shxsymtabndx].xsymtab;
+	unsigned long offset;
+	int index;
+
+	if (sym->st_shndx != SHN_XINDEX)
+		return sym->st_shndx;
+
+	/* calculate offset of sym from head of table. */
+	offset = (unsigned long)sym - (unsigned long)symtab;
+	index = offset / sizeof(*sym);
+
+	return elf32_to_cpu(xsymtab[index]);
+}
+
 static void read_ehdr(FILE *fp)
 {
 	if (fread(&ehdr, sizeof(ehdr), 1, fp) != 1) {

@@ -468,31 +490,60 @@ static void read_strtabs(FILE *fp)
 static void read_symtabs(FILE *fp)
 {
 	int i,j;
+
 	for (i = 0; i < shnum; i++) {
 		struct section *sec = &secs[i];
-		if (sec->shdr.sh_type != SHT_SYMTAB) {
+		int num_syms;
+
+		switch (sec->shdr.sh_type) {
+		case SHT_SYMTAB_SHNDX:
+			sec->xsymtab = malloc(sec->shdr.sh_size);
+			if (!sec->xsymtab) {
+				die("malloc of %d bytes for xsymtab failed\n",
+				    sec->shdr.sh_size);
+			}
+			if (fseek(fp, sec->shdr.sh_offset, SEEK_SET) < 0) {
+				die("Seek to %d failed: %s\n",
+				    sec->shdr.sh_offset, strerror(errno));
+			}
+			if (fread(sec->xsymtab, 1, sec->shdr.sh_size, fp)
+			    != sec->shdr.sh_size) {
+				die("Cannot read extended symbol table: %s\n",
+				    strerror(errno));
+			}
+			shxsymtabndx = i;
+			continue;
+
+		case SHT_SYMTAB:
+			num_syms = sec->shdr.sh_size / sizeof(Elf_Sym);
+
+			sec->symtab = malloc(sec->shdr.sh_size);
+			if (!sec->symtab) {
+				die("malloc of %d bytes for symtab failed\n",
+				    sec->shdr.sh_size);
+			}
+			if (fseek(fp, sec->shdr.sh_offset, SEEK_SET) < 0) {
+				die("Seek to %d failed: %s\n",
+				    sec->shdr.sh_offset, strerror(errno));
+			}
+			if (fread(sec->symtab, 1, sec->shdr.sh_size, fp)
+			    != sec->shdr.sh_size) {
+				die("Cannot read symbol table: %s\n",
+				    strerror(errno));
+			}
+			for (j = 0; j < num_syms; j++) {
+				Elf_Sym *sym = &sec->symtab[j];
+
+				sym->st_name  = elf_word_to_cpu(sym->st_name);
+				sym->st_value = elf_addr_to_cpu(sym->st_value);
+				sym->st_size  = elf_xword_to_cpu(sym->st_size);
+				sym->st_shndx = elf_half_to_cpu(sym->st_shndx);
+			}
+			shsymtabndx = i;
+			continue;
+
+		default:
 			continue;
-		}
-		sec->symtab = malloc(sec->shdr.sh_size);
-		if (!sec->symtab) {
-			die("malloc of %d bytes for symtab failed\n",
-				sec->shdr.sh_size);
-		}
-		if (fseek(fp, sec->shdr.sh_offset, SEEK_SET) < 0) {
-			die("Seek to %d failed: %s\n",
-				sec->shdr.sh_offset, strerror(errno));
-		}
-		if (fread(sec->symtab, 1, sec->shdr.sh_size, fp)
-		    != sec->shdr.sh_size) {
-			die("Cannot read symbol table: %s\n",
-				strerror(errno));
-		}
-		for (j = 0; j < sec->shdr.sh_size/sizeof(Elf_Sym); j++) {
-			Elf_Sym *sym = &sec->symtab[j];
-			sym->st_name  = elf_word_to_cpu(sym->st_name);
-			sym->st_value = elf_addr_to_cpu(sym->st_value);
-			sym->st_size  = elf_xword_to_cpu(sym->st_size);
-			sym->st_shndx = elf_half_to_cpu(sym->st_shndx);
 		}
 	}
 }

@@ -759,13 +810,14 @@ static void percpu_init(void)
  */
 static int is_percpu_sym(ElfW(Sym) *sym, const char *symname)
 {
-	return (sym->st_shndx == per_cpu_shndx) &&
+	int shndx = sym_index(sym);
+
+	return (shndx == per_cpu_shndx) &&
 		strcmp(symname, "__init_begin") &&
 		strcmp(symname, "__per_cpu_load") &&
 		strncmp(symname, "init_per_cpu_", 13);
 }
 
-
 static int do_reloc64(struct section *sec, Elf_Rel *rel, ElfW(Sym) *sym,
 		      const char *symname)
 {

@@ -1088,7 +1140,7 @@ static int do_reloc_info(struct section *sec, Elf_Rel *rel, ElfW(Sym) *sym,
 		sec_name(sec->shdr.sh_info),
 		rel_type(ELF_R_TYPE(rel->r_info)),
 		symname,
-		sec_name(sym->st_shndx));
+		sec_name(sym_index(sym)));
 	return 0;
 }
 

2.20.1

From: Kees Cook <[email protected]>

Under earlyprintk, each RNG call produces a debug report line. When shuffling hundreds of functions, this is not useful information (each line is identical and tells us nothing new). Instead, allow for a NULL "purpose" to suppress the debug reporting.

---
 arch/x86/lib/kaslr.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

index a53665116458..2b3eb8c948a3 100644
@@ -56,11 +56,14 @@ unsigned long kaslr_get_random_long(const char *purpose)
 	unsigned long raw, random = get_boot_seed();
 	bool use_i8254 = true;
 
-	debug_putstr(purpose);
-	debug_putstr(" KASLR using");
+	if (purpose) {
+		debug_putstr(purpose);
+		debug_putstr(" KASLR using");
+	}
 
 	if (has_cpuflag(X86_FEATURE_RDRAND)) {
-		debug_putstr(" RDRAND");
+		if (purpose)
+			debug_putstr(" RDRAND");
 		if (rdrand_long(&raw)) {
 			random ^= raw;
 			use_i8254 = false;

@@ -68,7 +71,8 @@ unsigned long kaslr_get_random_long(const char *purpose)
 	}
 
 	if (has_cpuflag(X86_FEATURE_TSC)) {
-		debug_putstr(" RDTSC");
+		if (purpose)
+			debug_putstr(" RDTSC");
 		raw = rdtsc();
 
 		random ^= raw;

@@ -76,7 +80,8 @@ unsigned long kaslr_get_random_long(const char *purpose)
 	}
 
 	if (use_i8254) {
-		debug_putstr(" i8254");
+		if (purpose)
+			debug_putstr(" i8254");
 		random ^= i8254();
 	}
 

@@ -86,7 +91,8 @@ unsigned long kaslr_get_random_long(const char *purpose)
 	    : "a" (random), "rm" (mix_const));
 	random += raw;
 
-	debug_putstr("...\n");
+	if (purpose)
+		debug_putstr("...\n");
 
 	return random;
 }

2.20.1

Allow user to select CONFIG_FG_KASLR if dependencies are met. Change the make file to build with -ffunction-sections if CONFIG_FG_KASLR.

While the only architecture that supports CONFIG_FG_KASLR does not currently enable HAVE_LD_DEAD_CODE_DATA_ELIMINATION, make sure these 2 features play nicely together for the future by ensuring that if CONFIG_LD_DEAD_CODE_DATA_ELIMINATION is selected when used with CONFIG_FG_KASLR the function sections will not be consolidated back into .text. Thanks to Kees Cook for the dead code elimination changes.

---
 Makefile                          |  6 +++++-
 arch/x86/Kconfig                  |  4 ++++
 include/asm-generic/vmlinux.lds.h | 16 ++++++++++++++--
 init/Kconfig                      | 14 ++++++++++++++
 4 files changed, 37 insertions(+), 3 deletions(-)

index ac2c61c37a73..363f53798fca 100644
@@ -872,7 +872,7 @@ KBUILD_CFLAGS += $(call cc-option, -fno-inline-functions-called-once)
 endif
 
 ifdef CONFIG_LD_DEAD_CODE_DATA_ELIMINATION
-KBUILD_CFLAGS_KERNEL += -ffunction-sections -fdata-sections
+KBUILD_CFLAGS_KERNEL += -fdata-sections
 LDFLAGS_vmlinux += --gc-sections
 endif
 

@@ -880,6 +880,10 @@ ifdef CONFIG_LIVEPATCH
 KBUILD_CFLAGS += $(call cc-option, -flive-patching=inline-clone)
 endif
 
+ifneq ($(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION)$(CONFIG_FG_KASLR),)
+KBUILD_CFLAGS += -ffunction-sections
+endif
+
 ifdef CONFIG_SHADOW_CALL_STACK
 CC_FLAGS_SCS	:= -fsanitize=shadow-call-stack
 KBUILD_CFLAGS	+= $(CC_FLAGS_SCS)

index 6a0cc524882d..932cbc327af0 100644
@@ -372,6 +372,10 @@ config CC_HAS_SANE_STACKPROTECTOR
 	   We have to make sure stack protector is unconditionally disabled if
 	   the compiler produces broken code.
 
+config ARCH_HAS_FG_KASLR
+	def_bool y
+	depends on RANDOMIZE_BASE && X86_64
+
 menu "Processor type and features"
 
 config ZONE_DMA

index db600ef218d7..a5552cf28d5d 100644
@@ -93,14 +93,12 @@
  * sections to be brought in with rodata.
  */
 #ifdef CONFIG_LD_DEAD_CODE_DATA_ELIMINATION
-#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*
 #define DATA_MAIN .data .data.[0-9a-zA-Z_]* .data..LPBX*
 #define SDATA_MAIN .sdata .sdata.[0-9a-zA-Z_]*
 #define RODATA_MAIN .rodata .rodata.[0-9a-zA-Z_]*
 #define BSS_MAIN .bss .bss.[0-9a-zA-Z_]*
 #define SBSS_MAIN .sbss .sbss.[0-9a-zA-Z_]*
 #else
-#define TEXT_MAIN .text
 #define DATA_MAIN .data
 #define SDATA_MAIN .sdata
 #define RODATA_MAIN .rodata

@@ -108,6 +106,20 @@
 #define SBSS_MAIN .sbss
 #endif
 
+/*
+ * Both LD_DEAD_CODE_DATA_ELIMINATION and CONFIG_FG_KASLR options enable
+ * -ffunction-sections, which produces separately named .text sections. In
+ * the case of CONFIG_FG_KASLR, they need to stay distict so they can be
+ * separately randomized. Without CONFIG_FG_KASLR, the separate .text
+ * sections can be collected back into a common section, which makes the
+ * resulting image slightly smaller
+ */
+#if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION) && !defined(CONFIG_FG_KASLR)
+#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*
+#else
+#define TEXT_MAIN .text
+#endif
+
 /*
  * Align to a 32 byte boundary equal to the
  * alignment gcc 4.5 uses for a struct

index a46aa8f3174d..e29c032e4d66 100644
@@ -1990,6 +1990,20 @@ config PROFILING
 config TRACEPOINTS
 	bool
 
+config FG_KASLR
+	bool "Function Granular Kernel Address Space Layout Randomization"
+	depends on $(cc-option, -ffunction-sections)
+	depends on ARCH_HAS_FG_KASLR
+	default n
+	help
+	  This option improves the randomness of the kernel text
+	  over basic Kernel Address Space Layout Randomization (KASLR)
+	  by reordering the kernel text at boot time. This feature
+	  uses information generated at compile time to re-layout the
+	  kernel text section at boot time at function level granularity.
+
+	  If unsure, say N.
+
 endmenu		# General setup
 
 source "arch/Kconfig"

2.20.1

When using -ffunction-sections to place each function in it's own text section so it can be randomized at load time, the linker considers these .text.* sections "orphaned sections", and will place them after the first similar section (.text). In order to accurately represent the end of the text section and the orphaned sections, _etext must be moved so that it is after both .text and .text.* The text size must also be calculated to include .text AND .text.*

---
 arch/x86/kernel/vmlinux.lds.S     | 17 +++++++++++++++--
 include/asm-generic/vmlinux.lds.h |  2 +-
 2 files changed, 16 insertions(+), 3 deletions(-)

index 3bfc8dd8a43d..e8da7eeb4d8d 100644
@@ -146,9 +146,22 @@ SECTIONS
 #endif
 	} :text =0xcccc
 
-	/* End of text section, which should occupy whole number of pages */
-	_etext = .;
+	/*
+	 * -ffunction-sections creates .text.* sections, which are considered
+	 * "orphan sections" and added after the first similar section (.text).
+	 * Placing this ALIGN statement before _etext causes the address of
+	 * _etext to be below that of all the .text.* orphaned sections
+	 */
 	. = ALIGN(PAGE_SIZE);
+	_etext = .;
+
+	/*
+	 * the size of the .text section is used to calculate the address
+	 * range for orc lookups. If we just use SIZEOF(.text), we will
+	 * miss all the .text.* sections. Calculate the size using _etext
+	 * and _stext and save the value for later.
+	 */
+	text_size = _etext - _stext;
 
 	X86_ALIGN_RODATA_BEGIN
 	RO_DATA(PAGE_SIZE)

index a5552cf28d5d..34eab6513fdc 100644
@@ -835,7 +835,7 @@
 	. = ALIGN(4);							\
 	.orc_lookup : AT(ADDR(.orc_lookup) - LOAD_OFFSET) {		\
 		orc_lookup = .;						\
-		. += (((SIZEOF(.text) + LOOKUP_BLOCK_SIZE - 1) /	\
+		. += (((text_size + LOOKUP_BLOCK_SIZE - 1) /	\
 			LOOKUP_BLOCK_SIZE) + 1) * 4;			\
 		orc_lookup_end = .;					\
 	}

2.20.1

When reordering functions, the relative offsets for relocs that are either in the randomized sections, or refer to the randomized sections will need to be adjusted. Add code to detect whether a reloc satisifies these cases, and if so, add them to the appropriate reloc list.

---
 arch/x86/boot/compressed/Makefile |  7 +++++-
 arch/x86/tools/relocs.c           | 41 ++++++++++++++++++++++++++++---
 arch/x86/tools/relocs.h           |  4 +--
 arch/x86/tools/relocs_common.c    | 15 +++++++----
 4 files changed, 55 insertions(+), 12 deletions(-)

index 7619742f91c9..c17b1c8ec82c 100644
@@ -119,6 +119,11 @@ $(obj)/vmlinux: $(vmlinux-objs-y) FORCE
 	$(call if_changed,check-and-link-vmlinux)
 
 OBJCOPYFLAGS_vmlinux.bin :=  -R .comment -S
+
+ifdef CONFIG_FG_KASLR
+	RELOCS_ARGS += --fg-kaslr
+endif
+
 $(obj)/vmlinux.bin: vmlinux FORCE
 	$(call if_changed,objcopy)
 

@@ -126,7 +131,7 @@ targets += $(patsubst $(obj)/%,%,$(vmlinux-objs-y)) vmlinux.bin.all vmlinux.relo
 
 CMD_RELOCS = arch/x86/tools/relocs
 quiet_cmd_relocs = RELOCS  $@
-      cmd_relocs = $(CMD_RELOCS) $< > $@;$(CMD_RELOCS) --abs-relocs $<
+      cmd_relocs = $(CMD_RELOCS) $(RELOCS_ARGS) $< > $@;$(CMD_RELOCS) $(RELOCS_ARGS) --abs-relocs $<
 $(obj)/vmlinux.relocs: vmlinux FORCE
 	$(call if_changed,relocs)
 

index 43c83c0fd22c..f582895c04dd 100644
@@ -31,8 +31,8 @@ enum symtype {
 
 void process_32(FILE *fp, int use_real_mode, int as_text,
 		int show_absolute_syms, int show_absolute_relocs,
-		int show_reloc_info);
+		int show_reloc_info, int fgkaslr);
 void process_64(FILE *fp, int use_real_mode, int as_text,
 		int show_absolute_syms, int show_absolute_relocs,
-		int show_reloc_info);
+		int show_reloc_info, int fgkaslr);
 #endif /* RELOCS_H */

index 6634352a20bc..a80efa2f53ff 100644
@@ -12,14 +12,14 @@ void die(char *fmt, ...)
 
 static void usage(void)
 {
-	die("relocs [--abs-syms|--abs-relocs|--reloc-info|--text|--realmode]" \
-	    " vmlinux\n");
+	die("relocs [--abs-syms|--abs-relocs|--reloc-info|--text|--realmode|" \
+	    "--fg-kaslr] vmlinux\n");
 }
 
 int main(int argc, char **argv)
 {
 	int show_absolute_syms, show_absolute_relocs, show_reloc_info;
-	int as_text, use_real_mode;
+	int as_text, use_real_mode, fgkaslr_opt;
 	const char *fname;
 	FILE *fp;
 	int i;

@@ -30,6 +30,7 @@ int main(int argc, char **argv)
 	show_reloc_info = 0;
 	as_text = 0;
 	use_real_mode = 0;
+	fgkaslr_opt = 0;
 	fname = NULL;
 	for (i = 1; i < argc; i++) {
 		char *arg = argv[i];

@@ -54,6 +55,10 @@ int main(int argc, char **argv)
 				use_real_mode = 1;
 				continue;
 			}
+			if (strcmp(arg, "--fg-kaslr") == 0) {
+				fgkaslr_opt = 1;
+				continue;
+			}
 		}
 		else if (!fname) {
 			fname = arg;

@@ -75,11 +80,11 @@ int main(int argc, char **argv)
 	if (e_ident[EI_CLASS] == ELFCLASS64)
 		process_64(fp, use_real_mode, as_text,
 			   show_absolute_syms, show_absolute_relocs,
-			   show_reloc_info);
+			   show_reloc_info, fgkaslr_opt);
 	else
 		process_32(fp, use_real_mode, as_text,
 			   show_absolute_syms, show_absolute_relocs,
-			   show_reloc_info);
+			   show_reloc_info, fgkaslr_opt);
 	fclose(fp);
 	return 0;
 }

2.20.1

In preparation for changes to the upcoming fgkaslr commit, change misc.c to not define STATIC as static, but instead set STATIC to "". This allows memptr to become accessible to multiple files.

---
 arch/x86/boot/compressed/kaslr.c | 4 ----
 arch/x86/boot/compressed/misc.c  | 7 ++++---
 arch/x86/boot/compressed/misc.h  | 6 ++++++
 3 files changed, 10 insertions(+), 7 deletions(-)

index d7408af55738..6f596bd5b6e5 100644
@@ -39,10 +39,6 @@
 #include <generated/utsrelease.h>
 #include <asm/efi.h>
 
-/* Macros used by the included decompressor code below. */
-#define STATIC
-#include <linux/decompress/mm.h>
-
 #ifdef CONFIG_X86_5LEVEL
 unsigned int __pgtable_l5_enabled;
 unsigned int pgdir_shift __ro_after_init = 39;

index 9652d5c2afda..a55a4ec48422 100644
@@ -26,9 +26,6 @@
  * it is not safe to place pointers in static structures.
  */
 
-/* Macros used by the included decompressor code below. */
-#define STATIC		static
-
 /*
  * Use normal definitions of mem*() from string.c. There are already
  * included header files which expect a definition of memset() and by

@@ -49,6 +46,10 @@ struct boot_params *boot_params;
 
 memptr free_mem_ptr;
 memptr free_mem_end_ptr;
+#ifdef CONFIG_FG_KASLR
+unsigned long malloc_ptr;
+int malloc_count;
+#endif
 
 static char *vidmem;
 static int vidport;

index 726e264410ff..d2ec7c745cfa 100644
@@ -39,6 +39,12 @@
 /* misc.c */
 extern memptr free_mem_ptr;
 extern memptr free_mem_end_ptr;
+#define STATIC
+#ifdef CONFIG_FG_KASLR
+#define STATIC_RW_DATA extern
+#endif
+#include <linux/decompress/mm.h>
+
 extern struct boot_params *boot_params;
 void __putstr(const char *s);
 void __puthex(unsigned long value);

2.20.1

Thanks for splitting this out!

After looking at the results, I think I finally understand the issue getting solved. tl;dr: I think your patch isn't the right solution (basically making "malloc_ptr" a global so that multiple static copies of malloc() all behave the same). I think the right solution is to avoid the multiple copies of malloc()/free().

I think this patch should be used instead:

Subject: [PATCH] x86/boot/compressed: Avoid duplicate malloc() implementations

The preboot malloc() (and free()) implementation in include/linux/decompress/mm.h (which is also included by the static decompressors) is static. This is fine when the only thing interested in using malloc() is the decompression code, but the x86 preboot environment uses malloc() in a couple places, leading to a potential collision when the static copies of the available memory region ("malloc_ptr") gets reset to the global "free_mem_ptr" value. As it happens, the existing usage pattern happened to be safe because each user did 1 malloc() and 1 free() before returning and were not nested:

extract_kernel() (misc.c)

	choose_random_location() (kaslr.c)
		mem_avoid_init()
			handle_mem_options()
				malloc()
				...
				free()
	...
	parse_elf() (misc.c)
		malloc()
		...
		free()

Adding FGKASLR, however, will insert additional malloc() calls local to fgkaslr.c in the middle of parse_elf()'s malloc()/free() pair:

	parse_elf() (misc.c)
		malloc()
		if (...) {
			layout_randomized_image(output, &ehdr, phdrs);
				malloc() <- boom
				...
		else
			layout_image(output, &ehdr, phdrs);
		free()

To avoid collisions, there must be a single implementation of malloc(). Adjust include/linux/decompress/mm.h so that visibility can be controlled, provide prototypes in misc.h, and implement the functions in misc.c. This also results in a small size savings:

$ size vmlinux.before vmlinux.after
   text    data     bss     dec     hex filename
8842314     468  178320 9021102  89a6ae vmlinux.before
8842240     468  178320 9021028  89a664 vmlinux.after

---
 arch/x86/boot/compressed/kaslr.c |    4 ----
 arch/x86/boot/compressed/misc.c  |    3 +++
 arch/x86/boot/compressed/misc.h  |    2 ++
 include/linux/decompress/mm.h    |   12 ++++++++++--
 4 files changed, 15 insertions(+), 6 deletions(-)

index 7667415417dc..ae6691e8bb08 100644
@@ -44,12 +44,12 @@ void *memmove(void *dest, const void *src, size_t n);
  */
 struct boot_params *boot_params;
 
+/* Initial heap area used to initialize malloc()/free() internals.*/
 memptr free_mem_ptr;
 memptr free_mem_end_ptr;
-#ifdef CONFIG_FG_KASLR
+/* Global internals for malloc()/free() implementations. */
 unsigned long malloc_ptr;
 int malloc_count;
-#endif
 
 static char *vidmem;
 static int vidport;

index 86a5f00b018f..45644056572b 100644
@@ -36,15 +36,14 @@
 #define memptr unsigned
 #endif
 
-/* misc.c */
-extern memptr free_mem_ptr;
-extern memptr free_mem_end_ptr;
-#define STATIC
-#ifdef CONFIG_FG_KASLR
+/* malloc()/free() */
+#define STATIC static
 #define STATIC_RW_DATA extern
-#endif
 #include <linux/decompress/mm.h>
 
+/* misc.c */
+extern memptr free_mem_ptr;
+extern memptr free_mem_end_ptr;
 extern struct boot_params *boot_params;
 void __putstr(const char *s);
 void __puthex(unsigned long value);

However, after all that, I actually think the correct way to solve this is actually to have only one implementation of malloc()/free(). i.e. replace this patch with this:

index d7408af55738..6f596bd5b6e5 100644
@@ -39,10 +39,6 @@
 #include <generated/utsrelease.h>
 #include <asm/efi.h>
 
-/* Macros used by the included decompressor code below. */
-#define STATIC
-#include <linux/decompress/mm.h>
-
 #ifdef CONFIG_X86_5LEVEL
 unsigned int __pgtable_l5_enabled;
 unsigned int pgdir_shift __ro_after_init = 39;

index 1c8b8aa5539f..f52150ec3ee7 100644
@@ -28,6 +28,9 @@
 
 /* Macros used by the included decompressor code below. */
 #define STATIC		static
+/* Define an externally visible malloc()/free(). */
+#define MALLOC_VISIBLE
+#include <linux/decompress/mm.h>
 
 /*
  * Use normal definitions of mem*() from string.c. There are already

index 214ef31db468..fd0c63cfaa4a 100644
@@ -39,6 +39,8 @@
 /* misc.c */
 extern memptr free_mem_ptr;
 extern memptr free_mem_end_ptr;
+extern void *malloc(int size);
+extern void free(void *where);
 extern struct boot_params *boot_params;
 void __putstr(const char *s);
 void __puthex(unsigned long value);

index 868e9eacd69e..9192986b1a73 100644
@@ -25,13 +25,21 @@
 #define STATIC_RW_DATA static
 #endif
 
+/*
+ * When an architecture needs to share the malloc()/free() implementation
+ * between compilation units, it needs to have non-local visibility.
+ */
+#ifndef MALLOC_VISIBLE
+#define MALLOC_VISIBLE static
+#endif
+
 /* A trivial malloc implementation, adapted from
  *  malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
  */
 STATIC_RW_DATA unsigned long malloc_ptr;
 STATIC_RW_DATA int malloc_count;
 
-static void *malloc(int size)
+MALLOC_VISIBLE void *malloc(int size)
 {
 	void *p;
 

@@ -52,7 +60,7 @@ static void *malloc(int size)
 	return p;
 }
 
-static void free(void *where)
+MALLOC_VISIBLE void free(void *where)
 {
 	malloc_count--;
 	if (!malloc_count)

Kees Cook

This commit contains the changes required to re-layout the kernel text sections generated by -ffunction-sections shortly after decompression. Documentation of the feature is also added.

After decompression, the decompressed image's elf headers are parsed. In order to manually update certain data structures that are built with relative offsets during the kernel build process, certain symbols are not stripped by objdump and their location is retained in the elf symbol tables. These addresses are saved.

If the image was built with -ffunction-sections, there will be ELF section headers present which contain information about the address range of each section. Anything that is not broken out into function sections (i.e. is consolidated into .text) is left in it's original location, but any other executable section which begins with ".text." is located and shuffled randomly within the remaining text segment address range.

After the sections have been copied to their new locations, but before relocations have been applied, the kallsyms tables must be updated to reflect the new symbol locations. Because it is expected that these tables will be sorted by address, the kallsyms tables will need to be sorted after the update.

When applying relocations, the address of the relocation needs to be adjusted by the offset from the original location of the section that was randomized to it's new location. In addition, if a value at that relocation was a location in the text segment that was randomized, it's value will be adjusted to a new location.

After relocations have been applied, the exception table must be updated with with new symbol locations, and then re-sorted by the new address. The orc table will have been updated as part of applying relocations, but since it is expected to be sorted by address, it will need to be resorted.

---
 Documentation/security/fgkaslr.rst       | 173 +++++
 Documentation/security/index.rst         |   1 +
 arch/x86/boot/compressed/Makefile        |   2 +
 arch/x86/boot/compressed/fgkaslr.c       | 812 +++++++++++++++++++++++
 arch/x86/boot/compressed/misc.c          | 154 ++++-
 arch/x86/boot/compressed/misc.h          |  28 +
 arch/x86/boot/compressed/utils.c         |  12 +
 arch/x86/boot/compressed/vmlinux.symbols |  17 +
 arch/x86/include/asm/boot.h              |  15 +-
 include/uapi/linux/elf.h                 |   1 +
 10 files changed, 1187 insertions(+), 28 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

new file mode 100644
index 000000000000..9478b1298ae8
@@ -0,0 +1,173 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=====================================================================
+Function Granular Kernel Address Space Layout Randomization (fgkaslr)
+=====================================================================
+
+:Date: 6 April 2020
+:Author: Kristen Accardi
+
+Kernel Address Space Layout Randomization (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 as it was originally implemented 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. The term "fgkaslr" is used in this document to refer to the
+technique of function reordering when used with KASLR, as well as finer grained
+KASLR in general.
+
+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 code reuse
+attacks, and should be considered as one of several tools that can be used.
+
+Implementation Details
+======================
+
+The over-arching objective of the fgkaslr implementation is incremental
+improvement over the existing KASLR algorithm. It is designed to work with
+the existing solution, and there are two main area where code changes occur:
+Build time, and Load time.
+
+Build time
+----------
+
+GCC has had an option to place functions into individual .text sections
+for many years now (-ffunction-sections). This option is 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 shuffled immediately after decompression.
+Some data tables inside the kernel that have assumptions about order
+require sorting after the update. In order to modify these tables,
+a few key symbols from the objcopy symbol stripping process are preserved
+for use after shuffling the text segments. Any special input sections which are
+defined by the kernel build process and collected into the .text output
+segment are left unmodified and will still be present inside the .text segment,
+unrandomized other than normal base address randomization.
+
+Load time
+---------
+
+The boot kernel was modified to parse the vmlinux elf file after
+decompression to check for symbols for modifying data tables, and to
+look for any .text.* sections to randomize. The sections are then shuffled,
+and tables are updated or resorted. 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.
+
+In order to hide the new layout, symbols reported through /proc/kallsyms will
+be sorted by name alphabetically rather than by address.
+
+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.
+Randomly reordering the functions will cause an increase in cache misses
+for some workloads. Some workloads perform significantly worse under FGKASLR,
+while others stay the same or even improve. In general, it will depend on the
+code flow whether or not finer grained KASLR will impact a 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.
+
+Image Size
+==========
+
+fgkaslr increases the size of the kernel binary due to the extra section
+headers that are included, as well as the extra relocations that need to
+be added. You can expect fgkaslr to increase the size of the resulting
+vmlinux by about 3%, and the compressed image (bzImage) by 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``
+
+fgkaslr for the kernel 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 the following config option:
+
+``CONFIG_MODULE_FG_KASLR``
+
+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. In addtion, it is possible to disable fgkaslr separately by booting
+with fgkaslr=off on the commandline.
+
+Further Information
+===================
+
+There are a lot of academic papers which explore finer grained ASLR.
+This paper in particular contributed significantly to the implementation design.
+
+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
+

index 8129405eb2cc..19677beb33d4 100644
@@ -7,6 +7,7 @@ Security Documentation
 
    credentials
    IMA-templates
+   fgkaslr
    keys/index
    lsm
    lsm-development

index c17b1c8ec82c..1508995dc2ed 100644
@@ -82,6 +82,7 @@ vmlinux-objs-y := $(obj)/vmlinux.lds $(obj)/kernel_info.o $(obj)/head_$(BITS).o
 
 vmlinux-objs-$(CONFIG_EARLY_PRINTK) += $(obj)/early_serial_console.o
 vmlinux-objs-$(CONFIG_RANDOMIZE_BASE) += $(obj)/kaslr.o
+vmlinux-objs-$(CONFIG_FG_KASLR) += $(obj)/utils.o $(obj)/fgkaslr.o
 ifdef CONFIG_X86_64
 	vmlinux-objs-$(CONFIG_RANDOMIZE_BASE) += $(obj)/kaslr_64.o
 	vmlinux-objs-y += $(obj)/mem_encrypt.o

@@ -122,6 +123,7 @@ OBJCOPYFLAGS_vmlinux.bin :=  -R .comment -S
 
 ifdef CONFIG_FG_KASLR
 	RELOCS_ARGS += --fg-kaslr
+	OBJCOPYFLAGS += --keep-symbols=$(srctree)/$(src)/vmlinux.symbols
 endif
 
 $(obj)/vmlinux.bin: vmlinux FORCE

index d2ec7c745cfa..86a5f00b018f 100644
@@ -80,6 +80,34 @@ struct mem_vector {
 	unsigned long long size;
 };
 
+#ifdef CONFIG_X86_64
+#define Elf_Ehdr Elf64_Ehdr
+#define Elf_Phdr Elf64_Phdr
+#define Elf_Shdr Elf64_Shdr
+#else
+#define Elf_Ehdr Elf32_Ehdr
+#define Elf_Phdr Elf32_Phdr
+#define Elf_Shdr Elf32_Shdr
+#endif
+
+#if CONFIG_FG_KASLR
+void layout_randomized_image(void *output, Elf_Ehdr *ehdr, Elf_Phdr *phdrs);
+void pre_relocations_cleanup(unsigned long map);
+void post_relocations_cleanup(unsigned long map);
+Elf_Shdr *adjust_address(long *address);
+void adjust_relative_offset(long pc, long *value, Elf_Shdr *section);
+bool is_percpu_addr(long pc, long offset);
+#else
+static inline void layout_randomized_image(void *output, Elf_Ehdr *ehdr,
+					   Elf_Phdr *phdrs) { }
+static inline void pre_relocations_cleanup(unsigned long map) { }
+static inline void post_relocations_cleanup(unsigned long map) { }
+static inline Elf_Shdr *adjust_address(long *address) { return NULL; }
+static inline void adjust_relative_offset(long pc, long *value,
+					  Elf_Shdr *section) { }
+static inline bool is_percpu_addr(long pc, long offset) { return true; }
+#endif /* CONFIG_FG_KASLR */
+
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
 void choose_random_location(unsigned long input,

new file mode 100644
index 000000000000..ceefc58d7c71
@@ -0,0 +1,12 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * utils.c
+ *
+ * This contains various libraries that are needed for fgkaslr
+ */
+#define __DISABLE_EXPORTS
+#define _LINUX_KPROBES_H
+#define NOKPROBE_SYMBOL(fname)
+#include "../../../../lib/sort.c"
+#include "../../../../lib/bsearch.c"
+

new file mode 100644
index 000000000000..cc86e79a2a3d
@@ -0,0 +1,17 @@
+kallsyms_offsets
+kallsyms_addresses
+kallsyms_num_syms
+kallsyms_relative_base
+kallsyms_names
+kallsyms_token_table
+kallsyms_token_index
+kallsyms_markers
+__start___ex_table
+__stop___ex_table
+_sinittext
+_einittext
+_stext
+_etext
+__start_orc_unwind_ip
+__stop_orc_unwind_ip
+__start_orc_unwind

index 680c320363db..6918d33eb5ef 100644
@@ -26,8 +26,19 @@
 
 #ifdef CONFIG_KERNEL_BZIP2
 # define BOOT_HEAP_SIZE		0x400000
-#else /* !CONFIG_KERNEL_BZIP2 */
-# define BOOT_HEAP_SIZE		 0x10000
+#elif CONFIG_FG_KASLR
+/*
+ * We need extra boot heap when using fgkaslr because we make a copy
+ * of the original decompressed kernel to avoid issues with writing
+ * over ourselves when shuffling the sections. We also need extra
+ * space for resorting kallsyms after shuffling. This value could
+ * be decreased if free() would release memory properly, or if we
+ * could avoid the kernel copy. It would need to be increased if we
+ * find additional tables that need to be resorted.
+ */
+# define BOOT_HEAP_SIZE		0x4000000
+#else /* !CONFIG_KERNEL_BZIP2 && !CONFIG_FG_KASLR */
+# define BOOT_HEAP_SIZE		0x10000
 #endif
 
 #ifdef CONFIG_X86_64

index c6dd0215482e..4ef6360bd18c 100644
@@ -299,6 +299,7 @@ typedef struct elf64_phdr {
 #define SHN_LIVEPATCH	0xff20
 #define SHN_ABS		0xfff1
 #define SHN_COMMON	0xfff2
+#define SHN_XINDEX	0xffff
 #define SHN_HIRESERVE	0xffff
  
 typedef struct elf32_shdr {

2.20.1

This looks good! I wonder about some way (in the future) to share the sorting routines for kallsyms, exceptions, orc, etc. For now, though, I think this is fine.

Kees Cook

This patch makes /proc/kallsyms display alphabetically by symbol name rather than sorted by address in order to hide the newly randomized address layout.

---
 kernel/kallsyms.c | 128 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 128 insertions(+)

index 16c8c605f4b0..df2b20e1b7f2 100644
@@ -25,6 +25,7 @@
 #include <linux/filter.h>
 #include <linux/ftrace.h>
 #include <linux/compiler.h>
+#include <linux/list_sort.h>
 
 /*
  * These will be re-linked against their real values

@@ -446,6 +447,11 @@ struct kallsym_iter {
 	int show_value;
 };
 
+struct kallsyms_iter_list {
+	struct kallsym_iter iter;
+	struct list_head next;
+};
+
 int __weak arch_get_kallsym(unsigned int symnum, unsigned long *value,
 			    char *type, char *name)
 {

@@ -660,6 +666,127 @@ int kallsyms_show_value(void)
 	}
 }
 
+static int sorted_show(struct seq_file *m, void *p)
+{
+	struct list_head *list = m->private;
+	struct kallsyms_iter_list *iter;
+	int rc;
+
+	if (list_empty(list))
+		return 0;
+
+	iter = list_first_entry(list, struct kallsyms_iter_list, next);
+
+	m->private = iter;
+	rc = s_show(m, p);
+	m->private = list;
+
+	list_del(&iter->next);
+	kfree(iter);
+
+	return rc;
+}
+
+static void *sorted_start(struct seq_file *m, loff_t *pos)
+{
+	return m->private;
+}
+
+static void *sorted_next(struct seq_file *m, void *p, loff_t *pos)
+{
+	struct list_head *list = m->private;
+
+	(*pos)++;
+
+	if (list_empty(list))
+		return NULL;
+
+	return p;
+}
+
+static const struct seq_operations kallsyms_sorted_op = {
+	.start = sorted_start,
+	.next = sorted_next,
+	.stop = s_stop,
+	.show = sorted_show
+};
+
+static int kallsyms_list_cmp(void *priv, struct list_head *a,
+			     struct list_head *b)
+{
+	struct kallsyms_iter_list *iter_a, *iter_b;
+
+	iter_a = list_entry(a, struct kallsyms_iter_list, next);
+	iter_b = list_entry(b, struct kallsyms_iter_list, next);
+
+	return strcmp(iter_a->iter.name, iter_b->iter.name);
+}
+
+int get_all_symbol_name(void *data, const char *name, struct module *mod,
+			unsigned long addr)
+{
+	unsigned long sym_pos;
+	struct kallsyms_iter_list *node, *last;
+	struct list_head *head = (struct list_head *)data;
+
+	node = kmalloc(sizeof(*node), GFP_KERNEL);
+	if (!node)
+		return -ENOMEM;
+
+	if (list_empty(head)) {
+		sym_pos = 0;
+		memset(node, 0, sizeof(*node));
+		reset_iter(&node->iter, 0);
+		node->iter.show_value = kallsyms_show_value();
+	} else {
+		last = list_first_entry(head, struct kallsyms_iter_list, next);
+		memcpy(node, last, sizeof(*node));
+		sym_pos = last->iter.pos;
+	}
+
+	INIT_LIST_HEAD(&node->next);
+	list_add(&node->next, head);
+
+	/*
+	 * update_iter returns false when at end of file
+	 * which in this case we don't care about and can
+	 * safely ignore. update_iter() will increment
+	 * the value of iter->pos, for ksymbol_core.
+	 */
+	if (sym_pos >= kallsyms_num_syms)
+		sym_pos++;
+
+	(void)update_iter(&node->iter, sym_pos);
+
+	return 0;
+}
+
+#if defined(CONFIG_FG_KASLR)
+/*
+ * When fine grained kaslr is enabled, we need to
+ * print out the symbols sorted by name rather than by
+ * by address, because this reveals the randomization order.
+ */
+static int kallsyms_open(struct inode *inode, struct file *file)
+{
+	int ret;
+	struct list_head *list;
+
+	list = __seq_open_private(file, &kallsyms_sorted_op, sizeof(*list));
+	if (!list)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD(list);
+
+	ret = kallsyms_on_each_symbol(get_all_symbol_name, list);
+	if (ret != 0)
+		return ret;
+
+	list_sort(NULL, list, kallsyms_list_cmp);
+
+	return 0;
+}
+#else
 static int kallsyms_open(struct inode *inode, struct file *file)
 {
 	/*

@@ -676,6 +803,7 @@ static int kallsyms_open(struct inode *inode, struct file *file)
 	iter->show_value = kallsyms_show_value();
 	return 0;
 }
+#endif /* CONFIG_FG_KASLR */
 
 #ifdef	CONFIG_KGDB_KDB
 const char *kdb_walk_kallsyms(loff_t *pos)

2.20.1

[...]

[...]

Oop, nice catch. It seems the list would need to be walked on s_stop.

i.e. sub-sort by visibility?

I wonder, instead, if sorting should be just done once per module load/unload? That would make the performance and memory management easier too.

Kees Cook

My first solution (just don't show kallsyms at all for non-root) is looking better and better :). But seriously, I will rewrite this one with something like this, but I think we are going to need another close look to see if sidechannel issues still exist with the new implementation. Hopefully Jann can take another look then.

I've been thinking about something like the below instead - I was thinking that there was no reason to sort kallsyms at all, so instead I just randomly shuffle an index list. Do you see any issues with this approach? (I guess I need to rename my functions at least...)

From 2e8eb63c957f469af047dd4b056e54aa93f6fe35 Mon Sep 17 00:00:00 2001
From: Kristen Carlson Accardi <[email protected]>
Date: Mon, 3 Feb 2020 12:06:44 -0800
Subject: [PATCH 1/2] kallsyms: Hide layout

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

---
 kernel/kallsyms.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)

index 16c8c605f4b0..7e4939b9ed61 100644
@@ -25,6 +25,7 @@
 #include <linux/filter.h>
 #include <linux/ftrace.h>
 #include <linux/compiler.h>
+#include <linux/list_sort.h>
 
 /*
  * These will be re-linked against their real values

@@ -446,6 +447,17 @@ struct kallsym_iter {
 	int show_value;
 };
 
+struct kallsyms_iter_list {
+	struct kallsym_iter iter;
+	struct list_head next;
+};
+
+struct kallsyms_sorted_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)
 {

@@ -660,6 +672,110 @@ int kallsyms_show_value(void)
 	}
 }
 
+static void *sorted_start(struct seq_file *m, loff_t *pos)
+{
+	struct kallsyms_sorted_iter *s_iter = m->private;
+
+	if (*pos >= s_iter->total_syms)
+		return NULL;
+
+	return s_start(m, &s_iter->shuffled_index[*pos]);
+}
+
+static void *sorted_next(struct seq_file *m, void *p, loff_t *pos)
+{
+	struct kallsyms_sorted_iter *s_iter = m->private;
+
+	(*pos)++;
+
+	if (*pos >= s_iter->total_syms)
+		return NULL;
+
+	if (!update_iter(m->private, s_iter->shuffled_index[*pos]))
+		return NULL;
+
+	return p;
+}
+
+static const struct seq_operations kallsyms_sorted_op = {
+	.start = sorted_start,
+	.next = sorted_next,
+	.stop = s_stop,
+	.show = s_show
+};
+
+/*
+ * shuffle_text_list()
+ * Use a Fisher Yates algorithm to shuffle a list of text sections.
+ */
+static void shuffle_index_list(loff_t *indexes, int 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;
+	}
+}
+
+#if defined(CONFIG_FG_KASLR)
+/*
+ * When fine grained kaslr is enabled, we need to
+ * print out the symbols sorted by name rather than by
+ * by address, because this reveals the randomization order.
+ */
+static int kallsyms_open(struct inode *inode, struct file *file)
+{
+	loff_t pos;
+	struct kallsyms_sorted_iter *sorted_iter;
+	struct kallsym_iter iter;
+
+	/*
+	 * 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))
+			break;
+		pos++;
+	} while (1);
+
+	/*
+	 * add storage space for an array of loff_t equal to the size
+	 * of the total number of symbols we need to print
+	 */
+	sorted_iter = __seq_open_private(file, &kallsyms_sorted_op,
+					 sizeof(*sorted_iter) +
+					 (sizeof(pos) * pos));
+	if (!sorted_iter)
+		return -ENOMEM;
+
+	reset_iter(&sorted_iter->iter, 0);
+	sorted_iter->iter.show_value = kallsyms_show_value();
+	sorted_iter->total_syms = pos;
+
+	/*
+	 * initialize the array with all possible pos values, then
+	 * shuffle the array so that the values will display in a

random
+ * order.
+ */
+ for (pos = 0; pos < sorted_iter->total_syms; pos++)
+ sorted_iter->shuffled_index[pos] = pos;
+
+ shuffle_index_list(sorted_iter->shuffled_index, sorted_iter-

+
+ return 0;
+}
+#else
static int kallsyms_open(struct inode *inode, struct file *file) {
/*
@@ -676,6 +792,7 @@ static int kallsyms_open(struct inode *inode, struct file *file)
iter->show_value = kallsyms_show_value(); return 0;
}
+#endif /* CONFIG_FG_KASLR */

#ifdef CONFIG_KGDB_KDB
const char *kdb_walk_kallsyms(loff_t *pos)

2.20.1

I'll happily review and test again ... but since you've made substantive changes, you should drop these tags until I do.

FWIW I think random order is a good idea. Do you shuffle once? Or every time somebody opens /proc/kallsyms?

-Tony

Will do - thanks! If nobody thinks this is a horrible direction, I'll clean up this patch and submit it with the rest as part of v4.

I am shuffling every single time that somebody opens /proc/kallsyms - this is because it's possible that somebody has loaded modules or bpf stuff and there may be new/different symbols to display.

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.

---
 arch/x86/Makefile |  5 +++
 init/Kconfig      | 12 +++++++
 kernel/kallsyms.c |  2 +-
 kernel/module.c   | 81 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 99 insertions(+), 1 deletion(-)

index 00e378de8bc0..0f2dbc46eb5c 100644
@@ -51,6 +51,11 @@ ifdef CONFIG_X86_NEED_RELOCS
         LDFLAGS_vmlinux := --emit-relocs --discard-none
 endif
 
+ifndef CONFIG_FG_KASLR
+	ifdef CONFIG_MODULE_FG_KASLR
+		KBUILD_CFLAGS_MODULE += -ffunction-sections
+	endif
+endif
 #
 # Prevent GCC from generating any FP code by mistake.
 #

index e29c032e4d66..87706a08a2ca 100644
@@ -1994,6 +1994,7 @@ config FG_KASLR
 	bool "Function Granular Kernel Address Space Layout Randomization"
 	depends on $(cc-option, -ffunction-sections)
 	depends on ARCH_HAS_FG_KASLR
+	select MODULE_FG_KASLR
 	default n
 	help
 	  This option improves the randomness of the kernel text

@@ -2278,6 +2279,17 @@ config UNUSED_KSYMS_WHITELIST
 	  one per line. The path can be absolute, or relative to the kernel
 	  source tree.
 
+config MODULE_FG_KASLR
+	depends on $(cc-option, -ffunction-sections)
+	bool "Module Function Granular Layout Randomization"
+	help
+	  This option randomizes the module text section by reordering the text
+	  section by function at module load time. In order to use this
+	  feature, the module must have been compiled with the
+	  -ffunction-sections compiler flag.
+
+	  If unsure, say N.
+
 endif # MODULES
 
 config MODULES_TREE_LOOKUP

index df2b20e1b7f2..da65593bffc7 100644
@@ -761,7 +761,7 @@ int get_all_symbol_name(void *data, const char *name, struct module *mod,
 	return 0;
 }
 
-#if defined(CONFIG_FG_KASLR)
+#if defined(CONFIG_FG_KASLR) || defined(CONFIG_MODULE_FG_KASLR)
 /*
  * When fine grained kaslr is enabled, we need to
  * print out the symbols sorted by name rather than by

2.20.1

I've built and booted this successfully with both GCC/bfd and Clang/lld:

gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
GNU ld (GNU Binutils for Ubuntu) 2.34

clang version 11.0.0 (https://github.com/llvm/llvm-project.git c32d695b099109118dbd50dd697fffe23cd9a529) LLD 11.0.0 (https://github.com/llvm/llvm-project.git c32d695b099109118dbd50dd697fffe23cd9a529)

Clang + objtool is a bit noisy, but I haven't investigated why:
kernel/panic.o: warning: objtool: .text.nmi_panic: unexpected end of section kernel/panic.o: warning: objtool: .text.__warn_printk: unexpected end of section kernel/cred.o: warning: objtool: .text.exit_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.get_task_cred: unexpected end of section kernel/cred.o: warning: objtool: .text.cred_alloc_blank: unexpected end of section kernel/cred.o: warning: objtool: .text.abort_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.prepare_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.copy_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.override_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.revert_creds: unexpected end of section kernel/cred.o: warning: objtool: .text.prepare_kernel_cred: unexpected end of section

And when interacting with my orphan-section series[1], this patch is needed to keep from getting A LOT of warnings. ;)

index af3d004d9a7e..de687ffa4966 100644
@@ -57,9 +57,14 @@ ifndef CONFIG_FG_KASLR
 	endif
 endif
 
+ifndef CONFIG_FG_KASLR
 # We never want expected sections to be placed heuristically by the
 # linker. All sections should be explicitly named in the linker script.
+# However, without a way to provide a wildcard mapping from input
+# sections named .text.* to identically named output sections, this
+# can only be used with FGKASLR is disabled.
 LDFLAGS_vmlinux += --orphan-handling=warn
+endif
 
 #
 # Prevent GCC from generating any FP code by mistake.

[1] https://lore.kernel.org/lkml/[email protected]/

Kees Cook