Après réflexion, je me suis souvenu que certains fichiers pouvaient rester
bloqués dans les limbes.
En effet, il faut savoir que, sous Linux, quand un fichier est supprimé (avec
rm par exemple), il n’est pas réellement supprimé tant qu’au moins un
processus utilise ledit fichier. Par conséquent, même si le fichier n’est plus
affiché par ls ou find, il occupe toujours de l’espace sur le disque.
Pour lister ces fichiers, on ne peut pas utiliser les commandes habituelles
telles que ls ou find, mais on peut utiliser lsof qui est une
commande qui liste les fichiers ouverts (lsof => list open files).
La sortie de lsof est très verbeuse, heureusement en lisant sa page de manuel
(man 8 lsof) on y trouve l’option L qui peut être suivi d’un nombre.
Lorsque L est suivi d’un nombre N, lsof va uniquement lister les
fichiers qui sont référencé un nombre de fois strictement inférieur à N.
Dans notre cas, comme on veut lister les fichiers supprimés (qui ne sont donc
plus référencés) il faut utiliser L1 pour lister les fichier ayant 0
référence.
En combinant lsof +L1 avec la commande sort on peut trier par taille
pour voir quels sont les fichiers occupant le plus de place.
La commande finale est donc lsof -s +L1 | sort -nk7 ce qui se traduit
par : liste (lsof) la taille (-s) de tout les fichiers supprimés et
encore ouvert (+L1) et trie (sort) cette liste de manière numérique
(-n) sur le champs 7 (-k7, car c’est le septième champs qui est le
champ de la taille).
Cette commande a permis de découvrir que l’espace disque était utilisé par des
fichiers temporaires de
Terminator.
Terminator et libVTE
Reste à savoir pourquoi Terminator utilise autant d’espace disque.
Tout d’abord il faut savoir que le Terminator en cause ici était configuré pour
conserver toutes les sorties des terminaux, sans limite (option Inifinite
scrollback). Le problème c’est que les buffers des terminaux sont stockés
sur disques et donc que plus les terminaux sont utilisés longtemps et plus il
y’a de choses affichées dedans, plus l’espace disque occupé va augmenter.
Ce comportement ne vient pas de Terminator lui-même, mais de la
libVTE qui est une bibliothèque utilisée pour
implémenter des émulateurs de terminaux. Ce bug touche donc tout les terminaux
basés sur libVTE (Terminator, Gnome-Terminal, xfce4-terminal, guake, …).
Ce comportement existe depuis 2009, il est connu et ne sera probablement pas
corrigé, alors même que cela peut poser problème (je vous conseille de lire
ce rapport de bug
qui explique bien la situation)…
Conclusion
Je pense que je vais continuer d’utiliser
urxvt :D, qui est l’un des rares
terminaux à bien gérer l’espace insécable fine et qui n’est pas basé sur libVTE.
Cette petite mésaventure m’aura au moins fait découvrir un aspect fort utile
de lsof.
Depuis la version 7.01 (sortie le 2009/10/06), GDB embarque un interpréteur
Python cela qui permet d’utiliser Python comme langage de scripting pour étendre
les fonctionnalités de GDB.
Dans cet article je vais aborder la création de pretty-printer en Python.
Le problème
Comme un exemple vaut mieux qu’un long discours, je vais montrer ici un cas
pratique : l’affichage d’adresses IP.
Les systèmes POSIX représentent les adresses via deux structures:
in_addr pour les IPv4 : une structure qui doit contenir au minimum un champ
s_addr de type in_addr_t (qui est équivalent à uint32_t).
in6_addr pour les IPv6 : une structure qui doit contenir au minimum un champ
s6_addr de type uint8_t[16].
Ces informations, parmi d’autres, sont disponibles
ici.
De par la définition de ces structures, si on veut les afficher dans GDB on
n’obtient quelque chose qui n’est pas très lisible pour un humain.
Le moins que l’on puisse dire c’est que ce n’est pas super human-friendly
($1 étant l’IPv4 et $2 l’IPv6).
Les pretty-printers
Nous allons créer un module python my_pp. Dans le répertoire my_pp, nous
aurons deux fichiers :
netinet.py qui contiendra le code des pretty-printers.
__init__.py qui se chargera d’enregistrer nos pretty-printers auprès
de GDB.
Commençons avec le premier fichier (j’ai omis les docstrings pour raccourcir
le code).
netinet.py
123456789101112131415161718192021
fromstructimportpackfromsocketimportinet_ntop,AF_INET,AF_INET6fromgdbimportlookup_typeclassipv4Printer(object):def__init__(self,val):self.addr=pack('I',int(val['s_addr']))defto_string(self):returninet_ntop(AF_INET,self.addr)classipv6Printer(object):def__init__(self,val):# IPv6 addresses have a size of 128 bits (== 16 octets).N=16addr=val.cast(lookup_type("uint8_t").array(N))self.addr=pack('B'*N,*[int(addr[i])foriinrange(N)])defto_string(self):returninet_ntop(AF_INET6,self.addr)
Les adresses IP étant stockées sous forme binaire, on importe le module struct
pour pouvoir les manipuler. Le module socket va nous servir à les convertir en
chaîne de caractères2. Enfin, on importe le module gdb.
Lorsque GDB va instancier un objet ipv4Printer, il va lui passer en argument
une structure de type in_addr. Comme dit précédemment, cette structure
contient un champ s_addr qui est un uint32_t. Notre méthode d’initialisation
se contente donc d’extraire ce champ dans le membre addr de notre objet.
Ensuite, la méthode to_string est appelée par GDB à chaque fois qu’il doit
afficher un objet de type in_addr. Cette méthode renvoie la chaîne de
caractère représentant l’adresse IP contenue dans addr.
Pretty-printer pour l’IPv6
123456789
classipv6Printer(object):def__init__(self,val):# IPv6 addresses have a size of 128 bits (== 16 octets).N=16addr=val.cast(lookup_type("uint8_t").array(N))self.addr=pack('B'*N,*[int(addr[i])foriinrange(N)])defto_string(self):returninet_ntop(AF_INET6,self.addr)
En théorie; la version IPv6 devrait être aussi simple que la version IPv4. En
théorie… En pratique c’est malheureusement plus compliqué.
En effet, si POSIX requiert que la structure in6_addr_t possède un champ nommé
s6_addr le fait est que, la plupart du temps, ce membre n’existe pas vraiment:
c’est un symbole de préprocesseur. En tant que tel, il n’est pas accessible dans
GDB (sauf si on utilise certaines options de compilation bien spécifiques telle
que -g3 et -gdwarf-2 par exemple). Pis encore, Windows ne définit pas ce
membre du tout (Windows ne cherche pas vraiment à être conforme POSIX).
La solution que j’ai trouvée est de traiter la structure in6_addr comme un
tableau de 16 octets. Cela fonctionne et me semble relativement portable étant
donné que la structure in6_addr est définie comme une union dont l’un des
champs est effectivement un uint8_t[16] au moins sur les systèmes
d’exploitation suivant :
La méthode __init__ de notre objet va donc caster la valeur puis la stocker
dans l’attribut addr. Au niveau de la méthode to_string, c’est quasiment la
même chose que pour ipv4Printer (on remplace seulement AF_INET par AF_INET6).
Enfin, l’enregistrement de nos deux classes se fait dans le fichier
__init__.py.
On commence par importer le module gdb.printing, puis nos pretty-printers.
L’enregistrement se fait via un objet RegexpCollectionPrettyPrinter (via
lequel on peut donner un nom à notre groupe de pretty-printers) dans lequel nous
ajoutons nos pretty-printers. Lors de l’ajout, on donne un nom, une expression
rationnelle qui va définir les noms des types que nous pouvons afficher, puis la
classe du pretty-printer.
Maintenant que le code est fait, voyons comment utiliser tout ça.
La mise en œuvre
La mise en œuvre est très simple, elle peut se faire via le fichier .gdbinit.
Il suffit d’y ajouter ces lignes :
12345678910
# Python
python
from sys import path
from gdb.printing import register_pretty_printer
path.insert(0, '/chemin/vers/répertoire/contenant/my_pp')
import my_pp
register_pretty_printer(gdb.current_objfile(), my_pp.netinet_pp())
Je pense que ça se passe de commentaire.
Le résultat
Et maintenant, si on lance GDB sur notre exemple on obtient :
12345678
% gdb -q ./example --command=command.gdb 2> /dev/null
Reading symbols from ./example...done.
Breakpoint 1 at 0x8065581: file example.c, line 17.
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".
$1 = 82.66.107.250
$2 = 2a01:e35:2426:bfa0:215:ff:fe42:7fd3
[Inferior 1 (process 2424) exited normally]
Ce qui est, il faut l’admettre, bien plus lisible.
Pour conclure, je mentionnerai que la commande info pretty-printer permet
d’afficher la liste des pretty-printers actuellement chargé dans GDB. Il est
également possible d’utiliser l’affichage « brut » de GDB, sans passer par un
pretty-printer (même s’il en existe un pour le type) en utilisant le
modificateur /r de la commande print (par exemple print /r toto).
Voilà, ça sera tout pour cette introduction aux pretty-printers. La
documentation officielle est
ici
pour ceux qui veulent approfondir.
je vous conseille d’utiliser au moins GDB 7.8, les versions antérieures ayant un bogue avec les types définis via typedef.↩
depuis Python 3.3, on utilise plutôt le module ipaddress↩
Premièrement, qu’est-ce que j’entends par « fonction de comparaison » ?
Je parle des fonctions qui prennent deux arguments en entrée et qui renvoie :
un nombre positif si le premier argument est strictement supérieur au
second.
0 si les deux arguments sont égaux.
un nombre négatif si le premier argument est strictement inférieur au
second.
Ce genre de fonction est utilisée pour ordonner des éléments (ordre total), et
elles sont donc naturellement utilisée par certaines fonctions de tri telles que
qsort.
Maintenant, pourquoi est-ce que je parle d’une erreur répandue ?
Et bien parce qu’en tapant « qsort » ou « qsort example » dans un moteur de
recherche, je tombe sur ça (il y a aussi des versions correctes, je vous
rassure) :
L’idée derrière cette fonction est que comme on doit renvoyer un nombre positif
si a > b, négatif is a < b et 0 si a = b alors autant renvoyer la
différence.
En théorie, ça fonctionne. En pratique, les nombres représentables dans un int
sont bornés et il y a donc risque d’overflow lorsque l’on approche les valeurs
limites. Et en effet, l’opération a - b peut produire un résultat non
représentable dans un int.
À toutes fins utiles, je rappelle que les overflow d’entiers signés en C sont
un comportement non-défini. Cela vient en partie du fait que le standard du C
n’impose rien sur la représentation des entiers signés (signe et magnitude,
complément à un ou complément à deux) et ne veut donc pas dicter le comportement
attendu pour ce genre de situation.
Solution
La solution est très simple. Étant donné que l’on souhaite faire une fonction de
comparaison il suffit d’utiliser les opérateurs de comparaison afin d’éviter
tout problème d’overflow :
Cette version se base sur le fait que les opérateurs > et < renvoie 0 ou 1,
ce qui est garanti par le standard (Cf. ISO/IEC 9899:TC3, 6.5.8 Relational
operators §6, page 86) :
[...] Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int. [...]
Cette version est donc absolument portable et devrait même fonctionner sur un
DS9K :P
J’ai été confronté à ce bogue le 2013/08/25, je n’avais donc pas encore
découvert le comportement indéfini lié à offsetof (que j’ai découvert lors
de la rédaction de
l’article précédent)
ce qui explique pourquoi je ne le mentionne pas ici.
Le 2013/08/25, j’ai été confronté à un bogue assez surprenant au premier abord.
Comme cela faisait longtemps que je n’étais pas tombé sur un bogue de ce genre,
j’ai eu envie de partager le raisonnement que j’ai suivi pour en venir à
bout (au cas où cela puisse servir à d’autres) sur le forum
ubuntu-fr.
Ce bogue fut aussi, d’une certaine façon, ce qui a conduit à l’ouverture de ce
blog.
Le contexte
J’étais en train d’implémenter une liste linéaire simplement chaînée. Une liste
générique, mais sans utiliser void* comme on le fait traditionnellement.
Au lieu de cela, j’avais décidé de m’inspirer d’une méthode assez connue qui est
utilisée dans le noyau Linux (utilisation d’une structure de données intrusive).
Le morceau de code qui suit permet d’avoir un aperçu de l’interface de la liste.
Il s’agit en fait d’une version minimale du véritable programme d’exemple auquel
j’ai retiré la gestion des erreurs (malloc) et la libération de la mémoire
allouée car ce n’est pas le sujet ici (ne vous inquiétez pas, dans le programme
d’origine tout cela est présent).
#include <stdio.h>#include <stdlib.h>#include "slist.h"typedefstruct{unsignedto;slist_nodenode;unsignedfrom;}pair_list;intmain(void){slist_listlist;pair_list*elt;unsignedi;/* Initialize the list. */slist_init(&list);/* Populate the list. */for(i=0;i<2;++i){elt=malloc(sizeof*elt);elt->from=i;elt->to=i+1;slist_add(&list,&(elt->node));}/* Iteration with `slist_foreach_elt`. */slist_foreach_elt(&list,elt,pair_list,node)printf("from = %u | to = %u\n",elt->from,elt->to);return0;}
La découverte
Voyons maintenant ce que l’on obtient en sortie en l’exécutant.
Compilation avec gcc -O0
12
from = 1 | to = 2
from = 0 | to = 1
Compilation avec clang -O0
12
from = 1 | to = 2
from = 0 | to = 1
Compilation avec gcc -O2
12
from = 1 | to = 2
from = 0 | to = 1
Compilation avec clang -O2
123
from = 1 | to = 2
from = 0 | to = 1
zsh: segmentation fault (core dumped)
Tiens, tiens. Comme c’est intéressant : un bogue qui n’apparaît que lorsque l’on
active les optimisations, et sur un seul compilateur en plus !
Quand on a une différence de comportement entre deux compilateurs, il y a deux
solutions possibles :
l’un des deux compilateurs a un bogue (peu probable, mais cela arrive).
notre code contient :
un comportement non défini (undefined behavior, que je vais abréger par
UB par la suite).
OU un comportement non spécifié (unspecified behavior).
OU un comportement dépendant de l’implémentation
(implementation-specific behavior).
La différence entre les trois étant parfois oubliée, je vais faire un petit
rappel ici. Tout d’abord, il faut savoir que le standard décrit une machine
abstraite C (C abstract machine) qui peut être vu comme un interpréteur C.
un comportement dépendant de l’implémentation (comme la taille d'un int
par exemple) peut être vu comme un paramètre de la machine abstraite. Le
standard peut proposer plusieurs comportements possibles, auquel cas
l’implémentation doit en choisir un parmi ceux proposés. Si le standard ne
spécifie rien, alors l’implémentation est libre de choisir son comportement.
Dans tous les cas, l’implémentation doit documenter ses choix (on trouve ceux
de GCC ici).
un comportement non spécifié (comme l’ordre d’évaluation des arguments d’une
fonction) peut être vu comme un comportement non-déterministe de la machine
abstraite. Comme pour un comportement dépendant de l’implémentation, le
standard peut proposer plusieurs possibilités et l’implémentation doit faire
un choix parmi eux. Sinon, elle est libre de choisir le comportement
qu’elle souhaite. En revanche, ces comportements ne sont pas forcément
documentés par l’implémentation.
un comportement non défini (comme déréférencer un pointeur NULL) est un
comportement pour lequel le standard n’offre aucune garantie. Un compilateur
qui rencontre un UB est libre de faire ce qu’il veut, ABSOLUMENT TOUT
ce qu’il veut. Ce qui inclut (entre autres) :
produire une erreur de compilation
ignorer le problème
supprimer le code qui contient l’UB
ignorer le standard (oui, un seul UB à un endroit rend TOUT le code
indéfini)
générer un programme qui va crasher à l’exécution
générer un programme qui va produire de mauvais résultats
générer un programme qui va fonctionner comme prévu (et oui, cela arrive)
générer un programme qui va formater votre disque dur
Ceci dit, les UB ont aussi leurs bons côtés : c’est en partie grâce à leur
existence que les compilateurs C peuvent faire de nombreuses optimisations. À ce
sujet, je vous conseille cet excellent article en trois parties écrit par
Chris Lattner (qui sait donc très
bien de quoi il parle) :
mon bogue apparaît seulement avec les optimisations activées (avec clang, il
est présent à partir de O1 et avec gcc le programme s’exécute correctement
quel que soit le niveau d’optimisation).
mon code joue avec des pointeurs, des adresses, des structures et des macros.
Je suis donc directement partie sur la solution 2.
Le bogue
J’ai commencé par utiliser Memcheck sur la version compilé et optimisé par clang
(entre temps, j’ai pris soin de recompiler avec le flag -g en plus de -O2
pour avoir les informations de déboguage).
Voilà le résultat :
Sortie de Memcheck
123
==7949== Invalid read of size 4
==7949== at 0x4006A0: main (min_bug.c:34)
==7949== Address 0xfffffffffffffff8 is not stack'd, malloc'd or (recently) free'd
Petite précision utile : la ligne 34 c’est le printf dans la boucle.
Donc a priori, la boucle fait trop d’itérations et essaye d’afficher des
éléments en dehors de la liste. Étrange, sachant que le même code sans
optimisations est tout à fait correct (Memcheck ne rapporte rien d’anormal).
Donc une boucle tout à fait correcte, deviens boguée après optimisations. Hum…
Suite à cela, j’ai tenté de passer par gdb. En vain… La variable d’intérêt,
elt, était optimized out (même en O1, et comme en O0 le bogue ne se
manifeste pas…).
Du coup, j’ai ajouté un printf pour afficherelt et elt->node (ce sont
les variables utilisées dans la condition d’arrêt du foreach) à chaque
itération et j’ai pu constater que quand elt->node atteint la valeur
nécessaire à l’arrêt de la boucle, et bien cette dernière ne s’arrête pas.
Bien, ma condition semble avoir disparue, c’est très ennuyeux ça. Je dois le
vérifier. Et pour cela, il n’y a qu’une seule façon fiable : regarder le code
assembleur généré.
En avant donc. Jetons d’abord un coup d’œil au code produit par gcc (je commence
par celui là, car je sais que même optimisé ma boucle est toujours correcte).
Sortie de gcc -g -O1 -S (code de la boucle uniquement)
Et là : BAM !!!
En plein dans le mille.
La dernière instruction de la boucle est un saut inconditionnel en début de
boucle. Pas de cmp ou test. Mais un bon gros jmp tout ce
qu’il y a de plus inconditionnel. La différence saute au yeux !
C’est donc une belle boucle infinie, ce qui explique que je continue à boucler
même après avoir rencontré ma condition d’arrêt (et donc cela explique également
le fait que j’aille lire des adresses pourries qui me font faire une jolie
Segmentation Fault).
L’explication
Maintenant, on est sûr que le problème vient de la boucle, et donc de
slist_foreach_elt. Regardons donc ça de plus près :
Bon, ça peut faire peur de voir ça comme ça, à froid et sans explication :D
Mais en réalité c’est très simple, et c’est le cœur même de l’astuce qui permet
d’avoir une liste générique sans passer par du void*.
Cela dit, je ne vais pas m’étendre sur le sujet du pourquoi du comment ça
fonctionne (voire
l’article précédent
pour cela).
Donc sans plus d’explications, je vous montre la ligne fautive (qui est belle
est bien dans le foreach) :
&(curr->fieldname) != NULL; \
Ça peut sembler bizarre comme test, mais en fait ça tient la route (enfin
presque, à un détail près et c’est bien pour cela que ça plante)
Pour information, voilà la version que l’on trouve dans le
noyau Linux :
&pos->member != (head); \
C’est presque exactement le même code. À un détail près.
Détail qui vient du fait que la version Linux est une liste circulaire
doublement chaînée. Et le point crucial ici est : circulaire.
Car grace à cette propriété, la condition d’arrêt est un test contre la tête de
la liste, pas contre NULL.
Différence minime ? C’est ce que je pensais. Mais pas du tout, c’est une énorme
différence : la différence entre un code correct et un UB.
Pas à pas
Lorsque je suis sur le dernier nœud (dont le pointeur next vaut NULL), je
vais exécuter cette ligne (la partie incrémentation du foreach) :
offsetof renvoie, comme son nom l’indique, l’offset (en byte) d’un champ
dans une structure.
Ici, je veux l’offset de mon nœud dans la structure. Ça me retourne donc
8 (en effet, dans la structure pair_list il y a un unsigned avant
ce champ, et les unsigned sur ma machine font 4 bytes et il y a 4
bytes de padding pour aligner le champ suivant).
NULL étant défini, au niveau du code source (ce n’est pas toujours vrai après
compilation), comme étant 0 cela donne donc : 0 - 8.
NULL étant un pointeur et les pointeurs étant non signés et sur 64 bits (sur
ma machine), on obtient l’adresse suivante : 0xfffffffffffffff8
Tiens, c’est l’adresse qui était apparue dans Valgrind ça ;)
Donc après exécution de cette partie « incrémentation » de la boucle for,
on retourne au début de la boucle et on va tester la condition :
&(curr->fieldname) != NULL; \
Ce qui donne dans mon cas :
&(elt->node) != NULL; \
curr vaut 0xfffffffffffffff8, l’offset du champ auquel je souhaite
accéder est 8. Cela donne donc 0 quand je les additionne. C’est bien égal à
NULL, ma boucle s’arrête et c’est parfait.
Oui… Mais non !
Car mon implémentation contient un UB et donc le compilateur peut produire
un autre code.
Du point de vue de la norme
Voici quelques extraits choisis de la norme du C99 :
6.3.2.3 Pointers […] 3 An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function. […]
Et :
6.5.6 Additive operators […] 7 For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
8 When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated. […]
Réfléchissons un peu. Qu’est-ce que je fais dans cette condition :
&(elt->node) != NULL; \
Je compare l’adresse d’un champ de ma structure (donc l’adresse d’un objet) avec
NULL (qui ne peut pas être l’adresse d’un objet, cf. §6.3.2.3/3), partant
de là le compilateur sait que le test ne renverra jamais faux et il peut donc le
supprimer.
De manière générale, toute opération arithmétique avec un pointeur NULL
débouche sur un UB. En effet, la condition 6.5.6/8 sera toujours violé (vu que
le §6.3.2.3/3 garanti que NULL est différent de tout sauf de lui-même, le
résultat de l’opération ne pourra jamais pointer sur le même objet que NULL
(vu que par définition il ne pointe sur rien)).
Même faire NULL - NULL c’est un UB. C’est presque le même principe que
précédemment, sauf que c’est le §6.5.6/9 au lieu de §6.5.6/8 qui s’applique (je
laisse les curieux consulter la norme).
Pour terminer sur une petite remarque,
la norme du C++ est un peu plus défini à ce
niveau-là car elle autorise deux opérations arithmétiques sur les pointeurs
nuls :
NULL + 0 ou NULL - 0 renvoie NULL
NULL - NULL renvoie 0
Pour citer la norme :
5.7 Additive operators […] 7 If the value 0 is added to or subtracted from a pointer value, the result compares equal to the original pointer value. If two pointers point to the same object or both point one past the end of the same array or both are null, and the two pointers are subtracted, the result compares equal to the value 0 converted to the type std::ptrdiff_t. […]
Si vous voulez en savoir plus à propos de pourquoi C++ supporte cela, je vous
conseille la lecture de cet
article.
La solution
Comme le problème vient du fait d’appeler slist_elt avec NULL il suffit de
reformuler la boucle for pour éviter ce cas de figure :
implémenter une liste circulaire (comme le noyau Linux), du coup on testera
contre l’adresse de la tête.
créer un nœud global dont l’adresse servira de valeur nulle, on fera donc la
comparaison contre ce nœud au lieu de NULL.
Le mot de la fin
Tester son code avec plusieurs compilateurs, c’est très utile.
Le diable se cache dans les détails.
Rien n’est magique, tout est logique (même si pour remonter le fil, il faut
parfois des connaissances en standard du C, optimisations faites par les
compilateurs et lecture de l’assembleur produit ^^).
Contrairement à d’autres langages (tels que C++, Ada, Java, …) le C n’offre
pas de réel support pour la programmation générique. Cela ne signifie pas que la
programmation générique est impossible en C, par contre elle nécessite plus
d’effort pour être mise en œuvre. Dans cet article, je vais présenter deux
approches :
une approche à base de void*, que je nomme approche « traditionnelle ».
une approche intrusive, sur laquelle je m’attarderai un peu plus car elle me
semble moins connue.
Dans la suite de cet article, je vais prendre l’exemple d’une liste simplement
chaînée. En effet, c’est une des structures de données de bases et on la
retrouve dans d’autres structures de données (certaines tables de hachage par
exemple) ou algorithmes. Elle peut même servir de support à un langage (comme
les dialectes Lisp où tout est liste, le programme lui-même y compris).
Approche « traditionnelle »
L’approche la plus courante (on la retrouve dans la
GLib
et les EFL
entre autres) est l’utilisation d’un pointeurvoid*. Pour implémenter une liste
simplement chaînée générique on pourrait donc avoir le code suivant :
slist.h
1234567891011
/* Head of a singly-linked list. */typedefstructslist_s{size_tlength;/* List length. */structslist_node_s*first;/* List head. */}slist;/* A node of a singly-linked list. */typedefstructslist_node_s{structslist_node_s*next;/* Next element. */void*data;/* User data. */}slist_node;
Ici j’ai choisi d’avoir une structure à part pour la tête (ce qui permet d’avoir
accès à longueur de la liste sans avoir à la parcourir), mais ce n’est qu’un
détail d’implémentation. Chaque nœud de la liste contient un pointeur vers le
nœud suivant et un pointeur void* sur les données.
Maintenant que la liste est définie, il faudrait stocker quelque chose dedans.
Je vais partir sur une structure qui représente un labyrinthe :
maze.h
1234567891011
/* A cell of the maze. */typedefunsignedcharCell;/* A Maze. */typedefstructmaze_s{Cell*maze;size_tm;/* Number of lines. */size_tn;/* Number of columns. */size_tin;/* Index of the starting point. */size_tout;/* Index of the exit. */}Maze;
En combinant les deux fichiers précédents on peut donc créer une liste de
labyrinthes. Cela peut être représenté graphiquement de la manière suivante :
L’avantage de cette approche est qu’elle est relativement naturelle et simple à
comprendre. En revanche, elle comporte quelques inconvénients :
le fait d’utiliser un pointeur pour les données stockées implique qu’il
faudra presque toujours allouer de la mémoire pour les données. On se
retrouve donc avec deux allocations par élément de la liste : allocation de
la donnée et allocation du nœud lui-même.
un autre souci, même s’il est probablement rarement ressenti dans la plupart
des cas, est celui des performances : à chaque fois que l’on veut accéder à
un élément de la liste à partir du nœud on doit déréférencer un pointeur. Ce
n’est pas gratuit.
L’impact du point 1 peut être réduit en utilisant une stratégie d’allocation
adaptée (la GLib propose
quelque chose
dans ce sens).
Si la perte de performance due au point 2 se fait vraiment sentir, il est
toujours possible remplacer l’implémentation naïve de la liste par une
liste « déroulée » afin
d’augmenter la localité des données et de bénéficier de l’usage du cache.
Approche intrusive
Définition
Tout d’abord, il me semble utile de définir ce que l’on appelle une structure de
données intrusive.
Dans le cas « normal », le conteneur et le contenu sont totalement indépendants.
Le conteneur n’a pas besoin de savoir s’il va servir à stocker des int ou
une structure Maze pour être défini. De même, une structure Maze n’a pas
besoin de savoir si elle va être stockée dans une liste pour être définie
(souvenez vous de la première partie de cet article : slist.h et maze.h sont
totalement indépendants).
En revanche, dans le cas d’une structure de données intrusive, la donnée
contenue (la structure Maze dans mon exemple) devra être définie en tenant
compte du conteneur (dans notre exemple, cela signifie que maze.h dépendra de
slist.h).
Mise en œuvre
La liste est toujours indépendante de son contenu (comme dans l’approche
« traditionnelle »).
slist.h
12345678910
/* Head of a singly-linked list. */typedefstructslist_s{size_tlength;/* List length. */structslist_node_s*first;/* List head. */}slist;/* A node of a singly-linked list. */typedefstructslist_node_s{structslist_node_s*next;/* Next element. */}slist_node;
Définition quasiment identique à la définition précédente. À un détail près :
chaque nœud de la liste ne contient qu’un pointeur vers le nœud suivant et rien
d’autre. Aucune référence à son contenu (le champ data a disparu).
En effet, le lien entre la liste et la donnée est maintenant embarqué dans la
donnée elle-même (on voit bien le côté intrusif) comme le prouve le nouveau
champ node ajouté à la structure Maze :
maze.h
1234567891011121314
#include "slist.h"/* A cell of the maze. */typedefunsignedcharCell;/* A Maze. */typedefstructmaze_s{Cell*maze;slist_nodenode;size_tm;/* Number of lines. */size_tn;/* Number of columns. */size_tin;/* Index of the starting point. */size_tout;/* Index of the exit. */}Maze;
En combinant les deux fichiers précédents on peut donc créer une liste de
labyrinthes. Cela peut être représenté graphiquement de la manière suivante (on
voit bien la différence par rapport à l’approche « traditionnelle ») :
Avec cette approche, nous n’avons plus les inconvénients dus à l’utilisation de
void* :
plus besoin d’allouer le nœud ET la donnée : une seule allocation suffit.
plus de déréférencement pour accéder à la donnée à partir du nœud.
Contrairement à ce que l’on pourrait penser, une liste intrusive n’est pas plus
difficile à utiliser qu’une liste « traditionnelle » et ne nécessite pas plus de
code. D’ailleurs, on retrouve ces structures intrusives dans le noyau Linux
(liste doublement chaînée
et
arbre rouge-noir
par
exemple), dans l’en-tête sys/queue.h chez les
*BSD (Linux en
propose aussi une implémentation) et dans
les
EFL
pour ne citer que quelques exemples connus.
Cependant, cette approche n’est pas parfaite non plus :
on utilise de l’espace pour le nœud de la liste même si la donnée n’est pas
stockée dans une liste.
il faut avoir le contrôle sur la définition des données que l’on veut stocker
afin pouvoir ajouter le membre nécessaire à l’utilisation de la liste.
il faut avoir un moyen d’accéder à la donnée à partir d’une référence au
nœud.
Les problèmes 1 et 2 peuvent être contournés en encapsulant la donnée dans une
structure dédiée.
#include <stdio.h>#include <stdlib.h>#include "slist.h"typedefstruct{unsignedto;slist_nodenode;unsignedfrom;}pair_list;intmain(void){slistlist;slist_node*curr;slist_node*tmp;pair_list*elt;unsignedi;/* Initialize the list. */slist_init(&list);/* Populate the list. */for(i=0;i<5;++i){elt=malloc(sizeof*elt);if(elt==NULL)gotofailure;elt->from=i;elt->to=i+1;slist_add(&list,&(elt->node));}/* Display the list. */slist_foreach(&list,curr){elt=slist_elt(curr,pair_list,node);printf("from = %u | to = %u\n",elt->from,elt->to);}/* Free the list. */slist_foreach_safe(&list,curr,tmp){elt=slist_elt(curr,pair_list,node);slist_del(&list);free(elt);}returnEXIT_SUCCESS;/* Error handling. */failure:if(!slist_is_empty(&list)){slist_foreach_safe(&list,curr,tmp){elt=slist_elt(curr,pair_list,node);slist_del(&list);free(elt);}}returnEXIT_FAILURE;}
Lignes 6-10 on définit notre structure (qui pourrait représenter un intervalle).
On n’oublie pas d’y intégrer un membre slist_node afin de pouvoir en faire
une liste.
Ligne 14 on déclare notre liste puis on l’initialise ligne 20. S’en suit une
boucle (lignes 22-30) pour la peupler : on alloue 5 structures et on les ajoute
à la liste les unes à la suite des autres. On remarque que pour ajouter un
élément à la liste on ne passe pas la structure elle-même mais uniquement son
champ node (ligne 29, second paramètre de slist_add).
La seconde boucle (lignes 32-35) affiche le contenu de notre liste.
slist_foreach permet de parcourir la liste nœud par nœud. À partir du nœud,
on récupère notre structure et on l’affiche.
Enfin, la dernière boucle (lignes 37-41) libère la mémoire allouée. On remarque
que l’on supprime d’abord le nœud de la liste via slist_del avant de libérer
la mémoire allouée à notre structure (ce qui est logique étant donné que la
structure contient le nœud, si on la désalloue en premier on perd l’accès au
nœud).
L’exécution de ce code nous donne :
12345
from = 4 | to = 5
from = 3 | to = 4
from = 2 | to = 3
from = 1 | to = 2
from = 0 | to = 1
Le code est relativement clair et concis, rien de bien compliqué. Cependant, la
ligne 33 nous rappelle le problème 3 : comment peut-on récupérer la structure à
partir du nœud ?
Dans l’approche traditionnelle, c’est très simple : étant donné que le nœud
contient un pointeur sur les données, il suffit de faire node->data pour
accéder aux données. Mais dans l’approche intrusive, c’est la donnée qui
contient notre nœud : comment peut on accéder à une structure à partir d’un de
ses champs ?
Solution
Champ en première position
La norme (ISO/IEC 9899:TC3, 6.7.2.1 Structure and
union specifiers § 13, page 103) nous dit :
Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.
Cela signifie qu’il n’y a jamais de padding avant le premier membre d’une
structure et que son adresse correspond donc à l’adresse de la structure
elle-même.
Par conséquent, si le champ slist_node est le premier de la structure, il
suffit d’un simple cast pour obtenir l’adresse de la structure. Cette solution
est très simple et très efficace (un cast en lui-même ne coute rien à
l’exécution) mais souffre de deux inconvénients :
manque de flexibilité : l’utilisateur doit faire en sorte que le champ
slist_node soit le premier de la structure.
il est impossible de stocker la structure dans plus d’une liste (comme
cette structure
qui peut à la fois être dans une liste de bus (champ node) et dans une liste
de bus enfant (champ children)) car on ne peut avoir qu’un seul
slist_node en première position.
Utilisation d’offsetof
La solution pour être indépendant de la position du champ (et donc de pouvoir
avoir plusieurs champs slist_node par structure) est d’utiliser une macro
méconnue mais pourtant fort utile : offsetof (définie dans stddef.h).
Cette macro prend deux arguments :
un nom de structure (pair_list par exemple).
un nom de champ (node par exemple).
Elle renvoie alors l’offset1 du champ dans la structure, en byte2. À
partir de là, c’est très simple : il suffit de calculer l’offset via offsetof
puis de soustraire cette valeur à l’adresse du champ qui contient le nœud afin
d’obtenir l’adresse de la structure.
Pour éviter de se retrouver avec une dépendance au nom du champ, on passe par la
macro suivante :
slist_elt
12345678910111213
/** * Returns a pointer to the structure which contains the node. * * \param node a list node (slist_node*). * \param type type of the structure which contains the node. * \param fieldname name of the node (field name) in the structure. * * \pre `node` must be not NULL. * * \remarks Complexity: O(1) */#define slist_elt(node, type, fieldname) \ ((type*)((char*)(node) - offsetof(type, fieldname)))
Cette macro prend trois arguments :
l’adresse du nœud (l’adresse du champ slist_node).
le type de la structure (pair_list par exemple) : nécessaire pour convertir
le type de l’adresse retournée.
le nom du champ slist_node utilisé comme premier argument.
Seul point un peu délicat : il faut absolument convertir node en char*
sinon la soustraction ne va pas renvoyer l’adresse que l’on souhaite. En effet,
soit P un pointeur T* et N un nombre entier : P-N est
équivalent à P-N*sizeof(T) (arithmétique des pointeurs de base). Or,
l’offset renvoyé par offsetof est exprimé en byte, il faut donc faire la
soustraction avec un pointeur sur un type T vérifiant sizeof(T)==1.
Sachant que la norme (ISO/IEC 9899:TC3, 6.5.3.4 The
sizeof operator § 3, page 80) nous dit :
When applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.
sizeof(char) renvoyant toujours 1 par définition, il suffit donc de convertir
node en char* avant la soustraction pour obtenir le résultat souhaité.
Cependant, cette solution a un gros problème3 : elle contient un comportement
indéfini ! En effet, l’arithmétique des pointeurs n’est pas aussi simple qu’elle
en à l’air. Il y a un certains nombre de règles à respecter, parmi lesquelles
ISO/IEC 9899:TC3, 6.5.6 Additive operator § 7, page 83 :
For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
[...] If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. [...]
Qu’est ce que cela implique dans notre cas ?
On applique une soustraction à un pointeur qui pointe sur le champ slist_node
d’une structure. De manière évidente, ce pointeur ne pointe pas sur un élément
contenu dans un tableau donc la première règle que j’ai cité va être appliquée
et on va considérer node comme un pointeur sur le premier élément d’un tableau
de char (et oui, on convertit node en char* avant d’appliquer la
soustraction) de taille 1. Jusque là, on est sauf.
Ensuite, on applique notre soustraction. On va donc soustraire un certain nombre
de byte à l’adresse contenue dans le pointeur : le résultat pointera donc à une
adresse située avant node. Et là, la seconde règle va nous frapper : le
pointeur node et l’adresse résultante ne pointe pas sur le même tableau (étant
donné que l’adresse résultante pointe avant le tableau), on a donc un undefined
behavior (comportement indéfini). GAME OVER !
Conclusion
En conclusion, le choix entre les deux approches dépend principalement de vos
objectifs, de vos contraintes et de vos données.
Si les données peuvent exister de manière indépendante, en dehors de toute
structure, la première approche est probablement plus logique. De la même
manière, si ce sont des données que vous ne pouvez pas modifier pour y ajouter
les champs nécessaires, il est probablement plus pratique d’utiliser l’approche
« traditionnelle ».
D’un autre côté, si les données font nécessairement partie d’une liste, on peut
envisager l’approche intrusive (en plaçant le champ requis en premier dans la
structure). En revanche, si les données doivent pouvoir être stockées dans
plusieurs conteneurs à la fois il faudra revenir à la première approche ou
utiliser l’approche à base d’offsetof (tout en étant conscient que cela se
base sur un comportement indéfini et qu’un compilateur pourrait « casser » le
code en l’optimisant).
D’autres critères peuvent bien sûr entrer en compte (si les ajouts/suppressions
sont très frèquents, une approche intrusive peut être plus efficace). Il n’y a
pas de règle absolue en la matière.
Téléchargement
Pour ceux que cela intéresse, le code complet de la liste simplement chaînée
(version intrusive) est disponible ici.
Attention : Ce code ayant été écrit longtemps avant la rédaction de cet
article, il est donc basé sur la méthode offsetof qui contient un
comportement indéfini (dont j’ignorai l’existence au moment de l’écriture du
code).
Le code est sous licence BSD-3. Il est écrit en C89 et aucune dépendance
particulière n’est requise (hormis Check pour
les tests unitaires). La compilation se fait via CMake, une documentation peut
être générée par Doxygen. Deux exemples sont disponibles dans le dossier
examples.
« multiplet » en bon français. J’en profite pour signaler qu’un byte n’est pas forcément égal à un octet (même si, de nos jours, c’est le cas le plus répandu) et que ce n’est pas non plus un synonyme de bit (Cf. Wikipédia pour plus d’information).↩
problème que j’ai remarqué lors de la rédaction de cet article.↩
Le crackme étudié dans cet article provient
d’ici.
Cinquième crackme, et cette fois nous allons travailler non pas sur du code
machine, mais sur du bytecode Python.
Un fichier Python compilé reste un fichier binaire, donc nous pouvons commencer
par la traditionnelle commande strings.
12345678910111213141516171819
% strings ch19.pyc
__main__u$
Welcome to the RootMe python crackmeu
Enter the Flag: u'
I know, you love decrypting Byte Code !i
You Winu
Try Again !N(
__name__u
printu
inputu
PASSu
KEYu
SOLUCEu
KEYOUTu
appendu
ordu
len(
crackme.pyu
<module>
Bon rien de bien concluant. Il est maintenant temps de se renseigner sur ce
fameux fichier de bytecode, et plus particulièrement sur son format. Après
quelques recherches, je suis tombé sur
ce fil
de la liste de diffusion Python-ideas. La partie intéressante est la
suivante :
Currently .pyc files use a very simple format:
- MAGIC number (4 bytes, little-endian) - last modification time of source file (4 bytes, little-endian) - code object (marshaled)
Et bien ça c’est une bonne nouvelle :-). Le format de ce fichier est extrêmement
simple. Deux entiers 32-bit et un objet code sérialisé.
Cela dit, le fait que l’objet code soit sérialisé via le module
marshal plutôt que via le
module pickle implique qu’il
va nous falloir utiliser une version de Python relativement proche de celle qui
a généré le bytecode, sinon on risque de ne pas pouvoir désérialiser l’objet.
Le crackme ayant été publié le 3 juillet 2013, je vais tenter ma chance avec
le Python 3.3 de mon Archlinux.
Ok, c’est bien du Python 3. À titre de comparaison, voilà ce qui arrive si l’on
essaye de lire le fichier avec du Python 2.7.
123456789101112131415161718
% python2
Python 2.7.5 (default, Sep 6 2013, 09:55:21)
[GCC 4.8.1 20130725 (prerelease)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import marshal
>>> import struct
>>> import time
>>> pyc = open('ch19.pyc', 'rb')
>>> magic_number = struct.unpack('<i', pyc.read(4))[0]
>>> hex(magic_number)
'0xa0d0c4f'
>>> timestamp = struct.unpack('<i', pyc.read(4))[0]
>>> time.strftime('%Y/%m/%d', time.localtime(timestamp))
'2013/07/02'
>>> code = marshal.load(pyc)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: bad marshal data (unknown type code)
Ok, on arrive donc bien à désérialiser notre binaire en un objet code. Et
maintenant, on fait quoi avec cet objet ?
C’est là que l’excellente et très complète bibliothèque standard de Python
intervient. Dans cette bibliothèque on trouve une section
Python Language Services
qui contient le module dis. Et
c’est exactement ce qu’il nous faut !
Allez, faisons un petit script pour désassembler ce fichier compilé et avoir du
bytecode à nous mettre sous la dent.
disass.py
1234567891011121314151617181920212223
#!/usr/bin/env python3importdisimportmarshalimportstructimportsysdefdisassemble(filepath):withopen(filepath,'rb')aspyc:# Read the magic number._=struct.unpack('<i',pyc.read(4))# Read the timestamp_=struct.unpack('<i',pyc.read(4))# Read the code.code=marshal.load(pyc)dis.disassemble(code)if__name__=='__main__':iflen(sys.argv)==2:disassemble(sys.argv[1])else:print('Error: missing argument',file=sys.stderr)print('Usage: {} file.pyc'.format(sys.argv[0]))
Si l’on ajoute à cela le fait que le script à l’origine de ce bytecode est court,
alors il est simple de faire une décompilation à la main, à partir du bytecode,
qui nous permet de retrouver le script suivant :
crackme.py
12345678910111213141516
#!/usr/bin/env python3if__name__=='__main__':print('Welcome to the RootMe python crackme')PASS=input('Enter the Flag: ')KEY='I know, you love decrypting Byte Code !'I=5SOLUCE=[57,73,79,16,18,26,74,50,13,38,13,79,86,86,87]KEYOUT=[]forXinPASS:KEYOUT.append(ord(X)+I^ord(KEY[I])%255)I=I+1%len(KEY)ifSOLUCE==KEYOUT:print('You Win')else:print('Try Again !')
Maintenant que l’on connaît le résultat à obtenir et comment la chaîne en entrée
est transformée, il nous suffit d’appliquer la transformation inverse (et ici la
transformation est simple à inverser) sur le résultat attendu (SOLUCE) afin
d’obtenir ce que nous cherchons(PASS). Pour ce faire, j’ai fait un petit
script Ruby :
breakit.rb
1234567
#!/usr/bin/env rubySOLUCE=[57,73,79,16,18,26,74,50,13,38,13,79,86,86,87]KEY='I know, you love decrypting Byte Code !'.each_char.map(&:ord).to_aI=5psw=SOLUCE.zip(KEY[I..-1]).each_with_index.map{|(x,k),i|(x^k)-(i+I)}puts(psw.map(&:chr).join)
Et il nous donne :
12
% ./breakit.rb
I_hate_RUBY_!!!
Si j’avais su ^^
Bon allez, testons cela :
1234
% ./crackme.py
Welcome to the RootMe python crackme
Enter the Flag: I_hate_RUBY_!!!
You Win
Gagné !
Voilà, ce crackme un peu original est terminé. Il était relativement simple,
mais il aura fallu quelques recherches pour en venir à bout. En tout cas, ce fut
instructif.
Le crackme étudié dans cet article provient
d’ici.
Quatrième crackme, et cette fois nous allons rencontrer notre premier
mécanisme anti-débogueur.
Nous avons donc à faire à un exécutable statique avec un strings de 2069
lignes qui ne contient pas de mot de passe (cette fois j’ai vérifié ^^‘)
Ok, sortons le débogueur (comme pour le crackme 2, sauf que cette fois c’est
justifié :-P). Mais avant cela, voyons d’abord une exécution normale :
1234567
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
Password : AAAAAAAA
Wrong password.
Maintenant, avec notre ami GDB :
1234
(gdb) r
Starting program: /home/slaperche/Téléchargements/crackme/ch3.bin
Debugger detecté ... Exit
[Inferior 1 (process 5244) exited with code 01]
Hoho, voyez-vous ça ? Monsieur n’aime pas être surveillé. Bon, on va y aller un
peu plus doucement cette fois :
Tiens, tiens, mais que vois-je ? Un appel à
ptrace à l’adresse 0x08048410. Il faut
savoir que, sous Linux du moins, ptrace est l’appel système à la base des
débogueurs. Il permet de mettre en pause un programme, de faire du pas à pas, de
lire et écrire sa mémoire et ses registres. Il permet également de détecter si
un programme est sous la surveillance de ptrace (et donc, potentiellement
sour la surveillance d’un débogueur). Et c’est ce qui est fait ici. Le code :
Qui permet de savoir si le processus courant est sous surveillance.
Maintenant que l’on sait comment le binaire se défend, nous allons pouvoir
contourner cette protection. Pour cela, nous pouvons placer un point d’arrêt sur
l’instruction qui teste la valeur de retour de ptrace et la changer (sachant
que l’appel renvoi -1 si le processus est tracé et 0 si ce n’est pas le cas)
avant de continuer l’exécution.
1234567
(gdb) b *0x08048418
Breakpoint 2 at 0x8048418
(gdb) c
Continuing.
Breakpoint 2, 0x08048418 in main ()
(gdb) set $eax = 0
Avant de continuer, regardons le code de plus près. Bon déjà, il n’y a pas
d’appel à strcmp. Cependant, en examinant le code avec attention on remarque
cette partie :
Tiens tiens, on dirait bien qu’il y a un pattern ici :
on charge un octet dans dl
on charge une valeur dans eax
on fait une opération arithmétique sur eax (add ou inc)
on ramène eax sur un octet.
on compare al avec dl
on saute à l’adresse 0x80484e4 si la comparaison précédente génère un résultat
différent de 0 (ce qui signifie que les deux opérandes étaient différents).
Cela ressemble étrangement à une boucle (boucle déroulée certes, mais boucle
quand même) pour comparer deux chaînes de caractères. Et comme ce pattern se
répète quatre fois, on pourrait émettre l’hypothèse que le mot de passe
recherché a une longueur de 4 caractères.
Vérifions nos hypothèses en examinant les valeurs de al et dl à chaque
cmp. Commençons par poser un point d’arrêt sur le premier cmp.
123456789101112131415
(gdb) b *0x080484a3
Breakpoint 3 at 0x80484a3
(gdb) c
Continuing.
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
Password : AAAA
Breakpoint 3, 0x080484a3 in main ()
(gdb) p (char)$al
$1 = 101 'e'
(gdb) p (char)$dl
$2 = 65 'A'
Ok, dl semble contenir notre chaîne (on reconnaît notre A), c’est donc al
qui va contenir les caractères du mot de passe à trouver (le premier caractère
du mot de passe est donc e).
Bien, maintenant que l’on sait quel registre surveiller, continuons avec les
autres cmp. Mais avant cela, il va falloir bidouiller un peu. Et oui, le
cmp ne va pas produire le résultat attendu et la prochaine instruction va
nous faire sauter (ce qui va nous empêcher d’analyser les autres cmp). La
prochaine instruction est un jne ce qui signifie Jump if Not Equal, qui
est le parfait équivalent de l’instruction jnz (qui signifie Jump if Not
Zero). Or le second nom (jnz) nous met la puce à l’oreille : cette
instruction se base sur la valeur du flag z. Pour éviter le saut, il va donc
falloir mettre ce flag à 1 après l’instruction cmp.
Allons-y :
1234567
(gdb) ni
0x080484a5 in main ()
(gdb) p $eflags
$3 = [ CF AF SF IF ]
(gdb) set $eflags = $eflags | 64
(gdb) p $eflags
$4 = [ CF AF ZF SF IF ]
Et voilà, le flag z est positionné (il y a peut-être une syntaxe plus simple
pour faire ça, mais je n’ai pas trouvé). D’où sort le 64 ? Et bien c’est tout
simple : d’après
cette page, le
flag z correspond au bit 6, et comme chacun sait 26 = 64. S’en suit
un petit OU bit à bit pour positionner le flag voulu. Et voilà le travail.
Allez, continuons et découvrons ce fichu mot de passe :
(gdb) b *0x080484b2
Breakpoint 4 at 0x80484b2
(gdb) c
Continuing.
Breakpoint 4, 0x080484b2 in main ()
(gdb) p (char)$al
$5 = 97 'a'
(gdb) ni
0x080484b4 in main ()
(gdb) set $eflags = $eflags | 64
(gdb) b *0x080484bf
Breakpoint 5 at 0x80484bf
(gdb) c
Continuing.
Breakpoint 5, 0x080484bf in main ()
(gdb) p (char)$al
$6 = 115 's'
(gdb) ni
0x080484c1 in main ()
(gdb) set $eflags = $eflags | 64
(gdb) b *0x080484ce
Breakpoint 6 at 0x80484ce
(gdb) c
Continuing.
Breakpoint 6, 0x080484ce in main ()
(gdb) p (char)$al
$7 = 121 'y'
Ok, le mot de passe serait donc easy.
Voyons voir :
12345678
% ./ch3.bin
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
Password : easy
Good password !!!
Le crackme étudié dans cet article provient
d’ici.
Avec ce troisième crackme, on reste dans du très simple mais ça va nous
permettre de voir une nouvelle approche lorsque l’on veut faire de la
rétroingénierie sur des exécutables dynamiques.
Bon, déjà voyons à quoi nous avons à faire.
12
% ./crackme
(*) -Syntaxe: ./crackme03 [password]
Ok, celui-ci prend le mot de passe via les arguments de la ligne de commande.
Commençons par le traditionnel strings qui, comme on pouvait s’y attendre,
ne nous apprend pas grand-chose.
% strings crackme
/lib/ld-linux.so.2
__gmon_start__
libc.so.6
_IO_stdin_used
strcpy
exit
puts
__stack_chk_fail
printf
memcpy
malloc
strcmp
__libc_start_main
GLIBC_2.4
GLIBC_2.0
PTRh0
QVhT
libe
_0cG
jc5m
_.5T
[^_]
(*) -Syntaxe: %s [password]
_0cGj35m9V5T3
8CJ0
9H95h3xdh
_Celebration
rification de votre mot de passe..
(!) L'authentification a
chou
Try again !
'+) Authentification r
ussie...
U'r root!
sh 3.0 # password: %s
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
Il y a bien quelques chaînes qui ressemblent vaguement à un mot de passe, mais
aucune ne fonctionne.
123456
% ./crackme _0cGj35m9V5T3
Vérification de votre mot de passe..
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
% ./crackme 9H95h3xdh
Vérification de votre mot de passe..
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
Voyons à quel type de binaire nous avons là :
1
crackme03: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.8, not stripped
Hum, intéressant : cet exécutable est lié dynamiquement. Voyons donc ce que nous
donne un petit ltrace :
12345678910111213
% ltrace ./crackme AAAAAAAA
__libc_start_main(0x8048554, 2, 0xbfa5d744, 0x8048840, 0x8048830 <unfinished ...>
malloc(29) = 0x09a6d008
memcpy(0x09a6d008, "_0cGj35m9V5T3\303\2078CJ0\303\2009H95h3xdh", 31) = 0x09a6d008
memcpy(0xbfa5d60a, "_Celebration", 13) = 0xbfa5d60a
strcpy(0xbfa5d66e, "AAAAAAAA") = 0xbfa5d66e
puts("V\303\251rification de votre mot de pa"...Vérification de votre mot de passe..
) = 38
strcmp("AAAAAAAA", "_0cGjc5m_.5\r\n\303\2078CJ0\303\2009") = -1
printf("le voie de la sagesse te guidera"...le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
) = 84
exit(0 <unfinished ...>
+++ exited (status 0) +++
Hum, c’est très instructif. On voit que le code fait un strcmp contre une chaîne
un peu bizarre. Essayons d’utiliser cette chaîne bizarre en tant que mot de
passe. Étant donné que la chaîne contient la séquence de caractères de contrôles
\r\n, je préfère utiliser Ruby pour passer la chaîne en argument (d’autres
solutions étaient bien sûr possible) plutôt que d’essayer de la taper
directement dans le shell.
123456
% ./crackme "$(ruby -e 'print("_0cGjc5m_.5\r\n\303\2078CJ0\303\2009")')"
Vérification de votre mot de passe..
'+) Authentification réussie...
U'r root!
sh 3.0 # password: liberté!
Le crackme étudié dans cet article provient
d’ici.
Ce second crackme est un peu moins simple que le précédent, mais il est tout
de même trivial. En revanche, je me suis compliqué la vie : la solution était en
fait bien plus simple que ce que l’on peut penser. Mais au moins, ça me permet
de présenter l’usage de GDB ^^
Comme la dernière fois, on va commencer par lancer strings sur notre
binaire. Cependant, cette fois le nombre de chaîne de caractères est beaucoup
plus important (1506 chaînes). Ayant la flemme de regarder cela en détail
(pourtant j’aurai dû, comme vous le verrez par la suite), je décide de passer à
autre chose.
Déjà, on peut remarquer (via la commande file
ou ldd) que l’exécutable est compilé en mode statique (ce
qui explique le grand nombre de chaîne de caractères), ça signifie que l’on peut
oublier d’office les bidouilles à base de ltrace et autres LD_PRELOAD
(ne vous inquiétez pas, on aura l’occasion de s’amuser avec ça dans d’autres
défis).
Partant de ces premières observations, je décide de partir sur
GDB. Mais avant cela,
voyons une exécution normale :
1234567
% ./ch2.bin
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
username: foo
Bad username
Ok, il faut donc fournir un nom d’utilisateur avant de pouvoir fournir le mot de
passe.
Maintenant, passons à GDB. Première chose à faire : placer un point d’arrêt sur
la fonction main, puis regarder le code assembleur.
Information intéressante : il y a deux appels à strcmp. Ça pourrait bien
correspondre aux vérifications du nom d’utilisateur et du mot de passe. On va
donc placer un point d’arrêt sur strcmp afin de pouvoir examiner son code.
(gdb) b *0x80502f0
Breakpoint 2 at 0x80502f0
(gdb) c
Continuing.
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
username: AAAAAAAA
Breakpoint 2, 0x080502f0 in strcmp ()
(gdb) disass
Dump of assembler code for function strcmp:
=> 0x080502f0 <+0>: push %ebp
0x080502f1 <+1>: xor %edx,%edx
0x080502f3 <+3>: mov %esp,%ebp
0x080502f5 <+5>: push %esi
0x080502f6 <+6>: push %ebx
0x080502f7 <+7>: mov 0x8(%ebp),%esi
0x080502fa <+10>: mov 0xc(%ebp),%ebx
0x080502fd <+13>: lea 0x0(%esi),%esi
0x08050300 <+16>: movzbl (%esi,%edx,1),%eax
0x08050304 <+20>: movzbl (%ebx,%edx,1),%ecx
0x08050308 <+24>: test %al,%al
0x0805030a <+26>: je 0x8050328 <strcmp+56>
0x0805030c <+28>: add $0x1,%edx
0x0805030f <+31>: cmp %cl,%al
0x08050311 <+33>: je 0x8050300 <strcmp+16>
0x08050313 <+35>: movzbl %al,%edx
0x08050316 <+38>: movzbl %cl,%eax
0x08050319 <+41>: sub %eax,%edx
0x0805031b <+43>: mov %edx,%eax
0x0805031d <+45>: pop %ebx
0x0805031e <+46>: pop %esi
0x0805031f <+47>: pop %ebp
0x08050320 <+48>: ret
0x08050321 <+49>: lea 0x0(%esi,%eiz,1),%esi
0x08050328 <+56>: movzbl %cl,%edx
0x0805032b <+59>: neg %edx
0x0805032d <+61>: mov %edx,%eax
0x0805032f <+63>: pop %ebx
0x08050330 <+64>: pop %esi
0x08050331 <+65>: pop %ebp
0x08050332 <+66>: ret
End of assembler dump.
On prend soin d’utiliser une chaîne très facilement reconnaissable en tant que
nom d’utilisateur, ça peut être utile par la suite.
En analysant le code on voit que la comparaison (instruction cmp à l’adresse
0x0805030f) se fait sur le contenu des registres cl et al. Ces registres
correspondent en fait aux registres 32-bit ecx et eax traités comme des
registres 8-bit. Or, on voit que les valeurs de ces registres sont chargées à
partir des adresses contenues dans esi (pour eax) et ebx (pour
ecx) via des instructions movzbl. Il suffit donc de mettre un point
d’arrêt après le chargement des adresses dans esi et ebx afin de pouvoir
afficher les chaînes de caractères :
12345678910
(gdb) b *0x08050300
Breakpoint 3 at 0x8050300
(gdb) c
Continuing.
Breakpoint 3, 0x08050300 in strcmp ()
(gdb) p (char*)$esi
$1 = 0x80c8688 "AAAAAAAA"
(gdb) p (char*)$ebx
$2 = 0x80a6b19 "john"
On reconnaît notre chaîne AAAAAAAA dans esi, c’est donc ebx qui contient
le nom d’utilisateur. On découvre alors que le nom d’utilisateur est john.
Comme nous avons donné un mauvais mot de passe, le programme va se terminer
avant que nous puissions découvrir le mot de passe. Pour éviter cela, nous
allons modifier la valeur de retour de strcmp. On commence par ajouter un
point d’arrêt juste après le premier appel de strcmp dans main, puis on
placera 0 (valeur de retour de strcmp lorsque les deux chaînes sont
identiques) dans le registre eax (registre utilisé pour stocker la valeur de
retour, ce comportement est défini par la
convention d’appel utilisée)
avant de continuer l’exécution.
123456789101112
(gdb) b *0x08048378
Breakpoint 4 at 0x8048378
(gdb) c
Continuing.
Breakpoint 4, 0x08048378 in main ()
(gdb) set $eax = 0
(gdb) c
Continuing.
password: BBBBBBBB
Breakpoint 2, 0x080502f0 in strcmp ()
Comme prévu, il nous demande le mot de passe et l’on se retrouve à nouveau dans
strcmp. En appliquant le même principe que précédemment on obtient le mot de
passe.
123456
(gdb) c
Continuing.
Breakpoint 3, 0x08050300 in strcmp ()
(gdb) p (char*)$ebx
$3 = 0x80a6b1e "the ripper"
Étant maintenant en possession des identifiants, on peut récupérer le code
secret :
12345678
% ./ch2.bin
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
username: john
password: the ripper
Bien joue, vous pouvez valider l'epreuve avec le mot de passe : 987654321 !
Gagné !
Le mot de passe était donc 987654321.
Le mot de la fin
Pour information, tout cela était inutile. En effet, la sortie de strings
nous donnait déjà toutes les informations nécessaires (pour peu que l’on prenne
le temps de la regarder de plus près) :
1234567
% strings ch2.bin
[…]
john
the ripper
[…]
987654321
[…]
On voit donc que le nom d’utilisateur et le mot de passe était en clair dans le
binaire. Pis encore : le code à obtenir (987654321) est lui aussi en clair dans
le binaire. On n’avait même pas besoin de connaître le nom d’utilisateur et le
mot de passe pour y accéder.
Le crackme étudié dans cet article provient
d’ici.
Ce premier crackme va nous permettre de voir la première chose à faire en
rétroingénierie : lorsque l’on cherche une information textuelle dans un
binaire, il faut commencer par lancer un coup de
strings.
Ici, on obtient :
12345678910111213141516171819202122232425262728
% strings ch1.bin
/lib/ld-linux.so.2
__gmon_start__
libc.so.6
_IO_stdin_used
puts
realloc
getchar
__errno_location
malloc
stderr
fprintf
strcmp
strerror
__libc_start_main
GLIBC_2.0
PTRh@
[^_]
%s : "%s"
Allocating memory
Reallocating memory
123456789
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
Veuillez entrer le mot de passe :
Bien joue, vous pouvez valider l’epreuve avec le pass : %s!
Dommage, essaye encore une fois.
La chaîne 123456789 ressemble étrangement à un mot de passe.
Essayons :
1234567
% ./ch1.bin
############################################################
## Bienvennue dans ce challenge de cracking ##
############################################################
Veuillez entrer le mot de passe : 123456789
Bien joue, vous pouvez valider l’epreuve avec le pass : 123456789!
Gagné !
Celui-ci était vraiment simple, le mot de passe était stocké en clair dans le
binaire. Les prochains ne seront pas aussi évident ;-)
