bpf: improve verifier state equivalence
authorAlexei Starovoitov <ast@fb.com>
Fri, 6 May 2016 02:49:11 +0000 (19:49 -0700)
committerDavid S. Miller <davem@davemloft.net>
Fri, 6 May 2016 20:01:54 +0000 (16:01 -0400)
commit735b433397ea2f97d59240cbe4ea770aa7c88eef
treec2caeca835dc4a72ee04652e37274c98d4ad88eb
parent969bf05eb3cedd5a8d4b7c346a85c2ede87a6d6d
bpf: improve verifier state equivalence

since UNKNOWN_VALUE type is weaker than CONST_IMM we can un-teach
verifier its recognition of constants in conditional branches
without affecting safety.
Ex:
if (reg == 123) {
  .. here verifier was marking reg->type as CONST_IMM
     instead keep reg as UNKNOWN_VALUE
}

Two verifier states with UNKNOWN_VALUE are equivalent, whereas
CONST_IMM_X != CONST_IMM_Y, since CONST_IMM is used for stack range
verification and other cases.
So help search pruning by marking registers as UNKNOWN_VALUE
where possible instead of CONST_IMM.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
kernel/bpf/verifier.c