https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @jonigata よいですね！今度からGLRを人に説明するときこのページ投げます / CFG全体を表現できるので文法クラスに対する名前でわざわざGLRと呼ぶのは少ない気がしました。文法がLRな特殊ケースで自然にLR法に落ちるような汎用構文解析法のクラスを呼ぶということはあるかも | |
| @sinya8282 何かありそう感はありますよね。aperiodic性が一番使いやすそうな気がするのでモノイド表現を使う応用で何か…… #アルプスの湖畔の街の路地裏の水路に沿ったカフェでのランチ https://twitter.com/kinaba/status/452826660299997184/photo/1 | |
| @ranha らじゃー | |
| #etaps2014 1日目。http://www.etaps.org/index.php/2014/programme/monday-april-7th 招待講演→CC→POST→CC を見るつもりで今のところいます。 | |
| #etaps2014 CC(コンパイラを作る会議)の招待講演: よりマシン語に近い特徴も表せるような方向へのSSAの魔改造の歴史。conditional命令を抽象化する"ψ関数"とかVLIWで分岐を同時実行するためのif変換とか、ここでレジスタにあって欲しい的条件のエンコードとか | |
| #etaps2014 CC1件目:データフロー解析で一文毎に情報更新(dense)は重いので、情報が変わらない所は1ブロックにまとめて解析(sparse)したい。フローの向きを与えると必要な粒度にCFGを分解した形にする枠組。SSAにφの双対(σと呼んでた)を入れたのと大体同じ？ | |
| #etaps2014 CC2件目:配列の要素アクセスを可能ならローカル変数化してメモリアクセス減らす最適化の拡張ArraySSAによる実現。ループ中の配列要素読み/書き/に加えbody開始の位置にuφ/dφ/hφという特殊φ関数を入れることで使える添字セットのデータフロー解析する | |
| #etaps2014 CC3件目: C++のバイナリの逆エンジニアリングでクラスの継承関係とhas-a関係を復元するツール。ABIからthisと分かる引数が同じメソッド呼び出し列を同一オブジェクトと判断、その最後のメソッドreturn連打をデストラクタとみなし継承関係をそこで取る | |
| #etaps2014 CC4件目: これ面白かった。ポインタによる到達可能性で回収範囲を判断するのではなく、プログラム解析して今後アクセスされない部分は例え到達可能でも捨てる"liveness GC"の提案。まずは純粋関数型・一階・A正規形のSchemeサブセットで実装 (続 | |
| #etaps2014 続)どうやるかというと、各関数がアクセスする可能性のあるcar/cdrパスを01の文字列集合で予め静的解析しておく。一階プログラムだと文脈自由になる。consを考えると01の逆元も必要。逆元除去をCFGでやりにくかったので正規言語で近似。この情報を元に頑張る | |
| .@ranha @sinya8282 https://t.co/T8I7Dq7iO9 群+形式言語でプログラミング言語を殴る応用例情報です ( PDF: http://www.cl.cam.ac.uk/~am21/papers/liveGCdraft.pdf ) 高階バージョン考えたい | |
| #etaps2014 CC5件目: 4件目の論文読んでたらほとんど聞き逃した。なんかFFTWみたいな感じの賢く色んなタイイングでのコード生成組み合わせアタックをサポートする感じのライブラリの話だったような気がする | |
| 線路が芝生なのかわいい https://twitter.com/kinaba/status/453131421440163840/photo/1 | |
| フランスで二日過ごしての感想としては、パンがpainなのがどうしても英語読みしてしまって慣れない。bugzillaでunconfirmedがUNCOと略されてる級に慣れない。今晩のメニューは肉と野菜と痛みと苦しみで御座いますって書いてある気分になる。 | |
| #etaps2014 第二セッションはPOST ( http://www.etaps.org/index.php/2014/post/programme )に来ました。たぶん今までこの会議の論文一本も読んだこと無いので何するとこかいまいちよく知らないですがまあ適当です。以下の投稿で"○件目"はその日の頭から1オリジンで数えたものとする | |
| #etaps2014 POST6件目:「プログラムがどのくらい情報を漏らすか」の理論。動かした前後での秘密情報のエントロピーの差を考えるのが既存の話で、ただシャノンのに限らず種々のエントロピー的な定義を用いても話はできて、そうやって計算された値の意味づけがはっきりしなかった (続 | |
| #etaps2014 続) そこでgeneralizeしよう。ゲーム的確率論みたい(?)にやる。情報毎にgainを定義する。attackerはgain最大化アタックをする。この観点で事前事後のgain漏れをleakとする。どういうgain関数で考えたのかという意味づけがつく。(続 | |
| #etaps2014 続) 全てのgain関数と事前分布に関してのこの値の大小、という形でprogram間のleakに関する順序も定まるし、これは行列に帰着して綺麗な定式化もできるし、既存の個々のエントロピーに限定した定理の一般化もできている。 | |
| 基本からして知らない分野の話を140文字にまとめるのは困難を極めるのであきらめてしまった…頑張ろう。さっきの話めっちゃ発表うまかった、というか午前のCCのセッションの発表の多くがびみょかった | |
| #etaps2014 POST6件目: bool型のみのプログラムで、さっきの話に出てきたShannonエントロピーでleakageを定義するとき、leakの具体的な値を計算するのはPSPACE (これまではhardnessとEXPTIMEアルゴリズムしか知られていなかった) | |
| #etaps2014 Q: PSPACEはわかったけどFPTみたいな、何かのパラメタを固定したら効率的みたいなのはないのその方が実用に近そうだけど A: 頑張ります | |
| #etaps2014 POST7件目: 引き続きプログラムの情報漏れ度評価の話。情報には漏れるとやばいのとそうでもない物があるので区別入れたい。gain関数でも原理的にはできるが色々難しいので別アプローチ。secretをfieldの集合とみなし部分集合に"worth"を割当る拡張 | |
| #etaps2014 POST8件目: これも面白かった。攻撃シナリオを説明する"attack tree"という概念があって、and-or木で「これまたはこれかつこれが成功したらアタック成功」みたいな状態を記述する。これを時間の概念で拡張した話。(続 | |
| #etaps2014 基本アクションに「これくらいの時間を掛ければこの確率で成功」というt→p分布を割り当てられる。andをsequential-andにできる。この確率分布は有限状態のDAGの状態遷移で表現することで合成可能でシナリオ全体の分布などが計算できる。 | |
| #etaps2014 指数分布の一般化みたいなのを http://en.wikipedia.org/wiki/Phase-type_distribution で表現できてそれの状態の最小化とかが何かマセマティカリーかっこよかった。去年の Xmas Contest http://hos.ac/contest/xmas2013/ の問題F思い出す。 | |
| @john_229 じゅぬせぱふらんせ | |
| #etaps2014 "Dynamic field access (DFA)" この業界の人はなぜ形式言語と略語をかぶせる趣味があるのか | |
| @chiguri 混同がない状況なら短い略語が他と一致してもまあ別にいいかなとは思っているのですが。この研究JavaScriptの文字列によるフィールドアクセスを適宜述語抽象して静的解析するというものなので、いつ決定性有限オートマトンがでてきてもおかしくない話なのがすごい | |
| #etaps2014 CC11件目: JavaScriptのobj["field"]みたいなアクセスが何を指しているか静的解析するために、文字集合や長さや'_'などの重要な文字の位置や最後の手段適当なハッシュで文字列を有限領域に落として抽象解釈するお話。まあ頑張っている |