Les 4 bins de ptmalloc2, à quoi ils
servent vraiment

Les quatre familles de bins ptmalloc2 : fast bins (sans fusion), unsorted bin (DCLL pour la seconde chance), small bins (moins de 512 octets) et large bins triees par classes de taille.

Maxime J10 mars 20265 min de lecture

Un doute sur votre exposition ?

On audite votre surface d'attaque externe et on vous dit ce qui est exploitable.

Parler à un pentester

Prerequis

Langage C
Syscalls Linux
Maniement de GCC
Introduction a ptmalloc2
Chunks
Arenas

Hello ! o/

La derniere fois on avait vu les arenas, enfin surtout comment la heap etait structuree au final. Il y a encore des choses a creuser, et une de ces choses ce sont les bins (les poubelles). Lors de la liberation d'un chunk, celui-ci est automatiquement mis dans une bin, et c'est bien sur le role de free(3).

Pour augmenter les performances de l'allocation memoire, ptmalloc2 implemente plusieurs bins : fast, unsorted, small et large.

Fast bins

Comme on l'a vu dans l'article sur les arenas, il y a un tableau de 10 elements qui correspond a fastbinsY. Ces elements sont en realite des listes chainees simplement de tailles 16, 24, 32, jusqu'a 80, avec un pas (step) de 8 octets. Une particularite de ces chunks : on ne permet pas leur fusion pour former un chunk plus gros. Ca les rend ultra-rapides a allouer et liberer, au prix d'une fragmentation potentielle.

Pourquoi pas de fusion ?

Les fast bins ciblent des allocations courtes et frequentes (buffers temporaires, petites structures). Eviter la fusion supprime le cout de coalescence et rend le path malloc/free quasi constant pour ces tailles.

fastbinsY.txt

  fastbinsY (dans malloc_state / arena)
  ┌─────────────────────────────────────────────────────────────┐
  │ [0] taille 16   → [ chunk ] → [ chunk ] → NULL             │
  │ [1] taille 24   → [ chunk ] → NULL                         │
  │ [2] taille 32   → [ chunk ] → [ chunk ] → [ chunk ] → NULL │
  │ [3] taille 40   → NULL                                      │
  │ [4] taille 48   → [ chunk ] → NULL                         │
  │ [5] taille 56   → NULL                                      │
  │ [6] taille 64   → [ chunk ] → NULL                         │
  │ [7] taille 72   → NULL                                      │
  │ [8] taille 80   → NULL                                      │
  │ [9] (reserve)   → NULL                                      │
  └─────────────────────────────────────────────────────────────┘

  Chaque chunk freed conserve :
  ┌────────┬────────┬─────────────────────────────────┐
  │  prev  │  size  │  fd (Forward pointer) → suivant │
  │  size  │        │  (pas de bk dans les fast bins) │
  └────────┴────────┴─────────────────────────────────┘

fastbinsY : 10 listes chainees independantes, une par classe de taille. Les chunks freed pointent vers le precedent via fd (Forward pointer).

Source : Understanding glibc malloc, sploitfun

Unsorted bin

Dans le cas ou vous liberez un chunk qui correspond a une bin Small ou Large, il est d'abord mis dans l'Unsorted bin. Ca lui donne une 2e chance : si vous devez free une structure pour rea-allouer derriere une structure de meme taille, cette bin prend toute son importance dans les performances.

Il n'y a qu'une seule unsorted bin, et elle est sous la forme d'une DCLL (Doubly Circular Linked List = liste doublement chainee circulaire). Les chunks freed conservent ici deux pointeurs : FD (Forward pointer) et BK (Backward pointer).

unsorted-bin.txt

  unsorted_bin (dans bins[1])
  ┌──────────────────────────────────────────────────────────┐
  │                                                          │
  │   ┌──────────────────────────────────────────────────┐   │
  │   │                                                  │   │
  │   ▼                                                  │   │
  │  HEAD ◄──── chunk_A ◄──── chunk_B ◄──── chunk_C     │   │
  │   │          │              │              │          │   │
  │   └──────────┘              │              │          │   │
  │              └──────────────┘              │          │   │
  │                             └──────────────┘──────────┘   │
  │                                                          │
  │  Structure d'un chunk freed dans l'unsorted bin :        │
  │  ┌──────────┬──────────┬──────────┬────────────────────┐ │
  │  │ prev_sz  │   size   │    fd    │        bk          │ │
  │  │          │          │ (Forward)│    (Backward)      │ │
  │  └──────────┴──────────┴──────────┴────────────────────┘ │
  └──────────────────────────────────────────────────────────┘

L'unsorted bin : une DCLL (liste doublement chainee circulaire) unique. Chaque chunk freed pointe vers ses voisins via fd et bk.

Source : Understanding glibc malloc, sploitfun

Small bins

Il y a 62 small bins, toutes sous forme de DCLL (Doubly Circular Linked List, comme l'unsorted bin). Elles acceptent tous les chunks < 512 octets. Elles sont evidemment moins rapides que les fast bins. Les tailles vont de 16 a 504 avec un pas de 8.

Contrairement aux fast bins, la fusion de chunks est ici possible : si deux chunks freed sont adjacents en memoire et qu'on peut satisfaire une demande avec leur reunion, on les coalesce en un seul. Ca evite la fragmentation.

small-bins.txt

  small bins (dans bins[2..63])

  bins[2]  taille 16  : HEAD ◄► chunk ◄► chunk ◄► HEAD (circulaire)
  bins[3]  taille 24  : HEAD ◄► chunk ◄► HEAD
  bins[4]  taille 32  : HEAD ◄► HEAD (vide)
  ...
  bins[63] taille 504 : HEAD ◄► chunk ◄► HEAD

  Fusion de chunks adjacents :
  ┌────────────────────────────────────────────────────────────┐
  │  [chunk_A freed] [chunk_B freed]  →  [chunk_AB fusionne]  │
  │   taille 64       taille 64            taille 128          │
  └────────────────────────────────────────────────────────────┘
  Insertion : FIFO (First In, First Out)

62 small bins : une DCLL par classe de taille (16, 24, ..., 504). Insertion en tete (FIFO : First In, First Out), et fusion possible entre voisins freed.

Large bins

Il y a 63 large bins, pour tous les chunks >= 512 octets. Ce sont les bins les plus lentes : les chunks n'ont pas tous la meme taille dans une meme bin, et la liste est triee. La fusion de chunks est evidemment possible, et heureusement : sinon imaginez les trous en memoire que ca ferait...

Les 63 large bins sont reparties en 6 groupes, chacun couvrant une plage de tailles avec un pas different :

Nb de bins	Debut (octets)	Fin (octets)	Pas (step)
32	512	2432	64
16	2433	10240	512
8	10241	40960	4096
4	40961	131072	32768
2	131073	524288	262144
1	524289	sans limite	-

Pourquoi des pas croissants ?

Plus les chunks sont grands, moins il y a d'allocations de ces tailles. Avoir un pas de 64 pour les petites large bins permet une granularite fine la ou elle compte ; les tres grandes tailles (512 Ko+) tiennent toutes dans une seule bin car elles sont si rares que le tri interne suffit.

large-bins-structure.txt

  large bin (exemple : bins[64], taille 512..575)
  ┌────────────────────────────────────────────────────────────────┐
  │                                                                │
  │  HEAD ◄──────────────────────────────────────────────────┐    │
  │   │                                                       │    │
  │   ▼                                                       │    │
  │  [chunk 568] ◄──fd/bk──► [chunk 568] ◄──fd/bk──► [chunk 524] │
  │       │                                                │       │
  │  fd_nextsize ◄────────────────────────────────────────┘       │
  │  bk_nextsize ──────────────────────────────────────────►      │
  │                                                                │
  │  Structure chunk freed large bin :                             │
  │  ┌────────┬────────┬────┬────┬─────────────┬─────────────┐    │
  │  │prev_sz │  size  │ fd │ bk │ fd_nextsize │ bk_nextsize │    │
  │  └────────┴────────┴────┴────┴─────────────┴─────────────┘    │
  │                     trie par taille decroissante               │
  └────────────────────────────────────────────────────────────────┘

Dans chaque large bin, les chunks sont tries par taille decroissante (LIFO : Last In, First Out pour les egaux). Chaque chunk conserve fd_nextsize et bk_nextsize pour naviguer entre tailles differentes.

Recapitulatif

En resume, les quatre familles de bins de ptmalloc2 et leurs caracteristiques cles :

Bin	Nb	Taille chunks	Structure	Fusion
Fast	10	16..80	Liste simplement chainee (fd seul)	Non
Unsorted	1	Small ou Large	DCLL (fd + bk)	Oui
Small	62	16..504 (< 512)	DCLL (fd + bk)	Oui
Large	63	>= 512	DCLL triee (fd + bk + fd_nextsize + bk_nextsize)	Oui

Veille sécurité

Ce qui bouge vraiment sur la surface d'attaque externe, NIS2 et la sécurité applicative, écrit par le pentester qui signe ces articles. Un envoi par mois, désinscription en un clic.

Votre adresse ne sert qu'à cet envoi. Voir la politique de confidentialité.