KernelAddressSanitizer (KASan) による Linux のメモリ破壊問題の検出

この記事は Fujitsu extended Advent Calendar 2016 の 25 日目の記事です。
記事は全て個人の見解です。会社・組織を代表するものではありません。

この記事では Linux カーネルの機能の一つである、KernelAddressSanitizer (KASan) の紹介、および、機能を実際に使った結果を紹介します。

はじめに

カーネルやモジュールにおいて、厄介なバグの一つにメモリ破壊があります。メモリ破壊が厄介なのは、破壊されたことはログやメモリダンプ等からわかりますが、破壊したことの証拠が残らないケースが殆どなことです。なので、ひたすらソース解析や、printkやトレースを仕込んでバグを探す・・・という苦行を繰り返す必要があります。

KASan は Linux 4.0 から導入されており、厄介なメモリ破壊につながる以下のバグを検出する手助けをしてくれます。

• free 後のオブジェクトへの書き込み・読み込み (use after free)
• オブジェクトの領域外への書き込み・読み込み

バグの検出を手助けしてくれる反面、KASan には以下のようなリスクがあります。

• システム全体の性能劣化
• 使用できるメモリ量の減少

本記事では use after free について KASan を使って実際に検出する実験をしてみます。

KASan による use after free の検出実験

環境

以下の環境で実験しています。

• fedora25 (for x86_64)
• kernel-4.9.0

準備

gcc のオプションの確認

プログラムはなんでもいいので、gcc で -fsanitize=address オプションが使えることを確認しておきます。

$ cat print.c
int main()
{
    return 0;
} 
$ gcc -fsanitize=address print.c 
$ 

自分の環境だと以下のエラーがでてコンパイルできませんでした。

$ gcc  -fsanitize=address  print.c 
/usr/bin/ld: cannot find /usr/lib64/libasan.so.3.0.0
collect2: error: ld returned 1 exit status
$ 

libasan パッケージをインストールすると、コンパイルできるように。

# dnf install libasan

カーネルコンパイル

fedora25 のカーネルでは KASan は無効になっているので、適当にカーネルを拾ってきて、コンパイルして KASan を有効にします。
KASan をビルドするため、カーネルコンパイルのときの make menuconfig 等で以下を設定しておきます。

CONFIG_KASAN=y

menuconfig だと、以下の項目。

• Kernel hacking
  • memory debugging
    • KAsan: runtime memory debugger

レッツコンパイル＆インストール。
インストールして、再起動後、以下のメッセージが確認できればOK.

$ dmesg | grep kasan:
[    0.000000] kasan: KernelAddressSanitizer initialized
$ 

実験1. free 後のオブジェクトに書き込み

kmalloc() で 128 byte のオブジェクトを獲得して、kfree() 後、memset() で書き込みをするカーネルモジュール(uaf_slab.c)を作成し、実施してみます(uaf_slab.c のソースコードは本記事の[各実験で使用したモジュールのソースコード]にあります)。

uaf_slab.c をコンパイルして、insmod します。

$ insmod uaf_slab.ko

すると、以下のようなメッセージがコンソールとシスログに出力されます。

uaf_slab: object addr: ffff880035f4e780
==================================================================
①BUG: KASAN: use-after-free in uaf_slab_init+0x71/0x1000 [uaf_slab] at addr ffff880035f4e780
①Write of size 128 by task insmod/4441
(省略)
①Call Trace:
 [<ffffffffb560fb6c>] dump_stack+0x86/0xca
 [<ffffffffb534a451>] kasan_object_err+0x21/0x70
 [<ffffffffb534a6dd>] kasan_report_error+0x1ed/0x500
 [<ffffffffb5174ece>] ? vprintk_default+0x3e/0x60
 [<ffffffffb534b008>] kasan_report+0x58/0x60
 [<ffffffffc06f0071>] ? uaf_slab_init+0x71/0x1000 [uaf_slab]
 [<ffffffffb534969c>] check_memory_region+0x13c/0x1a0
 [<ffffffffb5349b13>] memset+0x23/0x40
 [<ffffffffc06f0000>] ? 0xffffffffc06f0000
 [<ffffffffc06f0071>] uaf_slab_init+0x71/0x1000 [uaf_slab]
(省略)
 [<ffffffffb51c219e>] SyS_finit_module+0xe/0x10
 [<ffffffffb5cb1fc1>] entry_SYSCALL_64_fastpath+0x1f/0xbd
②Object at ffff880035f4e780, in cache kmalloc-128 size: 128
③Allocated:
③PID = 4441
③[<ffffffffb5054a0b>] save_stack_trace+0x1b/0x20
[<ffffffffb53497c6>] save_stack+0x46/0xd0
[<ffffffffb5349a4d>] kasan_kmalloc+0xad/0xe0
[<ffffffffb5345642>] kmem_cache_alloc_trace+0xf2/0x1e0
[<ffffffffc06f0033>] uaf_slab_init+0x33/0x1000 [uaf_slab]
(省略)
[<ffffffffb51c219e>] SyS_finit_module+0xe/0x10
[<ffffffffb5cb1fc1>] entry_SYSCALL_64_fastpath+0x1f/0xbd
④Freed:
④PID = 4441
④[<ffffffffb5054a0b>] save_stack_trace+0x1b/0x20
[<ffffffffb53497c6>] save_stack+0x46/0xd0
[<ffffffffb534a013>] kasan_slab_free+0x73/0xc0
[<ffffffffb5346653>] kfree+0x93/0x1a0
[<ffffffffc06f005f>] uaf_slab_init+0x5f/0x1000 [uaf_slab]
(省略)
[<ffffffffb51c219e>] SyS_finit_module+0xe/0x10
[<ffffffffb5cb1fc1>] entry_SYSCALL_64_fastpath+0x1f/0xbd
⑤Memory state around the buggy address:
 ffff880035f4e680: fc fc fc fc fc fc fc fc fb fb fb fb fb fb fb fb
 ffff880035f4e700: fb fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc
>ffff880035f4e780: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
                   ^
 ffff880035f4e800: fc fc fc fc fc fc fc fc fb fb fb fb fb fb fb fb
 ffff880035f4e880: fb fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc
==================================================================

ログの中に記載している①〜⑤の意味はそれぞれ以下になります。

①

• uaf_slab モジュール内の uaf_slab_init() のオフセット 0x71 で、use after free となる処理が行われた
• use after free となったオブジェクトのアドレスは ffff880035f4e780
• use after free を行ったのは、PID: 4441 insmod コマンド
• 128 byte の write が use after free となった
• 128 byte の write が行われるまでのスタックトレース。このログからは、uaf_slab_init() のオフセット 0x71 で　call されている memset() で write が行われている。

②

• オブジェクト(ffff880035f4e780) は kmalloc-128 として管理されており、サイズは 128 byte

③

• このオブジェクトは、PID: 4441 のタスクによって獲得されていた
• 獲得した処理は、uaf_slab_init() のオフセット 0x33 で call している kmem_cache_alloc() (kmalloc() の中身の関数)

④

• このオブジェクトは、PID: 4441 のタスクによって free されていた
• free した処理は、uaf_slab_init() のオフセット 0x5f で call している kfree()

⑤

• オブジェクト(ffff880035f4e780)付近のメモリの状態。オブジェクト付近では、0xfb, 0xfc でマークされている領域。
  • 0xfb: free されているオブジェクトの領域
  • 0xfc: redzone (KASan でメモリ破壊を検出するために使用しているマーカー)の領域

なので、このログからすると、以下の点をモジュールで確認する必要があります。

• uaf_slab_init() のオフセット 0x71 で memset() を実施することが正しいか。
• uaf_slab_init() のオフセット 0x5f で kfree() を実施することが正しいか。

なお、読み込みの use after free でも同様に検出できます。モジュールの memset() を、 printk() 等の値を参照するコードに書き換えることで、読み込みの use after free の実験ができます。

実験2. free 後のページに書き込み

実験1. と似てますが、今度は　kmalloc() ではなく、allc_page() で獲得したページを、free した後に memset() で書き込むモジュール(uaf_page.c)を実施してみます (uaf_page.c のソースコードは本記事の[各実験で使用したモジュールのソースコード]にあります)。

uaf_page.c をコンパイルして、insmod します。

$ insmod uaf_page.ko

すると、以下のようなメッセージがコンソールとシスログに出力されます。

uaf_page: page: ffffea0001929640 addr: ffff880064a59000
==================================================================
①BUG: KASAN: use-after-free in uaf_page_init+0x93/0x1000 [uaf_page] at addr ffff880064a59000
①Write of size 128 by task insmod/4878
①page:ffffea0001929640 count:0 mapcount:0 mapping:          (null) index:0x0
①flags: 0x3fff8000000000()
①page dumped because: kasan: bad access detected
(省略)
①Call Trace:
 [<ffffffffb560fb6c>] dump_stack+0x86/0xca
 [<ffffffffb534a9b8>] kasan_report_error+0x4c8/0x500
 [<ffffffffb5174ece>] ? vprintk_default+0x3e/0x60
 [<ffffffffb534b008>] kasan_report+0x58/0x60
 [<ffffffffc06f0093>] ? uaf_page_init+0x93/0x1000 [uaf_page]
 [<ffffffffb534969c>] check_memory_region+0x13c/0x1a0
 [<ffffffffb5349b13>] memset+0x23/0x40
 [<ffffffffc06f0000>] ? 0xffffffffc06f0000
 [<ffffffffc06f0093>] uaf_page_init+0x93/0x1000 [uaf_page]
(省略)
 [<ffffffffb51c219e>] SyS_finit_module+0xe/0x10
 [<ffffffffb5cb1fc1>] entry_SYSCALL_64_fastpath+0x1f/0xbd
②Memory state around the buggy address:
 ffff880064a58f00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
 ffff880064a58f80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>ffff880064a59000: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
                   ^
 ffff880064a59080: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
 ffff880064a59100: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
==================================================================

実験1. と大体同じです。ページに関する情報が出力されるようになっているのと、獲得、free した処理の情報は出力されないようです。

①

• uaf_page モジュールの uaf_page_init() のオフセット 0x93 で call している memset() で use after free となっている
• use after free となったアドレスは ffff880064a59000 である。
• ffff880064a59000 に対応するページ構造体のアドレスは ffffea0001929640 である。

②

• アドレス ffff880064a59000 付近のメモリの状態。0xff, 0xfc でマークされている領域。
  • 0xff: free されているページの領域
  • 0xfc: redzone (KASan でメモリ破壊を検出するために使用しているマーカー)の領域

なので、このログからすると、以下の点をモジュールで確認する必要があります。

• uaf_page_init() のオフセット 0x93 で memset() することは正しいか。
• uaf_page_init() のオフセット 0x93 で memset() する前までに意図せずページを free していないか。

なお、実験1. と同じく、読み込みの use after free でも同様に検出できます。

実験3. free 後、オブジェクトが再利用されたあとに書き込み

use after free の中でもかなり厄介なケースです。

• タスクが２つ存在する状況 (TASK A, TASK B)
• TASK A が use after free の問題を持っている

この条件で、以下のような時系列での獲得、free、書き込みが発生するとします。
何も悪くない TASK B が、何故か変な値を参照してしまい、大変なことに。。。TASK B にデバッグを仕込んでも手がかりが得られません。

1. TASK A が pa = kmalloc()
2. TASK A が kfree(pa)
3. TASK B が pb = kmalloc()。このとき、pb には pa と同じアドレスが入る。(pa の領域の再利用)
4. TASK B が pb の領域を使用。
5. TASK A が pa (== pb)に対して書き込み (use after free)
6. TASK B が pb を参照。TASK A に書き換えられているので、意図していない値を参照することになるので、あわわわわ

この状況を再現するために、以下の動作をするモジュール(uaf_slab2.c)で実験しました (uaf_slab2.c のソースコードは本記事の[各実験で使用したモジュールのソースコード]にあります)。

• 処理A
  • 128 byte のオブジェクトを kmalloc() して、kfree() をする
  • kfree() 後、処理 B に再利用されるまで待ち合わせして、再利用されたあとに書き込み
• 処理B
  • 処理 A で kfree() をされることを待ち合わせして、kfree() されたあとに kmalloc() で再利用

また、KASan には、オブジェクトの再利用をなるべく避けるようにするための機構(Quarantine)もあります。Quarantine では、kfree() された領域をすぐに再利用するのではなく、メモリ枯渇等でオブジェクトの回収処理が行われるまで再利用しないようにします。

この実験では再利用することが目的なので、KASan の Quarantine　が邪魔です（笑）。なので、上記に加えて　128 byte のオブジェクトを回収処理を動作させるスクリプト(shrink.sh)を平行に流します。

結果、残念ながら KASan でこの問題を検出することはできませんでした。free 状態で書き込みが行われる場合は検知できるようですが、獲得された後の書き込みは検知はできないようですね。

実験まとめ

KASan の use after free を検知する仕組みでは・・・

• 獲得されたオブジェクト、または、ページの領域について、free 後での書き込み・読み込みを検知できる
• use after free を行ったタスクの PID、タスク名、スタックトレース、オブジェクト/ページのアドレスがログに出力される。
• free 後、再利用されると検知できない

おわりに

KASan の紹介と、use after free を KASan を使って実際に検出してみました。
メモリ破壊問題は検出が厄介で、かつ、影響が甚大(システムダウン、データ破壊等)になりやすいので、なるべく開発段階で検出をするべきバグです。カーネルモジュールを提供している製品において、KASan を有効にしたカーネルでモジュールのテストを行うことは良いかもしれせん。潜在的なメモリ破壊のバグが見つかるかも。。。

各実験で使用したモジュールのソースコード

ソースコードは以下になります。意図的にメモリ破壊を起こすモジュールなので、システムダウンやデータ破壊等が発生する可能性があります。使用はご注意。

実験1

uaf_slab.c

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/slab.h>

#define OBJSIZE 128
#define WRSIZE OBJSIZE

#define d_info(fmt, ...) \
    pr_info("uaf_slab: " fmt,  ## __VA_ARGS__)

static int __init uaf_slab_init(void)
{
    void *victim;

    d_info("uaf_slab is loaded.\n");

    victim = kmalloc(OBJSIZE, GFP_KERNEL);

    memset(victim, 0xaa, WRSIZE);

    d_info("object addr: %p\n", victim);

    kfree(victim);

    /* use after free! */
    memset(victim, 0xbb, WRSIZE);

    return 0;
}

static void __exit uaf_slab_exit(void)
{
    d_info("uaf_slab is unloaded.\n");
}

MODULE_LICENSE("GPL v2");
module_init(uaf_slab_init);
module_exit(uaf_slab_exit);

実験2

uaf_page.c

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/mm.h>

#define WRSIZE 128

#define d_info(fmt, ...) \
    pr_info("uaf_page: " fmt,  ## __VA_ARGS__)

static int __init uaf_page_init(void)
{
    struct page *victim;
    void *victim_addr;

    d_info("uaf_page is loaded.\n");

    victim = alloc_page(GFP_KERNEL);
    victim_addr = page_address(victim);

    memset(victim_addr, 0xaa, WRSIZE);

    d_info("page: %p addr: %p\n", victim, victim_addr);

    __free_page(victim);

    /* use after free! */
    memset(victim_addr, 0xbb, WRSIZE);

    return 0;
}

static void __exit uaf_page_exit(void)
{
    d_info("uaf_page is unloaded.\n");
}

MODULE_LICENSE("GPL v2");
module_init(uaf_page_init);
module_exit(uaf_page_exit);

実験3

uaf_slab2.c

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/slab.h>
#include <linux/kthread.h>

#define MAXTRY 1024
#define OBJSIZE 128
#define WRSIZE OBJSIZE

#define d_info(fmt, ...) \
    pr_info("uaf_slab: " fmt,  ## __VA_ARGS__)

static void *victim;
static struct task_struct *reuser_tsk;

enum {
    NOTSTARTED = 0x0,
    REALLOCED,
    REUSED,
};

static int status = NOTSTARTED;

DECLARE_COMPLETION(freedone);
DECLARE_COMPLETION(reusedone);

static int reuser(void *data)
{
    void **reuse_obj = data;
    int i;

    wait_for_completion(&freedone);

    for (i = 0; i < MAXTRY; i++) {
        reuse_obj[i] = kmalloc(OBJSIZE, GFP_KERNEL);
        if (reuse_obj[i] == victim) {
            d_info("reallocation is success. tried: %d\n", i);
            status = REALLOCED;
            break;
        }
        kfree(reuse_obj[i]);
    }

    if (status == REALLOCED) {
        memset(reuse_obj[i], 0xee, WRSIZE);
        status = REUSED;
    } else
        d_info("reuse is failed...\n");

    complete(&reusedone);

    while (!kthread_should_stop())
        schedule_timeout_interruptible(HZ);

    return 0;
}

static int __init uaf_slab_init(void)
{
    void **reuse_obj;

    d_info("uaf_slab is loaded.\n");

    victim = kmalloc(OBJSIZE, GFP_KERNEL);

    memset(victim, 0xcc, WRSIZE);

    d_info("object addr: %p\n", victim);

    /*
     * create kthread to reallocate and reuse the object.
     * The kthread should be binded to this cpu because
     * the freed object is queued in the per cpu region.
     */
    reuse_obj = kcalloc(MAXTRY, sizeof(void *), GFP_KERNEL);
    reuser_tsk = kthread_create(reuser, reuse_obj, "reuser");
    kthread_bind(reuser_tsk, raw_smp_processor_id());
    wake_up_process(reuser_tsk);

    kfree(victim);

    complete(&freedone);

    /* wait for reuse the object and page by reuser thread. */
    wait_for_completion(&reusedone);

    if (status == REUSED) {
        /* use after free! */
        memset(victim, 0xdd, WRSIZE);
    }

    kfree(reuse_obj);

    return 0;
}

static void __exit uaf_slab_exit(void)
{
    kthread_stop(reuser_tsk);
    d_info("uaf_slab is unloaded.\n");
}

MODULE_LICENSE("GPL v2");
module_init(uaf_slab_init);
module_exit(uaf_slab_exit);

shrink.sh

#!/bin/bash

while true
do
    echo 1 > /sys/kernel/slab/kmalloc-128/shrink
done

参考資料

https://github.com/google/kasan/wiki
http://events.linuxfoundation.org/sites/events/files/slides/LinuxCon%20North%20America%202015%20KernelAddressSanitizer.pdf