requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu

public inbox for stable@vger.kernel.org
 help / color / mirror / Atom feed

* requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()")
@ 2018-03-18  2:17 Jann Horn
  2018-03-18 12:57 ` Greg Kroah-Hartman
  2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
  0 siblings, 2 replies; 6+ messages in thread
From: Jann Horn @ 2018-03-18  2:17 UTC (permalink / raw)
  To: stable, security
  Cc: David S. Miller, Daniel Borkmann, Alexei Starovoitov,
	Greg Kroah-Hartman

Hi!

Someone on Twitter
(https://twitter.com/vnik5287/status/974277953394651137) is pointing
out that the BPF fix commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f
("bpf: fix incorrect sign extension in check_alu_op()") needs to be
applied all the way back to 4.4, and probably also 4.1; my "Fixes:"
tag on that commit is incorrect. I assumed that without map access,
math correctness issues don't matter, but actually, this one does
matter because check_cond_jmp_op() will omit verification for branches
that appear to be unreachable (comparison of CONST_IMM register and a
constant value). :/

FWIW, I checked by hand what the binary blob of BPF code in the linked
PoC does, and it's basically this (with some error checking and other
minor stuff omitted):

// trick the verifier into not checking any of the code below
r9 = (u32)-1
if (r9 == (s32)-1) exit 0

// read some configuration
r6 = *map_lookup_elem(MAP_FD, &0) // operation selector
r7 = *map_lookup_elem(MAP_FD, &1) // pointer to access
r8 = *map_lookup_elem(MAP_FD, &2) // value to write
r2 = map_lookup_elem(MAP_FD, &2)

if r6 == 0: // operation: read
  r3 = *r7
  *r2 = r3
  exit
if r6 == 1: // operation: get frame pointer
  *r2 = fp
  exit
*r7 = r8 // operation: write
exit

The author of the tweet does point out that this exploit is mitigated
by sanitize_dead_code() (introduced in "bpf: fix branch pruning logic"
and backported all the way), but 95a762e2c8c9 should still be applied.

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()")
  2018-03-18  2:17 requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()") Jann Horn
@ 2018-03-18 12:57 ` Greg Kroah-Hartman
  2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
  1 sibling, 0 replies; 6+ messages in thread
From: Greg Kroah-Hartman @ 2018-03-18 12:57 UTC (permalink / raw)
  To: Jann Horn
  Cc: stable, security, David S. Miller, Daniel Borkmann,
	Alexei Starovoitov

On Sat, Mar 17, 2018 at 07:17:17PM -0700, Jann Horn wrote:
> Hi!
> 
> Someone on Twitter
> (https://twitter.com/vnik5287/status/974277953394651137) is pointing
> out that the BPF fix commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f
> ("bpf: fix incorrect sign extension in check_alu_op()") needs to be
> applied all the way back to 4.4, and probably also 4.1; my "Fixes:"
> tag on that commit is incorrect. I assumed that without map access,
> math correctness issues don't matter, but actually, this one does
> matter because check_cond_jmp_op() will omit verification for branches
> that appear to be unreachable (comparison of CONST_IMM register and a
> constant value). :/

Ok, but the patch doesn't apply cleanly to 4.4.y, and I don't know the
bpf code well enough to do it myself.  Can you provide a working
backport so that I can queue it up?

thanks,

greg k-h

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op()
  2018-03-18  2:17 requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()") Jann Horn
  2018-03-18 12:57 ` Greg Kroah-Hartman
@ 2018-03-19 16:55 ` Jann Horn
  2018-03-19 16:58   ` Daniel Borkmann
                     ` (2 more replies)
  1 sibling, 3 replies; 6+ messages in thread
From: Jann Horn @ 2018-03-19 16:55 UTC (permalink / raw)
  To: stable
  Cc: security, David S. Miller, Daniel Borkmann, Alexei Starovoitov,
	Greg Kroah-Hartman

commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f upstream.

Distinguish between
BPF_ALU64|BPF_MOV|BPF_K (load 32-bit immediate, sign-extended to 64-bit)
and BPF_ALU|BPF_MOV|BPF_K (load 32-bit immediate, zero-padded to 64-bit);
only perform sign extension in the first case.

This patch differs from the mainline one because the verifier's internals
have changed in the meantime. Mainline tracks register values as 64-bit
values; however, 4.4 still stores tracked register values as 32-bit
values with sign extension. Therefore, in the case of a 32-bit op with
negative immediate, the value can't be tracked; leave the register as
UNKNOWN_VALUE (set by the preceding check_reg_arg() call).


I have manually tested this patch on top of 4.4.122. For the following BPF
bytecode:

        BPF_MOV64_IMM(BPF_REG_1, 1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_1, 1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV64_IMM(BPF_REG_1, -1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_1, -1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 2),
        BPF_MOV32_IMM(BPF_REG_0, 42),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_0, 43),
        BPF_EXIT_INSN()

Verifier output on 4.4.122 without this patch:

0: (b7) r1 = 1
1: (15) if r1 == 0x1 goto pc+1
3: (b4) (u32) r1 = (u32) 1
4: (15) if r1 == 0x1 goto pc+1
6: (b7) r1 = -1
7: (15) if r1 == 0xffffffff goto pc+1
9: (b4) (u32) r1 = (u32) -1
10: (15) if r1 == 0xffffffff goto pc+2
13: (b4) (u32) r0 = (u32) 43
14: (95) exit

Verifier output on 4.4.122+ with this patch:

0: (b7) r1 = 1
1: (15) if r1 == 0x1 goto pc+1
3: (b4) (u32) r1 = (u32) 1
4: (15) if r1 == 0x1 goto pc+1
6: (b7) r1 = -1
7: (15) if r1 == 0xffffffff goto pc+1
9: (b4) (u32) r1 = (u32) -1
10: (15) if r1 == 0xffffffff goto pc+2
 R1=inv R10=fp
11: (b4) (u32) r0 = (u32) 42
12: (95) exit

from 10 to 13: R1=imm-1 R10=fp
13: (b4) (u32) r0 = (u32) 43
14: (95) exit


This patch should be applied to linux-4.4.y and linux-4.1.y.

Signed-off-by: Jann Horn <jannh@google.com>
---
 kernel/bpf/verifier.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c14003840bc5..79e3c21a35d0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1135,7 +1135,8 @@ static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)
 				regs[insn->dst_reg].type = UNKNOWN_VALUE;
 				regs[insn->dst_reg].map_ptr = NULL;
 			}
-		} else {
+		} else if (BPF_CLASS(insn->code) == BPF_ALU64 ||
+			   insn->imm >= 0) {
 			/* case: R = imm
 			 * remember the value we stored into this reg
 			 */
-- 
2.16.2.804.g6dcf76e118-goog

^ permalink raw reply related	[flat|nested] 6+ messages in thread

* Re: [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op()
  2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
@ 2018-03-19 16:58   ` Daniel Borkmann
  2018-03-19 17:13   ` Patch "bpf: fix incorrect sign extension in check_alu_op()" has been added to the 4.4-stable tree gregkh
  2018-03-19 17:13   ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Greg Kroah-Hartman
  2 siblings, 0 replies; 6+ messages in thread
From: Daniel Borkmann @ 2018-03-19 16:58 UTC (permalink / raw)
  To: Jann Horn, stable
  Cc: security, David S. Miller, Alexei Starovoitov, Greg Kroah-Hartman

On 03/19/2018 05:55 PM, Jann Horn wrote:
> commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f upstream.
> 
> Distinguish between
> BPF_ALU64|BPF_MOV|BPF_K (load 32-bit immediate, sign-extended to 64-bit)
> and BPF_ALU|BPF_MOV|BPF_K (load 32-bit immediate, zero-padded to 64-bit);
> only perform sign extension in the first case.
> 
> This patch differs from the mainline one because the verifier's internals
> have changed in the meantime. Mainline tracks register values as 64-bit
> values; however, 4.4 still stores tracked register values as 32-bit
> values with sign extension. Therefore, in the case of a 32-bit op with
> negative immediate, the value can't be tracked; leave the register as
> UNKNOWN_VALUE (set by the preceding check_reg_arg() call).
> 
> 
> I have manually tested this patch on top of 4.4.122. For the following BPF
> bytecode:
> 
>         BPF_MOV64_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV64_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 2),
>         BPF_MOV32_IMM(BPF_REG_0, 42),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_0, 43),
>         BPF_EXIT_INSN()
> 
> Verifier output on 4.4.122 without this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> Verifier output on 4.4.122+ with this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
>  R1=inv R10=fp
> 11: (b4) (u32) r0 = (u32) 42
> 12: (95) exit
> 
> from 10 to 13: R1=imm-1 R10=fp
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> 
> This patch should be applied to linux-4.4.y and linux-4.1.y.
> 
> Signed-off-by: Jann Horn <jannh@google.com>

Acked-by: Daniel Borkmann <daniel@iogearbox.net>

Looks good, thanks Jann!

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Patch "bpf: fix incorrect sign extension in check_alu_op()" has been added to the 4.4-stable tree
  2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
  2018-03-19 16:58   ` Daniel Borkmann
@ 2018-03-19 17:13   ` gregkh
  2018-03-19 17:13   ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Greg Kroah-Hartman
  2 siblings, 0 replies; 6+ messages in thread
From: gregkh @ 2018-03-19 17:13 UTC (permalink / raw)
  To: jannh, ast, daniel, davem, gregkh; +Cc: stable, stable-commits


This is a note to let you know that I've just added the patch titled

    bpf: fix incorrect sign extension in check_alu_op()

to the 4.4-stable tree which can be found at:
    http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
     bpf-fix-incorrect-sign-extension-in-check_alu_op.patch
and it can be found in the queue-4.4 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@vger.kernel.org> know about it.


>From jannh@google.com  Mon Mar 19 18:11:54 2018
From: Jann Horn <jannh@google.com>
Date: Mon, 19 Mar 2018 17:55:52 +0100
Subject: bpf: fix incorrect sign extension in check_alu_op()
To: stable@vger.kernel.org
Cc: security@kernel.org, "David S. Miller" <davem@davemloft.net>,  Daniel Borkmann <daniel@iogearbox.net>, Alexei Starovoitov <ast@kernel.org>,  Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Message-ID: <20180319165552.146891-1-jannh@google.com>

From: Jann Horn <jannh@google.com>

commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f upstream.

Distinguish between
BPF_ALU64|BPF_MOV|BPF_K (load 32-bit immediate, sign-extended to 64-bit)
and BPF_ALU|BPF_MOV|BPF_K (load 32-bit immediate, zero-padded to 64-bit);
only perform sign extension in the first case.

This patch differs from the mainline one because the verifier's internals
have changed in the meantime. Mainline tracks register values as 64-bit
values; however, 4.4 still stores tracked register values as 32-bit
values with sign extension. Therefore, in the case of a 32-bit op with
negative immediate, the value can't be tracked; leave the register as
UNKNOWN_VALUE (set by the preceding check_reg_arg() call).


I have manually tested this patch on top of 4.4.122. For the following BPF
bytecode:

        BPF_MOV64_IMM(BPF_REG_1, 1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_1, 1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV64_IMM(BPF_REG_1, -1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 1),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_1, -1),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 2),
        BPF_MOV32_IMM(BPF_REG_0, 42),
        BPF_EXIT_INSN(),

        BPF_MOV32_IMM(BPF_REG_0, 43),
        BPF_EXIT_INSN()

Verifier output on 4.4.122 without this patch:

0: (b7) r1 = 1
1: (15) if r1 == 0x1 goto pc+1
3: (b4) (u32) r1 = (u32) 1
4: (15) if r1 == 0x1 goto pc+1
6: (b7) r1 = -1
7: (15) if r1 == 0xffffffff goto pc+1
9: (b4) (u32) r1 = (u32) -1
10: (15) if r1 == 0xffffffff goto pc+2
13: (b4) (u32) r0 = (u32) 43
14: (95) exit

Verifier output on 4.4.122+ with this patch:

0: (b7) r1 = 1
1: (15) if r1 == 0x1 goto pc+1
3: (b4) (u32) r1 = (u32) 1
4: (15) if r1 == 0x1 goto pc+1
6: (b7) r1 = -1
7: (15) if r1 == 0xffffffff goto pc+1
9: (b4) (u32) r1 = (u32) -1
10: (15) if r1 == 0xffffffff goto pc+2
 R1=inv R10=fp
11: (b4) (u32) r0 = (u32) 42
12: (95) exit

from 10 to 13: R1=imm-1 R10=fp
13: (b4) (u32) r0 = (u32) 43
14: (95) exit


Signed-off-by: Jann Horn <jannh@google.com>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
 kernel/bpf/verifier.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1135,7 +1135,8 @@ static int check_alu_op(struct verifier_
 				regs[insn->dst_reg].type = UNKNOWN_VALUE;
 				regs[insn->dst_reg].map_ptr = NULL;
 			}
-		} else {
+		} else if (BPF_CLASS(insn->code) == BPF_ALU64 ||
+			   insn->imm >= 0) {
 			/* case: R = imm
 			 * remember the value we stored into this reg
 			 */


Patches currently in stable-queue which might be from jannh@google.com are

queue-4.4/fs-aio-add-explicit-rcu-grace-period-when-freeing-kioctx.patch
queue-4.4/fs-aio-use-rcu-accessors-for-kioctx_table-table.patch
queue-4.4/bpf-fix-incorrect-sign-extension-in-check_alu_op.patch

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op()
  2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
  2018-03-19 16:58   ` Daniel Borkmann
  2018-03-19 17:13   ` Patch "bpf: fix incorrect sign extension in check_alu_op()" has been added to the 4.4-stable tree gregkh
@ 2018-03-19 17:13   ` Greg Kroah-Hartman
  2 siblings, 0 replies; 6+ messages in thread
From: Greg Kroah-Hartman @ 2018-03-19 17:13 UTC (permalink / raw)
  To: Jann Horn
  Cc: stable, security, David S. Miller, Daniel Borkmann,
	Alexei Starovoitov

On Mon, Mar 19, 2018 at 05:55:52PM +0100, Jann Horn wrote:
> commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f upstream.
> 
> Distinguish between
> BPF_ALU64|BPF_MOV|BPF_K (load 32-bit immediate, sign-extended to 64-bit)
> and BPF_ALU|BPF_MOV|BPF_K (load 32-bit immediate, zero-padded to 64-bit);
> only perform sign extension in the first case.
> 
> This patch differs from the mainline one because the verifier's internals
> have changed in the meantime. Mainline tracks register values as 64-bit
> values; however, 4.4 still stores tracked register values as 32-bit
> values with sign extension. Therefore, in the case of a 32-bit op with
> negative immediate, the value can't be tracked; leave the register as
> UNKNOWN_VALUE (set by the preceding check_reg_arg() call).
> 
> 
> I have manually tested this patch on top of 4.4.122. For the following BPF
> bytecode:
> 
>         BPF_MOV64_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV64_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 2),
>         BPF_MOV32_IMM(BPF_REG_0, 42),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_0, 43),
>         BPF_EXIT_INSN()
> 
> Verifier output on 4.4.122 without this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> Verifier output on 4.4.122+ with this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
>  R1=inv R10=fp
> 11: (b4) (u32) r0 = (u32) 42
> 12: (95) exit
> 
> from 10 to 13: R1=imm-1 R10=fp
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> 
> This patch should be applied to linux-4.4.y and linux-4.1.y.

Now queued up for 4.4.y, thanks!

greg k-h

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2018-03-19 17:13 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-03-18  2:17 requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()") Jann Horn
2018-03-18 12:57 ` Greg Kroah-Hartman
2018-03-19 16:55 ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Jann Horn
2018-03-19 16:58   ` Daniel Borkmann
2018-03-19 17:13   ` Patch "bpf: fix incorrect sign extension in check_alu_op()" has been added to the 4.4-stable tree gregkh
2018-03-19 17:13   ` [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op() Greg Kroah-Hartman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox