Logo Blog perso d'Ozwald

Une vitesse de tous les diables

Par Oz le - Informatique
Python unicode performance tracing

Pour ce premier billet depuis la résurrection de mon blog et sa migration vers Pelican, je vais vous présenter une bizarrerie de Python2. Ce sera l'occasion de parler de persévérance, de temps perdu, et d'analyse de performance de code Python.

"Mickey Brown" driving an old dragster - CC BY SA by "Insomnia Cured Here" on Flickr

Le contexte

Il y a quelques années1 j'avais rédigé vite fait une petite librairie Python2 mono-fichier me permettant d'afficher proprement2 des tableaux dans un terminal. Bien que pleine de défauts, cette petite librairie est toujours utilisée par une poignée de projets au travail et j'avais donc toujours dans un coin de ma tête l'idée de la ré-écrire plus proprement. Le moteur principal de cette envie c'était de corriger LE défaut majeur de la librairie tel que je m'en souvenais : quand elle traite des tableaux dépassant le millier de lignes, elle devient vraiment lente (jusqu'à plusieurs dizaines de secondes juste pour l'affichage du tableau, en fonction de votre CPU).

Ce (long) weekend, je m'étais lancé dans l'écriture d'une librairie générant des graphiques en nuages de points dans un terminal3. Dans l'élan, je me suis enfin attelé à la ré-écriture de cet afficheur de tableau ! Quatre années s'étant écoulées depuis la précédente version, la nouvelle sera écrite en Python3 avec un algorithme totalement différent pour calculer la largeur optimale des colonnes4. À la fin de la journée, en ayant codé "une heure par-ci, dix minutes par-là", ma nouvelle version de la librairie était prête à être testée.

Je lance quelques tests et j'observe un premier effet inattendu (mais très agréable) : le choix de largeur des colonnes est beaucoup plus pertinent sur ma nouvelle version que sur l'ancienne ! Fort de cette agréable surprise, j'attaque confiant la vérification du gain de performance tant recherché. Pour comparer les performances de l'ancienne et de la nouvelle librairie, je jette une vingtaine de lignes de code dans un fichier que j'appelle "stresstest.py"

import random

data = []
for _ in range(2000):
    line = [random.randint(1,i+1)*'{0:.04f}'.format(random.random()) for i in range(25)]
    data.append(line)

import time
before = time.time()

import NEWLIB
a = NEWLIB.Array(data)
print(a)
after1 = time.time()

import OLDLIB
b = OLDLIB.ascii_array()
for row in data:
    b.add_row(row)
print(b)
after2 = time.time()

print("Nouvelle librairie : {0}s".format(after1-before))
print("Ancienne librairie : {0}s".format(after2-after1))

Je lance ce fichier et...

$ python3 stresstest.py
...
Traceback (most recent call last):
  File "(...)OLDLIB.py", line 55, in __init__
    content = unicode(content, errors='replace')
NameError: name 'unicode' is not defined

Prévisible. Une librairie écrite il y a 4 ans pour du Python2 avait quand même de fortes chances de ne pas fonctionner avec du Python3. Pas grave, pour le comparatif, je n'ai qu'à lancer stresstest.py avec un interpréteur Python2. Évidemment, cette fois c'est la nouvelle librairie qui refuse de fonctionner. Que faire ? Sachant que :

  • J'avais en tête de remplacer la vieille librairie par la nouvelle (or la vieille librairie est actuellement utilisée par quelques projets qui tournent encore en Python2) ;
  • Le code de la nouvelle librairie était encore frais dans ma tête (car tout juste écrit), contrairement au code de l'ancienne (pas relu depuis sa création initiale) ;
  • En 4 ans je pense que j'ai progressé et que le code de la nouvelle librairie est plus facilement maintenable/modifiable que le code de l'ancienne librairie.

J'ai donc décidé de modifier ma nouvelle librairie pour la rendre compatible Python2.

Le détail où se cache le diable

Le premier problème (quand je lance ma nouvelle librairie en Python2) c'est que mon code de test demande l'affichage d'un tableau dans lequel certaines cellules contiennent des caractères nationaux. Voici l'un d'eux avec un accent sur le "e" de Fév(rier) :

│     T1    │     T2     │Futur│
│Jan│Fév│Mar│Avr│Mai│Juin│     │
│0.0│0.2│0.8│1.3│0.7│0.7 │  ?  │
│0.7│0.9│1.3│1.4│0.9│1.2 │  ?  │

N'ayant rien précisé sur ces chaines de caractère, Python2 considère qu'il s'agit de son type par défaut, à savoir string. Le problème c'est que, en l'absence d'indication contraire, Python2 traite les données des string comme si elles étaient encodées en ascii or nos caractères nationaux n'existent pas en ascii. Ainsi, Python2 "plante"5 dès qu'il tente de traiter cet accent.

La première correction a donc été plutôt rapide : j'ai supprimé les accents de mon jeu de données de test. Ça me permet bien de contourner le plantage, mais la sortie affichée est immonde puisque tous les caractères unicodes que j'utilise (tout particulièrement les barres verticales délimitant les colonnes du tableau) sont affichées en tant que séquence d'échapement :

$ python3 -c 'print("\u2502")'

$ python2 -c 'print("\u2502")'
\u2502

Autant vous dire que mes tableaux ne ressemblent plus à rien. Le problème est similaire au précédent : en l'absence de précision, Python2 considère que ma chaine de caractère est une chaine ascii et il n'interprète donc pas la séquence d'échapement unicode. Pour corriger ça on peut, par exemple, re-passer sur l'ensemble du code et préfixer les chaines de caractères qui contiennent de l'unicode par la lettre "u" :

$ python2 -c 'print("\u2502")'
\u2502
$ python2 -c 'print(u"\u2502")'

Étant pressé de tester la performance de ma nouvelle librairie, j'opte pour une solution plus rapide qui consiste à utiliser un import "magique" précisant à Python2 qu'il doit considérer toutes mes chaines de caractères comme étant de l'unicode. Cette précision amène ainsi Python2 à se comporter comme Python3 vis à vis des chaines de caractères, ce qui va me simplifier la vie6 puisque la librairie est écrite pour Python3 :

from __future__ import unicode_literals

Avec ça, je n'aurai plus de problème d'interprétation de caractères unicode puisque l'interpréteur Python2 se comportera exactement comme l'interpréteur Python3 :

$ python2 -c 'from __future__ import unicode_literals;print("\u2502")'

$ python3 -c 'from __future__ import unicode_literals;print("\u2502")'

Je re-lance le test mais, cette fois, c'est une vérification de conformité de ma nouvelle librairie qui grogne. En effet, ma nouvelle librairie exige que toutes les cellules du tableau à afficher ne contiennent que des chaines unicodes. La librairie ne se charge pas de transformer d'éventuels entiers, flottants, ou datetime.datetime en chaines imprimables. Cette conversion en chaine de caractères imprimables, c'est le boulot du code qui appelle la librairie. Sauf que, pour vérifier que le code appelant respecte bien cette convention de type, j'ai utilisé un if isinstance(cell, str). La classe str correspond bien à une chaine unicode en Python3, mais pas en Python2. En Python2, les chaines unicodes sont de type unicode, pas de type str...et mon import "magique" vient de transformer toutes mes chaines str en unicode... Bon, il suffit de modifier la condition de mon test de conformité pour que ça passe :

from sys import version_info

(...)

    if isinstance(cell, str)\
        or ((version_info<(3,0) and cell.__class__.__name__=='unicode')):  # Python2

Nouvelle tentative : la librairie fonctionne bien...jusqu'au print final qui me retourne le tant redouté "UnicodeEncodeError: 'ascii' codec can't encode character u'\u2502' in position 4: ordinal not in range(128)"... Bon, je sais comment corriger ce "petit" problème : il faut appeler encode(...) et decode(...) aux bons moments sur les chaines que je souhaite imprimer, mais ça risque d'être un peu fastidieux et, surtout, d'insérer beaucoup de code Python2 dans ma librairie Python3. Heureusement, j'ai une solution alternative : j'avais tout codé de façon à pouvoir désactiver facilement l'utilisation de caractères unicodes exotiques pour enjoliver l'ascii-art. Je n'ai donc qu'à changer le comportement par défaut (afficher de l'unicode, sauf mention contraire) en son inverse pour le Python2 (à savoir : ne pas utiliser d'unicode, sauf mention contraire) :

class BEFORE:
    def __init__(self, only_ascii=False, ...)
        self.only_ascii = only_ascii


class AFTER:
    def __init__(self, only_ascii=None, ...)
        self.only_ascii = only_ascii
        if only_ascii is None:
            self.only_ascii = False if version_info>=(3,0) else True

La modification est très simple et, en fait, j'aurai du y penser avant de faire un import "magique" qui transforme la quasi totalité de mes textes en chaines unicode (on en reparlera...). Au final, j'ai touché à moins de 10 lignes et, maintenant, la librairie accepte de m'afficher des tableaux lorsqu'elle est exécutée avec un interpréteur Python2. C'est moins joli (puisque je me restreint aux symboles ascii), mais c'est quand même très lisible :

|     T1    |     T2     |Futur|
|Jan|Fev|Mar|Avr|Mai|Juin|     |
|0.0|0.2|0.8|1.3|0.7|0.7 |  ?  |
|0.7|0.9|1.3|1.4|0.9|1.2 |  ?  |

Le moment de la confrontation est donc enfin venu, je lance mon comparateur, super confiant :

$ python2 stresstest.py
(...)
Nouvelle librairie : 12.8832149506s
Ancienne librairie : 2.36754417419s

Douche froide. Une fois la première vague de déception avalée, je hack dans ma nouvelle librairie une optimisation que j'avais été contraint de faire sur l'ancienne (sinon elle était vraiiiiiment lente) : au lieu de prendre en compte toutes les lignes pour calculer la largeur idéale des colonnes, je n'en considère qu'un échantillon. (Mal?)Heureusement, ça ne sert à rien du tout et je retire ce vieux hack.

Le diagnostic

Devant un problème de vitesse, j'ai pris l'habitude de dégainer cProfile. Aussitôt dit, aussitôt fait : je commente les 6 lignes qui importent puis appellent l'ancienne librairie puis je relance le stresstest en traçant son exécution.

$ python2 -m cProfile -s cumtime stresstest.py
(...)
Nouvelle librairie : 14.5225701332s
(...)
         1110680 function calls in 15.248 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.258    0.258   15.248   15.248 stresstest.py:1(<module>)
        1   12.006   12.006   13.847   13.847 NEWLIB.py:902(__str__)
        1    0.232    0.232    0.812    0.812 NEWLIB.py:853(compute_col_width)
    50000    0.479    0.000    0.774    0.000 NEWLIB.py:733(formatted)
(...)

Cette fois, cProfile me laisse un peu tomber. En effet, ce profileur a pleins de qualités (dont celles d'être dans la librairie standard et très simple à utiliser) mais il ne trace que les appels de fonctions et, visiblement, dans mon cas ça ne sera pas assez précis. En effet, la trace m'indique qu'il passe bien 13.847s (des 14.5225701332s que stresstest.py mesure lui-même) dans la fonction __str__ de ma nouvelle librairie mais nous ne saurons pas qu'est-ce-qui, dans cette fonction de 28 petites lignes, prend le plus gros du temps (puisque la fonction qui a pris le plus de temps juste après est négligeable avec ses 0.812s alors que je pensais que ça serait justement elle la plus lente puisque c'est cette portion de code qui était critique dans la vieille version).

Heureusement, Google ne me laisse pas tomber et je découvre rapidement l'existence de line_profiler. Je l'installe donc dans un environnement virtuel avec pip install line_profiler, j'ajoute un @profile au dessus de ma fonction __str__, je baisse drastiquement le nombre de lignes du tableau (pour ne pas attendre encore 15s pour avoir mon résultat) et c'est parti :

$ kernprof -l -v stresstest.py
(...)
Total time: 2.68528 s
File: NEWLIB.py
Function: __str__ at line 902

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
   902                                               @profile
   903                                               def __str__(self):
   904         1     308429.0 308429.0     11.5          self.compute_col_width()
(...)
   913     17500     865419.0     49.5     32.2                  result += '|' if self.only_ascii else '\u2502'
(...)
   923     17500     882593.0     50.4     32.9                      result += to_add
(...)

La surprise n'est pas immense, mais ça fait plaisir d'avoir des "preuves". D'abord, on note que le calcul de largeur des colonnes prend ici 11.5% du temps alors qu'il ne représentait que 5,86% sous cProfile... C'est peut-être la différence de traceur qui explique cet écart, ou la réduction drastique du nombre de lignes. En tout cas, il reste marginal face aux 65% passés dans deux lignes anodines : des concaténations de chaines.

Anodines ? Pas tant que ça en fait. La vitesse de concaténation des chaines de caractères en Python est un sujet assez souvent évoqué sur Internet. D'ailleurs, pour rapidement construire une chaine de caractère en Python2, on voit très souvent des appels à la fonction join, censée être beaucoup plus rapide :

bigstring = ''
small_string = 'plop'

# Ça, c'est censé être lent
for _ in range(500):
    bigstring += small_string

# Ça, c'est censé être rapide
bigstring = ''.join([small_string for _ in range(500)])

Je le savais déjà, j'avais déjà utilisé ce genre de formulation (y compris dans ma vieille librairie), mais je n'avais jamais vérifié si il y avait un vrai gain de performance. Il est donc temps de vérifier ! Après cProfile, on va donc utiliser timeit, un autre module standard qui est justement conçu pour faire des comparaison de performances.

$ python2  -m timeit -s 'bigstring=""' 'for i in range(1000):' ' bigstring+="plop"'
10000 loops, best of 3: 69.7 usec per loop
$ python2  -m timeit -s 'bigstring=""' 'bigstring+="".join(["plop" for _ in range(1000)])'
10000 loops, best of 3: 49 usec per loop

D'accord c'est plus rapide, mais je n'ai même pas un facteur 2. On est loin du facteur 6 que l'ancienne librairie met à ma nouvelle.

Découverte du paradoxe

Je commence donc à être circonspect sur mon analyse. D'autant plus que, lorsque je faisais mes tests fonctionnels pendant le développement de la nouvelle librairie, elle ne m'avait pas l'air si lente que ça...

Par acquis de conscience, je prends le stresstest.py dont j'ai commenté la partie relative à l'ancienne librairie, je supprime le décorateur @profile, et je lance ce stresstest deux fois d'affilés en changeant juste l'interpréteur :

$ python2 stresstest.py
(...)
Nouvelle librairie : 66.7044699192s
(...)

$ python3 stresstest.py
(...)
Nouvelle librairie : 0.8455526828765869s
(...)

Rho la vache ! Ça serait juste une question d'interpréteur ?! La version 3 de Python aurait-elle amené un gain aussi énorme sur une fonction aussi basique qu'une concaténation de chaine ?! Vérifions, avec timeit, si le Python3 met vraiment une claque au Python2 (ça tombe bien, on a testé Python2 il y a un pragraphe de ça :-D).

$ python3  -m timeit -s 'bigstring=""' 'for i in range(1000):' ' bigstring+="plop"'
2000 loops, best of 5: 104 usec per loop
$ python3  -m timeit -s 'bigstring=""' 'bigstring+="".join(["plop" for _ in range(1000)])'
5000 loops, best of 5: 49.1 usec per loop

Là, c'est le moment où j'en ai perdu mon latin. Python3 est en fait légèrement plus lent que Python2 sur ces opérations de concaténation de chaine qui sont censées prendre la majorité du temps et, pourtant, Python2 est 79 fois plus lents que Python3 sur mon stresstest.py (sur 2000 lignes) !

Conclusion

À ce moment de l'analyse j'ai passé une bonne demi-heure à vérifier tout un tas d'hypothèse à coup de timeit. Systématiquement, Python2 était dans le même ordre de grandeur de vitesse que Python3. Puis j'ai eu une illumination...

from __future__ import unicode_literals

Évidemment, j'avais fait tous mes timeit avec des string standard or avec l'import de unicode_literals j'avais, quasi-silencieusement, transformé presque toutes mes string standard de l'interpréteur Python2 par des objets d'un type totalement différents (des objets unicode). Voyons voir si Python2 manipule aussi bien les unicode que les str :

$ python2  -m timeit -s 'bigstring=""' 'for i in range(1000):' ' bigstring+="plop"'
10000 loops, best of 3: 69.9 usec per loop
$ python2  -m timeit -s 'bigstring=u""' 'for i in range(1000):' ' bigstring+=u"plop"'
100 loops, best of 3: 117 msec per loop

Et bien voilà un joli facteur 1674 ! L'explication de l'extrème lenteur de ma nouvelle librairie quand on utilise un interpréteur Python2 se décompose donc ainsi :

  • J'ai transformé quasiment tous les objets str en objets unicode pour le Python2 avec mon import "magique"
  • Python2 est beaucoup plus lent à manipuler des objets unicode que des objets str

Pour une comparaison plus honnête entre mes deux librairies, je lance alors un stresstest de l'ancienne librairie avec un interpréteur Python2 et un autre de la nouvelle librairie avec un interpréteur Python3 :

$ python2 stresstest2.py
(...)
Ancienne librairie : 6.01993203163s

$ python3 stresstest3.py
Nouvelle librairie : 0.8533799648284912s

Pour afficher un tableau de 2000 lignes la nouvelle librairie va donc 7 fois plus vite que l'ancienne. De plus, l'affichage est meilleur7. Malheureusement, je ne peux pas remplacer mon ancienne librairie par la nouvelle dans les projets les plus importants au boulot car ils tournent encore en Python2 et qu'ils doivent traiter des caractères non-ascii. Dommage...

Au moins j'ai la nouvelle librairie pour les projets Python3, j'ai découvert line_profile, et si j'arrive à me motiver je pourrai toujours plonger dans le code de la vieille librairie pour lui adapter le nouvel algorithme de calcul de largeur des colonnes8.

  1. Le 6 aout 2016 pour être précis, donc il y a environ 4 ans (merci git :)).
  2. Cette librairie permet d'afficher des en-tête, des colonnes bien alignées les unes à côté des autres, et le contenu des cellules est tronqué de façon "intelligente" quand tout ne rentre pas dans la largeur du terminal.
  3. J'aime bien utiliser le terminal et j'aime bien les librairies minimalistes.
  4. Je suis passé d'un algo assez naïf tentant maladroitement d'implémenter du "Regret Minimization" à quelque chose de beaucoup plus court n'utilisant que deux mesures statistiques pour tenter d'aller plus vite.
  5. En réalité il remonte une exception propre, mais le résultat est le même : le programme s'arrête sur une stacktrace.
  6. En réalité, c'était une grave erreur qui va me faire perdre une heure...on s'en rendra compte plus tard
  7. C'est le premier effet bénéfique inattendu dont j'ai parlé tout en début d'article et qui découle directement du changement complet d'algorithme de calcul de la largeur optimale des colonnes
  8. On se console comme on peut.

Avaro omnia desunt, inopi pauca, sapienti nihil

Par Oz le - Électronique
PCB SSTIC arduino atmega

L'an dernier, j'avais relaté quelques unes de mes pérégrinations dans la réalisations de mes propres PCB et, depuis, je m'étais lancé dans la conception de ma propre planche de prototypage à base d'atmega(8), d'un cristal à environ 16MHz, sans doute d'un cristal de montre pour pouvoir utiliser le tout en RTC, et en gardant les ports I2C/SPI accessibles pour jouer avec des nRF24 facilement. Mais cette semaine, j'ai réalisé que ce n'était pas très malin...

Shenzen - CCBYSA by Britt Selvitelle on Flickr

Lorsque j'avais conçu un PCB pour contrôler des moteurs depuis un arduino et que je l'avais commandé (pour une bouchée de pain chez elecfreaks, je m'étais dit que c'était le début d'une longue liste de commande de PCB personnalisés. Sauf que le second dans lequel je me suis lancé (un PCB générique de prototypage) n'est toujours pas terminé. En raison de la vocation très générique de ce PCB, je n'arrive pas à me décider sur un design et je tourne en rond sans rien commander. Pourtant, j'ai trouvé un second fournisseur vraiment pas cher et je meurt d'envie de le tester. Finalement, j'ai donc décidé d'abandonner (pour l'instant) l'idée de concevoir mon propre PCB de prototypage et j'ai même décidé d'en faire un micro article afin de communiquer plus largement l'une des raisons de ce choix qui me semble méconnue : les clones d'arduino, ça ne coute rien.

L'été dernier, j'ai eu l'honneur de présenter une seconde conférence au SSTIC. Si vous regardez les slides (ou mieux : la vidéo) de cette conférence vous verrez que, lors d'un calcul de couts, je compte un arduino pour "environ 7€". Après cette conférences, plusieurs personnes sont venus me voir1 pour me dire que si ça coute vraiment si peu ils veulent bien m'en acheter une centaine pour les revendre. J'aurai du accepter :p ! En effet, les prix français/européens sont bien ancrés dans nos esprits et, pour la majorité des gens que je croise, un arduino coute environ 20~25€. Moi-même, jusqu'à il y a peu, j'avais inconsciemment l'idée qu'un arduino "ça ne coute pas cher" mais qu'un microcontrolleurs ça ne coute vraiment rien. En réalité, et c'est en partie ce qui a motivé ma décision d'abandonner mon projet de PCB de prototypage, un clone d'arduino ça ne coute quasiment rien. Pour être précis, ça coute 3,02€ chez aliexpress ou 4,70€ sur ebay,..tout ça livraison incluse.

Autant vous dire qu'à 3€ le clone d'arduino, même en déployant des trésors d'ingénierie, mon PCB conçu maison n'atteindra jamais un tel rapport qualité prix2 ! Bref : je me suis commandé une demi-douzaine de clones d'arduino (chez 3 vendeurs différents, pour limiter les risques de paquets s'évaporant en chemin) pour moins de 20€, et je peux à présent passer à la conception de PCB dédié à une tache spécifique :-D ! Les deux seuls inconvénients de cette solution découlent du format bien particulier de l'arduino : il fait un peu plus de 5cm de large (donc pour nos shields on rate, de quelques millimètres, le format le moins cher des graveurs de PCB : 5cmX5cm) et les deux rangées de connecteurs empilables ne sont pas alignées3 ce qui est un peu chiant pour l'alignement dans gschem. En tout cas, j'espère avoir motivé certains d'entre vous à ressortir leurs arduino du tiroir/placard où il prend la poussière, et je conclurai ce billet ainsi : Happy Hacking !

  1. D'ailleurs : merci à tous pour vos retours ! C'est vraiment très sympa de savoir que la conférence a été appréciée, au moins par certains :)
  2. Sur le prix d'un PCB personnalisé on peut déjà compter 1€ pour le microcontrôleur et minimum 1€ pour le PCB. Il ne reste plus grand chose pour les connecteurs, les cristaux, les résistances/diodes, et la main d’œuvre
  3. En électronique amateur l'un des standard d'espacement les plus répandus est 0,1", soit 2.54mm. L'arduino utilise cet espacement partout sauf à un endroit, où il y a un décalage de 0,16" ce qui décale la moitié du PCB ...Pourquoi ont-ils fait ça?

Mes frameworks python du moment

Par Oz le - Informatique
bottle peewee python wsgi

Fin 2012, je vous avait parlé de deux modules standards de la librairie python que j'aimais beaucoup : logging et argparse. Presque deux ans plus tard, il est temps de rendre hommage à deux modules n'appartenant pas à la librairie standard python mais que j'aime tout particulièrement : peewee et bottle.

Swiss Knife - Creative Common by "focusforaword" on Flickr

Sqlite, MySQL, PostgreSQL ? Les trois !

Nombre des scripts python que j'écris ont besoin, lorsqu'ils atteignent une certaine importance, de stocker des informations de façon stable. Dans les cas les plus rustres je me contente d'un gros coup de pickle dans un fichier qui sera relu plus tard mais, parfois, le stockage et l'accès à mes données doit être plus performant et l'utilisation d'un outil dédié (à savoir : une base de donnée) semble trop évidente pour être ignorée. Avant que je ne découvre peewee, je réglais systématiquement ces besoins par la librairie sqlite31, qui a le bon gout d'être standard et, donc, de ne pas rajouter de dépendance à mes scripts (les laissant ainsi le plus portable possibles d'une machine à une autre). Malheureusement, cette approche avait deux défauts majeurs pour moi :

  • Si sqlite s'avérait, au bout de plusieurs semaines/mois d'utilisation, trop léger pour traiter mon volume de donnée je n'avais plus qu'à tout reprendre de zéro pour passer à une solution plus robuste

  • Je suis mauvais en SQL, donc taper les requêtes SQL moi-même était à la fois désagréable et peu efficace.

C'est pourquoi, lorsque j'ai découvert peewee, j'ai tout de suite adhéré au concept : c'est un orm (donc pas de SQL à écrire) capable d'utiliser un backend sqlite, mysql, ou postgresql sans avoir à changer le code :) ! En plus, je connais quelqu'un qui m'a dit récemment avoir testé peewee sur un backend sqlite avec une dizaine de thread concurrent sans le moindre problème. Étant assez fan du multithread et ayant déjà eu des problèmes avec sqlite ça serait pour moi la cerise sur le gateau si cette robustesse en multithread se confirmait :) ! En tout cas, j'ai déjà utilisé peewee sur une demi douzaine de projets (dont un qui commence à devenir assez imposant) et c'est toujours un plaisir de travailler avec cet ORM : je le conseille donc vivement.

Seul tout petit bémol, pour terminer le paragraphe : j'ai eu UN problème avec peewee. Je voulais utiliser un modèle ou une table A référence (foreign key) une table B; sachant que la table B doit, elle aussi, avoir une foreign key vers la table A. Oui, je sais, ça fait des références circulaires et ce n'est généralement pas le signe d'une bonne conception mais dans mon cas d'usage c'est ce que je voulais faire et il n'y avait pas vraiment d'autres alternative plus propre. Comme peewee crée les table en base au fur et à mesure qu'il lit la déclaration des objets, ce cas d'usage pose problème puisqu'au moment de créer la première table peewee n'a pas (encore) connaissance de la seconde et il échoue plante lors de la création de la foreign key vers une table qui n'existe pas encore. Si une seule des deux tables référençait l'autre, il me suffirait d'inverser l'ordre de déclaration des tables pour que peewee découvre la table cible en premier, mais comme j'ai une référence dans les deux sens cette astuce ne me sauvera pas. Tout n'est pas perdu pour autant : peewee prévoit ce cas de figure et propose d'utiliser un objet "proxy" qui sera la cible de la foreign key lors de la création des tables puis qui sera remplacé par les tables réellement ciblées une fois qu'elles auront toutes été créées. En pratique, ça marche probablement...SAUF quand le backend est sqlite.

En effet, pour réaliser ce tour de passe-passe, peewee crée les tables sans les foreign key lorsqu'il découvre la déclaration des objets, puis il utilise l'opération SQL "ALTER TABLE" pour ajouter les "CONSTRAINT" de foreign key au moment où l'objet proxy est remplacé par les bonnes tables une fois que ces dernières ont toutes été créées. Sauf que sqlite ne supporte pas cette fonctionnalité du SQL. Dans ce cas, il n'y a que deux solutions :

  • abandonner sqlite
  • créer (et gérer) soit même la relation de foreign key, en utilisant de simples champ "INTEGER" référençant un ID dans la table cible (c'est ce que j'ai choisi).

Nginx ? Apache ? IIS ? Aucun des trois !

Une autre fonction classique de mes script python lorsqu'il prennent de l'ampleur, c'est d'avoir une interface web (plus ou moins simpliste). Pour ce faire, j'ai longtemps surchargé BaseHTTPServer. J'ai bien tenté d'utiliser cherrypy ou django quand je prévoyais que mes scripts allaient demander un peu plus de complexité, mais j'ai vite abandonné2. Bref : j'utilisais toujours BaseHTTPServer, et j'étais contraint de ne faire que de petits sites un peu minables...

Puis, un jour, j'ai découvert wsgi sur l'excellent site de bortzmeyer. En résumé : c'est une spécification, dans un esprit assez similaire à CGI, qui définit une interface python très simple pour fabriquer des sites web. Pour offrir une interface web à votre script python il vous suffit donc de créer une classe d'objet "application" compatible avec la spécification WSGI, et à donner cette classe en argument à un serveur web compatible (par exemple, le "simple_server" de la librairie standard wsgiref). L'énorme avantage, c'est que si vous avez besoin de performance plus tard il vous suffit de changer le serveur web sans changer une seule ligne de votre code python (un peu comme lorsque vous changer de backend peewee). Par exemple, vous pouvez remplacer le serveur inclus dans la librairie standard par werkzeug ou cherrypy et vous obtenez immédiatement le support du multithread (qui est quand même un must pour tout ce qui est web).

Le seul inconvénient de WSGI (qui m'est tombé dessus assez vite), c'est que ça reste quand même assez rustre. On est à un niveau d'abstraction supérieure à BaseHTTPServer, mais il manque quand même des raccourcis pour réaliser certaines tâches classiques (comme mettre des fichiers statiques à dispositions, types CSS ou JS). On se retrouve donc rapidement à devoir passer du temps de développement sur des fonctions "inutiles" vis-à-vis de l'objet du script mais nécessaires au fonctionnement de l'interface web (et servir des fichiers static peut prendre beaucoup de temps de développement, en particulier quand on est paranoïaque et qu'on veut faire attention aux LFI et autres farces). C'est pourquoi, je conseille bottle ! Bottle est une librairie python non-standard typiquement dans l'esprit de ce que j'aime : elle tient en un seul fichier python (et vous pouvez donc l'embarquer partout sans sacrifier la portabilité de votre script :)). C'est un wrapper mince autour de la spécification WSGI qui vous offre des facilité pour tout un tas de besoins classiques, par exemple :

De plus, comme bottle est un wrapper mince, on ne perd pas la puissance de WSGI puisqu'on peut passer d'un simple serveur embarqué écrit en python à des choses plus musclées comme gunicorn ou bjoern sans avoir à ré-écrire son code ! Cerise (inutile mais agréable) sur le gateau : bottle accepte d'utiliser un serveur "auto" signifiant qu'il va, tout seul, sélectionner le serveur compatible WSGI le plus performant actuellement installé sur votre machine (sympa quand vous avez cherrypy sur vos machines de prod mais pas sur les machines de dev par exemple).

  1. et, par moments, pysqlite qui permet d'optimiser un peu l'utilisation du moteur sqlite
  2. Je conserve de ces tests une légère rancœur envers django, qui m'a laissé la très mauvaise impression de sortir une nouvelle version tout les 6 mois tellement incompatible avec les versions précédentes que même les tutoriaux "Hello World" ne fonctionnaient subitement plus

shutdown -h -~1500

Par Oz le - Perso
RIP sid

Hier, Cédric "Sid" Blancher est mort d'un accident de parachutisme. En plus d'être un hacker extrèmement compétent c'était quelqu'un de gentil qui communiquait ses passions à merveille. D'ailleurs, si ce blog existe c'est en grande partie grace à l'inspiration prodiguée par sa petite parcelle d'internet. Je ne le connaissais pas très bien mais j'avais l'habitude de le voir de loin aux conférences de sécurité informatique où je traine mes guètres, et j'ai même eu le privilège et le plaisir de discuter quelques fois avec lui à ces occasions. Il va manquer au paysage de la SSI française et à beaucoup de monde, dont moi. RIP Sid.

"RIP"

Les mots me manquant je me contenterai, en conclusion, de lier ci-dessous quelques homages supplémentaires, sans prétention d'exhaustivité (loin de là) :

Crypto à retardement : à la règle et au compas

Par Oz le - Sécurité
SSTIC challenge cryptographie

Ce billet est le dernier d'une série de 4 portant sur l'analyse à postériori de l'étape 2 du challenge SSTIC 2013. Si vous n'avez lu aucun des billets précédents je vous invite à lire au moins l'introduction du premier avant de plonger dans celui-ci. Si vous avez lu les billets précédents : félicitations, vous arrivez au bout du tunnel :) !

enigma - Creative Common CCBY by "joncallas" on flickr

Les classiques

Dans les billets précédents j'ai avancé pas mal dans la cryptanalyse de data mais je reste encore relativement loin de la solution. Il est probable qu'en forçant dans cette voie je finisse par obtenir la bonne solution, mais il est temps d'explorer une autre voie ! Jusqu'à présent j'ai beaucoup avancé par recettes persos en tirant parti de mes connaissances sur la crypto du 19ème siècle et antérieur, mais je pense qu'il est temps de se pencher sur ce qui se fait dans les attaques crypto un peu plus modernes.

J'ai donc raffraichi pas mal de vieux souvenirs de cours et j'ai éliminé une à une toutes les attaques modernes.

Au final je me suis dit que je ne trouverai pas de protocole d'attaque "tout prêt" utilisable dans mon cas. Tout ce temps n'était pas perdu pour autant ! A force de lire toutes ces méthodes d'attaques, et les descriptifs des chiffrements attaqués, j'ai réalisé que le schéma SBox-PBox-XOR était vraiment très, très, très répandu et que les SBox tenait un rôle de première importance dans la force du chiffrement. Je me suis alors dit : "et si on était en face d'un algorithme de chiffrement de ce type, particulièrement nul ?". Le "particulièrement nul" était légitime, puisque c'était notre hypothèse de base depuis le départ (après tout c'est un challenge, on est censé pouvoir le casser !). Sur wikipédia on vous explique que l'une des caractéristiques les plus essentielles des SBox c'est de générer beaucoup de changements de bit (environ 1 sur 2) quand on change un seul bit en entrée; j'ai donc supposé qu'on avait à faire à une SBox tellement nulle qu'elle changeait un seul bit quand on changeait un seul bit en entrée :)

Ce bon vieux Hamming

En formulant cette hypothèse de faiblesse de la SBox, je ne sais pas pourquoi, j'ai immédiatement pensé à la distance de hamming : si je prends deux octets qui diffèrent d'un seul bit, et que je les passe dans ma mauvaise SBox, leur représentation chiffrée diffèrerons, elles aussi, d'un seul bit ! Ce qui devient vraiment sympa c'est que, lorsque je passerai ces représentation chiffrées dans la PBox, les deux octets résultants diffèreront, eux aussi, d'un seul bit entre eux (une PBox se contente de ré-ordonner les bits de façon déterministe). La cerise sur le gateau c'est que si j'applique un XOR à mes deux sorties de SBox, les deux octets que j'obtiendrai diffèreront, encore une fois, d'un seul bit ! En bref : si la SBox est aussi nulle que je l'ai supposé, deux octets ayant une distance de hamming de 1 seront chiffrés (par tout l'algorithme de chiffrement) en deux octets ayant une distance de hamming de 1 entre eux.

Arrivé à ce point j'ai fait une petite généralisation illégitime : si la SBox est vraiment pourri, peut-être que la distance de Hamming est laissée invariante par l'application de l'algorithme de chiffrement. Formulé comme ça, ça n'a pas forcément l'air super excitant, mais en fait, ça pourrait devenir essentiel. En effet, je sais que mon texte d'origine est en base64 et qu'il contient donc un sous-ensemble des valeurs possibles d'un octet. Peut-être qu'avec un peu de chance l'ensemble des distances de Hamming d'un élément de l'alphabet base64 aux autres éléments de ce même alphabet est caractéristique ? Peut-être pourrais-je donc me servir de cet "ensemble des distances aux autres éléments de l'alphabet" comme d'une espèce d'empreinte digitale.

Pour vérifier cette seconde hypothèse (i.e. : que l'ensemble des distances est partiellement caractéristique) j'ai tracé, pour chaque élément de l'alphabet base64, une droite horizontale composé de rectangles colorés. Chaque rectangle coloré correspond aux éléments de l'alphabet distant de la distance X de mon élément de référence (X étant écrit sur le rectangle coloré). Je vous mets l'image ci-dessous et je vais expliquer la première ligne ensuite, ça sera sans doute plus clair comme ça :

Hamming fingerprinting of base64 charset - Creative Common CCBYSA by Ozwald from ozwald.fr

La première ligne de cette image montre "l'empreinte digitale" de la lettre de code ascii "0xa" (c'est à dire du caractère "retour charriot") dans l'alphabet base64. On voit que ce caractère:

  • n'est distant d'une distance 0 que d'un seul autre élément de l'alphabet base64 (à savoir : lui-même)
  • est distant d'un unique caractère de l'alphabet base64 d'une distance de 1
  • est distant de 7 caractères de l'alphabet base64 d'une distance de 2
  • est distant de 16 caractères de l'alphabet base64 d'une distance de 3
  • ...
  • est distant d'un seul caractères de l'alphabet base64 d'une distance de 7

En regardant l'image dans son ensemble on a l'impression qu'il n'y a pas deux lignes qui soient identiques. C'est une bonne nouvelle pour nous : notre élément caractérisant (i.e. : l'ensemble des distances de Hamming aux autres éléments de l'ensemble) est bel et bien caractérisant puisqu'unique à chaque symbole de l'alphabet base64 !

Je vais donc pouvoir tracer les "empreintes de Hamming" des octets chiffrés de data et en tirer des conclusions. Malheureusement, nous avons vu que nos buckets ne contiennent qu'environ 55 valeurs différentes (au lieu des 65 possibles) et mes empreintes seront donc partielles...Je ne vais ainsi sans doute pas pouvoir faire d'identification immédiates, mais je vais au moins pouvoir faire des éliminations. En effet je sais que si je trouve une distance de Hamming de 7 entre deux octets chiffrés ceux-ci appartiendront forcément à l'ensemble des clairs qui possèdent au moins une distance de Hamming de 7; de même si je trouve un octet qui a deux distance de Hamming de 1 il ne peut correspondre qu'aux clairs qui ont au moins deux distances de Hamming de 1; et ainsi de suite.

En appliquant cette méthode j'obtient une réduction drastique du problème. Pour beaucoup d'octets chiffrés je me retrouve avec moins de 10 clairs possibles. C'est donc une bonne avancée, mais c'est insuffisant. Comment aller plus loin ? En triangulant :) ! Après tout, nous avons une propriété de conservation d'une distance, et quand on cherche à placer des points les uns par rapports aux autres en connaissant la distance qui les sépare, moi ça me fait penser à de la triangulation. En substance je vais donc passer plusieurs fois sur l'ensemble de tous mes octets chiffrés en supprimant les clairs potentiels qui ne sont pas à une distance possible par rapport aux clairs possibles des autres chiffrés.

Formulé de façon plus "informatique" :

pour chaque octet chiffré, A :
    je vais étalibr une liste temporaire, L, contenant tous les clairs possibles vis à vis de la triangulation
    Cette liste est initialement vide
    pour chaque autre octet chiffré, B je vais :
        mesurer la distance de hamming, H, le séparant de A. 
        pour chaque clairs possible de B :
            je rajoute à ma liste L les clairs qui y sont distants de H. 
    la nouvelle liste de clairs possibles pour A est l'intersection de son ancienne liste de clairs possible et de la liste L.

Ca a l'air assez bourrin mais, vous savez quoi ? Ca marche :) En quelques itérations (à la louche une vingtaine) et moins de 5s de calculs je me retrouve avec un seul clair possible pour chacun des chiffré. En appliquant la substitution ainsi trouvée j'obtient bien la solution de l'étape 2 ! Comme quoi tous les essais relatés dans les billets précédents étaient inutiles...1

Comme quoi, il était aisé de passer cette étape sans regarder le FPGA, mais encore fallait-il faire LA bonne hypothèse...


Dromi le 2013/09/10 13:10

Super intéressant ! Merci !
Puisque tu te remets doucement à l'électronique, n'oublie pas que le hardware peut aussi être très utile en crypto ! Entre ceux qui utilisent leur carte graphique pour faire des calculs plus rapides (méthode bruteforce, avec la fourberie en plus), ou ceux qui implémentent des processeurs de crypto en FPGA, il y a de quoi faire ! (toi aussi reconvertit toi en mineur de Bitcoins sur FPGA...)

  1. Si on fait abstraction de l'expérience acquise et d'une petite entourloupe : avec la triangulation pure j'obtient en fait quelques milliers de combinaisons possibles et pas directement la bonne solution. Ca reste aisément bruteforçable, mais j'ai préféré hard-coder les relations chiffré<=>clair que j'avais trouvé pour les retours charriots tout au début de l'analyse puisque, là, je tombe directement sur le bon résultat par triangulation :)

Page 1 / 11 »