memalloc - HackMD

## Preface Yo! This article is written for the 9th day of the [nitkc advent calender](https://qiita.com/advent-calendar/2024/nit_kisarazu). The previous, 8th day of it is [CloudflareはDNSだけじゃない!](https://qiita.com/toreis/items/a31e1c59b40ca8604935) by [@toreis](https://qiita.com/toreis). Check it out! The next, 10th day will be wirtten by [NXVZBGBFBEN](https://qiita.com/NXVZBGBFBEN).I'm looking forward it!Do NOT miss it! First of all, let me introduce myself. ## Introduction of @tsuneki * Ungraduate student of National Institute of Technology, Kisarazu College. * Majoring for computer security. * Working at GMO CyberSecurity by IERAE INC,. as a security engineer. * CTF player with team: sush1st, ierae, m01nm01n. * Click [here](https://yayoi-cs.github.io/my-next/ctf) to check my CTF results. Additionary our team, m01nm01n [got a 1st place in Kosen-SECCON 2024!](https://x.com/HTsun3k1/status/1865312501807878406) I perfectly solved all binary exploitation and programming challenge. That’s enough for the intro, let’s jump into the main topic! ## Memory allocator In this article, I will explain two types of memory allocators: those in kernel space and userland, with a focus on glibc malloc. ### Userland, glibc malloc Glibc malloc is a interface to allocate memory dynamicly. #### Basic heap information * structure The heap is located on the opposite side of the stack, but its structure is not LIFO. Instead, the heap is an unstructured memory area that supports dynamic allocation. |stack|heap| |-|-| |↓|| ||| ||| ||↑| you can check stack and heap address with vmmap command in gdb(require extentions.I reccomend [pwndbg](https://github.com/pwndbg/pwndbg) or [beta24/gef](https://github.com/bata24/gef)) ![image](https://hackmd.io/_uploads/B1E62z74Jg.png) Let's check heap structure. I use this code which I create in programming class. ```clike= #include<stdio.h> #include<stdlib.h> #include <string.h> #include <ctype.h> typedef struct Club { char FirstName[25]; char LastName[25]; char Department[25]; int SchoolYear; int CommutingTime; int Fare; struct Club *NextMember; }ClubMembers; ClubMembers *FirstMember=NULL; void AddMembers() { ClubMembers *NewMember, *CurrentMember; NewMember=(ClubMembers*)malloc(sizeof(ClubMembers)); printf("Type Details of New Member:\n"); printf("First Name\n"); scanf("%s",NewMember->FirstName); printf("Last Name\n"); scanf("%s",NewMember->LastName); printf("Department(for eg. Information, Mechanical, Civil, Elecrical, Control etc)\n"); scanf("%s",NewMember->Department); printf("School Year (1~5)\n"); scanf("%d",&NewMember->SchoolYear); printf("Commuting Time(in minutes)\n"); scanf("%d",&NewMember->CommutingTime); printf("Transportation Fare(in JPY)\n"); scanf("%d",&NewMember->Fare); NewMember->NextMember=NULL; if (FirstMember==NULL) { FirstMember=NewMember; return; } CurrentMember=FirstMember; while (CurrentMember->NextMember!=NULL) { CurrentMember=CurrentMember->NextMember; } CurrentMember->NextMember=NewMember; } void DisplayMembers() { if(FirstMember == NULL){ printf("Please set the data!!!\n"); return; } ClubMembers *CurrentMember = FirstMember; while(1){ printf("--------------------------\n"); printf("FirstName\t: %s\n",CurrentMember->FirstName); printf("LastName\t: %s\n",CurrentMember->LastName); printf("Department\t: %s\n",CurrentMember->Department); printf("SchoolYear\t: %d\n",CurrentMember->SchoolYear); printf("CommutingTime\t: %d\n",CurrentMember->CommutingTime); printf("Fare\t: %d\n",CurrentMember->Fare); if(CurrentMember->NextMember == NULL) break; CurrentMember = CurrentMember->NextMember; } printf("--------------------------\n"); printf("That's all!!\n"); } void RemoveMembers(){ if(FirstMember == NULL){ printf("Please set the data!!!\n"); return; } char tmpFN[25]; char tmpLN[25]; printf("FirstName? : "); scanf("%s",tmpFN); printf("LastName? : "); scanf("%s",tmpLN); ClubMembers *CurrentMember = FirstMember; ClubMembers *preData = NULL; while(1){ if(strncmp(tmpFN,CurrentMember->FirstName,24)==0 && strncmp(tmpLN,CurrentMember->LastName,24)==0){ if(preData == NULL){ if(FirstMember->NextMember == NULL){FirstMember = NULL;} else{ printf("FirstMember will delete.\n"); FirstMember = FirstMember->NextMember; } } else{ preData->NextMember = CurrentMember->NextMember; } free(CurrentMember); printf("%s %s was deleted.\n",tmpFN,tmpLN); return; } preData == CurrentMember; if(CurrentMember->NextMember == NULL){printf("No data was deleted\n");break;} CurrentMember = CurrentMember->NextMember; } } int main() { char KeyBoardInput,Options; while(1) { printf("A:Add, D:Display, R:Remove Q:Quit\n"); printf("Type desired options(A,D,R,Q):"); scanf("%s",&KeyBoardInput); Options=toupper(KeyBoardInput); switch (Options) { case 'A': AddMembers(); break; case 'D': DisplayMembers(); break; case 'R': RemoveMembers(); break; case 'Q': return 0; default: printf("Invalid Option.\n"); break; } } } ``` As you can read, this program has obvious vulnerability. I'll exploit this code later. ```gdb= pwndbg> disass main -----------------------------omit-------------------------------- 0x00000000000016eb <+66>: mov rsi,rax 0x00000000000016ee <+69>: lea rax,[rip+0x93a] # 0x202f 0x00000000000016f5 <+76>: mov rdi,rax 0x00000000000016f8 <+79>: mov eax,0x0 0x00000000000016fd <+84>: call 0x1130 <__isoc99_scanf@plt> 0x0000000000001702 <+89>: movzx eax,BYTE PTR [rbp-0xa] 0x0000000000001706 <+93>: movsx eax,al 0x0000000000001709 <+96>: mov edi,eax ``` I'll set the breakpoint into *main+84 to check the heap status every input. :::info 1. adding kisarazu hanako ```gdb= 0x555555559ab0 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559ac0 0x757a61726173696b 0x0000000000000000 kisarazu........ 0x555555559ad0 0x0000000000000000 0x006f6b616e616800 .........hanako. 0x555555559ae0 0x0000000000000000 0x0000000000000000 ................ 0x555555559af0 0x6d726f666e690000 0x0000006e6f697461 ..information... 0x555555559b00 0x0000000000000000 0x0000000300000000 ................ 0x555555559b10 0x000186a00001bf52 0x0000000000000000 R............... 0x555555559b20 0x0000000000000000 0x00000000000204e1 ................ <-- Top chunk ``` 2. adding kiyomidai kotaro ```gdb= 0x555555559ab0 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559ac0 0x757a61726173696b 0x0000000000000000 kisarazu........ 0x555555559ad0 0x0000000000000000 0x006f6b616e616800 .........hanako. 0x555555559ae0 0x0000000000000000 0x0000000000000000 ................ 0x555555559af0 0x6d726f666e690000 0x0000006e6f697461 ..information... 0x555555559b00 0x0000000000000000 0x0000000300000000 ................ 0x555555559b10 0x000186a00001bf52 0x0000555555559b30 R.......0.UUUU.. 0x555555559b20 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559b30 0x6164696d6f79696b 0x0000000000000069 kiyomidai....... 0x555555559b40 0x0000000000000000 0x006f7261746f6b00 .........kotaro. 0x555555559b50 0x0000000000000000 0x0000000000000000 ................ 0x555555559b60 0x6e616863656d0000 0x000000006c616369 ..mechanical.... 0x555555559b70 0x0000000000000000 0x0000000400000000 ................ 0x555555559b80 0x000100010000032a 0x0000000000000000 *............... 0x555555559b90 0x0000000000000000 0x0000000000020471 ........q....... <-- Top chunk ``` ::: #### How it works? As you can see.After I added data into heap.The top chunk moves to lower address and insert the new data. To understand how it works, we have to read glibc source code. It's open source, there's no reason not to read the source code! * [read glibc](https://github.com/lattera/glibc/blob/master/malloc/malloc.c#L3504) * [skip to read (go to next section)](https://youtu.be/xvFZjo5PgG0?si=ybPaV0FrzvvF1p7i) :::info 1. Checking the size of the Top Chunk 2. If the Top Chunk can satisfy the requested size, the required portion is split from the Top Chunk. The remaining part is treated as the new Top Chunk. Movement towards lower addresses 3. Since the heap grows from lower to higher addresses, allocating new memory causes the starting address of the Top Chunk to shift towards lower addresses. ::: After allocating memory, malloc_chunk will create. https://github.com/lattera/glibc/blob/master/malloc/malloc.c#L1044 ```clike= struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */ struct malloc_chunk* fd; /* double links -- used only if free. */ struct malloc_chunk* bk; /* Only used for large blocks: pointer to next larger size. */ struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */ struct malloc_chunk* bk_nextsize; }; ``` :::info ``` INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */ struct malloc_chunk* fd; /* double links -- used only if free. */ struct malloc_chunk* bk; ``` are only used in the chunk is in the free status. ::: For example, the kiyomidai kotaro's data. ```gdb= 0x555555559b20 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559b30 0x6164696d6f79696b 0x0000000000000069 kiyomidai....... 0x555555559b40 0x0000000000000000 0x006f7261746f6b00 .........kotaro. 0x555555559b50 0x0000000000000000 0x0000000000000000 ................ 0x555555559b60 0x6e616863656d0000 0x000000006c616369 ..mechanical.... 0x555555559b70 0x0000000000000000 0x0000000400000000 ................ 0x555555559b80 0x000100010000032a 0x0000000000000000 *............... 0x555555559b90 0x0000000000000000 0x0000000000020471 ........q....... <-- Top chunk ``` mchunk_size is placed in $0x555555559b28$ Next, let's check out what happens when the data becomes free. ```gdb= 0x555555559ab0 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559ac0 0x0000000555555559 0xec68d291d9268696 YUUU......&...h. <-- tcachebins[0x70][0/1] 0x555555559ad0 0x0000000000000000 0x006f6b616e616800 .........hanako. 0x555555559ae0 0x0000000000000000 0x0000000000000000 ................ 0x555555559af0 0x6d726f666e690000 0x0000006e6f697461 ..information... 0x555555559b00 0x0000000000000000 0x0000000300000000 ................ 0x555555559b10 0x000186a00001bf52 0x0000555555559b30 R.......0.UUUU.. 0x555555559b20 0x0000000000000000 0x0000000000000071 ........q....... 0x555555559b30 0x6164696d6f79696b 0x0000000000000069 kiyomidai....... 0x555555559b40 0x0000000000000000 0x006f7261746f6b00 .........kotaro. 0x555555559b50 0x0000000000000000 0x0000000000000000 ................ 0x555555559b60 0x6e616863656d0000 0x000000006c616369 ..mechanical.... 0x555555559b70 0x0000000000000000 0x0000000400000000 ................ 0x555555559b80 0x000100010000032a 0x0000000000000000 *............... 0x555555559b90 0x0000000000000000 0x0000000000020471 ........q....... <-- Top chunk ``` ![image](https://hackmd.io/_uploads/SyhHl474Jl.png) The kisarazu hanako became tcachebins!! R.I.P kisarazu hanako Content of chunks,fd and bk becomes adtivivated! But bk isn't seems like a valid address. The identity of bk's area is "key". :::info Key is not defined explicitly, just used for checking the next address ```clike= #if USE_TCACHE /* We overlay this structure on the user-data portion of a chunk when the chunk is stored in the per-thread cache. */ typedef struct tcache_entry { struct tcache_entry *next; } tcache_entry; ``` ::: Tcache manages the list within the heap region, so it does not hold internal addresses of glibc. To exploit the binary, it's important to leak the libc address. Therefore, by filling up the tcache(by default, the limit is 7), it becomes necessary to use other bins where root addresses are stored within glibc. |Bin|Size Range|Conditions| |-|-|-| |Fastbins|Small sizes (approximately 16–80 bytes)|Small chunks that are frequently reused.|Reused immediately after being freed.| |Unsortedbins|Larger than Fastbins but smaller than Largebins|Chunks that don't fit in Fastbins or need reordering after being freed.| |Largebins|Large sizes (typically over 1 page)|Large chunks, often allocated via mmap.| These bins hold libc address in the bk of first bin, fd of last bin. ### Kernel The kernel memory allocator is a mechanism for using physical and virtual memory managed by the operating system(OS). #### Bussy system The basic mechanism used in kernel physical memory allocation. Memory is divided and allocated in order of 2. Managed in units of page size (typically 4KB,$4048=1<<12$). # THERE'S NO TIME TO COMPLETE THE ARTICLE! # TO BE CONTINUED