Signature-Based Malware Detection Using Approximate Boyer Moore String Matching Algorithm

Full Text (PDF, 745KB), PP.49-62

Views: 0 Downloads: 0


A. Ojugoa 1,* A. O. Eboka 2

1. Department of Mathematics/Computer Science, Federal University of Petroleum Resources Effurun, Delta State, Nigeria

2. Department of Computer Education, Federal College of Education (Technical), Asaba, Delta State, Nigeria.

* Corresponding author.


Received: 22 Jun. 2018 / Revised: 18 Apr. 2019 / Accepted: 13 Jun. 2019 / Published: 8 Jul. 2019

Index Terms

String Matching Algorithm, Malware Detection, Metamorphics, Pattern Matching, Code Obfuscation


Adversaries to any system restlessly continues to sought effective, non-detectable means to aid them successful penetrate secure systems, either for fun or commercial gains. They achieve these feats easily through the use of malware, which keeps on the rise, an ever-growing and corresponding overpopulated malware zoo. As such, information technology industry will continue to encounter via these escapades, both monetary and prestigious losses. Malware by design aims to alter the behaviour of its host by self-replicating its genome or codes unto it. They are quite fascinating in that on execution, some malware change their own structure so that its copies have same functionality but differ in signature and syntax from the original or parent virus. This makes signature detection quite unreliable. Study investigates detection of metamorphic malware attacks using the Boyer Moore algorithm for string-based signature detection scheme.

Cite This Paper

A. Ojugo, A. O. Eboka,"Signature-Based Malware Detection Using Approximate Boyer Moore String Matching Algorithm", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.5, No.3, pp.49-62, 2019. DOI: 10.5815/ijmsc.2019.03.05


[1]Grossi, R and Luccio, F., (1989). Simple and efficient string matching with k mismatches, Information Processing Letters, Vol. 33, pp113–120.

[2]Ukkonen, E and Wood, D., (1990). Fast approximate string matching with suffix automata, Report A-1990-4, Department of Computer Science, University of Helsinki.

[3]Zink, T., (2009). Network security algorithms, Konstanzer Online Publikationss-System,

[4]Daoud, E and Jebril, I., (2008). Computer Virus Strategies and Detection Methods, International Journal of Open Problems Computational Mathematics, 1(2), [web]:

[5]Dawkins, R., “The selfish gene”, Oxford University Press, Second Edition, 1989. 

[6]Zakorzhevsky, E.R., “Monthly malware statistics”, 2011,[online]

[7]Allenotor, D., “An Evolvable Framework for Metamorphics”. Computing, Information Systems, Development Informatics and Allied Research Journal, 2016, Vol 7 No 2. Pp 33-40 Available online at 

[8]Ojugo, A.A., “Computer virus evolution: polymorphics analysis and detection”, Journal of Academic Research, 2010, Vol. 15, No. 8, p34 – 46.

[9]Ojugo, A.A., R.E. Yoro., A. Eboka., M.O. Yerokun., C.N. Anujeonye and F.N. Efozia (2014). Evolutionary model for virus propagation on networks, Automation, Control and Intelligent Systems, 3(4): 56-62, doi: 10.11648/j.acis.20150304.12.

[10]Ojugo, A.A., A.O. Eboka., R.E. Yoro., M.O. Yerokun and F.N. Efozia., (2015). Framework design for statistical fraud detection, Mathematics and Computers in Science and Industry (Mathematics and Computers in Science and Engineering Series), 50: 176-182, ISBN: 978‐1‐61804‐327‐6, ISSN: 2227‐4588 

[11]Ye, Y., Wang, D., Li, T and Ye, D., “Intelligent malware detection based on association mining”, Journal of Computer Virology, 2008, Vol. 4, No. 4, p323–334, doi: 10.1007/s11416-008-0082-4.

[12]Szor, P., “The Art of Computer Virus Research and Defense”, Addison Wesley Symantec Press. 2005, ISBN-10: 0321304543, New Jersey.

[13]Mishra, P., “Taxonomy of software unique transformations”, 2003,

[14]Orr, “The viral Darwinism of W32.Evol: an in-depth analysis of a metamorphic engine”, 2006, [online]: available at

[15]Orr, “The molecular virology of Lexotan32: Metamorphism illustrated”, 2007, [online]:

[16]Singhal, P and Raul, N., “Malware detection module using machine learning algorithm to assist centralized security in enterprise network”, International Journal of Network Security and Applications, 2012, 4(1), doi: 10.5121/ijnsa.2012.4106, p61

[17]Rabek, J., Khazan, R., Lewandowski, S., Cunningham, R., “Detection of injected, dynamic generated and obfuscated malicious code”, In Proceedings of ACM Workshop on Rapid Malcode, 2003, p76.

[18]Filiol, E., “Computer Viruses: from Theory to Applications”, New York, Springer, 2005, ISBN 10: 2287-23939-1. 

[19]Hashemi,S., Yang, Y., Zabihzadeh, D and Kangavari, M., “Detecting intrusion transactions in databases using data item dependencies and anomaly analysis”, Expert Systems, 2008, Vol. 25, No. 5, p460, doi:10.1111/j.1468-0394.2008.00467.x

[20]Grimes, R., “Malicious Mobile Code: Virus Protection for Windows”, O'Reilly and Associates, Inc., Sebastopol, CA, USA, 2001.

[21]Cohen, F., “Computer viruses: theory and experiments”, Computer Security, 1987, 6(1), p22-35.

[22]Sung, A., Xu, J., Chavez, P., Mukkamala, S., “Static analyzer of vicious executables”, Proceedings of 20th Annual Computer Security Applications Conference, IEEE Computer Society, 2004, p326-334.

[23]Venkatesan, A., “Code obfuscation and metamorphic Virus Detection”, Master thesis, San Jose State University, 2006,

[24]Konstantinou, E., “Metamorphic virus: analysis and detection”, Technical report (RHUL-MA-2008-02), Dept. of Mathematics, Royal Holloway, University of London, 2008.

[25]Walenstein, R., Mathur, M., Chouchane R., and Lakhotia, A., “The design space of metamorphic malware”, In Proceedings of 2nd Int. Conference on Information Warfare, 2007, p243.

[26]Wong, W., “Analysis and Detection of Metamorphic Computer Viruses”, Master’s thesis, San Jose State University, 2006,

[27]Borello, J and Me, L., “Code obfuscation techniques for Metamorphics, 2008, [online]: available at

[28]Aycock, J., “Computer Viruses and malware”, Springer Science and Business Media, 2006.

[29]VX Heavens Virus Collection, [online]:

[30]Ojugo, A.A and Yoro, R.E., “Computational intelligence in stochastic solution for Toroidal Queen”, Progress in Intelligence Computing Applications, 2013a, Vol. 2, No. 1, doi: 10.4156/pica.vol2.issue1.4, p46

[31]Ojugo, A.A., Emudianughe, J., Yoro, R.E., Okonta, E.O and Eboka, A.O., “Hybrid artificial neural network gravitational search algorithm for rainfall runoff”, Progress in Intelligence Computing and Applications, 2013b, Vol. 2, No. 1, doi: 10.4156/pica.vol2.issue1.2, p22.

[32]Ojugo, A.A., Oyemade, D.A., Allenotor, D., Longe, O.B and Anujeonye, C.N., “Comparative Stochastic Study for Credit-Card Fraud Detection Models,. African Journal of Computing and ICT, 2015, Vol 8, No. 1, Issue 2. pp 15-24.

[33]Ojugo, A.A., Eboka, A.O., Yoro, R.E., Yerokun, M.O and Efozia, F.N., Hybrid model for early diabetes diagnosis, Mathematics and Computers in Science and Industry (A Mathematics and Computers in Science and Engineering Series), 2015, 50: 176-182, ISBN: 978‐1‐61804‐327‐6, ISSN: 2227‐4588

[34]Ojugo, A.A., “A profile hidden markov model for forecasting energy spread options direction and volatility, Technical Report for Dynamic High Performance Computing Research Group of the Federal University of Petroleum Resources Effurun, 2013, FUPRE-TR-DHCP-08, Pp 10-24.

[35]Ramage, D., “Hidden markov model fundamentals”, Lecture notes in Computer Science, [online source]:

[36]Noreen, S., Ashraf, J and Svrenahak, K., “Malware detection using evolutionary models”, International Journal of Virology, 2008, Vol. 23, No. 2, p123-132.

[37]Ojugo, A., A.O. Eboka., E.O. Okonta., E.R. Yoro and F.O. Aghware., “Genetic algorithm trained rule-based intrusion detection system”, Journal of Emerging Trends in Computing and Information Systems, Vol. 3, No. 8, 2012, Pp 1182-1194

[38]Ursem, R., Krink, T., Jensen, M.and Michalewicz, Z., “Analysis and modeling of controls in dynamic systems”, IEEE Transaction on Evolutionary Computing, 2002, 6(4), p378-389. 

[39]Clerc, M., “The .Aswarm and the queen: towards a deterministic and adaptive particle swarm optimization”, In Proceedings of Evolutionary Computation (IEEE), 1999, 5, p123-132.

[40]Gray, J and Klefstad, R., “Adaptive and evolvable software systems: techniques, tools and applications”, 38th Annual Hawaii Int. Conf. on System Sciences, 2005, p274, IEEE Press.

[41]Hassan, R and Crosswley, W., “Variable population-based sampling for probabilistic design optimization and with a genetic algorithm”, Proceedings of 42nd Aerospace Science, p32, Reno: NV, 2004.

[42]Hassan, R., Cohanin, B., De Wec and Venter, G., “Comparison of particle swarm optimization and genetic algorithm”, In Proceeding of 44th Aerospace Science, 2004, Washington, p56.

[43]Homaifar, A.A., Turner, J and Ali, S., “N-queens problem and genetic algorithms”, In Proceedings of the IEEE Southeast conference, 1992, p262.

[44]Hu, X., Eberhart, R.C and Kennedy, J., “Solving constrained nonlinear optimization problems with PSO, In Proceedings of the Multi-conference on Systems, Cybernetics and Informatics, 2005a, p234.

[45]Hu, X., Eberhart, R.C and Shi, Y., “Swarm intelligence for permutation optimization: study of n-queens”, Proceedings of IEEE Genetic Evolutionary Computing on Memetic Algorithm, 2005b, p243

[46]Kennedy, J and Mendes, R., “Population structure and particle swarm performance”, In Proceedings of the IEEE Congress on Evolutionary Computation, 2002, p1671, Honolulu 

[47]Lakhotia, A., Kapoor, A and Kumar, E.U., “Are metamorphic computer viruses really invisible?”, 2004, Part 1, Virus bulletin, p5-7.

[48]Ojugo, A.A and Eboka, A.O,, “An intelligent hunting profile for evolvable metamorphic malware”, IEEE African Journal of Computing and ICT, 2015, 8(1-2), p181.

[49]Desai, P., “Towards an undetectable computer virus, Masters Thesis, Department of Computer Science, San Jose State University, 2008

[50]Gong, R.H.., Zulkernine, M & Abolmaesumi, P., “A software implementation of GA based to network intrusion detection”, 2005,

[51]Kandeeban, S. S. and Rajesh, R. S., (2007): GA for framing rules for intrusion detection, J. Comp. Sci and Security., 7(11), ISSN:1738-7906, PP.285-290.

[52]Kurose, J.F and Ross, K.N., “Computer network a top down approach”, Pearson publisher, 2010, ISBN-10: 0-13-136548-7.

[53]Ojugo, A.A and Allenotor, D., “Text mining identification and detection using the exact string matching algorithm: a comparative analysis”, Journal of Digital Innvations & Contemporary Research in Science, Engineering and Technology, 2018, 6(1), p169-180.