netail.net

_ 論文 ▲

論文の大量消化を進行中．

Mark Harman, Lin Hu, Malcolm Munro, Xingyuan Zhang, David Binkley, Sebastian Danicic, Lahcen Ouarbya and Dave (Mohammed) Daoudi:Syntax-Directed Amorphous Slicing.Journal of Automated Software Engineering,11(1): pp.27-61, 2004.

Amorphous slicing は，構文の簡略化を含んだスライシング手法．スライス計算の結果，if 文の条件式が必ず false になるとか，関数の引数が使われないとかいったことが判明したら，if文を丸ごと削除したり，引数を減らした関数定義を作ったりして構文木を保存しない状態でスライス結果を出力する．なので，用途としてはプログラムの簡略化などになる．

計算時間や空間コストはやっぱり n の自乗．500 行のプログラムで，最善で約１秒，最悪で約２分とかいうくらいに極端な差が出るようで，そんなに大規模なシステムに適用できるわけではない．

AST 変換なアプローチを取っていて，依存グラフ構築のアプローチよりも局所的な変換ルールはシンプルになる点が有利らしい．SDG アプローチ側は依存関係の整理には向いている，というように比較が入っているので，この種の比較を引用するには便利そう．

_ 論文 ▲

Lahcen Ouarbya, Sebastian Danicic, Dave (Mohammed) Daoudi, Mark Harman and Chris Fox:A Denotational Interprocedural Program Slicer.9th IEEE Working Conference on Reverse Engineering (WCRE 2002). 28 October - 1 November, 2002. Richmond, Virginia, USA, Pages 181 - 189.

コールグラフなどの構築ではなく，AST の変換によってプログラムスライスを計算しようという方法．

V が注目している変数（スライス基点）だとして，Slice(if B then S1 else S2, V) はif B then Slice(S1, V) else Slice(S2, V) となる，といったような処理を，各時点での変数の最新値を持ちながら計算していく．グラフ構築→ traverse という順序のかわりにいきなり計算しているだけのようにも見えるが．

式における SideEffect のあるなしを考慮している点はえらいかもしれない．関連研究として CodeSurfer を挙げているわりにほとんど比較がないので，この手法の利点がよく分からない．

_ 論文 ▲

Mark Harman, Rob Hierons, Chris Fox, Sebastian Danicic and John Howroyd:Pre/Post Conditioned Slicing.17th IEEE International Conference on Software Maintenance (ICSM 2001). Florence, Italy, November 6th-10th, 2001. Pages 138-147.

Conditioned slicing を応用して，Pre condition からの forward conditioning (Pre condition が成立している状態で実行されるプログラム文）と Post condition の否定からの backward conditioning(Post condition が成立しない状態へ寄与するプログラム文）の共通部分を抽出することで，「pre condition が成り立っているのに post condition が失敗する可能性のある（バグの可能性がある）」文集合を抽出しようというもの．

基本は conditioned slicing で，symblic state expression（システムがとりうる状態）を各プログラム文に対して伝播させていく．

pre/post conditioned slicing が空になるようにコンポーネント抽出を行う，あるいは verification 用途に使う，といったことが主目的となる．assert の積極的な定義と合わせて使えば強力なツールとなりうる？フィールド値などの条件定義をうまく与えないと他の手続きからの影響を除去しきれないかもしれないが．とはいえ，スライス系の研究の中ではかなり面白い部類に思える．

_ 論文 ▲

Mark Harman, Nicolas Gold, Rob Hierons, Dave Binkley:Code Extraction Algorithms which Unify Slicing and Concept Assignment.9th IEEE Working Conference on Reverse Engineering (WCRE 2002). 28 October - 1 November, 2002. Richmond, Virginia, USA Pages 11 - 21.

プログラムスライシングと Concept Assignment を併用することでプログラムを分解しようという試み．

Concept Assignment というのは，プログラム文の集合と Concept を対応付けるというものらしい．これに，各 Concept のプログラム文からスライスを計算することで Concept に関連したプログラム文を得る．また，concept の最終結果となるような変数 (Principal Variable) を最後に使ったプログラム文を重視して，それを基点に計算したスライスに含まれているところを重要度が高い，と分類する．（0から1の実数と定義しているが，　実際には 0と1だけを使っている）

そして，各 concept の Principal Variable の最後の利用場所から計算したスライスの共通部分の大きさによって concept 間の依存性を解析する．で，concept 間の関係を重み付きグラフとして出力する．

いちおうケーススタディとして小さなプログラムを相手に計算を行って，どの文が重要か，というところは計算している．しかし，concept 間の関係については，得られた結果をどう使うか，という問題がある，concept 同士の依存関係がわかっても，concept 同士の相互の関係がどういうものか分かるというわけではない，としている．

全体としては，こんなので効果があるのかなぁ，という落ち着きのない感じがする．アルゴリズムは丁寧に書いてあるのだが，スライシングや concept assignment の手法についてほとんど言及がないせいかもしれない．

_ 論文 ▲

David Binkley, Mark Harman:A Survey of Empirical Results on Program Slicing.

プログラムスライシングの survey．といっても，ほとんどの論文は読んだことがあったのであまり意味がなかったが，どのデータがどの論文から来たか，というのが分かるという点で便利な論文．

静的スライスはだいたいプログラムを３割くらいに減らせる，とか CodeSurfer はシステム依存グラフを事前計算してしまうのでスライス計算速度自体は早い，とか，dataflow based slicing は10万行ぐらいのプログラムでも相手にできる，とか．

スライシングの方法としてデータフローから計算するタイプとプログラム依存グラフを構築する方法と大きく区別できて，それにサポート技術として context-sensitivity やsummary edge やグラフの集約があるため，条件を対等にして比較することが難しい，と言っている．スライスの応用に関しても，たとえばプログラム理解であれば，単なる静的スライスを使う方法とPre/Post Conditioned Slicing などを使う方法ではだいぶ違った結果になるだろう，としている．

全体としては，プログラムスライシング技術が実用的であるといえるだけの証拠はある，というふうに締め括っている．ちょっと胡散臭い気もするが．何に使うか，という話から始まらないとどの目的にはどのスライス手法が有効，みたいな議論になっていかないので，まだまだ怪しい気がする．

_ 論文 ▲

David Larochelle, David Evans:Statically Detecting Likely Buffer Overflow Vulnerabilities.

LCLint でのバッファオーバーフロー検出機能に関する話．配列ごとに安全に読み書きできる範囲をmaxSet, minSet, maxRead, minRead として保持して，その範囲外になる可能性がある読み書きの文に対して警告メッセージを出す，というもの．

検出方法として，手続き内部で制約を伝播させていく以外にfor ループから，*buf++ のような定型句を見つけてindex や buf がどの範囲を指しうるかを検出する．こんなのでうまくいくのか，という気もするのだが，けっこううまくいくらしい．

C言語だと書き方がある程度決まりきっているからかもしれないが，実例として wu-ftpd や BIND などが上がっていて，きちんと実験しているツールなので，説得力もある．

_ 論文 ▲

David Evans, John Guttag, James Horning, and Yang Meng Tan:LCLint: A Tool for Using Specifications to Check Code.Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering.pp.87-96, New Orleans, Louisiana, United States, 1994.

論文というよりは LCLint の説明ドキュメントか．「こういう spec を書くとこういうエラーが検出できます」という見本集のような印象．

_ 論文 ▲

L.C.Briand, Y.Labiche, J.Leduc:Towards the Reverse Engineering of UML Sequence Diagramsfor Distributed, Real-Time Java software.Carleton University, Technical Report SCE-04-04, April 2004.

AspectJ Users ML で，「loop や if 文を検出するpointcut がほしい」と言っていた研究者の論文．

やってることは実行履歴からのシーケンス図の復元．contribution としては復元方法についてきちんと仕様として明記したこと．他の手法は形式的な記述が少なく詳細も十分でない，らしい．

スレッドIDとどのメソッドが実行されているか，とどのループや if 文が実行されているか，という情報を合わせて使って，プログラムの動作を追跡する．

分散環境についてもきちんと考えていて，RMI は呼び出し時にブロックするのでノード（JVM）ごとに local clock を１個だけ保持しておけばRMI に関しては呼び出し側の node ID + client thread ID を覚えておけば remote 側の呼び出し履歴と対応が取れる，ときちんと説明しているあたりはえらい．# 非同期な呼び出しは想定していないとも言うが……．

スレッド間の同期方法については，Runnable.start および run の呼び出しの監視が基本．データ構造を介した非同期な情報のやりとりについては，（開発者は組織などの標準的情報を持っているはずなので）どのクラスがスレッド間の情報転送に使われるかを設定ファイルとして用意するらしい．何か参考になるかと期待していたのに，がっかり．

実現方法について，AspectJ のソースコード風に表現しているところが親切．「AspectJ の future release では loop や if を　検出する pointcut が入る可能性がある」と書いてるあたりはいい加減だが，東工大の千葉先生のグループの Josh とかを使って自前で実装するぶんにはできるだろうし．

一通り目を通してみて，実際にはシーケンス図作ってないなーと思ったら論文タイトルの "Towards" に気づいてがっかり．ステレオタイプの "boundary" とか "control" とかまで書いてある図が一つあって「こんなのまで識別してるのか！」と期待してしまったが，単に設計書からのコピーだった．うーむ．