STRING SEARCH AND MATCHING FOR GATE FUNCTIONALITY

Fast string search and matching is critical for many security tasks in particular if these have gate functionality for instance as found in access control applications, firewalls, routers, and load balancers. The fast matching of strings is essential to impose and enforce access control policies without creating bottlenecks. Firewalls protect networks by monitoring the traffic crossing the network perimeter. The number of packet matching rules firewalls can effectively handle is limited by the matching time and space complexity of the algorithms employed. A new approach implements matching independent of the number of rules and linear in the length of the rule to be matched. A data structure used in this approach is referred to as a Bipartite Concatenated Representation (BCR). The space complexity of the BCR within this application scenario scales as O(N log2N) where N is the number of rules.