Pour avoir un algorithme en O(1), il faut donc être capable de trouver la règle correspondant à ton paquet en O(1)....
Non, et c'est là l'astuce ! ;-)
Le problème fondamental que l'on traite dans les firewalls c'est la classification de paquets basé sur leur header.
En gros, si tu considères chaque champs du header comme une variable entière qui a un domaine fixé (entre 0 et 255 par exemple), tu peux traduire chaque règle de ta configuration comme autant de formules logiques. Ensuite, tu peux 'compiler' ces formules logiques en une seule (en faisant attention de conserver l'ordre de précedence sur les règles).
Le fait de 'compiler' ces formules en une seule est un problème NP-complet. Cependant, tu peux très bien compiler tout ça en dehors du noyau. Une fois que tu as ta formule logique, tu la met dans le noyau et tu n'auras pas à évaluer chaque champs du header plus d'une fois (au plus), ce qui fait que c'est en temps constant puisque tu as un nombre de champs fixé (du moins sur ipv4).
En gros, on retire du noyau toutes les opérations qui ne sont pas nécessaires. Et cela donne une accéleration assez intéressantes (du moins sur les prototypes que l'on a fait jusqu'à présent).
De plus, sur des fichiers de configuration réalistes, on s'en tire à quelques secondes de compilation (il y a une table dans le papier à ce propos). Et on a quelques idées pour encore optimiser le compilateur.
[^] # Re: Benchs et filtrage.....
Posté par Alan_T . En réponse à la dépêche La sécurité en Open Source. Évalué à 1.
Non, et c'est là l'astuce ! ;-)
Le problème fondamental que l'on traite dans les firewalls c'est la classification de paquets basé sur leur header.
En gros, si tu considères chaque champs du header comme une variable entière qui a un domaine fixé (entre 0 et 255 par exemple), tu peux traduire chaque règle de ta configuration comme autant de formules logiques. Ensuite, tu peux 'compiler' ces formules logiques en une seule (en faisant attention de conserver l'ordre de précedence sur les règles).
Le fait de 'compiler' ces formules en une seule est un problème NP-complet. Cependant, tu peux très bien compiler tout ça en dehors du noyau. Une fois que tu as ta formule logique, tu la met dans le noyau et tu n'auras pas à évaluer chaque champs du header plus d'une fois (au plus), ce qui fait que c'est en temps constant puisque tu as un nombre de champs fixé (du moins sur ipv4).
Mais, on explique tout ça mieux dans: http://www.cs.auc.dk/~fleury/papers/CF-infocom2003-submitted.ps.gz(...)
En gros, on retire du noyau toutes les opérations qui ne sont pas nécessaires. Et cela donne une accéleration assez intéressantes (du moins sur les prototypes que l'on a fait jusqu'à présent).
De plus, sur des fichiers de configuration réalistes, on s'en tire à quelques secondes de compilation (il y a une table dans le papier à ce propos). Et on a quelques idées pour encore optimiser le compilateur.