netail.net
自作フリーソフトや，ゲームに関する雑記を公開してます．
日記はソフトウェア工学の論文ネタが中心です．
最近のお知らせ (古いものはこちら)
2002-09-14 古い日記からの変換データ ▲
2005-09-14 ▲
_ ESEC/FSE 2005 サマリ ▲
参加者 251人（うち学生111人，28カ国）．Conference本体だけの人は147人（学生47人）．
Proceedings は全部で350kg超．Organizing に働いた人は65人以上．
採録論文数は，201本中の32本．
ツールデモは，21本中の8本．
Doctoral Symposium が12本中6本．
ワークショップが17個中6個．
チュートリアルが25個中8個（ただし，そのうち開催されたのは2個）．
ACM SIGSOFT Ditinguished Paper Awards は以下の３本．
- Martin P. Robillard: Automatic Generation of Suggestions for Program Investigation.
- Yichen Xie, Alex Aiken: Context- and Path-sensitive Memory Leak Detection.
- Koushik Sen, Darko Marinov, Gul Agha: CUTE: A Concolic Unit Testing Engine for C.
個人的には，最初の Keynote Talk とか，Software Evolution Analysis のセッションとか明示的に Evolution と言っている人たち以外でも，リポジトリから過去の変更の様子を調べてバグ発見に役立てようとか，Evolution 系でよく聞くようなお話が増えてきている気がした．
_ ESEC/FSE Keynote メモ ▲
- Keynote その１. Oscar Nierstrasz: The Story of Moose: A Language Independent Reengineering Environment.
前半は Reengineering の特徴の話．
ソフトウェアの保守作業と呼んでいるものは，60％くらいが機能の追加，25％くらいがバグフィクスで，"continuous evolution" だというのが正しい．変更しなければ，そのソフトウェアが徐々に役立たずになっていくだけ．
legacy system は，価値があるものの，知識が失われており，アーキテクチャや設計が変化したりしていて，変更が困難である．extract design, identify components といった研究は，これに対処するためのものだと言える．
で，reengineering では，コード→設計→要求→変更された要求→変更された設計→変更されたコードというように，コードから始まってコードに帰っていく特徴を持つ．
スタート地点として，まずはソフトウェア内のエンティティ群から，メトリクスなどをもとに特別な(exceptional)エンティティを発見しておき，そこから詳細なモデルの獲得，コードクローンの検出，責任の再配分(redestribute responsibilities)，コード変換と進む．
後半は，Reengineering を支援するために作った MOOSE という環境の話．Java や C++ といった言語から中立なモデルを作ってツールの integration を可能にすること，entity のグループも entity とすることで階層的なエンティティの取り扱いを可能としていることなどが特徴．また，smalltalk のような動的言語を使って，entity に直接様々な働きかけをできるような環境も有用である，と言っていた．
- Keynote その２．António Câmara: Innovations in Pervasive Computing.
日本でいうところのユビキタス環境に近いお話．
主役は携帯電話とか無線タグ(RFID)で，色々なサービスが作れる．たとえばタグの物理的な位置の識別を使ったサービスであれば，タグを持っている人の位置情報と，どの場所に人がいるかの他のセンサーからの情報との一貫性をチェックすることで侵入者を検知したり，行きたい場所へのナビゲーション情報を提示したり，何らかの資産が無許可で移動させられようとしているのを検知したり，といったものが考えられる．
その他，消防士であれば通信デバイスや位置・周辺環境・体調に関するセンサを付けて消防車や病院などと情報を交換するとか，運動選手ならやはり体調や外気温などのセンシングをしたりとかいった intelligent garment のような応用があるといったように，今後数年でこのような応用がある，という紹介系な話だった．
- Keynote その３．Jeff Kramer and Jeff Magee: Engineering Distributed Software: A Structural Discipline.
こちらは分散アプリケーションと，アーキテクチャ記述言語の関わりについてのお話．モデリングによって実際のアプリケーションの複雑さを抑えて解析を容易なものとし，プロセス代数として構造(structure)や振る舞いを合成する combinator を用意してデッドロックや一貫性のない状態への到達を検出する．
オブジェクトの管理の例として，オブジェクトの active/passive 管理を挙げており，active （処理を実行中）のオブジェクトはたとえ破棄される命令が来ても，処理が終わって passive に戻るまでは途中で消滅したりできないようにすることで，データの一貫性が保持される様子を紹介していた．
_ [論文]ESEC/FSE セッションメモ１: Change Impact Analysis ▲
プレゼンで聞いた話ベースなので，詳細は論文自体を読む必要あり．
- Martin P. Robillard: Automatic Generation of Suggestions for Program Investigation.
プログラム要素間の接続グラフに対して，ユーザが調べたい要素名をいくつか与えると，それに関連した注目すべき要素だけを取り出すというシステムの構築．たとえば allocated フィールド，allocateFiles，getAllocated，setAllocated メソッドを入力として指定すると，それらを使っているようなメソッドが候補として紹介されることになる．
推薦の基準は，Specificity と Reinforcement．Specificityとは，入力で与えられた要素集合だけに関連しているものは，他の要素にも関連を持っているものよりは優先度が高くなるということ．また，Reinforcementとは，入力で与えられた要素集合のに対して多くの関連を保持しているものを，関連が少ないものよりも優先するということ．
関連としては，calls, called by, accesses, accessed by を使って，それぞれについて個別に推薦を出すらしい．同じ要素に，複数の関連から推薦が来た場合は，範囲の値なので f(x, y) = x + y - xy で merge する．
ケーススタディでは，推薦されたアイテムをチェックして，上位に関連したものが固まりやすい傾向があることを確認している．
- Bill McCloskey, Eric Brewer: ASTEC: A New Approach to Refactoring C.
C言語のマクロには文法がなく，扱いにくいが，実際に使われているほとんど(著者らによれば99％)のマクロは構文的に完全な文や式が来ることが前提になっているので，そういう制約を付けたC言語用のプリプロセッサを作ってみた，という話．マクロの引数の型として，文や式が選択できるようになっている．また，言語を定義すると同時に，従来のマクロを新しい言語上に自動変換するツールを作っている．基本的には，どこを展開したか記憶しながらマクロを展開→構文木を構築→展開後の構文木からその展開されたマクロの型情報を取得→展開していた部分を徐々にマクロに変換していく，という形式．
- Thomas Henzinger, Ranjit Jhala, Rupak Majumdar: Permissive Interfaces.
ライブラリに対して，どんなメソッド呼び出し列が許されるのかを自動分析しましょう，という話．
ライブラリの中にある状態変数を選択すると，関数呼出しごとにそれらの値の範囲がどのように変わるかをチェックして，型付きの有限状態オートマトンを構成する．状態変数の指定を間違えていた場合，正常状態とエラー状態とが同じ条件を保持してしまうので判別可能だったりするらしい．引数のことは考慮してないようだが．
_ [論文]ESEC/FSE セッションメモ２: Patterns and Aspects ▲
- Murali Haran, Alan Karr, Alessandro Orso, Adam Porter, Ashish Sanil: Applying Classification Techniques to Remotely-Collected Program Execution Data.
プログラムの実行履歴ごとに実行の成功・失敗をラベル付けしておき，モデル学習を行っておくことで，新しい実行履歴に対してそれが成功だったか失敗だったかを自動分類する．
モデル学習には，tree-based classifier（分類木？）を作成．複数の木を作ってから多数決を取る "forest" を構成することで，tree の不安定性は克服できるらしい．で，この分類の実現にはどんなデータが必要かを調査している．
データとしては，プログラム中の各ブロックあるいはメソッドが何回ずつ実行されたか，あるいは例外が何度投げられたかの記録を使っているのだが，実際に集めてみたら，あまり性能に変化は出ず，集めるのが簡単なメソッドの実行回数ベースで良いようだ，ということになったらしい．また，計測するメソッドの数を何％か減らしても，性能が急激に劣化したりはしないようで，メソッド呼び出し回数を，ランダム選定した10％くらいのメソッドだけに対して集めただけでも pass/fail の２値分類はできるようだ，と述べている．
- Hamid Abdul Basit, Stan Jarzabek: Detecting Higher-level Similarity Patterns in Programs.
Structural Clone を見つけよう，という論文．Structural Clone は，相互にクローンであるようなコード片の集合（Clone Class）ごとに割り当てられた ID の列．「クローン A のコード片が１個とクローン B のコード片が２個同時に登場することが多い」といったパターン．例としては，Java Buffer Library を挙げていた（似たような構造を持ったクラスが多いため）．
質疑応答では，クローン検出しなくても名前などだけからでも似ていると分かるものもあるのでは？というのに対して，ファイル名などが似ているから中身がコピーとは限らない場合がある，といった答えをしていた．また，「コードクローンなら同時に直さないといけないというのであれば，同時に変更されているかどうかの情報を集めたほうが早くないか」とも聞かれていた．クローン検出は別にそれだけのために使われるわけではないと思うけど．
- Kevin Sullivan, William Griswold, Yuanyuan Song, Yuanfang Cai, Macneil Shonle, Nishit Tewari, Hridesh Rajan: Information Hiding Interfaces for Aspect-Oriented Design.
アスペクト指向プログラミングでは，横断的関心事を修正するときはアスペクトだけ直せばよいが，アスペクトが貼りつく対象となるクラス群のどれかが変更されても，アスペクトの修正を検討しないといけなくなる．これでは困るので，クラスよりも先にまず抽象的な "Pointcut interface" を用意しておいて，それをクラスが実装して，またアスペクト側はそのポイントカットを利用するという形にできないか，と提案している．
_ [論文]ESEC/FSE セッションメモ３: Software Evolution Analysis と Tools から一部 ▲
- Miryung Kim, Vibha Sazawal, David Notkin, Gail Murphy: An Empirical Study of Code Clone Genealogies.
ソフトウェアのバージョン間のクローンの変化を調べてみました，という論文．ローカルな修正が困難なクローンがたいてい long-lived クローンとして長く生存し，修正しやすいものは volatile （たいてい５バージョン程度で消滅）であった，という調査結果．
long-lived で，開発者が放っている間に複雑化してしまうことはないのか，と質問をしてみたら，そんなことはないようだ，とあっさり答えが帰ってきた．実は全部手で調べている？
生存期間のバージョン数の数え方が，total lines of code clones が変化したかどうかで決定されているので，少し怪しい印象は受けた．また，volatile なものは，共通化して消してもまたすぐに分岐させないといけない場合があるから放っておいてよい，といった発言をしていた点も，少し気になるところではあった．開発者が努力したから消えたのでは？という気もするが，volatile クローンについては，発生してもすぐにコードとして分岐する例を見たからそう言っているようにも聞こえた．
- Reid Holmes, R.J.Walker, Gail Murphy: Strathcona Example Recommendation Tool.
ツールデモのみ．目的のインタフェースやメソッド名のコード片から，それに似ているコード（実際に使っているコード）の推薦を行う．やはり，弱点は把握しているようで，悪い例を推薦してしまう可能性，それとコピーペーストを促進してしまう可能性がある，と言っていた．とはいえ，面白い試みではある．
- N. Tillmann and W. Schulte: Parameterized Unit Tests with Unit Meister.
普通の Unit Test では，条件分岐などをカバーするようにうまく入力変数を色々作っていかないといけないが，このツールは，パラメータとして変数宣言だけを用意しておくと，条件分岐を一通りカバーするように変数値を準備するテストケースを作ってくれるらしい．やっていることは単なるテスト生成ツールなのだが，その自動設定されるパラメータ変数を使って好き勝手にテスト用コードが書けるので使いやすそうな印象は受けた．
- Robert Chatley and T. Timbul: KenyaEclipse: Learning to Program in Eclipse.
Kenya というのが，Java のクラスなどを省いた手続き風教育用言語らしい．クラス宣言などを取り払ったぶん，簡単に言語が学べるようにしようという試み．実行時にはJava にコード変換される．個人的には Pascal の置き換えなのかも，と思った．
このツール自体は，Eclipse 用の Kenya 開発環境で，スタイルチェッカなどを充実させている．色々な開発ツールを使いながらプログラムを書くことを学べるようにしたい様子．IDEを使うとコマンドラインの使い方が分からないとか，「スタイルチェッカが直してくれるから」とそれに依存したコードを書いてしまわないか，といった懸念はある，としていた．
_ [論文]ESEC/FSE セッションメモ４: Bug Localization ▲
- Chao Liu, Xifeng Yan, Long Fei, Jiawei Han, Samuel Midkiff: SOBER: Statistical Model-based Bug Localization.
if 文での predicate を，true/false の２値をとるランダム変数と考えて，テストケースに対して true になる確率を計算し，成功テストケースと失敗テストケースで大きくその値が変わるものを疑わしい条件だとする手法．
どのくらい値が変わったかを評価する関数を決めて predicate をランキングすると，大半のバグについてはコードの10〜20％を調べると発見でき，Andreas Zeller らの Cause Transition などと比べても若干良い値が出ていた．ただし，Cause Transition では，成功テストケースと失敗テストケースを１つずつ用意するだけでよいので，１個しか失敗テストケースがない場合は Cause Transition を使い，複数テストケースが集まってきたらこちらの手法に切り替えるのが良い，といった形になっている．
- Benjamin Livshits, Thomas Zimmermann: DynaMine: Finding Common Error Patterns by Mining Software Revision Histories.
ソフトウェアリポジトリから，メソッドの使い方のパターンを探そう，という試み．同時に追加されるメソッドの集合というのはいくつか決まっているので，追加しているメソッドが足りない場合，あるいは呼び出し順序が間違っている場合はルール違反ではないか，と推論する．
情報収集は，リポジトリからリビジョン単位のコード片を取り出してきて，１つのオブジェクトに対するメソッド呼び出しがどれだけ追加されたかを調べておく．で，frequent item set だけを取り出す．{acquire, release} といった集合が取り出されたとき，{acquire}だけを追加したリビジョンと，その前後に{release}だけを追加したリビジョンがあれば，{acquire, release} にしようとした変更だと判断するようなことを言っていた．
見つけられてきたメソッド群に対して，プログラムを実行し，どのような順序でメソッドが実行されるかを調べる．メソッド呼び出し順序については，現在はまだ自動化できておらず，人間が与えないといけない様子．また，実行は単体テストとか，特に限定していないようだが，ちゃんと選ぶ必要があると思われる．
この方法は，「moveを呼んだ後にupdateを呼ぶ」といったパターンが発見できれば，アスペクトマイニングにも使えるかもしれない．- Zhenmin Li, Yuanyuan Zhou: PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code.
lock-unlock, SearchSysCache-ReleaseSysCache のようにペアで使うメソッド呼び出し，var.command = foo; var.driver = bar; のような構造体へ設定する値には，ある程度パターン（しばしばundocumented）が存在する．そのような implicit rule を見つけようという研究．
今までには，事前にルールを定義しておいて後でそれをチェックするというのはあったが，自動で探索するものはなかったらしい．
基本は関数単位で，呼び出している関数名，構造体名，フィールド名の集合で関数を抽象化する（ローカル変数は除外）．
IDを数値で表現したら，たとえば {5, 12, 19, 26} といった集合が関数ごとに割り当てられることになる．で，{5, 12, 19, 26} が19回登場して {5, 12, 19} が20回登場しているなら，if {5, 12, 19} then {26} が confidence 19/20 = 95% として得られる．
また，一連のメソッド呼び出しなどが複数のメソッドに分割されている可能性もあるので，その関数を呼び出している関数へと遡ってから子供の関数の呼び出し列を調べるという作業も行っているらしい（ただ，call path を調べる都合上 dynamic binding なんかには弱そう…）．
ケーススタディでは Linux や PostgreSQL などを対象に適用実験を行っていて，関数群よりもむしろ関数と変数あるいは変数同士といった組のほうが多く見つかったらしい．Linuxでは合計約３万種類ほど．要素数的には，９割方が10個以下に収まっている．ただ，出てきたルールに違反しているであろうと判定された上位60例を取り出してきたとき，Linuxでは16個がバグ，20個が正しい使い方，24個はfalse positive．PostgreSQL では45個がfalse positiveとなっていて，現段階では，false positive 率がけっこう高いのが少し気になるところ．
