Embed Size (px)
Citation preview
1
Contributions futures du CRILdans le cadre de l’ACI Daddi
Présenté par :
S. Benferhat
2
Contributions futures du CRILdans le cadre de l’ACI Daddi
Complémentarité– « Comportementale/signature »– Réseaux bayésiens (RB) / arbres de décision
(AD)
Extensions AD et RB
Vers la décision et le diagnostic
3
Plan Brefs rappels
– RB et AD– Base KDD (Dico)
Quelques mots sur :– Complémentarités– Une extension RB
Deux mots sur :– Extensions AD – Autres extenstions des RB– Vers la décision et le diagnostic
4
Réseaux Bayésiens (RB)Réseaux Bayésiens (RB)
C
FlagDurationProtocol_ type …
Causalité + probabilités
Dans le contexte de détection d’intrusion : Réseaux
Bayésiens naïfs (Valdes, projet DICO)
Deux niveaux: un nœud racine (variable non-observable)
et plusieurs nœuds fils (variables observables)
Construction des RBN est très simple (structure unique)
Inférence (classification) est linéaire
Pb. hypothèse d ’indépendance très forte!
5
Arbre de décision
Une technique de classification
Expression simple de la connaissance.
Compréhension et interprétation facile des résultats.
Arbre de décision (AD)Arbre de décision (AD)
6
Racine
Nœud interne
Feuille
Couleur
Rouge
Vert Jaune
Forme=carré
Forme=rond 3D
Bleu
Forme=carré
3D 2D3D 2D
Vrai Faux Vrai Faux
3D 2D
Vrai Faux Test
Modalités du test
Arbre de décision
7
KDD’99 (données DARPA)
10% du training set: 494019 connections
10% du testing set: 311029 connections
38 attaques (dont certaines sont nouvelles)
41 attributs (certains ont été rajoutés par des
experts)
Données utilisées dans DICO
8
Denial of Service Attacks (DOS)
User to Root Attacks (U2R)
Remote to User Attacks (R2L)
Probing
Liste des attaques
Testing
Training
1,34%0,07%5,21%73,9%19,48%
0,83%0,01%0,23%79,24%19,69%
Prob.U2RR2LDOSNormal
9
Récapitulatif des résultats
C4.5 NaïveBayes
PCC 92.06% 91.47%
Normal 99.50% 97.68%
DoS 97.24% 96.65%
R2L 0.52% 8.66%
U2R 13.60% 11.84%
Probe 77.92% 88.33%
10
Conclusions des résultats de C4.5 et Naive Bayes pour KDD’99
Aucune technique n’est meilleure dans les quatre catégories d’attaques
Toutes les techniques sont faibles dans la détection des attaques rares en générale, R2L et U2R en particulier
Alternative : Exploiter la complémentarité
11
• Complémentarités (travail très préliminaire):
- Comportementale/signature
- Réseaux bayésiens (RB) / arbres de décision (AD)
12
Retour sur les résultats
C4.5 NaïveBayes
PCC 92.06% 91.47%
Normal 99.50% 97.68%
DoS 97.24% 96.65%
R2L 0.52% 8.66%
U2R 13.60% 11.84%
Probe 77.92% 88.33%
Remarques : - Résultats sur testing base, et non training base! - Une fonction de combinaison simple n’est pas satisfaisants
13
Méta-calssificate
ur«
Connexion »
NaïveBayes
C4.5
Catégorie de la connexion
Combinaison de C4.5 et NaïveBayes dans un méta-classificateur hybride
14
la majorité des erreurs de classification sont des faux négatifs
la majorité des erreurs de classification sont d’origines R2L et U2R
Gérer différemment les prédictions de NaïveBayes et C4.5 pour traiter les: vrais/faux négatifs vrais/faux positifs
Principe du méta-classificateur hybride
15
Principe du méta-classificateur hybride
Traitement des vrais/faux positifs (la classe prédite par les deux classificateurs n’est pas la classe normale)
Traitement des vrais/faux négatifs (au moins, l’un des classificateurs a prédit la classe normale)
- Confirmation des prédictions de la classe normale ou
- Correction de ces prédictions.
Utiliser des informations externes (info. Disponibles sur la construction de la base et des attaques)
16
Fusion des distributions de probabilités associées par NaïveBayes et C4.5 à la connexion à classifier.
Sélection de la classe la plus probable
Traitement des vrais/faux positifs:Fusion élémentaire
17
Traitement « naïf » des vrais/faux positifs
Si (C4.5(a)≠ Normal) et (NaïveBayes(a) ≠ Normal) alors Si C4.5(a) = R2L ou NaïveBayes(a) = R2L alors Meta-NB-C4.5(a) :=R2L ; Sinon
Si C4.5(a) = U2R ou NaïveBayes(a) = U2R alors Meta-NB-C4.5(a) :=U2R ;Sinon
Pour k :=0 à 39 faire %40 nbre de classes% d_Meta [k] :=0.5*(d_C4.5[k] + d_NB[k]) ;
Fin pour ;c_Meta :=Argmaxk(d_Meta[k]) ;Meta-NB-C4.5(a) :=Catégorie(c_Meta) ;
Fin si ;
Fin si ;
18
Confirmer ou corriger les prédictions de la classe normale nécessite de recourir à:
• l’approche comportementale pour distinguer entre vrais et faux négatifs
• un mécanisme permettant d’identifier la catégorie d’attaques des connexions reconnues comme faux négatifs
Principes du traitement des vrais/faux négatif
19
Schéma général pour le traitement des vrais/faux négatifs
vrai/faux négatif ?
vrai négatif ?
Catégorie(a) :=Normal Fausse alerte ?
Identification de la catégorie d’attaque du faux négatif.
Catégorie(a) :=Normal
Oui
Oui
Non
Non
NaïveBayes(a)=Normal
C4.5(a)=Normal
Procédure de distinction entre vrais et faux négatifs
Info. externesCompor-tementale
20
Modélisation des connexions normales dans les données d’apprentissage
Élaboration d’une mesure de similarité pour juger le degré de normalité d’une connexion (similarité avec le modèle des connexions normales)
Vérifier si les connexions reconnues anormales ne constituent-elles pas des fausses alertes
Distinction entre vrais/faux négatifs
21
Mesure « naïve » de distance d’une connexion avec le modèle des connexions normales
wi représente le poids associé à l’attribut ai
Dist(ai, âi) représente la distance entre l’attribut ai de la
connexion avec l’attribut correspondant dans le modèle des connexions normales âi.
22
Mesure « naïve » de distance d’une connexion avec le modèle des connexions normales
Distance: • Si ai est continu :
•Si ai est discret ou symbolique :
23
Mesure « naïve » de distance d’une connexion avec le modèle des connexions normales
Décider si la connexion représentée par le vecteur d’attributs a est normale ou anormale Si Dist(a, â) < α alors
a est normale ;Sinon
a est anormale ;Fin si
Avec
24
Traitement des vrais/faux négatifs
Traitement des fausses alertes (loin de la norme)
La connexion déclarée anormale est-elle une connexion R2L ou U2R?
Dans KDD’99, ce sont certains attributs relatifs au contenu qui renseignent le plus sur ces deux types d’attaques
Si tous les attributs relatifs au contenu sont nuls, alors cette connexion est normale (rien n’indique qu’elle est R2L ou U2R)
25
Identification « naïve » de la catégorie d’attaques des connexions déclarées
anormales
Distinction entre attaques DoS/Probe et R2L/U2R sur la base des attributs relatifs à l’aspect temporel des connexions
Distinction entre DoS et Probe sur la base des attributs relatifs à l’hôte de destination
Distinction entre attaques R2L et U2R sur la base des attributs relatifs au contenu et la sémantique de ces deux catégories d’attaques
26
Exemple de règle de distinction entre attaques DoS/Probe d’un côté et R2L/U2R d’un autre côté
Si ((count >100) ou (duration <=1)) alors
Catégorie(a) ∊ {DoS,Probe};
Sinon Catégorie(a) {R2L, U2R};∊
Fin si;
27
Un autre exemple de règle de distinction
entre attaques DoS et Probe
Si ((count >100) et (srv_count >50)) alors
Catégorie(a) :=DoS ;Sinon
Si ((duration <=1) et (dst_host_same_srv_rate >0.718)) alors
Catégorie(a) :=DoS ;Sinon
Si ((count >100) et ((srv_count <=50) ou (dst_host_diff_srv_rate>0.59)) alors
Catégorie(a) :=Probe ;Fin si;
Fin si;Fin si;
28
Future mise en œuvre du méta-classificateur
Catégorie(connexion)
C4.5
NaïveBayes
Traitement des
vrais/faux positifs
Traitement des
vrais/faux négatifs
Méta- classificateur
Connexion
Ensemble de classificateur
s
Sous-système 1 Sous-système 2
29
Les réseaux naïfs Les réseaux naïfs crédibilistescrédibilistes
30
Exemple (1)
Protocole Service Flag Classe
tcp http SF Normal
tcp http RSTO Normal
tcp http REJ Probing
tcp time SF Probing
tcp time SO DOS
tcp auth SF Normal
tcp auth SO DOS
tcp private SF Normal
tcp private SF Normal
tcp private REJ Probing
tcp private RSTO DOS
tcp private SO DOS
udp domain_u SF Normal
udp private SF DOS
tcp http RSTO Normal
tcp private RSTO DOS
tcp http SF Normal
Nature des connexions
Ensemble d’apprentissage (détection d’intrusion)
…
31
Protocole Service Flag Classe
tcp http SF Normal
tcp http RSTO Normal
tcp http REJ Probing ou DOS
tcp time SF Probing
tcp time SO DOS
tcp auth SF Normal
tcp auth SO ?
tcp private SF Normal
tcp private SF Normal
tcp private REJ Probing
tcp private RSTO DOS avec degré 1 et U2R avec un autre degré 2
tcp private SO DOS
udp domain_u SF Normal
udp private SF DOS
tcp http RSTO ?
tcp private RSTO DOS
tcp http SF Normal
32
Idée
Utilisation de la théorie des fonctions de croyance qui permet:
L'expression des croyances partielles.
La possibilité d'exprimer l'ignorance partielle ou totale.
Le traitement des jugements subjectifs et personnels.
La représentation des informations mathématiques et épistémiques.
33
Concepts de base
Fonction de masse de croyance élémentaire (bba)
m: 2 [0,1]
m(A)A
1
m(A) Partie de croyance attribuée exactement à A
Fonction de croyance (bel)
bel(A) Croyance totale attribuée à A
ABm(B)bel(A)A
[0,1]2 :bel
34
Exemple Protocole Service Flag Classe
tcp http SF m{I1}
tcp http RSTO m{I2}
tcp http REJ m{I3}
tcp time SF m{I4}
tcp time SO m{I5}
tcp auth SF m{I6}
tcp auth SO m{I7}
tcp private SF m{I8}
tcp private SF m{I9}
tcp private REJ m{I10}
tcp private RSTO m{I11}
tcp private SO m{I12}
udp domain_u SF m{I13}
udp private SF m{I14}
tcp http RSTO m{I15}
tcp private RSTO m{I16}
tcp http SF m{I17}
m{I2}(probing DOS) =1; m1{I2} () = 0
35
Réseaux Bayésiens (RB)Réseaux Bayésiens (RB)
La base de test de KDD’99 contient des incohérences
Etudier des formes générales de RB (simplement connectés,
TAN, etc)
Adapter les réseaux causaux pour:
prise en compte de nouveaux cas et détecter de nouvelles
attaques
diagnostics et explications
Développer les diagrammes d ’influences:
intégrer la notion de risque et de décision
Développer des réseaux causaux basés sur les fonctions de
croyances
36
Arbre de décision (AD)Arbre de décision (AD)
Développer des arbres de décisions possibilistes
prise en compte des données manquantes/incertaines
Adapter les arbres de décisions pour les problèmes de
détection d ’intrusions
Développer des meta-classificateurs
complémentarité RB/AD
