'Optimizing the Interval Decision Diagram Implementation in the CF Firewall'
Author
Christensen, Jesper Sloth
Term
4. term
Education
Publication year
2005
Abstract
Formålet er at gøre det hurtigere at bygge et beslutningsdiagram ud fra firewall-regler. Et beslutningsdiagram er en struktureret, træ-lignende repræsentation, der hjælper med hurtigt at afgøre, hvilke trafikpakker der skal tillades eller blokkeres. Vi forbedrer implementeringen af CF-firewallen, så de funktioner, der udfører logiske operationer på beslutningsdiagrammer, i værste fald går fra eksponentiel til polynomiel køretid. Vi optimerer også andre dele, og for store regelsæt reducerer vi tiden til at bygge beslutningsdiagrammet fra timer til sekunder. Derudover undersøger vi rækkefølgen af variabler i beslutningsdiagrammet og hvilken effekt det har at ændre den. Vi præsenterer en algoritme til at finde en bedre rækkefølge, men ser, at den ikke mindsker diagrammets størrelse. Selv når størrelsen er uændret, kan variabelrækkefølgen stadig påvirke, hvor lang tid det tager at bygge diagrammet.
The goal is to speed up building a decision diagram from firewall rules. A decision diagram is a structured, tree-like representation that helps quickly determine which network packets should be allowed or blocked. We improve the implementation of the CF firewall so that the functions performing logical operations on decision diagrams have worst-case runtime that drops from exponential to polynomial. We also optimize other parts, and for large rule sets we cut the time to build the decision diagram from hours to seconds. We further study the order of variables in the decision diagram and how changing it affects performance. We present an algorithm to find a better order, but find that the order it produces does not reduce the diagram’s size. Even when size stays the same, variable order can still influence how long it takes to build the diagram.
[This abstract was generated with the help of AI]
Documents