Dynamic rule-ordering optimization for high-speed firewall filtering

ABSTRACT

Packet filtering plays a critical role in many of the current high speed network technologies such as firewalls and IPSec devices. The optimization of firewall policies is critically important to provide high performance packet filtering particularly for high speed network security. Current packet filtering techniques exploit the characteristics of the filtering policies, but they do not consider the traffic behavior in optimizing their search data structures. This results in impractically high space complexity, which undermines the performance gain offered by these techniques. Also, these techniques offer upper bounds for the worst case search times; nevertheless, average case scenarios are not necessarily optimized. Moreover, the types of packet filtering fields used in most of these techniques are limited to IP header fields and cannot be generalized to cover transport and application layer filtering.In this paper, we present a novel technique that utilizes Internet traffic characteristics to optimize firewall filtering policies. The proposed technique timely adapts to the traffic conditions using actively calculated statistics to dynamically optimize the ordering of packet filtering rules. The rule importance in traffic matching as well as its dependency on other rules are both considered in our optimization algorithm. Through extensive evaluation experiments using simulated and real Internet traffic traces, the proposed mechanism is shown to be efficient and easy to deploy in practical firewall implementations.

REFERENCES

• 1: E. Al-Shaer and H. Hamed. Modeling and management of firewall policies. IEEE Transactions on Network and Service Management, 1(1), April 2004.
• 2: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 3: Elizabeth D. Zwicky , Simon Cooper , D. Brent Chapman, Building Internet firewalls (2nd ed.), O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 4: Edith Cohen , Carsten Lund, Packet classification in large ISPs: design and evaluation of decision tree classifiers, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 5: A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In IEEE INFOCOM'00, March 2000.
• 6: R. Graham, E. Lawler, J. Lenstra, and A. Kan. Optimizing and applixation in deterministic seuquencing and scheduling: A surevey. Annals of Discrete Mathematics, 5, 1979.
• 7: P. Gupta and N. McKeown. Algorithms for packet classification. IEEE Network, 15(2):24--32, 2001.
• 8: P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Interconnects VII, August 1999.
• 9: P. Gupta, B. Prabhakar, and S. Boyd. Near optimal routing lookups with bounded worst case performance. In IEEE INFOCOM'00, 2000.
• 10: H. Hamed and E. Al-Shaer. Adaptive statistical optimization techniques for firewall packet filtering. Technical Report TR-05-012, DePaul University, 2005.
• 11: D. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, third edition.
• 12: K. Lan and J. Heidemann. On the correlation of internet flow characteristics. Technical Report ISI-TR-574, USC/ISI, 2003.
• 13: E. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics, 2, 1978.
• 14: J. Lenstra and A. Kan. Complexity of scheduling under precendence constraints. Operations Research, 26(1), 1978.
• 15: A. J. McAulay and P. Francis. Fast routing table lookup using CAMs. In IEEE INFOCOM'93, March 1993.
• 16: Passive Measurement and Analysis Project, National Laboratory for Applied Network Research. Auckland-VIII Traces. http://pma.nlanr.net/Special/auck8.html, December 2003.
• 17: J. Qian, ACLA: A framework for Access Control List (ACL) Analysis and Optimization, Proceedings of the IFIP TC6/TC11 International Conference on Communications and Multimedia Security Issues of the New Century, p.4, May 21-22, 2001
• 18: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 19: Andreas S. Schulz, Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.301-315, June 03-05, 1996
• 20: V. Srinivasan , S. Suri , G. Varghese, Packet classification using tuple space search, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.135-146, Oct. 1999
• 21: Cisco Systems. Optimizing ACLs. User Guide for ACL Manager 1.4, Cisco Works2000, 2002.
• 22: Cisco Systems. Netflow services solutions guide, October 2004.
• 23: D. Taylor and J. Turner. Scalable packet classification using distributed crossproducting of field labels. In IEEE INFOCOM, 2005.
• 24: SimJava v2.0. Process based discrete event simulation package for java. http://www.dcs.ed.ac.uk/home/hase/simjava/, 2002.
• 25: Jörg Wallerich , Holger Dreger , Anja Feldmann , Balachander Krishnamurthy , Walter Willinger, A methodology for studying persistency aspects of internet flows, ACM SIGCOMM Computer Communication Review, v.35 n.2, April 2005 [doi>10.1145/1064413.1064417]
• 26: Thomas Y. C. Woo. A modular approach to packet classification: Algorithms and results. In IEEE INFOCOM'00, pages 1213--1222, March 2000.
• 27: A Quantitative Study of Firewall Configuration Errors, Computer, v.37 n.6, p.62-67, June 2004 [doi>10.1109/MC.2004.2]
• 28: L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.19-29, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 29: G. Zipf. Human Behaviour and the Principle of Least-Effort. Addison-Wesley, 1949.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Management, Security