tailieunhanh - Tối ưu không gian trạng thái của thuật toán AhoCorasick sử dụng kỹ thuật nén dòng và bảng chỉ số

Bài viết trình bày cách biểu diễn không gian trạng thái của thuật toán AC và các cải tiến bằng kỹ thuật nén dòng và bảng chỉ số. Các kết quả thực nghiệm, phân tích và đánh giá sẽ được trình bày trong mục III. Cuối cùng là kết luận và hướng phát triển. | Tối ưu không gian trạng thái của thuật toán AhoCorasick sử dụng kỹ thuật nén dòng và bảng chỉ số Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 9 (29), tháng 6/2013 Tối ưu không gian trạng thái của thuật toán Aho- Corasick sử dụng kỹ thuật nén dòng và bảng chỉ số Optimizing State Space of Aho-Corasick Algorithm using Compressed State Storage and Index Table Techniques Lê Đắc Nhường, Lê Đăng Nguyên và Lê Trọng Vĩnh Abstract: The pattern matching algorithms are trên hậu tố và so khớp thừa số) dựa vào thời gian và important roles in most applications of information bộ nhớ. technology. For example, Network Intrusion Detection Ngày nay, việc so khớp mẫu trở nên khó khăn hơn System looks for evidence of malicious behavior based nhiều do sự gia tăng về số lượng các mẫu. Chẳng hạn, on matching packet contents with known patterns. trong an ninh mạng số đợt tấn công, hình thức tấn Therefore, the study of the pattern-matching algorithm công, các loại virus, spam, trojan không chỉ tăng is a hot topic many researchers are interested. In this nhanh về số lượng mà cả sự đa dạng của nó. Vì vậy, paper, we propose a new method to optimize the state việc thu thập đầy đủ các mẫu làm cho kích thước tập storage of the pattern matching algorithms, Aho- mẫu ngày càng tăng nhanh. Do vậy việc tối ưu bộ nhớ Corasick by using compressed row and index table thực thi của các thuật toán so khớp mẫu đang rất được techniques. The experimental results that compare the quan tâm bởi lẽ nó quyết định tốc độ và hiệu năng của efficacy performed between the original Aho-Corasick hệ thống. algorithm and the improved algorithm installed in Đã có rất nhiều phương pháp được đề xuất trong Snort showed that our method achieved better results. việc quản lý bộ nhớ và truy cập bộ nhớ thông qua các Keywords: Pattern Matching; Aho-Corasick; bảng cú pháp như của Johnson [4], nén nội dung bảng Compressed Row Storage; Index table. dùng tập đa