==Phrack Inc.== Volume 0x0c, Issue 0x40, Phile #0x08 of 0x11 |=-----------------------------------------------------------------------=| |=-------=[ Audit Automatique de vulnérabilités du code machine ]=-------=| |=-----------------------------------------------------------------------=| |=-----------------------------------------------------------------------=| |=-------------------=[ By Tyler Durden ]=---------------------=| |=-------------------=[ ]=---------------------=| |=-----------------------------------------------------------------------=| |=---------------=[ Traduit par TboWan pour arsouyes.org ]=--------------=| I. Introduction a/ Sur le besoin d'audit automatique b/ Que sont les framework d'exploitation c/ Pourquoi n'est-ce pas un framework d'exploitation d/ Pourquoi n'est-ce pas du fuzzing e/ Audit de code machine : vraiment plus difficile que le source ? II. Préparation a/ Une première intuition b/ Analyses statiques vs dynamiques c/ Dépendances & prédicats - Analyse du flux de contrôle - Analyse du flux de données d/ Traduction en forme intermédiaires e/ Variables induites (variables dans les boucles) III. Analyse a/ Qu'est-ce qu'une vulnérabilité ? b/ Buffer overflows et intervalles numériques - Insensible au flux - Sensible au flux - Accélérer l'analyse par widening c/ Type-state checking - Fuites mémoire - Corruption du tas d/ Plus de problèmes - Analyse par prédicats - Analyse des alias et solution naïve - Conseil pour détecter les conditions de compétition IV. Chevarista : un analyseur de programmes binaires a/ Modélisation du projet b/ transformation de programmes c/ Vérification de vulnérabilités d/ Extraction de chemins vulnérables e/ Travaux futures : raffinement V. Travaux relatifs a/ Model Checking b/ Interprétation abstraite VI. Conclusion VII. Remerciements VIII. Références IX. Le code X. Notes du traducteur .::###########################################################::. Les logiciels ont des bugs. C'est un fait assez connu. ----------------------[ I. Introduction Dans cet article, nous allons parler de la conception d'un moteur pour l'analyse automatique de vulnérabilités de programmes compilés. Le code source de l'analyseur statique Chevarista est donné à la fin de ce document. Le but de ce papier n'est pas de dévoiler des 0days, mais de comprendre comment il peut être possible de les trouver sans intervention humaine (ou alors restreintes). Cependant, nous ne fournirons pas gentiment de résultats de notre audit automatique sur des binaires prédéfinis : à la place, nous utiliserons toujours des exemples génériques sur les difficultés les plus communes rencontrées quand on maudite ce genre de programme. Notre but est d'éclairer la communauté underground sur l'écriture de son propre analyseur statique et de ne pas être utile pour les compagnies de sécurité ou autres organisations à but lucratif. Au lieu d'aller directement au résultat de l'implantation proposée, nous allons introduire le domaine de l'analyse de programme, sans rentrer profondément dans la théorie (qui peut devenir très formelle), mais en prenant le point de vue d'un hacker fatigué de se concentrer sur un problème d'exploit spécifique et désireux de savoir jusqu'à quel point il est possible de trouver des vulnérabilités et les exploits correspondants automatiquement et sans intervention humaine. Chevarista n'a pas atteint cet objectif d'être cet outil complètement automatique, cependant, il ouvre la voie pour implémenter incrémentalement ce genre d'outil avec une généricité qui le rend capable de trouver n'importe quelle sorte de vulnérabilité définissable. Détecter toutes les vulnérabilités d'un programme donné peut être infaisable, et ceci pour plusieurs raisons. La première raison est qu'on ne peut prédire qu'un programme qui fonctionne sans arrêt aura ou non un bug. La deuxième raison est que si ce programme s'arrête un jours, le nombre d'états (c'est à dire de "contextes mémoires") qu'il a atteint et par lesquels il est passé avant de s'arrêter est très gros, et tester tous les chemins d'exécutions possibles va soit vous prendre toute votre vie, soit un gros cluster de machines dédiées y travaillant pendant des siècles. Puisque nous avons besoin de systèmes automatiques pour trouver les bugs à notre place, et que nous ne disposons pas d'une telle puissance de calcul, nous devons être ingénieux dans le choix de ce qui doit être analysé, à quel point nous pouvons être génériques pour raisonner sur les programmes, pour qu'un simple et petit analyseur puisse raisonner sur une grosse quantité de bugs de sortes différentes. Après tout, si les efforts ne valent pas la généricité, il serait probablement mieux d'auditer le code manuellement ce qui serait plus productif. Cependant, les systèmes automatiques ne sont pas limité à la recherche de vulnérabilités mais, à cause de leur relation étroite avec le programme analysé, peuvent trouver les conditions exactes dans lesquelles le bug à lieu, et quel est le contexte pour le générer. Mais certains pourraient me dire : "Le fuzzing n'est-il pas supposé le faire déjà ?". Ma réponse pourrait être : oui. Mais l'analyse statique est l'intelligence dans le fuzzing. Le fuzzing de programmes donne de très bons résultats mais tout bon fuzzer à besoin d'être conçu avec des orientations d'analyses statiques majeures. Cet article s'applique aussi d'une certaine manière au fuzzing mais l'implémentation proposée de l'analyseur Chevarista n'est pas un fuzzer. La première raison est que Chevarista n'exécute pas le programme pour l'analyser. À la place, il agit comme un (dé)compilateur mais effectue des analyses plutôt que de (re) traduire en code assembleur (ou code source). Il est donc bien plus efficace que le fuzzing mais requiert beaucoup de développement et de lecture de la littérature pour arriver à un outil automatique complet que chaque hacker rêve de maintenir. Un autre type égaré pourrait soutenir : "Ton truc ressemble plus ou moins à un environnement d'exploitation [NDT : exploitation framework], ce n'est pas nouveau." Les environnements d'exploitations sont en fait des trucs pas très neufs. Aucun d'entre eux n'analyse à la recherche de vulnérabilités, et ne fonctionnent en fait que si les exploits intégrés sont assez bons. C'est pourquoi Chevarista n'est pas CORE-Impact ni Metasploit : c'est un analyseur qui trouve les bugs dans les programmes et vous dit où ils sont. Un autre gros type au fond menacerait : "Il est purement impossible de trouver les vulnérabilités dans un code sans le source ..." et alors, beaucoup de gens se lèveraient et le déclarerait comme une prophétie, parce qu'il est déjà assez difficile de le faire avec le code source de toutes façons. Je mesurerais ce jugement par quelques remarques : pour certaines personnes, le code assembleur -est- le code source, et donc, avoir le code assembleur c'est comme avoir le code source, sans un certain nombre d'informations. C'est cette quantité d'informations perdues qu'on doit retrouver quand on écrit un décompilateur. Tout d'abord, nous n'avons pas les noms des variables, mais nommer les variables d'une manière différente n'affecte pas le résultat d'une analyse de vulnérabilités. Ensuite, nous n'avons pas les types de données, mais les types de données dans les programmes C compilés n'appliquent pas des propriétés sur les valeurs des variables (à causes de casts C ou d'un compilateur manquant de fortes vérifications des types). La seule réelle information qui soit obligatoire est la taille des variables en mémoire, qu'on peut retrouver à partir du code assembleur la plupart du temps. Ce n'est pas vrai pour les programmes C++ (ou d'autres programmes dans des langages de plus haut niveaux orientés objets ou fonctionnels), mais dans cet article, nous nous concentrerons principalement sur les programmes C compilés. Un opinion largement répandue sur l'analyse de programme est qu'elle est plus difficile à effectuer sur des langages (impératifs) de bas niveau que sur des langages (impératifs) de haut niveau. C'est vrai et faut, nous devons préciser un peut cette phrase. Spécifiquement, nous voulons comparer l'analyse d'un code C avec l'analyse d'un code assembleur : --------------------------------------------------------------------- | Informations disponibles| code C | code assembleur | |---------------------------------------------------------------------| | Noms de variables | Oui (explicite) | Non | |---------------------------------------------------------------------| | Noms des types | Oui (explicite) | Non | |---------------------------------------------------------------------| | Séquence de contrôle | Oui (explicite) | Oui (explicite) | |---------------------------------------------------------------------| | Structures de contrôle | Oui (explicite) | Oui (retrouvable)| |---------------------------------------------------------------------| | Dépendances de données | Oui (implicite) | Oui (implicite) | |---------------------------------------------------------------------| | Types de données | Oui (explicite) | Oui (retrouvable)| |---------------------------------------------------------------------| | Transfert de registres | Non | Oui (explicite) | |---------------------------------------------------------------------| | Instruction courante | Non | Oui (explicite) | --------------------------------------------------------------------- Parlons de ces points plus en détail : - La séquence de contrôle [NDT : control sequentiality] est évidement gardée dans l'assembleur, sinon, le processeur ne saurait pas comment exécuter le programme binaire. Cependant, le binaire ne contient pas un arbre d'exécution clairement structuré. Les conditions, mais surtout, les boucles n'apparaissent pas dans ce genre de code exécutable. Nous avons besoin d'une analyse préliminaire pour structurer le graphe de contrôle du flux. Ça a déjà été fait sur du code source et du code binaire en utilisant différents algorithmes que nous ne présentons pas dans cet article. - Les dépendances des données en sont pas explicites, même dans le source du programme, cependant, on peut le calculer précisément à la fois dans le code source et dans le code binaire. L'analyse du flux de donnée [NDT : data-flow] dans le code binaire est légèrement différente, parce qu'il contient chaque instruction de lecture et écriture entre les registres et la mémoire, et pas seulement au niveau des variable comme c'est le cas dans le code source. À cause de cela, le code assembleur contient plus d'instructions que le code source n'en contient. C'est à la fois un avantage et un désavantage. C'est un avantage parce qu'on peut tracer le flox plus densément au niveau machine, et c'est ce qui est nécessaire, particulièrement pour toutes sortes d'optimisations, ou de bugs spécifiques à la machine qui dépendent d'une certaine variable qui soit soit en mémoire ou dans un registre, etc. C'est un désavantage parce qu'on a besoin de plus de mémoire pour analyser ce genre de long listing de programme. - Les types de données sont explicites dans le source. La récupération des types est probablement l'information la plus difficile à récupérer depuis le code binaire. Cependant, ça a déjà été fait et l'approche que nous présentons dans ce papier est en définitive compatible avec les travaux existants en décompilation basée sur les types [NDT : type-based compilation]. Les types de données sont plus difficiles à récupérer quand on traite d'objets réels (comme les classes dans les programmes C++ compilés). Nous ne traiterons pas du problème de récupérer les classes dans cet article, puisque nous nous concentrerons sur les vulnérabilités liées à la mémoire. - Des anomalies au niveau des registres peuvent apparaître [DLB], ce qui peut être utile à un hacker pour créer un contexte de registre ou de mémoire lors de l'écriture d'un exploit. L'analyse de code au niveau binaire a cet avantage qu'il fournir une approche plus sûre pour la génération d'exploits sur des cibles existantes du monde réel. - Les informations au niveau des instructions sont encore une fois intéressantes pour être sûr de ne pas rater de bugs du compilateur lui-même [NDT-1]. C'est très académiquement respecté de coder un compilateur certifié qui prouve l'équivalence sémantique entre le code source et le code compilé. Mais du point de vue du hacker, ça ne veut pas dire grand chose. Une utilisation concrète dans la nature signifie un code concret, qui signifie de l'assembleur. En plus, c'est rare mais on a déjà été témoins de certaines irrégularités dans l'exécution de certains schémas d'instructions par le processeur. Une analyse au niveau des instructions peut les gérer, mais une analyse du source ne le peut pas. Une dernière raison que je mentionnerais est que le code source d'un projet est très verbeux. Si un analyseur de code est embarqué dans un périphérique important, soit le code source du logiciel dans le périphérique ne sera pas disponible, soit le périphérique manquera de mémoire ou de bande passante pour garder une copie accessible du code source. Un analyseur de code binaire n'a pas cette dépendance vis à vis du code source et peut donc être utiliser à plus large échelle. Pour résumer, il y a beaucoup de travail de récupération d'information avant de commencer à effectuer une analyse comme celles au niveau du source. Cependant, les seules informations qui ne sont pas disponibles après la récupération ne sont pas obligatoires pour l'analyse du code : le nom des types et des variables n'affectent pas l'exécution du programme. Nous allons abstraire ces noms et utiliser nos propres méthodes de nom mages dans notre analyse, comme présenté dans la prochaine section de ce papier. -------------[ II. Préparation Nous devons continuer avec les premiers souhaits et essayer de mieux comprendre quelles sont les vulnérabilités, comment on peut les détecter automatiquement, si nous sommes vraiment capables de générer des exploits à partir de l'analyse d'un programme sans jamais l'avoir exécuté. La réponse est oui et non et on doit la clarifier. La réponse est oui, parce que si vous savez comment caractériser exactement un bug, et si ce bug est détectable par un algorithme, alors on peut coder un programme qui va raisonner uniquement sur ces spécificités de la vulnérabilité connue-à-l'avance et convertir le code assembleur (ou source) vers une forme intermédiaire qui montrera où ces spécificités ont lieu, pour qu'une "signature" de la vulnérabilité puisse être trouvée si elle est présente dans le programme. La réponse est non car, avec une vulnérabilité inconnue, nous ne connaissons pas à l'avance les spécificités qui caractérisent sa signature. Ça signifie que nous devons prendre une signature approximative et vérifier le programme, mais les résultats pourrait être sur-approximé (beaucoup de faux positifs) ou sous-approximé (ne trouve rien mais quelques vulnérabilités existent sans avoir été détectées). Pendant que les tests par fuzzing ou boite noire sont des analyses dynamiques, le coeur de notre analyseur de n'est pas, mais il peut trouver un intérêt à lancer le programme dans un but différent du fuzzer. Ceux-ci tentent leur chance sur des entrées créées aléatoirement. Les fuzzers n'ont aucune connaissance *interne* du programme qu'ils analysent. C'est un problème majeur car un analyser dynamique qui est un fuzzer ne peut pas optimiser ou raffiner ses entrées en fonction d'événements qu'il ne peut observer. Un fuzzer peut par contre être couplé à un tracer [AD] ou un débogueur, pour que le fuzzing soit guidé par les connaissances du débogueur sur les états de la mémoire interne et des valeurs des variables pendant l'exécution du programme. Néanmoins, le réel concept d'un outil d'analyse de code doit être une solution intégrée, pour éviter de perdre encore plus de performances quand on utilise un débogueur externe (comme gdb qui est vraiment lent quand on utilise ptrace). Notre technique d'analyse est capable de prendre des décisions en fonction des états internes d'un programme sans même l'exécuter. Cependant, notre représentation d'état est abstraite : nous ne calculons pas tout le contenu de l'état mémoire réel à chaque étape d'exécution, mais considérons uniquement les informations utiles au comportement du programme en laissant automatiquement l'analyseur annoter le code avec des qualificatifs tels que "la prochaine instruction du programme va effectuer une allocation mémoire" [NDT-2] ou "Le registre R ou la case mémoire M va contenir un pointeur vers une région mémoire allouée dynamiquement". Nous expliquerons plus en détail les vérifications de propriétés relatives au tas dans le paragraphe sur [[type-state analysis]] de la partie III. Dans cette partie du papier, nous allons décrire une famille de formes intermédiaires qui recouvrent l'espace entre l'analyse de code sur un code structuré et l'analyse de code sur un code non-structuré (assembleur). Les conversions vers cette forme peuvent être faites à partir de code binaire (comme un décompilateur analysant) ou à partir du code source (comme un compilateur analysant). Dans cet article, nous allons transformer du code binaire vers un programme écrit dans une forme intermédiaire, et ensuite, effectuer toutes les analyses sur cette forme intermédiaire. Toutes les propriétés étudiées seront liées à l'analyse de flot de données [NDT-3]. Aucun flux de contrôle structuré n'est nécessaire pour les effectuer, un simple graphe du flux du contrôle (ou même une liste de blocs basics avec xrefs) peut être le point de départ de telles analyses. Soyons plus concrets et illustrons comment nous pouvons analyser les états internes d'un programme sans l'exécuter [NDT-4]. Nous commençons avec un bout de code très basique : Stub 1: ------- o : état interne if (a) / \ b++; -> o o /\ : division du flux de contrôle else \ / \/ : unification du flux de contrôle c--; o ------- Dans cet exemple simplissime, nous présentons un programme comme un graphe dont les noeuds sont les états et les arrêtes sont les dépendances du flot de contrôle. Qu'est-ce qu'un état interne ? Si nous voulons utiliser les informations de toutes les lignes du code, ces états doivent être des objets se souvenant des variables utilisées et modifiées (et aussi les flags du processeur). Alors, chacun de ces états de contrôle effectuera quelques opérations avant de sauter vers une autre partie du code (représentée par l'état interne des bout de code du if() et du else()). Une fois que le code du if/else est terminé, les deux chemins se rejoignent pour ne faire qu'un état, qui est l'état après avoir exécuté la partie conditionnelle. En fonction du niveau d'abstraction de l'analyse, l'état interne du programme contiendra plus ou moins d'informations à chaque étape du calcul. Par exemple, on doit différencier l'analyse du flux de contrôle (comme dans l'exemple précédent), et l'analyse du flux de données. Imaginez ce bout de code : Stub 2: ------- Code flux de contrôle flux de données avec les dépendances a ---o--- / \ \ / \ \ / c \ \ c = 21; o | o b o \ b = a; | | / \ / \ a = 42; o \/ ------ / if (b != c) / \ /\ |b != c| / a++; o o / \ ------ / else \ / / \ / \ / a--; o | a o a o c += a; | \ | / ------- o \ | / \ | / \ | / c o | (...) Dans un graphe de flux de données, les noeuds sont les variables, et les flèches sont les dépendances entre les variables. Le graphe du flux de contrôle et celui des données sont en fait des informations complémentaires. L'un ne s'occupe que de séquentialité dans le graphe, l'autre s'occupe des dépendances entre les variables sans appliquer appliquer apparemment aucun ordre d'évaluation. Ajouter des prédicats aux graphes de flux de données aide pour déterminer quel noeud est impliqué dans une condition et quelle instance des noeuds de données successeur (dans notre cas, les variables dans le if() ou le else()) devraient être considérées pour notre analyse. Comme vous pouvez le voir, même un petit graphe de flux de données avec peu de variables commence déjà à être fouillis. Pour clarifier la représentation du programme sur lequel on travaille, nous avons besoin d'une sorte de représentation intermédiaire qui garde la séquentialité du graphe de flux de contrôle, mais fournis aussi les dépendances du graphe de flux de données, pour pouvoir raisonner sur les deux avec une seule structure. On peut utiliser une sorte de "graphe de dépendance de programme" [NDT : "program dependence graph"] qui résumerait les deux dans un seul graphe. C'est ce graphe que nous considérerons dans les prochains exemples de cet article. Certaines formes intermédiaires introduisent des noeuds spéciaux dans le graphe du flux de données, et donne un type bien-reconnaissable à ces noeuds. C'est le cas des noeuds Phi() et Sigma() dans les formes intermédiaires "Static Single Assignment" [SSA] et "Static Single Information" [SSI] et en fait, ça facilite le raisonnement sur les graphes de flux de données. En plus, décomposer une seule variable en plusieurs "single assignment" [NDT-5] (et en plusieurs "single use" [NDT-6] dans la forme SSI), c'est à dire, nommer de façon unique chaque apparition d'une variable donnée, ce qui permet d'aider à désambiguïser quelle instance de la variable nous considérons sur un point donné du programme : Stub 2, forme SSA Stub 2 forme SSI graphe de flux de données sous la forme SSI ------------------ ------------------ -------------------------- c1 = 21; c1 = 21; o a1 b1 = a1; b1 = a1; / \ if (b1 != c1) (a3, a4) = Sigma(a2); (a3, a4) = Sigma(a2) o o b1 a2 = a1 + 1; if (b1 != c1) /| else a5 = a3 + 1; / | / | / | / | o c1 a3 = a1 - 1; else | | | a4 = Phi(a2, a3) a6 = a4 - 1; a5 o o a6 | c2 = c1 + a4; a7 = Phi(a5, a6); \ | | c2 = c1 + a7; \ | | ---------------- ------------------- \ | | \| | a7 = Phi(a5, a6) o | \ / o c2 . . . Notez que nous n'avons pas mis de prédicats (les tests des conditions) dans ce graphe. En pratique, il est plus pratique d'ajouter des liens supplémentaires dans le graphe, pour les prédicats (qui facilitent les tests des prédicats quand on parcours le graphe), mais nous les avons retiré ici, juste pour clarifier ce que sont SSA/SSI. Ces "fonction de choix-symbolique" Phi() et Sigma() peuvent sembler un peu abstraites. En fait, elle ne changent pas la signification du programme, mais elles capturent l'information qu'un noeud de donnée donné a plusieurs successeurs (Sigma) ou plusieurs prédécesseurs (Phi). Les lecteurs curieux sont invités à jeter un coup d'oeil aux références pour plus de détails sur comment sont effectuées ces traductions intermédiaires. Nous allons ici nous concentrer sur l'utilisation de ce genre de représentation, surtout lors d'analyse de code contenant des boucles, telle que le code suivant : Stub 3 code C Stub 3 sous forme SSI étiquetée ------------- ------------------------------- int a = 42; int a1 = 42; int i = 0; int i1 = 0; P1 = [i1 < a1] (, ) = Sigma(P1,i2); (, ) = Sigma(P1,a2); while (i < a) { => Loop: a3 = Phi(, ); i3 = Phi(, ); a--; a5 = a4 - 1; i++; i5 = i4 + 1; P2 = [i5 < a5] (, ) = Sigma(P2,a6); (, ) = Sigma(P2,i6); } End: a8 = Phi(, ); i8 = Phi(, ); a += i; a10 = a9 + i9; ----------- --------------------------------- En essayant de synthétiser un peu plus cette forme (en groupant les variables sous un seul Phi() ou un seul Sigma() aux points de séparations ou de réunion du graphe de flux de contrôle), nous obtenons un programme plus petit mais identique. Cette fois, les fonctions Sigma et Phi ne prennent pas une seule liste de variables en paramètre, mais un vecteur de listes (une liste par variable) : Stub 3 sous forme SSI Factorisée et étiquetée -------------------------------------- int a1 = 42; int i1 = 0; P1 = [i1 < a1] (, ) (i2) ( ) = Sigma(P1,( )); (, ) (a2) Loop: (a3) (, ) ( ) = Phi( ); (i3) (, ) a5 = a4 - 1; i5 = i4 + 1; P2 = [i5 < a5] (, ) (a6) ( ) = Sigma(P2, ( )); (, ) (i6) End: (a8) (, ) ( ) = Phi( ); (i8) (, ) a10 = a9 + i9; ---------------------------------------- Comment pouvons-nous ajouter des informations à cette forme intermédiaire ? Maintenant, les fonctions Phi() et Sigma() nous permettent de raisonner sur les flux de données vers l'avant (dans l'ordre d'exécution normale, en utilisant Sigma) et les flux de données vers l'arrière (dans l'ordre inverse, en utilisant Phi). On peut facilement trouver les variables inductives (des variables qui ne dépendent que d'elles mêmes, comme l'index ou le pointeur incrémenté dans une boucle), en utilisant une simple analyse : Considérons le Sigma avant chaque étiquette et essayons d'itérer ses arguments [NDT-7] : (, ) (a6) ( ) = Sigma(P2, ( )); (, ) (i6) -> (,) ( ) (, _|_ ) -> (, _|_ ) ( ) (, _|_ ) Nous avons utilisé _|_ ("bottom" [NDT-8]) pour signifier qu'une variable n'a plus aucun successeur après une certaine itération de la fonction Sigma(). Après quelques itérations (dans cet exemple, 2), nous remarquons que la partie droite et la partie gauche [NDT : par rapport au "->"] sont identiques pour les variables a et i. En fait, les deux parties sont écrites d'après a6 et i6. Dans le jargon mathématique, c'est ce qu'on appelle un point fixe (d'une fonction F) : F(X) = X et sur cet exemple précis : a6 = Sigma(a6) En faisant cette simple analyse basée sur les itérations sur nos fonctions symboliques, nous pouvons déduire de manière automatique quelle variables sont inductives dans nos boucles. Dans notre exemple, a et i sont toutes deux inductives. C'est très utile comme vous pouvez l'imaginer, puisque ces variables acquiert un intérêt pour nous, surtout quand on cherche des débordement de tampons qui pourraient apparaître dans des tampons dans une boucle Nous allons quelque peu spécialiser cette analyse dans la prochaine partie de cet article, en montrant comment cette représentation peut être appliquée à [NDT-9] -------------------[ III. Analyse La partie précédente de l'article a introduit diverses notions en analyse de programmes. Nous n'utiliseront pas tous les formalismes dans le futur de cet article, et nous concentrerons sur des exemples concrets. Cependant, gardez à l'esprit que nous raisonneront à partir de maintenant pour l'analyse sur la forme intermédiaire des programmes. Cette forme intermédiaire est adaptée à la fois pour les codes binaires ou les codes sources, mais nous resterons au niveau binaire dans nos exemples, proposant une traduction en C seulement pour faciliter la compréhension. Jusqu'à maintenant, nous avons montré comment [NDT-10] comprendre l'analyse des flux de données et trouver les variables inductives à partir du code (source ou binaire) du programme. Quels sont donc maintenant les étapes pour trouver les vulnérabilités ? Une première intuition est qu'il n'y a pas de définition générique pour une vulnérabilité. Mais si nous pouvons les décrire comme un comportement qui viole une propriété précise donnée, nous pouvons dire si un programme est vulnérable ou pas. Généralement, la propriété dépend de la classe de bug qu'on veut analyser. Par exemple, les propriété qui expriment la sécurité des buffer overflow ou les propriétés qui expriment une corruption du tas (disons, un double free) sont différentes. Dans le premier cas, nous parlons de l'indexation d'une certaine zone mémoire qui ne doit jamais aller en dehors des limites de la mémoire allouée. En plus, pour avoir un débordement, ça doit être un accès en écriture. Dans le cas ou nous aurions un accès en lecture, nous pourrions nous adresser à lui comme un bug de fuite d'information, qui peut être utilisé aveuglément ou non par un hacker, suivant si le résultat de la lecture mémoire puisse être inspecté à partir de l'extérieur du processus ou pas. Parfois, un accès en lecture seule en dehors des bornes peut aussi être utilisé pour avoir accès à une partie du code qui n'est pas supposée être exécutée dans le contexte courant (si l'accès hors-des-bornes est utilisé dans un prédicat). Dans tous les cas, c'est de toutes façons intéressant de récupérer l'information par notre analyser pour ce comportement non-supposé, parce qu'il pourrait mener à un faux comportement, et donc, un bug. Dans cette partie de l'article, nous allons jeter un oeil à différentes classes de bugs, et comprendre comment nous pouvons les caractériser, en lançant des algorithmes simples et répétitifs, faciles à implémenter. Cet algorithme n'est simple que parce que nous travaillons sur une forme intermédiaire qui indique déjà les faits du flux de données et du flux de contrôle intéressants du programme. En plus, nous allons raisonner à la fois vers l'avant [NDT : forward] et vers l'arrière [NDT : backward], en fonction de ce qui est le plus adapté à la vulnérabilité. Nous allons commencer par un exemple sur l'analyse d'intervalles numériques et montrer comment ils peuvent être utiles pour détecter les débordement de tampon. Nous allons ensuite montrer comment le graphe du flux de données sans aucune information des valeurs peut être utile pour trouver les problèmes apparaissant dans le tas. Nous enrichirons notre présentation e ndécrivant un problème très classique en analyse de programmes, qui est la découverte d'équivalence entre pointeurs (est-ce qu'ils pointent toujours vers la même variable ? seulement parfois ? jamais ?), aussi connu comme l'analyse des alias [NDT : alias analysis]. Nous expliquerons pourquoi cette analyse est obligatoire pour tout analyseur sérieux qui fonctionne sur des programmes réels. En fin, nous donnerons quelques conseils supplémentaires sur l'analyse de propriétés concurrentes dans les codes multi-threadés, en essayant de caractériser ce qu'est une situation de compétition [NDT : race condition]. ------------[ A. intervalles numériques Quand on cherche les débordement de tampon ou les dépassements d'entiers, l'information importante est la valeur que peuvent prendre les indexes mémoire ou les variables entières, qui sont des valeurs numériques. Évidement, il ne serait pas sérieux de calculer toutes les valeurs possibles pour toutes les variables du programme, sur chaque chemin du programme : ça prendrait trop de temps à calculer et/ou trop de mémoire pour stocker le graphe des valeurs entièrement. En utilisant une certaine abstraction comme les intervalles, nous pouvons représenter l'ensemble de toutes les valeurs possibles d'un programme à un certain point de celui-ci. Nous allons maintenant illustrer ceci. L'exemple en lui-même n'a pas de sens, mais le point intéressant est de comprendre la façon mécanisée de déduire des informations en utilisant les informations du flux de données du graphe du programme. Nous devons commencer par un exemple très introductif, qui consiste à trouver [NDT-11] Stub 4 Analyse d'intervalle ------- --------------------------- int a, b; b = 0; b = [0 à 0] if (rand()) b--; b = [-1 à -1] else b++; b = [1 à 1] après if/else: b = [-1 à 1] a = 1000000 / b; a = [1000000 / -1 à 1000000 / 1] [Erreur: b peut valoir 0] Dans cet exemple, un analyseur insensible au flux [NDT : flow-insensitive] va unifier les intervalles de valeurs à chaque point d'unification du flux de contrôle du programme. C'est une approche séduisante puisque vous n'avez qu'une fois à passer sur le programme pour calculer tous les intervalles. Cependant, cette approche est intraitable la plupart du temps. Pourquoi ? Dans ce simple exemple, l'analyseur insensible au flux va signaler un bug de division potentielle par 0, alors que b ne peut pas prendre 0 pour valeur à l'endroit de la division dans le programme. C'est parce que 0 est dans l'intervalle [-1,1] que ce faux positif est signalé par l'analyseur. Comment pouvons-nous éviter cette sorte d'analyse trop prudente ? Nous devons introduire un peut de sensibilité au flux à l'analyseur, et différencier les intervalles pour différents chemins d'exécution du programme. Si nous faisons une analyse complètement sensible au flux pour ce programme, nous obtenons la chose suivante [NDT-12] : Stub 4 Analyse d'intervalle ------- --------------------------- int a, b; b = 0; b = [0 à 0] if (rand()) b--; b = [-1 à 0] else b++; b = [0 à 1] Après if/else: b = [-1 à 0 Ou 0 à 1] a = 1000000 / b; a = [1000000 / -1 à 1000000 / -1] ou [1000000 / 1 à 1000000 / 1] = {-1000000 ou 1000000} Ici, le faux positif disparaît. Nous allons peut-être faire attention à éviter d'être sensible au flux depuis le début. En fait, si l'analyse insensible au flux ne trouve pas de bug, alors, aucun bug ne sera signalé par l'analyse sensible au flux non plus (au moins pour cet exemple). En plus, calculer tous les ensembles d'intervalles sensibles au flux pour un point du programme va grandir exponentiellement en fonction du nombre de points de division du flux de données (c'est à dire, la fonction Phi() de la forme SSA). Pour cette raison, la meilleure approche semble commencer avec une insensible au flux complète, et raffine l'analyse à la demande. Si le programme est transformé en forme SSI, alors, il devient assez facile de savoir quelles intervalles sources nous devons utiliser pour calculer les intervalles de valeurs de variables destination. Nous allons utiliser la même sorte d'analyse pour détecter les débordements de tampons, dans ce cas, l'analyse par intervalles sera utilisée sur les variables d'index qui sont utilisées pour accéder à la mémoire à un certain offset par rapport à une adresse de base donnée. Avant de le faire, nous pourrions vouloir faire une remarque sur le choix d'une abstraction d'intervalle elle-même. Cette abstraction ne fonctionne pas très bien quand des opérations de changements des bits sont utilisées. En fait, les intervalles auront généralement des valeurs sans aucun sens quand les bits sont échangés dans la variable. Si une opération cryptographique utilise des échanges de bits qui introduisent 0 pour remplacer les bits déplacés, ça ne sera pas un problème, mais échanger des bits dans un mot donné est un problème, puisque les intervalles en sortie n'ont alors aucun sens. exemples : c = a | b (avec a, b et c des entiers) c = a ^ b c = not(c) Avec les intervalles de a et b, que pouvons nous déduire de l'intervalle de C ? C'est moins trivial qu'avec de simples changements numériques dans la variable. L'analyse par intervalles n'est pas très adaptée pour l'analyse de ce genre de code, dont la plupart se trouve dans les procédures cryptographiques. Nous allons maintenant analyser un exemple qui implique un débordement de tampon sur le tas. Avant d'effectuer une analyse par intervalles, nous allons faire une première passe pour se renseigner des instructions relatives à l'allocation et la désallocation de mémoire. Sachant où la mémoire est allouée et désallouée et un pré-requis pour toute analyse future de vérification des bornes. Stub 5 Analyse par intervalles avec annotation des allocations ------ ---------------------------------------- char *buf; buf = _|_ (non-initialisé) int n = rand(); n = [-Inf, +Inf] buf = malloc(n) buf = initialisé avec une taille de [-Inf à Inf] i = 0; i = [0,0], [0,1] ... [0,N] while (i <= n) { assert(i < N) buf[i] = 0x00; i++; i = [0,1], [0,2] ... [0,N] (iter1 iter2 ... iterN) } return (i); Expliquons d'abord que le assert() est une représentation logique dans la forme intermédiaire, et n'est pas le assert() comme dans des programmes C. Encore une fois, nous ne faisons aucune analyse dynamique mais uniquement une analyse statique sans aucune exécution. Dans l'analyse statique du programme sous forme intermédiaire, le flux de contrôle va atteindre, à un moment, un noeud contenant l'instruction assert. Dans le monde (abstrait) intermédiaire [NDT-13], atteindre un assert signifie d'effectuer des vérifications sur les valeurs abstraites des prédicats dans le assert (i < N). En d'autres mots, l'analyseur va tester si le assert peut être faut en utilisant l'analyse par intervalles des variables, et imprimera un rapport de bug si assert peut être faux. On pourrait laisser le assert() implicite, mais les représenter explicitement rend l'analyse plus générique, modulaire et adaptable aux utilisateurs. Comme vous pouvez le voir, il y a un débordement d'un octet dans cet exemple. C'est assez trivial à montrer manuellement, cependant, nous voulons développer des procédures automatiques pour le faire. Si nous déployons l'analyse que nous avons fait dans l'exemple précédent, le assert() qui a été ajouté automatiquement par l'analyser après chaque accès mémoire par le programme va échouer après N itérations. C'est parce que les tableaux en langage C commencent avec l'index 0 et finissent par un index valant la taille allouée moins 1. Quel que soit le code inséré entre ces lignes (à part bien entendu les échanges de bits comme on l'a déjà dit), nous seront toujours capables de propager les intervalles et de trouver que l'accès mémoire est fait au delà des limites allouées, trouvant alors une vulnérabilité de fuite de mémoire claire ou d'écrasement mémoire dans le programme. Cependant, cet exemple spécifique apporte 2 questions supplémentaires : - Nous ne savons pas la valeur réelle de N. Est-ce un problème ? Si nous nous débrouillons pour voir que la contrainte sur l'index de buf est en fait la même variable (ou a la même valeur) que la taille du buffer alloué, alors, ce n'est pas un problème. Nous le développeront dans la partie de l'article sur l'analyse des alias quand ça apparaîtra être une difficulté. - Qu'importe la valeur de N, et en admettant qu'on ait pu identifier toutes les définitions et utilisations de la variable N, l'analyseur va avoir besoin de N itérations de la boucle pour détecter la vulnérabilité. Ce n'est pas acceptable, surtout si N est très gros, et dans ce cas nous prendra plusieurs minutes pour analyser la boucle, alors qu'en fait, nous voulons y répondre dans la seconde qui suit. La réponse à ce problème d'optimisation est une technique appelée Widening [NDT-14], récupérée de la théorie des interprétations abstraites. Au lieu d'exécuter la boucle N fois jusqu'à ce que la condition soit fausse, nous allons directement en une seule itération aller à la dernière valeur positive possible dans un certain intervalle, et ceci, dès qu'on aura détecté une croissance monotone de l'intervalle. L'exemple précédent se calcule alors de la manière suivante : Stub 5 Analyse par intervalles avec Widening ------ ------------------------------- char *buf; buf = _|_ (non-initialisé) int n = rand(); n = [-Inf, +Inf] buf = malloc(n) buf = initialisé avec une taille de [-Inf à Inf] i = 0; i = [0,0] while (i <= n) { assert(i < N); iter1 iter2 iter3 iter4 ASSERT! buf[i] = 0x00; i = [0,0], [0,1] [0,2] [0,N] i++; i = [0,1], [0,2] [0,3] [0,N] } return (i); En utilisant ce test, nous pouvons aller directement à l'intervalle le plus grand possible en seulement quelques itérations, réduisant donc drastiquement le temps requis pour trouver la vulnérabilité. Cependant, cette optimisation pourrait introduire des difficultés supplémentaires quand des instructions conditionnelles se trouvent dans la boucle : Stub 6 Analyse par intervalles avec Widening ------ ------------------------------- char *buf; buf = _|_ (non-initialisé) int n = rand() + 2; n = [-Inf, +Inf] buf = malloc(n) buf = initialisé avec une taille de [-Inf à Inf] i = 0; i = [0,0] while (i <= n) i = [0,0] [0,1] [0,2] [0,N] [0,N+1] { if (i < n - 2) i = { assert(i < N - 1) [Jamais lancé !] buf[i] = 0x00; i = [0,0] [0,1] [0,2] [0,N] } i++; i = [0,1] [0,2] [0,3] [0,N] [0,N+1] } return (i); Dans cet exemple, nous ne pouvons pas supposer que l'intervalle de i sera le même tout le temps dans la boucle (comme nous aurions pu être tenté de le faire comme première piste pour gérer les intervalles dans une boucle). En fait, il y a une condition au milieu de la boucle (dont le prédicat est i < n - 2) qui interdis que l'intervalle ne grandisse quelque part dans le code. C'est problématique particulièrement si nous décidons d'utiliser le widening jusqu'à ce que la boucle finisse. Nous raterons cette répartition plus subtile des valeurs dans les variables de la boucle. La solution à ça est d'utiliser le widening avec un seuil. Au lieu d'appliquer le widening une seule fois sur la boucle en entier, nous allons définir une suite de valeur qui correspondra à des "points stratégiques" du code, pour pouvoir décider d'augmenter précisément en utilisant une itération avec des petits pas de valeurs [NDT-14]. Les points stratégiques peuvent être la liste des valeurs sur lesquelles une condition est appliquée. Dans notre cas, nous appliquerions le widening jusqu'à n = N - 2 et pas n = N. De cette façon, nous ne lancerions plus de faux positif à cause d'une sur-approximation des intervalles sur la boucle en entier. Quand chaque étape est réalisée, ça permet d'annoter quel endroit du programme sera l'objet du widening dans le futur (dans notre cas : le code de la boucle avant et après l'instruction "if"). Notez que quand nous atteignons un seuil pendant le widening, nous pourrions avoir besoin d'appliquer une itération avec un petit pas plus d'une fois avant que continuer le widening jusqu'au prochain seuil. Par exemple, quand des prédicats tels que (a != immed_value) sont rencontrés, ils oublieront le code interne de la condition pour propager leurs intervalles. Cependant, ils ne l'oublieront qu'une seule itération (en admettant que a soit une variable inductive et que son état changera à la prochaine itération) ou sur plusieurs itérations (si elle n'est pas inductive et sera modifiée uniquement à un autre moment de l'exécution itérative abstraite de la boucle). Dans le premier cas, nous n'avons besoin que de 2 itérations abstraites à petit pas pour voir que l'intervalle continue de grandir après une certain itération. Dans le deuxième cas, nous aurons besoin de plusieurs itérations jusqu'à ce qu'une condition dans la boucle soit atteinte. On a alors juste besoin d'être sûr que la liste des seuils inclut les valeurs des variables utilisées pour ce prédicat (qui débute le code, là ou la variable a va changer[NDT-15]). De cette façon, on peut appliquer seulement 2 itérations à petit pas entre ces étapes de "widening bornés", et éviter de générer des faux positifs en utilisant une séquence d'évaluation abstraite très optimisée mais précise. Dans notre exemple, nous n'avons pris qu'un exemple simple : la liste des seuils n'est faite que de deux éléments (n et (n - 2)). Mais qu'arrivera-t-il si une condition est réalisée en utilisant deux variable mais pas une et une valeur immédiate ? Dans ce cas, nous avons trois cas : CAS 1 - Les deux variables sont inductives : dans ce cas, la liste des seuils des deux variables doit être fusionnée, pour que le widening ne fasse pas un pas sur une condition qui lui ferait perdre de la précision. Ça semble être une condition raisonnable quand une variable est sujette d'une contrainte impliquant une constante et la seconde variable sujette à une contrainte impliquant la première variable. Stub 7: Découverte des seuils ------- --------------------- int a = MIN_LOWERBOUND; int b = MAX_UPPERBOUND; int i = 0; int n = MAXSIZE; while (i < n) seuil n trouvé { if (a < i < b) Prédicat impliquant a et b trouvé (...) if (a > sizeof(something)) seuil pour a trouvé i = b; else if (b + 1 < sizeof(buffer)) seuil pour b trouvé i = a; } Dans ce cas, on peut définir le seuil de cette boucle comme étant une liste de deux valeurs, l'une étant sizeof(something), l'autre étant sizeof(buffer) ou sizeof(buffer) - 1 si l'analyser est un peu plus intelligent (et si le code assembleur est clair sur le fait que la condition s'applique sur sizeof(buffer) - 1). CAS 2 - L'une des variable est inductive, mais pas l'autre. Nous avons alors deux sous cas : - La variable inductive est impliquée dans un prédicat qui mène à une modification de la variable non-inductive. Ce n'est pas possible sans que les deux variables soient inductives, nous retombons alors dans le cas 1. - La variable non-inductive est impliquée dans un prédicat qui mène à une modification de la variable inductive. Dans ce cas, la variable non-inductive sera invariante sur la boucle, ce qui signifie qu'un test entre son domaine de valeur (son intervalle) et le domaine de la variable inductive est nécessaire pour entrer dans le bout de code qui commence par le prédicat analysé. Encore une fois, nous avons deux sous-cas : * Soit le prédicat est un test du type == ou !=. Dans ce cas nous devons calculer l'intersection des intervalles des deux variables. Si l'intersection est vide, le test n'est jamais vrai, c'est donc du code mort. Si l'intersection est elle-même un intervalle (ce qui sera le cas la plupart du temps), ça signifie que le test sera vrai sur ces intervalles de valeurs de variable inductive, et faux sur le reste du domaine des valeurs. Dans ce cas, nous devons mettre les bornes de l'intervalle de la variable non-inductive dans la liste des seuils pour le widening des variables inductive qui dépendent de cette variable non-inductive. * Soit le prédicat est une comparaison : a < b (où a ou b est une variable inductive). La même remarque reste : nous calculons l'intervalle d'intersection entre a et b. S'il est vide, le test sera toujours vrai ou faux et nous le savons avant d'entrer dans la boucle. Si l'intervalle n'est pas vide, nous devons mettre les bornes de l'intervalle d'intersection dans les seuils de widening de la variable inductive. CAS 3 - Aucune des variable n'est inductive Dans ce cas, le prédicat qu'elles définissent a une seule valeur sur la boucle entière, et peut être calculé avant que la boucle n'ait lieu. On peut alors rendre le code conditionnel en code inconditionnel et appliquer le widening comme si la condition n'existait pas. Où si la condition est toujours fausse, nous retirerons simplement ce code de la boucle puisque le contenu des instructions conditionnelles ne seront jamais atteint. Comme vous pouvez le voir, nous devons être très prudents dans la manière d'effectuer le widening. Si le widening est fait sans seuils, les valeurs numériques abstraites seront sur-approximées, et notre analyse générera beaucoup de faux positifs. En introduisant les seuils, on diminue très peu les performances et gagnons beaucoup de précision sur l'analyse du code des boucles. Le widening est un accélérateur de convergence pour la détection de problème tels que les débordements de tampons. Certains problèmes de débordement peuvent apparaître après des millions d'itérations de la boucle et le widening nous apporte une chouette solution pour avoir une réponse immédiate, même sur ces concepts. Je n'ai pas détaillé comment trouver la taille des buffers dans ce paragraphe. Que les buffers soient alloués sur la pile ou dans le tas, ils ont besoin d'avoir une taille fixe à un certain point et le pointeur de pile doit être soustrait quelque part (ou malloc doit être appelé, etc) ce qui nous donne les informations d'allocation en même temps que la taille, à partir de laquelle nous pouvons appliquer notre analyse. Nous allons maintenant passer à la dernière grosse partie de cet article, en expliquant comment chercher une autre classe de vulnérabilités. ------------[ B. Type state checking (aka double free, fuite mémoire, etc) Il y a d'autres types de vulnérabilité qui sont légèrement différentes à chercher. Dans la partie précédente, nous avons expliquer comment raisonner avec des intervalles de valeurs pour trouver les débordement de tampons dans les programmes. Nous avons présenté une technique d'optimisation appelée le widening et avons étudié comment l'affaiblir pour gagner en précision, en générant une liste de seuils à partir d'un ensemble de prédicats. Notez que nous n'avons pas explicitement utilisé ce qu'on appelle "l'abstraction par prédicats", qui pourrait mener à améliorer encore l'efficacité de l'analyse. Le lecteur intéressé trouvera des informations sur l'abstraction par prédicats via n'importe quel bon moteur de recherche orienté recherche [NDT : recherche académique]. Encore une fois, cet article n'a pas pour but de donner toutes les solutions au problème du monde, mais introduire le hacker débutant aux problématiques concrètes de l'analyse de programme. Dans cette partie de l'article, nous allons étudier comment détecter les fuites mémoire et les corruptions du tas. Les techniques de base pour les trouver ne sont pas liées à l'analyse par intervalles, mais l'analyse par intervalles peut être utilisée pour rentre le type state checking plus précis (en réduisant le nombre de faux positifs). Regardons un exemple de fuite mémoire plus concret : Stub 8: ------- 1. u_int off = 0; 2. u_int ret = MAXBUF; 3. char *buf = malloc(ret); 4. do { 5. off += read(sock, buf + off, ret - off); 6. if (off == 0) 7. return (-ERR); 8. else if (ret == off) 9. buf = realloc(buf, ret * 2); 10.} while (ret); 11. printf("Received %s \n", buf); 12. free(buf); 13. return; Dans ce cas, il n'y a pas de débordement mais si une condition est vérifiée après la lecture, une erreur est retournée sans libérer le tampon. Ce n'est pas une vulnérabilité en tant que telle, mais elle peut beaucoup aider à gérer l'agencement de la mémoire du tas quand on essaye d'exploiter un débordement dans le tas. Donc, nous sommes aussi intéressés pour détecter les fuites mémoires qui rendent certains exploits particuliers en armes puissantes. en utilisant une représentation graphique des flux de contrôle et flux de données, on peut facilement trouver que le code est faux : Analyse par graphe du Stub 8 ---------------------------- o A A: Allocation | | o<---- | \ o \ / \ \ / \ \ R: Return R o o REA / REA: Realloc \ / / \ / / o / | / | / | / | / |/ o | F: Free F o | R o R: Return Notez que cette représentation n'est pas un graphe de flux de données mais un graphe de flux de contrôle annoté avec les informations d'allocation de données pour la variable BUF. Ceci nous permet de raisonner sur les chemins de contrôle existants et la séquences d'événements relatifs à la mémoire. Une autre façon de le faire aurait été de raisonner sur les dépendances de données en même temps que les prédicats, comme on l'a fait dans la première partie de cet article avec la forme SSI étiquetée. Nous ne prêchons aucune forme particulière, et le lecteur est invité à peser par lui-même quelle représentation est la mieux adaptée à sa compréhension. Je vous invite à réfléchir deux fois à la forme SSI qui est vraiment une vue condensée de beaucoup d'informations différentes. Par but pédagogique, nous utiliseront ici une forme intermédiaire plus intuitive qui exprime une classe similaire de problèmes. Stub 8: ------- 0. #define PACKET_HEADER_SIZE 20 1. int off = 0; 2. u_int ret = 10; 3. char *buf = malloc(ret); M 4. do { 5. off += read(sock, buf + off, ret - off); 6. if (off <= 0) 7. return (-ERR); R 8. else if (ret == off) 9. buf = realloc(buf, (ret = ret * 2)); REA 10.} while (off != PACKET_HEADER_SIZE); 11. printf("Received %s \n", buf); 12. free(buf); F 13. return; R En utilisant une simple DFS (Depth-First Search - NDT : Recherche en profondeur d'abord) sur le graphe représentant Stub 8, nous sommes capables d'extraire des séquences telles que les suivantes : 1,2,(3 M),4,5,6,8,10,11,(12 F),(12 R) M...F...R -noleak- 1,2,(3 M),4,(5,6,8,10)*,11,(12 F),(12 R) M(...)*F...R -noleak- 1,2,(3 M),4,5,6,8,10,5,6,(7 R) M...R -leak- 1,2,(3 M),(4,5,6,8,10)*,5,6,(7 R) M(...)*R -leak- 1,2,(3 M),4,5,6,8,(9 REA),10,5,6,(7 R) M...REA...R -leak- 1,2,(3 M),4,5,6,(7 R) M...R -leak- etc [NDT : noleak = pas de fuite, leak = fuite] Plus généralement, nous pouvons représenter l'ensemble de toutes les traces possibles pour cet exemple de la manière suivante : 1,2,3,(5,6,(7 | 8(9 | Nop)) 10)*,(11,12,13)* Avec | signifiant un choix et * signifiant une boucle potentielle sur les événements placés entre (). Comme le programme pourra boucler plus d'une fois ou deux, beaucoup de traces différentes sont potentiellement vulnérables à une fuite mémoire (et pas seulement les quelques unes qu'on a listé), mais toutes peuvent être exprimées en utilisant cette expression régulière générique globale sur les événements de la boucle, suivant cette expression régulière : .*(M)[^F]*(R) qui représente les traces contenant un malloc suivi d'un retour sans free intermédiaire, qui correspond à notre programme à : .*(3)[^12]*(7) = .*(3).*(7) # parce que 12 n'est jamais entre 3 et 7 dans un cycle En d'autres mots, si nous pouvons extraire une trace qui mène à un retour après être passé par une allocation non suivie d'un free (avec un nombre indéterminé d'état entre ces deux étapes), nous trouvions un bug de fuite de mémoire. On peut alors calculer l'intersection de l'expression régulière globale et l'expression régulière des traces vulnérables pour extraire tous les chemins potentiellement vulnérables à partir d'un langage des traces. En pratique, nous ne générerons pas toutes les traces vulnérables mais émettrons simplement quelques unes d'entre elles, jusqu'à en trouver un que nous pouvons en fait lancer. Clairement, les deux premières traces on une intersection vide (elles ne contiennent pas 7). Donc, ces traces ne sont pas vulnérables. Cependant, les expressions des traces suivantes correspondent au patron, et sont donc des chemins vulnérables potentiels pour cette vulnérabilité. Nous pourrions utiliser le système exactement identique pour détecter les doubles frees, sauf que dans ce cas, le patron serait : .*(F)[^A]*(F) C'est à dire : un free suivi d'un autre free sur le même flux de donnée, sans passé par une allocation entre les deux. Un simple analyseur basé sur les traces peut détecter beaucoup de cas de vulnérabilités en utilisant un seul moteur ! Cette super-classe de vulnérabilités est faite de ces fameuses vulnérabilités type-state, suivant l'idée que si le type d'une variable ne change pas pendant le programme, son état change, et donc, l'approche standard de vérification de type n'est pas suffisante pour détecter cette sorte de vulnérabilités. Le lecteur attentif pourrait avoir noté, cet algorithme ne prend pas en compte les prédicats, ce qui signifie que si une telle trace vulnérable est émise, nous n'avons aucune garantie si la condition réelle du programme l'exécutera. En fait, nous pourrions extraire un chemin du programme qui "croise" plusieurs prédicats, certains incompatibles avec d'autres, et donc générant des chemins infaisables en utilisant notre technique. Par exemple, pour notre Stub 8 traduit en code assembleur, une analyse insensible aux prédicats pourrait générer la trace : 1,2,3,4,5,6,8,9,10,11,12,13 Qui est impossible à exécuter parce que les prédicats qui sont dans les états 8 et 10 ne peuvent pas être vrai et faux après une seule itération de la boucle. Une telle trace ne peut donc pas exister dans le monde réel. Nous n'irons pas plus loin sur ce sujet dans cet article, mais dans la prochaine partie, nous allons discuter de diverses améliorations de ce que devrait être un bon moteur d'analyse pour éviter de générer trop de faux positifs. ------------[ C. Comment améliorer. Dans cette partie, nous allons examiner diverses méthodes rapidement pour déterminer comment il est possible exactement de rendre une analyse plus précise et efficace. Les recherches actuelles en analyse de programmes utilise pour ceci une vérification "guidée par contre-example". Diverses techniques prises du monde du model checking ou de l'interprétation abstraite peuvent alors être utilisées, mais nous ne rentrerons pas dans ces soucis théoriques. Nous discuterons simplement de ces idées de ces techniques sans rentrer dans les détails. L'analyseur Chevarista proposé en annexe de cet article ne fait qu'une analyse par alias basique, sans analyse de prédicats, et sans analyse d'ordonnancement de processus (qui aurait été utile pour détecter des situations de compétition). Je donnerai le nom de quelques analyseurs qui implémentent ces analyses et noterez quelles techniques ils utilisent. ----------------------[ a. Analyse des prédicats et treillis des prédicats L'abstraction de prédicats [PA] consiste à collecter tous les prédicats dans un programme, et de construire un objet mathématique à partir de cette liste qu'on appelle "treillis" [LAT]. Un treillis est un ensemble d'objets sur lesquels on défini une certaine relation d'ordre (partielle) entre les éléments de cet ensemble. Un treillis à différentes propriétés théoriques qui le rende différent d'un ordre partiel, mais nous ne donnerons pas ces détails dans cet article. Nous discuterons sur l'ordre lui-même et le type des objets sur lesquels nous travaillons : - L'ordre peut être défini comme l'union d'objets (P < Q iif P is included in Q) - Les objets peuvent être des prédicats - La conjonction (ET) de prédicats peut être la plus petite borne supérieure de N prédicats. Les prédicats (a > 42) et (b < 2) ont comme borne supérieure : (a > 42) && (b < 2) - La disjonction (OU) de prédicats peut être la plus grande borne inférieure de N prédicats. Les prédicats (a > 42) et (b < 2) auraient comme borne inférieure : (a > 42) || (b < 2) Le treillis ressemblerait donc à ça : (a > 42) && (b < 2) / \ / \ / \ (a > 42) (b < 2) \ / \ / \ / (a > 42) || (b < 2) Imaginez maintenant que nous ayons un programme qui aurait N prédicats. Si tous les prédicats peuvent être vrais en même temps, le nombre de combinaisons entre prédicats est de 2 puissance N [NDT : noté 2^N par la suite]. Et c'est sans compter les éléments du treillis qui sont les disjonctions entre prédicats. Le nombre total de combinaisons sera alors de 2*2^N - N : nous devons soustraire N parce que les prédicats fait d'un seul prédicat atomique, sont partagés entre l'ensemble des conjonctions et l'ensemble des disjonctions, qui ont tout deux 2^N nombre d'éléments [NDT-16] incluant les prédicats atomiques, qui est le cas de base pour une conjonction (pred && true) ou une disjonction (pred || false). Nous devrons peut-être aussi considérer les autres valeurs des prédicats : faux, et inconnu. Faux serait simplement la négation d'un prédicat, et inconnu nous informerait de l'ignorance de la valeur d'un prédicat (soit vrai, soit faux, mais nous ne savons pas). Dans ce cas, le nombre de combinaisons possibles entre prédicats est le nombre de combinaisons possibles de N prédicats, chacun pouvant être vrai, faux ou inconnu. Ça nous mène à 3^N possibilités. Cette approche est appelée logique tri-valuée [TVLA]. En d'autres mots, nous avons une complexité dans le pire des cas exponentielle pour la construction du treillis des prédicats qui correspond à un programme analysé. Très souvent, le treillis sera plus petit, puisque beaucoup de prédicats ne peuvent être vrais en même temps. Cependant, il y a une grosse limitation dans ce genre de treillis : il n'est pas capable d'analyser les prédicats qui mélangent les ET et les OU. Ceci veut dire que si nous analysons un programme qui peut être atteint en utilisant beaucoup d'ensembles différents de prédicats (disons en exécutant beaucoup de chemins différents, ce qui est le cas des fonctions ré-entrantes), ce treillis ne sera pas capable de nous donner la représentation "complètement" abstraite la plus précise, puisqu'il pourrait introduire quelques insensibilité au flux dans l'analyse (p.e. une seule combinaison de prédicats représentera des chemins différents). Comme ça pourrait générer des faux positifs, ça ressemble à un bon compromis entre la précision et la complexité. Bien sûr, ce treillis est fourni juste en exemple et le lecteur devrait se sentir libre de l'adapter à ses besoins précis et en fonction de la taille du code à vérifier. C'est un bon indice pour une abstraction donnée mais nous allons voir que d'autres informations que les prédicats sont importantes dans l'analyse des programmes. ---------------------[ b. L'analyse des alias est difficile Un problème qui arrive à la fois dans l'analyse automatique de code source, mais plus encore dans celle de binaires est l'analyse d'alias entre pointeurs. Quand deux pointeurs pointent-ils vers la même variable ? C'est important pour propager les tailles allouées inférées (quand on travaille sur les tableaux), et pour partager un état-type (comme quand un pointeur est alloué ou libéré : vous pourriez rater des doubles frees ou des choses du genre si vous ne savez pas que deux variables sont en fait la même). Il y a des techniques multiples pour effectuer l'analyse d'alias. Certaines d'entre elles fonctionne à l'intérieur d'une seule fonction (appelées intra-procédurale [DDA]). D'autres fonctionnent en dehors des bornes des fonctions. Généralement, plus votre analyse d'alias est précise, plus votre programme analysable est petit. Il semble assez difficile de passer à des millions de lignes de code si on trace chaque allocation de tous les pointeurs possible d'une façon naïve. En plus du problème que chaque variable peut avoir une très grosse quantité d'alias (surtout quand on veut gérer les alias sur les tableaux), un programme traduit sous forme SSA ou SSI a aussi une très grosse quantité de variables. Cependant, la durée de vie de ces variables est très limitée, et donc le nombre de leurs alias aussi. Il est nécessaire de définir une relation d'alias entre les variables pour pouvoir effectuer notre analyse en utilisant des tests supplémentaires : - no_alias(a,b) : les pointeurs a et b pointent vraiment à des endroits différents. - must_alias(a,b) : les pointeurs a et b pointent vraiment au même endroit. - may_alias(a,b) : l'ensemble des variables "vers lesquelles on pointe" de a et b partagent quelques éléments (intersection non-vide), mais ne sont pas égaux. NoAliasing et MustAliasing sont assez intuitives. Le gros morceau est en fait Mayaliasing. Par exemple, 2 pointeurs pourraient pointent la même variable en exécutant un chemin d'exécution, mais des variables différentes en exécutant un autre chemin. Une analyse capable de faire ces différences est appelées analyse sensible au chemin (path-sensitive). En plus, pour un seul endroit du programme manipulant une variable donnée, l'ensemble "vers lesquelles on pointe" de la variable peut être différent en fonction du contexte (par exemple : l'ensemble des prédicats qui peuvent être vrais à ce moment de l'interprétation abstraite du programme). Une analyse qui peut raisonner sur ces différences est appelée sensible au contexte (context-sensitive). C'est un problème ouvert en recherche de trouver le meilleur algorithme d'analyse d'alias qui traite les gros programmes (p.e. un coût d'exécution faible) et qui est capable de garder suffisamment de précision pour prouver des propriétés de sécurité. Généralement, vous pouvez en avoir un, mais pas l'autre. Certaines analyses sont très précises mais ne fonctionnent que dans les bornes d'une fonction. D'autres fonctionne d'une manière complètement insensible au flux, traitant donc les gros programmes mais sont très imprécis. Mon exemple d'analyseur Chevarista implémente uniquement une simple analyse d'alias, qui est très précise mais ne s'adapte pas aux gros programmes. Pour chaque pointeurs, il va essayer de calculer son ensemble de "cibles" et regarder ses résultats à partir de l'analyseur. Il est juste fournis comme exemple mais n'est en aucun cas une réponse définitive à ce problème. --------------------[ c. Conseils pour détecter les situations de compétition Une autre classe de vulnérabilité que nous sommes intéressés à détecter automatiquement est les conditions de compétition. Ces vulnérabilité nécessitent une analyse différente pour être découvertes, puisqu'elles dépendent de propriétés de l'ordonnancement : est-il possible que 2 thread récupèrent des exécutions entrelacées (a, b, a, b) pendant leurs sections critiques où ils partagent certaines variables ? Si les variables sont bien verrouillées, une exécution entrelacée ne sera pas un problème. Mais si le verrouillage est mal géré (comme cela peut se produire dans de très grands programmes tels que les systèmes d'exploitation), alors une analyse de la programmation peut découvrir le problème. Quelles structures de données pouvons-nous utiliser pour exécuter de telles analyses ? L'approche de JavaPathFinder [JPF] cela est développé à NASA est d'utiliser un graphe d'ordonnancement. Le graphe d'ordonnancement est un graphe non cyclique (sans la boucle), où les noeuds représentent des états du programme et et les arrêtes représentent les événements de l'ordonnanceur qui stoppent [NDT-17] l'exécution d'un thread pour en exécuter un autre. Comme cette approche semble intéressante pour détecter n'importe quel chemin d'ordonnancement potentiel (en utilisant encore une recherche en profondeur d'abord dans le graphe d'ordonnancement) qui ne verrouille pas convenablement une variable qui est utilisée dans des threads différents, il semble être plus délicat de l'appliquer quand nous traitons plus de 2 threads. Chaque noeud potentiel aura autant d'arètes qu'il y a de threads, ainsi le graphe d'ordonnancement grandira exponentiellement à chaque étape de l'ordonnancement. Nous pourrions utiliser une technique appelée réduction d'ordre partiel pour représenter par un seul noeud un grand morceau de code pour lequel toutes les instructions partagent la même propriété d'ordonnancement (tel que : "Il ne peut pas être interrompu") ou une même propriété de flux de données (tel que : "il utilise le même ensemble de variables") réduisant ainsi le graphe d'ordonnancement pour le rendre plus abstrait. Encore une vois, l'analyseur Chevarista ne gère pas les conditions de compétition, mais d'autres analyseurs le font et des techniques existes pour le rendre possible. Veuillez lire les références pour plus de détails sur ce sujet. -----------[ IV. Chevarista: un analyseur de programmes binaires Chevarista est un projet pour l'analyse de code binaire. Dans cet article, la plupart des exemples ont été donnés en C ou assembleur, mais Chevarista n'analyse que du code binaire, sans informations sur le source. Tout ce dont il a besoin est d'un point d'entrée pour commencer l'analyse, qu'on peut toujours obtenir sans problèmes pour tout format de binaire (qui fonctionne ?) comme ELF, PE, ... Chevarista est un analyseur plus simple que tout qui a été présenté dans cet article, cependant il tente de suivre ce modèle, conduit par les résultats réussis qui ont été obtenus par l'utilisation de l'outil actuel. En particulier, la forme intermédiaire actuelle de Chevarista est un graphe qui contient l'information du flux de données et de contrôle, mais avec les fonctions sigma et phi laissées implicites. Par simplicité, nous avons choisi de traiter du code binaire SPARC [SRM], mais après avoir lu cet article, vous pourriez comprendre que les représentations utilisées sont suffisamment abstraites pour être utilisées sur n'importe quelle architecture. L'on pourrait dire que le jeu instruction de SPARC est de la famille RISC, et gérer des architecture CISC tel INTEL ou ARM où la plupart des instructions sont conditionnelles, serait un problème. Vous avez raison de vous opposer à ceci parce que ces architectures nécessitent des fonctionnalités spécifiques pour le back-end dépendant de l'architecture du décompilateur-analyseur. Actuellement, seulement le back-end pour SPARC est codé et il n'y a qu'un squelette vide pour l'architecture d'INTEL [IRM]. Quels sont, en détails, les différences entre ces architectures ? Elles sont groupées pour l'essentiel dans un seul composant dépendant de l'architecture : le Back-end Sur les processeurs INTEL 32bits, chaque instruction peut exécuter plusieurs opérations. C'est aussi le cas pour SPARC, mais seulement quand les flags conditionnels sont affectés par le résultat de l'opération exécutée par l'instruction. Par exemple, une instruction push écrit dans la mémoire, modifie le pointeur de pile, et modifie potentiellement les flags de statut (le registre eflags sur INTEL), ce qui rend très difficile à analyser. Beaucoup d'instructions font plus qu'une seule opération, nous avons donc besoin de traduire dans les formes intermédiaires pour rendre ces opérations plus explicites. Si nous limitons le nombre de constructions syntaxiques dans cette forme intermédiaire, nous sommes capables d'exécuter l'analyse indépendante de l'architecture beaucoup plus facilement avec toutes opérations faites explicitement. La forme intermédiaire de bas niveau de Chevarista a environ 10 "opérations abstraites" dans son IR : Branch, Call, Ternop (qui a un champ supplémentaire dans la structure indiquant quelle opération arithmétique ou logique est exécutée), Cmp, Ret, le Test, Interrupt, et Stop. En plus vous avez des opérations purement abstraites (FMI : Flag Modifying Instruction - Instruction Modifiant un Flag), CFI (l'instruction de Flux de Contrôle), et Invoke (les appels de fonctions externes) qui permettent de rendre l'analyse encore plus générique. Invoke est un type de déclaration qui informe l'analyseur qu'il ne doit pas essayer d'analyser l'intérieur de la fonction invoquée, mais considérer le corps comme une abstraction. Par exemple, les types Alloc, Free, Close sont des sous-classes de la classe abstraite Invoke, qui modélise le fait que malloc(), free(), ou close() sont appelées et l'analyseur ne doit pas essayer de gérer le code appelé, mais le considérer comme une boîte-noir. En effet, Trouver les bugs d'allocation n'exigent pas d'aller analyser le corps de malloc() ou free(). Ceci serait nécessaire pour automatiser la génération d'exploits, mais nous ne couvrons pas ceci ici. Nous allons utiliser le design pattern [NDT : patron de conception] pour structurer l'analyse, comme présenté dans le paragraphe suivant. --------------------[ B. Transformation de programmes et modélisation Le projet est organisé en utilisant le design pattern visitor [DP]. Pour résumer, ce design pattern permet de se balader dans un graphe (c'est à dire la forme intermédiaire à l'intérieur de l'analyseur), et de transformer les noeuds (qui contiennent soit des blocs de base pour l'analyse du flux de contrôle, ou des opérations pour l'analyse du flux de données : en fait les liens de flux de contrôle ou de données dans le graphes représentent une relation de prédecesseur / successeurs entre les blocs (flux de contrôle) ou les variables (flux de données). Le projet est organisé comme suit : visitor : le visitor par défaut. Quand le graphe contient des noeuds dont le type n'est pas géré par le visitor courant, c'est ce visitor qui effectue les opérations. Le visitor par défaut est la classe parente dans la hiérarchie des classes Visitor. arch : le back-end de l'architecture. Actuellement, SPARC32/64 est entièrement disponible et le back-end pour INTEL n'est qu'un squelette. Le proof of concept entier a été écrit pour SPARC par simplicité. Cette partie contient aussi le code générique pour le calcul des flux de contrôle et de données. graph : elle contient tout l'API pour construire des graphes directement dans le langage intermédiaire. Elle défini aussi toutes les instructions abstraites (et les instructions "plus" abstraites comme présentées précédemment). gate : C'est le visiteur d'analyse inter-procédural. Les liens de flux de contrôle et de données sont propagés inter-procéduralement dans ce visiteur. En plus, un nouveau type de "continuation" abstrait différentes sortes de transferts de contrôle (Branch, Call, Ret, etc) qui rendent l'analyse plus facile à effectuer après cette traduction. alias : effectue une analyse grossière de "pointe vers qui" pour déterminer des alias évidents entre variables avant de chercher après des vulnérabilités. Cette analyse est exacte et ne s'adapte donc pas aux gros programmes. Il faudrait beaucoup d'heures de lecture et de hack pour améliorer ce visiteur, ce qui rendrait l'analyseur bien plus intéressant en pratique sur de gros programmes. heap : ce visiteur n'effectue aucune transformation réelle, mais un parcours simpliste du graphe pour détecter les anomalies dans le graphe du flux de données. Les doubles frees, les fuites de mémoires, et autres, sont implémentées dans ce visitor. print : Le visitor print, imprime simplement la forme intermédiaire après chaque transformation dans un fichier texte. printdot : Imprime de manière visuelle (dot/graphviz), la représentation par intervalles. Il peut aussi être appelé après chaque transformation mais nous ne l'appelons actuellement qu'à la fin de l'analyse. En plus, une autre transformation a été commencée mais est toujours en état de développement : symbolic : Effectue les transformations dans une forme intermédiaire plus symbolique (comme SSA et SSI) et (rate à) structure(r) le graphe du flux de contrôle en graphe de zones. Ce visiteur est en développement mais fait partie de cette version puisque Chevarista va continuer à être développer pour être implémenté dans le langage ERESI [RSI] plutôt qu'en C++. ------------ ------- ------- ------- ASM |Architecture| | Gate | | Alias | | Heap | ---> | | -> | | -> | | -> | | -> Résultats BRUTE| Back-end | |Visitor| |Visitor| |Visitor| ------------ ------- ------- ------- --------------------[ C. Recherche de vulnérabilités Chevarista est utilisé comme suit dans cet ensemble de démos. Une grosse suite de tests de fichier binaires est fournie dans le package et l'analyse est effectuée. En seulement une paire de secondes, toutes les analyses sont effectuées : # We execute Chevarista on testsuite binary 34 $ autonomous/chevarista ../testsuite/34.elf .:/\ Chevarista standalone version /\:. [...] => Chevarista Detected SPARC Chevarista IS STARTING Calling sparc64_IDG Created IDG SPARC IDG : New bloc at addr 0000000000100A34 SPARC IDG : New bloc at addr 00000000002010A0 [!] Reached Invoke at addr 00000000002010A4 SPARC IDG : New bloc at addr 0000000000100A44 Cflow reference to : 00100A50 Cflow reference from : 00100A48 Cflow reference from : 00100C20 SPARC IDG : New bloc at addr 0000000000100A4C SPARC IDG : New bloc at addr 0000000000100A58 SPARC IDG : New bloc at addr 0000000000201080 [!] Reached Invoke at addr 0000000000201084 SPARC IDG : New bloc at addr 0000000000100A80 SPARC IDG : New bloc at addr 0000000000100AA4 SPARC IDG : New bloc at addr 0000000000100AD0 SPARC IDG : New bloc at addr 0000000000100AF4 SPARC IDG : New bloc at addr 0000000000100B10 SPARC IDG : New bloc at addr 0000000000100B70 SPARC IDG : New bloc at addr 0000000000100954 Cflow reference to : 00100970 Cflow reference from : 00100968 Cflow reference from : 00100A1C SPARC IDG : New bloc at addr 000000000010096C SPARC IDG : New bloc at addr 0000000000100A24 Cflow reference to : 00100A2C Cflow reference from : 00100A24 Cflow reference from : 00100A08 SPARC IDG : New bloc at addr 0000000000100A28 SPARC IDG : New bloc at addr 0000000000100980 SPARC IDG : New bloc at addr 0000000000100A10 SPARC IDG : New bloc at addr 00000000001009C4 SPARC IDG : New bloc at addr 0000000000100B88 SPARC IDG : New bloc at addr 0000000000100BA8 SPARC IDG : New bloc at addr 0000000000100BC0 SPARC IDG : New bloc at addr 0000000000100BE0 SPARC IDG : New bloc at addr 0000000000100BF8 SPARC IDG : New bloc at addr 0000000000100C14 SPARC IDG : New bloc at addr 00000000002010C0 [!] Reached Invoke at addr 00000000002010C4 SPARC IDG : New bloc at addr 0000000000100C20 SPARC IDG : New bloc at addr 0000000000100C04 SPARC IDG : New bloc at addr 0000000000100910 SPARC IDG : New bloc at addr 0000000000201100 [!] Reached Invoke at addr 0000000000201104 SPARC IDG : New bloc at addr 0000000000100928 SPARC IDG : New bloc at addr 000000000010093C SPARC IDG : New bloc at addr 0000000000100BCC SPARC IDG : New bloc at addr 00000000001008E0 SPARC IDG : New bloc at addr 00000000001008F4 SPARC IDG : New bloc at addr 0000000000100900 SPARC IDG : New bloc at addr 0000000000100BD8 SPARC IDG : New bloc at addr 0000000000100B94 SPARC IDG : New bloc at addr 00000000001008BC SPARC IDG : New bloc at addr 00000000001008D0 SPARC IDG : New bloc at addr 0000000000100BA0 SPARC IDG : New bloc at addr 0000000000100B34 SPARC IDG : New bloc at addr 0000000000100B58 Cflow reference to : 00100B74 Cflow reference from : 00100B6C Cflow reference from : 00100B2C Cflow reference from : 00100B50 SPARC IDG : New bloc at addr 0000000000100B04 SPARC IDG : New bloc at addr 00000000002010E0 SPARC IDG : New bloc at addr 0000000000100AE8 SPARC IDG : New bloc at addr 0000000000100A98 Intraprocedural Dependance Graph has been built succesfully! A number of 47 blocs has been statically traced for flow-types [+] IDG built Scalar parameter REPLACED with name = %o0 (addr= 00000000002010A4) Backward dataflow analysis VAR %o0, instr addr 00000000002010A4 Scalar parameter REPLACED with name = %o0 (addr= 00000000002010A4) Backward dataflow analysis VAR %o0, instr addr 00000000002010A4 Scalar parameter REPLACED with name = %o0 (addr= 00000000002010A4) Backward dataflow analysis VAR %o0, instr addr 00000000002010A4 Backward dataflow analysis VAR %fp, instr addr 0000000000100A48 Return-Value REPLACED with name = %i0 (addr= 0000000000100A44) Backward dataflow analysis VAR %i0, instr addr 0000000000100A44 Backward dataflow analysis VAR %fp, instr addr 0000000000100A5C Return-Value REPLACED with name = %i0 (addr= 0000000000100A58) Backward dataflow analysis VAR %i0, instr addr 0000000000100A58 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100A6C Scalar parameter REPLACED with name = %o0 (addr= 0000000000201084) Backward dataflow analysis VAR %o0, instr addr 0000000000201084 Scalar parameter REPLACED with name = %o0 (addr= 0000000000201084) Backward dataflow analysis VAR %o0, instr addr 0000000000201084 Scalar parameter REPLACED with name = %o1 (addr= 0000000000201084) Backward dataflow analysis VAR %o1, instr addr 0000000000201084 Scalar parameter REPLACED with name = %o1 (addr= 0000000000201084) Backward dataflow analysis VAR %o1, instr addr 0000000000201084 Scalar parameter REPLACED with name = %o2 (addr= 0000000000201084) Backward dataflow analysis VAR %o2, instr addr 0000000000201084 Scalar parameter REPLACED with name = %o2 (addr= 0000000000201084) Backward dataflow analysis VAR %o2, instr addr 0000000000201084 Backward dataflow analysis VAR %fp, instr addr 0000000000100A84 Return-Value REPLACED with name = %i0 (addr= 0000000000100A80) Backward dataflow analysis VAR %i0, instr addr 0000000000100A80 Backward dataflow analysis VAR [%fp + 7d3], instr addr 0000000000100AA4 Backward dataflow analysis VAR [%fp + 7df], instr addr 0000000000100ABC Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100AAC Backward dataflow analysis VAR %fp, instr addr 0000000000100AD4 Return-Value REPLACED with name = %i0 (addr= 0000000000100AD0) Backward dataflow analysis VAR %i0, instr addr 0000000000100AD0 Backward dataflow analysis VAR [%fp + 7d3], instr addr 0000000000100AF4 Backward dataflow analysis VAR [%fp + 7d3], instr addr 0000000000100B24 Backward dataflow analysis VAR [%fp + 7df], instr addr 0000000000100B18 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100B70 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100B70 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100B70 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100B38 Backward dataflow analysis VAR %fp, instr addr 0000000000100964 Backward dataflow analysis VAR %fp, instr addr 0000000000100964 Backward dataflow analysis VAR %fp, instr addr 0000000000100964 Scalar parameter REPLACED with name = %o0 (addr= 0000000000100958) Backward dataflow analysis VAR %o0, instr addr 0000000000100958 Scalar parameter REPLACED with name = %o0 (addr= 0000000000100958) [....] Backward dataflow analysis VAR %fp, instr addr 0000000000100B6C Backward dataflow analysis VAR [%fp + 7df], instr addr 0000000000100B60 Backward dataflow analysis VAR [%fp + 7e7], instr addr 0000000000100B58 [+] GateVisitor finished [+] AliasVisitor finished + Entered Node Splitting for Node id 24 + Entered Node Splitting for Node id 194 + Entered Node Splitting for Node id 722 + Entered Node Splitting for Node id 794 + Entered Node Splitting for Node id 1514 + Entered Node Splitting for Node id 1536 + Entered Node Splitting for Node id 1642 [+] SymbolicVisitor finished Entering DotVisitor + SESE visited + SESE visited * SESE already visited * SESE already visited + SESE visited + SESE visited * SESE already visited * SESE already visited * SESE already visited ! Node pointed by (nil) is NOT a SESE + SESE visited * SESE already visited * SESE already visited * SESE already visited [+] Print*Visitors finished Starting HeapVisitor Double Free found Double Free found Double malloc [+] Heap visitor finished [+] Chevarista has finished L'exécution s'est faite en moins de deux secondes et de multiples vulnérabilités ont été trouvées dans le fichier binaire (deux doubles free, et une fuite de mémoire, comme indiqué par la dernière sortie). C'est assez inutile sans plus d'informations, qui nous mène aux résultats. -------------------------[ D. Extraction de chemins vulnérables Encore une fois, l'analyse a été effectuée, on peut vérifier simplement de quel chemin vulnérable il s'agit : ~/IDA/sdk/plugins/chevarista/src $ ls tmp/ cflow.png chevarista.alias chevarista.buchi chevarista.dflow.dot \ chevarista.dot chevarista.gate chevarista.heap chevarista.lir \ chevarista.symbolic dflow.png Chaque visitor (transformation) sort le programme complet dans chaque forme intermédiaire. La chose la plus intéressante est la sortie du visitor heap qui nous donne le chemin vulnérable exact : ~/IDA/sdk/plugins/chevarista/src $ cat tmp/chevarista.heap [%fp + 7e7] [%fp + 7df] [%l0] *********************************** * * * Multiple free of same variables * * * *********************************** ****************** path to free : 1 ****************** @0x2010a4 (0) {S} 32: inparam_%i0 = Alloc(inparam_%i0) @0x100a44 (4) {S} 46: %g1 = outparam_%o0 @0x100a48 (8) {S} 60: local_%fp$0x7e7 = %g1 @0x100bcc (8) {S} 1770: outparam_%o0 = local_%fp$0x7e7 @0x1008e4 (8) {S} 1792: local_%fp$0x87f = inparam_%i0 @0x1008f4 (8) {S} 1828: outparam_%o0 = local_%fp$0x87f @0x2010c4 (0) {S} 1544: inparam_%i0 = Free(inparam_%i0) ****************** path to free : 2 ****************** @0x2010a4 (0) {S} 32: inparam_%i0 = Alloc(inparam_%i0) @0x100a44 (4) {S} 46: %g1 = outparam_%o0 @0x100a48 (8) {S} 60: local_%fp$0x7e7 = %g1 @0x100b58 (8) {S} 2090: %g1 = local_%fp$0x7e7 @0x100b5c (8) {S} 2104: local_%fp$0x7d7 = %g1 @0x100b68 (8) {S} 2146: %g1 = local_%fp$0x7d7 @0x100b6c (8) {S} 2160: local_%fp$0x7df = %g1 @0x100c14 (8) {S} 1524: outparam_%o0 = local_%fp$0x7df @0x2010c4 (0) {S} 1544: inparam_%i0 = Free(inparam_%i0) ****************** path to free : 3 ****************** @0x2010a4 (0) {S} 32: inparam_%i0 = Alloc(inparam_%i0) @0x100a58 (4) {S} 96: %g1 = outparam_%o0 @0x100a5c (8) {S} 110: local_%fp$0x7df = %g1 @0x100c14 (8) {S} 1524: outparam_%o0 = local_%fp$0x7df @0x2010c4 (0) {S} 1544: inparam_%i0 = Free(inparam_%i0) ****************** path to free : 4 ****************** @0x2010a4 (0) {S} 32: inparam_%i0 = Alloc(inparam_%i0) @0x100a58 (4) {S} 96: %g1 = outparam_%o0 @0x100a5c (8) {S} 110: local_%fp$0x7df = %g1 @0x100b60 (8) {S} 2118: %g1 = local_%fp$0x7df @0x100b64 (8) {S} 2132: local_%fp$0x7e7 = %g1 @0x100bcc (8) {S} 1770: outparam_%o0 = local_%fp$0x7e7 @0x1008e4 (8) {S} 1792: local_%fp$0x87f = inparam_%i0 @0x1008f4 (8) {S} 1828: outparam_%o0 = local_%fp$0x87f @0x2010c4 (0) {S} 1544: inparam_%i0 = Free(inparam_%i0) ~/IDA/sdk/plugins/chevarista/src $ Comme vous pouvez le voir, nous avons un chemin vulnérable complet où de multiples frees sont effectués à la suite sur la même variable. Dans cet exemple, deux doubles frees sont trouvés et une fuite de mémoire, pour laquelle le free n'est pas donné, puisqu'il n'y en a pas (c'est une fuite de mémoire :) . Un truc très utile a aussi été de donner des types plus précis aux opérations. Par exemple, les variables locales peuvent être identifiées assez facilement si on y accède via le pointeur de pile. Les paramètres de fonctions et les résultats peuvent aussi êtres facilement trouvés en inspectant l'utilisation des registres %i et %o (pour l'architecture SPARC seulement). ----------------[ E. Travaux futures : raffinement Les étapes finales de l'analyse sont le raffinement [CEGF]. Une fois qu'on a analysé un programme pour trouver des vulnérabilités et qu'on a extrait un chemin du programme qui semble mener à une corruption, nous devons recréer les conditions réelles qui génèrent le bug en réalité, et non une description abstraite pour le programme, comme on l'a fait dans cet article. Pour ceci, nous devons exécuter le programme pour de vrai (cette fois), et essayer de lui fournir les données déduites des prédicats qui sont sur le chemin abstrait du programme qui mène à la vulnérabilité potentielle. Les valeurs en entrée qu'on pourrait donner au programme doivent passer tous les tests sur le chemin pour lancer le bugs dans le monde réel. Il n'y a pas beaucoup de projets qui utilisent cette technique. C'est des recherches assez récentes pour déterminer exactement comment être le plus précis mais rester quand même adaptés aux gros programmes. La solution est que la précision peut être configurée à la demande, en utilisant une procédure itérative comme c'est fait dans le model checker BLAST [BMC]. Même des frameworks d'interprétation abstraite avancée n'ont pas encore de raffinement dans leur framework : certains pourront dire que c'est trop cher en calcul pour raffiner des abstractions et que c'est mieux de coupler des faibles abstractions que d'essayer d'en raffiner une "parfaite". ---------------[ V. Travaux en rapport Presqu'aucun projet sur ce sujet n'a été initié par l'underground. Le travail de Nergal pour trouver les integer overflow dans les binaires win32 est la première tentative notable de mélanger des connaissances de recherche et du reverse engineering, en utilisant un décompilateur et un model checker. Le travail de Halvar Flake dans le framework BinDiff/BinNavi [BN] est intéressant mais s'occupe jusqu'à présent d'un autre objectif que de trouver les vulnérabilités dans un code binaire. D'un point de vue plus théorique, le lecteur intéressé est invité à jeter un oeil aux référence pour trouver beaucoup de lectures majeures sur le thème de l'analyse de programmes. Le reverse engineering automatique, ou la décompilation, ont été étudiées uniquement depuis une dizaines d'années et le fossé entre ces deux mondes n'est pas entièrement comblé. Cet article tente d'aller dans cette direction en introduisant des techniques formelles en utilisant un point de vue complètement informel. Deux différentes théories peuvent être étudiées : le model checking [MC] et l'interprétation abstraite [AI]. Le model checking utilise généralement des propriétés de logique temporelle exprimées dans des langages tels que LTL, CTL ou CTL* ou [TL]. Ces propriétés sont alors traduites en automates. Des traces sont alors utilisées comme des mots et si l'automate ne reconnaît pas un de ces mots, ça veut dire que la trace correspondante ne respectent pas la propriété. En pratique, on utilise la négation de la formule, pour que l'automate construit ne reconnaissent que les traces menant à des vulnérabilités, qui ressemble plus à une approche naturelle pour détecter les vulnérabilités. L'interprétation abstraite [ASA] s'occupe de trouver la représentation système la plus adéquate pour permettre à la vérification d'être calculable en temps raisonnable (sinon, nous finirions par faire une "vérification exhaustive par force brute" si nous essayons de vérifier tous les comportements potentiels du programme, ce qui, de toutes façons peut être infini). En raisonnant dans un domaine abstrait, nous rendons l'ensemble des états fini (ou au moins réduit, comparé à l'espace des états réel) qui rend notre analyse faisable. Au plus l'abstraction est forte, plus vite et imprécise on peut faire l'analyse. Tout le travail consiste à trouver la meilleure abstraction (quand c'est possible), ou une abstraction approximative qui est assez précise et forte pour donner des résultats en quelques secondes ou minutes. Dans cet article, nous avons présenté quelques abstractions sans les citer explicitement (abstractions par intervalles, abstractions de traces, abstraction de prédicats ...). Vous pouvez aussi concevoir des domaines produits, où plusieurs abstractions sont considérées en même temps, ce qui vous donne les meilleurs résultats, mais pour lesquelles, les procédures automatisées nécessitent plus de travail pour être définies. ------[ VI. Conclusion J'espère avoir encouragé la communauté underground à réfléchir à l'utilisation de techniques plus formelles dans la découverte de bugs dans des programmes. Je n'inclus pas cet outil automatisé rêvé, mais un plus simple qui montre cette approche comme gratifiante, et j'espère voir plus d'outil automatisés pour la communauté du reverse engineering dans le futur. L'analyseur Chevarista ne sera pas continué tel quel, mais il est en train d'être réimplémenté dans un environnement d'analyse différent, au dessus d'un langage dédié au reverse engineering et de la décompilation de code machine. N'hésitez pas à hacker dans le code, vous n'avez pas besoin de m'envoyer des patches puisque je n'utilise plus cet outil pour mes propres audits de vulnérabilités. Je ne veux pas encourager les script kiddies à utiliser ce genre d'outils, car ils ne comprendront pas comment exploiter les résultats de toutes façons (non, ça ne vous donne pas un shell root). ------[ VII. Remerciements Pourquoi chaque article de phrack devrait avoir des remerciements ? Les personnes qui ont apprécié Chevarista savent qui elles sont. ------[ VIII. Références [TVLA] Three-Valued Logic http://en.wikipedia.org/wiki/Ternary_logic [AI] Abstract Interpretation http://www.di.ens.fr/~cousot/ [MC] Model Checking http://en.wikipedia.org/wiki/Model_checking [CEGF] Counterexample-guided abstraction refinement E Clarke - Temporal Representation and Reasoning [BN] Sabre-security BinDiff & BinNavi http://www.sabre-security.com/ [JPF] NASA JavaPathFinder http://javapathfinder.sourceforge.net/ [UNG] UQBT-ng : a tool that finds integer overflow in Win32 binaries events.ccc.de [SSA] Efficiently computing static single assignment form R Cytron, J Ferrante, BK Rosen, MN Wegman ACM Transactions on Programming Languages and SystemsFK [SSI] Static Single Information (SSI) CS Ananian - 1999 - lcs.mit.edu [MCI] Modern Compiler Implementation (Book) Andrew Appel [BMC] The BLAST Model Checker http://mtc.epfl.ch/software-tools/blast/ [AD] 22C3 - Autodafe : an act of software torture events.ccc.de/congress/2005/fahrplan/events/606.en.html [TL] Linear Temporal logic http://en.wikipedia.org/wiki/Linear_Temporal_Logic [ASA] The ASTREE static analyzer www.astree.ens.fr [DLB] Dvorak LKML select bug Somewhere lost on lkml.org [RSI] ERESI (Reverse Engineering Software Interface) http://eresi.asgardlabs.org [PA] Automatic Predicate Abstraction of C Programs T Ball, R Majumdar, T Millstein, SK Rajamani ACM SIGPLAN Notices 2001 [IRM] INTEL reference manual http://www.intel.com/design/pentium4/documentation.htm [SRM] SPARC reference manual http://www.sparc.org/standards/ [LAT] Wikipedia : lattice http://en.wikipedia.org/wiki/Lattice_%28order%29 http://fr.wikipedia.org/wiki/Treillis_%28ensemble_ordonn%C3%A9%29 [DDA] Data Dependence Analysis of Assembly Code ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-3764.pdf [DP] Design Patterns : Elements of Reusable Object-Oriented Software Erich Gamma, Richard Helm, Ralph Johnson & John Vlissides ------[ IX. Le code N'hésitez pas à me contacter pour récupérer le code. Il n'est pas inclut dans cet article, mais il sera fourni à la demande si vous y montrer un intérêt. ------[ X. Notes du traducteur : [NDT-1] Dans la Vo : "Instruction level information is interested again to make sure we do not miss bugs from the compiler itself". Qu'on devrait traduire par "L'information [...] est encore intéressée pour ...". En remplaçant "interested" par "interesting", la phrase prend plus de sens, il doit s'agir d'une erreur dans la VO. [NDT-2] Dans la VO : "The next instruction of the will perform a memory allocation". Il doit manquer quelque chose après le "of the" pour que le phrase ait un sens grammaticalement correct. Dans le contexte, "program" est un bon candidat. [NDT-3] Dans la VO : "All the studies properties will be related [...]". Il faut remplacer studies par studied. [NDT-4] Dans la VO : "Lets be more concrete a illustrate how we can [...]". Le "a" doit sûrement signifier "and". [NDT-5] "static single assignment", modélisation où chaque variable ne peut être affectée qu'une seule fois. On "divise" alors les variables en plusieurs versions, qui ne seront affectées qu'une seule fois chaqu'unes, ces fameuses "single assignment". [NDT-6] SSA ne renomme les variables que lors d'affectations. Deux extensions existes, la forme "static single use", qui renomme les variables à chaque fois qu'elles sont utilisées dans une ligne de code (ce sont ces "single use"), et la forme "static single information", qui, en plus de renommer lors des affectations, renomme les variables à chaque fois qu'elles apparaissent dans un contexte conditionnel. Dans la VO, il utilise "single use", qui est différent de "single information", la différence étant légère, je préfère rester fidèle à la VO. [NDT-7] "Lets consider the Sigma() before each Label, and try to iterate its arguments" [NDT-8] En logique, on utilise T pour vrai et _|_ (un T la tête en bas) pour faux. Généralement, on utilise "bottom" pour désigner _|_. [NDT-9] Dans la VO : "[...] by showing how this representation can apply to". Cette phrase n'a pas été terminée. Cette phrase n'est qu'une phrase de liaison, il ne manque rien d'important. [NDT-10] Dans la VO : "[...] we have shown our to understand [...]", il faut lire "how" à la place de "our" [NDT-11] Dans la VO "We need to start by a very introductory example, which consists of finding". Comme dans la [NDT-9], il n'y a pas de fin à cette phrase. [NDT-12] La façon de noter ces intervalles suggère qu'ils soient fermés (et comprennent donc leurs bornes). Or, dans cet exemple, ces intervalles ne comprennent pas toutes leurs bornes (et en fonction des intervalles, ce n'est pas toujours la même borne qu'il faut prendre). Cette notation n'est donc pas à prendre au sens usuel des intervalles. [NDT-13] Dans la VO : "In the intermediate (abstract) word", en ajoutant un 'l' on obtient "world" ("monde" en français) qui a déjà plus de sans que "word" ("mot" en français). [NDT-14] Dans la VO : "[...] we can decide to increase precisely using a small-step values iteration." Si quelqu'un a mieux, je suis preneur. [NDT-15] Dans la VO : "which heads the code where the variable a will change". [NDT-16] Dans la VO : "2pow(N) number of element". [NDT-17] Dans la VO : "that preempt one thread". preempt (signifiant anticiper en anglais), fait en fait référence ici aux ordonnanceurs préemptifs. Dans une telle configuration, le système d'exploitation arrete un thread lui-même pour passer la main au suivant.