Depuis la version 7.0¹ (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.

Soit le programme suivant :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <stdlib.h>

#include <arpa/inet.h>

int main(void)
{
    struct sockaddr_in  ipv4;
    struct sockaddr_in6 ipv6;

    if (inet_pton(AF_INET,  "82.66.107.250", &ipv4.sin_addr) != 1)
        return EXIT_FAILURE;

    if (inet_pton(AF_INET6, "2a01:e35:2426:bfa0:215:ff:fe42:7fd3",
                  &ipv6.sin6_addr) != 1)
        return EXIT_FAILURE;

    return EXIT_SUCCESS;
}

Si on lance GDB dessus en utilisant le fichier de commande suivant :

1
2
3
4
5
6
7
8
9
10

break example.c:17
command
silent
print ipv4->sin_addr
print ipv6->sin6_addr
continue
end

run
quit

On obtient :

1
2
3
4
5
6
7
8

% 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 = {s_addr = 4201333330}
$2 = {__in6_u = {__u6_addr8 = "*\001\016\065$&\277\240\002\025\000\377\376B", <incomplete sequence \323>, __u6_addr16 = {298, 13582, 9764, 41151, 5378, 65280, 17150, 54143}, __u6_addr32 = {890110250, 2696881700, 4278195458, 3548332798}}}
[Inferior 1 (process 2043) exited normally]

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 :

1. netinet.py qui contiendra le code des pretty-printers.
2. __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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from struct import pack
from socket import inet_ntop, AF_INET, AF_INET6

from gdb import lookup_type

class ipv4Printer(object):
    def __init__(self, val):
        self.addr = pack('I', int(val['s_addr']))

    def to_string(self):
        return inet_ntop(AF_INET, self.addr)

class ipv6Printer(object):
    def __init__(self, val):
        # IPv6 addresses have a size of 128 bits (== 16 octets).
        N = 16
        addr = val.cast(lookup_type("uint8_t").array(N))
        self.addr = pack('B'*N, *[int(addr[i]) for i in range(N)])

    def to_string(self):
        return inet_ntop(AF_INET6, self.addr)

Allons y étape par étape.

1
2
3
4

from struct import pack
from socket import inet_ntop, AF_INET, AF_INET6

from gdb import lookup_type

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ères². Enfin, on importe le module gdb.

1
2
3
4
5
6

class ipv4Printer(object):
    def __init__(self, val):
        self.addr = pack('I', int(val['s_addr']))

    def to_string(self):
        return inet_ntop(AF_INET, self.addr)

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.

1
2
3
4
5
6
7
8
9

class ipv6Printer(object):
    def __init__(self, val):
        # IPv6 addresses have a size of 128 bits (== 16 octets).
        N = 16
        addr = val.cast(lookup_type("uint8_t").array(N))
        self.addr = pack('B'*N, *[int(addr[i]) for i in range(N)])

    def to_string(self):
        return inet_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 :

• Linux
• DragonFlyBSD
• Windows
• FreeBSD
• NetBSD

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.

1
2
3
4
5
6
7
8

from gdb.printing import RegexpCollectionPrettyPrinter
import netinet

def netinet_pp():
    pp = RegexpCollectionPrettyPrinter("netinet")
    pp.add_printer('in_addr',  '^in_addr$',  netinet.ipv4Printer)
    pp.add_printer('in6_addr', '^in6_addr$', netinet.ipv6Printer)
    return pp

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 :

1
2
3
4
5
6
7
8
9
10

# 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 :

1
2
3
4
5
6
7
8

% 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.

Contexte

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) :

• cplusplus.com
• bien-programmer.fr
• tutorialspoint.com
• anyexample.com

Problème

Alors, quel est le problème ?
Prenons l’exemple donné sur le site cplusplus.com :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

Si on teste cet exemple, on obtient bien le résultat attendu :

10 20 25 40 90 100

Bien, et si maintenant on utilise¹ :

1

int values[] = { 40, INT_MIN, 100, INT_MAX, 20, INT_MIN + 42 };

Alors là, rien ne va plus ! En sortie on obtient :

40 100 2147483647 -2147483648 -2147483606 20

Ce qui ne correspond pas du tout à un tableau trié par ordre croissant.

Explication

Le souci vient de la fonction de comparaison :

1
2
3
4

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

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 :

1
2
3
4
5
6
7
8
9
10
11
12

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;

    if (*left > *right)
        return 1;
    else if (*left < *right)
        return -1;
    else
        return 0;
}

Et pour ceux qui trouvent l’alternative précédente trop verbeuse, il est toujours possible l’utiliser l’idiome suivant :

1
2
3
4
5
6

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;
    return (*left > *right) - (*left < *right);
}

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <stdio.h>
#include <stdlib.h>

#include "slist.h"

typedef struct
{
    unsigned to;
    slist_node node;
    unsigned from;
} pair_list;

int main(void)
{
    slist_list list;
    pair_list* elt;
    unsigned i;

    /* 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);

    return 0;
}

La découverte

Voyons maintenant ce que l’on obtient en sortie en l’exécutant.

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2
3

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 :

1. l’un des deux compilateurs a un bogue (peu probable, mais cela arrive).
2. 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
  • générer un programme qui va afficher 42
  • faire sortir des démons de votre nez.

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) :

• What Every C Programmer Should Know About Undefined Behavior #1/3
• What Every C Programmer Should Know About Undefined Behavior #2/3
• What Every C Programmer Should Know About Undefined Behavior #3/3

Tant que j’en suis à donner des liens, cet article en trois parties de John Regehr est aussi très instructif sur les UB :

• A Guide to Undefined Behavior in C and C++, Part 1
• A Guide to Undefined Behavior in C and C++, Part 2
• A Guide to Undefined Behavior in C and C++, Part 3

Étant donné que :

1. je connaissais les articles précédemment cités.
2. 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).
3. 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 :

1
2
3

==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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

.LVL4:
        .loc 1 33 0
        movq    %rsp, %rdi
        call    slist_first
.LVL5:
        leaq    -8(%rax), %rdx
.LVL6:
        movq    %rax, %rbx
        testq   %rax, %rax
        je      .L2
.L3:
        .loc 1 34 0 discriminator 2
        movl    16(%rdx), %esi
        movl    (%rdx), %edx
.LVL7:
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
.LVL8:
        .loc 1 33 0 discriminator 2
        movq    %rbx, %rdi
        call    slist_next
.LVL9:
        leaq    -8(%rax), %rdx
.LVL10:
        movq    %rax, %rbx
        testq   %rax, %rax
        jne     .L3

Dans les dernières lignes on voit bien une comparaison (testq) suivi d’un saut conditionnel (jne) en début de boucle : tout va bien.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

.Ltmp13:
# BB#2:
        leaq    8(%rsp), %rdi
        .loc    1 33 0                  # examples/min_bug.c:33:0
.Ltmp14:
        callq   slist_first
        movq    %rax, %rbx
        .align  16, 0x90
.LBB0_3:                                # =>This Inner Loop Header: Depth=1
        .loc    1 34 0                  # examples/min_bug.c:34:0
        movl    -8(%rbx), %edx
        movl    8(%rbx), %esi
        movl    $.L.str, %edi
        xorb    %al, %al
        callq   printf
        .loc    1 33 0                  # examples/min_bug.c:33:0
        movq    %rbx, %rdi
        callq   slist_next
        movq    %rax, %rbx
        jmp     .LBB0_3

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 :

1
2
3
4

#define slist_foreach_elt(list, curr, type, fieldname)         \
    for (curr = slist_elt(slist_first(list), type, fieldname); \
         &(curr->fieldname) != NULL;                           \
         curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Hooooo yeaaah :)

Sachant que slist_elt est aussi une macro :

1
2

#define slist_elt(node, type, fieldname) \
    ((type*)((char*)(node) - offsetof(type, fieldname)))

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) :

curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Donc ici, je vais appeler slist_elt avec le contenu du pointeur next (car j’appelle slist_next), c’est-à-dire avec NULL.

Cela donne :

((type*)((char*)(node) - offsetof(type, fieldname)))

Et donc dans le cas présent :

((pair_list*)((char*)(NULL) - offsetof(pair_list, node)))

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 :

1
2
3
4
5

#define slist_foreach_elt(list, curr, type, fieldname)                     \
        for (curr = slist_elt(slist_first(list), type, fieldname);         \
             curr != NULL;                                                 \
             curr = curr->fieldname.next == NULL ? NULL :                  \
                    slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Et le problème est résolu.

Deux autres solutions possibles :

• 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 :

1. une approche à base de void*, que je nomme approche « traditionnelle ».
2. 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 :

1
2
3
4
5
6
7
8
9
10
11

/* Head of a singly-linked list. */
typedef struct slist_s {
    size_t length;              /* List length. */
    struct slist_node_s* first; /* List head.   */
} slist;

/* A node of a singly-linked list. */
typedef struct slist_node_s {
    struct slist_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 :

1
2
3
4
5
6
7
8
9
10
11

/* A cell of the maze. */
typedef unsigned char Cell;

/* A Maze. */
typedef struct maze_s {
    Cell* maze;
    size_t m;   /* Number of lines.             */
    size_t n;   /* Number of columns.           */
    size_t in;  /* Index of the starting point. */
    size_t out; /* 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 :

1. 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.

2. 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 »).

1
2
3
4
5
6
7
8
9
10

/* Head of a singly-linked list. */
typedef struct slist_s {
    size_t length;              /* List length. */
    struct slist_node_s* first; /* List head.   */
} slist;

/* A node of a singly-linked list. */
typedef struct slist_node_s {
    struct slist_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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include "slist.h"

/* A cell of the maze. */
typedef unsigned char Cell;

/* A Maze. */
typedef struct maze_s {
    Cell* maze;
    slist_node node;
    size_t m;   /* Number of lines.             */
    size_t n;   /* Number of columns.           */
    size_t in;  /* Index of the starting point. */
    size_t out; /* 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 :

1. 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.
2. 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.
3. 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.

1
2
3
4
5
6
7
8

struct Data {
    /* Interesting fields. */
};

struct data_wrapper {
    struct Data       data;
    struct slist_node node;
};

Cependant, on perd la facilité d’utilisation.

La solution au problème 3 sera abordée plus loin dans cet article.

Exemple d’utilisation

Voici un petit exemple d’utilisation : on crée une liste de 5 éléments, on l’affiche puis on libère la mémoire.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <stdio.h>
#include <stdlib.h>

#include "slist.h"

typedef struct {
    unsigned to;
    slist_node node;
    unsigned from;
} pair_list;

int main(void)
{
    slist list;
    slist_node* curr;
    slist_node* tmp;
    pair_list*  elt;
    unsigned i;
    /* Initialize the list. */
    slist_init(&list);
    /* Populate the list. */
    for (i = 0; i < 5; ++i) {
        elt = malloc(sizeof *elt);
        if (elt == NULL)
            goto failure;

        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);
    }
    return EXIT_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);
        }
    }
    return EXIT_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 :

1
2
3
4
5

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 :

1. un nom de structure (pair_list par exemple).
2. un nom de champ (node par exemple).

Elle renvoie alors l’offset¹ du champ dans la structure, en byte². À 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 :

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * 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 :

1. l’adresse du nœud (l’adresse du champ slist_node).
2. le type de la structure (pair_list par exemple) : nécessaire pour convertir le type de l’adresse retournée.
3. 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ème³ : 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.

et ISO/IEC 9899:TC3, 6.5.6 Additive operator § 8, page 83 :

[…]
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.

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

% 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.

Essayons donc de lire ce fichier :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

% bpython
>>> 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)
>>> code
<code object <module> at 0x7fb7b60e80c0, file "crackme.py", line 8>
>>> pyc.close()

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

% 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#!/usr/bin/env python3

import dis
import marshal
import struct
import sys

def disassemble(filepath):
    with open(filepath, 'rb') as pyc:
        # 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__':
    if len(sys.argv) == 2:
        disassemble(sys.argv[1])
    else:
        print('Error: missing argument', file=sys.stderr)
        print('Usage: {} file.pyc'.format(sys.argv[0]))

Et maintenant, appliquons-le à notre crackme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

% ./disass.py ch19.pyc
  8           0 LOAD_NAME                0 (__name__)
              3 LOAD_CONST               0 ('__main__')
              6 COMPARE_OP               2 (==)
              9 POP_JUMP_IF_FALSE      219

  9          12 LOAD_NAME                1 (print)
             15 LOAD_CONST               1 ('Welcome to the RootMe python crackme')
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 POP_TOP

 10          22 LOAD_NAME                2 (input)
             25 LOAD_CONST               2 ('Enter the Flag: ')
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 STORE_NAME               3 (PASS)

 14          34 LOAD_CONST               3 ('I know, you love decrypting Byte Code !')
             37 STORE_NAME               4 (KEY)

 16          40 LOAD_CONST               4 (5)
             43 STORE_NAME               5 (I)

 17          46 LOAD_CONST               5 (57)
             49 LOAD_CONST               6 (73)
             52 LOAD_CONST               7 (79)
             55 LOAD_CONST               8 (16)
             58 LOAD_CONST               9 (18)
             61 LOAD_CONST              10 (26)
             64 LOAD_CONST              11 (74)
             67 LOAD_CONST              12 (50)
             70 LOAD_CONST              13 (13)
             73 LOAD_CONST              14 (38)
             76 LOAD_CONST              13 (13)
             79 LOAD_CONST               7 (79)
             82 LOAD_CONST              15 (86)
             85 LOAD_CONST              15 (86)
             88 LOAD_CONST              16 (87)
             91 BUILD_LIST              15
             94 STORE_NAME               6 (SOLUCE)

 19          97 BUILD_LIST               0
            100 STORE_NAME               7 (KEYOUT)

 22         103 SETUP_LOOP              75 (to 181)
            106 LOAD_NAME                3 (PASS)
            109 GET_ITER
        >>  110 FOR_ITER                67 (to 180)
            113 STORE_NAME               8 (X)

 23         116 LOAD_NAME                7 (KEYOUT)
            119 LOAD_ATTR                9 (append)
            122 LOAD_NAME               10 (ord)
            125 LOAD_NAME                8 (X)
            128 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            131 LOAD_NAME                5 (I)
            134 BINARY_ADD
            135 LOAD_NAME               10 (ord)
            138 LOAD_NAME                4 (KEY)
            141 LOAD_NAME                5 (I)
            144 BINARY_SUBSCR
            145 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            148 BINARY_XOR
            149 LOAD_CONST              17 (255)
            152 BINARY_MODULO
            153 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            156 POP_TOP

 24         157 LOAD_NAME                5 (I)
            160 LOAD_CONST              18 (1)
            163 BINARY_ADD
            164 LOAD_NAME               11 (len)
            167 LOAD_NAME                4 (KEY)
            170 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            173 BINARY_MODULO
            174 STORE_NAME               5 (I)
            177 JUMP_ABSOLUTE          110
        >>  180 POP_BLOCK

 30     >>  181 LOAD_NAME                6 (SOLUCE)
            184 LOAD_NAME                7 (KEYOUT)
            187 COMPARE_OP               2 (==)
            190 POP_JUMP_IF_FALSE      206

 31         193 LOAD_NAME                1 (print)
            196 LOAD_CONST              19 ('You Win')
            199 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            202 POP_TOP
            203 JUMP_ABSOLUTE          219

 33     >>  206 LOAD_NAME                1 (print)
            209 LOAD_CONST              20 ('Try Again !')
            212 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            215 POP_TOP
            216 JUMP_FORWARD             0 (to 219)
        >>  219 LOAD_CONST              21 (None)
            222 RETURN_VALUE

On constate que le bytecode Python produit par l’interpréteur de référence CPython est :

• simple et lisible
• documenté
• un bytecode pour stack machine

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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#!/usr/bin/env python3

if __name__ == '__main__':
    print('Welcome to the RootMe python crackme')
    PASS = input('Enter the Flag: ')
    KEY = 'I know, you love decrypting Byte Code !'
    I = 5
    SOLUCE = [57, 73, 79, 16, 18, 26, 74, 50, 13, 38, 13, 79, 86, 86, 87]
    KEYOUT = []
    for X in PASS:
        KEYOUT.append(ord(X) + I ^ ord(KEY[I]) % 255)
        I = I + 1 % len(KEY)
    if SOLUCE == 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 :

1
2
3
4
5
6
7

#!/usr/bin/env ruby

SOLUCE = [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_a
I = 5
psw = 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 :

1
2

% ./breakit.rb
I_hate_RUBY_!!!

Si j’avais su ^^
Bon allez, testons cela :

1
2
3
4

% ./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 :

1
2
3
4
5
6
7

############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

Password : AAAAAAAA

Wrong password.

Maintenant, avec notre ami GDB :

1
2
3
4

(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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

(gdb) b main
Breakpoint 1 at 0x80483fe
(gdb) r
Starting program: /home/slaperche/Téléchargements/crackme/ch3.bin

Breakpoint 1, 0x080483fe in main ()
(gdb) disass
Dump of assembler code for function main:
   0x080483f0 <+0>:     lea    0x4(%esp),%ecx
   0x080483f4 <+4>:     and    $0xfffffff0,%esp
   0x080483f7 <+7>:     pushl  -0x4(%ecx)
   0x080483fa <+10>:    push   %ebp
   0x080483fb <+11>:    mov    %esp,%ebp
   0x080483fd <+13>:    push   %ecx
=> 0x080483fe <+14>:    sub    $0x14,%esp
   0x08048401 <+17>:    movl   $0x80c2888,-0xc(%ebp)
   0x08048408 <+24>:    push   $0x0
   0x0804840a <+26>:    push   $0x1
   0x0804840c <+28>:    push   $0x0
   0x0804840e <+30>:    push   $0x0
   0x08048410 <+32>:    call   0x8058a70 <ptrace>
   0x08048415 <+37>:    add    $0x10,%esp
   0x08048418 <+40>:    test   %eax,%eax
   0x0804841a <+42>:    jns    0x8048436 <main+70>
   0x0804841c <+44>:    sub    $0xc,%esp
   0x0804841f <+47>:    push   $0x80c2894
   0x08048424 <+52>:    call   0x80492d0 <puts>
   0x08048429 <+57>:    add    $0x10,%esp
   0x0804842c <+60>:    mov    $0x1,%eax
   0x08048431 <+65>:    jmp    0x80484f9 <main+265>
   0x08048436 <+70>:    sub    $0xc,%esp
   0x08048439 <+73>:    push   $0x80c28b0
   0x0804843e <+78>:    call   0x80492d0 <puts>
   0x08048443 <+83>:    add    $0x10,%esp
   0x08048446 <+86>:    sub    $0xc,%esp
   0x08048449 <+89>:    push   $0x80c28f0
   0x0804844e <+94>:    call   0x80492d0 <puts>
   0x08048453 <+99>:    add    $0x10,%esp
   0x08048456 <+102>:   sub    $0xc,%esp
   0x08048459 <+105>:   push   $0x80c2930
   0x0804845e <+110>:   call   0x80492d0 <puts>
   0x08048463 <+115>:   add    $0x10,%esp
   0x08048466 <+118>:   mov    $0x80c296e,%eax
   0x0804846b <+123>:   sub    $0xc,%esp
   0x0804846e <+126>:   push   %eax
   0x0804846f <+127>:   call   0x8048f60 <printf>
   0x08048474 <+132>:   add    $0x10,%esp
   0x08048477 <+135>:   mov    0x80e549c,%eax
   0x0804847c <+140>:   sub    $0x4,%esp
   0x0804847f <+143>:   push   %eax
   0x08048480 <+144>:   push   $0x9
   0x08048482 <+146>:   lea    -0x16(%ebp),%eax
   0x08048485 <+149>:   push   %eax
   0x08048486 <+150>:   call   0x8048f90 <fgets>
   0x0804848b <+155>:   add    $0x10,%esp
   0x0804848e <+158>:   lea    0x8048497,%eax
   0x08048494 <+164>:   inc    %eax
   0x08048495 <+165>:   jmp    *%eax
   0x08048497 <+167>:   mov    $0x8bea558a,%eax
   0x0804849c <+172>:   inc    %ebp
   0x0804849d <+173>:   hlt
   0x0804849e <+174>:   add    $0x4,%eax
   0x080484a1 <+177>:   mov    (%eax),%al
   0x080484a3 <+179>:   cmp    %al,%dl
   0x080484a5 <+181>:   jne    0x80484e4 <main+244>
   0x080484a7 <+183>:   mov    -0x15(%ebp),%dl
   0x080484aa <+186>:   mov    -0xc(%ebp),%eax
   0x080484ad <+189>:   add    $0x5,%eax
   0x080484b0 <+192>:   mov    (%eax),%al
   0x080484b2 <+194>:   cmp    %al,%dl
   0x080484b4 <+196>:   jne    0x80484e4 <main+244>
   0x080484b6 <+198>:   mov    -0x14(%ebp),%dl
   0x080484b9 <+201>:   mov    -0xc(%ebp),%eax
   0x080484bc <+204>:   inc    %eax
   0x080484bd <+205>:   mov    (%eax),%al
   0x080484bf <+207>:   cmp    %al,%dl
   0x080484c1 <+209>:   jne    0x80484e4 <main+244>
   0x080484c3 <+211>:   mov    -0x13(%ebp),%dl
   0x080484c6 <+214>:   mov    -0xc(%ebp),%eax
   0x080484c9 <+217>:   add    $0xa,%eax
   0x080484cc <+220>:   mov    (%eax),%al
   0x080484ce <+222>:   cmp    %al,%dl
   0x080484d0 <+224>:   jne    0x80484e4 <main+244>
   0x080484d2 <+226>:   sub    $0xc,%esp
   0x080484d5 <+229>:   push   $0x80c297a
   0x080484da <+234>:   call   0x80492d0 <puts>
   0x080484df <+239>:   add    $0x10,%esp
   0x080484e2 <+242>:   jmp    0x80484f4 <main+260>
   0x080484e4 <+244>:   sub    $0xc,%esp
   0x080484e7 <+247>:   push   $0x80c298e
   0x080484ec <+252>:   call   0x80492d0 <puts>
   0x080484f1 <+257>:   add    $0x10,%esp
   0x080484f4 <+260>:   mov    $0x0,%eax
   0x080484f9 <+265>:   mov    -0x4(%ebp),%ecx
   0x080484fc <+268>:   leave
   0x080484fd <+269>:   lea    -0x4(%ecx),%esp
   0x08048500 <+272>:   ret
End of assembler dump.

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 :

1
2
3
4
5

   0x08048408 <+24>:    push   $0x0
   0x0804840a <+26>:    push   $0x1
   0x0804840c <+28>:    push   $0x0
   0x0804840e <+30>:    push   $0x0
   0x08048410 <+32>:    call   0x8058a70 <ptrace>

correspond à :

1

ptrace(PTRACE_TRACEME, 0, NULL, NULL);

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.

1
2
3
4
5
6
7

(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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

   0x0804849e <+174>:   add    $0x4,%eax
   0x080484a1 <+177>:   mov    (%eax),%al
   0x080484a3 <+179>:   cmp    %al,%dl
   0x080484a5 <+181>:   jne    0x80484e4 <main+244>
   0x080484a7 <+183>:   mov    -0x15(%ebp),%dl
   0x080484aa <+186>:   mov    -0xc(%ebp),%eax
   0x080484ad <+189>:   add    $0x5,%eax
   0x080484b0 <+192>:   mov    (%eax),%al
   0x080484b2 <+194>:   cmp    %al,%dl
   0x080484b4 <+196>:   jne    0x80484e4 <main+244>
   0x080484b6 <+198>:   mov    -0x14(%ebp),%dl
   0x080484b9 <+201>:   mov    -0xc(%ebp),%eax
   0x080484bc <+204>:   inc    %eax
   0x080484bd <+205>:   mov    (%eax),%al
   0x080484bf <+207>:   cmp    %al,%dl
   0x080484c1 <+209>:   jne    0x80484e4 <main+244>
   0x080484c3 <+211>:   mov    -0x13(%ebp),%dl
   0x080484c6 <+214>:   mov    -0xc(%ebp),%eax
   0x080484c9 <+217>:   add    $0xa,%eax
   0x080484cc <+220>:   mov    (%eax),%al
   0x080484ce <+222>:   cmp    %al,%dl
   0x080484d0 <+224>:   jne    0x80484e4 <main+244>

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(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 :

1
2
3
4
5
6
7

(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 2⁶ = 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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(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 :

1
2
3
4
5
6
7
8

% ./ch3.bin
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

Password : easy

Good password !!!

Gagné !
Ça commence à devenir intéressant :–)

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.

1
2

% ./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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

% 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.

1
2
3
4
5
6

% ./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 :

1
2
3
4
5
6
7
8
9
10
11
12
13

% 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.

1
2
3
4
5
6

% ./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é!

Gagné !
Le mot de passe est donc 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 :

1
2
3
4
5
6
7

% ./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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

(gdb) b main
Breakpoint 1 at 0x8048317
(gdb) r
Starting program: ch2.bin

Breakpoint 1, 0x08048317 in main ()
(gdb) disass
Dump of assembler code for function main:
   0x08048309 <+0>:     lea    0x4(%esp),%ecx
   0x0804830d <+4>:     and    $0xfffffff0,%esp
   0x08048310 <+7>:     pushl  -0x4(%ecx)
   0x08048313 <+10>:    push   %ebp
   0x08048314 <+11>:    mov    %esp,%ebp
   0x08048316 <+13>:    push   %ecx
=> 0x08048317 <+14>:    sub    $0x24,%esp
   0x0804831a <+17>:    movl   $0x80a6b19,-0xc(%ebp)
   0x08048321 <+24>:    movl   $0x80a6b1e,-0x10(%ebp)
   0x08048328 <+31>:    movl   $0x80a6b2c,(%esp)
   0x0804832f <+38>:    call   0x8048de0 <puts>
   0x08048334 <+43>:    movl   $0x80a6b6c,(%esp)
   0x0804833b <+50>:    call   0x8048de0 <puts>
   0x08048340 <+55>:    movl   $0x80a6bac,(%esp)
   0x08048347 <+62>:    call   0x8048de0 <puts>
   0x0804834c <+67>:    movl   $0x80a6bea,(%esp)
   0x08048353 <+74>:    call   0x8048db0 <printf>
   0x08048358 <+79>:    mov    -0x8(%ebp),%eax
   0x0804835b <+82>:    mov    %eax,(%esp)
   0x0804835e <+85>:    call   0x804826a <getString>
   0x08048363 <+90>:    mov    %eax,-0x8(%ebp)
   0x08048366 <+93>:    mov    -0xc(%ebp),%eax
   0x08048369 <+96>:    mov    %eax,0x4(%esp)
   0x0804836d <+100>:   mov    -0x8(%ebp),%eax
   0x08048370 <+103>:   mov    %eax,(%esp)
   0x08048373 <+106>:   call   0x80502f0 <strcmp>
   0x08048378 <+111>:   test   %eax,%eax
   0x0804837a <+113>:   jne    0x80483d0 <main+199>
   0x0804837c <+115>:   movl   $0x80a6bf5,(%esp)
   0x08048383 <+122>:   call   0x8048db0 <printf>
   0x08048388 <+127>:   mov    -0x8(%ebp),%eax
   0x0804838b <+130>:   mov    %eax,(%esp)
   0x0804838e <+133>:   call   0x804826a <getString>
   0x08048393 <+138>:   mov    %eax,-0x8(%ebp)
   0x08048396 <+141>:   mov    -0x10(%ebp),%eax
   0x08048399 <+144>:   mov    %eax,0x4(%esp)
   0x0804839d <+148>:   mov    -0x8(%ebp),%eax
   0x080483a0 <+151>:   mov    %eax,(%esp)
   0x080483a3 <+154>:   call   0x80502f0 <strcmp>
   0x080483a8 <+159>:   test   %eax,%eax
   0x080483aa <+161>:   jne    0x80483c2 <main+185>
   0x080483ac <+163>:   movl   $0x80a6c00,0x4(%esp)
   0x080483b4 <+171>:   movl   $0x80a6c0c,(%esp)
   0x080483bb <+178>:   call   0x8048db0 <printf>
   0x080483c0 <+183>:   jmp    0x80483dc <main+211>
   0x080483c2 <+185>:   movl   $0x80a6c52,(%esp)
   0x080483c9 <+192>:   call   0x8048de0 <puts>
   0x080483ce <+197>:   jmp    0x80483dc <main+211>
   0x080483d0 <+199>:   movl   $0x80a6c5f,(%esp)
   0x080483d7 <+206>:   call   0x8048de0 <puts>
   0x080483dc <+211>:   mov    $0x0,%eax
   0x080483e1 <+216>:   add    $0x24,%esp
   0x080483e4 <+219>:   pop    %ecx
   0x080483e5 <+220>:   pop    %ebp
   0x080483e6 <+221>:   lea    -0x4(%ecx),%esp
   0x080483e9 <+224>:   ret
End of assembler dump.

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

(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 :

1
2
3
4
5
6
7
8
9
10

(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.

1
2
3
4
5
6
7
8
9
10
11
12

(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.

1
2
3
4
5
6

(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 :

1
2
3
4
5
6
7
8

% ./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) :

1
2
3
4
5
6
7

% 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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

% 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 :

1
2
3
4
5
6
7

% ./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 ;–)

Normalement, mes deux prochains articles devraient être sur l’implémentation d’une structure de données générique sans usage de pointeur générique et sur la résolution d’un bug intéressant sur lequel je suis tombé.

N’ayant pas trop de temps/motivation pour bosser sur le premier, et le second dépendant un peu du premier, je ne publie rien depuis quelque temps. Pour remédier à cela, je vais faire une petite séries d’article sur la rétroingénierie.

Les exemples seront tirés du site Root-Me.org. Pour télécharger les binaires, il faut avoir un compte. Si vous ne voulez pas vous enregistrer, vous pouvez jeter un œil à bugmenot ;–)