Autres
Introduction au reverse engineering

1. Qu’est-ce que le « reverse engineering »

Le « reverse » n’est pas une activitĂ© strictement informatique : on peut penser Ă  la formule du Coca-Cola qui a Ă©tĂ© analysĂ©e au spectrographe de masse, aux capsules de cafĂ© dites « compatibles », Ă  la fabrication d’accessoires pour l’iPhone 5 (dont Apple n’a pas publiĂ© les spĂ©cifications), etc.
À la limite de l’informatique, il existe Ă©galement une forte activitĂ© autour du « reverse » de cartes Ă©lectroniques, de bitstreams FPGA, voire de composants Ă©lectroniques. Cette activitĂ© existe depuis fort longtemps, par exemple dans le domaine de la tĂ©lĂ©vision sur abonnement (Pay TV), mais elle devient de plus en plus prĂ©sente dans les confĂ©rences de sĂ©curitĂ©, Ă  mesure que la sĂ©curitĂ© descend dans les couches matĂ©rielles via des TPM et autres processeurs « ad-hoc ». Portes d’hĂŽtel, bus automobiles, microcode des cartes Wi-Fi, tĂ©lĂ©phones par satellite, femtocells, routeurs et autres Ă©quipements embarquĂ©s deviennent des objets d’étude pour les « hackers ». À titre anecdotique, on peut par exemple citer le projet 3DBrew [1] qui compte « libĂ©rer » la console Nintendo 3DS en dĂ©capsulant le processeur Nintendo pour en extraire les clĂ©s privĂ©es par microscopie Ă©lectronique.
Dans le domaine de la sécurité informatique, le « reverse » est souvent considéré comme le « Graal » des compétences, à la limite de la sorcellerie. Pénétrons donc dans le territoire des arts obscurs.

2. L’épine lĂ©gislative

La question rĂ©currente liĂ©e Ă  la pratique du « reverse » en France est lĂ©gale : que risque-t-on Ă  s’afficher publiquement « reverser » ? Le Malleus Maleficarum nous indique qu’il faut transpercer chaque grain de beautĂ© du suspect Ă  l’aide d’une aiguille : si la plaie ne saigne pas, nous sommes en prĂ©sence d’un sorcier. Et je ne vous parle pas des techniques dĂ©ployĂ©es par l’ANSSI 

« Je ne suis pas juriste », mais il me semble que la rĂ©ponse Ă  la question lĂ©gislative n’a aucune importance. Si vous ĂȘtes du cĂŽtĂ© lumineux de la Force – par exemple, que vous analysez des virus pour dĂ©sinfecter un parc d’entreprise (voire que vous Ă©ditez un antivirus français) – ni l’auteur du virus, ni le procureur de la RĂ©publique ne vous inquiĂ©teront pour ce fait.
Si par mĂ©garde vous cheminez sur les sentiers obscurs du cracking et de keygening, vous passerez sous les fourches caudines de l’autoritĂ© publique pour un motif quelconque. N’oublions pas que dans la plus cĂ©lĂšbre affaire judiciaire de « reverse » française – la sociĂ©tĂ© Tegam contre Guillermito – ce dernier a Ă©tĂ© condamnĂ© du fait qu’il n’avait pas acquis de licence pour le logiciel objet de son Ă©tude

Le point juridique étant évacué, entrons désormais dans le vif du sujet.

3. « Reverse engineering » vs. « cracking »

Le vrai « reverse » est une discipline noble et exigeante. Elle consiste Ă  comprendre entiĂšrement un logiciel au point d’en produire une copie interopĂ©rable. Les exemples sont nombreux : projet Samba (dont la version 4 peut se substituer Ă  un contrĂŽleur de domaine Microsoft Active Directory), nombreux pilotes Linux et codecs, algorithme RC4 (republiĂ© en 1994 sous le nom de ARC4 pour « Alleged RC4 »), etc.
Il s’agit d’une activitĂ© trĂšs diffĂ©rente de la recherche et de l’exploitation de failles logicielles, ou du « dĂ©plombage » de logiciels commerciaux. Il est regrettable de recevoir de nombreux CV mentionnant la compĂ©tence « reverse engineering », alors que le candidat ne sait que suivre un flot d’exĂ©cution Ă  la main dans son dĂ©bogueur (technique dite du « F8 »), jusqu’à trouver l’instruction « JNZ » qui va contourner la quasi-totalitĂ© des systĂšmes de licence Ă©crits « Ă  la main ».

4. Bestiaire Monstrueux

MĂȘme en se limitant au logiciel informatique, la notion de « reverse » couvre un pĂ©rimĂštre excessivement large : du code embarquĂ© dans un microcontrĂŽleur Ă  une application Java, en passant par les « bonnes vieilles » applications en C.
Avant de traiter du cƓur du sujet – Ă  savoir les langages compilĂ©s (C/C++/Objective-C/
), feuilletons le reste du bestiaire que tout apprenti doit connaĂźtre.

4.1 Assembleur

Les applications les plus bas niveaux (BIOS, firmwares, systĂšmes d’exploitation, jeux pour consoles archaĂŻques, applications MS-DOS, etc.) sont gĂ©nĂ©ralement largement Ă©crites en assembleur. Dans ce cas, il n’y a guĂšre d’alternatives : il est strictement nĂ©cessaire de connaĂźtre trĂšs finement l’architecture de la plateforme matĂ©rielle cible, ainsi que les instructions du processeur rĂ©servĂ©es aux opĂ©rations bas niveau (initialisation matĂ©rielle, etc.).
Ce cas est gĂ©nĂ©ralement rĂ©servĂ© Ă  des spĂ©cialistes et ne sera pas couvert dans la suite de l’article.

4.2 Bytecode

PlutĂŽt que de livrer des applications compilĂ©es pour un processeur existant, certains environnements de dĂ©veloppement compilent dans un langage intermĂ©diaire de haut niveau, appelĂ© « bytecode ». Un environnement d’exĂ©cution (la « machine virtuelle ») doit ĂȘtre fourni pour chaque plateforme matĂ©rielle sur laquelle doit s’exĂ©cuter ce langage intermĂ©diaire.
Le lecteur Ă©veillĂ© pense immĂ©diatement aux environnements Java et .NET, mais l’utilisation de « bytecode » est beaucoup plus rĂ©pandue : on peut citer Flash ActionScript, Visual Basic 6 et son P-Code, les langages de script comme Python (fichiers PYC/PYO), mais aussi 
 les protections logicielles.
On peut disserter sans fin des avantages et des inconvĂ©nients d’un « bytecode » par rapport Ă  du code « natif » d’un point de vue gĂ©nie logiciel. Ce qui est sĂ»r, c’est que la quasi-totalitĂ© des « bytecodes » qui n’ont pas Ă©tĂ© conçus dans une optique de protection logicielle se dĂ©compilent sans aucune difficultĂ© sous forme de code source original. Je vous renvoie Ă  vos outils favoris pour cette opĂ©ration (JD-GUI pour Java, Reflector pour .NET, Uncompyle2 pour Python, etc.).

4.3 Cas des protections logicielles

La protection logicielle est au reverse engineering ce que la nĂ©cromancie est Ă  la divination : ce sont deux Ă©coles qui procĂšdent selon les mĂȘmes principes, mais que tout oppose. Et tandis que tout le monde consulte son voyant, peu nombreux sont ceux qui admettent lever les morts.
NĂ©anmoins, il ne faut pas se mentir : l’étude des protections logicielles constitue la meilleure Ă©cole pour apprendre rapidement le reverse engineering. Sites de « crackmes », tutoriels, outils, tout est lĂ  pour qui veut brĂ»ler les Ă©tapes. Plus rapide, plus sĂ©duisant, mais pas plus puissant est le « cracking ». Seule la maĂźtrise de l’algorithmique et de la thĂ©orie de la compilation permettra d’atteindre la transcendance.
Les protections logicielles sont gĂ©nĂ©ralement mises en Ɠuvre pour protĂ©ger la gestion des licences logicielles, d’oĂč le caractĂšre sulfureux de leur analyse. Il faut noter toutefois qu’il existe d’autres cas d’usage, comme par exemple :
  • La protection d’algorithmes contre l’analyse par des clients lĂ©gitimes du logiciel (ex. Skype) ;
  • La protection de codes malveillants contre l’analyse par les Ă©diteurs antivirus (ex. rootkit TDL-4) ;
  • La protection de « cracks » contre l’analyse par les Ă©diteurs (ex. crack pour Windows Vista simulant un BIOS OEM [2]).
Ces derniers cas lĂ©gitiment grandement l’activitĂ© de reverse engineering des protections logicielles. Vous pouvez donc poursuivre la lecture de cet article sans craindre pour votre Ăąme.
Une « bonne » protection doit rĂ©sister aussi bien Ă  l’analyse statique qu’à l’analyse dynamique de la cible. L’objet de cet article introductif n’est pas d’énumĂ©rer toutes les techniques mises au point dans le jeu du chat et de la souris entre « crackers » et Ă©diteurs de protection, mais il existe grosso modo deux grandes classes de protections logicielles utilisĂ©es actuellement :
  • Les protections externes (dites « packers »). Ces protections visent Ă  « enrober » le logiciel original dans une couche de protection. Le logiciel est chiffrĂ© contre l’analyse statique. Il est dĂ©chiffrĂ© en mĂ©moire Ă  l’exĂ©cution, mais des protections anti-dĂ©bogage et anti-dump permettent d’éviter une rĂ©cupĂ©ration trop facile du code.
  • Les protections internes (dites « obfuscateurs »). Le principe est de rĂ©Ă©crire le code assembleur du logiciel afin de le rendre inintelligible aux Moldus. Plusieurs techniques ont Ă©tĂ© expĂ©rimentĂ©es : transformation du code assembleur en bytecode (vulnĂ©rable Ă  un « class break » si la machine virtuelle est analysĂ©e), insertion de code mort ou complexe Ă  Ă©valuer statiquement, rĂ©Ă©criture du graphe de contrĂŽle (« code flattening »), etc. Il s’agit d’un domaine de recherche trĂšs actif, y compris dans le monde acadĂ©mique.
À titre anecdotique, les systĂšmes de contrĂŽle de licence sont Ă  classer dans plusieurs catĂ©gories :
  • Les protections matĂ©rielles (dongles) : trĂšs puissantes, mais assez rares aujourd’hui, sauf pour du logiciel trĂšs haut de gamme. Le principe consiste Ă  dĂ©porter une partie des traitements dans un composant Ă©lectronique (clĂ© USB « intelligente ») supposĂ© inviolable. Plus le traitement dĂ©portĂ© est complexe, plus il sera difficile Ă  comprendre en boĂźte noire. Un logiciel qui se contenterait de vĂ©rifier la prĂ©sence du susdit dongle sans jamais s’en servir serait bien sĂ»r condamnĂ© Ă  finir sur Astalavista.
  • NumĂ©ro de sĂ©rie ou fichier de licence : la cryptographie moderne autorise des schĂ©mas thĂ©oriquement inviolables, si l’implĂ©mentation est correcte. Mais mĂȘme un systĂšme inviolable peut ĂȘtre piraté  en remplaçant la clĂ© publique de l’éditeur dans le binaire !
  • Activation en ligne : le logiciel vĂ©rifie qu’il dispose du droit de s’exĂ©cuter auprĂšs d’un serveur tiers. Dans les cas les plus Ă©laborĂ©s, une partie des traitements est effectuĂ©e en ligne – mais cette situation n’est pas toujours acceptable par le client.

5. Les Piliers du Temple

Entrons maintenant dans le vif du sujet : quelles sont les compĂ©tences requises pour s’attaquer Ă  une application « native », compilĂ©e depuis un langage relativement courant (tel que le C) ?
De mon expérience, elles sont au nombre de quatre.

5.1 Connaütre l’assembleur cible

Il n’est absolument pas nĂ©cessaire de connaĂźtre par cƓur le manuel de rĂ©fĂ©rence du processeur ! À titre d’exemple, le jeu d’instructions des processeurs x86 et x64 contient une majoritĂ© d’instructions en virgule flottante, rarement rencontrĂ©es et dont la sĂ©mantique est impossible Ă  mĂ©moriser.
Par ailleurs, les compilateurs n’utilisent qu’un sous-ensemble rĂ©duit du jeu d’instructions, comme on le verra plus tard.
Il est par contre de bon ton de connaĂźtre les spĂ©cifiĂ©s du processeur cible. Sur architectures x86 et x64, ce sont par exemple la segmentation et les registres implicites. Sur architecture SPARC ce sont les registres glissants et les « delay slots » (qu’on retrouve Ă©galement sur MIPS). Il existe des architectures encore plus exotiques telles que les processeurs VLIW (Very Long Instruction Word).

5.2 Savoir développer

N’oublions pas que le reverse engineering logiciel consiste Ă  comprendre ce qu’a Ă©crit le dĂ©veloppeur d’origine. Il est donc fortement recommandĂ© de savoir soi-mĂȘme dĂ©velopper dans le langage cible

Il est amusant de constater qu’il existe des modes dans les « design patterns ». Si le code Sendmail est truffĂ© de constructions setjmp/longjmp/goto dĂ©sormais obsolĂštes, le tout nouveau C++11 autorise bien d’autres acrobaties

Par ailleurs, chaque dĂ©veloppeur a ses lubies. Il ne s’agit donc pas de savoir programmer, mais d’avoir une idĂ©e de comment programment les autres
 La lecture rĂ©guliĂšre de code issu de projets open source – ou la consultation de forums d’aide aux dĂ©veloppeurs – permet de se faire une idĂ©e de l’extrĂȘme libertĂ© que confĂšre le code.

5.3 Connaissance du compilateur

N’oublions pas que le code assembleur n’est qu’une libre interprĂ©tation du code de haut niveau Ă©crit par l’humain. Le compilateur a la charge de produire un code fonctionnellement identique, mais qui peut ĂȘtre structurellement trĂšs diffĂ©rent. Nous reviendrons plus tard sur les optimisations proposĂ©es par les compilateurs, mais si vous ĂȘtes du genre Ă  encore penser que vous pouvez faire mieux qu’un compilateur moderne « Ă  la main », arrĂȘtez-vous et lisez immĂ©diatement la formation de Rolf Rolles intitulĂ©e « Binary Literacy – Optimizations and OOP » [3].
La diversitĂ© des compilateurs s’est considĂ©rablement rĂ©duite ces derniers temps (il devient rare de rencontrer les compilateurs de Borland, Watcom ou Metrowerks). Les deux survivants sont GCC et Visual Studio – avec LLVM en challenger, et une mention spĂ©ciale pour le compilateur Intel (ICC), qui est capable de produire du code incroyablement optimisĂ© – et donc totalement illisible.
MĂȘme s’il ne reste que deux compilateurs, il n’en reste pas moins que la liste des options de compilation proposĂ©es par GCC laisse rĂȘveur [4]. Or, le niveau d’optimisation, les options finline*, funroll* ou fomit-frame-pointer vont avoir des effets considĂ©rables sur le code gĂ©nĂ©rĂ©.

5.4 Reconnaissance de forme

C’est probablement la qualitĂ© essentielle du bon reverser. AprĂšs des milliers d’heures d’apprentissage, son cerveau reconnaĂźt immĂ©diatement toutes les structures « classiques », de la boucle « for »  Ă  l’implĂ©mentation DES en boĂźte blanche.
Je ne prĂ©tends absolument pas jouer dans cette catĂ©gorie – c’est d’ailleurs pour cela qu’on ne m’a confiĂ© que l’introduction – mais je crois qu’il m’a Ă©tĂ© donnĂ© d’approcher des gens rĂ©ellement hors du commun dans le domaine. Et je peux vous dire que c’est beau comme un concert de Rammstein.
Ce qui nous amĂšne Ă  la conclusion essentielle : seul un conditionnement du cerveau Ă  l’ñge oĂč sa plastique est maximale permet de produire un reverser d’exception. Si les Chinois mettent en place des camps d’entraĂźnement, on peut commencer Ă  craindre pour notre propriĂ©tĂ© intellectuelle. Et si la sĂ©curitĂ© informatique espĂšre encore recruter dans 10 ans, il serait temps de mettre http://crackmes.de/ au programme du collĂšge.

6. Another World

6.1 Analyse statique ou analyse dynamique ?

Les puristes vous diront que le vrai « reverser » ne fait que de l’analyse statique, c’est-Ă -dire de la lecture de code mort (Ă©ventuellement couplĂ©e Ă  un peu d’exĂ©cution symbolique). Il est vrai que cette approche est parfois la seule envisageable, par exemple lorsque la plateforme matĂ©rielle n’est pas disponible ou dĂ©bogable (ex. systĂšmes SCADA).
NĂ©anmoins, je ne serai pas aussi intransigeant et je vous prĂ©senterai l’autre approche moins Ă©lĂ©gante, mais plus « quick win » : il s’agit de l’analyse dynamique.
En effet, l’observation du logiciel en cours d’exĂ©cution permet d’identifier rapidement ses fonctions essentielles en « boĂźte noire ». Des outils comme Process Monitor, APIMonitor ou WinAPIOverride32 s’avĂšrent indispensables.

6.2 DĂ©marche pour l’analyse statique

Une dĂ©marche de reverse efficace ne commence pas bille en tĂȘte par la lecture du code assembleur. D’autres Ă©lĂ©ments plus facilement observables donnent rapidement des pistes essentielles.
  • Sections
Cela peut sembler une Ă©vidence, mais si votre cible contient 3 sections nommĂ©es UPX0, UPX1 et UPX2, vous gagnerez un temps prĂ©cieux Ă  utiliser la commande upx -d plutĂŽt que d’exĂ©cuter pas-Ă -pas le programme depuis le point d’entrĂ©e [5]

Il faut Ă©galement prĂȘter attention au dĂ©veloppeur malicieux, qui utilise une version modifiĂ©e du logiciel UPX pour induire en erreur l’analyste. C’est pourquoi des outils d’identification (tels que PEiD) proposent de rechercher les signatures applicatives des « packers » les plus courants.
  • Imports/exports
La liste des fonctions importĂ©es – lorsqu’elle est disponible – permet rapidement de se faire une idĂ©e des parties essentielles du programme : cryptographie, gĂ©nĂ©ration d’alĂ©a, accĂšs au rĂ©seau, etc.
Dans l’hypothĂšse oĂč l’application cible prend une « empreinte » de la plateforme matĂ©rielle pour gĂ©nĂ©rer un numĂ©ro d’installation unique par exemple, identifier les fonctions GetAdaptersAddresses() ou GetVolumeInformation() dans les imports donne des points d’entrĂ©e intĂ©ressants

  • Constantes
La plupart des algorithmes reposent sur des constantes « bien connues » : la chaĂźne de caractĂšres [email protected]#$% pour la gĂ©nĂ©ration des hashes LM, les constantes 0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476 pour MD5, etc.
D’autre part, de nombreuses implĂ©mentations « optimisĂ©es » reposent Ă©galement sur des tableaux prĂ©-calculĂ©s : c’est le cas pour DES, tous les algorithmes de CRC, etc.
Enfin, la plupart des algorithmes disposent d’une structure identifiable (nombre de tours, ordre des dĂ©calages, etc.).
  • ChaĂźnes de caractĂšres
Les chaĂźnes de caractĂšres sont des constantes particuliĂšres. Il n’existe pas de mĂ©thode scientifique pour explorer les chaĂźnes de caractĂšres, mais l’Ɠil humain repĂšre rapidement les chaĂźnes « intĂ©ressantes » : chaĂźnes encodĂ©es en Base64 ou en ROT13, chaĂźnes donnant des indications d’usage (comme User-Agent : Mozilla/4.0 ou BEGIN RSA PRIVATE KEY), copyrights, rĂ©fĂ©rences au code source, messages de dĂ©bogage, etc.
  • BibliothĂšques et code open source
Force est de constater que les dĂ©veloppeurs adorent la rĂ©utilisation de code, comme l’a encore dĂ©montrĂ© la rĂ©cente faille dans libupnp. OpenSSL, Boost, ZLib et LibPNG font Ă©galement partie des suspects habituels. La prĂ©sentation d’Antony Desnos sur les applications Android laisse rĂȘveur, sachant que certaines applications se composent Ă  95% de code publicitaire !
Il est donc strictement indispensable d’élaguer tout le code provenant des librairies standards fournies avec le compilateur, et tout le code issu des projets open source, avant de se concentrer sur la partie essentielle du code.
Il n’existe pas d’approche universelle dans le domaine, mais il existe au moins deux pistes intĂ©ressantes : la gĂ©nĂ©ration de signatures pour IDA avec l’outil FLAIR [6], et l’outil BinDiff [7]. Ce dernier Ă©tant basĂ© sur la comparaison de graphes, il est indĂ©pendant du langage assembleur : il est donc thĂ©oriquement possible de compiler OpenSSL sur Linux/x86, puis d’identifier les fonctions correspondantes dans un binaire Android/ARM par exemple.
Il existe des projets visant Ă  mutualiser l’échange de signatures entre « reversers », comme par exemple CrowdRE [8].
  • MĂ©tadonnĂ©es
Selon les technologies utilisĂ©es, le compilateur peut intĂ©grer dans le binaire des mĂ©tadonnĂ©es parfois trĂšs intĂ©ressantes : informations de dĂ©bogage, donnĂ©es RTTI pour le C++ (voire Ă  ce sujet l’article de Jean-Philippe LUYTEN dans MISC n°61), stubs des interfaces MS-RPC (cf. plugin mIDA), etc.
  • Traces et modes de dĂ©bogage
De (trop) nombreux logiciels disposent de fonctions de journalisation qui peuvent ĂȘtre rĂ©activĂ©es par une configuration spĂ©cifique (clĂ© de base de registre, variable d’environnement, conjonction astrale, etc.). La sortie de cette journalisation peut s’effectuer dans un fichier texte, un fichier au format Windows ETL, un dĂ©bogueur attachĂ© au processus, etc.
Non seulement les chaĂźnes de caractĂšres associĂ©es Ă  ces fonctions vont livrer des informations prĂ©cieuses pour l’analyse statique (comme les types ou les noms des champs dans les structures de donnĂ©es), mais ces traces vont Ă©galement considĂ©rablement accĂ©lĂ©rer l’analyse dynamique.
Je crois qu’on sous-estime grandement la valeur des versions « Checked Build » de Windows disponibles aux abonnĂ©s MSDN


6.3 Théorie de la compilation

Passons en revue quelques techniques « classiques » d’optimisation qu’il est de bon ton de connaĂźtre.
  • Alimentation du « pipeline » et prĂ©diction de branchement
Les processeurs modernes pratiquent la divination : ils exĂ©cutent des instructions au-delĂ  de la valeur courante du pointeur d’instruction (exĂ©cution spĂ©culative), dans l’ordre qui leur paraĂźt le plus efficace (rĂ©-ordonnancement). Cette optimisation est trĂšs efficace sur des instructions arithmĂ©tiques indĂ©pendantes - d’autant que le compilateur va entremĂȘler les instructions (scheduling) et allouer les registres en consĂ©quence - mais se heurte au problĂšme des sauts conditionnels.
La majoritĂ© des sauts conditionnels Ă©tant corrĂ©lĂ©s Ă  l’implĂ©mentation d’une boucle, le processeur applique l’heuristique suivante : les sauts en arriĂšre sont gĂ©nĂ©ralement pris, tandis que les sauts en avant ne sont gĂ©nĂ©ralement pas pris. Si le processeur s’est trompĂ© dans sa prĂ©diction, il doit annuler le commencement d’exĂ©cution de toutes les instructions qui ne seront finalement pas exĂ©cutĂ©es, ce qui est trĂšs coĂ»teux.
Le compilateur connaüt cette heuristique, ce qui lui permet d’optimiser les boucles et les tests conditionnels.
Sur architectures Intel x86 et x64, il est possible de contrĂŽler la prĂ©diction de branchement via des registres de configuration, voire d’enregistrer tous les branchements dans un buffer circulaire (Branch Trace Store) Ă  des fins de profiling.
Sur architecture ARM, toutes les instructions sont conditionnelles, ce qui permet des optimisations intéressantes, comme la suppression des sauts conditionnels pour les assignations simples (de type opérateur ternaire).
Le Pentium Pro (architecture P6) a introduit l’instruction d’assignation conditionnelle CMOV, qui permet le mĂȘme type d’optimisation. Il faut toutefois noter que le gain en performance n’est pas automatique, et que d’autres astuces (comme l’instruction SBB, qui prend en compte la valeur du « Carry Flag ») permettaient dĂ©jĂ  des optimisations.
  • Le dĂ©roulement de boucle
La meilleure solution pour Ă©viter le coĂ»t des sauts conditionnels
 c’est de les supprimer purement et simplement !
Si le compilateur connaĂźt Ă  l’avance le nombre d’itĂ©rations dans une boucle, et que le code gĂ©nĂ©rĂ© peut tenir entiĂšrement dans une page de code (soit 4 Ko sur architectures x86/x64), alors le compilateur copie/colle le code de la boucle autant de fois que nĂ©cessaire.
Cette construction est trĂšs courante dans les sĂ©quences d’initialisation d’algorithmes cryptographiques. Le code gĂ©nĂ©rĂ© semble anormalement long de prime abord, mais s’analyse trĂšs rapidement.
  • L’alignement
Par conception des microcircuits, il est beaucoup plus efficace de travailler Ă  la taille native des mots du processeur. Par exemple, une implĂ©mentation naĂŻve de memcpy() pourrait ĂȘtre :
for (i=0 ; i < len ; i++) dst[i] = src[i] ;
Aucune librairie C ne propose une implĂ©mentation aussi mĂ©diocre : travailler octet par octet sur un bus de 32 bits, c’est diviser par 4 la performance. Une meilleure implĂ©mentation de memcpy() serait la suivante :
  1. 1.
    En amont, s’assurer que dst et src sont allouĂ©s Ă  des adresses multiples de 4. Si les deux tableaux sont alignĂ©s sur 4 Ko et occupent donc un nombre minimal de pages en mĂ©moire, c’est encore mieux.
  2. 2.
    Copier len / 4 mots de 32 bits.
  3. 3.
    Copier les len % 4 octets restants.
C’est en substance l’implĂ©mentation qu’on trouve dans la librairie C de Windows XP (MSVCRT.DLL).
Bien entendu, des algorithmes plus complexes s’optimisent encore mieux. Je vous invite par exemple Ă  consulter l’implĂ©mentation de la fonction strlen() dans la librairie C du projet GNU (mais pas celle de BSD, qui est naĂŻve).
Si vous ĂȘtes sensible Ă  la beautĂ© du code, voici l’implĂ©mentation rĂ©elle de strlen() sur Mac OS 10.7 (64 bits), telle que reprĂ©sentĂ©e par l’outil otool :
_strlen:
pxor %xmm0,%xmm0
movl %edi,%ecx
movq %rdi,%rdx
andq $0xf0,%rdi
orl $0xff,%eax
pcmpeqb (%rdi),%xmm0
andl $0x0f,%ecx
shll %cl,%eax
pmovmskb %xmm0,%ecx
andl %eax,%ecx
je 0x000a250b
00000000000a2501:
bsfl %ecx,%eax
subq %rdx,%rdi
addq %rdi,%rax
ret
00000000000a250b:
pxor %xmm0,%xmm0
addq $0x10,%rdi
00000000000a2513:
movdqa (%rdi),%xmm1
addq $0x10,%rdi
pcmpeqb %xmm0,%xmm1
pmovmskb %xmm1,%ecx
testl %ecx,%ecx
je 0x000a2513
subq $0x10,%rdi
jmp 0x000a2501
  • « Inlining »
Comme les sauts conditionnels, l’appel de fonction est une opĂ©ration excessivement coĂ»teuse, surtout si la destination ne se trouve pas dans la mĂȘme page de code.
On notera au passage que le noyau Windows – ainsi que le logiciel Chrome [9] – font l’objet d’une optimisation post-compilation, qui consiste Ă  regrouper le code le plus souvent exĂ©cutĂ© dans quelques pages mĂ©moire, plutĂŽt que de le rĂ©partir dans tout le binaire (optimisation dite « OMAP » [10]). Il est mĂȘme optimal d’aligner le code sur la taille des lignes du cache d’instruction, soit 16 octets sur architectures x86 et x64.
Afin de limiter les appels de fonction, le compilateur peut dĂ©cider d’inclure le code de la sous-routine directement sur son lieu d’appel, comme dans les exemples ci-dessous.
strcpy()
strcmp()
Notez l’utilisation des instructions SCAS/MOVS/CMPS associĂ©es au prĂ©fixe REP, plutĂŽt qu’une construction de boucle beaucoup moins performante.
  • Les instructions interdites
Certaines instructions sont peu ou pas utilisĂ©es par les compilateurs. Il s’agit d’une optimisation liĂ©e au temps d’exĂ©cution de ces instructions. Par exemple, l’instruction LOOP nĂ©cessite 6 cycles d’horloge en cas de branchement sur processeur 80486. La sĂ©quence DEC ECX / JNZ xxx ne nĂ©cessite que 1 + 3 cycles pour la mĂȘme opĂ©ration.
A contrario, l’instruction LEA est couramment utilisĂ©e pour effectuer des additions entre constantes et registres, alors que ça n’est pas sa fonction premiĂšre.
La situation se complique encore, car le nombre de cycles par instruction est trĂšs variable d’un processeur Ă  l’autre. C’est pourquoi en fonction du processeur cible que vous spĂ©cifierez au compilateur Intel ICC, vous obtiendrez un code sensiblement diffĂ©rent

  • Multiplication et division
La multiplication et la division par une puissance de 2 s’implĂ©mentent par un simple dĂ©calage de bits : ce sont des opĂ©rations simples. Les mĂȘmes opĂ©rations avec des opĂ©randes arbitraires sont des opĂ©rations excessivement coĂ»teuses. À titre d’exemple, voici les durĂ©es d’exĂ©cution (en nombre de cycles d’horloge) de quelques instructions sur un processeur 80486 :
Opération
Opérande
Cycles
Multiplication
IMUL <reg32>
12 Ă  42
​
MUL <reg32>
13 Ă  42
Division
DIV <reg32>
40
​
IDIV <reg32>
43
DĂ©calage
SHL <reg>, <imm8>
2
Addition
ADD <reg>, <reg>
1
Pour multiplier X par 12, le compilateur va donc dĂ©couper l’opĂ©ration de la maniĂšre suivante : (X*8) + (X*4).
Pour diviser un nombre X sur 32 bits par 17, le compilateur peut ĂȘtre tentĂ© d’utiliser la multiplication rĂ©ciproque.
Selon l’algorithme d’Euclide Ă©tendu, l’inverse de 17 modulo 2^32 est 4042322161. Il suffit donc de multiplier X par ce nombre (modulo 2^32) pour obtenir le rĂ©sultat de la division.

6.4 Pratique de la décompilation

La compilation en langage assembleur provoque la perte d’informations essentielles, telles que le type de donnĂ©es. La dĂ©compilation (retour au code source d’origine) s’avĂšre donc ĂȘtre un problĂšme difficile. Ce domaine a stimulĂ© de nombreux travaux universitaires, qui sont pour la plupart restĂ©s du niveau de la « preuve de concept ».
Loin du Latex et autres CiteSeer, un maĂźtre du reverse engineering - auteur du logiciel IDA Pro – s’est un jour attaquĂ© au problĂšme. Combinant l’abondante thĂ©orie sur le sujet avec sa pratique de la chose et de nombreuses heuristiques par compilateur, il fabriqua par un matin blĂȘme la Pierre Philosophale de la dĂ©compilation : Hex-Rays Decompiler [11].
Aujourd’hui, cet outil intĂ©grĂ© Ă  IDA Pro dĂ©compile de maniĂšre tout Ă  fait correcte les assembleurs x86 et ARM, supporte l’enrichissement manuel du listing, mais permet Ă©galement le dĂ©bogage au niveau du code source reconstituĂ©. Il justifie donc largement son coĂ»t d’acquisition, relativement modique pour une entreprise.