| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Wed, 9 Nov 2016 16:21:39 -0500
From: Josef Bacik <jbacik@...com>
To: Jann Horn <jannh@...gle.com>,
Daniel Borkmann <daniel@...earbox.net>,
Alexei Starovoitov <ast@...nel.org>,
"David S. Miller" <davem@...emloft.net>
CC: <security@...nel.org>, <netdev@...r.kernel.org>
Subject: Re: 484611357c19 introduces arbitrary kernel write bug (root-only)
On 11/08/2016 07:23 PM, Jann Horn wrote:
> In 484611357c19 (not in any stable kernel yet), functionality is
> introduced that allows root (and afaics nobody else, since nobody else
> is allowed to perform pointer arithmetic) to basically write to (and
> read from) arbitrary kernel memory. There are multiple bugs in the
> validation logic:
>
> - A bitwise AND of values in the ranges [a,b] and [c,d] is assumed to
> always result in a value
> >= a&b. However, for the combination of ranges [1,1] and [1,2],
> this calculates a minimum of 1
> while actually, 1&2 is zero. This is the bug that my crasher
> (below) triggers.
> - a%b is assumed to always be smaller than b-1. However, for b==0,
> this will calculate an upper
> limit of -1 while the values will actually always be zero.
> - I'm not sure about this, but I think that, when only one end of the
> range is bounded, the logic will
> incorrectly also treat the other end as a bounded, and because of
> the usage of bound
> placeholders that are smaller than the actual maximum values, this
> could be used to perform
> out-of-bounds accesses.
>
> The fun part here is that, as soon as the validation is just
> off-by-one, arithmetic transformations can be used to turn that into
> out-of-bounds accesses at arbitrary offsets. The crasher turns the
> off-by-one into a memory write at offset 0x10000000.
>
Can you give this a whirl? It addresses your testcase and the other issues
you've brought up. Thanks
From e47a1de98af2c1bcebd4224f546e3be1fd340b6a Mon Sep 17 00:00:00 2001
From: Josef Bacik <jbacik@...com>
Date: Wed, 9 Nov 2016 16:09:52 -0500
Subject: [PATCH] bpf: fix range arithmetic for bpf map access
I made some invalid assumptions with BPF_AND and BPF_MOD that could result in
invalid accesses to bpf map entries. Fix this up by doing a few things
1) Kill BPF_MOD support. This doesn't actually get used by the compiler in real
life and just adds extra complexity.
2) Fix the logic for BPF_AND. If the min value is negative then that is the new
minimum, otherwise it is unconditionally 0.
3) Don't do operations on the ranges if they are set to the limits, as they are
by definition undefined, and allowing arithmetic operations on those values
could make them appear valid when they really aren't.
This fixes the testcase provided by Jann as well as a few other theoretical
problems.
Reported-by: Jann Horn <jannh@...gle.com>
Signed-off-by: Josef Bacik <jbacik@...com>
---
include/linux/bpf_verifier.h | 3 +-
kernel/bpf/verifier.c | 65 ++++++++++++++++++++++++++++----------------
2 files changed, 44 insertions(+), 24 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index ac5b393..15ceb7f 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -22,7 +22,8 @@ struct bpf_reg_state {
* Used to determine if any memory access using this register will
* result in a bad access.
*/
- u64 min_value, max_value;
+ s64 min_value;
+ u64 max_value;
u32 id;
union {
/* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9002575..840533a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -234,8 +234,8 @@ static void print_verifier_state(struct bpf_verifier_state
*state)
reg->map_ptr->value_size,
reg->id);
if (reg->min_value != BPF_REGISTER_MIN_RANGE)
- verbose(",min_value=%llu",
- (unsigned long long)reg->min_value);
+ verbose(",min_value=%lld",
+ (long long)reg->min_value);
if (reg->max_value != BPF_REGISTER_MAX_RANGE)
verbose(",max_value=%llu",
(unsigned long long)reg->max_value);
@@ -1490,7 +1490,7 @@ static void check_reg_overflow(struct bpf_reg_state *reg)
{
if (reg->max_value > BPF_REGISTER_MAX_RANGE)
reg->max_value = BPF_REGISTER_MAX_RANGE;
- if ((s64)reg->min_value < BPF_REGISTER_MIN_RANGE)
+ if (reg->min_value < BPF_REGISTER_MIN_RANGE)
reg->min_value = BPF_REGISTER_MIN_RANGE;
}
@@ -1498,7 +1498,8 @@ static void adjust_reg_min_max_vals(struct
bpf_verifier_env *env,
struct bpf_insn *insn)
{
struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg;
- u64 min_val = BPF_REGISTER_MIN_RANGE, max_val = BPF_REGISTER_MAX_RANGE;
+ s64 min_val = BPF_REGISTER_MIN_RANGE;
+ u64 max_val = BPF_REGISTER_MAX_RANGE;
bool min_set = false, max_set = false;
u8 opcode = BPF_OP(insn->code);
@@ -1534,22 +1535,45 @@ static void adjust_reg_min_max_vals(struct
bpf_verifier_env *env,
return;
}
+ /* If one of our values was at the end of our ranges then we can't just
+ * do our normal operations to the register, we need to set the values
+ * to the min/max since they are undefined.
+ */
+ if (min_val == BPF_REGISTER_MIN_RANGE)
+ dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
+ if (max_val == BPF_REGISTER_MAX_RANGE)
+ dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
+
switch (opcode) {
case BPF_ADD:
- dst_reg->min_value += min_val;
- dst_reg->max_value += max_val;
+ if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
+ dst_reg->min_value += min_val;
+ if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
+ dst_reg->max_value += max_val;
break;
case BPF_SUB:
- dst_reg->min_value -= min_val;
- dst_reg->max_value -= max_val;
+ if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
+ dst_reg->min_value -= min_val;
+ if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
+ dst_reg->max_value -= max_val;
break;
case BPF_MUL:
- dst_reg->min_value *= min_val;
- dst_reg->max_value *= max_val;
+ if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
+ dst_reg->min_value *= min_val;
+ if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
+ dst_reg->max_value *= max_val;
break;
case BPF_AND:
- /* & is special since it could end up with 0 bits set. */
- dst_reg->min_value &= min_val;
+ /* & is special since it's could be any value within our range,
+ * including 0. But if the thing we're AND'ing against is
+ * negative and we're negative then that's the minimum value,
+ * otherwise the minimum will always be 0.
+ */
+ if (min_val < 0 && dst_reg->min_value < 0)
+ dst_reg->min_value = min_t(s64, dst_reg->min_value,
+ min_val);
+ else
+ dst_reg->min_value = 0;
dst_reg->max_value = max_val;
break;
case BPF_LSH:
@@ -1559,24 +1583,19 @@ static void adjust_reg_min_max_vals(struct
bpf_verifier_env *env,
*/
if (min_val > ilog2(BPF_REGISTER_MAX_RANGE))
dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
- else
+ else if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
dst_reg->min_value <<= min_val;
if (max_val > ilog2(BPF_REGISTER_MAX_RANGE))
dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
- else
+ else if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
dst_reg->max_value <<= max_val;
break;
case BPF_RSH:
- dst_reg->min_value >>= min_val;
- dst_reg->max_value >>= max_val;
- break;
- case BPF_MOD:
- /* % is special since it is an unsigned modulus, so the floor
- * will always be 0.
- */
- dst_reg->min_value = 0;
- dst_reg->max_value = max_val - 1;
+ if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
+ dst_reg->min_value >>= min_val;
+ if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
+ dst_reg->max_value >>= max_val;
break;
default:
reset_reg_range_values(regs, insn->dst_reg);
--
2.5.5
Powered by blists - more mailing lists