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

ABSTRACT

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.

REFERENCES

• 1: Al-Shaer, E., Hamed, H. 2004. Discovery of policy anomalies in distributed firewalls. In Proceedings of the 23^rd Annual Joint Conference of the IEEE Computer and Communications Societies. INFOCOM'04. vol. 4. pp. 2605--2616. IEEE.
• 2: Mohamed G. Gouda , Xiang-Yang Alex Liu, Firewall Design: Consistency, Completeness, and Compactness, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.320-327, March 24-26, 2004
• 3: Pankaj Gupta , Nicholas W. Mckeown, Algorithms for routing lookups and packet classification, Stanford University, Stanford, CA, 2000
• 4: Kim, H., Kang, I. 2003. On the effectiveness of martian address filtering and its extensions. In Proceedings of the 2003 Global Telecommunications Conference. GLOBECOM'03. pp. 1348--1353. IEEE.
• 5: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.203-214, Oct. 1998
• 6: Li, J., Liu, H., Sollins, K. 2003. Scalable packet classification using bit vector aggregating and folding. MIT LCS Technical Memo. MIT-LCS-TM-637. MIT Laboratory for Computer Science. Cambridge, MA.
• 7: Soldo, F., Defrawy, K. Markopoulou, A. 2008. Filtering sources of unwanted traffic. In Proceedings of the 2008 Information Theory and Applications Workshop. pp. 199--208. IEEE.
• 8: Jian Zhang , Phillip Porras , Johannes Ullrich, Highly predictive blacklisting, Proceedings of the 17th conference on Security symposium, p.107-122, July 28-August 01, 2008, San Jose, CA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Security

Keywords:
bit vectors, blacklisting, firewalls, packet classification, path matrix