| Message ID | 20250114-kcov-v1-0-004294b931a2@quicinc.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | kcov: Introduce New Unique PC|EDGE|CMP Modes | expand |
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
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.
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
On Tue, Jan 14, 2025 at 11:43:08AM +0100, Marco Elver 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? Ideally we should get the pos, but the test in syzkaller only counts how many times the overflow occurs. Actually I guess the pos is much bigger than cover size because originally we have 64KB cover size, the overflow happens; then now syzkaller set it to 1MB, but still 3535 times overflow for `ioctl$DMA_HEAP_IOCTL_ALLOC` syscall which has only 19 inputs. mmap syscall is also likely to overflow for 10873 times with 181 inputs in my case. Internally, I tried also 64MB cover size, but I still see the overflow case. Using syz-execprog together with -cover options shows many pcs are hit frequently, but disabling instrumentation for each these PC is less efficient and sometimes no lucky to fix the overflow problem. I think the overflow happens more frequent on arm64 device as I found functions in header files hit frequently. And I'm not able to access syzbot backend syz-manager data, perhaps qemu x86_64 setup has more info. > > > 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. I tried many ways to store the uniq info, like bitmap, segment bitmap, customized allocator + allocation index, also considering rhashmap, but perhaps hashmap (maybe rhashmap) is better. I also tried a full bitmap to record all PCs from all threads which shows that syzkaller can't find the new coverage while the full bitmap recorded it. If I replay the syzkaller log (or prog), kernel GCOV can also show these functions/lines are hit (not because flaky or interrupt) but syzkaller coverage doesn't have that data, which can be another proof of the kcov overflow. > > Thanks, > -- Marco
On Tue, Jan 14, 2025 at 2:00 PM Joey Jiao <quic_jiangenj@quicinc.com> wrote: > > On Tue, Jan 14, 2025 at 11:43:08AM +0100, Marco Elver 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. Hi Joey, Sorry for not responding earlier, I thought I'd come with a working proposal, but it is taking a while. You are right that kcov is prone to overflows, and we might be missing interesting coverage because of that. Recently we've been discussing the applicability of -fsanitize-coverage=trace-pc-guard to this problem, and it is almost working already. The idea is as follows: - -fsanitize-coverage=trace-pc-guard instruments basic blocks with calls to `__sanitizer_cov_trace_pc_guard(u32 *guard)`, each taking a unique 32-bit global in the __sancov_guards section; - these globals are zero-initialized, but upon the first call to __sanitizer_cov_trace_pc_guard() from each callsite, the corresponding global will receive a unique consequent number; - now we have a mapping of PCs into indices, which can we use to deduplicate the coverage: -- storing PCs by their index taken from *guard directly in the user-supplied buffer (which size will not exceed several megabytes in practice); -- using a per-task bitmap (at most hundreds of kilobytes) to mark visited basic blocks, and appending newly encountered PCs to the user-supplied buffer like it's done now. I think this approach is more promising than using hashmaps in kcov: - direct mapping should be way faster than a hashmap (and the overhead of index allocation is amortized, because they are persistent between program runs); - there cannot be collisions; - no additional complexity from pool allocations, RCU synchronization. The above approach will naturally break edge coverage, as there will be no notion of a program trace anymore. But it is still a question whether edges are helping the fuzzer, and correctly deduplicating them may not be worth the effort. If you don't object, I would like to finish prototyping coverage guards for kcov before proceeding with this review. Alex > > > 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. Note that on ARM64 this will be effectively using bits 11:2, so if I am understanding correctly more than a million coverage callbacks will be mapped into one of 1024 buckets.
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. 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, Joey Jiao --- Jiao, Joey (7): kcov: introduce new kcov KCOV_TRACE_UNIQ_PC mode kcov: introduce new kcov KCOV_TRACE_UNIQ_EDGE mode kcov: allow using KCOV_TRACE_UNIQ_[PC|EDGE] modes together kcov: introduce new kcov KCOV_TRACE_UNIQ_CMP mode kcov: add the new KCOV uniq modes example code kcov: disable instrumentation for genalloc and bitmap arm64: disable kcov instrument in header files Documentation/dev-tools/kcov.rst | 243 ++++++++++++++-------------- arch/arm64/include/asm/percpu.h | 2 +- arch/arm64/include/asm/preempt.h | 2 +- include/linux/kcov.h | 10 +- include/uapi/linux/kcov.h | 6 + kernel/kcov.c | 333 +++++++++++++++++++++++++++++++++------ lib/Makefile | 2 + 7 files changed, 423 insertions(+), 175 deletions(-) --- base-commit: 9b2ffa6148b1e4468d08f7e0e7e371c43cac9ffe change-id: 20250114-kcov-95cedece4654 Best regards,