• Feb 07, 2023 News!JACN will adopt Article-by-Article Work Flow. The benefit of article-by-article workflow is that a delay with one article may not delay the entire issue. Once a paper steps into production, it will be published online soon.   [Click]
  • May 30, 2022 News!JACN Vol.10, No.1 has been published with online version.   [Click]
  • Dec 24, 2021 News!Volume 9 No 1 has been indexed by EI (inspec)!   [Click]
General Information
    • ISSN: 1793-8244 (Print)
    • Abbreviated Title:  J. Adv. Comput. Netw.
    • Frequency: Semiyearly
    • DOI: 10.18178/JACN
    • Editor-in-Chief: Professor Haklin Kimm
    • Executive Editor: Ms. Cherry Chan
    • Abstracting/ Indexing: EBSCO, ProQuest, and Google Scholar.
    • E-mail: jacn@ejournal.net
    • APC: 500USD
Professor Haklin Kimm
East Stroudsburg University, USA
I'm happy to take on the position of editor in chief of JACN. We encourage authors to submit papers on all aspects of computer networks.

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