GCC, Trampoline, et code auto-modifiable

March 4th, 2005 by lucas

Aux temps héroïques, le code auto-modifiable était fréquent. Ça consiste à écrire du code qui se modifie lui-même pendant l’exécution, pour faire des micro-optimisations qui tuent (en fait, surtout gagner une indirection par ci par là, mais à l’époque c’était pas négligeable).

Mais en fait, ça n’a pas complètement disparu : GCC, dans un cas précis, en génère d’ailleurs !

Fonctions imbriquées en C

Une fonction imbriquée en C est une fonction définie à l’intérieur d’une autre fonction. A quoi est-ce que ça sert ? Parfois, pour rendre votre code plus clair, vous définissez des fonctions qui ne sont utiles que dans une autre fonction. Il est donc débile de la rendre accessible depuis toutes les autres fonctions ! GNU CC vous autorise à écrire le code suivant (c’est une extension de GCC, ce n’est pas dans la norme C99) :

 int f1() { 	int f2() 	{ 		[...] 	} 	[...] 	f2(); 	[...] } 

C’est bien joli, mais ça pose un problème. Regardez cet exemple (qui compile, n’hésitez pas à essayer) :

 void f0(void (*f)()); long f1 (void) { 	long i = 0; 	void f2(void) 	{ 		i++; 	} 	f0(f2); 	return i; } void f0(void (*f)()) { 	(*f)(); } int main() { 	return f1(); } 

C’est tout à fait légal : f1 passe un pointeur vers f2 à f0, qui se charge d’appeler la fonction en paramètre. Le problème est que f2 modifie i. Or i est une variable locale de f1 (allouée sur la pile par f1). La distance entre ESP dans f2 et les variables locales de f1 sur la pile n’est pas connue : ici, f0 appelle directement f2, mais il pourrait appeler blop(f2) qui lui même appelerait f2. Il faut trouver un moyen de passer à f2 l’adresse du contexte de sa fonction parente.

Trampolines

Un papier (PDF) évoque ce problème pour le C++ (où les closures sont encore plus pratiques qu’en C, notamment lorsqu’on utilise des itérateurs). Il propose une solution élégante utilisant un trampoline. Dans l’article, il démontre la solution avec de l’assembleur 68000. Voici le code ci-dessus compilé pour x86, sans optimisation histoire de garder le code le plus proche possible du C.

 	.file	"t5.c" 	.text 	.type	f2.0, @function f2.0: 	pushl	%ebp 	movl	%esp, %ebp 	subl	$4, %esp 	movl	%ecx, -4(%ebp) 	movl	-4(%ebp), %ecx 	incl	-4(%ecx) 	leave 	ret 	.size	f2.0, .-f2.0 .globl f1 	.type	f1, @function f1: 	pushl	%ebp 	movl	%esp, %ebp 	subl	$40, %esp 	leal	-24(%ebp), %eax 	addl	$0, %eax 	andl	$-1, %eax 	movl	$f2.0, %ecx 	leal	10(%eax), %edx 	subl	%edx, %ecx 	movl	%ecx, %edx 	movb	$-71, (%eax) 	leal	-8(%ebp), %ecx 	movl	%ecx, 1(%eax) 	movb	$-23, 5(%eax) 	movl	%edx, 6(%eax) 	movl	$0, -12(%ebp) 	leal	-24(%ebp), %eax 	addl	$0, %eax 	andl	$-1, %eax 	movl	%eax, (%esp) 	call	f0 	movl	-12(%ebp), %eax 	leave 	ret 	.size	f1, .-f1 .globl f0 	.type	f0, @function f0: 	pushl	%ebp 	movl	%esp, %ebp 	subl	$8, %esp 	movl	8(%ebp), %eax 	call	*%eax 	leave 	ret 	.size	f0, .-f0 .globl main 	.type	main, @function main: 	pushl	%ebp 	movl	%esp, %ebp 	subl	$8, %esp 	andl	$-16, %esp 	movl	$0, %eax 	subl	%eax, %esp 	call	f1 	leave 	ret 	.size	main, .-main 	.section	.note.GNU-stack,"x",@progbits 	.ident	"GCC: (GNU) 3.3.5 (Debian 1:3.3.5-8)" 

Un trampoline, c’est un petit bout de code qui va mettre dans registre (ici ECX, je ne sais pas quelle est la convention exactement) l’adresse de l’environnement de la fonction parente. Dans le code de f2, on voit qu’on incrémente -4(%ecx) pour incrémenter i. Ce petit bout de code est généré sur la pile par f1 avant d’appeler f0. Le code qui génère le code est entre “subl $40, %esp” et “call f0″, en gros. Et mon débogueur me dit que le code généré ressemble à :

 Dump of assembler code from 0xbffff930 to 0xbffffa30:     0xbffff930:     mov    $0xbffff940,%ecx     0xbffff935:     jmp    0x8048354  

Quand f0 fera son call, il appellera une adresse de la pile sans le savoir. Et quand f2 retournera, elle retournera directement dans f0.

C’est trop beau, il doit bien y avoir un problème qqpart …

Hé oui. La pile exécutable, c’est un problème : c’est la base de l’exploitation de beaucoup de trous de sécurité. Du coup, des systèmes essayent de rendre la pile non exécutable. C’est le cas de OpenBSD avec W^X, ou de Linux avec Exec-shield (PDF). Comment faire pour continuer à autoriser les trampolines, alors ? Et bien c’est tout simple. Sous linux, l’en-tête ELF des binaires contient un flag indiquant si ce programme a besoin que la pile soit exécutable. Avec l’exécutable du code de tout à l’heure :

 ***lucas@blop:~% readelf -l t5 | grep STACK   STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4 

Tandis qu’avec un autre exécutable (notez le RW au lieu du RWE) :

 ***lucas@blop:~% readelf -l t3 | grep STACK   STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4 

C’est un flag ajouté par GCC.

Bravo si vous avez lu jusque là ;)

3 Responses to “GCC, Trampoline, et code auto-modifiable”

  1. Lucas Nussbaum wrote on 03/4/05 at 4:54 pm :

  2. Alban wrote on 03/4/05 at 9:24 pm :

    Merci pour ton billet, j’ai appris des choses intéressantes ;)

  3. Thibault wrote on 03/22/05 at 4:26 pm :

    Oui merci aussi, comme Alban, … sauf que j’ai rien compris :D

    Je crois que je vais lire un peu plus ton blog, ca me fera pas de mal *-)