Fix a bug in ebpf verifier
Subsystems (4)
PATCH 1/1 Fix a bug in ebpf verifier
In find_equal_scalars(), it should not copy the reg->subreg_def, otherwise a bug will occur when the program flag has BPF_F_TEST_RND_HI32.
--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)
kernel/bpf/verifier.c +4 -0
@@ -15101,7 +15101,9 @@ static void find_equal_scalars(struct bpf_verifier_state *vstate,continue ;if ((!(reg->id &BPF_ADD_CONST ) && !(known_reg->id &BPF_ADD_CONST )) || reg->off == known_reg->off) { +s32 subreg_def = reg->subreg_def;copy_register_state (reg, known_reg); + reg->subreg_def = subreg_def; }else {s32 saved_off = reg->off;
@@ -15109,7 +15111,9 @@ static void find_equal_scalars(struct bpf_verifier_state *vstate,__mark_reg_known (&fake_reg, (s32 )reg->off - (s32 )known_reg->off);/* reg = known_reg; reg += delta */ +s32 subreg_def = reg->subreg_def;copy_register_state (reg, known_reg); + reg->subreg_def = subreg_def;/* * Must preserve off, id and add_const flag, * otherwise another find_equal_scalars() will be incorrect.
Signature · 1 line
2.7.4
Eduard Zingerman
maintainerQuoted 5 lines · lonial con
In
find_equal_scalars(), it should not copy thereg->subreg_def, otherwise a bug will occur when the program flag hasBPF_F_TEST_RND_HI32.Reported-by Lonial Con <[email protected]>Signed-off-by Lonial Con <[email protected]>---
Hello,
could you please write a selftest for this fix? (please let me know if you need some intro on BPF selftests).
[...]
Hi,
I have never written a selftest before. I wrote a simple POC to demonstrate this bug. This POC can crash the Linux kernel 6.6.50. I think the ebpf code in the POC will be helpful for writing a selftest.
Thanks,
Lonial Con
Quoted 16 lines · Eduard Zingerman <[email protected]> 于2024年9月11日周三 22:54写道:
Quoted 1 line · lonial con
In
find_equal_scalars(), it should not copy thereg->subreg_def,otherwise a bug will occur when the program flag has
BPF_F_TEST_RND_HI32.Quoted 4 lines
Reported-by Lonial Con <[email protected]>Signed-off-by Lonial Con <[email protected]>---
Hello,
could you please write a selftest for this fix? (please let me know if you need some intro on BPF selftests).
[...]
Eduard Zingerman
maintainerQuoted 4 lines · lonial con
I have never written a selftest before. I wrote a simple POC to demonstrate this bug. This POC can crash the Linux kernel 6.6.50. I think the ebpf code in the POC will be helpful for writing a selftest.
Well all depends on how familiar you want to get with selftests infrastructure :) Here is a promised intro. If you don't want to bother, please let me know, I can write the selftest. If you do want to bother, feel free to ask any questions.
***
Please find a minimal recipe allowing to compile and run selftests in a chroot at the bottom of this email. You would probably want to adjust it, e.g. setup a user matching your local user inside chroot and do a bind mount for sources directory etc.
After setting up the environment you will have to write the test.
BPF selftests reside in the following directory:
- tools/testing/selftests/bpf/
Nowadays we mostly add selftests to test_progs executable and use bpftool skeletons / libbpf to simplify maps and programs creation.
The files located under prog_tests/ directory are compiled as host programs, the files located under progs/ are compiled as BPF programs (and libbpf skeletons are generated for these programs). Skeletons generated for files from progs/ are used in tests declared in prog_tests/.
Your POC structure:
- sets up a few maps
- sets up data for ringbuf
- loads and runs BPF program
You can look at a selftests that have similar structure, e.g.:
- tools/testing/selftests/bpf/prog_tests/ringbuf.c
- tools/testing/selftests/bpf/progs/test_ringbuf.c
Interesting parts of the 'prog_tests/ringbuf.c':
// this includes skeleton generated by bpftool
#include "test_ringbuf.lskel.h"
static void ringbuf_subtest(void)
{
...
// use generated methods to setup maps and programs
skel = test_ringbuf_lskel__open();
...
err = test_ringbuf_lskel__load(skel);
// you can do bpf_prog_run here as well
}
// build system automatically wires up functions
// void test_*(void) as entry points for tests
// executed by test_progs binary
void test_ringbuf(void)
{
// needed for tests filtering, e.g. -t option for test_progs
if (test__start_subtest("ringbuf"))
ringbuf_subtest();
...
}*** chroot selftests build/run recipe follows ***
# First, setup the bullseye chroot
sudo /usr/sbin/debootstrap --variant=buildd --arch=amd64 bullseye bullseye-chroot/ http://deb.debian.org/debian
# provide {dev,proc} for chroot
sudo mount --rbind /dev ./bullseye-chroot/dev/
sudo mount --make-rslave ./bullseye-chroot/dev/
sudo mount -t proc proc ./bullseye-chroot/proc/# enter chroot sudo chroot ./bullseye-chroot
# Install build tools
apt install build-essential bc flex bison git libelf-dev libssl-dev \
docutils-common rsync curl zstd qemu-system-x86 sudo cmake \
libdw-dev lsb-release wget software-properties-common gnupg e2fsprogs
# Install fresh clang-18 snapshot, the llvm.sh sets up some repos curl https://apt.llvm.org/llvm.sh --output /tmp/llvm.sh bash /tmp/llvm.sh 18
apt install clang-tools-18
ln -s /usr/bin/clang-18 /usr/bin/clang
ln -s /usr/bin/llvm-strip-18 /usr/bin/llvm-strip
# that would be /root inside chroot cd $HOME
# Get and compile pahole, use instructions from:
# https://git.kernel.org/pub/scm/devel/pahole/pahole.git/about/
git clone https://git.kernel.org/pub/scm/devel/pahole/pahole.git
cd pahole
git submodule update --init --recursive
mkdir build
cd build
cmake -D__LIB=lib ..
make -j
# make it available system-wide ln -s $(realpath pahole) /usr/local/bin/
cd $HOME
git clone --depth=1 https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git
# Run vmtests, this should download rootfs, build kernel and tests, run test_verifier
# vmtest.sh would ask for root password to mount rootfs image cd bpf-next/tools/testing/selftests/bpf ./vmtest.sh -- ./test_verifier
# And now run test_progs
./vmtest.sh -- ./test_progs
# One can filter tests too
./vmtest.sh -- ./test_progs -t ringbuf
A message that is not in the archive (sent off-list or not yet received): CAH6SPwjoACNcNBWCjYauSMYCFOUAys10uH-xM6mF8_Q79D0Yow@mail.gmail.com
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Thanks,
Lonial Con
Quoted 134 lines · lonial con <[email protected]> 于2024年9月12日周四 21:31写道:
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Thanks,
Lonial ConQuoted 125 lines · Eduard Zingerman <[email protected]> 于2024年9月12日周四 12:31写道:
Quoted 4 lines · lonial con
I have never written a selftest before. I wrote a simple POC to demonstrate this bug. This POC can crash the Linux kernel 6.6.50. I think the ebpf code in the POC will be helpful for writing a selftest.
Well all depends on how familiar you want to get with selftests infrastructure :) Here is a promised intro. If you don't want to bother, please let me know, I can write the selftest. If you do want to bother, feel free to ask any questions.
***
Please find a minimal recipe allowing to compile and run selftests in a chroot at the bottom of this email. You would probably want to adjust it, e.g. setup a user matching your local user inside chroot and do a bind mount for sources directory etc.
After setting up the environment you will have to write the test.
BPF selftests reside in the following directory:
-tools/testing/selftests/bpf/Nowadays we mostly add selftests to
test_progsexecutable and use bpftool skeletons / libbpf to simplify maps and programs creation.The files located under prog_tests/ directory are compiled as host programs, the files located under progs/ are compiled as BPF programs (and libbpf skeletons are generated for these programs). Skeletons generated for files from progs/ are used in tests declared in prog_tests/.
Your POC structure:
- sets up a few maps
- sets up data for ringbuf
- loads and runs BPF programYou can look at a selftests that have similar structure, e.g.:
-tools/testing/selftests/bpf/prog_tests/ringbuf.c
-tools/testing/selftests/bpf/progs/test_ringbuf.cInteresting parts of the '
prog_tests/ringbuf.c':// this includes skeleton generated by bpftool #include "test_ringbuf.lskel.h" static void ringbuf_subtest(void) { ... // use generated methods to setup maps and programs skel = test_ringbuf_lskel__open(); ... err = test_ringbuf_lskel__load(skel); // you can do bpf_prog_run here as well } // build system automatically wires up functions // void test_*(void) as entry points for tests // executed by test_progs binary void test_ringbuf(void) { // needed for tests filtering, e.g. -t option for test_progs if (test__start_subtest("ringbuf")) ringbuf_subtest(); ... }*** chroot selftests build/run recipe follows ***
# First, setup the bullseye chroot
sudo/usr/sbin/debootstrap--variant=buildd --arch=amd64 bullseye bullseye-chroot/ http://deb.debian.org/debian# provide {dev,proc} for chroot sudo mount --rbind /dev ./bullseye-chroot/dev/ sudo mount --make-rslave ./bullseye-chroot/dev/ sudo mount -t proc proc ./bullseye-chroot/proc/# enter chroot sudo chroot ./bullseye-chroot# Install build tools
apt install build-essential bc flex bison git libelf-dev libssl-dev \
docutils-common rsync curl zstd qemu-system-x86 sudo cmake \
libdw-dev lsb-release wget software-properties-common gnupg e2fsprogs# Install fresh clang-18 snapshot, the
llvm.shsets up some repos curl https://apt.llvm.org/llvm.sh --output/tmp/llvm.shbash/tmp/llvm.sh18
apt install clang-tools-18
ln -s/usr/bin/clang-18/usr/bin/clang
ln -s/usr/bin/llvm-strip-18/usr/bin/llvm-strip# that would be /root inside chroot cd $HOME# Get and compile pahole, use instructions from:
# https://git.kernel.org/pub/scm/devel/pahole/pahole.git/about/
git clone https://git.kernel.org/pub/scm/devel/pahole/pahole.git
cd pahole
git submodule update --init --recursive
mkdir build
cd build
cmake -D__LIB=lib ..
make -j# make it available system-wide ln -s $(realpath pahole) /usr/local/bin/cd $HOME
git clone --depth=1 https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git# Run vmtests, this should download rootfs, build kernel and tests, run
test_verifier# vmtest.sh would ask for root password to mount rootfs image cd bpf-next/tools/testing/selftests/bpf ./vmtest.sh -- ./test_verifier# And now run
test_progs
./vmtest.sh -- ./test_progs# One can filter tests too
./vmtest.sh -- ./test_progs -t ringbuf
Eduard Zingerman
maintainerQuoted 5 lines · lonial con
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Ok, no problem.
Quoted 3 lines
Thanks,
Lonial Con
[...]
Eduard Zingerman
maintainerQuoted 5 lines · lonial con
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Please find the patch for test in the attachment.
Please submit a v2 as a patch-set of two parts:
- first patch: your fix
- second patch: my test
Also, please make sure to use up to date bpf-next kernel tree, your patch changes function find_equal_scalars(), this function was renamed to sync_linked_regs() some time ago.
So the updated fix should look like:
@@ -15349,8 +15349,12 @@ static void sync_linked_regs(struct bpf_verifier_state *vstate, struct bpf_reg_s
continue;
if ((!(reg->id & BPF_ADD_CONST) && !(known_reg->id & BPF_ADD_CONST)) ||
reg->off == known_reg->off) {
+ s32 saved_subreg_def = reg->subreg_def;
+
copy_register_state(reg, known_reg);
+ reg->subreg_def = saved_subreg_def;
} else {
+ s32 saved_subreg_def = reg->subreg_def;
s32 saved_off = reg->off;
fake_reg.type = SCALAR_VALUE;
@@ -15363,6 +15367,8 @@ static void sync_linked_regs(struct bpf_verifier_state *vstate, struct bpf_reg_s
* otherwise another sync_linked_regs() will be incorrect.
*/
reg->off = saved_off;
+ /* TODO: describe why */
+ reg->subreg_def = saved_subreg_def;
scalar32_min_max_add(reg, &fake_reg); scalar_min_max_add(reg, &fake_reg);
For illustrative purposes, you might refer to the test case in the commit message for the fix. (You can actually run it w/o KVM, it would be slower but otherwise should work). W/o your fix the test case is miscompiled as follows:
call %[bpf_ktime_get_ns]; call unknown
r0 &= 0x7fffffff; after verifier r0 &= 2147483647
w1 = w0; rewrites w1 = w0
if w0 < 10 goto +0; --------------> r11 = 794195110
r1 >>= 32; r11 <<= 32
r0 = r1; r1 |= r11
exit; if w0 < 0xa goto pc+0
r1 >>= 32
r0 = r1
exitLeaving return value undefined.
[...]
From a76a9debfacbca0f5eba2e271728ac16c6b84538 Mon Sep 17 00:00:00 2001
From: Eduard Zingerman <[email protected]>
Date: Thu, 12 Sep 2024 15:57:20 -0700
Subject: [PATCH bpf-next v1 2/2] selftests/bpf: verify that sync_linked_regs
preserves subreg_def
This test was added because of a bug in verifier.c:sync_linked_regs(), upon range propagation it destroyed subreg_def marks for registers. The test is written in a way to return an upper half of a register that is affected by range propagation and must have it's subreg_def preserved. This gives a return value of 0 and leads to undefined return value if subreg_def mark is not preserved.
--- .../selftests/bpf/progs/verifier_scalar_ids.c | 67 +++++++++++++++++++ 1 file changed, 67 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +67 -0
@@ -760,4 +760,71 @@ __naked void two_old_ids_one_cur_id(void) : __clobber_all); } +SEC ("socket" ) +/* Note the flag, see verifier.c:opt_subreg_zext_lo32_rnd_hi32() */ +__flag (BPF_F_TEST_RND_HI32) +__success +/* This test was added because of a bug in verifier.c:sync_linked_regs(), +* upon range propagation it destroyed subreg_def marks for registers. +* The subreg_def mark is used to decide whether zero extension instructions +* are needed when register is read. When BPF_F_TEST_RND_HI32 is set it +* also causes generation of statements to randomize upper halfs of +* read registers. +* +* The test is written in a way to return an upper half of a register +* that is affected by range propagation and must have it's subreg_def +* preserved. This gives a return value of 0 and leads to undefined +* return value if subreg_def mark is not preserved. + */ +__retval (0 ) +/* Check that verifier believes r1/r0 are zero at exit */ +__log_level(2) +__msg("4: (77) r1 >>= 32 ; R1_w=0") +__msg("5: (bf) r0 = r1 ; R0_w=0 R1_w=0") +__msg("6: (95) exit") +__msg("from 3 to 4") +__msg("4: (77) r1 >>= 32 ; R1_w=0") +__msg("5: (bf) r0 = r1 ; R0_w=0 R1_w=0") +__msg ("6: (95) exit" ) +/* Verify that statements to randomize upper half of r1 had not been +* generated. + */ +__xlated("call unknown") +__xlated("r0 &= 2147483647") +__xlated ("w1 = w0" ) +/* This is how disasm.c prints BPF_ZEXT_REG at the moment, x86 and arm +* are the only CI archs that do not need zero extension for subregs. + */ +#if !defined(__TARGET_ARCH_x86) && !defined(__TARGET_ARCH_arm64) +__xlated("w1 = w1") +#endif +__xlated("if w0 < 0xa goto pc+0") +__xlated("r1 >>= 32") +__xlated("r0 = r1") +__xlated("exit") +__naked void linked_regs_and_subreg_def (void ) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +/* make sure r0 is in 32-bit range, otherwise w1 = w0 won't +* assign same IDs to registers. +*/ +"r0 &= 0x7fffffff;" +/* link w1 and w0 via ID */ +"w1 = w0;" +/* 'if' statement propagates range info from w0 to w1, +* but should not affect w1->subreg_def property. +*/ +"if w0 < 10 goto +0;" +/* r1 is read here, on archs that require subreg zero +* extension this would cause zext patch generation. +*/ +"r1 >>= 32;" +"r0 = r1;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.46.0
Eduard Zingerman
maintainerQuoted 11 lines · Eduard Zingerman
Quoted 5 lines · lonial con
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Please find the patch for test in the attachment.
Please submit a v2 as a patch-set of two parts:
- first patch: your fix
- second patch: my test
Hi Lonial,
Do you plan to proceed with this fix?
[...]
Hi Eduard,
Sorry, I was on vacation recently and didn't reply to emails in time. Could you please submit this patch directly? Because I am on vacation and don't have my computer with me.
Thanks.
Quoted 20 lines · Eduard Zingerman <[email protected]> 于2024年9月24日周二 16:12写道:
Quoted 11 lines · Eduard Zingerman
Quoted 5 lines · lonial con
Hi,
I tried to build this environment, but it seems that it needs kvm support. For me, it is very troublesome to prepare a kvm environment. So could you please write this selftest?
Please find the patch for test in the attachment.
Please submit a v2 as a patch-set of two parts:
- first patch: your fix
- second patch: my testHi Lonial,
Do you plan to proceed with this fix?
[...]
Eduard Zingerman
maintainerQuoted 5 lines · lonial con
Hi Eduard,
Sorry, I was on vacation recently and didn't reply to emails in time. Could you please submit this patch directly? Because I am on vacation and don't have my computer with me.
Sure, thanks again for the fix.
Have a good vacation.