ホーム » 未分類

未分類」カテゴリーアーカイブ

Scureなapkを作るためのNative

こんにちは。kiwamizamuraiです。

今回はセキュアなapkの作り方について少しまとめます。apkってなんだ?という方は以下の記事をどうぞ。

そもそもこの記事を書こうと思ったのはJavaが原因なんですよね。

Recap

とりあえず3つの手法があるようです。

Isolate Java Program

重要なClassをサーバー側に置いておくことです。クライアントとは通信によってそのファイルへアクセスさせます。こうすることでデコンパイル自体を不可能することができます。重要なデータについてもサーバー側に置いておくことでデクリプションの可能性もなくなります。

Convert to Native Codes

アンドロイドアプリケーションはJava(Kotlin)が一般的です。しかしJavaはデコンパイルされやすいです。(理由は後述します。)そこでデコンパイルが難しいネイティブを組み込む方法です。ネイティブはデコンパイルしたところでアセンブリになります。画像をもって説明します。
NDKはアプリケーションの一部をネイティブに変換するためのツールです。また、コンパイルされたsoファイル(共有ファイル、windowsの場合は.dll)はJNIによってJavaが扱えるようにされます。また、ネイティブを使うことによって早くなることもメリットの一つになります。

一方でデメリットもあります。一つはファイルが大きくなることです。アンドロイドはさまざまなアーキテクチャ上で動くことができるため、その分互換性のあるファイルを多く持つ必要があります。デコンパイルしたapkのlib内を確認してみます。
上の画像からわかるようにそれぞれのマイクロプロセッサーに対応する機械語のファイルがあることがわかります。

Code Obfuscation

ProGuardなどのツールを用いてコードを難読化する方法です。クラス名やメソッド名が乱数になったりします。以下をしてくれます。
  1. Shrinking – detects and removes unused classes, fields, methods, and attributes.
  2. Optimization – analyzes and optimizes the bytecode of the methods.
  3. Obfuscation – renames the remaining classes, fields, and methods using short meaningless names.
具体的なObfuscationの方法はconfiguration file(build.gradle)に設定するようです。
詳しくはドキュメントを読んでください。

Why is Java easily cracked?

先ほど対策方法でネイティブを埋め込む理由としてJavaはデコンパイルされやすいと言いました。それについて少し深入りします。そもそもJavaのコンパイル、デコンパイルの流れを確認しましょう。
JavaのコードはDEXと呼ばれるバイトコードに変換されます。これはARTで動くためです。最近のアプリケーションはARTで実行されます。一昔前はJavaVMで動いていました。で、問題はこのバイトコードがデコンパイルされやすいことです。デコンパイルの過程も復習します。
復習ですがsmaliファイルはdexのアセンブリでした。このデコンパイルが簡単な理由は次のようです。
簡単に言えば、コンパイルの最適化が単純なことが原因です。メタデータ(クラス名やメソッド名)が付与されることが大きい理由らしいです。で、なぜコンパイルが単純なのか僕なりに調べました。原因はJITです。

Just-In-Time Compiler

JITはJavaのコンパイラです。ネイティブのコンパイルとの違いはタイミングです。これはdexをnative codeに変換します。公式からワークフローを拾ってきました。 よくわからないのでコピペで引用します。
JIT コンパイラは、ART の現行の事前(AOT)コンパイラを補完し、ランタイムのパフォーマンスの改善、ストレージ容量の節約、アプリとシステムのアップデートの高速化を実現します。また、アプリの自動アップデート中のシステム シャットダウンや無線(OTA)アップデート中のアプリの再コンパイルを回避することで、AOT コンパイラのパフォーマンスも改善します。

ここはまだ理解できる気がしないので今後の課題にしておきます。

ちなみに、dexじゃなくて機械語にコンパイルすればいいじゃんということにもなります。GCJというコンパイラが一応ありますが詳しくはわかっておりません。

Reverse Engineering Native Code

Javaが単純なのでNativeで書こう、ということになりました。ではNative Codeは本当に安全なのでしょうか?少しだけ深入りします。
僕の中の回答はIDA Proの商用版で解析することです。Free版だと対応のCPUがありません。。。。まあせっかくなのでJavaでnativeが動くまでについても調べてみます。

ネイティブメソッドが走るには.so内のSystem.loadLibraryかSystem.loadが呼ばれる必要があるようです。そしてその時に先ほど紹介したJNIのJNI_OnLoad()とかが使われるらしいです。じゃあ具体的にNativeってJavaの中でどう書かれているの?と思うのでみてみます。
ちょっと複雑ですが簡単にいうとnativeがあればネイティブメソッドということです。詳しくは参照よりどおぞ。

感想

やはりネイティブ最高、リバエン最高ですね

References

Frida 入門

こんにちは。kzです。

今回はFridaを使ってAndroid用のCTFを解いてみます。
これが今回のapkです。Objectiveのところにあるように、secret stringを見つけて、root検出の回避が目標です。

とりあえず起動してみるとこんな感じ。(エミュレータを使用しています。実機ほしい、、、、)
おー、root detectedですね。これは端末がroot化されているものを検出したということです。たとえばiPhoneのJailbreakも同じようなものです。なぜroot化かするのか?ですがたとえばゲームがいい例です。ゲームでチートってあるじゃないですかあれとかができるようになります。他にもiPhoneの場合だとTweakというアプリが作れたりします。ただ、よくないので行わないでください。

Source Code

Javaのコードをデコンパイルして覗いてみましょう。やり方は前回の記事にあります。こうすることでroot detectedの実装が確認できます。
root判定の部分がありました。
ふむふむ、Successとなるように分岐されるところのソースコードをみてみます。
Base64の文字列5UJiFctbmgbDoLXmpL12mkno8HT4Lv8dlat8FxR2GOc=ともう一つ気になるHex?があります、8d127684cbc37c17616d806cf50473ccこれはなんだろう、、?その後にAESもありますね、ということは逆算してパスフレーズがわかりそうです。ぐぐるとJavaにはCipherというAES/ECB/PKCS7Padding暗号があるようです。

どうやらkeyと平文を引数とする関数のようです。さらにHexの方がKeyであることがソースコードよりわかります。
なのでPythonでちゃちゃっとやります。
パスフレーズがわかりました。イエーい。まあそれはおいておいて、今回はFridaがメインみたいなところありますからね、、

Frida

Fridaとはモバイルアプリケーションの動的解析ツールです。静的解析と違ってソースコードを書き換えてリビルドしてアプリを起動する、といった一連の流れをスキップして動的に解析が可能です。
使い方は少々面倒ですが公式のドキュメントを頑張って読みましょう。 まずはfridaとfrida-serverのインストールです。frida-serverはアンドロイドに埋め込んでfridaを実行できる環境にするためのものです。
では、fridaのドキュメントを参考にしながらbypassのためのコードを書きます。exploit.jsと命名しました。アプリの挙動から考えて起動後最速でHookしたいですね。あ、Hookとはアプリケーション外に定義されたスクリプトを実行する行為のことを言います。

ここではアプリ起動時のroot detectedのスクリプトをHookingにより無効にします。そして入力可能な状況を確立し、先ほどのパスフレーズを入力して目標を達成します。他にもいろいろやり方はあるのでいろんなwrite-upを参考にしてくださいね。

exploit.js

ではHooking用のスクリプトを書きます。このjsのコードをpythonのファイルに埋め込んでpythonのAPIより実行します。
最終的にはこんな感じ
あとはターミナルを開いてfrida-serverを立てたのちにpyを実行するだけです。
起動時
rootをbypassできました。先ほどのパスフレーズを入力してみると
簡単ですね。ちなみに、Pythonでなくてもjsでfrida CLIから実行する場合は

Root Detection

iOSのJailbreak検出の実際の手法をいくつか紹介だけしておきます。

  • System Files Check
  • Symbolic Links Detection
  • Calling Cydia’s URL Scheme
  • Loaded Libraries
おそらくわかりやすいのは一つ目ではないかと思います。これはTweak含め、特定のファイルがあるかないかで検出します。たとえばWinterBoard.appiCleaner.appなどですね。今回の例題だとc.cにあたります。ソースコードを見てみてください。

とはいえ、level1なだけあって簡単ですね。マルウェア解析もやっていきたいです。

References


UpliftModeling 入門

こんにちは。kzです。
本日はアップリフトモデリングやっていきます。こちらも傾向スコア分析と同様にマーケティングの分野で使われる機械学習的な手法です。ちなみに論文の原本はこちらです。 まず前回の復習を行い、今回のアップリフトモデリングとの違いをはっきりさせましょう。

傾向スコア分析

復習です。傾向スコア自体はバランシングスコアの特殊形として定義される実数でした。その実数を出力する関数(モデル)としてロジスティック回帰を使うのでした。こうして得られた傾向スコアがRubinのSUTVAを満たしてくれるおかげで、「もしTreatmentを受けていたら〜」の代替として扱えるのでした。

今回のアップリフトモデリングは少し異なります。名前の「アップリフト」からわかるように費用対効果を最大化するためのモデリングです。つまり、どういったユーザーをTreatすれば無駄なく効果を最大化できるかをモデリングします。一方で傾向スコア分析は因果効果の推定方法です。

Who is Target ?

上のセクションで述べた「どういったユーザー」について確認します。Rubinのモデルを思い出してください。「もし〜だったら」も含めたユーザーの行動の有無を考えると行動パターンは次の4種類になります。
前回のサイゼリアを例にするとTreatmentはクーポンの配布です。ラベルYがサイゼリアに行ったか、行かなかったかです。アップリフトはこのクーポンの費用対効果を最大化させるための指標です。

見ての通り、図中の白い部分のユーザーを対象にクーポン配布することが最も効果的であることがわかります。

Two-Model Approach

ではそのアップリフトの定義です。
The uplift is defined as the difference between success probabilities in the treatment and control groups.

見ての通りこれは各集合における成功確率の差です。(モデルはそれぞれ定義します。)したがってアップリフトモデルは
として定義されます。ちなみに、参考文献ではアップリフトを差ではなく、割合として定義されていました。おそらくどちらでも構わないと思いますが、この記事では論文にしたがって差として話を進めていきます。(割合にすると理論上は無限まで飛びます。)

また、先ほどの図とこのUMの値を共に考えていただきたいのですが、UMが大きいとはつまり、P(Y=1|X, G=T)が大きく、P(Y=1|X, G=T)が小さいことを意味します。これはまさに図中の白い部分に相当します。逆も同様です。したがってアップリフトが費用対効果最大化の指標として素晴らしいことがわかります。

AUUCとLIFT

AUUCはアップリフトモデリングの指標になります。
The Area Un- der the Uplift Curve (AUUC) can be used as a single number summarizing model performance.
AUCのように面積が広い方が精度が高いことを意味します。このAUUCの導出の際にLIFTと呼ばれる値を用います。AUCがどうやって導出されたかを思い出して考えます。AUCは無数の閾値で与えられたグラフでした。さらにTPRとFPRに対してトレードオフの性質を持っていました。AUUCも同じようなものです。

アップリフト上位のk個のサンプルに対して次がliftになります。
N_TはTreatmentの総数です。またベースラインはアップリフトの上位ではなくランダムで算出した値になります。

ここで考えます。アップリフト上位のデータ群に対するLIFTは右上がりになりますよね。これは先ほどのUMの写像の際の説明からわかります。となると逆も然りです。つまり、アップリフト下位のデータ群はLIFTは右下がりになることが予想できます。したがって最終的にAUUCのグラフはAUCと同様に凸関数のような形になり、その頂上を刺す時のUPLIFTが閾値として最適であると判断できます。(AUUC図のx軸はアップリフトの降順、y軸はLIFT)AUUC自体はbaselineとliftに囲まれた実数になります。

ここまでのTwo-Model ApproachではTreatmentとControlのそれぞれについてmodelを用いてYを予測しました。しかし、二つのmodelを用いることによってパラメータチューニングが難しくなるなどの問題点があります。共変量シフトがあるかもしれないので。そこで単一のモデルのみを用いたClass Variable Transformationについてみてみます。

Class Variable Transformation

とはいえ単一のモデルでどうやってアップリフトを定義するのでしょうか。非常に気になります。文字がかなり出てきますが頑張っていきましょう。

まずは次の変数を導入するところからです。
これを用いて先ほどと同じようにZについて確率を計算してみます。
ここで割り当ては無作為を仮定します。これ重要。したがって
こちらも必要な仮定になります。
また、次も成り立ちます。
すると次が得られます。
お、できました、移項すると
つまり新しく導入したZが1になる確率を予測するモデル一つで先ほどと同じようにアップリフトが算出できるということです。

ちなみにAUUCとLIFTはアップリフトモデリングの指標なのでこちらのアプローチにももちろん使えます。

アルゴリズムの比較

まずはAUUCです。
閾値としてのアップリフトスコアは0.03あたりが良さそうです。ちなみにスコアと各確率は次のような感じ
先ほどのグラフで原点より左が潰れていることがここから確認できます。ではもう一方のアルゴリズムでも確認してみます。
シングルモデルのおかげか綺麗なグラフになっています。ちなみにコンバージョン率のパーセンタイル分布は以下のようになってます。
シングルモデルの方が上位60パーセントにおいてTreatの効果があることがわかります。

長くなりましたが実装貼っておきます。
一般化傾向スコア分析が難しすぎます。でわ

References

Android リバースエンジニアリング 入門

こんにちは。kzです。

前どこかの記事で書いたかもしれませんが、僕はリバエンが大好きです。好きすぎてやばいです。めちゃめちゃ楽しいので皆さんにも紹介します。

UnCrackable App for Android Level 1

リバエンしていきたいと思います。この.apkはCTF的なやつでroot detectedをbypassするのが最終目的になります。しかし今回の記事では.apkからJaveのコードをデコンパイルするまでの内容になります。

apkってなに?という方もいるかと思うので用語などについて説明します。

Introduction to .apk file

アンドロイドのアプリケーションは.apkという拡張子を持ちます。実はこれは.zipと同じでリネームして展開すると開ます。今回の.apkを例にとって開いてみましょう。
見ての通り.pngなどいろいろありますね。これはあくまで一例ですが、いくつか紹介します。
  • AndroidManifest.xml
    • permissionとかpackageとかapiとか
  • META-INF
    • MF アプリのハッシュ値
    • RSA アプリの証明書
    • SF: list of resources and the SHA-1 digest of the corresponding lines in the MANIFEST.MF file
  • classes.dex
    • コンパイルされたJava(Kotlin)のDalvik bytecode(プログラムの部分)
  • res
    • 画像とかのリソース
  • assets
    • マルウェア系が組み込まれやすいところ
  • lib
    • nativeライブラリ
  • .smali
    • .dexのアセンブリ
僕もまだよくわかってないところが多いですがとりあえず、.xmlとclasses.dexくらいだけまず気にかけておけばいいです。ちなみに.smaliはこんな感じ

From .apk To .dex

上では.apkを.zipにリネームしてから開く方法を紹介しましたが実はこれよくないです。なぜならば一部がバイナリ エンコードされています。そこで専用のツールを使って.apkをdecompileして.dexを取得する方法を紹介します。
apktoolというものを使います。これを使えば.apkを展開できます。結果的に上で紹介したAndroidManifest.xmlなどが見れます。
上のどちらかのコマンドで.apkを展開できます。

これで展開したので.smaliを直接書き換えてから.apkを新しくリビルドする作戦でもいいですが、初心者には少しきついのでとりあえずここではJavaのソースコードまでコンパイルする作戦でいきます。ソースコードが見れれば振る舞いが理解しやすいですしね。

そこで.dexをJavaに変換するツールが必要になります。

From .dex To Java (decompiled)

dex2jarというものをつかいます。 どちらも一応同じものですが
  • d2j_invoke.sh
  • d2j-dex2jar.sh
をchmod +xで実行可能にします。そしてdex2jar-2.0/d2j-dex2jar.shを実行するだけです。一連の流れをまとめますと
出力される.jarファイルはclasses-dex2jar.jarです。ちなみに.apkから.jarまで一気にやるパターンは試してません。

See Decompiled Java Code

あとはJD-GUIを使えばソースコードが見れます。
僕はmacなのでmac版をインストールして上で作ったclasses-dex2jar.jarを開けば
いい感じです。

Resign signature

デコンパイルした.apkをEmulatorでも実機でもどちらでもインストールしようとすると
Failure [INSTALL_PARSE_FAILED_UNEXPECTED_EXCEPTION]

とエラーが出る場合が多いです。そんな時はsignature(certification)が潰れてるので再発行します。その前にリビルド
からの
これでインストールできます。adb系のコマンドはいろいろありますね。
とりあえず今回はここまでにします。リバエンかfridaかどっちが好きですか?

References

コンピューターにとっての「あ」とは

こんにちは。kzです。

僕の長年の疑問を解決しようと思います。それはコンピュータが「あ」という文字をどのように理解しているかです。同じ疑問を持たれている方は多いはず、、、?

1バイト文字

1bitは0か1が入る箱です。これが8つ集まって1byteです。1byteは00000000~11111111のように表現できるので例えば

  • 00000000を「あ」
  • 00000001を「い」
のようにしていくと1byteは2^8=256個の情報を対応づけられます。なので256文字以内だと1byteで表現できますね。例えばアルファベットは26文字です。このように1byteで表現できる文字を1バイト文字と言います。また、対応付る文字を文字集合、それにビットを対応づけたものを文字コード(符号化文字集合)と言います。下のようにACSIIは一例です。
おや?UTF-8 Unicodeというものがありますね。これについては下で説明します。ところで、日本語は、、?平仮名だけだと約70なので大丈夫ですが、常用漢字は2000を超えます。これではまずい、

Unicode

上でUnicodeなるものが登場しました。これも文字コードの一種です。

  • Unicode: 世界中で使われている文字や記号たち
  • JIS: 平仮名とか
  • ASCII: アルファベットと一部の記号

UTF-8

これは符号化方式です。他にShift-JSなどがあります。文字コードを定義したにもかかわらず、なぜこんなものが必要なんでしょう?複数の文字コードを併用する際に必要になるそうです。
  • Unicode: UTF-8
  • JS: Shift-JS
のように異なる文字コードは異なる文字符号化方式を使っているので互換性を持たせる時に使うらしいです。

コードポイント

上の1byteの文字でやったように世界中の文字(Unicode)に対して同様の操作を行った時に付与される個別のコードをコードポイントと呼びます。16真数表示が一般的で先頭に「U+」がつきます。
で、ここから難しいんですけど、コードポイントは符号空間という場所で割り振られているようなんですがそこに「」という概念がありまして、、
正直よく分からないのですが、第ゼロ面の基本多言語面(BMP)だけとりあえず気にすれば良さそうです。

BMPとか

BMPは第ゼロ面です。コード位置はU+0000~U+FFFFです。これをもう少し細かくみます。
  • 1byte(U+0000~U+007F)
ASCII文字
  • 2byte(U+0080~U+07FF)
ギリシャ文字、アラビア文字
  • 3byte(U+0800~U+FFFF)
日常で使う文字はほとんど3バイト: U+0800 ~ U+FFFF だそうです。

Conclusion

とりあえずいろんな方式や文字コードがあったのでコンピュータが「あ」をどのように受け取っているか正確なことはわからないがイメージはできた。UTF-8が最もポピュラーらしいので「あ」は「\xe3\x81\x82」ということにしよう。

この文字はなんバイト?

もうこの時点で、「あ」がなんバイトなんだ、のような話はあまり意味を為さないと思えてくると思いますが、少しまとめます。

異体字セレクタ

元号が令和になりました。で、この「令」の漢字色々ありますよね。経済産業省のホームページには次のような質問がありました。
下に書いてある「異体字セレクタ」ですが今回の
令
令
が異体字に当たります。これらの微妙な違いに対してコードポイントを付与する行為は非常にもったいないと思いませんか?そこでベースとなる漢字を基底文字と呼ばれるものを用意してそれを装飾しようという仕組みが異体字セレクタです。そして参考にある日経の記事によると漢字は2byteから8byteへ変わろうとしているらしいです。

Cのメモリについて勉強しているときにふと気になって調べると色々わかって楽しかったです。でわ

Reference

dockerでkali-linuxの環境構築

こんにちは。kzです。

今回は久しぶりにセキュリティ関連の記事です。ちなみに前回は

をやりました。あれからGhidraがなぜか動かなくなって困っているんですよね僕。それはいいとして今回はdockerでkalilinuxの環境構築です。

KaliLinuxとはなんぞや?

このページを見ている方の大多数はMacかWindowsかLinuxを使っておられると思います。僕はMacです。そしてそれぞれOSというものがあります。今回扱うKaliLinuxとはLinuxOSの一種であり、ペネトレーションなどのセキュリティに優れています。ちなみに双子の兄弟的な存在のParrotOSというものもあります。

Dockerとはなんぞや?

例えばこんな状況があります。

  • Macbook使ってるけどWordとか使えへんしWindows使いたいわぁ
  • Windowsとりあえず生協で買ったけどLinux使ってみたい
そんな時に、Dockerが有効です。簡単にいうと今あるPCで別のOSが使えるんです。ちなみに同じことを達成する方法として

  • Virtual Machine
  • Vagrant
  • Dual Boot
などが僕の知ってる限りあるんですが僕みたいな初心者は上記はとりあえずやめましょう。そしてDockerを使いましょう。利点をズバリ簡潔にいうと「速い・軽い・楽」につきます。ということでインストールしましょう。

Kitematicとはなんぞや?

これはGUIでdockerが使える便利ツールです。GUIがわからない方は次をイメージしてください。

  • GUIは.ipynb
  • CLIは.py
とにかく初心者の方が使いやすい(コマンドを打ち込みまくらなくていい)ものがGUIなんです。
ということでダウンロードしましょう。

kalilinuxのコンテナをゲットする

まずはインストールしたDockerをアプリケーションから起動しましょう。すると下のようにメニューバーのクジラのアイコンを押すと少し経ってから緑になります。
次にKitematicを起動します。
左にあるのがコンテナです。多分みなさんはまだ空のはずです。ちなみにDockerfileは下のものです。

Createしたら左にコンテナが生成されると思うのでそれをクリックしてから
するとTerminal(Windowsの方はCommandPrompt)が開くと思います。ちなみに僕はItermというオシャンティなやつを使ってます。

ツールのInstall

これでKaliLinuxが使える状態にはなりましたが、色々とツール(パッケージ)をインストールする必要があります。なのでやっていきましょう。
パッケージをインストールする前に必ずすべきコマンドが二つあります。

  • apt-get update
  • apt-get upgrade
です。apt-getとはパッケージマネージャーです。pipみたいなやつです。KaliLinuxはDebianベースのLinuxなのでapt-getになります。ではインストールしていきましょう。

  • apt-get install vim
  • apt-get install nmap
  • apt-get install metasplot-framework
他にもインストールしたい方はぜひ。最後にインストールしたmetasplotは有名なやつです。(僕はスクリプトキティ、、、)実際に起動してみましょう。

  • msfconsole
アスキーアートは起動毎に変わります。無事起動できました。exitで抜けられます。

イメージの保存

今色々パッケージをインストールしました。これを元に新たなイメージを作ろうと思います。Docker用語としてイメージ・コンテナがあります。簡単に説明しますと

  • イメージはカップ麺にお湯を入れる前
  • コンテナはカップ麺にお湯を入れた後
つまり、違いは保存状態か、使える状態か、という点です。これを踏まえて今までの僕たちを振り返ると

  1. kaliをCREATEした(カップ麺を入手し、お湯を注いだ)
  2. execでkaliのコンテナに入りパッケージをインストールした(カップ麺の具材が増えた)
そこで、本来ならあり得ませんがこの具材マシマシの麺をオリジナル乾麺に戻します。それが今からする作業です。こうすることでいつでもオリジナルのカップ麺が食べられるんです。

ターミナルでDockerからBashに移動してから下のように打ちましょう。
上ではdocker commitでkali_envというイメージ名で作りました。今後このカップ麺を食べたくなった時は

  • docker run -it kali_env
としましょう。オプションについては

  • iはホストからコンテナをつなぐ
  • t(ttyの略)はコンテナからホストにつなぐ
  • itでコンテナ内部で作業をする時(kaliを使いたい時)
です。

感想

Dockerfileをいつものように書かないで済んだので楽でした。次回は早速metasploitした記事を書こうかな?あと調べているとvncというものを使えばブラウザでkaliが使えるようですね。勉強になりました。でわ。

Reference

位相空間論の基礎まとめ


こんにちは。kzです。

前回、集合論をまとめました。今回は位相空間論です。この分野は機械学習に密接に関係しているものになります。例えば
  • Reproducing Hilbert Space
  • Dimension Reduction
達があります。KernelやT-SNEなどですね。もう少し簡単な例だと距離、つまりKLなども関係してきます。そんな非常に重要な位相空間論をまとめます。前回同様に数学書形式で、コメントをちょいちょい残すことにします。

位相空間

定義

次の条件を満たすXの部分集合の族UをXの開集合系という
  • \emptyset,X \in U
  • U_1,U_2\in  U なら、U_1\cap U_2\inU
  • Uの元からなる任意の集合族\{  U_{\lambda}  \}_{\lambda\in\Lambda}に対し、\cup_{\lambda}U_{\lambda}\in U
UXの開集合系とするとき、UXに位相を定めるといい、(X,U)を位相空間という.また、Uの元は開集合と呼ばれる.位相空間の部分集合はその補集合が開集合となるとき、閉集合という.

命題

位相空間Xの閉集合全体の集合Fは次の性質を満たす.
  • \emptyset,X\in F
  • F_1,F_2\in Fなら、F_1\cup F_2\in F
  • Fの元からなる任意の集合族\{  F_{\lambda}  \}_{\lambda\in\Lambda}に対し、\cap_{\lambda}F_{\lambda}\in  F

命題

Xを位相空間、AXの部分集合とするとき、任意のa\in Aに対して、Xの開集合Ua\in U\subset Aとなるものが存在するなら、AXの開集合である.

集積点と孤立点

Xを位相空間、AXの部分集合とするとき、x\in XAの集積点であるとは、x\in UとなるXの任意の開集合Uに対して、(U-{x})\cap A \neq\emptysetが成り立つときにいう.Aの点で集積点でないものをAの孤立点という.

命題

Xを位相空間、AXの部分集合とするとき、AXの閉集合であるための必要十分条件は、Aがその集積点をすべて含むことである
ポイントとしては、位相空間は開集合のある空間ということですね。もっと雑にいうと「近さの概念」だと思ってもらっていいです。(違うんですけどね)位相にも密着位相など色々あるんですけど、これから距離などの議論を進めるための準備だと思ってくれるといいです。

定義

Xを位相空間とする.
  • 任意のx\in Xに対して、一点集合{x}Xの閉集合になるならば、XT_{1}空間という.
  • 任意のx,y\in Xに対して、x\neq yならば、開集合U_1,U_2x\in U_1,y\in U_2かつU_1\cap U_2=\emptysetを満たすものが存在するとき、XT_2空間またはハウスドルフ空間という.
  • 任意のx\in  XXの閉集合Fに対して、x\not\in Fならば、開集合U_1,U_2x\in U_1,F\subset U_2かつU_1\cap U_2=\emptysetを満たすものが存在するとき、XT_3空間という.T_1条件を満たすT_3空間を正則空間という.
  • 任意のXの閉集合F_1,F_2に対して、F_1\cap F_2=\emptysetならば、開集合U_1,U_2F_1\subset U_1,F_2\subset U_2かつU_1\cap U_2=\emptysetを満たすものが存在するとき、XT_4空間という.T_1条件を満たすT_4空間を正規空間という.
Xを位相空間とする.Xの点列{a_n}a\in  Xに収束するとは、任意のa\in UとなるXの開集合Uに対して、あるN\in\mathbf{N}が存在して、n\geq Nを満たす任意のn\in\mathbf{N}に対して、a_n\in Uが成り立つときをいう.また、このとき\lim_{n\to\infty}a_n=aとかく

命題

ハウスドルフ空間の収束点列の極限点は一意的に定まる.
空間が出てきましたが、覚えておくべきは「ハウスドルフ空間」です。次元削減の「T-SNE」において「多様体」というものが出てきますが、そこでハウスドルフ空間が大切になります。また、数学では「一意」が結構大切です。

連続写像

X,  Yを位相空間、f:X  \rightarrow Yとするとき、fa\in Xで連続であるとは、f(a)\in VとなるYの任意の開集合Vに対して、あるXの開集合Ua\in Uかつf(U)\subset Vとなるものが存在するときにいう.fXのすべての点で連続であるとき、fを連続写像という.

命題

X,Yを位相空間、f: X  \rightarrow  Yとするとき、fa\in  Xで連続であるための必要十分条件は、f(a)\in VとなるYの任意の開集合Vに対して、f^{-1}(V)aを含むXの開集合になることである.

命題

X,Yを位相空間、f: X  \rightarrow  Yとするとき、次の条件はすべて同値である.
  • fは連続写像である.
  • Yの任意の開集合Uに対して、f^{-1}(U)Xの開集合になる.
  • Yの任意の閉集合Vに対して、f^{-1}(V)Xの閉集合になる.

定義

X,Yを位相空間、f: X  \rightarrow Yとする.
  • Xの任意の開集合Uに対して、f(U)Yの開集合になるとき、fを開写像という.
  • Xの任意の閉集合Vに対して、f(V)Yの閉集合になるとき、fを閉写像という.
  • fが連続な全単射であり、逆写像f^{-1}も連続であるとき、fを同相写像という.

命題

X,Yを位相空間、f: X  \rightarrow Yを全単射とするとき、fが開写像であることと、fが閉写像であることは同値である.

命題

X,Yを位相空間、f:  X  \rightarrow  Yとするとき、次の条件はすべて同値である.
  • fは同相写像である.
  • fは連続な全単射開写像である.
  • fは連続な全単射閉写像である.
個人的にな意見ですが、「連続=開集合」のイメージを持っています。特に多様体の証明の時にめっちゃ使うイメージです。

距離空間

定義

次の性質を満たす関数d: X \times  X  \rightarrow\mathbf{R}が定義された集合Xを距離空間という.
  • 任意のx,y\inXに対して、d(x,y)\geq 0が成り立つ.
  • d(x,y)=0\Leftrightarrow x=y
  • 任意のx,y\inXに対して、d(x,y)=d(y,x)が成り立つ.
  • 任意のx,y,z\inXに対して、d(x,y)\leq d(x,z)+d(z,y)が成り立つ.

定理

(X,d)を距離空間とする.任意の\epsilon >0,a\inXに対して、B_{\epsilon}(a)={ x\in  X |  d(x,a)<\epsilon }と定義する.任意のa\in Uに対して、ある\epsilon >0B_{\epsilon}(a)\subset Uとなるものが存在するようなXの部分集合U全体からなるXの部分集合族をUとするとき、(X,U)は位相空間となる. 距離空間はこの定理により定まる開集合系により位相空間とみなす.
距離の定義は覚えましょう。KLは距離ではありません。JS divergenceは対称性を加味したものですね。

コンパクト空間

Xを位相空間とする.{  U_{\lambda}  }_{\lambda\in\Lambda}Xの開集合族で\cup_{\lambda\in\Lambda}U_{\lambda}=Xを満たすものをXの開被覆という.Xの任意の開被覆が有限部分被覆をもつとき、すなわち、Xの任意の開被覆{  U_{\lambda}  }_{\lambda\in\Lambda}に対して、\lambda_1,…,\lambda_n\in\Lambdaを選択して、\cup^n_{k=1} U_{\lambda_{k}}=Xとできるとき、Xはコンパクトであるという.Xの部分集合Aが相対位相に関してコンパクトとなるとき、Aはコンパクトであるという.

命題

Xを位相空間、AXの部分集合とするとき、Aがコンパクトであるための必要十分条件は、A\subset \cup_{\lambda\in\Lambda}U_{\lambda}となるXの任意の開集合族{  U_{\lambda}  }_{\lambda\in\Lambda}に対して、\lambda_1,…,\lambda_n\in\Lambdaを選択して、A\subset \cup^n_{k=1}U_{\lambda_k}とできることである.

定理

コンパクト空間からハウスドルフ空間への連続な全単射は同相写像である

補題

\mathbf{R}の有界閉区間[a,b]はコンパクトである. 定理 \mathbf{R}^nの部分集合Aがコンパクトであるための必要十分条件は、Aが有界閉集合となることである.

最大値・最小値の定理

Xをコンパクト空間、f:  X \rightarrow\mathbf{R}を連続関数とするとき、fは最大値・最小値をとる.

定理

(X,d)を距離空間とするとき、次の条件はすべて同値である.
  • Xはコンパクトである.
  • Xは点列コンパクトである.
  • Xは全有界かつ完備である

定理

\mathbf{C}^nの部分集合Aがコンパクトであるための必要十分条件は、Aが有界閉集合となることである.

中間値の定理

Xを連結空間、f: X \rightarrow\mathbf{R}を連続関数とするとき、任意のc\in\mathbf{R}に対して、a,b\in Xf(a)\leq c\leq f(b)を満たすものが存在するなら、x\in Xf(x)=cとなるものが存在する.
とりあえず、コンパクトだと便利なんです。また、私たちが議論する場はほとんどが実数世界なので「コンパクト=有界閉集合」なんです。なのでイメージしやすいと思います。イメージとしては覆得れば良いので水溜りも球体もコンパクトです。
今回は位相空間論でした。基礎を部分的にまとめただけなので詳しく知りたい人は数学書を読んでください。T-SNEなどの論文を軽く見るのもいいかもしれません。

Ghidraが人気のようですがマルウェア解析の記事ももっと書きたいですねえ。でわ。

集合論の基礎まとめ



こんにちは。kzです。

今まで数学に触れつつ機械学習を中心に書いてきましたが、おそらく読者さんは数学科の方ではないと思うのでアルゴリズムの記事をみて、数学書を読もうとした方が本を買ってから後悔しないように、大学一年で習う集合論というものを簡単にまとめてみました。なのでこれは素人の方が数学書の初戦でボコボコにされないための踏み台のような扱いになればいいかな、と思っています。なお、この内容は大学の数学科1年生が習うものになります。

集合

数学で考える対象のはっきりとした集まりのことを集合といいます。

ある集合Aに属する対象aをその集合の元または要素といい、a\in AまたはA\ni aと書きます。

有限個の元からなる集合を有限集合と呼び、無限個の元からなる集合を無限集合と呼びます。

An個の元からなる有限集合のとき、|A|=nと書く.便宜上、元を1つも持たない集合を考え、この集合を空集合と呼び、\emptysetと書きます。

集合を表す場合、{a,b,c,…}のように属する元を並べて書きます。

自然数全体の集合などに以下の記号を用います。

  • \mathbf{N} 自然数全体の集合
  • \mathbf{Z} 整数全体の集合
  • \mathbf{Q} 有理数全体の集合
  • \mathbf{R} 実数全体の集合
  • \mathbf{C} 複素数全体の集合
A,Bを集合とする.Aの元がすべてBの元であるとき、ABの部分集合であるといい、A\subset BまたはB\supset Aと書きます。

A \subset BかつB\subset Aのとき、A=Bと書きます。

A\subset BかつA\neq Bであるとき、ABの真部分集合といいます。

空集合は任意の集合の部分集合であると定義します。

A,Bの少なくとも一方に属する元全体からなる集合をA,Bの和集合といい、A\cup Bと書きます。

A,Bのどちらにも属する元全体からなる集合をA,Bの共通部分といい、A\cap Bと書きます。

Aには属するがBには属さない元全体からなる集合をAからBを引いた差集合といい、A-BまたはA\backslash Bと書きます。

集合Xの部分集合Aに対して差集合X-AA^cと書き、Xに関するAの補集合と呼びます。

Aの部分集合全体からなる集合をAのべき集合といい、2^Aと書きます。

有限個の集合A_{1},A_{2},…,A_{n}の直積をA_{1}\times A_{2}\times\cdot\cdot\cdot\times A_{n}={(a_1,a_2,…,a_n) | a_i\in A_i\ (i=1,…,n)}により定義します。ここで(a_1,a_2,…,a_n)は各i=1,…,nに対してA_iの元a_iを順序付けて並べたものです。

ここまでは高校数学でも経験があると思うので直積を除いて簡単ですね。直積は書き方が独特ですが、ただの写像です。簡単にいうと、「二倍する」という写像は引数をひとつ取り出力をひとつ返します。一方で「掛け算」という写像は二つの引数に対しひとつの出力を返します。このようにいくつかの引数を考えるときに直積を使います。

写像

集合Aの任意の元aに対して集合Bのある元f(a)を対応させる規則fのことをAからBへの写像といい、f:A\rightarrow Bと書きます。また、A\ni a\mapsto f(a)\in Bと書くこともあります。

Afの定義域,Bfの値域と言います。2つの写像f:A\rightarrow B, g:A\rightarrow Bに対してf(a)=g(a)\ \ (\forall a\in A)が成り立つとき、f=gと書きます。

A_{1}\subset A, B_{1}\subset Bとするとき、f(A_{1})={f(a)\ | a\in A_{1}}fによるA_{1}の像,f^{-1}(B_{1})={a\in A | f(a)\in B_{1}}fによるB_{1}の逆像と言います。特に、f(A)fの像といい、Imfとも書きます。

f:A\rightarrow BA_{1}\subset Aに対して写像f\vert_{A_{1}}:A_{1}\rightarrow Bf\vert_{A_{1}}(a)=f(a)\ \ (\forall a\in A_{1})と定義し、fA_{1}への制限と呼びます。

また、A\subset Xとなるような集合Xに対して写像\widetilde{f}:X\rightarrow B\widetilde{f}(a)=f(a) (\forall a\in A)となるものはfXへの拡張と呼ばれます。

2つの写像f:A\rightarrow B, g:B\rightarrow Cに対して写像g\circ f:A\rightarrow Cg\circ f(a)=g(f(a))\ \ (\forall a\in A)と定義し、fgの合成と呼びます。

「写像」という言葉が出てきましたがただの「関数」だと思ってもらって構いません。人によっては「作用素」と言う人もいます。「\forall」と言う記号については「for all」と読み、「任意の」と言う意味です。「\exists」は「exist」と読み「存在する」と言う意味です。

Proposition

  • 3つの写像f:A\rightarrow B,  g:B\rightarrow C,  h:C\rightarrow Dに対して等式h\circ(g\circ f)=(h\circ g)\circ fが成り立つ.

Definition

A,Bを集合とし、f:A\rightarrow Bを写像とします。
  • \forall a_{1},a_{2}\in A\ \ s.t.\ \ f(a_{1})=f(a_{2})\Rightarrow a_{1}=a_{2}が成り立つときfは単射であるという
  • \forall b\in B,\exists a\in A\ \ s.t.\ \ f(a)=bが成り立つときfは全射であるという
  • fが単射かつ全射であるとき、fは全単射であるという
集合AからAへの写像fで任意のa\in Aに対してf(a)=aと定義したものをAの恒等写像といい、id_{A}と書きます。

写像f:A\rightarrow Bに対してある写像g:B\rightarrow Aが存在してg\circ f= id_{A},f\circ g= id_{B}が成り立つとき、gfの逆写像といい、g=f^{-1}と書きます。

「逆写像」とよく間違えられるもので「逆像」と言うものがあります。また、「恒等写像」が出てきましたがこちらは有名なResnetのアルゴリズムで登場します。

Proposition

  • f:A\rightarrow Bが逆写像を持つこととfが全単射であることは同値である

関係

A\times Aの部分集合RAにおける関係といいます

Definition

Aにおける関係Rは次の3条件を満たすとき、同値関係という。ただしx\sim y(x,y)\in Rを表す。
  • 任意のx\in Aに対してx\sim x (反射律)
  • x\sim yとなる任意のx,y\in Aに対してy\sim x (対称律)
  • x\sim y,  y\sim zとなる任意のx,y,z\in Aに対してx\sim z (推移律)
\simA上の同値関係とするとき、C(x)={y | y\sim x}x\in Aの同値類といい、A/ \sim ={C(x) | x\in A}A\simによる商または商集合といいます。

x\in Aに対してC(x)\in A/\simを対応させる写像をAからA/\simへの自然な写像といいます。

A/\simの元Cに対してx\in CとなるAの元をCの代表元といい、Aの部分集合RA/\simの各元(つまり同値類)の代表元をちょうど1つずつ含むとき、Rを完全代表系といいます。

「同値類」、「商集合」は初見で理解するのは難しいものだと思います。僕のイメージとしてはとある集合に対して「グルーピング」の動作を考えます。ここでグルーピングされてできた新たな集合を商集合、各グループを同値類、グルーピング方法を同値関係と言います。簡単な例は割り算のあまりです。

Definition

Aにおける関係Rは次の3条件を満たすとき、順序関係といいます。ただしx\leq y(x,y)\in Rを表します。
  • 任意のx\in Aに対してx\leq x (反射律)
  • x\leq y,\ !y\leq xとなる任意のx,y\in Aに対してx=y (反対称律)
  • x\leq y,\ !y\leq zとなる任意のx,y,z\in Aに対してx\leq z (推移律)
順序\leqの与えられた集合を順序集合といいます。

順序集合Aの任意の2元x,yに対してx\leq yまたはy\leq xのいずれかが成り立つとき、Aを全順序集合といいます。

A_1を順序集合Aの部分集合とするとき、Aの順序関係をA_1\times A_1に制限すればA_1もまた順序集合となります。

このとき、A_1Aの部分順序集合という。順序集合Aの部分順序集合A_{1}が上界を持つとは、あるa\in Aが存在して、任意のx\in A_1に対してx\leq aとなる場合をいいます。

任意の全順序部分集合が上界を持つような順序集合を帰納的順序集合といいます。また、a\in Aは任意のx\in Aに対してa\leq xならa=xとなるとき、Aの極大元といいます。

順序集合に関しては記号のせいか混乱する友人が多いです。あくまでただの記号なので大小を図る記号の存在は一旦忘れてください。

多様体シリーズとかも欲しいですか?でわ。

Pythonでやる多次元ニュートン法

こんにちは。

以前、ニュートン法について述べましたが1次元でした。やっぱり多次元じゃないとあんまりスキルアップにならないですよね。ということでやります。ちなみに差分法を使います。しかし、この記事で初めてニュートン法を知る人のためにも簡単にアルゴリズムを説明してから実装へ移りましょう。 上のリンクがヒジョーーーーにわかりやすいです。では、始めましょう。

結局はこれ、テイラー展開

テイラー展開は非常に便利です。本日もいつものように勾配法を使うのですが、結局局所的にしか関数は見ないんです。「局所的に」というキーワードが来れば「テイラー展開」と覚えましょう。そして一般的にテイラー展開は2次の項まで使われます。すなはち、

    \[ f\left(x_{k}+ x\right) \approx f\left(x_{k}\right)+\nabla f\left(x_{k}\right)^{T}  x+\frac{1}{2} x^{T} H(x_{k})  x\]

上のは多変数関数fx_k周りでテイラー展開し、二次の項までで近似したものです。ここで\nabla f\left(x_{k}\right)^{T}を勾配、H(x_{k})をヘッセ行列と言います。ヘッセ行列の定義は簡単です。
微分を並べるだけです。ちなみに、一変数の場合は次のようになります。

    \[H(f) = \nabla^2 f(x) = f''(x)\]

ニュートン法について

ではニュートン法ですが、まず正定値行列を知る必要があります。正定値行列とは
n\times n行列Aが正定値とは、\forall \epsilon x \neq 0に対してx^T A x > 0となること。

なぜこれが重要かというと、極値判定に使うからです。つまり、正定値であれば極小値、負定値であれば極大値です。覚え方は単純、ヘッセ行列は2回微分なので単純に「微分増加率が正か負か」で覚えましょう。極大値であれば「負」になりますね。そしてお待ちかねの更新式は非常にシンプルです。

    \[ x^{t}=x^{t}-\left(\nabla^{2} f\left(x^{t}\right)\right)^{-1} \times \nabla f\left(x^{t}\right)^{T}\]

ヘッセの逆行列をとるので、正則でなければこのアルゴリズムは「THE END」です。加えて、変数の数が多いと逆行列計算がヤバくなって破綻します。一方で、シンプルな勾配法よりも収束が早いことが知られています。では今回の問題を考えます。

ニュートン法 with 差分法

今回の問題はちょっと複雑です。
見ての通り少し複雑です。他のブログで紹介されているニュートン法はシンプルであり、結果的にベクトルとして書き換え直接勾配やヘッセ行列が計算できるようになっていますがこれは見ての通り厳しい。そこで差分法により解決します。差分法を覚えてますか?微分の定義式を使って数値計算により偏微分を計算します。今回の最適化問題は嬉しいことにcontinuousな関数なので偏微分の順序交換が可能です。すなはち

    \[f_{xy}  =  f_{yx}\]

です。なぜこんなことを気にするかというと今回は二変数のヘッセ行列を求めるのでこれらをそれぞれ計算する必要があります。さらに前述通り差分法を用いた数値計算です。少しでも工夫するためにはこの等式を活用する必要があります。ヘッセ行列の定義式よりH_{12} = H_{21}が言えるので計算が1つ減りました、わーい。ではコードに移りましょう。

実装

2種類の初期値を使っています。片方は極小値に行っていないことがわかります。これは初期値が極小値に近くないことが原因です、つまり、ニュートン法はいつでも便利というわけではないということです。

Ghidraでマルウェア解析入門

こんにちは。

本日はマルウェア解析のチュートリアルです。
使うツールはなんとGhidraです。2019年3月5日、NSA(アメリカ国家安全保障局)が、Ghidraを公開してくれました!わーい。
これはリバースエンジニアリングのツールです。逆アセンブルとも言えますでしょうか。今まではHopper Disassembler v4とかが同じツールでありますが個人的にアレの使い方がよくわからなかったのでこれを機に乗り換えます。では早速、インストールに移りましょう。個人的にJavaのインストールにかなり手間取ったのでその辺詳しく説明します。

Ghidraのインストール(Mac)

まずはGhidra本体のダウンロードを行います。 上のリンクからダウンロードを押すだけです。そしてフォルダの中身を見てみると次のようになっているかと思います
docsをダブルクリックしてみると installationGuide.html というものがあるのでそれを読んでみるとJDK11が必要であることがわかります。なのでインストールしていきましょう。 まずは上をダウンロードして
  1. $ tar xvf ./Downloads/openjdk-11.0.2_osx-x64_bin.tar
  2. $ vim ~/.bashrc
  3. export PATH=~/jdk-11.0.2.jdk/bin:$PATH の1行を追加
で、ターミナルで
  1. $ java –version
  2. $ /usr/libexec/java_home -V
とやってみて11が確認できればいいのですがおそらくできていないと思うので最後に からMacOSのものをダウンロードして解答後 pkg をダブルクリックでインストールするとjavaがインストールできたはずです!

Ghidraの起動

先ほどダウンロードしたGhidraのフォルダの中にghidraRunという実行ファイルがあるのでダブルクリックすると起動します。(batじゃないよ)またはターミナルで次をタイプします。
  • $ /Users/username/ghidra_9.0.4/ghidraRun ; exit;

Malware解析の超絶入門

ではマルウェア解析の練習、いや、基礎の基礎、いや、Ghidraの使い方、を学びましょう。 から練習問題をダウンロードします。そしてGhidraを起動し、Newprojectを適当に作ってから先ほどダウンロードしたstring1を解答したもの(exe)をドラッグします。すると
このようになると思うのでダブルクリックで起動。
Yesをクリックしてオプションを選択させられますが無視してAnalyzeをクリック。警告など出ればとりあえずOK押してください。

さて、string1をダウンロードしたサイトによればFLAGを見つける問題のようなので探します。CTFですね。
strings1.exe contains an un-encrypted flag stored within the executable. When run, the program will output an MD5 hash of the flag but not the original. Can you extract the flag?

なぜか僕の環境ではダブルクリックで開くことができなかったんですがそれはおいておいて、hash化されているようなので左のFilterでhashとフィルタリングします。
アセンブラにはあまり詳しくないのですがここをみるとmd5_hashという関数がハッシュ化する関数だということが予測できます。そしてスクロールダウンすると
おっと、ありましたね、しかもFLAGって書いてあります。ここをダブルクリックしてみると

たくさんフラグがありますね。他のものは無視して
FLAG{CAN-I-MAKE-IT-ANYMORE-OBVIOUS}
をコピペして先ほどのサイトに入力します。
CHECK FLAGをクリックすると正解と出ました。やったあああ。

感想

リバースエンジニアリングには非常に興味がありますが、アセンブリの知識がまだまだ素人です。なのでこのサイトの問題を解きつつわからないキーワードを調べて勉強していこうと思います。

Reference