Skip to contentSkip to conversation

Fix bpf_probe_read_user_str() overcopying

PATCH Superseded Daniel Xu 3 participants 7 messages Nov 16, 2020 – Nov 17, 2020

Subsystems (4)

v6 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Daniel Xu

author
#0 lore raw

v6 cover Fix bpf_probe_read_user_str() overcopying

6ae08ae3dea2 ("bpf: Add probe_read_{user, kernel} and probe_read_{user, kernel}_str helpers") introduced a subtle bug where bpf_probe_read_user_str() would potentially copy a few extra bytes after the NUL terminator.

This issue is particularly nefarious when strings are used as map keys, as seemingly identical strings can occupy multiple entries in a map.

This patchset fixes the issue and introduces a selftest to prevent future regressions.

v5 -> v6:
* zero-pad up to sizeof(unsigned long) after NUL

v4 -> v5:
* don't read potentially uninitialized memory

v3 -> v4:
* directly pass userspace pointer to prog
* test more strings of different length

v2 -> v3:
* set pid filter before attaching prog in selftest
* use long instead of int as bpf_probe_read_user_str() retval
* style changes

v1 -> v2:
* add Fixes: tag
* add selftest

Daniel Xu (2):
lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator selftest/bpf: Test bpf_probe_read_user_str() strips trailing bytes
after NUL

 lib/strncpy_from_user.c                       |  8 ++-
 .../bpf/prog_tests/probe_read_user_str.c      | 71 +++++++++++++++++++
 .../bpf/progs/test_probe_read_user_str.c      | 25 +++++++
 3 files changed, 102 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/probe_read_user_str.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_probe_read_user_str.c
Signature · 1 line
2.29.2
author
#1 lore raw

PATCH v6 1/2 lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator

do_strncpy_from_user() may copy some extra bytes after the NUL terminator into the destination buffer. This usually does not matter for normal string operations. However, when BPF programs key BPF maps with strings, this matters a lot.

A BPF program may read strings from user memory by calling the bpf_probe_read_user_str() helper which eventually calls do_strncpy_from_user(). The program can then key a map with the resulting string. BPF map keys are fixed-width and string-agnostic, meaning that map keys are treated as a set of bytes.

The issue is when do_strncpy_from_user() overcopies bytes after the NUL terminator, it can result in seemingly identical strings occupying multiple slots in a BPF map. This behavior is subtle and totally unexpected by the user.

This commit uses the proper word-at-a-time APIs to avoid overcopying.

Fixes 6ae08ae3dea2 ("bpf: Add probe_read_{user, kernel} and probe_read_{user, kernel}_str helpers")

---
Based on on-list discussion and some off-list discussion with Alexei, I'd like to propose the v4-style patch without the (*out & ~mask) bit.

We can't really zero out the rest of the buffer due to ABI issues. The bpf docs state for bpf_probe_read_user_str():

Quoted 2 lines

In case the string length is smaller than *size*, the target is not padded with further NUL bytes.

 lib/strncpy_from_user.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
lib/strncpy_from_user.c +6 -2
index e6d5fcc2cdf3..de084f04e50d 100644
@@ -35,17 +35,21 @@ static inline long do_strncpy_from_user(char *dst, const char __user *src,
 		goto byte_at_a_time;
 
 	while (max >= sizeof(unsigned long)) {
-		unsigned long c, data;
+		unsigned long c, data, mask;
 
 		/* Fall back to byte-at-a-time if we get a page fault */
 		unsafe_get_user(c, (unsigned long __user *)(src+res), byte_at_a_time);
 
-		*(unsigned long *)(dst+res) = c;
 		if (has_zero(c, &data, &constants)) {
 			data = prep_zero_mask(c, data, &constants);
 			data = create_zero_mask(data);
+			mask = zero_bytemask(data);
+			*(unsigned long *)(dst+res) = c & mask;
 			return res + find_zero(data);
 		}
+
+		*(unsigned long *)(dst+res) = c;
+
 		res += sizeof(unsigned long);
 		max -= sizeof(unsigned long);
 	}
Signature · 1 line
2.29.2
#2 lore raw

Re: [PATCH bpf v6 1/2] lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator

Quoted 4 lines · Daniel Xu

Based on on-list discussion and some off-list discussion with Alexei, I'd like to propose the v4-style patch without the (*out & ~mask) bit.

So I've verified that at least on x86-64, this doesn't really make code generation any worse, and I'm ok with the patch from that standpoint.

However, this was not what the discussion actually amended at as far as I'm concerned.

I mentioned that if BPF cares about the bytes past the end of the string, I want a *BIG COMMENT* about it. Yes, in strncpy_from_user() itself, but even more in the place that cares.

And no, that does not mean bpf_probe_read_user_str(). That function clearly doesn't care at all, and doesn't access anything past the end of the string. I want a comment in whatever code that accesses past the end of the string.

And your ABI point is actively misleading:

Quoted 5 lines

We can't really zero out the rest of the buffer due to ABI issues. The bpf docs state for bpf_probe_read_user_str():

Quoted 2 lines

In case the string length is smaller than *size*, the target is not padded with further NUL bytes.

This comment is actively wrong and misleading.

The code (after the patch) clearly *does* pad a bit with "further NUL bytes". It's just that it doesn't pad all the way to the end.

Where is the actual buffer zeroing done?

Because without the buffer zeroing, this whole patch is completely pointless. Which is why I want that comment, and I want a pointer to where that zeroing is done.

Really. You have two cases:

(a) the buffer isn't zeroed before the strncpy_from_user()

(b) the buffer is guaranteed to be zero before that

and in case (a), this patch is pointless, since the data after the string is already undefined.

And in case (b), I want to see a comment and a pointer to the code that actually does the zeroing.

HOWEVER. Look at bpf_probe_read_user_str_common(), and notice how it ALREADY does the zeroing of the buffer past the end, it's just that it only does it in the error case.

Why do you send this patch, instead of

(a) get rid of the pointless pre-zeroing

(b) change bpf_probe_read_user_str_common() to do

        int ret;
        u32 offset;

        ret = strncpy_from_user_nofault(dst, unsafe_ptr, size);
        offset = ret < 0 ? 0 : ret;
        memset(dst+offset, 0, size-offset);
        return ret;

which seems to be much simpler anyway. The comment you quote about "target is not padded with further NUL bytes" is clearly wrong anyway, since that error case *does* pad the target with NUL bytes, and always has.

So honestly, in this whole discussion, it seems rather clear to me that the bug has always been in bpf, not in strncpy_from_user(). The ABI comment you quote is clearly not true, and I can point to that existing bpf_probe_read_user_str_common() code itself:

        ret = strncpy_from_user_nofault(dst, unsafe_ptr, size);
        if (unlikely(ret < 0))
                memset(dst, 0, size);

as to why that is.

But guys, as mentioned, I'm willing to apply this patch, but only if you add some actually *correct* comments about the odd bpf use of this string, and point to where the pre-zeroing is done.

Linus

#3 lore raw

Re: [PATCH bpf v6 1/2] lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator

Quoted 4 lines · Linus Torvalds

So I've verified that at least on x86-64, this doesn't really make code generation any worse, and I'm ok with the patch from that standpoint.

.. looking closer, it will generate extra code on big-endian architectures and on alpha, because of the added "zero_bytemask()". But on the usual LE machines, zero_bytemask() will already be the same as "mask", so all it adds is that "and" operation with values it already had access to.

I don't think anybody cares about alpha and BE - traditional BE architectures have moved to LE anyway. And looking at the alpha word-at-a-time code, I don't even understand how it works at all.

Adding matt/rth/ivan to the cc, just so that maybe one of them can educate me on how that odd alpha zero_bytemask() could possibly work. The "2ul << .." part confuses me, I think it should be "1ul << ...".

I get the feeling that the alpha "2ul" constant might have come from the tile version, but in the tile version, the " __builtin_ctzl()" counts the leading zeroes to the top bit of any bytes in 'mask'. But the alpha version actually uses "find_zero(mask) * 8", so rather than have values of 7/15/23/... (for zero byte in byte 0/1/2/.. respectively), it has values 0/8/16/....

But it's entirely possible that I'm completely confused, and alpha does it right, and I'm just not understanding the code.

It's also possible that the "2ul" vs "1ul" case doesn't matter. because the extra bit is always going to mask the byte that is actually zero, so being one bit off in the result is a non-event. I think that is what may actually be going on.

Linus

#4 lore raw

Re: [PATCH bpf v6 1/2] lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator

Quoted 28 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

So I've verified that at least on x86-64, this doesn't really make code generation any worse, and I'm ok with the patch from that standpoint.

.. looking closer, it will generate extra code on big-endian architectures and on alpha, because of the added "zero_bytemask()". But on the usual LE machines, zero_bytemask() will already be the same as "mask", so all it adds is that "and" operation with values it already had access to.

I don't think anybody cares about alpha and BE - traditional BE architectures have moved to LE anyway. And looking at the alpha word-at-a-time code, I don't even understand how it works at all.

Adding matt/rth/ivan to the cc, just so that maybe one of them can educate me on how that odd alpha zero_bytemask() could possibly work. The "2ul << .." part confuses me, I think it should be "1ul << ...".

I get the feeling that the alpha "2ul" constant might have come from the tile version, but in the tile version, the " __builtin_ctzl()" counts the leading zeroes to the top bit of any bytes in 'mask'. But the alpha version actually uses "find_zero(mask) * 8", so rather than have values of 7/15/23/... (for zero byte in byte 0/1/2/.. respectively), it has values 0/8/16/....

Quoted 2 lines

But it's entirely possible that I'm completely confused, and alpha does it right, and I'm just not understanding the code.

No, you are right, it should be "1ul". Indeed, seems like it came from the tile version which looks incorrect either, BTW. The tile-gx ISA
(https://studylib.net/doc/18755547/tile-gx-instruction-set-architecture)
says that clz/ctz instructions count up to the first "1", not to the last "0", so the shift values in tile's zero_bytemask() are 0/8/16/... as well.

Quoted 4 lines

It's also possible that the "2ul" vs "1ul" case doesn't matter. because the extra bit is always going to mask the byte that is actually zero, so being one bit off in the result is a non-event. I think that is what may actually be going on.

Yes, looks like that.

Ivan.

author
#5 lore raw

Re: [PATCH bpf v6 1/2] lib/strncpy_from_user.c: Don't overcopy bytes after NUL terminator

In reply to Linus Torvalds

Hi Linus,

Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Daniel Xu

Based on on-list discussion and some off-list discussion with Alexei, I'd like to propose the v4-style patch without the (*out & ~mask) bit.

So I've verified that at least on x86-64, this doesn't really make code generation any worse, and I'm ok with the patch from that standpoint.

Quoted 6 lines

However, this was not what the discussion actually amended at as far as I'm concerned.

I mentioned that if BPF cares about the bytes past the end of the string, I want a *BIG COMMENT* about it. Yes, in strncpy_from_user() itself, but even more in the place that cares.

Sure, sorry. Will send another version with comments.

Quoted 4 lines

And no, that does not mean bpf_probe_read_user_str(). That function clearly doesn't care at all, and doesn't access anything past the end of the string. I want a comment in whatever code that accesses past the end of the string.

If I'm reading things right, that place is technically in kernel/bpf/hashtab.c:alloc_htab_elem. In line:

    memcpy(l_new->key, key, key_size);

where key_size is the width of the hashtab key. The flow looks like:

<bpf prog code>
bpf_map_update_elem()
htab_map_update_elem()
alloc_htab_elem()

It feels a bit weird to me to add a comment about strings in there because the hash table code is string-agnostic, as mentioned in the commit message.

Quoted 5 lines

And your ABI point is actively misleading:

Quoted 3 lines

We can't really zero out the rest of the buffer due to ABI issues. The bpf docs state for bpf_probe_read_user_str():

Quoted 7 lines
Quoted 2 lines
Quoted 2 lines

In case the string length is smaller than *size*, the target is not padded with further NUL bytes.

This comment is actively wrong and misleading.

The code (after the patch) clearly *does* pad a bit with "further NUL bytes". It's just that it doesn't pad all the way to the end.

Right, it's a bit ugly and perhaps misleading. But it fixes the real problem of keying a map with potentially random memory that strncpy_from_user() might append on. If we pad a deterministic number of zeros it should be ok.

Quoted 1 line

Where is the actual buffer zeroing done?

Usually the bpf prog does it. I believe (could be wrong) the verifier enforces the key is initialized in some form.

For my specific use case, it's done in the bpftrace code:
https://github.com/iovisor/bpftrace/blob/0c88a1a4711a3d13e8c9475f7d08f83a5018fdfd/src/ast/codegen_llvm.cpp#L529-L530

Quoted 4 lines

Because without the buffer zeroing, this whole patch is completely pointless. Which is why I want that comment, and I want a pointer to where that zeroing is done.

Quoted 8 lines

Really. You have two cases:

(a) the buffer isn't zeroed before the strncpy_from_user()

(b) the buffer is guaranteed to be zero before that

and in case (a), this patch is pointless, since the data after the string is already undefined.

See above -- I think the verifier enforces that the data is initialized.

Quoted 2 lines

And in case (b), I want to see a comment and a pointer to the code that actually does the zeroing.

See above also.

Quoted 3 lines

HOWEVER. Look at bpf_probe_read_user_str_common(), and notice how it ALREADY does the zeroing of the buffer past the end, it's just that it only does it in the error case.

I don't think the error case is very relevant here. I normally wouldn't make any assumptions about the state of a buffer after a failed function call.

Quoted 14 lines

Why do you send this patch, instead of

(a) get rid of the pointless pre-zeroing

(b) change bpf_probe_read_user_str_common() to do

        int ret;
        u32 offset;

        ret = strncpy_from_user_nofault(dst, unsafe_ptr, size);
        offset = ret < 0 ? 0 : ret;
        memset(dst+offset, 0, size-offset);
        return ret;
Quoted 4 lines

which seems to be much simpler anyway. The comment you quote about "target is not padded with further NUL bytes" is clearly wrong anyway, since that error case *does* pad the target with NUL bytes, and always has.

I think on the bpf side there's the same concern about performance. You can't really dynamically size buffers in bpf land so users usually use a larger buffer than necessary, sometimes on the order of KBs. So if we unnecessarily zero out the rest of the buffer it could cause perf regressions.

[...]

Thanks,
Daniel

author
#6 lore raw

PATCH v6 2/2 selftest/bpf: Test bpf_probe_read_user_str() strips trailing bytes after NUL

In reply to Daniel Xu

Previously, bpf_probe_read_user_str() could potentially overcopy the trailing bytes after the NUL due to how do_strncpy_from_user() does the copy in long-sized strides. The issue has been fixed in the previous commit.

This commit adds a selftest that ensures we don't regress bpf_probe_read_user_str() again.

---
 .../bpf/prog_tests/probe_read_user_str.c      | 71 +++++++++++++++++++
 .../bpf/progs/test_probe_read_user_str.c      | 25 +++++++
 2 files changed, 96 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/probe_read_user_str.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_probe_read_user_str.c
tools/testing/selftests/bpf/prog_tests/probe_read_user_str.c new file +71 -0
new file mode 100644
index 000000000000..e419298132b5
@@ -0,0 +1,71 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+#include "test_probe_read_user_str.skel.h"
+
+static const char str1[] = "mestring";
+static const char str2[] = "mestringalittlebigger";
+static const char str3[] = "mestringblubblubblubblubblub";
+
+static int test_one_str(struct test_probe_read_user_str *skel, const char *str,
+			size_t len)
+{
+	int err, duration = 0;
+	char buf[256];
+
+	/* Ensure bytes after string are ones */
+	memset(buf, 1, sizeof(buf));
+	memcpy(buf, str, len);
+
+	/* Give prog our userspace pointer */
+	skel->bss->user_ptr = buf;
+
+	/* Trigger tracepoint */
+	usleep(1);
+
+	/* Did helper fail? */
+	if (CHECK(skel->bss->ret < 0, "prog_ret", "prog returned: %ld\n",
+		  skel->bss->ret))
+		return 1;
+
+	/* Check that string was copied correctly */
+	err = memcmp(skel->bss->buf, str, len);
+	if (CHECK(err, "memcmp", "prog copied wrong string"))
+		return 1;
+
+	/* Now check that no extra trailing bytes were copied */
+	memset(buf, 0, sizeof(buf));
+	err = memcmp(skel->bss->buf + len, buf, sizeof(buf) - len);
+	if (CHECK(err, "memcmp", "trailing bytes were not stripped"))
+		return 1;
+
+	return 0;
+}
+
+void test_probe_read_user_str(void)
+{
+	struct test_probe_read_user_str *skel;
+	int err, duration = 0;
+
+	skel = test_probe_read_user_str__open_and_load();
+	if (CHECK(!skel, "test_probe_read_user_str__open_and_load",
+		  "skeleton open and load failed\n"))
+		return;
+
+	/* Give pid to bpf prog so it doesn't read from anyone else */
+	skel->bss->pid = getpid();
+
+	err = test_probe_read_user_str__attach(skel);
+	if (CHECK(err, "test_probe_read_user_str__attach",
+		  "skeleton attach failed: %d\n", err))
+		goto out;
+
+	if (test_one_str(skel, str1, sizeof(str1)))
+		goto out;
+	if (test_one_str(skel, str2, sizeof(str2)))
+		goto out;
+	if (test_one_str(skel, str3, sizeof(str3)))
+		goto out;
+
+out:
+	test_probe_read_user_str__destroy(skel);
+}
tools/testing/selftests/bpf/progs/test_probe_read_user_str.c new file +25 -0
new file mode 100644
index 000000000000..3ae398b75dcd
@@ -0,0 +1,25 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+
+#include <sys/types.h>
+
+pid_t pid = 0;
+long ret = 0;
+void *user_ptr = 0;
+char buf[256] = {};
+
+SEC("tracepoint/syscalls/sys_enter_nanosleep")
+int on_write(void *ctx)
+{
+	if (pid != (bpf_get_current_pid_tgid() >> 32))
+		return 0;
+
+	ret = bpf_probe_read_user_str(buf, sizeof(buf), user_ptr);
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
Signature · 1 line
2.29.2