## 2 Background
### Coverage Accuracy  
For the coverage-based fuzzing method, the coverage is the main metric to evaluate the performance, though there are different ways to define how to compute coverage. The accuracy of different coverage computation methods is firstly discussed systematically by CollAFL [21], which also proposes a new method to improve this metric based on AFL [2], i.e., a widely-used fuzzer baseline. There are three different coverage computation methods: basic block coverage, edge or branch coverage, and path coverage. We use a simple program execution figure to explain their differences, as shown in Figure 1.  
If we consider each basic block as a different coverage, then for the simple program shown in Figure 1, the full coverage of the program can be represented as set {_A_, \(B\), \(C\), \(D\), \(E\), _F_}. This metric is the least accurate one compared with the other two methods. For example, if we already have program paths (_A_, \(B\), \(E\), _F_) and (_A_, \(B\), \(D\), _F_), the coverage set will be {_A_, \(B\), \(D\), \(E\), _F_}. Then, if we discover a new execution path (_A_, \(B\), \(D\), \(E\), _F_), it will not be considered as a new path because all basic blocks in this path have already been recorded as explored coverage, and as a result, we will lose context.  
Edge coverage describes more information about the execution path from one basic block to another, which considers the edge between two basic blocks as one unique coverage. If we use edge coverage to describe the program, it will be represented as set {_(A_, _B_), (_A_, _C_), (_B_, _D_), (_B_, _E_), (_C_, _E_), (_C_, _D_), (_D_, _F_), (_D_, _E_), (_E_, _F_)}. Though edge coverage is more accurate than basic block coverage, it is still not perfect. For example, suppose that we have already found program paths (_A_, \(B\), \(D\), \(E\), _F_) and (_A_, \(C\), \(D\), _F_), then our coverage set \(P\) will be {_(A_, _B_), (_B_, _D_), (_D_, _E_), (_E_, _F_), (_A_, _C_), (_C_, _D_), (_D_, _F_)}. If we then find another path (_A_, \(C\), \(D\), \(E\), _F_), which is a new path that has never been executed, however, it will not be considered under the edge coverage metric, because the edge coverage is set {_(A_, _C_), (_C_, _D_), (_D_, _E_), (_E_, _F_)}, which is the subset of the previously calculated set \(P\). As a result, we will lose program coverage context.  
This simple example shows clearly that path coverage is the most accurate way of computing coverage, edge coverage is less accurate, and basic block coverage is the least accurate. However, path coverage is hard to apply to real-world scenarios because of the huge overhead for computation. We need heavy instrumentation analysis on the program to get precise path coverage information. Therefore, edge coverage is a good trade-off in terms of both accuracy and scalability.  
When we try to selectively execute branches in concolic execution, the problem of coverage accuracy still influences the results. Specifically, it is important to decide whether a branch is executed or not. If we only consider each branch as unique, then we will lose the context of edge coverage, similar to the problem we have shown in the previous paragraphs. To solve this problem, we propose a critical branch selection algorithm with a new way to calculate the branch coverage and decide whether a branch should be executed or not.