暗黙の述語

ここでは、プログラムコードの難読化に関連するコンピューターセキュリティのいくつかの側面について説明します。 .NETアプリケーションの難読化ツール-.NETコードをハッキングから保護するプログラムの開発に関連して、私が興味を持っていたものです。 別の暗い側面があります。ウイルスやその他の悪いことの開発者はコードの難読化に非常に興味を持っていますが、彼らは私たちには興味がありません。

エミュレーター

そこで、プログラムコードを難読化するためのスーパーアルゴリズムを思いつきました。 コードを逆コンパイルすると、見た目が悪くなり、誰も確実に分析しなくなります。 どうやら：勝利！ しかし、違います。 当然、難読化されたコードは誰も分析しません...手作業で。 ハッカーは、あなたがコードを台無しにした方法を理解し、「解き明かす」ことを書きます。 アルゴリズムが十分に強力だった場合、ハッカーは独自のエミュレーターを作成する必要がありますが、これは一見すると思われるような問題ではありません-ネットワーク上に利用可能なエミュレーターがあり、ハッキング専用に特別に作成されています。



コンピュータサイエンスの理論から、プログラムが永久に停止するか動作するかを決定するアルゴリズム、いわゆる「シャットダウンの問題」は存在しないことが知られています。 これにより、難読化されたプログラムを解くハッカーエミュレーターが「ローカル」に実行できるようになります。コードの各セクションに含まれるすべての変数の状態と値を見つけることができないため、条件分岐点では、すべてのオプションが可能なことが想定されますプログラム。 これが解決策が思い浮かぶところです：絡み合ったコードは常に真である条件の下で遷移で満たされますが、これをエミュレートして理解することは困難です。 このようなもの：

if ((x+x & 1) == 0) good_code else 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「しかし、これはハッカーがエミュレーターを使って回避するトリックの1つに過ぎません」とあなたは言います。 しかし、これらのトリックを何千も思いついたらどうでしょうか？ ああ、この決定は、もしあなたがたくさんのプログラマを持っているなら、それぞれが他の人のトリックとは違うトリックを思いつきます。 現実には、そうではありません。 実際には、1週間考えて30のトリックを思いつきます。ハッカーは1日間コードを見て、30のトリックをすべて見つけます。30はそれほど多くないからです。





コードの難読化の分野では、まったく同じ条件式は「暗黙の述語」と呼ばれます（元の用語は「不透明な述語」です）。 さらに、「述語」と「条件」という言葉を同義語として使用します。 このトピックは長い間発明されたものであり、正直なところ、私は元の作者が誰を伝承すべきかわからない。 述語に関するいくつかの著名な記事：

• http://crypto.cs.mcgill.ca/~garboit/sp-paper.pdf
• citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.302.2312
• sandmark.cs.arizona.edu/ginger_pubs_talks/icecr7_paper.pdf

理想的な暗黙の述語ジェネレータ

暗黙の述語の一種の理想的なスーパージェネレータがどのように見えるべきかを定式化します。 変数x1、x2、...、xnに応じて、述語P（x1、x2、...、xn）を作成し、ジェネレーターユーザーの希望に応じて、まったく同じ述語と常に真ではない述語を作成できます。 また、ジェネレータには次の素晴らしい機能があります。

1. 述語は長さから線形時間で生成されます。
2. 述語は、通常のプログラム（ステルス）の通常の状態に非常に似ています。
3. 述語がジェネレータによって生成されたことを決定するアルゴリズムは存在せず、存在することもできません（！）。
4. 生成された述語に基づいて、それが真であるか、偽である入力パラメーターがあるかを常に判断できるアルゴリズムは存在せず、存在することもできません（！）。
5. ジェネレーターによって作成された述語がまったく同じであるかどうかを、少なくとも80％のケースで正確に判断する確率的なアルゴリズムはありません（図は科学的な突きの方法によって発見されました）。

ここで、理論的にもそのようなことが可能かどうかを理解する必要があります。



ポイント4は可能だと思われる 。 Diophantine方程式は、f（x1、x2、...、xn）= 0の形式の方程式であることに注意してください。ここで、fは整数係数の多項式で、xは非負の整数です。 再びコンピュータサイエンスの理論を参照すると、ディオファンチン方程式によって解があるかどうかを決定するアルゴリズムは存在せず、存在できないことを思い出します。 特に、フェルマーの偉大な定理により、ディオファンタス方程式（x + 1）*（x + 1）*（x + 1）+（y + 1）*（y + 1）*（y + 1）-（z + 1 ）*（z + 1）*（z + 1）= 0には解がありません。 どうやらこれは掘る場所です！ しかし、急がないでください。 Diophantine方程式は、0〜40億の値を持つ整数の和と積のセットではなく、0〜無限大の値を持つ整数の和と積のセットです。 いわゆる「ロング算術」を使用してそれらを記述する必要があり、コードでは非常に奇妙に見えます。



ポイント2はみんなを悩ます 。 直感的に秘密とは、実際のプログラムの実際の「暗黙の」述語の群集では際立っていない述語を意味します。 賢明な人々はすでに多くの典型的なアプリケーションを分析しており、それらの述語のほとんどは非常に簡単であることがわかりました：x == 0、x == y、x> 0など、x、yはint変数です（上記の2番目）記事のすぐ上の賢い人が典型的なJavaプログラムの状態を分析しています。 ステルスの状態が述語にとって非常に重要であることを理解するために、長い間推測する必要はありません。 実際、ハッカーはすべての「奇妙な」述語を簡単に見つけて、何らかの形でそれらを分離するか、まったく削除することさえできますが、まったく必要ありません。



ポイント2のためにポイント4は不可能です... したがって、述語が算術であり、「隠されている」場合は、intを使用した算術のみが関係する可能性が高く、これは、述語が常に真であるかどうかをチェックするアルゴリズムがあることを意味します。述語にあるintのすべての値を単純に調べるだけで十分です。 しかし、これは悪いことではありません。最良の場合、述語の分析のために、40億の値を整理する必要があるからです！ そして、述語に2つの変数があるならば？ ですから、良心的に、P <NPであると信じて、ジェネレータの4番目の特性を弱めます。ジェネレータによって作成された述語が常に真であるという事実を明らかにするタスクは、NP完全でなければなりません。 もちろん、P = NPであることが判明した場合、これもほとんどオプションではありませんが、これまでのところ、平和に眠ることができます。 ここで、私は3-SATを思い出します。これは、神自身がこの瞬間に思い出すように命じた有名なNP完全タスクです。 しかし、このパスに沿って取得された述部を非表示と呼ぶことはほとんどできません。



沈黙の中でポイント1、3、および5を通過します。短い記事には薄すぎる質問です。

プログラム実行グラフ

算術述語とは、f（x1、...、xn）<g（x1、... xn）またはf（x1、...、xn）== g（x1、...、xn）の形式の述語を意味します。ここで、すべてのXはint型です。 fとgは通常の算術式です。 なぜ述語は必ずしも算術演算である必要があるのですか？ いいえ、私はすべきではありませんし、下のテキストであなたに私がそうすべきだと確信させることができるとは言いません。 それでも、算術述語が最も現実的であるという考えに至った理由を説明します。



考えてみると、暗黙の述語を使用した難読化には、プログラム実行グラフを難読化するという1つの主な目標があることが明らかです。 実行グラフは、難読化段階で持っている情報のうち、ハッカーがハッキング段階で持っていない唯一の情報です。 上記のことから、この情報を不可逆的に混乱させることは本当に理論的に可能であることがわかりました。



算術述語は暗黙的ですか（つまり、常に真ですか）。 これはNP完全な問題です。 このポインターは、プログラムの特定のポイントで何を示していますか？ これは解決できない問題です。つまり、シャットダウンの問題の場合のように、このような問題を解決するための一般的なアルゴリズムはありません。 それは問題ありません。不溶性はNP完全よりも優れています。 暗黙の述語を構築する方法に関する次のアイデアは、上記の2番目の記事（Collberg、Clark、Low）から収集されます。



グラフを実行したら、プログラム内の不可視コードを分散させ、メモリ内のどこかでかなり複雑な動的構造を構築および変更します。 それは本当に目に見えないことがあります：そこにメモリに書き留めるのに何が必要かを誰が知っていますか？

そして、プログラム内の各特定のポイントで、構造の状態が何であるか、またその中に含まれるポインターが何を示しているかを知ることができます。

この知識に基づいて、暗黙の述語と暗黙の述語の下にデッドコードを挿入します。これにより、プログラムの一部が隠された構造を変更します。

その結果、ハッカーはポインターを解決するという不溶性の問題を解決しない限り、構造に関する知識を失います。

おもちゃの例を考えてみましょう。 プログラム実行の初期グラフの一部を次のようにします。



難読化されたプログラムでは、1つの4バイト数値とこの数値へのポインターで構成される非常に複雑な構造をメモリ内に形成します。 pをポインターとします。 グラフの左に描かれた部分の入口（* p）で1であることが保証されていると仮定します。グラフは次のように変更されます。



以前に* p == 1が困難であることが明らかになった場合、この部分について誤った仮定を加えることができます。これは、図の左側に* p == 7となる場合があります。



これは良い方法であり、算術述語よりも優れています。 しかし、1つの大きな問題があります。実際には、ハッカーのように、実行グラフはわかりません。 この卑劣なリフレクション、コールバック/デリゲート、その他のコードを実行する予測不可能な方法。 そして、コードがメモリで生成された場合はどうなりますか？ はい、これも起こります。特に.NETではそうです。 ただし、実行グラフはローカルにわかっています。 .NETでは、少なくとも、特定の各メソッド内のコード実行のグラフを確認できます。 ただし、メモリ内の特定の構造の作成と構築を各メソッドに挿入する場合、秘密になりそうにありません。 これは、この方法を使用できないようにするために、秘密、またはむしろその不在がどのように防止するかです。



暗黙の述語を構築する方法は他にもありますが、それらすべて（耳の隅から聞いたもの）はプログラム全体の実行グラフに結び付けられており、1つの方法のコンテキストではかさばっています。 算術述語は別の問題です。

実装

理想的な暗黙の述語ジェネレータには、もう1つの大きなプラスがあります。ジェネレータのアルゴリズムは秘密にしてはいけません！ 残念ながら、ジェネレーターの実装は理想的ではありません。アルゴリズムの実装の詳細については、現時点では公開しません。 しかし、理想的な発電機に近い人は誰もいませんでした。 このトピックは非常に興味深いものであり、コメントでその議論を続けたいと思います。



以下は、暗黙的な述語ジェネレータの結果の一部です。 述語のリストの先頭、中央、および末尾からの抜粋（3000個; c＃〜; * /％; +-; "";＆; ^; |;のような操作の優先度）：すべてのint変数）：

  ~x != x (x + x & 1) == 0 (x + -x & 1) == 0 ~x != x * 4u >> 2 (-x & 1) == (x & 1) ((-x ^ x) & 1) == 0 (x * 0x80 & 0x56) == 0 (x << 1 ^ 0x1765) != 0 ~(-x * 0x40) != x << 6 (~(x * 0x80) & 0x3d) == 0x3d x - 0x9d227fa9 != x - 0x699c945e (y ^ y - 0x35f5f4d2) != 0x42a26409 (x * 0x20000000 & 0x19a27923) == 0 (int)(y * 9u + y * 0xf7u >> 3) >= 0 (x * 4 & 8) == (x + x * 3 - 0x1fef9d8f & 8) (x | 0xffffdbe8) - 0x1baa != x || (x & 0x10) == 0x10 (x ^ 0x1145f) != 0 || (x | 0xfffeffff) == 0xffffffff (uint)x / 0x59d7e3 != 0x90298cf9 || (x * 3 + x & 3) == 0 ((uint)x % 0x38 + 0xe4df62c8 & 0x6d755e00) == 0x64554200 (x ^ 0x770363c6) != 0 || ((uint)x >> 0x19 ^ 0x926797eb) != 0 (uint)y / 0x2369af8 - 0x78400000 != (uint)x / 0x1f2ce * 0x10 (x & 0x8e3ef800) != 0x70641deb && (uint)x / 0x9388ea != 0x3ab6921c
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

投稿者 Dmitry Kosolobov、 Appfuscator開発者 。