きゅうり。

主にCTF関係のことを書いていく気がします

malloc/free まとめ

CTF pwn

難しいheap問ではmalloc/freeの動作を正確に把握していることが大切。と感じたので、malloc.cを読みつつその動作をまとめてみた。

noobなのでなにか変なことが書いてあったらマサカリください。

 

しかしこの記事を書けば書くほど↓でいいのでは、という気もしてきた。

www.valinux.co.jp

CTFに必要そうな部分だけまとめる、ということで一応の差別化をはかります。

あとは自分の理解を深めるための覚書。

x64を前提として書いているため、x86の場合は64bit->32bitとして読み替えてください。

ちなみにソースコードはここ。

https://code.woboq.org/userspace/glibc/malloc/malloc.c.html

 

内容は以下の通り

・arenaについて

・chunk構造について

・malloc()の流れ

・unlink()について

・free()の流れ

 

arenaについて

mallocではheap領域からメモリを動的に確保するが、何も考えず適当に確保・解放を繰り返しているとすぐにフラグメント化が進んでしまうという問題がある。そこで、メモリをどこからどのように確保・解放をするかを管理する機構をつくることでこの問題を解決している。この機構がarena（アリーナ）と呼ばれるものである。arenaでは、chunk（確保するメモリの塊）をサイズ別に管理している。

プログラム起動時にはデフォルトで1つarenaが存在し、これをmain_arenaと呼ぶ。マルチスレッド処理などで複数のarenaが必要になった場合は随時arenaが作られるが、現状のCTFにおいて複数のarenaが登場することはない（と思う）ためmain_arenaに絞って話を進めていく。

arenaはmalloc_state構造体によって定義されるが、覚えておくべき重要なメンバはmax_fast、fastbins、top、last_remainder、bins の5つ。

max_fast

後述するfastbinsに登録するchunkの最大サイズ。（デフォルト値はx64で160、x86で80？）

fastbins

サイズ別にchunkを管理していると書いたが、小さいサイズ（max_fast以下）のchunkが登録されるのがこのfastbinsである。一方でmax_fastより大きいサイズのchunkは後述するbinsにより管理される。fastbinsは一方向リストとして管理されている。

fastbinsの中でもさらにサイズによってわかれており、適切なサイズのfastbinsに適切なサイズのchunkが登録されるようになっている。

chunk構造についてで述べるが、fastbinsのchunkは、binsのchunkに比べて構造が単純になっていて確保・解放の処理もシンプルである。これは、小さいサイズのchunkは頻繁に確保・解放が繰り返されるためそのコストを減らすためである。

top

大雑把に書くと「困ったらここからchunkを確保するところ」という認識。

heap領域は、最初にある程度大きい塊を確保した後にそこから適宜chunkを確保していく。確保されて細かくなったchunkは前述のfasbinsや後述のbinsにつながれていくが、最初に大きく確保した部分は依然として残っている。後に触れるが、fastbinsやbinsから適当なchunkが見つからなかった場合この塊からchunkを切り出して確保する。この残っている塊のアドレスが入っているのがtopである。

last_remainder

malloc()する際、既存のchunkを分割して確保することがある。last_remainderには分割した残りのchunkのアドレスが入る。これは、分割するchunkをなるべく同じ場所に固めることでフラグメントを防ぐ目的がある。

bins

max_fastより大きいサイズのchunkが登録されていく。fastbinsとは異なり双方向リストである。binsもまたその中で更にサイズ毎にわかれていて適切なリストに登録されていく。

また、binsの中にはunsorted_binsと呼ばれる特殊なbinsがある。解放されたmax_fast以上のサイズのchunkを適切なサイズのbinsに登録する前に、いったんunsorted_chunksに登録をしておく。これは、同じサイズのchunkが再び確保されやすいという特性を活かしたものである。mallocで確保するときにunsorted_chunksに登録されたchunkをbinsに登録する処理が入ることがある。

おそらくこれ以上の知識を要されることは現状ではない（？）ため、どのようなサイズでわかれているのか、などはここでは触れない。

 

（ところで、x86のgdbでは&main_arenaとやると見れるけど、x64では&main_arenaできないんだろうか...？）

 

chunk構造について

chunkとは、mallocで確保されるメモリの塊の単位である。このchunkはmalloc_chunk構造体として定義されており、ヘッダとしていくつかのメンバが存在する。以下はmalloc.cから抜粋。

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
  };

本当はもう2つほどメンバがあるものの、現状のCTFでは必要ないと思われるため省略。

prev_size (64bit)

名前の通り、前のchunkのサイズ。ここで「前」とは、メモリ上で直前という意味。

size (64bit)

名前の通り、ヘッダーを含んだ自身のchunkのサイズ。ただし、下位3bitは特殊な用途に使われる。これは、mallocで確保されるchunkのサイズは8bytesアラインメントされるため、かならず下位3bitは0となることを利用している。

最下位bitを0番目としたとき、0~2番目のbitの意味はそれぞれ以下の通り。

  • 0番目：prev_inuse。ここが1のとき、直前のchunkは使用中。0なら未使用。
  • 1番目：is_mmaped。どデカイchunkはmmapを呼んで確保するため、そのフラグ。CTFでは出てこないと思うのであまり気にしないでよい。
  • 2番目：is_main_arena。main_arena以外から確保したかどうかのフラグ。CTFではmain_arenaしか出てこないと思うのであまり気にしないでよい

つまり、最下位bitが立っているかどうかだけを気にしていればだいたい良い。

fd, bk (各64bit)

binsでは双方向リストとしてchunkが管理されていると書いたが、それを実現しているのがこの2つのメンバである。その名の通り、fdは次のchunkへのポインタ、bkは前のchunkへのポインタを持つ。ここでchunkへのポインタは、prev_sizeを指すものである。なお、fastbinsに入るchunkは一方向リストなため、fdメンバのみを持ちbkは存在しない。

 

ここまでchunkの各メンバの説明をしたが、実はchunkの状態は使用中と解放済みで異なる。まず、fd, bkメンバは使用中のchunkでは存在しない。正確には、fd, bkがあるべき場所はユーザ領域として使われているため何が入っているかはわからない状態にある。

また、prev_sizeは前のchunkと被っている場所にある。つまり、前のchunkが使用中の場合は、次のchunkのprev_sizeは何が入っているかはわからない。これは後に説明するが、prev_sizeを参照する場合は必ず前のchunkは解放済みなためである。ここまで入り組んだ構造になっているのは、なるべくchunkのサイズを小さく済ませたかったという開発背景によるもの。

 

chunk構造については以下のことがわかっていればokというまとめ

  • mallocで確保されるサイズは8の倍数バイト
  • sizeの下位3bitは特殊な用途であり、特に最下位bitはprev_inuse
  • 使用中のchunkにfd, bkは存在しない
  • 前のchunkが使用中のときprev_sizeは存在しない
  • あるchunkを指すポインタに自身のchunk sizeを足すと次のchunkのアドレスが得られる
  • あるchunkを指すポインタからprev_sizeを引くと前のchunkのアドレスが得られる
  • fd, bkは他のchunkのprev_size部分を指す

 

malloc()の流れ

基本的に、_int_malloc()ですべて行われる。_int_malloc()に入らないようなサイズの確保についてはCTFで問われないため省略。

確保の流れを疑似コードにすると以下の通り。

 

// av:arenaのポインタ, bytes:要求サイズ
_int_malloc(av, bytes){
  // 要求サイズを処理して確保するサイズをnbに代入
  checked_request2size(bytes,nb);

  // fastbinsから確保を試みる
  if(nb <= max_fast){
    if(fastbinsに適切なchunkがあったら){
      return chunk;
    }
  }

  // binsから確保を試みる
  else if(max_fast < nb){
    if(binsに適切なchunkがあったら){
      return chunk;
    }
  }

  // unsorted_chunksから確保を試みる
  if(unsoreted_chunksに適切なchunkがあったら){
    return chunk;
  }

  // topからchunkの切り出し
  return chunk;
}

 というわけで、それぞれのパートでどのような処理をするのかを説明する。

 

checked_request2size

要求サイズを8の倍数にし、8を足す。最低値は16。

fastbinsからの確保

fastbinsはFIFOキューとして扱われる。

fastbinsからchunkを確保する際はまず最初の要素を見て、適切なサイズかを確認する。

その後fastbinsから切り出すが、切り出すchunkをPとしたとき、fastbinsにはP->fdを登録する。

binsからの確保

こちらはLIFOのスタックとして扱われる。

nb>=512のときには異なる動作をするが、ここでは取り扱わないことに注意されたい。

nbに応じて適切なbinsを選択し、そこにchunkがあれば切り出す処理をする。切り出す処理は以下の通り。

  • 直後のchunkのprev_inuseビットを1にする
  • リスト上で隣接するfd, bkの更新（bin->bk=P->bk, bck->fd=bin）

ただし、binは適切なbinsのことであり、Pは確保するchunk、bckはP->bkにあたるchunkである。つまり、 bck->P->bin となっていたリンクトリストを、bck->binとする処理。

unsorted_chunksからの確保

この処理を疑似コードに起こすと以下の通り。

for(chunk in unsoted_chunks){
  if(nb<512 && len(unsorted_chunks) == 1 && chunk == last_remainder){
    // last_remainderからchunkを切り出して確保
    // 切り出した残りの部分はunsorted_chunksに登録
    return chunk;
  }

  // chunkをunsorted_chunksから外す
  // bck->chunk->unsorted_chunks => bck->unsorted_chunks
  bck = chunk->bk;
  unsorted_chunks->bk = bck;
  bck->fd = unsorted_chunks;
  
  // ピッタリのサイズならそのまま返す
  if(nb == chunk.size){
    return chunk;
  }

  // chunkを適切なbinsに登録して次のループへ
}

unsorted_chunksのすべてのchunkをbinsに登録し終えても確保できない場合、topからの切り出しを行う。

topからの切り出し

av->top.size>=nb+MINSIZEの場合、topから切り出して確保する。残った部分は新たなtopとして登録する。

av->top.size<nb+MINSIZEの場合、malloc_consolidate()を呼んで再度unsorted_chunksからの確保を試みるが、CTFではここまで求められないように思えるので今は省略する。

 

以上により、おおまかなmalloc()でのchunk確保の流れを示した。

unlink()について

free()の流れを追う前に、unlink()についての説明をする。

unlinkとは、binsに登録されているchunkをとりはずす処理である。

疑似コードに起こすと以下の通り。

unlink(P){ // chunk Pをunlinkする
  // size check
  if(P.size != nextchunk(P).prev_size){ error; }

  // safe unlinking
  if(P->fd->bk != P || P->bk->fd != P){ error; }

  // unlink
  P->fd->bk = P->bk;
  P->bk->fd = P->fd;
}

safe unlinkingの処理は2004年以降のlibcで追加されたもの。

独自のメモリアロケータが実装されてるような問題はたいていsafe unlinkingの処理がない古いunlinkのような気がする。

free()の流れ

疑似コードに起こすと以下の通り。

_int_free(P){ //Pはfreeするchunk
  // fastbinsサイズならfasbinsに登録
  if(P.size <= max_fast){
    FB = 適切なサイズのfastbins
    P->fd = *FB;
    *FB = P;
  }
  // binsサイズならunsorted_chunksに登録
  else{
    // 直前のchunkが未使用ならconsolidate backward
    // consolidateしたらbinsからunlink
    if((P.prev_inuse) == 0){
      size = P->size + P->prev_size;
      P = P - P->prev_size;
      unlink(P);
    }

    nextchunk = P + P->size;
    // 直後のchunkがav->topでないとき
    if(nextchunk != av->top){
      // 直後のchunkが解放済み（次の次のchunkのprev_inuseを確認）
      if((nextchunk + nextchunk->size).prev_inuse == 0){
        // consolidate forward
        unlink(nextchunk);
        P->size +=  nextchunk->size;
      }
      // 直後のchunkが使用中
      else{
        // clear prev_inuse bit
        (nextchunk + nextchunk->size).prev_inuse = 0;
      }
      // chunkをunsorted_chunksに登録
      bck = unsorted_chunks;
      fwd = bck->fd;
      P->fd = fwd;
      P->bk = bck;
      bck->fd = P;
      fwd->bk = P;
    }
    // 直後のchunkがav->topであるとき topとconsolidateしtopを更新
    else{
      P->size += av->top->size;
      av->top = P;
    }
  }
}

 

以上でmalloc(), free()のおおまかな流れをそれぞれ示した。