執筆者 : 岡部究

1. 静的コード解析

普段の開発で品質向上させるためにどのような手法を採用されているでしょうか。おそらくユニットテストや結合テストを代表するテストを使っているのではないでしょうか。このテスト手法は現実的ですがざっと挙げるだけでも以下の課題があります:

入力と出力をテストケースと呼ばれる例として与えるので全ての場合を網羅することは不可能
テストの網羅率を上げるにはユニットテストのような小さい単位で記述する必要があるが現実的なアプリケーションから逸脱しがち
テストを現実的なものにするには結合テストのような大きい単位で記述する必要があるがテストの網羅率が下がってしまう
ユニットテスト可能な実装になるように常に努力する必要がある
ユニットテスト可能にするためにテストダブルを準備することがあるが、このテストダブルが現実的なアプリケーションの挙動から乖離してしまうことがある

一方でテストとは別の手法として静的コード解析がさかんに研究開発されています。この手法ではテストケースのような例を人間が与えることなく、さらにソフトウェアを実際に実行させることなく解析して不具合をレポートしてくれます。製品のテストは不可欠ですが静的コード解析による網羅的な不具合検出もまた有用です。

この分野で最も成功した製品の1つはCoverityでしょう。商用のプロプライエタリなツールですが様々なプログラミング言語のソースコードをただこのツールに入力するだけで様々なエラーの可能性を検出してくれます。(多少解析に時間はかかりますが。) 近年はCoverity Scanというオープンソースのソフトウェアを対象としてクラウドで静的コード解析をするソリューションも提供されています。

残念ながらこれまでこれら大規模なツールの多くは基本的にはソースコードは開示されずクローズドに開発される傾向がありました。

2. Infer

今回の記事では静的コード解析ツールの1つとしてInferを紹介します。このツールを使うことでソフトウェアにおけるメモリ関連の不具合の可能性を静的コード解析によって検出してくれます。この時ソフトウェアに特別な注釈などは不要です。単純に既存のソフトウェア実装をツールにかけるだけで解析してくれます。このツールはMITライセンスで配布されているオープンソースソフトウェアです。現在はFacebookを運用しているMeta社が開発チームを所有しています。

先程から「不具合の可能性 (potential bugs)」という言い回しを使っていることに注意してください。 Inferが発見する不具合の可能性は実際に不具合を引き起こすとは限りません。このツールは実際には不具合ではないにもかかわらず「不具合の可能性」があるとレポートする可能性があります。つまりInferの下では解析対象のソースコードは以下に分類されることになります:

Inferが検出する真のバグ - Inferが「不具合の可能性」があるとしたレポートの内、実際に不具合を誘発するもの
フォールスポジティブ - Inferが「不具合の可能性」があるとしたレポートの内、実際には不具合を引き起こさないもの
フォールスネガティブ - Inferが「不具合の可能性」があるとレポートしなかったが、不具合を誘発するコード片
Inferが検出しない不具合のないコード - Inferは「不具合の可能性」があるとレポートしなかったし、実際に不具合を誘発しないコード片

Inferの不具合レポートには上記の内1と2が混ざっているため適切に人力で実際に不具合を誘発するのか精査してやる必要があります。また仮にInferが不具合レポートを全く挙げなかったソフトウェアにメモリ関連の不具合がゼロだとも言いきれないことにも注意が必要です。不具合レポートがゼロ件でもフォールスネガティブが潜んでいる可能性があるためです。

ちなみにInferは分離論理とBi-abductionという理論的裏付けをもって作られています。筆者は雑に、分離論理というポインタを含むソフトウェアを抽象化する論理体系があり、その論理体系に現実の実装コードを持ち上げる推論がBi-abductionだと理解しています。 Inferを修正するようになったらより深く理解する必要があるでしょう。

弊社はLinuxの開発/サポートをしている会社です。そのためこのInferを使ってLinuxカーネルの不具合を調べたいと考えても不思議はないでしょう。調べると2019年ごろにInferを使ってLinuxカーネルを解析した実績があるようです。しかしこの解析ではLinuxカーネルソースコードのいくつかのサブディレクトリを解析対象から除外していました。 2023年の現在になってこの状況が改善したのかが本記事を書こうと思ったきっかけです。

3. 調査環境

Debian GNU/Linux bookworm
おそらく16GB以上のメモリ (筆者は32GBメモリで試験しました)

4. Inferのビルド

解析の前にまずはInferをビルドしましょう。このツールはバイナリ配布もされていますが、ちょっとした修正を加える必要があるのでソースコードからビルドする必要があります。その修正は01_infer.patchから入手できます。

$ mkdir ~/src
$ cd ~/src
$ git clone git@github.com:facebook/infer.git
$ cd infer
$ git log | head -1
commit f93cb281edb33510d0a300f1e4c334c6f14d6d26
$ patch -p1 < ~/Downloads/01_infer.patch
$ ./build-infer.sh clang
$ export PATH=~/src/infer/infer/bin:$PATH
$ infer --version
Infer version v1.1.0-f93cb281ed
Copyright 2009 - present Facebook. All Rights Reserved.

5. Inferで解析できるようにLinuxカーネルソースコードに少し修正を加える

次にLinuxカーネルのソースコードを入手します。この時あらかじめ筆者によって設定された.configファイルである03_dot.configとちょっとしたカーネルへの修正02_kernel.patchを入手しておきます。 (カーネルへの修正は多少乱暴なところがありますが現状解析には必要なのでお許しください。) .configファイルをコピーし、カーネルコードに修正を加えましょう。

$ cd ~/src
$ git clone git@github.com:torvalds/linux.git
$ cd linux
$ git checkout v6.1
$ cp ~/Downloads/03_dot.config ./.config
$ patch -p1 < ~/Downloads/02_kernel.patch

今回の記事ではカーネルバージョンをちょっと古めの6.1を選択しました。これはInferがC言語のパーサとしてClangコンパイラを採用しているためです。本記事の執筆時点ではLinuxカーネルのClangコンパイラ対応はまだ途上で確実にパースできるのはこのバージョン6.1であると考えられます。 Clangコミュニティの努力と時間で今後より多くのC言語実装をInferで解析できるようになるでしょう。

6. LinuxカーネルソースコードをInferで検証

準備はできました。それではInferによる解析を実行します。実行するハードウェアにもよりますが筆者の環境では10時間以上解析に時間がかかりました。気長に終わるのを待ちましょう。

$ cd ~/src/linux
$ infer -- make clean
$ infer -- make CC=clang -j`nproc`
--snip--
Found 6070 issues (console output truncated to 5, see '/home/user/src/linux/infer-out/report.txt' for the full list)
          Issue Type(ISSUED_TYPE_ID): #
              Dead Store(DEAD_STORE): 5109
  Null Dereference(NULL_DEREFERENCE): 950
        Resource Leak(RESOURCE_LEAK): 11
$ cp infer-out/report.txt ~/Downloads/04_report.txt

なんと合計で6千件もの不具合がレポート(04_report.txt)されました。

7. 解析結果に対する精査の一例

しかしこのレポートの内、大部分を占める"Dead Store(DEAD_STORE)"は単に後に使われない変数への代入なので大抵の場合は無害です。筆者の見解では一旦"Dead Store"は無視して他のレポートを精査した方が良いでしょう。

それでも9百件もの不具合の可能性が真のバグかフォールスポジティブかを選り分けるのは大変です。そこでここでは筆者による精査からいくつかピックアップして紹介します。

7.1. 真のバグの例

#328
arch/x86/xen/p2m.c:233: error: Null Dereference
  pointer `p2m_top_mfn_p` last assigned on line 232 could be null and is dereferenced by call to `p2m_top_mfn_p_init()` at line 233, column 3.
  231. 
  232.      p2m_top_mfn_p = alloc_p2m_page();
  233.      p2m_top_mfn_p_init(p2m_top_mfn_p);
         ^
  234. 
  235.      p2m_top_mfn = alloc_p2m_page();

上記のコードは単純にalloc_p2m_page()関数が返すp2m_top_mfn_pポインタをp2m_top_mfn_p_init()関数に渡します。 p2m_top_mfn_p_init()関数は内部でこのポインタをデリファレンスします。

static void p2m_top_mfn_p_init(unsigned long **top)
{
    unsigned i;

    for (i = 0; i < P2M_TOP_PER_PAGE; i++)
        top[i] = p2m_mid_missing_mfn;
}

ではp2m_top_mfn_pポインタをメモリ確保したalloc_p2m_page()関数はどのような実装になっているでしょうか。

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
    struct page *page;

    page = alloc_pages(gfp_mask & ~__GFP_HIGHMEM, order);
    if (!page)
        return 0;
    return (unsigned long) page_address(page);
}

#define __get_free_page(gfp_mask) \
       __get_free_pages((gfp_mask), 0)

static void * __ref alloc_p2m_page(void)
{
    if (unlikely(!slab_is_available())) {
        void *ptr = memblock_alloc(PAGE_SIZE, PAGE_SIZE);

        if (!ptr)
            panic("%s: Failed to allocate %lu bytes align=0x%lx\n",
                  __func__, PAGE_SIZE, PAGE_SIZE);

        return ptr;
    }

    return (void *)__get_free_page(GFP_KERNEL);
}

なんとslab_is_available()な場合には__get_free_pages(GFP_KERNEL, 0)関数を経由して、alloc_pages()でメモリ確保を試し、最悪のケースではNULLを返してしまいます。結果としてp2m_top_mfn_pポインタによるNULLデリファレンスは発生することになります。

7.2. フォールスポジティブの例

#336
block/bio-integrity.c:377: error: Null Dereference
  pointer `bip` last assigned on line 373 could be null and is dereferenced at line 377, column 2.
  375.  unsigned bytes = bio_integrity_bytes(bi, bytes_done >> 9);
  376. 
  377.  bip->bip_iter.bi_sector += bio_integrity_intervals(bi, bytes_done >> 9);
        ^
  378.  bvec_iter_advance(bip->bip_vec, &bip->bip_iter, bytes);
  379. }

上記のコードはbipポインタをNULLポインタデリファレンスしている可能性があります。 bipポインタはどこからやってきたのでしょうか。

static inline struct bio_integrity_payload *bio_integrity(struct bio *bio)
{
    if (bio->bi_opf & REQ_INTEGRITY)
        return bio->bi_integrity;

    return NULL;
}

void bio_integrity_advance(struct bio *bio, unsigned int bytes_done)
{
    struct bio_integrity_payload *bip = bio_integrity(bio);
    struct blk_integrity *bi = blk_get_integrity(bio->bi_bdev->bd_disk);
    unsigned bytes = bio_integrity_bytes(bi, bytes_done >> 9);

    bip->bip_iter.bi_sector += bio_integrity_intervals(bi, bytes_done >> 9);

bioポインタはbio->bi_opf & REQ_INTEGRITYではない場合にはNULLになる可能性があります。ここでbio_integrity_advance()の呼び出し元を見てみましょう。

void __bio_advance(struct bio *bio, unsigned bytes)
{
    if (bio_integrity(bio))
        bio_integrity_advance(bio, bytes);

今回NULLデリファレンスの疑いがあるbio_integrity_advance()関数はbio->bi_opf & REQ_INTEGRITYの場合に限って呼び出されることがわかります。そのためこのポインタデリファレンスにNULLポインタは渡りません。フォールスポジティブであることがわかります。

7.3. 真のバグか判断に困るものの例

#281
arch/x86/kernel/apic/vector.c:124: error: Null Dereference
  pointer `apicd` last assigned on line 120 could be null and is dereferenced at line 124, column 2.
  122.  lockdep_assert_held(&vector_lock);
  123. 
  124.  apicd->hw_irq_cfg.vector = vector;
        ^
  125.  apicd->hw_irq_cfg.dest_apicid = apic->calc_dest_apicid(cpu);
  126.  irq_data_update_effective_affinity(irqd, cpumask_of(cpu));

上記のコードはapicdポインタをデリファレンスしています。このポインタがNULLであればバグです。 apicdポインタはどこからやってきたのでしょうか。

static struct apic_chip_data *apic_chip_data(struct irq_data *irqd)
{
    if (!irqd)
        return NULL;

    while (irqd->parent_data)
        irqd = irqd->parent_data;

    return irqd->chip_data;
}

static void apic_update_irq_cfg(struct irq_data *irqd, unsigned int vector,
                unsigned int cpu)
{
    struct apic_chip_data *apicd = apic_chip_data(irqd);

    lockdep_assert_held(&vector_lock);

    apicd->hw_irq_cfg.vector = vector;

apic_chip_data()関数に渡しているirqd変数が0の場合にはNULLが返されてしまうようです。ではapic_update_irq_cfg()関数の呼び出し元でirqd変数が0になることは起きうるのでしょうか。ところがapic_update_irq_cfg()関数の呼び出し元は幾重にも積み重なっていて全ては調べきれません。

筆者の個人的な感想ではこのように設計者が自信を持てない場合にはNULLポインタのチェックをした方が良いと感じます。一方で「NULLポインタデリファレンスが起きる場合は異常事態なのでカーネルパニックをして良い」というのも一つのポリシーだとは思います。

8. 結論とこれから

本記事ではLinuxカーネルのソースコードを、Inferを使った静的コード解析によってメモリ関連の不具合を検出してみました。 Linuxカーネルは多種のGCCコンパイラの方言を使っているにもかかわらず、驚くべきことにほんのわずかな修正でInferはLinuxカーネルコード全体を解析することができました。解析の結果、本記事で用いた.configファイルの範囲でさえ961件の不具合の可能性が見つかりました。その内のいくつかを筆者が精査してみたところ実感では約半分はフォールスポジティブで、残りが真のバグもしくはバグの疑いがあるレポートと思われます。

本記事でのLinuxカーネルソースコードとInferへの修正はできうるかぎり上流のメンテンナに還元し、誰もが修正なしにLinuxカーネルの静的コード解析ができるようになることが望まれます。特にInfer側を修正することで今回Linuxカーネルソースコードへの修正の多くは不要になるはずです。

Linuxカーネルの開発においてInferが検出する不具合の可能性は有用であることも確かめられました。今回はLinuxカーネル全体を解析したためレポートが膨大になってしまいました。このレポートを逐一人力で精査することは現実的ではありません。 Meta社が社内開発でInferを活用しているように修正がレビュープロセスに回覧されたらその時点でInferをインクリメンタルに実行して結果をレビュープロセスに即時に提示することで、修正と関連するメモリ関連エラーをドメイン知識を持った開発者が精査できるようにすることができるでしょう。

またLinuxカーネル以外のオープンソース製品にInferを応用することも求められます。ここでもInfer自体を拡張することが必要になる場面があります。例えばInferはninjaビルドシステムをサポートしていません。そのためQEMUのようにninjaを使ってビルドするソフトウェアの静的コード解析は効率的に行なうことが現状ではできません。

またInferだけが静的コード解析に有用なツールではありません。昨今ではAIアルゴリズムの進化が目覚しく、これまで研究開発されてきた静的コード解析の理論や実装を刷新する可能性があります。しかしいかにツールが進化してもフォールスポジティブやフォールスネガティブを完全にゼロにすることは難しいかもしれません。不具合の可能性を示すレポートを読み解く人間の力は不要になるどころか、求められる技術力と難易度はAIのような技術によってさらに底上げされることになるでしょう。