Issue #20448 has been updated by ms-tob (Matt S).
**TL;DR: I've been further researching how fuzzers gather coverage information, and
what types of coverage are most useful for fuzzing. I think the best course of action
regarding this request would be to implement a fairly general coverage instrumentation
approach that can be used to implement different types of coverage.**
Based on my research, I've found that there are four commonly used types of coverage:
1. Function
2. Basic block
3. Edge
4. Path
libFuzzer's SanitizerCoverage tool offers [three coverage instrumentation
points](https://clang.llvm.org/docs/SanitizerCoverage.html#instrumentation-…:
`func`, `bb`, and `edge`. So these would correspond to (1), (2), and (3) above.
AFL's coverage instrumentation implements [edge
coverage](https://github.com/mirrorer/afl/blob/master/docs/technical_detail….
This corresponds to (3) above.
I have not seen any practical fuzzers that implement (4) above. I believe this is likely
due to the state explosion of trying to track all unique paths through a program. So, if
we can implement functionality in the `TracePoint` module to gather coverage information
for instrumentation points (1), (2), and (3), then I think we will cover the vast majority
of use-cases. libFuzzer and AFL are far and away the two most popular fuzzers. Instead of
focusing solely on my specific use-case, I think it's a good idea to enable a
generalized solution that others can test out different fuzzing strategies with.
The good news is I think supporting (1) above is already possible with the `call`,
`a_call`, `b_call`, and `c_call` `TracePoint` events. However, function based
instrumentation is the least useful in my opinion. I see function -> basic block ->
edge tracking as least to most granular. The tradeoff here is higher granularity requires
potentially more memory and compute time, although I think it's negligible in this
case.
So, if Ruby already supports events for (1), and we're discarding (4), then that
leaves us with (2) and (3). Fortunately, both (2) and (3) can be implemented based on a
[control-flow
graph](https://en.wikipedia.org/wiki/Control-flow_graph) (CFG) generated
from branch events. The main difference here is that basic block coverage is simply branch
destinations, whereas edge coverage is branch sources + branch destinations. In other
words, basic blocks are simply `(branch_dst)` and edges are `(branch_src, branch_dst)`.
This is described well in AFL's [coverage
measurement](https://github.com/mirrorer/afl/blob/master/docs/technical_det…
technical documentation.
I've been reading up on this quite a bit, so I've picked out a few quotations to
back up my claims:
... tracking accurate path coverage is infeasible in
practice, but tracking edge and block coverage are possible. The edge coverage provided by
AFL provides more information than block coverage solutions.
- [CollAFL: Path Sensitive
Fuzzing](https://wcventure.github.io/FuzzingPaper/Paper/SP18_ColLAFL.pdf)
AFL [60] leverages edge coverage (a.k.a. branch
coverage or transition coverage), and libFuzzer [47] supports both edge and block
coverage.
- [Not All Coverage Measurements Are Equal: Fuzzing by Coverage Accounting for Input
Prioritization](https://www.ndss-symposium.org/wp-content/uploads/2020/02/2…
The number of unique paths (#paths) continues to be a
common performance measure for greybox fuzzers [17, 18, 68] despite its obvious flaws [36,
38]. The number of unique edges (#edges), reported as map size by AFL-based fuzzers, is
often used as a proxy for branch coverage. AFL maintains a fixed-size hashmap containing
an entry for every tuple of conditional jumps that are sequentially exercised in the
program.
- [On the Reliability of Coverage-Based Fuzzer
Benchmarking](https://mboehme.github.io/paper/ICSE22.pdf)
Branch coverage is a straightforward yet effective
enhancement over block coverage, which is the most basic one that can only tell which code
block is visited. By involving the code block preceding the currently visited one, branch
coverage can differentiate the visits of the same code block from different predecessors.
Branch here means an edge from one code block to another one. Ideally, branch coverage
should be measured as a tuple (prev_block, cur_block), where prev_block and cur_block
stand for the previous block ID and the current block ID, respectively. In practice,
branch coverage is usually measured by hashing this tuple (as key) into a hash table
(e.g., a hit_count map).
- [Be Sensitive and Collaborative: Analyzing Impact of Coverage Metrics in Greybox
Fuzzing](https://www.usenix.org/system/files/raid2019-wang-jinghan.pdf)
I believe we can achieve both basic block and edge coverage instrumentation with the
following API:
```ruby
TracePoint.enable_branch_tracepoints
TracePoint.new(:branch) do |tp|
p tp.branch_src #=> [src_id, src_first_lineno, src_first_column, src_last_lineno,
src_last_column]
p tp.branch_dst #=> [dst_id, dst_first_lineno, dst_first_column, dst_last_lineno,
dst_last_column]
end.enable
load "target.rb"
TracePoint.disable_branch_tracepoints
```
In this case, the `src` is the location in code of the branch statement (e.g. the `if`
statement), and the `dst` is the location in code where execution will continue after the
branch statement (i.e. which branch is taken). If a fuzzer would like to track basic
blocks, they can use only `branch_dst`. If they'd like to track edges, they can use
both `branch_src` and `branch_dst`. This would allow fuzzers flexibility in their
implementation and allow them to experiment with different instrumentation points to
optimize the fuzzing process. It would also allow Ruby fuzzers to be built on both AFL and
libFuzzer, which enables further experimentation and options.
One small edge case: we will likely want to consider [critical
edges](https://en.wikipedia.org/wiki/Control-flow_graph#Special_edges) as well. This is an
implementation detail, and shouldn't impact the overall API of the functionality.
I think this would be a good, generalized solution that many parties interested in fuzzing
could experiment with. Let me know what you think of this proposal. I have a much better
understanding of how fuzzers implement and use coverage information now, so I hope this
additional information helps.
----------------------------------------
Feature #20448: Make coverage event hooking C API public
https://bugs.ruby-lang.org/issues/20448#change-108322
* Author: ms-tob (Matt S)
* Status: Open
----------------------------------------
# Abstract
Gathering code coverage information is a well-known goal within software engineering. It
is most commonly used to assess code coverage during automated testing. A lesser known
use-case is coverage-guided fuzz testing, which will be the primary use-case presented in
this issue. This issue exists to request that Ruby coverage event hooking be made part of
its official, public C API.
# Background
Ruby currently provides a number of avenues for hooking events *or* gathering coverage
information:
1. The [
Coverage](https://ruby-doc.org/3.3.0/exts/coverage/Coverage.html) module
2. The [
TracePoint](https://ruby-doc.org/3.3.0/TracePoint.html) module
3. The
[
rb_add_event_hook](https://ruby-doc.org/3.3.0/extension_rdoc.html#label-Hoo…
extension function
Unfortunately, none of these pieces of functionality solve this issue's specific
use-case. The `Coverage` module is not a great fit for real-time coverage analysis with an
unknown start and stop point. Coverage-guided fuzz testing requires this. The `TracePoint`
module and `rb_add_event_hook` are not able to hook branch and line coverage events.
Coverage-guided fuzz testing typically tracks branch events.
# Proposal
The ultimate goal is to enable Ruby C extensions to process coverage events in real-time.
I did some cursory investigation into the Ruby C internals to determine what it would take
to achieve this, but I'm by no means an expert, so my list may be incomplete.
The good news is that much of this functionality already exists, but it's part of the
private, internal-only C API.
1. Make `RUBY_EVENT_COVERAGE_LINE` and `RUBY_EVENT_COVERAGE_BRANCH` public:
https://github.com/ruby/ruby/blob/v3_3_0/vm_core.h#L2182-L2184
a. This would be an addition to the current public event types:
https://github.com/ruby/ruby/blob/v3_3_0/include/ruby/internal/event.h#L32-…
2. Allow initializing global coverage state so that coverage tracking can be fully
enabled
a. Currently, if `Coverage.setup` or `Coverage.start` is not called, then coverage
events cannot be hooked. I do not fully understand why this is, but I believe it has
something to do with `rb_get_coverages` and `rb_set_coverages`. If calls to
`rb_get_coverages` return `NULL`
(
https://github.com/ruby/ruby/blob/v3_3_0/iseq.c#L641-L647,
https://github.com/ruby/ruby/blob/v3_3_0/iseq.c#L864-L868), then coverage hooking will not
be enabled. I believe the `Coverage` module initializes that state via a
`rb_set_coverages` call here:
https://github.com/ruby/ruby/blob/v3_3_0/ext/coverage/coverage.c#L112-L120.
b. So, to achieve this goal, a C extension would need to be able to call
`rb_set_coverages` or somehow initialize the global coverage state.
I've actually been able to achieve this functionality by calling undocumented features
and defining `RUBY_EVENT_COVERAGE_BRANCH`:
```c
#include <ruby.h>
#include <ruby/debug.h>
#define RUBY_EVENT_COVERAGE_BRANCH 0x020000
// ...
rb_event_flag_t events = RUBY_EVENT_COVERAGE_BRANCH;
rb_event_hook_flag_t flags = (
RUBY_EVENT_HOOK_FLAG_SAFE | RUBY_EVENT_HOOK_FLAG_RAW_ARG
);
rb_add_event_hook2(
(rb_event_hook_func_t) event_hook_branch,
events,
counter_hash,
flags
);
```
If I call `Coverage.setup(branches: true)`, and add this event hook, then branch hooking
works as expected. `rb_add_event_hook2` will still respect the
`RUBY_EVENT_COVERAGE_BRANCH` value if its passed. But it would be better if I could rely
on official functionality rather than undocumented features.
The above two points would be requirements for this functionality, but there's an
additional nice-to-have:
3. Extend the public `tracearg` functionality to include additional coverage information
a. Currently, `tracearg` offers information like `rb_tracearg_lineno` and
`rb_tracearg_path`. It would be helpful if it also provided additional coverage
information like `coverage.c`'s column information and a unique identifier for each
branch. Currently, I can only use `(path, lineno)` as a unique identifier for a branch
because that's what's offered by the public API, but more information like column
number would be helpful for uniquely identify branches. Since there can be multiple `if`
statements on a single line, this can provide ambiguous identification for a branch
event.
# Use cases
This use-case was born out of a new coverage-guided Ruby fuzzer:
https://github.com/trailofbits/ruzzy. You can read more about its implementation details
here:
https://blog.trailofbits.com/2024/03/29/introducing-ruzzy-a-coverage-guided….
You can also find the Ruby C extension code behind its implementation here:
https://github.com/trailofbits/ruzzy/blob/v0.7.0/ext/cruzzy/cruzzy.c#L220-L….
So, the primary use-case here is enabling real-time, coverage-guided fuzz testing of Ruby
code. However, as mentioned in the abstract, gathering code coverage information is useful
in many domains. For example, it could enable new workflows in standard unit/integration
test coverage. It could also enable gathering coverage information in real-time as an
application is running. I see this as the most generalized form of gathering code coverage
information, and something like the `Coverage` module as a specialized implementation.
Another example,
https://bugs.ruby-lang.org/issues/20282 may be solved by this more
generalized solution.
We are tracking this request downstream here:
https://github.com/trailofbits/ruzzy/issues/9
# Discussion
Fuzz testing is another tool in a testers toolbelt. It is an increasingly common way to
improve software's robustness. Go has it built in to the standard library, Python has
Atheris, Java has Jazzer, JavaScript has Jazzer.js, etc. OSS-Fuzz has helped identify and
fix over 10,000 vulnerabilities and 36,000 bugs [using
fuzzing](https://google.github.io/oss-fuzz/#trophies). Ruby deserves a good fuzzer, and
improving coverage gathering would help achieve that goal.
The `Coverage` module, `TracePoint` module, and `rb_add_event_hook` function seem like
they could fulfill this goal. However, after deeper investigation, none of them fit the
exact requirements for this use-case.
# See also
-
https://bugs.ruby-lang.org/issues/20282
-
https://github.com/google/atheris
-
https://security.googleblog.com/2020/12/how-atheris-python-fuzzer-works.html
-
https://github.com/CodeIntelligenceTesting/jazzer/
-
https://www.code-intelligence.com/blog/java-fuzzing-with-jazzer
-
https://go.dev/doc/security/fuzz/
--
https://bugs.ruby-lang.org/