coinsAC受かった
受かった嬉しい😊
Fuzzingに入門したいんすけど①
はじめに
セキュリティ・キャンプのネットワーククラスでは、実践的にファジング(Fuzzing)をして脆弱性を発見するといったことをした。あくまでファジングは脆弱性を見つけるプロセスであるため、アプローチはいくらでもある(はず)。講師であり、リサーチャーである園田さんからSCWやオンライン線形分類器を使ったfuzzのデータセットを研究するたのも面白いのではないかと言われ、黄色い本を読んでいる最中だ。しかし、今回はファジングの可能性について見てみたい。幼稚な日本語を要しているため読みづらいと思うし、間違っているところもあると思うし、正直自分のメモのために書いているのであまり読まないで欲しい。すぐ閉じて欲しい。
ファジング及びDowser
Dowserとは、BufferOverflowやUnderflow脆弱性などを減らすために、Fuzzingとシンボリック実行(symbolic execution)、テイント追跡 (Taint Tracking)と組み合わせたロジックである。
BufferOverflowはずーっとなくなることのないソフトウェアのエラーのひとつだ。Overflowが(実行時に)起きたときにプログラムを強制的に終了させるようなメモリプロテクタによりセキュリティを強化させるか、上記したように、ファジングなどのテスト段階で脆弱性を追跡するかなどがある。
メモリプロテクタには、私達pwnerが殺しまくっているCanaryや、WITのような複雑にするためのコンパイラ拡張などもある。しかし、それでは脆弱性を隠しているようなもので、脆弱性がなくなっているわけではない(=Crashしてしまう可能性がある)。だから、ファジングのような脆弱性を見つけるものが好かれていくわけだ。
Microsoftなどは、2008年から24時間365日ファジングを稼働している。しかし、現在のFuzzer(Codenomiconは除く)の精度は大したことはなく、入力フォーマットにばかり焦点を当てて、Software自体を無視しているとされている。つまり、BlackBoxのファジングは速くて人気ではあるが、効率が悪い。
各々に長所と短所があるように、WhiteboxファジングはBlackBoxに比べて原則が多い。だでぃ子さんのブログに書かれていたシンボリック実行(ex. KLEE , S2E)によって、可能であるすべての実行パスを処理してバグ、脆弱性を見つけるというものがある。だでぃ子さんがブログに書いてあったように、計算量が膨大になってしまうため実用には困難となる。
ターゲットを絞ろうぜっていう話だ。このようなアプローチは、反復方式でコード領域のシンボリック実行を行うことで、バッファオーバーフロを見つけることが出来て、既存のFuzzerでみつけることが難しかった複雑なバグ及び脆弱性をある程度高速に発見することができる(かもしれない)。
方法
上記したように、「victimとなるソフトウェアを決めて、脆弱性はバッファオーバーフローであり、そのソフトウェアのここらへんに脆弱性がありそうだ」と言ったように莫大な計算量を減らすためにスポットを特定しておく必要がある。
1.可能な限りプログラムをたくさん実行する
2.Dowserが脆弱性が潜むであろう箇所を特定してくれる
バッファオーバーフロは、バッファ領域として設定されているアドレス範囲を超えたメモリが上書きされ、誤動作が引き起こされるであるため、そこに集中して、他のコードの大部分を無視する。Dowserはそのようなアクセスをランク付けするようなプログラムを静的に解析する。1つの評価関数ではなく、色々なものを用いる。あと直感的に考えても、ポインタの演算や、複雑な制御フローが単純な配列アクセスに比べてメモリエラーが増えることは明白だ。
Dowserはそのようなプログラムに着目して、脆弱性であろうプロウグラムの優先順位を決定する。なぜそんなことをするのかというと、そうすることにより上記したような「浅いバグ」に無駄な時間を費やすこともなく危険の高い複雑なものを見つけるためだ。他にも、シンボリック実行をするため具体値の入力のベースラインとして、*concolic testing[1]を使う。
DowserはConcolic executionを使うことによってシンボリック実行をより精度の高いものとする。
1.Dowserは上記したようなエラーが起こりうる可能性が高いポインタ参照などを検査する。そして、ポインタの値を変更される可能性の高い木(枝)に沿ってシンボリック実行をしてゆく。
2.Dowserは配列のアクセスのために使われるポインタがどの入力バイトが影響するかを決めるために動的テイント解析(Dynamic Taint Analysis)を使う。つまり、それをシンボリックとして扱う。動的テイント解析自体は新しいものではないが、可能な限り精密なものにシンボリック入力のデータセットを近づけるために最適化を行う。
まとめ
「はじめに」に書いてあるようにアプローチとして、Dowserという新しいファジングの可能性について少しだけ見た(というよりこれ序盤なのでもっと書いていきたい)。上記でめっちゃ言ったが、Dowserは「すべてのバグを見つけてやる👊」という概念ではなくて「はぃ…私はここ(特定のクラス)のバグ見つけます」という概念であるため、実用に富んでいるんではないかと考えている、実際コードインジェクションなども少なくなるはず。
実際、DowserによってNginx,ffmpeg,inspircdみたいな複雑なプログラムのバグを見つけたそうだ。うほ、なるほど。つまり、既存のシンボリックツールで見つけることが困難だったもので見つけることが出来たのか。可能性を感じる。
感想
「だでぃ子さんのブログ内容カッコイイな〜(鼻ホジホジ)」って思って、私もそれに関係しそうな論文とか漁って書いたが、あまり詳しくない部分もあった。例えば、LLVMとしてダウザー解析をしてシンボリック実行ステップとしてS2Eを採用している,とか。それこそ、「LLVM Bitcodeに一回変換して〜」とか言ってみたいものだ。
セキュリティキャンプでファジングに出会ってvictimを何にしようかなどをずーっと考えていた時期があった。しかし、今となってはどういうアプローチでFuzzingするべきであるかということを考えるようになった。可能性は大きいほうが良い。もっと勉強しようと思う。
引用先
[1] concolic testing: symbolic(シンボル)とconcrete(具体値)からなる造語
http://ntddk.github.io/2014/09/12/symexec-intro
参考
Dynamic Taint Analysisに関する
Fuzzing活用の手引き(IPA)
Dowsing for Overflows: A Guided Fuzzer to Find Buffer Boundary Violations論文
追記
Pin Tools使ったMemory-In Fuzzingの記事だが、非常に興味深い。
http://shell-storm.org/blog/In-Memory-fuzzing-with-Pin/
- Choose a targeted piece of code.
- Set a breakpoint before and after our targeted area.
- Save the execution context when the first breakpoint occurs.
- Restore the execution context when the second breakpoint occurs.
- Catch the SIGSEGV signal.
- Repeat the operation 3 and 4 until the crash occurs.
Dowserと近しい部分もある。
Hopper+qira作りたい②
【はじめに】
昨日テンションあげあげで、@segfoさんと今後について話していた。
すると、昨日のブログ
のFeedbackにakiymさんから、
@ashigirl96 QIRAのIDA連携をHopperに持ってきたいのなら現状では無理。あと、読むべきはこれ https://t.co/kx1Eqt6lj4
— akiym (@akiym) 2014, 9月 4
と返事が来た。
正直嗚咽をした。しかし、私と@segfoさんは+qiraだけをしたかったわけではない。し、したかったわけじゃないんだからね!諦める必要もないので、引き続き【Hopper+qira作りたい】という記事で書いていきたい。
【別のプロジェクト、Hopperの問題①】
もう一つのプロジェクトに、IDAProとHopperのinstructionの相違を埋めたいというものがあった。@segfoさんによるとつまり、位置独立実行形式のバイナリはバイナリの中のアドレスが相対アドレスで書かれてるときがある。という。
下の図を見てもらいたい。
Hopper/Objdumpでは、call 0x8cdであるにも関わらず、
IDA Free,Pro/gdbでは、call putsというように、関数名として表示されている。
【問題改善、目標】
端的に言えばHopperScript/SDKを使い、『アドレス解決をして関数名とリンクをする』というようなことが出来れば良いのではないかと考えた。
正解であるgdbとIDAの挙動としては、メモリ上にあるバイナリを読んで、それに対応する命令を置き換えたら良いのではないかということになった。
実際、実行してメモリにロードしてアドレスが解決されると正常に見える、という感じである。
【そのために】
私はそのために、デバッガについて勉強するべきではと考えたが、@segfo氏曰く、「ローダーとは、プログラムを、メモリにロード(と必要であれば、メモリの初期化)して、
そのプログラムの実行必要なメモリを割り当てたり、Cのライブラリを初期化したり
最後にその実行したいプログラム(コンテキスト)に切り替える一連の作業をするプログラムであるから、call 0x8cdってなってるよく分からないアドレスが有りますけど、このアドレスを解決するのがローダのはず。このアドレスが解決されて、メモリの定位置を指すようにするのも多分OSの役目のはず。」という見解により、ローダーについて勉強しようと二人でなった。
「次の商品を購入しました:坂井 弘亮 『リンカ・ローダ実践開発テクニック―実行ファイルを作成するために必須の技術 (COMPUTER...#アマゾンポチ と入れて@返信でカートに追加・後で買う via @amazonJP」
本は即決で買った。明後日には届く。
楽しみだ。(テスト2週間前だけどそんなことどうでもいい)
【別のプロジェクト、Hopperの問題②】
以前、私と@_wata1221さんでpwnの問題を解いていた。すると、お互いの情報を交換している最中に、Hopperによりデコンパイルされた PseudoCがオカシイと@ucqさんに指摘された。
具体的に言うと、@ucqさん「memsetの関数呼び出しが消えて、rep stosdのようなものに置き換わる」とのことだった。
【問題改善、目標】
ディスアセンブリの時点で本来のinstructionになっていないという可能性はあるのだろうかと考えたが、本来の命令というか、memsetなどの一部の関数はコンパイラによって最適化され、関数でなくinline化される。つまり、コンパイラについて勉強したほうが良い。それを勉強してHopperScriptでパース出来ればと考えている。
【そのために】
コンパイラがどのようにしてソースコードからバイナリを作成して、その際にどのような情報が失われているのか(=セマンティックギャップ)を理解があった方が良いらしい。
HopperScriptでコンパイラのセマンティックギャップを埋めるたいと考えている。
純粋にコンパイラの勉強も怠らずに、wikipediaに載っているインライン展開についても勉強しようと考えている。
【最後に】
+qiraが出来ないのが非常にショックだったが、HopperのAuthorが処理にHookするような関数なり機能なりを作ってくれれば私と@segfoさんでどうにか出来ると考えている。(正直、デバッガがHookするための関数がないというのはオカシイはずなんだと思う)
それ以外にも課題はあるのでそれらの改善を目指していきたいと思う。
【追記】
某氏「たかがインライン展開のためにコンパイラについて学ぶのは非効率。
というかインライン展開はmemsetの様な有名標準関数以外では基本的に直すことにほとんど意味がない。IDAのデコンパイラでさえ、基本的に頭が悪いから、その頭の悪さと折り合いをつけてツールは使えるべきであって、直そうという努力も素晴らしいとはおもうけど、その前にそもそもデコンパイラなしで読めないのに使うなというのはあると思う。というだけなので別に間違ってはないと思うし頑張れ。まあ少し思うのは何でもかんでもソースコードと本読んで勉強するのが必ずしも良いことではないということですかね。そもそもよく知らないのに読んでも意味ないし。まあ実際努力次第では、インライン化されているかどうかを確率的に判定して読みやすくするみたいなことは可能だし、間違ってはないというのはそういう意味。インライン化されているかどうかなんて、セマンティックギャップ的にも判定出来ることじゃないから、単純に読みやすくするためにインライン化されていたと仮定するのはあり。」
↑感想、口悪い。
【追記②】
alcさん「最適化された命令列を最適化前の状態に戻したいということだよね。それめっちゃムズいやつ。de-optimizationって言ってやってる論文があるけど、一部の最適化に関してだけだねー。
Using de-optimization to re-optimize code ブログで言ってる②の方(インライン展開されたAPI呼び出しをcall api_nameっていう感じのシンボル使った呼び出しに直したいっていうやつ)だよね?FLIRTみたいなシグネチャベースでマッチさせるか、学習ベースでやるかのどっちかだと思うなぁ。手法的には学習使った方が賢いようにも思えるけど(汎化性能=ちょっと違う最適化された上でインライン展開されちゃったものにも対応できる性能を持たせられる)、かかる時間や誤認識がどれくらい出るか分からないし、実用的にはシグネチャを使うのがいいのかなぁ。という意味でIDAのFLIRTみたいにシグネチャをいっぱい用意しなきゃいけなくなりそうなので、②は超大変そう、っていう感じのツイートをしたのさー。(さっき」
Hopper+qira作りたい①
【はじめに】
我らがHopperにはgdbと連携させるプラグインがある。そして、私のHopperではなぜか使えない…。しかし、使いたい。ん?本当に使いたいのか、私は。もっとミーハー精神を出してもいいんではないだろうか。ということで、F**KIN' ブルジュアら(私が嫉妬してるだけ)が使うIDA Proと組み込ませて使うqira(当初のイメージは gdb+QEMUでエミュレーションを実現してるGeohotが作ったツール)を Hopperにも組み込ませたい。
【動機】
私の大好きなゲームであるpwnを効率よく遊びたいというものもあるのだが、
私の高専の3年生後期に「自由研究」というものがあり、QNX6.5(車載OS)のリバースエンジニアリングをしようと考えた。なぜ、リバースエンジニアリングの必要があるかというと、QNXは全部Closedなのだ。つまり、OSのカーネル部とかを見るために使わないといけない。あと、メモリ部はVoltility Frameworkで解析していきたいと考えている。
だでぃ子さんにVolatilityFrameworkを使ったツール教えてもらったのでこれも使えたら使いたいと考えている。
【懸念】
HopperもIDAPro同様 IDAPythonライクな物があるのだろうか?
実は、HopperScriptというものがある。しかし、 IDAProはバイブルが出てるぐらい汎用性?が認められているが、HopperScriptは公式でせえ全く興味なさそうな。しかし、「可能性は無限大」的なことを公式が書いていたので、可能性を信じてやろうと思う。
【協力者】
私は、binary/pwn強強の@segfoさんを誘った。理由としては、わたあめさんが「@segfoさんはbin/pwn最強」という事実と、「Hopper使いでありPythonistaだ」ということを聞いたからだ。
【環境】
BackTrack5を愛用しているのだが、qiraは極めて新しいツールなので、glibとかその辺りが対応していないらしい。パッケージもダメらしい。
そして、急遽 Kali Linux 1.0.9を入れた。
【インストール】
qira - QEMU Interactive Runtime Analyser - Google Project Hosting
を参照したとおりである。
【調べてわかったこと】
詳しくはまだ調べていないのであまり言及できない。
pin,cda,QEMUなどをコア?として、それらのプラグインをC言語で書いている。
Web及び、アプリケーションとして動かすために Pythonを使っている。
私と@segfoさんが重要視したフォルダは、middlewareとqemu_modsだが、qemu_modsは実装するときにあまり関係はなさそうだ。
middlewareの中で一番重要そうなプログラムは, qira_program.pyだった。
実際、Cから取ってきたqemuなどをWebアプリで実現させるためにレジスタとかホゲな感じだった。qira_analysis.pyも重要そうだが、いまいちなにをやってるのかわからない。
【実現性】
調べた感じでは、実現性は大いにある。
私「@segfo よし!とりあえず、qira使う&qiraのソース読むで仕様理解して、
HopperScriptの勉強したら行けそうですね!!」
というのが私の最後の感想だ。
【感想】
確かに出来そうなのだが、geohotが作ったものなので、ドキュメントライクなものが落ちていない。つまり、Hopperにプラグインするのに一苦労かかりそうだというのが感想だ。
だでぃ子さんとしゅーとくんはイケメン(QEMUの話
☆はじめに
今朝PostgreSQLの設定が終わって虚無感に襲われていた所、SFCの発表があるか伊賀るかみたいな話のときに、だでぃ子さんの発表内容しりてーなーとか思ってたらスライドくれたので読んでみました。内容はあまり言ってはいけないと思いますが、書かれていた単語にQEMUとか、仮想化?とか書かれていて、「仮想化って言っても、あまり知らねぇな〜」と思ったのでググりながら読んでみました。すると、エミュレーションとか、ゲストOSとか面白そうな単語がちらほら書かれていて、「っべーw面白そうw」ってなりましてどんどん読み漁りました。
☆内容
1.しゅーとくんの会話&だでぃ子さんのスライド
すると、イケメンしゅーとくんが
リア糞OS
— しゅーと (@shutingrz) 2014, 7月 30
@ashigirl96 俺の中で一番ダメなイメージ
— しゅーと (@shutingrz) 2014, 7月 30僕「what's the best?」
@ashigirl96 qemu=>virtualboxにしたら体感3倍位早くなった
— しゅーと (@shutingrz) 2014, 7月 30僕「@shutingrz エミュレータって仮想マシンと同じなん? アレじゃないの、QEMUって自由度有るんじゃない?(だでぃ子さんのブログとか読んでるとそんなイメージ」
@ashigirl96 CPUそのものエミュレートしてるらしいから自由度は高いっぽ
— しゅーと (@shutingrz) 2014, 7月 30僕「@shutingrz マジか。そもそも、OSごとでCPUの使い方に相違点とかあるの? イメージできるのがカーネルのエミュレートまでかな…」
@ashigirl96 i386とかx86_64とかあるやん?それぞれ使い方が違う
— しゅーと (@shutingrz) 2014, 7月 30僕「@shutingrz え、え、x86 -> ARMとかってこと?(ありえなくね?」
@ashigirl96 ネットワークのカプセル化を想像してみると、IPv4データ部の中にIPv6ヘッダが入ってるようなもん
— しゅーと (@shutingrz) 2014, 7月 30僕「@shutingrz つまり、仮想的にx86のinstructionをARMにエミュレート(擬似)してるっちゅーことかな? けど、ARMってメモリに直接データぶっこんだりする書き方するし、エミュレートするの大変そう(KONAMI」
@ashigirl96 @shutingrz ご参考まで: https://t.co/Wmpmx3HlVf
— 能登だでぃ子 (@ntddk) 2014, 7月 30@ntddk @ashigirl96 アーありがとうございます あしがるの質問にビクビクしてた
— しゅーと (@shutingrz) 2014, 7月 30
と、僕の質問にすべて答えてくれました。最後には、だでぃ子さんから返事も来てやったぜという感じです。
しゅーとくん、だでぃ子さんありがとうございます。
好奇心旺盛のかわいいあしがるくんの素朴な質問に答えてくれて。
じゃあ、だでぃ子さんにもらったスライド読もうという話です。
・QEMUは動的バイナリ変換できる。
・ユーザーモードエミュレーション/ カーネルモードエミュレーションがある。
-すげぇ…。
じゃあ、そのすげぇDBTはどうやて実現してるんだって話が
・Tiny Code Translationらしいです
・ゲストのコードを逆アセンブルして、中間コードに直してホスト用に直す…
- あまり知らないけど、LLVMと何が違うの?
・unchained blockって何?
・TCGにより Guest Code → Host Codeになる仕組み興奮してきた
・Translation Block
- 分岐命令やページ境界までコードを区切る…ふむ
・コードキャッシュ is 誰?
・そうそう、LLVMっぽい!
・binをLLVMにdiscompileする機能 を S2Eという。
- そこは、 b2Lじゃないの?
・Win binをLLVM bitcodeになおす (bitcode 何?
・あ~、TCGとS2Eは違うDBTなのね。(今更
・LLVM CodeでmappingするとLLVM bitcodeとやらが出てきて、
任意のHost Code(dictonary)とmappingすると実行コード(Exec-c)が出力されると〜。
(すばらしい)
・Dagger IRとはで検索しても英語しか出てこないから、だでぃ子さんに聞いてみよう…
・あと、セマンティックギャップ って何ですか?
- ぐぐったら、
高水準言語の言語要素とこれらを実現するためのコンピュータの機能構造との間には大きな隔りがあること.例えば,配列,データ型,文字列処理,手続き,ブロック構造などを取り扱うには,多数の機械語命令が必要になる.
http://ejje.weblio.jp/content/semantic+gap
って出てきた。
ついでに、bitcodeも調べる
LLVM bitcode
リファレンスも公開されている、LLVMメインの中間言語。
http://nothingcosmos.wiki.fc2.com/wiki/LLVMの中間言語
静的単一代入(SSA Static single assignment)形式である。
大規模な変換(最適化)をやりやすく、低コストで解析、変換を行うことができる。その理由はuse-def連鎖と支配関係の、解析とメンテナンスが容易なため。
ASTで保持していたコンテキストが失われており、プログラミング言語のループ構文が失われている。
パターンマッチがし難い。
うぉお。思ったより詳しい。
そういえば、じりずの誕生日にLLVMのきつねの本買ったの読んでくれたのかな?
MachineInstr
llc内部で使われる、レジスタ割り付けや命令スケジューリング、アセンブラ変換用の中間言語。
3番地および2番地コードの中間言語。アセンブラに変換しやすい。
BitCodeよりも低レイヤー向けであり、1命令ごとの粒度が小さい。
・与えられたコードをビルド。
・セマンティックギャップをQUMEが埋めた(素晴らしい)
☆まとめ
僕「QEMUにDBTがある。DBTがある=LLVMbitcode使う。 LLVMでコンパイルする=マルウェアなどの難読化を解読できる!! QEMUにDBTあってよかった!(感動」
なんというか、本質はGuest Code → Host CodeにTranslationするアルゴリズムの面白さとかだったりするのだと思うのですが、LLVMデコンパイラなどを使うことにより難読化を解読できるというのは、今後、マルウェア解析にとっても非常に役に立つ存在だなと思いました
。学校の後期の研究をSVMを使ったマルウェア判別 IDS/IPSを作りたいと思っていたのですが、LLVMデコンパイラおよびQEMUがあることが今後もっと研究を楽にしてくれるのではと思えました。
☆Reference
仮想化について載っていて面白かった。
http://www.atmarkit.co.jp/ait/articles/0903/12/news120.html
だでぃ子さんが書いてるブログで、動的Taint解析について書かれています。
http://ntddk.hatenablog.com/entry/survey_dta
今日は疲れたので、また読んでブログに書きたいです。
並列プログラミング
目的
もうすぐ、SuperConでスーパーコンピュータで競技するので、すこしでも並列処理について詳しくなって、何が必要かまとめます。ROP chalやりたいんですけど、解法もわかってもう少しっていうところで出来なくて泣きそうなので、少し別のことをしたいと思いました。以前、Geventについても調べていて、それをブログにうpしてたのですが、当時は並列プログラミングにしか興味なくて実際どのような動きをコンピュータの中で動いているかわからなかったため、もう少し調べようと思いました。
内容
1.MPIについて
1-1.並列処理の種類
・単一命令・単一データ流(SISD)
・単一命令・複数データ流(SIMD)
・複数命令・単一データ流(MISD)
・複数命令・複数データ流(MIMD)
種類はたくさんあるが、有名なのは「単一命令・複数データ流(SIMD)である。SIMDとは、一つの命令で同時に複数のデータを処理する概念であります。MPIに基づく並列計算は広い意味でSIMDと…。メモリの使い方でも呼び方に種類があります。共有メモリ型と分散メモリ型。分散メモリ型では各CPUのメモリの中身を参照するために、メッセージを交換する(メッセージ・パッシング)必要があります。それをMPI(Message Passing Inferface)という。
1-2.並列プログラミングのモデル
実際どのような実行方式が行われているかわからないと、誤動作になる可能性が有る。SPMDモデルと、Master/Workerモデルがある。SPMDは、一つの並列プログラムしか存在せず、並列開始したときの並列プログラムがp個分コピーされて実行されます。MPI.ver1というわけです。Makster/Workerモデルは、一般的なモデルです。MasterはWorkerの生成と消去を管理することで、進めます。つまり、Master用とWorker用にプログラムが別れることがあります。
1-3.プログラムの種類
大きく分けて、マルチプロセス(HPF)とマルチスレッドがあります。Pythonでいうmultiprocessingモジュールが前者で、後者はthreadingモジュールが後者です。C言語で後者をPthreadというのをよく使います。僕が以前読んだ LinuxNetworkProgrammingに載っていたはずですプロセスとスレッドの概念について話します。プロセスとは、ソフトウェア上の概念で、CPUはハードウェア上での概念。ハードウェアの機能として1つのOSで1CPUに複数のスレッドを割り当てることを保証する場合、必ず1プロセスだけが1CPUに割り当てられるわけではないということです。すると、複数のMPIプロセスを1CPUに割り当てることができるという認識になります。スレッドとプロセスを混同して使うことでハイブリットMPI実行が可能となります。最近では、GPUも含めて使うことでMPI+X実行状態を可能にしています。GPGPUのことかな…。
1-4. 性能評価指標
並列化効率で、並列効率Ep[%] = Sp/P * 100 (0 <= Ep)となります。100台使って、効果が50倍のときは、並列化効率は50%となります。
アムダールの法則とは、並列処理でとても重要な法則となる。あるプログラムの実行時間をK秒とする。そのうち並列化が可能な割合をα%とする。その結果が図です。
無限大の数のCPUを使っても(p → ∞ )、代数効果はたかだか1/(1-α)ということを示した式です。
1-5.MPI functionの種類
・システム関数
MPIを利用に必須な関数。MPI_Init,MPI_Comm_rank,MPI_Comm_size,MPI_Finalizeなど…。
1対1通信関数
あるプロセスからプロセスへデータを転送する関数。MPIではP2P的関数が基本で非常に重要です。
- ブロッキング型
関数を止めたり、動かしたりする。MPI_Send,MPI_Recvです。
- ノンブロッキング型
通信データの送受信が各々待たずにおやく終わらせて、呼び出し箇所まで戻る方式。通信終了の状態判断は, MPI_Waitが使われます。該当関数に MPI_Isend, MPI_Irecvなどがあります。
この2つはC言語で言うselect.hのことかと思います。
1-6.データ分散方式
並列計算では、配列データをどのように分散メモリに分散させるかというデータ分散が重要になります。1次元データ分散で、行列データの分散と配列データの分散は同じことです。ここから、難しいのですが、MPIの数値計算では、大域的な配列のインデックスから、各ランクが持つ局所的なインデックスを計算して、処理を進める必要があります、また、大域インデックスから、データを所有しているランク番号を知る必要があります。そこで、それらの計算方式をデータ分割方式で表します。
元の配列サイズを N, 元の配列の行インデックス(大域インデックス)を i(global) , MPI実行時の最大ランク数を p とします。データ分割により分散された行列のインデックス(局所インデックス)をj(local)とします。 i(global)を所有しているランク番号を P(iglobal)とします。自分のランク番号を myidとします。
1-7.逐次プログラム→並列プログラム
1.正しく動く逐次プログラムを作る。
2. (1.)のプログラムで、適正なテスト判定をする
3. (2.)のテスト問題の実行について、
適切な処理の単位ごとに、正常動作する計算結果を確認する
4. (1.)を並列化する
5. (2.)のテスト問題をつかって動作検証する
6. (3.)と同じだったかを判定する。
1. 全てのプロセスで、配列サイズは逐次プログラムと同じサイズで良い
2. 各プロセスは、データ分散に基づいく配列の担当範囲のみ計算し、
ループの開始値と終了値を変更する。
3. (2.)の動作を確認する
4. 各プロセスで、データ分散に基づき、
担当するデータ範囲しか配列を確保しないようにする
配列確保に基づき、計算ループの範囲と配列の参照の仕方を変更する
1次元ブロック分散を採用するとしますと、
ib = N / p for j in range(myid*ib, (myid+1)*ib): [ 逐次プログラムと同じ計算式 ]
を、手順4の処理をすると、
for j in range(ib): #jj = j を用いた式 A[jj][...] = ... #データ分散に基づく局所インデックスの参照
1-8. ベクトル計算
y = Ax.という式が行列-ベクトル積であります。
for i in range(n): y[i] = 0.0 for j in n: y[i] += A[i][j]*x[j]
が、ベクトル積となる。
2.Pythonモジュールについて
Pythonには、いくつか並列処理をさせるためのモジュールがあります。今回ボクが使って説明するのは、multiprocessing/Gevent/asyncioの3つなのですが、各々の違いを言いたいと思います。あと、自分の見解だと限界があるので、サイトからの引用と、僕の見解で言及していきたいと思います。間違ってたら怖いので、あとで師匠にも合ってるか聞いてみたいと思います。
multiprocessing
要はプロセス間通信を行うときに便利なパッケージで,threadingと似たようなAPIなのでGILが回避できてマルチプロセッサとかマルチコアの性能を有効に使える...multiprocessingパッケージはローカルとリモートマシンのプロセス並行制御をサポートしています。スレッドの代わりにプロセスを使うことで,GIL(Global Interpreter Lock)が起こす問題を効果的に避けることができます。
Gevent
並行プログラムのコアとなる考え方は、大きいタスクは小さいサブタスクに分割して、 それらを1つずつ、あるいは 同期的に 動かす代わりに、同時に、あるいは 非同期に 動かすことです。 2つのサブタスク間の切り替えは コンテキストスイッチ と呼ばれます。
asyncio
This module provides infrastructure for writing single-threaded concurrent code using coroutines, multiplexing I/O access over sockets and other resources, running network clients and servers, and other related primitives.
どれも同じような関数ばっかりで、わかりやすいといえばわかりやすいのかもしれないです。
もう少し、Pythonモジュールについて書こうかと思ったんですが、
少し知識不足がすぎるので、もう少し蓄えてから、Part2を書きたいと思います。
考察
詰まるところ、並列処理には割りと種類があるが、厳選?された中でMPIが強いと。そのMPIのプログラミングを学ぼうという感じです。ここまでは理論が割りと簡単。難しいというのは別に、関数の多さとその概念を理解するのに時間がかかるということです。言ってしまえば、時間さえ多少取れれば、MPIにしてもPythonのモジュールの理解にしてもわかると思います。「効率の良いメッセージパッシング」というのが、並列プログラミングの課題だと思うのですが、実のところそこはまだ理解が浅いので、「並行コンピューティング技法」など読んで、バブルソートなどの、一般的に使われているアルゴリズムから勉強しようかと思います。。
感想
〇〇に精通した人、というのは大抵低レイヤを専攻しているというのが私のイメージで、僕もいつかはそういう人になりたいなと思っていたのですが、どのようにしたら成れるのかもわからないですし、とりあえず、並列処理から始めるのもいいかなと思いました。楽しかったです。Part2もがんばって書きます。
セキュリティ・キャンプのチューター受かった、よかった。
パソコン触り始めて早2年経って、ようやくチューターになれたかという気持ちです。
精進します。
テスト終わったら…
目標&やりたいこと
僕みたいなやりたいことが分散する人間は、とりあえずやりたいことを
ばーって書いて、そのあとに後付のように体系化すれば良いはず。
1.数学&アルゴリズム
2.Web関連(特にクライアント周り)
- CoffeeScript
- jQuery
- AngularJS
- D3.js
- Ruby on Rails
- 本当にやりたいのは)Flask
3.制御システム&組み込みセキュリティ
- Fuzzing
- Exploit
今一番やりたいのが、数学(&アルゴリズム)。
結局プログラマって「プログラミング(文系)」ができるのって
正直頭の良さに関係無いような気がして。
つまり、数学脳をプログラミングに活かすことが出来たら、最強じゃん?
っていう中二病精神の元頑張る所存。
機械学習というより、自然言語処理の部分はWebサイトで活かしてみたいと思ってる。
あと、愚直なプログラミングよりカッコイイ書き方を勉強したいし、
高速化を図るようなプログラミングを勉強したい。
次にやらなきゃいけないし、凄く楽しみにしてるのがWeb。
今まで偏見ばっかりで触りたくなかったWebが今では大好き。
特に、Flaskでサイト作ってるときは時間を忘れる。
(けど、まだ静的なサイトしか創れないんだよな〜)
つまり、必要なのはjs(coffee)なので、門をくぐるつもり。
Railsはルールが多すぎて自由度がないしすきじゃないけど、
やるしかないよねって感じ(使命感)
制御システムセキュリティは今のところ置いておこうと考えてる。
そりゃあ面白そうな記事見つけたら見るけど、自主的にやる必要もないかなと。
(なにより実験するためのお金がないし)
お金がないんだったら仕方がない。大人に頼るか、諦めるか。
後者っすね。はい。
まとめ
これでも、割りと絞った方。
数学に関しては、同じクラスの友達に影響されてる。
その子は、プログラミングもできるし、数学もできるからスゴイ知的。
alcさんとかもそういうイメージだし、きゅうりさんもそんな感じ。
もっと、プログラミングを楽しむには数学が必要なのかもしれない。
【非技術】国語の宿題(テーマ自由)
タレント、及びアイドルについて
近年、日本や世界に「タレント」「アイドル」と呼ばれている職業がある。そして、その数は増えていき、誰がなれて、誰がなれないかわからない状態に有るほどだ。それが良いことなのか、はたまた問題として懸念するべきなのか。
そして、彼らが逡巡することもなく「私達、俺達はアイドルだ」ということに対しての善悪を考える。
そもそも、タレントの定義は、テレビやラジオなどのマスメディアに職業として出演する芸能人などの総称である。
タレントの種類としては、お笑いタレント、タレント政治家、コメンテイターなどなど。では、タレントの本来の意味は、古代の通貨単位で、才能、能力を指している。
つまり、タレントとは才能や人より特化した能力がある人を指す言葉であると考える。
よって、この現代で誰でもがタレントになれるということに首肯できないというわけである。
「アイドル」の本来の意味と現在使われている意味を照らしあわせて考えてみる。
世の中でアイドルとは、魅力的で可愛い人物を指す。また、そのアイドルの種類にはアイドル歌手、巨乳アイドル、グラビアアイドルなどがある。
しかし、本来の意味は「偶像」である。つまり、アイドルは偶像のように崇められるようなほど可愛くてはならないと考える。
しかし、世間で見られる自称アイドルは、一瞥する程度なら中途半端に可愛い、よく見たらブス、めちゃくちゃ可愛いなどカテゴライズ出来て、保全するにも限界があるような顔をしている者もいる。
ついには、「可愛くないけど、やさしい」など、精神面を美化して虚飾することで擁護するファンまでいる。
婉曲的な言い方をせずに言うと、これらは間違っていると考えている。
なぜなら、「タレント」に関しても「アイドル」に関しても元々の意味から離れていき、言葉の定義が揺らぎつつあるからである。
そんな脆弱な状態では今すぐにも瓦解してしまうと考えていて、私達一人ひとりが如実を諦観する必要があると考えてる。
あとがき
実はもっと書きたがったが、制限が800文字だったので、書くのをやめた。いや、書くのをやめた時には1200文字ぐらい言ってたので、死ぬ思いで400字削った。
【久々ぎじゅつ 】キャンバン in Osaka
【はじめに】
セキュリティ・キャンプのお話をするキャンバン。
キャンバンが何の略可分からないけど、今日ありました〜。
今回はセキュリティでもネットワークのセキュリティについて
みなさんがお話してくれるので非常に楽しみ…。
リアルタイムでブログ書いてるので、日本語がおかしいかも
(いやそれ元から)
【園田さん - 通信パケット】
園田さんは、ネットワークパケットやTCP/UDPに対するスキャンについて解説をしてる。
Wireshark…。
TCP通信がどのようにWiresharkで見えるか、どうか。
telnetの見ちゃダメ!っていうパケットを見てる…。
攻撃したらSSLの通信が見えちゃう(平文)。
>パケットの中からアセンブリのソースが…<
>start msblast.exe
レアなパケットを集めているサイトが有る
-> ここ。OPSFのパケットもある。
Packet Analysis 2011 Chaenges
3問ぐらいあって、そこから問題を解いていく。
DEFCON 18 -- Packet Madness 200
These folks seak a different language. Join their site and translate the key for us.
の解説を園田さんがする…(?)
Chris Sandersさんがパケットの本以外に面白いパケットをまとめている
Wiresharkがsampleのパケットを公開している.
ここで、園田さんからジェームズさんにバトンタッチ。
【ジェームズさん -- パケット工作から学ぶNWSec】
セキュリティ・キャンプで使ったスライドを使っているので、
うーんって感じかと思ったけど、がんばります。
あのときしゅーとくんと「あれな」って感じで見てます。
バイナリのパケットを16進数にした場合、0806が書かれていたらそれはARP
0800はIPアドレス…2つが一つのパケットに書かれていたら、
つまり ARP/IPということがわかる。。
%iptables -P INPUT DROP
【殿様ぁあああ -- パケット偽装】
・通信プロトコル - 「人が決めたこと」
・孫子の兵法
- 人より早めに攻撃(?)
【悪い例】電話
悪人A 善人B
もしもし?オレオレ
----------->
はいはい、たかし?
<----------
たかしだけど〜
------------>
どうしたの、たかし
<------------
みたいなことをプロトコル上でする。
偽装通信の定義:
1.情報を転送しているように見えない
2.リソースのステータスが入るべき値に任意の値を入れて送る
3.リソースの配置ポリシーと、管理実装の結果を…(ぷつん
実際の偽装通信は?
・もうちょっと多様化している
- レイヤも関係なし
- Proxy も関係なし
・正常な通信しか見えないようにしている
- Bot や標的型攻撃などにも使われている
最近の攻撃では、ZeusBotやSpyEyeなどが使われている。
独自のプロトコルで、違うところに送っているように見て、偽装していることもある。
偽装のアプローチ
・本来「通信データとして使われている」と意図されないところに「任意の」
データを配置する - 今回のメイン
・データを受信する他意タイミングを符号化する
- ばれない通信路
- 「これ?」っていう通信路
を攻撃者目線から見つけることが重要。
TCPペイロードに隠す
- GNU httptunnnel
- HTTPTunnel@JUMPERZ_NET
ICMPペイロード
GNU httptunnel
- Cで書かれたトンネルプログラム
- HTTPトラフィックに、別の通信内容を載せる
- hts (サーバ)とhtc(クライアント)がHTTP
HTTPのトンネル
ICMPペイロード
・Tunnel Shell
- ICMP パケットを使って、シェルイン…(ぷつん)
そろそろ、スライド発表会があるのでやばい…(Scapy)
【はじめに】
そろそろ、とある3箇所でScapyを使ったファジングについて
発表しなきゃいけないので、今から頑張ろうと思います。
いや最近ずっとWebやってたので、、(言い訳
【メソッド】
1.プロトコルの内容を見る
2.類似したプロトコルがScapyでどういう関数が使われてて、どのように書かれてるか見る
3.実際書いてみる
をやってみよう…
【内容】
とりあえず、ブログに学んだ内容ぶち込んでいこうと思います。
プロトコルはDNP3.0とHARTっていうのが面白そうですが、
今回はDNP3.0に挑戦したいと思います。
【プロトコルの内容を見る】目標時間120分
このサイトを参考にしたいと思います。
えっと…プロトコルの中身が全部載ってるサイトずっと探してるのに
全く見つからない…ヤバイ
まぁいいや
1時間ぐらい、DNSとDNP3.0を見比べてるんですが、
うーんっていう感じですね…。
class DNS(Packet): name = "DNS" fields_desc = [ ShortField("id",0), BitField("qr",0, 1), BitEnumField("opcode", 0, 4, {0:"QUERY",1:"IQUERY",2:"STATUS"}), BitField("aa", 0, 1), BitField("tc", 0, 1), BitField("rd", 0, 1), BitField("ra", 0 ,1), BitField("z", 0, 3), BitEnumField("rcode", 0, 4, {0:"ok", 1:"format-error", 2:"server-failure", 3:"name-error", 4:"not-implemented", 5:"refused"}), DNSRRCountField("qdcount", None, "qd"), DNSRRCountField("ancount", None, "an"), DNSRRCountField("nscount", None, "ns"), DNSRRCountField("arcount", None, "ar"), DNSQRField("qd", "qdcount"), DNSRRField("an", "ancount"), DNSRRField("ns", "nscount"), DNSRRField("ar", "arcount",0) ] def answers(self, other): return (isinstance(other, DNS) and self.id == other.id and self.qr == 1 and other.qr == 0) def mysummary(self): type = ["Qry","Ans"][self.qr] name = "" if self.qr: type = "Ans" if self.ancount > 0 and isinstance(self.an, DNSRR): name = ' "%s"' % self.an.rdata else: type = "Qry" if self.qdcount > 0 and isinstance(self.qd, DNSQR): name = ' "%s"' % self.qd.qname return 'DNS %s%s ' % (type, name) dnstypes = { 0:"ANY", 255:"ALL", 1:"A", 2:"NS", 3:"MD", 4:"MD", 5:"CNAME", 6:"SOA", 7: "MB", 8:"MG", 9:"MR",10:"NULL",11:"WKS",12:"PTR",13:"HINFO",14:"MINFO",15:"MX",16:"TXT", 17:"RP",18:"AFSDB",28:"AAAA", 33:"SRV",38:"A6",39:"DNAME"} dnsqtypes = {251:"IXFR",252:"AXFR",253:"MAILB",254:"MAILA",255:"ALL"} dnsqtypes.update(dnstypes) dnsclasses = {1: 'IN', 2: 'CS', 3: 'CH', 4: 'HS', 255: 'ANY'} class DNSQR(Packet): name = "DNS Question Record" show_indent=0 fields_desc = [ DNSStrField("qname",""), ShortEnumField("qtype", 1, dnsqtypes), ShortEnumField("qclass", 1, dnsclasses) ] class DNSRR(Packet): name = "DNS Resource Record" show_indent=0 fields_desc = [ DNSStrField("rrname",""), ShortEnumField("type", 1, dnstypes), ShortEnumField("rclass", 1, dnsclasses), IntField("ttl", 0), RDLenField("rdlen"), RDataField("rdata", "", length_from=lambda pkt:pkt.rdlen) ] bind_layers( UDP, DNS, dport=53) bind_layers( UDP, DNS, sport=53)
をみて、なんで、わざわざ3つに分ける必要があるんだ…ってことで、
しゅーとくんに聞いてみました。(返事待ち)
DNSってメッセージヘッダ、質問欄?、リソースレコードって分かれてるじゃないですか? 要は、DNSには3つのプロトコルが存在するってことですか? Scapyは、3つのプロトコルに分けてるんですけど、実際のDNSの概念自体、3つに分けてるんですか?
眠くて日本語のゲシュタルト崩壊も起こってるけど、仕方ないし、
わかってもらうしかない。これは。
辛くなったので、
Scapyのサイトを参考にすることにしました…
本当は自分だけでやりたかったんですけどね、、
予定変更
【Adding Protocol黙読】目標時間120分
def vlenq2str(l): s = [] s.append( hex(l & 0x7F) ) l = l >> 7 while l>0: s.append( hex(0x80 | (l & 0x7F) ) ) l = l >> 7 s.reverse() return "".join(map( lambda(x) : chr(int(x, 16)) , s)) def str2vlenq(s=""): i = l = 0 while i<len(s) and ord(s[i]) & 0x80: l = l << 7 l = l + (ord(s[i]) & 0x7F) i = i + 1 if i == len(s): warning("Broken vlenq: no ending byte") l = l << 7 l = l + (ord(s[i]) & 0x7F) return s[i+1:], 1
ココらへんで撃沈。
何言ってるかわからん。
それまでは9割分かりました。
2時間どころか、40分も読んでない気がする…難しい。
〜寝る(明日続き書きます)〜
Rubyよくわからないけど、多分Railsできる👊
【はじめに】
Railsやらないといけなくなったので頑張ります
理由は2つあって、一つは秘密☆
もう一つはプロコンで、とあるデバイスを制御するためにプロットフォームを
ある程度広い範囲で使えるようにしたいからWebがいいなってなりました。
【環境】
学校のサーバ(さくらサーバ)を使います。
中身は多分CentOSです。
【参考サイト】
ドットインスコール
小学生でもわかるRuby on Rails
をやろうと思います。Rubyあまりわからないんですけど、Railsと一緒に覚えていけたら
いいかなーっていう軽い気持ちでやります。
【重要なコマンド】
% rails g model Project title % rake db:migrate irb(main):002:0> p = Project.new(title: "New one") => #<Project id: nil, title: "New one", created_at: nil, updated_at: nil> irb(main):003:0> p.save % rails g controller Projects % vim config/routes.rb 1 Taskapp::Application.routes.draw do↲ 2 resources :projects↲ % rake routes Prefix Verb URI Pattern Controller#Action projects GET /projects(.:format) projects#index POST /projects(.:format) projects#create new_project GET /projects/new(.:format) projects#new edit_project GET /projects/:id/edit(.:format) projects#edit project GET /projects/:id(.:format) projects#show PATCH /projects/:id(.:format) projects#update PUT /projects/:id(.:format) projects#update DELETE /projects/:id(.:format) projects#destroy
**app/controllers/projects_controller.rb**
class ProjectsController < ApplicationController def index @projects = Project.all end end
**app/views/projects/index.html.erb **
<h1>Projects</h1> <ul> <% @projects.each do |project| %> <li><%= project.title%> </li> <% end %> </ul>
を上手く書くのが難しい…
ていうか、この人、ProjectとProjectsを書きすぎてどれがどれを参照してるか
わからないし、教えるの下手くそ(無茶苦茶
@projects = Project.all<%= project.title%>
ってこれまた違うし…
www....3000/projects
のprojectsが
app/views/projects/index.html.erb
のことね。
Projectってなに?
えっと、
rails g controller users index show
ってすることで、
app/controllers/users_controller.rb
app/views/users/index.html.erb
app/views/users/show.html.erb
っていうのが自動的に生成される
【非技術】今日の出来事
【日記】
友達と別れて1人で帰ってる途中、お爺さんが仰向けに倒れてて、
そのお爺さんの上に自転車が乗っかってる状態なのを見つけて、
やべぇやべぇ!ってなって自転車止めて、お爺さんに乗っかってる自転車どけて
「大丈夫ですか!!」って言って心臓が動いてるか否かの確認したら動いていたので、すぐさま救急車を呼ぼうとしました。
けど、「あっ充電ないわ(白目)」ってなったので、
走ってる車を
止めようとして色々やったのですが、5,6人ぐらいみんな無視して走っていきました。割りとキレそうになったんですけど、我慢して倒れてるお爺さんの前にある家に駆けつけてインターホン押そうとしたら普通におばあさんが窓からボケーっと見てて、「早く救急車呼んで下さい!」って叫んだら、「えぇ…」みたいなこと言われて渋々電話していったのを見ました。
(こいつらなんでこんな消極的なんだ…)
って思いながらお爺さんにずっと「大丈夫ですか」って言い続けたら5分ぐらいで
救急車が来て、ぱっと運ばれていきました。(気絶してるだけだったらしいので安心しました)
そのあとおばあさんが降りてきて「いやぁ、第一人者だと疑われるからねぇ、息子にも第一人者にはなるなよって言われてるのよ」って言われたのが印象的でした。
【感想】
僕が行動したのは正義感とかそんな徳が高いものじゃなくて、反射でした。
熱いものに触ったら「あちっ」っつって手を離すのと同じぐらいに
倒れてるヒト見つけたら近寄るものだと思ってたのに、
関わった人が、たった少しの時間だったり、面倒くささだったりなんかの言い訳で
行動しなかったのがすげぇなーって思いました。
一番気になるのが、倒れてるのに誰も近づいて来なかったときのお爺さんの気持ちですね。
続き
これ重要やね