Performance evaluation of string matching algorithms on smart phones

Abstract

Smartphone malwares and anti-virus applications have raised a lot of concerns, for which the Signature-based technique is widely used. At the same time, although the evolution of smartphones has equipped them with higher computation power and memory space, the computation and memory resources available are still very limited. In this report, several versions of Aho-Corasick (AC) string matching algorithms have been studied and discussed for their performance on different platforms as well as space-time efficiency. For example, the basic AC with GOTO and Failure functions is memory efficient but time-consuming, while the expanded version with full state transition table can be very fast but memory-demanding. Here we study another method to reduce the transition table size by row-shift hash table with minimum degradation to the performance. These AC algorithms are implemented and tested on both PC and smartphone. Among the five selected AC algorithms, AC Row Shift stands out as it is both memory and time efficient. Due to the fact that smartphone has limited resources, AC Row Shift algorithm can be a suitable solution for the smartphone malware detection.