Hoe werkt glibc malloc?

Om te begrijpen hoe dynamische geheugentoewijzing (de malloc, free, calloc, realloc bibliotheekfuncties) echt werkt, is er geen vervanging voor het lezen van de broncode van malloc(). Het is goed becommentarieerd:

opmerkingen over brokken:

/* 1056 malloc_chunk details: 1057 1058 (The following includes lightly edited explanations by Colin Plumb.) 1059 1060 Chunks of memory are maintained using a `boundary tag" method as 1061 described in e.g., Knuth or Standish. (See the paper by Paul 1062 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a 1063 survey of such techniques.) Sizes of free chunks are stored both 1064 in the front of each chunk and at the end. This makes 1065 consolidating fragmented chunks into bigger chunks very fast. The 1066 size fields also hold bits representing whether chunks are free or 1067 in use. 1068 1069 An allocated chunk looks like this: 1070 1071 1072 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1073 | Size of previous chunk, if unallocated (P clear) | 1074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1075 | Size of chunk, in bytes |A|M|P| 1076 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1077 | User data starts here... . 1078 . . 1079 . (malloc_usable_size() bytes) . 1080 . | 1081 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1082 | (size of chunk, but used for application data) | 1083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1084 | Size of next chunk, in bytes |A|0|1| 1085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1086 1087 Where "chunk" is the front of the chunk for the purpose of most of 1088 the malloc code, but "mem" is the pointer that is returned to the 1089 user. "Nextchunk" is the beginning of the next contiguous chunk. 1090 1091 Chunks always begin on even word boundaries, so the mem portion 1092 (which is returned to the user) is also on an even word boundary, and 1093 thus at least double-word aligned. 1094 1095 Free chunks are stored in circular doubly-linked lists, and look like this: 1096 1097 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1098 | Size of previous chunk, if unallocated (P clear) | 1099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1100 `head:" | Size of chunk, in bytes |A|0|P| 1101 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1102 | Forward pointer to next chunk in list | 1103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1104 | Back pointer to previous chunk in list | 1105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1106 | Unused space (may be 0 bytes long) . 1107 . . 1108 . | 1109 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1110 `foot:" | Size of chunk, in bytes | 1111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1112 | Size of next chunk, in bytes |A|0|0| 1113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1114 1115 The P (PREV_INUSE) bit, stored in the unused low-order bit of the 1116 chunk size (which is always a multiple of two words), is an in-use 1117 bit for the *previous* chunk. If that bit is *clear*, then the 1118 word before the current chunk size contains the previous chunk 1119 size, and can be used to find the front of the previous chunk. 1120 The very first chunk allocated always has this bit set, 1121 preventing access to non-existent (or non-owned) memory. If 1122 prev_inuse is set for any given chunk, then you CANNOT determine 1123 the size of the previous chunk, and might even get a memory 1124 addressing fault when trying to do so. 1125 1126 The A (NON_MAIN_ARENA) bit is cleared for chunks on the initial, 1127 main arena, described by the main_arena variable. When additional 1128 threads are spawned, each thread receives its own arena (up to a 1129 configurable limit, after which arenas are reused for multiple 1130 threads), and the chunks in these arenas have the A bit set. To 1131 find the arena for a chunk on such a non-main arena, heap_for_ptr 1132 performs a bit mask operation and indirection through the ar_ptr 1133 member of the per-heap header heap_info (see arena.c). 1134 1135 Note that the `foot" of the current chunk is actually represented 1136 as the prev_size of the NEXT chunk. This makes it easier to 1137 deal with alignments etc but can be very confusing when trying 1138 to extend or adapt this code. 1139 1140 The three exceptions to all this are: 1141 1142 1. The special chunk `top" doesn"t bother using the 1143 trailing size field since there is no next contiguous chunk 1144 that would have to index off it. After initialization, `top" 1145 is forced to always exist. If it would become less than 1146 MINSIZE bytes long, it is replenished. 1147 1148 2. Chunks allocated via mmap, which have the second-lowest-order 1149 bit M (IS_MMAPPED) set in their size fields. Because they are 1150 allocated one-by-one, each must contain its own trailing size 1151 field. If the M bit is set, the other bits are ignored 1152 (because mmapped chunks are neither in an arena, nor adjacent 1153 to a freed chunk). The M bit is also used for chunks which 1154 originally came from a dumped heap via malloc_set_state in 1155 hooks.c. 1156 1157 3. Chunks in fastbins are treated as allocated chunks from the 1158 point of view of the chunk allocator. They are consolidated 1159 with their neighbors only in bulk, in malloc_consolidate. 1160 */ 

opmerkingen over interne datastructuren:

/* 1313 -------------------- Internal data structures -------------------- 1314 1315 All internal state is held in an instance of malloc_state defined 1316 below. There are no other static variables, except in two optional 1317 cases: 1318 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above. 1319 * If mmap doesn"t support MAP_ANONYMOUS, a dummy file descriptor 1320 for mmap. 1321 1322 Beware of lots of tricks that minimize the total bookkeeping space 1323 requirements. The result is a little over 1K bytes (for 4byte 1324 pointers and size_t.) 1325 */ 1326 1327 /* 1328 Bins 1329 1330 An array of bin headers for free chunks. Each bin is doubly 1331 linked. The bins are approximately proportionally (log) spaced. 1332 There are a lot of these bins (128). This may look excessive, but 1333 works very well in practice. Most bins hold sizes that are 1334 unusual as malloc request sizes, but are more usual for fragments 1335 and consolidated sets of chunks, which is what these bins hold, so 1336 they can be found quickly. All procedures maintain the invariant 1337 that no consolidated chunk physically borders another one, so each 1338 chunk in a list is known to be preceeded and followed by either 1339 inuse chunks or the ends of memory. 1340 1341 Chunks in bins are kept in size order, with ties going to the 1342 approximately least recently used chunk. Ordering isn"t needed 1343 for the small bins, which all contain the same-sized chunks, but 1344 facilitates best-fit allocation for larger chunks. These lists 1345 are just sequential. Keeping them in order almost never requires 1346 enough traversal to warrant using fancier ordered data 1347 structures. 1348 1349 Chunks of the same size are linked with the most 1350 recently freed at the front, and allocations are taken from the 1351 back. This results in LRU (FIFO) allocation order, which tends 1352 to give each chunk an equal opportunity to be consolidated with 1353 adjacent freed chunks, resulting in larger free chunks and less 1354 fragmentation. 1355 1356 To simplify use in double-linked lists, each bin header acts 1357 as a malloc_chunk. This avoids special-casing for headers. 1358 But to conserve space and improve locality, we allocate 1359 only the fd/bk pointers of bins, and then use repositioning tricks 1360 to treat these as the fields of a malloc_chunk*. 1361 */ 

Een van de auteurs van malloc(), Doug Lea, heeft een artikel geschreven met de naam “ A Memory Allocator ” waarin wordt beschreven hoe malloc werkt (merk op dat het artikel uit 2000 komt, dus er zal wat verouderde informatie zijn).

Uit het artikel:

Brokken:

Bakken:

Een extra bron is hoofdstuk 7: “Geheugentoewijzing” van “The Linux Programming Interface” door Michael Kerrisk. TLPI is de beste referentie van elk type dat ik ooit ben tegengekomen en kan het niet sterk genoeg aanbevelen.

Hier is een diagram van de implementatie van malloc() en free() van TLPI:

Tot slot malloc() is een wrapper rond de brk() en sbrk() systeemaanroepen, die de grootte van de heap wijzigen door de locatie van het programmaonderbreking te wijzigen.

Van opmerkingen in de bron:

 901 In the new situation, brk() and mmap space is shared and there are no 902 artificial limits on brk size imposed by the kernel. What is more, 903 applications have started using transient allocations larger than the 904 128Kb as was imagined in 2001. 905 906 The price for mmap is also high now; each time glibc mmaps from the 907 kernel, the kernel is forced to zero out the memory it gives to the 908 application. Zeroing memory is expensive and eats a lot of cache and 909 memory bandwidth. This has nothing to do with the efficiency of the 910 virtual memory system, by doing mmap the kernel just has no choice but 911 to zero. 912 913 In 2001, the kernel had a maximum size for brk() which was about 800 914 megabytes on 32 bit x86, at that point brk() would hit the first 915 mmaped shared libaries and couldn"t expand anymore. With current 2.6 916 kernels, the VA space layout is different and brk() and mmap 917 both can span the entire heap at will. 918 919 Rather than using a static threshold for the brk/mmap tradeoff, 920 we are now using a simple dynamic one. The goal is still to avoid 921 fragmentation. The old goals we kept are 922 1) try to get the long lived large allocations to use mmap() 923 2) really large allocations should always use mmap() 924 and we"re adding now: 925 3) transient allocations should use brk() to avoid forcing the kernel 926 having to zero memory over and over again 927 928 The implementation works with a sliding threshold, which is by default 929 limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts 930 out at 128Kb as per the 2001 default. 931 932 This allows us to satisfy requirement 1) under the assumption that long 933 lived allocations are made early in the process" lifespan, before it has 934 started doing dynamic allocations of the same size (which will 935 increase the threshold). 936 937 The upperbound on the threshold satisfies requirement 2) 938 939 The threshold goes up in value when the application frees memory that was 940 allocated with the mmap allocator. The idea is that once the application 941 starts freeing memory of a certain size, it"s highly probable that this is 942 a size the application uses for transient allocations. This estimator 943 is there to satisfy the new third requirement. 944 945 */ 

Er zijn verschillende redelijk goede referenties over de exploitatie van de hoop in software beveiliging, een van mijn favorieten is waarschijnlijk de “ cursus voor binair hacken ” van LiveOverflow .

Je kunt de volgende lezingen bekijken voor een vereenvoudigde benadering van het heapbeheer (met behulp van de Protostar oefenset van Exploit-oefeningen ):

• 0x14 – The Heap: wat doet malloc() doen?
• 0x15 – The Heap: Hoe misbruik te maken van een Heap Overflow
• 0x16 – The Heap: Hoe werken use-after-free exploits?
• 0x17 – The Heap: Once upon a free()
• 0x18 – The Heap: dlmalloc unlink() exploit

En ook:

• 0x1F – [Live] Remote oldschool dlmalloc Heap exploit

Vervolgens kunt u proberen de beschrijvingen van alle Heap-oefeningen op Protostar .

Maar de blogberichten van sploitfun is een van de meest nauwkeurige artikelen die ik ooit op internet heb gezien over dit specifieke onderwerp. Ik zou je aanraden om terug te keren naar de artikelen van sploitfun zodra je voldoende begrip hebt van de basisprincipes.