Detecção de Padrões - Departamento de Engenharia ...paf/proj/Set2002/Sistemas Deteccao Intrusoes.pdf · 1.1.1 Definição ... 1 O Snort é um produto opensource de utilização

Instituto Superior de Engenharia do Porto

Licenciatura de Engenharia Informática

Sistemas de Detecção de Intrusões

Detecção de Padrões

Autor

José Carlos Sousa nº940549 Agosto 2002

IDSs: Detecção de Padrões Índice

José Carlos Sousa 940549 (ISEP 2002) Pág. 2

Índice

Resumo..................................................................................................................................5

1 Introdução ........................................................................................................................6

1.1 Sistemas de Detecção de Intrusões..........................................................................6

1.1.1 Definição ..............................................................................................................6

1.1.2 Evolução ..............................................................................................................8

1.1.3 Classificação......................................................................................................12

1.1.3.1 Baseados na Rede ......................................................................................12

1.1.3.2 Baseados no Host .......................................................................................15

1.1.3.3 Híbridos........................................................................................................19

1.1.4 Respostas ..........................................................................................................21

1.1.4.1 Alarmes........................................................................................................21

1.1.4.2 Session Sniping ...........................................................................................22

1.1.4.3 Actualizações da Firewall ............................................................................23

1.2 Métodos de Detecção..............................................................................................24

1.2.1 Detecção de Padrões ........................................................................................24

1.2.2 Detecção de Padrões que mantém o estado ....................................................25

1.2.3 Análise de Protocolo..........................................................................................26

1.2.4 Análise Heurística..............................................................................................27

1.2.5 Análise das Anomalias ......................................................................................28

2 Técnicas de Detecção de Padrões................................................................................29

2.1 Definição ..................................................................................................................29

2.2 Evolução ..................................................................................................................31

2.3 Algoritmos ................................................................................................................32

2.3.1 Força Bruta ........................................................................................................33

2.3.2 Boyer-Moore ......................................................................................................37

2.3.3 Horspool.............................................................................................................41

2.3.4 Aho-Corassick....................................................................................................44

3 Detecção de Padrões nos IDSs.....................................................................................46

3.1 Definição ..................................................................................................................46



3.2 Snort.........................................................................................................................47

3.2.1 Modo de Operação ............................................................................................47

3.2.1.1 Regras .........................................................................................................47

3.2.1.2 Motor de Pesquisa.......................................................................................49

3.2.1.3 Algoritmo Utilizado.......................................................................................50

3.2.2 Desempenho......................................................................................................51

3.2.2.1 Perfil.............................................................................................................51

3.2.2.2 Ataques........................................................................................................51

3.3 Novos Algoritmos.....................................................................................................53

3.3.1 AC_BM...............................................................................................................54

3.3.1.1 Implementação ............................................................................................56

3.3.1.2 Limitações....................................................................................................58

3.3.1.3 Desempenho ...............................................................................................58

3.3.2 SBMH.................................................................................................................61

3.3.2.1 Implementação ............................................................................................61

3.3.2.2 Limitações....................................................................................................61

3.3.2.3 Desempenho ...............................................................................................62

4 Conclusão ......................................................................................................................64

Referências Bibliográficas ...................................................................................................66

Anexos .................................................................................................................................70

Anexo A: Terminologia......................................................................................................70

Anexo B: Código dos Algoritmos......................................................................................73

Índice de Figuras Fig. 1 : Evolução dos IDSs ..................................................................................................10

Fig. 2 : Utilização dos IDSs..................................................................................................11

Fig. 3 : Evolução da Utilização dos IDSs.............................................................................11

Fig. 4 : Exemplo do Algoritmo Força Bruta..........................................................................36

Fig. 5 : Good Sufix Shift (opção 1).......................................................................................38

Fig. 6 : Good Sufix Shift (opção 2).......................................................................................38

Fig. 7 : Bad Character Shift (opção 1) .................................................................................38

Fig. 8 : Bad Character Shift (opção 2) .................................................................................38



Fig. 9 : Exemplo Algoritmo Boyer-Moore.............................................................................40

Fig. 10 : Exemplo do Algoritmo de Horspool .......................................................................43

Fig. 11 : Árvore de padrões de Aho-Corasick .....................................................................45

Fig. 12 : Exemplo de Regras Snort......................................................................................48

Fig. 13 : Exemplo de RTN ...................................................................................................49

Fig. 14 : Exemplo de OTN ...................................................................................................50

Fig. 15 : Exemplo de Padrões Semelhantes .......................................................................55

Fig. 16 : Árvore de Palavras de AC_BM..............................................................................55

Fig. 17 : Bad Character Shift de AC_BM.............................................................................56

Fig. 18 : Good Prefix Shift de AC_BM .................................................................................57

Fig. 19 : Teste Desempenho AC_BM..................................................................................59

Fig. 20 : Teste Memória AC_BM .........................................................................................60

Índice de Tabelas Tabela 1 : Perfil de desempenho do Snort .........................................................................51

Tabela 2 : Desempenho em sobrecarga do Snort .............................................................52

Tabela 3 : Tempo de Procura para Pior Tempo.................................................................62

IDSs: Detecção de Padrões Resumo


Resumo

A segurança é um factor de extrema importância para os sistemas informáticos. A

sensibilidade da informação e a sua exposição prolongada ao meio, fez crescer o receio

de espionagem, deterioração, indisponibilidade ou roubo da mesma. Assim, pretende-se

contribuir para um melhor esclarecimento de alguns dos aspectos que envolvem a

segurança dos referidos sistemas, nomeadamente, os Sistemas de Detecção de Intrusões

(IDSs: Intrusion Detection Systems), e mais concretamente, as técnicas de detecção de

padrões que usam.

Este estudo está dividido em quarto capítulos: Introdução; Técnicas de Detecção de

Padrões; Detecção de Padrões nos IDSs e respectiva Conclusão. Existe ainda uma

secção de referências bibliográficas e uma outra que contem anexos.

Na Introdução, são apresentados os IDSs, salientando os seus benefícios num sistema

computacional. Importa ainda realçar a exposição dos diferentes métodos de detecção,

onde se podem usar técnicas de detecção de padrões. Nas Técnicas de Detecção de

Padrões, após uma breve introdução, é demonstrado o modo de operar dos algoritmos

mais relevantes para este estudo. Assim, serão apresentados os seguintes algoritmos:

Força Bruta, Boyer-Moore, Horspool e Aho-Corasick.

A secção Detecção de Padrões nos IDSs mostra a integração e a importância das

técnicas de detecção de padrões nos IDSs. Assim, é usado o Snort1 possibilitando a

comparação do desempenho dos diferentes algoritmos envolvidos. No fim do capítulo,

são apresentados os algoritmos AC_BM e SBMH, que melhoram o desempenho da

detecção de padrões. Quanto à conclusão, são expostas todas as ilações, que dizem

respeito a detecção de padrões utilizados nos IDSs, focando o seu desempenho.

1 O Snort é um produto opensource de utilização gratuita na área dos NIDSs (www.snort.org)

IDSs: Detecção de Padrões Introdução : Sistemas de Detecção de Intrusões


1 Introdução

Nesta secção pretende-se mostrar o universo dos Sistemas de Detecção de Intrusões

(IDSs: Intrusion Detection Systems) e da importância destes na segurança global dos

actuais sistemas informáticos.

Inicialmente, é apresentada uma definição dos IDSs fazendo referência à sua importância

relativamente a outros dispositivos de segurança. Em seguida, são analisadas as diversas

classificações possíveis destes sistemas, bem como as respectivas vantagens e

desvantagens, sendo ainda indicados os vários tipos de resposta que estes sistemas

podem gerar. A secção termina com a exploração dos métodos de detecção usados pelos

IDSs, onde estão incluídas técnicas de detecção de padrões.

1.1 Sistemas de Detecção de Intrusões

1.1.1 Definição

Os Sistemas de Detecção de Intrusões (IDSs) são sistemas responsáveis pela

monitorização de Sistemas informáticos de forma a detectar actividades ilícitas,

desencadeando um conjunto de respostas.

A abertura das redes privadas das organizações através da disponibilidade de um variado

conjunto de serviços tem vindo, desafortunadamente, a contribuir para aumentar o uso

ilegítimo desses serviços com determinados propósitos de natureza criminosa, que

podem ir desde a obtenção de informação confidencial até à destruição integral dos

sistemas informáticos.

Várias medidas podem ser tomadas a fim de reduzir o risco, tais como: criptografia, redes

privadas virtuais (VPN: Virtual Private Network), políticas de segurança ou dispositivos de

filtragem de tráfego, normalmente designados por firewalls. Uma firewall é configurada

com um conjunto de regras bem estabelecidas que bloqueiam o acesso a determinados

endereços e portas (também fazem de gateway de circuitos e de aplicações), de forma a



limitar o conjunto de serviços disponíveis a partir do exterior da organização. Ainda assim,

é possível explorar vulnerabilidades das aplicações ou serviços com o objectivo de

desencadear intrusões.

Os IDSs foram desenvolvidos para colmatar algumas das limitações da firewall tais como:

não detectar ataques no interior da rede (indicado como ponto de ataque por 33% dos

entrevistados[1]), não analisar os conteúdos das unidades de tráfego, não registar as

tentativas de ataque e não manter o estado.

Analogamente as firewalls podem ser comparadas com as fechaduras e os IDSs com os

alarmes. A instalação de portas e janelas nos edifícios ajuda a manter os intrusos

afastados. No entanto, existe sempre a possibilidade de certos procedimentos de

segurança poderem ser negligenciados, tais como deixarem uma porta aberta ou mal

fechada. Depois de penetrar no edifício, o intruso pode destruir ou roubar, ou pode fazer

cópias das chaves e voltar mais tarde. Se forem instalados alarmes nos edifícios, a

activação desses alarmes pode fazer desencadear a fuga do intruso não lhe dando tempo

necessário para provocar estragos. Além disso, conhecendo a natureza da intrusão mais

facilmente se recupera dos danos provocados e se corrigem as falhas de segurança do

edifício.



1.1.2 Evolução

O principal objectivo dos IDSs é fazer a monitorização dos sistemas informáticos de modo

a detectar comportamentos anormais ou usos indevidos. Estes sistemas remontam a

aproximadamente vinte anos, mas apenas recentemente tiveram um crescimento em

popularidade e na sua aceitação como participantes activos na segurança de um sistema

computacional.

Em 1980, James Anderson observou que os registos dos sistemas continham informação

vital para detectarem os usos indevidos e compreender os comportamentos dos

utilizadores em “Computer Security Threat Monitoring and Surveillance”[2]. Assim, surgiu

o conceito de detecção de usos indevidos e eventos específicos do utilizador, levando a

uma melhoria muito significativa nos subsistemas de auditoria de praticamente todos os

sistemas operativos existentes. Esta conjectura está na origem das fundações da

concepção e desenvolvimento dos IDSs. O seu trabalho foi o início dos IDSs baseados no

host (HIDSs) e dos IDSs em geral.

Em 1983, Dorothy Denning, da SRI International, participou num projecto que originou um

significativo avanço no desenvolvimento dos IDSs. O seu objectivo era analisar os

registos dos mainframes do governo e criar perfis de utilizadores segundo as suas

actividades. Um ano depois, Denning colaborou no desenvolvimento do primeiro sistema

de detecção de intrusões, o Intrusion Detection Expert System (IDES)[3].

Em 1984, a SRI Internacional desenvolveu os meios para analisar os registos que

continham informação da autenticação dos utilizadores da ARPANET (a Internet original).

Estes meios estiveram na origem do primeiro IDS funcional (IDES).

Em 1987, Denning, utilizando a sua experiência em investigação e desenvolvimento de

IDSs, publicou o artigo, “An Intrusion Detection Model”[4] que serviu de base para futuros

desenvolvimentos.

Entretanto, em 1988, avanços significativos foram introduzidos pelo projecto Haystack[5].

Este projecto consistiu no desenvolvimento de um IDS chamado Distributed Intrusion



Detection System (DIDS)[6], introduzindo técnicas de detecção de padrões. Estas

técnicas consistiam na comparação dos dados existentes nos registos produzidos pelo

sistema com padrões definidos. Para além de monitorizar os servidores, também

monitorizava os clientes.

Em 1989, os investigadores do projecto Haystack formaram uma empresa comercial

chamada Haystack Labs e lançaram a última geração da tecnologia Stalker. Esta

tecnologia era um IDS baseado no host (HIDS) com um sistema de detecção de padrões,

que incluía capacidades robustas de busca manual ou automática através de

interrogações aos registos dos sistemas. A tecnologia Stalker juntamente com os

trabalhos da SRI e de Demming, constituíram um grande avanço na tecnologia dos IDSs

baseados no host (HIDSs).

No início dos anos 90, Tood Heberlein introduziu a ideia de Network Intrusion Detection

Systems (NIDSs)[7]. Em 1990, Heberlein foi o principal autor do Network Security Monitor

(NSM), o primeiro NIDS que foi implementado nas mais importantes organizações

governamentais, onde a análise do tráfego da rede gerava uma quantidade maciça de

informação. Este sistema contribuiu para o aumento do interesse na área da detecção de

intrusões e os investimentos neste tipo de produto aumentou significativamente. A

contribuição de Heberlein estendeu-se ao projecto DIDS onde, conjuntamente com a

equipa da Haystack, introduziram os sistemas de detecção de intrusões híbridos

(HIDSs/NIDSs).

Os vários IDSs comerciais surgiram no início dos anos 90. A Haystack Labs foi a primeira

a comercializar este tipo de ferramentas IDSs, com a sua linha Stalker baseada no host. A

SAIC também desenvolveu uma forma de detecção baseada no host chamada Computer

Misuse Detection System (CMDS)[8]. Simultaneamente, a Cryptologic Support Center

desenvolveu o Automated Security Measurement System (ASIM) para monitorar o tráfego

dos sistemas informáticos da força aérea dos EUA[9]. O ASIM trouxe enormes progressos

para os problemas de escalonamento e portabilidade dos anteriores produtos NIDSs.

Adicionalmente, a ASIM foi a primeira empresa a incorporar hardware e software na

mesma solução de IDSs. Além disso este sistema ainda está actualmente em uso pelo

Computer Emergency Response Team (CERT)[10] da força aérea americana, um pouco



por todo o mundo. O grupo de desenvolvimento do projecto ASIM formou uma empresa

comercial em 1994 com o nome de Wheel Group. O seu produto, designado por

NetRanger, foi o primeiro NIDS comercialmente viável.

O mercado de produtos na área da detecção de intrusões só começou a ganhar

popularidade em meados de 1997. Nesse ano, o líder de mercado em produtos da área

de segurança era a Internet Security Systems (ISS). Esse sucesso foi alcançado devido à

sua solução de NIDSs designada por RealSecure. Um ano depois, a Cisco adquiriu a

Wheel Group de modo a conseguir competir com a ISS. Outra empresa com uma solução

HIDSs com bastante sucesso foi a Centrax Corporation constituída por investigadores da

Haystack Labs e do CMDS da SAIC. A partir daqui, os IDSs expandiram os seus

horizontes originando um conjunto de novas empresas, resultantes de fusões e

aquisições.

Fig. 1 : Evolução dos IDSs

Actualmente, estatísticas na área de segurança[1] mostram os IDSs como um dos

dispositivos mais utilizados. Estes ocupam a quinta posição (60%), logo abaixo do

software antivírus (90%), firewall (89%), segurança física (84%) e controlo de acesso

(82%). Relativamente a 1998, obtiveram um crescimento na sua utilização de 25%, o que

corresponde ao maior crescimento verificado (ver gráficos).



60%

82%

84%

89%

90%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

Antivírus

Firewall

Segurança Física

Controlo de Acesso

IDSs

Utilização das Tecnologias de Segurança

Fig. 2 : Utilização dos IDSs

35%60%

89%82%

89%84%

81%89%

96%90%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

Antivírus

Firewall

Segurança Física

Controlo de Acesso

IDSs

Evolução da Utilização das Tecnologias de Segurança

19982002

Fig. 3 : Evolução da Utilização dos IDSs



1.1.3 Classificação

Actualmente, os IDSs podem ser classificados em:

• Baseados na Rede (NIDSs: Network Intrusion Detection Systems);

• Baseados no host (HIDSs: Host Intrusion Detection Systems);

• Baseados nos (NNIDSs: Network Node Intrusion Detection Systems).

Por sua vez, os HIDSs podem ser classificados em:

• Tradicionais;

• Avaliadores da Integridade dos Ficheiros (FIA: File Integrity Assessment);

• Sistemas de Prevenção a Intrusões (IPSs: Intrusion Prevention Systems).

Em seguida, serão detalhados estes tipos de sistemas, apresentando as vantagens e

desvantagens de cada um.

1.1.3.1 Baseados na Rede

Os IDSs baseados na rede (NIDSs) monitorizam o tráfego desta em tempo real ou em

intervalos de tempo (batch), examinando as unidades de tráfego de modo a detectar

padrões de uso indevido.

Essencialmente, existem sistemas baseados em assinaturas que comparam várias

unidades de tráfego com uma assinatura de ataque correspondente ou sistemas que

analisam o protocolo a fim detectar anomalias. Existem também abordagens híbridas. As

bases de dados de assinaturas são actualizadas de forma regular à medida que novos

ataques são descobertos. Em alguns casos, as assinaturas podem ser manualmente

adicionadas a essas bases de dados.

Quando actividade suspeita é detectada, os IDSs baseados na rede são capazes de gerar

alarmes e, simultaneamente, terminar a conexão que originou esse alarme (alguns HIDSs



também o conseguem fazer). Alguns NIDSs podem ser integrados com a firewall que, em

caso de ataque, podem definir novas regras e bloquear futuros ataques2.

A maioria dos NIDSs actuais trabalham em modo promíscuo. Isto significa que analisam

todas as unidades de tráfego que passam no seu segmento. É desejável que sejam

máquinas dedicadas e com bastantes recursos, devido à necessidade de manterem o

estado sobre todas as sessões activas (muitos ataques não estão contidos em apenas

uma unidade de tráfego).

De seguida apresenta-se as vantagens mais importantes dos NIDSs:

• Custo de Propriedade;

• Análise das Unidades de Tráfego;

• Remoção de Evidências;

• Detecção e Resposta em Tempo Real;

• Detecção de Más Intenções;

• Complemento e Verificação;

• Independência do Sistema Operativo.

Custo de Propriedade Os NIDSs podem ser colocados estrategicamente em pontos críticos de modo a

controlarem um número elevado de sistemas a serem protegidos, não necessitando assim

que software de HIDSs seja instalado e gerido em todas as máquinas.

Análise das Unidades de Tráfego Os NIDSs examinam todos os cabeçalhos das unidades de tráfego à procura de sinais de

ataque ou suspeita de ataque. Muitos dos ataques do tipo Denial of Service (DoS)

baseados no TCP/IP, são detectados desta forma. Por exemplo, o Land, consiste num

pacote forjado com o mesmo endereço IP e porta de origem iguais ao endereço e porta

de destino. O pacote forjado faz com que seja aberta uma conexão com a própria

máquina e está irá operar lentamente ou ficar indisponível. Este tipo de ataque pode ser

2 deve-se ter cuidado com este tipo de configuração, pois o atacante ao usar endereços de IP falsos (IP

spoffing) e conhecidos, pode usar esta funcionalidade contra a própria empresa.



facilmente detectado pelos NIDSs. Importa ainda referir que os ataques que usam

unidades de tráfego fragmentadas como o TearDrop podem ser detectados através da

análise dos cabeçalhos.

Alguns NIDSs também analisam o conteúdo das unidades de tráfego à procura de

sequências de bytes que correspondem a assinaturas de ataques. Algumas dessas

assinaturas descrevem comandos que desencadeiam um ataque. Por exemplo, um

intruso à procura de um novo exploit do BackOrifice em sistemas que não estejam

infectados por esse programa, pode ser detectado ao examinar-se o conteúdo da unidade

de tráfego.

Remoção de Evidências Alguns NIDSs detectam ataques em tempo real e, assim, um intruso não tem a

oportunidade de remover as evidências no momento em que o ataque é detectado. Os

dados capturados não mostram apenas o tipo de ataque, por vezes é possível a

identificação do intruso. Um dos problemas dos HIDSs é que muitas das vezes os intrusos

conseguem sabotar os registos dos sistemas.

Detecção e Resposta em Tempo Real Os NIDSs detectam ataques, ou suspeitas de ataques, à medida que eles ocorrem em

tempo real e vão produzindo respostas rápidas. Por exemplo, um intruso faz uma tentativa

de ataque usando o protocolo TCP, este ataque pode ser imediatamente bloqueado se o

IDSs enviar um TCP reset em ambas as direcções. Este procedimento faz com que seja

finalizada a conexão entre o host do intruso e o host que estava a ser alvo de ataque.

Nos HIDSs, quando o ataque é identificado através dos registos, pode já ser tarde de

mais.

Detecção de Más Intenções Os NIDSs podem ser extremamente valiosos a detectar más intenções. Se o sistema está

posicionado da parte de fora da firewall, pode detectar ataques direccionados à zona

interior da rede ou à própria firewall (mesmo que esta os bloqueie). Isto é útil para

detectar mais rapidamente um ataque, prevenir falhas na configuração da firewall e de



fornecer informação sobre todos os ataques dirigidos ao sistema informático. Os HIDSs

não têm conhecimento dos ataques bloqueados pela firewall.

Complemento e Verificação Os NIDSs complementam outros componentes da segurança do sistema informático. Se

for utilizada a encriptação das unidades de tráfego, os NIDSs não analisam as partes

encriptadas, mas verificaram se o tráfego que chega está encriptado. Na firewall, os

NIDSs podem verificar se devem permitir certo tipo de tráfego ou endereços.

Independência do Sistema Operativo Os NIDSs não são dependentes do sistema operativo para a detecção, como acontece

nos HIDSs. O formato da informação do registo varia de sistema para sistema e faz com

que os HIDSs necessitem que este funcione correctamente e não comprometa a

detecção.

1.1.3.2 Baseados no Host

Os HIDSs tiveram um decréscimo de interesse com o surgimento dos NIDSs, mas estão a

ressurgir devido a novas potencialidades adquiridas. Como já foi referido, os HIDSs

podem ser divididos em: HIDSs Tradicionais, Avaliadores da Integridade dos Ficheiros

(FIA) e Sistemas de Prevenção a Intrusões (IPSs). Em seguida serão detalhados cada um

deles.

HIDSs Tradicionais Os HIDSs tradicionais empregam um agente que reside em cada host a ser monitorizado.

O agente escrutina: os eventos e registos do sistema, os registos do kernel, os ficheiros

críticos e outras fontes de informação. O objectivo é procurar alterações não autorizadas

ou actividades constituindo padrões suspeitos. Quando algo de anormal é detectado são

accionados automaticamente alertas ou SNMP traps.

Por exemplo, podem monitorizar o registry do Windows procurando determinados

acessos, os registos do kernel de modo a detectar quando são iniciados determinados



processos, ou os registos de início de sessão dos utilizadores podem ser usados para

detectar tentativas de acesso com palavras-chaves incorrectas. Quando essas tentativas

são demasiadas para um curto espaço de tempo, o sistema conclui que estão a obter

acesso ilegal e um alarme é gerado.

Os HIDSs Tradicionais são mais eficientes a detectar ameaças internas produzindo

avaliações extensivas dos danos e análise forense dos dados. Note-se que as ameaças

internas podem não ser de colaboradores da empresa, mas pessoas exteriores que ao

comprometer uma máquina a utilizem para lançar ataques do interior da rede. Podem ter

descoberto a palavra-chave de um utilizador autorizado ou explorado um exploit que

permite ter acesso à máquina, comprometendo todo o sistema.

Avaliadores da Integridade dos Ficheiros (FIA) Os produtos FIA monitorizam o estado do sistema, nomeadamente, os ficheiros das

aplicações críticas e os ficheiros do sistema operativo.

Inicialmente capturam o estado normal do sistema, sob a forma de cryptographic hashes

dos objectos a serem monitorizados. Quando este processo termina, é impossível

intrometer-se com os objectos originais ou com os valores de hash sem invalidar o

checksum dos ficheiros. Em intervalos regulares, os produtos FIA fazem novas

passagens, recalculando os valores de checksum e comparando-os com os valores

anteriormente guardados.

Por exemplo, se um intruso (ex. cavalo de Tróia) penetrar no sistema e mudar os ficheiros

chave, os FIA vão detectar e gerar um alarme. Além disso, permitem avaliar a extensão

dos dados provocados por um ataque bem sucedido e repor novamente a integridade do

sistema.

O seu lado negativo advém do facto da verificação dos ficheiros ser periódica e não em

tempo real. O principal ponto forte destes sistemas é a possibilidade da análise forense

depois de uma ataque ser perpetrado.



Sistemas de Prevenção a Intrusões (IPSs) A grande maioria dos sistemas baseados no host tendem a ser reactivos em vez de

serem proactivos: esperam que um ataque aconteça para accionar o alarme.

No entanto os IPSs, pretendendo ser proactivos, monitorizam e interceptam chamadas do

sistema ao Kernel ou às APIs de modo a prevenirem ataques e a gerarem registos

correctos. Podem ainda monitorizar o fluxo de dados e o ambiente específico de

determinada aplicação (ex. localização de ficheiros no servidor Web) de modo a protege-

la de ataques genéricos, para os quais ainda não existe uma assinatura.

A característica mais relevante dos IPSs (também conhecidos como Host Intrusion

Prevention ou HIP) é a capacidade de bloquearem as intrusões, em vez de simplesmente

as reportarem ou somente as detectar depois de terem ocorrido. É claro que

configurações incorrectas podem causar condições de Denial of Service (DoS), onde

clientes legítimos são impedidos de acederem aos recursos. Além disso, as actualizações

ao sistema operativo também podem ser problemáticas.

Em seguida são apresenta-se as vantagens mais importantes dos HIDSs:

• Verificação do Ataque;

• Actividade Especifica do Sistema;

• Ambientes Encriptados e Comutados;

• Monitorização de Componentes Chave;

• Detecção e Resposta quase em Tempo Real;

• Não é Necessário Hardware Adicional.

Verificação do Ataque Os HIDSs utilizam os registos do sistema e conseguem saber se um ataque teve sucesso.

Este tipo de detecção é mais exacta e é menos propensa a falsos alarmes. Pelo contrário,

os NIDSs geram falsos alarmes quando o tráfego maligno é idêntico ao tráfego normal,

tendo dificuldade em comprovar o sucesso de um ataque.



Actividade Especifica do Sistema Os HIDSs podem rapidamente monitorizar as actividades do acesso dos utilizadores e de

acesso aos ficheiros. Quando o procedimento de autenticação de um utilizador é

executado, o registo é actualizado e o HIDSs pode monitorizar, baseando-se numa

determinada política de segurança. Pode também monitorizar os vários acessos aos

ficheiros e notificar quando um ficheiro especifico é aberto ou fechado.

Este tipo de actividade não é efectuado pelos NIDSs, pois não geram tráfego na rede. Por

exemplo, alguém usa um teclado e abre um ficheiro sem partilha. Os HIDSs podem

monitorizar actividades que só podem ser efectuadas pelos administradores, como por

exemplo criar, alterar ou apagar uma conta.

Ambientes Encriptados e Comutados Como os HIDSs residem nos vários hosts podem ser colocados directamente nos

sistemas críticos. Nesta situação, um ambiente puramente comutado, não afecta a sua

função. Em contrapartida, os NIDSs tem problemas devido à separação do tráfego que

existe em cada segmento3.

Quanto à encriptação, esta não apresenta problemas para os HIDSs, porque detectam os

ataques a partir dos registos efectuados pelo sistema.

Monitorização de Componentes Chave Os HIDSs possibilitam a monitorização dos componentes importantes do sistema, como

executáveis críticos, DLLs específicas ou recursos do sistema. Todos eles podem ser

usados para quebrar a segurança e inutilizar o sistema informático.

Detecção e Resposta quase em Tempo Real Devido aos HIDSs se basearem na análise dos registos, a detecção não é efectuada em

tempo real, mas é efectuada imediatamente após o sistema registar uma assinatura

conhecida de um ataque.

3 Embora já existam soluções de comutadores com NIDSs incorporados ou Network Taps (Test Access

Port) para ultrapassar esses problemas.



Não é Necessário Hardware Adicional Os HIDSs não necessitam de hardware adicional para detectar intrusões e podem ser

instalados nos recursos já existentes na rede (Servidores de Ficheiros, Servidores Web,

ou noutros recursos críticos). Em certos casos, isto pode tornar os HIDSs numa solução

mais económica.

1.1.3.3 Híbridos

Os NNIDSs são sistemas híbridos porque possuem características dos NIDSs (analisam

as unidades de tráfego) e características dos HIDSs (residem nos hosts). Estes sistemas

vieram colmatar algumas das limitações dos NIDSs, porque apenas analisam as unidades

de tráfego destinadas ao respectivo host.

Devido à sua instalação (micro-agente) ser na stack dos protocolos do host, são por

vezes referidos como IDSs baseados na stack (Stack-based IDSs) e classificados como

HIDSs. Os NNIDSs permitem a monitorização do tráfego à medida que este vai

atravessando a stack dos protocolos. Isto permite a análise das unidades de tráfego antes

destas chegarem ao sistema operativo ou às aplicações, mas depois da referida stack as

ter desencriptado.

Em seguida apresenta-se as vantagens mais importantes dos NNIDSs (não incluindo as

comuns aos NIDSs):

• Geram pouco Overhead;

• Utilização em Redes Fortemente Comutadas;

• Utilização em Segmentos Sobrecarregados;

• Analisam Unidade de Tráfego Encriptadas.

Geram pouco Overhead O referido micro-agente encontra-se na stack dos protocolos do próprio host e só interfere

se detectar uma assinatura de ataque conhecida.



Utilização em Redes Fortemente Comutadas Os NNIDSs só processam as unidades de tráfego que se destinam ao seu host e

portanto, não são afectados pela separação do tráfego originada pelos comutadores.

Utilização em Segmentos Sobrecarregados Como os NNIDSs residem no próprio host, a sobrecarga do seu segmento de rede não

apresenta problemas ao nível do seu desempenho.

Analisam Unidades de Tráfego Encriptadas A localização dos NNIDSs na stack dos protocolos, permite analisar as unidades de

tráfego enquanto vão sendo desencriptadas.



1.1.4 Respostas

Os IDSs quando detectam uma assinatura referente a um ataque, geram um alarme e

registam a ocorrência, isto é, fornecem uma resposta. Neste caso, trata-se de uma

resposta passiva, porque apenas informam mas não executam acções correctivas. Essas

acções são efectuadas por utilizadores responsáveis pelo tratamento dos alarmes.

Este tratamento manual dos alarmes pode originar que os ataques em curso não sejam

bloqueados em tempo útil. As causas para que isso aconteça, podem ser: falta de tempo

para o tratamento imediato, execução de acções correctivas inadequadas, demasiados

alarmes que dificultam a correcta triagem, menosprezar determinado alarme, etc.

Para acautelar estas situações, alguns IDSs têm capacidade de fornecerem respostas

activas, isto é, não só fornecem a informação como tomam as devidas acções correctivas

de modo a bloquearem um ataque e a evitarem a sua repetição. Algumas dessas acções

são: desactivar uma conta, terminar imediatamente a sessão de um utilizador, retirar ao

host o acesso à rede e, principalmente, session sniping e actualizações da firewall.

Em seguida, serão detalhados os alarmes como respostas passivas e, a session sniping e

a actualização da firewall, como respostas activas.

1.1.4.1 Alarmes

Os alarmes são respostas passivas geradas pelos IDSs e são classificados como:

• Alarmes Verdadeiros;

• Falsos Alarmes;

• Falsos Negativos.

Alarmes Verdadeiros Estes alarmes são gerados pelos IDSs e realmente correspondem à ocorrência de um

ataque.



Falsos Alarmes

Os falsos alarmes (false alarms/false positives) ocorrem quando os IDSs geram um

alarme, mas não existe nenhum ataque. Quando são gerados em grandes quantidades

podem originar:

• Perdas de tempo desnecessário;

• Ocultação de alarmes importantes de ataques;

• Descrédito nos IDSs.

Falsos Negativos

Os alarmes considerados falsos negativos (false negatives) ocorrem quando existe um

ataque e os IDSs não geram o respectivo alarme. Algumas das causas para que esta

situação se verifique são:

• Método de identificar assinaturas deficiente;

• Não consegue manter o estado das sessões em certas condições;

• Não analisa todos as unidades de tráfego, quando há sobrecarga;

• Não têm uma assinatura definida para o tipo de ataque;

• Não usa meios suficientes para detectar novos ataques;

1.1.4.2 Session Sniping

Este tipo de resposta activa não necessita de drivers para os dispositivos exteriores e é

de instalação simples. Quando é detectado um ataque, os IDSs enviam um pacote forjado

com a flag RESET dos pacotes TCP activa, para as duas terminações da ligação. Ambas

as stacks vão interpretar a referida flag como um pedido para terminarem as

comunicações, o que vai originar que os buffers sejam esvaziados e não permitam o

exploit concluir com sucesso. A sua eficácia pode ser contornada se:

• O exploit não necessita de uma sessão interactiva pode activar a flag PUSH nos

pacotes TCP;

• O tempo que os IDSs demoram a enviar o pacote de TCP com a flag RESET

activa, pode ser usado para fazer com que esses pacotes sejam ignorados.



1.1.4.3 Actualizações da Firewall

Este tipo de resposta activa consiste na manipulação directa das regras da firewall pelos

IDSs. Quando um ataque se inicia, as firewall recebem instruções para não permitir entrar

o tráfego que vem da origem do ataque, essa limitação pode ser temporária. A sua

eficácia pode ser contornada se:

• Adoptar uma táctica de “hit-and-run” e aproveitar o tempo que demora a actualizar

a firewall (cerca de 2 segundos);

• Uso de endereços IP forjados de modo a banir endereços conhecidos;

Em conclusão, podemos constatar que os tipos de respostas activos fornecem uma acção

correctiva em tempo útil. Apesar disso têm que ser implementadas com extrema

precaução, pois podem ser contornadas e usadas contra a própria rede como foi

demonstrado no caso das actualizações da firewall.

IDSs: Detecção de Padrões Introdução : Métodos de Detecção


1.2 Métodos de Detecção

Os métodos que os IDSs usam para detectar uma assinatura coincidente com um ataque

conhecido podem ser:

• Detecção de Padrões (Pattern Matching);

• Detecção de Padrões que mantém o estado (Stateful Pattern Matching);

• Análise de Protocolo (Protocol Decode);

• Análise Heurística (Heuristic Analysis);

• Análise das Anomalias (Anomaly Analysis).

Há a realçar, que cada produto pode não ter apenas uma destas metodologias

empregues, o mais provável é que tenha uma mistura de várias. Convém ainda referir que

o termo assinatura é normalmente associado a detecção de padrões, mas para os IDSs

indica qualquer evento de intrusão. Assim, o algoritmo usado para verificar a assinatura

de um ataque, pode ser baseado em qualquer das metodologias de detecção

apresentadas. De seguida vamos analisar as várias metodologias, bem como as suas

vantagens e desvantagens.

1.2.1 Detecção de Padrões

Na sua forma mais básica tenta identificar um sequência fixa de bytes numa única

unidade de tráfego. Embora seja uma aproximação bastante rígida é de implementação

simples. Para diminuir o número e a quantidade de inspecções em cada unidade de

tráfego, o padrão da assinatura só é testado para: determinado serviço, determinada

porta, determinada combinação de flags e determinado inicio/fim no seu conteúdo.

Um exemplo da estrutura de uma assinatura baseada na detecção de padrões simples, é:

• Accionar um alarme se o pacote é IPv4 e TCP e a porta destino é 2222 e o

conteúdo contem “foo.”



Quanto mais específicos forem estes parâmetros, menos inspecção necessita de ser

efectuada para cada unidade de tráfego. Contudo, este tipo de aproximação complica-se,

quando os protocolos não estão associados a portas específicas.

Apesar da simplicidade da definição de assinaturas para um determinado exploit, as

pequenas variações que este pode ir adquirindo, torna necessário que a assinatura seja

muito específica. Este método pode ainda gerar muitos falsos alarmes, porque o tráfego

legítimo pode conter o mesmo conjunto pequeno de critérios, para determinarem a

ocorrência de um ataque.

Vantagens

• Método de implementação simples;

• Método bastante específico, permite uma correlação directa do padrão com o

ataque;

• Alertas fiáveis dos padrões especificados;

• Aplicado em todos os protocolos.

Desvantagens

• Falsos alarmes se o padrão não é único de um ataque;

• Falsos negativos se há alterações ao ataque;

• Múltiplas assinaturas para variações do mesmo exploit;

• Inspecção de uma única unidade de tráfego permite utilizar técnicas de evasão aos

IDSs (ex.: fragmentação).

1.2.2 Detecção de Padrões que mantém o estado

Este método (Stateful Pattern Matching) fornece uma aproximação mais sofisticada

porque mantem o estado da conexão, em vez de analisar em uma única unidade de

tráfego.

Assim, considera a ordem de entrega das unidades de tráfego e usa a detecção de

padrões em várias delas. Por exemplo, o atacante envia a cadeia de caracteres “fo” numa



unidade de tráfego e “o” em outra. Se essa for uma assinatura correspondente a um

ataque é reconhecido por este método..

Isto requer mais recursos que o método anterior, porque os IDSs têm que alocar grandes

quantidades de memória e processamento para seguir um número elevado de sessões

abertas. Esta aproximação torna a evasão aos IDSs mais difícil, mas longe de impossível.

Vantagens

• Método de implementação mais complicado;

• Método bastante especifico, permite uma correlação directa do padrão com o

ataque;

• Alertas fiáveis dos padrões especificados;

• Aplicado em todos os protocolos;

• Torna as evasões um pouco mais difíceis;

Desvantagens

• Falsos alarmes se o padrão não é único de um ataque;

• Falsos negativos se há alterações ao ataque;

• Múltiplas assinaturas para variações do mesmo exploit;

1.2.3 Análise de Protocolo

As assinaturas baseadas na Análise de Protocolo (Protocol Decode) são extensões

inteligentes da Detecção de Padrões que mantém o estado. Quando os elementos do

protocolo são identificados, os IDSs aplicam as regras definidas pelos RFC à procura de

violações. Em certos casos, essas violações são encontradas em padrões dentro dos

campos do protocolo, mas outras requerem técnicas mais avançadas como o tamanho do

campo ou o número de argumentos. Esta metodologia detecta determinadas anomalias

como dados binários em pedidos HTTP, grandes quantidades de dados onde não era

suposto, etc. De notar, que os métodos de Detecção de Padrões e Análise de Protocolo

não são mutuamente exclusivos.



Vantagens

• Minimiza a ocorrência de falsos alarmes, se o protocolo está bem definido e

robusto;

• Permite uma correlação directa com um ataque;

• Mais abrangente e generalista, o que permite detectar variações do mesmo ataque;

• Fornece alertas fiáveis na violação das regras do protocolo definidas.

Desvantagens

• Falsos alarmes se o RFC do protocolo é ambíguo;

• Demasiado tempo para desenvolver um analisador do protocolo.

1.2.4 Análise Heurística

Este método de assinaturas usa algum tipo de lógica nos algoritmos, de modo a decidir

quando accionar um alarme e são normalmente avaliações estatísticas do tipo de tráfego

a analisar.

Um exemplo deste tipo de assinatura é a assinatura que pode ser usada para verificar a

varredura das portas. Está assinatura procura pela presença de um número limiar de

utilizações de cada porta num determinado sistema. Depois, verifica se o padrão de

tráfego para cada uma delas é similar.

Vantagens

• Alguns tipos de actividade ilegais não podem ser detectados por outros meios.

Desvantagens

• Os algoritmos podem necessitar de ajustes, de modo a tornarem-se mais

conformes com o tráfego e de forma a diminuir os falsos alarmes.



1.2.5 Análise das Anomalias

A última aproximação não tenta identificar directamente os ataques, concentra-se em

ignorar aquilo que é considerado normal. O princípio básico é identificar o que é

considerado tráfego normal na rede, todo o tráfego restante é considerado como uma

intrusão. No mínimo é visto como algo que vale a pena alertar. Assim, têm a capacidade

de reconhecer ataques novos, porque não está à procura de assinaturas de ataques, mas

se tal constitui tráfego normal.

Vantagens

• Pode detectar ataques novos;

• Pouco overhead porque não necessita de novas assinaturas.

Desvantagens

• Detecta que há algo de errado mas não consegue especificar;

• O alarme pode disparar à mínima alteração;

• Depende muito do meio onde o sistema aprendeu o que é normal.

IDSs: Detecção de Padrões Técnicas de Detecção de Padrões : Definição


2 Técnicas de Detecção de Padrões

Neste capítulo pretende-se apresentar as técnicas utilizadas para detecção de padrões e

mostrar porque têm uma vasta utilização no mundo da informática, biologia (procura de

sequências no DNA) e em outras áreas.

Inicialmente, é apresentada uma definição das técnicas de detecção de padrões fazendo

referência à sua área de aplicação e à sua evolução. Em seguida, é descrita a forma

genérica de funcionamento destas técnicas. A secção termina com a demonstração dos

algoritmos: Força Bruta, Boyer-Moore[12], Horspool[13] e Aho-Corasick[14]. O

conhecimento detalhado destes algoritmos vai ser fundamental para a compreensão do

próximo capítulo.

2.1 Definição

A detecção de padrões (pattern matching/string matching) é um assunto importante em

vários domínios, como por exemplo, nos IDSs, processamento de texto, detecção de

vírus, biologia molecular, entre outros. Estes algoritmos são componentes básicos usados

em muitos dos programas existentes pelos diferentes sistemas operativos. Além disso,

ainda desempenham um papel importante na teoria das ciências dos computadores, ao

providenciarem problemas que oferecem enormes desafios.

Apesar dos dados serem armazenados de diferentes formas, os caracteres de texto ainda

são a forma principal na troca de informação. A crescente exigência de um maior número

de padrões (ex. IDSs, detecção de vírus) a serem procurados, faz com que os algoritmos

necessitem de serem cada vez mais eficientes, mesmo sabendo que a velocidade e

capacidade dos computadores aumentam regularmente.

A detecção de padrões consiste em encontrar uma ou mais ocorrências de uma cadeia de

caracteres (pattern) dentro de um texto. O padrão é indicado por x=x[0..m-1] e o seu

comprimento é igual a m. O texto é indicado por y=y[0..n-1] e o seu comprimento é igual

IDSs: Detecção de Padrões Técnicas de Detecção de Padrões : Definição


a n. Ambas as cadeias de caracteres são construídas a partir de um conjunto finito de

caracteres que se chama alfabeto e é indicado por Σ com o seu comprimento igual a σ.

Os referidos algoritmos trabalham da forma como a seguir se descreve. O varrimento do

texto é feito com a ajuda de uma janela, da qual o tamanho é geralmente igual a m.

Primeiro alinham os lados esquerdos da janela e do texto, depois comparam os

caracteres da janela com os caracteres do padrão a encontrar (tentativa). Se ocorre uma

combinação com todo o padrão (o algoritmo pára neste ponto se procura apenas uma

ocorrência) ou ocorre de um falha, é efectuado um deslocamento da janela para a direita.

De seguida, repetem o mesmo procedimento, até o lado direito da janela ultrapassar o fim

do texto. Este mecanismo é usualmente chamado de mecanismo de janela deslizante.

IDSs: Detecção de Padrões Técnicas de Detecção de Padrões


2.2 Evolução

A detecção de padrões começou-se a evidenciar nos inícios dos anos 70 quando os

editores de texto estavam em desenvolvimento e começavam a surgir os sistemas de

linguagem como os parsers e os term-rewriters. Inicialmente, a única técnica usada para

resolver a detecção de padrões, era a Força Bruta que ia percorrendo todo o texto em

busca de uma determinada combinação de caracteres, mas geralmente era considerada

insatisfatória.

Em 1977, surgiram os primeiros algoritmos que evidenciavam um significativo aumento de

desempenho, e que foram desenvolvidos por Knuth-Morris-Pratt[11] e por Boyer-

Moore[12]. Os estudos efectuados deixavam antever que a detecção de padrões seria

uma área com um futuro promissor e indicavam a direcção a seguir. Além do mais, esses

algoritmos ainda são considerados actuais, e estão na base de muitas das

implementações híbridas actuais.

IDSs: Detecção de Padrões Técnicas de Detecção de Padrões : Algoritmos


2.3 Algoritmos

Em seguida apresentam-se os algoritmos de detecção de padrões relevantes para o

presente trabalho: Força Bruta, Boyer-Moore[12], Horspool[13], Aho-Corasick[14]. Cada

algoritmo tem: a indicação das suas funcionalidades principais, uma breve descrição do

seu funcionamento e um exemplo da sua aplicação. Em anexo encontram-se as

implementações dos respectivos algoritmos.

O Algoritmo de Força Bruta também está incluído para: servir de comparação com os

algoritmos mais complexos e como uma referência histórica dos primórdios da detecção

de padrões.

Todos os algoritmos aqui descritos procuram mais do que uma ocorrência do mesmo

padrão, o que no caso dos IDSs não era de todo necessário e até era impensável em

termos de desempenho. Nos IDSs apenas basta notar que uma sequência de caracteres

ocorre, o que equivale a um possível ataque e a accionar um alarme. Mesmo, assim não

se alterou os algoritmos que podem assim ser usados de uma forma mais geral.



2.3.1 Força Bruta

Funcionalidades Principais

• Sem fase de pré-processamento;

• Necessidade constante de espaço extra;

• Desloca sempre a janela uma posição para a direita;

• Comparações podem ser feitas em qualquer ordem;

• Complexidade no tempo: O(mn);

• Número de comparações esperado: 2n.

Descrição O algoritmo de força bruta consiste em verificar, em todas as posições do texto a

ocorrência do padrão. Depois de cada tentativa, desloca a janela exactamente uma

posição para a direita. Exemplo 1ª tentativa

y G C A T C G C A G A G A G T A T A C A G T A C G

1 2 3 4

x G C A G A G A G

• Deslocamento de 1

2ª tentativa


1

x G C A G A G A G


3ª tentativa


1

x G C A G A G A G




4ª tentativa


1

x G C A G A G A G


5ª tentativa


1

x G C A G A G A G


6ª tentativa


1 2 3 4 5 6 7 8

x G C A G A G A G


7ª tentativa


1

x G C A G A G A G


8ª tentativa


1

x G C A G A G A G


9ª tentativa


1 2

x G C A G A G A G




10ª tentativa


1

x G C A G A G A G


11ª tentativa


1 2

x G C A G A G A G


12ª tentativa


1

x G C A G A G A G


13ª tentativa


1 2

x G C A G A G A G


14ª tentativa


1

x G C A G A G A G


15ª tentativa


1

x G C A G A G A G




16ª tentativa


1

x G C A G A G A G


17ª tentativa


1

x G C A G A G A G


Conclusão: O algoritmo de força bruta executou 30 comparações no exemplo dado.

Fig. 4 : Exemplo do Algoritmo Força Bruta



2.3.2 Boyer-Moore


• Executa as comparações da direita para a esquerda;

• Fase de pré-processamento com complexidade no tempo e no espaço de O(m+ σ);

• Fase de procura com complexidade no tempo de O(mn);

• Número de comparações esperado: 3n (no pior caso quando procura por um

padrão não periódico);

• Melhor desempenho: O(n/m);

Descrição O Boyer-Moore[12] é considerado o algoritmo de detecção de padrões mais eficiente para

aplicações usuais. Normalmente é implementado nos editores de texto para os comandos

“procurar” e o “substituir” e é também usado na maioria dos IDSs e dos antivírus.

O algoritmo faz o varrimento dos caracteres no padrão da direita para a esquerda a

começar no que está mais à direita. Se ocorrer uma falha (ou no caso de uma

combinação total com o padrão), ele usa duas funções para deslocar a janela para a

direita. Essas duas funções chamam-se: good sufix shift e bad character shift.

Vamos assumir que uma falha ocorreu entre o caracter x[i]=a do padrão e o caracter

y[i+j]=b do texto durante uma tentativa à posição j. Então, x[i+1..m-1]=y[i+j+1..j+m-1]=u

e x[i]<>y[i+j]. O good sufix shift consiste em alinhar o segmento y[i+j+1..j+m-

1]=x[i+1..m-1] com a sua ocorrência em x o mais à direita e que é precedida por um

caracter diferente de x[i] (ver figura). Se não existe tal segmento, a deslocação consiste

em alinhar o maior sufixo v de y[i+j+1..j+m-1] com o prefixo coincidente de x (ver figuras).



Fig. 5 : Good Sufix Shift (opção 1)

Fig. 6 : Good Sufix Shift (opção 2)

O bad character shift consiste em alinhar o caracter y[i+j] do texto com a ocorrência

mais à direita em x[0..m-2] (ver figura). Se y[i+j] não ocorrer no padrão x, nenhuma

ocorrência de x em y pode incluir y[i+j], e o fim esquerdo da janela é alinhado com o

caracter imediatamente a seguir a y[i+j], ou seja y[i+j+1] (ver figuras). De notar que o bad

character shift pode ser negativo, assim para deslocar a janela, o algoritmo Boyer-Moore

aplica o máximo de deslocamento de uma das funções.

Fig. 7 : Bad Character Shift (opção 1)

Fig. 8 : Bad Character Shift (opção 2)



Exemplo

c A C G T

bmBc[c] 1 6 2 8

É a distância do carácter à direita do padrão (sem contar com o que está mais à direita)

i 0 1 2 3 4 5 6 7

x[i] G C A G A G A G suff[i] 1 0 0 2 0 4 0 8

bmGs[i] 7 7 7 2 7 4 7 1

1ª tentativa


1

x G C A G A G A G

• Deslocamento de 1 (bmGs[7] = bmBc[A] – 7 + 7)

2ª tentativa


3 2 1

x G C A G A G A G

• Deslocamento de 4 (bmGs[5] = bmBc[C] – 7 + 5)

3ª tentativa


8 7 6 5 4 3 2 1

X G C A G A G A G

• Deslocamento de 7 (bmGs[0])



4ª tentativa


3 2 1

x G C A G A G A G

• Deslocamento de 4 (bmGs[5] = bmBc[C] – 7 + 5)

5ª tentativa


2 1

x G C A G A G A G

• Deslocamento de 7 (bmGs[6] )

Conclusão: O algoritmo de Boyer-Moore executou 17 comparações no exemplo dado.

Fig. 9 : Exemplo Algoritmo Boyer-Moore



2.3.3 Horspool


• Simplificação do algoritmo Boyer-Moore;

• Apenas usa bad character shift;

• Fácil de implementar;

• Fase de pré-processamento com complexidade no tempo de O(m+σ) e no espaço

de O(σ);

• Fase de procura com complexidade no tempo de O(mn);

• Número médio de comparações esperado: [1/σ, 2(σ + 1)];

Descrição O algoritmo Horspool[13] é uma adaptação do algoritmo de Boyer-Moore que usa apenas

o bad character shift. Esta heurística não é muito eficiente para pequenos alfabetos,

mas já o é para alfabetos grandes comparados com o comprimento do padrão (ex. tabela

ASCII e pesquisas num editor de texto). Ao ser usado sozinho produz um eficiente

algoritmo na prática.

Exemplo

c A C G T

bmBc[c] 1 6 2 8

É a distância do carácter à direita do padrão (sem contar com o que está mais à direita)

1ª tentativa


1

x G C A G A G A G

• Deslocamento de 1 (bmBc[A] )



2ª tentativa


2 1

x G C A G A G A G

• Deslocamento de 2 (bmBc[G] )

3ª tentativa


2 1

x G C A G A G A G


4ª tentativa


2 3 4 5 6 7 8 1

x G C A G A G A G


5ª tentativa


1

x G C A G A G A G

• Deslocamento de 1 (bmBc[A] )

6ª tentativa


1

x G C A G A G A G

• Deslocamento de 8 (bmBc[T] )

7ª tentativa


2 1

x G C A G A G A G




Conclusão: O algoritmo de Horspool executou 17 comparações no exemplo dado.

Fig. 10 : Exemplo do Algoritmo de Horspool



2.3.4 Aho-Corassick


• Tempo que demora a busca é independente do número de padrões;

• Fase de busca com complexidade no tempo de O(n log σ);

• Desloca sempre a janela uma posição para a direita;

• Número de comparações esperado: 2n (para um conjunto de padrões).

Descrição Os algoritmos descritos até ao momento, apenas procuram um padrão em cada

interacção. Isto significa que para encontrar um conjunto de padrões no mesmo texto,

temos que repetir esses algoritmos para cada padrão. O Aho-Corasick[14] resolve esta

limitação, pois permite procurar um conjunto finito de padrões em uma só interacção. Este

algoritmo é uma extensão directa do algoritmo Knuth-Morris-Pratt[11] e o tempo que

demora a busca é independente do número de padrões.

A sua execução é efectuada em duas fases, a fase de pré processamento que constrói a

árvore de padrões e a fase de busca que procura esses padrões no texto. A fase de pré

processamento encontra-se ainda dividida em três partes: criação de ciclos na raiz da

árvore, inserir cada padrão na árvore indicando respectiva saída e completar a árvore

com as ligações falhadas e novas saídas determinadas (‘sear’ na figura). A árvore T(X)

é construída com os prefixos do padrão X nos nós e o mesmo soletrado nos ramos.

Quando a fase de pré processamento termina, inicia a fase de busca. Esta fase consiste

em percorrer todos os caracteres do texto y com todos os padrões da árvore T(X). O

início é na raiz da árvore T(X) e usa uma ligação falhada quando um caracter no texto y

não combina com qualquer das etiquetas destino do nó actual. Sempre que um nó com

saída não vazia é encontrado, isto significa que padrões da saída foram descobertos no

texto, e termina na posição corrente, devolvendo esse valor (ver figura).



Fig. 11 : Árvore de padrões de Aho-Corasick

Exemplo O algoritmo Aho-Corasick tem uma funcionamento idêntico ao algoritmo da Força Bruta, a

diferença, é que utiliza uma árvore de padrões o que permite verificar mais do que um

padrão em simultâneo.

IDSs: Detecção de Padrões Detecção de Padrões nos IDSs : Definição


3 Detecção de Padrões nos IDSs Nesta secção pretende-se mostrar o estado actual da detecção de padrões nos IDSs e de

evidenciar formas de aumentar o desempenho desta.

Inicialmente, é apresentada uma definição da detecção de padrões nos IDSs fazendo

referência à sua importância. Em seguida, é apresentado o Snort que, devido às suas

características4, é uma ferramenta importante para avaliar o desempenho dos algoritmos

expostos no último capítulo, adaptando-os ao universo dos IDSs. Desta combinação,

serão analisados dois novos algoritmos: AC_BM e SBMH que pretendem obter uma

melhoria significativa no desempenho do Snort e da detecção de padrões.

3.1 Definição

Dos métodos de detecção que os IDSs usam importa destacar os de Detecção de

Padrões (os simples e os que mantêm o estado), uma vez que são os que utilizam os

algoritmos de detecção de padrões para efectuarem uma busca ao conteúdo das

unidades de tráfego.

O grande desafio para a detecção de padrões nos IDSs é a sua capacidade para

processar todas as unidades de tráfego, sem descartar nenhuma e sem originar falsos

alarmes. Como o número de assinaturas a verificar por unidade de tráfego está

constantemente a aumentar, bem como as subtis variações5 nessas mesmas, o

desempenho é factor crucial.

4 O Snort é um NIDSs popular e robusto, gratuito e é open source. 5 Variações nas assinaturas: códificação hexadecimal, caracteres unicode, espaço supérfluo, fragmentação,

inserção de directório /./, sensibilidade às maiúsculas/minúsculas, etc

IDSs: Detecção de Padrões Detecção de Padrões nos IDSs : Snort


3.2 Snort

O Snort é um produto de utilização gratuita (de acordo com a licença GNU). O produto é

um NIDS e tem um desempenho assinalável. Isto levou a que fosse bastante conhecido e

admirado no meio e, por consequência, bastante utilizado. Como é open source pode ser

facilmente analisado e melhorado por qualquer indivíduo. Além disso, o motor de

detecção de padrões que possui encontra-se implementado noutros produtos, como por

exemplo, nos da Cisco[16]. A seguir será feita uma análise exaustiva do seu

funcionamento, o que permite averiguar que tipo de pesquisa faz e como é possível

melhorar em termos de desempenho.

3.2.1 Modo de Operação

3.2.1.1 Regras Os IDSs baseados nas assinaturas, tal como é o Snort, tipicamente são configurados com

um conjunto de regras para detectarem padrões de ataques conhecidos. Essas regras

são muito parecidas às regras de um firewall, pois estas também permitem bloquear

padrões (ex. todos as unidades de tráfego da subrede X enviados para a porta 80) e são

flexíveis a especificar prefixos, campos com asterisco, e limites das portas.

Contudo, a detecção de assinaturas nos IDSs vai mais longe que a filtragem de unidades

de tráfego na firewall. A sua maior complexidade permite procurar um padrão, mesmo no

conteúdo das unidades de tráfego. Isto torna os IDSs muito atractivos para detectarem

ataques, que de outra forma passariam impunes à firewall. Mas tudo isto tem custos em

termos de processamento. Uma regra da firewall pode ter que analisar 128 bits dentro de

um cabeçalho de 40 bytes. Nos IDSs além de terem que analisar esse cabeçalho, podem

ter que procurar um padrão dentro do conteúdo da mesma unidade de tráfego e o

comprimento deste pode ser de uns míseros bytes ou milhares deles. De seguida

apresenta-se dois exemplos destas regras.



A

alert tcp !HOME_NET any -> $HOME_NET 80

(msg:”IDS219 – Web-CGI-Perl access attempt”;

flags:PA; content:”perl.exe”; nocase;)

B

alert udp $EXTERNAL_NET any -> $HOME_NET 177

(msg:”MISC xdmcp query”);

content:“|00 01 00 03 00 01 00|”; reference:arachnids, 476;

classtype:attempted-recon; sid:517; rev1;)

Fig. 12 : Exemplo de Regras Snort

As regras do Snort podem ser divididas em duas partes, o cabeçalho da regra e as

opções da mesma. O cabeçalho vai desde o início até ao primeiro parêntesis e as opções

são todas as que estão dentro do parêntesis.

No cabeçalho cada regra contem uma acção (alert), um protocolo (tcp, udp), uma

mascara de rede da origem, uma porta de origem (any), uma mascara de rede do destino

e a porta (80, 177). Nas opções podemos ter uma lista de parâmetros a ter em conta,

como por exemplo: mensagem de alerta em caso de ataque (msg), teste às flags TCP

(flags), o conteúdo especifica o padrão a procurar no conteúdo da unidade de tráfego

(content), etc.

A mensagem de alerta no exemplo A refere o IDS129, que é uma chave única associada

a esta vulnerabilidade. Estas chaves ajudam na correlação que deve existir entre produtos

diferentes, e também ajuda a equipa de resposta a incidentes ao providenciar mais

informações sobre o ocorrido. No caso B, temos uma mensagem que não indica a chave

única standard (IDSxxx), indicando uma chave alternativa da base de dados de

assinaturas arachNIDS (arachnids, 476). A chave única standard faz parte de um mesmo

dicionário chamado Common Vulnerabilities and Exposures (CVE) e tem a participação de

mais de trinta entidades influentes no meio. Por este motivo, essa chave deve ser sempre

indicada.



3.2.1.2 Motor de Pesquisa O Snort usa o seu conjunto de regras para criar uma estrutura bidimensional de duas

listas ligadas que consiste na Rule Tree Nodes (RTN) e Option Tree Nodes (OTN). Numa

primeira fase a lista do RTN é percorrida, se as condições se verificarem, será percorrida

a lista do OTN. O RTN guarda muitas das propriedades comuns às várias regras, como

por exemplo, os endereços de origem e destino, as portas de origem e de destino e o tipo

de protocolo (TCP, ICMP, UDP). O OTN guarda a informação para as várias opções que

podem ser adicionadas como por exemplo, flags TCP, códigos e tipos ICMP , tamanho do

conteúdo da unidade de tráfego e o maior bottleneck para o desempenho: o conteúdo da

unidade de tráfego.

Fig. 13 : Exemplo de RTN

Há trinta e cinco (35) palavras-chave no Snort 1.8.3 que podem ser usadas na parte das

opções, vinte (20) delas para serem usadas no OTN. Dessas, dezassete (17) são de

verdadeiro/falso ou envolvem operadores relacionais entre valores (ex. ‘<’, ‘>’). O motor

do Snort pode facilmente passar essa informação pela lista ligada com pouco overhead.

Muito do overhead gerado nestes motores vem do uso das seguintes três (3) palavras

chave: ‘content’, ‘contentlist’ e ‘urlcontent’. Cada uma delas chama o motor de detecção

de padrões e das 1.270 regras existentes nesta versão, 1.086 delas contem as referidas

palavras-chaves. Por este motivo são as últimas a serem verificadas dentro da mesma

unidade de tráfego.



Fig. 14 : Exemplo de OTN

3.2.1.3 Algoritmo Utilizado Nos seus primórdios o Snort usava o algoritmo de Força Bruta que era muito lento e por

isso foi identificado como um dos pontos a melhorar. Para aumentar o desempenho,

implementou-se o algoritmo Boyer-Moore, embora que parcialmente. Passados alguns

meses, o referido algoritmo foi implementado na íntegra. Actualmente, o Snort continua a

usar no motor de detecção de padrões, o algoritmo de Boyer-Moore, que já foi

anteriormente descrito.



3.2.2 Desempenho

O conhecimento do desempenho do Snort, permite averiguar a importância da detecção

de padrões no desempenho total do produto. Permite ainda, saber quais as implicações

de um fraco desempenho no funcionamento dos NIDSs.

3.2.2.1 Perfil O motor de detecção de padrões do Snort é o que consome mais recursos no

reconhecimento de assinaturas[16]. No estudo foi utilizando o Snort 1.6.3 a correr num

conjunto de dados de 8.7 milhões de unidades de tráfego, totalizando mais de 1GB num

período de 25 minutos. Para medir o desempenho por perfil, foi usado o gprof6 (ver

tabela).

Propósito Rotina Tempo Execução

Detecção de Padrões

Classificação de Unidades de Tráfego

Classificação de Unidades de Tráfego

Outros (detecção)

Restantes

mSearch

EvalHeader

CheckSrcIPNotEq

EvalOpts

-

31,0%

8,5%

6,7%

5,8%

48%

Tabela 1 : Perfil de desempenho do Snort

3.2.2.2 Ataques Como já vimos anteriormente, um fraco desempenho do produto pode significar uma

perca de unidades de tráfego na análise dos NIDSs. Este factor é ainda mais

determinante se tivermos em conta, que um atacante pode usar essa deficiência para

quebrar a segurança da rede. Primeiro, invade a rede com unidades de tráfego que ele à

partida sabe que os NIDSs vão demorar muito tempo a tratar. Entretanto, vai enviando

unidades de tráfego com ataques, na esperança que a sobrecarga causada na rede force

os NIDSs a se descartarem de alguns deles. Testes de desempenhos efectuados[20],

provam que o Snort têm problemas a este nível (ver tabela).

6 gprof é analisador de perfis, ver em www.gnu.org/manual/gprof-2.9.1/gprof.html



Carga Desempenho em Sobrecarga (% detectados) 0% 25% 50% 75% 100%

Pequenos pacotes (64 bytes/148.000pps) 100% 100% 76% 46% 37%

Pacotes do “mundo real” (40.000pps) 100% 100% 15% 10% 6%

Grandes pacotes (1514 bytes/8.172ppp) 100% 100% 100% 100% 100%

Tabela 2 : Desempenho em sobrecarga do Snort

Assim, seria de todo importante conseguir melhorar o desempenho do motor de detecção

de padrões, de modo a deixar de ser um bottleneck dentro do Snort e melhorar

consideravelmente o desempenho e qualidade total do produto. Isto só é possível se

houver uma mudança radical na forma como está implementada a estrutura de apoio ou

na alteração/modificação do algoritmo Boyer-Moore de detecção de padrões que está

actualmente a ser usado.

IDSs: Detecção de Padrões Detecção de Padrões nos IDSs : Novos Algoritmos


3.3 Novos Algoritmos

O Snort é um produto NIDSs open source e está aberto à colaboração de quem o quiser o

melhorar. Estas características fazem com que o produto seja o ideal para se realizarem

vários estudos, estudos esses que vão acrescentando mais valias ao mesmo. Sendo o

motor de detecção de padrões, o principal problema de desempenho do produto (com

31% do tempo de computação, como anteriormente mostrado), não admira que haja já

soluções que podem melhorar o seu desempenho até 5 vezes mais. Muitas outras irão

surgir: pela utilização de novos algoritmos, pela modificação dos já existentes ou ainda

pela combinação de vários deles.

As técnicas dos algoritmos da família Boyer-Moore podem ser adaptadas para operar

num conjunto de padrões em uma única passagem. Commentz-Walter[21] foi o primeiro a

introduzir esta ideia e Watson[22] demostrou que este algoritmo tem um melhor

desempenho que o de Aho-Corasick, principalmente para padrões extensos. Por sua vez,

Gusfield[23] argumentou preferir usar um algoritmo simplificado e usar árvores de sufixos

nos cálculos da heurística Good Suffix Shift. Wu e Manber[24] desenvolveram outras

técnicas para implementar as heurísticas de Boyer-Moore e, conseguiram desempenhos

melhores do que Aho-Corasick ou Commentz-Walter, para textos com linguagem natural.

Muitos destes algoritmos são poderosos, mas complexos na sua utilização. A variante de

Horspool ao Boyer-Moore evidenciou que algoritmos mais simples, na maioria das vezes,

tem melhor desempenho que os algoritmos que passam muitos caracteres de uma só vez

(mais processamento). Horspool usa apenas a heurística Bad Character Shift do

algoritmo de Boyer-Moore sem grande perda de desempenho.

Tendo em conta estes pressupostos, relevantes para o aumento de desempenho no

motor de detecção de padrões, vamos analisar os estudos que resultaram em dois novos

algoritmos: Aho-Corasick-Boyer-Moore (AC_BM)[15] e o Setwise-Boyer-Moore-Horspool

(SBMH)[16].



3.3.1 AC_BM

O algoritmo Aho-Coracssick-Boyer-Moore (AC_BM)[15] usa uma implementação do

algoritmo Boyer-Moore com alterações mínimas, em um conjunto de palavras dispostas

numa árvore construída pelo algoritmo de Aho-Corassick e que sobrepõe os prefixos

comuns das palavras.

As similaridades são as seguintes:

• Bad Character Shift;

• Árvore de palavras;

As variações são as seguintes:

• Uso de Good Prefix Shift em vez do Good Sufix Shift;

• Procura do padrão da direita para a esquerda do texto e não vice-versa;

• Árvore baseada em prefixos em vez de sufixos;

Normalmente, nos padrões a procurar para o mesmo tipo de vulnerabilidade existem

semelhanças que não são devidamente exploradas. Mesmo, quando não existe uma

relação tão evidente entre os padrões a procurar, há sempre a possibilidade de encontrar

partes comuns e retirar daí benefícios em termos de eficiência (ver figura). O que se

passa actualmente no produto em análise (e em muitos dos outros que se baseiam nos

mesmos princípios) é que testam um padrão de cada vez no conteúdo de cada uma das

unidades de tráfego. O objectivo, que parece evidente, é testar um conjunto de padrões

ao mesmo tempo. A isto, chama-se Pesquisa de Padrões Múltiplos.



Fig. 15 : Exemplo de Padrões Semelhantes

Ao analisar os padrões a procurar propostos na figura, nota-se que existem dezasseis

(16) diferentes regras que partilham informação comum. Essa informação pode ser

armazenada numa árvore de palavras de AC_BM (ver figura) e usada na Pesquisa de

Padrões Múltiplos. De notar, que uma falha de combinação numa parte comum pode

eliminar a necessidade de se verificar muitas regras.

Fig. 16 : Árvore de Palavras de AC_BM



3.3.1.1 Implementação Como na aproximação de Boyer-Moore, este novo algoritmo alinha o padrão a procurar

com o texto a ser procurado e executa deslocamentos para eliminar comparações não

necessárias. A árvore de palavras move-se do fim do conteúdo da unidade de tráfego

para o seu início. Logo que a referida árvore de palavras esteja alinhada, as comparações

de caracteres são feitas da esquerda para a direita. Ao contrário do Boyer-Moore que

desloca um único padrão ao longo do conteúdo, o algoritmo AC_BM desloca uma árvore

de padrões ao longo do mesmo usando o Bad Character Shift e Good Prefix Shift.

- os caracteres são examinados a começar no asterisco e comparados da esquerda para a direita;

- toda a árvore de padrões move-se ao longo do texto a procurar da direita para a direita;

- a comparação começa alinhando o padrão mais pequeno na árvore (time) com as últimas 4 letras ;

- os caracteres são lidos da esquerda para a direita a iniciar no asterisco;

- a primeira comparação falha no caracter S;

- o próximo S ocorre no padrão tinsel e origina um deslocamento de 3 caracteres.

Fig. 17 : Bad Character Shift de AC_BM



O Bad Character Shift é similar à primeira heurística do Boyer-Moore, se uma falha

ocorre, ele recomenda deslocar a árvore para alinhar com a próxima ocorrência do

carácter dentro da árvore de palavras. Se o carácter não existir na árvore de padrões,

este é deslocado para a esquerda n caracteres, onde n é o comprimento do mais

pequeno padrão na árvore.

O Good Prefix Shift recomenda um deslocamento até à próxima ocorrência de um prefixo

completo que já foi visto noutro padrão, ou até à próxima ocorrência de um qualquer

prefixo.

- os caracteres são examinados a começar no asterisco e comparados da esquerda para a direita;

- toda a árvore de padrões move-se ao longo do texto a procurar da direita para a direita;

- a comparação começa alinhando o padrão mais pequeno na árvore (time) com as últimas 4 letras ;

- os caracteres são lidos da esquerda para a direita a iniciar no asterisco;

- a primeira comparação falha no caracter N;

- dos caracteres que tiveram sucesso, TO (prefixo) aparece no fim de TOMATO;

- isto origina um deslocamento de 4 para alinhar os últimos 2 caracteres do padrão com o já visto;

Fig. 18 : Good Prefix Shift de AC_BM



No final, é apenas executado o maior deslocamento conseguido, devolvido por ambas as

heurísticas do algoritmo AC_BM.

3.3.1.2 Limitações Algumas das limitações deste algoritmo são:

• Não suporta procuras sensíveis ás maiúsculas/minúsculas;

• Não suporta regras múltiplas para o mesmo conteúdo – regras que requerem que

dois ou mais padrões sejam verificados, são tratados pelo algoritmo Boyer-Moore

(depois do primeiro teste);

• Muito dependente do tamanho do mais pequeno dos padrões - quanto menor ele

for, menos se pode deslocar de uma só vez;

• Necessita de mais memória;

3.3.1.3 Desempenho Convém referir que os teste elaborados sobre o desempenho e uso de recursos foram

elaborados para testar o Snort, e que são influenciados por;

• Tempo de pesquisa na estrutura da lista ligada associada ao RTN;

• Tempo de pesquisa na estrutura da lista ligada associada ao OTN;

• E finalmente, pela detecção de padrões no conteúdo da unidade de tráfego.

Condições Os testes foram elaborados nas seguintes condições gerais:

• Uso de tráfego real adquirido7;

• Snort 1.6.3;

• Uso do comando time do Linux;

• Desactivação das letras maiúsculas;

• Execução em 30 minutos;

• Conjunto de dados de 77Mb;

• Uso de base de dados com 854 regras das quais 786 eram de conteúdo.

7 Tráfego real adquirido em: www.shmoo.org



Resultados Os resultados dos teste elaborados demonstram que o algoritmo AC_BM:

• É 1,02 a 3,32 vezes mais rápido do que o algoritmo Boyer-Moore implementado no

Snort;

• Quanto maior a percentagem de conteúdo analisado, maior é o seu desempenho;

• Necessita de 3 vezes mais memória;

Fig. 19 : Teste Desempenho AC_BM



Fig. 20 : Teste Memória AC_BM

Melhoramentos

• Implementar a árvore de palavras recorrendo a sufixos ou prefixos dependendo do

qual devolve melhores resultados de eficiência na combinação dos padrões (ex.

‘\dir\*’ ou ‘*\xpto’);

• Usar o algoritmo Commentz-Walter em vez do Aho-Corasick, pois foi demonstrado

por Watson que o primeiro tinha melhor desempenho, principalmente para padrões

extensos;

• Permitir procura de maiúsculas/minúsculas.



3.3.2 SBMH

As necessidades de diminuir o tempo de processamento de modo a gastar menos

recursos do sistema e a manter a desempenho, levam ao aparecimento de algoritmos

simplificados. Este algoritmo, Setwise-Boyer-Moore-Horspool (SBMH)[16], usa uma

implementação do algoritmo Boyer-Moore-Horspool (simplificação) com alterações

mínimas, em um conjunto de palavras dispostas numa árvore e que sobrepõe os sufixos

comuns das palavras.

As similaridades são as seguintes:

• Bad Character Shift;

• Árvore de palavras;

As variações são as seguintes:

• Não usa o Good Sufix Shift;

De notar, que este algoritmo tem muitas parecenças com algoritmo anteriormente

analisado (AC-BM), mas o SBMH apenas usa a heurística Bad Character Shift de modo a

simplificar.

3.3.2.1 Implementação O procedimento básico do algoritmo é o que se segue. A posição inicial do ponto terminal

e é o comprimento do padrão mais pequeno. O conjunto de padrões pode rapidamente

ser comparado com qualquer posição no texto ao guardar-se os padrões invertidos numa

árvore. As comparações são efectuadas da direita para a esquerda até encontrar um

carácter no texto que não combina com o próximo carácter na árvore.

Convém relembrar que a heurística Bad Character Shift do algoritmo Boyer-Moore apenas

depende da distancia conhecida do fim do padrão à última ocorrência de cada carácter

no mesmo.

3.3.2.2 Limitações Nenhuma a assinalar.



3.3.2.3 Desempenho De seguida são mostrados como foram realizados os testes de desempenho e quais os

resultados obtidos.

Condições Os testes foram elaborados nas seguintes condições gerais:

• Pentium III a 733Mhz com 256Kb de memória cache L1;

• Sistema Operativo Linux 2.2.18;

• Snort 1.6.3-p2;

• Informação temporal adquirida pelo programa gprof8;

• Uso de tráfego real adquirido através da Internet de uma grande empresa com

área comercial e cientifica;

• Foram adquiridos 8,7 milhões de unidades de tráfego com mais de 1GB.

Resultados Os resultados dos teste elaborados demonstram que o algoritmo SBMH:

• É 4.3 a 4.6 vezes mais rápido do que o algoritmo Boyer-Moore implementado no

Snort;

Método Tamanho Mínimo

Tempo Total (s)

Procura Múltiplos Padrões (s)

Procura Padrão Único (s)

BM

BMH

-

-

21,25

22,47

0

0

21,25

22,47

AC

AC

AC

SBMH

SBMH

SBMH

2

2

2

2

2

2

4,76

4,36

4,74

4,63

4,98

4,73

3,19

3,22

3,50

3,66

3,97

3,51

0

0

0

0

0

0

Tabela 3 : Tempo de Procura para Pior Tempo

8 gprof é analisador de perfis, ver em www.gnu.org/manual/gprof-2.9.1/gprof.html



Melhoramentos

• Combinar os algoritmos existentes de modo a trocar entre eles de acordo com o

número de padrões a ser analisados de uma só vez:

o Boyer-Moore-Horspool para 1 padrão;

o Setwise Boyer-Moore-Horspool entre 2 e 100 padrões (inclusive);

o Aho-Corasick para mais do que 100 padrões.

IDSs: Detecção de Padrões Conclusão


4 Conclusão

A preocupação com a segurança tem vindo a aumentar. Há uma panóplia de tecnologias

disponíveis na referida área o que, por vezes, dificulta a sua escolha. Os IDSs fazem

parte dessas tecnologias, tendo o seu conceito surgido há cerca de vinte anos. Existe

uma tendência para a sua comparação com as firewalls, verificando-se que ambos se

complementam. Contudo, importa salientar que apenas os IDSs permitem detectar

ataques no interior da rede, analisar o conteúdo das unidades de tráfego, registar todas

as tentativas de ataque e manter o estado de uma sessão (evita ataques dissimulados).

Estatísticas recentes na área das tecnologias de segurança[1], indicaram que os IDSs são

usados em 60% dos sistemas informáticos e que obtiveram um crescimento de 25% em

apenas quatro anos. Esse aumento foi o mais significativo da área, o que vem reforçar a

sua crescente importância.

Da análise das técnicas consideradas relevantes e recorrendo à utilização de um exemplo

prático, retiraram-se algumas ilações. Primeira, o algoritmo de Boyer-Moore e o Horspool

detectam o padrão utilizando menos comparações (17) do que o de Força Bruta (30).

Segunda, não existe grande diferença entre os resultados de Boyer-Moore e de

Horspool. Se tivermos em conta que este último é uma versão simplificada do primeiro (só

usa o bad character shift), então o algoritmo de Horspool é a melhor escolha sempre que

o tempo de processamento seja importante. A terceira e última ilação é que o algoritmo de

Aho-Corasick é mais eficaz que o de Força Bruta, embora efectue o mesmo número de

comparações. Isto acontece porque, no primeiro, o tempo de pesquisa é independente do

número de padrões, comparando um conjunto de padrões numa só interacção.

Para justificar a necessidade de melhorar o desempenho da detecção de padrões e

procederem a medições das alterações propostas, os autores dos algoritmos AC_BM e

dos SBMH, usaram o Snort. Este é um produto NIDSs gratuito, opensource, poderoso e,

como muitos, outros usa no seu motor de detecção de padrões o algoritmo Boyer-Moore.

IDSs: Detecção de Padrões Conclusão


As primeiras análises[16] ao Snort indicaram que era o motor de detecção deste que

consumia 31% do tempo de processamento. Quando este foi submetido a uma

sobrecarga de unidades de tráfego a analisar, começou a descartá-las[20], aumentando a

probabilidade de ocorrerem falsos negativos. Esta vulnerabilidade é regularmente usada

pelos atacantes que enviam grandes quantidades de unidades de tráfego para

sobrecarregarem os IDSs e, posteriormente, enviam ataques dissimulados na expectativa

de que estes não os detectem. Estes aspectos demonstraram que era necessária uma

melhoria significativa no desempenho da detecção de padrões.

O algoritmo AC_BM consiste numa solução híbrida do Boyer-Moore e da árvore de Aho-

Corasick. Foi demonstrado que este era até 3,32 vezes mais rápido para um grande

número de regras com conteúdo, mas também consumia 3 vezes mais memória. Quanto

ao algoritmo de SBMH, também consiste numa solução híbrida do Boyer-Moore, Horspool

e usa uma árvore de padrões. Os resultados obtidos indicam que este é até 4,6 vezes

mais rápido que o actual algoritmo implementado. Assim sendo, o SBMH é o que tem

melhor desempenho. Foram ainda identificados alguns melhoramentos: usar os prefixos

ou os sufixos das árvores conforme o tipo de padrão; combinar algoritmos existentes de

acordo com o número de padrões a verificar, maximizando assim o desempenho total.

Para terminar, importa referir que os Sistemas de Detecção de Intrusões são

fundamentais para a segurança de um sistema informático e que os algoritmos AC_BM e

SBMH criaram novas perspectivas para os tornarem mais eficientes, preservando o que é

mais importante - a informação.

IDSs: Detecção de Padrões Referências Bibliográficas


Referências Bibliográficas

[1] Computer Crime and Security Survey, CSI/FBI, 2002.

[2] James P. Anderson, “Computer Security Threat Monitoring and Surveillance”, Fort

Washington,1980.

[3] Denning, D. E., Neumann, P. G. "Requirements and Model for IDES - A Real-Time

Intrusion Detection Expert System", SRI International, 1985.

[4] Denning, D. E., “An Intrusion Detection Model”, Transactions on Software Engineering

(IEEE), Fevereiro de 1987.

[5] Smaha, S. E.: Haystack: “An intrusion detection system”, IEEE 4th Aerospace

Computer Security Applications Conference, Orlando, Dezembro de 1988.

[6] Distributed Intrusion Detection System (DIDS): http://seclab.cs.ucdavis.edu

[7] Heberlein, L. et al., “A Network Security Model”, IEEE Computer Society Symposium,

Research in Security, Maio de 1990.

[8] Proctor P., "Audit reduction and misuse detection in heterogeneous environments:

Framework and application, Proc. of the 10th Annual Computer Security Applications

Conference, Orlando, Dezembro de 1994-

[9] Automated Security Measurement System (ASIM): http://www.access.gpo.gov

[10] Computer Emergency Response Team (CERT): http://www.cert.org

[11] D. Knuth, J. Morris, e V. Pratt, “Fast pattern matching in strings”, SIAM Journal on

Computing, Junho de 1977.



[12] R. S. Boyer e J. S. Moore, “A fast string searching algorithm”, Communications of the

ACM, Outubro de 1977.

[13] R. Nigel Horspool, “Practical fast searching in strings”, Software Practice and and

Experience, 1980.

[14] A. Aho e M. Corasick, “Efficient string matching: An aid to bibliographic search”,

Communications of the ACM, Junho de 1975.

[15] C. Jason Coit, Stuart Staniford, e Joseph McAlerney, “Towards faster patern matching

for intrusion detection or exceeding the speed of snort”, 2nd DARPA

Information Survivability Conference and Exposition (DISCEX II), Junho de 2001.

[16] M. Fisk and G. Varghese, “Fast content-based packet handling for intrusion

detection”, University of California, San Diego, Junho de 2001.

[17] NIDSs Snort: www.snort.org

[18] S. Gossin, N. Jones, N. Mccurdy e R. Persaud, “Pattern Matching in Snort”, 2001.

[19] N. Desai, “Increasing Performance in High Speed NIDS. A look at Snort’s Internals”,

2002.

[20] Bob Walder, “Intrusion Detection Systems – Group Test (Edition 3)”, NSS Group,

Julho 2002.

[21] Beate Commentz-Walter, “A string matching algorithm fast on the average”,6th

International Colloquium on Automata, Languages and Programming, Julho de 1979.

[22] B.W.Watson, “The performance of single-keyword and multiple-keyword pattern

matching algorithms”, Eindhoven University of Technology, 1994.



[23] D. Gusfield, “Algorithms on Strings, Trees, and Sequences”, Cambridge University

Press, 1997.

[24] Sun Wu e Udi Manber, “A fast algorithm for multi-pattern searching”, Department of

Computer Science, University of Arizona, Maio de 1994.

R. Graham, “FAQ: Network Intrusion Detection Systems”, Março de 2000.

B. Laing, “How to Guide – Implementing a Network Based Intrusion Detection System”,

Internet Security Systems, 2000.

K. Frederick, “Understanding Network Intrusion Detection Signatures”, NFR Security, Abril

2002.

K. Timm, “IDS Evasion Techniques and Tatics”, Maio 2002.

N. Einwechter, “Implementing Networks Taps with Network Intrusion Detection Systems”,

Fate Research Labs, Junho de 2002.

K. Frederick, “Network Intrusion Detection Signatures”, Abril 2002.

“The Science of Intrusion Detection System – Attack Identification”, Cisco Press, 2002.

K. Tim, “Strategies to Reduce False Positives and False Negatives”, Setembro de 2001.

J. Larsen, “Understanding IDS Active Response Mechanisms”, Janeiro de 2002.

Marcus J. Ranum, “Experiences Benchmarking Intrusion Detection Systems”, Dezembro

2001.

M. Crochemore, T. Lecroq, “Pattern Matching and Text Compression Algorithms”



White Hats: www.whitehats.com/ids/

Hack in the Box: www.hackinthebox.org

arachNIDS: www.arachnids.com

Security Focus: www.securityfocus.com/ids

NSS Group: www.nss.co.uk/ids

IDSs: Detecção de Padrões Anexos


Anexos

Anexo A: Terminologia

Alerta (alert)

È uma aviso enviado pelo IDS para o operador do sistema a indicar que uma intrusão foi

efectuada ou que está a decorrer. A forma desse aviso pode ser: na consola local, numa

consola remota, SNMP, correio electrónico, SMS, etc.

Anomalia (anomaly)

A maioria dos IDSs accionam uma alarme quando certos eventos coincidem com a

assinatura de um ataque conhecido, os IDSs baseados nas anomalias vão construindo

um perfil das actividades do host ou da rede ao longo do tempo. Quando um evento está

fora desse perfil, é accionado um alarme. Por exemplo, quando alguém ganha privilégios

de administrador, demasiados logins falhados, etc.

ArachNIDS (Advanced Reference Archive of Current Heuristics for NIDS)

Desenvolvido por White Hats da Max Vision é um base de dados de perfis de ataque

usada para dinamicamente criar assinaturas que são compatíveis com vários produtos

NIDSs.

ARIS (Attack Registry & Intelligence Service)

Um serviço oferecido pela SecurityFocus que permite que redes com ligação à Internet

passem anonimamente os seus eventos para a SecurityFocus. Esta utilizam estes dados

para formarem uma análise estatística e verificarem tendências, que depois é publicado

na Internet.

Assinaturas (signatures)

O que acciona os alarmes dos IDSs num evento.

Ataques (atacks)



Podem ser considerados de tentativas de penetração indevida num sistema ou de tentar

tornear a segurança de um sistema de modo a obter informação, modificar informação ou

interromper o normal funcionamento da rede.

Cavalos de Tróia (trojans)

Refere-se a programas que aparentam ser legítimos, mas que contêm código maligno.

Quando estes são executados, o referido código é também executado, sem que os

utilizadores se apercebam.

CVE (Common Vulnerabilities and Exposures)

Base de dados que contem os nomes standard de ataques conhecidos, possibilitando a

sua uniformização nos diferentes produtos IDSs.

Dessincronizarão (desynchronization)

(ver Evasão)

Detecção de Padrões (pattern matching/string matching)

A detecção de padrões consiste em encontrar uma ou mais ocorrências de uma cadeia

de caracteres dentro de um texto

DoS (Denial of Service)

O objectivo deste tipo de ataque é de interromper um serviço, de modo a que este não

possa ser usado por que o utiliza. Existem muitas formas de alcançar este proposito,

como por exemplo, buffer overflow e flooding (imundação) aos recursos dos sistemas.

DDoS (Distributed DoS)

Um ataque DoS tradicional por vezes não consegue gerar grandes quantidades de dados

para conseguir os seus objectivos. A ideia é distribuir a origem desse ataque por vários

hosts.

Evasão (evasion)

É o processo de perpetrar um ataque sem que o IDSs o detecte.



Exploits

Exploração de uma vulnerabilidade do sistema.

Falsos Negativos (false negatives)

Situação que ocorre quando um ataque não é detectado pelos IDSs.

Falsos Alarmes (false alarms/false positives)

Situação que ocorre quando os IDSs geram um alarme, mas não está em curso nenhum

ataque.

Firewall Dispositivo de segurança que permite a filtragem das unidades de tráfego (endereços e

portas) e, também servem de gateway de circuitos e de aplicações.

Fragmentação (fragmentation)

Se uma unidade de tráfego é demasiado grande, vai ser dividida em bocados mais

pequenos (fragmentos). Também pode ocorrer quando os redes têm diferentes máximos

de unidades de transmissão (MTU). Por exemplo, o MTU da Token Ring é de 4464 e o da

Ethernet é de apenas 1500.

HIDSs (Host Intrusion Detection Systems)

IDSs que se baseiam no host, que monitorizam os registos do sistema.

Modo Promíscuo (promiscuous)

Modo que permite que todas as unidades de tráfego que passam no segmento, sejam

capturadas para se proceder à respectiva análise.

NIDSs (Network Intrusion Detection Systems)

IDSs que se baseiam na rede, que monitorizam as unidades de tráfego.

NNIDSs (Network Node Intrusion Detection Systems)

IDSs híbrido residente nos host e que analisa as unidades de tráfego à medida que estas

vão atravessando a stack dos protocolos.



Anexo B: Código dos Algoritmos

Algoritmo de Força Bruta

void BF(char *x, int m, char*y, int n){ int i, j; /*searching*/ for(j = 0; j <= n - m; ++j){ for(i = 0; i < m && x[i] == y[i + j]; ++i); if (i >= m) OUTPUT(j); } }



Algoritmo Boyer-Moore

void preBmBc(char *x, int m, int bmBc[]){ int i; for(i = 0; i < ASIZE; ++i){ bmBc[i] = m; } for(i = 0; i < m – 1 ; ++i){ bmBc[x[i]] = m – i – 1; } } void suffixes(char *x, int m, int *suff){

int f, g, i; suff[m – 1] = m; g = m – 1; for(i = m – 2; i >= 0; --i){

if(i > g && suff[i + m – 1 – f ] < i – g ){ suff[i] = suff[i + m – 1 – f];

}else{ if(i < g){

g = i; } f = i; while(g >= 0 && x[g] == x[g + m – 1 – f ]){

--g; } suff[i] = f – g;

} }

} void preBmGs(char *x, int m int bmGs[]){

int i, j, suff[XSIZE]; suffixes(x, m, suff); for(i = 0; i < m; ++i){

bmGs[i] = m; } j = 0;



for(i = m – 1; i >= -1; -- i){ if(i == -1 || suff[i] == i + 1){

for(; j < m – 1 – i; ++j){ if(bmGs[j] == m){

bmGs[j] = m – 1 – i ; }

} }

} for(i = 0; i <= m – 2; ++i){

bmGs[m – 1 – suff[i]] = m – 1 – i; }

} void BM(char *x, int m, char *y, int n){

int i, j, bmGs[XSIZE], bmBc[ASIZE]; /*preprocessing*/ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /*searching*/ j = 0; while(j <= n – m){

for(i = m – 1; i >= 0 && x[i] == y[i + j]; --i); if(i < 0){

OUTPUT(j); j += bmGs[0];

}else{ j += MAX(bmGs[i], bmBc[y[i + j]] – m + 1 + i);

} }

}



Algoritmo Horspool

void preBmBc(char *x, int m, int bmBc[]){ int i; for(i = 0; i < ASIZE; ++i){ bmBc[i] = m; } for(i = 0; i < m – 1 ; ++i){ bmBc[x[i]] = m – i – 1; } } void HORSPOOL(char *x, int m, char *y, int n){

int j, bmBc[ASIZE]; /*preprocessing*/ preBmBc(x, m, bmBc); /*searching*/ j = 0; while(j <= n – m){

c = y[j + m – 1]; if(x[m – 1] == c && memcmp(x, y + j, m – 1) == 0){

OUTPUT(j); j += bmBc[c];

} }

}



Algoritmo Aho-Corasick

PRE-AC(X, k) criar um novo nó para a raiz /* criar ciclos na raiz da árvore */ para cada a ∈ Σ /* alfabeto */ filho(raiz, a) <- raiz /* coloca cada padrão na árvore */ para cada i <- 0 até k - 1 COLOCAR(X[i], raiz) /* completa árvore com as ligações falhadas e */ /* completa a saída */ COMPLETAR(raiz) devolve raiz COLOCAR(x, raiz) r <- raiz i <- 0 /* segue destinos dos nós */ enquanto i < comprimento(x) e filho(r, x[i]) <> INDEFINIDO

e filho(r, x[i]) <> raiz r <- filho(r, x[i]) i <- i + 1

/* criar novos destinos */ enquanto i < comprimento(x) criar um novo nó s filho(r, x[i]) <- s r <- s i <- i + 1 saída(r) <- x



COMPLETAR(raiz) q <- FILA_VAZIA l <- lista dos destinos (raiz, a, p) para cada a ∈ Σ e nó p <> raiz enquanto l <> VAZIA (r, a , p) <- PRIMEIRO(l) l <- PROXIMO(l) COLOCAR_FILA(q, p) falha(p) <- raiz enquanto q<>VAZIA r <- RETIRAR_FILA(q) l <- lista dos destinos (raiz, a, p) para cada a ∈ Σ e para qualquer nó p enquanto l <> VAZIA (r, a , p) <- PRIMEIRO(l) l <- PROXIMO(l) COLOCAR_FILA(q, p) s <- falha(r) enquanto filho(s, a) = INDEFINIDO s <- falha(s) falha(p) <- filho(s, a) saída(p) <- saída(p) ∪ saída(filho(s, a)) AC(y, n, X, K)

/* texto, comp. texto, conj. padrões, num padrões */ /* pré-processamento */ r <- PRE-AC(X, k) /* busca */ para cada i <- 0 até n – 1 enquanto filho(r, y[i]) = INDEFINIDO r <- falha(r) r <- filho(r, y[i]) se saída(r) <> VAZIO então SAIDA(saída(r), i)

Documents

Detecção de Padrões - Departamento de Engenharia ...paf/proj/Set2002/Sistemas Deteccao Intrusoes.pdf · 1.1.1 Definição ... 1 O Snort é um produto opensource de utilização