Détection de failles avec Address Sanitizer

1. Présentation

Address Sanitizer se présente sous la forme d'un plugin à Clang, qui est lui-même un frontend C, C++, Objective-C et Objective-C++ de la suite de compilation LLVM. La philosophie de LLVM est d'offrir une succession d'outils indépendants dont la combinaison permet d’effectuer l'ensemble des tâches de compilation d'un programme. Cette architecture modulaire, à l'opposé d'outils monolithiques comme GCC, permet à la fois de simplifier chaque composant et de centraliser les opérations compliquées comme l'optimisation, mais également de disposer d'une API ouverte, complète et stable.

Cette API a permis l'émergence d'un grand nombre de projets qui en tirent parti pour s'intercaler à différents stages de la compilation, et ce sans avoir besoin de modifier le compilateur pour accéder à des informations qui ne sont pas normalement disponibles. D'autres projets ont par ailleurs réalisé les avantages de ce type d'ouverture. GCC a par exemple relativement récemment intégré la possibilité d'écrire des plugins [RASNEUR11].

Address Sanitizer [ASAN] est l'exemple typique d'un outil qui n'aurait pas pu voir le jour sans l'architecture ouverte de LLVM. Ce plugin tire parti de la possibilité de modifier le code généré de façon à mettre en place des mécanismes de détection des erreurs de manipulation mémoire les plus courantes, à savoir :

- utilisation d'une zone mémoire après sa libération (Use-After-Free) ;

- dépassement de tampon dans le tas (heap out of bounds) ;

- dépassement de tampon sur la pile (stack out of bounds) ;

- dépassement de tampon global (global out of bounds) ;

- double libération de mémoire (double free).

Malgré sa jeunesse, ASAN dispose d'ores et déjà d'un palmarès impressionnant en termes d'erreurs détectées, affichant notamment sur son tableau de chasse Chromium, FFMpeg, Freetype, GCC, LLVM, Mozilla Firefox, Parrot, Perl, VIM, et Webkit. Un pourcentage non négligeable de ces erreurs a par ailleurs donné lieu à des vulnérabilités sérieuses, notamment dans les navigateurs mentionnés [FOUNDBUGS].

Initialement développé en dehors de Clang, ASAN a été intégré à celui-ci à partir de la version 3.1, et ne nécessite donc plus d'être téléchargé, compilé et installé séparément.

Il existe de nombreux autres outils dont le but est de détecter les erreurs de manipulation mémoire lors de l'exécution d'un programme. Les plus connus sont notamment l'outil Memcheck dans Valgrind [VALGRIND] et Electric Fence [EFENCE], qui obtiennent d'excellent résultats, mais se trouvent limités par le fait qu'ils se placent tous les deux à l'extérieur du programme qu'ils veulent surveiller. Nous reviendrons sur ce point vers la fin de cet article.

2. Utilisation

Pour illustrer les possibilités de l'outil, rien ne vaut quelques exemples pratiques. Tous les programmes mentionnés peuvent être obtenus depuis une adresse de téléchargement mentionnée à la fin de l'article, et sont tous compilés avec Clang sous Linux en utilisant la commande suivante :

puis exécutés ainsi :

Lorsqu'un programme doit être compilé sans le support d'ASAN, la ligne de compilation utilisée est la suivante :

2.1 Use-After-Free

Le premier exemple illustre l'utilisation d'une zone mémoire après sa libération :

Le programme alloue une zone de 2 octets, écrit dans ces derniers, puis libère la mémoire. Enfin, il essaye à nouveau d'écrire dans la zone précédemment libérée. L'exécution du programme compilé avec ASAN donne le résultat suivant :

Comme nous pouvons le voir, l'utilisation d'une zone mémoire libérée est correctement détectée, et ASAN nous indique non seulement à quel endroit du code chercher l'utilisation problématique, mais également l'allocation initiale et la libération.

2.2 Exploitation des traces

Avant de passer à l'exemple suivant, revenons rapidement sur le message d'erreur affiché par ASAN lors de l'exécution de notre exemple. Les informations remontées sont très intéressantes, mais à ce stade un peu décevantes : nous aimerions bien avoir des informations plus exploitables qu'un offset et le nom du binaire, comme par exemple un nom de fichier et un numéro de ligne :

Cette fonctionnalité n'est pas directement présente dans ASAN, mais un script fourni dans les sources de LLVM permet de remédier à cet inconvénient. Ce script peut être trouvé dans le répertoire projects/compiler-rt/lib/asan/scripts/asan_symbolize.py des sources de LLVM [ASANSYMBOLIZE]. En passant le contenu de la sortie d'erreur de notre programme sur l'entrée standard de ce script, nous obtenons cette trace :

Cette fois-ci, nous avons bien la fonction, le fichier et le numéro de ligne pour chaque information.

De manière moins rigoureuse, et pour gagner du temps, nous pouvons copier le script Python en question dans le répertoire courant et invoquer directement notre programme de test de la façon suivante :

2.3 Heap out of bounds

Notre deuxième exemple se présente ainsi :

Et le résultat lors de son exécution :

Ici non plus, pas de surprise, l'erreur est bien détectée.

2.4 Stack out of bounds

Notre dernier exemple sera celui de l'écriture illicite sur la pile, juste après une zone de mémoire correctement allouée.

Notons que Clang effectue un certain nombre de vérifications par défaut lors de la compilation et, dans le cas présent, ces vérifications s'avèrent payantes :

Si nous décidons de passer outre et d'exécuter quand même le programme, l'erreur est correctement détectée par ASAN :

Nous allons nous contenter de ces exemples, mais il en existe d'autres, qui sont disponibles sur le site internet d'ASAN [ASANEXAMPLES], notamment pour un dépassement de tampon en variable globale (global out of bounds) et une double libération de mémoire (double free).

3. Étude des mécanismes internes d'ASAN

Pour un programme comme ASAN, il est nécessaire de réaliser deux types d'opérations :

- Maintenir à jour la liste des adresses mémoire auxquelles le programme peut accéder.

- Intercepter les accès à la mémoire pour vérifier qu'ils sont valides, en se basant sur la liste précédente.

Afin de comprendre comment ASAN réalise ces tâches de manière plus efficace que les autres outils du même type, nous allons nous pencher plus en détails sur ses mécanismes internes.

3.1 État de la mémoire

ASAN utilise un algorithme simple mais efficace pour conserver l'état de chaque zone mémoire. L'espace d'adressage virtuel est divisé en deux parties :

- la mémoire « normale » du programme, appelée par la suite Memory ;

- le registre d'état de la mémoire « normale », qu'ASAN nomme Shadow Memory ou Shadow.

L'implémentation actuelle d'ASAN associe un octet de Shadow Memory pour 8 octets de la mémoire normale, et les valeurs de cet octet permettent de savoir s'il est correct ou non d’accéder à chacun des octets de la mémoire normale. Par exemple :

- Il est possible d'accéder aux 8 octets de la mémoire normale, tous les bits de l'octet correspondant de Shadow sont à 0.

- Aucun octet n'est accessible, tous les bits de l'octet de Shadow sont à 1.

- Les n premiers octets sont accessibles, alors la valeur de l'octet de Shadow est à n.

Sur les systèmes GNU, l'implémentation de l'allocateur de mémoire renvoie toujours une adresse alignée sur 8 bytes, ce qui a pour conséquence qu'il n'y a pas d'autres cas à gérer que ceux-ci.

La correspondance entre la mémoire normale et la mémoire Shadow se fait de la façon suivante :

L'opération « >> » représentant un décalage de bits vers la droite, et l'opération « | » un OR binaire.

Pour obtenir les valeurs de SHADOW_SCALE et SHADOW_OFFSET sur notre architecture, nous allons utiliser la variable d'environnement ASAN_OPTIONS. Cette variable permet de modifier le comportement d'ASAN à l'exécution. Ici, nous allons définir la valeur de ASAN_OPTIONS à « verbosity=1 », pour obtenir plus d'informations.

Nous apprenons donc que la valeur de SHADOW_SCALE sur un Linux 64 bits est de 3, et que celle de SHADOW_OFFSET est de 0x0000100000000000. Les lecteurs attentifs auront également remarqué une autre information très intéressante, à savoir la disposition mémoire de notre programme. Nous constatons que la Shadow Memoryest divisée en deux sous-parties, une pour la mémoire basse et une pour la mémoire haute, ce que nous pouvions deviner en appliquant la formule de calcul de la mémoire Shadow vue plus haut. Ce qui nous donne le tableau suivant :

 

Mémoire Haute	[0x0000200000000000, 0x00007fffffffffff]
Shadow (Mémoire Haute)	[0x0000140000000000, 0x00001fffffffffff]
ShadowGap	[0x0000120000000000, 0x000013ffffffffff]
Shadow (Mémoire Basse)	[0x0000100000000000, 0x000011ffffffffff]
Mémoire Basse	[0x0000000000000000, 0x00000fffffffffff]

Nous constatons alors la présence d'une zone mémoire qui n'a jusqu'ici pas été évoquée, le Shadow Gap. Sa présence s'explique simplement par le fait que les accès à la mémoire Shadow doivent eux aussi être contrôlés. L'algorithme indiqué précédemment a pour conséquence que Shadow(Shadow) = Shadow Gap. Toute tentative de la part du programme d'accéder directement à la mémoire Shadow se retrouve donc dans le Shadow Gap.

Pour vérifier ces nouvelles informations, il nous suffit d'afficher la disposition mémoire de notre programme pendant son exécution :

Nous retrouvons bien à la 4e ligne la mémoire Shadow basse, à la 5e notre Shadow Gap et à la 6e la mémoire Shadowhaute. Regardons maintenant comment la présence du Shadow Gap protège les accès à la mémoire Shadow en examinant les allocations mémoire effectuées par ASAN lors du démarrage du programme :

Nous constatons que si les allocations des deux zones réservées à la mémoire Shadow basse et haute sont bien effectuées avec des permissions en lecture et écriture (PROT_READ|PROT_WRITE), la réservation de l'espace du Shadow Gap est faite avec une interdiction totale d'accès (PROT_NONE). Toute tentative d'accès au Shadow Gap déclenchera donc une violation d'accès à la mémoire et terminera le programme.

Nous connaissons donc maintenant l'algorithme utilisé par ASAN pour conserver la liste des zones mémoire accessibles, et vérifier lors d'un accès si celui-ci est autorisé ou non. Il nous reste maintenant à voir comment cette liste est mise à jour et de quelle façon les accès sont interceptés en pratique.

Pour cela, nous allons étudier le code généré par ASAN à l'aide d'Objdump [OBJDUMP]. Objdump est un outil de la suite GNU Binutils, qui contient également GNU ld, mais aussi le linker gold et d'autres commandes indispensables telles que addr2line (utilisée sous Linux par le script asan_symbolize.py), nm ou encore readelf. Il a l'avantage d'être libre et gratuit, et installé sur la majorité des machines. Le code assembleur qu'il génère est bien suffisant pour notre analyse même si, à titre personnel, IDADWARF me manque [IDADWARF] :)

Le code désassemblé de cet article a été compilé par Clang 3.1 sous Linux sur une architecture x86_64.

3.2 Utilisation d'objdump

Nous allons soumettre les binaires obtenus à Objdump pour étudier le code généré par ASAN à l'aide de la commande suivante :

L'option -d indique à Objdump de désassembler le programme, l'option -R de nous afficher les relocations, -l les numéros de lignes et -M intel permet d'obtenir une notation Intel à la place de la notation AT&T. Enfin, l'option -C demande à Objdump de démêler (demangle) les noms C++ lorsque cela est possible. Nos programmes de test sont écrits en C et ne nécessitent normalement pas cette option, mais Clang, LLVM et ASAN étant développés en C++, elle va s'avérer utile par la suite.

3.3 Protection du tas

Reprenons notre second exemple, qui consistait en une allocation dynamique de mémoire, suivie d'un accès au-delà de la mémoire allouée. À l'aide d'Objdump, nous voyons que le code généré est le suivant :

Tout d'abord, l'appel à malloc() est surprenant, car nous nous attendions à voir un appel à la PLT (Procedure Linkage Table), étant donné que malloc() se trouve dans une bibliothèque partagée. Ici, l'appel semble faire référence à un symbole présent dans le binaire.

En regardant ce qui se trouve à l'adresse concernée, nous comprenons qu'ASAN fournit le symbole malloc() de manière à contrôler les allocations mémoire.

En effet, nous voyons distinctement que des informations concernant le contexte de l'allocation mémoire sont récupérées et conservées par ASAN, de manière à pouvoir les fournir si une mauvaise manipulation mémoire impliquant la zone nouvellement allouée devait se produire. Ces informations sont récupérées par des appels aux méthodes __asan::AsanStackTrace::GetCurrentPc() et __asan::AsanStackTrace::GetStackTrace().

L'allocation mémoire proprement dite est faite dans la méthode Allocate() du fichier asan_allocator.cc, appelée à partir de la méthode  __asan::asan_malloc que nous voyons ici.

Pour chaque zone mémoire de taille size allouée, une zone mémoire de taille supérieure, REDZONE + size (alignée sur REDZONE) est allouée.

La zone mémoire complète commence par une zone spéciale « gauche » de longueur 128 (comme indiqué par ASAN lorsque l'option ASAN_OPTIONS=verbosity=1 lui est passée) qui contient des données internes à ASAN, notamment la taille de la zone allouée, son état et le contexte de l'allocation mémoire. La zone se termine enfin par une seconde zone spéciale « droite » de taille variable, le but étant que la zone complète soit alignée sur une taille de REDZONE. Les deux zones spéciales sont bien empoisonnées par le mécanisme décrit précédemment de mémoire Shadow, permettant ainsi de détecter tout accès avant ou après la zone utilisable par le programme.

Notons que les zones allouées dynamiquement ne sont pas directement réutilisables après leur libération par un appel à free(), mais restent pendant un temps dans une liste de zones récemment libérées, de manière à pouvoir différencier un accès à une zone récemment libérée et un accès à une zone mémoire jamais allouée.

Continuons l'analyse de notre programme :

L'adresse de la zone mémoire pointée par buffer (qui se trouve en rsp + 0x68) est chargée dans rdx. L'adresse est incrémentée de 2 puisque la ligne 14 essaye d’accéder au second octet de buffer. On retrouve alors l'algorithme de vérification évoqué précédemment, à savoir :

Ici, un décalage à droite de SHADOW_SCALE (3) est effectué dans rsi, et le résultat se voit appliquer un OR binaire avec SHADOW_OFFSET (0x0100000000000). La valeur résultante est l'adresse de l'octet de mémoire Shadow indiquant si l'accès à cette zone mémoire est ou non autorisé. Si l'octet de Shadow concerné est à 0, il n'est pas nécessaire d'aller plus loin et l'accès est autorisé. Sinon, la vérification se poursuit en 406049 :

L'adresse mémoire est soumise à un AND binaire avec SHADOW_GRANULARITY (8) – 1 et le résultat est comparé à l'octet de Shadow Memory. Si le résultat est supérieur ou égal, cela signifie que l’adresse mémoire n'est pas une adresse valide, et l'accès est refusé avec les conséquences que nous connaissons.

3.4 Protection de la pile

Nous avons vu dans notre dernier exemple la façon dont une écriture dépassant les limites d'une variable sur la pile est détectée par ASAN. Une lecture sera par ailleurs détectée de manière équivalente. Cette détection peut paraître un cas simple, mais elle est par exemple impossible à réaliser pour un programme comme Valgrind qui ne se place pas au niveau de la compilation.

Prenons comme exemple le code suivant :

Une simple fonction déclarant trois variables sur la pile, deux entiers et un caractère. Le code compilé avec ASAN puis désassemblé nous donne le résultat suivant :

Nous voyons là la façon dont la pile est protégée par ASAN. Un rapide décodage nous indique que la pile de chaque fonction est entourée de deux REDZONE, la « gauche » et la « droite », toutes deux d'une taille de 32 octets. Ensuite, pour chaque variable déclarée sur la pile, nous avons une REDZONE partielle, dont la longueur permet d'arrondir à 32 octets celle de la variable protégée, et une REDZONE intercalaire elle-même de 32 octets.

En utilisant ces zones de protection de la même manière que celles qui entourent normalement les allocations dynamiques, tout accès dépassant une variable déclarée sur la pile peut être détecté.

Nous notons sur le code désassemblé qu'ASAN utilise des valeurs spéciales pour la mémoire Shadow associée aux différentes REDZONE :

- celle de la zone « gauche » est remplie avec la valeur « magique » 0xf1 ;

- celle de la zone « droite » avec la valeur 0xf3 ;

- celle des zones intercalaires avec la valeur 0xf2 ;

- enfin, la zone partielle est remplie avec la valeur 0xf4, sauf pour les octets qui correspondent à la mémoire de la variable et qui sont eux déterminés avec le même algorithme que précédemment.

Nous avons donc ici les valeurs suivantes pour les trois zones partielles :

- 0xf4f4f404 pour result, dont la valeur correspond bien au fait que les quatre octets de l'entier sont accessibles ;

- idem pour result2 ;

- 0xf4f4f401 pour c, qui en tant que caractère n'a qu'un seul octet accessible.

4. Comparaison aux outils du même type

L'architecture même d'ASAN et son intégration au niveau du compilateur offrent des perspectives virtuellement illimitées en termes d'instrumentalisation. La majorité des concurrents utilisent une approche beaucoup moins intrusive et ne nécessitant pas de recompilation, que ce soit en remplaçant les fonctions d'allocation et de libération de la mémoire à l'aide de préchargement ou de compilation statique, comme Electric Fence, ou à l'aide d'un mécanisme de traduction de code à la volée comme Valgrind. Malheureusement, ces approches sont soit trop limitées parce qu'elles ne contrôlent pas le flot d'exécution complet du programme, comme Electric Fence, ou bien trop lourdes et consommatrices de ressources, comme Valgrind.

À titre de comparaison, les tests effectués par Google montrent que l'utilisation d'ASAN implique un ralentissement d'ordre 2 par rapport au temps d'exécution du programme initial, là où Valgrind affiche un rapport d'ordre 20, et les autres outils un rapport allant entre 10 et 40.

Il est également important de noter qu'il semble qu'à l'heure actuelle, ASAN soit le seul outil capable de détecter les dépassements sur la pile et sur les variables globales, ainsi qu'un certain nombre d'utilisations de variables allouées sur la pile d'une fonction après que le programme soit sorti de cette fonction.

En contrepartie, ASAN n'est d'aucune utilité lorsque les violations mémoire surviennent dans une partie du code qui n'a pas été compilée avec le support adéquat, ce qui est en général le cas des bibliothèques partagées. Prenons le cas très récent d'une vulnérabilité dans la glibc, la CVE-2012-3480. Le programme suivant est l'exemple qui a été donné lors de la publication de la vulnérabilité :

L'exécution de ce code sur un programme utilisant une version vulnérable de la glibc donne les traces suivantes, avec respectivement ASAN et Valgrind :

Là où Valgrind est capable d'obtenir des informations très intéressantes sur l'origine du problème, ASAN est totalement démuni.

Il est par ailleurs important de noter qu'il ne faut pas, à l'heure actuelle, utiliser Valgrind sur un binaire compilé avec le support d'ASAN. L'exécution du programme part alors en boucle infinie, consommant toute la mémoire disponible jusqu'à ce qu'elle soit interrompue par OOM Killer.

Notons bien par ailleurs que nous ne parlons ici que de la détection des erreurs de manipulation de mémoire. La détection des fuites de mémoire reste un domaine où Valgrind règne sans conteste.

Conclusion

La force de cet outil réside sans aucun doute dans les nombreuses failles potentielles qu'il permet de détecter, dans son faible coût de mise en œuvre et surtout sa rapidité.

Son coût est si peu pénalisant à l'exécution que, contrairement à ses concurrents, il n'existe aucune bonne raison de ne pas l'utiliser systématiquement lors des phases de tests unitaires et fonctionnels de façon à repérer ainsi un maximum de bugs qui ne seraient en temps normal pas détectés.

Il existe encore de nombreuses améliorations envisageables à Address Sanitizer. Certaines d'entre elles sont d'ores et déjà en cours d'implémentation, notamment la fonctionnalité permettant d'avoir des traces d'appels exploitables avec nom de fichier, fonction et numéro de lignes sans passer par un script externe, ou encore une fonctionnalité rudimentaire de détection de fuites mémoire.

Les codes complets des différents programmes évoqués dans cet article sont présents à l'adresse suivante : http://www.coredump.fr/static/misc/asan/.

Références

[ASAN] Address Sanitizer : http://clang.llvm.org/docs/AddressSanitizer.html

[ASANEXAMPLES] https://code.google.com/p/address-sanitizer/w/list

[ASANSYMBOLIZE] Script résolvant les traces : http://llvm.org/svn/llvm-project/compiler-rt/trunk/lib/asan/scripts/asan_symbolize.py

[CLANG] Clang : http://clang.llvm.org

[EFENCE] Electric Fence : http://perens.com/FreeSoftware/ElectricFence/

[FOUNDBUGS] https://code.google.com/p/address-sanitizer/wiki/FoundBugs

[GCC] GCC : http://gcc.gnu.org

[IDADWARF] IDA-Dwarf : http://vrasneur.coredump.fr/idadwarf/

[LLVM] LLVM : http://www.llvm.org

[OBJDUMP] Objdump est un outil de la suite GNU Binutils : http://www.gnu.org/software/binutils/

[RASNEUR11] Vincent Rasneur, MISC 56, « Analyse statique et pratique avec GCC et ses plugins »

[VALGRIND] Valgrind : http://valgrind.org/

Remerciements

Un grand merci aux différents relecteurs, notamment Pierre-François Hugues, Vincent Rasneur et Nicolas Sitbon.