Compile-time stack frame pointer validation

In discussions around my 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 setup the frame pointer, its caller won't show up in the stack trace.

This patch set aims to fix the first problem 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] https://lkml.org/lkml/2015/2/9/475

Josh Poimboeuf (2):
x86, stackvalidate: Compile-time stack frame pointer validation
x86: 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           | 341 ++++++++++++++++++++++++++++++++++
 scripts/stackvalidate/elf.h           |  56 ++++++
 scripts/stackvalidate/list.h          | 217 ++++++++++++++++++++++
 scripts/stackvalidate/stackvalidate.c | 224 ++++++++++++++++++++++
 15 files changed, 1129 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

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

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           | 341 ++++++++++++++++++++++++++++++++++
 scripts/stackvalidate/elf.h           |  56 ++++++
 scripts/stackvalidate/list.h          | 217 ++++++++++++++++++++++
 scripts/stackvalidate/stackvalidate.c | 224 ++++++++++++++++++++++
 14 files changed, 1047 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 885be14..ac02138 100644
@@ -9329,6 +9329,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 e106898..89f9abf 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 2ea27da..c6ea994 100644
@@ -142,6 +142,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 5ba2d9c..9c91747 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 ea369dd..8671e38 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

[ ... snip ... ]

I haven't really gone through your patchset thoroughly yet, but I just wanted to make sure that you are aware of existing DWARF-based stack unwinder which exists for the kernel.

It's not merged in mainline (one of the reasons being disagreements about bugfixes between Jan and Linus), but we've been carrying it in SUSE kernels as an out-of-tree patch for quite some time, and it really makes stack dumps much more reliable and understandable.

You can see it for example here:

http://kernel.suse.com/cgit/kernel-source/tree/patches.suse/stack-unwind

(and some merge attempt failures due to disagreements between Jan and Linus, not really completely related to the actual code itself, in LKML archives).

Jiri Kosina
SUSE Labs

Thanks, that could be helpful. I also found a nice (currently only 32-bit) DWARF unwinder in arch/sh/kernel/dwarf.c.

The DWARF metadata has a reputation for being unreliable, but I have some ideas on how to improve it for future patch sets, with both compile-time and runtime validations.

Josh

That's putting it really mildly ...

The thing is, there's no chance in hell we can take any dwarf annotation based stack dump patches to mainline without first changing the fundamental dynamics of debug info quality: and I doubt we can do that, given that we suffer the dwarf debug info created by external tools which don't care much about occasionally incorrect debug info because nothing depends on it functionally.

The beauty of framepointers is:

- framepointers they are simple

- and if tooling breaks them, then actual _C code_ breaks: arguments on the stack are not accessible anymore and code crashes. That's a heck of a strong incentive not to mess up framepointers...

The big problem with Dwarf stack annotations on the other hand is that they are the 180 degress opposite of framepointers:

- dwarf annotations are complex

- if tooling breaks them, then no code breaks, nothing but debug output breaks. C code still works just fine. This is a heck of a weak incentive.

Having said all that, I like this particular patch-set because it IMHO shows the right attitude towards debug info: it does not trust it and does exactly the kind of checks that I think will improve stack trace quality in the long run, even with the very simple model of framepointers - for example inside assembly code.

We have experience with dwarf debug info quality in tools/perf/ as well, and "reliable" is not the word I'd use.

Here's a very quick grep of dwarf debug info related fixes in tools/perf/:

4093325f8297 perf probe: Fix crash in dwarf_getcfi_elf 9b118acae310 perf probe: Fix to handle aliased symbols in glibc b93b0967826a perf test: Fix dwarf unwind using libunwind. c6e5e9fbc3ea perf tools: Fix building error in x86_64 when dwarf unwind is on 082f96a93eb5 perf probe: Fix perf probe to find correct variable DIE 9a126728165e perf tests x86: Fix stack map lookup in dwarf unwind test b42dc32d4f91 perf tools: Fix dwarf unwind max_stack processing e08cfd4bda76 perf probe: Fix to find line information for probe list 0dbb1cac1dbd perf probe: Fix finder to find lines of given function a128405c6b40 perf probe: Fix line walker to check CU correctly 66a301c380d4 perf probe: Fix format specified for Dwarf_Off parameter 4046b8bb5ffa perf probe: Fix type searching
75ec5a245c77 perf probe: Fix to close dwarf when failing to analyze it fc6ceea04503 perf probe: Fix need_dwarf flag if lazy matching is used

(I'm sure there are both false positives and false negatives in that list)

and dwarf unwind isn't even the default for perf, you have to specify a weird option to make use of it so most users don't even know it's there.

That again is putting it way too mildly IMHO ...

Summary: framepointers are fine, but dwarf based backtraces were problematic in the past and we have trouble trusting them.

Thanks,

Ingo