読者です 読者をやめる 読者になる 読者になる

Kernel (中略) 話 - mirrorrepo-git とかいうツールをわざわざ作った理由

本エントリは、カーネル/VM Advent Calendar 2012 : ATND のために寄稿されました。

序章: git ヤバイ

突然ですが、git って便利ですよね。分散バージョン管理って素敵です。git を使う Linux カーネルも、Linux カーネルを使う Android も素敵です。
ですが似たような git リポジトリを幾つもクローンするのは非効率的だとは思いませんか? 例えば Linux カーネルのツリーは git clone すると約 700MB もの量になります。これに "カスタマイズ版 Linux カーネル" が少なくとも数十個あることを考えると、とても面倒なことになります。しかし… git は、重複するオブジェクト、重複する歴史を重複して格納することはありません。つまり git 自身は、オブジェクトや歴史の重複排除の機能を持っているのです。普通の方なら、git remote と fetch の設定変更を使うことで、なんとかなるはずです。

なんとかならない話

しかし、なんとかならないときもあります。私が数十個の Android / Linux カーネルリポジトリをまとめて remote でアーカイブ、管理していたとき、幾つもの問題に遭遇しました。例えば、次のような具合です。

  1. 削除されたブランチ、タグを追跡しきれない
  2. タグやブランチが移動したりすると、アーカイブしてあるタグや参照が消えるおそれがある
  3. fetch すると、何故か 1 コミット巻き戻っている

1 つめと 2 つめの話は、どちらも git fetch の仕様に関わるものです。特に 2 つめの、fast-forward のできない参照の付け替えが成された後で gc によってコミットが削除されてしまうのは、(リポジトリをただ使うのではなく) リポジトリデータ全体のアーカイブを行いたい私としては困ります*1。3 つめの話は、…マジです。とある SoC メーカーの Android カーネルリポジトリを fetch していたら、あるとき突然 1 コミットだけ巻き戻ってしまい大慌てしてしまいました。
というわけで、自分としてはこんなツールが欲しい。

  1. 複数のリポジトリをまとめる (重複排除)
  2. すべてのコミットやオブジェクトなどをそのまま保存 (正確なアーカイブ)
  3. git の alternates (特定リポジトリのオブジェクトを借りることで、重複するオブジェクトを排除する機能) に使える信頼性のあるオブジェクトストアの提供 (アーカイブを使うことによる HDD 使用量の削減)
  4. 参照の歴史を管理することで、特定の日のリポジトリを再現する (アーカイブに基づく正確なエクスポート)

というわけで、独自ツールを作ることになっちゃったわけです。mirrorrepo-git*2

mirrorrepo-git を実装する

GitPython ですべてを自動化

私には、好きな言語があります。シェルスクリプトです。ワンライナーで書いた複雑なコマンドがシェル上で実行されるのは大好きですし、ちょっとした自動化をシェルスクリプトで行うのも大好きです。しかし、ここにはひとつだけ問題があります。プログラムが複雑になると (例えば配列のようなものが絡んでくると)、シェルスクリプトの記述は容易に非効率的に、そしてわかりづらくなるのです。
そこで私が頼ることにしたのは、スクリプト的な言語の中でもシェルスクリプトの次に好きな、Python です。ライブラリが色々整っていますし、まぁ頑張れば色々できると目論んでのことです。私が使ったのは Index of Packages : Python Package Index という git を Python から自動で弄るライブラリです。面倒なことの多くをやってくれるのですが、実際には問題も発生したりしたので、ハックで回避しています。

mirrorrepo-git の構造

mirrorrepo-git は、次のような構造をした特別な git bare レポジトリを用います。メタデータ用とデータ格納用の 2 つのリポジトリがあるのが特徴です。重要なところから見て行きましょう。

+ repository.git
  + mirrorrepo.metadata
  | fetch したリポジトリのメタデータ (refs) を格納
  + objects
  | 共有オブジェクトが配置される (git)
  + refs
  | 参照
    + tags
    | コミット削除を防ぐためのタグを自動で追加
    + mirrorrepo
    | 一時的にミラーを行う場所

基本は git remote

私が git の共有リポジトリを作るのに重宝した機能は git remote (複数のリモートサイトを管理する) ですが、mirror-repo も例に漏れずこの機能を活用しています。具体的には、複数の git リポジトリに対して別々のリモート名を与え、そして、ミラーのために特別な場所に fetch する設定を保存しておきます*3

repo.create_remote(name, url).config_writer.
    set('fetch', '+*:refs/mirrorrepo/{}/*'.format(name))
repo.remote(name).config_writer.set('tagopt', '--no-tags')

fetch してから保存

mirrorrepo-git は、次の順番で参照を保存します。

  • refs/mirrorrepo/(ミラー名) で始まる参照をすべて削除
  • refs/mirrorrepo/(ミラー名) のディレクトリ全体を削除
    • 例えば a/b を fetch した後で a を fetch しようとするとエラーになるため。
  • git fetch を実行
  • refs/mirrorrepo/(ミラー名) で始まる参照を保存
  • refs/mirrorrepo/(ミラー名) で始まる参照をタグの形で保存する
    • GC による不用意な削除を防止

fetch した参照は一時的に用いるだけです。これによって、複数回 fetch するときに出がちな問題を回避することができます。

が…ハックは必要

実は、GitPython をこのままで fetch に用いると、fetch 後に例外で終了してしまいます。これは、fetch の特別な設定 ("+*:" の部分) が GitPython の実装 (戻り値を返す部分) と相性が悪いのです。
原因は HEAD です。mirrorrepo-git では色々な問題を回避するために HEAD や notes といった (通常は fetch の対象にならない) 参照を保存するのですが、この中でも HEAD は、branch でも tag でもない特別な参照として扱われます。ですが GitPython はこのような参照を扱えず、例外が出てしまうのです。とはいえこの時点で fetch は済んでいるので…
というわけで、簡単なハックをすることにしました。この種類の例外は特別なメッセージを持っているので、単純に…例外を握りつぶします。戻り値は使いません。

try:
    repo.remote(name).fetch()
except Exception as e:
    # hack to ignore FETCH__HEAD errors (due to special handling)
    if e.message.startswith('Failed to parse FETCH__HEAD line: '):
        break

実はこの辺で時間切れになってしまい、まだ実装が完成していません。データを取得するまではできているので、それを共有リポジトリとしてエクスポートするというのが最大の目標になります。

これで、幾つリポジトリがあっても大丈夫…なはず!

自分にとっての必要性からこういうものを作ることになりましたが、git のハックというのは面白いですよ。また結果等を追記します。

*1:たとえ gc を無効にしたとしても、どこからも参照されない宙に浮いた参照というのはアーカイブを使う上で望ましくありません。

*2:git という名前を後ろにつけたのは、リポジトリクローンツールの Subversion 版を mirrorrepo-svn として作っているから。開発中のこちらには重複排除機能はないが、基本となるツールである svnsync の取得する情報に加えてメタデータの歴史を同時管理することを目標にしている。

*3:デフォルト設定のままだとタグがローカルリポジトリのタグとして保存されたりと都合が悪い。

Android 4.0 "Ice Cream Sandwich" の ASLR とその問題

Android 3.x までは、ASLR が全く存在しなかったことが問題のひとつでした。Android 4.0 "Ice Cream Sandwich" で ASLR が追加されたことにより、どこまで攻撃に強くなったのかを見てみようと考えました…が…エミュレータで試すとランダム要素がないという重大な問題に行き当たりました。

2 つの問題

ASLR がエミュレータ上でうまく働いていないのは、次の 2 つの問題が複合しているものと考えられます。

  • ARM における mmap のランダム性の問題
  • app_process コンパイラフラグの問題

ARM における mmap のランダム性の問題

この問題がある場合にはすべてのライブラリは 0x4000_0000 から順番に並び、ランダム性を失います。例えばこんな風に。

40000000-40000fff r-x  /library1.so
40001000-40006fff r-x  /library2.so
40007000-40009fff r-x  /library3.so

この根本原因は、ARM における mmap のランダム性の問題です。

ライブラリは mmap でロードされる

AOSP で sync したソースコードのうち、bionic/linker 中にある linker.c が、ライブラリをロードするためのコードを保持しています。ソースコードによれば、ライブラリは mmap でマップされた領域にロードされます。では mmap がメモリをランダマイズするのはどこで? 答えはカーネルの arch/.../mm/mmap.c です。ここは空きメモリ領域を、必要あらばランダム化して返すことが基本的な役目です。
しかしランダム化のコードが Android 2.6.35.7 ベースのとあるデバイスのソースコード中 (arch/arm/mm/mmap.c) には見当たりませんでした。結論から言えば、ARM の mmap にランダム性が追加されたのは比較的最近なのです。(x86 はずっと前にランダム化のためのコードがマージされています。)

カーネルのバージョン

Linux のコミットログを見てみると ARM の mmap ランダム化が導入されたのは 2.6.35-rc2 以降で、しかも本家の 2.6.35 にはマージされていません。メインラインへの統合は 2.6.36 で、当然これ以上のバージョンのカーネルを使わない限り、mmap で返されるアドレスはランダム化されません。
エミュレータは、といえば、どのバージョンも変わらず 2.6.29 ベース。そう、これが問題だったのです。たとえ prelink 情報を削除して ASLR が理論上効くようにしても、実際のロードに使用される mmap のランダム性がなければ意味がありません。Android エミュレータはちょうどこの問題に当たってしまったといえるでしょう。
一方の実機…例えば Galaxy Nexus は、すでに公開されたスクリーンショットに 3.0.1 との表記がありました。よって、ライブラリに関しては Android 4.0 の実機では ASLR が効くはずです。(私は実機を手に入れたわけではないので断定こそできませんが。)

app_process コンパイラフラグの問題

こちらは、「全くの別問題」です。前者の問題とは独立しています。この問題があるときには、app_process が全くランダム化されず、0x0000_8000 以降に配置されます。例えば次のように。

00008000-00009fff r-x  /system/bin/app_process
0000a000-0000afff rw-  /system/bin/app_process

こちらは mmap の問題ではなく、app_process をコンパイルするときの問題です。

PIE (Position Independent Executable)

PIE という種類のバイナリがあります。これは実行ごとにランダム化されることで、ASLR の恩恵を常に受けるタイプのバイナリです。コンパイラフラグは -fPIE、リンカフラグには -pie を付加することによって、この種のバイナリを作成することができます。
こうして生成されたバイナリには特徴があります。ELF ファイルということには変わりありませんが、ELF ファイルの種類を示すメンバーの値*1が通常の実行ファイルを示す ET_EXEC ではなく、共有ライブラリを示す ET_DYN となるのです。*2
じゃあ実際にコンパイルされた app_process を見てみると、…ET_EXEC ですorz
ET_EXEC じゃ何が悪いかというと、カーネル (fs/binfmt_elf.c) が ELF ヘッダに示された通りの固定のメモリアドレスを確保してしまいます。これにより ASLR が効かないようになっている? のです。

コンパイラフラグの問題

Android のツールチェーンは -fPIC を実行ファイルにつけますが、-fPIE はつけません。そして -fPIC つきで生成された実行ファイルは単なる PIC な実行ファイル (ET_EXEC) になってしまうのです…。
こちらに関しては、カーネルのバージョンでは解決しません。これは「仕様」だからです。

結論

ライブラリのランダム化に関しては、おそらく実機では問題ないでしょう。mmap のランダム化はお世辞にも強いとはいえません (一回の確保につき、256 通りのアドレスから 1 つ選ばれる) が、それでもエントロピーだけでいえば 32-bit 版 Windows (同じく 256 通りのアドレス中から 1 つ選ばれる) に相当します。ですが app_process は完全なミスに見えます。ASLR は実行コード全部が適切にランダム化されていることが前提であるため、このように一部でも実行可能なコードが固定されていると、exploit の可能性を残します。
幸いにも app_process は小さく、また低位アドレスに配置されているため、低いところに生っている実とはいえません。しかしながら、…ASLR がついたことをわざわざリリースノートに書いたのだったら、この問題くらいは解決しておいてほしかったです。