6.170 Laboratory in Software Engineering, Fall 2005: Lecture 5 - OpenCourseWare(OCW)を勉強するWiki

MIT OpenCourseWare ＞ 6.170 Laboratory in Software Engineering, Fall 2005 ＞ 6.170 Laboratory in Software Engineering, Fall 2005: Lecture 5

MIT OpenCourseWare 6.170 Laboratory in Software Engineering, Fall 2005, Lecture 5: Testing のまとめ

ラジオの方では vol.11- にあたりました。Lecture Noteを読むときの助けにしてください。
6.170 Laboratory in Software Engineering, Fall 2005のLecture NoteのPDFはこちら

Barbara Liskovの「Program Development in Java」の10章の内容です。

5.1 Program verification techniques and input space partitioning

テストのゴールってつまりは、プログラムの機能が正しく動いてることを保証したいんだけど、テストではエラーが「ない」ことじゃなくてエラーが「ある」ってことしか言えない。でもテストによってソフトウェアをより正しくすることができるよ、いくつかのテストでほとんどのエラーがわかるっていう仮定に従えば。

以下はプログラムの正しさを確かめる(verify)3つのテクニック。

Prove correctness

このアプローチはすごく真面目にフォーマルなspecification (precondition, postcondition, あとしばしばloop invariants)を書かなきゃいけない。そしてそのspecificationをコードと環境が満たしてることを証明しなきゃいけない。これは人手が必要なんだけどプログラムの手間はかかるし、人がまたエラーだすしね。全部自動化したいかもしれないけど、人の指揮とか監督とかを必要とするテの話。そもそも手間より全部のspecificationを書き出したり証明したりするほうが難しいし、このspecificationが正しいことを証明するのはどうしよう？

Run the program on all possible inputs

ありうる入力を全部入れてテストして全部の出力を確かめたらそのプログラムは正しい。欲しいアウトプットはやっぱりこれも人手か別に正しさを確認した簡単な実装で与えておく。でも入力空間は無限だったりかなり大きかったりするから実行不可能だよね。

Run the program on some inputs

いくつかのインプットでテストするので、前2個と違って正しさの保証はできないけど、もしもテストケースをちゃんと選んだら、全ての入力についてそのプログラムはかなり信頼性がおける。

このアプローチの背後には、全ての入力空間を振る舞いが一緒（behaves the same）なグループに等しく(equivalence class/group) 分ける、という考えがあって。グループ内の任意の入力でプログラムが落ちるならグループ内の全ての入力で失敗するし、グループ内の任意の入力でちゃんと動くならグループ内の全ての入力で動くってこと。だから、全ての入力のグループの任意を1つずつ持ったテストスイート（test suite）は完全なテストになる。

でもこのequivalence groupを見つけるのはプログラムの正しさを証明するのと同じぐらい難しい。なので、ヒューリスティックにテストケースは見つけましょう。それぞれのequivalence classで少なくとも1個のテストケースが入ってて欲しいね。ってことで1)equivalence classを推測する（で、テストケースをテストスイートに加える）、2)さらに、1)での選び方が持ってる潜在的な問題を潰すようなテストケースをつけくわえる、という手順。もしequivalence groupをいい感じに推測できたら（もしくは全equivalence groupの一部だけでも正しいとわかれば）、テストスイートで全てのバグがわかるよ。

5.2 Heuristics for test case selection

じゃあどうやってテストケースを選ぼう、入力空間を分けよう：　要はどうテストスイートを作ろう？　テストスイートを選ぶ3つのキーとなるヒューリスティクスは"coverage"、"boundary cases"、"duplicates"。

Coverage

これはテストで使われるヒューリスティクスで一番大事。それぞれのコードやspecificationの構成を確かめる入力を選ぶたにカバレッジの判断基準を考える。

完全なカバレッジは普通は不可能だから、エラーがないことを示すのに有効じゃない。

テストスイートのコードのカバレッジをチェックするには色んなツールやメソドロジーがある。たとえば、

• statement coverage（全てのステートメントがテストスイートで実行されること）
• branch coverage(それぞれの分岐を通ったり通らなかったりするか)
• decision coverage(たとえばif(a&&b)でのaとbみたく、それぞれのbooleanコンポーネントがconditionalか)
• def-use coverage(defはdefinition、every use of a variable is reached by each definition of the variable)
• path coverage (every loop-free path, or sequence of subsequent statements, in a method is followed on some execution)

とか。

領域のカバレッジは、それぞれのパートの要素を含む必要がある。monolithic domainだとテストケースは1個でいいけど、複数のドメインが自然な構造を持ってるときは、その最小値と最大値、その近傍を含むのが賢明。たとえば非負のBigIntegerだったら、0, 1, 2, といくつかのとても大きい値をインプットとするべき。

Boundary

equivalence class の作り方がおおよそ合っていたとしても、実際のものとちょっとずれてたりするかもしれない。（p.3に、入力が10未満、10を含み20未満、20以上、というのが本来のequivalence classだったとして、テストを9,20,21の入力で作ると3つのgroupのうち2つしかカバーしないとかの例。）
こういう間違いがないように、クラスの真ん中に近い"代表値"に加えて境界に近いテストケースを加える。あと入力空間の最大値、最小値とその近傍も入れるほうが賢明。
大きくて複雑な入力を入れることを"stress testing"という。特にこれはrepresentation invariantsやpreconditionsやpostconditionsをチェックするのに有効。

Duplicates

入力値同士に相関があれば、プログラムの振る舞いは変わる。例えば下の例、

／／ modifies: v1, v2
／／ effects: removes all elements of v2 and appends them in reverse order
／／ tothe end of v1
／／ throws: NullPointerException if v1 is null or v2 is null
static void appendVector (Vector v1, Vector v2) {
　while (v2.size() > 0) {
　　Object elt = v2.remove(v2.size()-1);
　v1.add(elt);
　}
}

これはv1とv2が同じものでなければちゃんと働くけど、同じだったら無限ループになる。

3つのヒューリスティクスは

• 入力値
• 出力値
• non-explicit value　例えばループのイテレーション、Setの大きさ、特定の事象の起こる回数など。これらは陽に暗にコードの振る舞いに影響する。

ヒューリスティクスは、

• ブラックボックステスト　specificationのみに依存してテストケースを作る
• クリアボックステスト　実装をテストする

のいずれにも使える。
で、複数のヒューリスティクスが適用可能なら全部を組み合わせる(cross-product)べき。例えば、1つのヒューリスティクスが2つのグループだと導出し、他のものが3つと言った場合、2*3で6つのテストケースにする。

5.3 Black-Box Testing

specificationをテストする。“functional tests”とも呼ばれる。実装の穴を見つけ、そのエラーや仮定をチェックする。実装から独立で再利用可能、古い実装から新しい実装になっても使えるもの。

たとえばこのspecification。

／／returns the absolute value of its input
int abs(int x);

• coverage
  • input　入力の領域はmonolithicだから1つのケースでよい。（といってもほんとはInteger本来の性質で、正、0、負って分けたほうがいいよ）
  • output　inputに同じ（実際のアウトプットは正なわけだけど、この話は後で）
  • non-explicit value　明らかでないので特になし
• boundary cases　
  • input　integerの範囲はInteger.MIN VALUEからInteger.MAX VALUE。なのでこれら最大値、最小値を加えてね。
  • output　アウトプットの範囲もintegerだけど、specで絶対値って言ってるんだから0が最小値。その近傍も加えてね。
  • non-explicit value　明らかでないので特になし
• duplicate
  • 入力が一個なのでなし

このspecificationを考えると、

／／ if x<0, returns -x; else returns x
int abs(int x);

specificationをカバーするには全ての分岐に行かなきゃ行けない。とすると明らかなグループ分けは正、0、負。なので境界の入力は-2, -1, 1, 2。

次の例。

／／returns the length of the longest stutter in s
int stutterCount(String s)

（詳細はp.6参照）

5.4 Clear-box testing

実装を見ながら作るテスト。“glass-box”とか“white-box” (“black-box”に対して)とか“structural” (“functional”に対して)とかとも言う。最適化など、specificationには明記されず実装にのみ依存することをテストする。

ブラックボックスとの差異を見るにはたとえばこれ、

／／ returns the maximum of its arguments
　int max3(int x, int y, int z) {
　　　if (x>y) {
　　　　if (x>z) return x; else return z;
　　　} else {
　　　　if (y>z) return y; else return z;
　　　}
　}

宣言されてるspecificationだけ見ればx,y,zどれかが一番大きいときつまり3つのテストケースでいんじゃないかって思わせる。
（かしこいテスターは順列を考えて3!=6とおりでテストするし、さらによく気づくテスターは重複を考えるけど、ここではそんなテスターではないという仮定で。）

ブラックボックステストではクリアボックスのカバレージははない。というのも、3つのテストだけだと少なくとも1つのif文が実行されないので、ここで必要なのは4つのテスト。そんな感じでクリアボックスはコピペを手直ししてコードを書くときのミスを防ぐのにもいい。

なお、ステートメント(statement)をカバーするのとブランチ(branch)をカバーするのは別の話。

　int abx(x) {
　　if (x<-1)　(※ocwreadingの中の人註："x<0"ではなかろうか)
　　　x = -x;
　　return x;
　}

この例では、1つのテストケースでプログラムの全てのステートメントを通る。でも、ブランチカバレッジを考えると2つ必要。

同様に、ブランチカバレッジとパス(path)カバレッジの違い。次の例では、ブランチカバレッジには2つのテストが、パスカバレッジには4つ必要。

　if (p1)
　　a;
　else
　　b;
　if (p2)
　　c;
　else
　　d;

ただ、クリアボックスは実装のダメさは見つけてくれない。たとえばこんなのとか。

　int max3(int x, int y, int z) {
　　return x;
　}

5.5 Test strategy and automation

ブラックボックスもクリアボックスもどっちも使うのがいい、というのもお互い違うタイプのエラーを見つけてくれるから。最初に、コードの知識がなくてもいい（specificationだけで決まる）ブラックボックステストをやるといい。
テストには色んなレベル（unit, module, system, and acceptance）がある。テストはボトムアップ(bottom-up)からでもトップダウン(top-down)からでもどっちからでもできる。
ボトムアップテストの場合は、クラスの関数を実行するドライバを必要とする。ドライバは開発者が作ったシステムにおける環境（どう呼ばれるか）およびspecificationにしたがって呼ばれる全ての環境をシミュレートする。ドライバはまたテストをするために必要なもので、これ以上のボトムアップテストは必要としない。トップダウンテストには、まだ実装されていない部分の振る舞いをシミュレートするスタブを使う。トップダウンテストの利点は、システムを作る前に設計上のミスを検出しやすいこと。
一般的には正しいテストのアプローチは開発スタイルによる。コードのテストはバグをクイックに探すし、他のデザイン部分に影響する問題も早くわかる。

あと重要なのは"Regression testing"、コードの変更後に再テストをすること。コレを忘れるとはまることがあるので注意。
他に有効なテスト戦略はassertionを利用すること。assertionはプロパティをチェックして、もしもそのプロパティを満たしていなければエラーを吐く。これは、preconditions, postconditions, representation invariantsのテストに有効。
とにかくエラーは早く見つけようね。

5.6 Static verification

上記のテクニックはdynamicなものだけど、じゃあstaticなverificationは？

• run tools　theorem-proverとか、日常的に使ってるものでもコンパイラとか。
• think about the code　自動化できなくても形式or日形式でも何がしかコードのプロパティを証明する方法がある。例えばrepresentation invariant, abstraction function, pre-and post-conditions を書き出すことで構造的に感がられる。あとプログラマもテストケースを考えること。
• ask a friend　友達やTAに聞いてね。

---

today's visitor： -
total visitor： -