Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752420AbdF3Rey (ORCPT ); Fri, 30 Jun 2017 13:34:54 -0400 Received: from dispatch1-us1.ppe-hosted.com ([67.231.154.164]:57275 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751676AbdF3Rex (ORCPT ); Fri, 30 Jun 2017 13:34:53 -0400 From: Edward Cree Subject: [TEST PATCH] bpf/verifier: roll back ptr&const handling, and fix signed bounds To: Alexei Starovoitov , Alexei Starovoitov , Daniel Borkmann References: <91267d15-652a-16d9-4ee9-42958bd842aa@solarflare.com> CC: , , , iovisor-dev Message-ID: <9d11d115-4b5a-e845-d408-2f829d9bbab2@solarflare.com> Date: Fri, 30 Jun 2017 18:34:40 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 MIME-Version: 1.0 In-Reply-To: <91267d15-652a-16d9-4ee9-42958bd842aa@solarflare.com> Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-Originating-IP: [10.17.20.45] X-ClientProxiedBy: ocex03.SolarFlarecom.com (10.20.40.36) To ukex01.SolarFlarecom.com (10.17.10.4) X-TM-AS-Product-Ver: SMEX-11.0.0.1191-8.100.1062-23166.003 X-TM-AS-Result: No--13.217500-0.000000-31 X-TM-AS-User-Approved-Sender: Yes X-TM-AS-User-Blocked-Sender: No X-MDID: 1498844091-l0XeE5zJs444 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 14473 Lines: 399 I'm far from sure that my adjust_reg_min_max_vals() code remains correct in the face of maybe-signed-maybe-not bounds, even with the checks I've added in. So this probably has security leaks in it; but it should suffice for measuring the effect on pruning. The treat_as_signed part is loosely based on a patch by Josef Bacik . Build-tested only. Applies on top of patches 1-3. Signed-off-by: Edward Cree --- include/linux/bpf_verifier.h | 5 +- kernel/bpf/verifier.c | 179 ++++++++++++++++++++++++++----------------- 2 files changed, 111 insertions(+), 73 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index ca7e2ce..ad02a9d 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -51,8 +51,9 @@ struct bpf_reg_state { * These refer to the same value as var_off, not necessarily the actual * contents of the register. */ - s64 min_value; /* minimum possible (s64)value */ - u64 max_value; /* maximum possible (u64)value */ + bool treat_as_signed; /* Do below limits come from a JSGT/JSGE? */ + s64 min_value; + u64 max_value; }; enum bpf_stack_slot_type { diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 82823f1..b59c09b 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -474,6 +474,7 @@ static void __mark_reg_known_zero(struct bpf_reg_state *reg) reg->var_off = tnum_const(0); reg->min_value = 0; reg->max_value = 0; + reg->treat_as_signed = false; } static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno) @@ -497,6 +498,7 @@ static void __mark_reg_unknown(struct bpf_reg_state *reg) reg->var_off = tnum_unknown; reg->min_value = BPF_REGISTER_MIN_RANGE; reg->max_value = BPF_REGISTER_MAX_RANGE; + reg->treat_as_signed = false; } static void mark_reg_unknown(struct bpf_reg_state *regs, u32 regno) @@ -1087,6 +1089,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn state->regs[value_regno].var_off.value | state->regs[value_regno].var_off.mask, BPF_REGISTER_MAX_RANGE); + state->regs[value_regno].treat_as_signed = false; } return err; } @@ -1601,6 +1604,9 @@ static void check_reg_overflow(struct bpf_reg_state *reg) if (reg->min_value < BPF_REGISTER_MIN_RANGE || reg->min_value > BPF_REGISTER_MAX_RANGE) reg->min_value = BPF_REGISTER_MIN_RANGE; + /* Unsigned cannot be < 0 */ + if (!reg->treat_as_signed && reg->min_value < 0) + reg->min_value = 0; } static void coerce_reg_to_32(struct bpf_reg_state *reg) @@ -1612,10 +1618,12 @@ static void coerce_reg_to_32(struct bpf_reg_state *reg) reg->var_off = tnum_cast(reg->var_off, 4); /* Did value become known? Then update bounds */ if (tnum_is_const(reg->var_off)) { - if ((s64)reg->var_off.value > BPF_REGISTER_MIN_RANGE) + /* We're treating as unsigned, so min is always >= 0 */ + if (reg->var_off.value < BPF_REGISTER_MAX_RANGE) { reg->min_value = reg->var_off.value; - if (reg->var_off.value < BPF_REGISTER_MAX_RANGE) reg->max_value = reg->var_off.value; + } + reg->treat_as_signed = false; } } @@ -1637,6 +1645,18 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, u8 opcode = BPF_OP(insn->code); u32 dst = insn->dst_reg; + /* If we can cross the sign boundary, don't trust our bounds. + * Normally the program should have given us both upper and lower + * bounds (e.g. two signed checks or one unsigned upper bound), in + * which case this won't fire. + */ + if (off_reg->treat_as_signed) { + if (min_val == BPF_REGISTER_MIN_RANGE) + max_val = BPF_REGISTER_MAX_RANGE; + } else { + if (max_val == BPF_REGISTER_MAX_RANGE) + min_val = BPF_REGISTER_MIN_RANGE; + } dst_reg = ®s[dst]; if (WARN_ON_ONCE(known && (min_val != max_val))) { @@ -1677,6 +1697,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, */ dst_reg->type = ptr_reg->type; dst_reg->id = ptr_reg->id; + /* We also inherit the signedness of our offset. + * XXX If we already had an offset of a different signedness, this + * might lead to trouble! + */ + dst_reg->treat_as_signed = off_reg->treat_as_signed; switch (opcode) { case BPF_ADD: @@ -1820,6 +1845,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, } min_val = src_reg->min_value; max_val = src_reg->max_value; + /* If we can cross the sign boundary, don't trust our bounds. + * Normally the program should have given us both upper and lower + * bounds (e.g. two signed checks or one unsigned upper bound), in + * which case this won't fire. + */ + if (src_reg->treat_as_signed) { + if (min_val == BPF_REGISTER_MIN_RANGE) + max_val = BPF_REGISTER_MAX_RANGE; + } else { + if (max_val == BPF_REGISTER_MAX_RANGE) + min_val = BPF_REGISTER_MIN_RANGE; + } src_known = tnum_is_const(src_reg->var_off); dst_known = tnum_is_const(dst_reg->var_off); @@ -2004,10 +2041,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, src_reg, dst_reg); if (rc == -EACCES && env->allow_ptr_leaks) { /* scalar += unknown scalar */ - __mark_reg_unknown(&off_reg); - return adjust_scalar_min_max_vals( - env, insn, - dst_reg, &off_reg); + __mark_reg_unknown(dst_reg); } return rc; } @@ -2018,8 +2052,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, if (rc == -EACCES && env->allow_ptr_leaks) { /* unknown scalar += scalar */ __mark_reg_unknown(dst_reg); - return adjust_scalar_min_max_vals( - env, insn, dst_reg, src_reg); } return rc; } @@ -2031,6 +2063,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, off_reg.var_off = tnum_const(insn->imm); off_reg.min_value = insn->imm; off_reg.max_value = insn->imm; + off_reg.treat_as_signed = false; src_reg = &off_reg; if (ptr_reg) { /* pointer += K */ rc = adjust_ptr_min_max_vals(env, insn, @@ -2038,8 +2071,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, if (rc == -EACCES && env->allow_ptr_leaks) { /* unknown scalar += K */ __mark_reg_unknown(dst_reg); - return adjust_scalar_min_max_vals( - env, insn, dst_reg, &off_reg); } return rc; } @@ -2151,6 +2182,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) regs[insn->dst_reg].var_off = tnum_const(insn->imm); regs[insn->dst_reg].max_value = insn->imm; regs[insn->dst_reg].min_value = insn->imm; + regs[insn->dst_reg].treat_as_signed = false; regs[insn->dst_reg].id = 0; } @@ -2271,12 +2303,15 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, struct bpf_reg_state *false_reg, u64 val, u8 opcode) { + bool treat_as_signed = true; + switch (opcode) { case BPF_JEQ: /* If this is false then we know nothing Jon Snow, but if it is * true then we know for sure. */ true_reg->max_value = true_reg->min_value = val; + true_reg->treat_as_signed = false; true_reg->var_off = tnum_const(val); break; case BPF_JNE: @@ -2284,45 +2319,42 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, * we know the value for sure; */ false_reg->max_value = false_reg->min_value = val; + false_reg->treat_as_signed = false; false_reg->var_off = tnum_const(val); break; case BPF_JGT: - /* Unsigned comparison, can only tell us about max_value (since - * min_value is signed), unless we learn sign bit. - */ - false_reg->max_value = val; - /* If we're not unsigned-greater-than a positive value, then - * we can't be negative. - */ - if ((s64)val >= 0 && false_reg->min_value < 0) - false_reg->min_value = 0; - break; + /* Unsigned comparison, min_value is 0 */ + true_reg->min_value = 0; + treat_as_signed = false; case BPF_JSGT: - /* Signed comparison, can only tell us about min_value (since - * max_value is unsigned), unless we already know sign bit. + /* r > k => true->min = k+1 + * r <= k => false->max = k */ + false_reg->max_value = val; true_reg->min_value = val + 1; - /* If we're not signed-greater than val, and we're not negative, - * then we can't be unsigned-greater than val either. - */ - if (false_reg->min_value >= 0) - false_reg->max_value = val; + if (false_reg->treat_as_signed != treat_as_signed) + false_reg->min_value = BPF_REGISTER_MIN_RANGE; + if (true_reg->treat_as_signed != treat_as_signed) + true_reg->max_value = BPF_REGISTER_MAX_RANGE; + false_reg->treat_as_signed = treat_as_signed; + true_reg->treat_as_signed = treat_as_signed; break; case BPF_JGE: - false_reg->max_value = val - 1; - /* If we're not unsigned-ge a positive value, then we can't be - * negative. - */ - if ((s64)val >= 0 && false_reg->min_value < 0) - false_reg->min_value = 0; - break; + /* Unsigned comparison, min_value is 0 */ + true_reg->min_value = 0; + treat_as_signed = false; case BPF_JSGE: - true_reg->min_value = val; - /* If we're not signed-ge val, and we're not negative, then we - * can't be unsigned-ge val either. + /* r >= k => true->min = k + * r < k => false->max = k-1 */ - if (false_reg->min_value >= 0) - false_reg->max_value = val - 1; + false_reg->max_value = val - 1; + true_reg->min_value = val; + if (false_reg->treat_as_signed != treat_as_signed) + false_reg->min_value = BPF_REGISTER_MIN_RANGE; + if (true_reg->treat_as_signed != treat_as_signed) + true_reg->max_value = BPF_REGISTER_MAX_RANGE; + false_reg->treat_as_signed = treat_as_signed; + true_reg->treat_as_signed = treat_as_signed; break; default: break; @@ -2339,12 +2371,15 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, struct bpf_reg_state *false_reg, u64 val, u8 opcode) { + bool treat_as_signed = true; + switch (opcode) { case BPF_JEQ: /* If this is false then we know nothing Jon Snow, but if it is * true then we know for sure. */ true_reg->max_value = true_reg->min_value = val; + true_reg->treat_as_signed = false; true_reg->var_off = tnum_const(val); break; case BPF_JNE: @@ -2352,45 +2387,42 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, * we know the value for sure; */ false_reg->max_value = false_reg->min_value = val; + false_reg->treat_as_signed = false; false_reg->var_off = tnum_const(val); break; case BPF_JGT: - /* Unsigned comparison, can only tell us about max_value (since - * min_value is signed), unless we learn sign bit. - */ - true_reg->max_value = val - 1; - /* If a positive value is unsigned-greater-than us, then we - * can't be negative. - */ - if ((s64)val >= 0 && true_reg->min_value < 0) - true_reg->min_value = 0; - break; + /* Unsigned comparison, min_value is 0 */ + true_reg->min_value = 0; + treat_as_signed = false; case BPF_JSGT: - /* Signed comparison, can only tell us about min_value (since - * max_value is unsigned), unless we already know sign bit. + /* k > r => true->max = k-1 + * k <= r => false->min = k */ false_reg->min_value = val; - /* If val is signed-greater-than us, and we're not negative, - * then val must be unsigned-greater-than us. - */ - if (true_reg->min_value >= 0) - true_reg->max_value = val - 1; + true_reg->max_value = val - 1; + if (true_reg->treat_as_signed != treat_as_signed) + true_reg->min_value = BPF_REGISTER_MIN_RANGE; + if (false_reg->treat_as_signed != treat_as_signed) + false_reg->max_value = BPF_REGISTER_MAX_RANGE; + false_reg->treat_as_signed = treat_as_signed; + true_reg->treat_as_signed = treat_as_signed; break; case BPF_JGE: - true_reg->max_value = val; - /* If a positive value is unsigned-ge us, then we can't be - * negative. - */ - if ((s64)val >= 0 && true_reg->min_value < 0) - true_reg->min_value = 0; - break; + /* Unsigned comparison, min_value is 0 */ + true_reg->min_value = 0; + treat_as_signed = false; case BPF_JSGE: - false_reg->min_value = val + 1; - /* If val is signed-ge us, and we're not negative, then val - * must be unsigned-ge us. + /* k >= r => true->max = k + * k < r => false->min = k + 1 */ - if (true_reg->min_value >= 0) - true_reg->max_value = val; + false_reg->min_value = val + 1; + true_reg->max_value = val; + if (true_reg->treat_as_signed != treat_as_signed) + true_reg->min_value = BPF_REGISTER_MIN_RANGE; + if (false_reg->treat_as_signed != treat_as_signed) + false_reg->max_value = BPF_REGISTER_MAX_RANGE; + false_reg->treat_as_signed = treat_as_signed; + true_reg->treat_as_signed = treat_as_signed; break; default: break; @@ -2404,12 +2436,14 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, static void __reg_combine_min_max(struct bpf_reg_state *src_reg, struct bpf_reg_state *dst_reg) { + src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off, + dst_reg->var_off); + if (src_reg->treat_as_signed != dst_reg->treat_as_signed) + return; src_reg->min_value = dst_reg->min_value = max(src_reg->min_value, dst_reg->min_value); src_reg->max_value = dst_reg->max_value = min(src_reg->max_value, dst_reg->max_value); - src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off, - dst_reg->var_off); check_reg_overflow(src_reg); check_reg_overflow(dst_reg); } @@ -2443,6 +2477,7 @@ static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id, reg->var_off.value || reg->var_off.mask || reg->off)) { reg->min_value = reg->max_value = reg->off = 0; + reg->treat_as_signed = false; reg->var_off = tnum_const(0); } if (is_null) { @@ -2637,6 +2672,7 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) regs[insn->dst_reg].type = SCALAR_VALUE; regs[insn->dst_reg].min_value = imm; regs[insn->dst_reg].max_value = imm; + regs[insn->dst_reg].treat_as_signed = false; check_reg_overflow(®s[insn->dst_reg]); regs[insn->dst_reg].var_off = tnum_const(imm); regs[insn->dst_reg].id = 0; @@ -2927,7 +2963,8 @@ static int check_cfg(struct bpf_verifier_env *env) static bool range_within(struct bpf_reg_state *old, struct bpf_reg_state *cur) { - return old->min_value <= cur->min_value && + return old->treat_as_signed == cur->treat_as_signed && + old->min_value <= cur->min_value && old->max_value >= cur->max_value; }