«前の日記(2004-06-16) 最新 次の日記(2004-06-18)» 編集

netail.net

自作フリーソフトや,ゲームに関する雑記を公開してます.
日記はソフトウェア工学の論文ネタが中心です.

最近のお知らせ (古いものはこちら)


2004-06-17 古い日記からの変換データ [長年日記]

_ [論文]プログラム実行の可視化

ICSE 2004 Research (Formal) Demos, Analysis and Visualization より.

Alessandro Orso, James A. Jones, Mary Jean Harrold, John Stasko:GAMMATELLA: Visualization of Program-Execution Data for Deployed Software.Proceedings of ICSE 2004, pp.699-700.

ソフトウェア可視化ツール.カバレッジ計測,データ収集デーモン,可視化ツールのセットらしい.

http://sourceforge.net/projects/insectj

_ [論文]Traits

ICSE 2004 Technical Papers, Object-Oriented Programming より.

Andrew P. Black, Nathanael Scharli:Traits: Tools and Methodology.Proceedings of ICSE 2004, pp.676-686.

Traits というプログラミング言語のお話.クラスのメンバー群をクラスとは別単位で固めておけるというだけなのだが.

ECOOP2003のときの論文に比べると,開発環境まわりの話が主体に見える.Traits Browser とかいうツールでメンバーの管理などができるらしい.前に読んだとき

Agile系の話が少し加わっていて,リファクタリング時などには,関連しあったメンバーの集合をクラスから分離しておくと便利だ,とかいう話が増えている.Subject-Oriented Programming なんかにも近い話だと思うのだがそのあたりの話は出て来ず.

_ [論文]リンク解析によるクラス分類

ICSE 2004 Technical Papers, Object-Oriented Programming より.

Alexander Chatzigeorgiou, Spiros Xanthos and George Stephanides:Evaluating Object-Oriented Designs with Link Analysis.Proceedings of ICSE 2004, pp.656-665.

井上先生の論文が引用されているのだが論文タイトルがなぜか抜けてたりしてけっこういい加減…….

Component Rank は汎用コンポーネントの発見が目的だが,こちらはシステムの設計上の問題点を見つけることが目的らしい.

メインは,クラス間のリンク情報を使ってクラスの分類をしましょう,という論文."オーソリティ" (色々なクラスから参照されるクラス)と"ハブ" (色々なクラスを参照するクラス)という概念を使って,クラスをグループ化する.

お互いに(密に)参照しあっているようなクラス群が存在するとそこをグループとして取り出すことになる.インタフェース使って厳しく抽象化されてしまっても,特定のインタフェース群を参照しているグループが取り出せる.グループといっても3,4個のクラスから構成される小さなものだが.

"fat interface" アンチパターンみたいに責任が集中しているとクラス群が全部固まって出てくるから責任を分散させよう,みたいな話になるのか.どのくらいで集中したら問題,という話がないのでよく分からない.

_ [論文]生成されうるSQLの静的チェック

ICSE 2004 Technical Papers, Static Analysis より.

Carl Gould, Zhendong Su, Premkumar Devanbu:Static Checking of Dynamically Generated Queries in Database Applications.Proceedings of ICSE 2004, pp.645-654.

プログラム中で動的に生成されるSQL文を静的にチェックしたい,という動機の論文.チェックの対象は,生成される文がSQLとして正しいかどうか(構文)と,生成される列名や値の型が正しいかどうか(意味).

生成されうる文字列をオートマトン表現に落として,Context-Free Language Rechability という方法を使ってテストする.アルゴリズムの計算量は O( |s|^3 + |D|^3 ) .ここで,|s|はアルファベットの種類数,|D|はグラフサイズ.ただ,一般にはSQL生成のオートマトンは小さいので,実験で使われた最も大きいもの(1300ノード程度)でもたかだか数分で検査が終了している.

動的生成されるHTML検査の研究などに立場は近い.SQLのほうが,アプリケーションごとのデータベーススキーマの情報が使えることと,SQL自体が長くなることがあまりないので有利という気はする.

また,きちんと型検査などもしているので,たとえば列名ごとの型チェックだとか(String 型の列を間違って Integer として取り出したりとか)にも応用が利くだろう,とも言っている.このあたり,使えるとけっこう便利な技術ではある.ちょっと false error も出てしまうので悩ましくはあるが.

_ [論文]モデルチェックへのヒューリスティックの導入

ICSE 2004 Technical Papers, Static Analysis より.

Jianbin Tan, George S. Avrunin, Lori A. Clarke:Heuristic-Based Model Refinement for FLAVERS.Proceedings of ICSE 2004, pp.635-644.

FLAVERS という名前のモデルチェックの話.特定の性質が成り立つかどうかを,プログラム実行中のイベント列を受理するかどうかという有限オートマトンとして表現しておいて,プログラム側から自動生成した Task Flow Graph (プログラム実行中に発生するイベントをノードとして,その発生順序関係を辺とするようなグラフ)上のパスがオートマトンの条件を満たすかどうか,ということになるらしい.

ただ,グラフ上にはパスが作れても「実際には起こらないパス」というのが登場してくる.

これを削るために,イベント間の制約であるTask Automata(実行スレッドごとに分解したTask Flow)を使うが,チェックするべき制約が少なすぎるとパスの除去に失敗し,多すぎると無用にコストが増大していくという問題がある.

そこで,ヒューリスティックを使って,必要なオートマトンを適当な数だけ選び出そう,ということになる.特定のタスクでしか使われていないイベントがある場合はそのタスクを選び,また,複数(通常2つ)が同期したイベントではカバーしてないイベントの個数が多いものを選ぶ,といった具合でイベントを一通りカバーするようなタスクセットを選ぶと80%くらいの正確性となり,コスト対効果が良くなるらしい.

_ [論文]ソース解析ツール DMS

ICSE 2004 Technical Papers, Static Analysis より.

Ira D. Baxtor, Christopher Pidgeon, Michael Mehlich:DMS(TM): Program Transformations for Practical Scalable Software Evolution.Proceedings of ICSE 2004, pp.625-634.

筆者たちが DMS という名前の商用のソース解析ツールを作っているらしく,その中身を紹介している論文.

ソースコードを高速に解析することで大規模なソフトウェアにも適用可能なツールにしました,という話.COBOL や C,Java などが相手で,機能としては,コードクローン検出,プリプロセッサ命令の部分評価,カバレッジ計算,DTD に対応したパーサの合成など.

高速化の工夫としては,できるだけ並列に処理できるようにするとか,構文の書き換えルールを使って,たとえば A = A + 1 を A++ に置き換えるような形で,ソースコードの表現をまとめていくとか,LR文法で,解釈候補が複数あった場合に並行して処理するGLRという手法を使ったりとか.

研究や開発のインフラとして,この種の解析プラットフォームが必要だろう,という立場のよう.Conclusion のところに50人年で8年くらいかけてる,とか書いている.このプロジェクト管理能力はすごい.

お名前:
E-mail:
右の画像に書かれている文字列を入力してください:
コメント: