[PATCH v2 1/2] bpf: Forbid XADD on spilled pointers for unprivileged users

[PATCH v2 1/2] bpf: Forbid XADD on spilled pointers for unprivileged users

[Jann Horn]

When check_xadd() verifies an XADD operation on a pointer to a stack slot
containing a spilled pointer, check_stack_read() verifies that the read,
which is part of XADD, is valid. However, since the placeholder value -1 is
passed as `value_regno`, check_stack_read() can only return a binary
decision and can't return the type of the value that was read. The intent
here is to verify whether the value read from the stack slot may be used as
a SCALAR_VALUE; but since check_stack_read() doesn't check the type, and
the type information is lost when check_stack_read() returns, this is not
enforced, and a malicious user can abuse XADD to leak spilled kernel
pointers.

Fix it by letting check_stack_read() verify that the value is usable as a
SCALAR_VALUE if no type information is passed to the caller.

To be able to use __is_pointer_value() in check_stack_read(), move it up.

Fix up the expected unprivileged error message for a BPF selftest that,
until now, assumed that unprivileged users can use XADD on stack-spilled
pointers. This also gives us a test for the behavior introduced in this
patch for free.

In theory, this could also be fixed by forbidding XADD on stack spills
entirely, since XADD is a locked operation (for operations on memory with
concurrency) and there can't be any concurrency on the BPF stack; but
Alexei has said that he wants to keep XADD on stack slots working to avoid
changes to the test suite [1].

The following BPF program demonstrates how to leak a BPF map pointer as an
unprivileged user using this bug:

    // r7 = map_pointer
    BPF_LD_MAP_FD(BPF_REG_7, small_map),
    // r8 = launder(map_pointer)
    BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_7, -8),
    BPF_MOV64_IMM(BPF_REG_1, 0),
    ((struct bpf_insn) {
      .code  = BPF_STX | BPF_DW | BPF_XADD,
      .dst_reg = BPF_REG_FP,
      .src_reg = BPF_REG_1,
      .off = -8
    }),
    BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_FP, -8),

    // store r8 into map
    BPF_MOV64_REG(BPF_REG_ARG1, BPF_REG_7),
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 0),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
    BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
    BPF_EXIT_INSN(),
    BPF_STX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),

    BPF_MOV64_IMM(BPF_REG_0, 0),
    BPF_EXIT_INSN()

[1] https://lore.kernel.org/bpf/20200416211116.qxqcza5vo2ddnkdq@ast-mbp.dhcp.thefacebook.com/

Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
Signed-off-by: Jann Horn <jannh@google.com>
---
 kernel/bpf/verifier.c                         | 28 +++++++++++++------
 .../bpf/verifier/value_illegal_alu.c          |  1 +
 2 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 38cfcf701eeb7..9e92d3d5ffd17 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2118,6 +2118,15 @@ static bool register_is_const(struct bpf_reg_state *reg)
 	return reg->type == SCALAR_VALUE && tnum_is_const(reg->var_off);
 }
 
+static bool __is_pointer_value(bool allow_ptr_leaks,
+			       const struct bpf_reg_state *reg)
+{
+	if (allow_ptr_leaks)
+		return false;
+
+	return reg->type != SCALAR_VALUE;
+}
+
 static void save_register_state(struct bpf_func_state *state,
 				int spi, struct bpf_reg_state *reg)
 {
@@ -2308,6 +2317,16 @@ static int check_stack_read(struct bpf_verifier_env *env,
 			 * which resets stack/reg liveness for state transitions
 			 */
 			state->regs[value_regno].live |= REG_LIVE_WRITTEN;
+		} else if (__is_pointer_value(env->allow_ptr_leaks, reg)) {
+			/* If value_regno==-1, the caller is asking us whether
+			 * it is acceptable to use this value as a SCALAR_VALUE
+			 * (e.g. for XADD).
+			 * We must not allow unprivileged callers to do that
+			 * with spilled pointers.
+			 */
+			verbose(env, "leaking pointer from stack off %d\n",
+				off);
+			return -EACCES;
 		}
 		mark_reg_read(env, reg, reg->parent, REG_LIVE_READ64);
 	} else {
@@ -2673,15 +2692,6 @@ static int check_sock_access(struct bpf_verifier_env *env, int insn_idx,
 	return -EACCES;
 }
 
-static bool __is_pointer_value(bool allow_ptr_leaks,
-			       const struct bpf_reg_state *reg)
-{
-	if (allow_ptr_leaks)
-		return false;
-
-	return reg->type != SCALAR_VALUE;
-}
-
 static struct bpf_reg_state *reg_state(struct bpf_verifier_env *env, int regno)
 {
 	return cur_regs(env) + regno;
diff --git a/tools/testing/selftests/bpf/verifier/value_illegal_alu.c b/tools/testing/selftests/bpf/verifier/value_illegal_alu.c
index 7f6c232cd8423..ed1c2cea1dea6 100644
--- a/tools/testing/selftests/bpf/verifier/value_illegal_alu.c
+++ b/tools/testing/selftests/bpf/verifier/value_illegal_alu.c
@@ -88,6 +88,7 @@
 	BPF_EXIT_INSN(),
 	},
 	.fixup_map_hash_48b = { 3 },
+	.errstr_unpriv = "leaking pointer from stack off -8",
 	.errstr = "R0 invalid mem access 'inv'",
 	.result = REJECT,
 	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,

base-commit: edadedf1c5b4e4404192a0a4c3c0c05e3b7672ab
-- 
2.26.1.301.g55bc3eb7cb9-goog

[PATCH v2 2/2] bpf: Fix handling of XADD on BTF memory

[Jann Horn]

check_xadd() can cause check_ptr_to_btf_access() to be executed with
atype==BPF_READ and value_regno==-1 (meaning "just check whether the access
is okay, don't tell me what type it will result in").
Handle that case properly and skip writing type information, instead of
indexing into the registers at index -1 and writing into out-of-bounds
memory.

Note that at least at the moment, you can't actually write through a BTF
pointer, so check_xadd() will reject the program after calling
check_ptr_to_btf_access with atype==BPF_WRITE; but that's after the
verifier has already corrupted memory.

This patch assumes that BTF pointers are not available in unprivileged
programs.

Fixes: 9e15db66136a ("bpf: Implement accurate raw_tp context access via BTF")
Signed-off-by: Jann Horn <jannh@google.com>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9e92d3d5ffd17..9382609147f53 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3099,7 +3099,7 @@ static int check_ptr_to_btf_access(struct bpf_verifier_env *env,
 	if (ret < 0)
 		return ret;
 
-	if (atype == BPF_READ) {
+	if (atype == BPF_READ && value_regno >= 0) {
 		if (ret == SCALAR_VALUE) {
 			mark_reg_unknown(env, regs, value_regno);
 			return 0;
-- 
2.26.1.301.g55bc3eb7cb9-goog

Re: [PATCH v2 1/2] bpf: Forbid XADD on spilled pointers for unprivileged users

[Alexei Starovoitov]

On Thu, Apr 16, 2020 at 5:00 PM Jann Horn <jannh@google.com> wrote:
>
> When check_xadd() verifies an XADD operation on a pointer to a stack slot
> containing a spilled pointer, check_stack_read() verifies that the read,
> which is part of XADD, is valid. However, since the placeholder value -1 is
> passed as `value_regno`, check_stack_read() can only return a binary
> decision and can't return the type of the value that was read. The intent
> here is to verify whether the value read from the stack slot may be used as
> a SCALAR_VALUE; but since check_stack_read() doesn't check the type, and
> the type information is lost when check_stack_read() returns, this is not
> enforced, and a malicious user can abuse XADD to leak spilled kernel
> pointers.
>
> Fix it by letting check_stack_read() verify that the value is usable as a
> SCALAR_VALUE if no type information is passed to the caller.
>
> To be able to use __is_pointer_value() in check_stack_read(), move it up.
>
> Fix up the expected unprivileged error message for a BPF selftest that,
> until now, assumed that unprivileged users can use XADD on stack-spilled
> pointers. This also gives us a test for the behavior introduced in this
> patch for free.
>
> In theory, this could also be fixed by forbidding XADD on stack spills
> entirely, since XADD is a locked operation (for operations on memory with
> concurrency) and there can't be any concurrency on the BPF stack; but
> Alexei has said that he wants to keep XADD on stack slots working to avoid
> changes to the test suite [1].
>
> The following BPF program demonstrates how to leak a BPF map pointer as an
> unprivileged user using this bug:
>
>     // r7 = map_pointer
>     BPF_LD_MAP_FD(BPF_REG_7, small_map),
>     // r8 = launder(map_pointer)
>     BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_7, -8),
>     BPF_MOV64_IMM(BPF_REG_1, 0),
>     ((struct bpf_insn) {
>       .code  = BPF_STX | BPF_DW | BPF_XADD,
>       .dst_reg = BPF_REG_FP,
>       .src_reg = BPF_REG_1,
>       .off = -8
>     }),
>     BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_FP, -8),
>
>     // store r8 into map
>     BPF_MOV64_REG(BPF_REG_ARG1, BPF_REG_7),
>     BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
>     BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
>     BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 0),
>     BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
>     BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
>     BPF_EXIT_INSN(),
>     BPF_STX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),
>
>     BPF_MOV64_IMM(BPF_REG_0, 0),
>     BPF_EXIT_INSN()
>
> [1] https://lore.kernel.org/bpf/20200416211116.qxqcza5vo2ddnkdq@ast-mbp.dhcp.thefacebook.com/
>
> Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
> Signed-off-by: Jann Horn <jannh@google.com>

Applied both. Thanks