# APT Attack Detection Scheme Based on CK Sketch and DNS Traffic
## 3 Research Design
### Count and Compress DNS Traffic with an Improved Sketch Structure
#### 3.4.2 Counting and Compressing  
The process of compressing the statistical DNS traffic (Key, Value) is shown in Figure 7 and consists of the following five steps, where the key is the DNS domain name and the value is the eight features used to describe the APT attack in Section 3.3.  
Figure 7: Compress and count flow chart.  
Determine whether the current DNS traffic is already located in the hash bucket. The key in the network traffic (Key, Value) is calculated by the main hash function through Equation (4) to obtain the \(Loc_{m}\). \[Loc_{m}=H_{m}(key),\] (4) According to whether the \(Loc_{m}\) position in the Bloom filter already contains elements, corresponding to the following three cases. * There are no data in this position, then the element is added to the \(Loc_{m}\) position in the Bloom filter, and the element is stored in the multi-layer hash bucket from the first layer. * There are data in this location but the corresponding key is different from the corresponding key of the current DNS traffic, the element will be stored in the hash bucket of the multi-layer starting from the first layer. * There are data in this location and the corresponding key is the same as the corresponding key of the current network traffic, the element will be stored in the corresponding layer of the multi-layer hash bucket directly according to the number of layers in the Bloom filter. 2. Calculate the location of the hash bucket where the DNS traffic is stored. Put the network traffic (Key, Value) into the nth layer according to step 1 and Equation (5) to determine the location where the DNS traffic is stored in the nth layer. \[Loc_{n}=H_{n}(key),\] (5) 3. Determine whether there is a hash conflict. If the \(Loc_{n}\) position in the hash bucket does not contain any data, then there is no hash conflict. If there are already data in it and the data are the same as the data to be inserted, then there is no hash conflict, otherwise, there is a hash conflict. 4. Count and compress network traffic (Key, Value). If there is no hash conflict, the key in the network traffic is recorded, and the value is added to the value in the hash bucket. If a hash conflict occurs, create a different hash function \(H_{n+1}\) and a layer of hash bucket \(S_{n+1}\), where the number of hash buckets in \(S_{n+1}\) is twice the number of \(S_{n}\). The hash function of layer \(n+1\) is used to calculate Formula (6) to obtain the location of layer \(n+1\) traffic, and insert this DNS traffic into the layer \(n+1\) hash bucket according to the above steps. Finally, the number of layers where the traffic resides is recorded in Bloom filter. Figure 8 shows an example of step 4 counting and compressing DNS traffic (Key, Value) with hash conflict. At this time, after main hash calculation, the Bloom filter does not contain the number of layers of the traffic. Therefore, counting and compressing network traffic started from the first layer of the CK sketch. \[Loc_{n+1}=H_{n+1}(key),\] (6) 5. Record the number of hash bucket layers where the DNS traffic (Key, Value) is located. After counting and compressing, the number of layers where the DNS traffic is located will be recorded in the Bloom filter.  
Figure 8: Example of hash collision.