netail.net

_ 読書 ▲

紅茶を買うついでに買ってきた，アン・マキャフリィ，パーンの竜騎士外伝３「ネリルカ物語」読了．ということで，これでパーンの竜騎士シリーズの日本語訳はコンプリートしたことになる．あとは手を出すとしたら，未訳の資料集系だろうか．

_ 紅茶 ▲

祝ダージリン・ファーストフラッシュ発売．ということで，今年はアリヤ 50g，去年個人的に大当たりだったミリクトンを50g を購入．どうやら，農園指定のは入荷量が 150kg 程度に限定されているらしい．たぶん，来月頃には売り切れてるだろうから，ちょっと残念だ．かといって，好みとは限らないので100g 単位で仕入れる気にもならない．

定番となりつつあるディクサムも仕入れて，紅茶代金は5000円．

帰って早速アリヤを試飲してみたが，かなりいい感じ．ミリクトンとどっちがいいかな？

_ 論文 ▲

Tamara Munzner:H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space.

ノード数は指数的に増えるが，ユークリッド空間は多項式でしか増えないので空間が足りない，だから hyperbolic space 上で配置して，Focus+Context view というユークリッド空間への写像として扱う．

関連研究はいろいろ．2Dでノードを階層的に配置するもの，平面上にビルのように積み重ねていくもの，3Dで木を描画するものなど．

基本はグラフから spanning tree を構築してあるノードから隣接したノードを球面上に配置していって，それらを回転させて見ていく，という感じ．

意外とグラフ表示関係のアルゴリズムはたくさんあるらしい．

_ Calendar ▲

hyCalendar 0.7.3 が Vector で公開された．

こちらが送るの忘れていたのに，更新してくださったのだろうか．感謝 :-)

_ 論文 ▲

Davide Balazarotti, Mattia Monga:Using Program Slicing to Analyze Aspect Oriented Composition.FOAL 2004.

プログラムスライスでアスペクト間の干渉を検出しようという Position Paper．A1, A2 というアスペクトがあるとき，それらをスライス基点として計算した S1, S2 がA1 ∩ S2 = φ なら干渉なし，とする方法．ただし，スライスが正確でないと（冗長なコードを含むと）false positive が出てしまうし，誤ったスライスを計算してしまうとfalse negative が出てしまう．いちおうスライスツールを作っていて実際的な AspectJ プログラムに適用可能なJava バイトコードスライスを計算できるようにしたい，としている．スライスはどんどん発散してしまうので，効果のほどは謎．

_ 論文 ▲

Kiarash Mahdavi, Mark Harman, Robert Mark Hierons:A Multiple Hill Climbing Approach to Software Module Clustering.19th IEEE International Conference on Software Maintenance (ICSM 2003), pp. 315-324, Amsterdam, The Netherlands, 22-26 September 2003.

モジュール間の接続を重み付きグラフで表現したものを入力として，モジュールのクラスタを再構築する．評価関数は i = モジュール内部辺の重みの総和j = モジュール外部辺の重みの総和各モジュールについて，MF = i / (i + j/2 )全体の評価関数 MQ = Sum of MFと定義する．実験では，重みとして関数呼び出しや変数参照の回数を取っている．

ただし，MQ は正規化されていないので順序値としてしか使えないらしい．なので，改善度合いの評価については微妙．MQ がどのくらいよくなったか，ということから実際のモジュール構成がどのくらいよくなったか，という直接的な評価ができない．

_ 論文 ▲

論文というよりは article だが．

David Evans, David Larochelle:Improving Security Using Extensible Lightweight Static Analysis.IEEE Software January/Feburary 2002, pp. 42-51, 2002.

Splint（以前はLClint と呼ばれていたもの）の実装に関するお話．NULL ポインタによる問題やリソース解放忘れ，バッファオーバーフローなどを防ぐために，/* @notnull */ のような annotation をプログラムに付加しておいて手続き単位でのフロー解析を行うというもの．基本は pre/post condition 間の接続チェック．バッファオーバーフローに関しては，間違いやすい gets などの関数を使っているかどうか，というのと引数のバッファ長が文字列より長くなり得るかどうか，といった検査を行う．このあたり，かなり heuristics を入れて実用性の維持を重視しているらしい．false positive と false negative と両方出るが，false positive/negative のどっちかをなくすために実用性を失うのは嫌だ，ということで警告メッセージの一部をフィルタするといったことで対処しよう，ということらしい．

_ 論文 ▲

Jinlin Yang, David Evans:Dynamically Inferring Temporal Properties.ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tols and Engineering(PASTE 2004), Washington, D.C., June 7-8, 2004.

プログラムの実行系列（イベント列；基本はメソッド）からパターンを認識しよう，というもの．ここでのパターンは，いくつかのテンプレートのマッチで，関連研究の中には機械学習の手法やErnst, Cockrell, Griswold, Notokin によるDynamically discovering likely program invaliantsto support program evolution.などが挙げられている．

イベントパターンのテンプレートとしては，Response (Pが起こった後には，必ずSが起きる）　-- SPPSS は OK だが SPPSSP は不可OneEffect (Pが１回以上起きたら，１回だけ S が起きる） -- SPPS は OK だが PPSS, SPSS は不可といったものを用意して，P と S として使うイベントを選んで，それが複数のイベントトレースでどのくらい出現するか，ということを調べて，推論する．イベント列の順序について甘いのは，並行性を強く意識しているためのよう．

いちおう Producer/Consumer パターンで小さな実験をして，イベント間の関係をそれなりに認識できているみたい．しかし，大規模システムでは，多数のイベントが発生するので，P, S の組み合わせをどうするか，また大量の実行履歴に対するマッチをどうするか，という問題を抱えている．このあたりはさすがに position paper っぽい．

_ 論文 ▲

M. Daoudi, L. Ouarbya, Mark Harman, Chris Fox, M.P. Ward:ConSUS: A Scalable Approach to Conditioned Slicing.

conditioned slicing は，入力パラメータなどに対する特定の条件を与えて "conditioned program" を生成して，その上で静的スライス計算を行うことで，特定の条件に対するプログラムだけを抽出してくるというもの．

というわけで，重要なのは，与えられた条件に対してその条件を伝播させていく Symbolic Execute というステップ．制御フローをたどりながら，if, while, assert などを，常に true/false となる場合に限って，簡略化していく．

問題は，どのくらい時間がかかるのか，ということだが，色々な　if 文の構造を自動生成してコードサイズごとにどう変化していくかをテストしている．グラフを見た限りではだいたい n の自乗ペースで，多項式時間なのでまあ reasonable ではないか，と言っている．意外と時間がかかってないといえばかかっていない．

conditioned slicing の特徴が簡単に説明されているので親切な論文．

_ [近況] ICSE出張は禁止 ▲

うちの大学では，豚インフルエンザ感染者が発見された国，感染した疑いがある人がいる国への渡航は原則禁止になりました．渡航した場合は帰国後一週間は自宅待機となり，授業とかで大幅に支障が出るので，ちょっとICSEへの参加は無理そうです．今回の duty は ICPC のツールデモだけなので，渡航できなくても，私はそれほど被害はありませんが……．

他の大学でも似たような状況なんでしょうか．