Contrôle d ’Accès Contrôle d ’Accès et et

Hauts DébitsHauts Débits

Olivier PaulOlivier Paul

ENST de BretagneENST de Bretagnehttp://www.rennes.enst-bretagne.fr/~paul/http://www.rennes.enst-bretagne.fr/~paul/

PlanPlan

1- Introduction1- Introduction

2- Amélioration des performances du 2- Amélioration des performances du contrôle d ’accès réseaucontrôle d ’accès réseau2-1Problème théorique.2-1Problème théorique.

2-2 Amélioration des techniques de 2-2 Amélioration des techniques de classification. classification.

2-3 Distribution des mécanismes.2-3 Distribution des mécanismes.

3- Conclusion.3- Conclusion.

0, 1/1

IntroductionIntroduction Le contrôle d ’accès:Le contrôle d ’accès:

– Service qui assure une protection contre une Service qui assure une protection contre une utilisation non autorisée de ressources par une utilisation non autorisée de ressources par une entité ou un groupe d ’entité (ISO).entité ou un groupe d ’entité (ISO).

Réseau

Client Serveur

Firewall

1, 1/6

Comment ca marche ?Comment ca marche ? Le Firewall se Le Firewall se

situe entre le situe entre le réseau interne réseau interne et le réseau et le réseau externe.externe.

Layer 2

TCP/UDP

IP

PacketFilter

ApplicationProxy

InsideOutside

1, 2/6

Comment ca marche ?Comment ca marche ? Les paquets IP Les paquets IP

sont filtrés au sont filtrés au niveau niveau réseau/transporréseau/transport et au niveau t et au niveau application si application si une passerelle a une passerelle a été configurée.été configurée.

Layer 2

TCP/UDP

IP

PacketFilter

ApplicationProxy

InsideOutside

src and dst addressesProtocol ID

src and dst ports

Direction and flags

Protocol Info.

Application Data

1, 3/6

Comment ca marche ?Comment ca marche ? Le paquet est Le paquet est

envoyé sur le envoyé sur le réseau interne.réseau interne.

Layer 2

TCP/UDP

IP

PacketFilter

ApplicationProxy

InsideOutside

Layer 2 Frame

1, 4/6

Quels problèmes ?Quels problèmes ?

Réassemblage FragmentationClassificationBuffer Buffer

Filtre

Le processus de classification est un processus gourmand en Le processus de classification est un processus gourmand en ressourcesressources

– Performances faibles.Performances faibles.

1, 5/6

Algorithme linéaireAlgorithme linéaire

CT : O(nCT : O(n..d), CS : O(nd), CS : O(n..d), insertion O(1).d), insertion O(1).

PolitiqueSi @S=A et @D=B et PS=C et PD=D alors autoriseSi @S=A et @D=B et PS=C et PD=E alors interditSi @S=A et @D=B alors autoriseSi @S=A et @D=C alors interdit

Flux

A C C C

INTERDIT

1, 6/6

Le problème de la Le problème de la classification de fluxclassification de flux

Classificateur

ProtoSourceports

DestAddress

SourceSource

AddressAddressFlags

Destports

If Cond1 and Cond2 and Cond3 then action1If Cond4 and Cond5 then action2If Cond6 then action1

Politique de n règlesportant sur les d champs

Bornes théoriques :Bornes théoriques :

Complexité : O(log n), Complexité : O(log n), complexité spatiale : O(n complexité spatiale : O(n dd).).

Complexité spatiale: O(n), Complexité spatiale: O(n), complexité : O(log complexité : O(log d-1d-1 n). n).

flux composé de d champsflux composé de d champs

Overmars, Van der Stappen [Journal of Algorithms 96]Overmars, Van der Stappen [Journal of Algorithms 96]

2-1, 1/1

Améliorations des Améliorations des techniques de techniques de classificationclassification

Utilisation de mémoires caches.Utilisation de mémoires caches. Définition de nouveaux Définition de nouveaux

algorithmes de classification:algorithmes de classification:– Permettant une parallèlisation des Permettant une parallèlisation des

traitements.traitements.– Utilisant la redondance des politiques Utilisant la redondance des politiques

de contrôle d ’accès.de contrôle d ’accès.

2-2, 1/9

Mémoires cachesMémoires caches

Classificateur

Classificateurlogiciel

MémoireCache

Flux@S,@D,PS,PD

Hit

Miss

Update (LRU)

Hit

2-2, 2/9

Mémoires CacheMémoires Cache CAM (Content Addressable Memory)CAM (Content Addressable Memory)

(@S,@D,PS,PD) CAM Action

– Complexité temporelle O(1), Complexité spatiale O(n.d).Complexité temporelle O(1), Complexité spatiale O(n.d).– 32 K entrées (64 bits), 16 ns (sibercore).32 K entrées (64 bits), 16 ns (sibercore).

SRAM (Static Random Access Memory)SRAM (Static Random Access Memory)

(@S,@D,PS,PD) SRAM Action

– Complexité temporelle O(1)/O(n), Complexité spatiale O(n.d).Complexité temporelle O(1)/O(n), Complexité spatiale O(n.d).– 32 Mbits, 10 ns (motorola).32 Mbits, 10 ns (motorola).

Fonction de hachage

pointeur

2-2, 3/9

Mémoires cachesMémoires caches

Vitesse de classification très importanteVitesse de classification très importante– 60 Mp/s.60 Mp/s.

Taille faibleTaille faible– Utilisation fréquente du classificateur Utilisation fréquente du classificateur

logiciel.logiciel.– Sensible au dénis de service.Sensible au dénis de service.– Nombre de champ de recherche limité (CAM Nombre de champ de recherche limité (CAM

255 bits, SRAM fonction de la FH).255 bits, SRAM fonction de la FH).

2-2, 4/9

Parallèlisation du Parallèlisation du processus de classificationprocessus de classification

Ex: Lakshman, Stiliadis [SIGCOMM98], CT : O(log(2n+1)), CS : O(d.nEx: Lakshman, Stiliadis [SIGCOMM98], CT : O(log(2n+1)), CS : O(d.n22)). )).

R0R1

R2

X

110 111&

110

010

110

010

011

001

000

000 001 101 111 011 010

2n + 1 tableaux de n champs R1

Log(d) +1

2-2, 5/9

Log(2n+1) +1Recherche par arbre binaire

Flux

Parallélisation du Parallélisation du processus de classificationprocessus de classification

Solution généraleSolution générale– Vitesse de classification constante.Vitesse de classification constante.– Ne dépend pas du type de traffic/de politique.Ne dépend pas du type de traffic/de politique.

Vitesse de classification moyenne (1 Mp/s).Vitesse de classification moyenne (1 Mp/s). Solution hardware uniquement.Solution hardware uniquement. Difficulté d ’implémentation lorsque d Difficulté d ’implémentation lorsque d

augmente.augmente.

2-2, 6/9

Utilisation de la Utilisation de la redondance de la politique redondance de la politique

de C.A.de C.A.

Ex: Gupta, McKeown [SIGCOMM99]Ex: Gupta, McKeown [SIGCOMM99]

If @S=A ET @D=B ET PS=C et PD=D

If @S=B ET @D=A ET PS=D et PD=C

If @S=A ET @D=B ET PS=F et PD=D

If @S=B ET @D=A ET PS=D et PD=F

0 0 00 00

1 1 01 01

0 0 10 00

1 1 01 10

0 0 00 00

1 1 01 01

0 0 10 00

1 1 01 10

0 00

1 01

0 10

1 11

00

01

10

11

2-2, 7/9

Utilisation de la Utilisation de la redondance de la politique redondance de la politique

de C.A.de C.A.

Ex: Gupta, McKeown [SIGCOMM99], CT : O(1), CS : ?, Insertion 10sEx: Gupta, McKeown [SIGCOMM99], CT : O(1), CS : ?, Insertion 10s

A

B

0

1

A

B

1

0

@S @D

C

F

00

10

PS

D 01

C

F

01

10

PD

D 0

paquet (A,B,F,D)

00

11

0

1

@

0000

0110

0001

P

1011

10000101

000

111

0001

R

1011

010101Etape 1

Etape 2

Etape 3

0

0

10

00

0

10

10

2-2, 8/9

R2

Utilisation de la Utilisation de la redondance de la politique redondance de la politique

de C.A.de C.A.

Vitesse de classification importanteVitesse de classification importante– 30 Mp/s (hardware), 1 Mp/s (software).30 Mp/s (hardware), 1 Mp/s (software).

Solution non généraleSolution non générale– Marche bien pour les politiques des Marche bien pour les politiques des

auteurs.auteurs.– Evolution des politiques ?Evolution des politiques ?– Temps de mise à jour (10 s).Temps de mise à jour (10 s).

2-2, 9/9

Distribution du processus Distribution du processus de classificationde classification

Distribution interne à un Distribution interne à un équipement.équipement.

Distribution sur plusieurs Distribution sur plusieurs équipements du réseau.équipements du réseau.

Distribution sur les équipements Distribution sur les équipements extrémité.extrémité.

2-3, 1/5

Distribution au sein d’un seul Distribution au sein d’un seul équipementéquipement

La capacité de classification est multipliée par le nombre de classificateursLa capacité de classification est multipliée par le nombre de classificateurs

Firewall

Classificateur

Classificateur

Classificateur

Classificateur

ClassificateurClassificateur

Port 0

Port 1

Port 2

Port 3

Port 4

Port 5

2-3, 2/5

Distribution sur plusieurs Distribution sur plusieurs équipements réseauéquipements réseau

Nesset, Hummen [NDS98], utiliser les capacités de C.A. des équipts réseaux.Nesset, Hummen [NDS98], utiliser les capacités de C.A. des équipts réseaux.

Pont

Switch

Switch

RouteurPC

PC

PC PC

PC

2-3, 3/5

Distribution sur les Distribution sur les équipements extrémitééquipements extrémité

Ex: Bellovin [Login99], utiliser les capacités de C.A. des équipts extrémité.Ex: Bellovin [Login99], utiliser les capacités de C.A. des équipts extrémité.

Pont

Switch

Switch

RouteurPC

PC

PC PC

PC

2-3, 4/5

Distribution du processus Distribution du processus de classificationde classification

Performance du service de C.A.Performance du service de C.A.– Dépend du degré de distribution.Dépend du degré de distribution.

Amélioration indépendante des algorithmes de Amélioration indépendante des algorithmes de classification.classification.

Autres améliorations (contrôle interne…)Autres améliorations (contrôle interne…) Gestion de la politique de C.A.Gestion de la politique de C.A. Intégrité de la politique de C.A.Intégrité de la politique de C.A.

2-3, 5/5

Et l ’ENSTB dans tout ca ?Et l ’ENSTB dans tout ca ? Architecture distribuée du C.A.Architecture distribuée du C.A.

– Contrôle d ’accès par agentsContrôle d ’accès par agents Distribution de politiques de C.A.Distribution de politiques de C.A.

– Optimisation du processus de C.A. sur l ’ensemble du réseau.Optimisation du processus de C.A. sur l ’ensemble du réseau. Définition d ’algorithmes de classificationDéfinition d ’algorithmes de classification

– Projet CARAT (Contrôle d ’Accès et qualité de service dans les Réseaux ATm).Projet CARAT (Contrôle d ’Accès et qualité de service dans les Réseaux ATm).– Partenariat CNET, CELAR, ENSTB.Partenariat CNET, CELAR, ENSTB.– Cartes IFT (CNET), solution générale, pas de parallélisation.Cartes IFT (CNET), solution générale, pas de parallélisation.– Performances: 1 Mp/s, 53 octets, Insertion 1 ms.Performances: 1 Mp/s, 53 octets, Insertion 1 ms.

3, 1/2

ConclusionConclusion Améliorations des performances de C.A. : Plusieurs Améliorations des performances de C.A. : Plusieurs

voies pas forcément divergentes (combinaisons voies pas forcément divergentes (combinaisons possibles).possibles).

Comment juger un outil de contrôle d ’accès :Comment juger un outil de contrôle d ’accès :– Mp/s.Mp/s.– Nombre de champs utilisables.Nombre de champs utilisables.– Nombre de règles pouvant être analysées.Nombre de règles pouvant être analysées.– Temps d ’insertion.Temps d ’insertion.

3, 2/2