Árvores de Decisão baseadas nas entropias de Shannon

Árvores de Decisão baseadas nas entropias de Shannon,
Rényi e Tsallis para Sistemas Tolerantes a Intrusão
Christiane Ferreira Lemos Lima
Departamento de Ensino
Instituto Federal do Maranhão
Campus Maracanã
São Luís, MA - Brasil
[email protected]
Francisco Marcos de Assis
Departamento de Engenharia Elétrica
Universidade Federal de Campina Grande
Campina Grande, PB - Brasil
[email protected]
Abstract—Este artigo descreve um estudo comparativo do uso das
entropias de Shannon, Rényi e Tsallis, com o objetivo de encontrar
alternativas mais eficientes aplicadas a um Sistema Tolerante a
Intrusões. Árvores de Decisão têm sido utilizadas em modelos de
classificação de problemas relacionados à detecção de intrusos em redes
de computadores, apresentando bons resultados. Um algoritmo muito
utilizado é o C4.5 que aplica a entropia de Shannon na escolha dos
atributos que melhor dividem os itens de dados dentro de suas classes.
Entretanto, outras formulações de entropia podem ser aplicadas visando
garantir uma melhor generalização nos que se refere aos critérios de
divisão. Os resultados experimentais demonstram que as entropias de
Tsallis e Rényi aplicadas a este problema, constroem árvores mais
compactas e eficientes, se comparadas com a entropia de Shannon.
Palavras-Chaves: Entropias de Shannon, Rényi e Tsallis; Sistema
Tolerante a Intrusão; árvore de Decisão.
I. I NTRODUÇÃO
Segundo Crosbie e Spafford [1], uma intrusão pode ser definida
como sendo um conjunto de ações que tentam comprometer a
integridade, confidencialidade ou disponibilidade de recursos em um
sistema computacional.
Geralmente, as intrusões são causadas por usuários não autorizados
tentando acessar um sistema através da rede interna ou externa ou
por usuários legítimos tentando abusar de seus privilégios, motivados por: ganhos financeiros, vingança, necessidade de aceitação ou
respeito, idealismo, curiosidade ou busca de emoção, aprendizado ou
espionagem industrial. Portanto, os sistemas devem ser capazes de
tolerar automaticamente intrusões e continuar operacionais, sem que
sejam necessárias ações de reparação por parte de administradores de
sistema, porque essas são tipicamente demoradas e potencialmente
introduzem erros.
Nesse contexto, torna-se imprescindível a construção de sistemas
que apliquem conceitos e técnicas de tolerância a falhas que visem
dar apoio e agilidade no processo de tomada de decisão na ocorrência
de um incidente de intrusão, principalmente no caso de ausência
de administrador de segurança, em decorrência de que a maioria
ocorre fora do expediente normal das corporações e um invasor pode
permanecer durante semanas em um ambiente, estudando a melhor
forma de efetuar o acesso indevido à rede, sem que seja identificado.
Nos Sistemas Tolerantes a Intrusão (STI), uma falha pode ser uma
intrusão, uma vulnerabilidade, um ataque, uma falha de projeto ou
falha de configuração [2] [3]. Com base em Jalote [4], um defeito
no sistema pode ocorrer quando o seu comportamento desvia do
que é requerido pelas suas especificações, ou seja, um sistema está
defeituoso quando não pode fornecer o serviço desejado. Se há uma
falha no sistema, então existe uma seqüência de ações que podem ser
executadas pelo sistema até a ocorrência de um erro. A não ser que
Cleonilson Protásio de Souza
Departamento de Engenharia Elétrica
Universidade Federal da Paraíba
João Pessoa, PB - Brasil
[email protected]
medidas preventivas sejam empregadas, a conseqüência de um erro
será um defeito. Contudo, tem-se que o ponto de partida de qualquer
atividade de tolerância a falhas é a detecção de erros.
Falhas e defeitos podem não ser diretamente observados, mas
devem ser deduzidos através da presença de erros. Portanto, para que
um esquema de tolerância a falhas seja eficiente, existe uma relação
direta com o mecanismo de detecção de erro empregado, ou seja,
quanto mais eficiente for a detecção, mais eficiente será o processo
de tolerância [4].
As pesquisas na área de detecção de intrusos seguem por várias
linhas de ação. O conceito de detecção de intrusos foi proposto
pela primeira vez por James Anderson [5], sendo difundido somente
em 1987, com a publicação do artigo Um Modelo de Detecção
de Intrusão por Dorothy Denning [6]. Nos anos seguintes, vários
modelos foram apresentados na tentativa de aumentar a segurança
de um computador ou rede de computadores. Dentre eles, têm-se os
baseados em árvore de decisão, que apresentam bons resultados, com
baixas taxas de falso positivo e falso negativo [7] [8] [9].
Atualmente há diversos algoritmos de árvore de decisão implementados, sendo os mais populares provavelmente o ID3 (Induction
of Decision Tree), desenvolvido por Quinlan [10] com base no CLS
(Concept Learning System) [11] e seu sucessor, o C4.5 [12]. Ambos
constroem a árvore num processo top-down, selecionando o atributo
de teste apropriado para cada nó de decisão da árvore, através do
cálculo de sua entropia. A introdução da entropia no processo de
construção de árvores de decisão tem como objetivo a criação de
árvores menores e mais eficazes na classificação [13]. A redução do
tamanho da árvore depende da seleção dos atributos.
Várias estratégias podem ser utilizadas para determinar qual atributo de teste será usado em cada nó da árvore e, nesse contexto,
outras formulações de entropia podem ser aplicadas na escolha dos
atributos, visando garantir uma melhor generalização nos que se
refere aos critérios de divisão. Portanto, neste artigo é realizado um
estudo comparativo do uso das entropias de Shannon [14], Rényi [15]
e Tsallis [16] [17] com o objetivo de encontrar alternativas mais
eficientes no uso de árvores de decisão aplicadas na detecção de
intrusos em redes de computadores.
O artigo está organizado da seguinte forma: na Seção II são
abordados os conceitos relevantes sobre as formulações de entropia e
o uso da divergência Jensen-Rényi como informação mútua. Na Seção
III é descrito o processo de construção de uma árvore de decisão. O
ambiente de experimento é apresentado na Seção IV e os resultados
são analisados na Seção V, seguido da Conclusão e trabalhos futuros
desta pesquisa.
II. F ORMULAÇÕES DE E NTROPIA
O conceito de entropia foi associado à quantidade de informação
de uma mensagem como uma medida estatística que obedece a um
conjunto de axiomas e utilizado no estudo da Teoria da Informação
por Claude Shannon em 1948 [14], baseada na expressão de entropia
de Boltzmann-Gibbs [18] [19].
Com base no trabalho de Shannon [14], a entropia de uma variável
aleatória X comPuma distribuição discreta de probabilidade pi =
{p1 , p2 , ..., pk }, ki=1 pi = 1, associada aos resultados possíveis de
um acontecimento é dada por:
H(X) = −
k
X
pi log2 pi bits/símbolo
(1)
i=1
A entropia binária de uma variável aleatória pode ser interpretada
como sendo o "menor número médio de perguntas binárias (sim ou
não) necessário para identificar a saída de uma fonte (X = x).
Sendo X a saída de uma fonte discreta sem memória, o esquema de
perguntas ótimo equivale à codificação mais eficiente para a fonte.
Shannon definiu outro conceito básico na Teoria da Informação
em relação à medida de dependência estatística entre duas variáveis
aleatórias, chamada de informação mútua. Quanto maior for a informação mútua, maior será a redução da incerteza, significando que
mais relacionadas são essas variáveis.
Sejam X e Y duas variáveis aleatórias com distribuição conjunta
de probabilidades p(x, y) e distribuições marginais p(x) e p(y), a
informação mútua I(X; Y ), definida por Shannon, é a divergência
de Kullback-Leibler (entropia relativa) entre a distribuição conjunta
p(x, y) e o produto das distribuições marginais p(x)p(y) [20].
I(X; Y ) = D[p(x, y); p(x)p(y)]
(2)
onde D[p(x,y);p(x)p(y)] é a divergência Kullback-Leibler que resulta
em:
I(X; Y ) =
X
x,y
p(x, y)log
p(x, y)
p(x)p(y)
(3)
A informação mútua expressa em termos da entropia de Shannon
é dada por:
I(X; Y ) =
=
=
H(X) + H(Y ) − H(X, Y )
H(X) − H(X|Y )
H(Y ) − H(Y |X)
Rα (X) =
k
X
1
log
pα
i
1−α
i=1
(5)
P
onde ki=1 pi = 1 e limα→1 Rα (X) = H(X).
Para α > 1, a entropia de Rényi não é côncava nem convexa, mas
para α ∈ (0, 1) é côncava e tende à entropia de Shannon quando
α → 1. Dessa forma:
Rα (X) ≥ H(X), ∀α ∈ (0, 1)
A diferença entre a entropia de Rényi e a entropia de Shannon
é que a de Rényi não satisfaz o quarto postulado básico, que é a
propriedade recursiva. Todas as demais propriedades são satisfeitas,
incluindo a propriedade aditiva.
A divergência de Rényi pode também ser usada como uma
medida de informação mútua entre variáveis aleatórias, em função
da distribuição conjunta e a distribuição do produto das marginais.
Entretanto, a mesma não pode ser expressa em termos de entropia,
como é feita na entropia de Shannon (Eq. 4).
Dessa forma, nessa pesquisa, a informação mútua foi substituída
pela divergência Jensen-Rényi [21], também chamada de diferença
α-Jensen [22], que é uma medida que usa a entropia de Rényi
generalizada para medir a dependência estatística entre um número
arbitrário de distribuição de probabilidade, utilizada com sucesso
em processamento de imagem, segmentação e classificação. É uma
função mais flexível a qual é parametrizada por uma quantidade
positiva α e tem muitas propriedades, dentre elas, continuidade, nãonegatividade e convexidade. Sua fórmula geral é:
w
JRα
(p1 , p2 , ..., pk )
= Rα
k
X
i=1
!
wi pi
−
k
X
representando a redução de incerteza sobre X devido ao conhecimento de Y e é fácil provar que é simétrica e não negativa.
A entropia de Shannon encontrou muitas aplicações não somente
na engenharia, mas também em diversas áreas tais como a estatística,
economia, no reconhecimento de padrões, aprendizado de máquina
e sistemas dinâmicos, entre outras. Nessa perspectiva, dentro da
Teoria da Informação foram formuladas propostas de generalização
da entropia, algumas claramente relacionadas, chegando a reduziremse à mesma expressão em alguns casos particulares, tais como a
formulação de Rényi [15] e Tsallis [16] [17].
Em 1961, Alfréd Rényi evidenciou, através de um conjunto de
postulados, que outras quantidades poderiam ajustar-se igualmente
ou talvez melhor a uma medida de informação, surgindo a idéia de
entropia generalizada. Rényi propôs uma entropia parametrizada α
(α > 0 e α 6= 1) que contém a entropia de Shannon como caso
limite, chamada entropia de Rényi.
wi Rα (pi )
(7)
i=1
Pk
onde
i=1 wi = 1, wi ≥ 0, Rα é a entropia de Rényi e w =
(w1 , w2 , ..., wn ) é um vetor peso.
Para 0 < α < 1, a divergência Jensen-Rényi é não-negativa,
simétrica e uma função convexa de p1 , p2 , ..., pk . Portanto, a informação mútua, chamada α-informação mútua, pode ser generalizada,
usando a entropia de Rényi.
Iα (X; Y ) = Rα (X) − Rα (X|Y )
(4)
(6)
(8)
Alguns anos depois, Constantino Tsallis [17] definiu uma forma
generalizada de entropia, tendo como caso particular a entropia de
Boltzmann-Gibbs-Shannon.
!
k
X
1
α
Sα (X) =
1−
pi
(9)
α−1
i=1
onde α ≥ 0 e limα→1 Sα (X) = H(X).
Para α > 1, a informação mútua de Tsallis é definida como [23]:
Iα (X; Y ) = Sα (X) − Sα (X|Y )
(10)
A entropia de Tsallis tem uma concavidade bem definida para todos
os valores de α, sendo côncava quando α > 0 e convexa quando
α < 0.
As entropias de Shannon, Rényi e Tsallis atingem um extremo no
caso de equiprobabilidade, mas este nem sempre traduz o máximo
da entropia. Para α > 0, a entropia de Rényi e Tsallis atingem o
máximo. Nos demais casos, atingem o mínimo.
A entropia de Tsallis satisfaz algumas das propriedades da entropia
de Shannon e Rényi. As principais diferenças entre estas, encontramse, fundamentalmente, na aditividade e na convexidade. Enquanto a
entropia de Shannon e Rényi verificam a aditividade, a entropia de
Tsallis verifica a α-aditividade. A entropia de Shannon é côncava,
enquanto as de Rényi e Tsallis nem sempre são, pois dependem de
seus parâmetros. Além disso, a entropia de Shannon e de Tsallis não
são aplicáveis a distribuições incompletas, ao contrário de Rényi.
Na entropia de Shannon, os eventos com probabilidade muito
alta ou muito baixa não têm grande peso no valor da entropia.
Entretanto, na entropia de Tsallis, para valores de α > 1, os eventos
com probabilidades mais elevadas contribuem mais para o valor de
entropia do que os eventos de probabilidade baixa. Estabelecendo um
paralelo com a entropia de Shannon, a média ponderada da entropia
é substituída por uma média de potência α. Assim, uma mudança do
valor de α altera a contribuição relativa de um dado evento para a
soma total. Quanto mais elevando for α, mais peso têm os eventos
de probabilidade elevada, na soma total.
III. Á RVORES DE D ECISÃO
Uma Árvore de Decisão é uma estrutura de dados, sendo percorrida iniciando por um nó raiz até uma folha. Cada nó interno
(também chamado de nó de decisão) especifica um atributo de teste
(previsor). Para cada resultado do teste, existe uma ligação (ramo
ou aresta) para cada subárvore. Cada subárvore possui a mesma
estrutura que a árvore. Um nó folha representa uma classificação ou
resultado predito.
Segundo Breiman et al. [24], árvores de decisão são modelos
utilizados em problemas de aprendizado de máquina e predição
supervisionada, em que o referido modelo é induzido a partir de um
conjunto de instâncias de treinamento, com as classes previamente
conhecidas. Cada instância é composta por um conjunto de atributos
de entrada que são utilizados para predizer uma classe em particular,
indicada por um atributo objetivo.
O mapeamento que ocorre entre as entradas e a saída é denominado
de modelo preditivo, que pode ser representado numa estrutura
semelhante a uma árvore ou expresso através de um conjunto de
regras se-então, sendo, portanto, de fácil interpretação por seres
humanos. A vantagem de se utilizar esse algoritmo é que a estrutura
criada pode ser aplicada em novos casos em que o resultado é
desconhecido.
A escolha dos atributos influencia diretamente no tamanho e
na capacidade de generalização da árvore. Existem vários métodos
usados na seleção de um bom subconjunto de atributos [25]. Em Ben
Bassat [26], uma classificação de regras de avaliação de atributos é
apresentada em três categorias, conforme a seguir:
•
•
•
Regras derivadas da teoria da informação, que usam, por
exemplo, o cálculo de entropia e informação mútua de Shannon
são bastante utilizadas no reconhecimento de padrões [27];
Regras derivadas de medidas de distância entre a distribuição
de probabilidade das classes, por exemplo, uso do índice
Gini [24];
Regras derivadas de medidas de dependência estatística entre
duas variáveis aleatórias [25].
Entretanto, existem muitos critérios de seleção de atributos que
não se enquadram perfeitamente em uma das categorias definidas na
Taxonomia de Ben Bassat, mas usam uma combinação das mesmas
com o objetivo de encontrar melhores alternativas na construção de
árvores de decisão.
A. Construindo árvores de decisão
O algoritmo ID3 [10] constitui uma das referências base dos
algoritmos atuais de indução de árvores de decisão. Desenvolvido
com vista ao tratamento de problemas contendo apenas características
discretas, a sua estrutura básica é iterativa e muito simples no que
se refere ao tratamento de problemas sem erros de classificação nos
dados dos treinos ou atributos sem valores.
O algoritmo C4.5[12] estende o ID3, sendo capaz de tratar conjuntos de treinamentos com registros contendo valores desconhecidos
para alguns atributos, tratar atributos com intervalos discretos e
contínuos e realizar o procedimento de poda, o qual é responsável
por remover as comparações redundantes ou remover subárvores para
melhorar o desempenho da árvore de decisão. Essas características
motivaram seu uso nesta pesquisa.
A criação da árvore de decisão, baseada no algoritmo C4.5, é
realizada através de um processo recursivo, a partir da raiz, com
base nos valores que melhor dividem os itens de dados dentro de suas
classes. O algoritmo C4.5 usa, como padrão, a medida de entropia
de Shannon. Esse processo é continuado até gerar uma árvore de
decisão que classifique as instâncias de treinamento ou até que todos
os atributos sejam usados.
A seguir será ilustrado o processo de criação da árvore de decisão,
usando o algoritmo C4.5, com base na entropia de Shannon, podendo
ser substituída pelas entropias de Rényi e Tsallis, seguindo suas formulações e obedecendo suas restrições apresentadas para os valores
de α.
1) Inicialização. Seja |T | o número total de instâncias de
treinamento, representando um conjunto de classes C =
{c1 , c2 , ...., ck }, onde k é o número de classes possíveis (k ≥
2). Cada instância é formada por um conjunto de n atributos
A = A1 , A2 , ..., An , sendo que seus valores Ai = {a1 , ..., am }
definem a classe ck .
2) Determinar o esquema eficiente de perguntas. "Qual o
melhor atributo a ser utilizado como nó da árvore"? O algoritmo
C4.5 [12] examina todos os atributos previsores e escolhe o
i)
atributo Ai que maximize a razão I(C;A
, para que o teste
H(Ai )
escolhido tenha um ganho de informação pelo menos maior que
a média de ganho de informação sobre todos os testes avaliados,
para rotular o nó atual da árvore. O atributo Ai usado como nó
da árvore de decisão irá dividir o conjunto de treinamento T
em N partições, com base nos valores do atributo escolhido. O
processo é repetido de forma recursiva para dar continuidade
à construção da árvore de decisão nos subconjuntos residuais
T1 , ..., TN .
• Calcular a entropia das classes. A entropia total da classificação é a quantidade de informação esperada necessária para
especificar um conjunto de classes. Tomando como base um
conjunto T de instâncias de treinamento, então f req(cj , T )
é o número de instâncias em T que apontam para a classe
cj . Portanto, a entropia de C para k classes é dada por [12]:
H(C) =
=
•
−
Pk
j=1
P
− kj=1
f req(cj ,T )
|T |
log2
f req(cj ,T )
|T |
p(cj ) log2 p(cj )
(11)
Calcular a informação mútua. Para cada atributo Ai , a
informação mútua I(C; Ai ) mede a redução da entropia das
classes ocasionada pela divisão das instâncias T em função
da escolha de um atributo Ai .
I(C; Ai ) = H(C) − H(C|Ai )
(12)
Table I
I DENTIFICAÇÃO DE ATAQUES POR CATEGORIA
onde a informação esperada requerida para a árvore com o
atributo Ai , com valores a1 , ..., am , selecionado como nó da
árvore é obtida através da entropia condicional, H(C|Ai ).
H(C|Ai ) =
m
X
p(av )H(C|Ai = av )
(13)
p(cj |av ) log2 p(cj |av )
(14)
v=1
em que
H(C|Ai = av ) =
k
X
DOS
PROBING
R2L
U2R
back (1026)
land (11)
neptune(10401)
pod (69)
smurf (7669)
teardrop (15)
ipsweep (586)
nmap (151)
portsweep (155)
satan (16)
spy (4)
ftp-write (8)
guess-passwd(53)
imap (11)
multihop (11)
phf (5)
wareszclient (60)
warezmaster (20)
buffer-overflow(11)
loadmodule (10)
perl (3)
rootkit (7)
j=1
•
sendo p(cj |av ) a probabilidade condicional de que a classe
é cj quando o atributo Ai tiver valor av .
Calcular a razão do ganho. O objetivo é escolher o atributo
que permita maximizar a razão (I(C; Ai ))/(H(Ai )), sendo
H(Ai ) a quantidade de informação em potencial gerada pela
divisão de T em N subconjuntos por um atributo Ai , dada
pela expressão a seguir:
H(Ai ) = −
N
X
pv log2 pv
(15)
v=1
sendo pv a probabilidade do ramo v. Se atributo for discreto,
será criado um ramo para cada valor de atributo. Senão,
se um atributo Ai assume valores reais, é gerado um teste
binário cujos resultados são Ai ≤ av e Ai > av e nesse caso,
será escolhido o maior valor do conjunto de treinamento
T que não exceda o ponto médio calculado (por exemplo:
(av +a(v+1) )
, assegurando que todos os valores que aparecem
2
na árvore de fato ocorram nos dados.
• Escolher atributo. O atributo que maximizar a razão do
ganho será escolhido para ser o nó da árvore.
• Estender a árvore. Adicionar um ramo para cada valor
a1 , a2 , ..., av do atributo escolhido Ai como nó da árvore, de
acordo com seu tipo (contínuo ou discreto). Nesse momento,
o conjunto de treinamento T é subdividido T1 , T2 , ..., Tv
partições, ou seja, cada subdivisão da árvore terá um novo
conjunto de treinamento Tv , contendo todas as instâncias
em T que possuem como resultado daquele teste o valor
av . Para cada ramo criado, se as instâncias em Tv são da
mesma classe, então associar essa classe a uma folha, senão,
voltar ao passo Calcular a entropia das classes, usando o
conjunto Tv como nova instância de treinamento.
3) Finalização. O modelo gerado é a solução do problema proposto.
IV. A MBIENTE DE EXPERIMENTOS
O objetivo principal desta pesquisa consiste na realização de um
estudo comparativo do uso das entropias de Shannon, Renyi e Tsallis
em projetos de árvores de decisão aplicáveis em redes de computadores tolerantes a intrusões. Dessa forma, pode-se classificar o tráfego
de rede como normal ou com o indicativo de um determinado tipo
de ataque.
Para treinamento e teste dos modelos, foi utilizada a ferramenta
WEKA (Waikato Environment for Knowledge Analysis) desenvolvida
em linguagem Java, pela Universidade de Waikato na Nova Zelândia [28]. O algoritmo C4.5 é implementado nessa ferramenta através
do algoritmo J48, sendo este modificado através dos cálculos das
entropias de Rényi e Tsallis, obedecendo as devidas restrições em
relação a α.
Nessa pesquisa foi utilizado um subconjunto da base de dadosdisponibilizada na competição internacional de mineração de dados,
Knowledge Discovery and Data Mining Competition - KDD Cup
99 [29] contendo um conjunto padrão de dados para serem auditados,
incluindo uma grande variedade de intrusões simuladas durante nove
semanas em uma rede militar de computadores. Devido ao grande
volume de dados e com o intuito de reduzir o custo computacional,
selecionou-se aleatoriamente um subconjunto de 22.653 instâncias,
de um total de 494.021 [30].
Essa base de dados contém 2.351 registros de conexões indicando
tráfego de rede normal e 20.302 registros contendo 22 tipos de
ataques identificados, conforme ilustrado na Tabela I. Para cada
registro, tem-se 41 atributos para caracterizarem as assinaturas de
ataque e 1 atributo-objetivo (indicando a qual classe pertence a
instância), utilizado para classificar o tipo de ataque. Em [31] é feita
uma descrição resumida desses ataques.
Serão utilizados atributos para reconhecer as seguintes categorias
de ataques:
•
•
•
•
User to Root (U2R) - quando uma pessoa que possui acesso
autorizado como um usuário e tenta obter acesso como superusuário (root). Ex.: buffer overflow.
Remote to Local (R2L) - quando uma pessoa, em uma máquina
remota, tenta obter acesso ao servidor local. Ex.: guess-passwd.
Probing - um intruso varre uma rede em busca de informação ou
para encontrar vulnerabilidades conhecidas para explorar. Ex.:
ipsweep.
DOS - ataques de negação de serviço. O objetivo do invasor é
causar a indisponibilidade do serviço alvo, seja através do consumo de recursos computacionais como memória, processador
ou rede. Ex.: back.
Um problema que pode ocorrer na construção de uma árvore é
que a mesma pode ficar sobre-ajustada (overfitting) aos dados de
treinamento e, assim, diminuir a sua capacidade de generalização.
Para evitar tal situação e para garantir que fossem construídas árvores
mais compactas e com menos folhas, na simulação foi executado o
procedimento de poda da árvore.
O método de validação cruzada com dez folds foi utilizado na
simulação para determinar o coeficiente ótimo a ser utilizado na
árvore de decisão. Exaustivos testes em diversas bases de dados
demonstram que o teste de validação cruzada com dez folds é um
teste adequado para se encontrar a estimativa de erro na classificação
correta das instâncias. Esse método consiste em dividir aleatoriamente
em dez partes nas quais as classes são representadas aproximadamente na mesma proporção da base de dados completa. O esquema de
aprendizagem é treinado com nove folds e o restante (1/10) é usado
para teste do modelo. O teste é realizado dez vezes em diferentes
bases de dados e, então, o resultado é a média das estimativas de
erro encontradas.
Table II
PARA A ENTROPIA DE R ÉNYI : R ESULTADO G ERAL PARA O CONJUNTO DE
INSTÂNCIAS T
α
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
Classificação
Correta
99,687%
99,6601%
99,6468%
99,6204%
99,691%
99,6822%
99,6424%
99,691%
99,607%
Falso
Positivo
0,7656%
0,9783%
1,0634%
1,1910%
0,7656%
0,7231%
0,8507%
0,7656%
1,1910%
Falso
Negativo
0,1330%
0,1281%
0,1281%
0,1428%
0,0837%
0,0985%
0,1478%
0,1133%
0,1822%
Número
de Folhas
391
453
454
273
189
128
259
380
450
Tamanho
da árvore
456
517
519
339
244
186
313
434
509
Table III
PARA A ENTROPIA DE S HANNON : R ESULTADO G ERAL PARA O CONJUNTO
DE INSTÂNCIAS T
-
Classificação
Correta
99.638%
Falso
Positivo
0.8932%
Falso
Negativo
0,1675%
Número
de Folhas
533
Além disso, das 65 instâncias classificadas erroneamente, 41 foram
identificadas como suspeitas, o que pode ser considerado positivo em
sistemas que apenas classificam conexões como normais ou suspeitas.
O uso da entropia de Rényi também apresentou melhores resultados
do que os testes realizados com a entropia de Shannon, por exemplo,
ao ser utilizado α = 0, 5. Entretanto, os resultados encontrados
com as entropias de Rényi e Tsallis foram mais significativos
considerando-se a redução no tamanho e número de folhas da árvore.
Um exemplo simplificado e meramente ilustrativo de árvore de
decisão que pode ser gerado pelo modelos simulados a partir do
conjunto de instâncias T é mostrado na Figura 1. Nesse exemplo é
possível visualizar um modelo aplicado na detecção de ataques do
tipo DOS.
Tamanho
da árvore
593
V. R ESULTADO E XPERIMENTAL
As entropias de Rényi e Tsallis contêm um coeficiente α que
pode ser usado para ajustar a sensibilidade em relação à distribuição
de probabilidade, sendo esse coeficiente diferente em cada base
de treinamento. Nesse contexto, como as entropias generalizadas
oferecem diferentes compromissos entre a puridade dos nós e a
informação mútua, buscou-se encontrar coeficientes ótimos para as
bases de treinamento testadas.
Nas Tabelas II, III e IV são apresentados os resultados comparativos obtidos com os respectivos percentuais de instâncias classificadas corretamente, o percentual de falsos positivos (dados normais
classificados erroneamente como suspeitos) e falsos negativos (dados
suspeitos classificados erroneamente como normais), o número de
folhas e o tamanho da árvore para os valores de α testados.
Para o conjunto de treinamento e testes adotado nesta pesquisa, os
melhores resultados experimentais, dentre todos os algoritmos testados com seus respectivos valores de α e tomando como referência
apenas a classificação correta das conexões normais ou suspeitas (independente do tipo de intrusão e se foram corretamente classificadas
ou não pelo seu tipo específico) foram obtidos com a entropia de
Tsallis, com apenas 0, 2869% de erro na classificação das instâncias
testadas, com 0, 4679% de falso positivo e um percentual de falso
negativo na faixa de 0, 0690%, com uma considerada redução no
tamanho e número de folhas da árvore, para o valor de α = 1, 8.
Table IV
PARA A ENTROPIA DE T SALLIS : R ESULTADO G ERAL PARA O CONJUNTO
DE INSTÂNCIAS T
α
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2
2,1
3
Classificação
Correta
99,6248%
99,6601%
99,6292%
99,638%
99,638%
99,691%
99,7042%
99,7131%
99,6998%
99,691%
99,6866%
99,6733%
Falso
Positivo
0,6806%
0,8082%
0,8932%
0,7231%
0,6806%
0,5104%
0,5104%
0,4679%
0,5104%
0,5104%
0,5104%
0,5104%
Falso
Negativo
0,2217%
0,1872%
0,1872%
0,1872%
0,1872%
0,5530%
0,0690%
0,0690%
0,0739%
0,0837%
0,0837%
0,0985%
Número
de Folhas
393
509
571
572
571
170
166
167
167
167
167
168
Tamanho
da árvore
443
557
617
619
617
219
211
213
213
213
213
215
Figure 1.
Exemplo simplificado de árvore de decisão
Com base nos tipos de ataques apresentados na Tabela I, é possível
verificar, por exemplo, que o ataque do tipo land foi modelado
contendo 8 instâncias pertencentes a uma folha e 3 instâncias pertencente a outra folha, totalizando 11 instâncias utilizadas no processo
de treinamento. Isso significa que para o mesmo ataque, pode-se
ter diferentes assinaturas, gerando árvores com número de folhas
superior ao número de classes. Assim, o número de nós da árvore
depende do domínio de aplicação e da base de dados de treinamento.
VI. C ONCLUSÃO E TRABALHO FUTURO
Nesta pesquisa, buscou-se encontrar alternativas mais eficientes,
baseadas na Teoria da Informação, para serem utilizadas como critério
de divisão do algoritmo de árvore de decisão C4.5, gerando modelos
para serem aplicados na detecção de erros em Sistemas Tolerantes à
Intrusão.
Os resultados experimentais, tomando-se uma base de dados
artificial de tráfego de rede contendo variados tipos de intrusões,
demonstram que a entropia de Tsallis e Rényi, com os parâmetros
adequados, se adaptam bem ao problema proposto, construindo
árvores mais compactas e eficientes, de forma mais rápida, obtendo
resultados com menores percentuais de erro de classificação, falso
positivo e falso negativo, se comparados à entropia de Shannon. O
uso da divergência Jensen-Rényi como informação mútua aplicadas
na construção de árvores de decisão foi uma proposta inovadora nesta
pesquisa.
Como trabalho futuro para esta pesquisa, propõe-se utilizar um
algoritmo de otimização, por exemplo um algoritmo genético, para
obter um parâmetro α mais próximo do "ótimo". Aplicar as entropias
de Rényi e Tsallis na extração de regras usando árvores de decisão.
Aplicar os modelos estudados em algoritmos de seleção de atributos,
além de pesquisar técnicas que possam ser aplicadas para encontrar
um valor ótimo para o limiar de decisão de um atributo contínuo
usado como nó de decisão, com o intuito de minimizar os erros de
classificação.
AGRADECIMENTOS
Os autores agradecem à Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior (CAPES) e à Fundação de Amparo à
Pesquisa e ao Desenvolvimento Científico e Tecnológico do Maranhão (FAPEMA).
R EFERENCES
[1] M. Crosbie and E. Spafford, “Defending a computer system using autonomous agents,” Department of Computer Sciences, Purdue University,
CSD-TR-95-022; Coast TR 95-02, 1995.
[2] Veríssimo, P, “Uncertainty and predictability: Can they be reconciled?
,” Lecture Notes in Computer Science: Future Directions in Distributed
Computing, vol. 2584, pp. 108–113, 2003.
[3] A. Adelsbach, D. Alessandri, C. Cachin, S. Creese, Y. Deswarte,
K. Kursawe, J. C. Laprie, D. Powell, B. Randell, J. Riordan, P. Ryan,
W. Simmonds, R. Stroud, P. Veríssimo, M. Waidner, and A. Wespi.,
“Conceptual model and architecture of maftia,” 2002. [Online].
Available: http://www.research.ec.org/maftia/deliverables/D21.pdf
[4] P. Jalote, Fault tolerance in distributed systems. Englewood Cliffs, New
Jersey: Prentice Hall, 1994.
[5] J. P. Anderson, “Computer security threat monitoring and surveillance,”
James P. Anderson Co, Fort Washington, PA, Tech. Rep., April 1980.
[6] D. E. Denning, “An intrusion detection model,” vol. SE-13, no. 2.
february: IEEE Transactions on Software Engineering, 1987, pp. 222–
232.
[7] W. Lee, S. Stolfo, and P. Chan, “Learning patterns from unix process
execution traces for intrusion detection,” in AAAI-97 Workshop on AI
Approaches to Fraud Detection and Risk Management, 1997, pp. 50–
56.
[8] S. Peddabachigari, A. Abraham, C. Grosan, and J. Thomas, “Modeling
intrusion detection system using hybrid intelligent systems,” J. Netw.
Comput. Appl., vol. 30, no. 1, pp. 114–132, 2007.
[9] N. B. Amor, S. Benferhat, and Z. Elouedi, “Naive bayes vs decision
trees in intrusion detection systems,” in SAC ’04: Proceedings of the
2004 ACM symposium on Applied computing. New York, NY, USA:
ACM, 2004, pp. 420–424.
[10] J. R. Quinlan, “Induction of decision trees,” Machine Learning, vol. 1,
no. 1, pp. 81–106, 1986.
[11] E. B. Hunt, J. Marin, and P. J. Stone, “Experiments in induction,” New
York: Academic Press, 1966.
[12] J. R. Quinlan, C4.5 Programs for Machine Learning. San Diego, CA:
Morgan Kaufmann Publishers, 1993.
[13] X. Wu, Knowledge Acquisition from Databases. Norwood, New Jersey,
USA: Ablex Publishing Corporation, 1995.
[14] C. E. Shannon, “A mathematical theory of communication,” Bell Systems
Technical Journal, vol. 27, pp. 379–423 and 623–656, 1948.
[15] A. Rényi, “On measures of entropy and information,” in Proceedings of
the 4th Berkeley Symposium on Mathematical Statistics and Probability,,
vol. 1. Berkeley: University of California Press, 1961, pp. 547–561.
[16] M. Havrda and F. Charvát, “Quantification method of classification
processes: concept of structural alfa-entropy,” Kybernetika, vol. 3, pp.
30–35, 1967.
[17] C. Tsallis, “Possible generalization of boltzmann-gibbs statistics,” Journal of Statistical Physics, vol. 52, no. 1–2, pp. 479–487, 1988.
[18] L. Boltzmann, “On the relation between the second law of the mechanical theory of heat and probability, and the theorems concerning thermal
equilibirum, respectively,” pp. 373–435, 11 October 1877.
[19] J. W. Gibbs, Elementary Principles in Statistical Mechanics. Yale U.
P., 1902.
[20] S. Kullback and R. A. Leibler, “On information and sufficiency,” The
Annals of Mathematical Statistics, pp. 79–86, 1951.
[21] Y. He, A. B. Hamza, and H. Krim, “A generalized divergence measure
for robust image registration,” in IEEE Transaction on Signal Processing,
vol. 51, no. 5, may, pp. 1211–1220.
[22] A. Hero, B. Ma, O. Michel, and J. Gorma, “Alphadivergence for classification, indexing and retrieval,” University of Michigan Ann Arbor,
Communications and Signal Processing Laboratory, Tech. Rep. CSPL328, may 2001.
[23] S. Furuichi, “Information theoretical properties of tsallis entropies,”
Journal of Mathematical Physics, vol. 47, no. 2, 2006. [Online].
Available: http://link.aip.org/link/?JMP/47/023302/1
[24] L. Breiman, J. Friedman, R. Olshen, and C. Stone, “Classification and
regression trees,” 1984.
[25] S. Murthy, “Automatic construction of decision trees from data: a multidisciplinary survey,” in Data Mining and Knowledge Discovery, vol. 2,
no. 4. Springer, december 1998, pp. 345–389.
[26] M. Ben-Bassat, Use of distance measures, information measures, and
error bounds in feature evaluation in Handbook of Statistics, P. R.
Krishnaiah and L. N. Kana, Eds. Amsterdam, The Netherlands: NorthHolland, 1982, vol. 2.
[27] Q. R. Wang and C. Y. Suen, “Analysis and design of a decision tree
based on entropy reduction and its application to large character set
recognition,” in IEEE Transaction on Pattern Analysis and Machine
Intelligence, vol. 6, 1984, pp. 406–417.
[28] I. Witten and E. Frank, Data Mining: Practical Machine Learning Tools
and Techniques with Java Implementations, 2nd ed. San Francisco,
California: Morgan Kaufmann Publishers, 2005.
[29] Kdd
cup
99
intrusion
detection
data
set.
Retrieved
March
01,
2010.
[Online].
Available:
http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
[30] Kdd
cup
99
intrusion
detection
10_percent_data
set.
Retrieved
March
01,
2010.
[Online].
Available:
http://kdd.ics.uci.edu/databases/kddcup99/kddcup.data_10_
percent.gz
[31] E. P. de Souza, “Estudo sobre sistema de detecção de intrusão por
anomalias: uma abordagem utilizando redes neurais,” Master’s thesis,
Salvador University, Salvador, Brazil, 2008.