Naive Bayes com estimaç˜ao de densidade de kernel

Naive Bayes com estimação de densidade de kernel
para Classificação de Tráfego Internet
Silas Santiago Lopes Pereira
Jorge Luiz de Castro e Silva
Departamento de Estatı́stica e Computação
UECE - Universidade Estadual do Ceará
Fortaleza - Ceará - Brasil
Email: [email protected]
Departamento de Estatı́stica e Computação
UECE - Universidade Estadual do Ceará
Fortaleza - Ceará - Brasil
Email: [email protected]
Resumo—A dificuldade da caracterização da estrutura e comportamento da rede é evidente dado a imensa comunidade de
usuários, a variedade de aplicações existentes, a heterogeneidade
de equipamentos, a administração distribuı́da e o dinamismo,
tı́picos da Internet atual. A identificação de aplicações de tráfego
de rede é de fundamental importância em várias atividades
relacionadas à gerência de rede, tais como Qualidade de Serviço,
segurança, monitoramento e detecção de intrusões. Este trabalho
demonstra o desempenho das técnicas supervisionadas de Aprendizado de Máquina (AM) Naive Bayes (NB) e Flexible Naive
Bayes (FNB) quanto a tarefa de classificar corretamente o tráfego
Internet.
I. I NTRODUÇ ÃO
O comportamento do tráfego de rede está em constante
mudança devido às altas demandas requeridas por um determinado serviço, ataques à rede, surgimento de novos serviços,
entre outros [1]. A partir da observação dos pacotes que passam por um determinado ponto de medição, pode-se identificar
as aplicações mais presentes em uma rede [2]. A utilização de
números de portas bem conhecidos não mais indica, de forma
confiável, o tipo de aplicação presente no tráfego.
Várias técnicas de AM já foram aplicadas na classificação
de tráfego Internet. [3] utiliza o método NB e apenas dados estatı́sticos sobre o tráfego coletado para o treinamento
do classificador, obtendo resultados superiores à abordagem
baseada em portas. Em [4], a técnica NB com discretização
mostrou-se mais estável e eficiente que a abordagem FNB
apresentada em [5]. Em [5], mostrou-se que a seleção de
discriminantes baseada no método FCBF (Fast Correlationbased Filter) pode consideravelmente maximizar a acurácia
da classificação das técnicas NB e FNB.
A abordagem apresentada nesse trabalho utiliza um número
reduzido de discriminantes selecionados em [5] com a técnica
FCBF e traces reais na avaliação dos métodos NB e FNB para
classificação de tráfego Internet, os quais foram desenvolvidos
e avaliados com o MATLAB [6].
Este trabalho está organizado como a seguir. A seção II
apresenta as técnicas de AM abordadas. As seções III e IV
apresentam respectivamente a obtenção dos dados de tráfego
e a metodologia de classificação. Na seção V Os resultados são
apresentados e discutidos. A seção VI apresenta as principais
conclusões e por fim a bibliografia.
II. T ÉCNICAS AVALIADAS
A. Naive Bayes
O classificador Naive Bayesiano, o qual fornece uma abordagem simples e com semânticas claras para a representação,
uso e aprendizado do conhecimento probabilı́stico, é indicado
para o contexto de indução supervisionada, no qual a meta de
desempenho é a predição precisa das instâncias de teste e o
conhecimento sobre quais instâncias de treinamento contém
informações sobre as classes [7]. Segundo [3] e [5], o classificador Naive Bayes é uma técnica simples que pode ser
aplicada ao problema de classificação de tráfego Internet. Uma
descrição mais detalhada desse método pode ser encontrada
em [8].
Segundo [9], o classificador Naive Bayes pode ser entendido
como uma forma especializada de uma rede Bayesiana intitulada ”Naive”(ingênua) por se sustentar em dois importantes
pressupostos: A suposição que os atributos preditivos são
condicionalmente independentes dada a classe e postula-se que
nenhum atributo oculto ou subtendido influencia o processo
de predição. Assim, um classificador Naive Bayesiano pode
ser representado graficamente conforme a figura 1, na qual
todos os enlaces partem do atributo classe para os atributos
observáveis e preditivos (X1 , X2 , . . . Xk ), expressando a independência condicional destes dado ao atributo classe (C).
Essas suposições apoiam muitos algoritmos eficientes tanto
para classificação quanto aprendizado.
Figura 1. Projeção do Classificador Naive Bayes como uma Rede Bayesiana
Assuma C uma variável aleatória que denota a classe de
uma instância e X um vetor de variáveis aleatórias representando os valores observados dos atributos. Além disso, assuma
c um rótulo de uma determinada classe e x um vetor de
valores de atributo. Considere uma instância de teste x a ser
classificada. A classe mais provável será aquela com maior
valor para P (C = c|X = x). ou seja, a probabilidade da classe
c dada a instância x. A expressão seguinte apresenta a regra de
Bayes, aplicada para calcular esta probabilidade, onde X = x
corresponde ao evento X1 = x1 ∧ X2 = x2 ∧ . . . Xk = xk e
P (C = c) representa a probabilidade a priori de c, ou seja, a
probabilidade de obtenção da classe c sem levar em conta os
dados de treinamento:
p(C = c|X = x) =
p(C = c)p(X = x|C = c)
p(X = x)
(1)
Uma suposição comum e não inerente à abordagem Naive
Bayesiana, porém frequentemente usada é que para cada
classe os valores dos atributos numéricos são normalmente
distribuı́dos. Segundo [8], embora essa suposição não reflita a
realidade do tráfego Internet, supera em desempenho alguns
modelos mais complexos.
B. Flexible Naive Bayes
O algoritmo de aprendizado Flexible Naive Bayes é uma
generalização do Naive Bayes apresentado em II-A e algoritmicamente semelhante a este em todos os aspectos, com
exceção da computação da função de distribuição P (X =
x|C = c) para atributos contı́nuos. Substitui-se a suposição
de normalidade do Naive Bayes, na qual a estimação de uma
única Gaussiana é o método mais comum para tratar variáveis
contı́nuas, por uma variedade de métodos de estimação não
paramétricos, dentre eles, a estimação de densidade de kernel,
a qual, como o nome sugere, utiliza métodos de estimação de
kernel [7] [5].
O método Naive Bayes com estimação de densidade de kernel com kernels Gaussianos estima a função densidade a partir
de um amplo conjunto de kernels. A função de distribuição é
então expressa pela fórmula abaixo, na qual n corresponde ao
número de instâncias de treinamento pertencentes à classe c e
ui corresponde ao atributo xi de cada exemplo de treinamento:
n
p(X = x|C = c) =
1X
g(x; µi , σc )
n i
(2)
Deve-se observar que a equação 2 é semelhante à expressão
padrão para cálculo
da densidade de kernel p(X = x|C =
Pn
i
c) = (nh)−1 i K( xi −µ
h ) , onde h = σ e K(xi , µi , h) =
g(x, 0, 1)
Quando se calcula p(X = x|C = c) para um atributo contı́nuo na classificação de um exemplo, o método
Naive Bayes estima a função de densidade de probabilidade
Gaussiana apenas uma vez, enquanto que o Flexible Naive
Bayes executará n estimações, onde n é o número de valores
observados nas instâncias de treinamento com classe c. Tal fato
implica em um aumento da complexidade computacional do
modelo. A tabela I, obtida em [5], apresenta a complexidade
das técnicas Naive Bayes e Flexible Naive Bayes apresentadas,
onde n representa o número de instâncias de treinamento e k
o número de discriminantes:
Tabela I
C OMPLEXIDADES DAS T ÉCNICAS NB E FNB.
Operação
Treinamento com n instâncias
Teste com m instâncias
NB
Tempo
O(nk)
O(mk)
Espaço
O(k)
FNB
Tempo
O(nk)
O(mnk)
Espaço
O(nk)
A maior dificuldade na estimação de kernel se encontra na
configuração do parâmetro largura de banda de kernel σ. A
seleção do parâmetro estatı́stico largura de banda do kernel
desempenha um papel importante no desempenho do modelo
e uma descrição mais detalhada sobre algumas propriedades
assintóticas do Flexible Bayes pode ser encontrada em [7].
Segundo [7], a estimação de kernel assume algumas propriedades exatas quando σ tende a zero conforme o número de
instâncias tende ao infinito. A literatura existente apresenta
diversas abordagens para definição da largura do kernel,
mas cada heurı́stica faz suposições implı́citas e explicitas
sobre a função de densidade que serão válidas para algumas
distribuições mas não para outras.
Neste trabalho, utiliza-se σc = √1nc com base em [7], sendo
nc o número de instâncias de treinamento pertencentes à classe
c. Segundo [7], como o Flexible Bayes observa uma maior
quantidade de instâncias de treinamento, suas estimativas de
densidade se tornam crescentemente locais.
O intuito detrás do Flexible Bayes é que a estimação de
kernel permita que o método tenha um bom desempenho em
domı́nios que violam a suposição de normalidade. Segundo
[5], a simples suposição sobre a normalidade dos discriminantes é imprecisa e problemas eminentes surgem quando
a distribuição real é multimodal e tal situação pode indicar
que a classe em consideração é muito grande ou que outra
distribuição deve ser utilizada para a análise dos dados.
III. D ESCRIÇ ÃO DOS Traces
Os dados de tráfego foram coletados de um monitor de
rede de alto desempenho descrito em [10] e refletem uma rede
com cerca de 1000 usuários conectados à Internet através de
uma conexão full-duplex Gigabit Ethernet em um perı́odo de
24 horas. Foi gerado um conjunto de 10 arquivos de trace
sendo cada um referente a um perı́odo de 1.680 segundos,
e disponibilizados para a comunidade cientı́fica [11]. Para
a classificação, foram consideradas as categorias de tráfego:
Attack (ex: internet worm,virus attacks), Bulk (ex: ftp), Database (ex: oracle, etc), Mail(smtp, etc), Multimedia (Windows
Media Player,etc), P2P (GnuTella, etc), Services(X11, dns, etc)
e WWW.
Durante o pré-processamento, foi gerado além das categorias de aplicações para cada fluxo um conjunto de informações
estatı́sticas relacionadas ao fluxo que em [11] são denominados
discriminantes. Foram gerados 249 discriminantes (incluindo a
categoria de aplicação). Isso inclui estatı́sticas simples sobre o
tamanho do pacote e o tempo entre os pacotes, e informações
derivadas do protocolo de transporte (TCP) tais como contadores de pacote SIN e ACK [11]. A tabela II exibe o
número de instâncias de fluxo por classe de aplicação presentes
nos traces utilizados.Pode-se observar que existe uma grande
variabilidade no número de fluxos das aplicações presentes
nos dados:
Tabela III
C ARACTER ÍSTICAS DOS TRAÇOS UTILIZADOS
Tabela II
N ÚMERO DE F LUXOS POR C ATEGORIA DE A PLICAÇ ÃO
Attack
1.793
Multimedia
576
Bulk
11.538
P2P
2.094
Database
2.648
Services
2.099
Mail
28.567
WWW
328.093
Um segundo conjunto de dados também foi utilizado. A
partir de um monitor desenvolvido inteiramente em Python,
que coleta o tráfego de um determinado ponto de acesso,
efetua a remontagem de sessões TCP com base em [12]
e [13], extrai um dado número de caracterı́sticas (Tempo
decorrido entre primeiro e último pacote, número de pacotes,
total de bytes, número de pacotes com ao menos um byte de
payload de dados TCP, número de pacotes com bit PUSH
ativo no cabeçalho TCP, e mediana e variância do total de
bytes no pacote IP. Desde que cada atributo é calculado para
ambas as direções do fluxo, cada instância de fluxo possui
14 discriminantes estatı́sticos além do atributo classe) e rotula
os fluxos pelo método de portas bem conhecidas [14]. Dessa
forma, possibilitou-se o uso de traces próprios para avaliação
dos classificadores. Utilizou-se traços de tráfego coletados em
um host conectado a uma rede Ethernet banda larga 100Mbps.
O monitor foi executado em um PC Core i5 com CPU
2.30 GHz e 4GB de memória. Neste momento, a ferramenta
Weka (Waikato Environment for Knowledge Analysis) [15],
que dispõe de uma coleção de algoritmos de aprendizagem
de máquina para resolução de problemas de Data Mining, foi
utilizada para treinamento e avaliação dos classificadores.
Para a execução do classificador NB e FNB no Weka, o
monitor gera um arquivo contendo as instâncias de fluxo de
tráfego em formato compatı́vel com o Weka. Em seguida,
o sistema executa a rotina weka.classifiers.bayes.NaiveBayes,
passando como parâmetros a opção de uso de estimação de
kernels (no caso do FNB) e o arquivo com os dados de
treinamento e avaliação. Foi utilizada validação cruzada para
avaliar a precisão dos modelos de classificação, com número
de folds igual a 10. As caracterı́sticas do traço de tráfego
utilizado, referenciado como T 1, são apresentadas na tabela
III.
As aplicações identificadas nos respectivos traços a partir
do método baseado em portas são mostradas na tabela V. Em
T1, a maior parte do tráfego considerado refere-se a aplicações
Www e Ftp.
IV. AVALIAÇ ÃO DAS T ÉCNICAS
Na abordagem utilizada para avaliar os métodos estudados,
um novo arquivo de trace foi utilizado para testar os classificadores, o qual diz respeito a uma coleta realizada 12 meses
depois em relação aos dez arquivos de trace apresentados
anteriormente. A aplicação de dados mais recentes para a
avaliação dos classificadores utilizando modelos antigos visa
Parâmetro
T1
Número de pacotes
614282
Tamanho da captura
565.62MB
Duração da captura
3516.79s
Tamanho médio do pacote
920.78 bytes
Taxa média de captura
1.28 Mbps
Tabela IV
C OMPOSIÇ ÃO DOS DADOS DE TR ÁFEGO POR CLASSE DE APLICAÇ ÃO
Classificação
Descrição
T1
Www
World Wide Web
1353
Https
Http protocol over TLS/SSL
145
Ftp
File Transfer Protocol
1458
-
Xvttp
Xvttp Protocol
Isakmp
Isakmp Protocol
-
Total
-
2956
Tabela V
C OMPOSIÇ ÃO DOS DADOS DE TR ÁFEGO POR CLASSE DE APLICAÇ ÃO
Classificação
Descrição
T1
Www
World Wide Web
1353
Https
Http protocol over TLS/SSL
145
Ftp
File Transfer Protocol
1458
Total
-
2956
demonstrar se as técnicas abordadas tem capacidade de classificar corretamente os fluxos de tráfego em suas respectivas
classes ou se os modelos de classificação são obsoletos [5].
Todos os fluxos de tráfego pertencentes aos dez arquivos
de trace foram agregados em um único trace e utilizados
para treinamento dos classificadores. A tabela VI exibe a
quantidade de fluxos de tráfego em cada classe presentes neste
arquivo de trace. Uma vez que o trace considerado não contém
fluxos das classes Attack e Multimedia, os valores de acurácia
destas duas categorias não são analisados:
Tabela VI
N ÚMERO DE F LUXOS POR A PLICAÇ ÃO NO N OVO Trace
Attack
-
Bulk
1513
P2P
297
Database
295
Services
121
Mail
1799
WWW
15597
Multimedia
Total
19622
V. R ESULTADOS
A partir da tabela VII, é claro perceber que os valores
de acurácia para cada técnica considerada atingiram bons
resultados e variaram entre 78.58% e 92.42% para a 1o
abordagem de avaliação. na 2o abordagem, não houve ganhos
significativos na utilização de estimação de densidade de
kernels e o desempenho de ambos os classificadores foi baixo.
A principal razão para o desempenho razoável das técnicas
NB e FNB na 1o abordagem deve-se a pouca ocorrência
Tabela VII
P RECIS ÃO M ÉDIA DOS C LASSIFICADORES
Traces (Moore)
T1
Naive Bayes
78.58%
59.03%
Flexible Naive Bayes
84.77%
59.33%
de grandes variações nas distribuições dos discriminantes
utilizados, ou seja, a aplicação de distribuições gaussianas e
kernels gaussianos sobre os valores dos atributos em estimadores Naive Bayes mostraram-se aceitáveis por descreverem
bem as distribuições reais dos atributos. No segundo contexto, uma possı́vel explicação para o baixo desempenho das
técnicas seria incapacidade dos classificadores em descrever
as distribuições dos atributos do fluxo.
VI. C ONCLUS ÃO
A principal contribuição desse trabalho foi demonstrar a
utilização de classificadores amplamente abordados na literatura para categorização de tráfego de rede em um dado número
de categorias de aplicação e avaliá-los sobre cada experimento
realizado.
A metodologia aplicada baseia-se categorização de tráfego
de rede através da utilização dos algoritmos NB, FNB. Os
dados usados para avaliar os métodos referem-se um trace
datado como coletado 12 meses depois em relação aos traces
utilizados para treinamento, permitindo uma posterior análise
da estabilidade temporal das técnicas estudadas. Os resultados
encontrados mostram que o método Flexible Naive Bayes
obteve maior precisão na classificação que o método Naive
Bayes. Isso leva a perceber que a utilização do método de
estimação de kernel melhor descreve as distribuições complexas dos atributos preditivos que o uso comum de uma simples
distribuição gaussiana. Em um segundo cenário com traces
próprios, os classificadores foram imcapazes de categorizar
corretamente uma quantidade significativa do tráfego. Uma
possı́vel explicação seria a má qualidade dos fluxos usados,
evidenciando a pertinência da aplicação de técnicas de seleção
de atributos e exemplos para os dados de treinamento e teste.
R EFER ÊNCIAS
[1] R. Holanda Filho, J. Maia, and G. Paulino, “Broadband network traffic
characterization and classification using a multivariate statistical method
broadband network traffic characterization and classification,” pp. 113–
122, 2006.
[2] A. Ziviani and O. Duarte, “Metrologia na Internet,” Minicursos do XXIII
Simpósio Brasileiro de Redes de Computadores, SBRC, pp. 285–329,
2005.
[3] D. Zuev and A. Moore, “Traffic classification using a statistical approach,” Passive and Active Network Measurement, pp. 321–324, 2005.
[4] Y. Liu, Z. Li, S. Guo, and T. Feng, “Efficient, Accurate Internet Traffic
Classification using Discretization in Naive Bayes,” Networking, Sensing
and Control,ICNSC 2008. IEEE International Conference on, vol. 0, pp.
1589 – 1592, 2008.
[5] A. Moore and D. Zuev, “Internet traffic classification using bayesian
analysis techniques,” in Proceedings of the 2005 ACM SIGMETRICS
international conference on Measurement and modeling of computer
systems. ACM, 2005, p. 60.
[6] S. Chapman, “Programação em MATLAB para Engenheiros,” São
Paulo: Pioneira Thomson Learning, 2003.
[7] G. John and P. Langley, “Estimating continuous distributions in Bayesian
classifiers,” in Proceedings of the eleventh conference on uncertainty in
artificial intelligence, vol. 1. Citeseer, 1995, pp. 338–345.
[8] I. Witten and E. Frank, Data Mining: Practical machine learning tools
and techniques. Morgan Kaufmann Pub, 2005.
[9] W. L. Buntine, “Operations for learning with graphical models,” Journal
of Artificial Intelligence Research, vol. 2, pp. 159–225, 1994.
[10] A. Moore, J. Hall, C. Kreibich, E. Harris, and I. Pratt, “Architecture of
a network monitor,” in Passive & Active Measurement Workshop 2003
(PAM2003). Citeseer, 2003.
[11] A. Moore, D. Zuev, and M. Crogan, “Discriminators for use in flowbased classification,” RR-05.13 Department of Computer Science, University of London, 2005.
[12] G. Wagener, A. Dulaunoy, and T. Engel, “Towards an estimation of the
accuracy of tcp reassembly in network forensics,” in Future Generation
Communication and Networking, 2008. FGCN’08. Second International
Conference on, vol. 2. IEEE, 2008, pp. 273–278.
[13] B. XIONG, C. Xiao-su, and C. Ning, “A Real-Time TCP Stream
Reassembly Mechanism in High-Speed Network,” JOURNAL OF
SOUTHWEST JIAOTONG UNIVERSITY, vol. 17, no. 3, 2009.
[14] M. Rose and K. McCloghrie, “Structure and identification of management information for tcp/ip-based internets,” Structure, 1990.
[15] E. Frank, M. Hall, and L. Trigg, “Weka 3-Data Mining with Open Source
Machine Learning Software in Java,” The University of Waikato, 2000.