tableau vers TrieRésolu

Question

Bonjour, 
je suis entrain d’améliorer les performance d'un projet en C,
 le projet utilise lex,et Bison pour parser un fichier qui contient les règles d'une politique de sécurité réseau, exemple de règle: 
"lan : (addr_src = @ipsrc ) & (addr_dest = @ipdst ) & ( tcp ) -> permit ;"

en fait le projet utilise des structures de données (tableaux) qui permet de sauvegarder les règles en mémoire

// structure pour representer adresse ipv4 avec cidr ou sans
typedef struct _addr{
 short egal; // 0 pour representer != ou n'appartient pas, 1 autrement
 struct in_addr addr4;
 struct in6_addr addr6;
 int cidr;

int ipversion;

unsigned long haddr;
 unsigned long hnetmask;
 
} addresse;

// structure pour representer port ou plage de ports
typedef struct _port{
 short egal ; // 0 pour representer != ou n'appartient pas, 1 autrement
 long inf;
 long sup;
} port;

// structure pour representer reste selon type de protocole (TCP-UDP ou ICMP)
typedef struct s_proto{
        struct s_tcp_udp {
  port port_s;
  port port_d;
  short flags ;
  short egal_flags;
 } tcp_udp;
        struct s_icmp{
  short egal_type;
  short type;
  short egal_code;
  short code;
 } icmp;
} proto_packet;

// ligne du tableau pour representer la politique de securite
typedef struct s_tableau {
 unsigned short action;
 unsigned short proto;
     addresse addr_s;
 addresse addr_d;
 proto_packet proto_protocole;
} tab_donnees;

typedef struct
{
 tab_donnees **policy_in;
 tab_donnees **policy_out;
 tab_donnees **policy_lan;

int policy_in_size; 
 int policy_out_size;
 int policy_lan_size;
} access_policy;
   
en fait "tab_donnees" est un tableaux d'objet; je voudrais convertir ce tableau en une Patricia Trie pour que la recherche soit efficace (matcher les objets avec un packet réseaux )

svp aidez moi si vous avez des idées
merci

cptpingu · Answer

Bonjour.

Il y a assez peu de détails donnés, je vais tout de même essayer de t'aider.
Si j'ai bien compris ton besoin, tu voudrais récupérer rapidement pour un paquet réseau, la politique de sécurité associée. Actuellement, tu as un tableau, et le parcourir est trop long. Donc tu aimerais remplacer le tableau par une autre structure de données, plus rapide.

À partir de là, il va falloir détailler ce qui te bloque. Réaliser un "Radix tree" (ou Patricia Tree) générique découpant des char* ne devrait pas poser de soucis. Faire rentrer un paquet réseau dans cette structure consiste simplement à convertir celle-ci en char* (tu peux appliquer la transformation que tu veux, tant que tu appliques bien la même partout).

PS: Merci d'utiliser les balises de code à l'avenir.

too12 · Answer

merci de votre réponse
mais, en fait les règles de la politique de sécurité ce sont eux qui sont sauvegarder dans la mémoire, c -a-d dans un tableaux d'objets pas les paquets réseaux 
après quand je reçois un paquets réseaux je vais parcourir mon tableau et si je trouve un element qui corespond à un autre element dans le paquets (@IP du paquet existe dans le tableau de politique de sécurité,) 

en fait le Patricia Tree est utilisé pour sauvegarder des char* (recherche rapide des string) , est ce que je cree pour chaque element (par exemple @IPsrc) un Trie, ou un Trie pour toute la règle (par exemple:

"lan : (addr_src = @ipsrc ) & (addr_dest = @ipdst ) & ( tcp ) -> permit ;" 
en fait dans cette version du projet, si on a beucoups de règles, les performance diminue

l'objectif est de parcourir  toutes les règles selon la longeur de règle
(principe de Trie)

cptpingu · Answer

Comment fonctionne le projet actuellement ? J'entends par là, peux-tu me décrire comment se passe le matching des règles ?
Est-ce qu'un "tab_donnees" représente la transcription d'une ligne de règle, ou seulement une des conditions d'une règle ?
J'ai déjà besoin de comprendre l'existant avant de pouvoir aller plus loin (et je ne saisi pas du tout comment une règle textuelle est transcrite en une structure tab_donnee**).

Ps: Attention à l'orthographe et à la ponctuation, j'ai beaucoup de mal à te relire (ce n'est pas pour t'embêter, mais l'absence de ponctuation est très gênante pour la compréhension. Par exemple, dans certains phrases je ne sais pas si tu affirmes quelque chose ou si tu poses une question...).

too12 · Answer

le programme:
- charge le fichier contenant la politique de sécurité dans la structure access_policy (via le parser). Ensuite, c’est lui qui est chargé d’analyser chacun des paquets  
- effectue l’action définie par la règle correspondante aux caractéristiques du paquet.

en fait: la structure "tab_données" représente une ligne de règle.

une ligne de règle est parser avec (lex,bison), dans le fichier "readpolicy.y" en remplissant la structure "tab_données" avec  les élément qui construit la règle.  

(type de règle,@ipsrc/cidr ,@ipdst/cidr, portsrc,portdst,type service, action)

après on fait le parcours de la structure "tab_données", en matchant chaque élément de la règle qui correspond a une caractéristique du paquet. 

merci

cptpingu · Answer

Si j'ai bien compris, une ligne de règle a toujours le même format. Elle commence toujours par "type de règle", puis "ip source", puis "ip dest", puis "port source",  puis "port dest", enfin "type service" et "action". Toujours dans le même ordre, toujours avec exactement 7 propriétés.

Tu vas pouvoir effectivement faire un "radix tree". Je te conseille dans un premier temps de faire un simple "trie tree" plus simple à implémenter et à débugger (tu l'amélioreras en radix après).

Par exemple: Ton but va être dans transformer ceci:lan 192.168.1.0 192.168.1.1 tcp -> permitlan 192.168.1.0 192.168.1.2 tcp -> permitwan 192.168.1.0 192.168.1.1 tcp -> permit
En ceci:
lan                               wan  192.168.1.0                       192.168.1.0    [192.168.1.1, 192.168.1.2]        192.168.1.1      tcp                               tcp        permit                            permit

Peux-tu me confirmer que j'ai bien compris ta problématique ?


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

too12 · Answer

oui , c'est ça

cptpingu · Answer

Est-ce que toutes les règles auront *exactement* la forme:
"lan : (addr_src = @ipsrc ) & (addr_dest = @ipdst ) & ( tcp ) -> permit ;"

Ou alors est-il possible d'avoir, l'une des ces constructions ?:
"lan : (addr_src = @ipsrc ) | (addr_dest = @ipdst ) | ( tcp ) -> permit ;" 
"lan : (addr_dest = @ipdst )  & (tcp) & (addr_src = @ipsrc ) -> permit ;"
"lan : (tcp) & (addr_src = @ipsrc ) -> permit ;"
"lan : (tcp) -> permit ;"

too12 · Answer

toutes les règles sont de la forme (avec cette ordre)
"type_de_règle : (addr_src = @ipsrc ) & (addr_dest = @ipdst ) & ( (type_service portinf ... portsup) -> action ;" 

type_de_regle: (LAN,IN,OUT)
typeservice: (tcp,http,udp...)
action: (permit,deny,alert)

mais on peut avoir des règles sans définition de port un  port ou plage de port pour un service donné

ou encore sans définir le CIDR pour une @IP donnée

lan : (addr_src = 192.168.1.1/24) | (addr_dest = 192.168.1.0/20) | ( http 80 ) -> permit ;" out : (addr_src = 192.168.1.1/24 ) | (addr_dest = 192.168.1.2/20 ) | ( tcp 1000 ... 2000 ) -> alert ;" in : (addr_src = 192.168.1.1 ) | (addr_dest = 192.168.1.5) | ( udp ) -> deny ;" 

merci bien

cptpingu · Answer

C'est très clair, merci. 
Dernière petite question: est-ce toujours des "&" ou peut-il y avoir des "|" (ou un mélange des deux) ?

too12 · Answer

toujours des &

cptpingu · Answer

Au vu de la structure, tu as de la chance, ça sera moins compliqué que prévu :)

La structure a une hauteur fixe, dont chaque "étage" est similaire. On peut donc faire un tri tree (et plus tard l'améliorer en radix tree) de "hauteur" complètement fixe. Ça sera pour le coup bien plus simple à implémenter.

Ce que tu vas faire, c'est créer un arbre générale de hauteur 5, contenant:

 Étage 1: type_de_règle
 Étage 2: addr_src
 Étage 3: addr_dest
 Étage 4: type_service
 Étage 5: action

Voici un exemple d'arbre pour les règles:
lan : (addr_src = 192.168.1.0/24) | (addr_dest = 192.168.1.0/20) | ( http 80 ) -> permit ;" lan : (addr_src = 192.168.1.1/24) | (addr_dest = 192.168.1.0/20) | ( http 80 ) -> permit ;" lan : (addr_src = 192.168.1.1/24) | (addr_dest = 192.168.1.2/20) | ( http 80 ) -> permit ;" lan : (addr_src = 192.168.1.1/24) | (addr_dest = 192.168.1.2/20) | ( tcp 1000 ... 2000 ) -> permit ;" out : (addr_src = 192.168.1.1/24 ) | (addr_dest = 192.168.1.2/20 ) | ( tcp 1000 ... 2000 ) -> alert ;" in : (addr_src = 192.168.1.1 ) | (addr_dest = 192.168.1.5) | ( udp ) -> deny ;"
 
Qui donnera (visuellement) ceci:
                             lan                                                     out                         in                  /                         \                                         |                           |        192.168.1.0/24               192.168.1.1/24                             192.168.1.1/24              192.168.1.1               |                    /             \                                   |                           |        192.168.1.0/20    192.168.1.0/20      192.168.1.2/20                    192.168.1.2/20              192.168.1.5               |              |              /          \                             |                           |           http 80          http 80      http 80    tcp 1000 ... 2000          tcp 1000 ... 2000                 udp               |              |            |                |                         |                           |           permit          permit        permit           permit                    alert                       deny

Au niveau de la structure de données, ça va fortement ressembler à un arbre général.

typedef struct
{
  unsigned short action; // permit, alert, deny, ...
} action_node;

typedef struct
{
  proto_packet proto_protocole; // tcp 1000..2000, http 80, etc...
  action_node** nodes;
  unsigned int nodes_size;
} type_service_node;

typedef struct
{
  addresse addr; // ip_dest
  type_service_node** nodes;
  unsigned int nodes_size;
} addr_dest_node;

typedef struct
{
  addresse addr; // ip_src
  addr_dest_node** nodes;
  unsigned int nodes_size;
} addr_src_node;

typedef struct
{
  unsigned short proto; // lan, in, out
  addr_src_node** nodes;
  unsigned int nodes_size;
} rule_node;

typedef struct
{
  rule_node** nodes;
  unsigned int nodes_size;
} tree_type;


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

too12 · Answer

merci beaucoup

juste une petite question, peut-on transformer cet arbre général en Radix trie "facilement" , 
est ce que je peut utiliser  (cprpos: http://cprops.sourceforge.net)  qui  offre une meilleur implémentation de radix trie)

cptpingu · Answer

juste une petite question, peut-on transformer cet arbre général en Radix trie "facilement"
Oui. Au final, un radix tree veut juste dire qu'au lieu d'avoir une valeur par noeuds, tu regroupes N valeurs.
Il suffit alors de remplacer tes structures pour qu'elles aient un tableau de valeurs au lieu d'une valeur.
Exemple:
typedef struct
{
  addresse addr; // ip_src
  addr_dest_node** nodes;
  unsigned int nodes_size;
} addr_src_node;

// Deviendra:

typedef struct
{
  addresse* addr; // tableau d'ip_src
  addr_dest_node** nodes;
  unsigned int nodes_size;
} addr_src_node;

L'algo changera légèrement puisqu'il faudra se rendre compte des "fusions" et "éclatement" de noeuds lors de l'insertion (mais là on est plus dans la difficulté inhérente à l'implémentation d'un radix tree plus que dans le design des structures qui ne changent pratiquement pas).

est ce que je peut utiliser (cprpos: http://cprops.sourceforge.net) qui offre une meilleur implémentation de radix trie)
Aucune idée. Je ne connais pas. Après, si tu as une structure dédiée à ton souci, c'est généralement meilleur qu'une implémentation générique (ou tu ne pourras que stocker des noeuds de même nature, alors que là, tu peux "tricher" et avoir un type de noeud par étage).

too12 · Answer

merci infiniment pour votre aide et tes conseils

too12 · Answer

Bonjour.

En fait j'ai un petit soucis concernant la structure que vous m'avez donné, dans la section :

typedef struct{  proto_packet proto_protocole; // tcp 1000..2000, http 80, etc...  action_node** nodes;  unsigned int nodes_size;} type_service_node;

Au niveau de règles, il ya le type de service (http, udp, tcp...) et le reste suivant le type de service (c-à-d les port).
Dans la structure actuelle "tab_données", on a "proto_packet":
// structure pour representer reste selon type de protocole (TCP-UDP //ou ICMP)typedef struct s_proto{        struct s_tcp_udp {  port port_s;  port port_d;  short flags ;  short egal_flags; } tcp_udp;        struct s_icmp{  short egal_type;  short type;  short egal_code;  short code; } icmp;} proto_packet;

Le nom de service (tcp, udp, ...) existe dans la structure:
// ligne du tableau pour representer la politique de securitetypedef struct s_tableau { unsigned short action; // permit,deny,alert unsigned short proto; // type de service tcp,udp,...     addresse addr_s; addresse addr_d; proto_packet proto_protocole; // reste du protocole suivant le ype de service} tab_donnees;
 
Est-ce que je modifie le trie Tree general comme ça ? :
typedef struct{  unsigned short action; // permit, alert, deny, ...} action_node;typedef struct{  unsigned short type_proto; // tcp,udp,http,...........} type_proto_node;typedef struct{  proto_packet proto_protocole; // rest du proto 1000..2000,  80, etc...  action_node** nodes;  type_proto_node** nodes;  unsigned int nodes_size;} type_service_node;

Merci de votre réponse.

cptpingu · Answer

Tu peux effectivement le modifier comme ceci. Je viens de me rendre compte qu'on pourrait aussi simplifier un peu cette structure.
On pourrait directement faire cela:
typedef struct
{
  proto_packet proto_protocole; // rest du proto 1000..2000,  80, etc...
  unsigned short action; // permit, alert, deny, ...
  unsigned short type_proto; // tcp,udp,http,...........
} type_service_node; 

Le "type_proto" ne change pas au niveau d'un noeud "type_service", et le "action" n'est pas censé être en double (donc pas besoin de liste de noeuds pour la règle "action", puisque tu ne peux pas avoir "permit", et "deny" pour exactement la même règle).


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

too12 · Answer

Merci beaucoup.
J'ai une dernière question,  je ne vois pas l’intérêt du champs: unsigned int nodes_size; pour toutes les structures.

Oui effectivement, par contre on pourra avoir deux règles identiques avec deux actions différentes le cas (alert et deny) ou (alert et permit).

cptpingu · Answer

Les champs "nodes_size" donnent la taille du tableau "nodes"  associé. Je l'aurais implémenté sous forme de tableau. Si tu choisis de le faire sous forme de tableau délimité à sa fin par un 0, alors cette taille n'est effectivement plus nécessaire.
De même, si tu choisis que "nodes" est une liste chaînée, la taille n'est plus nécessaire.
Néanmoins, un tableau dont les informations sont contigües, sera plus performant qu'une liste chaînée.

Si tu peux avoir deux règles identiques avec des "actions" différentes, alors il faut laisser le tableau de noeuds pour les "actions".
 

Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

too12 · Answer

Merci beaucoup.

too12 · Answer

Bonjour, je reviens vers vous pour m'aider sur la structure que vous m'avez proposé. "tree type" j'arrive pas à créer le tableau "Nodes" pour chaque nœud associé: voila mon code pour créer chaque nœud de l'arbre général : action_node *get_Action_Node(unsigned short action){ action_node *pNode=NULL; pNode=(action_node *)malloc(sizeof(action_node)); if(pNode) { pNode->action=action; } return pNode;}//------------------------------------------------------------------------ type_service_node *get_Service_Node(unsigned short type_service,proto_packet reste_proto,unsigned int size_node,action_node *action_node){ type_service_node *pNode=NULL; pNode=(type_service_node *)malloc(sizeof(type_service_node)); int i; pNode->nodes_size=size_node; if(pNode) { for(i=0;inodes_size;i++) { pNode->nodes=action_node; } pNode->type_proto=type_service; pNode->proto_protocole=reste_proto; } return pNode;} //----------------------------------------------------------------------------------------addr_dest_node *get_addr_dest_Node(addresse addr_dst,unsigned int size_node,type_service_node *service_node){ addr_dest_node *pNode=NULL; pNode=(addr_dest_node *)malloc(sizeof(addr_dest_node)); int i; pNode->nodes_size=size_node; if(pNode) { for(i=0;inodes_size;i++) { pNode->nodes=service_node; } pNode->addr=addr_dst; } return pNode;}//addr_src_node *get_addr_src_Node(addresse addr_src,unsigned int size_node,addr_dest_node *addr_dst_node){ addr_src_node *pNode=NULL; pNode=(addr_src_node *)malloc(sizeof(addr_src_node)); int i; pNode->nodes_size=size_node; if(pNode) { for(i=0;inodes_size;i++) { pNode->nodes=addr_dst_node; } pNode->addr=addr_src; } return pNode;}//rule_node *get_type_rule_Node(unsigned short rule_type,unsigned int size_node,addr_src_node *addr_src_node){ rule_node *pNode=NULL; pNode=(rule_node *)malloc(sizeof(rule_node)); int i; pNode->nodes_size=size_node; if(pNode) { for(i=0;inodes_size;i++) { pNode->nodes=addr_src_node; } pNode->type_rule=rule_type; } return pNode;}tree_type *get_tree_type_Node(unsigned int size_node,rule_node *rule_node){ tree_type *pNode=NULL; pNode=(tree_type *)malloc(sizeof(tree_type)); int i; pNode->nodes_size=size_node; if(pNode) { for(i=0;inodes_size;i++) { pNode->nodes=rule_node; } } return pNode;} en fait je fais une boucle pour créer le tableau "Nodes" pour chaque nœud de l'arbre général (de 5 étage): for(i=0;inodes_size;i++) { pNode->nodes=action_node; } et quand je mets: for(i=0;inodes_size;i++) { pNode->nodes[i]=action_node; } ça marche pas (erreur segmentation fault) merci de m'aider à remplire l' arbre à partir d'une règle donnée.

Tableau vers Trie

20 réponses

Votre réponse

Discussions similaires