Episode 1 : où nos héros se lancent un défi
Un bout de code, appelons-le Robert de Saint Loup :
var set = Enumerable.Range(1,1000)
.Select(i => new Point(i,0))
.ToDictionary(p=>p);
Maintenant, pratiquement le même bout de code. Appelons-le Palamède de Charlus :
var set = Enumerable.Range(1,1000)
.Select(i => new Point(i,i))
.ToDictionary(p=>p);
Robert et Palamède on décidé un matin de coller le plus grand nombre de points dans un dictionnaire. Ils auraient aussi pu utiliser un Hashset, mais ils ont leurs lubies. Ils auraient pu faire une vulgaire boucle for et faire des dico.Add mais ce sont des viveurs décadents qui font du LINQ en arborant un mince sourire satisfait. Une chose en entraînant une autre, ils décident de mesurer leur temps d'exécution :
Robert : 2 ms
Palamède : 11 ms
Un peu déçu, Palamède propose d'essayer avec 10000 points, dix fois plus. Ca donne :
Robert : 3 ms
Palamède : 1032 ms
C'est drôle. C'est comme si Palamède mettait cent fois plus de temps pour ajouter dix fois plus d'éléments. Et si on essayait avec 20000 points ?
Robert : 4 ms
Palamède : 3450 ms
Laissons de côté Robert pour le moment. Palamède a mis presque 4 fois plus de temps pour traiter deux fois plus de points. On dirait bien que notre ami est quadratique.
Episode 2 : où l'on révèle pourquoi Palamède est quadratique et, surtout, si c'est grave d'être quadratique (oui, c'est grave)
Palamède commence par accuser LINQ. Mais Robert utilise LINQ lui aussi. Palamède devient tout rouge, puis blanc et d'une toute petite voix demande
au fait ça veut dire quoi quadratique ?
Robert soupire et explique que c'est une façon un peu précieuse pour l'auteur de dire que Palamède a une complexité en O(n2). C'est à dire que, à un facteur multiplicatif constant près, le temps passé par Palamède à traiter n éléments sera de l'ordre de n2. Et c'est pas bon du tout.
Sauf qu'il paraît qu'un dictionnaire c'est en O(1), autrement dit, insérer un élément dans un dictionnaire prend un temps constant, quel que soit le nombre d'éléments déjà présents. Donc ajouter 10 éléments devrait prendre 10 fois plus de temps qu'un seul. Pas 100 fois. Ca devrait être linéraire, quoi (ici, Robert simplifie, la complexité vaut pour un n suffisamment grand, mais il a pas tort sur le fond, ce brave garçon).
Alors c'est la faute du dictionnaire ? Pas vraiment.
Un dictionnaire .Net, comme la plupart des tableaux associatifs/maps/sets du monde est implémenté sur le modèle d'une hashtable. Pour simplifier, on calcule un hash de la clé insérée (en .Net, on appelle GetHashCode() ) et ce hash (éventuellement transformé) donne l'index du tableau contenant la paire clé-valeur. Comme le principe d'un hash est de réduire une instance d'objet à une valeur entière (un Int32 dans le cas de .Net), et qu'on peut avoir plus d'objets que de valeurs de hash possibles (dans le cas du point, il y a (Int32.MaxValue)^2 points possibles pour seulement Int32.MaxValue hash possibles), fatalement il y aura des collisions.
S'il y a collision, on stocke dans la même cellule du tableau (qu'on appelle bucket) une liste de toutes les clé-valeur de même hashcode. Lors de l'insertion on doit parcourir cette liste pour s'assurer que la paire n'existe pas déjà. On doit faire de même pour la récupération. Ca n'a rien de dramatique si le calcul du hash est de bonne qualité, c'est à dire qu'il est bien réparti sur les valeurs possibles et qu'il n'est pas facile de trouver des collisions (on reviendra sur ce point).
On doit faire attention, la fonction de hash doit être bien répartie, pas trop prévisible, mais elle doit être aussi rapide à l'exécution, sinon on passerait beaucoup plus de temps à calculer le hashcode qu'à accéder à la paire clé-valeur.
Résumons : ce n'est pas la faute de LINQ, ce n'est pas la faute du Dictionnaire. C'est donc la faute du Point. Regardons l'implémentation de GetHashcode de System.Drawing.Point :
public override int GetHashCode()
{
return (this.x ^ this.y);
}
Ouh que c'est laid. Presque aussi laid que d'utiliser le XOR comme méthode de chiffrement. Ici, si deux points on les mêmes valeurs pour X et Y, ils auront le même hashcode (zéro). Et c'est précisément ce que fait Palamède.
var set = Enumerable.Range(1,1000)
.Select(i => new Point(i,i))
.ToDictionary(p=>p);
A chaque élément ajouté, on calcule le hashcode, qui vaut invariablement zéro ( i ^ i ). Tous les points se trouvent tous dans le même bucket et le dictionnaire doit parcourir l'intégralité des points déjà stockés dans le bucket pour savoir s'il est déjà présent (il ne l'est pas) et pour l'ajouter au bout. L'ajout d'un nouveau point nécessite donc de parcourir les p points déjà présents. On fait ça n fois et c'est comme ça ma brave dame qu'on se retrouve avec une complexité en n2.
Pour résumer, on a pris un dictionnaire et on se retrouve à faire des recherches linéaires dans une liste. Ah c'était bien la peine.
On pourrait dire que mon exemple est tordu. En fait, pas vraiment. Une implémentation classique des matrices ou vecteurs de grande taille mais avec plein de trous, consiste à faire des sparse matrix, c'est à dire qu'au lieu d'allouer un tableau [n,n] on utilise un dictionnaire et on se contente d'associer des valeurs là où elles existent (en passant une paire (x,y) comme clé et la valeur comme euh valeur), en considérant qu'on renvoie 0 si la valeur n'est pas présente dans la matrice. On perd un peu en performances, on gagne énormément en mémoire occupée. Mais dans le cas d'une matrice identité, seule la diagonale a des valeurs. Si on a le malheur d'utiliser Point comme structure pour représenter la paire (ou si on implémente sa propre classe Pair<T,T> reprenant cette désastreuse fonction de hash), on est mort.
Episode 3 : où l'on apprend que le monde est peuplé de vauriens mal intentionnés
D'accord, mais soyons sérieux, dans un dictionnaire on utilise 95% du temps des chaînes de caractères, et elle est béton la fonction de hash des chaînes de caractères, non ?
Regardez Pluto :
Pardon, regardez plutôt :
public override unsafe int GetHashCode()
{
fixed (char* str = ((char*) this))
{
char* chPtr = str;
int num = 0x15051505;
int num2 = num;
int* numPtr = (int*) chPtr;
for (int i = this.Length; i > 0; i -= 4)
{
num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
if (i <= 2)
break;
num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
numPtr += 2;
}
return (num + (num2 * 0x5d588b65));
}
}
Ca c'est le GetHashcode de System.String. Ca fait des cochonneries avec des pointeurs pour aller vite, ça fait un fold bizarroïde sur la liste des caractères et ça applique joyeusement un modulo à tout ça. Disons qu'il n'est pas trivial de trouver des chaînes de caractères qui ont le même hashcode, et si vous ne le faites pas exprès, il y a peu de chances que ça arrive.
Mais si vous vouliez le faire exprès ? Si, par exemple, vous vouliez faire une blague à un programme qui maintient un dictionnaire en lui passant des url, ou des adresses IP, ou des noms, et que ce pauvre programme se trouve obligé de traiter vos ajouts en n2 au lieu de n.
Et si ce programme était, je sais pas moi, un routeur. Ou un site Web. Et que vous lui passiez cinq mille entrées. Ca lui prendrait cinq mille fois plus de temps que si il n'y avait pas de collisions. Ce n'est pas très gentil et ça s'appelle un Denial of Service.
Scott Crosby et Dan Wallach ont ainsi trouvé une façon vicieuse d'exploiter ces petits détails, à partir d'implémentation connues – et relativement standard – de calculs de hashcode (voir Denial of Service via Algorithmic Complexity Attacks ). Dans leur article, ils montrent comment générer des listes de chaînes différentes qui ont le même hashcode, en variant le plaisir pour certaines versions de Perl, de Python, de librairies C et de Java 1.4 (qui a le double malheur d'avoir une fonction de hash pas géniale pour les strings et d'avoir intégré cette fonction de hash au standard, ce qui signifie que jusque là TOUTES les implémentations de hashcode de chaîne en Java devaient utiliser cet algorithme). Ne croyez pas que .Net est immunisé, trouver la séquence empoisonnée est un peu plus difficile qu'en Java, mais à moins d'utiliser un algorithme de hash cryptographique (SHA-1 et ses amis un peu plus sécurisés - non MD5, on ne parle pas de toi), dont le principe réside dans la difficulté à trouver facilement des collisions mais dont le temps de calcul est bien plus élevé, et qui de toute façon nécessitent bien plus que 32 bits, on n'est pas à l'abri des nuisances.
Pour un exemple d'utilisation malveillante de ce genre d'attaques sur des routeurs ou des filtreurs de paquets : Remote Algorithmic Complexity Attacks against Randomized Hash Tables par Noa Bar-Yosef qui montre en plus qu'on ne peut même pas se protéger en utilisant un masque aléatoire dans sa fonction de hash.
Bon, il est tard. Nous allons laisser Palamède se noyer dans sa mare de désespoir mais je m'en voudrais de ne pas terminer sur une note ensoleillée : vous saviez que le quicksort utilisé à peu près partout pour trier a une complexité moyenne en n log n mais une maximale en n2, et qu'on peut aussi passer un jeu de données tordu (M. Douglas McIlroy) qui force ce pauvre algorithme à faire fumer votre CPU ?
En bonus, encore des attaques de fonctions de hash connues : http://www.team5150.com/~andrew/blog/2007/03/hash_algorithm_attacks.html par Andrew (?)
Categories : Meta
Par
yann on
28/03/2009 22:36 |
Commentaires (8)
Bonjour je m'appelle Yann Schwartz et je suis informaticien (Bonjour Yann ! fait la salle).
Pourquoi un blog ?
- Les deux lecteurs et demi de mon blog personnel n'aiment pas la technique
- Moi si.
Voilà qui est dit.
Maintenant, de quoi vais-je bien pouvoir parler ici ?
De développement, principalement.
Comme je suis vendu à Microsoft un développeur .Net, il sera ici beaucoup question de langages qui se terminent par #, essentiellement C et F de leurs prénoms. On parlera aussi de vocoder, de programmation parallèle, du zen de l'écriture de code, de la psychopathologie de l'informaticien et de son milieu socio-professionnel, de la programmation fonctionnelle et, plus généralement, des choses qui en informatique amusent ou apaisent.
Bon, d'accord, mais pourquoi I am a vocoder ?
Pour le subtil jeu de mots. Parce que I am a vocoder est un morceau parfait d'italo disco, écrit en 82 par euh Gay Cat Park et que j'allais quand même pas appeler ce blog Gay Cat Park.
Et puis les paroles ont l'air d'avoir été générées à l'aide de chaînes de Markov :
I am a vocoder, I am synthetic voice
I am a very extravagant device
Into my box, there are a lot of things
But I will not, tell you about their means
I am a friend of the circulator (??), Which is in love of microprocessor
Is out of memory, for this silicon chips
But is no possible exchange with them his bits (???)
Ensuite, tout blog se doit d'avoir son hymne. Et ce blog, cet extravagant device, en a un. Vous pouvez d'ailleurs l'écouter en haut à droite (dans une version abrégée qui je l'espère sera considérée comme du fair use et ne provoquera pas la coupure de mon accès internµ/#!___