bpf: make infinite loop detection in is_state_visited() exact
authorEduard Zingerman <eddyz87@gmail.com>
Mon, 8 Jan 2024 20:51:56 +0000 (22:51 +0200)
committerAlexei Starovoitov <ast@kernel.org>
Tue, 23 Jan 2024 22:40:22 +0000 (14:40 -0800)
commitd5b892fd607abec2a1e49b6a2afc278c329a0ee2
tree50975743c8d1ad2caf70a4487f7f37f276dd71e8
parent242d18514149d86b431b6f5db5a33579ea79ebad
bpf: make infinite loop detection in is_state_visited() exact

Current infinite loops detection mechanism is speculative:
- first, states_maybe_looping() check is done which simply does memcmp
  for R1-R10 in current frame;
- second, states_equal(..., exact=false) is called. With exact=false
  states_equal() would compare scalars for equality only if in old
  state scalar has precision mark.

Such logic might be problematic if compiler makes some unlucky stack
spill/fill decisions. An artificial example of a false positive looks
as follows:

        r0 = ... unknown scalar ...
        r0 &= 0xff;
        *(u64 *)(r10 - 8) = r0;
        r0 = 0;
    loop:
        r0 = *(u64 *)(r10 - 8);
        if r0 > 10 goto exit_;
        r0 += 1;
        *(u64 *)(r10 - 8) = r0;
        r0 = 0;
        goto loop;

This commit updates call to states_equal to use exact=true, forcing
all scalar comparisons to be exact.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20240108205209.838365-3-maxtram95@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
kernel/bpf/verifier.c