Mon blog

Un des pièges de SQL est que c'est un langage de haut niveau. Le rapport entre la commande qu'on tape et le travail que doit faire la machine est beaucoup moins direct et beaucoup plus dur à saisir qu'avec l'assembleur. Il est donc fréquent qu'une requête SQL qui n'aie pas l'air bien méchante prenne des heures à s'exécuter. Heureusement, PostgreSQL dispose d'une excellent commande EXPLAIN qui explique, avant même qu'on exécute la commande, ce qu'elle va faire et ce qui va prendre du temps.

Un excellent exposé d'introduction est Explaining EXPLAIN mais, uniquement avec les transparents, c'est un peu court. Voyons des exemples d'utilisation d'EXPLAIN sur la base de données de StackOverflow.

Je commence par une requête triviale, SELECT * FROM Votes et je la fais précéder de EXPLAIN pour demander à PostgreSQL de m'expliquer :

so=> EXPLAIN SELECT * FROM Votes;
                           QUERY PLAN                           
----------------------------------------------------------------
 Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=16)
(1 row)

On apprend que PostgreSQL va faire une recherche séquentielle (Seq Scan), ce qui est normal, puisqu'il faudra tout trouver, que 2379537 tuples (lignes de la table SQL) sont à examiner. Et que le coût sera entre... zéro et 36658,37. Pourquoi zéro ? Parce que PostgreSQL affiche le coût de récupérer le premier tuple (important si on traite les données au fur et à mesure, ce qui est souvent le cas en OLTP) et celui de récupérer tous les tuples. (Utiliser LIMIT ne change rien, PostgreSQL calcule les coûts comme si LIMIT n'était pas là.)

Et le 36658,37 ? C'est 36658,37 quoi ? Pommes, bananes, euros, bons points ? Ce coût est exprimé dans une unité arbitraire qui dépend notamment de la puissance de la machine. Avant de lire toute la documentation sur le calcul des coûts, faisons une autre requête :

so=> EXPLAIN SELECT count(*) FROM Votes;
                             QUERY PLAN                              
---------------------------------------------------------------------
 Aggregate  (cost=42607.21..42607.22 rows=1 width=0)
   ->  Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=0)
(2 rows)

Cette fois, le coût du premier tuple est le même que le coût total, ce qui est logique, puisque les fonctions d'agrégation comme count() nécessitent de récupérer toutes les données.

Les coûts qu'affiche EXPLAIN ne sont que des coûts estimés, sans faire effectivement tourner la requête (donc, EXPLAIN est en général très rapide). Si on veut les temps réels, on peut ajouter le mot-clé ANALYZE :

so=> EXPLAIN ANALYZE SELECT * FROM Votes;
                                                    QUERY PLAN                                                     
-------------------------------------------------------------------------------------------------------------------
 Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=16) (actual time=0.042..3036.302 rows=2379537 loops=1)
 Total runtime: 5973.786 ms
(2 rows)

Cette fois, on a le temps effectif, trois secondes. On peut en déduire que, sur cette machine, l'unité de coût de PostgreSQL vaut environ 0,08 milli-secondes (3036,302 / 36658,37). Sur un serveur identique, mais avec des disques de modèle différent et un autre système de fichiers, on arrive à une valeur quasiment identique. Mais sur un simple portable, je mesure un facteur de 0,5 milli-secondes par unité de coût.

De toute façon, il faut faire attention : ce facteur d'échelle dépend de beaucoup de choses, à commencer par les réglages du SGBD. Est-ce que ce ratio de 0,08 milli-secondes peut nous aider à prévoir le temps d'exécution d'une requête ? Voyons une requête plus compliquée qui compte le nombre de votes ayant eu lieu dans les 24 heures ayant suivi le message :

so=> EXPLAIN SELECT count(votes.id) FROM votes, posts WHERE votes.post = posts.id AND 
so->                             votes.creation <= posts.creation + interval '1 day';
                                   QUERY PLAN                                    
---------------------------------------------------------------------------------
 Aggregate  (cost=147911.94..147911.95 rows=1 width=4)
   ->  Hash Join  (cost=31161.46..145928.99 rows=793179 width=4)
         Hash Cond: (votes.post = posts.id)
         Join Filter: (votes.creation <= (posts.creation + '1 day'::interval))
         ->  Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=12)
         ->  Hash  (cost=15834.65..15834.65 rows=881665 width=12)
               ->  Seq Scan on posts  (cost=0.00..15834.65 rows=881665 width=12)
(7 rows)

PostgreSQL affiche un coût de 147911,95 soit 11,8 secondes. Et le résultat effectif est :

so=> EXPLAIN ANALYZE SELECT count(votes.id) FROM votes, posts WHERE votes.post = posts.id AND 
                            votes.creation <= posts.creation + interval '1 day';
                                                            QUERY PLAN                                                             
-----------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=147911.94..147911.95 rows=1 width=4) (actual time=15125.455..15125.456 rows=1 loops=1)
...

soit 15 secondes au lieu des 11 prévues, ce qui n'est pas trop mal, pour une fonction de coût qui agrège beaucoup de choses différentes.

Que voit-on d'autre sur la sortie de EXPLAIN pour cette requête ? Que les coûts s'additionnent (regardez bien l'indentation des lignes commençant par -> pour voir comment faire l'addition). La recherche séquentielle la plus interne (sur la table Posts) coûte 15834,65, le hachage coûte le même prix (il n'a rien ajouté), l'autre recherche séquentielle (sur la table Votes) a un coût de 36658,37 et ces deux coûts vont s'ajouter, ainsi que le filtrage et le test de jointure, pour donner 145928,99, le coût de la jointure. Ensuite, un petit coût supplémentaire restera à payer pour l'agrégat (count()) nous emmenant à 147911,95.

L'addition des coûts se voit encore mieux sur cette requête :

so=> EXPLAIN SELECT count(votes.id)*100/(SELECT count(votes.id) FROM Posts, Votes 
so(>                                 WHERE Votes.post = Posts.id) AS percent
so->        FROM votes, posts WHERE 
so->                    votes.post = posts.id AND 
so->                    votes.creation > (posts.creation + interval '1 day')::date;
                                             QUERY PLAN                                             
----------------------------------------------------------------------------------------------------
 Aggregate  (cost=287472.95..287472.97 rows=1 width=4)
   InitPlan
     ->  Aggregate  (cost=133612.15..133612.16 rows=1 width=4)
           ->  Hash Join  (cost=30300.46..127663.31 rows=2379537 width=4)
                 Hash Cond: (public.votes.post = public.posts.id)
                 ->  Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=8)
                 ->  Hash  (cost=15834.65..15834.65 rows=881665 width=4)
                       ->  Seq Scan on posts  (cost=0.00..15834.65 rows=881665 width=4)
   ->  Hash Join  (cost=31161.46..151877.84 rows=793179 width=4)
         Hash Cond: (public.votes.post = public.posts.id)
         Join Filter: (public.votes.creation > ((public.posts.creation + '1 day'::interval))::date)
         ->  Seq Scan on votes  (cost=0.00..36658.37 rows=2379537 width=12)
         ->  Hash  (cost=15834.65..15834.65 rows=881665 width=12)
               ->  Seq Scan on posts  (cost=0.00..15834.65 rows=881665 width=12)
(14 rows)

dont le temps d'exécution effectif est de 30 secondes, très proche des 23 secondes calculées en multipliant le coût total de 287472,97 par le facteur d'échelle de 0,08 millisecondes.

Plusieurs essais avec des bases très différentes montrent que le facteur d'échelle (la valeur en milli-secondes d'une unité de coût) est plutôt stable. Voici un résultat avec la base de DNSmezzo :

dnsmezzo2=> EXPLAIN ANALYZE SELECT DISTINCT substr(registered_domain,1,43) AS domain,count(registered_domain) AS num FROM DNS_packets WHERE file=3 AND NOT query AND rcode= 3 GROUP BY registered_domain ORDER BY count(registered_domain) DESC;
                                                                            QUERY PLAN                                                                            
------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Unique  (cost=496460.23..496460.31 rows=10 width=12) (actual time=41233.482..42472.861 rows=234779 loops=1)
   ->  Sort  (cost=496460.23..496460.26 rows=10 width=12) (actual time=41233.478..41867.259 rows=234780 loops=1)
         Sort Key: (count(registered_domain)), (substr(registered_domain, 1, 43))
         Sort Method:  external merge  Disk: 11352kB
         ->  HashAggregate  (cost=496459.91..496460.06 rows=10 width=12) (actual time=38954.395..39462.324 rows=234780 loops=1)
               ->  Bitmap Heap Scan on dns_packets  (cost=197782.55..496245.34 rows=42914 width=12) (actual time=34594.268..38306.833 rows=250006 loops=1)
                     Recheck Cond: ((rcode = 3) AND (file = 3))
                     Filter: (NOT query)
                     ->  BitmapAnd  (cost=197782.55..197782.55 rows=87519 width=0) (actual time=34590.468..34590.468 rows=0 loops=1)
                           ->  Bitmap Index Scan on rcode_idx  (cost=0.00..74228.75 rows=1250275 width=0) (actual time=28144.654..28144.654 rows=1290694 loops=1)
                                 Index Cond: (rcode = 3)
                           ->  Bitmap Index Scan on pcap_idx  (cost=0.00..123532.10 rows=2083791 width=0) (actual time=6393.187..6393.187 rows=2233781 loops=1)
                                 Index Cond: (file = 3)
 Total runtime: 42788.863 ms
(14 rows)

La prochaine version de BIND, le serveur de noms le plus répandu sur l'Internet, est désormais en phase active de développement, financée par des organisations comme l'AFNIC. Cette version sera marquée par plusieurs changements majeurs, notamment un mode de développement nettement plus ouvert (BIND 9 avait toujours été géré de manière très privée).

Une liste résumée des principaux changements est en ligne. La nouvelle version sera écrite en C++, avec Python pour les extensions et les scripts. Il existe aussi déjà un Trac public, en https://bind10.isc.org/. Pour l'instant, il contient surtout du remue-méninges. Et il existe une liste de diffusion des développeurs et personnes intéressées.

Le DNS est souvent présenté comme utile, car permettant d'utiliser des identificateurs « conviviaux » (les noms de domaine) plutôt que des suites de chiffres (les adresses IP). Cette explication n'est pas fausse mais elle est très incomplète.

On trouve une justification du DNS analogue à celle-ci en beaucoup d'endroits. L'article de Wikipédia dit « Il n'est pas évident pour un humain de retenir ce numéro lorsque l'on désire accéder à un ordinateur d'Internet. C'est pourquoi un mécanisme a été mis en place pour permettre d'associer à une adresse IP un nom intelligible, humainement plus simple à retenir, appelé nom de domaine.  ». Sur le site de l'AFNIC, on trouve « Sans le DNS, il faudrait mémoriser l'adresse d'un site ou une adresse électronique sous la forme de l'adresse IP du domaine (qui est une suite de chiffres. Exemple : mon-correspondant@[192.134.4.35]) ! ». Et, en anglais, on voit sur le site de l'ICANN « Because IP addresses (which are strings of numbers) are hard to remember, the DNS allows a familiar string of letters (the "domain name") to be used instead. So rather than typing "192.0.34.163," you can type "www.icann.org." ». Mais ce n'est pas parce que tout le monde répète quelque chose que c'est complètement vrai. D'abord, le fait que des identificateurs composés uniquement de chiffres soient moins pratiques n'est pas si évident que cela. Ainsi, les numéros de téléphone restent largement utilisés et n'ont (malheureusement) pas été remplacés par les URL SIP comme sip:helpdesk@voip.apnic.net. (Curiosité : il existe même une proposition de remplacer les noms de domaine par des numéros de téléphone, ENUM.)

Personnellement, je pense que les noms de domaine sont plus simples, car plus mémorisables et plus porteurs d'identité mais, manifestement, tout le monde n'est pas d'accord, sinon les numéros de téléphone auraient disparu depuis longtemps (supprimant également le problème de la portabilité).

Les noms « conviviaux » ont un autre problème : comme ils ont une sémantique, ils font l'objet de conflits. Tout le monde veut sex.com et la multinationale Kraft Foods peut empêcher Mme Milka de garder son nom de domaine s'il correspond à une marque déposée de ladite multinationale.

Néanmoins, le DNS est le système d'identificateur le plus fréquent sur l'Internet. Quasiment toutes les transactions sur le réseau passent par lui, et le trafic sur les serveurs de noms ne cesse pas d'augmenter. C'est parce que les noms de domaine fournissent un service bien plus utile que la « convivialité » des noms : ils fournissent de la stabilité. La plupart des sites Internet reçoivent des adresses IP liées au fournisseur d'accès ou à un hébergeur. Ce sont des adresses PA, dont il faut changer si on change de prestataire. Si je fait de la publicité pour mon blog en annonçant http://208.75.84.80/, son adresse IP actuelle, ce n'est pas seulement « moins joli » et « moins mémorisable » que http://www.bortzmeyer.org/, c'est surtout moins stable. L'adresse IP 208.75.84.80 est liée à l'hébergeur actuel, Slicehost, et devra changer si je passe à un autre hébergeur comme OVH. Et je devrais prévenir tous mes lecteurs, faire corriger tous les articles qui parlaient de ce blog, demander à Google de changer l'URL (tout en gardant mon PageRank), etc.

Bien sûr, il existe des adresses IP indépendantes du fournisseur, les adresses PI. Mais elles ne sont pas forcément faciles à obtenir et, surtout, elles ne résolvent pas complètement la question de la stabilité. Si deux services sont sur la même machine, et ont donc la même adresse IP, et que j'en déménage un seul, il devra bien changer d'adresse, même si l'ancienne et la nouvelle étaient indépendantes du prestataire. En application du principe « Cool URIs don't change », les noms de domaine permettent la permanence des identificateurs.

Et ne parlons même pas de la transition d'adresses IPv4 aux adresses IPv6. Sans l'intermédiaire des noms de domaine, cette transition serait encore plus pénible qu'elle ne l'est.

(Certaines personnes relativisent l'importance de la stabilité des URL en affirmant que les moteurs de recherche permettent de toute façon de retrouver la page Web. D'abord, les noms de domaine ne servent pas qu'au Web. Ensuite, le moteur de recherche ne permet justement aucune stabilité : un jour, taper « hôtel luchon » dans Google mènera à l'hôtel Majestic, un jour à un autre hôtel...)

Comme le savent les lecteurs de ce blog, je suis en général très méfiant vis-à-vis de l'optimisation prématurée des programmes. Pas seulement parce que la plupart des programmeurs qui parlent de performance tout de suite ne mesurent pas le résultat de leurs bricolages mais aussi parce que cette « optimisation » est souvent un prétexte pour faire du code imbittable et inmaintenable. Mais, comme avec toute règle, il y a des exceptions.

Par exemple, si une fonction donnée est appelée très souvent, elle est évidemment une bonne candidate pour des optimisations très poussées. C'est le cas de strlen, fonction de la libc qui mesure la longueur d'une chaîne de caractères en C. Les programmes écrits en C (ce qui inclue les implémentations des langages comme Ruby ou Perl) appellent strlen tout le temps. On peut donc, une fois une mise en œuvre correcte de strlen produite, chercher des optimisations de bas niveau.

Il est par exemple amusant de comparer les deux versions produites par OpenBSD :

• La version portable, triviale,
• et la version optimisée pour les processeurs i386, en assembleur.

La GNU libc dispose également d'une telle version optimisée sur les i386 (version en assembleur pour i586 et plus). Voir aussi un bon article sur l'écriture en assembleur de strlen. Évidemment, strcmp serait encore plus intéressante à étudier, car plus complexe (les deux chaînes n'ont pas forcément la même longueur).

Une autre curiosité pour les amateurs d'optimisation est la discussion sur un strlen() rapide pour UTF-8.

Merci à Victor Stinner pour ses intéressants ajouts.

À la conférence SARSSI à Luchon, j'ai eu le plaisir de faire un tutoriel sur DNSSEC.

SARSSI est une petite conférence scientifique qui se déroule dans un cadre magnifique (surtout qu'il fait beau). Les sessions ont lieu dans le superbe « Pavillon Normand » qui avait été construit à Paris pour une Exposition Universelle et démonté ensuite pour être remonté à Luchon.

Les transparents du tutoriel DNSSEC sont le résultat du travail de plusieurs ingénieurs successifs à l'AFNIC. Voici leur source au format OpenOffice : dnssec-tutorial-sarssi.odp.

Tout le monde sait que le DNS n'est pas sûr. Si quelqu'un n'est pas au courant, il suffit de l'envoyer lire le RFC 3833. En 2008, la faille Kaminsky avait encore remis le dossier de la sécurité DNS sur le dessus de la pile. Les risques étant de natures très variées, il n'y a certainement pas de solution miracle à tous les problèmes de sécurité du DNS. Mais comme l'analyse sérieuse des problèmes de sécurité est difficile, comme la « balle d'argent » est une histoire plus vendeuse que la longue liste des mesures à prendre, on voit souvent une technologie particulière présentée comme la solution à tout. Vu l'expérience avec d'autres créations de Daniel Bernstein, il est probable que DNSCurve sera ainsi promu.

Avant de regarder DNSCurve et ses différences avec le protocole DNSSEC, revenons en arrière sur la sécurité du DNS. Lorsqu'un serveur DNS faisant autorité pour une zone envoie une réponse à un résolveur, un serveur DNS récursif, un méchant peut répondre avant le bon serveur et voir sa réponse acceptée par le résolveur, qui sera alors empoisonné (le RFC 5452 contient une explication plus détaillée et des calculs de la probabilité de réussite). C'est l'une des principales vulnérabilités du DNS.

Pour résoudre ce problème, il y a deux approches. Pour reprendre le vocabulaire du RFC 3552, on peut choisir de sécuriser le canal (vérifier qu'on parle bien à la machine à qui on voulait parler) ou de sécuriser le message (vérifier que le message vient bien de l'autorité et qu'il n'a pas été modifié en route). Les deux méthodes ne sont d'ailleurs pas contradictoires, on peut aussi choisir une défense en profondeur en adoptant les deux approches. En général, la sécurisation du message offre le maximum de sécurité (même si des intermédiaires ne sont pas dignes de confiance, on peut s'assurer de l'authenticité du message, ce qui est une propriété essentielle pour le DNS, qui dépend de tels intermédiaires, les serveurs cache) mais la sécurisation du canal est souvent plus facile à déployer.

Le débat existe pour tous les protocoles Internet. Par exemple, pour le courrier électronique, PGP sécurise le message, SMTP sur TLS (RFC 3207) sécurise le canal.

Dans le monde du DNS, la première solution, sécuriser le canal, est possible grâce à de nomnbreuses technologies :

• TSIG (RFC 2845), une signature de la transaction grâce à une clé secrète partagée entre les deux serveurs,
• SIG(0) (RFC 2931), une signature de la transaction utilisant des clés publiques,
• Diverses techniques de résistance à la fraude, comme le choix au hasard du port source (RFC 5452),
• Puisqu'une grande partie de la vulnérabilité du DNS vient de la taille trop petite du Query ID, il y a des propositions de l'étendre comme les DNS cookies (Internet-Draft draft-eastlake-dnsext-cookies) ou EDNS ping (Internet-Draft draft-hubert-ulevitch-edns-ping),
• IPsec (RFC 3401), si seulement il était déployé,
• Un protocole de transport résistant naturellement aux tricheries, comme TCP ou SCTP,
• Et pourquoi pas des datagrammes protégés par TLS comme avec DTLS (RFC 4347),
• Et enfin DNSCurve.

Toutes ces techniques ont leurs avantages et leurs inconvénients, certaines (comme celles du RFC 5452) ont eu de grands succès (comme de rendre peu exploitable la faille Kaminsky) mais toutes ont en commun de ne sécuriser que le canal entre deux serveurs. Si un serveur esclave d'une zone est contrôlé par un méchant et modifie les données, s'assurer qu'on parle bien à ce serveur ne servira à rien. Idem dans le cas, beaucoup plus fréquent, où un résolveur/cache d'un FAI ment à ses propres clients (cf. RFC 4924, section 2.5.2).

Pour la sécurisation du message, il n'existe à l'heure actuelle qu'une seule méthode, DNSSEC (RFC 4033 et suivants).

Revenons donc à DNSCurve. Cette technique n'est pas normalisée à l'heure actuelle et ne fait pas l'objet d'une spécification détaillée. Il existe juste une présentation sommaire sur le site officiel. Le principe de DNSCurve est que le dialogue entre deux serveurs est chiffré (par un algorithme de la famille des courbes elliptiques, Curve25519) et authentifié. La clé publique du serveur auquel on parle est obtenue dans le DNS, c'est le nom du serveur. Si le TLD .example est délégué à uz5xgm1kx1zj8xsh51zp315k0rw7dcsgyxqh2sl7g8tjg25ltcvhyw.nic.example, le résolveur peut, en examinant ce nom, voir que la délégation est sécurisée par DNSCurve, trouver la clé publique, et interroger le serveur de manière sûre, grâce au chiffrement asymétrique. Seule la communication entre deux serveurs est protégée. Si un des serveurs est une machine pirate, DNSCurve ne sert à rien.

Donc, DNSCurve n'est pas réellement un concurrent de DNSSEC, il traite un problème assez différent. Sur le site officiel, on trouve une comparaison de DNSCurve avec DNSSEC qui est intellectuellemnt très malhonnête, comme presque toujours avec Daniel Bernstein. Notamment, il manque dans le tableau deux points :

Type of security          DNSSEC                   DNSCURVE

Integrity despite         Protects against         Does not protect against
rogue secondary name      it                       it
servers of resolvers

Ability to follow         The actual algo-         Only one algorithm,
the progress in           rithm is not hardwired   if it is broken,
cryptography              in the protocol. New     everything is over.
                          algos can be added.

J'ai signalé ces deux points au mainteneur mais évidemment sans résultat. Le premier de ces deux points vient directement du fait que DNSCurve protège le canal et pas le message. Le second vient du fait que l'algorithme utilisé a été très peu analysé pour l'instant.

Il y a bien d'autres énormités. Par exemple, dire que « NS cache software (e.g., dnscache or PowerDNS Recursor or Unbound or BIND) - Administrator upgrades to a cache that supports DNSSEC. - Administrator upgrades to a cache that supports DNSCurve. » alors que Unbound et BIND ont le support DNSSEC depuis de nombreuses années et que presque tous les administrateurs DNS l'ont déjà installé, même s'ils ne l'ont pas activé (c'est un point important lorsqu'on veut déployer DNSSEC et qu'on se demande si ses serveurs secondaires habituels le géreront). Ou affirmer que NSEC3 est « almost always breakable » en donnant zéro explication (il n'existe actuellement aucune attaque publiée contre NSEC3). Cela se nomme du FUD. Encore un autre exemple de propagande très lourde, dire que « [Avec DNSSEC, ] Administrator must generate new signatures every month » alors qu'une telle contrainte n'apparait nulle part dans le protocole DNSSEC (c'est le signeur qui choisit la durée de validité des signatures, un mois est juste la valeur par défaut du signeur inclus dans BIND). Et, avec DNSCurve, c'est à chaque requête qu'il faut générer une nouvelle signature.

Que peut-on dire encore en comparant ces deux protocoles ? D'abord que DNSSEC a été soigneusement conçu pour que le serveur n'aie aucune opération de cryptographie à faire « par requête » (à l'exception de NSEC3 et encore il ne s'agit que de hachage, pas de chiffrement asymétrique). Toutes les opérations de signature peuvent être faites hors-ligne, une fois pour toute, sur la zone. Au contraire, DNSCurve exige des opérations de signature à chaque requête. Il ne convient donc pas à de gros serveurs.

Il est amusant de noter que la page officielle de DNSCurve reproche à DNSSEC que « DNSSEC reduces existing confidentiality by publishing the complete list of "secured" DNS records. This publication is integrated into the DNSSEC protocol; » alors que cette publication est inhérente au fait de signer la zone et pas chaque requête. Si on est prêt à faire des opérations de cryptographie à chaque requête, les solutions des RFC 4470 et RFC 5155 résolvent le problème de la confidentialité des données.

On peut terminer par un point amusant : avec DNSCurve, la clé publique est encodée dans le nom de la machine. C'est astucieux. Mais les clés de la cryptographie asymétrique sont très longues et les composants d'un nom de domaine sont limités à 63 octets. Cela a deux conséquences :

• Pour les zones qui limitent la taille d'une délégation à 512 octets, comme la racine du DNS, on ne peut utiliser qu'un maximum de trois serveurs avec DNSCurve (car il faut aussi laisser de la place pour la question, et pour la colle).
• DNSCurve n'utilise donc pas les courbes elliptiques parce qu'elles sont meilleures que les algorithmes basés sur la factorisation des nombres premiers (comme RSA) mais simplement parce qu'elles permettent des clés plus courtes. Le fait de les mettre dans les noms de domaine va sérieusement contraindre l'évolution ultérieure de DNSCurve. Il sera par exemple impossible d'augmenter la taille des clés.

Merci à Kim Minh Kaplan pour ses nombreuses et pertinentes remarques sur DNSCurve.

Parmi les écrivains français d'aventure de la « Belle Époque », Maurice Renard est nettement moins connu que Jules Verne ou J.-H. Rosny aîné. On cite souvent uniquement son livre « Les Mains d'Orlac ». Mais il est aussi l'auteur d'un fantastique roman, « Le Péril bleu ».

Le livre n'a pas été réédité depuis trente ans. Il s'inscrit clairement dans le courant du roman « pré-science-fiction » français. Je ne peux absolument pas raconter l'histoire, car beaucoup repose sur les surprises successives (et ne lisez donc pas l'article de Wikipédia avant le livre !). Dans une petite région tranquille de France, le Bugey, deux années avant la première guerre mondiale, dans un monde qui se croit stable, où les ouvriers restent à leur place, où les bourgeois républicains rêvent de marier leur fille avec un noble, où les allemands sont des méchants militaristes, où les policiers ont forcément d'épaisses moustaches et où les paysans sont assez abrutis, mais fidèles, de mystérieuses disparitions d'objets se produisent. Drôles au début, elles vont vite devenir plus dramatiques. Pour retrouver les mystérieux « Sarvants », comme les gens du pays appellent leurs persécuteurs, sur quoi peut-on compter ? Sur la science de l'astronome Le Tellier ou de son assistant Robert Collin ? Sur la fougue sportive du jeune, beau et riche duc d'Agnès ? Sur les capacités de déduction du détective amateur Tiburce ?

Le livre passe du tragique au très drôle (excellente caricature du concurrent des romains anglais, Sherlock Holmes, bien plus drôle que celle de Maurice Leblanc). Il y a d'innombrables pistes à suivre et toutes ne sont pas fausses...

À l'heure où on recommande les lectures de vacances, voici mon conseil : allez enquêter au Bugey. Et voyez si vous déduirez mieux que Tiburce.

Les érudits peuvent aussi emporter à la plage « La science-fiction française au XXe siècle (1900-1968) » de Jean-Marc Gouanvic (éditions Rodopi), qui détaille longuement le Péril bleu.

Comment signale t-on un problème sur l'Internet ? Si un ver fait des requêtes HTTP répétées à la recherche d'une vulnérabilité ? Si un autre ver se connecte en SSH en permanence à votre Kimsufi en tentant le compte guest ? Si un script utilise automatiquement votre service en dépit des conditions d'utilisation ? Si vous recevez du spam depuis telle ou telle machine ? En théorie, il existe une adresse de courrier standard pour cela. Spécifiée dans le RFC 2142, c'est abuse@DOMAIN.EXAMPLE où DOMAIN.EXAMPLE est le domaine en cause. Mais le courrier envoyé à abuse n'obtient jamais de réponse et, souvent, n'est même pas lu. Pourquoi ?

Au cours de ma carrière, j'ai été des deux côtés de la barrière, du côté de ceux qui reçoivent les messages envoyés à abuse et du côté de ceux qui les envoient. Du côté du simple utilisateur, qui voudrait signaler un problème, le bilan n'est pas très glorieux. Les réponses reçues sont rarissimes. La plupart du temps, c'est le silence complet. Parfois, on reçoit un avis de non-remise « il n'y a pas de compte abuse à l'adresse indiquée ». Parfois une réponse standard inutile.

Est-ce qu'au moins les messages sont lus, même si abuse ne peut pas répondre à tous ceux qui lui écrivent ? Même pas. La plupart du temps, les messages atterissent directement dans /dev/null, ou bien, à la rigueur, dans la boîte d'un stagiaire embauché pour faire le support utilisateur, qui n'y connait rien et n'est pas assez payé pour qu'on puisse lui demander de travailler sérieusement.

Même si certains gros FAI s'obstinent à nier et affirment, contre toute évidence, que les messages sont lus soigneusement, la triste réalité est qu'écrire à abuse ou bien jouer à World of Warcraft donneront le même résultat (et, dans le second cas, au moins, on voit les monstres qu'on combat).

Est-ce de la paresse ou de la méchanceté de la part des FAI ? En partie oui, bien sûr, c'est vrai qu'ils se moquent totalement de ce que leurs propres utilisateurs peuvent raconter. Alors, quand il s'agit d'inconnus... Mais il faut aussi remarquer que le problème n'est pas simple. D'abord, sur l'Internet, il y a tout le temps des problèmes. Si on héberge un parc de dix mille machines Unix dédiées et louées à des clients, il y en a forcément toujours un bon nombre qui se lancent dans des attaques, soit parce que le locataire est un méchant, soit parce qu'il a laissé un script PHP vulnérable sur sa machine. Si on connecte des dizaines de milliers de foyers où se trouvent des machines MS-Windows, c'est encore pire, un bon nombre a été transformé en zombies et les attaques qu'elles lancent vaudront certainement à abuse pas mal de courrier.

Mais il y a un autre problème : la très grande majorité des rapports envoyés à abuse sont inutilisables. Aucun détail, aucune précision, l'heure de l'attaque n'est pas indiquée (ou alors en heure locale, sans indication du fuseau horaire), les messages sont résumés et mal traduits au lieu d'être cités littéralement, etc. Le message typique reçu par abuse (rappelez-vous qu'un gros hébergeur peut avoir des dizaines de milliers de machines, voire davantage pour les très gros) est simplement « Mon firewall [sic] me dit que votre machine m'attaque, arrêtez tout de suite » (et encore, je n'ai pas respecté l'orthographe). Il est même fréquent que le message soit 100 % erroné et qu'il n'y aie pas d'attaque du tout (comme le voit fréquemment l'IANA).

Analyser de tels messages sérieusement nécessiterait du temps et une main d'œuvre qualifiée, alors qu'en général on met au « support de premier niveau » les gens les moins payés de l'entreprise. Il faudrait demander des précisions, faire preuve de patience, suivre le dossier, tout ce que fait un avocat d'affaires payé très cher de l'heure, mais pas ce que peut faire le marocain ou l'indien qui travaille dans un call center. Pour des simples raisons économiques, les messages à abuse sont donc traités vite et mal.

abuse est d'autant moins enclin à lire ses messages qu'un certain nombre d'utilisateurs spamment à tout vent et écrivent, lors de n'importe quel problème, à toutes les adresses de courrier qu'ils peuvent trouver en interrogeant whois.

Et les messages de qualité ? En général, vu l'afflux de messages inutilisables, les rares messages corrects, précis et complets sont traités comme les autres, perdus au milieu du flot.

The great social site Stack Overflow just announced the publication of its entire database under a Creative Commons free licence. I believe it is the first time such an important social networking site publishes its data, so it is a great day for data miners. In this small article, I will explain how I entered these data into a PostgreSQL database for easier mining. (The work was done on a Debian machine but it should work on any Unix.)

The original file is huge (200 megabytes today, and growing). To avoid killing the Stack Overflow servers, it is distributed in a peer-to-peer fashion with BitTorrent. I just downloaded the torrent file http://blog.stackoverflow.com/wp-content/uploads/so-export-2009-06.7z.torrent to my download directory and BitTorrent does the rest. I then extract the XML files with p7zip. Each XML file store a class of Stack Overflow objects:

• Users, today 88,558 (but many of them registered once but never came back afterwards),
• Posts, today 182,742 questions and 698,923 answers,
• Comments, today 705,085,
• Votes,
• Badges.

I then created one SQL table for each class. The complete DDL instructions are in file so-create.sql. I can then create the database and its schema:

% createdb --encoding=UTF-8 so
% psql -f so-create.sql so

I am normally a fan of integrity constraints in databases. But, in the case of Stack Overflow, there are many obvious integrity constraints that I did not include because they are violated at least one, especially in old data (presumably during beta testing of the site). For instance, 18,239 users (20 %) has no name (see for instance http://stackoverflow.com/users/57428, the one with the highest reputation) and therefore I cannot write name TEXT NOT NULL.

Same problem with the accepted answer, some posts reference an answer which is not available (for instance post #202271 has an accepted answer in the XML file, #202526, which does not exist).

Once the database is set up, we just have to parse the XML files and to load them in the database. I choose the Python programming language and the ElementTree XML library. I produce SQL files which uses the COPY instruction.

The Python program is available as so-so2postgresql.py. To execute it, you just indicate the directory where the Stack Overflow XML files have been extracted. Then, you run PostgreSQL with the name of the produced SQL COPY file, and with the name of the database:

% python so-so2postgresql.py /where/the/files/are > so.sql
% psql -f so.sql so

This so-so2postgresql.py program requires a lot of memory, because it keeps the entire XML tree in memory (that is a weakness of the XML library used). Do not attempt to run it on a machine with less than eight gigabytes of physical RAM, swapping will make it awfully slow. You may also have to increase the available memory with ulimit.

Once the program is over, you can start studying the data:

so=>  SELECT avg(reputation)::INTEGER FROM Users;
 avg 
-----
 183
(1 row)

so=> SELECT avg(reputation)::INTEGER FROM Users WHERE reputation > 1;
 avg 
-----
 348
(1 row)

The first analysis produced with this database was an exploration of the "fastest gun in West" syndrome (available at stack-overflow-short-tail.html, in French).

Many people already posted on the subject of the Stack Overflow database. For instance:

• Data Mining the StackOverflow Database (SQL server, only as a video in this article but other articles are more text-friendly),
• What interesting stats can I obtain from the Stack Overflow data-dump?, with many interesting statistics,
• Stack Overflow: Up and Down Voting Pattern Analysis,
• Statistics about tags, users and questions at StackOverflow, ServerFault and SuperUser,
• How to Import the StackOverflow XML into SQL Server, which focuses on the import into a database, like this article,
• StackOverflow question statistics (nice graphs),

Le site social Stack Overflow ayant désormais rendu publique sa base de données, il est possible de l'analyser et d'étudier les comportements des participants à ce site. Par exemple, les votes et les réponses se poursuivent-ils pendant des mois ou bien sont-ils concentrés dans les heures qui suivent la publication d'une question ?

Regardons d'abord l'évolution des votes dans le temps. Combien de temps s'écoule t-il entre un message (question ou réponse) et les votes sur ce message ?

so=> SELECT DISTINCT (votes.creation - posts.creation::date) AS interval, 
so->                 to_char(count(votes.id)*100.0/
so(>                         (SELECT count(votes.id) FROM Posts, Votes 
so(>                                 WHERE Votes.post = Posts.id), '99.99') AS 
so->                  percent
so->    FROM Votes, Posts 
so->    WHERE Votes.post = Posts.id
so->    GROUP BY interval ORDER BY interval;         
 interval | percent 
----------+---------
        0 |  54.75
        1 |  10.33
        2 |   2.62
        3 |   1.74
        4 |   1.26
        5 |   1.01
        6 |    .87
        7 |    .70
        8 |    .57
        9 |    .49
       10 |    .44
       11 |    .42
       12 |    .38
       13 |    .39
       14 |    .39
       15 |    .33
       16 |    .30
...

La majorité absolue des votes ont lieu le jour de publication de l'article. Dès le cinquième jour, on passe en dessous d'un pour cent des votes pour la journée. Bref, il semble que le syndrôme connu à Stack Overflow sous le nom de fastest gun in West joue à plein. N'importe quel contributeur peut le voir : si on arrête d'écrire, la réputation ne bouge plus guère, les votes tardifs étant rares.

Cela se voit très bien sur le graphique, produit par gnuplot avec ces instructions :

set xrange [:150]
set format y "%.0f"
plot "votes-per-day.dat" using 1:2 with lines title ""

et en extrayant les données avec psql --file votes-per-day.sql --field-separator ' ' --tuples-only --no-align so > votes-per-day.dat, on obtient :

Mais la traîne est tellement longue qu'elle contribue quand même. Ainsi, 27 % des votes ont lieu plus d'une semaine après l'article et 19 % des votes plus d'un mois après :

so=> SELECT count(votes.id)*100/(SELECT count(votes.id) FROM Posts, Votes 
                                WHERE Votes.post = Posts.id) AS percent
       FROM votes, posts WHERE 
                   votes.post = posts.id AND 
                   votes.creation >= (posts.creation + interval '7 day')::date;
 percent 
---------
      27
(1 row)

so=> SELECT count(votes.id)*100/(SELECT count(votes.id) FROM Posts, Votes 
                                WHERE Votes.post = Posts.id) AS percent
       FROM votes, posts WHERE 
                   votes.post = posts.id AND 
                   votes.creation >= (posts.creation + interval '30 day')::date;
 percent 
---------
      19
(1 row)

Graphiquement, en mettant l'axe des Y en logarithmique, on voit mieux la longue traîne. Les instructions gnuplot sont :

set xrange [:150]
set logscale y
set format y "%.0f"
plot "votes-per-day.dat" using 1:2 with lines title ""

et le résultat est :

Et l'intervalle entre la question et une réponse acceptée (dans Stack Overflow, l'auteur d'une question peut marquer une question et une seule comme acceptée) ?

so=> SELECT DISTINCT(answers.creation::date - questions.creation::date) AS interval, 
so->        to_char((count(questions.id)*100.0/(SELECT count(answers.id) 
so(>                                  FROM Posts questions, Posts answers
so(>                                  WHERE answers.id = questions.accepted_answer AND 
so(>                                        questions.type = 1 AND
so(>                                        answers.type = 2)), '999.9') AS percent
so->     FROM Posts questions, Posts answers
so->     WHERE answers.id = questions.accepted_answer AND questions.type = 1 AND
so->           answers.type = 2
so->     GROUP BY interval ORDER by interval;
 interval | percent 
----------+---------
        0 |   83.9
        1 |    7.3
        2 |    1.5
        3 |    1.0
        4 |     .7
        5 |     .5
        6 |     .4
        7 |     .4
        8 |     .3
...

La courbe est encore plus brutale. On pourrait résumer en disant que, si on ne répond pas le premier jour, on n'a que peu de chances d'être accepté... Mais il faut garder espoir. 4 % des réponses acceptées ont été écrites plus d'une semaine après l'article et 1 % après un mois.

so=> SELECT count(answers.id)*100/(SELECT count(answers.id) 
                                FROM Posts questions, Posts answers
                                WHERE  answers.id = questions.accepted_answer AND 
                                       questions.type = 1 AND
                                       answers.type = 2) AS percent
       FROM Posts questions, Posts answers
       WHERE answers.id = questions.accepted_answer AND 
             questions.type = 1 AND answers.type = 2 AND
             answers.creation > (questions.creation + interval '7 day')::date;
 percent 
---------
       4
(1 row)

so=> SELECT count(answers.id)*100/(SELECT count(answers.id) 
                                FROM Posts questions, Posts answers
                                WHERE  answers.id = questions.accepted_answer AND 
                                       questions.type = 1 AND
                                       answers.type = 2) AS percent
       FROM Posts questions, Posts answers
       WHERE answers.id = questions.accepted_answer AND 
             questions.type = 1 AND answers.type = 2 AND
             answers.creation > (questions.creation + interval '30 day')::date;
 percent 
---------
       1
(1 row)

On pourrait se dire que oui. Après tout, ceux qui tapent le plus sur l'Internet, Sarkozy, Allègre, Val ou Lefebvre, sont tous des gens de droite (même si certains sont parfois, en raison d'une très ancienne adhésion à un parti de gauche, étiquetés différemment par les médias). Mais ces discours anti-Internet, méfiants, voire franchement hostile, face à la liberté que procure ce nouvel outil, se retrouvent bien au-delà de la droite. Et ceux qui ont construit Internet, étaient-ils de gauche ?

L'ancêtre d'Internet, l'Arpanet, a été développé, pendant des années, à 100 % sur fonds publics, les capitalistes n'aimant pas prendre des risques. Mais ces fonds n'étaient pas distribués pour la culture ou la recherche puisqu'ils venaient en totalité de l'armée états-unienne, via son agence de recherche, nommée à l'époque ARPA. Revoyons le contexte. C'était en pleine guerre du Viêt Nam. Sur les campus états-uniens en ébullition, il n'était pas toujours facile de trouver des chercheurs qui acceptaient de travailler pour l'armée. Aujourd'hui, la plupart des chercheurs ne prennent plus en compte des considérations politiques ou morales avant d'accepter un budget : l'argent n'a pas d'odeur. Mais, à l'époque, la prise de conscience était bien plus forte et tout un courant existait chez les scientifiques pour dire qu'on ne pouvait pas faire n'importe quelle recherche en éludant ses responsabilités. (Pour une bonne édition en français des textes de ce courant, voir le livre de Jean-Marc Lévy-Leblond et Alain Jaubert, « (Auto)critique de la science », publié au Seuil en 1973.)

Ceux qui ont créé Arpanet puis l'Internet étaient donc les moins hostiles à l'armée et à sa guerre en Asie du Sud-Est. Ce fut au point que d'autres réseaux, concurrents de l'Arpanet, refusaient tout simplement d'utiliser des techniques marquées comme « militaires ». Ce fut le cas de Fidonet, par exemple, très utilisé par les ONG, notamment en Afrique parmi les ONG d'aide au développement et qui prenait soin de développer ses propres protocoles.

Comme rien n'est jamais aussi simple, l'argument que l'Internet était un protocole de l'armée états-unienne avait aussi été utilisé de manière protectionniste (par exemple en France), pour travailler sur des protocoles spécifiques aux entreprises françaises, en rejetant le « protocole du DoD » comme TCP/IP était qualifié dans les livres de cours comme le Pujolle.

En fait, la complexité de la question vient d'un problème plus fondamental, la neutralité des objets techniques. Est-ce que le téléphone est de gauche ou de droite ? Est-ce que IPv6 est plus ou moins à gauche qu'IPv4 ? Ce genre de questions parait absurde et cela permet au chercheur de travailler sur n'importe quel sujet en disant qu'il est neutre, que ce sont les applications qui sont bonnes ou mauvaises mais certainement pas le sujet de recherche pour lequel il touche des subventions.

Or, s'il est vrai que le téléphone ou l'Internet peuvent être utilisés par tous, il est également vrai que de tels réseaux complexes et très coûteux à déployer ne naissent pas dans un garage : leur mise au point et, encore plus, leur sortie dans le monde réel nécessite que la société mette d'énormes moyens en jeu et elle ne le fera que s'il y a un intérêt (c'est la différence entre l'invention, phénomène individuel qui peut se faire dans un garage, et l'innovation qui est un phénomène social.). Un objet technique ne réussit pas sur ses propres mérites, mais parce que des gens riches et puissants y voient un intérêt.

Et, en même temps, il a toujours une ambiguité. Les objets techniques peuvent partiellement échapper à leur créateur, ils peuvent avoir des résultats inattendus et un réseau conçu pour l'armée de l'Empire peut servir à diffuser plein d'informations d'une manière qui était difficile et chère avant, peut servir à bâtir une encyclopédie libre et peut servir à bien d'autres choses qui auraient sans doute surpris les généraux de 1969...

darcs est un excellent VCS décentralisé. Il est par exemple utilisé pour gérer les fichiers de ce blog. Permet-il de travailler sur plusieurs machines sans qu'aucun des dépôts ne soit connecté en permanence ? Oui, en échangeant des patches par courrier, patches qu'on applique ensuite localement.

D'abord, il faut demander à darcs de produire un patch. On peut utiliser pour cela la fonction shell darcsdiff, que présentait mon article sur les fonctions shell. darscdiff prend comme argument l'ID du dernier message du dépôt qui est en retard de synchronisation. (Ou, dit autrement, l'ID immédiatement précédent celui à partir duquel on veut envoyer les patches.) Si on prend un ID trop lointain dans le passé, ce n'est pas très grave (le message sera simplement trop gros), darcs n'appliquera que les patches nouveaux.

Donc, par exemple :

% darcsdiff 'Manque de scalabilite du Wifi' 
What is the target email address? stephane+darcs@bortzmeyer.org
Successfully sent patch bundle to: stephane+darcs@bortzmeyer.org.

(Attention, par défaut, darcsdiff envoie tout le dépôt s'il ne trouve pas l'ID donc lisez bien les avertissements avant de taper sur la touche Entrée.)

Et le destinataire reçoit un message du genre :

Subject: darcs patch: Article NetBSD format fini (and 26 more)
From: bortzmeyer@batilda.nic.fr
To: stephane+darcs@bortzmeyer.org
Date: Tue,  9 Jun 2009 09:04:00 +0200 (CEST)
X-Mail-Originator: Darcs Version Control System
X-Darcs-Version: 2.0.2 (release)
DarcsURL: CONTEXT

[-- Attachment #1 --]
[-- Type: text/plain, Encoding: quoted-printable, Size: 2.4K --]

Wed Jun  3 11:37:53 CEST 2009  stephane@ludwigVII.sources.org
  * Article NetBSD format fini

Wed Jun  3 13:25:43 CEST 2009  stephane@ludwigVII.sources.org
  * TODO: strlen et l'optimisation

...

Il doit alors sauvegarder le message (par défaut, l'attachement porte comme nom l'ID du premier patch qui était manquant) puis demander à darcs d'appliquer ces patches (il peut y en avoir plusieurs, comme dans l'exemple ci-dessus) :

% darcs apply article-netbsd-format-fini.dpatch 

Si on le fait deux fois, par erreur :

% darcs apply article-netbsd-format-fini.dpatch 
All these patches have already been applied.  Nothing to do.

On trouve de nombreux détails, notamment l'intégration avec mutt dans la documentation de darcs.

La question du meilleur format pour transmettre des données structurées d'une machine du réseau à une autre a toujours suscité bien des discussions. Ce n'est peut-être pas aussi passionnel que le choix du langage de programmation mais cela fait toujours largement débat.

Le débat n'est pas toujours très informé. Sur les forums, on voit souvent, lorsque quelqu'un s'enquiert du « meilleur » format pour transmettre des données structurées, des réponses aussi idiotes que « XML est nul [sans autre explication], utilises JSON » ou bien « Il faut utiliser les Protocol Buffers [là aussi, sans explication, à part que c'est le protocole de Google et que Google a forcément raison] ». (Données « structurées » signifie qu'elles ne sont pas simplement des listes de tuples, donc un format comme CSV (RFC 4180) ne compte pas.)

Une discussion bien meilleure s'est déroulée récemment sur une liste de diffusion de l'IETF, apps-discuss, la liste du secteur Applications de l'IETF. On trouve son point de départ dans un article de Patrik Fältström. L'IETF n'a pas de format standard pour ses applications, SNMP (RFC 1157) utilise ASN.1, EPP (RFC 4930) et Netconf (RFC 4741) XML, etc.

Pour ceux qui n'ont pas participé aux N discussions précédentes sur le même sujet, voici une liste (que je crois exhaustive) des candidats au rôle de format idéal, ainsi que quelques notes personnelles, et qui assument leur subjectivité, sur chacun. Tous disposent d'une documentation, parfois d'une vraie norme ouverte, et tous ont des mises en œuvre en logiciel libre :

• XML, normalisé (par le W3C), très répandu, beaucoup de mises en œuvres en logiciel libre dans tous les langages, beaucoup d'experts disponibles, gère proprement Unicode depuis le début.
• JSON, le seul, semble t-il, qui aie fait l'objet d'un RFC, le RFC 4627. Assez répandu dans le monde Web 2.0.
• YAML, plus répandu pour des fichiers (par exemple des fichiers de configuration) locaux, je ne crois pas l'avoir souvent rencontré sur le réseau.
• Les S-expressions, popularisées par le langage Lisp et donc appréciées par les fans de ce langage.
• ASN.1, d'origine ISO et donc, à juste titre, mal aimé dans le monde Internet. ASN.1 permet de décrire les données, l'encodage exact sur le câble étant laissé à des formats compagnons comme BER ou DER.
• Les netstrings, conçu par l'inénarrable djb et qui plait donc à ses fans.
• Les Protocol Buffers, un des plus récents, mais qui a derrière lui tout le poids du géant Google.
• On peut citer aussi les formats spécifiques à un langage de programmation donné, qui permettent de sérialiser des objets du langage pour les transporter sur le réseau comme pickle pour Python ou java.io.Serializable pour Java.
• Et, enfin, les informaticiens étant ce qu'ils sont, il y a toute la cohorte des formats conçus et mis en œuvre localement par un programmeur ou bien une petite équipe...

Il existe une classe de protocoles réseaux nommés protocoles de bavardage (gossip protocol) qui résoud élegamment un problème classique dans les réseaux : informer tout le monde sans utiliser de mass media centralisé. Ils utilisent pour cela un principe simple : tout pair du réseau transmet l'information aux pairs qu'il connait (un sous-ensemble du total) et ceux-ci, à leur tour, transmettent aux pairs qu'ils connaissent, et ainsi de suite (on appelle parfois cette procédure l'indondation - flooding). Au bout d'un moment, la totalité du réseau est au courant, sans qu'on aie eu besoin d'un système centralisé.

L'Internet utilise un certain nombre de protocoles de bavardage. C'est ainsi que le routage global, avec le protocole BGP (RFC 4271), dépend d'un protocole de bavardage. Aucun routeur BGP ne connait tous les autres routeurs BGP de la DFZ, l'Internet n'a pas de centre, pas de chaîne de télévision unique qui informerait tous les routeurs de l'arrivée d'un nouveau réseau. Pourtant, de fil en aiguille, l'information sur un nouveau préfixe d'adresses IP touche tout l'Internet en quelques minutes.

Avant BGP, les protocoles de bavardage ont été surtout popularisés par les News (RFC 1036, section 5), où un article était diffusé à chaque pair (par opposition au Web qui est d'avantage centralisé : si le serveur de www.playboy.fr tombe en panne ou bien est victime d'une attaque, l'information (?) sur le site n'est plus accessible du tout). Au contraire, avec BGP ou les News, il faut détruire beaucoup de machines pour réellement supprimer certaines informations ! (Avec les protocoles de bavardage, l'information cesse d'être accessible à tous dès que le réseau cesse d'être connecté, lorsqu'il est partitionné en deux - ou plus - morceaux.)

Donc, les principales forces des protocoles de bavardage sont la résistance aux pannes et le fait qu'aucun nœud ne joue de rôle essentiel, y compris pour l'injection initiale (alors que le terme d'« inondation » n'implique pas d'égalité, l'inondation peut aussi servir lorsqu'un des nœuds est le seul à pouvoir initier une information).

Pour fonctionner correctement, les protocoles de bavardage ont besoin que chaque pair maintienne un historique : quels messages a t-il reçus, a qui les a t-il envoyés, etc. Autrement, on perdrait du temps et des ressources à retransmettre un message déjà connu et on risquerait même de faire des boucles sans fin. Dans les News, chaque serveur retient les messages reçus (identifiés par leur Message-ID:, et « oubliés » au bout d'une durée réglable, pour éviter de remplir le disque dur). BGP a en outre d'autres mesures pour limiter l'inondation comme le fait de ne transmettre comme toutes que celles qu'il utilise lui-même, éliminant ainsi d'une propagation ultérieure les « mauvaises » routes.

Une propriété intéressante des architectures fondées sur le bavardage est qu'il n'est pas nécessaire que la transmission des messages entre les pairs utilise toujours le même protocole. Par exemple, dans les News, le protocole NNTP (RFC 3977) est le plus courant mais pas le seul (pendant longtemps, UUCP était plus utilisé).

Pour illustrer le fonctionnement d'un protocole de bavardage, voici une petite implémentation en Python, avec la bibliothèque standard socket : gossiper.py. Les fils sont utilisés pour éviter d'être bloqué, chaque pair pouvant évidemment être en panne, injoignable, etc. Dans l'implémentation actuelle, on réessaie un nombre limité de fois si un pair n'est pas joignable. Il ne faut évidemment pas comparer cette petite implémentation aux vraies qui tournent sur le vrai Internet, notamment parce qu'elle manque sérieusement de robustesse, par exemple lors de la lecture des messages des autres pairs.

Dans cet exemple simple, le protocole entre deux pairs est fixé (comme avec BGP, mais contrairement aux News). Chaque pair a un numéro unique, l'ID, fixé à la main au démarrage (si on n'a pas de serveur central pour attribuer des numéros uniques, le mieux est de tirer ces ID au hasard dans un espace très grand, limitant ainsi les risques de collision, ou bien de prendre le résumé cryptographique d'une phrase, unique pour chaque pair.) Le « serveur » (le pair qui répond aux demandes de connexion) envoie son ID (suivi d'une virgule). Le « client » (le pair qui lance la connexion) envoie son ID, suivi d'une virgule et suivi du message (sur une seule ligne). Si l'ID est l'identificateur du pair, pour s'y connecter effectivement sur l'Internet, il faut un localisateur, un tuple (adresse IP, port). Dans cette simple implémentation, il n'y a qu'un de ces tuples par pair mais ce n'est pas imposé par le protocole (de toute façon, les pairs sont identifiés par leur ID, pas par leur adresse IP, donc une connexion du pair N peut venir d'une autre adresse IP que celle connue pour N, si la machine cliente a plusieurs adresses).

Au démarrage, on indique donc au programme gossiper.py le port sur lequel il doit écouter (30480 par défaut) et les identificateurs et localisateurs de ses pairs. À noter que la relation entre pair n'est pas symétrique : 1 peut savoir comment joindre 2 sans que le contraire soit vrai. Le nombre de pairs est quelconque mais il faut juste que l'ensemble des pairs soit connecté sinon certains messages n'arriveront pas partout.

Les pairs se souviennent des messagers qu'ils ont vu (dans l'historique global) et de ceux qu'ils ont envoyés à chaque pair (dans un historique spécifique au pair).

Le mode d'emploi est simple. Supposons qu'on veuille lancer le pair d'ID 42, écoutant sur le port 22000, et pouvant parler aux pairs d'ID 261 (2001:DB8:1::bad:dcaf, port par défaut) et d'ID 4231 (2001:DB8:2::dead:beef, port 443), on tapera :

% python gossiper.py -i 42 -p 22000 \
    261,\[2001:DB8:1::bad:dcaf\] 4231,\[2001:DB8:2::dead:beef\]:443

La syntaxe (adresse IP, port) utilisée est celle du RFC 3986, section 3.2.2. Les barres obliques inverses devant les crochets sont imposés par certains shells Unix.

Le programme affichera alors les communications avec ses pairs. Pour amorcer la pompe et injecter des messages facilement, on peut utiliser netcat (ici, l'injecteur original a indiqué un ID de 0) :

% echo 0,"Les sanglots longs des violons de l'automne" | nc 127.0.0.1 22000

Avec des messages inspirés de Radio Londres, on obtiendra des dialogues comme suit (un délai artificiel a été ajouté pour mieux simuler la durée de propagation dans un réseau). Ici, le pair d'ID 5 :

2009-06-05 17:30:13 - ::ffff:127.0.0.1 - 30 bytes (NEW message received from peer 0: "Jean a de longues moustaches...")
2009-06-05 17:30:29 -  - 0 bytes (Sender task Thread-1 received "Jean a de longues moustaches" from 0, connecting to 2 (192.134.7.253:30480))

Et ici le 2 :

2009-06-05 17:31:30 - ::ffff:192.134.4.69 - 30 bytes (NEW message received from peer 5: "Jean a de longues moustaches...")
2009-06-05 17:32:01 -  - 0 bytes (Sender task Thread-3 received "Jean a de longues moustaches" from 5, connecting to 6 (192.134.7.248:4242))

Et ici, un pair, le 3, reçoit un message deux fois, de 6, puis de 2. il ignore le second. Cette précaution est ce qui permet aux protocoles de bavardage de ne pas boucler éternellement.

2009-06-06 22:56:35 2a01:e35:8bd9:8bb0:21c:23ff:fe00:6b7f - 30 bytes - NEW message received from peer 6: "Jean a de longues moustaches..."
2009-06-06 22:56:49 2a01:e35:8bd9:8bb0:21c:23ff:fe00:6b7f - 30 bytes - Ignoring known message from peer 2: "Jean a de longues moustaches..."
...
2009-06-06 22:58:08 2a01:e35:8bd9:8bb0:21c:23ff:fe00:6b7f - 35 bytes - NEW message received from peer 6: "Les lapins s'ennuient le dimanche..."
2009-06-06 22:58:28 2a01:e35:8bd9:8bb0:21c:23ff:fe00:6b7f - 35 bytes - Ignoring known message from peer 2: "Les lapins s'ennuient le dimanche..."

Pour approfondir le concept, on peut lire le bon article du Wikipédia anglophone.