Skip to contentSkip to conversation

bpf: KUnit-based soundness tests for tnums

PATCH In review Langston Barrett 2 participants 2 messages Apr 30, 2022 – May 10, 2022 BPF

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: KUnit-based soundness tests for tnums

Add tests that check that each binary operation on tnums is a valid abstraction of the corresponding operation on u64s. This soundness condition is an important part of the security of eBPF.

---

I also made sure that these tests are meaningful by changing the tnum operations or test conditions and ensuring that they fail when such erroneous modifications are made.

This is my first time submitting a kernel patch. I've read through the documentation on doing so, but apologies in advance if I've missed something. Thank you very much for your time.

 kernel/bpf/Kconfig     |   7 ++
 kernel/bpf/Makefile    |   2 +
 kernel/bpf/tnum_test.c | 208 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 217 insertions(+)
 create mode 100644 kernel/bpf/tnum_test.c
kernel/bpf/Kconfig +7 -0
index d56ee177d5f8..c1a726f33193 100644
@@ -36,6 +36,13 @@ config BPF_SYSCALL
 	  Enable the bpf() system call that allows to manipulate BPF programs
 	  and maps via file descriptors.
 
+config BPF_TNUM_TEST
+	tristate "Enable soundness tests for BPF tnums" if !KUNIT_ALL_TESTS
+	depends on BPF_SYSCALL && KUNIT=y
+	default KUNIT_ALL_TESTS
+	help
+	  Enable KUnit-based soundness tests for BPF tnums.
+
 config BPF_JIT
 	bool "Enable BPF Just In Time compiler"
 	depends on BPF
kernel/bpf/Makefile +2 -0
index c1a9be6a4b9f..11d88798a538 100644
@@ -40,3 +40,5 @@ obj-$(CONFIG_BPF_PRELOAD) += preload/
 obj-$(CONFIG_BPF_SYSCALL) += relo_core.o
 $(obj)/relo_core.o: $(srctree)/tools/lib/bpf/relo_core.c FORCE
 	$(call if_changed_rule,cc_o_c)
+
+obj-$(CONFIG_BPF_TNUM_TEST) += tnum_test.o
kernel/bpf/tnum_test.c new file +208 -0

208 lines not on this page · raw message

Signature · 1 line
2.33.3
#1 lore raw
Quoted 71 lines · Langston Barrett

Add tests that check that each binary operation on tnums is a valid abstraction of the corresponding operation on u64s. This soundness condition is an important part of the security of eBPF.

---

I also made sure that these tests are meaningful by changing the tnum operations or test conditions and ensuring that they fail when such erroneous modifications are made.

This is my first time submitting a kernel patch. I've read through the documentation on doing so, but apologies in advance if I've missed something. Thank you very much for your time.

 kernel/bpf/Kconfig     |   7 ++
 kernel/bpf/Makefile    |   2 +
 kernel/bpf/tnum_test.c | 208 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 217 insertions(+)
 create mode 100644 kernel/bpf/tnum_test.c
kernel/bpf/Kconfig +7 -0
index d56ee177d5f8..c1a726f33193 100644
@@ -36,6 +36,13 @@ config BPF_SYSCALL
          Enable the bpf() system call that allows to manipulate BPF programs
          and maps via file descriptors.
 
+config BPF_TNUM_TEST
+       tristate "Enable soundness tests for BPF tnums" if !KUNIT_ALL_TESTS
+       depends on BPF_SYSCALL && KUNIT=y
+       default KUNIT_ALL_TESTS
+       help
+         Enable KUnit-based soundness tests for BPF tnums.
+
 config BPF_JIT
        bool "Enable BPF Just In Time compiler"
        depends on BPF
kernel/bpf/Makefile +2 -0
index c1a9be6a4b9f..11d88798a538 100644
@@ -40,3 +40,5 @@ obj-$(CONFIG_BPF_PRELOAD) += preload/
 obj-$(CONFIG_BPF_SYSCALL) += relo_core.o
 $(obj)/relo_core.o: $(srctree)/tools/lib/bpf/relo_core.c FORCE
        $(call if_changed_rule,cc_o_c)
+
+obj-$(CONFIG_BPF_TNUM_TEST) += tnum_test.o
kernel/bpf/tnum_test.c new file +15 -0
new file mode 100644
index 000000000000..168780b648ac
@@ -0,0 +1,208 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/* Soundness tests for tnums.
+ *
+ * Its important that tnums (and other BPF verifier analyses) soundly
+ * overapproximate the runtime values of registers. If they fail to do so, then
+ * kernel memory corruption may result (see e.g., CVE-2020-8835 and
+ * CVE-2021-3490 for examples where unsound bounds tracking led to exploitable
+ * bugs).
+ *
+ * The implementations of some tnum arithmetic operations have been proven
+ * sound, see "Sound, Precise, and Fast Abstract Interpretation with Tristate
+ * Numbers" (https://arxiv.org/abs/2105.05398). These tests corroborate these
+ * results on actual machine hardware, protect against regressions if the
+ * implementations change, and provide a template for testing new abstract
+ * operations.

kernel/bpf/tnum_test.c line 25

Quoted 10 lines
kernel/bpf/tnum_test.c new file +10 -0
+ */
+
+#include <kunit/test.h>
+#include <linux/tnum.h>
+
+/* Some number of test cases, particular values not super important but chosen
+ * to be most likely to trigger edge cases.
+ */
+static u64 interesting_ints[] = { S64_MIN, S32_MIN, -1,             0,
+                                 1,       2,       U32_MAX, U64_MAX };

Frankly I don't see how running the same test over and over again will help us discover bugs or catch a regression. Sorry not applying this.