Voyage en C++ie : un diamant d'innocence

Magazine
Marque
MISC
HS n°
Numéro
18
Mois de parution
novembre 2018
Domaines


Résumé

Cet article est le troisième d'une mini-série sur le C++, ou plutôt sur les binaires compilés depuis C++, leurs particularités, comment les concepts du langage se retrouvent parfois dans le binaire final.


Body

Cet opus corrige un oublie lors de l'épisode précèdent (Voyage en C++ie : les objets, publié dans MISC n°96), et présente le boss final : le fameux « deadly diamond of death ». Manquement d'autant plus intolérable dans une revue des Éditions Diamond…

1. Le problème du diamant

Imaginons la (mauvaise) hiérarchie de classe suivante, qui n'est pas sans rappeler certains jeux très ancrés dans l'imaginaire médiéval fantastique.

struct Fighter {
    int hp = 10;
    int chop() const;
};
 
struct Warrior : Fighter {
};
 
struct Monk : Fighter {
};

Osons maintenant créer un type de personnage bi-classé (et d'une humilité sans faille) :

struct Me : Warrior, Monk {
    void strike(Fighter& other) const {
        if(hp>0)
            other.hp -= chop();
    };
};

Ce code ne compile pas, et pour cause : Warrior et Monk ont une base commune, Fighter et l'accès à hp est ambigu. Quand on veut que les membres communs ne soient présents qu'une seule fois, et c'est le cas ici, on utilise l'héritage virtuel, le fameux héritage en diamant.

struct Warrior : virtual Fighter {
};
 
struct Monk : virtual Fighter {
};

Il n'y aura alors qu'une seule instance de Fighter instanciée par instance de Me (notez l'élégante référence à une célèbre licence de jeux de baston édités par SEGA).

2. Initialisation d'un objet avec héritage virtuel

Si l'on tente d'instancier un objet de la classe Me :

Me spontaneaous_me() {
    return {};
}

On obtient le bitcode LLVM suivant (d'après clang++ -S -emit-llvm -O0 -o - diamond.cpp -std=c++11 | c++filt, on regardera le code optimisé une fois qu'on a bien tout compris) que nous allons décortiquer. Notons le filtrage par c++filt pour appliquer le demangling (décodage des symboles, cf. épisodes précédents disponibles chez tous les bons libraires) sur le bitcode LLVM, cette commande est bien pensée ! J'ai enlevé quelques attributs (genre align 8 sur les store) pour ne garder que l'essentiel.

define linkonce_odr void @Me::Me()(%struct.Me*) {
  ; copy parameter to a register through the stack,

  ; let's call this register `this'
  %2 = alloca %struct.Me*
  store %struct.Me* %0, %struct.Me** %2
  %3 = load %struct.Me*, %struct.Me** %2
  ; access the 16th byte of `this' and

  ;cast it to Fighter* to initialize it
  %4 = bitcast %struct.Me* %3 to i8*
  %5 = getelementptr inbounds i8, i8* %4, i64 16
  %6 = bitcast i8* %5 to %struct.Fighter*
  call void @Fighter::Fighter()(%struct.Fighter* %6)
 
  ; cast this as warrior and call a specific constructor

  ;that uses the 1st element of the VTT
  %7 = bitcast %struct.Me* %3 to %struct.Warrior*
  call void @Warrior::Warrior()(%struct.Warrior* %7, i8** getelementptr inbounds ([4 x i8*], [4 x i8*]* @VTT for Me, i64 0, i64 1))
 
  ; access the 8th byte of `this' and

  ;cast it to Monk* to initialize it
  %8 = bitcast %struct.Me* %3 to i8*
  %9 = getelementptr inbounds i8, i8* %8, i64 8
  %10 = bitcast i8* %9 to %struct.Monk*
  call void @Monk::Monk()(%struct.Monk* %10, i8** getelementptr inbounds ([4 x i8*], [4 x i8*]* @VTT for Me, i64 0, i64 2))
 
  ;;;;;;;;;;;;;;;; PAUSE ;;;;;;;;;;;;;;;;
 
  ; store values from the vtable in the 0st bytes of `this'
  %11 = bitcast %struct.Me* %3 to i32 (...)***
  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i32 (...)**), i32 (...)*** %11,
 
  ; store other values from the vtable in the 8th bytes of `this'
  %12 = bitcast %struct.Me* %3 to i8*
  %13 = getelementptr inbounds i8, i8* %12, i64 8
  %14 = bitcast i8* %13 to i32 (...)***
  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 1, i32 3) to i32 (...)**), i32 (...)*** %14
  ret void
}

Mmmmh, notre diamant a de multiples facettes qui reflètent autant de subtilités du langage ! On retrouve bien les constructeurs de chaque classe parente @Fighter::Fighter, @Warrior::Warrior et @Monk::Monk(), mais les deux derniers constructeurs prennent un nouveau paramètre, la VTT, la Virtual Table Table… Qu'est-ce donc ? Regardons son initialisation, en s'arrêtant à la ; PAUSE ; :

@VTT for Me = constant [4 x i8*] [
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @construction vtable for Warrior-in-Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @construction vtable for Monk-in-Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 1, i32 3) to i8*)
]

Okay… On parle de construction vtable for Warrior-in-Me et de construction vtable for Monk-in-Me, inspectons cela :

@construction vtable for Warrior-in-Me = constant { [3 x i8*] } { [3 x i8*] [
    i8* inttoptr (i64 16 to i8*),
    i8* null,
    i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64 }* @typeinfo for Warrior to i8*)
] }
@construction vtable for Monk-in-Me = constant { [3 x i8*] } { [3 x i8*] [
    i8* inttoptr (i64 8 to i8*),
    i8* null,
    i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64 }* @typeinfo for Monk to i8*)
] }

Soit, un pointeur à null, des typeinfo et un entier qui ressemble à un offset… regardons comment cette VTT est utilisée par les constructeurs :

define void @Warrior::Warrior()(%struct.Warrior*, i8**) {
  : typical copy-arg-to-stack-then-load
  %3 = alloca %struct.Warrior*
  %4 = alloca i8**
  store %struct.Warrior* %0, %struct.Warrior** %3
  store i8** %1, i8*** %4
  %5 = load %struct.Warrior*, %struct.Warrior** %3
  %6 = load i8**, i8*** %4
 
  ; %5 = `this', %6 = `construction vtable for Warrior-in-Me'
  %7 = load i8*, i8** %6
  %8 = bitcast %struct.Warrior* %5 to i32 (...)***
  %9 = bitcast i8* %7 to i32 (...)**
 
  ; the VTT is stored in `this'
  store i32 (...)** %9, i32 (...)*** %8
  ret void
}

Le même schéma se retrouve pour l'appel au constructeur de Monk, on a donc maintenant une idée un peu plus précise de l’organisation mémoire du bouzin à la ; PAUSE ; :

---------------------------------------
 construction vtable for Warrior-in-Me
---------------------------------------
  construction vtable for Monk-in-Me
---------------------------------------
           actual attributes
---------------------------------------

Et si on continue après la ; PAUSE ;, on voit que les deux premiers champs sont écrasés par les vtables des deux parents ! En fait, les construction vtable for Warrior-in-Me et construction vtable for Monk-in-Me sont des tables temporaires qui permettent de construire l'objet alors qu'il n'est pas encore complètement initialisé. Effectivement, si on appelle une méthode virtuelle dans le constructeur de Warrior, l'ordre de résolution sera différent que si on l'appelle depuis le constructeur de Me, d'où cette rustine temporaire de la vtable. Extra !

Comme notre exemple est trop simple, ces tables ne sont pas vraiment utiles, comme le montre le code craché par clang en -02 :

define void @spontaneaous_me()(%struct.Me* noalias nocapture sret) {
  ; first set everything to zero
  %2 = bitcast %struct.Me* %0 to i8*
  tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 24, i32 8, i1 false)
 
  ; store the actual attribute in the 2nd slot
  %3 = getelementptr inbounds %struct.Me, %struct.Me* %0, i64 0, i32 2, i32 0
  store i32 10, i32* %3
 
  ; store the two vtables in the 0th and 1st slot
  %4 = bitcast %struct.Me* %0 to <2 x i32 (...)**>*
  store <2 x i32 (...)**> <i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i64 0, i32 1, i64 0) to i32 (...)**), i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i64 1, i32 0, i64 0) to i32 (...)**)>, <2 x i32 (...)**>* %4
  ret void
}

Comme les vtable temporaires ne sont pas utilisées, l'optimiseur les a proprement dégagées. On remarquera combien l'optimisation faite par clang est raccord avec le discours :-)

Vérification par le code :

int main() {
  Me me = spontaneaous_me();
  void* raw = &me;
  void** as_ptr = (void**)raw;
  printf("%p - %p - %p\n", as_ptr[0], as_ptr[1], as_ptr[2]);
  return 0;
}

Qui à l'exécution affiche le tant attendu résultat :

$ ./diamond
0x4008a0 - 0x4008b8 - 0xa

Et un petit objdump -C -t diamond | grep 4008 nous confirme que la vtable de Me prend 48 octets chargés de 0x400888 à 0x4008b8, on est bon !

3. Poussière de diamant

Continuons avec un scénario d'apparence banale :

int chop(Me const& ref) {
    return ref.chop();
}

Une fois compilé sans optimisation, on obtient ce gros pavé, commenté au fil de l'eau :

define i32 @chop(Me&)(%struct.Me* dereferenceable(24)) #4 {

; copy-arg-to-stack-then-load-to-ref

%2 = alloca %struct.Me*

store %struct.Me* %0, %struct.Me** %2

%3 = load %struct.Me*, %struct.Me** %2

 

; load the first pointer inthis, i.e. the vtable for Warrior

%4 = bitcast %struct.Me* %3 to i8** %5 = load i8*, i8** %4

 

; access an element before this vtable, taking advantage of the vtable layout for Me

%6 = getelementptr i8, i8* %5, i64 -24

%7 = bitcast i8* %6 to i64*

%8 = load i64, i64* %7

 

; perform a small correction of thethisptr using the value from the vtable

%9 = bitcast %struct.Me* %3 to i8*

%10 = getelementptr inbounds i8, i8* %9, i64 %8

%11 = bitcast i8* %10 to %struct.Fighter*

%12 = call i32 @Fighter::chop() const(%struct.Fighter* %11)

ret i32 %12

}

L'offset de -24 peut paraître surprenant ! Mais si on se souvient de l'initialisation du premier champ de this, c'était à travers :

store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i32 (...)**), i32 (...)*** %11

Soit le 4ème élément du premier élément du tableau @vtable for Me qui n'en contient que 3… Donc le premier du deuxième élément. Et en reculant de 24 octets, on tombe (ouille) sur le premier champ du premier item, à savoir :

@vtable for Me = constant { [3 x i8*], [3 x i8*] } {
    [3 x i8*] [i8* inttoptr (i64 16 to i8*), i8* null, i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @typeinfo for Me to i8*)],
    [3 x i8*] [i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 -8 to i8*), i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @typeinfo for Me to i8*)]
}

Soit la valeur 0x10. Dans le doute, le code suivant permet de le confirmer :

int main() {
  Me me = spontaneaous_me();
  void* raw = &me;
  void** as_ptr = (void**)raw;
  void* vtable = as_ptr[0];
  printf("%p",(void*)*(intptr_t*)((char*)vtable -24));
  return 0;
}

À l’exécution, on obtient :

$ ./diamond
0x10

Ouf ! Ce petit ajustement de +16 permet de repositionner this après les deux vtable des classes filles, de façon à ce que this ressemble à une instance de Fighter normale :-)

Conclusion

Cette exploration de code devrait avoir un peu démystifié le diagramme en diamant à la sauce C++, avec pour effet de bord une piqûre de rappel sur les vtables. Comme quoi il y avait de quoi creuser !

Remerciements

Cet article a bénéficié des conseils et relectures de neitsa, papa zours et lancelot. Un grand merci à eux !

 



Articles qui pourraient vous intéresser...

Identification automatique de signaux grâce à la fonction d’autocorrélation

Magazine
Marque
MISC
HS n°
Numéro
22
Mois de parution
octobre 2020
Domaines
Résumé

Vous connaissiez la chasse au trésor… Initiez-vous maintenant à la chasse au signal (signal hunting en anglais). La chasse au signal consiste à rechercher les signaux qui nous entourent dans l’espace invisible du spectre électromagnétique. Mais plus besoin de rester l’oreille collée sur un haut-parleur à tourner le bouton pour régler la fréquence. La SDR (Software Defined Radio) a révolutionné tout cela : une radio numérique et un PC est vous voilà armé pour découvrir ce monde que les professionnels dénomment le SIGINT (SIGnal INTelligence).

Avec le Spanning Tree Protocol, suis-je en sécurité dans mon réseau ?

Magazine
Marque
MISC
HS n°
Numéro
22
Mois de parution
octobre 2020
Domaines
Résumé

Dans le cadre des hors-séries sur les retours aux fondamentaux, cet article aura comme sujet le protocole STP (Spanning Tree Protocol). Inventé en 1985 par Radia Perlman, il permet principalement d’assurer une liaison réseau redondante et sans boucle. Ce protocole étant primordial au sein d’un réseau de moyenne à grande envergure, s’il n’est pas correctement configuré, cela pourra alors permettre à des attaquants de compromettre le réseau.

Simulation d’un ordinateur mécanique en scriptant sous FreeCAD

Magazine
Marque
Hackable
Numéro
35
Mois de parution
octobre 2020
Domaines
Résumé

L’évolution du traitement du signal est une histoire fascinante largement déroulée par David Mindell dans ses divers ouvrages [1] et citations [2]. Partant de l’ordinateur mécanique avec ses rouages, poulies, bielles et crémaillères, le passage à l’électrique au début du 20ème siècle, puis à l’électronique intégrée avec l’avènement du transistor et des circuits intégrés (VLSI) nous ont fait oublier les stades initiaux qui ont amené à notre statut actuel d’ordinateurs infiniment puissants, précis et compacts. Alors que cette histoire semble s’accompagner du passage de l’analogique au numérique – de la manipulation de grandeurs continues en grandeurs discrètes avec son gain en stabilité et reproductibilité – il n’en est en fait rien : un boulier fournit déjà les bases du calcul discrétisé mécanique, tandis que [3] introduit les concepts du calcul mécanique avec les traitements numériques avant de passer aux traitements analogiques.

Return oriented programming 101

Magazine
Marque
MISC
HS n°
Numéro
22
Mois de parution
octobre 2020
Domaines
Résumé

Le Returned Oriented Programming (ou ROP) est une technique permettant d'exploiter des programmes disposant de la protection NX (No eXecute) ou DEP (Data Execution Prevention). L'objectif de cet article est de vous présenter les bases du ROP, ainsi que l’exploitation pas-à-pas d’un programme d’entraînement via l'utilisation de la bibliothèque python pwntools [1]. Dans un souci de simplicité, la démonstration sera réalisée sur un programme s'exécutant sur un système Linux 64 bits. Bien entendu, cette démonstration reste applicable sur d'autres architectures (ARM, MIPS, etc.).