Clarification on PointerArithmetic Strategy's Boundary Check

[marckwei]

Hi,

I have been reviewing the PointerArithmetic strategy in the buzzer project and I have some questions regarding the logic used to determine if a boundary write has occurred. Specifically, I am confused about the comparison of the contents at key 0 and key 1 in the map to determine if a boundary write has occurred.

Code in Question:

// Footer part of the GenerateProgram method
footer, err := InstructionSequence(
    // Select a random register and store its value in R8.
    Mov64(R8, RandomRegister()),

    // Load a fd to the map.
    LdMapByFd(R9, pa.mapFd),

    // Begin by writing a value to the map without ptr arithmetic.
    StW(R10, 0, -4),
    Mov64(R2, R10),
    Add64(R2, -4),
    Mov64(R1, R9),
    Call(MapLookup),
    JmpNE(R0, 0, 1),
    Exit(),
    StDW(R0, 0xCAFE, 0),

    // Now repeat the operation but doing pointer arithmetic.
    StW(R10, 1, -4),
    Mov64(R2, R10),
    Add64(R2, -4),
    Mov64(R1, R9),
    Call(MapLookup),
    JmpNE(R0, 0, 1),
    Exit(),

    // Do math with the random register selected at the start.
    Add64(R0, R8),
    StDW(R0, 0xCAFE, 0),

    // Exit
    Mov64(R0, 0),
    Exit(),
)

Issue:

The strategy compares the contents at key 0 and key 1 in the map to determine if a boundary write has occurred:

func (pa *PointerArithmetic) OnExecuteDone(ffi *units.FFI, executionResult *fpb.ExecutionResult) bool {
    mapElements, err := ffi.GetMapElements(pa.mapFd, 2)
    if err != nil {
        fmt.Println(err)
        return true
    }

    return mapElements.Elements[0] == mapElements.Elements[1]
}

However, if R8 is not zero, the pointer arithmetic will cause the value to be written to an offset location, which means the contents at key 0 and key 1 will inherently be different. This makes the comparison unreliable for detecting boundary writes.

Questions:

1. Is the intention to detect boundary writes by comparing the contents at key 0 and key 1?
2. If so, how does this logic account for the offset introduced by R8?

I appreciate any clarification or guidance you can provide on this matter.

Thank you!

[thatjiaozi]

Hi

Thanks for your question.

The goal of the pointer arithmetic strategy (and any other strategy of buzzer) is to fuzz for logic bugs in the verifier.

You are right that if R8 is not zero, then the contents of index 0 and 1 will be different at run time, this is precisely what we are looking for.

If the verifier thought that it was safe to add R8 to the map element, then the verifier also thought that R8 was 0, because this is the only value that it considers safe to add to map pointers.

If, however at runtime of the bpf program we detect that R8 was not 0, in other words that the verifier was wrong, then we can take that corrupted R8 register and turn it into an LPE exploit, this is more or less what happened with CVE-2023-2163 (https://github.com/google/security-research/tree/master/pocs/linux/cve-2023-2163)

That being said. I recently discovered that this strategy is not as efficient as I thought because the verifier does some instruction patching that effectively mitigate these kind of attacks (https://elixir.bootlin.com/linux/v6.9.5/source/kernel/bpf/verifier.c#L19747)