Patch "bpf, verifier: fix alu ops against map_value{, _adj} register types" has been added to the 4.9-stable tree

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

bpf, verifier: fix alu ops against map_value{, _adj} register types

to the 4.9-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-verifier-fix-alu-ops-against-map_value-_adj-register-types.patch
and it can be found in the queue-4.9 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

From: Daniel Borkmann <[email protected]>
Date: Fri, 31 Mar 2017 02:24:02 +0200
Subject: bpf, verifier: fix alu ops against map_value{, _adj} register types

From: Daniel Borkmann <[email protected]>

[ Upstream commit fce366a9dd0ddc47e7ce05611c266e8574a45116 ]

While looking into map_value_adj, I noticed that alu operations directly on the map_value() resp. map_value_adj() register (any alu operation on a map_value() register will turn it into a map_value_adj() typed register) are not sufficiently protected against some of the operations. Two non-exhaustive examples are provided that the verifier needs to reject:

i) BPF_AND on r0 (map_value_adj):

0: (bf) r2 = r10
1: (07) r2 += -8
2: (7a) *(u64 *)(r2 +0) = 0
3: (18) r1 = 0xbf842a00
5: (85) call bpf_map_lookup_elem#1
6: (15) if r0 == 0x0 goto pc+2
R0=map_value(ks=8,vs=48,id=0),min_value=0,max_value=0 R10=fp
7: (57) r0 &= 8
8: (7a) *(u64 *)(r0 +0) = 22
R0=map_value_adj(ks=8,vs=48,id=0),min_value=0,max_value=8 R10=fp
9: (95) exit

from 6 to 9: R0=inv,min_value=0,max_value=0 R10=fp 9: (95) exit
processed 10 insns

ii) BPF_ADD in 32 bit mode on r0 (map_value_adj):

0: (bf) r2 = r10
1: (07) r2 += -8
2: (7a) *(u64 *)(r2 +0) = 0
3: (18) r1 = 0xc24eee00
5: (85) call bpf_map_lookup_elem#1
6: (15) if r0 == 0x0 goto pc+2
R0=map_value(ks=8,vs=48,id=0),min_value=0,max_value=0 R10=fp
7: (04) (u32) r0 += (u32) 0
8: (7a) *(u64 *)(r0 +0) = 22
R0=map_value_adj(ks=8,vs=48,id=0),min_value=0,max_value=0 R10=fp
9: (95) exit

from 6 to 9: R0=inv,min_value=0,max_value=0 R10=fp 9: (95) exit
processed 10 insns

Issue is, while min_value / max_value boundaries for the access are adjusted appropriately, we change the pointer value in a way that cannot be sufficiently tracked anymore from its origin. Operations like BPF_{AND,OR,DIV,MUL,etc} on a destination register that is PTR_TO_MAP_VALUE{,_ADJ} was probably unintended, in fact, all the test cases coming with 484611357c19 ("bpf: allow access into map value arrays") perform BPF_ADD only on the destination register that is PTR_TO_MAP_VALUE_ADJ.

Only for UNKNOWN_VALUE register types such operations make sense, f.e. with unknown memory content fetched initially from a constant offset from the map value memory into a register. That register is then later tested against lower / upper bounds, so that the verifier can then do the tracking of min_value / max_value, and properly check once that UNKNOWN_VALUE register is added to the destination register with type PTR_TO_MAP_VALUE{,_ADJ}. This is also what the original use-case is solving. Note, tracking on what is being added is done through adjust_reg_min_max_vals() and later access to the map value enforced with these boundaries and the given offset from the insn through check_map_access_adj().

Tests will fail for non-root environment due to prohibited pointer arithmetic, in particular in check_alu_op(), we bail out on the is_pointer_value() check on the dst_reg (which is false in root case as we allow for pointer arithmetic via env->allow_ptr_leaks).

Similarly to PTR_TO_PACKET, one way to fix it is to restrict the allowed operations on PTR_TO_MAP_VALUE{,_ADJ} registers to 64 bit mode BPF_ADD. The test_verifier suite runs fine after the patch and it also rejects mentioned test cases.

---
 kernel/bpf/verifier.c |    1 +
 1 file changed, 1 insertion(+)

@@ -1870,6 +1870,7 @@ static int check_alu_op(struct bpf_verif
 		 * register as unknown.
 		 */
 		if (env->allow_ptr_leaks &&
+		    BPF_CLASS(insn->code) == BPF_ALU64 && opcode == BPF_ADD &&
 		    (dst_reg->type == PTR_TO_MAP_VALUE ||
 		     dst_reg->type == PTR_TO_MAP_VALUE_ADJ))
 			dst_reg->type = PTR_TO_MAP_VALUE_ADJ;

Patches currently in stable-queue which might be from [email protected] are

queue-4.9/bpf-adjust-verifier-heuristics.patch queue-4.9/bpf-verifier-add-additional-patterns-to-evaluate_reg_imm_alu.patch queue-4.9/bpf-fix-bpf_trace_printk-on-32-bit-archs.patch queue-4.9/bpf-verifier-fix-alu-ops-against-map_value-_adj-register-types.patch queue-4.9/bpf-fix-mixed-signed-unsigned-derived-min-max-value-bounds.patch queue-4.9/bpf-verifier-fix-min-max-handling-in-bpf_sub.patch