概要

パッチ生成アルゴリズムは以下の構成となっている。

Courgette はバイナリファイル中のアドレス情報を解析することで効率のよいパッチ生成を実現しているが、一口にアドレス情報といっても、 2種類に大別して扱われておりそれぞれ処理が異なる。

リロケーションテーブルにアドレスが保存されているもの: abs32
分岐命令や CALL 命令中に含まれていて、相対アドレスの形で記述されているもの: rel32

また、便宜上旧バージョンのバイナリファイルを旧バイナリ, 新バージョンのバイナリファイルを新バイナリとする。

旧バイナリと新バイナリを読み込む
旧バイナリ、新バイナリそれぞれについて、アドレス abs32, rel32 を取得する。バイナリファイル中のリロケーションテーブルを参照して abs32 を取得する。バイナリファイル中の .text を参照して jmp 命令列を切り出す
旧バイナリ、新バイナリそれぞれについて、abs32 の対応先アドレスを計算する
旧バイナリと新バイナリとの間で、 Adjustment を実行する
旧バイナリと新バイナリとの間で、bsdiff を走らせる
bsdiff の結果と Adjustment 結果をパッチファイルとして保存する

このうち、Adjustment と呼ばれる、旧バイナリと新バイナリ同士の対応付け作業は他の作業から分離されており、ここではそれ以外の項について説明する。

前提

https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/image_utils.h#20 にコメントがあるようにアドレス情報はさまざまな扱われ方をしており、場合によって適宜変換が行なわれている:

VA: バイナリファイルがロードされた際の仮想メモリ上のアドレス
RVA: バイナリファイルがロードされた際の仮想メモリ上のアドレスで、相対位置となったもの

また、呼出元アドレス情報の場合はファイル開始地点からのそのアドレスがある位置へのオフセット (File Offset) として扱うこもある。

更に、TypedRVA, TypedRVAX86 は呼出元アドレスのFile Offsetと呼出先アドレスの RVA, 命令長を一括で扱うためのクラスである。

abs32 命令取得

まずは簡単な abs32の命令取得について述べる。これは ELF のリロケーションテーブルを参照することで行い、DisassemblerElf32::ExtractAbs32Locations 関数にて実装されている。

      // Loop through relocation objects in the relocation section
      for (int rel_id = 0; rel_id < relocs_table_count; ++rel_id) {
        RVA rva;
        // Quite a few of these conversions fail, and we simply skip
        // them, that's okay.
        if (RelToRVA(relocs_table[rel_id], &rva) && CheckSection(rva))
          abs32_locations_.push_back(rva);

セクションヘッダの SHT_REL にあるリロケーションテーブルを参照しつつ、そのセクションが境界内にあれば登録する形で行なっている。

rel32 命令取得

これは Windows 向けと Linux 向けで大幅に実装が異なる。本節では Linux (ELF)向けを前提に述べていく。

パッチ生成のためにはアドレスが書き変わりうる命令を見つける必要があり、具体的には以下の通りである。

JMP/CALL
MOV/LEA
JCC (JPO/JPE を除く)

具体的には、.text セクションごとに、ヒューリスティックに探索していく形でディスアセンブル処理を行なう。 disassembler_elf_32_x86.cc の151行目にソースコードがあり、バイナリ列で特定命令の並びを見つけ次第そのニーモニックをrel32候補として登録している。

    if (p + 5 <= end_pointer) {
      if (*p == 0xE8 || *p == 0xE9) {  // jmp rel32 and call rel32
        rel32 = p + 1;
      }
    }
    if (p + 6 <= end_pointer) {
      if (*p == 0x0F && (p[1] & 0xF0) == 0x80) {  // Jcc long form
        if (p[1] != 0x8A && p[1] != 0x8B)  // JPE/JPO unlikely
          rel32 = p + 2;
      }

この結果、false positive として実際には命令ではない部分が紛れこむことがある。そこで、DisassemblerElf32::IsValidTargetRVA 関数で RVA が呼出先プログラム中のどこかに存在することを確認した上で、rel32 を登録している。

なお、 Windows 向けの実装は Rel32Finder, Rel32FinderX32, Rel32FinderX64 などにあり、以下のソースコードからたどることができる。 chromium.googlesource.com

abs32, rel32 の対応先アドレスを計算する

この時点では、abs32 の対応先アドレスは登録されていないなど、Adjustment で利用するために不十分な情報しか取得できていない。

DisassemblerElf32::ParseFile 関数にて対応先アドレスを計算し、EncodedProgram として作成する。

具体的には、 disassembler_elf_32.cc の466行目にあるように、セクションヘッダから SHT_REL と SHT_PROGBITS を再度取り出し、 rel32, abs32とを見比べて不整合がないことを確認している。

https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/disassembler_elf_32.cc#528

  for (Elf32_Half section_id : section_header_file_offset_order_) {
    const Elf32_Shdr* section_header = SectionHeader(section_id);
    if (section_header->sh_type == SHT_NOBITS)
      continue;
    if (!ParseSimpleRegion(file_offset, section_header->sh_offset, receptor))
      return false;
    file_offset = section_header->sh_offset;
    switch (section_header->sh_type) {
      case SHT_REL:
        if (!ParseRelocationSection(section_header, receptor))
          return false;
        file_offset = section_header->sh_offset + section_header->sh_size;
        break;
      case SHT_PROGBITS:
        if (!ParseProgbitsSection(section_header, &current_abs_offset,
                                  end_abs_offset, &current_rel, end_rel,
                                  program, receptor)) {
          return false;
        }

最後に、ELFファイル中のデバッグ情報など、今まで無視してきた情報を登録している。https://chromium.googlesource.com/chromium/src/+/21264cc9649f454255bdea9fae22342df25862d1/courgette/disassembler_elf_32.cc#466

hiromi_mi’s blog

Courgette アルゴリズムについてその1

概要

前提

abs32 命令取得

rel32 命令取得

abs32, rel32 の対応先アドレスを計算する