• Dec 20, 2018 News!JACN Vol.6, No.2 has been published with online version.   [Click]
  • Sep 17, 2018 News!Welcome to 2019 4th International Conference on Information and Network Technologies (ICINT 2019), which will be held in Kyoto, Japan during May 25-27, 2019.   [Click]
  • Jul 04, 2018 News!JACN Vol.6, No.1 has been published with online version.   [Click]
General Information
    • ISSN: 1793-8244
    • Abbreviated Title:  J. Adv. Comput. Netw.
    • Frequency: Semiyearly
    • DOI: 10.18178/JACN
    • Editor-in-Chief: Dr. Ka Wai Gary Wong
    • Executive Editor: Ms. Nina Lee
    • Abstracting/ Indexing: EI (INSPEC, IET),  Electronic Journals Library, Ulrich's Periodicals Directory, EBSCO, ProQuest, and Google Scholar.
    • E-mail: jacn@ejournal.net
Dr. Ka Wai Gary Wong
Division of Information and Technology Studies, Faculty of Education, The University of Hong Kong.
It's a honor to serve as the editor-in-chief of JACN. I'll work together with the editors and reviewers to help the journal progress
JACN 2013 Vol.1(3): 228-233 ISSN: 1793-8244
DOI: 10.7763/JACN.2013.V1.45

Attacking Pattern Matching Algorithms Based on the Gap between Average-Case and Worst-Case Complexity

Yu Zhang, Ping Liu, Yanbing Liu, Aiping Li, Cuilan Du, and Dongjin Fan
Abstract—We have developed an effective method to generate attack data for widely-used pattern matching algorithms. Perceived to be a fundamental problem in the field of computer science, pattern matching has received extensive attention in research and has been used in a variety of fields to include information retrieval, computational biology, information security, etc. The extensive applications of pattern matching are mainly rooted in the fact that pattern matching algorithms, such as SBOM and WuManber, typically have a low time-complexity. However, in the worst case time-complexities of algorithms are very high, making pattern matching algorithms vulnerable to algorithmic complexity attacks (in other words, one might significantly slow down pattern matching algorithms simply by feeding them with specifically-designed text). In this study, we investigated this potential vulnerability by proposing a dynamic programming method designed to attack text having knowledge of patterns. Experimental results suggest that SBOM and WuManber run the specifically-designed text slower than random text (real text). Interestingly, it has been observed that the attacking method is still effective even when parts of patterns are only known, meaning that even a leak of small proportions has the potential to lead to severe attacks. Finally, we propose some suggestions to reduce the risks of these attacks. To the best of our knowledge, this is the first time that an attacking pattern matching approach is proposed based on algorithm complexity.

Index Terms—Computer security, algorithmic complexity attacks, pattern matching, SBOM algorithm, WuManber algorithm.

Yu Zhang, Ping Liu, and Yanbing Liu are with Institute of Information Engineering, University of Chinese Academy of Sciences, 100093, Beijing, China (e-mail: zhangyu@iie.ac.cn, liuping@iie.ac.cn, liuyanbing@iie.ac.cn).
Aiping Li is with National University of Defense Technology, 410073, Changsha, China (e-mail: apli1974@gmail.com).
Cuilan Du and Dongjin Fan are with National Computer Network Emergency Response Technical Team/Coordination Center of China, 100029, Beijing, China (e-mail: dcl@isc.org.cn, fandongjin@126.com).


Cite:Yu Zhang, Ping Liu, Yanbing Liu, Aiping Li, Cuilan Du, and Dongjin Fan, "Attacking Pattern Matching Algorithms Based on the Gap between Average-Case and Worst-Case Complexity," Journal of Advances in Computer Networks vol. 1, no. 3, pp. 228-233, 2013.

Copyright © 2008-2018. Journal of Advances in Computer Networks.  All rights reserved.
E-mail: jacn@ejournal.net