Optimized Aho-Corasick string matching algorithm for smart phones
Rui Lu, Derek C.W. Pao · 2016
String matching is a core component of signature-based malware detection. Unlike personal computers, smart phones have limited memory resources. In this poster, we shall present an optimized version of the Aho-Corasick (AC) string matching algorithm for smart phones. The basic AC algorithm consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. The proposed optimized AC algorithm has outstanding performances in both space and time. The memory cost of the proposed algorithm is close to the basic AC algorithm, and the processing speed can be faster than the fully expanded version when executed on smart phones.