Re: [PATCH 0/7] kcov: Introduce New Unique PC|EDGE|CMP Modes

[Marco Elver <elver@google.com>]

On Tue, 14 Jan 2025 at 06:35, Jiao, Joey <quic_jiangenj@quicinc.com> wrote:
>
> Hi,
>
> This patch series introduces new kcov unique modes:
> `KCOV_TRACE_UNIQ_[PC|EDGE|CMP]`, which are used to collect unique PC, EDGE,
> CMP information.
>
> Background
> ----------
>
> In the current kcov implementation, when `__sanitizer_cov_trace_pc` is hit,
> the instruction pointer (IP) is stored sequentially in an area. Userspace
> programs then read this area to record covered PCs and calculate covered
> edges.  However, recent syzkaller runs show that many syscalls likely have
> `pos > t->kcov_size`, leading to kcov overflow. To address this issue, we
> introduce new kcov unique modes.

Overflow by how much? How much space is missing?

> Solution Overview
> -----------------
>
> 1. [P 1] Introduce `KCOV_TRACE_UNIQ_PC` Mode:
>    - Export `KCOV_TRACE_UNIQ_PC` to userspace.
>    - Add `kcov_map` struct to manage memory during the KCOV lifecycle.
>      - `kcov_entry` struct as a hashtable entry containing unique PCs.
>      - Use hashtable buckets to link `kcov_entry`.
>      - Preallocate memory using genpool during KCOV initialization.
>      - Move `area` inside `kcov_map` for easier management.
>    - Use `jhash` for hash key calculation to support `KCOV_TRACE_UNIQ_CMP`
>      mode.
>
> 2. [P 2-3] Introduce `KCOV_TRACE_UNIQ_EDGE` Mode:
>    - Save `prev_pc` to calculate edges with the current IP.
>    - Add unique edges to the hashmap.
>    - Use a lower 12-bit mask to make hash independent of module offsets.
>    - Distinguish areas for `KCOV_TRACE_UNIQ_PC` and `KCOV_TRACE_UNIQ_EDGE`
>      modes using `offset` during mmap.
>    - Support enabling `KCOV_TRACE_UNIQ_PC` and `KCOV_TRACE_UNIQ_EDGE`
>      together.
>
> 3. [P 4] Introduce `KCOV_TRACE_UNIQ_CMP` Mode:
>    - Shares the area with `KCOV_TRACE_UNIQ_PC`, making these modes
>      exclusive.
>
> 4. [P 5] Add Example Code Documentation:
>    - Provide examples for testing different modes:
>      - `KCOV_TRACE_PC`: `./kcov` or `./kcov 0`
>      - `KCOV_TRACE_CMP`: `./kcov 1`
>      - `KCOV_TRACE_UNIQ_PC`: `./kcov 2`
>      - `KCOV_TRACE_UNIQ_EDGE`: `./kcov 4`
>      - `KCOV_TRACE_UNIQ_PC|KCOV_TRACE_UNIQ_EDGE`: `./kcov 6`
>      - `KCOV_TRACE_UNIQ_CMP`: `./kcov 8`
>
> 5. [P 6-7] Disable KCOV Instrumentation:
>    - Disable instrumentation like genpool to prevent recursive calls.
>
> Caveats
> -------
>
> The userspace program has been tested on Qemu x86_64 and two real Android
> phones with different ARM64 chips. More syzkaller-compatible tests have
> been conducted. However, due to limited knowledge of other platforms,
> assistance from those with access to other systems is needed.
>
> Results and Analysis
> --------------------
>
> 1. KMEMLEAK Test on Qemu x86_64:
>    - No memory leaks found during the `kcov` program run.
>
> 2. KCSAN Test on Qemu x86_64:
>    - No KCSAN issues found during the `kcov` program run.
>
> 3. Existing Syzkaller on Qemu x86_64 and Real ARM64 Device:
>    - Syzkaller can fuzz, show coverage, and find bugs. Adjusting `procs`
>      and `vm mem` settings can avoid OOM issues caused by genpool in the
>      patches, so `procs:4 + vm:2GB` or `procs:4 + vm:2GB` are used for
>      Qemu x86_64.
>    - `procs:8` is kept on Real ARM64 Device with 12GB/16GB mem.
>
> 4. Modified Syzkaller to Support New KCOV Unique Modes:
>    - Syzkaller runs fine on both Qemu x86_64 and ARM64 real devices.
>      Limited `Cover overflows` and `Comps overflows` observed.
>
> 5. Modified Syzkaller + Upstream Kernel Without Patch Series:
>    - Not tested. The modified syzkaller will fall back to `KCOV_TRACE_PC`
>      or `KCOV_TRACE_CMP` if `ioctl` fails for Unique mode.
>
> Possible Further Enhancements
> -----------------------------
>
> 1. Test more cases and setups, including those in syzbot.
> 2. Ensure `hash_for_each_possible_rcu` is protected for reentrance
>    and atomicity.
> 3. Find a simpler and more efficient way to store unique coverage.
>
> Conclusion
> ----------
>
> These patches add new kcov unique modes to mitigate the kcov overflow
> issue, compatible with both existing and new syzkaller versions.

Thanks for the analysis, it's clearer now.

However, the new design you introduce here adds lots of complexity.
Answering the question of how much overflow is happening, might give
better clues if this is the best design or not. Because if the
overflow amount is relatively small, a better design (IMHO) might be
simply implementing a compression scheme, e.g. a simple delta
encoding.

Thanks,
-- Marco