ヒューリスティックなしの決定論的・完全静的な全バイナリ翻訳
(arxiv.org)- Elevator は、デバッグ情報・ソースコード・バイナリレイアウトの仮定なしに、x86-64 実行ファイル全体を AArch64 へ静的に翻訳する
- コード・データ判別のヒューリスティックの代わりに、各バイトのあり得る解釈をすべて含む superset CFG を構築し、終了経路のみを取り除く
- x64 状態を AArch64 レジスタに 1 対 1 で対応付け、元のアドレスから翻訳コードへ向かう ルックアップテーブル で間接分岐を処理する
- オフラインの タイルバンク は、x64 命令の意味を C テンプレートで記述した後、LLVM 20 で AArch64 バイト列へコンパイルされる
- 成果物はランタイム翻訳のない自己完結型 AArch64 バイナリであり、SPECint 2006 で QEMU ユーザーモード JIT と同等以上の性能を示す
Elevator の目標
- Elevator は、x86-64 実行ファイル全体を AArch64 へ移す完全静的バイナリ翻訳器である
- デバッグ情報、ソースコード、元のバイナリのコードパターン、バイナリレイアウトに関する仮定を用いない
- 既存の静的翻訳器は、コードとデータを区別するためにヒューリスティックやランタイムフォールバックに依存するが、Elevator は元の実行ファイルの全バイトを、あり得る解釈ごとにあらかじめ翻訳する
- 任意のバイトはデータ、opcode の一部、opcode オペランドの一部になり得るため、あり得る制御フローをすべて含む superset CFG を構築し、例外的なプログラム終了につながる経路のみを取り除く
- 出力は、翻訳コード、元の x64 バイナリ、アドレスルックアップテーブル、ランタイムドライバを含む 自己完結型 AArch64 バイナリ で構成される
- 翻訳完了後は、JIT やランタイム翻訳支援なしで実行できる
- 同じ入力バイナリを 2 回翻訳すると同一の出力ビット列が生成され、テスト・検証・認証・暗号署名の対象が実際の配布コードと一致する
- 主なコストは コードサイズの増加 であり、その代わりにエミュレータや JIT コンパイラよりも配布前の検証可能性が高まる
- 評価には完全な SPECint 2006 ベンチマークと手作りのバイナリが含まれ、性能は JIT 加速付きの QEMU ユーザーモードエミュレーションと同等以上だった
- 研究チームは、プロジェクト終了時に全体をオープンソースとして公開すると述べている
静的翻訳が必要な理由と既存の限界
- ハードウェアがある ISA から別の ISA へ移行する際、既存ソフトウェアを新しいプラットフォームへ持ち込む必要があり、残っているソースコードを再コンパイルするだけでは不十分な場合がある
- 検証済みまたは認証済みのレガシーコードでは、ソースコードではなく、十分にテストされた特定の 権威あるバイナリ実行ファイル が認証対象であることが多い
- 後からソースから同一バイナリをビット単位で再現するには、当時のコンパイラ、リンカ、ビルドシステムのバージョンが必要になる場合があり、現実的には難しい
- ベンダーがソースコードを経由せずにバイナリへ直接パッチを当てた場合、保管されたソースから再ビルドすると、すでに修正済みの不具合が復活する可能性がある
- 既存のバイナリ直接処理方式は、エミュレーション、静的翻訳、動的翻訳を組み合わせるが、翻訳済みプログラムとともに動作する追加のシステムコンポーネントが信頼ベースのコードに含まれる
- 動的な振る舞いはテスト順序や入力に応じて変わり得るため、全体の信頼性を確認しにくい
- Horspool と Marovac は 1980 年に、実行ファイルを逆変換するにはコードとデータを確実に区別しなければならず、多くのアーキテクチャではこれは 停止性問題 と等価で一般には解けないことを示した
- 既存の静的バイナリリフタは、コードとデータの区別をヒューリスティックで近似し、とくに間接制御フロー転送のターゲット予測で問題が大きい
- LLBT は ARM 命令を LLVM IR に持ち上げて対象アーキテクチャへ再コンパイルするが、間接分岐ターゲットの検出にヒューリスティックを用い、入力バイナリにも複数の仮定を置く
- 優れたヒューリスティックでも一部の入力では失敗し得るし、全バイナリを正しくリフトするにはすべてのコード・データ判別が正しくなければならないため、バイナリが大きいほど失敗可能性は高まる
- 動的方式は実際に実行された命令フローをたどるため、命令復元や間接制御フローを扱えるが、具体的な実行で到達しなかった命令はリフトできない
- x64 のように 可変長命令 を持つ ISA では、ある命令列の中に別の命令列が入れ子になることがあり、多バイト命令の途中へ分岐すると、元のオペランドが別個の命令としてデコードされることがある
- ROP 攻撃やコード難読化はこの特性を利用できる
- Apple の Rosetta II と Microsoft の Prism は、事前翻訳と動的翻訳コンポーネントを組み合わせている
- WYTIWYG と Polynima は、動的プロファイリングで特定した制御フロー経路に沿って静的にリフトし、未観測のターゲットアドレスに到達した場合は動的に制御フロー情報を収集するフォールバックを使う
- Elevator は、どのバイトがコードかデータか、命令語かオペランドかを決定せず、実行ファイルの各バイトをあり得るすべての解釈として別個の制御フロー経路に含める
- この方式は、superset disassembly を静的再コンパイルとクロス ISA コンパイルに適用したもので、デコード精度とコード増加をトレードオフする
制御フローと状態保持
- Elevator は、翻訳された AArch64 コード内で x64 状態全体の保持 を原則として動作する
- x64 レジスタと AArch64 レジスタを 1 対 1 に対応付け、各 x64 レジスタ状態を対応する AArch64 レジスタ上でエミュレートする
- x64 スタックは AArch64 スタック上で直接エミュレートされ、実行中の通常のスタック拡張は OS が処理する
- 入力 x64 バイナリの ABI を解析せず、外部コードへ実行が移るか戻る地点でのみ、x64 System V ABI と AArch64 Procedure Call Standard の規則に従って ABI 変換を行う
- 完全な状態保持と 1 対 1 のレジスタ対応により、各 x64 命令は前後の命令を知らなくても独立して翻訳できる
- 元バイナリの各実行可能バイトオフセットは、データであると同時に潜在的な命令列の開始点としても解釈される
- 間接ジャンプ、コールバック、ランタイムディスパッチのように静的解析できない潜在ターゲットすべてに対し、書き換え後バイナリ内に対応する着地点が用意される
- ランタイムには、元命令アドレスから翻訳済みコードアドレスへ向かう ルックアップテーブル を最終バイナリに含めてターゲットを解決する
-
入れ子命令の例
Listing 1は、.byte 0xB0からデコードを開始するとMOV AL, 0xC3の後にRETが現れ、1 バイト後のReturnC2から開始するとRETのみになる構造である- 2 つのデコードはいずれも直前の
jzから到達可能であり、翻訳器が 2 バイトについて 1 つの解釈しか選ばないと、一方の経路を見落とす
-
計算された間接分岐の例
Listing 2は、call Labelがテーブル基準アドレスを作り、pop rsiでそれを回収した後、入力依存オフセットを加えてjmp rsiのターゲットを構成する- 分岐は、エンコード列の中で 2 バイト間隔に配置された 4 個の
inc eax命令のいずれかに着地できる - 静的に解釈可能なジャンプターゲットだけを書き換える翻訳器には、このような分岐を着地させる場所がない
-
呼び出し・復帰・分岐
call、return、branch命令は、戻りアドレス位置、プログラムカウンタ、条件フラグのレイアウトが x64 と AArch64 で異なるため、C タイルで表現できない- 直接呼び出しは、元の x64 戻りアドレスをエミュレーションスタックへ push し、callee の翻訳タイルへ分岐する
- 間接呼び出しは、ターゲットが翻訳済みバイナリ内部か外部ライブラリかを確認し、内部ターゲットは x64 オフセット-タイルテーブルで変換して対応タイルへ分岐する
- 外部ターゲットでは、AArch64 ライブラリが戻る
X30に逆 ABI 変換ガジェットのアドレスを入れ、exit ABI 変換を行った後に外部ターゲットへ分岐する - 復帰では、エミュレーションスタックから 8 バイトの戻りアドレスを取り出して埋め込み x64 バイナリ範囲と比較し、内部復帰ならルックアップテーブルでアドレスを変換して対応タイルへ分岐する
- 直接分岐は翻訳時点でターゲットが既知であり、条件分岐は
X14に保持された x64 フラグビットを調べる AArch64 条件分岐へ翻訳される - 間接分岐は間接呼び出し・復帰と同じ bounds check を出力し、ターゲットが外部なら exit ABI 変換を行う
タイルベース翻訳パイプライン
- Elevator の翻訳は、オフライン タイルバンク 生成、入力バイナリごとの書き換え、最終パッケージングの 3 段階に分かれる
- オフライン段階では、x64 命令の意味を C 関数として表現し、固定された x64-to-AArch64 レジスタ対応のもとでオペランド組み合わせごとに特殊化したうえで、改変した LLVM 20 でコンパイルして再利用可能な AArch64 バイト列を作る
- 入力バイナリごとの段階では、superset disassembly を実行し、見つかった各候補命令に対して名前でタイルを引いて AArch64 バイト列を連結する
- 制御フロー転送や ABI 境界のように C タイルで表現しにくい命令カテゴリは、手書きの小さなテンプレートで処理する
- パッケージング段階では、翻訳済みコード、元の x64 バイナリ、アドレスルックアップテーブル、ランタイムドライバを結合して独立実行可能な AArch64 バイナリを生成する
-
オフラインタイルバンク
- x64 命令ごとに等価な AArch64 命令列を手で書く方式は実用的でない
ADD Reg8, Reg8のような 1 つのテンプレートでも、256 個の具体的なレジスタ組み合わせへ展開され、x64 命令セット全体にはレジスタ、メモリオペランド、即値アドレッシングの変種が多数ある- Elevator は、各 x64 命令の意味を小さな C 関数として書き、具体的なオペランド組み合わせごとに特殊化した後、LLVM に AArch64 へコンパイルさせる
ADD Reg8, Reg8の例では、テンプレートは宛先レジスタの下位 8 ビットを 8 ビット加算結果で更新し、上位 56 ビットは保持して、x64 の部分レジスタ書き込みの意味を再現する- x64 の
ADD Reg8, Reg8はRFLAGSの Carry、Parity、Auxiliary Carry、Zero、Sign、Overflow フラグも変更するため、単一の戻り値しか持てない C 関数の制約上、フラグ更新は別の フラグタイル に切り出される - 1 つの x64 命令は 1 つまたは複数のタイルに対応し、出力時にはそれらを再び連続して連結し、全体の意味を復元する
aarch64_custom_reg属性は、LLVM に戻り値と各引数をどの AArch64 レジスタへ配置するかを宣言する- 固定対応は、x64 System V と AAPCS64 の callee-saved / caller-saved の性質を合わせ、整数引数レジスタ位置の並べ替えを減らし、余った AArch64 callee-saved レジスタを将来のシャドウ状態用に残すよう選ばれている
- x64 の
RFLAGSビットとXMMレジスタファイルも、同じ 1 対 1 の原則のもとで専用 AArch64 レジスタに保持される - 改変版 LLVM 20 は、関数ごとの
aarch64_custom_reg属性を処理し、エミュレートされた x64 状態を保持する AArch64 レジスタを、レジスタ割り当て器内で callee-saved として再分類する TileGenは C テンプレートを走査し、許容可能なオペランド組み合わせごとに特殊化コピーを生成し、テンプレートのパラメータ位置とレジスタ対応から属性を機械的に合成する
-
入力バイナリごとの書き換え
- 入力 x64 バイナリが与えられると、per-binary 段階は superset disassembly を実行し、結果の CFG を走査する
- 各ノードでフォーマッタは、デコード済み命令の opcode とオペランドからタイル名を生成し、複数タイルが必要な命令では複数の名前を組み合わせる
- x64 にはスタックポインタ整列の制約がないが、AArch64 はスタックポインタをメモリオペランドに使う際に 16 バイト整列 を要求する
RSPをSPに直接対応付けると、関数プロローグの連続PUSHのような一般的な x64 コードパターンが、AArch64 では整列例外を引き起こす可能性がある- Elevator は、タイルが別レジスタ
X25を介してスタックへアクセスするようにし、タイルが実際に必要とするときだけSPをそこへ具体化する - LLVM でコンパイルされたタイルは、エントリ時に 16 バイト整列された
SPを前提とするため、spill 領域を割り当てると検出されたタイルを実行する前にSPを下方向へ整列し、実行後に復元する - フラグ計算タイルは比較的高コストなため、その後の post-dominating 命令で読み出される前にフラグが上書きされる場合、現在ノードのフラグ計算を削除する
- 現時点で未対応の命令は主に x64 の AVX2 以降の広幅ベクタ拡張 であり、その位置にはタイルの代わりに割り込み命令を挿入する
- SPECint 2006 の完全評価では、x86-64 整数 ISA 全体と SPECint が使う SSE の部分集合だけで、すべてのベンチマーク実行に十分だった
- 追加命令のサポートは新しいタイルを足す形で拡張可能だが、追加のエンジニアリングが科学的洞察を増やす可能性は低いと見ている
ABI 境界の処理
- Elevator は動的リンクされたバイナリのみをサポートする
- 静的リンクバイナリは
CPUIDのようなアーキテクチャ依存命令を直接含み得るが、動的リンクバイナリではそれをlibcに委譲するため、翻訳の必要性が減る - 動的リンクライブラリと相互作用する際には、エミュレートされた x64 環境とネイティブ AArch64 ライブラリコードの間を行き来するために、x64 Linux ABI と AArch64 Linux ABI の間の変換をサポートする
- ABI 変換で重要なのは 引数配置 と戻りアドレス位置である
- System V x64 ABI は
RDI、RSI、RDX、RCX、R8、R9の 6 レジスタを引数レジスタとして使い、追加引数は[RSP+8]からスタックで渡す - x64
CALLは戻りアドレスを[RSP]に保存する - AArch64 Procedure Call Standard は
X0-X7の 8 引数レジスタを使い、残りの引数を[SP]のスタックに置き、戻りアドレスはX30に保存する -
外部ライブラリ呼び出し
- 翻訳された x64 呼び出しが外部ライブラリをターゲットにする場合、AArch64 呼び出し規約に合わせて引数レイアウトを変更しなければならない
- まず
SPから 8 を引いて 16 バイト境界へ再整列し、すでにスタックにある x64 戻りアドレスを[SP+0x8]に置く [SP+0x10]と[SP+0x18]の値をX6、X7に読み込み、x64 コードがスタックに置いた可能性のある 7 番目、8 番目の引数を AArch64 ライブラリから見えるようにする- 残る可能性のあるスタック引数は
[SP+0x20]以降に残るため、AArch64 が期待する位置とは一致しない - x64 戻りアドレスと
X6、X7に移した値をスタックから取り除く方法は、それらが実際の引数ではなく caller spill 領域や caller スタック上に配置された構造体の一部である可能性があるため安全でない - Elevator は caller のスタックレイアウトに手を加えず、
n×8バイトの追加スタック領域を確保したうえで、現在位置から潜在的な 8 バイト引数n個をコピーする - デフォルトの
nは 10 で、入力バイナリが外部ライブラリ関数へ合計 16 個を超える引数を渡す場合は設定で増やせる - 最後に、外部ライブラリが戻る先のガジェットアドレスを
X30に保存する
-
外部ライブラリからの復帰
- 外部ライブラリ呼び出し前に
X30に保存したガジェットへ制御が戻ると、先にコピーしたスタック引数を片付けるためにスタックポインタへn×8を加える - 外部ライブラリの戻り値を
X0から、エミュレートされた x64 コードが期待するRAXの位置であるX9へ移す - 元の x64 戻りアドレスと関連パディングをスタックから取り出し、アドレスを変換したうえでそこへ分岐し、元の
CALLの次の実行を再開する
- 外部ライブラリ呼び出し前に
-
翻訳コードへ入るコールバック
- ネイティブ AArch64 コードが翻訳済みバイナリを呼び出す場合、AArch64 呼び出し規約を x64 呼び出し規約へ変換する必要がある
- エミュレートされた x64 コードは 7 番目と 8 番目の引数を
X6、X7ではなくスタックに期待するため、X7を先に push し、その後X6を push して x64 が期待するスタック位置に配置する - callee が実際には 7 番目と 8 番目の引数を期待しない場合、これらの push された値は影響しない
- 外部ライブラリの AArch64 branch-and-link 命令が
X30に入れた戻りアドレスを、x64 の戻り命令が期待するスタック位置へ push する
-
コールバックから外部ライブラリへ戻る
- 翻訳済みコードがコールバックから外部ライブラリへ戻るときは、入口処理を逆順に実行する
- 戻りアドレスをスタックから取り出し、
X6とX7を push し、確保したスタック領域はスタックポインタに0x10を加えて解放する
1件のコメント
Hacker Newsのコメント
QEMUのユーザーモードJITが正確に何をしているのかは分からないが、かなり改善の余地がありそうに見える
2013年にx86-64からaarch64へ変換するJITエンジンを作ったことがあり、当時はFedoraベータ版のaarch64バイナリを動かし、x86_64 Linux上でFedoraのaarch64ポートの大半を再ビルドできていた
逆方向のaarch64 → x86-64 JITも作り、面白半分で同じプロセス内でx86-64 → aarch64 → x86_64という形で、2つのJITが互いをループバック的に実行するところも見せた
私の作ったJITは命令とCPU状態を1対多にマッピングしており、ネイティブの再コンパイルコードと比べておおむね2〜5倍遅い程度だった
後でQEMU JITと比べてみると、QEMUは10〜50倍遅い範囲に見えた
残念ながらオープンソースライセンスではなかったので、証拠となるコードを公開することはできなかった
特に設計を「x86からaarch64だけ」「ユーザーモードだけ」に特化できるなら、得られる性能上の利点は大きい
QEMUのユーザーモード対応は、システムエミュレーション対応に付随する「たまたま動いている」付録に近く、JIT全体の構造も「ゲスト → 中間表現 → ホスト」という方式なので、複数のゲストアーキテクチャと複数のホストアーキテクチャを支えるには都合がいいが、「x86は整数レジスタが少ないのでハード割り当てできる」や「aarch64 CPUを適切なモードにしておけば複雑な浮動小数点セマンティクスが常に正しくなる」といった、特定のゲスト/ホスト組み合わせの性質を活用するのは難しい
しかもQEMU開発では、性能最適化の機会を探すことよりも「新しいアーキテクチャ機能Xをエミュレートする」ことに多くの時間が使われる。開発費を出す側がそちらをより重要視しているからだ
.textセクションが50倍大きくなるのは途方もないが、完全に決定論的な変換を得るための代償としては納得できる範囲にも見える多くの場合、サイズ増加の不便さよりも、エミュレーションとの差による性能向上のほうが大きいだろう
マルチスレッドと例外処理が不可能なのではなく、このプロジェクトのスコープ外だという点も興味深い
次の段階は、ヒューリスティクスで可能性空間を刈り込んでバイナリサイズを減らすことなのか気になる
そうなれば変換保証は崩れるが、バイナリ移植性は現実的には向上するかもしれない
この変換器はBox64やFEXよりずっと遅く、何らかの理由でJITが使えない状況でもない限り、単により悪い選択肢だ
この翻訳器が間接ジャンプをどう扱うのか、ずっと気になっていた
バイナリを解析する際に見つけられるのは、宛先アドレスが分かっている直接ジャンプでつながったコード区間だけだ
すると、間接ジャンプが発生するたびに対象関数を見つけ、必要なら変換してから、変換済みコードに戻らなければならないことになるが、遅くないのだろうか？
もっと速い方法があるのか、変換後の関数アドレスを元の関数アドレスに合わせられるのか、それとも元のアドレスに変換済みコードへ飛ぶジャンプを入れるのかが気になる
jmpに対応するブロックは位置Yにある」という大きなテーブルを置いているこの方式は、テーブルを使わない直接
jmpよりは遅いが、元のプログラムでも間接ジャンプはもともと遅く、たいていは性能が重要なループの中にはあまり出てこない上位集合制御フローグラフのアイデアは本当に気に入ったが、記事を読もうとする人なら以下の点は把握しておく価値がある
実行時間は約4.75倍高速化する一方で（QEMUよりは速いがBox64よりはかなり遅い）、実行命令数は7倍に増え、バイナリサイズは50倍に増える
外部呼び出しの直前まではx86 ABIをエミュレートする
EFLAGSのようなx86 CPU状態の大部分をエミュレートしなければならず、複雑な
movも個別に計算しなければならない単一スレッドのバイナリしかサポートしない
例外処理とスタックアンワインドはない
命令セット全体をサポートしているわけではない
興味深い仕事だ
詳しくは見ていないが、相対オフセットは依然として問題になりそうだ
どうせコード生成結果のサイズは変わるのだから、何らかの翻訳レイヤーやMMUが必要になりそうで、主にジャンプテーブルや内部分岐に影響しそうだ
主に90年代のものを扱っているが、逆アセンブラはコードの開始と終了について多くの仮定を置く
しかし時には、固定位置のエントリポイントポインタのような事前知識がなければ、バイナリの塊を見つけられない場合もある
数回のパスを経れば、バイナリを「確実にコードである領域」へと洗練できるように思える
「Elevatorはすべてのバイトの可能な解釈をすべて考慮し、それぞれの可能性ごとに別々の変換をあらかじめ生成し、[...] 異常終了につながる場合だけ枝刈りする」のであれば、衝突し得る実際のプログラムは全部枝刈りされるのだろうか？
そうすれば依然として衝突はするが、直接実行された誤ったコードによる衝突と同じにはならないはずだ
私にとって最も興味深いのは認証の観点だ
航空や医療機器のような規制産業では、実行されるコードが認証済みのコードでなければならず、まさにその理由でJITを使えないことが多い
署名可能なバイナリを生成する静的変換は、コード膨張を受け入れてでも、実用的な突破口になり得る
おそらくこの分野では、LLMも大規模に適用する方法がないだろうし、「業務におけるAI」という大きな議論の中では、こうした部分はほとんど扱われていない
50倍は合理的ではなく、キャッシュ災害だ
JITを避けて得られる性能上の利得が、すべて食い潰されるかもしれない
ホットコードを一か所に集めれば、使われないコードは決してロードされないようにできる
命令はどうせそこまで大きくないし、CPUが実行中に最適化もする
自己書き換えコードを処理できるのだろうか？
なぜx86_64だけなのかも気になる
古いゲームのような32ビットプログラムを変換するほうが、より意味がありそうだ
「自己書き換えおよびJITコンパイルされたコード。Elevatorは、あらゆる完全静的バイナリ書き換え器と同様に、自己書き換えコードやJITコンパイルコードをサポートしない」
最近の
.textセクションはたいてい読み取り専用であり、セキュリティ要件が緩むこともないだろう根本的に矛盾している
キャッシュラインやパイプラインの分岐予測性能を壊すからだ
またW^Xにも違反するので、通常はJIT互換のメモリページ上でしか使うべきではない
だからほとんど常に避けるべきだ
486やP5の時代には、即値を内部ループ変数のように使う形である程度使われていたが、今はあまりそうではない
ほぼ完璧なエミュレーションや変換を実現するには、x86の厄介な例外ケースを数多く処理しなければならない
ソースコードはどこにあるのか？