BPF Archive on lore.kernel.org
 help / color / Atom feed
From: John Fastabend <john.fastabend@gmail.com>
To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com,
	daniel@iogearbox.net
Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com
Subject: [bpf-next PATCH 07/10] bpf: test_verifier, bpf_get_stack return value add <0
Date: Tue, 24 Mar 2020 10:39:55 -0700
Message-ID: <158507159511.15666.6943798089263377114.stgit@john-Precision-5820-Tower> (raw)
In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower>

With current ALU32 subreg handling and retval refine fix from last
patches we see an expected failure in test_verifier. With verbose
verifier state being printed at each step for clarity we have the
following relavent lines [I omit register states that are not
necessarily useful to see failure cause],

#101/p bpf_get_stack return R0 within range FAIL
Failed to load prog 'Success'!
[..]
14: (85) call bpf_get_stack#67
 R0_w=map_value(id=0,off=0,ks=8,vs=48,imm=0)
 R3_w=inv48
15:
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
15: (b7) r1 = 0
16:
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
16: (bf) r8 = r0
17:
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
 R8_w=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
17: (67) r8 <<= 32
18:
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
 R8_w=inv(id=0,smax_value=9223372032559808512,
               umax_value=18446744069414584320,
               var_off=(0x0; 0xffffffff00000000),
               s32_min_value=0,
               s32_max_value=0,
               u32_max_value=0,
               var32_off=(0x0; 0x0))
18: (c7) r8 s>>= 32
19
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
 R8_w=inv(id=0,smin_value=-2147483648,
               smax_value=2147483647,
               var32_off=(0x0; 0xffffffff))
19: (cd) if r1 s< r8 goto pc+16
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
 R8_w=inv(id=0,smin_value=-2147483648,
               smax_value=0,
               var32_off=(0x0; 0xffffffff))
20:
 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
 R1_w=inv0
 R8_w=inv(id=0,smin_value=-2147483648,
               smax_value=0,
 R9=inv48
20: (1f) r9 -= r8
21: (bf) r2 = r7
22:
 R2_w=map_value(id=0,off=0,ks=8,vs=48,imm=0)
22: (0f) r2 += r8
value -2147483648 makes map_value pointer be out of bounds

After call bpf_get_stack() on line 14 and some moves we have at line 16
an r8 bound with max_value 48 but an unknown min value. This is to be
expected bpf_get_stack call can only return a max of the input size but
is free to return any negative error in the 32-bit register space.
And further C signature returns 'int' which provides no guarantee on
the upper 32-bits of the register.

Lines 17 and 18 clear the top 32 bits with a left/right shift but use
ARSH so we still have worst case min bound before line 19 of -2147483648.
At this point the signed check 'r1 s< r8' meant to protect the addition
on line 22 where dst reg is a map_value pointer may very well return
true with a large negative number. Then the final line 22 will detect
this as an invalid operation and fail the program.

To fix add a signed less than check to ensure r8 is greater than 0 at
line 19 so the bounds check works as expected. Programs _must_ check
for negative return codes or they will fail to load now. But on the
other hand they were buggy before so for correctness the check really
is needed.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../testing/selftests/bpf/verifier/bpf_get_stack.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c
index f24d50f..24aa6a0 100644
--- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c
+++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c
@@ -7,7 +7,7 @@
 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
 	BPF_LD_MAP_FD(BPF_REG_1, 0),
 	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
-	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 28),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 29),
 	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
 	BPF_MOV64_IMM(BPF_REG_9, sizeof(struct test_val)),
 	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
@@ -16,6 +16,7 @@
 	BPF_MOV64_IMM(BPF_REG_4, 256),
 	BPF_EMIT_CALL(BPF_FUNC_get_stack),
 	BPF_MOV64_IMM(BPF_REG_1, 0),
+	BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, 20),
 	BPF_MOV64_REG(BPF_REG_8, BPF_REG_0),
 	BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32),
 	BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32),


  parent reply index

Thread overview: 19+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-24 17:37 [bpf-next PATCH 00/10] ALU32 bounds tracking support John Fastabend
2020-03-24 17:37 ` [bpf-next PATCH 01/10] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly John Fastabend
2020-03-24 17:38 ` [bpf-next PATCH 02/10] bpf: verifer, refactor adjust_scalar_min_max_vals John Fastabend
2020-03-26  6:10   ` Alexei Starovoitov
2020-03-24 17:38 ` [bpf-next PATCH 03/10] bpf: verifer, adjust_scalar_min_max_vals to always call update_reg_bounds() John Fastabend
2020-03-24 17:38 ` [bpf-next PATCH 04/10] bpf: verifier, do explicit ALU32 bounds tracking John Fastabend
2020-03-26  6:20   ` Alexei Starovoitov
2020-03-26 15:18     ` John Fastabend
2020-03-24 17:39 ` [bpf-next PATCH 05/10] bpf: verifier, return value is an int in do_refine_retval_range John Fastabend
2020-03-26  6:23   ` Alexei Starovoitov
2020-03-26 15:52     ` John Fastabend
2020-03-24 17:39 ` [bpf-next PATCH 06/10] bpf: test_progs, add test to catch retval refine error handling John Fastabend
2020-03-24 17:39 ` John Fastabend [this message]
2020-03-26  6:33   ` [bpf-next PATCH 07/10] bpf: test_verifier, bpf_get_stack return value add <0 Alexei Starovoitov
2020-03-26 15:48     ` John Fastabend
2020-03-24 17:40 ` [bpf-next PATCH 08/10] bpf: test_verifier, #70 error message updates for 32-bit right shift John Fastabend
2020-03-24 17:40 ` [bpf-next PATCH 09/10] bpf: test_verifier, #65 error message updates for trunc of boundary-cross John Fastabend
2020-03-24 17:40 ` [bpf-next PATCH 10/10] bpf: test_verifier, add alu32 bounds tracking tests John Fastabend
2020-03-26  6:34   ` Alexei Starovoitov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=158507159511.15666.6943798089263377114.stgit@john-Precision-5820-Tower \
    --to=john.fastabend@gmail.com \
    --cc=alexei.starovoitov@gmail.com \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=ecree@solarflare.com \
    --cc=netdev@vger.kernel.org \
    --cc=yhs@fb.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

BPF Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \
		bpf@vger.kernel.org
	public-inbox-index bpf

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.bpf


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git