Subscribe: 兼雑記
http://d.hatena.ne.jp/shinichiro_h/rss
Added By: Feedage Forager Feedage Grade B rated
Language: Japanese
Tags:
Rate this Feed
Rate this feedRate this feedRate this feedRate this feedRate this feed
Rate this feed 1 starRate this feed 2 starRate this feed 3 starRate this feed 4 starRate this feed 5 star

Comments (0)

Feed Details and Statistics Feed Statistics
Preview: 兼雑記

兼雑記





Updated: 2018-01-15T23:11:53+09:00

 



お天気プロコンと圧縮アルゴリズムについて

2018-01-16T13:51:15+09:00

https://beta.atcoder.jp/contests/wn2017_1/standingsむっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。今回…https://beta.atcoder.jp/contests/wn2017_1/standingsむっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測したものなので、互いに相関があり、相関を利用しない普通の画像圧縮だけでは上位の成績にはなかなか追いつかないと思っています(後述しますが汎用画像圧縮で7位は取れていたと思います)。 次のピクセルを予測する 圧縮についてある程度の知識があれば、色んな情報から次のピクセルの値を予測して、当然予測は外れるので外れた分についてエントロピー符号、という方法を考えるかと思います。エントロピー符号はデータに偏りがあればあるほど圧縮率が上がるため、問題のドメインについての知識を利用して、データを偏らせることができれば圧縮率が高くなります。例えば、普通の画像は一般的に直前のピクセルと近い値を持っていると考えられるので、直前のピクセルと次のピクセルの差分を保存すれば値が0に近い値に偏るので良いのです。すぐ左のピクセルだけでなく、左と真上のピクセルの平均値であるとか、付近のピクセルを適当なわりあいで混ぜた数値であるとか、予測の精度を上げる方法は色々と考えられます。今回の問題の場合、同じ波長を別の時間に観測した画像や、同じ時間に違う波長を観測した画像からもパラメータを拾ってくることができて、さらにこの予測の精度を上げることができます。これは、パラメータが複数あって一つの値を推定するので、普通にある種の機械学習と言えます。私が使った方法は、参照画像からピクセルの値を推定して、その推定した値がさらにどれだけ現実とずれているかということを近傍のピクセルから推定する、という方法と、参照画像と近傍の両方からピクセルを推定する、という両方のアプローチを、かつ色んな参照画像に対してやってみて良かったやつ、という方法です。機械学習で忌み嫌われていると思っている ensemble 的な話です。本当は一気に推定する方法だけで行きたかったのですが、一[...]



Deep Learning Acceleration 勉強会

2017-09-10T08:40:19+09:00

https://connpass.com/event/64632/すごく面白かった。最近こういう会に行って感心することは多いのだけど、しかしなんか書きたいと思うレベルになかなか来ない、まあそれなりに年喰ったしな、とか思ってたんですが。低レイヤとか、自分がある程度既に知ってるところの話を聞くのも楽しいけど、自分が最近勉強してて理解しはじめたことの話を見聞きする方が楽しいよねえということかと思いました。まさににわかほど語りたがる現象で、実際懇親会とかで間違ってること結構言ってそうな気がする。ジャンルとして、他のCSのジャンルとかと違って、深層学習はとにかく論理的に確定できない話が多くて、あの論文は…https://connpass.com/event/64632/すごく面白かった。最近こういう会に行って感心することは多いのだけど、しかしなんか書きたいと思うレベルになかなか来ない、まあそれなりに年喰ったしな、とか思ってたんですが。低レイヤとか、自分がある程度既に知ってるところの話を聞くのも楽しいけど、自分が最近勉強してて理解しはじめたことの話を見聞きする方が楽しいよねえということかと思いました。まさににわかほど語りたがる現象で、実際懇親会とかで間違ってること結構言ってそうな気がする。ジャンルとして、他のCSのジャンルとかと違って、深層学習はとにかく論理的に確定できない話が多くて、あの論文はあやしいなあ、あれは説得力あるなあ、というような、口コミベースの情報が回してる面が、良くも悪くもあるのかなあ、という印象を持っています。つーわけで口コミレベルの適当なことを、以下、書きます。(定型句)間違ってることが普通にいっぱいあると思います。(定型句)所属企業とは関係なく勝手に書いてます。定型句と書いたけどグーグルとしての感想では本当にないです。ちなみに僕はRNNしかいじったことないです モデルアーキテクチャ観点からの高速化 僕はこれとても興味があったドメインだったので、早速すごい俺得と思いながら聞いてました。 factorization, squeeze, pruning とかの話の一部は自分でも試したことがあったのですが、自分のやった範囲ではうまくいかなかったという感想です。僕なりの考えを箇条書きにすると このジャンル、まずトレードオフを明確にするべき(こういうのはハードウェアとかの人の方が得意であると思う) 少なくとも、クォリティ、学習スループット、推論レイテンシ、の3値があることは考えるべきで、どれか1つを狙うアプローチを他と混同すべきでない もちろん上記3つ以外にもいろいろ考えることがある。例えばパラメータサイズは学習推論両方のメモリ使用量に効く、とか あとこの発表はメインのターゲットはCNNだったと思う。CNNは正直よく知らないので間違ってたらホントすいません conv WxH を factorization で別のに落とす、てのは意味的に別モデルを作ってる感があって、他のFCやらRNNでやるfactorizationは同じモデルだと思う RNNだとfactorizationは悪くなるという印象。パラメータの数も減るし学習も早くなるのだけど、少なくともRNNだとembeddingの後の次元はほぼ完全に自由に決められるので全体の次元を落とすことは簡単で、それで同じパラメータ数で比べると余計なことしない方が計算量的に有利だった なんかこの手の論文見てると正直、単にデータに対してパラメータ数過剰な状況で学習したモデルをベースライ[...]



10年ほど後のBinary Hacks

2017-05-29T22:32:29+09:00

https://twitter.com/nalsh/status/869086098177146881を見て、今ならどういうネタが書かれるかなぁとざっくり考えてみます。 perf @nlashさんに指摘されていた通り、perfは重要だと思うんですが、書かれていたperf_event_openはptraceなんか目じゃないくらい使いこなしがムズいと思うので、素直にperfそのまま使えって感が強い気がします ptrace PTRACE_SYSCALL以外はあまり変わってないと思うんですが、PTRACE_SYSCALLはPTRACE_O_TRACESECCOMPでやるとずいぶん速くなるのでオトク a…

https://twitter.com/nalsh/status/869086098177146881

を見て、今ならどういうネタが書かれるかなぁとざっくり考えてみます。

perf

@nlashさんに指摘されていた通り、perfは重要だと思うんですが、書かれていたperf_event_openはptraceなんか目じゃないくらい使いこなしがムズいと思うので、素直にperfそのまま使えって感が強い気がします

ptrace

PTRACE_SYSCALL以外はあまり変わってないと思うんですが、PTRACE_SYSCALLはPTRACE_O_TRACESECCOMPでやるとずいぶん速くなるのでオトク

asan/tsan

valgrindのbinary translationでのinstrumentationてのはカッコいいけど、普通に考えるとコンパイラに手を入れる方が常識的ですよね……という

ELF

特に変わりが無い気がする

DWARF

よく知らないけど割と変わってて、-gsplit-dwarfとか-gzあたりは知っててもいい気がします

セキュリティまわり

mitigationは気休めなんで、ちゃんと2レイヤ以上セキュリティ機能使いましょう的な

angrとかqiraとか

CTF/セキュリティ系の人が作ったツールは色々面白そうだけどあまり知らない

glibcのrandomization

そういえば気がついたらプロセス内の関数ポインタ全部ランダマイズされるようになってたけど、たぶんここ10年な気がします

inotify

便利だと思う。特にinotifywaitコマンドが……fanotifyが何が違うかは忘れました

madvise

元々書いてなかった気がするとふと思い出しました

コンテナ

コンテナベースの仮想化とかは色々ありすぎて。cloneのオプションとかすごく増えた気がするけど、今見るとそうでもないか

x86の命令

_mm_cmpXstrYは使いどころ多いし使いやすいし良いものだという気がします。あとまぁAVXとかTSXとか?

ARMの命令

スマホの台頭を考えるとARMについてもなんか。thumbとか。

Android/iOS

スマホという意味ではこのへんで違うところとかも。これらだとglibcのローダと違って名前空間がフラットじゃないとか

まとめ

なんか結構あるなということと、最近知識がアップデートされてないから知らないだけで面白いことが起きていることがまだまだありそうだなぁということを思いました




Very symmetric JavaScript code

2017-04-30T19:53:49+09:00

だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.htmlコード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントで…

だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。

デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.html

コード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric

普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントですっとばすのがパズルという感じでした。何も考えずに実行するコードの最後に /* と入れただけだと、180度回転した部分に */ が現れてしまってコメントが終わってしまうという。




drdr

2017-02-19T23:08:21+09:00

オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。 thread pool Tensorflow make Digdag 閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまと…オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。 thread pool Tensorflow make Digdag 閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまとめて実行、終わったら結果を集計、みたいなことをしたりすることが最近多いです。1週間から1ヶ月ほど10回とか100回使うんだけど、でもそのうち捨てる系のコード。私の場合、よくやる解決と問題点は shell script で並列化したいところはバックグラウンド実行+waitで散らして、最後の部分は ruby かなんかで書く: shell script と ruby の2つを管理するのがうっとうしい。多少ややこしいパイプラインを作るの大変 ruby かなんかでスレッドプール作ってやる: 分散部分のコードがめんどくさい。多少ややこしいパイプラインを作るのがかなりめんどくさい make を使う: 動作は理想的なことが多いけど、コードがめんどくさくて、あと宣言的な記述になって、シーケンシャルな記述じゃなくなるので、読みにくく編集しにくい 欲しいことを考えると CPU並列は無くても良い パフォーマンスは最適でなくて良い コマンドが手軽に実行できると良い コマンドが失敗したら即座に止まると良い shell はミスりやすいから嫌だ 処理の後半部分のやりなおしとかのためにチェックポイントを仕込めると良い で、まあなんか作りはじめてみましたというのがこれ。https://github.com/shinh/drdr/あまり良い例が思いつかなかったのですが、自分のスライドのディレクトリにあるスライド全部に対して、それぞれページ数を集計するサンプルがこんな感じ。 URL = "http://shinh.skr.jp/slide/" drdr { # スライド一覧のところを読んできて、 list.ckpt に保存しておく # これ以降のスクリプトに書き損じがあっても、再度ネットワークアクセスは発生しない cmd("curl #{URL}", ckpt: 'list.ckpt') | task{|l| # ここから list.ckpt に依存した処理で、 Apache の directory index を適当にパース l.scan(/href="([a-z].*?)\/"/).map do |m| name = m[0] # スライドのページ数を適当に取ってくる。このコマンド実行は並列に走る cmd("curl #{URL}#{name}/ 2> /dev/null") | task{|l| last_page = 0 l.scan(/(\d+)\.html/) do last_page = [$1.to_i, last_page].max end[...]



tanlog

2017-02-12T03:12:07+09:00

最近、 tanlog というのを作って使っていて、割と便利なので紹介してみます。https://github.com/shinh/test/blob/master/tanlog.rb元々は同僚と、なんか端末に出たもの前もって lv とか tee に入れておくのって、忘れることあるし、 lv とか tee に流すと isatty が false になって色出ないのうざいよねえ…みたいな話をしてたように思います。 grep については fake_isatty とか作ったりしたんですが、この時 soda さんに仮想端末作ってやる方法があると教えてもらったのを思い出して、 script とかで記録して…

最近、 tanlog というのを作って使っていて、割と便利なので紹介してみます。

https://github.com/shinh/test/blob/master/tanlog.rb

元々は同僚と、なんか端末に出たもの前もって lv とか tee に入れておくのって、忘れることあるし、 lv とか tee に流すと isatty が false になって色出ないのうざいよねえ…みたいな話をしてたように思います。 grep については fake_isatty とか作ったりしたんですが、この時 soda さんに仮想端末作ってやる方法があると教えてもらったのを思い出して、 script とかで記録しておいたら…とか話していました。

結果、その同僚は zenlog というのを作って便利になった、とか言ってたのですが、なんか Perlbash 混じってるとか、コマンドの切れ目をプロンプトで教えるとか微妙…ということで自作したものです。 zenlog に対して tanlog なのはコマンド起動ごとになんかするからです。まあこういうのは人の作ったものを使うというよりはみんな勝手に作ればいい…

tanlog は screen/zsh と一緒に使うことが想定されていて、 preexec で tanlog start して precmd で tanlog end します。 tanlog start は screen のログファイルを指定して /tmp/tanlog/RAW の下に端末出力をダンプしはじめます。 tanlog end はその端末出力を綺麗にして /tmp/tanlog の下にコピーします。

このディレクトリの構造は適当に便利なようになっていて、

などと適当に便利そうなものが入っています。えーと llvm ビルドした時の cmake コマンドはどんな感じだったかな…とか思ったなら

wgrep llvm /tmp/tanlog/cmake/P*

なんてやってます。 wgrep てのは grep を w3m でラップした何かです。

あとは tanlog paths てすると最近実行したコマンドに含まれるパスとかURLぽいものがだーと出るので、それを w3m に喰わせる wl ていうのも使ったりしてます。コマンドが URL 出してくれたけど、それマウスとか screen とかでコピペするのめんどい、て時に使ってます。

https://github.com/shinh/test/blob/master/wl

そのまま他の人が使えるような形にはなってないと思いますが、 screen のログ機能なり script なり使って、とりあえずコマンドの実行結果を全部残しておく、てのはなかなか良いのではないかと思っています。 lv か tee 通すべきかな?とか一瞬逡巡するのが無くなります。実現がハッキーになりすぎるのが残念なところで、こういうことを色々便利にやってくれる screen つき shell みたいなの作りたいなぁとかいうことを割とずっと思っています。




ELVM Compiler Infrastructure について

2016-12-22T00:57:06+09:00

はじめに 言語実装 Advent Calendar 2016 用です。ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよ… はじめに 言語実装 Advent Calendar 2016 用です。ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよーということを書こうかと思っていました。しかし、ありがたいことにそういう趣旨だったり、あるいはもっと難しいターゲットについても、既にあれこれと書いていただいたのでした。例えば Perl: http://qiita.com/mackee_w/items/5397d6b9215f41c41db1 Tex: http://hak7a3.hatenablog.com/entry/2016/11/13/153418 Tex: http://hak7a3.hatenablog.com/entry/2016/12/03/124632 Vim: http://rhysd.hatenablog.com/entry/2016/12/02/030511 C++ (constexpr): http://kw-udon.hatenablog.com/entry/2016/12/03/201722 Unlambda: http://irori.hatenablog.com/entry/elvm-unlambda-part1 など。上のリストは、おおざっぱに、上の方に簡単な雰囲気をつかむのに向いてそうな記事、下の方に謎テクニックを楽しむのに向いてそうな記事を並べてみました。いずれにせよ、こういう記事は中身をよく把握してる私自身より、試行錯誤していただいた他の人達が書いた方がわかりやすいでしょう……ということでなんか違うことを書いてみます。具体的にはどういうふうに作業を進めたりした…てことを雑に書いていこうかと。技術的な概要は一つ前のこのポストとそこからリンクされてるスライドに書いたので、そっちを参照してください。http://shinh.hatenablog.com/entry/2016/10/18/095437 sedlisp, beflisp, makelisp, bflisp 色々あって、Esolangですごく簡単なLisp処理系を書く、というのがマイブームになったことがありました。 GNU sed と GNU make は完全手書きでした。sedlisp を書いた時から、 @rui314 さんは「手書きじゃなくて中間層を介して変換した方が良いのではないか」と言っていたのですが、 sed や make だと、計算モデルが違いすぎるので直接書く方がラクかなということと、結果できたものが遅くなりすぎそうだったので、直接書きました。ですが、 Befunge の時はなにか中間に入れないとキツいと感じたので、 LLVM bitcode から雑に変換する、という方法でやりました。といっても、 LLVM bitcode は任意のものを許すわけではなく、変換器がサポートしてる命令しか吐かないように注意深く[...]



ELVM Compiler Infrastructure

2016-10-18T09:55:02+09:00

最近作ってたオモチャがだいたいまとまってきました。https://github.com/shinh/elvm第12回 kernel/vm 勉強会で発表した時のスライド:http://shinh.skr.jp/slide/elvm/000.htmlこれは何かというと、前作った bflisp を改良したり整理したりしたもので、 C 言語をシンプルな中間言語 (EIR) に変換する改造 8cc と、その中間言語を Brainfuck をはじめとした他言語に変換するバックエンドから成り立っています。 bflisp との差分は、 Brainfuck 以外のバックエンドを追加しやすくしたり、バックエンドを…

最近作ってたオモチャがだいたいまとまってきました。

https://github.com/shinh/elvm

第12回 kernel/vm 勉強会で発表した時のスライド:

http://shinh.skr.jp/slide/elvm/000.html

これは何かというと、前作った bflisp を改良したり整理したりしたもので、 C 言語をシンプルな中間言語 (EIR) に変換する改造 8cc と、その中間言語Brainfuck をはじめとした他言語に変換するバックエンドから成り立っています。 bflisp との差分は、 Brainfuck 以外のバックエンドを追加しやすくしたり、バックエンドを C で書いて、完全に Brainfuck だけで 8cc.bf を再現することができるようにしたり、という感じです。

特に興味深いであろうバックエンドとしては、 Brainfuck, Unlambda (id:irori さん作), Piet, C-INTERCAL, Befunge, Whitespace などがあります。例えば Lisp を Piet で動かしたりもできるようになりました。 lisp.pnggimp で開いてスクリーンショットを撮ったこの画像なんかは結構お気にいりです。

(image)

JavaScript に変換することもできるので、デモサイトは ELVM を使って作った JS で作られています。

http://shinh.skr.jp/elvm/8cc.html

スライドにも書きましたが、「チューリング完全な言語互いに等価だからうんぬん…」というような、理論ではそうなんだけど…というようなことが実際確認されるのを見るのはなかなか楽しかったです。コンパイラいじり、 esolangs での計算プリミティブ作成パズル、最小限の libc 作り、など好きなトピックがたくさんあるという意味でも楽しくて良かったです。




Brainfuck interpreter in Ruby's Regexp

2016-10-17T12:07:56+09:00

Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rbつまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを BF_REG =~ bf + BF_SUFFIX で実行することができます。出力は $~['o0'], $~['o1'], ... …

Ruby正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。

https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb

つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを

BF_REG =~ bf + BF_SUFFIX

で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、

output = ''
256.times do |i|
 o = $~["o#{i}"]
 break if !o
 output += o
end

的なコードで取り出すことができます。入力は ! の後に続いてる文字列を入力とする形式。Ruby正規表現は Turing 完全でないので、無限ループはできないようになっています。

仕様の一覧を並べると

  • 8bit Brainfuck
  • 入力の終端は -1
  • メモリは255番地まで
  • 出力文字数は256まで
  • 入力文字数は256まで
  • Brainfuck命令以外の文字があると正規表現がマッチに失敗する
  • 無限ループがあると正規表現がマッチに失敗する(正確には1つのループが256回連続回ったら止まるという仕様なので、本当は止まるコードもマッチ失敗することがありえます)

など。256まで、という制限は実装をラクにするためなので、本質的な制限ではないです、が無限にはできないです(入力文字数は無限にできるかも?)。この程度の制限があっても十分に実用的(?)で、例えば cal.bf も動いています。

$ echo 2016 10 | time ruby bf.rb cal.bf
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
ruby bf.rb cal.bf  1147.54s user 0.26s system 99% cpu 19:07.91 total

ただすごく遅くて、 cal.bf の実行に19分とかかかってました。1命令10msとかその程度だと思います。 + とか - が実に遅い。

こんなことできるとはつい最近まで思ってなかったのですが、 HITCON CTF で正規表現力の研鑽を積んだ結果、なんかできるような気がしてきて、やってみたらできました。

今思うに、一番重要なことは後方参照を更新できる、ということだったのかなと思います。 \g で呼び出された中にある後方参照は、呼び出されるたびに値が変わっていくという。




DEFCON CTF 本戦

2016-08-13T04:06:11+09:00

binjaの現地枠がギリギリ空いてそうだったので、入れてもらいました。思ったことは、みんなすごいなあ、ということと、これしんどいなあということ、ルールはともかくみんなでわちゃわちゃやるの楽しいなということ、あとまあなんと言っても俺ふがいないな、ってことでした。今回はCTFの前日に優勝賞金2億円のDARPA主催のCyber Grand Challenge(以下CGC)というのが行なわれ、それで優勝したAIを含めて15チームで同じフォーマットで競う、という趣旨でした。CGCはELFベースにABIを簡略化してあり、いつものようにシェルコードを実行するまではやる必要がなく、 type 1: EIPを指…binjaの現地枠がギリギリ空いてそうだったので、入れてもらいました。思ったことは、みんなすごいなあ、ということと、これしんどいなあということ、ルールはともかくみんなでわちゃわちゃやるの楽しいなということ、あとまあなんと言っても俺ふがいないな、ってことでした。今回はCTFの前日に優勝賞金2億円のDARPA主催のCyber Grand Challenge(以下CGC)というのが行なわれ、それで優勝したAIを含めて15チームで同じフォーマットで競う、という趣旨でした。CGCはELFベースにABIを簡略化してあり、いつものようにシェルコードを実行するまではやる必要がなく、 type 1: EIPを指定されたところに飛ばす type 2: 特定のアドレスにある、フラグページから4byte取り出す のいずれかを達成すればOK、というルールでした。 準備 準備の段階では、 bjmit という名前でバイナリに mitigation (日本語でなんと言うのだろう) を入れるツールと、それの評価をするものを作っていました。バイナリジャンルの mitigation というのは ASLR や stack canary なんかがよく使われるものです。 stack canary みたいなのを入れるのはまぁまぁ大変なので、簡単に実装できるものをたくさん準備する、という方針で retをフックして戻り先が元々.textだったか、callの直後に戻っているかをチェックする jmp/callをフックして戻り先が元々.textだったかをチェックする sub esp, XXをフックして未初期化スタックを使わないようにする writeシステムコール相当をフックして、フラグページを直接writeできないようにする mmap(PROT_EXEC)相当を禁止する デフォルトでスタックがRWXなのでRWな空間に引っ越す ヒープを適当にrandomizeする 共通で使われるコードにある、いらないコードを削除もしくは総取っ替えし、ROPなどに使いにくくする というような機能を作りました。安易な攻撃には最初の2つが特に効く感じで、前もってサンプルで試してる感じでは、まあ半分強くらいのサンプル攻撃が止まるな、ってところでした。バイナリいじってパフォーマンス(CPUメモリディスク使用量)が落ちると評価が下がってしまうんですが、そのへんもまぁ、問題によっては使えないけどギリギリOKかな、ってレベルでした。mitigationというのは本質的にあまり意味がないものだと思っていて(おそらく世の中的にもそう思われていて)、やはりそういうゴマかしはさらなる回避策とのイタチごっこになるので、なんらかのsandboxで根本的に根本から断つのが筋というのが最近の流れだと思います。ですが、短期間のコンテストではまあまあ時間かせぎに[...]



システムプログラミング会

2016-07-06T02:43:52+09:00

すごい久々にイベントの(共同)主催的なことをしましたhttp://connpass.com/event/34995/イメージとしては言語雑談会的な感じで、closedに人集めてウダウダやるつもりだったんですが、途中でPFNさんに場所貸していただけるということで、不特定な人を呼ぶことになって、当初想定してたより大袈裟な会になりました。適当に募集すると人が集まって自己顕示欲が満たされるとか、普段得られない種類のフィードバックが得られたり交流ができる、てのがあるわけですが、めんどくさいのとグダグダ雑談がしにくいのが難点ですね。まあ自分自身が一般的に募集されてる会で勉強した面もあるわけで、そういうのの…すごい久々にイベントの(共同)主催的なことをしましたhttp://connpass.com/event/34995/イメージとしては言語雑談会的な感じで、closedに人集めてウダウダやるつもりだったんですが、途中でPFNさんに場所貸していただけるということで、不特定な人を呼ぶことになって、当初想定してたより大袈裟な会になりました。適当に募集すると人が集まって自己顕示欲が満たされるとか、普段得られない種類のフィードバックが得られたり交流ができる、てのがあるわけですが、めんどくさいのとグダグダ雑談がしにくいのが難点ですね。まあ自分自身が一般的に募集されてる会で勉強した面もあるわけで、そういうのの恩返しになるかもという面もあり、まあ色々。まとめとしてはkoieさんのブログやtogetterがまとまってそうhttp://blog.livedoor.jp/hkoie/archives/55525878.htmlhttp://togetter.com/li/995015私の発表はhttp://shinh.skr.jp/slide/kati_sp/000.htmlここに既に書いたことはざっくり飛ばして(それでも結構時間を使ってしまったけど…)、その後の細かいけど全体としてはそれなりに効いた最適化とか、straceいじって依存解析するプログラムを書いたような話をしました。後者の dsan のコードと改造 strace はhttps://github.com/google/kati/tree/dsan/toolshttps://github.com/shinh/straceにあります。 dsan_record.py の方はコマンドをラップして入出力を記録できる感じになってます。このコンセプトのドキュメントは https://docs.google.com/document/d/1eRSNE352rA6ocyoFljHQW2ySdhg9oKN8CHj2ljrlKX0/edit#@mkasaharaさんのLD_PRELOADベースの依存解析は、LD_PRELOADというかlibcレイヤでファイルシステムAPIフックするってのは、色んな機会に既に5回とかそれ以上やったことあって、手軽で高速なんだけど、結構問題も多いと認識してたので使いませんでした。具体的な問題としては、再入してウゲーとか、fts_openみたいなあまり使われないlibc API対応とか、ダイナミックローダを始めとしたスタティックリンクされてるバイナリに無力とか。LD_PRELOADベースな話として、djbのredoというアイデアを(僕から見れば中途半端に)実装した https://github.com/jekor/redo 、 https://github.com/apenwarr/redo 、あと @kazuho さんの https://github.com/kazuho/unco なんかも一応先行研究として眺めた記憶があります。 strace ベースの(これまた不完全な)やつだと https://github.com/nickstenning/trojans/blob/master/fabricate.py とか https://github.com/kgaughan/memoize.py/blob/master/memoize.py とか。印象に残った話@herumiさんの話: 途中に出てきた実行ファイル電子透かしは http://www1.cs.columbia.edu/~angelos[...]



defcon ctf qual 2016

2016-05-24T01:47:11+09:00

binjaの人たちすごいなと見てた。今回は結構な時間参加できたんだけど、まあひょっとしたら節約できた時間もあるかもね、てくらいの貢献度だったと思う。まあ入れてもらってからまともに時間使って参加した回が無かったくらいの勢いだったから、少しはなんかできて良かった。 b3s23 ライフゲーム15ターン動かした後の状態をshellcodeとして実行します、て問題。空間がループしてないタイプのライフゲームなんで、端っこの方は大変使いにくい…ので最初の命令で端じゃないところに実行飛ばして、あとは適当に、て方針で。うまく使えるジャンプ作るのが結構大変で、適当な形にグライダーぶち当てて都合よく出てくるパターン…binjaの人たちすごいなと見てた。今回は結構な時間参加できたんだけど、まあひょっとしたら節約できた時間もあるかもね、てくらいの貢献度だったと思う。まあ入れてもらってからまともに時間使って参加した回が無かったくらいの勢いだったから、少しはなんかできて良かった。 b3s23 ライフゲーム15ターン動かした後の状態をshellcodeとして実行します、て問題。空間がループしてないタイプのライフゲームなんで、端っこの方は大変使いにくい…ので最初の命令で端じゃないところに実行飛ばして、あとは適当に、て方針で。うまく使えるジャンプ作るのが結構大変で、適当な形にグライダーぶち当てて都合よく出てくるパターンを探した。うまいこといって、 read(0, buf, buf) とかが呼べたけど buf をちょっと動かさないとなってあたりで、別の人が1行目だけでできたぽかったので、放棄。終わってからローカルで shellcode 動くところまで作っておいた。https://gist.github.com/shinh/1891e3f346a1255fc06e8a7cbf63c756 15 o oo ooo oo o oo o o o o oo oo o o oo o o oo oo oo oo o o oo o oo o o o oo oo oo o o o o o oo oo oo oo oo o oo oo oo oo o o oo kiss レジスタを全消去の後 RAX RBX RCX RDX はヒープ内の好きな場所指した状態、それで RIP を好きなとこ飛ばせますよって問題。 RSP をまともな値にせんとどうしようもないやろ…ということで RSP をリストアするであろう、 libc の longjmp とか setcontext とかを眺める。 RSP の値の一時退避先が R[ABCD]X なら良いだろう、てことで。まあでも R8 とか使ってて惜しかったりするものの見つからない。で少し探索範囲を広げて RSP いじってるとこ探すと 498b0: 48 89 dc mov %rbx,%rsp 498b3: 5f pop %rdi 498b4: 48 85 ff test %rdi,%rdi 498b7: 74 08 je 498c1 ; [L5010] 498b9: e8 22 d9 ff ff callq 471e0 というのが見つかったので、これ都合良くないですか…と聞くと、他の人が使えそうといいうことで、後はやってくれた。終わってからこれ何かなーと調べてみると、 makecontext の実装に使ってる、トランポリンにあたるコードらしい。 makecontext て戻り値の書き換えとか使ってるんだな… crippled 寝て起きて二度寝するかなとそ[...]



8cc.bf

2016-03-17T09:15:07+09:00

https://github.com/shinh/bflisp/blob/master/8cc.bfBrainfuckで動くCコンパイラができました。このコンパイラ自身で同じコンパイラをコンパイルすることも可能です(ただし5時間以上かかる)。前回との差分はレジスタの幅とデータメモリ空間を24bitに広げたことと、いくつかバグをつぶしたことです。これまでわざわざ手書きで書いていたBrainfuckのプログラムを、Cのコードから生成することでお手軽に作れるようになりました…とさ。 sizeof(int)==1 で 1byte==24bits だったりする変なアーキテクチャな上に、ビット演算とかがな…

https://github.com/shinh/bflisp/blob/master/8cc.bf

Brainfuckで動くCコンパイラができました。このコンパイラ自身で同じコンパイラコンパイルすることも可能です(ただし5時間以上かかる)。前回との差分はレジスタの幅とデータメモリ空間を24bitに広げたことと、いくつかバグをつぶしたことです。

これまでわざわざ手書きで書いていたBrainfuckのプログラムを、Cのコードから生成することでお手軽に作れるようになりました…とさ。 sizeof(int)==1 で 1byte==24bits だったりする変なアーキテクチャな上に、ビット演算とかがないですけど。




就職して9年が過ぎる

2016-03-11T14:28:18+09:00

転職して7年が過ぎたというのを読んで気づいたんだけど、そろそろ入社後9年が経過したらしい。僕は結構長い期間をここで過ごしたことになるんだなと思った。ちょっと以前のことを振り返ってみようと思う。言うまでもないけどこれは僕の書ける範囲での個人的な感想と体験談であって会社の見解等を表しているものではない。 きっかけ わりと重要でない Borgチーム (の周辺) いつのまにやらBorgという名前を普通に言って良くなっている。嬉しい。まあ当時もぶっちゃけ、秘密だから出してないっていうよりは、単に誰もアカデミア的なキャリアに興味が無いから出してなかったんだと思う(私見)。さて、当時Borgというかクラスタ…転職して7年が過ぎたというのを読んで気づいたんだけど、そろそろ入社後9年が経過したらしい。僕は結構長い期間をここで過ごしたことになるんだなと思った。ちょっと以前のことを振り返ってみようと思う。言うまでもないけどこれは僕の書ける範囲での個人的な感想と体験談であって会社の見解等を表しているものではない。 きっかけ わりと重要でない Borgチーム (の周辺) いつのまにやらBorgという名前を普通に言って良くなっている。嬉しい。まあ当時もぶっちゃけ、秘密だから出してないっていうよりは、単に誰もアカデミア的なキャリアに興味が無いから出してなかったんだと思う(私見)。さて、当時Borgというかクラスタマネージメントのあたりでは、コンピュータのリソースて適当にたくさん使ってるけど、これ節約したらすっげー支出減ったりしない?みたいなのがホットで、なんかとりあえず色々な人々が色んなことをやっていた。いくつかうまくやったチームがあって、実際すっげー減ったんじゃないかな。最初の3ヶ月は練習期間的な感じで、そういうのの一つでチマチマPython書いたりしてた。で、日本に帰ってきて僕の入ったチームでは、色々なクラスタの変更の結果が予想しやすくなる、みたいなのを作っていた。Borg自体のコード使ったりもしてたこともあり、ちょっとパッチ投げたりもしたけど、まあ総じて重要度はそれほど高くないプロジェクトだったのかなぁと、今となっては思う。でも新卒で入った僕にわかるわけもなく、そしてエンジニアリング的にはすごく勉強になった。指導してくれた人達がすごかった。 glog (憧れの20%プロジェクトは80%より楽しくなかったでござるの巻) 当時僕はGoogleさっさと辞めると思っていた。しかしGoogleにあるものは色々便利なので、なんか色々opensourceになってると良いなあとか思っていた。Google入って最初の頃に特に感銘を受けた文化に、とりあえずログ残して、用途は後で考える、てのがあった。ログつーとアクセスログみたいなやつと、プログラムがこんなことあったぜ、て端末に吐き続けるログがある。前者は当然すさまじく重要なんだけど、後者も有意義。まークラウドみたいな環境だと、たまーに起きた問題にgdbで対処する、なんてのはあまり現実的でないことが多く、ログとコード見比べて、ああここNULLになりうるな、みたいな[...]



bflisp.bf

2016-02-28T23:18:25+09:00

https://github.com/shinh/bflispLisp インタプリタを作りました。 Brainfuck で。だいたい sedlisp や beflisp や makelisp と似たようなことができます。ちょっとバグあるみたいですが。Malbolge は実装不能だと思うので、これ以上なくキツいターゲットじゃないかと思っています、ので Lisp シリーズはこれで最後でないかと。というか現世的な速度で動くとは思ってなかった。月なみですが、今のパソコン速いですねー。実現は簡単な 16bit ハーバードアーキの CPU を定義して、魔改造した 8cc で lisp.c をその CPU …

https://github.com/shinh/bflisp

Lisp インタプリタを作りました。 Brainfuck で。

だいたい sedlispbeflispmakelisp と似たようなことができます。ちょっとバグあるみたいですが。

Malbolge は実装不能だと思うので、これ以上なくキツいターゲットじゃないかと思っています、ので Lisp シリーズはこれで最後でないかと。というか現世的な速度で動くとは思ってなかった。月なみですが、今のパソコン速いですねー。

実現は簡単な 16bit ハーバードアーキの CPU を定義して、魔改造した 8cc で lisp.c をその CPU のアセンブリコンパイル、そのアセンブリなどから Brainfuck を生成、という感じになってます。実行は最適化機能つきの 8bit Brainfuck インプリタでやってます。ある程度最適化しないとまともな速度で動かないと思います。

メモリとかなかなか大変で。 Brainfuck で 16bit アドレス空間の load/store を現実的な速度かつコードサイズで実現する方法がなかなか思いつかなかったのですが、今回思いついたから作業始めた、という感じでした。

仮想 16bit CPU を挟んだのは、 @rui314 さんが sedlisp くらいの時から、直接やるんじゃなくて間に中間的な複雑さのなにかを挟んだ方が簡単じゃないの?って言ってて、それを採用した感じです。 sed/befunge/make の時は挟まない方が簡単だと今でも思ってますが、 Brainfuck 直行はまあムリゲー感しか無いです。

Befunge の時は LLVM bit code からだったのですが、 8cc にしたのは Brainfuck 上で C コンパイラ自体を動かすという夢があるからです。これ実現するにはまだまだやること多いはず…です。 8cc 大変いじりやすくてありがたかったです。




あとひとつ書き忘れてた

2015-12-12T14:52:54+09:00

パーティクルプログラミング、Rubyは3文字連続のやつが1回と残りは全部2文字連続、てのができるんですが、Perlも全く同じ条件で書けると思っています。ただそれより厳しい条件が可能かどうかがよくわからない。

パーティクルプログラミング、Rubyは3文字連続のやつが1回と残りは全部2文字連続、てのができるんですが、Perlも全く同じ条件で書けると思っています。ただそれより厳しい条件が可能かどうかがよくわからない。




TRICK 2015

2015-12-12T14:14:32+09:00

口頭でも言いましたが、今回は落選したものでも良いできだなーというのが多かったです。前回が価値が無いというほどでは全然ないんですけど、しかしちょっと差があったのは事実かなと。僕が高得点をつけたものについて コラッツ https://github.com/tric/trick2015/blob/master/ksk_1/entry.rbすごい。これ見れば見るほどスルメみたいに味が増えていくというか、しかもその味やばいっていうか、この短さのコードで、いやここまで考えさせられるとは、っていう。圧巻でした。がまあ普通に考えてこれの評価がそろわないのは予想できます。2位でも十分評価されていたと思われます。…口頭でも言いましたが、今回は落選したものでも良いできだなーというのが多かったです。前回が価値が無いというほどでは全然ないんですけど、しかしちょっと差があったのは事実かなと。僕が高得点をつけたものについて コラッツ https://github.com/tric/trick2015/blob/master/ksk_1/entry.rbすごい。これ見れば見るほどスルメみたいに味が増えていくというか、しかもその味やばいっていうか、この短さのコードで、いやここまで考えさせられるとは、っていう。圧巻でした。がまあ普通に考えてこれの評価がそろわないのは予想できます。2位でも十分評価されていたと思われます。 ドラゴン曲線 https://github.com/tric/trick2015/blob/master/monae/entry.rbこれは初見の印象はかなり悪かった。単なる Quine てのは、もう相当なことをしない限りは僕の中ではマイナスだと言って良い。ただコード読んでみると、なるほどなー的な感じでコードがふくらんでいっていたと思う。いやでも忘れつつある。 数独 https://github.com/tric/trick2015/blob/master/eregon/entry.rbこれも最初のイメージはイマイチ。しかしよく読むとよくできてる…ていうかデータの埋め込み方かっこいいよね。こうやると決めればテクニックが必要な領域ではないけど、しかしこの埋め込み方決めたのは感心する。Fiber は正直解く部分ちゃんと読めてないからよくわかってないけど、それでなくても最高に近い点数あげるから文句言うな、的な感覚で読むの放棄した。。 文字数にエンコードされてるプログラム https://github.com/tric/trick2015/blob/master/usak/entry.rbいや本当にこういう一発ネタ好きで。コメントした通り中盤はこうグダグダ感あるな、って気付いたのと、あれこれそんな難しいわけでもないよね、てあたりで点数を落としてしまった。最初はあまり迷いなく10点つけてた…がさすがにおかしい気がして少し落とさせてもらった感じで。いやーでもこれ好きだな。ここまでのやつと比較してみると、コラッツは発想も実装も僕の枠を越えてて、ドラゴン曲線と数独は、発想はわかるなって感じで、実装はがんばったなーて感じ。このコードは発想がすごくわかりやすいが僕の発想の範囲にないのが好きで。http://www.garbagecollect.jp/~usa/d/201512b.html#id20151211_P1_6に書かれてますが、 ; の行は僕も味わいがあって良いなとか思ってました。その前後がちょっと残念かなあとは。[...]



printf 用のマクロの話

2015-12-11T00:18:37+09:00

C言語 Advent Calendar 2015 - Qiita 向け 15年ほどC++書いてるんですが、どんどん自分の書くコードがbetter Cになっていっているような気がしています。どんどん先進性みたいなのが劣化している気がするので、特に高度なことは書かない…というか書けないです。で、なんか C++ でも printf を使ってしまう傾向にあります。 cerr だと endl 書かないといけないのがめんどくさいけど自動で改行足すようなやつ作るのは少しめんどくさい フォーマット指定子が思い出せない という2点が主な理由かなあと思います。あとなんか % で書いてある方が出力が予想しやすいこと…

C言語 Advent Calendar 2015 - Qiita 向け


15年ほどC++書いてるんですが、どんどん自分の書くコードがbetter Cになっていっているような気がしています。どんどん先進性みたいなのが劣化している気がするので、特に高度なことは書かない…というか書けないです。

で、なんか C++ でも printf を使ってしまう傾向にあります。

  • cerr だと endl 書かないといけないのがめんどくさいけど自動で改行足すようなやつ作るのは少しめんどくさい
  • フォーマット指定子が思い出せない

という2点が主な理由かなあと思います。あとなんか % で書いてある方が出力が予想しやすいことが多いような気がするんですよね。特に括弧とかがたくさん登場する場合。

LOG("setenv(%s, %s)", name, value);
LOG << "setenv(" << name << ", " << value << ")";

のどっちが良いかというような話。

iostream 使えば operator<< のオーバーロードで自分の型でも表示できる、てのが嬉しいということがあるかと思うんですが、このへんはマクロ使うと少しラクになったりとか。例えば kati ではファイル名と行番号を保持する

typedef struct {
  const char* filename;
  int lineno;
} Loc;

みたいな型があったんですが、これを出力するために

#define LOCF(loc) loc.filename, loc.lineno

みたいなマクロを定義して

Loc loc;
fprintf(stderr, "%s:%d: something something\n", LOCF(loc));

みたいな感じで使っていました。このマクロだと LOCF に渡したものに副作用があると二度評価されてしまいますが、まあ普通問題にはならないでしょう。。

次の例はヌル終端してない、 Pascal 文字列のようなやつ。

class StringPiece {
 public:
  const char* data() const { return ptr_; }
  size_type size() const { return length_; }
};

これも

#define SPF(s) static_cast<int>((s).size()), (s).data()

みたいなマクロを定義してやると、

StringPiece str;
fprintf(stderr, "str=%.*s\n", SPF(str));

というようにすると出力できたりします。 %.*s で文字数を変数で指定できる、ていうちょっとマイナー気味な機能を使っています。

他のマクロネタも書こうかと思ってたんですけど、なんか nothingcosmos さんのやつとかぶってるような、かぶってないようなという感じだったので、書き気も起きなくなったので省略。




HITCON CTF 2015

2015-10-19T22:48:08+09:00

今回は fuzzi3 というなんか卑怯な人の多さのチームに混ぜてもらいました。用事もあったのでゆるく参加するつもりが割と頑張ったけ。けどゆるく参加しても貢献度変わらなかったんじゃね?という感じの成果でした。チームがものすごいので4位。他人の成果に乗っかってなんかするのができるのはラクだなーというのと、ちゃんと自分の成果を後に引きつげるように考えるべきだなーとか思った。https://ctf2015.hitcon.org/scoreboard hard to say なんか shell 呼べる Ruby で記号しばり 10B で cat flag しろ、という問題。4つにわかれてる問題で、1つ目…今回は fuzzi3 というなんか卑怯な人の多さのチームに混ぜてもらいました。用事もあったのでゆるく参加するつもりが割と頑張ったけ。けどゆるく参加しても貢献度変わらなかったんじゃね?という感じの成果でした。チームがものすごいので4位。他人の成果に乗っかってなんかするのができるのはラクだなーというのと、ちゃんと自分の成果を後に引きつげるように考えるべきだなーとか思った。https://ctf2015.hitcon.org/scoreboard hard to say なんか shell 呼べる Ruby で記号しばり 10B で cat flag しろ、という問題。4つにわかれてる問題で、1つ目とかは結構サイズ制限ゆるい。とりあえず任意コードの記号化プログラム的なものが手元にあるのでそれで1問目終了。全チーム最初の1以上の得点だったと思う。2,3とうーんどっちかというとshell芸だなーと思いつつ m4 flag とかしてこなす感じで。4つ目は全然わからなくて、1つ目で環境見て遊んでる最中に書き込める領域見つけたのでそこに cat flag て内容のファイル書いて実行して終わり。https://gist.github.com/shinh/4999b3d154aafc774b91本当は $0 が /bin/sh だからそれ使えば良かったらしい。おでかけに行く。 babyfirst 出先で docs を見ると、空白と改行と \w+ だけで shell のコード適当に動かせるよ、 wget で色んなファイル置けるよ、ただファイル名指定できない、ということをチームの人が発見していた。ファイル名指定できないと index.html になるので、 . が使えないと実行できない。うんテザリングであれこれ試すにはちょうどいいくらいかな…とあれこれ試す。まー redirect っしょーと色々やるも、どうもファイル名が index.html になる。 ftp どうよ、と ftp://.../robots.txt にリダイレクトすると robots.txt という名前で落ちてくる。ああこれいけるなーと思ったけど anonymous write できる ftp わからんかったし ftp サーバ出先で上げるのは困難な気がしたので(よく考えると VPS 使えばできたが)、チャットで言ったら他の人が終わらせてくれた。 risky 酒飲んで帰って、適当に見てると risky というのが x86 でない謎アーキテクチャで僕好み。見る。適当に PLT とか見て命令推測…とか少しやってたけどよく docs 見ると RISC-V であることはわかってたぽいので、ツールチェインインストール…とかやってたけどよく見ると他の人が objdump の結果はってた。適当にアセンブリを方程式にするコード書い[...]



kati について

2015-09-24T00:58:03+09:00

https://github.com/google/katikati について、ドキュメント書こう…と思っていたのですがなかなか進まないので、とりあえず日本語で書いてみることにしました。何書くかがあまり明確じゃないテーマなので、何書くか考えるのと英語考えるのを両方同時にやるのが少し大変で。 動機 kati は GNU make のクローンです。いずれ完全なコンパチになると嬉しいですが、なかなか難しいだろうと個人的には諦めています。用途に対して実用的ならば良いかなと。動機としては、 Android platform のビルドシステムが、なかなかシュールな GNU make 黒魔術で構成されていて…https://github.com/google/katikati について、ドキュメント書こう…と思っていたのですがなかなか進まないので、とりあえず日本語で書いてみることにしました。何書くかがあまり明確じゃないテーマなので、何書くか考えるのと英語考えるのを両方同時にやるのが少し大変で。 動機 kati は GNU make のクローンです。いずれ完全なコンパチになると嬉しいですが、なかなか難しいだろうと個人的には諦めています。用途に対して実用的ならば良いかなと。動機としては、 Android platform のビルドシステムが、なかなかシュールな GNU make 黒魔術で構成されていて、 make が実際になんかしはじめるまでが遅かったので、そこを高速化したいというものでした。ビルドシステムが遅いという時、まずだいたいヌルビルドとフルビルドの2点を考えます。ヌルビルドてのは生成物が全てできている時の、 make て叩いてから Nothing to be done て出るまでの時間で、フルビルドは生成物が全くない時の時間です。現実のビルドは両者の間になりますが、大雑把に言って、ヌルビルドは開発中に .c を一ついじった時のターンアラウンド時間などに強く影響し、フルビルドは新しいリビジョンをチェックアウトした時や多くのファイルから include されてるファイルをいじった時などのビルド時間に影響します。Android の場合、結構立派なワークステーション+SSDで、ヌルビルドが100秒ほど、フルビルドが30分てとこでした。30分はまぁ良いんです、30000ターゲット以上あるので。ヌルビルド100秒の方が終わっています。 C ファイル一個書き換えて、コンパイルが通るかがわかるのが100秒後というのは結構つらい。 kati 使うと Makefile 書き換えや Java ファイル追加が無い時のヌルビルドは5秒、ある場合で50秒てとこです。というわけで GNU make クローン作ってみるのはどうよ、ということで始めたプロジェクトでした。最初はコマンド実行もやる予定でしたが、 ninja 出力する方が色々都合が良い部分もあり今はそうなっています。 20% 的に始めたプロジェクトでしたが、気がついたら本職になってて、 AOSP で make て叩くと勝手に kati+ninja でビルドされるようになりました。最初は色んなものキャッシュするとかちゃんとやれば十分パフォーマンスが出るだろう、という見通しで ukai さんと Go で書き始めたのですが、主に GC のせいかす[...]



あなたの知らない超絶技巧プログラミングの世界

2015-09-17T02:22:47+09:00

奇書を頂きました。一応レビュアーとして参加したことになっています…が、掲示板かなにかと勘違いした人が雑談をして邪魔をしているな、という感じでした。浜地慎一郎という文字列が10回くらい出てくる残念な本です。もう少しマジメに説明すると、私がクソコードとか読んでいるような、トリッキーなコードの作品集兼使われているテクニックの解説などがなされています。読んでいてこの本面白いなーと思ったのは、関連する他の人が書いたコードも紹介されていますが、基本的に遠藤さんの作品が主人公ということでした。えっこの人本一冊書けるくらい Quine 書いてるんだ…という。それと、クソコードコンテスト for Ruby であ…

奇書を頂きました。

(image)

一応レビュアーとして参加したことになっています…が、掲示板かなにかと勘違いした人が雑談をして邪魔をしているな、という感じでした。浜地慎一郎という文字列が10回くらい出てくる残念な本です。

もう少しマジメに説明すると、私がクソコードとか読んでいるような、トリッキーなコードの作品集兼使われているテクニックの解説などがなされています。読んでいてこの本面白いなーと思ったのは、関連する他の人が書いたコードも紹介されていますが、基本的に遠藤さんの作品が主人公ということでした。えっこの人本一冊書けるくらい Quine 書いてるんだ…という。

それと、クソコードコンテスト for Ruby であるところの、 TRICK 2015 が開催されますので、みなさん頑張ってクソコードを書いて、審査員をうならせて下さい。

https://github.com/tric/trick2015/blob/master/README.ja.md




makelisp.mk

2015-09-15T14:14:38+09:00

https://github.com/shinh/makelispLisp インタプリタを書きました。 GNU make で。https://github.com/shinh/makelisp/blob/master/makelisp.mkもちろん $(shell) や $(guile) は使わない縛りです。だいたい sedlisp や beflisp と似たようなことができます。最近作ってる GNU make clone であるところの kati でもちゃんと動きます。というか fizzbuzz.l とかだと 50 倍以上速い。実装はまあ、やるだけ…と言いたいところですが、加減乗除が無いとか…

https://github.com/shinh/makelisp

Lisp インタプリタを書きました。 GNU make で。

https://github.com/shinh/makelisp/blob/master/makelisp.mk

もちろん $(shell) や $(guile) は使わない縛りです。

だいたい sedlispbeflisp と似たようなことができます。

最近作ってる GNU make clone であるところの kati でもちゃんと動きます。というか fizzbuzz.l とかだと 50 倍以上速い。

実装はまあ、やるだけ…と言いたいところですが、加減乗除が無いとか、文字列演算も色々不便とかあったりはします。あと地味に引数以外にローカル変数が無いのもだるいですね。当初は lisp to make translator を実装する感じがラクかな…と思ってたんですが、ローカル変数無いとかそういう理由で、別にラクじゃないどころかむしろ大変な気がしたのでやめました。

追記: もっとガチな Lisp 実装があるとのこと https://github.com/kanaka/mal/ 四則演算とかがちゃんと速いのがマジメ感あってやばい。おかげで一個 kati のバグ見つけた。。




MMA CTF 2015

2015-09-07T23:07:06+09:00

http://uecmma.github.io/mmactf/ja/なんかとても面白かった。21位。あまり気力の無い季節なので、 Pwn を避けて慣れないジャンルを解く感じで。ただスプラトゥーンを始めてしまったため、最後の20時間は問題読むくらいしかしてなくて28時間コンテストでした。マジメに参加してない上に簡単な問題しか解いてないですけど、問題セットは僕にはすごく楽しかったです。色んなジャンルで、ちょっとこじゃれた感じというか。運営もほとんどヘンなトラブル無かったように思いますし。成果物: https://github.com/shinh/mma-ctf-2015解いた問題 Pattern …http://uecmma.github.io/mmactf/ja/なんかとても面白かった。21位。あまり気力の無い季節なので、 Pwn を避けて慣れないジャンルを解く感じで。ただスプラトゥーンを始めてしまったため、最後の20時間は問題読むくらいしかしてなくて28時間コンテストでした。マジメに参加してない上に簡単な問題しか解いてないですけど、問題セットは僕にはすごく楽しかったです。色んなジャンルで、ちょっとこじゃれた感じというか。運営もほとんどヘンなトラブル無かったように思いますし。成果物: https://github.com/shinh/mma-ctf-2015解いた問題 Pattern Lock https://github.com/shinh/mma-ctf-2015/blob/master/pat.cchttps://github.com/shinh/mma-ctf-2015/blob/master/pat3.ccAndroid のパターンでロックを解除するやつ、何通りあるか、て問題。2問目は4x4で最長のパターンの長さを求めよ、てやつ。2問目はメモ化必要だった。割と ICPC スタイル。 Smart Cipher System https://github.com/shinh/mma-ctf-2015/blob/master/c2.cchttps://github.com/shinh/mma-ctf-2015/blob/master/c4.cchttps://github.com/shinh/mma-ctf-2015/blob/master/c5.ccいくつかの古典暗号。3つ目はブルートフォースで、4つ目は手をつけなかった。 Login as admin! SQL injection Splitted https://github.com/shinh/mma-ctf-2015/blob/master/splitted.rbpcap 内の Partial Content で帰った HTTP リクエストを適当につなげるだけ。 How to use? https://github.com/shinh/mma-ctf-2015/blob/master/howtouse.rbDLL らしいが win バイナリ作るとかめんどくさいんで、 objdump 見て答えぽいところのデータをつないでるだけ。 RPS https://github.com/shinh/mma-ctf-2015/blob/master/rps.rbじゃんけんに50回勝てという問題。名前を最初に入れるのでバッファオーバーフローさせてエンディングにいきなり飛ばすゲー。 This program cannot be run in DOS mode https://github.com/shinh/mma-ctf-2015/blob/master/cannotberun.rbMZ ヘッダから PE ヘッダが参照されてないのでオフセットを書くだけ。笑っちゃうくらい短い解答やな。 Signer and Verifier https://github.com/shinh/mma-ctf-2015/blob/master/sign.rb本来 sign させたいメッセージを少し加工したものに sign してもらうと、そこから元のメッセージを sign できるという話。 Encrypted 見てない Impossible? 見てない Simple Hash 解けなかった文字列に対して、 hash = 0; for (ch in str) { hash *= 577; hash += ch; hash %= [...]



機械は人狼を見つけられるかな、の各国対応

2015-09-01T04:26:40+09:00

ずいぶん昔に作った対人狼ベイジアンフィルタ、少し前に各国対応してたんですが、 @mr_konnさんのtweetで思い出したのでここに書いておきます。使いかたはサンプルURLを参照のことhttp://shinh.skr.jp/expwolf/人狼AIなんてなー10年近く前に俺が通った道だ…とかいえるレベルのものではなく、まあオモチャです

ずいぶん昔に作った対人狼ベイジアンフィルタ、少し前に各国対応してたんですが、 @mr_konnさんのtweetで思い出したのでここに書いておきます。

使いかたはサンプルURLを参照のこと

http://shinh.skr.jp/expwolf/

人狼AIなんてなー10年近く前に俺が通った道だ…とかいえるレベルのものではなく、まあオモチャです




ICFPC 2015

2015-08-11T00:06:24+09:00

開始1時間くらい前に酒飲まないかと誘われる。まー ICFPC 一応やるんで、とか言うと一緒にやることになった。ので初のチームでの参加。チーム名は N6B 。FFRK やってたら始まる。なにこれ落ちゲーとかやる気起きないっていうかこれやるなら puyoai の方が面白いんじゃね…と移動する部分だけ書いて寝落ち。僕の中の今やりたいことランキングは、スプラトゥーン>>FFRK>仕事>>puyoai>ICFPC と致命的にモチベーションが湧かない状態。3時頃起きた。相方にシミュレータ完成させたらいいんじゃねみたいなことを言う。僕は C++ でソルバ書き始める。また寝て起きる。ソルバがそれっぽくなる、が…

開始1時間くらい前に酒飲まないかと誘われる。まー ICFPC 一応やるんで、とか言うと一緒にやることになった。ので初のチームでの参加。チーム名は N6B 。

FFRK やってたら始まる。なにこれ落ちゲーとかやる気起きないっていうかこれやるなら puyoai の方が面白いんじゃね…と移動する部分だけ書いて寝落ち。僕の中の今やりたいことランキングは、スプラトゥーン>>FFRK>仕事>>puyoai>ICFPC と致命的にモチベーションが湧かない状態。

3時頃起きた。相方にシミュレータ完成させたらいいんじゃねみたいなことを言う。僕は C++ でソルバ書き始める。また寝て起きる。ソルバがそれっぽくなる、が、リモート環境と結果が喰い違ってるらしく点数取れない。

いくつかバグなおすと、回転無しでやると得点取れるようになる。回転むずいなあ…とどはまりする。そのうちシミュレータの回転が完成したらしい。 C++ の方もなんかできた気がする。なんか色々やってると1位とかに一時的になったりする。まあ他のチームが潜伏してただけだが。ただその頃には lightning division は終了済み。ひどい。

その後は酒飲みながらだらだらやる。とりあえず、置きたいところを決めてからフレーズを探すように分離する。そうこうしてるうちに r'lyeh がフレーズだと相方が発見したので、そういえば…とマップの絵を見るとそれがあるので、他も試したらいいんじゃね、て言うと yuggoth と ia! ia! を見つけてくれる。

r'lyeh はおいしいのでそれまで使ってた bap (対抗のバグ修正の後は ei!) のかわりになるべく多用するようにする。このへんでまた1位になってたと思う。

テトリス部分を書かなければいけないが、どう考えても puyoai の方がまだ楽しい。やる気起きない。現実逃避にタイムアウト対策やマルチコア活用を入れる。やる気おきないーと思いつつ、今まで1手探索だったのを2手探索にする…と少しは良くなるが遅すぎてうざい。もういいやと放棄してスプラトゥーン。

終了。1日ちょいくらいでできそうなことしかやってない。ビールは8*350mlくらいでした。

コード: https://github.com/shinh/icfpc2015/




Unix v6 の C コンパイラが面白かった話

2015-06-04T21:02:38+09:00

Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdfの「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。構文木のノードの種類に対して switch してやること…Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdfの「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。構文木のノードの種類に対して switch してやること決める…的なものが、データドリブンな方法で書かれてます。データを保存するフォーマットは、 JSON とかではなく、時代が時代ですのでアセンブリです。こういうやつhttps://github.com/mortdeus/legacy-cc/blob/master/last1120c/regtab.sちなみにこれは v6 より古い時代のコードらしく、だいぶ v6 のやつよりシンプルですが、まぁ v6 も本質的にだいたいいっしょです。たとえば 60 番 (これは == のノード番号) を見てみると、 60.; cr60 となってて、 cr60 の定義は / relationals cr60: %n,n HC I 2f clr R br 1f 2: mov $1,R 1: です。最初の %n,n みたいなやつは、構文木にぶらさがってる左右の子が何者か、を示してます。 n はなんでもいいよ、っていうやつ。例えば %n,z だと右の子が定数ゼロなのでちょっと良いコードを出力する…みたいなことができます。そこからはちょっとした VM というかなんというかの命令列です。大文字は全部特殊な意味があって、それ以外はそのままアセンブリとして出力されます。HC は構文木のこのノードを含めてここから下を評価して condition code に置いて、という意味です。 I は自分のノード番号に対応する命令を置いてね、という意味。対応する命令ってのはhttps://github.com/mortdeus/legacy-cc/blob/master/last1120c/c1t.sに表になっていて、 60.; 0f; 1f; .data; 0:; 1:; .text とあるので 60 番は beq です(2番目のエントリは bne ですがこれはちょっと特殊な用途や、命令 I' で出力できます)。 は当時のアセンブラの記法で、 .ascii と同じ意味と思ってください。余談ですが 61 は != で、これの定義のしかたとかはちょっと素敵です。 60.; 0f; 1f; .data; 0:; 1:; .text 61.; 1b; 0b 1b は後ろに[...]



ppencode2

2015-06-03T02:26:16+09:00

Shibuya.pm で ppencode 2 についての話をしてきました。http://shinh.skr.jp/slide/ppencode2/000.htmlつうてもしかしはてなんの話したらいいんだっけ感があって、なんの話をしたんだっけ。。しっかしまあ、できたんだなーよかったねー感はありますね。おまけというかなふたつhttp://shinh.skr.jp/obf/yuine_kw.plhttp://shinh.skr.jp/obf/yuine_sym.plはまあなんかそれなりに面白い気がしないでもないが…これはまあ通常、通常てのが何かは知らんが通常、よりは少し大変で。なんだか quote…

Shibuya.pm で ppencode 2 についての話をしてきました。

http://shinh.skr.jp/slide/ppencode2/000.html

つうてもしかしはてなんの話したらいいんだっけ感があって、なんの話をしたんだっけ。。

しっかしまあ、できたんだなーよかったねー感はありますね。

おまけというかなふたつ

http://shinh.skr.jp/obf/yuine_kw.pl

http://shinh.skr.jp/obf/yuine_sym.pl

はまあなんかそれなりに面白い気がしないでもないが…

これはまあ通常、通常てのが何かは知らんが通常、よりは少し大変で。

なんだか quote に足りない文字があったりすりがたいしたことでもなく

まとめるとねむくてだるい




Python 2/3 で小文字アルファベットと丸括弧だけで Quine を書く

2015-05-31T00:23:38+09:00

http://shinh.hatenablog.com/entries/2015/05/11の続き。 @mametter が next(reversed(range(i))) で i-1 ができるということと、 @phoenixstarhiro が unichr(x)in(list(unichr(y))) で x==y ができるということを発見してくれたため、現実的なサイズで Quine が書けました。https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.pyhttps://raw.github…

http://shinh.hatenablog.com/entries/2015/05/11

の続き。 @mametter が next(reversed(range(i))) で i-1 ができるということと、 @phoenixstarhiro が unichr(x)in(list(unichr(y))) で x==y ができるということを発見してくれたため、現実的なサイズで Quine が書けました。

https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py

https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py3

今までいろいろクソコードを書いてきて、 http://shinh.skr.jp/obf/ にある程度まとめてたりしたんですが、最近全然アップデートしてないので、 github に新しい置き場を作ってみました。

https://github.com/shinh/hack

思いついた時に適当に色々足していこうかと思います。




Python 2/3 で小文字アルファベットと丸括弧だけでプログラムを書く

2015-05-11T01:22:23+09:00

http://d.hatena.ne.jp/nishiohirokazu/20120906/1346938523を読んで、なるほどー、でもカンマが必要というのは説得力が弱いな、と思ったので頑張ってみました。任意の Python コードを小文字アルファベットと丸括弧だけに変換できます。http://shinh.skr.jp/obf/ppencode_py.html 根っこの部分 は西尾さんのコードと同じ、つまり print(bytearray((XXX)for(x)in(YYY))) です。これ正直私の Python 力では自力では出てこないと思いますね。。西尾さんは YYY の部分が大雑把に …http://d.hatena.ne.jp/nishiohirokazu/20120906/1346938523を読んで、なるほどー、でもカンマが必要というのは説得力が弱いな、と思ったので頑張ってみました。任意の Python コードを小文字アルファベットと丸括弧だけに変換できます。http://shinh.skr.jp/obf/ppencode_py.html 根っこの部分 は西尾さんのコードと同じ、つまり print(bytearray((XXX)for(x)in(YYY))) です。これ正直私の Python 力では自力では出てこないと思いますね。。西尾さんは YYY の部分が大雑把に ASCII コードに対応する物体の tuple になってます。ここに tuple が必要だというのが、西尾さんの「カンマを使わずにイテレート可能なオブジェクトを作ろうとすると…」の元だと思うのですが、まぁ range/xrange はカンマ使わないわけです。 任意の数字を作る さて、 range 使うとなると文字列長をあらわす数字が必要です。特に 256 までは任意の文字を表現するために必須と言えます。西尾さんはタプルの長さを使ったりして、適切なサイズの文字列を作って len してました。カンマが無いと、単項演算しか無いわけで、だいぶやれることが減るのですが、いろいろ考えてると、数値を引数として数値をいじってかえす関数をいくつか作ることができます。例えば len(repr(zip(bytearray(i)))) は i に入ってる数値を 6 倍する関数です。こういう感じで、 3 倍するであるとか、 4 倍して 14 足すであるとか、微妙な材料が色々得られます。 2 倍とか +X とか便利なものはありません。要は repr で文字列を伸ばしていて、その前にした演算によって伸びる率が違う、って感じです。あとは数値を減らす手段としては bin, oct, str, hex を使って、 len(oct(i)) などとするのが唯一だと思います。これらは底を 2, 8, 10, 16 とした log_k(i)+1 として機能します。まあそんな連中でも 1000 程度までの数字なら作れてたみたいです。残念ながら 256 文字も使えば既にすごく遅いので、 JavaScript でのエンコーダでは 255 文字までしかサポートされてません。できあがったテーブルはhttp://shinh.skr.jp/obf/alpha_paren_py2_dataにあります。これで、大元の for の右っかわができそうな気配です print(bytearray((XXX)for(i)in(range(YYY)))) YYY にこの方法で生成した数字をあらわす式を入れれば文字列長だけのループが回せるのです。 テーブルをひき[...]



重複なしで Hello, world! を Ruby だけで

2015-05-13T01:56:12+09:00

CodeIQ に Hello, world! を3つ以上の言語で書きなさい、ただしそれぞれで使われてる文字種に重複があったらダメ、という問題がありました。http://nabetani.hatenablog.com/entry/codeiq_hwx3_q766私の解答は6言語使ったものでした。http://shinh.hatenablog.com/entries/2014/03/18今回は Ruby だけを使って、4つの Hello, world! ができました。言語が一つしか無いと複数言語を使うより色々なことをする余地が減るので、当然大変なので6つとかはちょっと無理です。5つも厳しいかなぁと…CodeIQ に Hello, world! を3つ以上の言語で書きなさい、ただしそれぞれで使われてる文字種に重複があったらダメ、という問題がありました。http://nabetani.hatenablog.com/entry/codeiq_hwx3_q766私の解答は6言語使ったものでした。http://shinh.hatenablog.com/entries/2014/03/18今回は Ruby だけを使って、4つの Hello, world! ができました。言語が一つしか無いと複数言語を使うより色々なことをする余地が減るので、当然大変なので6つとかはちょっと無理です。5つも厳しいかなぁと思っていて、なんらかの文字を出力する方法が4つ以上思いあたらないからです。4つというのは puts/putc/print 系 IO#[...]