Facebook がバグの自動修正ツールを発表したという話があり、 code.fb.com
その紹介記事を見て、 Sapienz のほうは論文が発表されているという話だったので読んでみた。軽く。
バグの自動修正ツールのほうはSapFixというやつで、バグを修正するためにはまずバグを見つけなければいけないが、そのバグを検知するために使われているのがSapienz。
で、SapienzというのはAndroidアプリ向けの自動テストツール。
この論文を書いた一人のMark Harmanという方(とMcMinnさんという方)が2001年にSearch-based software engineering (SBSE) という手法を提案しており(参考: http://a-lifelong-tester.cocolog-nifty.com/publications/STM07_Notes_on_new_software_testing_techniques.pdf)、 曰くSBSEとは、
手法であり、
このサーチ技法をテストの分野に適用するのがSearch-based testingと呼ばれる技法
である。そのSearch-based testingの手法をAndroidのテストに応用して成果が出たよんということのようだ.
上で参考にあげた資料に書いてあるようにサーチ技法として用いられるアルゴリズムにはいくつかの種類があるが、Sapienzで用いられているのは Evolutionary Algorigthm (進化的アルゴリズム) である。 また、Androidのテストにおいては、多目的最適化を使ったsearch-based testingの初めてのアプローチだぜ、と言っているし、論文のタイトルからしてMulti-objective Automated Testing for Android Applicationsであるように、多目的最適化問題として扱っている。
進化的アルゴリズムでは、解きたい問題の解を個体として表現する(多分)。
個体の性質は染色体によって決まり、染色体は複数の遺伝子から成る。
そして個体同士で交叉して子を作ったり突然変異したり一部の個体は淘汰されたりして進化をして世代を重ねていくことで、よりいい感じの解を探す。
詳しくや正確にはもちろん他の資料を参考に。
で、Sapienzで具体的にどんな風に問題が表現されているか。
Sapienzで最適化したい問題というのは、
- より多くの範囲をテストし(coverage)
- より多くの不具合を(fault revelation)
- より短い手順で(shorter test sequence)
発見するようなテストを生成したいということ。
この3つを同時に最適化するので、Multi-objectiveな最適化という話。
論文中でも言及されているが、多目的最適化においては一般にパレート最適な解を見つけることが目的になる。 この場合上記の3つの要素についてパレート最適な解を探す。
Sapienzでは、進化的アルゴリズムにおける個体などの表現は下記のようになっている。
- 個体: テストスイート
- 染色体:テストケース
- 遺伝子:なんらかのイベント
で、遺伝子には2種類ある。Atomic genesとMotif genes.
Atomic genesのほうはその名の通りAtomicであってそれ以上分割することのできない単位のイベント。 たとえばなんかのキーを押すとかどこかをタップするとか音量を調節するとかそういうの。
Motif genesのほうはAtomic genesの組み合わせ。
なんで組み合わせを使うのかというと、UIというのは複雑なものなので、状態やその時のコンテクストの知識なしに単純にAtomic genesだけ組み合わせているとちゃんとした動作を組み立てるのが難しいからだそう。まぁそれはそうっぽい感じがする。しかしこの論文の時点では、Motif genesは汎用的なもの1種類しか使っていないようだ。Motif geneをたくさん使うということはそれだけ人間の手がかかるということで、自動化を妨げることになるからということ。
個体や遺伝子についてはそれで、個体を進化させるためのアルゴリズムの話
下記のいずれかを確率的に個体に適用する。
- 交叉(crossover)
- 変異(mutation)
- 繁殖(reproduction)
個体間では一様交叉を行う。個体内では変異するが、変異は少し複雑。
個体はテストケースを複数含むテストスイートなので、まずテストケースの順序をランダムにシャッフルする。このシャッフルは交叉の際の多様性を増すことを目的にしている。シャッフルしたあとに2つの隣合うテストケース同士で, qの確率で1点交叉を行う。 更に、テストケース内のイベントをqの確率でシャッフルする。Atomic eventsにはパラメータがあるので、それを変異させることもできるが、操作を単純にするためにイベントの並び順を変えることにしたようだ。 繁殖は単にランダムに選ばれた個体をそのまま使うらしい。
淘汰(selection)にはNSGA-Ⅱというアルゴリズムを使う。雰囲気しか理解できてない。
個体の評価は、さっきも書いたが下記の組で行われる。
- カバレッジ
- テストシーケンスの短さ
- 発見したクラッシュの多さ
これらが最も望ましいケースと個体との距離で個体がランク付けされ、ランクが良いものが選ばれる。同じランクではより混雑距離が大きいものが選ばれる。混雑距離というのはランク内において隣接する個体への距離の和のこと。より混雑していないもののほうがが多様性を確保することができるため良い。
ここまで読むとなんとなく進化的アルゴリズムを適用してある程度良いものができそうな気がしてくる。むしろ、実際多様なアプリケーションに対してどのようにテストのイベントを生成するのかとかが気になってくるが、そのへんについては特に細かくは触れられてない。多分他にもテストを生成するツールは既にあるのでそこはこの論文にとってはあんまり重要ではないだろう。
ちなみにこのSapienzはDEAPという, python製の進化的アルゴリズムのためのフレームワークを使って構築されていたが、このDEAPはすごく簡単に使えて便利。自分の場合使う予定は特にないけど。NSGA-Ⅱを用いた多目的最適化とかもできる様子。
参考にした資料など
基本的に検索してすぐ出てきたもの
- wikipedia https://ja.wikipedia.org/wiki/%E9%80%B2%E5%8C%96%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
- http://mikilab.doshisha.ac.jp/dia/monthly/monthly2014/mlm152/syagami/syagami.pdf
- https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm
- http://tech.mof-mof.co.jp/blog/ga-one-max-problem.html
- https://qiita.com/neka-nat@github/items/0cb8955bd85027d58c8e
- DEAP https://deap.readthedocs.io/en/master/index.html
- Monkey https://developer.android.com/studio/test/monkey
- https://qiita.com/Taichi-Furukawa/items/a7a0982cc20a401133c0
- http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1589-07.pdf
- http://mikilab.doshisha.ac.jp/dia/research/mop_ga/moga/3/3-5-5.html
- http://bulletin.soe.u-tokai.ac.jp/vol53_no1_2013/P22_28.pdf