Hi,
We are currently doing research on Network Intrusion Detection System (NIDS) on graphics hardware (Tesla). The idea is to port Aho-Corasic Multi string searching algorithm on GPU using CUDA. I would like to know if someone in the forum has done something similar to this.
Thanks ,
Heshsham
I have made a prototype year ago, it seems WM will better than AC and SBOM in some very large sample scenes.
This is interesting… can either of you post more about the problem itself and its bottlenecks?
I have done a lot of string indexing and searching experiments in CUDA for bioinformatics (which is all about matching patterns)… perhaps some of the techniques would extend to this kind of search.
In fact, I think the major problem is not CUDA itself, because I worked for a security company, they have a complicate tool chain and hard to port those to CUDA based implementation.
So, I just made the prototype to proof concept, because the major bottleneck in our product is also the pattern matching, and it seems work very well as I expected.
From the technical perspective, I remember one of the problem is the pattern length, because I use a fixed size range as one CUDA thread target,
if the pattern length is double or more than the target range, there will be a lot of overlap, waste the computing resource for repetition work
do you have good suggestion? I think maybe I should try a dynamic thread range size, but I haven’t time to finish it year ago :)
I don’t have a suggestion because I don’t quite understand the problems that need to be solved. Is it similar to virus signature matching on the GPU?
It sounds a bit like this since you’re talking about Aho Corasic. But what kind of scope does your data and dictionary have? Something like “we want to pump a 1GB/sec stream through the GPU and detect all occurrences of any of 20,000 known substrings of length 40-100.?” Is the dictionary dynamic? Is it fixed strings or are wildcards allowed? (Probably not if you’re using AC).
A paper reference or two would be interesting, even if it’s not about a GPU version.
Sure, any content security product need a lot pattern matching computing, I have read GPU Gems 3, but it seems not very a good solution :)
In fact I implement three kind of algorithms including Aho-Corasick, Set Backward Oracle and Wu-Manber from Flexible pattern matching in strings.
Basically, we are trying to replace the source code of searching algorithm for open Source SNORT Network Intrusion detection system by the CUDA version that we plan to run on NVIDIA GPUs. My technical team is facing problem in editting the source code of SNORT so that the new CUDA code could be replaced by the earlier one.
Any pointers in this regard??
Further here is a reference that I found recently GNort
Very interesting, is it a open source project or product?
hi,
We are doing same project…so far we have understood the snort architecture and some of the codes in cuda as well as
we implemented aho curosick in vc++.Now the task left is to convert this aho curosick code into cuda working code…If you done with it,
then please mail me at pnss.projectgroup@gmail.com.
Thanks .
Hi
i am also trying to implement aho corasick algorithm on gpu , actually i want to modify its data structure such that it will access global memory very few tim plus i will try to improve the algorithm.
if any one has done something previously in this area then plz send me material it will great help.
Thank you.
