Pour avoir un algorithme en O(1), il faut donc être capable de trouver la règle correspondant à ton paquet en O(1)....
S'il n'y a qu'une règle qui correspond, pas (trop) de problèmes, on peut s'en sortir avec une fonction de hash ou autre chose du genre....
Seulement, dans la réalité vraie du monde de la vie, ben on met en place des règles de filtrage, qui correspondent souvent à différents traffics, avec éventuellement des règles communes à pas mal de paquets suivies de règles spécifiques.
Donc non seulement il faut que tu retrouves des règles associées à un paquet, mais en plus, il faut les retrouver (et les évaluer) dans le bon ordre !!
Il n'y a donc pas vraiment le choix: il faut parser l'ensemble des règles !
Après, il y a différentes facons d'optimiser, toutes (celles que je connais) plus ou moins basées sur un principe: être capable de repérer des ensembles de règles qu'il n'est pas nécessaire d'évaluer.
Ca peut être un système de filtrage "non linéaire" (genre Netfilter qui permet de faire des sauts d'une table vers une autre en fonction de certains critères), un système de "critères cummuns" qui permet de savoir que, si un paquet ne correspond pas à un certain profil, ca n'est pas la peine de le confronter aux <x> règles suivantes (pf, si je me souviens bien, et .... je peux faire ma pub ? :-), etc...
Mais l'algorithme reste en O(n), et on reste de toutes facons en O(n) dans le pire des cas à l'évaluation, et même en O(n) pour le cas "moyen", mais en gagnant du temps quand même....
Après, dans certains cas spécifiques, on peut avoir une évaluation en mieux que O(n) (mais bon, une évaluation systématique en O(1), ca doit vraiment être des cas particuliers...), mais c'est autre chose...
Ou alors, il faut complètement revoir la facon de décrire une politique de filtrage....
Bon courage, mais je suis intéressé par d'éventuels résultats :-)
[^] # Re: Benchs et filtrage.....
Posté par Vanhu . En réponse à la dépêche La sécurité en Open Source. Évalué à 2.
S'il n'y a qu'une règle qui correspond, pas (trop) de problèmes, on peut s'en sortir avec une fonction de hash ou autre chose du genre....
Seulement, dans la réalité vraie du monde de la vie, ben on met en place des règles de filtrage, qui correspondent souvent à différents traffics, avec éventuellement des règles communes à pas mal de paquets suivies de règles spécifiques.
Donc non seulement il faut que tu retrouves des règles associées à un paquet, mais en plus, il faut les retrouver (et les évaluer) dans le bon ordre !!
Il n'y a donc pas vraiment le choix: il faut parser l'ensemble des règles !
Après, il y a différentes facons d'optimiser, toutes (celles que je connais) plus ou moins basées sur un principe: être capable de repérer des ensembles de règles qu'il n'est pas nécessaire d'évaluer.
Ca peut être un système de filtrage "non linéaire" (genre Netfilter qui permet de faire des sauts d'une table vers une autre en fonction de certains critères), un système de "critères cummuns" qui permet de savoir que, si un paquet ne correspond pas à un certain profil, ca n'est pas la peine de le confronter aux <x> règles suivantes (pf, si je me souviens bien, et .... je peux faire ma pub ? :-), etc...
Mais l'algorithme reste en O(n), et on reste de toutes facons en O(n) dans le pire des cas à l'évaluation, et même en O(n) pour le cas "moyen", mais en gagnant du temps quand même....
Après, dans certains cas spécifiques, on peut avoir une évaluation en mieux que O(n) (mais bon, une évaluation systématique en O(1), ca doit vraiment être des cas particuliers...), mais c'est autre chose...
Ou alors, il faut complètement revoir la facon de décrire une politique de filtrage....
Bon courage, mais je suis intéressé par d'éventuels résultats :-)