Application de KNN et Naïve Bayes pour la détection des attaques contre les Web services : Etude comparative et combinaison des deux algorithmes

Ecole Nationale Supérieured’Informatique ESI ( ex INI )

Projet Fin d’EtudesOption: Systèmes Informatique SIQ

Présenté Par:Mr. Mohamed Amine BENATMANE

Proposé & Encadré Par:Mr. Hakim AMROUCHE

Application de KNN et Naïve Bayes pour la détection des attaques contre les Web services : Etude

comparative et combinaison des deux algorithmes

Promotion: 2014-2015

Problématique

Objectifs

Contexte

ContexteEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Introduction Conception RéalisationEtude

BibliographiqueTests &

RésultatsConclusion

01/75Mohamed Amine Benatmane | Application de KNN et Naïve Bayes pour sécuriser des WS

L’apparition du Web Service a facilité la communication entre plusieurs entitéshétérogènes à travers le réseau

Utilisés pour la distribution de l’information entre plusieurs entités hétérogènes à travers le réseau

Problématique

Objectifs

Contexte

Définition d’un Web-ServiceEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Une interface qui décrit une collection d'opérations ou de services accessibles via réseau

Une telle interface est compréhensible par d'autres machines

L'utilisation de standards liés aux web tels que le protocole HTTP et XML renforce l'interopérabilité entre services

Elle permet aux applications et encore aux web services d'accéder aux services fournis par ce web-service de manière automatique

Problématique

Objectifs

Contexte

Technologies d’un Web-ServiceEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Problématique

Objectifs

Contexte

Structure d’un message SOAPEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Protocol header

SOAP Envelope

SOAP header

SOAP body

SOAP Fault

Protocol de transport utilisé (HTTP, FTP, ...)

Définit le document XML comme un message SOAP

informations spécifiques aux standards du service Web

Les données à transporter

Gestion des erreurs

Contexte

Objectifs

Problématique

Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )





Problématique

Les Web-Services utilisent des standards comme SOAP & XML

L’utilisation de tels standards rend les web-services vulnérables à plusieurs type d’attaques

Ces vulnérabilités sont dues à des failles dans XML

Ces attaques sont généralement des attaques à base de XML

Contexte

Objectifs

Problématique


ESI ( ex INI )





Attaques à base de XML

Attaques à base de XML

Attaques par injection

Injections XML

Injections SQL

Injections Xpath

Injection de Commandes

OS

Attaques XDoS

RecursivePayload

XML Bomb

OversizePayload

ReplayAttacks

Contexte

Objectifs

Problématique


ESI ( ex INI )





Attaques par injection (Exemple)

<soapenv :Body><subscribe><user><username> Alice</username><ID>0</ID><username>Alice</username><password>pass</password></subscribe></soapenv :Body>

< ?xml version="1.0"><users><user><username> Alice</username><ID>0</ID><username>Alice </username><password> Secret </password></user></users>

Contexte

Objectifs

Problématique


ESI ( ex INI )





Attaques XDoS (Exemple)

< !DOCTYPE ez [ < !ENTITY e "e">< !ENTITY e8 "&e ;&e ;&e ;&e ; ... ;&e">...< !ENTITY e1 "&e2 ;&e2 ;&e2; ... ;&e2"> ]><soap :Envelope><soap :Body><attack><ez> &e1 ;</ez></attack></soap :Body></soap :Envelope>

«e1» == 1 280 000 000 «e8»

=> 5 gigaoctet d’espace mémoire

Contexte

Problématique

Objectifs


ESI ( ex INI )





Objectifs

Proposer un système de détection des attaques à base de XML basé sur les algorithmes de classification supervisée KNN, Naïve Bayes et la combinaison des deux algorithmes

Etablir une série de tests pour évaluer les performances du système proposé

Etudier la possibilité de la combinaison entre KNN & Naïve Bayes

Etudier les deux algorithmes de classification supervisée: KNN & Naïve Bayes

PlanEtude Bibliographique1

Conception2

Réalisation3

Tests & Résultats4

Conclusion Générale5

Classification supervisée

Combinaison de Classifieurs

Les données utilisées

Les mesures de performances utilisées

Les tests effectués & Quelques Résultats

Architecture Globale

Noyau de protection

Etude Bibliographique

" Once you stop learning, youstart dying "__________ Albert EINSTEIN


DéfinitionEcole Nationale Supérieure d’Informatique

ESI ( ex INI )


Conception RéalisationIntroductionTests &


La classification est un processus qui permet d’organiser unensemble de données en classes cohérentes ou homogènes.Elle s’applique sur n’importe quel type de données : tableau decontingence, tableau de distances, etc.


Classification

Méthodes de la classificationEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Classification Supervisée

K plus proche voisins

Machine à vecteurs de

supports SVM

Naïve Bayes

Arbres de décision

Classification non supervisée

ClusteringHiérarchique

Clustering Non Hiérarchique

Ascendante

Descendante Partitive Générative

K-Means

Spectral Clustering

Fuzzy K-Means

Espérance Maximisation

Méthodes de Classification






Classification

Classification SuperviséeEcole Nationale Supérieure d’Informatique

ESI ( ex INI )






Classification

Utilise un ensemble d’objets étiquetés (corpus) par leur classes pour prédire la classe d’un objet non étiqueté

Chaque classe a une sémantique unique

Des groupes de données ayant des traits descriptifs communs appartiennent à chaque classe

Les classes sont connues à priori.

Définition d’un ClassifieurEcole Nationale Supérieure d’Informatique

ESI ( ex INI )


Classification





ClassifieurCi

Ensemble des classes possibles

{ c1 , ... , cK }

SortieSi

Objet Oj

( a1 , ... , aS )Vecteur Caractéristique

Vectorisation

Définition d’un ClassifieurEcole Nationale Supérieure d’Informatique

ESI ( ex INI )


Classification





ClassifieurCi


{ c1 , ... , cK }

SortieSi

Objet Oj

( a1 , ... , aS )Vecteur Caractéristique

Vectorisation • La classe associée à l’objet en entréeClasse

• Une mesure de confiance est associée à chaque classe possibleMesure

• Un classement dur l’ensemble des classes possibleRang

Algorithme des K-plus Proches VoisinsEcole Nationale Supérieure d’Informatique

ESI ( ex INI )






Classification

Donne de bon résultats si l'on dispose d'un grand nombre d'exemples d'apprentissage.

Chercher dans le corpus les K plus proches voisins de l’objet en utilisant une distance, puis affecter l’objet à la classe majoritaire parmi les classes des K voisins

Utilise un corpus d’objets étiquetés pour déterminer la classe d’un nouvel objet

Un algorithme intuitif

Algorithme de Naïve BayesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )






Classification

Donne de bon résultats même s'il y a p eu d'exemples d'apprentissage.

Utilise la formule de Bayes pour prédire la classe d’un nouvel objet

Un algorithme probabiliste très répandu

KNN vs Naïve BayesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )






Classification

Critère KNN Naïves Bayes

Qualité de l’algorithme d’apprentissage

Complexité en déploiement O(nS) O(S)

Facilité de mise à jour ++ ++

CPU-mémoire -- +

Pertinence du Classifieur obtenu

Précision + +

Simplicité ++ ++

Rapidité de prédiction - ++

n: Le nombre d’exemplaires du corpus d’apprentissageS: La dimension du vecteur caractéristique


ESI ( ex INI )

Classification






Pourquoi Combiner des Classifieurs ?

L’objectif de la combinaison est de créer un système de classifieurs plus robuste et plus fiable, permettant d’aboutir aux meilleures performances en termes d’exactitude.

Il est intéressent de combiner les décisions de plusieurs classifieurs

Les performances des classifieurs dépendent du problème traité

Stratégies de combinaison de classifieursEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Stratégies de Combinaison

Combinaison Parallèle

Combinaison Hybride

Combinaison Séquentielle

Classification


ClassifieurC1

{ c1 , ... , cK } { c1 , ... , cK } { c1 , ... , cK }

ClassifieurC2

ClassifieurCLS1 S1 SL

...

...

...

...

( a1 , ... , aS )

Vecteur CaractéristiqueObjet Oj

Vectorisation

SL

Décision Finale

Combinaison Séquentielle de ClassifieursEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Classification


Combinaison Parallèle de ClassifieursEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





ClassifieurC1

{ c1 , ... , cK } { c1 , ... , cK } { c1 , ... , cK }

ClassifieurC2

ClassifieurCL

...

...

Objet Oj

Vec

toris

atio

n

Module de Combinaison

S1 SLS2

Décision Finale

( a1 , ... , aS )Vecteur

Caractéristique

Classification


Combinaison Hybride de ClassifieursEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Système de Classifieurs Séquentiels

Objet Oj

Vec

toris

atio

n( a1 , ... , aS )

Vecteur Caractéristique


{ c1 , ... , cK }

Système de Classifieurs Parallèles

Ensemble des classes réduit

{ c1 , ... , cT } , T<K

Décision Finale

Classification


Méthodes de combinaison parallèleEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Combinaison Paralléle de Classifieurs

Combinaison par Fusion

Combinaison par Sélection

Combinaison par Fusion

ParamétriqueNon

Paramétrique

Méthodes de Vote

Règles Fixes

Vote Pondéré

Règles Pondéré

Bayes avec Apprentissage

Méthodes de Bayes

Classification


Méthodes fixes & Méthodes PondéréesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Classification


𝑃𝑗′(𝑜)

𝑗=1𝑁 𝑃𝑗

′(𝑜)

Les probabilités 𝑷𝒋′(𝒐) sont estimées à partir des sorties des classifieurs,

Dans le cas des méthodes pondérées les sorties sont pondérées avec l’importance du Classifieur qui les a fournies,

La classe d’un nouvel objet non étiqueté o est la classe 𝒄𝒋 maximisant la probabilité:

Supportes des sorties de Type « mesure »

Méthode de BayesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Classification


Sortie du Classifieur 𝑖

Les probabilités à postériori sont Fournies explicitement par Naïve Bayes et peuvent être estimées dans le cas de KNN


Supporte des sorties de Type « mesure » (probabilité à postériori associée à chaque classe)

Méthode de Bayes avec apprentissageEcole Nationale Supérieure d’Informatique

ESI ( ex INI )





Classification


Estimée à partir de la sortie du 𝑖è𝑚𝑒 Classifieur plus d’autres

paramètres estimés lors d’une phase d’apprentissage


Suppose que les classifieurs sont indépendants deux à deux

Supporte des sorties de Type « classe

Conception

" Il y a deux façons de faire laconception d’un logiciel. Une façonest de le rendre si simple qu’il n’y aselon toute apparence aucun défaut.Et l’autre est de le faire si compliquéqu’il n’y a pas de défaut apparent "

________________ Tony HOARE

Module de prétraitements

Module de Prétraitement

ArchitectureGlobale


ESI ( ex INI )

RéalisationEtude




Introduction Conception

Classification Supervisée des messages SOAP

Messages SOAP d'apprentissage

étiquetés

Vecteurs Caractéristiques

BDDBase

d'apprentissage

Algorithme de Classification Supervisée

Extraction des attributsVectorisation

Extraction des attributsVectorisation

Nouveau Message SOAP non étiqueté Vecteur

Caractéristique

Classes des messages d'apprentissage

Non Malveillant

Non MalveillantMalveillant

Malveillant

Classe Prédite

Client

Administrateur Pare-Feu XML

Noyau d'Administration

Noyau de Protection

Module de prétraitement

Paramètres

Paramètres

Web-Services

BDD

Module de Gestion des

Corpus

Paramètres


ESI ( ex INI )

RéalisationEtude





Architecture Globale de notre Pare-Feu XML



ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





ArchitectureGlobale



Module de prétraitement pour les attaques xDoS

Module de prétraitement pour les attaques par

injection

xDoS ?

Oui

Non


Géneraux


étiquetés


étiquetés

Vecteur Caractéristique xDoS

Vecteur Caractéristique Tf-Idf


Corpus d'apprentissage

vectorisésBDD

Module de Gestion

des CorpusNouveau Message


ESI ( ex INI )

RéalisationEtude






• Vectoriser les messages SOAP

• => Extraction des attributs caractéristiquesModule de

Vectorisation

• Pondération où normalisation des Attributs extraits Module de

Pondération

• Sélection des Meilleurs attributs avec la mesure de Khi2

• Réduction de la dimension avec l’ACP

Module de Sélection d’attributs

Noyau de Protection

ArchitectureGlobale



ESI ( ex INI )

RéalisationEtude





Prétraitement pour les attaques par injection

Noyau de Protection

ArchitectureGlobale


Utilisation des TF-IDF pour la pondération des termes

Utilisation de la représentation en N-Gram de caractères pour la vectorisation

Vectoriser le contenu des messages SOAP


ESI ( ex INI )

RéalisationEtude





Représentation en N-Grams de caractères

Noyau de Protection

ArchitectureGlobale


Les n-grammes sont souvent utilisées dans le domaine de la Recherche d’Information.

Le déplacement de la fenêtre se fait caractères par caractères.

Une séquence de n caractères consécutifs extraite à partir d’une chaine de caractères, en délaçant une fenêtre de n caractères sur cette dernière.


ESI ( ex INI )

RéalisationEtude





Représentation en N-Grams (Exemple)

Noyau de Protection

ArchitectureGlobale


N = 1 Unigrammes de caractères « o », « r », « 1 », « = ».

N=2 Bigrammes de caractères « or », « r_ », « _1 », « 1= », « =1 »

N=3 Trigrammes de caractères « or_ », « r_1 », « _1=», « 1=1 »

Prenons la chaine de caractères suivante : «or 1=1».


ESI ( ex INI )

RéalisationEtude





Représentation en N-Grams (Vectorisation)

Noyau de Protection

ArchitectureGlobale


Construire un vocabulaire de N-Grams 𝑽 = (𝑵𝑮𝟏, … , 𝑵𝑮𝑺)

Chaque chaine de caractère 𝑺𝒊 est représenté par un vecteur d’attributs caractéristiques 𝑽𝒊 = (𝒂𝒊𝟏, … , 𝒂𝒊𝑺) où 𝒂𝒊𝒋 est l’importance duN-gram 𝑵𝑮𝒋dans la chaine 𝑺𝒊

L’importance 𝒂𝒊𝒋 peut être représentée par le nombre d’occurrences du N-gram 𝑵𝑮𝒋dans la chaine 𝑺𝒊


ESI ( ex INI )

RéalisationEtude





Représentation en N-Grams (Pondération)

Noyau de Protection

ArchitectureGlobale


𝒏𝒊𝒋: le nombre d’occurrences du terme 𝑵𝑮𝒋 dans 𝑺𝒊𝒏𝒊: le nombre total des termes dans 𝑺𝒊𝑵𝑺: le nombre total des chaines de caractères dans le corpus 𝒏𝒋: le nombre de chaines du corpus dont le terme 𝑵𝑮𝒋 apparait.

Assigner aux N-Grams des poids sensés traduire leurs importances dans l’ensemble de chaines de caractères où ils apparaissent


ESI ( ex INI )

RéalisationEtude





Sélection des M Meilleurs attributs

Noyau de Protection

ArchitectureGlobale


Sélection les M attributs ayants les meilleurs importances

Utiliser une statistique ou une mesure, afin de calculer l’importance des attributs dans l’ensemble des objets du corpus

La mesure de Khi2 est la plus utilisée notamment dans le cas des chaines de caractères


ESI ( ex INI )

RéalisationEtude





Prétraitement pour les attaques XDoS

Paramètre Description Variable

TailleMessage La taille du message SOAP en octets. s

NbrElements Le nombre d’éléments du message. ne

NbrAttributs Le nombre des attributs du message. na

ProfendeurMax La profondeur maximale du message SOAP p

TailleDTD La taille de la DTD du message SOAP en octets d

SommeTailleElement La somme des tailles de tout les éléments du message en octets

ste

Noyau de Protection

ArchitectureGlobale


Extraction des paramètres liés à la structure du message SOAP


ESI ( ex INI )

RéalisationEtude





Prétraitement pour les attaques XDoS< ?xml version="1.0" ?>< !DOCTYPE … ><soap :Envelope xmlns :soap="http ://www.w3.org/2001/12/soap-envelope" soap :encodingStyle="http ://www.w3.org/2001/12/soap-encoding"><soap :Body><subscribe><id>25174</id><gender>female</gender><firstname>&e8 ;</firstname><lastname>Fakhoury</lastname><adress><adress><adress>54RueHediLabidi</adress></adress></adress><city>CiteOuvriere</city><state>GovernorateSiliana</state><zipcode>4294</zipcode><email>[email protected]</email><tel>78849033</tel><birthday>14/02/1994</birthday></subscribe></soap :Body></soap :Envelope>

< !DOCTYPE item [< !ENTITY e0 "data data data ">< !ENTITY e1 "&e0 ;&e0 ;&e0 ;&e0 ;&e0 ;&e0 ;&e0 ;&e0 ;">< !ENTITY e2 "&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;&e1 ;">< !ENTITY e3 "&e2 ;&e2 ;&e2 ;&e2 ;&e2 ;&e2 ;">< !ENTITY e4 "&e3 ;&e3 ;&e3 ;&e3 ;&e3 ;&e3 ;&e3 ;">< !ENTITY e5 "&e4 ;&e4 ;&e4 ;&e4 ;&e4 ;&e4 ;&e4 ;&e4 ;&e4 ;">< !ENTITY e6 "&e5 ;&e5 ;&e5 ;&e5 ;&e5 ;&e5 ;">< !ENTITY e7 "&e6 ;&e6 ;&e6 ;&e6 ;&e6 ;&e6 ;&e6 ;">< !ENTITY e8 "&e7 ;&e7 ;&e7 ;&e7 ;&e7 ;&e7 ;&e7 ;">]>

V = (s = 988, ne = 16, na = 1, p = 5, d = 133358516, ste = 155643735)Noyau de

Protection

ArchitectureGlobale



ESI ( ex INI )

RéalisationEtude





Réduction avec l’ACP

Noyau de Protection

ArchitectureGlobale


Une méthode utilisée pour la réduction de la dimension du vecteur caractéristique

Transformer un grand nombre de variables corrélées entre eux en un ensemble réduit de variables non corrélées appelées composantes principales .

Les composantes principales ne sont que des transformations linéaires des variables corrélées



ESI ( ex INI )

RéalisationEtude





ArchitectureGlobale

Noyau de Protection

Noyau de protection


Module de détection des attaques xDoS

xDoS ?

Module de détection des attaques par injection

Injection ?

Non

Oui

Oui


Non

Vecteur Caractéristique TF-IDF

Bloquer le Message

Laisser passer le Message

Oui

Oui

Non



Profil WS existant ?

SOAP ?

Message SOAP

Noyau de Protection



ESI ( ex INI )

RéalisationEtude





ArchitectureGlobale

Noyau de Protection

Noyau de protection


Module de détection des attaques xDoS

xDoS ?

Module de détection des attaques par injection

Injection ?

Non

Oui

Oui


Non

Vecteur Caractéristique TF-IDF

Bloquer le Message

Laisser passer le Message

Oui

Oui

Non



Profil WS existant ?

SOAP ?

Message SOAP


ESI ( ex INI )

RéalisationEtude





Algorithmes utilisés par le noyau de protection

• Le nombre des plus proches voisins: K

• La Distance: Euclidienne, Cosine, ManhattanKNN

• Cas des variables Discrètes: Le facteur de lissage « alpha »

• Cas des variables Continues: Pas de paramètres,

Naïve Bayes

NB

• Méthode de Combinaison: Méthodes Fixes, Pondérées, Bayes et Bayes avec apprentissage

• Estimateur: Min, Max, Médiane, Produit, Somme

La combinaison de KNN et NB


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Algorithmes des K plus Proches Voisins KNN

Paramètres en entrée :(VecteurCar, Corpus, K, distance) Résultat: Classe du nouveau message représenté par son vecteur caractéristiqueDébutinitialiser distances à Zéro Pour i allant de 1 à N Faire //N: Le nombre des Messages SOAP du Corpus

Distances[i]:=distance(VectCar, Corpus.MatriceVC[i])FinPour

KPVoisins:=SélectionnerKProches(distances,K)Classe:=ClasseMajoritaire(KPVoisins, Corpus,Classes)

Retourner Classe Fin


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Algorithme de Naïve Bayes: Cas des VA Discrètes


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Algorithme de Naïve Bayes: Cas des VA DiscrètesParamètres en entrée :(VecteurCar, Corpus, Alpha) Résultat: Classe du nouveau message représenté par son vecteur caractéristiqueDébutEstimer les probabilités 𝑃(𝑐𝑖) de chaque classe 𝑐𝑖Calculer 𝑛𝑐1 le nombre de messages appartenant à la classe 𝑐1𝑃(𝑋(𝑒)|𝑐1) , 𝑃(𝑋(𝑒)|𝑐2) := 1Pour j allant de 1 à S Faire //S est la dimension du vecteur caractéristique𝑛1𝑗, 𝑛2𝑗 := 0

Pour i allant de 1 à N Faire //N: Le nombre des Messages SOAP du CorpusCalculer 𝑛1𝑗 (.resp 𝑛2𝑗 )le nombre de messages du corpus appartenant à la

classe 𝑐1 (,resp 𝑐2 ) don’t l’attribut j est égale au 𝑗é𝑚𝑒 attribut deVecteurCarFinPour𝑷(𝑿(𝒆)|𝒄𝟏) := 𝑷(𝑿(𝒆)|𝒄𝟏) ∗ (𝑛1𝑗 + Alpha)/(𝑛𝑐1+Alpha*S)

𝑷(𝑿(𝒆)|𝒄𝟐) := 𝑷 𝑿 𝒆 𝒄𝟐 ∗ (𝑛2𝑗 + Alpha)/(N-𝑛𝑐1+Alpha*S)

FinPourSi (𝑷(𝑿(𝒆)|𝒄𝟏) ∗ 𝑷(𝒄𝟏) ≥ 𝑷(𝑿(𝒆)|𝒄𝟐) ∗ 𝑷(𝒄𝟐) ) Alors Retourner 𝑐1Sinon Retourner 𝑐2 FSI

Fin


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Algorithme de Naïve Bayes: Cas des VA Continues


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Algorithme de Naïve Bayes: Cas des VA ContinuesParamètres en entrée :(VecteurCar, Corpus) Résultat: Classe du nouveau message représenté par son vecteur caractéristiqueDébutEstimer les probabilités 𝑃(𝑐𝑖) de chaque classe 𝑐𝑖Calculer 𝑛𝑐1 le nombre de messages appartenant à la classe 𝑐1𝑃(𝑋(𝑒)|𝑐1) , 𝑃(𝑋(𝑒)|𝑐2) := 1Pour j allant de 1 à S Faire //S est la dimension du vecteur caractéristique𝑛1𝑗, 𝑛2𝑗 := 0

Pour chaque classe 𝑐𝑖 FaireCalculer les moyennes µ𝑗,𝑐𝑖 et les variances σ²𝑗,𝑐𝑖FinPourFinPourPour j allant de 1 à S Faire𝑷(𝑿(𝒆)|𝒄𝟏) := 𝑷(𝑿(𝒆)|𝒄𝟏) ∗ g(V ectCar : [j], µ𝑗,𝑐1 σ²𝑗,𝑐1 )

𝑷(𝑿(𝒆)|𝒄𝟐) := 𝑷 𝑿 𝒆 𝒄𝟐 ∗ g(V ectCar : [j], µ𝑗,𝑐2 σ²𝑗,𝑐2 )

FinPourSi (𝑷(𝑿(𝒆)|𝒄𝟏) ∗ 𝑷(𝒄𝟏) ≥ 𝑷(𝑿(𝒆)|𝒄𝟐) ∗ 𝑷(𝒄𝟐) ) Alors Retourner 𝑐1Sinon Retourner 𝑐2 FSI

Fin


ArchitectureGlobale

Noyau de Protection

aEcole Nationale Supérieure

d’Informatique ESI ( ex INI )

RéalisationEtude





Combinaison parallèle de KNN & Naïve Bayes

• Méthodes Fixes avec l’un des estimateurs suivants: Min, Max, Médiane, Produit, Somme

• Méthodes de Bayes

Fusion non Paramétrique

• Méthodes Pondérées avec l’un des estimateurs suivants: Min, Max, Médiane, Produit, Somme

• Bayes Avec Apprentissage

Fusion

Paramétrique


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Fusion Non Paramétrique

Naïve Bayes

Com

binaison parallèle par fusion non param

étrique


Module de Fusion

S1

Décision Finale


S2


KNN


ArchitectureGlobale

Noyau de Protection


ESI ( ex INI )

RéalisationEtude





Fusion Paramétrique

KNN

KNN

Naïve Bayes

Naïve Bayes




Corpus d'entrainement Module de Fusion

Matrice De Confusion KNN

Matrice De Confusion NB

Décision Finale

Combinaison parallèle par fusion paramétrique




ArchitectureGlobale

Noyau de Protection

Matrice de Confusion

𝑛𝑐𝑘=𝑐𝑗 est le nombre de messages appartenant à la

classe 𝑐𝑘 que le Classifieur à classifier comme messages

de la classe 𝑐𝑗


ESI ( ex INI )

RéalisationEtude





Sorties des Classifieurs

𝑷 𝒄𝒋 𝑴𝒔𝒈 =𝑲𝒋

𝑲𝑲𝒋 est le nombre de messages appartenant à la classe 𝑐𝑗 parmi les K plus proches voisins


ArchitectureGlobale

Noyau de Protection

Des probabilités à postériori peuvent être utilisées comme mesures

Les Méthodes fixes, pondérées et Bayes requirent des sorties de type: mesure

Fournies explicitement par Naïve Bayes

Réalisation

" Talk is cheap. Show me thecode. "_________ Linus TORVALDS

Environnement de développementEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

RéalisationConceptionEtude




Introduction

Outils utilisés

Environnement

Outils & Bibliothèques utilisésEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

RéalisationConceptionEtude




Introduction

Environnement

Outils utilisés

NetfilterQueue

Tests & Résultats

Les Données utiliséesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude

BibliographiqueConclusion


Introduction

Mesures de Performances

utilisées

Données utilisées

Réalisation

Les Tests effectués

Résultats & interprétation

Web Service « Users »:

Subscribe (ID : string, gender : string, firstname : string ,…, tel : string, birthday : string)

Login (username :string,password :string) :string

Web Service « CalculMatrix »:

AddMatrix (mat1 : double[][], mat2 : double[][]) : double[][]

Taille de L’échantillon

1000 5000

Donnéesd’apprentissage

700 3500

Données de test

300 1500

Les Données utilisées (Attaques par injection)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


utilisées

Données utilisées

Réalisation



Echantillon 1000 5000

Bon Messages 500 2500

Messages Malveillants 500 2500

Injections XML 98 505

Injections XPath 99 510

Injections SQL 114 491

Injections CMD OS 92 515

Mélange d’attaques 97 479

Méthode « Subscribe »




Injections SQL 157 1669

Injections XPath 343 831

Méthode « Login »

Les Données utilisées (Attaques XDoS)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


utilisées

Données utilisées

Réalisation






Recursive Payload 87 360

XML Bomb 26 176

Repeated Elements 52 245

Mélange d'attaques 335 1719

Méthode « Subscribe »




Recursive Payload 115 572

XML Bomb 50 275

Repeated Elements 176 845

Mélange d'attaques 159 808

Méthode « AddMatrix »

Les Mesures de Performances utilisées (1/2)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


utilisées

Réalisation



Données utilisées • Le temps (en secondes) de prédiction

Temps de Prédiction

• Le taux de messages malveillants classifiésà tort comme des bons messages

Taux des Faux Positifs

• Le taux de bons messages classifiés à tortcomme des messages malveillants

Taux des Faux négatifs

Les Mesures de Performances utilisées (2/2)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


utilisées

Réalisation



Données utilisées

• La proportion des messages classifiéscomme des bons messages parmi lesvrais positifs

Précision

• La proportion des vrais négatifs parmi lesmessages classifiés comme des messagesmalveillants

Spécificité

• La relation entre le taux des vrais positifs (rappel) et le taux des faux positifs

Courbe ROC & AUC

Les Tests effectués: cas des attaques par injection Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

KNN

K Distance

5

Euclidienne

Cosine

Manhattan

9

Euclidienne

Cosine

Manhattan

13

Euclidienne

Cosine

Manhattan

Naïve Bayes

Alpha

1.0

0.5

0.1

0.01

Taille du N-Gram

N

2

3

4

5

Combinaison

Méthode de Combinaison Estimateur

Fixes

Max

Min

Produit

Somme

Pondérées

Max

Min

Produit

Somme

Bayes ---

Bayes avec apprentissage ---

Sélection(Khi2)

Taux de Sélection

80%

50%

10%

Les Tests effectués: cas des attaques XDoSEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

KNN

K Distance

5

Euclidienne

Cosine

Manhattan

9

Euclidienne

Cosine

Manhattan

13

Euclidienne

Cosine

Manhattan

Combinaison

Méthode de Combinaison Estimateur

Fixes

Max

Min

Produit

Somme

Pondérées

Max

Min

Produit

Somme

Bayes ---

Bayes avec apprentissage ---

Sélection (ACP)

Taux de Sélection

80%

50%

10%

Quelques Résultats: Attaques par injection Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées

Les tests effectués

Données utilisées

Attaques par injectionEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

KNN: Méthode « Subscribe »: 1000 messages

Attaques par injectionEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


N K Distance Temps de prédiction (s) Taux FP Taux FN AUC

Meilleure Configuration

39 Cosine 0,3235 0,0077 0,0941 0,9859

13 Cosine 0,2344 0,0000 0,0988 0,9858

Mauvaise Configuration

5 5 Manhattan 17,7812 0,5184 1,000 0,7334


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Naïve Bayes: Méthode « Subscribe »: 1000 messages


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


N Alpha Temps de prédiction (s) Taux FP Taux FN AUC


3 0,01 0,0017 0,0000 0,0000 1,000


5 1,0 0,0037 0,0000 0,0774 0,9998


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Résultats avec la sélection d’attributs (khi2)Algorithme des K plus Proches Voisins


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Résultats avec la sélection d’attributs (khi2)Algorithme des K plus Proches Voisins

Algorithme de Naïve Bayes


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Combinaison: Méthode « Subscribe »: 1000 messagesN Classifieur Configuration Temps de

prédictionTaux FP Taux FN AUC

2

KNN K=9, Manhattan 1,1234 0,0000 0,1885 0,9669

NB Alpha=1,0 0,0017 0,0000 0,1755 1,000

Combinaison Bayes avec App 1,1388 0,0000 0,1576 0,9000

3

KNN K=5, Manhattan 4,3337 0,0153 0,0947 0,9680

NB Alpha=1,0 0,0023 0,0000 0,1576 1,000

Combinaison Fixes, Produit 4,2636 0,0000 0.0882 0,9829

Résultats avec la Combinaison


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées



ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


N K Distance Temps de prédiction (s) Taux FP Taux FN AUC


3 13 Cosine 4.9921 0,0000 0.0837 0,9928


5 5 Manhattan 17,7812 0.4640 0.1000 0,7898


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées



ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


N Alpha Temps de prédiction (s) Taux FP Taux FN AUC


3 0,01 0,0017 0,0000 0,0000 1,000


2 1,0 0,0068 0,0000 0,0860 1,000

Quelques Résultats: Attaques XDoSEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


Attaques XDoSEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


Attaques XDoSEcole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


K Distance Temps de prédiction (s) Taux FP Taux FN AUC


13 Manhattan 0,0167 0,0000 0.0336 0,9948


5 Euclidienne 0,0165 0.0132 0.0405 0,9833


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées



ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Résultats avec la sélection d’attributs (ACP)Algorithme des K plus Proches Voisins


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Résultats avec la sélection d’attributs (ACP)Algorithme des K plus Proches Voisins

Algorithme de Naïve Bayes


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Combinaison: Méthode « Subscribe »: 1000 messagesClassifieur Configuration Temps de

prédictionTaux FP Taux FN AUC

KNN K=5, Cosine 0,0165 0.0132 0.0405 0,9833

NB --- 0,0065 0,0065 0,0138 0,9900

Combinaison Bayes 0.0175 0.0065 0.0138 0.9950

KNN K=5, Manhattan 0.0098 0.0066 0.0338 0.9838

NB --- 0,0065 0,0065 0,0138 0,9900

Combinaison Fixes, Max 0.0169 0.0000 0.0336 0.9952

Résultats avec la Combinaison


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées



ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


K Distance Temps de prédiction (s) Taux FP Taux FN AUC


9 Manhattan 0,1976 0,0000 0,0513 0.9916


5 Euclidienne, Cosine 0.33 0.0080 0,0479 0.9882


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées


Bilan (1/4) Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

La taille de N-Gram 3 donne les meilleurs résultats

La taille de l’échantillon influence sur les performances de la classification

Meilleurs résultat avec Naïve Bayes dans le cas des attaques par injection

Meilleurs résultats avec KNN dans le cas des attaques XDoS


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

Le facteur de lissage influence sur les performances de Naïve Bayes

Plus le K est grand plus nous obtenons de bons résultats dans le cas de KNN

La distance Cosine donne de bon résultats dans le cas des attaques par injection

La distance Manhattan donne de bons résultats dans le cas des attaques XDoS


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

La sélection peut améliorer les performances de la classification dans le cas des attaques par injection

La réduction de dimension dans le cas des attaques XDoS influence légèrement sur les performances de la classification


ESI ( ex INI )

Tests & Résultats

ConceptionEtude



Introduction


Réalisation


utilisées


Données utilisées

La combinaison améliore les performances en réduisant le nombre des Faux positifs et négatifs

Les méthodes de bayes avec apprentissage et fixes ont données les meilleurs résultats

Conclusion & Perspectives

Conclusion Générale (1/2)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )

ConclusionConceptionEtude


Résultats


Introduction

ConclusionGénérale

Réalisation

Perspectives

Les Web services sont confrontés à plusieurs types d’attaques notamment les attaques à base de XML

Les méthodes de classification supervisée ont prouvé leurs efficacité pour résoudre plusieurs problèmes

Un pare-feu XML pour la détection des attaques à base de XML en utilisant KNN, Naïve Bayes et la combinaison parallèle des deux.

Des résultats très satisfaisants

Conclusion Générale (2/2)Ecole Nationale Supérieure d’Informatique

ESI ( ex INI )



Résultats


Introduction

ConclusionGénérale

Réalisation

Perspectives

Cas des attaques par injection: les meilleurs résultats avec Naïve Bayes avec la taille du N-Gram = 3

Cas des attaques XDoS: les meilleurs résultats avec KNN avec la distance de Manhattan et un K assez grand (13)

La sélection peut améliorer les performances notamment khi2 dans le cas des injections et l’ACP dans le Cas de XDoS

La combinaison améliore les performances en réduisant le nombre des faux positifs & négatifs

PerspectivesEcole Nationale Supérieure d’Informatique

ESI ( ex INI )



Résultats


Introduction

Perspectives

Réalisation

Conclusion Générale Détecter le type d’attaque en utilisant un système de classification multi classes

L’utilisation de plusieurs classifieurs supervisés comme experts dans la combinaison

Étendre la liste des attaques que le pare-feu peut détecter avec d’autres types d’attaques comme les attaques XSS et les injections LDAP.

Questions

Merci Pour votre Attention !

Engineering

Application de KNN et Naïve Bayes pour la détection des attaques contre les Web services : Etude comparative et combinaison des deux algorithmes