# Fast Format-Aware Fuzzing for Structured Input Applications
## 4 Implementation and Evaluation
### RQ1: The Effectiveness Evaluation  
In this experiment, we evaluated the effectiveness of FFAFuzz input dependency recognition, by comparing the number of recognized dependencies with Redqueen and WEIZZ.  
Both the _format-well_ and _de Bruijn-based_ the initial inputs were adopted for the scenarios with and without prior knowledge of the input format, respectively. To evaluate the quantity of dependencies, Redqueen, WEIZZ, and FFAFuzz perform dependency recognition on the 11 targets as the benchmarks. For statistical purposes, we regarded a dependency as a three-tuple \(<o\mapsto site.opr>\). If the \(o\)-offset byte in the initial input could affect the operand \(opr\) of the comparison instruction \(site\) in the target, we deemed that one dependency exists between the \(o\)-offset byte and the \(opr\) of \(site\). In other words, when the \(o\)-offset byte is flipped, the operand \(opr\) of the comparison instruction \(site\) will have its value changed.  
Figure 9 below presents the result of dependency recognition performed by FFAFuzz, WEIZZ, and Redqueen.  
From the result of RQ1, we can observe that:  
1. The recognized dependency amount of both FFAFuzz and WEIZZ is greater than that of Redqueen, especially the average boost of 29k-times when adopting _format-well_ as the initial input.
2. All three perform equally well on the targets readelf, faad, optipng, gif2 rgb, etc., in the case of an unknown input format.
3. Given _de Bruijn-based_ input and not, the mean deviation between FFAFuzz and WEIZZ was 26.67% and 23.19%, respectively. This indicates that the captured dependency quantities of FFAFuzz and WEIZZ are roughly equal in orders of 10.  
FFAFuzz and WEIZZ recognized more dependencies than Redqueen. That is because not only FFAFuzz and WEIZZ could mine dependencies from _header_ fields such as the file signature and version, but also indirect dependencies from the complex data processing comparisons.  
Given the de Bruijn-based test case as the input, FFAFuzz, Redqueen, and WEIZZ performed equally well on most target programs. Since the _de Bruijn-based_ as the initial input is a kind of pseudo-random sequence and inherently unformatted for the targets, it fails checks such as magic-byte checks. The target applications treat it as an illegal one and terminate their execution to avoid misreading the data further. Thus, no deeper data processing comparison code is covered, and the quantity of dependencies obtained by those three fuzzers is approximately equal.  
The performance of FFAFuzz is similar to WEIZZ, whether the de Bruijn-based test case is given or not, as the FFAFuzz method of recognizing dependencies is basically the same as the WEIZZ byte-by-byte analysis scheme _GETDEPS_. _Non-deps exclusion_ only identifies and excludes _non-deps_ fragments and does not raise the quantity of dependencies.  
Responding to RQ1, for most targets as the benchmarks and regardless of the prior knowledge of the input format, FFAFuzz largely outperformed Redqueen and was on a par with WEIZZ, in terms of the effectiveness.  
Figure 9: The dependency amounts obtained by dependency recognition for RQ1.