FAQs

Q: Can you tell more about rationale of the replaying strategies:

Suppose after the fuzzing procedure, the seed queue has three test seeds (correspondingly their N_{c} is inside the braces): S1 (3), S2 (1), S3 (2). And S2 is a seed that do not enter the multithreading code segments at all -- it is rejected by the validation check early and exits the program immediately. These seeds will be replayed with the programs that are hardened with ThreadSanitizer.

• Vanilla round-robin replaying strategy (P1). The replaying sequence: S1 -> S2 -> S3 -> S1 -> S2 -> S3 -> S1 -> S2 -> S3 -> S1 -> S2 ...

• Weighted round-robin replaying strategy (P2). The replaying sequence: S1 -> S1 -> S1 -> S2 -> S3 -> S3 -> S1 -> S1 -> S1-> S2 -> S3 ...

Suppose within a time budget, totally 8 executions are replayed. For P1, S1 is executed 3 times, S2 3 times, and S3 twice; for Strategy-2, S1 is executed 5 times, S2 once, S3 twice. Since S2 does not execute multithreading code at all, it is not beneficial to run S2 multiple times. Therefore, P1 is inefficient in replaying S2 3 times. On the other hand, some seeds may be more prune to have thread-interleavings during actual execution (since they may execute deeper in the multithreading environment). During calibration execution in fuzzing procedure, as N_{c} records the number of different traces, it may heuristically exhibits the tendency of exhibiting different threading-interleavings during practical executions. Therefore, P2's more executions on S1 is supposed to be more effective to revealing Concurrency Bugs (if any).

N_{c} approximates the tendency to exhibit different interleavings. In fact, It is worth noting that some seeds may exhibit less thread-interleavings than others, therefore it will be less beneficial to replay against them; we heuristically estimate this based on the value N_{c} recorded during fuzzing procedure. Table-3 shows the weighted strategy can indeed expose C-Bug earlier and stabler. The utilization of N_{c} also demonstrates novelty in our approach.

Q: More explanations on why MUZZ instruments more on the multithreading segments?

A: The simple answer is that not all seeds are equal and not all instrumentations are equal, and instrumentation more on multithreading segments are likely to provide more seeds with high qualities.

1. Fuzzing is effectively to detect vulnerabilities resulting from some incomplete validation checks. This means that the seeds generated by fuzzing are prone to be "corrupted input files" and the detected vulnerabilities are usually "shallow".

2. If a seed is "corrupted" (categorized as S-bad), it is more likely that the mutation on it is more or less still "corrupted" (it is much difficult to go from bad to good). On the other hand, if a seed is mostly "valid" (categorized as S-good), we have a much higher chance to keep the validity of the mutated seed (it is easier to generate good seeds from intact seeds). One example is that if the target program accepts some input files with certain file header requirements, it is extremely difficult to generate a valid seed from those S-bad seeds whose file headers do not satisfy the requirement. However, if the seed belongs to S-good in that the file header matches, the seed will at least pass this check it can execute more "deeper" parts of the target program. Mutations on this seed may not change the file header at all, so the variants of this seed are more likely to pass the file header check requirements as well.

3. If the percentage of S-bad seeds in the seed queue is high, the generated seeds are more likely to still belong to S-bad. If we provide "sufficient" instrumentation on them, we will more likely to generate quite a few of S-bad seeds. In the setting of multithreaded programs, this means that more seeds cannot even execute the multithreading segments at all. In this sense, we should actually provide less instrumentation on the "prologue" of the program, where in the multithreaded programs this typically belongs to the "single-threading code segments".

4. Keeping more S-good seeds in fact probably does not reduce the capability of detecting vulnerabilities that have nothing to do with multithreading (Vs). This is because S-bad seeds are usually of lower quality which may not be easy to be accidentally to be mutated to fail another different validation check. Meanwhile, S-good seeds can be mutated to various kinds of "S-bad" seeds. Moreover, since most of the projects we tested have been fuzzed by other fuzzers such as AFL, libFuzzer, etc, it is less likely these projects contain "shallow vulnerabilities". Therefore, MUZZ applies less instrumentations on these program segments.

5. More instrumentations on thread-interleaving indeed help improve quality of the seeds. Seeds with thread-interleaving at least mean that they have passed certain fundamental validation check therefore they tend to be of "high quality" (S-good). Further, since the discovery of "new transitions/coverage" is discovered across "different seeds", this inheritance increase the diversity of the seeds themselves. Therefore there will not be many pairs of seeds that with enough executions, their interleavings may be the same. Therefore, keeping these seeds are "essentially" different.

6. With more different S-good seeds, the more seeds that belong to S-good may be mutated. Despite that there are still many of these seeds belonging to S-bad, however they will may not be "kept" due to the fact the transition observed by the fuzzer is not new.

Q: Why not use ConAFL's benchmarks during evaluation?