Brasileiro desenvolve novo algoritmo de pattern-matching super eficiente

Apesar da falta de investimento em pesquisa e desenvolvimento em tecnologias relacionadas à Segurança da Informação, existem alguns brasileiros que se destacam inovando em uma área praticamente dominada por chineses, israelenses, indianos e americanos.

Um destes brazucas é Breno Silva, que criou um algoritmo de pattern-matching que está sendo super bem recebido pela comunidade internacional.

Breno estará apresentando seu algoritimo na apresentação "Protecting smart-grid with BRENO-SILVA single pattern match algorithm for small patterns" evento IEEE Machine Learning and Cybernetics que aconterá na China em Julho.

Seguem algumas informações passadas pelo Breno sobre o assunto em uma rápida entrevista (as perguntas foram removidas para uma maior clareza e coesão do texto):

Vou estar publicando meu algoritmo single pattern match. O algoritmo foi criado pensando no projeto Suricata e ainda está no meu TODO colocá-lo funcionando dentro desse IPS.

O algoritmo tem se mostrado o mais eficiente atualmente para busca de patterns pequenas em super-alfabetos. O que é um problema ainda não muito bem resolvido para IDS/IPS e outras aplicações que fazem busca de patterns em rede IP. O algoritmo tem uma melhora na complexidade em pior e médio caso usando técnicas de skip e hashing para fazer a busca de patterns.

Basicamente o algoritmo foi projetado para ser eficiente na busca de pequenas patterns em super-alfabetos. Pattern pequenas sempre foram performance killers nesse tipo de aplicação e ainda se utilizavam algoritmos mais classicos para resolver esse problema.

Nenhum dos algoritmos comumente utilizados (Knuth-Morris-Pratt, Shift-And, Shift-Or, Boyer-Moore, Boyer-Moore-H) conseguiram ser mais rápidos. Também testei recentemente com um novo algoritmo publicado esse ano por um grupo de pesquisadores da Finlândia (SBNDMq) e um novo algoritmo que ainda será lançado pelo francês Thierry Lecroq (EBOM). Nenhum deles foi mais eficiente. O algoritmo criado foi pelo menos 50% mais eficiente nesses casos dos que os comparados.

O algoritmo se torna mais eficiente com o aumento do alfabeto. Pode ser uma boa opção para ferramentas de forense de rede e até mesmo para análise de logs.

Outro uso do algoritmo será possível em alguns anos - quando redes smart-grid forem uma realidade - e que provavelmente terão que trafegar um volume muito grande de dados, talvez haja necessidade de trabalhar com algoritmos mais eficientes daqueles que temos hoje em dia.

Um artigo científico que explica o funcionamento do algoritmo bem como testes comparativos com outros algoritmos comumente utilizados para essas tarefas será publicado em julho desse ano na International Conference on Machine Learning and Cybernetics (ICMLC) - China e depois disponível via ieeexplore.

Ainda não apresentei esse trabalho publicamente no Brasil, mas algumas pessoas do meio acadêmico estão interessadas em levar aos alunos. Particularmente eu espero bastante ter o apoio de pesquisadores para trabalhar em uma "versão" multi-pattern matching do mesmo algoritmo.