requesting stable backport for 4.1 and 4.4: 95a762e2c8c9 ("bpf: fix incorrect sign extension in check_alu_op()")
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.
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
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 */
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!
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%3Ba=su...
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
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
linux-stable-mirror@lists.linaro.org
-
Daniel Borkmann -
Greg Kroah-Hartman -
gregkh＠linuxfoundation.org
-
Jann Horn