检索结果-内蒙古大学图书馆

Pattern Matching in YARA: Improved aho-corasick algorithm

IEEE ACCESS 2021年 9卷 62857-62866页

作者： Regeciova, Dominika Kolar, Dusan Milkovic, Marek Brno Univ Technol Fac Informat Technol Brno 61266 Czech Republic Avast Software Sro Brno 60200 Czech Republic

YARA is a tool for pattern matching used by malware analysts all over the world. YARA can scan files, as well as process memory. It allows us to define sequences of symbols as text strings, hexadecimal strings and regular expressions. However, the use of regular expressions is limited because of the concern that it can slow down the scanning process. In this paper, we analyze the true nature of regular expressions in YARA and their implementation. We have, in fact, discovered several reasons why regular expressions can slow down scanning based on the nature of the used algorithm, aho-corasick. We have proposed a new version of this algorithm and have implemented it in the original version of this tool. The experiments are presented, proving that the speed of pattern matching with regular expressions can indeed be improved. In selected cases, the proposed version was about 27% faster than the original version. And in instances where strings were optimized for the original version, their speed was found to be comparable.

关键词： Pattern matching Tools Malware Cats Licenses Companies Syntactics aho-corasick algorithm pattern matching regular expressions YARA

来源：评论

学校读者我要写书评

暂无评论

Auto implementation of parallel hardware architecture for aho-corasick algorithm

引用

DESIGN AUTOMATION FOR EMBEDDED SYSTEMS 2022年第1期26卷 29-53页

作者： Najam-ul-Islam, M. Zahra, Fatima Tu Jafri, Atif Raza Shah, Roman ul Hassan, Masood Rashid, Muhammad Bahria Univ Cyber Reconnaissance & Combat Lab Islamabad Pakistan Umm Al Qura Univ Comp Engn Dept Mecca Saudi Arabia

Pattern matching using aho-corasick (AC) algorithm is the most time-consuming task in an Intrusion Detection System, and therefore, the Field Programmable Gate Array (FPGA) based solutions are frequently employed. In this context, the two possibilities are memory based solutions and hardwired solution. The limitation of memory based solutions is the inefficient utilization of slices while the hardwired solutions require a tremendous amount of effort and time as writing Hardware Description Language (HDL) code for thousands of rules is prone to human errors. Consequently, the contributions of this article are twofold. The first contribution is to develop a tool for the automatic generation of Verilog-HDL code from the rule set. The second contribution is to propose an efficient parallel hardware implementation scheme and compare it with a serial hardware implementation scheme in terms of various design parameters such as resource utilization, operational frequency and throughput. The proposed parallel scheme advocates the division of entire rule set into smaller sub-sets for parallel execution. Experimental results reveal that the proposed tool can generate the target code for 10,000 rules in less than a minute without any error. The automatic generation of target code has allowed to perform a comprehensive design space exploration for the parallel implementation of AC algorithm in quick time. Finally, our Xilinx ZC702 evaluation FPGA board based prototype for 10,000 rules can efficiently examine the packet stream coming at a bit rate of 1.56 Gbps at an operational frequency of 195 MHz.

关键词： Automatic code generation Parallel hardware aho-corasick algorithm Network security FPGA implementation

来源：评论

学校读者我要写书评

暂无评论

A MULTI-CHARACTER TRANSITION STRING MATCHING ARCHITECTURE BASED ON aho-corasick algorithm

引用

INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL 2012年第12期8卷 8367-8386页

作者： Chen, Chien-Chi Wang, Sheng-De Natl Taiwan Univ Dept Elect Engn Taipei 10617 Taiwan

A hardware string matching architecture is usually used to accelerate string matching in various applications that need to filter content in high speed such as intrusion detection systems. However, the throughput of the hardware string matching architecture inspecting data character by character is limited by the achievable highest clock rate. In this paper, we present a string matching architecture based on the aho-corasick algorithm. The proposed architecture is able to inspect multiple characters simultaneously and the throughput of string matching can be multiplied. We first describe an intuitive algorithm to construct a multi-character finite state machine (FSM) that accepts multiple characters per transition based on an aho-corasick prefix tree (AC-trie). Then we propose an architecture for multi-character transition string matching consisting of multiple matching units for processing the transition rules that are generated from the derived multi-character FSM. The design of proposed architecture utilizes the properties of the failure links of an AC-trie to reduce the transition rules derived from the failure functions linked to the initial state. As a result, the state growth rate is moderate in the number of the derived multi-character transition rules as the number of the characters inspected at a time increases. The proposed architecture was implemented on an ASIC device for evaluation and the resulting throughput can achieve 4.5 Gbps for a 4-character string matching implementation operated at 142 MHz clock.

关键词： String matching Finite state machine aho-corasick algorithm

来源：评论

学校读者我要写书评

暂无评论

Memory Efficient Parallelization for aho-corasick algorithm on a GPU

Memory Efficient Parallelization for Aho-Corasick Algorithm ...

引用

14th IEEE International Conference on High Performance Computing and Communications (HPCC) / IEEE 9th International Conference on Embedded Software and Systems (ICESS)

作者： Nhat-Phuong Tran Lee, Myungho Hong, Sugwon Shin, Minho Myongji Univ Dept Comp Sci & Engn Yongin 449728 Kyung Ki Do South Korea

ISBN: (纸本)9780769547497

Pattern matching is a commonly used operation in many applications including image processing, computer and network security, bioinformatics, among many others. aho-corasick (AC) algorithm is one of the well-known pattern matching techniques and it is intensively used in computer and network security. In order to meet the real-time performance requirements imposed on these security applications, developing a high-speed parallelization technique is essential for the AC algorithm. In this paper, we present a new memory efficient parallelization technique which efficiently places and caches the input text data and the reference data in the on-chip shared memories and texture caches of the Graphic Processing Unit (GPU). Furthermore, the new approach efficiently schedules memory accesses in order to minimize the overhead in loading data to the on-chip shared memories. The approach cuts down the effective memory access latencies and leads to significant performance improvements. Experimental results on Nvidia GeForce 9500GT GPU shows up to 15-times speedup compared with a serial version on 2.2Ghz Core2Duo Intel processor, and 15Gbps throughput performance.

关键词： aho-corasick algorithm computer security GPU parallelization

来源：评论

学校读者我要写书评

暂无评论

A File Undelete with aho-corasick algorithm In File Recovery 1

A File Undelete with Aho-Corasick Algorithm In File Recovery

引用

1st International Conference on Informatics and Computing (ICIC)

作者： Sitompul, Opim Salim Handoko, Andrew Rahmat, Romi Fadillah Univ Sumatera Utara Fac Comp Sci & Informat Technol Dept Informat Technol Medan Indonesia

ISBN: (纸本)9781509016488

In this research, a file undelete method is proposed by which the file recovery system retrieved the file metadata through a parsing process from the master file table (MFT) attributes. Using the aho-corasick algorithm, the process is then continued with a filtering process in which keywords are matched with file names. The result obtained shows that the proposed method is able to perform recovery of files that has been deleted from the file system. The experiment is performed four times with various file condition which had been overwritten 0%, 18.98%, 32.21 % and 59.77% from their original size. The rate of the average file recovery success is 87.50% and the average time required is 0.32 second for string matching on file names.

关键词： file undelete file recovery parsing process aho-corasick algorithm

来源：评论

学校读者我要写书评

暂无评论

A Parallel aho-corasick algorithm with Non-deterministic Finite Automaton Based on OpenMP 7

A Parallel Aho-Corasick Algorithm with Non-deterministic Fin...

引用

Seventh International Conference on Advanced Communication and Networking (ACN)

作者： Qu, Jiaxing Zhang, Guoyin Fang, Zhou Liu, Jiahui Liu, Xinyu Li, Fangzhou Harbin Engn Univ Harbin Peoples R China Heilongjiang Prov Elect Informat Prod Supervis In Harbin Peoples R China Harbin Univ Sci & Technol Coll Comp Sci & Technol Harbin Peoples R China

ISBN: (纸本)9781467379557

Existing typical algorithms of string matching are too difficult for taking advantage of multicore platforms. OpenMP (Open Multi-Processing) supports multiprocessing application programming interface with shared memory. We introduce a parallel aho-corasick algorithm based on OpenMP for shared memory, which exploits the non-deterministic finite automaton with space efficient for larger patterns. The experimental results show that the throughput can be achieved up to 7.5 Gbps on the average with 10000 patterns. The parallel algorithm would be successfully applied to data-intensive applications.

关键词： parallel computing aho-corasick algorithm multicore OpenMP

来源：评论

学校读者我要写书评

暂无评论

Dictionary Matching: Review of the aho-corasick algorithm and Vision for Large Dictionaries 18

Dictionary Matching: Review of the Aho-Corasick Algorithm an...

引用

8th ACM International Conference on Information Systems and Technologies (ACM ICIST)

作者： Qiao ZhanPeng Goto, Kento Ohshima, Takuya Tajima, Masahiro Motomichi, Toyama Keio Univ Yokohama Kanagawa Japan

ISBN: (纸本)9781450364041

Pattern-matching techniques have recently been applied to network security applications such as intrusion detection, virus protection, and spam filters. The widely used the aho-corasick algorithm can simultaneously match multiple patterns while providing a worst-case performance guarantee. The traditional aho-corasick algorithm has some problems on the large-scale dictionary matching, such as take a huge memory space, cost too much time when building trie, huge update cost (rebuild trie) and so on. In this paper, we summarize several recent works on the expansion of the AC algorithm: the original aho-corasick algorithm(AC), the parallel aho-corasick algorithm(PAC), and the parallel failure-less aho-corasick algorithm(PFAC). Among them, the PAC used muti-thread to process input text by divide input to few parts, but in this way, this is a problem called boundary detection problem. The PFAC which uses parallel processing, discarding the failure function and enhancing the AC processing capability by the power of GPU is relatively popular. The PFAC not only enhance the speed of matching process but also solve the boundary detection problem. In the original PFAC paper, only a small size dictionary pattern matching test was conducted. In this paper, we verify the feasibility of using PFAC for large-scale dictionary characters. And give a discussion on the possibility of using the PFAC algorithm to match large-scale pattern dictionaries. At last, we present our proposals for PFAC expansion for large-scale dictionary pattern matching. For example, the one called pattern cut approach is to cut the pattern from the common prefix with other words, and the other one is the large automaton is divided according to the input text by the prefix of words. And the sub-automatons are constructed separately. When the input text is processed, each word is processed by the sub-automaton that distributed according to the prefix of words. By this way, we can achieve the purpose of improvin

关键词： Dictionary Matching aho-corasick algorithm Parallel aho-corasick algorithm Parallel failure-less aho-corasick algorithm Pattern matching Trie Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A Memory Accessing Method for the Parallel aho-corasick algorithm on GPU 3

A Memory Accessing Method for the Parallel Aho-Corasick Algo...

引用

3rd International Conference on Information Science and Security (ICISS)

作者： Yoon, JinMyung Choi, Kang-Il Kim, HyunJin Dankook Univ Sch Elect & Elect Engn Yongin South Korea Elect & Telecommun Res Inst Adv Commun Res Lab Daejeon South Korea

ISBN: (纸本)9781509054930

In this paper, we propose a memory accessing method of Parallel Failureless aho-corasick (PFAC) algorithm considering Graphic Processing Unit (GPU) memory architecture for throughput improvement. Compared with aho-corasick (AC) algorithm using Central Processing Unit (CPU) and Data-Parallel aho-corasick (DPAC) using Open MultiProcessing (OpenMP), PFAC using GPU achieves high performance advancement in the string matching. However, due to the increasing network speed, there is need to increase the throughput of the string matching engine. In order to solve the problem of frequent memory accesses of the string matching engine based the AC algorithm, we propose the method of memory accesses for the PFAC algorithm. In the experiments using attack pattern from Snort and input stream from DEFCON on NVIDIA GTX 660. Our memory accessing method achieves about 10% improvement of throughput, compared with the original PFAC algorithm.

关键词： aho-corasick algorithm Graphic Processing Unit memory access Parallel Failureless aho-corasick algorithm string matching

来源：评论

学校读者我要写书评

暂无评论

Performance Optimization of aho-corasick algorithm on a GPU

Performance Optimization of Aho-Corasick Algorithm on a GPU

引用

12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)

作者： Nhat-Phuong Tran Lee, Myungho Hong, Sugwon Bae, Jongwoo Myongji Univ Dept Comp Sci & Engn 38-2 San Namdong Cheo In Guyong In Kyung Ki Do 449728 South Korea Myongji Univ Dept Informat Commun Engn Cheo In Guyong In Kyung Ki Do 449728 South Korea

ISBN: (纸本)9780769550220

aho-corasick (AC) algorithm is a multiple patterns matching algorithm commonly used for applications such as computer and network security, bioinformatics, image processing, among others. These applications are computationally demanding, thus optimizing performance for AC algorithm is crucial. In this paper, we present a performance optimization strategy for the AC algorithm on a Graphic Processing Unit (GPU). Our strategy efficiently utilizes the high degree of the on-chip parallelism and the complicated memory hierarchy of the GPU so that the aggregate performance (or throughput) for the AC algorithm can be optimized. The strategy significantly cuts down the effective memory access latencies and efficiently utilizes the memory bandwidth. Also, it maximizes the effects of the multithreading capability of the GPU through optimal thread scheduling. Experimental results on Nvidia GeForce GTX 285 GPU show that our approach delivers up to 127 Gbps throughput performance and 222-times speedup compared with a serial version running on single core of 2.2Ghz Core2Duo Intel processor.

关键词： aho-corasick algorithm GPU shared memory bank conflict thread scheduling multithreading

来源：评论

学校读者我要写书评

暂无评论

Node Configuration for the aho-corasick algorithm in Intrusion Detection Systems 16

Node Configuration for the Aho-Corasick Algorithm in Intrusi...

引用

12th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS)

作者： Lacroix, Alexsandre B. Langlois, J. M. Pierre Boyer, Francois-Raymond Gosselin, Antoine Bois, Guy Polytech Montreal Comp & Software Engn Dept Montreal PQ Canada

ISBN: (纸本)9781450341837

In this paper, we analyze the performance and cost trade-off from selecting two representations of nodes when implementing the aho-corasick algorithm. This algorithm can be used for pattern matching in network-based intrusion detection systems such as Snort. Our analysis uses the Snort 2.9.7 rules set, which contains almost 26k patterns. Our methodology consists of code profiling and analysis, followed by the selection of a parameter to maximize a metric that combines clock cycles count and memory usage. The parameter determines which of two types of nodes is selected for each trie node. We show that it is possible to select the parameter to optimize the metric, which results in an improvement by up to 12x compared with the single node-type case.

关键词： aho-corasick algorithm node configuration pattern matching string matching Deep Packet Inspection (DPI) Intrusion Detection System (IDS)

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：