netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2004-04-30 古い日記からの変換データ [長年日記] ▲
_ 論文 ▲
Tamara Munzner:H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space.
ノード数は指数的に増えるが，ユークリッド空間は多項式でしか増えないので空間が足りない，だから hyperbolic space 上で配置して，Focus+Context view というユークリッド空間への写像として扱う．
関連研究はいろいろ．2Dでノードを階層的に配置するもの，平面上にビルのように積み重ねていくもの，3Dで木を描画するものなど．
基本はグラフから spanning tree を構築してあるノードから隣接したノードを球面上に配置していって，それらを回転させて見ていく，という感じ．
意外とグラフ表示関係のアルゴリズムはたくさんあるらしい．
_ 論文 ▲
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 の特徴が簡単に説明されているので親切な論文．
