Journal of Information Security, 2012, 3, 314-318
http://dx.doi.org/10.4236/jis.2012.34038 Published Online October 2012 (http://www.SciRP.org/journal/jis)
State of the Art for String Analysis and Pattern Search
Using CPU and GPU Based Programming
Mario Góngora-Blandón, Miguel Vargas-Lombardo
Centro de Investigación, Desarrollo e Innovación en Tecnologías de la Información y las Comunicaciones (CIDITIC) Grupo de
Investigación en Salud Electrónica y Supercomputación (GISES), Technological University of Panama, Panama Ci ty, Panama
Received July 11, 2012; revised August 17, 2012; accepted August 26, 2012
ABSTRACT
String matching algorithms are an important piece in the network intrusion detection systems. In these systems, the
chain coincidence algorithms occupy more than half the CPU process time. The GPU technology has sh ow ed in the past
years to have a superior performance on these types of applications than the CPU. In this article we perform a review of
the state of the art of the different string matching algorithms used in network intrusion detection systems; and also
some research done about CPU and GPU on this area.
Keywords: GPU; String Matching; Pattern Matching
1. Introduction
Jack Dongarra [1,2], explains that GPU computing is the
use of graphics processing unit together with a CPU to
accelerate general-purpose scientific and engineering ap-
plications.
String matching algorithms allow string or pattern
searching in a given text. These algorithms are used in
many applications such as: word processors and in utili-
ties like grep in UNIX [3] based operating systems.
The network based network intrusion detection sys-
tems also apply these algorithms, since most of the pro-
cessing is found in pattern search.
Studies reveal that this process takes about 75% of the
total CPU time in modern intrusion detection systems.
For this reason the graphic processors, known as GPU,
are studied to develop general purpose applications with
the GPU [4]. The main reason is that the GPU are spe-
cialized in computationally intensive operations and h ighly
parallel operations, required for graphic rendering, there-
fore are more adequate for data processing than for cache
data storage and flow control. In this article we will be
discussing different string matching algorithms and their
application in intrusion d etection systems in CPU as well
as in GPU. The article is organized as follows: in Section
II we described different string matching algorithms. In
Section III we present a state of the art of the different
studies in the network intrusion detection syste ms (NIDS)
using string matching algorithms.
Section IV presents the state of the art of the studies
done in the GPU field using string matching algorithms.
In Section V the conclusions are presented.
2. String Matching Algorithms Used in
Intrusion Detection Systems
The objective of the String Matching Algorithms is to
locate and identify all the sub-strings, given a set of pat-
terns in a specific text. To make the reading easier lets
clarify the following terms when we refer to a string
matching algorithm [3]:
 A string is a finite sequence of symbols.


12
,
k
K
 Where ,,yyy is a finite set of strings
usually called keywords.
 And x is a random string that we can call text string.
These algorithms can be classified in unique or multi-
ple pattern algorithms. This means that if we have k pat-
terns to search, the algorithm is repeated k times. Knuth-
Morris-Pratt [5] and Boyer-Moore [6] are some of the
most used unique pattern search algorithms. Multiple
pattern search algorithms look simultaneously for a set of
patterns in a text. This is achieved by applying pre-
processing techniques to the set of patterns to get an
automaton. The automaton is a state machine that’s rep-
resented as a table, or a tree or a combination of both.
Each text character will be searched once. Some of the
multiple pattern search algorithms are: Aho-Corasick [7],
Wu-Manber [8] and Commentz-W alter [9]. Next we will
describe some of these algorithms.
2.1. Brute-Force Algorithm
The Brute-Force Algorithm [3] consists in comparing
C
opyright © 2012 SciRes. JIS

M. GÓNGORA-BLANDÓN, M. VARGA S-LOMBARDO 315
two strings of characters. This algorithm compares from
left to right each word the user writes with each letter of
the name of the file found inside of the route the user
specifies. The process that this algorithm performs is the
following [3]:
 Takes the character with which the pattern starts.
 Starts to compare it with each of the text characters,
until the first match is found.
 It stops in said p osition and from there it star ts to veri-
fy if the pattern matches with the rest of the text.
If the pattern matches, it stops the comparison and
then the next file in the route is reviewed. If otherwise,
the pattern is not equivalent it will compare again the
initial position with the rest of the text characters until a
match is found again.
The outer loop is executed at most n + m – 1 times,
and the inner loop m times, for each iteration of the outer
loop. Therefore, the running time of this algorithm is in
in the worst case. Algorithm 1 shows the Brute-
Force algorithm.
 nmO
Naive-String-Ma tcher (T,P)
n = T.length
m= P.length
for s = 0 to n – m
if P[1..m] == T[s + 1..s + m]
print “Pattern occurs with shift” s
Algorithm 1. Brute force.
2.2. Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt [5] developed KMP, an algorithm
that has the primary objective to search for the existence
of a pattern insid e a text string. In the algorithm it is used
the information based on the previous data capture mis-
takes, taking in adv antage the information that the search
word has on it itself (a table of values is calculated about
it), to determine where the next finding could be, without
the need of analyzing more than once the character string
where it’s been searched.
The KMP locates the start position of a character st rin g
inside another. The first step is to locate a string, imme-
diately a table of values is calculated (known as fault or
error table). Next the strings are compared with each
other and are used to make hops when an error is located.
For example, in a pre-calculated table, both strings
start the comparison using an advance pointer for the
string that is been searched (pattern), if an error occurs
instead of returning to the po sition next to the first match,
it hops the pattern and it places it aligning the character
where the error occurred and then it continues verifying
the matches. This process is executed until the pattern
matches completely with the text. The Kn uth-Morris -Pra tt
algorithm reaches an execution time of , which
is optimal in the worst case scenario, where each text
character and pattern has to be examined at least once.
Algorithm 2 shows the Knuth-Morris-Pratt algorithm.
KMP-Matcher(T,P)
n = T.lenght
m = P. lenght
p = Compute-Prefix-Function(P)
q = 0
for i = 1 to n
while q > 0 and P[q + 1] <> T[i]
q = p[q]
if P[q + 1] == T[i]
q = q + 1
if q == m
print “Pattern occurs with shift” i - m
q = p[q]
return p
Algorithm 2. Knuth-morris-pratt.
2.3. Boyer-Moore Algorithm
The Boyer-Moore algorithm [6] is considered the most
efficient string processing algorithm on usual applica-
tions. A simplified version or the complete algorithm are
frequently implemented on tex t editors for the search and
replace commands.
This algorithm consists on aligning the pattern in a text
window and comparing from right to left the characters
in the window with the ones in the pattern. If there is a
mismatch a secure displacement, is calculated, which
allows the displacement of the window to in front of the
text without the risk of omitting a match. If the start of
the window is reached and there are no mismatches, then
a match is reported and the window is displaced.
The Booyer-Moore algorithm as presented in the origi-
nal paper has worst case running time of only
if the pattern does not appear in the text. When the pat-
tern does occur in the text the running time of the origi-
nal algorithm is
 nmO

 nmO in the worst case. In the best
case the complexity of this algorithm is in


nmO. In
Algorithm 3 we present the Boyer-Moore Algorithm.
Boyer-Moore-Matcher(T,P,E)
n = T.length
m = P.length
l = Compute-Last-Ocurrence-Function(P, m, E)
y = Compute-Good-Suffix-Function(P, m)
s = 0
while s <= n – m
do j = m
while j > 0 and P[j ] = T[s + j]
do j = j – 1
if j = 0
print “Pattern occurs at shift” s
s = s + y[0]
else
 nmO s = s + max(y[j],j - l[T[s+j]])
Algorithm 3. Boyer-moore.

M. GÓNGORA-BLANDÓN, M. VARGA S-LOMBARDO
316
2.4. Aho-Corasick Algorithm
The Aho-Corasick [7], algorithm it’s a search algorithm
created by Alfred V. Aho and Margaret J. Corasick. Is a
dictionary search algorithm that locates the ele ments of a
finite set of strings (dictionary) within an input text. The
complexity of the algorithm is linear to the length of the
patterns, plus the length of the searched text, plus the
number of matches that the output provides. It should be
noted that due to the fact that all the matches are located,
there can be a quadratic number of coincidences if each
sub-string matches.
The algorithm builds a finite state machine that resem-
bles to a tree with additional links between the different
intern nodes. These internal links allow fast transitions
between the matching patterns without the need to take
steps back. When the dictionary pattern it’s known be-
forehand the bu ilding of the automaton can be done once
it’s off-line and the compiled automaton stored for future
use.
In this situation, its execution ti me is linear in the input
length plus the number of matching inputs. In this way,
we can conclude that the Aho-Corasick algorithm is
and the pre-processing of the string is linear with
the size of the pattern . Algorithm 4 shows the
Aho-Corasick algorithm.
 nO

mO
begin
state = 0
for i = 1 to n
begin
while g(state, a1) = fail do state = f(state)
state = g(state, a1)
if output(state) <> empty
begin
print i
print output(state)
end
end
end
Algori thm 4. Aho -corasi ck.
2.5. Karp-Robin Algorithm
The Karp-Rabin algo rithm [10] searches for a pattern in a
text by hashing. So we preprocess p by computing its
hash code, then compare that hash code to the hash code
of each substring in t if we find a match in the hash codes,
we go ahead and check to make sure the strings actually
match ( in case of collisions). The best case and average
case time for this algorithm is in


nm

nmO
 km mO
O (m time to
compute hash (p) and n iterations through the loop).
However, the worse case time is in , which occurs
when we have the maximum numbers of collisions.
Karp-Rabin is inferior for single pattern searching to
many other options because of its slow worst case be-
havior. However, it is excellent for multiple pattern
searches. If we wish to find one of some large number,
say k, fixed length pattern s in a text, we can make a small
modification that uses a hash table or other set to check if
the hash of a given substring of t belongs to the set of
hashes of the patterns we are looking fo r. In this way, we
can find one k patterns in time (km for hashing
the patterns, n for searching). In Algorithm 5 we present
the Karp-Robin algorithm.
KarpRabi n( T, P)
n = T.length
m = P.length
hpatt = hash(P)
htxt = hash(T[0..m–1])
for i = 0 to n
if(htxt == hpatt)
if(t[i..i + m – 1] == P
return i
htxt = hash(T[i + 1..i + m])
print “not found”
return -1
Algorithm 5. Karp-r ob i n a lgorithm.
After describing each one of the algorithms in Table 1,
the execution times of each algorithm are shown. The
string matching processing time is defined for the worst
case and best case respectively.
In the worst case scenario, the Aho-Corasick algorithm
with a

 nO runtime has the best execution time among
the analyzed algorithms. Although for simple string
matching cases, it does not performs very well, but when
there are multiple patterns or pattern matching is done at
regular expression level, it is one of the best options.
3. String Matching Algorithm Applied to
Intrusion Detection Systems
String processing is a highly intensive computational
process; studies demonstrate that the total processing
time in a CPU reaches 75% in modern intrusion detection
systems. For this reason, is necessary to count on string
Table 1. Comparison between the execution times. String
matching algorithms. Where m is the length of the string, n
the length of the text that is been searched, z is the amount
of string matches and  the used alphabe t.
String matching
Algorithm Pre-processing
CaseWorst BestCase
Brute force No preprocessing O (nm) O (n)
KMP O (m) O (nm) O (n)
Boyer moore O (m + ) O (nm) O (n/m)
Aho corasick O (m) O (n + z) O (n)
Karp rabin O (m) O (nm) O (n + m)

M. GÓNGORA-BLANDÓN, M. VARGA S-LOMBARDO 317
matching algorithms capable of processing high amounts
of information.
Most of the network intrusion detection systems use
finite automata and regular expressions for string match-
ing. Both Fisk and Vagese [11] optimized the Boyer-
Moore-Horspool algorithm for it to process a set of rules
(strings) simultaneously.
An innovative proposal is offered in the Set-Wise
Boyer-Moore-Horspool which demonstrated to be faster
than the Aho-corasick algorithm and the Boyer-Moore
algorithm for pattern sets smaller than 100. At the same
time, about this work, Coit, Stainford and MacAlemey
[12] implemented a new version of Gunsfield in the
Commentz-Wlater algorithm using suffix trees for the
heuristics of good suffix. The algorithm was improved in
the performance of Snort [13] combining the keyword
tree of the Aho-Corasick algorithm with the hop charac-
teristic of the Boyer-Moore algorithm.
In brief, they only measured the performance of a sin-
gle set-wise algorithm, while Fisk and Vaghese [11]
measured multiple algorithms and obtained better mea-
surements without sacrificing the semantic of the rules
used by Snort. Tuck [14] optimized the Aho-Corasick
algorithm applying bitmap nodes and path compression.
4. State of the Art of Applications Based on
String Matching in GPU
The continuous growth of traffic and signature databases
make the performance of these systems increasingly
more defying and important, is for this reason that the
researchers are developing technologies that involve the
Graphic Processing Units more every time. The main
reason resides in that the GPU specializes in calculation
of highly intensive and parallel operations, and therefore,
are designed in such a way that more transistors are
dedicated to data processing instead of cache data storage
and flow control [4]. The following works [15-22], are
based in GPU high performance computing.
One of the first works in the GPU field was PixelSnort
[15], a version of the intrusion detection system Snort
which processed the string matches with a NVIDIA GPU.
The GPU programming was complicated, because this
video card doesn’t support general purpose programming
models for GPU. The system coded the Snort rules and
packages to textures and did string searches using the
Knuth-Morris-Pratt algorithm. However, PixelSnort did
not get satisfactory results in normal load conditions. In
addition, it doesn’t have any multiple pattern matching
algorithms adapted to GPU. This represents a serious
limitation because the multiple pattern matching algo-
rithms are Snort’s by default.
For Marziale [16] the GPU shaping tool performance
was evaluated. The system was implemented in a G80
architecture [23] and the results showed that the GPU
usage increased substantially in the performance of the
digital forensic software analysis, which is based in bi-
nary string search. Both Nottingham and Irwin [17] de-
signed gPF: a package classification program based in
GPU. In Smith [18] a programmed signature matching
system in a GPU G80 [23] based in SIMD (Simple In-
struction Multiple Data) was implemented. This system
outperforms a Pentium 4 until 9X and a 32 thread syste m
based in Niagara until 2.3X demonstrating that the GPU
are promising candidates for signature matching. In their
work they evaluated two signatures matching mechanism
based in finite automata, these are:
 Deterministic Finite Automaton (DFA [19]: it recog-
nizes the exact type of regular expression.
 Extended Finite Automaton (XFA) [20,24 ], it reduces
the DFA memory requirements.
On the other hand, Vasiliadis and Io annidis developed
GrAVit [21], an antivirus engine, using the architecture
of an NVIDIA GPU. They designed, implemented and
evaluated pattern matching algorithms, integrated their
GPU implementation in the ClamAV [25], antivirus, a
very popular open source antivirus. GrAVity reached an
end to end performance in the 20 Gbits order, a 100
times the performance of ClamAV using only CPU.
In [4] an intrusion detection system was designed based
in Snort, which potentiates the computational power of
the video cards (GPU). Its prototype, called Gnort, rea ch ed
maximum processing rates of traffic of 2.3 Gbits using
synthetic tracks, while using an Ethernet interface; it
surpassed Snort by a factor of two. Its results demon-
strate that modern video cards can be used effectively to
accelerate the intrusion detection systems, as well as
other systems that involve string matching operations.
Seaman and Alexander [22] presented ways to build a
special type of regular expressions used by ClamAV in a
GPU. Phar and Fernando [26] show a review of some
high performan ce applications adapted to GPU.
This state of the art allowed us to identify string
matching algorithms with better performance that the
ones described previously. Also, it was demonstrated that
exists a very wide research field on GPU, specifically in
pattern analysis in intrusion detection systems. These
researches have given evidence that the usage of GPU
give better performance than the CPU.
5. Conclusion
In this article, we present a state of the art of different
algorithms used for pattern matching in network intru-
sion detection systems. We compare the execution time
of these algorithms. Also, we discuss different studies
that presented proposals to improve the algorithms based
in string matching. Finally, we present a state of the art
on some studies on pattern search and package signing

M. GÓNGORA-BLANDÓN, M. VARGA S-LOMBARDO
318
using GPU technology. We can state that in the next
years the high performance application development us-
ing GPU will increase, displacing CPU eventually.
REFERENCES
[1] S. Tomov, J. Dongarra and M. Baboulin, “Towards Dense
Linear Algebra for Hybrid GPU Accelerated Manycore
Systems,” Parallel Computing, Vol. 36, No. 5-6, 2010, pp.
232-240. doi:10.1016/j.parco.2009.12.005
[2] NVIDIA, “What Is GPU Computing,” 2012.
http://www.nvidia.com/object/what-is-gpu-computing.ht
ml
[3] D. Gusfield, “Algorithms on Strings, Trees, and Sequences:
Computer Science and Computational Biology,” Cam-
bridge University, Cambridge, 1997.
doi:10.1017/CBO9780511574931
[4] G. Vasiliadis, S. Antonatos, M. Poly chronakis, E. P. Mar-
katos and S. Ioannidis, “Gnort: High Performance Net-
work Intrusion Detection Using Graphics Processors,”
Proceedings of the 11th International Symposium on Re-
cent Advances in Intrusion Detection, Cambridge, 15-17
September 2008, pp. 116-134.
[5] D. E. Knuth, J. H. Morris Jr. and V. R. Pratt, “Fast Pattern
Matching in Strings,” SIAM Journal on Computing, Vol.
6, No. 2, 1977, pp. 323-350.
[6] R. S. Boyer and J. S. Moore, “A Fast String Searching
Algorithm,” Communications of the ACM, Vol. 20, No.
10, 1977, pp. 762-772.
[7] A. V. Aho and M. J. Corasick, “Efficient String Matching:
An Aid to Bibliographic Search,” Communications of the
ACM, Vol. 18, No. 6, 1975, pp. 333-340.
[8] S. Wu and U. Manber, “A Fast Algorithm for Multi-Pat-
tern Searching,” Technical Report TR-94-17, University
of Arizona, Tucson, 1994.
[9] B. Commentz-Walter, “A String Matching Algorithm Fast
on the Average,” Automata, Languages and Program-
ming, Vol. 71, 1979, pp. 118-132.
[10] R. M. Karp and M. O. Rabin, “Efficient Randomized
Pattern-Matching Algorithms,” IBM Journal of Research
and Development, Vol. 31, No. 2, 1987, pp. 249-260.
[11] M. Fisk and G. Varghese, “Applying Fast String Match-
ing to Intrusion Detection,” University of California, San
Diego, 2004.
[12] C. J. Coit, S. Staniford and J. McAlerney, “Towards
Faster String Matching for Intrusion Detection or Ex-
ceeding the Speed of Snort,” DARPA Information Sur-
vivability Conference and Exposition, Vol. 1, No. 2, 2001,
pp. 367-373.
[13] M. Roesch, et al., “Snort-Lightweight Intrusion Detection
for Networks,” Proceedings of the 13th USENIX Confer-
ence on System Administration, Seattle, 7-12 November
1999, pp. 229-238.
[14] N. Tuck, T. Sherwood, B. Calder and G. Varghese, “De-
terministic Memory-Efficient String Matching Algorithms
for Intrusion Detection,” INFOCOM, Vol. 4, 2004, pp.
2628-2639.
[15] N. Jacob and C. Brodley, “Offloading IDS Computation
to the GPU,” Proceedings of the 22nd Annual Computer
Security Applications Conference, Washington DC, 11-15
December 2006, pp. 371-380.
[16] L. Marziale, G. G. Richard III and V. Roussev, “Massive
Threading: Using GPUs to Increase the Performance of
Digital Forensics Tools,” Digital Investigation, Vol. 4,
2007, pp. 73-81.
[17] A. T. Nottingham and B. Irwin, “gPF: A GPU Acceler-
ated Packet Classification Tool,” Southern African Tele-
communications Networks and Applications Conference,
Royal Swazi Spa, 30 August-2 September 2009, pp. 339-
344.
[18] R. Smith, N. Goyal, J. Ormont, K. Sankaralingam and C.
Estan, “Evaluating GPUs for Network Packet Signature
Matching,” IEEE International Symposium on Perform-
ance Analysis of Systems and Software, Boston, 26-28
April 2009, pp. 175-184.
doi:10.1109/ISPASS.2009.4919649
[19] F. Yu, Z. Chen, Y. Diao, T. V. Lakshman and R. H. Katz,
“Fast and Memory-Efficient Regular Expression Match-
ing for Deep Packet Inspection,” Proceedings of the 2006
ACM/IEEE Symposium on Architecture for Networking
and Communications Systems, California, 4-5 December
2006, pp. 93-102. doi:10.1145/1185347.1185360
[20] R. Smith, C. Estan, S. Jha and S. Kong, “Deflating the
Big Bang: Fast and Scalable Deep Packet Inspection with
Extended Finite Automata,” SIGCOMM Computer Com-
munication Review, Vol. 38, No. 4, 2008, pp. 207-218.
[21] G. Vasiliadis and S. Ioannidis, “Gravity: A Massively
Parallel Antivirus Engine,” Recent Advances in Intrusion
Detection, Vol. 6307, 2011, pp. 79-96.
[22] E. Seamans and E. Alexander, “Fast Virus Signature
Matching on the GPU,” GPU Gems, Vol. 3, No. 1, 2007,
pp. 771-783.
[23] J. Owens, “GPU Architecture Overview,” ACM SIG-
GRAPH, Vol. 1, No. 2, 2007, pp. 5-9.
[24] R. Smith, C. Estan and S. Jha, “XFA: Faster Signature
Matching with Extended Automata,” Proceedings of the
2008 IEEE Symposium on Security and Privacy, Oakland,
18-21 May 2008, pp. 187-201.
[25] T. Kojm, “ClamAV,” 2004. http://www. clamav. net
[26] M. Pharr and R. Fernando, “2: Programming Techniques
for High-Performance Graphics and General-Purpose
Computation (Gpu Gems),” Addison-Wesley Professional,
Boston, 2005.