FLARE IDA Pro Script シリーズ: IDA でのグラフの簡素化

序章

IDA Pro ユーザー向けの新しいプラグイン SimplifyGraph をリリースできることを誇りに思います。これは、IDA の逆アセンブリ グラフ ビューでノードのグループの作成を自動化するのに役立ちます。コードとバイナリは、 FireEye GitHub リポジトリから入手できます。このリリースの前に、 2017 Hex-Rays プラグイン コンテストに提出し、全体で 3 位になりました。

私の個人的な好みは、リバース エンジニアリングの大部分を行うときに IDA のグラフ モードを使用することです。これは、制御フロー グラフのグラフィカルな表現を提供し、現在の関数の構造に関する視覚的な手がかりを提供するため、逆アセンブリをよりよく理解するのに役立ちます。

関数が複雑になるまでは、グラフ モードが最適です。 IDA では、隣接するノードを比較的離れた場所に配置したり、グラフのエッジが交差したり、パスが複雑になったりすることがよくあります。図 1 に示すように、ノードとエッジが密集しているため、概要グラフの使用は非常に困難になります。

IDA には、グラフを単純化するためのメカニズムが組み込まれています。ノードのグループを作成すると、選択したすべてのノードが新しいグループ ノードの代表に置き換えられます。これは、図 2 に示すように、1 つまたは複数のノードを選択し、右クリックして [ノードのグループ化] を選択することによって行われます。これを手動で行うことは確かに可能ですが、複雑なグラフのエッジをたどってすべてのノードを正しく選択するのは面倒です。関連するノードを欠落することなく、ミスを犯すことなく。

私たちがリリースする SimplifyGraph IDA Pro プラグインは、IDA のノード グループ化機能を自動化するために構築されています。このプラグインは、6.95 のレガシー IDA SDK とソース互換性があり、IDA 7.0 の新しい SDK に移植されています。両方のビルド済みバイナリは、プロジェクト リポジトリの [リリース] タブで利用できます。

プラグインにはいくつかのパーツがあり、以下で紹介します。これらを組み合わせることで、制御フロー グラフの一部を分離して詳細なリバース エンジニアリングを行うことができ、図 1 の代わりに図 3 を見ることができます。

Unique-Reachable (UR) サブグラフの作成

Unique-Reachable ノードは、特定の開始ノードからグラフ内で到達可能なすべてのノードであり、現在 UR セットにないノードからは到達できません。たとえば、図 4 では、緑色のノードから始まるすべての Unique-Reachable ノードが青色で強調表示されています。グレーのノードは緑のノードから到達可能ですが、現在の UR セットにない他のノードから到達可能であるため、グループ作成前にプルーニングされます。

このプラグインを使用すると、UR 定義に基づいて新しいグループを簡単に作成できます。 IDA のグラフ ビューで、到達可能な検索の開始点となるノードを選択します。右クリックして、[SimplifyGraph -> 一意に到達可能なグループを作成] を選択します。プラグインは、このノードから始まるグラフ トラバーサルを実行し、到達可能なすべてのノードを識別し、現在のセットにない先行ノードを持つすべてのノード (およびそれらの到達可能なノード) をプルーニングします。次に、ノード テキストを新しいグループ ノードに表示するように求められます。

UR アルゴリズムで複数のノードを選択した場合 (ノードを選択するときに Ctrl キーを押したままにすることにより)、追加の各ノードはセントリー ノードとして機能します。セントリー ノードは新しいグループに含まれず、到達可能なノードを検索するときにグラフ トラバーサルを停止します。たとえば、図 5 では、最初に緑のノードを選択すると開始ノードとして扱われ、次に赤のノードを選択するとセントリー ノードとして扱われます。 「Create unique-reachable group」プラグイン オプションを実行すると、緑色のノードとすべての青色のノードで構成される新しいグループが作成されます。これは、現在のグラフのサブセットの分析が完了し、グループ ノードの背後にある詳細を非表示にして、グラフの残りの部分に集中できるようにする場合に役立ちます。

UR アルゴリズムは、現在表示されているグラフで動作します。つまり、UR アルゴリズムを繰り返し実行して、グループをネストすることができます。

スイッチ ケース グループの作成

図 6 に示すように、ジャンプ テーブルとして実装された switch ステートメントは、大きなファンアウトを持つノードとしてグラフに表示されます。 「SimplifyGraph -> スイッチケースのサブグラフを作成」.これを選択すると、個別のケース ブランチごとに Unique-Reachable アルゴリズムが実行され、IDA のブランチ ラベルがグループ ノード テキストとして自動的に使用されます。

図 7 は、switch-case グループ化が実行されたときの同じ関数の前後のグラフの概要を示しています。

分離されたサブグラフ

[編集] -> [プラグイン] -> [SimplifyGraph] を実行すると、”SimplifyGraph – 分離サブグラフ” という名前の新しいセレクターが表示され、現在のグラフの分離サブグラフと呼ばれるものを表示し始めます (図 8 参照)。

完全な定義は、これらがどのように計算されるかを含め、付録の後半に記載されていますが、要点は、有向グラフの孤立したサブグラフは、単一の入口ノード、単一の出口ノードがあり、いずれも存在しないようなノードとエッジのサブセットであるということです。ノード (サブグラフ エントリ ノード以外) は、サブグラフにないノードから到達可能です。

孤立したサブグラフの検索は、もともとインライン関数を自動的に識別するために研究されていました。これは実行されますが、このグラフ構造はインライン関数のないコードで自然に発生することがわかりました。これは悪いことではありません。グラフ全体を簡素化し、分析を容易にするためにグループ化するのに適した候補となるノードの自然なグループ化を示しているからです。

チューザーがアクティブになると、チューザーの行をダブルクリック (または Enter キーを押す) して、サブグラフを構成するノードを強調表示できます (図 9 参照)。

次の方法で、分離されたサブグラフのグループを作成できます。

• チューザー行を右クリックして [グループの作成] を選択するか、行を選択した状態で [挿入] を押します。
• 強調表示された分離サブグラフ ノードを右クリックし、[SimplifyGraph -> 分離サブグラフの作成] を選択します。

これらのいずれかを実行すると、作成する新しいグラフ ノードのテキストを入力するよう求められます。

IDA を使用して手動でグループを作成/削除する場合は、現在の関数グループに関するチューザーの知識を更新する必要がある場合があります (チューザーで右クリックして [グループの更新] を選択します)。セレクターを右クリックして [ハイライトをクリア] を選択すると、現在のハイライトを削除できます。新しい関数に移動すると、チューザーが更新され、現在の関数で分離されたサブグラフが表示されます。セレクターを閉じると、アクティブなハイライトが削除されます。プラグインを実行する前に適用したカスタム カラーは保持され、現在のハイライトが削除されたときに再適用されます。

分離されたサブグラフの計算は元の制御フロー グラフで実行されるため、分離されたサブグループをネストすることはできません。グループを作成すると、チューザーの行が赤色に変わり、グループが既に存在するか、既存のグループとの重複があるために作成できないことを示します。

別の注意: この計算は、返されない関数 (無限ループを持つ関数) では現在機能しません。詳細については、付録を参照してください。

グラフの補数

グループを作成して全体的な制御フロー グラフを単純化するのは良いことですが、作成したグループの詳細を理解するのには役立ちません。これを支援するために、プラグインの最後の機能は、リバース エンジニアリングに集中できるように、関心のあるグループ以外のすべてを非表示にします。折りたたまれたグループ ノード、または折りたたまれていないグループに属するノード (IDA で黄色で強調表示) を右クリックすると、プラグイン オプションの [Complement & expand group] と [Complement group] がそれぞれ表示されます。これを実行すると、プラグインは、関心のあるグループ以外のすべてのノードのグループを作成します。これにより、現在調べていないすべてのグラフ ノードが非表示になり、現在のグラフの分析により集中できるようになります。グループ。ご覧のとおり、カスタム グラフ ビューアの作成を回避し、代わりに組み込みの IDA グラフ逆アセンブリ ビュー内にとどまることができるように、グループの作成を少し悪用しています。に。

グラフを補完すると、図 10 に示すビューが得られます。ここでは、グラフ全体が「Complement of group X」という名前のノードにグループ化されています。現在のグループの分析が完了したら、補ノードを右クリックし、IDA の [ノードのグループ解除] コマンドを選択します。

ワークフローの例

プラグインを実行する例として、図 1 の関数をもう一度見てみましょう。これは、マルウェアの一部に対する大規模なコマンド アンド コントロール ディスパッチ関数です。これには、入力文字列が予想されるコマンドと一致する場合に各コマンドのロジックに分岐する一連のインライン strcmp 比較の大規模な if-else-if が含まれています。

1. すべてのインライン strcmp を検索し、それらのグループを作成します。 Edit -> Plugins -> SimplifyGraph を実行して、プラグイン チューザーを表示します。この関数では、ほぼすべての分離されたサブグラフが 7 ノードのインライン化された strcmp 実装です。セレクターに移動して確認し、グループを作成します。これにより、図 11 のようなグラフが得られます。
   

   

2. 入力文字列がコマンド文字列と一致すると、マルウェアはコマンドを実装するコードに分岐します。グラフをさらに単純化して分析を容易にするには、各文字列比較の後に最初のノードを右クリックし、[SimplifyGraph] -> [一意の到達可能グループの作成] を選択して、個別のコマンドごとに Unique-Reachable アルゴリズムを実行します。この後、図 12 のようなグラフが得られます。
   

   

3. 次に、ディスパッチ関数の個別のブランチごとにリバース エンジニアリングを実行します。作成した各コマンド ハンドラー グループ ノードについて、そのノードを右クリックし、[SimplifyGraph -> Complement & expand group] を選択します。単一のコマンド ハンドラー ノードを補完した結果を図 13 に示します。これは、分析がはるかに簡単です。
   

   

4. 現在のコマンド ハンドラーの分析が完了したら、[Complement of group X] ノードを右クリックして補グループを削除し、IDA の組み込みの [Ungroup nodes] コマンドを使用します。残りのコマンド ハンドラー グループ化ノードについて繰り返します。

設定

%IDAUSR%/SimplifyGraph.cfg という名前のファイルにデータを入力することで、構成の一部を微調整できます。ここで、%IDAUSR% は通常、別のものに明示的に設定されていない限り、%APPDATA%/Hex-Rays/IDA Pro/ です。すべての構成は、分離されたサブグラフ コンポーネントに適用されます。オプション:

* SUBGRAPH_HIGHLIGHT_COLOR: デフォルト 0xb3ffb3: 現在選択されている分離されたサブグラフを構成するノードを表示するためにセレクターでダブルクリックまたは Enter キーを押したときにノードに適用される色。私の IDA カラー スキームが最適であると誰もが同意するわけではないため、ここで独自のハイライト カラーを設定できます。

* MINIMUM_SUBGRAPH_NODE_COUNT: デフォルト 3: 有効な分離サブグラフのノードの最小数。検出されたサブグラフのノード数がこの数よりも少ない場合、表示されるリストには含まれません。これにより、単純な 2 ノード サブグラフが表示されなくなります。

* MAXIMUM_SUBGRAPH_NODE_PERCENTAGE: デフォルト 95: 許可されるグループ ノードの最大パーセント (100.0 *(subgroup_node_count / total_function_node_count))。これにより、(ほぼ) 関数全体を構成する孤立したサブグラフが除外されますが、これは通常は重要ではありません。

SimplifyGraph.cfg の内容の例

“`

“MINIMUM_SUBGRAPH_NODE_COUNT”=5

“MAXIMUM_SUBGRAPH_NODE_PERCENTAGE”=75

“SUBGRAPH_HIGHLIGHT_COLOR”=0x00aa1111

“`

前職：

2014 Hex-Rays コンテストのGraphSlickに取り組んでいるときに、半関連の作品に出くわしました。そのプラグインには、CFG と基本的なブロック分析を介して (ほぼ) 同一のインライン関数を自動的に識別し、プログラムにパッチを適用して明示的な関数へのモック関数呼び出しを強制するという、異なる目標がありました。ユーザーに情報を表示するための別のビューアーがありました。

SimplifyGraph は、手動のリバース エンジニアリング (グループの作成) を行う際のタスクの自動化に重点を置いており、グラフ モードでの分解の複雑さを軽減します。今後の作業では、同じ素数積の計算を組み込んで、分離されたサブグラフを自動的に識別できるようにする可能性があります。

インストール

ビルド済みの Windows バイナリは、GitHub プロジェクト ページ の [リリース] タブから入手できます。 ZIP ファイルには、新しい IDA 7.0 SDK と従来の IDA 6.95 SDK のそれぞれに対応する IDA 32 と IDA 64 の両方のプラグインが含まれています。お使いのバージョンの IDA 用の 2 つのプラグインを %IDADIR%plugins ディレクトリにコピーします。

建物

このプラグインと関連ファイルは、Visual Studio 2013 Update 5 を使用してビルドされました。

プロジェクトによって参照される環境変数:

* IDASDK695: 抽出された IDA 6.95 SDK へのパス。これには、その下に「include」パスと「lib」パスが必要です。

* IDASDK: 抽出された IDA 7.0 (またはそれ以降) SDK へのパス。これには、その下に「include」パスと「lib」パスが必要です。

* BOOSTDIR: 抽出された Boost ライブラリへのパス。その下に `boost` と `libs` のパスが必要です。

最も簡単な方法は、Microsoft コマンドライン ビルド ツールを使用することです。

* IDA7.0 の場合: VS2013 x64 ネイティブ ツール コマンド プロンプトを起動し、次を実行します。

“`

msbuild SimplifyGraph.sln /property:Configuration=ReleaseIDA70_32 /property:Platform=x64

msbuild SimplifyGraph.sln /property:Configuration=ReleaseIDA70_64 /property:Platform=x64

“`

* IDA6.95 の場合: VS2013 x86 Native Tools コマンド プロンプトを起動し、次を実行します。

“`

msbuild SimplifyGraph.sln /property:Configuration=ReleaseIDA695_32 /property:Platform=Win32

msbuild SimplifyGraph.sln /property:Configuration=ReleaseIDA695_64 /property:Platform=Win32

“`

結論

このブログで、逆アセンブリ グラフ ビュー内でノードを自動的にグループ化し、これらのグループを分離して表示して分析に役立てることの威力を示していただければ幸いです。このプラグインは私のワークフローの定番となっており、他のユーザーにも役立つことを願ってコミュニティにリリースしています。

付録: 分離されたサブグラフ

孤立したサブグラフの検索は、特定の関数グラフの直接ドミネーター ツリーと即時ポストドミネーター ツリーの計算に依存します。

n へのすべてのパスが d を通過する必要がある場合、ノード d は n を支配します。

ノード n の直接ドミネーター p は、基本的に n に最も近いドミネーターであり、p が t を支配し、t が n を支配するノード t はありません。

ノード z は、ノード n から出口ノードまでのすべてのパスが z を通過しなければならない場合、ノード n を事後支配します。

ノード n の直後のポスト ドミネーター x は、最も近いポスト ドミネーターであり、ノード t がなく、t が n をポストドミネートし、x が t をポストドミネートします。

直接ドミネーター関係はノードのツリーを形成し、すべてのノードはエントリ ノード以外の直接ドミネーターを持ちます。

Lengauer-Tarjan アルゴリズムは、グラフの直接ドミネーター ツリーを効率的に計算できます。また、同じグラフ内の各エッジの方向を逆にすることで、ドミネーター直後のツリーを計算することもできます。

プラグインは、関数制御フロー グラフの直接ドミネーター ツリーと直後ドミネーター ツリーを計算し、(idom[i] == j) および (ipdom[j] == i) の状況を探します。これは、関数の開始からノード i までのすべてのパスがノード j を通過する必要があり、j から関数の終端までのすべてのパスが i を通過する必要があることを意味します。したがって、候補分離サブグラフは、ノード j で開始し、ノード i で終了します。

分離されたサブグラフの候補ごとに、プラグインはエントリ ノードのみがサブグラフの候補にない先行ノードを持っているかどうかをさらに検証します。また、プラグインは、ノード数が最小であり、ノードの最大パーセンテージをカバーしていることを確認することによって、候補サブグラフを除外します (構成セクションの MINIMUM_SUBGRAPH_NODE_COUNT および MAXIMUM_SUBGRAPH_NODE_PERCENTAGE を参照)。

複雑なことの 1 つは、多くの場合、関数には複数のターミナル ノードがあることです。プログラマは、現在の関数から任意の時点で任意に戻ることができます。ドミネーター直後のツリーはすべてのターミナル ノードに対して計算され、不一致は不確定としてマークされ、使用の候補にはなりません。無限ループを伴う関数には終端ノードがなく、現在は処理されていません。

簡単な例として、図 14 のグラフを考えてみましょう。このグラフには、次の直接ドミネーター ツリーとポストドミネーター ツリーがあります。

(idom[i] == j) と (ipdom[j] == i) のペアを探すと、次のようになります。

(0, 8) (1, 3) (3, 6) (6,7)

(0, 8) は、グラフのすべてのノードを構成するため、フィルター処理されます。

(1,3) と (6, 7) は、セットにないノードから到達可能なノードが含まれているため、除外されます。(1, 3) の場合、ノード 2 はノード 6 から到達可能であり、(6, 7) の場合、ノード 2 はノード 1 から到達可能です。

これにより、図 15 に示すように、(3, 6) がこの例の唯一の分離サブグラフとして残されます。