From patchwork Fri Jan 12 19:23:45 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Borkmann X-Patchwork-Id: 860157 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3zJCNH6Rjlz9s7c for ; Sat, 13 Jan 2018 06:23:59 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S965128AbeALTX5 (ORCPT ); Fri, 12 Jan 2018 14:23:57 -0500 Received: from www62.your-server.de ([213.133.104.62]:38316 "EHLO www62.your-server.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S965081AbeALTX4 (ORCPT ); Fri, 12 Jan 2018 14:23:56 -0500 Received: from [194.230.159.167] (helo=localhost) by www62.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.85_2) (envelope-from ) id 1ea4vh-0006cB-Cq; Fri, 12 Jan 2018 20:23:54 +0100 From: Daniel Borkmann To: ast@fb.com Cc: ecree@solarflare.com, netdev@vger.kernel.org, Daniel Borkmann Subject: [PATCH bpf] bpf: do not modify min/max bounds on scalars with constant values Date: Fri, 12 Jan 2018 20:23:45 +0100 Message-Id: <20180112192345.3589-1-daniel@iogearbox.net> X-Mailer: git-send-email 2.9.5 X-Authenticated-Sender: daniel@iogearbox.net X-Virus-Scanned: Clear (ClamAV 0.99.2/24215/Fri Jan 12 14:18:58 2018) Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org syzkaller generated a BPF proglet and triggered a warning with the following: 0: (b7) r0 = 0 1: (d5) if r0 s<= 0x0 goto pc+0 R0=inv0 R1=ctx(id=0,off=0,imm=0) R10=fp0 2: (1f) r0 -= r1 R0=inv0 R1=ctx(id=0,off=0,imm=0) R10=fp0 verifier internal error: known but bad sbounds What happens is that in the first insn, r0's min/max value are both 0 due to the immediate assignment, later in the jsle test the bounds are updated for the min value in the false path, meaning, they yield smin_val = 1 smax_val = 0, and when ctx pointer is subtracted from r0, verifier bails out with the internal error and throwing a WARN since smin_val != smax_val for the known constant. Fix is to not update any bounds of the register holding the constant, thus in reg_set_min_max() and reg_set_min_max_inv() we return right away, similarly as in the case when the dst register holds a pointer value. Reason for doing so is rather straight forward: when we have a register holding a constant as dst, then {s,u}min_val == {s,u}max_val, thus it cannot get any more specific in terms of upper/lower bounds than this. In reg_set_min_max() and reg_set_min_max_inv() it's fine to only check false_reg similarly as with __is_pointer_value() check since at this point in time, false_reg and true_reg both hold the same state, so we only need to pick one. This fixes the bug and properly rejects the program with an error of 'R0 tried to subtract pointer from scalar'. I've been thinking to additionally reject arithmetic on ctx pointer in adjust_ptr_min_max_vals() right upfront as well since we reject actual access in such case later on anyway, but there's a use case in tracing (in bcc) in combination with passing such ctx to bpf_probe_read(), so we cannot do that part. Reported-by: syzbot+6d362cadd45dc0a12ba4@syzkaller.appspotmail.com Signed-off-by: Daniel Borkmann --- kernel/bpf/verifier.c | 11 ++++ tools/testing/selftests/bpf/test_verifier.c | 95 +++++++++++++++++++++++++++++ 2 files changed, 106 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index b414d6b..6bf1275 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2617,6 +2617,14 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, */ if (__is_pointer_value(false, false_reg)) return; + /* Same goes for constant values. They have {s,u}min == {s,u}max, + * it cannot get narrower than this. Same here, at the branch + * point false_reg and true_reg have the same type, so we only + * check false_reg here as well. + */ + if (false_reg->type == SCALAR_VALUE && + tnum_is_const(false_reg->var_off)) + return; switch (opcode) { case BPF_JEQ: @@ -2689,6 +2697,9 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, { if (__is_pointer_value(false, false_reg)) return; + if (false_reg->type == SCALAR_VALUE && + tnum_is_const(false_reg->var_off)) + return; switch (opcode) { case BPF_JEQ: diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index b510174..162d497 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -8569,6 +8569,101 @@ static struct bpf_test tests[] = { .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS, }, { + "check deducing bounds from const, 1", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 0), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "R0 tried to subtract pointer from scalar", + }, + { + "check deducing bounds from const, 2", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 1), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "R0 tried to subtract pointer from scalar", + }, + { + "check deducing bounds from const, 3", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "R0 tried to subtract pointer from scalar", + }, + { + "check deducing bounds from const, 4", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, ~0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 0), + BPF_ALU64_REG(BPF_SUB, BPF_REG_1, BPF_REG_0), + BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, + offsetof(struct __sk_buff, mark)), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "dereference of modified ctx ptr", + }, + { + "check deducing bounds from const, 5", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, ~0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 1), + BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_0), + BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, + offsetof(struct __sk_buff, mark)), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "dereference of modified ctx ptr", + }, + { + "check deducing bounds from const, 6", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSLE, BPF_REG_0, 0, 0), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "R0 tried to subtract pointer from scalar", + }, + { + "check deducing bounds from const, 7", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 0), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "R0 tried to subtract pointer from scalar", + }, + { + "check deducing bounds from const, 8", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JSLE, BPF_REG_0, 0, 0), + /* Marks reg as unknown. */ + BPF_ALU64_IMM(BPF_NEG, BPF_REG_0, 0), + BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "math between ctx pointer and register with unbounded min value is not allowed", + }, + { "bpf_exit with invalid return code. test1", .insns = { BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0),