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.

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

Projet de Weekend : Tourelle de surveillance

Par Oz le - Robotique
HC-SR04 UART arduino atmega python robot servo électronique

Après plusieurs billets assez pauvre en contenu je me suis dit que résumer un micro-projet mettant en oeuvre plusieurs techniques différentes serait une bonne idée. Voici donc le résumé de la création d'un petit jouet qui m'a couté environ 7€ 1 ! Je vous laisse découvrir un à un les différents domaines que j'ai associés et essayer de deviner au fil de l'eau ce que j'obtient à la fin et qui constitue le but de ce projet (ainsi que le titre du billet...j'aurai d'ailleurs du y mettre des balises SPOIL ^^ ). Bonne lecture !

Tour de surveillance - Creative Common CC-BY-SA by Ozwald (me)

Un peu de vision

J'ai déjà expliqué sur ce blog comment on peut facilement programmer un micro-controlleur2, et nous avons également déjà vu comment utiliser ces micro-controlleurs pour faire tourner des moteurs, ce qui permet (par exemple) de faire bouger un robot. Nous savons donc à présent comment fabriquer un robot qui agit sur le monde (en s'y déplaçant) mais nous n'avons pas encore vu de méthode pour que le robot prenne connaissance du monde (or d'aucun diront qu'il est intéressant de comprendre son environnement avant d'agir). La première connaissance nouvelle que nous allons aborder dans ce billet c'est justement comment mesurer la distance qui sépare notre robot d'un obstacle situé devant lui.

Beaucoup de méthodes existent pour mesurer des distances sans contact. On peut par exemple citer les mesures de déphasages entre un rayon laser émis et son reflet renvoyé par l'obstacle, les mesures de focalisation d'un signal lumineux (généralement infra-rouge) émis puis réfléchi par l'obstacle, ou encore la mesure de temps entre l'émission d'un signal acoustique (généralement ultra-son) et la réception de son écho produit par l'obstacle.

Dans ce mini-projet j'ai opté pour la mesure par ultra-son, pour deux raisons :

  • c'est la méthode la moins chère (on trouve des modules tout fait à moins de 1.50€ sur eBay, à moins de 6$ sur amazon, à moins de 10€ sur robotshop, ou à 15€ chez gotronic pour la classe au dessus).
  • Ces modèles peu onéreux permettent pourtant déjà de mesurer des distances allant, classiquement, de quelques centimètres à environ 4m, ce qui est parfait pour un usage en intérieur.

Plus précisément j'ai opté pour un HC-SR04, qui semble être l'un des modèles les plus répandus (mais pas l'un des plus fiables).

HC-SR04 - Creative Common by "scanlime" on Flickr

Le fonctionnement de ce module est simplissime : on branche la PIN "GND" du module à la masse de notre circuit, la PIN "VCC" à une alimentation 5V, et les PIN "trig(ger)" et "echo" chacune à une I/O de notre microcontrolleur. Pour mesurer la distance qui sépare ce module d'un obstacle situé devant lui on envoie simplement une impulsion positive d'environ 10us sur la PIN "trigger" du module, puis on mesure la longueur de l'impulsion positive que nous envoie le module en réponse sur sa PIN "echo". La longueur de l'impulsion de réponse (sur la PIN "echo") est proportionnelle au temps mis par le son pour faire l'aller-retour entre le module et le premier obstacle rencontré (la vitesse du son étant à peu près constante on en déduit alors la distance qui sépare le module du premier obstacle situé devant lui). Pour être précis on considère que 1cm se traduit en environ 58uS d'impulsion "echo"; si je reçois une impulsion retour qui dure 580uS j'en déduis donc qu'il y a un obstacle à environ 10cm devant mon module. Trivial3 !

Un peu d'action (controllée)

La denière fois que nous avons parlé d'agir sur le monde depuis un microcontrolleur nous avions fait tourner des moteurs, dans un sens ou dans l'autre, à une vitesse arbitraire. C'est déjà très pratique, mais pas vraiment adapté à des mouvements finements controllés; en effet nous ignorons tout de la vitesse réelle de rotation du moteur (en fonction de la résistance qu'il rencontrera lors de sa rotation il tournera plus ou moins vite pour une même commande donnée). Pour palier ce manque de précision nous avons, là encore, de nombreuses options qui s'offrent à nous. Nous pouvons par exemple asservir la commande du moteur à la lecture de capteurs qui nous renseigneront sur la rotation réellement effectuée, ou nous pouvons opter pour des moteurs "pas à pas" plus compliqués à commander mais qui offrent une bien meilleure précision de commande, ou encore nous pouvons utiliser des servomoteurs qui permettent d'obtenir directement un déplacement asservi.

Pour ce petit projet nous allons opter pour un servomoteur. J'aurai pu avantageusement partir sur un moteur pas à pas mais j'avais besoin de jouer avec des servomoteurs pour un autre projet donc j'ai décidé de faire d'un pierre deux coups et de mettre également un servomoteur dans ce micro-projet. En plus, comme les capteurs ultrason hc-sr04, les servomoteurs ont le bon gout d'être simple à utiliser et peu cher (on en trouve à moins de 2€ sur eBay, à 3$ sur amazon, à un peu plus de 4€ chez gotronic, ou encore à une quinzaine d'euros chez selectronic pour la gamme au dessus).

Servo premier prix - Creative Common by "Nick Ames" on Flickr

Généralement les servomoteurs se connectent via 3 fils. Les couleurs varient selon les constructeurs mais vous pourrez trouver facilement les équivalences en cherchant sur internet. Les servomoteurs que j'ai (les même que celui de la photo ci-dessus) suivent les couleurs traditionnelles du constructeur Graupner :

  • un fil marron que je dois brancher à la masse
  • un fil rouge que je dois brancher à mon "VCC" (alimentation 5V);
  • un fil orange sur lequel je dois envoyer la commande. Comme je vous l'ai déjà dit la commande d'un servomoteur est simple : on doit envoyer sur le fil de commande, à intervalle régulier (environ toutes les 20ms au plus), une impulsion positive dont la largeur est notre commande4. L'impulsion doit avoir une largeur comprise, environ, entre 0,5ms et 2,5ms. Lorsque la commande est correctement envoyée l'axe du servomoteur s'aligne sur un angle compris entre 0° et 180°, proportionnellement à la commande envoyée5. Donc si j'envoie, toutes les 20ms, des impulsions de 0,5ms sur la commande de mon servomoteur celui-ci va s'aligner sur -90° et ne plus en bouger. Si j'allonge mes impulsions jusqu'à 1,5ms l'axe du servomoteur va tourner environ jusqu'à 0° et ne plus bouger. Enfin si je rallonge mon impulsion jusqu'à 2,5ms l'axe va sagement s'aligner sur +90°. L'avantage d'avoir un asservissement directement dans le servomoteur c'est que son axe va s'aligner à un angle correspondant à ma commande quelque soit la résistance à son mouvement, je n'ai pas à me préoccuper d'asservir le bouzin, c'est prévu dans le forfait de base.

Un peu de dialogue

Les amateurs d'arduino sont habitués à communiquer avec leur joujou préféré depuis leur PC en le branchant simplement en USB, seulement voilà : les atmega8 n'ont pas de port USB et donc pas de méthodes native pour discutter avec un PC. Pour palier ce "problème" nous avons, encore une fois, plusieurs solutions :

Les microcontrolleurs incluant directement le support de l'USB ont l'inconvénient d'être plus cher que nos composants "low cost" (atmega8, atmega328, attinyX5, etc.), mais surtout ils sont plutôt disponible au format TQFP qu'au format DIP6, donc j'exclus cette solution pour ce mini projet.

Implémenter la pile USB sur un atmega8 c'est sympa, mais comme je ne maitrise pas encore toutes les subtilités du débugage sur microcontrolleurs et que, de toute façon, la gestion USB pomperait quasiment toutes les resources du microcontrolleur, j'exclus aussi cette solution.

Il nous reste donc le passage par un "interprète". Ca tombe bien, sur internet on peut trouver des petits montages tout fait autour du chipset cp2102 pour moins de 2€ sur eBay ou moins de 9$ sur DX.

Convertisseur UART-USB à base de CP2102

Ces petits montages discutent en USB avec l'ordinateur, et en UART avec notre microcontrolleur. Avantage certain : les chipsets cp2102 sont pris en charge directement par le noyau linux depuis la version 2.6.12, il suffit donc de le brancher pour se retrouver avec un /dev/ttyUSBX fonctionnel qui fait le pont jusqu'à notre microcontrolleur :) Coté microcontrolleur l'UART est un protocole de communication série "universel" intégré en hardware dans les atmega8 et supérieurs7 ce qui permet de ne consommer quasiment aucune ressource de calcul !

Une fois le montage branché il nous suffit donc de coder la communication. Coté microcontrolleur c'est supporté en hardware, donc après la routine d'initialisation le code d'envoi d'un octet se résume à vérifier que le flag "REady" est positionné, puis à inscrire l'octet à envoyer dans le registre dédié "UDR" (on fait difficilement plus simple...) :

/* Wait for empty transmit buffer */
while ( !( UCSRA & (1<<UDRE)) ) {};
/* Put data into buffer, sends the data */ 
UDR = data;

Coté PC c'est de la communication série standard, vous pouvez donc utiliser des softs "tout fait" comme minicom, ou dénicher une librairie de communication série pour dialoguer à partir de votre language de script préféré :

import serial
ser = serial.Serial('/dev/ttyUSB0', 4800, stopbits = serial.STOPBITS_TWO, parity = serial.PARITY_ODD)
while True:
    print ord(ser.read(1))

Bien entendu la communication peut être bi-directionnelle sans aucune modification matérielle et sans vraiment plus d'effort de code (il faut remplacer ser.read par ser.write en python et lire un registre au lieu d'en écrire un du coté de l'atmega...dur n'est ce pas ?).

Un peu de superficiel

Je suppose maintenant que vous voyez où on va avec ces différentes briquettes et le titre de ce billet : nous montons une "tourelle de surveillance" (visible sur la photo tout en haut de ce billet). Cette "tourelle" va être constituée d'un capteur de distance à ultra-son, monté sur un servomoteur, controllé par un atmega8, communiquant avec un PC via UART/USB. L'idée c'est que nous allons mesurer la distance qui nous sépare d'un obstacle "devant nous", puis nous allons faire tourner le servomoteur de quelques degrés et nous allons à nouveau faire une mesure de distance. En itérant ainsi le procédé nous pouvons obtenir une cartographie à 180° de la distance qui nous sépare du premier obstacle; obtenant ainsi une vision partielle de la pièce dans laquelle nous sommes. Grace à la communication avec le PC nous pouvons, en prime, obtenir une jolie visualisation de ces informations à la façon "radar".

Pour ne pas changer les bonnes habitudes j'ai codé tout le bouzin en python :

  • Pour réaliser la communication j'utilise la librairie "pyserial"
  • Pour faire une "jolie visualisation" j'utilise pygame.

Avec ces deux éléments, un peu d'huile de coude, et 93 lignes de python (commentaires inclus), j'obtiens un joli écran "radar" ^^ Grace à la fonction pygame.image.save c'est un jeu d'enfant de sauvegarder chaque frame affichée, et grace à la toute puissance de la ligne de commande linux je peux vous faire partager le résultat facilement :

Radar - Creative Common par ozwald, janv. 2013

Pour ceux qui ne connaissent pas la pièce ça ne ressemble sans doute pas à grand chose, mais moi je vois bien les deux murs de ma pièce, la porte (ouverte) entre les deux murs, et mon armoire tout à droite (quand au gros obstacle collé tout à gauche du capteur...c'est moi -_-)

Conclusion

Et c'est tout pour ce résumé de la création d'un micro jouet conçu et bidouillé en quelques heures seulements :) Vous noterez que j'ai jeté un voile pudique sur la partie mécanique du projet, mais j'ai bien l'intention de revenir dessus dans un article ultérieur puisque c'est un domaine sur lequel j'ai également réalisé pas mal de recherches et progrès récemment, notamment grace à l'excellent "Guerrilla guide to CNC machining, mold making, and resin casting"8 et à ce produit miracle que l'on appelle "polymorph plastic".

En guise d'ultime conclusion un petit rappel des couts de construction (hors mécanique; comptez moins de 5€ de mécanique) :

Atmega8     1.50
UART-USB    1.80
servo       2
HC-SR04     1.50
============
TOTAL       6.80 €

Alexis le 2013/12/13 10:07

Bonjour,

Dans le cadre de notre projet de Terminale, mon groupe et moi-même sommes intéressés par ce capteur.

Cependant, une phrase nous bloque: "Appliquer à la pin "TRIGGER" une impulsion de niveau haut (5V) durant au moins 10µs pour que le module démarre sa lecture" Comment déclencher cette impulsion ? Est-ce difficile pour notre niveau ?

Merci d'avance.
Cordialement,

ozwald le 2013/12/16 14:44

Déclencher cette impulsion (dont la précision n'est pas importante) est bien plus facile que de mesurer la durée d'impulsion retournée par le module... Par exemple : si vous utilisez un microcontrolleur atmel pour envoyer le signal un code comme celui-ci fera l'affaire (en supposant que la pin TRIGGER du module est branchée sur le pin PB1 du microcontrolleur) : PORTB |= 1<<PB1; _delay_us(10); PORTB &= ~(1<<PB1);. En arduino on aurai un code similaire (en supposant cette fois que la pin TRIGGER du module est branchée sur le pin 13 de l'arduino) : digitalWrite(13, HIGH); delayMicroseconds(10); digitalWrite(13, LOW);

  1. Sans compter la main d'oeuvre, évidemment ;-)
  2. Vous pouvez également utiliser un arduino, c'est juste un peu plus cher
  3. Attention, le fonctionnement de ce module HC-SR04 vu "de l'extérieur" est trivial mais je vous rassure : son fonctionnement complet est un poil plus complexe. En effet, afin d'éviter d'être perturbé par des bruits parasites, le module se charge d'envoyer en réalité plusieurs trains d'ondes séparés pour fiabiliser sa mesure. C'est l'intérêt d'un module "tout fait" par rapport à un système bricolé à la main à partir des éléments d'émission et de réception ultra-son uniquement.
  4. Une méthode simple de faire ça sans consommer de temps de calcul de notre microcontrolleur c'est d'utiliser une PWM dont la fréquence avoisinne les 50/60Hz
  5. je ne parierai pas sur la linéarité de la relation entre l'angle du servomoteur et la largeur de l'impulsion ceci-dit...
  6. Petite parenthèse : le format "DIP" c'est le format standard du prototypage, c'est facilement manipulable et soudable à la main, les pattes des composants sont espacés de 2.54mm. Le format "TQFP" en revanche est nettement plus petit et, bien qu'il soit soudable à la main, vous allez galérer pour le manipuler et le mettre en place correctement puisque les pates peuvent s'y trouver espacées de seulement 0.4mm.
  7. Les attiny n'embarquent qu'une version "light" de l'UART que je n'ai pas testé, mais j'ose espérer que ça marche quand même
  8. Guide rédigé par Michal Zalewski alias lcamtuf qui ne se contente pas d'être un expert reconnu en sécurité informatique mais qui réalise aussi de bien jolis robots. Bref : un gars certainement très bien :-D !

Petites astuces vite fait

Par Oz le - Geek
code source python

Pour renouer avec les quelques billets express que j'ai déjà pu faire voici, en vrac, une poignée d'astuces (principalement python) qui pourraient être utiles.

Swiss Knife - Creative Common by "focusforaword" on Flickr

Python2 ou Python3 ? Les deux !

J'ai l'impression que tout le monde code en python2, malheureusement "Python 3.x is the present and future of the language" donc il va bien falloir y passer. Pour ma part j'étais réticent à passer à Python3 principalement à cause d'une unique différence print "toto" en python2 (que je trouvais très pratique) devient print("toto") en python3, or des "print" j'en colle à toutes les sauces dans mes scripts. L'habitude étant ce qu'elle est je me retrouvait toujours à coller un print "toto" quelque part dans mon code et je me disait "oh et puis zut" et je basculais en 100% python2. Aujourd'hui je partage avec vous une "astuce" que j'utilise à présent pour rendre mes scripts compatibles python2 ET python3 : je remplace les print par les fonctions du module standard logging.

import logging
logging.basicConfig(level = logging.DEBUG, format="%(message)s")

//équivalent de 
// print "toto" # en python2
// print("toto") # en python3
logging.debug("toto")

Autre avantage du module logging : ça gère directement les différents niveau de verbosité1. Entre logging.debug, logging.info, logging.warning, et leurs consoeurs vous trouverez forcément le niveau de log qui vous plait; ainsi il n'est plus besoin de commenter en masse les print entre votre version de "dev" et de "prod" ^^

Le C c'est bien, mais parfois il faut l'oublier

J'aime beaucoup le C, mais sur ce coup là ça m'a joué un mauvais tour : quand j'ai voulu parser les arguments de la ligne de commande de mes scripts python je me suis intéressé au module getopt qui ressemble furieusement à ce qui existe en C. Erreur grossière : j'aurai mieux fait de regarder argparse qui est beaucoup plus pythonique et infiniment plus pratique ! A titre de comparaison voilà un exemple typique avec les deux modules. Les arguments possibles sont -h/- -help pour afficher l'aide, ou -v/- -verbose suivi d'un niveau de 0 à 4 pour régler la verbosité du programme. Voilà deux équivalents fonctionnels, l'un avec argparse, l'autre avec getopt :

import argparse, logging

parser = argparse.ArgumentParser(description='Super script de la mort qui tue')
parser.add_argument('--verbose', '-v', type=int, dest='verb', help='verbosity level [0-4]', default=4, choices=[0,1,2,3,4])
args = parser.parse_args()

logging.basicConfig(level = logging.CRITICAL-args.verb*10, format="%(message)s")
logging.debug("Debug") # cette ligne et les 2 suivante servent juste a voir que le setting du niveau de verbose fonctionne
logging.info("Info")
logging.warning("Warning")

Contre :

def usage():
    print "La on a un souci puisqu'on doit utiliser 'print'..."
    print "Et puis surtout on doit ecrire son 'usage' soit-meme alors qu'argparse l'ecrit automatiquement"
    print "Usage : %s [--verbose/-v LEVEL]"%sys.argv[0]
    print " --verbose/-v LEVEL\\tVerbosity level between 0-5 [default to 4]" 

import sys, getopt, logging
try:
    opts, args = getopt.getopt(sys.argv[1:], "v:h", ["verbose", "help"])
except getopt.GetoptError, err:
        print str(err) # will print something like "option -a not recognized"
        usage()
        sys.exit(2)

verbose = 4
for o, a in opts:
    if o in ["-v","--verbose"]:
        try:
            verbose = int(a)
        except:
            usage()
            sys.exit(2)
        if not verbose in [0,1,2,3,4]:
            usage()
            sys.exit(2)
    elif o in ['-h', '--help']:
        usage()
        sys.exit(0)

logging.basicConfig(level = logging.CRITICAL-verbose*10, format="%(message)s")
logging.debug("Debug") # cette ligne et les 2 suivante servent juste a voir que le setting du niveau de verbose fonctionne
logging.info("Info")
logging.warning("Warning")

L'avantage d'argparse est évident pour tout le monde j'espère ! Par contre, bien qu'argparse soit censé être un module standard depuis python2.7, et qu'il soit par défaut présent sur ma ubuntu 12.04, j'ai été obligé de l'installer explicitement sur ma gentoo emerge dev-python/argparse...dommage.

  1. Même si ce mot n'existe pas

Packons (ou pas) avec miasm et elfesteem

Par Oz le - Sécurité
Hack Outil Reverse Engineering code source miasm python scripts

Comme beaucoup le savent à présent MIASM est un framework d'ingénierie inverse écrit en Python par Fabrice Desclaux. Pour ma part j'avais joué un petit peu avec il y a un an, mais j'étais finalement assez rapidement passé à autre chose devant mon incapacité à porter un "packeur" maison de ''pefile'' jusqu'à ''miasm''. Aujourd'hui, je re-tente la même tâche !

Engine - Creative Common by "cbowns" on Flickr

Il y a un an donc j'avais eu des soucis quand j'avais voulu porter un concept simple de ''packeur'' sur le framework miasm. En effet la base de tout ''packeur'' c'est d'ouvrir un fichier à traiter (dans mon cas un fichier PE), lui apporter des modifications, puis le sauvegarder pour obtenir un clone fonctionnel de notre fichier à traiter (clone dont la signature binaire sera pourtant différente). Le problème c'est que, même en n'apportant aucune modification à mon fichier cible, elfesteem semblait incapable de générer un clone fonctionnel. Par exemple le code suivant, qui est censé n'apporter aucune modification à l'exécutable passé en argument, me retournait systématiquement un clone que Windows refusait de démarrer :

import sys
from elfesteem.pe_init import PE

e = PE( open(sys.argv[1]).read() )

open( sys.argv[1]+'_modified.exe', 'wb').write(str(e))

De mémoire j'avais testé sur "winmine.exe", sur "calc.exe", et sur "notepad.exe" : à chaque fois l'exécutable modifié ne fonctionnait plus :-(

Un an après, re-motivé par la super conf de serpi au SSTIC, je réinstalle smiasm sur ma machine1 et je re-tente. Tristesse : le bilan est le même. Les exécutables que j'ouvre puis que je sauvegarde avec elfesteem ne fonctionnent plus (enfin en tout cas "calc.exe", qui est ma cible de test préférée, donne systématiquement des clones "cassés"). Mais cette année, j'ai décidé d'investiguer un petit peu plus ! Retroussons nous les manches et voyons voir ça de plus près. D'abord assurons nous que "calc.exe" et "calc.exe_modified.exe" sont bien différents (et que nous n'avons donc pas à faire à un simple saute d'humeur de windows) : diff calc.exe calc.exe_modified.exe nous confirme que les fichiers sont différents.

Pour y voir de plus près on va regarder ces deux spécimens en hexa (xxd calc.exe > calc.exe.XXD && xxd calc.exe_modified.exe > calc.modified.XXD && diff *.XXD) :

5,14c5,14
< 0000040: 0e1f ba0e 00b4 09cd 21b8 014c cd21 5468  ........!..L.!Th
< 0000050: 6973 2070 726f 6772 616d 2063 616e 6e6f  is program canno
< 0000060: 7420 6265 2072 756e 2069 6e20 444f 5320  t be run in DOS 
< 0000070: 6d6f 6465 2e0d 0d0a 2400 0000 0000 0000  mode....$.......
< 0000080: 8745 1664 c324 7837 c324 7837 c324 7837  .E.d.$x7.$x7.$x7
< 0000090: 3907 3837 c624 7837 1907 6437 c824 7837  9.87.$x7..d7.$x7
< 00000a0: c324 7837 c224 7837 c324 7937 4424 7837  .$x7.$x7.$y7D$x7
< 00000b0: 3907 6137 ce24 7837 5407 3d37 c224 7837  9.a7.$x7T.=7.$x7
< 00000c0: 1907 6537 df24 7837 3907 4537 c224 7837  ..e7.$x79.E7.$x7
< 00000d0: 5269 6368 c324 7837 0000 0000 0000 0000  Rich.$x7........
---
> 0000040: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000050: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000060: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000070: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000080: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00000c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
21c21
< 0000140: 00f0 0100 0004 0000 fcd7 0100 0200 0080  ................
---
> 0000140: 00f0 0100 0004 0000 b16f 0200 0200 0080  .........o......
39,46c39,46
< 0000260: 0ffe 7d3b 3800 0000 0efe 7d3b 4400 0000  ..};8.....};D...
< 0000270: 0efe 7d3b 4f00 0000 0efe 7d3b 5c00 0000  ..};O.....};\\...
< 0000280: 0efe 7d3b 6900 0000 0efe 7d3b 7300 0000  ..};i.....};s...
< 0000290: 0000 0000 0000 0000 5348 454c 4c33 322e  ........SHELL32.
< 00002a0: 646c 6c00 6d73 7663 7274 2e64 6c6c 0041  dll.msvcrt.dll.A
< 00002b0: 4456 4150 4933 322e 646c 6c00 4b45 524e  DVAPI32.dll.KERN
< 00002c0: 454c 3332 2e64 6c6c 0047 4449 3332 2e64  EL32.dll.GDI32.d
< 00002d0: 6c6c 0055 5345 5233 322e 646c 6c00 0000  ll.USER32.dll...
---
> 0000260: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000270: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000280: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 0000290: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00002a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00002b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00002c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
> 00002d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

Voilà donc l'intégralité des changements entre les deux fichiers. Sur 112ko ça fait peu, on devrait pouvoir être capable d'identifier précisément ce qui ne fonctionne plus :)

Le premier bloc de différence se situe entre les octets 0x0000040 et 0x00000d0. La position (en tout début de fichier) et le contenu ("...This program cannot be run in DOS mode...") de ce bloc me font penser qu'il s'agit uniquement du "DOS stub"2. Bref : pas intéressant.

Le second bloc de différence est beaucoup plus petit puisqu'il n'impacte que la ligne de notre dump commençant à l'octet 0x0000140. Sur toute cette ligne on a 3 octets de différence. Si jamais ces octets participent à une indirection quelconque on a peut-être trouvé notre coupable :) ! Après un petit tour dans "Lord PE" je réalise que, malheureusement, ce n'est probablement pas là que se situe le coupable. En effet la valeur du checksum de "calc.exe" est "0001D7FC" et celle de "calc.exe_modified.exe" est de "00026FB1". Cette suite d'octets correspond donc probablement au checksum du fichier contenu dans l'en-tête NT_HEADER. Comme le DOS-stub a été supprimé il est normal que la valeur de checksum soit différente; de plus il me semble qu'un checksum erroné n'empèche pas le lancement de programme simples (pour les drivers c'est une autre histoire, mais pour un soft user-land je ne crois pas que Windows vérifie). Pour avoir la conscience tranquille je modifie quand même la valeur du checksum dans "calc.exe.XXD" puis je reconstruit un binaire (xxd -r calc.exe.XXD > calc.exe.badchecksum.exe) et je peux confirmer que cette copie de calc.exe dont j'ai uniquement modifié le checksum pour en mettre un invalide fonctionne :)

Nous arrivons ainsi au troisième bloc, qui est devenu notre suspect numéro 1. En plus, les quelques chaines de caractères qui ont été remplacées par des octets nuls ont bien la tête d'informations provenant d'une table d'importation ("msvcrt.dll" , "KERNEL3.dll", etc.) ce qui pourrait expliquer le non-fonctionnement du programme si ces informations ont été altérées. Malheureusemnt "Lord PE" me donne des tables d'importations identiques entre les deux fichiers "calc.exe" et "calc.exe_modified.exe", et je ne trouve pas d'outil sympa pour disséquer simplement un PE :-( ...Qu'à celà ne tienne : on va en pondre un maison, à la porc bien entendu ! L'idée est simple : visualiser les structures du fichier PE simplement afin d'identifier à quelle structure appartient la zone d'octets modifiés.

Pour réaliser cet outil, quick&dirty rappelons-le, je vais faire appel à une poignée de fidèles compagnons :

  • VIM/gedit : parce que ce sont d'excellents éditeurs de code :)
  • C : parce que pour les manipulation "bas niveau" on n'a pas encore fait mieux que le bon vieux C.
  • Python : parce que pour les prototypages rapide c'est le must.
  • Python Imaging Library (PIL) : parce qu'on veut "visualiser les structures du fichier PE" et que c'est la meilleure librairie de manipulation d'image en python que je connaisse. Enfin, en guise d'aide mémoire, on utilisera aussi les excellents tutos d'Iczelions sur les entrailles du format PE et quelques URL de références de chez Krosoft. Au final j'ai obtenu en un aprem de jeu :

    • un prog en C qui analyse un fichier PE et dump ses caractéristiques sur la sortie standard (en prime j'ai rajouté un .h contenant les définitions des structures Windows, bien que j'aurai pu utiliser winnt.h qui doit se trouver quelque part sur ma machine étant donné que j'ai une gentoo avec de quoi compiler pour des centaines de systèmes exotiques, mais j'avais la flemme de le chercher :-D)
    • un prog en python qui lance le prog en C sur un exécutable passé en argument, parse la sortie obtenue, et génère deux jolies images permettant de visualiser quelle partie du fichier appartient à quelle structure.

Toutes les sources sont en pièce-jointe de ce billet, donc n'hésitez pas à jouez vous aussi (mais n'oubliez pas : j'ai codé ça comme un goret donc si ça ne marche pas chez vous "c'est normal", et si vous le lancez sur des PE de plusieurs Mo il est probable que votre RAM soit intégralement vampirisée, vous êtes prévenus)(NDLR : utilisez plutôt la v4 qui génère directement un svg et qui est donc infiniment plus performante).

La première image est une représentation à l'échelle des différentes structures du fichier PE sur disque (pas tel qu'il sera mappé en mémoire donc). La seconde image n'est qu'une représentation "compressée" de l'image précédente où j'ai inséré des séries de "petits points" pour remplacer visuellement les énormes applats de couleurs unis représentant des zones de fichier où "rien de spécial ne se passe" et qui rendent le premier type d'image carrément gigantesque (1200x14688 pour représenter "calc.exe" dans mon environnement de test ;) ). Voilà comment on s'en sert :

$ gcc -o a.out oz_pedissector.c
$ python oz_pedissector3.py calc.exe
INFO:root:PE zone discovered [ZONE : IMAGE_DOS_HEADER   En-tete DOS 0   64]
INFO:root:PE zone discovered [ZONE : IMAGE_NT_HEADERS   En-tete NT  240 488]
INFO:root:PE zone discovered [ZONE : SECTION_HEADERS[0] En tete de section ".text"  488 528]
INFO:root:PE zone discovered [ZONE : SECTION[0] Contenu de section ".text"  1024    76800]
(...)
INFO:root:Compression second pass 98%
INFO:root:Compression second pass 99%
INFO:root:Compression second pass finished.

Nous voilà à présent avec deux fichiers ".png", l'un étant la représentation à l'échelle, l'autre étant la représentation compressée. Voyons voir ce que donne l'image "compressée" générée automatiquement à partir du "calc.exe" de mon environnement de test (je vous invite à l'avoir sous les yeux en taille normale lorsque vous lirez le paragraphe suivant) :

Oz PE dissector (Compressed Example file) - Creative Common CC-BY-SA by Ozwald

En la regardant de haut en bas on retrouve bien :

  • L'en-tête MS-DOS commençant à l'adresse 0x0 et allant jusqu'à 0x40
  • Une zone noire (représentation graphique de "on ne sait pas ce que c'est") juste en dessous. C'est le DOS Stub.
  • l'en-tête NT commençant à 0xF0 et allant jusqu'à 0x1E8 (on se rappelle à ce moment là que le second bloc de différence était situé aux alentours de l'adresse 0x140 et que nous avions supposé qu'il s'agissait du checksum contenu dans l'en-tête NT, nous avons à présent confirmation que cette adresse est bien dans l'en-tête NT ce qui conforte notre hypothèse s'il en était besoin)
  • Les trois en-têtes de sections qui suivent l'en-tête NT
  • Une seconde zone noir juste en dessous...on en reparlera.
  • La première section (".text") qui va de 0x400 à 0x12C0. On notera (sur la droite de l'image) que cette section contient les zones mémoires suivantes appartenant au DATA_DIRECTORY : Import Address Table, Debug, Import Symbols.
  • La seconde section (".data") qui ne contient rien de spécial.
  • La troisième section (".rsrc") qui contient, on s'en doutai, la zone spéciale "Resources" du DATA_DIRECTORY.

Bref : tout va bien :) Tout va tellement bien d'ailleurs que je tombe d'accord avec elfesteem : il ne devrait rien y avoir d'important entre l'adresse 0x260 et 0x4003...Le mystère reste donc entier4.

Edit du lundi 9 Juillet 2012, 14h53 : je remplace les 3 fichiers sources joints au billet par une archive unique contenant le tout, ça évitera les 403 imposés par mon hébergeurs sur les fichiers d'extension ".py" -_-

Edit du mardi 10 Juillet 2012, 17h30 : après vérification sur d'autres versions de "calc.exe" (provenant de diverses versions de WinXP) on retrouve toujours ce bloc non nul entre la fin des en-tête de section et le début de la première section... Etrange... Par contre je viens seulement maintenant de vérifier un exécutable qui serait plus typiquement ce que j'aurai besoin de packer5, à savoir gsecdump, et il ne contient bien que des octets nuls entre la fin de ses en-tête de section et le début de sa première section. Donc à priori il devrait pouvoir être ouvert/enregistré par elfesteem sans être "cassé". Je teste ce soir :) ! Accessoirement je rajoute en PJ la version 4 du script dégueu programme permettant la visualisation des structures de fichiers PE. Il est maintenant infiniment moins gourmand en mémoire (forcément: il génère du svg directement compressé au lieu de générer un bitmap "taille réelle" puis de le compresser...); je l'ai testé sans douleur sur un binaire de 13Mo (en lui demandant cependant de n'afficher que les structures de plus de 40 octets).

Edit du mardi 10 Juillet 2012, 20h30 : A force d'avoir l'évidence sous les yeux (à savoir que je ne vois aucune raison pour lesquelles elfesteem ne pourrait pas légitimement écrire des bytes nuls sur ces zones du fichier) j'ai re-testé l'ouverture/sauvegarde simple mais sur plusieurs binaires ne provenant pas de Microsoft cette fois (à savoir : gsecdump-v2b5.exe, ftpserv.exe, notepad++.exe, 7zFM.exe, python.exe) et ils ont tous fonctionné à merveille après leur passage dans elfesteem. La conclusion du premier chapitre de ce mystère s'écrit donc d'elle même : elfesteem fonctionne très bien, c'est le compilateur utilisé par microsoft qui produit des résultats "exotiques" (et je suis un gros c*uillon de ne pas m'en être rendu compte il y a un an -_- ...).

Edit du mercredi 11 Juillet 2012 : Serpi a trouvé la solution (lisez les commentaires du billet pour les détails). Le problème venait de bound imports..


Gorgonite le 2012/07/09 10:53

Allez, je tente ma chance :

open(sys.argv[1],'rb')

au lieu de

open(sys.argv[1])

nb: je ne peux pas tester au boulot ^^

Ozwald le 2012/07/09 12:02

La vache tu es rapide à répondre :-D !
Alors l'idée était intéressante mais je viens de tester et, malheureusement, j'obtiens le même résultats avec et sans le 'rb' :

$ md5sum  calc.exe\*
829e4805b0e12b383ee09abdc9e2dc3c  calc.exe
bab1aecd69fa7e93d03da67b8601faf4  calc.exe_modified.exe
bab1aecd69fa7e93d03da67b8601faf4  calc.exe_gorgonite.exe

Décidément plus j'y réfléchi plus je me dit que ça doit avoir à faire avec la table d'importation. Vivement que j'ai un peu de temps pour me re-pencher sur le souci :) !

Baboon le 2012/07/09 13:48

File les binaires ! (les 2 calcs)
J'ai jamais réussit à installer miasm chez moi et le SDK de win veux même plus s'installer non plus...)
(vais regarder ton précédent post tient)

serpilliere le 2012/07/10 15:38

Yop!
C'est peut être normal. Sous windows 7:

  • tu copies calc.exe de c:\windows\system32
  • tu la colles sur le bureau
  • tu lances celle sur le bureau
  • surprise => segfault.

il a un problème pour retrouver ses petits dans les ressource de LANG FR s'il n'est pas lancé depuis c:\\windows\\system32

Après si tu es sous XP, ca devrait fonctionner :/

Ozwald le 2012/07/10 20:51

Merci à tous pour vos réactions !

@baboon> Tu as les deux binaires dans tes mails (si l'adresse que j'ai utilisé est la bonne).

@serpi> Je testais sous WinXP :-/ En fait (je répète un peu mon dernier edit, mais s'pas grave) je ne vois toujours aucune raison pour lesquelles les binaires générés ne marchent pas. Du coup j'ai testé avec pas mal de PE non-Microsoft et ils fonctionnent tous à merveille. On peut donc plus ou moins dire que mon problème est résolu :) Mais niveau curiosité intellectuelle le mystère reste quand même entier : toutes les versions de "calc.exe" ou de "winmine.exe" sur lesquels j'ai pu mettre la main (WinXP, et 7), avaient cette caractéristique étrange d'embarquer, entre la fin des headers de section et le début de la première section, une partie binaire non-nulle qui semble essentielle au fonctionnement de l'appli (et qui, entre autre, répète la liste ASCII des DLL utilisées dans la table d'importation). Bref on peut renommer le mystère de "pourquoi elfesteem ne parvient pas à ouvrir/sauvegarder mes binaires de tests ?" en "pourquoi le compilateur/linkeur de microsoft fait des choses étranges ?" ^_^

serpilliere le 2012/07/11 08:53

Ok. c'est les bound imports.
En fait de base, elfesteem ne parse pas (encore) les bound import, du coup quand il rebuild, il les met à 0, par contre, il laisse l'entrée dans l'import directory.
résultat: quand tu lances, certaines fonctions ne sont pas fixée dans l'iat.

petit fix rapide: il faut transformer ton code en :

import sys
from elfesteem.pe_init import PE, pe


fname = sys.argv[1]
e = PE(open(fname).read())
e.NThdr.optentries[pe.DIRECTORY_ENTRY_BOUND_IMPORT].rva = 0
e.NThdr.optentries[pe.DIRECTORY_ENTRY_BOUND_IMPORT].size = 0
open(fname+".mod", "w").write(str(e))

bon ok: je vais fixer le tripou soit pour qu'il les parse, soit qu'il supprime l'entrée dans le header.
note: je n'ai pas remarqué au premier coup d'oeil, parce que *tout* mes scripts d'unpacking ou autre ont ce fix... oui, j'avoue c'est *painfull*.

du coup corolaire: Avec miasm, on apprend plein de truc dans la bonne humeur... Désolé pour le temps perdu!

serpilliere le 2012/07/11 09:09

Au passage, pour se marrer, la fameuse ligne de code est dans la doc (les slides du repository) de miasm: slide 9/105. (comme quoi je ne suis pas totalement un escroc :p)

Concernant le packer, j'en ai également un basé sur miasm développé pour les pentest, et j'avoue il y a encore 2/3 "blagues" du même style, du coup tu me donnes presque envie de le releaser (ce qui diminuera peut être son efficacité). Mais l'exercice reste intéressant.
Après j'avais une amie juriste qui m'avait glissé à l'oreille que la publication de code de ce genre reste illégale. Dieu ait pitié de l'âme des juristes.

Ozwald le 2012/07/11 11:56

Bound Import, nice catch !! Je ne maitrise pas du tout cette structure là des PE...je vais y jeter un oeil du coup (comme quoi tu as raison : c'est un exercice intéressant et instructif).

Pour la petite histoire : wine, lui, réussi à lancer les versions modifiées de "calc.exe" dont les bound imports sont "pourris" :-)

"Désolé pour le temps perdu!" <= c'est une blague ^_^ ? Tu ponds un framework super, tu le mets à dispo en open source, et tu t'excuse qu'il ne soit pas parfait ? C'est plutôt à moi de te payer une bière si on se croise un jour pour te remercier de l'opportunité d'en apprendre plus sur les bound imports :-p

Pour ce qui est de releaser un packeur il y a en effet un problème légal (une sombre histoire de "motif légitime" en rapport avec l'article 323-3-1 du code pénal si j'ai tout suivi...http://www.legifrance.gouv.fr/affic...).En tout cas c'est pour ça que je n'ai pas non plus releasé le mien :-/

  1. L'installation n'est d'ailleurs toujours pas plus facile, je vous recommande la lecture de mon billet de l'époque, ça peut éventuellement aider
  2. Le DOS stub est,en résumé, un programme MSDOS censé être lancé à la place du programme PE lorsqu'il est exécuté sous DOS. Le but de ce mini programme DOS est principalement d'avertir l'utilisateur que le programme ne peut pas fonctionner sous DOS.C'est une zone totalement facultative de nos jours.
  3. Ce genre de zone "poubelle" pouvant apparaitre naturellement dans le fichier suite à des jeux de padding puisque les structures PE imposent des tailles multiples de certaines constantes renseignées dans les en-tête
  4. En attendant un autre après-midi de libre (où je pourrait me re-pencher sur le problème), ou que quelqu'un poste un commentaire expliquant ce bien étrange phénomène
  5. Pour rappel : je suis pentesteur pro, si je pack des binaires c'est pour mon taff et pour sensibiliser mes clients au fait qu'un AV ce n'est pas l'outil miracle qui les protègera de tout et n'importe quoi; ce n'est pas pour faire du pr0n, monter un botnet, ou pire : boire dans votre YOP.

Page 1 / 3 »