Применение алгоритмов биоинформатики для обнаружения мутирующих кибератак
Ключевые слова:
алгоритм Укконена, безопасность, биоинформатика, выравнивание, мутация, полиморфизм, сигнатура, суффиксное деревоАннотация
Функционал любой системы может быть представлен в виде совокупности команд, которые приводят к изменению состояния системы. Задача обнаружения атаки для сигнатурных систем обнаружения вторжений эквивалентна сопоставлению последовательностей команд, выполняемых защищаемой системой, с известными сигнатурами атак. Различные мутации в векторах атак (включая замену команд на равносильные, перестановку команд и их блоков, добавление мусорных и пустых команд) снижают эффективность и точность обнаружения вторжений. В статье проанализированы существующие решения в области биоинформатики, рассмотрена их применимость для идентификации мутирующих атак. Предложен новый подход к обнаружению атак на основе технологии суффиксных деревьев, используемой при сборке и проверке схожести геномных последовательностей. Применение алгоритмов биоинформатики позволяет добиться высокой точности обнаружения мутирующих атак на уровне современных систем обнаружения вторжений (более 90%), при этом превосходя их по экономичности использования памяти, быстродействию и устойчивости к изменениям векторов атак. Для улучшения показателей точности проведен ряд модификаций разработанного решения, вследствие которых точность обнаружения атак увеличена до 95% при уровне мутаций в последовательности до 10%. Метод может применяться для обнаружения вторжений как в классических компьютерных сетях, так и в современных реконфигурируемых сетевых инфраструктурах с ограниченными ресурсами (Интернет вещей, сети киберфизических объектов, сенсорные сети).
Литература
1. Khraisat A., Gondal I., Vamplew P., Kamruzzaman J. Survey of intrusion detection systems: techniques, datasets and challenges // Cybersecurity. 2019. vol. 2. no. 1.
2. Jatti S.A.V., Kishor Sontif V.J.K. Intrusion detection systems // International Journal of Recent Technology and Engineering. 2019. vol. 8. no. 2. special is-sue 11. pp. 3976–3983.
3. Branitskiy A.A., Kotenko I.V. Analysis and classification of methods for net-work attack detection // SPIIRAS Proceedings. 2016. vol. 2. no. 45. pp. 207–244.
4. Lakshminarayana D.H., Philips J., Tabrizi N. A survey of intrusion detection techniques // In Proceedings - 18th IEEE International Conference on Machine Learning and Applications, ICMLA 2019. 2019. pp. 1122–1129.
5. Platonov V.V., Semenov P.O. An adaptive model of a distributed intrusion detection system // Automatic Control and Computer Sciences. 2017. vol. 51. no. 8. pp. 894–898.
6. Platonov V.V., Semenov P.O. Detection of Abnormal Traffic in Dynamic Com-puter Networks with Mobile Consumer Devices // Automatic Control and Computer Sciences, 2018. vol. 52. no. 8. pp. 959–964.
7. Aljawarneh S.A., Moftah R.A., Maatuk A.M. Investigations of automatic methods for detecting the polymorphic worms signatures // Future Generation Computer Systems. 2016. vol. 60. pp. 67–77.
8. Khonde S.R., Venugopal U. Hybrid architecture for distributed intrusion detec-tion system // Ingenierie des Systemes d’Information. 2019. vol. 24. no. 1. pp. 19–28.
9. Zhang W.A., Hong Z., Zhu J.W., Chen B. A survey of network intrusion detection methods for industrial control systems // Kongzhi yu Juece/Control and Decision. 2019. vol. 34. no. 11. pp. 2277–2288.
10. Seoane Fernández J.A., Miguélez Rico M. Bio-Inspired Algorithms in Bioinformatics I // Encyclopedia of Artificial Intelligence. 2011.
11. Levshun D, Gaifulina D., Chechulin A., Kotenko I. Problematic issues of in-formation security of cyber-physical systems // SPIIRAS Proceedings. 2020. vol. 19. no. 5. pp. 1050–1088.
12. Coull S., Branch J., Szymanski B., Breimer E. Intrusion detection: A bioinformatics approach // In Proceedings Annual Computer Security Applications Conference, ACSAC. 2003. vol. 2003-January. pp. 24–33.
13. Lavrova D., Zaitceva E., Zegzhda P. Bio-inspired approach to self-regulation for industrial dynamic network infrastructure // CEUR Workshop Proceedings. 2019. vol. 2603. pp. 34–39.
14. Miller W. An Introduction to Bioinformatics Algorithms // Journal of the American Statistical Association. 2006. vol. 101. no. 474. pp. 855–855.
15. Sohn J. Il, Nam J.W. The present and future of de novo whole-genome assembly // Briefings in Bioinformatics. 2018. vol. 19, no. 1, pp. 23–40.
16. Recanati A., Brüls T., D’Aspremont A. A spectral algorithm for fast de novo layout of uncorrected long nanopore reads // Bioinformatics. 2017. vol. 33, no. 20. pp. 3188–3194.
17. Rizzi R., et al. Overlap graphs and de Bruijn graphs: data structures for de novo genome assembly in the big data era // Quantitative Biology. 2019. vol. 7, no. 4. pp. 278–292.
18. Wittler R. Alignment- And reference-free phylogenomics with colored de Bruijn graphs // Algorithms for Molecular Biology. 2020. vol. 15. no. 1.
19. Tan T.W., Lee E. Sequence Alignment // Beginners Guide to Bioinformatics for High Throughput Sequencing. 2018. pp. 81–115.
20. Muhamad F.N., Ahmad R.B., Asi S.M., Murad M.N. Performance Analysis of Needleman-Wunsch Algorithm (Global) and Smith-Waterman Algorithm (Lo-cal) in Reducing Search Space and Time for DNA Sequence Alignment // Journal of Physics: Conference Series. 2018. vol. 1019. no. 1.
21. Lee Y.S., Kim Y.S., Uy R.L. Serial and parallel implementation of Needleman-Wunsch algorithm // International Journal of Advances in Intelligent Informatics. 2020. vol. 6. no. 1. pp. 97–108.
22. Čavojský M., Drozda M., Balogh Z. Analysis and experimental evaluation of the Needleman-Wunsch algorithm for trajectory comparison // Expert Systems with Applications. 2021. vol. 165.
23. Sun J., Chen K., Hao Z. Pairwise alignment for very long nucleic acid sequences // Biochemical and Biophysical Research Communications. 2018. vol. 502. no. 3. pp. 313–317.
24. Zou H., Tang S., Yu C., Fu H., Li Y., Tang W. ASW: Accelerating Smith–Waterman Algorithm on Coupled CPU-GPU Architecture // International Journal of Parallel Programming. 2019. vol. 47. no. 3. pp. 388–402.
25. Chowdhury B., Garai G. A review on multiple sequence alignment from the perspective of genetic algorithm // Genomics. 2017. vol. 109. no. 5–6. pp. 419–431.
26. Dijkstra M.J.J., Van Der Ploeg A.J., Feenstra K. A., Fokkink W.J., Abeln S., Heringa J. Tailor-made multiple sequence alignments using the PRALINE 2 alignment toolkit // Bioinformatics. 2019. vol. 35. no. 24. pp. 5315–5317.
27. Chen S., Yang S., Zhou M., Burd R., Marsic I. Process-Oriented Iterative Multiple Alignment for Medical Process Mining // In IEEE International Conference on Data Mining Workshops, ICDMW. 2017. vol. 2017-November. pp. 438–445.
28. Ye N. Markov Chain Models and Hidden Markov Models // Data Mining. 2021. pp. 287–305.
29. Behera N., Jeevitesh M.S., Jose J., Kant K., Dey A., Mazher J. Higher accuracy protein multiple sequence alignments by genetic algorithm // Procedia Comput-er Science. 2017. vol. 108. pp. 1135–1144.
30. Cui X., Shi H., Zhao J., Ge Y., Yin Y., Zhao K. High Accuracy Short Reads Alignment Using Multiple Hash Index Tables on FPGA Platform // In Proceed-ings of 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference, ITOEC. 2020. pp. 567–573.
31. Marçais G., Delcher A.L., Phillippy A.M., Coston R., Salzberg S.L., Zimin A. MUMmer4: A fast and versatile genome alignment system // PLoS Computational Biology. 2018. vol. 14. no. 1. 2018.
32. Kay M. Substring alignment using suffix trees // Lecture Notes in Computer Science. 2004. vol. 2945. pp. 275–282.
33. Ukkonen E. On-line construction of suffix trees // Algorithmica. 1995. vol. 14. no. 3. pp. 249–260.
34. Breslauer D., Italiano G.F. On suffix extensions in suffix trees // Theoretical Computer Science. 2012. vol. 457. pp. 27–34.
35. KDD Cup 1999 Data: URL: kdd.ics.uci.edu/databases/kddcup99/kddcup99.html (дата доступа: 10.04.2021).
2. Jatti S.A.V., Kishor Sontif V.J.K. Intrusion detection systems // International Journal of Recent Technology and Engineering. 2019. vol. 8. no. 2. special is-sue 11. pp. 3976–3983.
3. Branitskiy A.A., Kotenko I.V. Analysis and classification of methods for net-work attack detection // SPIIRAS Proceedings. 2016. vol. 2. no. 45. pp. 207–244.
4. Lakshminarayana D.H., Philips J., Tabrizi N. A survey of intrusion detection techniques // In Proceedings - 18th IEEE International Conference on Machine Learning and Applications, ICMLA 2019. 2019. pp. 1122–1129.
5. Platonov V.V., Semenov P.O. An adaptive model of a distributed intrusion detection system // Automatic Control and Computer Sciences. 2017. vol. 51. no. 8. pp. 894–898.
6. Platonov V.V., Semenov P.O. Detection of Abnormal Traffic in Dynamic Com-puter Networks with Mobile Consumer Devices // Automatic Control and Computer Sciences, 2018. vol. 52. no. 8. pp. 959–964.
7. Aljawarneh S.A., Moftah R.A., Maatuk A.M. Investigations of automatic methods for detecting the polymorphic worms signatures // Future Generation Computer Systems. 2016. vol. 60. pp. 67–77.
8. Khonde S.R., Venugopal U. Hybrid architecture for distributed intrusion detec-tion system // Ingenierie des Systemes d’Information. 2019. vol. 24. no. 1. pp. 19–28.
9. Zhang W.A., Hong Z., Zhu J.W., Chen B. A survey of network intrusion detection methods for industrial control systems // Kongzhi yu Juece/Control and Decision. 2019. vol. 34. no. 11. pp. 2277–2288.
10. Seoane Fernández J.A., Miguélez Rico M. Bio-Inspired Algorithms in Bioinformatics I // Encyclopedia of Artificial Intelligence. 2011.
11. Levshun D, Gaifulina D., Chechulin A., Kotenko I. Problematic issues of in-formation security of cyber-physical systems // SPIIRAS Proceedings. 2020. vol. 19. no. 5. pp. 1050–1088.
12. Coull S., Branch J., Szymanski B., Breimer E. Intrusion detection: A bioinformatics approach // In Proceedings Annual Computer Security Applications Conference, ACSAC. 2003. vol. 2003-January. pp. 24–33.
13. Lavrova D., Zaitceva E., Zegzhda P. Bio-inspired approach to self-regulation for industrial dynamic network infrastructure // CEUR Workshop Proceedings. 2019. vol. 2603. pp. 34–39.
14. Miller W. An Introduction to Bioinformatics Algorithms // Journal of the American Statistical Association. 2006. vol. 101. no. 474. pp. 855–855.
15. Sohn J. Il, Nam J.W. The present and future of de novo whole-genome assembly // Briefings in Bioinformatics. 2018. vol. 19, no. 1, pp. 23–40.
16. Recanati A., Brüls T., D’Aspremont A. A spectral algorithm for fast de novo layout of uncorrected long nanopore reads // Bioinformatics. 2017. vol. 33, no. 20. pp. 3188–3194.
17. Rizzi R., et al. Overlap graphs and de Bruijn graphs: data structures for de novo genome assembly in the big data era // Quantitative Biology. 2019. vol. 7, no. 4. pp. 278–292.
18. Wittler R. Alignment- And reference-free phylogenomics with colored de Bruijn graphs // Algorithms for Molecular Biology. 2020. vol. 15. no. 1.
19. Tan T.W., Lee E. Sequence Alignment // Beginners Guide to Bioinformatics for High Throughput Sequencing. 2018. pp. 81–115.
20. Muhamad F.N., Ahmad R.B., Asi S.M., Murad M.N. Performance Analysis of Needleman-Wunsch Algorithm (Global) and Smith-Waterman Algorithm (Lo-cal) in Reducing Search Space and Time for DNA Sequence Alignment // Journal of Physics: Conference Series. 2018. vol. 1019. no. 1.
21. Lee Y.S., Kim Y.S., Uy R.L. Serial and parallel implementation of Needleman-Wunsch algorithm // International Journal of Advances in Intelligent Informatics. 2020. vol. 6. no. 1. pp. 97–108.
22. Čavojský M., Drozda M., Balogh Z. Analysis and experimental evaluation of the Needleman-Wunsch algorithm for trajectory comparison // Expert Systems with Applications. 2021. vol. 165.
23. Sun J., Chen K., Hao Z. Pairwise alignment for very long nucleic acid sequences // Biochemical and Biophysical Research Communications. 2018. vol. 502. no. 3. pp. 313–317.
24. Zou H., Tang S., Yu C., Fu H., Li Y., Tang W. ASW: Accelerating Smith–Waterman Algorithm on Coupled CPU-GPU Architecture // International Journal of Parallel Programming. 2019. vol. 47. no. 3. pp. 388–402.
25. Chowdhury B., Garai G. A review on multiple sequence alignment from the perspective of genetic algorithm // Genomics. 2017. vol. 109. no. 5–6. pp. 419–431.
26. Dijkstra M.J.J., Van Der Ploeg A.J., Feenstra K. A., Fokkink W.J., Abeln S., Heringa J. Tailor-made multiple sequence alignments using the PRALINE 2 alignment toolkit // Bioinformatics. 2019. vol. 35. no. 24. pp. 5315–5317.
27. Chen S., Yang S., Zhou M., Burd R., Marsic I. Process-Oriented Iterative Multiple Alignment for Medical Process Mining // In IEEE International Conference on Data Mining Workshops, ICDMW. 2017. vol. 2017-November. pp. 438–445.
28. Ye N. Markov Chain Models and Hidden Markov Models // Data Mining. 2021. pp. 287–305.
29. Behera N., Jeevitesh M.S., Jose J., Kant K., Dey A., Mazher J. Higher accuracy protein multiple sequence alignments by genetic algorithm // Procedia Comput-er Science. 2017. vol. 108. pp. 1135–1144.
30. Cui X., Shi H., Zhao J., Ge Y., Yin Y., Zhao K. High Accuracy Short Reads Alignment Using Multiple Hash Index Tables on FPGA Platform // In Proceed-ings of 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference, ITOEC. 2020. pp. 567–573.
31. Marçais G., Delcher A.L., Phillippy A.M., Coston R., Salzberg S.L., Zimin A. MUMmer4: A fast and versatile genome alignment system // PLoS Computational Biology. 2018. vol. 14. no. 1. 2018.
32. Kay M. Substring alignment using suffix trees // Lecture Notes in Computer Science. 2004. vol. 2945. pp. 275–282.
33. Ukkonen E. On-line construction of suffix trees // Algorithmica. 1995. vol. 14. no. 3. pp. 249–260.
34. Breslauer D., Italiano G.F. On suffix extensions in suffix trees // Theoretical Computer Science. 2012. vol. 457. pp. 27–34.
35. KDD Cup 1999 Data: URL: kdd.ics.uci.edu/databases/kddcup99/kddcup99.html (дата доступа: 10.04.2021).
Опубликован
2021-08-13
Как цитировать
Зегжда, Д. П., Калинин, М. О., Крундышев, В. М., Лаврова, Д. С., Москвин, Д. А., & Павленко, Е. Ю. (2021). Применение алгоритмов биоинформатики для обнаружения мутирующих кибератак. Информатика и автоматизация, 20(4), 820-844. https://doi.org/10.15622/ia.20.4.3
Раздел
Информационная безопасность
Copyright (c) Максим Олегович Калинин
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).