• Jul 03, 2017 News!JACN Vol.4, No.2 has been indexed by EI (inspec)!   [Click]
  • Jul 12, 2017 News!JACN Vol.5, No.1 has been published with online version.
  • Jul 03, 2017 News!Welcome to join in the 2017 8th International Conference on Networking and Information Technology (ICNIT 2017), which will be held in Penang, Malaysia during November 24-26, 2017.
General Information
    • ISSN: 1793-8244
    • Frequency: Semiyearly
    • DOI: 10.18178/JACN
    • Editor-in-Chief: Dr. Ka Wai Gary Wong
    • Executive Editor: Ms. Nina Lee
    • Abstracting/ Indexing: EI (INSPEC, IET), Engineering & Technology Digital Library, DOAJ, Electronic Journals Library, Ulrich's Periodicals Directory, International Computer Science Digital Library (ICSDL), ProQuest, and Google Scholar.
    • E-mail: jacn@ejournal.net
Editor-in-chief
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).

[PDF]

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-2017. Journal of Advances in Computer Networks.  All rights reserved.
E-mail: jacn@ejournal.net