Compactação do Algoritmo de Comparação de Strings do Snort para o uso na Memória Compartilhada de GPUs

José Bonifácio da Silva Júnior; Edward David Moreno; Ricardo Ferreira dos Santos

doi:10.5753/wscad.2017.237

José Bonifácio da Silva Júnior UFS
Edward David Moreno UFS
Ricardo Ferreira dos Santos UFV

DOI: https://doi.org/10.5753/wscad.2017.237

Resumo

A tarefa de comparar assinaturas de ataques com pacotes de redes em um Intrusion Detection System (IDS) consome bastante tempo de CPU. Para amenizar esse problema, tem-se tentado paralelizar o motor de comparação dos IDSs transferindo sua execução da CPU para a GPU. Este artigo mostra o processamento em paralelo dos dados no algoritmo de comparação de string Aho-Corasick e propõe compactar a Tabela de Transição de Estados desse algoritmo a fim de possibilitar o uso dele na memória compartilhada. A paralelização foi feita através da plataforma CUDA da NVIDIA e executada nas diversas memórias da GPU. O algoritmo AC foi compactado e executado na memória compartilhada, alcançando, em seu melhor resultado, um ganho de desempenho de 73% em relação às outras memórias da GPU e o algoritmo compactado chegou a ser 56 vezes mais rápido que sua versão serial. Com isso, pode-se perceber que o uso da compactação na memória compartilhada torna-se uma solução adequada para acelerar o processamento de IDSs que necessitem de agilidade na busca por padrões.

Referências

Aho, A.; Corasick, M. (1975). "Efficient string matching: an aid to bibliographic search", Communications of the ACM, v.18 n.6, p.333-340, June.

Bellekens, X. J. A.. et al. (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". ACM: SIN '14 Proceedings of the 7th International Conference on Security of Information and Networks. [s. L.], p. 302-310. September.

Cuda. "CUDA: Programación Paralela Facilitada". http://www.nvidia.com.br/object/cuda_home_new_br.html.

Jacob, N.; Brodley, C. (2006). "Offloading IDS Computation to the GPU". The 22nd Annual Computer Security Applications Conference, pp 371-380, December.

Jaiswal, M. (2014). "Accelerating Enhanced Boyer-Moore String Matching Algorithm on Multicore GPU for Network Security". International Journal of Computer Applications, Vol. 97 – No. 1, 2014. http://research.ijcaonline.org/volume97/number1/pxc3896934.pdf.

Kouzinopoulos, C. S.; Margaritis, K. G. (2008). "String Matching on a multicore GPU using CUDA". The 13th Panhellenic Conference on Informatics, pp 14-18, September.

Lee, C.; Lin, Y.; Chen, Y. (2015). "A Hybrid CPU/GPU Pattern-Matching Algorithm for Deep Packet Inspection". PLoS ONE 10(10): e0139301, October.

Lin, C. et al. (2013) "Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs". IEEE Transactions on Computers, Vol. 62, pp 1906-1916, October.

Lin, C. et al. (2010). "Accelerating String Matching Using Multi-threaded Algorithm on GPU". 2010 IEEE Global Telecommunications Conference (GLOBECOM 2010), pp 1-5, December.

Pungila, C. (2013). "Hybrid Compression of the Aho-CorasickAutomaton for Static Analysis in Intrusion Detection Systems". Springer. [s. L.], p. 1-10, January.

Pungila, C.; Negru, V. (2015). "Real-Time Hybrid Compression of Pattern Matching Automata for Heterogeneous Signature-Based Intrusion Detection". Springer Link. Berlim, p. 65-74, May.

Pungila, C.; Reja, M.; Negru, V. (2014). "Efficient parallel automata construction for hybrid resource-impelled data-matching". Future Generation Computer Systems, Vol. 36, pp 31-41, July.

Santos, B. R. (2005). "Detecção de Intrusos Utilizando o Snort". 83 f. Monografia (Especialização) - Curso de Pós-Graduação Latu Sensu em Administração de Rede Linux, Departamento de Computação, Universidade Federal de Lavras, http://www.ginux.ufla.br/files/mono-BrunoSantos.pdf, September.

Snort Team. (2015). "SNORT Users Manual 2.9.7: The Snort Project". 265 p, https://www.snort.org/documents, June.

Thambawita, D. R. V. L. B.; Ragel, R.; Elkaduwe, D. (2014). "To Use Or Not To Use: Graphics Processing Units (GPUs) For Pattern Matching Algorithms". The 7th International Conference on Information and Automation for Sustainability (ICIAfS), pp 1-4.

Tran, N.; Lee, M.; Hong, S.; Shin, M. (2012). "Memory Efficient Pararellelization for Aho-Corasick Algorithm on a GPU". The 14th International Conference on High Performance Computing and Communications, pp 432-438.

Villa, O.; Chavarría-miranda, D. G.; Tumeo, A. (2012). "Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures". IEEE Transactions on Parallel and Distributed Systems, Vol. 23, pp 436-443.