# Squill: Testing DBMS with Correctness Feedback and Accurate Instantiation
## 3 Design of Squill
### Correctness-Guided Mutation
#### 3.1.2 Mutation with Interesting Material Library  
Valid seeds usually trigger deep program logic. In contrast, seeds with syntactic or semantic errors (in other words, invalid) often terminate at the early phase of DBMS, such as the syntactic and semantic check. It means that the optimizer and executor of DBMS do not actually process these invalid SQL statements. So some SQL structures in the syntax-error or semantics-error seed are unactivated, as subsequent phases of DBMS do not actually process them. That is, although some SQL structures can trigger new DBMS logic, they are not actually executed because they are in an invalid seed. We call these SQL structures interesting structures here. For example, the query in Line 4 of Listingis an invalid input, which uses a not existing window \(\mathtt{v}\). The valid one is shown in Line 2. The function \(\mathtt{row\_number()}\) in Line 4 may be an interesting structure. It is not actually executed since it is in a semantics-error SQL statement that does not pass the semantic check of DBMS.  
Therefore, we designed a method to filter out these interesting structures and activate them, as shown in Algorithm 2. We maintain an interesting material library, which contains subtrees of all current favored and invalid seeds (Line 15-17). When the fuzzer needs a material (subtree) from the mutation material library to participate in mutation, it has a certain probability of obtaining the material from the interesting material library (Line 21-30). The variable probability in Line 25 is an input parameter, which is set to 5 by default.  
```
1://Run when top_rated changed
2:functioncull_QUEUE(void)
3:temp_bitmap[MAP_SIZE] = 0;
4:set_empty(interesting_library);
5:fori from 0 to MAP_SIZE do
6:iftop_rated[i] is not 0 and temp_bitmap[i] is 0 then
7://Favored means mutating first
8:top_rated[i] is favored;
9://Record the bitmap of top_rated[i] to temp_bitmap
10:forj from 0 to MAP_SIZE do
11:iftop_rated[i].bitmap[j] is not 0 then
12:temp_bitmap[j] = 1;
13:endif
14:endfor
15:iftop_rated[i] is invalid then
16:add_into_interesting_library(top_rated[i]);
17:endif
18:endif
19:endfor
20:endfunction
21://Run when insertion or replacement
22:functionGET_IR_FROM_LIBRARY(type)
23://Get a random number from 1 to 100
24:rand_int = get_rand_int(100);
25:ifrand_int<probability then
26:get_from_interesting_library(type);
27:else
28:get_from_all_library(type);
29:endif
30:endfunction
```  
**Algorithm 2** Mutation with interesting material library.  
We utilize the favored mechanism in AFL to select seeds that may contain interesting structures. After correctness-focused seed selection, the favored and invalid seed must trigger the program state (edge) that valid seeds have not triggered. For example, some SQL structures in these seeds might trigger a unique logic of the DBMS parser. When these SQL structures are actually executed, it is likely to bring path exploration or bug finding in the optimizer or executor of DBMS. Since it is difficult to generate valid seeds from the mutation of seeds with syntactic and semantic errors, we give the mutation material (subtrees) of these seeds more opportunities to participate in mutation, making interesting structures executed in valid seeds after insertion or replacement.