Compile-time stack frame pointer validation

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.

Quoted 3 lines · Josh Poimboeuf

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

Quoted 4 lines

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.

Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to also process the output of GCC with this tool? To both double check GCC and to give the tool more input?

Quoted 4 lines · Peter Zijlstra

Quoted 3 lines · Josh Poimboeuf

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

Quoted 8 lines

Quoted 4 lines

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.

Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to also process the output of GCC with this tool? To both double check GCC and to give the tool more input?

I tried that, but I discovered that gcc's usage of frame pointers would be a lot harder to validate. It only sets up the frame pointer in code paths which have call instructions. There are a lot of functions which have conditional jumps at the beginning which can jump straight to a return instruction without first doing the frame pointer setup.

Quoted 14 lines · Josh Poimboeuf

Quoted 12 lines · Peter Zijlstra

Quoted 7 lines · Josh Poimboeuf

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.

Would it make sense (maybe as an additional CONFIG_*_DEBUG thing) to also process the output of GCC with this tool? To both double check GCC and to give the tool more input?

Quoted 5 lines

I tried that, but I discovered that gcc's usage of frame pointers would be a lot harder to validate. It only sets up the frame pointer in code paths which have call instructions. There are a lot of functions which have conditional jumps at the beginning which can jump straight to a return instruction without first doing the frame pointer setup.

Hmm, would not such code break your patching?

Quoted 6 lines

Quoted 5 lines

I tried that, but I discovered that gcc's usage of frame pointers would be a lot harder to validate. It only sets up the frame pointer in code paths which have call instructions. There are a lot of functions which have conditional jumps at the beginning which can jump straight to a return instruction without first doing the frame pointer setup.

Quoted 1 line

Hmm, would not such code break your patching?

No, because we'll also do some runtime stack validation (which will be a future patch set). If we detect preemption or an irq frame on the stack, we'll assume the stack is unreliable and delay the patching of the task (*).

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.

Signed-off-by Josh Poimboeuf <[email protected]>

scripts/stackvalidate/arch-x86.c new file +50 -0

new file mode 100644
index 0000000..fbc0756
+/*
+ * arch_validate_function() - Ensures the given asm function saves, sets up,
+ * and restores the frame pointer.
+ *
+ * The frame pointer prologue/epilogue should look something like:
+ *
+ *   push %rbp
+ *   mov %rsp, %rbp
+ *   [ function body ]
+ *   pop %rbp
+ *   ret
+ *
+ * Return value:
+ *   -1: bad instruction
+ *    1: missing frame pointer logic
+ *    0: validation succeeded
+ */
+int arch_validate_function(struct elf *elf, struct symbol *func)
+{
+	struct insn insn;
+	unsigned long addr, length;
+	int push, mov, pop, ret, x86_64;
+
+	push = mov = pop = ret = 0;
+
+	x86_64 = is_x86_64(elf);
+	if (x86_64 == -1)
+		return -1;
+
+	for (addr = func->start; addr < func->end; addr += length) {
+		insn_init(&insn, (void *)addr, func->end - addr, x86_64);
+		insn_get_length(&insn);
+		length = insn.length;
+		insn_get_opcode(&insn);
+		if (!length || !insn.opcode.got) {
+			WARN("%s+0x%lx: bad instruction", func->name,
+			     addr - func->start);
+			return -1;
+		}
+
+		switch (insn.opcode.bytes[0]) {
+		case 0x55:
+			if (!insn.rex_prefix.nbytes)
+				/* push bp */
+				push++;
+			break;
+		case 0x5d:
+			if (!insn.rex_prefix.nbytes)
+				/* pop bp */
+				pop++;

scripts/stackvalidate/arch-x86.c new file +11 -0

+		return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * arch_is_return_insn() - Determines whether the instruction at the given
+ * address is a return instruction.  Also returns the instruction length in
+ * *len.
+ *

scripts/stackvalidate/arch.h new file +10 -0

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_ */

scripts/stackvalidate/elf.c new file +0 -0

new file mode 100644
index 0000000..7879a0f

scripts/stackvalidate/elf.c new file +22 -0

+static int elf_read_sections(struct elf *elf)
+{
+	Elf_Scn *s = NULL;
+	struct section *sec;
+	size_t shstrndx, sections_nr;
+	int i;
+
+	if (elf_getshdrnum(elf->elf, &sections_nr)) {
+		perror("elf_getshdrnum");
+		return -1;
+	}
+
+	if (elf_getshdrstrndx(elf->elf, &shstrndx)) {
+		perror("elf_getshdrstrndx");
+		return -1;
+	}
+
+	for (i = 0; i < sections_nr; i++) {
+		sec = malloc(sizeof(*sec));
+		if (!sec) {
+			perror("malloc");
+			return -1;

scripts/stackvalidate/elf.c new file +31 -0

+		}
+
+		sec->index = elf_ndxscn(s);
+
+		if (!gelf_getshdr(s, &sec->sh)) {
+			perror("gelf_getshdr");
+			return -1;
+		}
+
+		sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name);
+		if (!sec->name) {
+			perror("elf_strptr");
+			return -1;
+		}
+
+		sec->data = elf_getdata(s, NULL);
+		if (!sec->data) {
+			perror("elf_getdata");
+			return -1;
+		}
+
+		if (sec->data->d_off != 0 ||
+		    sec->data->d_size != sec->sh.sh_size) {
+			WARN("unexpected data attributes for %s", sec->name);
+			return -1;
+		}
+
+		sec->start = (unsigned long)sec->data->d_buf;
+		sec->end = sec->start + sec->data->d_size;
+
+		list_add_tail(&sec->list, &elf->sections);

scripts/stackvalidate/arch-x86.c line 83

Quoted 6 lines · Josh Poimboeuf

scripts/stackvalidate/arch-x86.c new file +6 -0

+		case 0x89:
+			insn_get_modrm(&insn);
+			if (insn.modrm.bytes[0] == 0xe5)
+				/* mov sp, bp */
+				mov++;
+			break;

I am a bit courious. You check 0x89 and 0x5e but I see the following in the disasembly:

48 89 e5 mov %rsp,%rbp

I wonder if 48 is just a prefix that is filtered by insn_get_opcode or what.

Sigh, I still need to learn a lot about assembly.

Quoted 4 lines

scripts/stackvalidate/arch-x86.c new file +4 -0

+		case 0xc3: /* ret */
+			ret++;
+			break;
+		}

scripts/stackvalidate/arch-x86.c line 92

Quoted 5 lines

scripts/stackvalidate/arch-x86.c new file +5 -0

+	}
+
+	if (push != 1 || mov != 1 || !pop || !ret || pop != ret) {
+		WARN("%s() is missing frame pointer logic.  Please use FUNC_ENTER.",
+		     func->name);

This looks quite weak condition to me. It accepts the instructions in any order and at any place.

Also livepatching will rely on having fentry before the prologue. Do you plan to add support for this ordering?

Quoted 10 lines

scripts/stackvalidate/elf.c new file +10 -0

+	for (i = 0; i < sections_nr; i++) {
+		sec = malloc(sizeof(*sec));
+		if (!sec) {
+			perror("malloc");
+			return -1;
+		}
+		memset(sec, 0, sizeof(*sec));
+
+		INIT_LIST_HEAD(&sec->symbols);
+		INIT_LIST_HEAD(&sec->relas);

scripts/stackvalidate/elf.c line 100

Quoted 5 lines

scripts/stackvalidate/elf.c new file +5 -0

+
+		s = elf_getscn(elf->elf, i);
+		if (!s) {
+			perror("elf_getscn");
+			return -1;

This is leaking "sec". It is not added to the list, so you could not free it later. The same problem is on many other locations.

scripts/stackvalidate/elf.c line 141

Quoted 8 lines

scripts/stackvalidate/elf.c new file +8 -0

+	/* sanity check, one more call to elf_nextscn() should return NULL */
+	if (elf_nextscn(elf->elf, s)) {
+		WARN("section entry mismatch");
+		return -1;
+	}
+
+	return 0;
+}

I basically ended here. I was rather curious how such a thing could get implemented than doing a proper review.