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

[Joey Jiao <quic_jiangenj@quicinc.com>]

On Tue, Jan 14, 2025 at 12:02:31PM +0100, Dmitry Vyukov wrote:
> On Tue, 14 Jan 2025 at 11:43, Marco Elver <elver@google.com> wrote:
> > 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.
> 
> Joey, do you have corresponding patches for syzkaller? I wonder how
> the integration looks like, in particular when/how these maps are
> cleared.
Uploaded in https://github.com/google/syzkaller/pull/5673