ハウテレビジョン開発者ブログ

『外資就活ドットコム』を日夜開発している技術陣がプログラミングネタ・業務改善ネタ・よしなしごとについて記していきます。

ICSE 2017 論文リーディング

弊社ハウテレビジョンでは、週の1日をR&D dayとして、業務と直接関係しない技術を学んでみたり、今まであまり触れてこなかった領域を調べたりしています。

f:id:itamisky:20170403103601j:plain

背景

最先端の研究を知るのに、カンファレンスの論文を読むのは有効な手段です。
直接役立つことは多くないですが、理論を応用できたり、今後どんな技術が出てくるのかを知ることができます。
何より楽しいです。

そこで今回は、ソフトウェア工学系のトップカンファレンスであるICSE(International Conference of Software Engineering)の論文をざっくり読んでゆきます。

折角なので、まだ開催されていない(2017/05月開催)ICSE 2017の論文を読みます。
まだなのにどうやって読むの?と思いますが、Preprintsとして事前に論文を公開してくれている場合があるので、それを利用します。
公式Twitterによると、おおよそ66%の論文がpreprintsとして集まっているようです。すごい。
https://twitter.com/ICSEconf/status/841892455809187840

preprintsはこちらに掲載されていますので、原文を読みたい方はこちらから辿ってください。
https://docs.google.com/spreadsheets/d/19rjBeNklsfFdggZ7Xj2h1oNpIXfZuR-hYrSQrk4xCfc/edit#gid=1276835202

注意

  • ICSEの全論文ではありません
    • 9つだけ
    • Technical Research Papersの中で、preprintsが公開されているもの
  • タイトルとアブストだけ読むため、手法の詳細には触れません

論文内容まとめ

Analyzing APIs Documentation and Code to Detect Directive Defects

http://www.zora.uzh.ch/134450/1/YU-ICSE.pdf

著者: Yu Zhou, Ruihang Gu, Taolue Chen, Zhiqiu Huang, Sebastiano Panichella and Harald Gall(南京大学・ロンドン大学・チューリッヒ大学)

概要の大雑把な訳:
APIドキュメントは開発者にとって最も重要なドキュメントだが、よくソースコードとずれが生じており、開発の効率や品質に関わる問題になっている。
本論文では、ソースコード理解と自然言語処理を利用し、自動でこのずれを検出する方法を提案している。
手法としては、引数の制約(NonNull、型など)と吐く可能性のある例外に関するAPIドキュメントの記述を利用する。
この内容を用いて、制約ソルバを使ってずれを検出する。
JDK1.8のAPIに対して実験し、2000 APIの中から1146個のずれを検出した。
プレシジョンは81.6%、リコールは82.0%となり、実際に使えることを示した。

感想: ドキュメントとずれている状態はよく直面する。ぜひとも早く普及して解消されて欲しい。ドキュメント中に「ずれてますよ」というマークがあるだけでも便利そう。

An Unsupervised Approach for Discovering Relevant Tutorial Fragments for APIs

http://oscar-lab.org/paper/icse_17_frapt.pdf

著者: He Jiang, Jingxuan Zhang, Zhilei Ren and Tao Zhang(大連大学、遼寧省の研究所、武漢大学、ハルビン工程大学)

概要の大雑把な訳:
開発者はどんどんAPIチュートリアルに頼るようになっている。
しかし、不慣れなAPIの中からチュートリアルのコード片を探すのは未だに困難である。
既存手法では、大量にコーパスを手動で作る必要があり、悩まされていた。
本論文では、FRAPT(APIをページランクとトピックによりコード片をリコメンドする)というアプローチを取り、自動で行えるようにしている。
FRAPTでは、APIに関連するチュートリアルとなるコード片を決定する上で生じる2つの課題に挑戦している。
1つ目は、「代名詞と変数の解像度問題」として、チュートリアルとなるコード片の中からAPIを特定し、抽象的な代名詞と変数をAPI名や即した文脈に置き換える、という問題。
2つ目は、「説明にならないコード片の検出問題」として、不要なコード片を除去するフィルターを作成する問題。
これらの問題を解決し、トピックモデルとページランクアルゴリズムの両方を適用することで相関係数の算出と関連するコード片の集約ができた。
オープンなデータに対して本手法を適用し、既存手法に比べF値で8.77%→12.32%に精度が向上した。
加えて、本手法の核となるコンポーネントの効率性も検証した。

感想: 既存手法でも同様かもしれないが、「開発者はAPIドキュメントのチュートリアルに頼っている」という切り口が良い。チュートリアルはAPIの習熟に大きく関わる要因なので、こちらも実務に直接関わってきそうな内容。

Efficient Detection of Thread Safety Violations via Coverage-Guided Generation of Concurrent Tests

http://mp.binaervarianz.de/icse2017-covcon.pdf

著者: Ankit Choudhary, Shan Lu and Michael Pradel(ダルムシュタット工科大学、シカゴ大学)

概要の大雑把な訳:
並列プログラムを書くのは難しく、困難な問題を隠してくれているスレッドセーフなクラスに頼ることが多い。
これらのクラスのテストは並列プログラムの正確性を担保する上で極めて重要な問題である。
テストの見逃しを減らすため、自動生成した並列テストを作成することは効果的な手法である。
ランダムに作成する既存手法があるが、これは計算コストが高い解析に依存していたり、特定のバグに依存していたりする(アトミック性など)。
本論文では、CovConというカバレッジでガイドしてテストを作成する手法を提案する。
2つのメソッドをペアにして、それらがどれくらい並列に実行されたかを計測し、その頻度に着目する。
本手法では特定のバグのパターンに依存するものではなく、あらゆる並列実行時のバグを検出できる可能性がある。
また、計算コストが高くなく、短時間で多くのテストを生成することが出来る。
本論文ではCovConを18個のスレッドセーフなJavaのクラスに適用し、17のバグを見つけた。
既存の5つの手法に比べ、CovConは短時間でかつより多くのバグを見つけた。
詳細には、38/47のケースでより早くバグを見つけ、22/47のケースでは4倍近い速度で検出をした。

感想: 手法としてはシンプルに見えるが、検出精度も速度も大きく向上しているらしく意外性がある。スレッドセーフなクラスには多くの人が頼っていると思うので、その裏側で日々研究がされているのを見ると面白い。

RClassify: Classifying Race Conditions in Web Applications via Deterministic Replay

http://www-bcf.usc.edu/~wang626/pubDOC/ZhangW17.pdf

著者: Lu Zhang and Chao Wang(バージニア工科大学、南カリフォルニア大学)

概要の大雑把な訳:
競合状態はWebアプリケーションでよく発生するが、原因を突き止めるのが難しく、修復するのも難しい。
既存の競合状態検出ツールはあるが、「ニセの検出(false positive)」が大量に出る。
ニセの検出とは、bogus(実際にはまず起こらない)、benign(エラーを引き起こさない)の両方を示す。
手動でこれらの検出結果を調べることは大変で間違えやすいため、これらの検出結果を提示することは非生産的である。
本論文ではプラットフォームに囚われない、決定性の実行に基づいた手法により、実際に起こり有害な競合状態を特定する。
手法としては、競合するイベントのペアを2つの異なった順番で実行し、プログラムの状態に及ぼす影響を評価する。
ここでは、「有害な競合」を (1)両方のイベント実行が実行完了すること、(2)それぞれが異なった状態を生み出すこと、という両方の条件を満たすものと定義する。
Fortune500の企業で使われている大規模で実際に使われているWebサイトに対して本手法を適用し、既存の手法を大きく上回る効果を示した。

感想: 概要だけでは詳細は分からないが、実際にかけてみやすい類のツールなので、公開されていたら類似ツールも含めて試してみよう。

Repairing Event Race Errors by Controlling Nondeterminism

http://cs.au.dk/~amoeller/papers/eventracecommander/paper.pdf

著者: Christoffer Quist Adamsen, Anders Møller, Rezwana Karim, Manu Sridharan, Frank Tip and Koushik Sen(オーフス大学、米サムスン研究所、ノースイースタン大学、カリフォルニア大学バークレー校)

概要の大雑把な訳:
モダンなWebアプリはイベントドリブンで書かれており、イベントハンドラが非同期にユーザーやシステムのイベントを処理する。
このスタイルでは、非決定性が致命的なエラーを生じさせうる。
近年の研究ではイベント競合とその分類(有害かそうでないか)にフォーカスをしている。
しかし、ソースコードをこれらの競合が起こらないようにするのは難しく間違えやすいため、よくない実行をさせない方が望ましい。
本論文では、JavaScriptで書かれたWebアプリケーションで発生するイベント競合を自動修正する手法を提案する。
この手法では、イベントを後で実行させたり破棄して競合を回避する、というポリシーを適用するため、イベントコントローラーを用意しブラウザ内のイベントハンドラのスケジューリングを制限する。
本手法はEventRaceCommanderというツールにし、Fortune500の中で大きな20のWebアプリケーションに対して適用し、100以上のイベント競合を検出した。
アプリケーションに依存しない修正ポリシーは、パフォーマンスやユーザー体験を大きく損なうこと無く十分にイベント競合を解消したが、特定の修正ポリシーを定めた方が望ましい場合もある。

感想: 1つ前の論文とは別のアプローチで競合状態に挑んでいる。スケジューリングの方法がかなり複雑になりそう。実行時に発生させないようイベント自体をずらすのは面白いが、逆に分かりにくいバグの原因が増えてしまいそう。

TRAVIOLI: A Dynamic Analysis for Detecting Data-Structure Traversals

https://rohanpadhye.github.io/travioli/paper.pdf

著者: Rohan Padhye and Koushik Sen(カリフォルニア大学)

概要の大雑把な訳:
トラバーサル(機械的に一部・全部のデータを辿る処理)はデータ構造に対する最も基礎的な処理である。
本論文ではTRAVIOLIという動的解析でトラバーサルを検知するツールを提案する。
ここでは、ループや再帰の中にある、配列やリスト・木などのトラバーサルを正確に検出することを可能にする、非環(acyclic)な実行コンテキストを導入する。
本論文では、「どのようにTRAVIOLIの実行結果をデータ構造のトラバーサルの可視化に利用するか」「パフォーマンスの劣化はどの程度か」「無駄なトラバーサルによる性能劣化の検出をどうするか」について説明する。
実際に使われている5つのJavaScriptのプログラムに適用し、誤検出は4%以下だった。
検出したうちの93.75%にパフォーマンステストを行った(訳注: 結果は概要にはない)。
また、D3とexpressに性能劣化を検出した。

感想: 面白いテーマ。概要を読む限り、動的解析だとどうしても誤検出が増えそうだが、どのようにして減らしているのかは読み込まないと分からなさそう。

ProEva: Runtime Proactive Performance Evaluation Based on Continuous-Time Markov Chains

http://www.comp.nus.edu.sg/~david/Publications/icse2017-preprint.pdf

著者: Guoxin Su, Taolue Chen, Yuan Feng and David Rosenblum(ウーロンゴン大学、ロンドン大学、シドニー工科大学、シンガポール国立大学)

概要の大雑把な訳:
ソフトウェアシステム、特にサービスは実行時のパフォーマンスが要求される。
もしパフォーマンスが落ちている場合、再設定によって対策をする。
しかし、その対策が反映されるまでしばらくラグがある。
そのため、現在のシステムを受動的に監視することは勿論大事だが、将来のパフォーマンスを予測することも大事である。
連続時間マルコフ連鎖(CTMC)は時間を区切ったパフォーマンスのメトリクスを算出するのに適している(例えば、ある将来の時間でパフォーマンスの劣化がどれくらい起こりうるかを求める)。
CTMCを活かす上で課題となるのが、遷移率などのモデルパラメーターを実行中に計測すること。
これらのパラメーターはシステムや環境によって頻繁に更新されるため、正確な値を与えるのが困難である。
本論文では、既存のCTMCモデルを、遷移率として不正確で区間の中での予測値を許容するよう拡張したProEvaというフレームワークを作った。
ProEvaは不正確なモデルの出力として、漸近的な式と境界を計算することをコアな手法としている。
精度とオーバーヘッドについても触れている。

感想: 数値予測の理論的な論文なので、読むのは骨が折れそう。サービス監視系のツール開発に特に役立つ内容に見える。

Clone Refactoring with Lambda Expressions

https://users.encs.concordia.ca/~nikolaos/publications/ICSE_2017.pdf

著者: Nikolaos Tsantalis, Davood Mazinanian and Shahriar Rostami Dovom(コンコルディア大学)

概要の大雑把な訳:
ラムダ式はJava8で関数型プログラミングをサポートするため導入され、関数を引数として渡すことで「動作のパラメーター化」を実現した。
既存のコードクローンは異なった動作をするものが大部分(Type2、Type3に分類されるもの)である。
しかし、筆者らの知る限りでは、これらのコードクローンをラムダ式を用いて共通化する研究は無かった。
本論文では、ふるまいの違うコードクローンを、ラムダ式を用いてリファクタリングできるかを調べる手法を提案する。
さらに、大規模なコードクローンのデータセットに対し適用し、適用可能性と、リファクタリングに使われたラムダ式の特徴を示している。
結果、他の手法ではリファクタリングできなかった多くのクローンに対して、ラムダ式を使ってリファクタリングができた。

感想: 普段からよくこの手のリファクタリングはするものの、そういえば研究されてるという話を聞かなかった。いい所を突いた感じがある。リファクタリング提案機能が備わっているIDEが増えているが、この機能が搭載されれば開発の強力なサポートになるのでは。期待。

Characterizing and Detecting Anti-patterns in the Logging Code

http://nemo9cby.github.io/resources/pubs/icse2017_chen.pdf

著者: Boyuan Chen and Zhen Ming Jack Jiang(SCALE Lab)

概要の大雑把な訳:
ログのスニペット(Log.infoやSystem.out.printlnなど)は開発者がソフトウェアに埋め込む。
ログコードが増える度に実行時のコンテキストが増えるが、メンテナンスの負担があり多すぎるログコードは望ましくない(訳注: 例えば、ログの中で出力している変数が無くなったり、NPEになったり)。
加えて、パフォーマンスが落ちたり、ディスクI/Oが増えたりする問題もある。
最近の研究では、効果的なロギング方法がしっかりと定められたコーディングガイドラインは無いとされている。
ロギングに関する先行研究の多くは、「どこに」「何を」ログを取るか、に主に取り組んでおり、「どのように」ログを取るか(ロギングコードの開発・保守性)に取り組んだ研究は非常に少ない。
本論文では、ロギングのアンチパターンを特徴づけ、及び検出を行い、「どのように」ログを取るかの問題に取り組む。
ロギングコードの大部分は対象となるコードの進化に伴い変化してゆき、残りはアンチパターンの解消のために修正される。
本研究では、3つのよくメンテナンスされているOSS(ActiveMQ、Hadoop、Maven)に対し352個のロギングコードに対する変更をチェックした。
その結果、6つのアンチパターンが見つかった。
この発見の有用性を示すため、これらのアンチパターンの検知をするLCAnalyzerというツールに実装した。
LCAnalyzerを使った実験では、リコールが95%、プレシジョンが60%でアンチパターンを発見し、未知のアンチパターンの発見にも使えることを示した。
また、フィードバックを得るため、64の代表的な検出結果を10個のOSSで修正して送った所、46個(72%)が(この時点で)マージされた。

感想: 普段開発する中で、たしかにロギング処理はとっ散らかりがち。実際に論文の先を読むと、「Nullable objects」「Wrong verbosity level」など、よくやってしまうものが多い。たかがログのコードと侮らず、ちゃんとメンテナンスしてゆくことが必要だと考えると、アンチパターンという分かりやすい形でまとめてくれているのはとても有用だと思う。

まとめ

まだまだ面白そうな論文がありますが、ここで一旦終わります。
ソフトウェア工学という分野の特性か、上記9つの中でも実用的な内容が多く、実際に使われるイメージが持てるものが多かったです。

ぜひ、上記概要で気になった論文があれば原文を読んでみてください。 また、残りの論文もタイトルを眺めて、面白そうなものを探すと良いかと思います。

おまけ

ハウテレビジョンでは、論文の好きな仲間を募集しています。
Webエンジニア
エンジニアインターンシップ