bpf: fix stacksafe exploration when comparing states

Commit cc2b14d51053 ("bpf: teach verifier to recognize zero initialized stack") introduced a very relaxed check when comparing stacks of different states, effectively returning a positive result in many cases where it shouldn't.

This can create problems in cases such as this following C pseudocode:

long var;
long *x = bpf_map_lookup(...);
if (!x)

        return;

if (*x != 0xbeef)

        var = 0;
else
        var = 1;

/* This is the key part, calling a helper causes an explored state
* to be saved with the information that "var" is on the stack as
* STACK_ZERO, since the helper is first met by the verifier after
* the "var = 0" assignment. This state will however be wrongly used
* also for the "var = 1" case, so the verifier assumes "var" is always
* 0 and will replace the NULL assignment with nops, because the
* search pruning prevents it from exploring the faulty branch. */
bpf_ktime_get_ns();

if (var)

        *(long *)0 = 0xbeef;

Fix the issue by making sure that the stack is fully explored before returning a positive comparison result.

Also attach a couple tests that highlight the bad behavior. In the first test, without this fix instructions 16 and 17 are replaced with nops instead of being rejected by the verifier.

The second test, instead, allows a program to make a potentially illegal read from the stack.

---
 kernel/bpf/verifier.c                       |  2 +-
 tools/testing/selftests/bpf/test_verifier.c | 51 +++++++++++++++++++++++++++++
 2 files changed, 52 insertions(+), 1 deletion(-)

index 8b442ae125d0..93e1c77dae1d 100644
@@ -4107,7 +4107,7 @@ static bool stacksafe(struct bpf_func_state *old,
 
 		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ))
 			/* explored state didn't use this */
-			return true;
+			continue;
 
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;

2.14.1

On Sat, Dec 23, 2017 at 10:09:55AM +0000, Gianluca Borello wrote:
...