Suite aux nombreuses discussions qu'on a eues ici au sujet de la
recherche de chaînes de caractères, j'ai fait un petit programme qui
recherche plusieurs chaînes à la fois. Plus concrètement: le fichier
n'est examiné du début à la fin qu'une seule fois, il n'y a donc pas
besoin d'examiner le fichier x fois pour x chaînes.
D'abord le procédé et les résultats pour ceux qui ne s'intéressent pas
au côté technique:
J'ai généré quelques essais philosophiques avec le générateur de
http://www.charabia.net puis j'en ai fait un fichier de 22 Mo (appelons
le "texte"). Ensuite j'ai laissé un programme créer 800 chaînes de
caractères minuscules de l'alphabet d'une longueur aléatoire de 5 à 20
caractères (appelons ça la "liste"). Bien sûr, aucune de ces chaînes
n'apparaît dans le texte, mais c'est voulu car ainsi le moteur de
recherche est obligé de parcourir les 22 Mo.
Résultats (Athlon 4 mobile 1 GHz, 256 Mo, Windows 98 SE,
meilleur résultat obtenu) par nombre de signatures:
1: 0,69 secondes pour 21,543 Mo = 31 Mo/s
2: 0,76 secondes pour 21,543 Mo = 28 Mo/s
10: 1,12 secondes pour 21,543 Mo = 19 Mo/s
100: 1,12 secondes pour 21,543 Mo = 19 Mo/s
200: 1,24 secondes pour 21,543 Mo = 17 Mo/s
400: 1,41 secondes pour 21,543 Mo = 15 Mo/s
800: 1,50 secondes pour 21,543 Mo = 14 Mo/s
Attention à deux choses:
- les mesures ne sont pas tout à fait exactes car l'environnement dans
lequel un programme s'exécute change très souvent sur les ordinateurs
modernes (état du processeur, exécution simultanée d'autres programmes,
etc.)
- dans un autre contexte avec un autre texte et une autre liste, on peut
obtenir des résultats différents. En effet, la vitesse de l'algorithme
est influencée par la structure du texte.
Mais bon, ça donne un aperçu et on devrait pouvoir constater la même
évolution dans d'autres conditions aussi.
Donc 800 signatures prennent plus longtemps qu'une seule, par contre le
temps moyen requis pour une signature baisse vertigineusement vite.
Pour en revenir à nos virus: le nombre de signatures influence
certainement la vitesse, mais c'est tout à fait négligeable (surtout
quand on considère que j'ai employé un algorithme de base sans
optimisation particulière, contrairement aux éditeurs qui se donnent
certainement plus de mal). On peut partir du principe que l'évolution
des performances du matériel se fera plus rapidement que celle du nombre
de virus. Faut du moins l'espérer. :-)
Du côté technique maintenant: en fait, au tout début, le programme crée
un arbre à partir des signatures. Si l'on prend les quatre chaînes
"sac", "sale", "sot" et "bleu", on obtient ceci:
b - l - e - u
racine -
s - a - c
- l - e
- o - t
Lors de la recherche, pour chaque caractère rencontré, le programme
vérifie s'il existe une branche de l'arbre qui commence par ce
caractère. Si ce n'est pas le cas, il continue avec le prochain
caractère (par exemple, ici, si le programme rencontrait le caractère
"z", il continuerait). Si par contre une telle branche existe, alors il
lit le prochain caractère et vérifie de nouveau si cette branche possède
elle-même une branche qui commence par le caractère qu'il vient de lire
et ainsi de suite. Arrivé à la fin d'une branche, c'est l'alerte.
Il y a différentes manières de réaliser ça en pratique. J'ai choisi la
manière la plus simple, qui a le malheur de consommer le plus de
mémoire. Dans mon cas, plus de 1 ko par caractère. J'ai aussi triché
pour la réservation de la mémoire - elle est réservée d'avance, comme ça
il n'y a pas besoin de la réserver au fur et à mesure en petites portions.
Pour ne pas être trop hors-sujet, j'ai fait un autre petit programme qui
recherche des chaînes d'octets appartenant à quatre bestioles bien
connues dans la première section exécutable d'une série de fichiers PE:
Swen.A, Opaserv.A, Ganda.A et Happy99.
Maintenant on peut discuter si oui ou non c'est intelligent de
n'examiner qu'une seule section et si les signatures ont été bien
choisies et patati et patata, mais ce n'est pas ça le problème. Il
s'agit avant tout d'illustrer le fonctionnement de l'algorithme et de
permettre de le voir en action en pratique, pas d'écrire un antivirus de
la mort qui tue.
L'exécutable est là:
http://www.uni-koblenz.de/~fbonroy/cv/cv.exe
Le code source (Pascal) est là:
http://www.uni-koblenz.de/~fbonroy/cv/cv.dpr
Il y a beaucoup de choses dans ce programme que j'ai faites pour la
première fois (décortiquer le PE par exemple, faut avoir les nerfs
solides), donc vous excuserez le mauvais style. :-)
Attention, vous ne pouvez examiner que les fichiers qui se trouvent dans
le même répertoire que cv.exe. Si vous possédez donc des fichiers que
vous voulez examiner, copiez les dans le même répertoire que cv.exe et
tapez cv *.* ou cv *.exe ou cv *.vir ou ce que vous voulez.
Vous pouvez aussi indiquer la cadence de votre processeur en MHz sur la
ligne de commande, comme ceci:
cv *.* 1000
(Exemple pour un processeur de 1 GHz). A partir de cela, le programme
pourra vous donner plus d'informations sur sa vitesse d'exécution. Exemple:
D:\cv>cv *.vir 1000
opaserva.vir: Opaserv.A
swen-a.vir: Swen.A
gandaa.vir: Ganda.A
0.00292 secondes pour 0.078 Mo = 27 Mo/s
Taille de l'arbre: 84 ko
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
pat
L'idee me semble en premiere lecture interessante mais je ne suis pas vraiment persuade que cette facon de faire change radicalement la complexite de la methode. Celle ci va etre selon moi d'autant plus efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi ce qui justifie que plus le nombre de chaines recherchees augmentent, plus le temps moyen de recherche diminue (car plus le nombre de chaines augmentent, plus la probabilite de pouvoir creer des branches augmentent et diminuent le nombre de noeud).
Maintenant, je pense que rechercher les 800 chaines une a une meme tres simplement sera au moins aussi efficace en temps que cette methode. Pour apporter une modeste contribution au sujet, une petite suggestion pour rester ds le tres simple : on parcourt une fois le texte et on construit une table indicee sur les caracteres qui donne la position d'un caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante : T[S,1]=1 T[S,2] T[A,1]=2 T[A,2]=6 T[L,1]=3 T[U,1]=4 T[U,2]=9 T[T,1]=5 T[T,2]=7 T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere de recherche : par exemple, si on recherche une chaine commencant par un 'U', on se positionne soit en position 4 soit en position 9 (il suffit de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de parcourir a chaque fois tous le texte pour chaque chaine donnee.
Bon courage pour la suite
L'idee me semble en premiere lecture interessante mais je ne suis pas
vraiment persuade que cette facon de faire change radicalement la
complexite de la methode. Celle ci va etre selon moi d'autant plus
efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi
ce qui justifie que plus le nombre de chaines recherchees augmentent,
plus le temps moyen de recherche diminue (car plus le nombre de chaines
augmentent, plus la probabilite de pouvoir creer des branches augmentent
et diminuent le nombre de noeud).
Maintenant, je pense que rechercher les 800 chaines une a une meme tres
simplement sera au moins aussi efficace en temps que cette methode. Pour
apporter une modeste contribution au sujet, une petite suggestion pour
rester ds le tres simple : on parcourt une fois le texte et on construit
une table indicee sur les caracteres qui donne la position d'un
caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante :
T[S,1]=1 T[S,2]
T[A,1]=2 T[A,2]=6
T[L,1]=3
T[U,1]=4 T[U,2]=9
T[T,1]=5 T[T,2]=7
T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere
de recherche : par exemple, si on recherche une chaine commencant par un
'U', on se positionne soit en position 4 soit en position 9 (il suffit
de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de
parcourir a chaque fois tous le texte pour chaque chaine donnee.
L'idee me semble en premiere lecture interessante mais je ne suis pas vraiment persuade que cette facon de faire change radicalement la complexite de la methode. Celle ci va etre selon moi d'autant plus efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi ce qui justifie que plus le nombre de chaines recherchees augmentent, plus le temps moyen de recherche diminue (car plus le nombre de chaines augmentent, plus la probabilite de pouvoir creer des branches augmentent et diminuent le nombre de noeud).
Maintenant, je pense que rechercher les 800 chaines une a une meme tres simplement sera au moins aussi efficace en temps que cette methode. Pour apporter une modeste contribution au sujet, une petite suggestion pour rester ds le tres simple : on parcourt une fois le texte et on construit une table indicee sur les caracteres qui donne la position d'un caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante : T[S,1]=1 T[S,2] T[A,1]=2 T[A,2]=6 T[L,1]=3 T[U,1]=4 T[U,2]=9 T[T,1]=5 T[T,2]=7 T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere de recherche : par exemple, si on recherche une chaine commencant par un 'U', on se positionne soit en position 4 soit en position 9 (il suffit de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de parcourir a chaque fois tous le texte pour chaque chaine donnee.
Bon courage pour la suite
Frederic Bonroy
pat wrote:
L'idee me semble en premiere lecture interessante mais je ne suis pas vraiment persuade que cette facon de faire change radicalement la complexite de la methode. Celle ci va etre selon moi d'autant plus efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi ce qui justifie que plus le nombre de chaines recherchees augmentent, plus le temps moyen de recherche diminue (car plus le nombre de chaines augmentent, plus la probabilite de pouvoir creer des branches augmentent et diminuent le nombre de noeud). Maintenant, je pense que rechercher les 800 chaines une a une meme tres simplement sera au moins aussi efficace en temps que cette methode.
Là je ne vous suis pas. Le temps moyen diminue par exemple quand deux chaînes commencent par le même caractère. Admettons qu'il y ait deux chaînes qui commencent par "a". Si le programme tombe sur le caractère "b", alors les deux chaînes sont tout de suite exclues. Il n'y a pas besoin de vérifier deux fois si "a" = "b". La diminution est due au fait que plus il y a de chaînes, plus il est probable que plusieurs de ces chaînes puissent être exclues en même temps.
Si vous recherchez les 800 chaînes une par une, alors vous multipliez la durée par 800 (pas tout à fait à cause des effets de cache et des longueurs variables des chaînes, mais faisons-en abstraction).
Ce qui ralentit la recherche, c'est la structure du texte. Si on a deux chaînes débutant en "a" et que le texte entier ne contient que des "a" alors ce sera très lent. Mais là ce n'est pas un problème du nombre de chaînes.
Pour apporter une modeste contribution au sujet, une petite suggestion pour rester ds le tres simple : on parcourt une fois le texte et on construit une table indicee sur les caracteres qui donne la position d'un caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante : T[S,1]=1 T[S,2] T[A,1]=2 T[A,2]=6 T[L,1]=3 T[U,1]=4 T[U,2]=9 T[T,1]=5 T[T,2]=7 T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere de recherche : par exemple, si on recherche une chaine commencant par un 'U', on se positionne soit en position 4 soit en position 9 (il suffit de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de parcourir a chaque fois tous le texte pour chaque chaine donnee.
Ce n'est pas bête comme idée, du moins en théorie. Il faudrait l'essayer. Le problème que je vois, c'est que cela ne résout pas le probléme de la recherche de plusieurs chaînes à la fois (imaginez que vous avez plusieurs chaînes commençant par un "U"). Ça peut seulement procurer une accélération supplémentaire, mais cette table risque de consommer beaucoup de mémoire.
Le problème est toujours le même - si on avait des quantités illimitées de mémoire on pourrait tout faire. Hélas ce n'est pas le cas. :-(
pat wrote:
L'idee me semble en premiere lecture interessante mais je ne suis pas
vraiment persuade que cette facon de faire change radicalement la
complexite de la methode. Celle ci va etre selon moi d'autant plus
efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi
ce qui justifie que plus le nombre de chaines recherchees augmentent,
plus le temps moyen de recherche diminue (car plus le nombre de chaines
augmentent, plus la probabilite de pouvoir creer des branches augmentent
et diminuent le nombre de noeud).
Maintenant, je pense que rechercher les 800 chaines une a une meme tres
simplement sera au moins aussi efficace en temps que cette methode.
Là je ne vous suis pas. Le temps moyen diminue par exemple quand deux
chaînes commencent par le même caractère. Admettons qu'il y ait deux
chaînes qui commencent par "a". Si le programme tombe sur le caractère
"b", alors les deux chaînes sont tout de suite exclues. Il n'y a pas
besoin de vérifier deux fois si "a" = "b". La diminution est due au fait
que plus il y a de chaînes, plus il est probable que plusieurs de ces
chaînes puissent être exclues en même temps.
Si vous recherchez les 800 chaînes une par une, alors vous multipliez la
durée par 800 (pas tout à fait à cause des effets de cache et des
longueurs variables des chaînes, mais faisons-en abstraction).
Ce qui ralentit la recherche, c'est la structure du texte. Si on a deux
chaînes débutant en "a" et que le texte entier ne contient que des "a"
alors ce sera très lent. Mais là ce n'est pas un problème du nombre de
chaînes.
Pour
apporter une modeste contribution au sujet, une petite suggestion pour
rester ds le tres simple : on parcourt une fois le texte et on construit
une table indicee sur les caracteres qui donne la position d'un
caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante :
T[S,1]=1 T[S,2]
T[A,1]=2 T[A,2]=6
T[L,1]=3
T[U,1]=4 T[U,2]=9
T[T,1]=5 T[T,2]=7
T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere
de recherche : par exemple, si on recherche une chaine commencant par un
'U', on se positionne soit en position 4 soit en position 9 (il suffit
de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de
parcourir a chaque fois tous le texte pour chaque chaine donnee.
Ce n'est pas bête comme idée, du moins en théorie. Il faudrait
l'essayer. Le problème que je vois, c'est que cela ne résout pas le
probléme de la recherche de plusieurs chaînes à la fois (imaginez que
vous avez plusieurs chaînes commençant par un "U"). Ça peut seulement
procurer une accélération supplémentaire, mais cette table risque de
consommer beaucoup de mémoire.
Le problème est toujours le même - si on avait des quantités illimitées
de mémoire on pourrait tout faire. Hélas ce n'est pas le cas. :-(
L'idee me semble en premiere lecture interessante mais je ne suis pas vraiment persuade que cette facon de faire change radicalement la complexite de la methode. Celle ci va etre selon moi d'autant plus efficace que l'arbre genere contiendra moins de noeuds et c'est pour moi ce qui justifie que plus le nombre de chaines recherchees augmentent, plus le temps moyen de recherche diminue (car plus le nombre de chaines augmentent, plus la probabilite de pouvoir creer des branches augmentent et diminuent le nombre de noeud). Maintenant, je pense que rechercher les 800 chaines une a une meme tres simplement sera au moins aussi efficace en temps que cette methode.
Là je ne vous suis pas. Le temps moyen diminue par exemple quand deux chaînes commencent par le même caractère. Admettons qu'il y ait deux chaînes qui commencent par "a". Si le programme tombe sur le caractère "b", alors les deux chaînes sont tout de suite exclues. Il n'y a pas besoin de vérifier deux fois si "a" = "b". La diminution est due au fait que plus il y a de chaînes, plus il est probable que plusieurs de ces chaînes puissent être exclues en même temps.
Si vous recherchez les 800 chaînes une par une, alors vous multipliez la durée par 800 (pas tout à fait à cause des effets de cache et des longueurs variables des chaînes, mais faisons-en abstraction).
Ce qui ralentit la recherche, c'est la structure du texte. Si on a deux chaînes débutant en "a" et que le texte entier ne contient que des "a" alors ce sera très lent. Mais là ce n'est pas un problème du nombre de chaînes.
Pour apporter une modeste contribution au sujet, une petite suggestion pour rester ds le tres simple : on parcourt une fois le texte et on construit une table indicee sur les caracteres qui donne la position d'un caractere donne dans le texte :
exemple : a partir du texte "SALUT A TOUS" on genere la table suivante : T[S,1]=1 T[S,2] T[A,1]=2 T[A,2]=6 T[L,1]=3 T[U,1]=4 T[U,2]=9 T[T,1]=5 T[T,2]=7 T[O,1]=8
A partir de cette table, on accede tres facilement au premiere caractere de recherche : par exemple, si on recherche une chaine commencant par un 'U', on se positionne soit en position 4 soit en position 9 (il suffit de parcourir T[U,.]) et le tour est joue : on a meme plus besoin de parcourir a chaque fois tous le texte pour chaque chaine donnee.
Ce n'est pas bête comme idée, du moins en théorie. Il faudrait l'essayer. Le problème que je vois, c'est que cela ne résout pas le probléme de la recherche de plusieurs chaînes à la fois (imaginez que vous avez plusieurs chaînes commençant par un "U"). Ça peut seulement procurer une accélération supplémentaire, mais cette table risque de consommer beaucoup de mémoire.
Le problème est toujours le même - si on avait des quantités illimitées de mémoire on pourrait tout faire. Hélas ce n'est pas le cas. :-(
