Tableau vers Trie [Résolu]

too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 10:54 - Dernière réponse : too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention
- 20 juin 2016 à 11:51
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
Afficher la suite 

Votre réponse

20 réponses

cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - 8 juin 2016 à 12:07
0
Merci
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.
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 12:36
0
Merci
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)
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - Modifié par cptpingu le 8/06/2016 à 14:15
0
Merci
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...).
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 14:44
0
Merci
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
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - Modifié par cptpingu le 8/06/2016 à 15:14
0
Merci
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 -> permit
lan 192.168.1.0 192.168.1.2 tcp -> permit
wan 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
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 15:06
0
Merci
oui , c'est ça
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - 8 juin 2016 à 15:20
0
Merci
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 ;"
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 16:03
0
Merci
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
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - 8 juin 2016 à 16:14
0
Merci
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) ?
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 16:16
0
Merci
toujours des &
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - Modifié par cptpingu le 8/06/2016 à 16:53
0
Merci
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
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 17:00
0
Merci
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)
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - 8 juin 2016 à 17:15
0
Merci
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).
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 8 juin 2016 à 17:22
0
Merci
merci infiniment pour votre aide et tes conseils
Commenter la réponse de too12
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - Modifié par cptpingu le 10/06/2016 à 10:40
0
Merci
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 securite
typedef 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.
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - Modifié par cptpingu le 10/06/2016 à 11:09
0
Merci
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
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - Modifié par cptpingu le 10/06/2016 à 11:07
0
Merci
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).
Commenter la réponse de too12
cptpingu 3827 Messages postés dimanche 12 décembre 2004Date d'inscriptionModérateurStatut 6 octobre 2018 Dernière intervention - Modifié par cptpingu le 10/06/2016 à 17:24
0
Merci
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
Commenter la réponse de cptpingu
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 10 juin 2016 à 11:08
0
Merci
Merci beaucoup.
Commenter la réponse de too12
too12 22 Messages postés mercredi 8 juin 2016Date d'inscription 5 juillet 2016 Dernière intervention - 20 juin 2016 à 11:51
0
Merci
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;i<pNode->nodes_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;i<pNode->nodes_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;i<pNode->nodes_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;i<pNode->nodes_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;i<pNode->nodes_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;i<pNode->nodes_size;i++)  
{
pNode->nodes=action_node;
}


et quand je mets:
for(i=0;i<pNode->nodes_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.
Commenter la réponse de too12

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.