# Fast Format-Aware Fuzzing for Structured Input Applications
## Appendix C
### The Time Complexity of Selective Flip
For any positive integer \(n\), \(BVT(n)\) is a binary tree, and each node in the tree has the following properties:  
* The value of the root node is \(n\). * The value of the leaf node is \(1\). * If a node with the value \(p\) is not a leaf node, then its left child node has the value \(\lfloor\frac{p}{2}\rfloor\), and the right one has the value \(\lceil\frac{p}{2}\rceil\)  
BVT(13) is shown in Figure 11. All the green nodes are leaves and the blue ones can be divided into their own left and right childs. The basic operation count of _Non-deps exclusion_ is equal to the number of nodes whose values in \(BVT(n)\) are greater than \(minSpan\) by this. \(D(n,m)\) is a special depth of \(BVT(n)\), all nodes under \(D\) whose values are no greater than \(m\). For any real number \(x\), \(\{x\}=x-\lfloor x\rfloor\), \(0\leq\{x\}<1\). For any real number \(x\), \(\langle x\rangle=\lceil x\rceil-x\), \(0\leq\langle x\rangle<1\). For any positive integer \(a\) and any real number \(x\), \(\lfloor\lfloor x\rfloor/a\rfloor=\lfloor x/a\rfloor\). \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\] \[=(x-\{x\})/a-\{(x-\{x\})/a\}\] \[=x/a-\{x/a\}-\{x/a-\{x/a\}\}\] \[=\lfloor x/a\rfloor-\{\lfloor x/a\rfloor\}\] \[=\lfloor x/a\rfloor\qed\]  
For any positive integer \(a\) and any real number \(x\), \(\lceil\lceil x\rceil/a\rceil=\lceil x/a\rceil\). **Proof. **  
\[\left\lceil\left\lceil x\right\rceil/a\right\rceil =\left\lceil x\right\rceil/a+\left\langle\left\lceil x\right\rceil/a\right\rangle\] \[=\left(x+\left\langle x\right\rangle\right)/a+\left\langle\left(x+ \left\langle x\right\rangle\right)/a\right\rangle\] \[=x/a+\left\langle x/a\right\rangle+\left\langle x/a+\left\langle x /a\right\rangle\right\rangle\] \[=\left\lceil x/a\right\rceil+\left\langle\left\lceil x/a\right\rceil\right\rangle\] \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]0  
**Theorem A3**. : _For any positive integer \(a\) and any real number \(x\), \(\left\lfloor\left\lceil x\right\rceil/a\right\rfloor=\left\lceil x/a\right\rceil\)._  
**Proof. **  
\[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]1 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]2 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]3 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]4 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]5  
**Theorem A4**. : _For any positive integer \(a\) and any real number \(x\), \(\left\lceil\left\lfloor x\right\rfloor/a\right\rceil=\left\lfloor x/a\right\rfloor\)._  
**Proof. **  
\[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]6 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]7 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]8 \[\lfloor\lfloor x\rfloor/a\rfloor =\lfloor x\rfloor/a-\{\lfloor x\rfloor/a\}\]9 \[=(x-\{x\})/a-\{(x-\{x\})/a\}\]0  
Next, we discuss the value of the nodes of \(BVT(n)\) with the same depth. **Theorem A5**. : _For all integers \(d\), \(n\) such that \(0\leq d\leq\left\lceil\log_{2}^{n}\right\rceil\) and \(n>0\), the nodes in \(BVT(n)\) with depth \(d\) have the value \(\left\lceil\frac{n}{2^{d}}\right\rceil\) or \(\left\lfloor\frac{n}{2^{d}}\right\rfloor\)._  
**Proof. ** When the depth is \(0\), the value of the node with depth \(1\) is \(\left\lceil\frac{n}{2}\right\rceil\) or \(\left\lfloor\frac{n}{2}\right\rfloor\). Assume that a positive integer \(d\), the nodes in \(BVT(n)\) with depth \(d\) has the value \(\left\lceil\frac{n}{2^{d}}\right\rceil\) or \(\left\lfloor\frac{n}{2^{d}}\right\rfloor\). In the depth \(d+1\), then four possible values exist, \(\left\lfloor\left\lceil\frac{n}{2^{d}}\right\rceil/2\right\rfloor\), \(\left\lceil\left\lceil\frac{n}{2^{d}}\right\rceil/2\right\rceil\), \(\left\lfloor\left\lfloor\frac{n}{2^{d}}\right\rfloor/2\right\rfloor\), and \(\left\lceil\left\lfloor\frac{n}{2^{d}}\right\rfloor/2\right\rceil\).