ENHANCING APPARATUS AND METHOD OF THE SEARCH ABILITY FOR REGULAR EXPRESSIONS BASED ON COST OPTIMIZED

摘要

The present invention relates to an apparatus and a method for enhancing search performance of a regular expression through a cost-based optimization method, in which an efficient search node is configured based on the partitioning, reassembly, complexity calculation, and learning information of the regular expression so as to perform high-performance search for the regular expression. The apparatus for enhancing search performance of a regular expression through a cost-based optimization method comprises: a policy database, in which a malicious payload detection rule containing a regular expression character string is stored; a regular expression extraction unit generating a set of regular expression character strings included in each policy from the policy database; a regular expression fragment unit dividing and integrating each regular expression character string extracted by the regular expression extraction unit according to a fragmentation rule to generate a regular expression fragment table; a regular expression generalization unit performing an optimization process on each regular expression fragment of the regular expression fragment table generated by the regular expression fragment unit to form an optimized regular expression fragment table; a cost calculation engine unit applying a sample traffic to the regular expression fragment table optimized by the regular expression generalization unit to appropriate costs for each regular expression fragment; a decision tree generation unit generating a decision tree based on the cost information calculated by a cost calculation engine unit for each fragment of the regular expression fragment table optimized by the regular expression generalization unit; and a pattern matching engine unit constructing a search engine for performing policy pattern matching by applying the decision tree.