ハクソク

世界を動かす技術を、日本語で。

決定論的完全静的全バイナリ翻訳におけるヒューリスティックなし

8時間前原文(arxiv.org)

概要

  • Elevator はx86-64バイナリをAArch64へ静的に変換する初のトランスレータ
  • ソースコードやデバッグ情報、コードレイアウトの仮定を必要としない特徴
  • 全てのバイトの解釈パターンを事前に網羅的に翻訳し、実行時成分を排除
  • 変換後バイナリは完全自己完結型で、検証や署名が容易
  • コードサイズは増加するが、QEMUのJITと同等以上の性能を実現

Elevator: 静的x86-64→AArch64バイナリトランスレータ

  • Elevator は、x86-64実行ファイルを AArch64 向けに完全静的変換する技術
  • ソースコードや デバッグ情報、コード配置の仮定を一切不要とする
  • 既存手法が ヒューリスティック や実行時フォールバックに依存するのに対し、Elevatorは全バイトの 全解釈パターン を事前に網羅的に処理
  • 各バイトを データ、 オペコード、 オペコード引数 のいずれとしても解釈し、実行不能なパスのみ除外
  • 制御フローごとに独立した変換を生成し、異常終了しないパスだけを採用
  • コード変換は 高水準ISA記述 から自動的に生成される「 タイル」の合成で実現
  • 変換後バイナリは 自己完結型 で、信頼されたコードベースに 実行時成分なし
  • コードサイズ増大 が主なコストだが、出力バイナリは事前に テスト ・ 検証 ・ 認証 ・ 署名 が可能
  • エミュレータや JIT と比べて、運用リスクを低減

実験評価と実用性

  • SPECint 2006 全スイートや多様な実バイナリで評価
  • 静的全プログラム変換が 信頼性 ・ 実用性 を両立できることを実証
  • 出力バイナリの性能は QEMUユーザモードJIT と同等またはそれ以上
  • 実運用環境での 検証 や セキュリティ認証 にも適用可能

Elevatorの意義と今後

  • 事前検証可能な完全変換バイナリ の提供による、セキュリティ・信頼性向上
  • エミュレーション やJIT依存からの脱却、運用時リスク低減
  • 今後の課題は コードサイズ増加 の抑制と、さらなる最適化技術の開発

Hackerたちの意見

これ面白いね。詳しくは見てないけど、相対オフセットはまだ問題になりそうだと思う。でも、コード生成がサイズが違うから、何かしらの翻訳レイヤーやMMUがあるはずだね。これがジャンプテーブルや内部ブランチに影響すると思う。自分は主に90年代のものを扱ってるけど、逆アセンブラはコードの開始と終了について多くの仮定をするんだよね。たまに、バイナリブロブが発見できないこともあって、固定位置のポインタがエントリーポイントを指してないとわからないこともある。数回のパスを経て、バイナリを確実にコードのエリアに絞り込めるんじゃないかな。

自己修正コードに対応できるの？なんでx86_64だけなの？古いゲームみたいな32ビットのプログラムを変換する方が意味があると思うけど。

└

リンク先の記事を読んでみるといいよ。ここで明確に触れられてるから。> 自己修正コードとJITコンパイルされたコード。Elevatorは、完全に静的なバイナリリライトツールとして、自己修正コードやJITコンパイルされたコードには対応してないんだ。

└

なんで俺のガレージも掃除してくれないの？落ち葉も掃かないといけないんだけど。

└

JITランタイム以外で自己修正するのは、今の時代では80年代や90年代に比べてかなり珍しいと思う。最近の.textセクションはほとんどがROだし、セキュリティ要件もそれを減らすことはないだろうね。

└

自己修正コードを扱えるの？扱えたら「完全に静的」じゃなくなるよね。根本的に矛盾してる。

Elevatorは、QEMUのユーザーモードJITエミュレーションと同等かそれ以上のパフォーマンスを達成している。QEMUのJITが何をしているのかはよくわからないけど、改善の余地はかなりあると思う。2013年に、x86-64からaarch64へのJITエンジンを書いて、当時のFedoraベータ版のaarch64バイナリを実行できて、ほぼ全てのaarch64ポートのFedoraをx86_64 Linux上で再構築できたんだ。それと同じように動作する逆のaarch64からx86-64へのJITも作ったし、遊びでその二つのJITがループバックでお互いを実行する様子も見せたよ：x86-64 -> aarch64 -> x86_64。同じプロセス内でね。自分が考案したJITは、1対多の命令とCPU状態のマッピングを行っていて、オーバーヘッドはネイティブ再コンパイルされたコードに比べて2倍から5倍遅い感じだった。後にQEMUのJITと比べたら、そっちは10倍から50倍遅いように見えた。残念ながら、これはオープンソースライセンスの下ではなかったから、証明するためのコードはリリースされてないんだ… :(

└

そうだね、QEMUのJITは結構簡単に打ち負かせるターゲットだよ。特に「x86からaarch64だけ」と「ユーザーモードだけ」に特化するなら、かなりの利点が得られると思う。QEMUのユーザーモードサポートは、システムエミュレーションサポートの付録みたいなもので、全体のJITアーキテクチャは「ゲストから中間表現、そしてホスト」って感じで、十数のゲストアーキテクチャと複数のホストアーキテクチャをサポートするのには優れてるけど、特定のゲスト/ホストペアの特性を活かすことはできないんだ。「x86は整数レジスタが少ないから、ハードに割り当てられる」とか、「aarch64 CPUを正しいモードにすれば、細かい浮動小数点のセマンティクスが常に一致する」みたいなことができない。さらに、QEMUの開発では「新しいアーキテクチャの機能Xをエミュレートする」ことに多くの時間がかけられていて、「もっと速くするための最適化の機会を探る」ことにはあまり時間がかけられてないんだ。なぜなら、開発作業にお金を払う人たちが気にしているのはそっちだから。

└

qemuはTCGであって、トランスレーターじゃないよ。nアーキテクチャで動作するように設計されてるから、限界があるんだ。

認証の観点が一番興味深いな。規制の厳しい業界（航空、医療機器など）は、まさにこの理由でJITを使えないことが多いんだ。実行されるコードは認証されたコードでなければならないからね。署名可能なバイナリを生成する静的翻訳は、本当に解放的だと思うけど、コードの膨張はさておき。

└

これってソフトウェア業界の中でどれくらい重要なのかな？LLmsを大規模に適用する方法もないと思うし、それについては大きなAIの職場での話では全然触れられてないよね。

.textセクションのサイズが50倍になるのはすごいけど、完全に決定論的な翻訳のためには妥当な代償だと思う。エミュレーションに比べてパフォーマンスの違いは、サイズ増加の不便さを上回ることが多いだろうしね。マルチスレッドや例外処理がサポート不可能じゃないってのはワクワクする。単にこのプロジェクトの範囲外なだけなんだろうけど。次のステップは、ヒューリスティックを使って可能性のスペースを削減し、バイナリのサイズを小さくすることなのかな（そうすると翻訳の保証が壊れちゃうけど、バイナリのポータビリティが実用的になる）。

QEMUと同等だけど、Rosettaにはまだまだ遠いね…。

└

それって、Rosettaがx86-64のメモリセマンティクスを模倣するためにAppleのARM拡張に依存してるからじゃないの？

└

Box64もあるけど、要はこれが動作することが保証されるに近いってことだよね。

50倍は妥当じゃない、キャッシュの大惨事だよ。JITを避けることで得られるパフォーマンスのメリットは、全部食われちゃう。

└

実行時に実際にすべてが使われる場合だけだよね。たぶん、ほとんどのデコードの開始ポイントは使われないと思うけど。

Elevatorは、すべてのバイトの可能な解釈を考慮し、実行可能なものごとに別々の翻訳を事前に生成する[...] 異常終了につながるものだけを削除する。じゃあ、クラッシュの可能性がある実際のプログラムは全部削除されるってこと？

└

アドレスからコードへのルックアップテーブルで、標準的なクラッシュに設定されてるだけじゃないかな。それでもクラッシュは起こるけど、直接実行された無効なコードのクラッシュではないってこと。

AIを調整して、最小限の正確な結果を得るようにした感じだね。それ以上の複雑で現実的、最終的には一般的に役立つものについては手を振ってるだけ。大きな問題空間はまだNP完全問題だし。データセンターが無限に大きくなれば、この問題は回避できるかもね。/s /jk

ソースコードはどこにあるの？