An advanced firewall rules matching algorithm

• Main Author: Elvira, Febiani
• Other Authors: Guo Huaqun
• Format: Final Year Project
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: http://hdl.handle.net/10356/75374
• Institution: Nanyang Technological University

The demand for network security has been on the rise in all application of life needs. Network security is very crucial for everybody including corporations to protect the internal network members while increasing demand in industry process must be. The efficiency of firewall rule matching is thus a great concern to filter occurring traffics in the shortest possible time. There have been many studies to define firewall rule matching algorithm or searching algorithm optimization, which time complexity still depends on the size of firewall rule database. This project adopted hash table technique for indexing or locating database in a system, that represents the input from a set of characters into a hash value. Using the hash function methodology, this project aims to define firewall rule matching algorithm that perform in shortest worst-case time complexity in firewall rule matching scheme, i.e. in O(1) searching time. Big O notation O(1) is a process time complexity that indicate the object of searching process can be found in one execution time of the algorithm to access every dataset input in the database with any size. With this time complexity, the algorithm is operated in a shortest constant time, which it takes to access one dataset from the entire database. Similar with many other studies in firewall rule matching algorithm, the study in this project shows that the memory consumption depends on the size of firewall rules. The experiment in this project started with around two hundred and fifty rules, until more than six hundred forty-five thousand rules. The results proved at least four times faster than standard binary search obtained. With more number of rules added in the database, this result shows that the algorithm based on hash table search is fifty-three times faster than the binary search for addresses in IPv6 format. Results show that the proposed hash table search algorithm outperformed linear search and standard binary search when these algorithms were tested with exponentially number of rules added. Furthermore, the analysis of the results shows that the execution time of the proposed hash table search algorithm for any number of rules are almost constant.