Bit vector algorithms enabling high-speed and memory-efficient firewall blacklisting

摘要

In a world of increasing Internet connectivity coupled with increasing computer security risks, security conscious network applications implementing blacklisting technology are becoming very prevalent because it provides the ability to prevent information exchange from known malicious sources. Current technology implementing blacklisting does so at the application level. However, there are numerous benefits for implementing blacklisting filters in the firewall. These benefits include reduced application workload and reduced bandwidth consumption. But, because the de facto algorithm in firewalls is based on a linear search first match principle, large blacklists are not feasible to implement in firewalls due to the O(N) timing complexity of linear search methods. This paper addresses this issue by describing techniques that solve the O(N) time complexity issue without changing the internal input-output behavior of the firewall.