Re: 484611357c19 introduces arbitrary kernel write bug (root-only)

[Jann Horn]

Can you resend with "git send-email" or so? "git am" says that the
patch is corrupt, likely because of line wrapping.

On Wed, Nov 9, 2016 at 10:21 PM, Josef Bacik  wrote:
> 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 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 0x1000.
>>
>
> 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 
> 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 
> Signed-off-by: Josef Bacik 
> ---
>  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 

Re: 484611357c19 introduces arbitrary kernel write bug (root-only)

[Josef Bacik]

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 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 0x1000.



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 
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 
Signed-off-by: Josef Bacik 
---
 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
+   

Re: 484611357c19 introduces arbitrary kernel write bug (root-only)

[Josef Bacik]

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 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.


Ugh crap.  I had this logic right before, but changed it to deal with the case 
of -value & -value which would make the min_value -value.  Instead if min and 
max are both positive then the min should be 0.  I'll fix this up and add a 
testcase, nice catch.



 - 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.


Yup you're right.


 - 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.


Yeah I think you're right, if we have register A min bounded at say 
REGISTER_MAX_VALUE, and then have register B not min bounded at all so we 
default to the REGISTER_MIN_VALUE we and did a add we could end up thinking the 
minimum was 0, when it could be anything.  I'll fix this as well.


Thanks for looking at all this, I'll get this fixed up in the morning with test 
cases and send it out,


Josef

Re: 484611357c19 introduces arbitrary kernel write bug (root-only)

[Andy Lutomirski]

On Tue, Nov 8, 2016 at 4: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:
>

I was curious, so I gave the code a quick read.  I also see:


+   /* PTR_TO_MAP_VALUE_ADJ is used for doing pointer math inside of a map
+* elem value.  We only allow this if we can statically verify that
+* access from this register are going to fall within the size of the
+* map element.
+*/
+   PTR_TO_MAP_VALUE_ADJ,

shouldn't this document what logical type this is?  Is it a pointer?
Is it an offset?  (It seems to be checked as though it's a pointer
with a max offset of "max_value", which makes very little sense to
me.)



regs[i].min_value = BPF_REGISTER_MIN_RANGE;
where min_value is a u64 and BPF_REGISTER_MIN_RANGE is negative.
Shouldn't those be s64?

init_reg_state() duplicates reset_reg_range_values().


That's all I've read so far.

484611357c19 introduces arbitrary kernel write bug (root-only)

[Jann Horn]

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 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 0x1000.

Here's the crasher program:
=
#define _GNU_SOURCE
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

/* start from kernel */
#define BPF_EMIT_CALL(FUNC) \
((struct bpf_insn) {\
.code  = BPF_JMP | BPF_CALL,\
.dst_reg = 0,   \
.src_reg = 0,   \
.off   = 0, \
.imm   = (FUNC) }) /* ??? */
#define BPF_MOV32_IMM(DST, IMM) \
((struct bpf_insn) {\
.code  = BPF_ALU | BPF_MOV | BPF_K, \
.dst_reg = DST, \
.src_reg = 0,   \
.off   = 0, \
.imm   = IMM })
#define BPF_REG_ARG1BPF_REG_1
#define BPF_REG_ARG2BPF_REG_2
#define BPF_REG_ARG3BPF_REG_3
#define BPF_REG_ARG4BPF_REG_4
#define BPF_REG_ARG5BPF_REG_5
#define BPF_PSEUDO_MAP_FD   1
#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \
((struct bpf_insn) {\
.code  = BPF_LD | BPF_DW | BPF_IMM, \
.dst_reg = DST, \
.src_reg = SRC, \
.off   = 0, \
.imm   = (__u32) (IMM) }),  \
((struct bpf_insn) {\
.code  = 0, /* zero is reserved opcode */   \
.dst_reg = 0,   \
.src_reg = 0,   \
.off   = 0, \
.imm   = ((__u64) (IMM)) >> 32 })
#define BPF_ALU32_IMM(OP, DST, IMM) \
((struct bpf_insn) {\
.code  = BPF_ALU | BPF_OP(OP) | BPF_K,  \
.dst_reg = DST, \
.src_reg = 0,   \
.off   = 0, \
.imm   = IMM })
#define BPF_LD_MAP_FD(DST, MAP_FD)  \
BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)
#define BPF_ALU32_REG(OP, DST, SRC) \
((struct bpf_insn) {\
.code  = BPF_ALU | BPF_OP(OP) | BPF_X,  \
.dst_reg = DST, \
.src_reg = SRC, \
.off   = 0, \
.imm   = 0 })
#define BPF_EXIT_INSN() \
((struct bpf_insn) {\
.code  = BPF_JMP | BPF_EXIT,\
.dst_reg = 0,   \
.src_reg = 0,   \
.off   = 0, \
.imm   = 0 })
/* Memory store, *(uint *) (dst_reg + off16) = src_reg */
#define BPF_STX_MEM(SIZE, DST, SRC, OFF)\
((struct bpf_insn) {\
.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM,\
.dst_reg = DST, \
.src_reg = SRC, \
.off   = OFF,   \
.imm   = 0 })
#define BPF_REG_FP  BPF_REG_10
#define BPF_MOV64_REG(DST, SRC) \
((struct bpf_insn) {\
.code  = BPF_ALU64 | BPF_MOV | BPF_X,   \
.dst_reg = DST, \
.src_reg = SRC, \
.off   = 0, \
.imm   = 0 })
#define BPF_ALU64_IMM(OP, DST, IMM) \
((struct bpf_insn) {\
.code  = BPF_ALU64 | BPF_OP(OP) | BPF_K,\
.dst_reg = DST, \
.src_reg = 0,   \
.off   = 0, \
.imm   = IMM })
#define BPF_MOV64_REG(DST, SRC) \
((struct bpf_insn) {\
.code  = BPF_ALU64 | BPF_MOV | BPF_X,   \
.dst_reg = DST,