Myriad Blog 1.3.0 Friday, Apr 25th, 2014 at 10:57am 

Technical Monday, Apr 14th, 2014 at 05:06pm
Heartbleed - Au coeur du problème

 
Les plus technophiles d'entre vous auront entendu parler, ces jours derniers, de Heartbleed, la faille de sécurité affectant les accès cryptés à certains sites Web.
L'impact et l'exemplarité de cet épisode méritent qu'on y revienne dessus.
Tout d'abord, de quoi s'agit-il exactement ?
 
Heartbleed, coté fonctionnement
 
Pour résumer (et simplifier un peu), le problème touche OpenSSL, qui gère les échanges sécurisés entre par exemple un serveur Web (gmail, facebook, yahoo, etc) et le client (vous, votre voisin, un hacker, un pirate ou un agent de la NSA) qui y accède.
Lors de ces échanges, le client peut demander des données au serveur, et, en exploitant une erreur de programmation, s'arranger pour recevoir, en plus de ces données, le contenu d'une zone mémoire utilisée préalablement par le serveur  lors des échanges avec quelqu'un d'autre et malencontreusement non effacée.
 
Ainsi, n'importe qui peut s'arranger pour obtenir des données qui ne lui étaient pas destinées. Ces données peuvent être totalement inutiles, mais aussi des données sensibles (noms d'utilisateur, mot de passe, échanges privés...). En récupérant beaucoup, beaucoup de données par ce biais et en les triant, une personne mal intentionnée peut récupérer des noms d'utilisateurs et des mots de passe, et donc pirater des comptes ou accéder à des données privées. Imaginez ce que ça peut donner s'il s'agit du serveur de votre banque en ligne...
 
Heartbleed, coté programmation
 
On peut légitimement se poser la question : pourquoi les données sensibles se sont-elles retrouvées en clair dans une zone mémoire non utilisée ? N'aurait-il pas été plus sûr, si cette zone mémoire n'était pas censée être utilisée telle quelle, de l'effacer ?
OpenSSL est, sauf erreur, écrit en C. Un langage rapide, mais pas réputé pour la sécurité intrinsèque du code. En gros, on peut faire beaucoup de choses, qui vont très vite, mais ça crashe facilement, ça peut déborder, ça peut lire et écrire en dehors des endroits prévus, etc.
 
On peut alors choisir de privilégier la sécurité ou la performance. La sécurité, c'est, lorsqu'une zone mémoire va être utilisée ou est libérée, de l'effacer complètement. La sécurité, c'est aussi d'utiliser un gestionnaire de mémoire qui va générer une "exception" (un arrêt du programme ou l'inscription dans un journal d'alerte) lorsqu'on accède un peu en dehors des zones prévues.
La performance, c'est tout le contraire. Dans OpenSSL, on a visiblement choisi la performance.
 
Heartbleed, coté autorités
 
On ne sait pas vraiment depuis combien de temps la faille heartbleed est connue de certains. Il se murmure que la NSA l'exploite depuis plusieurs mois, voire plusieurs années, avec l'accord explicite des plus hautes autorités américaines. Et il est strictement impossible de savoir quelles données ont été lues par ce biais, d'en remonter la trace et ainsi de savoir qui a volé quoi.
 
Le saint-Grââl de l'espionnage informatique.  
 
Heartbleed, coté philosophique
 
Cela nous amène à nous interroger. Comment une faille de cette importance, et présentant ces conséquences, a-t-elle pu perdurer dans l'un des programmes Open Source les plus utilisés au monde ? On nous a présenté l'Open Source comme un schéma dans lequel la sécurité était maximale, car tous les programmeurs avaient la possibilité d'examiner le code, trouver les erreurs, les signaler et les corriger. Ainsi, aucun défaut majeur ne pouvait perdurer bien longtemps avant d'être repéré et traité.
On s'aperçoit aujourd'hui que ce n'est pas vrai, en tout cas pas obligatoirement vrai.
 
Heartbleed, coté "Open"
 
Le beau scénario de l'Open Source ne peut fonctionner que si trois points sont respectés :
 
1- Il y a suffisamment de programmeurs compétents pour vérifier le code.  
 
2- Le code est suffisamment clair pour permettre à tous de s'y retrouver facilement
 
3- Il y a plus de programmeurs "honnètes" pour chercher les failles que de pirates ou d'agents du gouvernement.
 
Pour 1-, le nombre de programmeurs chevronnés est probablement grandement surestimé. Et dans ceux-ci, beaucoup ont autre chose à faire que d'examiner du code qui fonctionne (ou qui semble fonctionner) correctement.
 
Pour 2-, sans avoir étudié le code source d'OpenSSL, beaucoup de projets Open Source semblent avoir été écrit avec les pieds par Hannibal Lecter. La syntaxe semble avoir été compliquée à dessein, les noms de fonctions et de variables semblent issus d'un manuel de codage russe, et les commentaires se résument souvent à une belle en-tête de fichier en ASCII Art.
 
Pour 3-, Heartbleed semble avoir prouvé que les pirates et les cyberespions possèdent maintenant un avantage en terme de moyens et de main-d'oeuvre par rapport à la poignée de bénévoles décidés à passer leur week-ends à relire l'intégrale du code d'OpenSSL, on se demande pourquoi.
 
Et maintenant, tout le monde est en train de se poser la même question : "celle-ci a été repérée, mais y en a-t-il encore beaucoup, des failles comme ça ?"...
by Olivier Guillion
 2 comments.

Technical Tuesday, Apr 22nd, 2014 at 05:08pm
Figures anticrénelées (1/3) -  Les polygones

 
Dans le cadre de la mise à jour de la bibliothèque de compatibilité "ACAM", nous avons dû nous pencher sur le tracé de courbes dites "de Bezier". En effet, il s'agit du seul type d'objet graphique qui nous oblige encore à utiliser les bibliothèques du système, cairo sur Linux ou GDI+ sur Windows.
 
L'idée était donc de tracer par nous-même des courbes de Bezier, et anticrénelées qui plus est, c'est-à-dire utilisant des niveaux de gris sur les arètes de la courbe pour les faire apparaître lisses.
 
Voici toutes les étapes de notre cheminement, jusqu'à la solution définitive.
 
I- Tracé simple de polygone
 
La première étape consiste à pouvoir dessiner des polygones remplis. Un polygone est une figure fermée, constituée d'un ensemble de points reliés entre eux deux par deux, le dernier point étant relié au premier.
 
Pour tracer, nous avons utilisé le système de "scan-lines" :
 
 - On considère une à une les lignes horizontales (scan-lines) de l'aire contenant la figure.
 
 - Pour chacune de ces lignes horizontales, on calcule le point d'intersection entre cette ligne et chacun des segments de la figure. Il y a toujours un nombre pair d'intersections (vous pouvez le vérifier avec un papier et un crayon).  
 
 - Il suffit alors de classer ces intersections par X croissant, les considérer deux à deux et remplir en noir entre chaque paire.  
 
On obtient alors ceci, pour un polygone quelconque de 9 points :
 

 
Le tracé est mathématiquement exact, mais si on observe en détail la figure obtenue, on voit que les bords sont crénelés :
 

 
II- Anti-crénelage horizontal
 
Plutôt que de dessiner des points en noir ou blanc, on va traiter spécialement le premier et le dernier point de chaque ligne horizontale tracée, et choisir un niveau de gris représentant la proportion de noir dans le pixel.  
Le balayage considérant des scan-lines horizontales, ce procédé ne fonctionne que sur les segments de polygone plutôt verticaux. Pour les autres, il faudrait que plusieurs points à la suite aient des gris différents. Nous verrons cela plus tard.
 
On obtient alors :
 

 
Sur le détail, on voit que les lignes verticales ont bien été traitées, mais que les lignes horizontales sont encore crénelées:
 

 
III- Anti-crénelage bidirectionnel
 
L'algorithme, jusqu'ici, est rapide, très rapide.
 
Plutôt que de s'embarrasser de calculs mathématiques complexes pour traiter les bords des segments plutôt horizontaux, ce qui ralentirait le tracé d'un facteur 3 ou 4, nous estimons qu'il est plus simple et probablement plus rapide de simplement doubler l'algorithme existant avec un balayage vertical, à même de traiter les segments restants.
 
Dans la littérature, de tels algorithme de "cross scanline" ont déjà été envisagés il y a 25 ans pour obtenir des anticrénelages de haute qualité.
 
On obtient maintenant ceci :
 

 
Le détail montre que tous les segments ont été correctement anticrénelés.
 

 
Maintenant, il va falloir s'assurer que des courbes aux formes douces peuvent être correctement approximées par des polygones.  

(à suivre...)

by Olivier Guillion
 Leave a comment.

Technical Wednesday, Apr 23rd, 2014 at 05:03pm
Figures anticrénelées (2/3) -  Les courbes

 
Hier, nous étions parvenus à dessiner des polygones anticrénelés. Mais le but reste de dessiner des courbes. Peut-on, en créant suffisamment de segments, approximer une courbe par un polygone ?
 
I- Le test du disque
 
Afin de vérifier cela, et mettre également notre algorithme à l'épreuve, nous créons un polygone qui suit le contour d'un cercle. Un segment est créé pour chaque 5° d'angle, ce qui au final aboutit à un polygone à 72 cotés.
 
Nous lançons notre programme, et obtenons :
 

 
Le disque est correctement tracé et anticrénelé. Les pans coupés dont il est constitué ne sont pas visibles et la figure donne l'apparence d'une courbe douce.  
 
II- La transparence
 
Afin de nous permettre de mieux visualiser nos résultats, plutôt que de tracer systématiquement nos figures en noir opaque, nous introduisons un niveau de transparence.
 
Notre dessin de test, avec un nouveau polygone de 6 points, et une transparence différence pour chaque élément, donne ceci :
 

 
III- Les courbes de Bezier
 
Dans les courbes de Bezier, chaque noeud de la figure est constitué d'un point par lequel passe la figure, et de deux points de contrôle, un de chaque coté du point, définissant l'angle de la courbe lors du passage au point.
 
Nos polygones précédents peuvent être considérés comme des courbes de Bézier en ne prenant qu'un point sur trois, et en considérant les deux autres comme les points de contrôle.
 
L'algorithme de De Casteljau nous permet de diviser chaque segment en deux, et de calculer le point de Bezier intermédiaire. Répété récursivement, il permet de lisser complètement la courbe.
 
Si on ne considère qu'un point sur trois dans nos deux polygones à angles vifs, on obtient 3 points (un triangle) pour le premier, et 2 points (une ligne ultrafine, invisible) pour le second.
 

 
L'algorithme de De Casteljau nous permet de calculer les points intermédiaires sur les courbes de Bezier définissant ces figures. Voici, avec une subdivision de chaque segment en 4 :
 

 
Puis avec une subdivision en 8 :
 

 
Puis avec une subdivision et en 16 :
 

 
On ne voit presque plus les "coins" des polygones. En améliorant l'algorithme de division de De Casteljau pour continuer à diviser tant que c'est visuellement nécessaire, on obtient nos premières courbes de Bezier lisses et anticrénelées :
 

 
Le plus difficile est maintenant derrière nous. Il nous faut maintenant être capable de tracer les contours au lieu des formes pleines, et inclure ces algoritmes dans notre bibliothèque de programmation.  

(à suivre)

by Olivier Guillion
 Leave a comment.

Technical Thursday, Apr 24th, 2014 at 05:14pm
Figures anticrénelées (3/3) -  Contours et performances

 
Nous sommes parvenus à tracer des formes polygonales pleines, et à convertir une figure formée d'un ensemble de courbes de Bezier en polygone pour pouvoir la tracer.
 
Il faut maintenant pouvoir tracer seulement le contour de la forme, sans la remplir.  
 
I- Contours fins
 
L'idée est de conserver le principe des "scan lines" utilisé dans le remplissage, et de l'adapter au tracé de contour. La couleur d'un point dépend alors de la distance minimale qui le sépare d'un segment ou d'une extrémité de segment constituant le polygone.
 
Calculer, pour chaque point de l'image, la distance à chacun des segments ou extrémités de segment serait trop lourd et trop lent pour être viable. Il faut donc éliminer rapidement tous les segments qui n'ont aucune chance d'être à proximité immédiate du point considéré, et  calculer uniquement les distances jusqu'aux segments proches.  
Plusieurs méthodes ont été implémentées, mais n'ont pas d'effet sur le résultat, seulement sur la rapidité.  
 
On obtient donc, même avant que la rapidité soit optimisée :
 

 
II- Contours épais
 
Il est assez facile de faire varier l'épaisseur du trait :
 
Lorsque la distance qui sépare le point considéré du plus proche segment est inférieure à la demi-épaisseur, on est dans le trait. Lorsqu'elle est supérieure, on est en dehors du trait.
 

 
III- La totale
 
On peut maintenant combiner les deux, traits et remplissage, et vérifier qu'ils s'ajustent correctement.  
 

 
La même chose avec des traits encore plus épais :
 

 
IV- Performance
 
Il est assez difficile d'évaluer la performance du tracé. Cela dépend en effet de la complexité de la figure, de sa taille, et des capacités de la machine.
 
Cependant, sur un PC qui n'est plus de la première jeunesse, on obtient, pour le test précédent, une moyenne d'environ 1 milliseconde (1/1000e de seconde) par tracé de figure, donc 1 ms pour le remplissage du 1er polygone, 1 pour son contour... soit 6 millisecondes pour l'ensemble du dessin.
 
Pour ce que nous voulons en faire (nos programmes ne sont pas des jeux avec des centaines de formes dessinées en temps réel), cela nous paraît suffisant.
 
V- Implémentation
 
Ces algorithmes ont été mis en place dans ACAM-Winter, et essayés dans Harmony Assistant, pour le tracé des accolades et des liaisons entre les notes.
 
Nous avons pu comparer le rendu entre notre méthode et les courbes de Bezier traitées par cairo, la librairie système de notre Linux Ubuntu :


 
Les deux rendus sont tellement proches que nous avons dû superposer les images dans un logiciel de dessin pour pouvoir constater une différence sur quelques pixels.
 
On peut donc considérer que notre algorithme remplace parfaitement la bibliothèque système, nous permettant de nous affranchir complètement de cette dernière. Il y aura probablement quelques erreurs de tracé dans certains cas limites, que nous devrons corriger, mais cela pourra être détecté dans la version alpha ou beta du programme.
by Olivier Guillion
 3 comments.


Full view
Reduced view
Most recent first
Oldest first
All
Didier Guillion
Olivier Guillion
Sylvie Ricard
All
Dev News
Technical
Mood
Memories
Myriad Life
To be seen
30 previous days
Apr 2006
May 2006
Jun 2006
Jul 2006
Aug 2006
Sep 2006
Oct 2006
Nov 2006
Dec 2006
Jan 2007
Feb 2007
Mar 2007
Apr 2007
May 2007
Jun 2007
Jul 2007
Aug 2007
Sep 2007
Oct 2007
Nov 2007
Dec 2007
Jan 2008
Feb 2008
Mar 2008
Apr 2008
May 2008
Jun 2008
Jul 2008
Aug 2008
Sep 2008
Oct 2008
Nov 2008
Dec 2008
Jan 2009
Feb 2009
Mar 2009
Apr 2009
May 2009
Jun 2009
Jul 2009
Aug 2009
Sep 2009
Oct 2009
Nov 2009
Dec 2009
Jan 2010
Feb 2010
Mar 2010
Apr 2010
May 2010
Jun 2010
Jul 2010
Aug 2010
Sep 2010
Oct 2010
Nov 2010
Dec 2010
Jan 2011
Feb 2011
Mar 2011
Apr 2011
May 2011
Jun 2011
Jul 2011
Aug 2011
Sep 2011
Oct 2011
Nov 2011
Dec 2011
Jan 2012
Feb 2012
Mar 2012
Apr 2012
May 2012
Jun 2012
Jul 2012
Aug 2012
Sep 2012
Oct 2012
Nov 2012
Dec 2012
Jan 2013
Feb 2013
Mar 2013
Apr 2013
May 2013
Jun 2013
Jul 2013
Aug 2013
Sep 2013
Oct 2013
Nov 2013
Dec 2013
Jan 2014
Feb 2014
Mar 2014
Apr 2014
Apr 24th, 2014 at 07:38pm 
Comment from Bubu42
Apr 24th, 2014 at 06:54pm 
Comment from
Apr 24th, 2014 at 06:54pm 
Comment from
Apr 24th, 2014 at 05:34pm 
Comment from Bubu42
Apr 24th, 2014 at 05:34pm 
Comment from Bubu42
Apr 24th, 2014 at 05:14pm 
Article from Olivier Guillion
Figures anticrénelées (3/3) -  Contours et performances
Apr 23rd, 2014 at 05:03pm 
Article from Olivier Guillion
Figures anticrénelées (2/3) -  Les courbes
Apr 22nd, 2014 at 05:08pm 
Article from Olivier Guillion
Figures anticrénelées (1/3) -  Les polygones
Apr 19th, 2014 at 08:20pm 
Comment from Grorom
bravo !
Apr 19th, 2014 at 08:04am 
Comment from Antoine Bautista
et un optimiste...

Top of page
Last update:  (c) Myriad 2013