# Fast Format-Aware Fuzzing for Structured Input Applications
## Appendix C
### The Time Complexity of Selective Flip  
The _Selective Flip_ strategy divides the dependency recognition of the entire initial input into several small-scale equivalent tasks. For fields larger than \(minSpan\), _Non-deps exclusion_ is used to lightly analyze the existence of dependencies in the field, and if not, it will be excluded directly; otherwise, the field will continue to be split in half and wait for the next round of analysis. The fields less than or equal to \(minSpan\) are then processed in _Deps detection_. Based on Algorithms 2 and 3, we can conclude that \(run\_target(T)\) and the following _for_ loop statements are heavy in time overhead. They will thus be considered as basic operations. We denote by \(T(n)\) the count of the basic operations when using \(n\)-byte-long input and performing _Selective Flip_ once. The time overhead of _Selective Flip_ in the ideal, majority of, and worst-case scenarios will be discussed in the following. The Ideal Scenario  
Ideally, no dependencies exist in the initial input. _Selective Flip_ treats the entire input as a suspensive field and performs _Non-deps exclusion_. The basic operation is executed only once. The entire input will be flipped and used as the input. After the execution, no _cmp_ operands were affected because the whole input is the _non-deps_ one. We conclude:  
\[T(n)=1\] (A2)  
\(O(1)\) is the time complexity of _Selective Flip_ in this case. The Majority of Scenarios  
As Section 2.1 described, _header_ fields are tiny, but metadata-intensive and adjacent. They can be commonly found in various types of structured inputs. In this case, _Selective Flip_ will exclude the _non-deps_ fragment of length \(n/2\), \(n/4\), \(n/8\),..., and finally perform _Deps detection_ on the header fields. Each time a _non-deps_ fragment is excluded by _Selective Flip_, _Non-deps exclusion_ is performed two times, the first time on the large fragment including _header_ fields and the second time on the _non-deps_ half of the large fragment. Finally, the _non-deps_ fragment is excluded. _Selective Flip_ performs _Deps detection_ on the _header_ fields. _Deps detection_ will execute the basic operation as many times as they are long. We denote \(n_{header}\) as the length of these fields, \(t\) as the count of performing _Non-deps Exclusion_. From the above, we have \(n-\sum_{t=1}^{t}n\times 2^{-i}\leq n_{header}\), and this leads to \(t\geq 10\frac{n}{2}^{\frac{n}{n_{header}}}\). Taking \(t\) as an integer, thus \(t=\lceil\log_{2}^{\frac{n}{n_{header}}}\rceil\). We conclude:  
\[T(n)=n_{header}+t=n_{header}+\lceil\log_{2}^{\frac{n}{n_{header}}}\rceil\] (A3)  
From Equation (A3), \(O(\log n)\) is the time complexity of _Selective Flip_ in the majority of scenarios. The Worst Scenario  
In the worst scenario, the _header_ fields are distributed evenly and spaced less than \(minSpan\), making it impossible for _Selective Flip_ to recognize and exclude _non-deps_ fragment by _Non-deps exclusion_. Eventually, the whole initial input is divided into several fragments with lengths no greater than \(minSpan\), and _Deps detection_ is performed one by one. Based on Algorithms 2 and 3, we can infer:  
\[T(n)=\left\{ \begin{array}{cc}&T(\lfloor\frac{n}{2}\rfloor)+T(\lceil\frac{n }{2}\rceil)+1&,n>minSpan\\ &n&,n\leq minSpan\end{array} \right.\] (A4)  
None of fragments longer than \(minSpan\) are excluded by _Non-deps exclusion_. This leads to the count of basic operations performed on this fragment being equal to the sum of those performed on the left and right halves, then plus this basic operation. Thus, \(T(n)=T(\lfloor\frac{n}{2}\rfloor)+T(\lceil\frac{n}{2}\rceil)+1\). Fragments with lengths no longer than \(minSpan\) will be handled by _Deps detection_. The count of basic operations is equal to the fragment length, \(T(n)=n\). To analyze the time complexity, computing the basic operation count of _Non-deps exclusion_ is needed. We used _BVT_, a type of binary tree for the discussion.