Compile-time stack frame pointer validation

In discussions around the live kernel patching consistency model RFC [1], Peter and Ingo correctly pointed out that stack traces aren't reliable. And as Ingo said, there's no "strong force" which ensures we can rely on them.

So I've been thinking about how to fix that. My goal is to eventually make stack traces reliable. Or at the very least, to be able to detect at runtime when a given stack trace *might* be unreliable. But improved stack traces would broadly benefit the entire kernel, regardless of the outcome of the live kernel patching consistency model discussions.

This patch set is just the first in a series of proposed stack trace reliability improvements. Future proposals will include runtime stack reliability checking, as well as compile-time and runtime DWARF validations.

As far as I can tell, there are two main obstacles which prevent frame pointer based stack traces from being reliable:

1) Missing frame pointer logic: currently, most assembly functions don't set up the frame pointer.

2) Interrupts: if a function is interrupted before it can save and set up the frame pointer, its caller won't show up in the stack trace.

This patch set aims to remove the first obstacle by enforcing that all asm functions honor CONFIG_FRAME_POINTER. This is done with a new stackvalidate host tool which is automatically run for every compiled .S file and which validates that every asm function does the proper frame pointer setup.

Also, to make sure somebody didn't forget to annotate their callable asm code as a function, flag an error for any return instructions which are hiding outside of a function. In almost all cases, return instructions are part of callable functions and should be annotated as such so that we can validate their frame pointer usage. A whitelist mechanism exists for those few return instructions which are not actually in callable code.

It currently only supports x86_64. It *almost* supports x86_32, but the stackvalidate code doesn't yet know how to deal with 32-bit REL relocations for the return whitelists. I tried to make the code generic so that support for other architectures can be plugged in pretty easily.

As a first step, all reported non-compliances result in warnings. Right now I'm seeing 200+ warnings. Once we get them all cleaned up, we can change the warnings to build errors so the asm code can stay clean.

The patches are based on linux-next. Patch 1 adds the stackvalidate host tool. Patch 2 adds some helper macros for asm functions so that they can comply with stackvalidate.

[1] http://lkml.kernel.org/r/[email protected]

v2:
- Fixed memory leaks reported by Petr Mladek

Josh Poimboeuf (2):
x86, stackvalidate: Compile-time stack frame pointer validation x86, stackvalidate: Add asm frame pointer setup macros

 MAINTAINERS                           |   6 +
 arch/Kconfig                          |   4 +
 arch/x86/Kconfig                      |   1 +
 arch/x86/Makefile                     |   6 +-
 arch/x86/include/asm/func.h           |  82 ++++++++
 lib/Kconfig.debug                     |  11 ++
 scripts/Makefile                      |   1 +
 scripts/Makefile.build                |  22 ++-
 scripts/stackvalidate/Makefile        |  17 ++
 scripts/stackvalidate/arch-x86.c      | 134 +++++++++++++
 scripts/stackvalidate/arch.h          |  10 +
 scripts/stackvalidate/elf.c           | 352 ++++++++++++++++++++++++++++++++++
 scripts/stackvalidate/elf.h           |  56 ++++++
 scripts/stackvalidate/list.h          | 217 +++++++++++++++++++++
 scripts/stackvalidate/stackvalidate.c | 226 ++++++++++++++++++++++
 15 files changed, 1142 insertions(+), 3 deletions(-)
 create mode 100644 arch/x86/include/asm/func.h
 create mode 100644 scripts/stackvalidate/Makefile
 create mode 100644 scripts/stackvalidate/arch-x86.c
 create mode 100644 scripts/stackvalidate/arch.h
 create mode 100644 scripts/stackvalidate/elf.c
 create mode 100644 scripts/stackvalidate/elf.h
 create mode 100644 scripts/stackvalidate/list.h
 create mode 100644 scripts/stackvalidate/stackvalidate.c

2.1.0

Frame pointer based stack traces aren't always reliable. One big reason is that most asm functions don't set up the frame pointer.

Fix that by enforcing that all asm functions honor CONFIG_FRAME_POINTER. This is done with a new stackvalidate host tool which is automatically run for every compiled .S file and which validates that every asm function does the proper frame pointer setup.

Also, to make sure somebody didn't forget to annotate their callable asm code as a function, flag an error for any return instructions which are hiding outside of a function. In almost all cases, return instructions are part of callable functions and should be annotated as such so that we can validate their frame pointer usage. A whitelist mechanism exists for those few return instructions which are not actually in callable code.

It currently only supports x86_64. It *almost* supports x86_32, but the stackvalidate code doesn't yet know how to deal with 32-bit REL relocations for the return whitelists. I tried to make the code generic so that support for other architectures can be plugged in pretty easily.

As a first step, all reported non-compliances result in warnings. Right now I'm seeing 200+ warnings. Once we get them all cleaned up, we can change the warnings to build errors so the asm code can stay clean.

---
 MAINTAINERS                           |   6 +
 arch/Kconfig                          |   4 +
 arch/x86/Kconfig                      |   1 +
 arch/x86/Makefile                     |   6 +-
 lib/Kconfig.debug                     |  11 ++
 scripts/Makefile                      |   1 +
 scripts/Makefile.build                |  22 ++-
 scripts/stackvalidate/Makefile        |  17 ++
 scripts/stackvalidate/arch-x86.c      | 134 +++++++++++++
 scripts/stackvalidate/arch.h          |  10 +
 scripts/stackvalidate/elf.c           | 352 ++++++++++++++++++++++++++++++++++
 scripts/stackvalidate/elf.h           |  56 ++++++
 scripts/stackvalidate/list.h          | 217 +++++++++++++++++++++
 scripts/stackvalidate/stackvalidate.c | 226 ++++++++++++++++++++++
 14 files changed, 1060 insertions(+), 3 deletions(-)
 create mode 100644 scripts/stackvalidate/Makefile
 create mode 100644 scripts/stackvalidate/arch-x86.c
 create mode 100644 scripts/stackvalidate/arch.h
 create mode 100644 scripts/stackvalidate/elf.c
 create mode 100644 scripts/stackvalidate/elf.h
 create mode 100644 scripts/stackvalidate/list.h
 create mode 100644 scripts/stackvalidate/stackvalidate.c

index b99e5b8..86258e6 100644
@@ -9365,6 +9365,12 @@ L:	[email protected]
 S:	Supported
 F:	Documentation/stable_kernel_rules.txt
 
+STACK VALIDATION
+M:	Josh Poimboeuf <[email protected]>
+S:	Supported
+F:	scripts/stackvalidate/
+F:	arch/x86/include/asm/func.h
+
 STAGING SUBSYSTEM
 M:	Greg Kroah-Hartman <[email protected]>
 T:	git git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging.git

index a65eafb..9e7e388 100644
@@ -499,6 +499,10 @@ config ARCH_HAS_ELF_RANDOMIZE
 	  - arch_mmap_rnd()
 	  - arch_randomize_brk()
 
+config HAVE_STACK_VALIDATION
+	bool
+
+
 #
 # ABI hall of shame
 #

index 9cee995..ed41a76 100644
@@ -144,6 +144,7 @@ config X86
 	select ACPI_LEGACY_TABLES_LOOKUP if ACPI
 	select X86_FEATURE_NAMES if PROC_FS
 	select SRCU
+	select HAVE_STACK_VALIDATION if FRAME_POINTER && X86_64
 
 config INSTRUCTION_DECODER
 	def_bool y

index 2fda005..72f2f04 100644
@@ -171,9 +171,13 @@ KBUILD_CFLAGS += $(call cc-option,-mno-avx,)
 KBUILD_CFLAGS += $(mflags-y)
 KBUILD_AFLAGS += $(mflags-y)
 
-archscripts: scripts_basic
+archscripts: scripts_basic $(objtree)/arch/x86/lib/inat-tables.c
 	$(Q)$(MAKE) $(build)=arch/x86/tools relocs
 
+# this file is needed early by scripts/stackvalidate
+$(objtree)/arch/x86/lib/inat-tables.c:
+	$(Q)$(MAKE) $(build)=arch/x86/lib $@
+
 ###
 # Syscall table generation
 

index 8eaed3dd..b8a6884 100644
@@ -332,6 +332,17 @@ config FRAME_POINTER
 	  larger and slower, but it gives very useful debugging information
 	  in case of kernel bugs. (precise oopses/stacktraces/warnings)
 
+
+config STACK_VALIDATION
+	bool "Enable kernel stack validation"
+	depends on HAVE_STACK_VALIDATION
+	default y
+	help
+	  Add compile-time validations which help make kernel stack traces more
+	  reliable.  This includes checks to ensure that assembly functions
+	  save, update and restore the frame pointer or the back chain pointer.
+
+
 config DEBUG_FORCE_WEAK_PER_CPU
 	bool "Force weak per-cpu definitions"
 	depends on DEBUG_KERNEL

index 2016a64..c882a91 100644
@@ -37,6 +37,7 @@ subdir-y                     += mod
 subdir-$(CONFIG_SECURITY_SELINUX) += selinux
 subdir-$(CONFIG_DTC)         += dtc
 subdir-$(CONFIG_GDB_SCRIPTS) += gdb
+subdir-$(CONFIG_STACK_VALIDATION) += stackvalidate
 
 # Let clean descend into subdirs
 subdir-	+= basic kconfig package

index 01df30a..3b05833 100644
@@ -253,6 +253,24 @@ define rule_cc_o_c
 	mv -f $(dot-target).tmp $(dot-target).cmd
 endef
 
+ifdef CONFIG_STACK_VALIDATION
+stackvalidate = $(objtree)/scripts/stackvalidate/stackvalidate
+cmd_stackvalidate =							  \
+	case $(@) in							  \
+		arch/x86/purgatory/*) ;;				  \
+		*) $(stackvalidate) "$(@)"; \
+	esac;
+endif
+
+define rule_as_o_S
+	$(call echo-cmd,as_o_S) $(cmd_as_o_S);				  \
+	$(cmd_stackvalidate)						  \
+	scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,as_o_S)' >    \
+	                                              $(dot-target).tmp;  \
+	rm -f $(depfile);						  \
+	mv -f $(dot-target).tmp $(dot-target).cmd
+endef
+
 # Built-in and composite module parts
 $(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
 	$(call cmd,force_checksrc)

@@ -290,8 +308,8 @@ $(obj)/%.s: $(src)/%.S FORCE
 quiet_cmd_as_o_S = AS $(quiet_modtag)  $@
 cmd_as_o_S       = $(CC) $(a_flags) -c -o $@ $<
 
-$(obj)/%.o: $(src)/%.S FORCE
-	$(call if_changed_dep,as_o_S)
+$(obj)/%.o: $(src)/%.S $(stackvalidate) FORCE
+	$(call if_changed_rule,as_o_S)
 
 targets += $(real-objs-y) $(real-objs-m) $(lib-y)
 targets += $(extra-y) $(MAKECMDGOALS) $(always)

new file mode 100644
index 0000000..6027ec4
@@ -0,0 +1,17 @@
+hostprogs-y := stackvalidate
+always := $(hostprogs-y)
+
+stackvalidate-objs := stackvalidate.o elf.o
+
+HOSTCFLAGS += -Werror
+HOSTLOADLIBES_stackvalidate := -lelf
+
+ifdef CONFIG_X86
+
+stackvalidate-objs += arch-x86.o
+
+HOSTCFLAGS_arch-x86.o := -I$(objtree)/arch/x86/lib/ -I$(srctree)/arch/x86/include/ -I$(srctree)/arch/x86/lib/
+
+$(obj)/arch-x86.o: $(srctree)/arch/x86/lib/insn.c $(srctree)/arch/x86/lib/inat.c $(srctree)/arch/x86/include/asm/inat_types.h $(srctree)/arch/x86/include/asm/inat.h $(srctree)/arch/x86/include/asm/insn.h $(objtree)/arch/x86/lib/inat-tables.c
+
+endif

new file mode 100644
index 0000000..3b91b1c
@@ -0,0 +1,10 @@
+#ifndef _ARCH_H_
+#define _ARCH_H_
+
+#include "elf.h"
+
+int arch_validate_function(struct elf *elf, struct symbol *func);
+int arch_is_return_insn(struct elf *elf, unsigned long addr,
+			unsigned int maxlen, unsigned int *len);
+
+#endif /* _ARCH_H_ */

2.1.0

Add some helper macros for asm functions so that they can comply with stackvalidate.

The FUNC_ENTER and FUNC_RETURN macros help asm functions save, set up, and restore frame pointers.

The RET_NOVALIDATE and FILE_NOVALIDATE macros can be used to whitelist the few locations which need a return instruction outside of a callable function.

---
 arch/x86/include/asm/func.h | 82 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)
 create mode 100644 arch/x86/include/asm/func.h

new file mode 100644
index 0000000..ae84196
@@ -0,0 +1,82 @@
+#ifndef _ASM_X86_FUNC_H
+#define _ASM_X86_FUNC_H
+
+#include <linux/linkage.h>
+#include <asm/dwarf2.h>
+#include <asm/asm.h>
+
+.macro FUNC_ENTER_NO_FP name
+	ENTRY(\name)
+	CFI_STARTPROC
+	CFI_DEF_CFA _ASM_SP, __ASM_SEL(4, 8)
+.endm
+
+.macro FUNC_RETURN_NO_FP name
+	CFI_DEF_CFA _ASM_SP, __ASM_SEL(4, 8)
+	__ASM_SIZE(ret)
+	CFI_ENDPROC
+	ENDPROC(\name)
+.endm
+
+#ifdef CONFIG_FRAME_POINTER
+
+.macro FUNC_ENTER_FP name
+	FUNC_ENTER_NO_FP \name
+	__ASM_SIZE(push, _cfi) %_ASM_BP
+	CFI_REL_OFFSET _ASM_BP, 0
+	_ASM_MOV %_ASM_SP, %_ASM_BP
+	CFI_DEF_CFA_REGISTER _ASM_BP
+.endm
+
+.macro FUNC_RETURN_FP name
+	__ASM_SIZE(pop, _cfi) %_ASM_BP
+	CFI_RESTORE _ASM_BP
+	FUNC_RETURN_NO_FP \name
+.endm
+
+/*
+ * Every callable asm function should be bookended with FUNC_ENTER and
+ * FUNC_RETURN.  They do proper frame pointer and DWARF CFI setups in order to
+ * achieve more reliable stack traces.
+ *
+ * For the sake of simplicity and correct DWARF annotations, use of the macros
+ * requires that the return instruction comes at the end of the function.
+ */
+#define FUNC_ENTER(name) FUNC_ENTER_FP name
+#define FUNC_RETURN(name) FUNC_RETURN_FP name
+
+/*
+ * RET_NOVALIDATE tells the stack validation script to whitelist the return
+ * instruction immediately after the macro.  Only use it if you're completely
+ * sure you need a return instruction outside of a callable function.
+ * Otherwise, if the code can be called and you haven't annotated it with
+ * FUNC_ENTER/FUNC_RETURN, it will break stack trace reliability.
+ */
+.macro RET_NOVALIDATE
+	163:
+	.pushsection __stackvalidate_whitelist_ret, "ae"
+	_ASM_ALIGN
+	.long 163b - .
+	.popsection
+.endm
+
+/*
+ * FILE_NOVALIDATE is like RET_NOVALIDATE except it whitelists the entire file.
+ * Use with extreme caution or you will silently break stack traces.
+ */
+.macro FILE_NOVALIDATE
+	.pushsection __stackvalidate_whitelist_file, "ae"
+	.long 0
+	.popsection
+.endm
+
+#else /* !FRAME_POINTER */
+
+#define FUNC_ENTER(name) FUNC_ENTER_NO_FP name
+#define FUNC_RETURN(name) FUNC_RETURN_NO_FP name
+#define RET_NOVALIDATE
+#define FILE_NOVALIDATE
+
+#endif /* FRAME_POINTER */
+
+#endif /* _ASM_X86_FUNC_H */

2.1.0

Yeah, the separated pushq_cfi and pushl_cfi macros aren't really necessary. I'm guessing they were made separate in order to have a consistent naming interface with movq_cfi and movl_cfi.

I'm not sure about which way is better. But I can replace them with new push_cfi and pop_cfi macros if you like.

Josh