# Fast Format-Aware Fuzzing for Structured Input Applications
## 4 Implementation and Evaluation
### RQ2: The Efficiency Evaluation  
In this experiment, we evaluated the time efficiency of FFAFuzz input dependency recognition, comparing the time cost with Redqueen and WEIZZ.  
For evaluating the time efficiency, the multi-sized gradient initial input set (including 4 kb, 16 kb, 64 kb, 256 kb, 512 kb _de Bruijn-based_, and _format-well_ test cases) were used as the input, and Redqueen, WEIZZ, and FFAFuzz all performed dependency recognition on the 11 targets as the benchmarks. Finally, we evaluated the time cost of the respectively compared fuzzing methods.  
For the target catptpt, we used the initial input set including 8 kb, 64 kb, 128 kb, 256 kb, 512 kb _de Bruijn-based_, and _format-well_ as the initial inputs. As the MSDN document [29] demonstrates, an empty.ppt file still consists of several.xml files to store data such as theme, layout, etc., leading the minimum length of the.ppt file to exceed our expectation of 16 kb. The 8 kb _format-well_.ppt file comes from Windows updates [30].  
Figure 10 shows the time overhead of dependency recognition by various compared fuzzers, over the targets objdump, optipng, and opj_dump. All the results are shown in Figures 11 and 12.  
From the result of RQ2, we can observe that:  
1. Regardless of the prior knowledge of the target input format, in most cases, FFAFuzz outperformed Redqueen and WEIZZ in terms of the time overhead of dependency recognition. Figure 11 indicates that, when the inputs were _de Bruijn-based_ test cases, FFAFuzz reduced the time cost by an average of 89.10% compared to WEIZZ and 76.49% compared to Redqueen. When the inputs were _format-well_ as the initial inputs, it reduced the time overhead by an average of 55.25% compared to WEIZZ and 63.33% compared to Redqueen.
2. The time cost of FFAFuzz dependency recognition was roughly equal to that of WEIZZ when facing targets such as dipeg, faad, etc., and using _format-well_ as the initial inputs.  
The reason why FFAFuzz reduces the time overhead is that _Non-deps exclusion_ identifies and excludes _non-deps_ fragments in a lightweight manner. The theoretical analysis in Appendix C indicates that FFAFuzz is \(O(\log n)\) in the majority of the cases. The result of RQ2 corroborates this.  
Figure 10: The time overhead of dependency recognition by various compared fuzzers.  
Using _format-well_ as the initial inputs, the performance was comparable to WEIZZ. The reasons for this are that few _non-deps_ fields exist in the _format-well_ inputs, and _Selective Flip_ is hard to optimize for such scenarios via _Non-deps exclusion_. For example, the data fields in.jpg and.jpeg hold the data compressed by the algorithms such as the Discrete Cosine Transform (DCT) and Huffman coding [31]. Each time djpeg parses one.jpg file, the contests of the data fields will be decoded and compared, resulting in few _non-deps_ fields. _Non-deps exclusion_ is unable to scale down the range of unvalidated fragments, leaving FFAFuzz on par with WEIZZ in terms of time cost. It can be confirmed as the opposite when using the _de Bruijn-based_ test case as the input. The theoretical analysis in Appendix C indicates FFAFuzz is \(O(n)\) in this case as well.  
Responding to RQ2, in terms of time efficiency, FFAFuzz recognizes dependencies faster than WEIZZ and Redqueen in most cases, and even if no _non-deps_ fragments exist, FFAFuzz performs on par with WEIZZ.