A multiple string matching algorithm for large-scale URL filtering

作者：Liu Yan Bing^*; Shao Yan; Wang Yong; Liu Qing Yun; Guo Li

来源：Chinese Journal of Computers, 2014, 37(5): 1159-1169.

DOI：10.3724/SP.J.1016.2014.01159

• Pattern set
• Reduction strategy
• Searching speed
• Security application
• String matching
• String matching algorithm
• Url filtering
• Window selection

The filtering of large-scale hazardous URLs plays a fundamental role in many network security applications. The classical multiple string matching algorithms perform poorly on large-scale URLs, due to the heavy consumption of CPU power and memory space. Here we propose a multiple string matching algorithm-SOGOPT for large-scale URL filtering. By exploiting the characteristics of URLs, the proposed algorithm devises two strategies, i. e. the optimal window selection strategy and the pattern set partitioning and reduction strategy, to speed up the classical SOG algorithm. The proposed algorithm improves the searching speed of SOG greatly, especially on large-scale URLs. It is very suitable for large-scale (up to 1 million URLs) and online URL filtering.

• 出版日期2014
• 单位北京大学