CSC 4103 – Programmation système

Avant de commencer ce TP, téléchargez l'archive TP6.tgz et extrayez la.

GDB

L'objectif de cet exercice est d'apprendre à débugger un programme avec GDB.

Pour cet exercice, vous aurez à débugger des programmes avec gdb. Vous pourriez bien sûr utiliser d'autres méthodes (ajouter des printf, ou lire et comprendre tous les détails du code, etc.), mais:

Dans la vraie vie (sur de gros projets), ce n'est pas toujours faisable;
Vous rêvez d'apprendre à utiliser un des outils de base du développeur C.

Pour cet exercice, nous vous conseillons de vous référer abondamment à l'annexe gdb.

Le programme à débugger est basé sur le corrigé de l'exercice sur les listes vu lors du CI4. Quelques erreurs plus ou moins subtiles se sont néanmoins glissées dans le programme.

Compilez le programme list et exécutez le.

Exceptionnellement, pour que cet exercice vous entraine correctement à l'utilisation de gdb, compilez votre programme sans les options '-Wall' et '-Werror' ! Vous ne remettrez ces options de compilation que quand l'énoncé vous le suggérera à la question 1.g.

$ gcc -Wall -o list list.c
$ ./list
---- aaa bonjour monde ----
bonjour monde
bonjour
monde
aaa
bonjour
monde
---- que la (-force) soit avec toi ----
Erreur de segmentation
	    

Lancez le programme avec gdb et essayez d'afficher la ligne de code ayant causé l'erreur de segmentation.

$ gdb ./list
[...]
Reading symbols from ./list...(no debugging symbols found)...done.
(gdb) run
Starting program: ./list 
---- aaa bonjour monde ----
bonjour monde
bonjour
monde
aaa
bonjour
monde
---- que la (-force) soit avec toi ----

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554858 in insert ()
(gdb) frame
#0  0x0000555555554858 in insert ()
	    

On remarque que gdb ne peut pas afficher le contenu de la fonction insert. Cela est dû au fait que l'exécutable ne contient pas les symboles de debuggage (cf Reading symbols from ./list...(no debugging symbolso found)...done.)

Compilez maintenant le programme avec l'option -g. Relancez ensuite le programme avec gdb et trouvez la ligne de code causant l'erreur de segmentation.

$ gcc -Wall -g -o list list.c
$ gdb ./list
[...]

Reading symbols from ./list...done.
(gdb) r
Starting program: ./list
---- aaa bonjour monde ----
bonjour monde
bonjour
monde
aaa
bonjour
monde
---- que la (-force) soit avec toi ----

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554858 in insert (list=0x0, str=0x555555554be8 "que") at list.c:30
30        next_node = cur_node->next;
	    

À l'aide des commandes list (ou l) et print (ou p), déterminez la cause de l'erreur de segmentation.

(gdb) list
25      struct node* insert(struct node* list, char str[]) {
26        struct node* cur_node = list;
27        struct node* next_node = NULL;
28        struct node* new_node = create(str);
29
30        next_node = cur_node->next;
31        /* should we insert at the beginning of the list ? */
32        if(strcmp(cur_node->element, str) > 0) {
33          new_node->next = cur_node;
34          /* the list now starts with new_node */
(gdb) print cur_node 
$1 = (struct node *) 0x0
(gdb) print list
$2 = (struct node *) 0x0
	    

Donc, cur_node vaut NULL car le paramètre list est NULL.

En analysant la fonction insert, on voit que cas de l'insertion dans une liste vide n'est pas traité.

Corrigez le bug que vous venez de trouver.

list.c

// list.c
[...]
struct node* insert(struct node* list, char str[]) {
   struct node* cur_node = list;
   struct node* next_node = NULL;
   struct node* new_node = create(str);
   if (!cur_node) {
     /* the list is empty */
     new_node->next = NULL;
     return new_node;
   }

  next_node = cur_node->next;
  /* should we insert at the beginning of the list ? */
  if(strcmp(cur_node->element, str) > 0) {
[...]
	    

Maintenant que l'affichage de la liste fonctionne, la suite du programme s'exécute, mais l'application semble bloquée dans une boucle infinie. Avec Ctrl+C, arrêtez le programme, puis utilisez bt pour examiner la pile d'appels.

$ gdb ./list
(gdb) r
Starting program: ./list 
---- aaa bonjour monde ----
bonjour monde
bonjour
monde
aaa
bonjour
monde
---- que la (-force) soit avec toi ----
avec
force
que
soit
toi
^C
Program received signal SIGINT, Interrupt.
__strcmp_sse2_unaligned () at ../sysdeps/x86_64/multiarch/strcmp-sse2-unaligned.S:33
33      ../sysdeps/x86_64/multiarch/strcmp-sse2-unaligned.S: Aucun fichier ou dossier de ce type.
(gdb) bt
#0  __strcmp_sse2_unaligned () at ../sysdeps/x86_64/multiarch/strcmp-sse2-unaligned.S:33
#1  0x0000555555554974 in destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
#2  0x0000555555554b1f in main (argc=1, argv=0x7fffffffd668) at list.c:113
	    

Utilisez la commande frame <x> pour vous positionner sur la frame contenant la fonction destroy.

(gdb) frame 1
#1  0x0000555555554974 in destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {
	

Utilisez la commande b pour ajouter un point d'arrêt à l'entrée de la boucle. Continuez l'exécution du programme avec c.

Vous remarquerez que le programme s'arrête rapidement sur le point d'arrêt. En continuant l'exécution du programme plusieurs fois, vous remarquerez que la boucle est infinie !

(gdb) b 68
Breakpoint 1 at 0x555555554956: file list.c, line 68.
(gdb) c
Continuing.

Breakpoint 1, destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {
(gdb) c
Continuing.

Breakpoint 1, destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {
(gdb) c
Continuing.

Breakpoint 1, destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {

	    

Afin de comprendre pourquoi la boucle est infinie, nous allons observer le contenu des variables cur_node et next_node. Pour cela, utilisez la commande display afin d'afficher les valeurs de cur_node, *cur_node, *next_node. Continuez l'exécution du programme, et voyez comment les variables évoluent.

(gdb) display cur_node 
1: cur_node = (struct node *) 0x555555757b90
(gdb) display *cur_node 
2: *cur_node = {next = 0x555555757970, element = "avec", '\000' }
(gdb) display next_node 
3: next_node = (struct node *) 0x555555757970
(gdb) display *next_node 
4: *next_node = {next = 0x555555757750, element = "force", '\000' }
(gdb) c
Continuing.

Breakpoint 1, destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {
1: cur_node = (struct node *) 0x555555757b90
2: *cur_node = {next = 0x555555757970, element = "avec", '\000' }
3: next_node = (struct node *) 0x555555757970
4: *next_node = {next = 0x555555757750, element = "force", '\000' }
(gdb) c
Continuing.

Breakpoint 1, destroy (list=0x555555757b90, str=0x555555554c3f "toi") at list.c:68
68        while(next_node && strcmp(next_node->element, str) != 0); {
1: cur_node = (struct node *) 0x555555757b90
2: *cur_node = {next = 0x555555757970, element = "avec", '\000' }
3: next_node = (struct node *) 0x555555757970
4: *next_node = {next = 0x555555757750, element = "force", '\000' }
	    

Une fois le problème identifié, il ne vous reste plus qu'à corriger le programme !

On voit que cur_node et next_node n'avancent pas. En analysant le code, on comprend pourquoi:

 while(next_node && strcmp(next_node->element, str) != 0); {
[...]
  }
	    

Pour corriger le problème, il suffit de supprimer le ; à la fin du while. list.c

Une fois que vous avez corrigé l'erreur et vérifié que votre programme fonctionne correctement, remettez l'erreur dans le fichier source et compilez votre programme avec les options '-Wall' et '-Werror' pour constater que ces options vous auraient permis de détecter l'erreur (mais, cela ne vous aurait pas permis de bien jouer avec gdb, ce qui aurait été trop dommage).

Pointeurs de fonction

L'objectif de cet exercice est de s'exercer à l'utilisation de pointeurs de fonction.

Avant de commencer cet exercice, placez vous dans le répertoire 3-pointeurs

Dans le fichier tri_tabs.c, on définit deux tableaux non triés : un tableau de short et un tableau de double. Pour trier chacun de ces tableaux, nous allons utiliser la fonction qsort de la bibliothèque C. Elle est générique, dans le sens où elle est capable de trier des tableaux de n'importe quel type de données.

Faites man qsort pour comprendre comment travaille cette fonction, et écrivez la fonction compar_short requise pour trier votre tableau de short avec qsort.

Écrivez la fonction compar_double requise pour trier votre tableau de double avec qsort.

Faites l'appel à qsort sur votre tableau de short.

Faites l'appel à qsort sur votre tableau de double.

Compilez votre programme et vérifiez son bon fonctionnement.

tri_tabs_corrige_qsort.c

L'objectif de cette question est de définir une fonction de tri générique basée sur un tri à bulle.

Recopiez le fichier tri_tabs.c que vous avez obtenu à la question précédente en un fichier tri_tabs_bubble.c.

Écrivez une fonction bubble_sort qui a exactement les mêmes paramètres que qsort et dont l'algorithme implémente un tri à bulles.

NB : pour les recopies mémoire dont votre fonction aura besoin, utilisez la fonction memcpy de la bibliothèque C.

Remplacez les appels à qsort par des appels à votre fonction bubble_sort.

Compilez votre programme et vérifiez son bon fonctionnement.

tri_tabs_corrige_bubble.c

Valgrind

L'objectif de cet exercice est d'apprendre à débugger un programme avec Valgrind.

Compilez le programme overflow.c, puis exécutez le en faisant varier le paramètre de 1 à 20. D'après le code source du programme, la valeur de value devrait toujours être 17. Cette assertion est-elle vraie ?

$ ./overflow 1
value = 17
buf[0] = 5
$ ./overflow 2
value = 17
buf[0] = 5
buf[1] = 5
[...]
$ ./overflow 6
value = 5
buf[0] = 5
buf[1] = 5
buf[2] = 5
buf[3] = 5
buf[4] = 5
buf[5] = 5
$ ./overflow 7
value = 17
buf[0] = 5
buf[1] = 5
buf[2] = 5
[...]
$ ./overflow 10
value = 5
buf[0] = 5
buf[1] = 5
buf[2] = 5
[...]
	    

On observe que value=17 la plupart du temps. Toutefois, lorsque le paramètre vaut 6, 10, 14, ou 18, la valeur de value est 5.

L'initialisation de buffer semble donc avoir affecté value.

Utilisez valgrind pour lancer le programme dans un des cas problématiques et trouvez la ligne de code responsable du problème. Répétez l'opération pour un des cas non-problématiques. Valgrind affiche-t-il une erreur ?

$ valgrind ./overflow 6
==11409== Memcheck, a memory error detector
==11409== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==11409== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==11409== Command: ./overflow 6
==11409== 
==11409== Invalid write of size 4
==11409==    at 0x40059E: init_tab (overflow.c:7)
==11409==    by 0x400628: main (overflow.c:19)
==11409==  Address 0x51d9058 is 0 bytes after a block of size 24 alloc'd
==11409==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==11409==    by 0x4005F8: main (overflow.c:16)
==11409== 
value = 17
buf[0] = 5
buf[1] = 5
buf[2] = 5
buf[3] = 5
buf[4] = 5
buf[5] = 5
==11409== 
==11409== HEAP SUMMARY:
==11409==     in use at exit: 28 bytes in 2 blocks
==11409==   total heap usage: 3 allocs, 1 frees, 1,052 bytes allocated
==11409== 
==11409== LEAK SUMMARY:
==11409==    definitely lost: 28 bytes in 2 blocks
==11409==    indirectly lost: 0 bytes in 0 blocks
==11409==      possibly lost: 0 bytes in 0 blocks
==11409==    still reachable: 0 bytes in 0 blocks
==11409==         suppressed: 0 bytes in 0 blocks
==11409== Rerun with --leak-check=full to see details of leaked memory
==11409== 
==11409== For counts of detected and suppressed errors, rerun with: -v
==11409== ERROR SUMMARY: 3 errors from 1 contexts (suppressed: 0 from 0)
		

On remarque le message d'erreur de valgrind: Invalid write of size 4.

Ce message apparaît lorsque le programme écrit en dehors d'une zone allouée. La ligne de code responsable de l'erreur se trouve dans init_tab à la ligne 7: tab[i] = 5;

Au passage, on remarque que lorsqu'on exécute le programme avec valgrind, le bug n'apparaît plus (value est bien égal à 17). Ceci est dû à la méthode qu'utilise valgrind pour détecter les accès mémoires incorrects.

Pour un cas non problématique (par exemple, 2), valgrind détecte également un accès incorrect:

$ valgrind ./overflow 2
==11454== Memcheck, a memory error detector
==11454== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==11454== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==11454== Command: ./overflow 2
==11454== 
==11454== Invalid write of size 4
==11454==    at 0x40059E: init_tab (overflow.c:7)
==11454==    by 0x400628: main (overflow.c:19)
==11454==  Address 0x51d9048 is 0 bytes after a block of size 8 alloc'd
==11454==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==11454==    by 0x4005F8: main (overflow.c:16)
==11454== 
value = 17
buf[0] = 5
buf[1] = 5
[...]
		

Il semble dont que le bug soit présent quelle que soit la valeur du paramètre.

Maintenant que vous avez identifié la portion de code responsable du problème, utilisez maintenant gdb pour observer la valeur pointée par value. Pour cela, ajoutez un breakpoint au début de la fonction buggée, puis ajoutez un watchpoint sur la zone pointée par value.

Une fois le problème identifié, vous pouvez corriger le problème et vérifier avec valgrind qu'il n'y a plus d'accès mémoire incorrect.

$ gdb ./overflow 
[...]
(gdb) b init_tab
Breakpoint 1 at 0x400581: file overflow.c, line 6.
(gdb) r 6
Starting program: ./overflow 6

Breakpoint 1, init_tab (tab=0x601010, size=7) at overflow.c:6
6	  for(i=0; ibt
#0  init_tab (tab=0x601010, size=7) at overflow.c:6
#1  0x0000000000400629 in main (argc=2, argv=0x7fffffffdd38) at overflow.c:19
(gdb) frame 1
#1  0x0000000000400629 in main (argc=2, argv=0x7fffffffdd38) at overflow.c:19
19	  init_tab(buffer, size+1);
(gdb) p *value
$1 = 17
(gdb) watch *value
Hardware watchpoint 2: *value
(gdb) c
Continuing.


Hardware watchpoint 2: *value

Old value = 17
New value = 5
init_tab (tab=0x601010, size=7) at overflow.c:6
6	  for(i=0; i
(gdb) p i
$2 = 8
		

Le bug est donc causé par la fonction init_tab lorsqu'on modifie la valeur d'indice 8 de buffer. Comme le buffer est de taille 6, la case d'indice 8 est en dehors du tableau. Il se trouve que cette case correspond à l'emplacement mémoire pointé par value.

Ce type de bug s'appelle buffer overflow (en français: débordement de tampon). Il s'agit d'un bug pouvant causer des failles de sécurités importantes. Cette technique est fréquemment utilisée par les pirates à des fins malveillantes.

Un attaquant peut par exemple modifier une valeur stratégique (par exemple, l'identifiant de l'utilisateur, afin de se faire passer pour un administrateur).

Si la zone mémoire de laquelle on déborde est située sur la pile, il devient possible pour l'attaquant de changer le flot d'exécution du programme (en changeant l'adresse de retour de la fonction). Il s'agit alors d'un stack overflow, responsable d'un grand nombre d'attaques logicielles.

Pour cet exercice, nous allons étudier le programme nbody.c. Il s'agit d'un simulation NBody: le programme simule les interactions gravitationnelles d'un ensemble de corps. C'est à l'aide de ce type de programmes qu'on tente de comprendre la formation de galaxies (par exemple).

Le programme nbody.c alloue un ensemble de particules (des planètes, des étoiles, etc.), chacune caractérisée par une position, une vitesse, et une masse. La simulation consiste, pour chaque pas de temps, à calculer l'interaction gravitationnelle que chaque particule fait subir à chaque autre particule. Une fois la force appliquée à chaque particule calculée, on calcule ses nouvelles position et vitesse avant de passer au pas de temps suivant.

Exécutez le programme nbody avec valgrind. Essayez de comprendre la source des erreurs affichées par valgrind.

$ valgrind ./nbody
==13304== Memcheck, a memory error detector
==13304== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==13304== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==13304== Command: ./nbody
==13304== 
==13304== Conditional jump or move depends on uninitialised value(s)
==13304==    at 0x400970: compute_force (nbody.c:62)
==13304==    by 0x400CCB: all_move_particles (nbody.c:110)
==13304==    by 0x400D72: run_simulation (nbody.c:126)
==13304==    by 0x400E59: main (nbody.c:157)
==13304== 
==13304== Conditional jump or move depends on uninitialised value(s)
==13304==    at 0x4E592C8: sqrt (w_sqrt.c:27)
==13304==    by 0x400B39: move_particle (nbody.c:83)
==13304==    by 0x400D1F: all_move_particles (nbody.c:116)
==13304==    by 0x400D72: run_simulation (nbody.c:126)
==13304==    by 0x400E59: main (nbody.c:157)
==13304== 
==13304== Conditional jump or move depends on uninitialised value(s)
==13304==    at 0x4E592C8: sqrt (w_sqrt.c:27)
==13304==    by 0x400B97: move_particle (nbody.c:85)
==13304==    by 0x400D1F: all_move_particles (nbody.c:116)
==13304==    by 0x400D72: run_simulation (nbody.c:126)
==13304==    by 0x400E59: main (nbody.c:157)
==13304== 
[...]
	    

Il semble que certaines données n'aient pas été initialisées.

Utilisez l'option --track-origins=yes pour trouver de manière plus précise l'origine du problème. Corrigez ensuite le problème.

$ valgrind --track-origins=yes ./nbody
==13320== Memcheck, a memory error detector
==13320== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==13320== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==13320== Command: ./nbody
==13320== 
==13320== Conditional jump or move depends on uninitialised value(s)
==13320==    at 0x400970: compute_force (nbody.c:62)
==13320==    by 0x400CCB: all_move_particles (nbody.c:110)
==13320==    by 0x400D72: run_simulation (nbody.c:126)
==13320==    by 0x400E59: main (nbody.c:157)
==13320==  Uninitialised value was created by a heap allocation
==13320==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==13320==    by 0x400842: all_init_particles (nbody.c:44)
==13320==    by 0x400E3E: main (nbody.c:150)
==13320== 
==13320== Conditional jump or move depends on uninitialised value(s)
==13320==    at 0x4E592C8: sqrt (w_sqrt.c:27)
==13320==    by 0x400B39: move_particle (nbody.c:83)
==13320==    by 0x400D1F: all_move_particles (nbody.c:116)
==13320==    by 0x400D72: run_simulation (nbody.c:126)
==13320==    by 0x400E59: main (nbody.c:157)
==13320==  Uninitialised value was created by a heap allocation
==13320==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==13320==    by 0x400842: all_init_particles (nbody.c:44)
==13320==    by 0x400E3E: main (nbody.c:150)
[...]
	    

Les données allouées à la ligne 44 (particle->pos = malloc(sizeof(struct vector)); ne sont pas toutes initialisées.

Le problème se résout en initialisant pos et vel:

    particle->pos = malloc(sizeof(struct vector));
    particle->vel = malloc(sizeof(struct vector));
    particle->force = malloc(sizeof(struct vector));

    particle->pos->x = i*2.0/nparticles - 1.0;
    particle->pos->y = 0;

    particle->vel->y = particle->pos->x;
    particle->vel->x = 0;
	    

nbody.c

Le programme souffre d'un autre problème. Comme le montre valgrind, certaines zones mémoires sont "définitivement perdues". Utilisez valgrind pour trouver les buffers en question et corrigez le problème.

$ valgrind --leak-check=full ./nbody
[...]
==15831== 
==15831== HEAP SUMMARY:
==15831==     in use at exit: 480 bytes in 30 blocks
==15831==   total heap usage: 32 allocs, 2 frees, 1,824 bytes allocated
==15831== 
==15831== 160 bytes in 10 blocks are definitely lost in loss record 1 of 3
==15831==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==15831==    by 0x400882: all_init_particles (nbody.c:44)
==15831==    by 0x400E9E: main (nbody.c:153)
==15831== 
==15831== 160 bytes in 10 blocks are definitely lost in loss record 2 of 3
==15831==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==15831==    by 0x400896: all_init_particles (nbody.c:45)
==15831==    by 0x400E9E: main (nbody.c:153)
==15831== 
==15831== 160 bytes in 10 blocks are definitely lost in loss record 3 of 3
==15831==    at 0x4C2BBCF: malloc (vg_replace_malloc.c:299)
==15831==    by 0x4008AB: all_init_particles (nbody.c:46)
==15831==    by 0x400E9E: main (nbody.c:153)
==15831== 
==15831== LEAK SUMMARY:
==15831==    definitely lost: 480 bytes in 30 blocks
==15831==    indirectly lost: 0 bytes in 0 blocks
==15831==      possibly lost: 0 bytes in 0 blocks
==15831==    still reachable: 0 bytes in 0 blocks
==15831==         suppressed: 0 bytes in 0 blocks
==15831== 
==15831== For counts of detected and suppressed errors, rerun with: -v
==15831== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
	    

Les zones allouées aux ligne 44 à 46 du fichiers ne sont pas libérée:

    particle->pos = malloc(sizeof(struct vector));
    particle->vel = malloc(sizeof(struct vector));
    particle->force = malloc(sizeof(struct vector));
	    

Lorsque le programme libère le tableau particles, les zones correspondant aux pos, vel et force des particules restent allouées, mais ne sont plus accessibles (puisqu'on "oublie" leur adresse).

Pour corriger le problème, il est nécessaire d'appeler free() pour chacun des buffers alloués:

for (i = 0; i nbody.c