# Design of a Heterogeneous-Based Network Intrusion Detection System and Compiler
## 3 Materials and Methods
### Design of CPU-Based Intrusion Detection and Rule Compilation
#### 3.3.1 Rule Compilation Module
To achieve 100 Gbps line-speed processing capability, we integrate hash functions with bitmaps to realize memory-efficient access through the hash-discretized distribution characteristics of fast-pattern strings. The shift-or exact matching algorithm is incorporated to eliminate hash bitmap false positives and improve detection accuracy. Finally, we establish a strict binding mechanism between rule IDs and hash addresses to avoid mismatching risks. The three-part compilation design is as follows:  
**Hash Bitmap [39; 40] construction. ** Taking Figure 6 as an example, \"Gizmo\" is the fast-pattern string extracted by the compiler. First, according to the length of the extracted fast-pattern string, it is assigned to a specified bucket, and then converted to ASCII values. Since the string length is less than 8 bytes, zeros need to be padded to the higher bits of the string to ensure input consistency of the hash function, while padding \"0\" can make the result differences more distinct. Subsequently, hash computation is performed to generate bitmap indices. We designed two hash functions: one performs multiplication operations, and the other performs hierarchical addition and bit shifting, aiming to obtain completely distinct hash addresses. First, the input 8-byte characters are split. To make the calculated addresses as evenly distributed as possible, the data are multiplied with four predefined 16-bit constants split from the constant \"0x0b4e0e6f37 bc32127\". The specific calculation formula is shown in Listing 1. mul_hash formula. 1. uint64_t b = 0x0b4e0e6f37 bc32127;
2. uint16_t bn[4];
3. uint64_t tmpb = b;
4. for(int i = 0; i < 4; i++){
5. bn[i] = tmpb ;
6. tmpb = (tmpb > 16);
7. } 8. Mulhash_res res;
9. for(int i = 0; i < 4; i++){
10. res.ab_n[i] = a * bn[i];
11. } In the formula, \(a\) is the ASCII value of the character, and \(bn[i]\) represents the four 16-bit constants split from the predefined constant. Through calculation, each character obtains four corresponding multiplicative hash values, denoted as \(ab\_n[i]\). Figure 6: Fast-pattern compilation process. Then, the above multiplicative values are input into the hierarchical addition and shifting part. Adjacent characters and cross-character addition combinations are calculated. After hierarchical merging and extracting high-order bits, the final hash address is obtained through addition and shifting. The relevant calculation formulas are shown in Listing 2. 1. uint64_t_a01_b0 = aib[0]_ab_n[0] + (aib[1]_ab_n[0] \(\propto\) 8);
2....
3. uint64_t_add_a01_b1_a23_b0 = a01_b1 + a23_b0;
4....
5. uint64_t_sum0 = (add_a01_b1_a23_b0 \(\propto\) 16) + a01_b0;
6. uint64_t_sum1 = add_a01_b2_a45_b0 + a23_b1;
7. uint64_t_sum2 = (add_a01_b3_a23_b2
8. uint64_t_half_sum0 = (sum0;
9. uint64_t_half_sum1 = (sum2 \(\times\) 16) + sum1;
10. uint64_t_sum = half_sum0 + (half_sum1 \(\times\) 32);
11. uint32_t_addr = (sum \(\times\) (64 - NBITS));  
In the formula, line 1 represents the combination calculation of adjacent characters, synthesizing a 16-bit value through left-shifting 8 bits and addition. Line 3 represents cross-character addition calculation and cross-layer mixing, aiming to increase bit diffusion and make distribution more uniform. Lines 5-7 represent hierarchical merging, combining the previously calculated values. The modulo operation on sum2 is to extract the lower 16 bits. Lines 8-10 represent the final addition of hash results, where shifting aims to avoid overlap in lower bits affecting the results. Line 11 obtains the hash address. Here, NUM_BITS is 8, so the final hash address length is 8 bits. The higher 5 bits of the hash address are taken as the bitmap address, while the bitmap offset is designed as the lower 3 bits of the hash address, setting the corresponding bit to 1. At this point, hash bitmap construction is completed. Regarding hash collision resolution, our solution is to detect and report errors during compilation, then resolve them by modifying the fast-pattern string length or content to reclassify them into other buckets for computation.