K&Rのmalloc関数とfree関数を理解する

前回 は、CpawCTF の続きである CpawCTF2 を開始しました。

今回は、基礎力を付けるためにも、malloc関数とfree関数を理解していきます。脆弱性を見つけた後、実際の侵入に繋げるときに、malloc関数の理解が求められる場合があります（Use After Freeとか）。

実際に使われている glibc の malloc、free を読もうとしたのですが、すぐに挫折した（笑）ので、まずは、基本となる K&R の malloc関数、free関数から理解していきたいと思います。

それでは、やっていきます。

参考文献

プログラミング言語Cアンサー・ブック 第2版

C Programming Language (Prentice Hall Software)

はじめに

「セキュリティ」の記事一覧です。良かったら参考にしてください。

セキュリティの記事一覧

・第1回：Ghidraで始めるリバースエンジニアリング（環境構築編）
・第2回：Ghidraで始めるリバースエンジニアリング（使い方編）
・第3回：VirtualBoxにParrotOS（OVA）をインストールする
・第4回：tcpdumpを理解して出力を正しく見れるようにする
・第5回：nginx（エンジンエックス）を理解する
・第6回：Python＋Flask（WSGI＋Werkzeug＋Jinja2）を動かしてみる
・第7回：Python＋FlaskのファイルをCython化してみる
・第8回：shadowファイルを理解してパスワードを解読してみる
・第9回：安全なWebアプリケーションの作り方（徳丸本）の環境構築
・第10回：Vue.jsの2.xと3.xをVue CLIを使って動かしてみる（ビルドも行う）
・第11回：Vue.jsのソースコードを確認する（ビルド後のソースも見てみる）
・第12回：徳丸本：OWASP ZAPの自動脆弱性スキャンをやってみる
・第13回：徳丸本：セッション管理を理解してセッションID漏洩で成りすましを試す
・第14回：OWASP ZAPの自動スキャン結果の分析と対策：パストラバーサル
・第15回：OWASP ZAPの自動スキャン結果の分析と対策：クロスサイトスクリプティング（XSS）
・第16回：OWASP ZAPの自動スキャン結果の分析と対策：SQLインジェクション
・第17回：OWASP ZAPの自動スキャン結果の分析と対策：オープンリダイレクト
・第18回：OWASP ZAPの自動スキャン結果の分析と対策：リスク中すべて
・第19回：CTF初心者向けのCpawCTFをやってみた
・第20回：hashcatの使い方とGPUで実行したときの時間を見積もってみる
・第21回：Scapyの環境構築とネットワークプログラミング
・第22回：CpawCTF2にチャレンジします（この記事はクリア状況を随時更新します）
・第23回：K&Rのmalloc関数とfree関数を理解する ← 今回

参考文献の「プログラミング言語Cアンサー・ブック 第2版」の原著である「C Programming Language (Prentice Hall Software)」は、PDF がダウンロードできます。

https://seriouscomputerist.atariverse.com/media/pdf/book/C%20Programming%20Language%20-%202nd%20Edition%20(OCR).pdf

それでは、やっていきます。

参考にさせてもらったサイト

いくつか参考になりそうなサイトを見せてもらいましたが、ここが1番詳しかったと思います。

Memory Allocator for embedded system (K & R Ritchie book)

gnuchops.wordpress.com

最初の取っ掛かりとしては、いかのサイトが分かりやすかったです。

www.ei.fukui-nct.ac.jp

以下は、glibc の malloc の話がメインのようですが、先頭は K&R の malloc の内容があります。この資料は、非常に有名な資料らしいです。

www.slideshare.net

上の資料を書かれた方が、発表してる YouTube もあります。これも有名らしいです。一応、全て見させて頂きました。確かに、glibc の深いところまで、分かりやすく解説してくれているので必見だと思います。

www.youtube.com

動くソースコードを用意してデバッガで追いかけて理解する

K&R の malloc関数は、とてもソースコード量が少ないですが、それでも初見だとかなり難しいです。ソースコードだけ見るより、デバッガで動かして、変数の値を見ながら理解を進める方が、効率がいいと思います。

原著「C Programming Language (Prentice Hall Software)」の 8.7 Example - A Storage Allocator に、malloc、free のソースコードがあります。

C言語として、少し書き方が古いということと、タイプミスがいくつかあって、コンパイルが通らないので、そこを修正した、動くソースコードを用意しました。

https://github.com/dk0893/experiment/blob/main/c/k_and_r_org.cgithub.com

コンパイルと実行方法は以下です。末尾にある main関数で、malloc/free関数をコールしています。ここをいろいろ変えて、malloc関数の理解を進めます。

$ gcc -D DEBUG -o k_and_r_org.out k_and_r_org.c

$ ./k_and_r_org.out
0, 0
0, 0, 0, 0
0, 0, 0, 0, 0, 0

malloc関数とfree関数の理解

以降は、私が理解した内容を書いていきます。

先頭の宣言、定義部分

unistd.h は、sbrk関数を使うので必要です。

Header には、次のブロックのアドレスとこのブロックのサイズ（ユニット単位）が入っています。Align x は、アライメントを強制するために定義されていて、実際には使われません。

#include <unistd.h>

typedef long Align;           /* ユニットアライメント(1ユニットは 8 or 16byte) */

union header                  /* ブロックヘッダ */
{
  struct
  {
    union header *ptr;        /* フリーリストにある場合は次のブロックの先頭アドレス */
    unsigned size;            /* このブロックのサイズ */
  } s;
  
  Align x;                    /* ユニットアライメント強制 */

};
typedef union header Header;

static Header base;           /* empty list to get started */
static Header* freep = NULL;  /* フリーリスト開始アドレス */

static Header *morecore(unsigned nu);
void myfree(void *ap);

malloc関数

標準関数と名前がかぶるので、関数名を malloc から mymalloc に変えています。

最初はフリーリストが存在しないので、グローバル変数の base と freep を初期化します。

その後の for文では、最初はメモリが無いので、for文の最初の方は実行されず、morecore関数をコールします。この中で、システムから大きめのメモリを確保してきます。

for文の先頭に戻り、フリーリストから空きを探します。空いてるブロック（ブロックは連続して空いてるメモリのこと）を見つけたら、そのブロックの末尾から必要な量のメモリを切り出して上位に先頭アドレスを返します。見つけたブロックのサイズが変わるので、サイズを更新しています。

/* malloc: general-purpose storage allocator */
void* mymalloc (unsigned nbytes)
{
  Header*   p;
  Header*   prevp;
  unsigned  nunits;
  
  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; /* 1byte要求でもヘッダとデータで2ユニット必要 */
  
  if ((prevp = freep) == NULL)           /* まだフリーリストが存在しない場合 */
  {
    base.s.ptr = freep = prevp = &base;
    base.s.size = 0;
  }
  
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* ちょうど同じサイズ */
        prevp->s.ptr = p->s.ptr;         /* 使用済みとして次の空きを指すようにする */
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;             /* 後ろから切り分ける */
        p += p->s.size;
        p->s.size = nunits;
      }
      
      freep = prevp;
      return (void *)(p + 1);            /* ヘッダ＋１を返す */
    }
    
    if (p == freep)                      /* wrapped around free list */
      if ((p = morecore(nunits)) == NULL)
        return NULL;                     /* メモリ取得失敗 */
  }
}

morecore関数

最初は空きメモリが無いので、まず、この関数がコールされます。大きめのメモリ（1024 * 16 = 16384 byte）が確保されます。その後、free関数を呼び出します。free関数を呼び出すことで、確保したメモリをフリーリストに認識させて、使えるようにしています。

#define NALLOC 1024 /* 要求する最小単位：1024ユニット */

/* morecore: システムにメモリの追加を要求する */
static Header *morecore(unsigned nu)
{
  char *cp;
  Header *up;
  
  if (nu < NALLOC)
    nu = NALLOC;
  
  cp = sbrk(nu * sizeof(Header));
  
  if (cp == (char *) -1) /* メモリ取得失敗 */
    return NULL;
  
  up = (Header *) cp;
  up->s.size = nu;
  myfree((void *)(up + 1)); /* free()はデータのアドレスを指定する */
  
  return freep;
}

free関数

標準関数と名前がかぶるので、関数名を free から myfree に変えています。

free関数です。最初の for文が、まだ理解が不十分ですが、おそらく、フリーリストからリストをたどって（p）、解放する領域（bp）の近くに設定し（隣接させて）、解放後に空きメモリ同士を連結させるためにあるんだと思います。

/* free: put block ap in free list */
void myfree(void *ap) {
  Header *bp, *p;
  
  bp = (Header *)ap - 1; /* ヘッダのアドレスを取得 */
  
  for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
      break; /* freed block at start or end of arena */
  
  if (bp + bp->s.size == p->s.ptr) { /* 右隣の空きと連結可能なら連結する */
    bp->s.size += p->s.ptr->s.size;
    bp->s.ptr = p->s.ptr->s.ptr;
  } else
      bp->s.ptr = p->s.ptr;
  
  if (p + p->s.size == bp) { /* 左隣の空きと連結可能なら連結する */
    p->s.size += bp->s.size;
    p->s.ptr = bp->s.ptr;
  } else
    p->s.ptr = bp;
  
  freep = p;
}

main関数

最後に、main関数です。いろんなパターンで、malloc関数と free関数をコールするために用意しました。

#ifdef DEBUG
#include <stdio.h>
int main( int argc, char *argv[] )
{
  char *p0, *p1, *p2;
  
  p0 = (char *)mymalloc( 2 );
  printf( "%d, %d\n", p0[0], p0[1] );
  
  p1 = (char *)mymalloc( 4 );
  printf( "%d, %d, %d, %d\n", p1[0], p1[1], p1[2], p1[3] );
  
  p2 = (char *)mymalloc( 6 );
  printf( "%d, %d, %d, %d, %d, %d\n", p1[0], p1[1], p1[2], p1[3], p1[4], p1[5] );
  
  myfree( p1 );
  myfree( p0 );
  myfree( p2 );
}
#endif /* DEBUG */

おわりに

今回は、基本の K&R の malloc関数と free関数について、デバッガで実行できるソースコードを用意して、理解を進めました。何度か見直して理解が進んだら、glibc の malloc関数とfree関数の理解に進みたいと思います。

最後になりましたが、エンジニアグループのランキングに参加中です。

気楽にポチッとよろしくお願いいたします🙇

今回は以上です！

最後までお読みいただき、ありがとうございました。