Some problems with afl integration about k-scheduler HOT 4 CLOSED

Hi Manda,

Thanks for your interest in K-Scheduler!

1. K-Scheduler would incur slight runtime overhead due to the graph centrality analysis, but our evaluation results show that the drop in fuzzing throughput would not affect fuzzing performance. What do you mean by "discrepancy when there is no calculation"?
2. Regarding llvm sanitizer coverage, please look at the official llvm documents https://clang.llvm.org/docs/SanitizerCoverage.html. In short, llvm sanitizer coverage is collision-free instrumentation widely used in fuzzers (e.g., AFL++'s default instrumentation is an inline version of llvm sanitizer edge coverage with the pruning feature). In K-Scheduler, we use the default setting of llvm sanitizer edge coverage without the pruning feature. I am guessing you were asking, since we are instrumenting the edge (the C code snippet in your post), why can we delete nodes (the Python code snippet in your post)?

The short answer is that "edge coverage without prune feature" = "node coverage" + "critical edge coverage" (Please see the definition of prune feature and critical edge in https://clang.llvm.org/docs/SanitizerCoverage.html). I will use the same example from llvm sanitizer coverage to explain how it works as follows:
Code:

void foo(int *a) {
  if (a)
    *a = 0;
}

It contains three basic blocks, let’s name them A, B, C. If we do node instrumentation, we can have three nodes (each node corresponds to a basic block)

A -> node coverage 
|\
| \
|  B -> node coverage 
| /
|/
C -> node coverage 

But such node coverage is coarse-grained and fails to detect certain edges(A->C). Please read llvm sanitizer coverage document for more details. That's what we call critical edge. To solve this problem, edge coverage would add an explicit node to catch the critical edge shown as node D as follows:

A
|\
| \
D  B     (A,B,C -> node coverage; D -> critical edge coverage )
| /
|/
C

For this code example, K-Scheduler uses llvm sanitizer edge coverage without the pruning to instrument four locations (A, B, C, and D nodes). Therefore, we can literally delete nodes on an "edge coverage graph". Let me know if you have any questions.

Best,
Dongdong

from k-scheduler.

Can it be understood in this way？ this edge coverage is not the edge identifier calculated by the two basic block identifiers in llvmmode in afl. through the introduction of virtual nodes, as long as normal nodes and virtual nodes are covered, it can be considered as covering all edges. Indirect calculation of edge coverage by node coverage

from k-scheduler.

Yes, exactly.

from k-scheduler.

Thank you very much for your prompt reply

from k-scheduler.