Dynamic Time Warping (DTW) (Keogh e Ratanamahatana, 2005) é uma téc- nica utilizada com sucesso para o alinhamento de série fora de fase. Essa técnica utiliza um algoritmo de programação dinâmica, semelhante ao da dis-
tância Levenshtein (ou Edit distance), entre duas séries de tamanho n e m, n ≤ m. Essa técnica foi utilizada com sucesso por Pereira e de Mello (2009) para a caracterização do comportamentos de processos no sistema UNIX. Para a caracterização de sistemas, geram-se diversas séries referentes a um de- terminado processamento: quanto maior o valor da DTW entre duas séries, maior é a dissimilaridade entre elas, o que pode ser utilizado para caracterizar uma anomalia.
A grande limitação dessa técnica é o fato do algoritmo ser de ordem O(n) em relação a consumo de memória, e O(nm) (i.e. quadrático) em relação a tempo de execução. De qualquer forma, esse algoritmo tem sucesso desde que o tamanho das séries seja limitado, e pode ser utilizado para fins de comparação com algoritmos on-line.
3.3 Considerações finais
Neste capítulo foram apresentados diversos conceitos úteis para a carac- terização do comportamento de aplicações. Diferentes ferramentas podem ter aplicabilidade e eficiência distintas dependendo do problema analisado, de forma que uma análise crítica dessas ferramentas é essencial para a tomada de qualquer decisão de projeto.
Diversos outros algoritmos incrementais voltados a agrupamento em fluxos de dados são descritos na literatura (como por exemplo nos trabalhos de Ag- garwal et al. (2003) e Aggarwal et al. (2004)), e esses poderiam ser avaliados para a abordagem desse trabalho. Optou-se por não utilizar esses trabalhos nesta dissertação dado que, em primeiro lugar, seria inviável a análise de todos esses algoritmos, e em segundo lugar, o fato de que o objetivo deste trabalho é mostrar a viabilidade da abordagem mesmo sem a definição de algoritmos mais sofisticados.
CAPÍTULO
4
Abordagem proposta
O objetivo deste trabalho é projetar e avaliar um sistema autônomo de de- tecção de intrusões em aplicações Web, baseado em técnicas de aprendizado de máquina e computação bio-inspirada. Deseja-se que esse sistema atue de forma autônoma, i.e., que seja capaz de caracterizar intrusões sem o uso de assinaturas de ataques, ou seja, por meio de anomalias observadas durante o seu funcionamento. Avalia-se inicialmente a hipótese de que técnicas de agru- pamento são capazes de gerar séries temporais que caracterizam o comporta- mento normal de um sistema e de distingui-lo de comportamentos anômalos observados em situações de ataque. Neste capítulo são caracterizadas tanto a abordagem proposta, quanto a metodologia utilizada para sua avaliação.
4.1 Caracterização da abordagem proposta
O projeto de sistema de detecção de intrusão baseado em anomalias de- manda a caracterização de aspectos relevantes do sistema em estudo. Por exemplo, em trabalhos anteriores (Twycross, 2007; Forrest et al., 1996), onde se buscavam intrusões em serviços de rede, a sequência de chamadas de sis- tema é definida como o principal aspecto a ser observado, dado que ataques alteram seu comportamento. Por outro lado, essa caracterização não é válida para aplicações Web, uma vez que o comportamento de um servidor HTTP em situações de injeção de código não tende a diferir de situações normais. O que pode ser observado, nesse contexto, são as mensagens trocadas entre cliente e servidor, os valores de variáveis da aplicação, além das sequências de coman- dos executados pelos sistemas legados (tais como Sistemas de Gerenciamento de Banco de Dados – SGBD ou serviços de diretório como Lightweight Directory
Access Protocol – LDAP).
Seja qual for o aspecto observado, a abordagem proposta neste trabalho aplica um processo de discretização (que pode ser visto como uma função na forma f : Objeto → N) a fim de reduzir a dimensionalidade dos dados, ou para caracterizar um aspecto pouco estruturado da aplicação (como registros em log de aplicações, ou mensagens trocadas pela rede). Para essa tarefa são utilizadas técnicas de agrupamento de dados, que recebem como entrada ele- mentos observados no sistema (e.g. comandos executados nos SGBD’s ou valores de variáveis) e geram como saída um identificador de grupo ao qual esse elemento pertence. Dessa forma, esse procedimento gera uma série tem- poral composta por identificadores de grupo. Essa série é então analisada em busca de anomalias, que possam representar um comportamento de in- trusão. Essa abordagem é apresentada na Figura 4.1 (as setas tracejadas entre os componentes representam dependências).
Comportamento Monitorado da
Aplicação
Agrupamento
de Dados Detecção deNovidades a) Extração de comportamento
e representação dos dados e geração da série temporalb) Agrupamento de dados
c) Processamento da série e emissão de alertas Modelo de Dados Algoritmo de Agrupamento Função de Distância Função Mescla de Objetos (opcional) Algoritmo de Detecção Objetos pouco
estruturados Sequência de identificadores (série temporal)
Figura 4.1: Proposta para caracterização de comportamento e detecção de novidades.
A abordagem proposta neste trabalho divide o problema em três etapas, conforme a Figura 4.1. Para aplicar essa abordagem, é necessário: a) extrair e representar um aspecto do funcionamento de um sistema (e.g. chamadas de sistema executadas por um processo, consumo de memória e processamento, mensagens de log ou tráfego de rede) por meio de um modelo de dados; b) definir uma função de distância entre objetos e, em alguns casos, uma função de mescla de diversos objetos como uma única observação, além de um al- goritmo de agrupamento que recebe as saídas do sistema e gera uma série temporal que representa o comportamento da aplicação; c) aplicar um algo-
ritmo de detecção de novidades sobre a série gerada em busca de alterações no comportamento do sistema.