jcunit's blog

JCUnitの開発日誌(ログ)です。"その時点での"JCUnit作者の理解や考え、開発状況を日本語で書きます。

IEEE International Conference on Software Testing 2017でJCUnitの発表をすることになりました。

表題の通りです。スケジュールはこちら。

ICST 2017 | Schedule

東京で開催されるカンファレンスなのに、日本人の発表者があまり見当たらないのは残念なことです。 2/13まではEarly Birdで少しだけお安くお申し込みできます。

ICST 2017 | Registration

キーノ−トスピーチ等は同時通訳もつくそうです。

A new IPO-G based algorithm that supports constraint handling

Background

A couple of weeks ago, when I was writing a jcunit demo that tests geophile[0] library, I noticed that its old constraint handling doesn't work well. Since the behavior looked hard to fix without hurting compatibility and it would take a bit time, I decided to implement another algorithm which I came up with.

Introduction

I'm calling this new algorithm IPO-gc, named after well-known one IPO-G. Before getting into my own, I would shortly touch up on its ancestor.

IPO-G[7], which is a basis of my new algorithm IPO-gc, is one of best known combinatorial test suite generation algorithms where it grows up an initial covering array, generated by calculating Cartesian products of first t(= desired strength) factors, horizontally and vertically until all the desired tuples are covered.

Following is a pseudo code to illustrate the algorithm.[7]

    Algorithm: IPOG-Test (int t , ParameterSet ps ) {
      1.  initialize test set ts to be an empty set
      2.  denote the parameters in ps , in an arbitrary order, as P1 , P2, ...,
          and Pn
      3.  add into test set ts a test for each combination of values of the first
          t parameters
      4.  for (int i = t + 1 ; i ≤ n ; i ++ ){
      5.     let π be the set of t -way combinations of values involving parameter
             Pi and t -1 parameters among the first i – 1 parameters
      6.     // horizontal extension for parameter Pi
      7.     for (each test τ = (v 1 , v 2 , ..., v i-1 ) in test set ts ) {
      8.         choose a value vi of Pi and replace τ with τ’ = (v 1 , v 2 ,
                 ..., vi-1 , vi ) so that τ’ covers the most number of
                 combinations of values in π
      9.         remove from π the combinations of values covered by τ’
      10.    }
      11.    // vertical extension for parameter P i
      12.    for (each combination σ in set π ) {
      13.      if (there exists a test that already covers σ ) {
      14.          remove σ from π
      15.      } else {
      16.          change an existing test, if possible, or otherwise add a new test
                   to cover σ and remove it from π
      17.      }
      18.    }
      19. }
      20. return ts;
      }

This algorithm consists of 4 most core elements, which are

  1. *ts* = Create a initial covering array from first *t* factors.
  2. *π*  = Compute partial tuples to be covered by an iteration

  foreach *factor* not in first *t* factors:
     3. hg: Grow *ts* horizontally by adding a *factor* to the right of given 
        one so that partial tuples in *π* as many as possible. 
        covered tuples by this step will be removed from *π*.

       while *π* is not empty
       4. vg: Grow *ts* vertically by adding a new full tuple that covers partial 
          tuples in π as many as possible. If there is already a tuple in *ts* that
          can cover another partial tuple in *π*, it will be modified to cover the
          partial one instead of adding a new one to *ts*.

where "a full tuple" means a tuple which has all the first i attributes and "a partial tuple" means a tuple in π, only has t attributes.

IPO-gc algorithm

IPO-gc's core idea is simple.

  • Enhance definitions of hg and vg operation so that it can create a new covering array from 2 partial covering arrays, not only from 1 covering array and 1 factor.
  • Consider a simple factor a special form of covering arrays.
  • Group given constraints into smaller chunks, each of which reachable from one constraint to another connected by shared factors.
  • For each group of constraints, create covering array from factors referenced by the constraints in it. In the current implementation it is a brute force algorithm, but it can be any algorithm such as PICT, IPOC, or other AETG based algorithms.

Assumptions behind the last item is following,

  • Generally speaking, constraints defined over a test space can be grouped into some smaller groups each of which contains only small amount of factors.

In my limited experience, this is true for automatic test suite generation for FSM's by JCUnit[1]. And actually it would be considered that creating a set of constraints that relate to many factors directly and indirectly isn't a good idea[8]

Definitions

Before discussing further details, I want to define following several terms.

  • FS Factors.
  • CS Constraint sets.
  • t Desired strength of a generated test suite.
  • ts Generated test suite. To which the algorithm adds generated tests by growing up horizontally and vertically.
  • τ A (current) element in ts.
  • π Partial tuples that should be covered in a current iteration. A tuple in this set has values from FS (simple factors) only. Not from GFS because this set is used to evaluate how good a next choice is and it should be done based on how many possible partial tuples generated from FS not from GFS.
  • GFS Grouped factors. A grouped factors consists of one or more factors. And has zero or more constraints each of which uses one or more factors in it, but none of the constraints uses any factors outside the grouped factor. A grouped factor is one form of a "covering array" whose characteristics will be discussed later.
  • GFS.length Total number of grouped factors in GFS.
  • GFS[ i] ith element of GFS.
  • GFS[ i].subfactors Simple factors that belong to GFS[ i].
  • GFS[ i].constraints Constraints that belong to GFS[ i].
  • GFS[ i].levels Levels of GSF[ i], which are tuples that consist of values from GFS[ i].subfactors.
  • A grouped factor: If a set of factors FS, strength t, and constraints CS over them are given, we can define a grouped factor GF(FS, CS, t) as follows.

    • It is a set of full-tuples all of FS.
    • All the possible tuples of strength t over FS are covered by it.
    • None of CA violates any of CS.
    • For simplicity, if an element is removed from it and the conditions above are still met, it will be removed.

One thing to be noted here is once a covering array is computed for a given factors and their constraints, we are always able to compute all the possible partial tuples of strength t by just scanning elements in it. You do not need to worry about what constraints are given.

Ideas

Figures to illustrate the ideas of IPO-gc are as follows

In IPO-G, horizontal growth hg is defined as an operation between, ts, Pi (a conventional factor), t(desired strength), and π (tuples to be covered in this iteration).

   IPO-G
    
        ts                                ts'
         P0 P1...Pi-1    Pi                P0 P1...Pi-1 Pi
        +---------+     +---+             +---------------+
        |         |     |v0 |             |               |
        |         |     |v1 |             |               |
        |         |     |.  |             |               |
   hg(  |τ        |  ,  |.  |  , t, π) => |               |
        |         |     |.  |             |               |
        |         |     |   |             |               |
        |         |     |   |             |               |
        +---------+     +---+             +---------------+
    

π is calculated from a set of all possible tuples of strength t in ts and all the levels of Pi just by Cartesian product.

This will look like following diagram in IPO-gc.

   IPO-gc
    
        ts                                            ts'
         GF[0] GF[1]...GF[i-1]    GF[i]               GF[0] GF[1]...GF[i]
        +---------------------+     +---+             +---------------+
        |                     |     |v0 |             |               |
        |                     |     |v1 |             |               |
        |                     |     |.  |             |               |
   hg(  |τ                    |  ,  |.  |  , t, π) => |τ'             |
        |                     |     |.  |             |               |
        |                     |     |   |             |               |
                              |     |   |             |               |
        +---------------------+     +---+             +---------------+
    

GF[ i] is a grouped factor to be added to ts. π is calculated by following procedure.

  • Pick up all the possible partial tuples of strength x (smaller than t)from ts. Call it Left.
  • Pick up all the possible partial tuples of strength y (x + y = t)from GF[i]. Call it Right.
  • Calculate cartesian product between Left and Right. => π

When expanding ts to ts', values for GF[i] of τ' will be chosen to cover as many tuples in π as possible.

In vg (vertical growth) operation, there's a not a big difference than in hg. Add a new test or modify existing test to cover a new tuple. But when we add or modify a tuple, attributes that belong to the same grouped factor need to be updated at once. Not one by one. Otherwise, we may create a test case that violates some of given constraints.

To build a grouped factor, we group constraints first by original factors involved by them.

Suppose that factors Pi ( 0 <= i <= 7) and constraints C1, C2, C3, and C4 are given. And factors involved in each constraint are described as in following diagram.

       P1    P2    P3    P4   P5    P6    P7
   C1  |-----|           |              
   C2        |           |
   C3               |         |-----|
   C4                                     |

In this case, IPO-gc will build 3 grouped factors

  • GF[ 0] = ({P1, P2, P4}, {C1, C2})
  • GF[ 1] = ({P3, P5, P6}, {C3})
  • GF[ 2] = ({P7}, {C4})

Note: A simple factor can be considered a grouped factor.

Algorithm

In short, it is an algorithm that transforms given factors and constraints into grouped factors, which are actually a set of covering arrays under related constraints, of desired strength t. And then do enhanced IPO algorithm, which can handle horizontal growth between current ts (test suite) and a grouped factor.

   IPO-gc algorithm (summarized version)
     Input:
     - FS: Factor set
     - CS: Constraint set
     - t:  strength
     Output:
     - ts <- ca(FS, CS, t)

   1.     GFS[] = transform(FS, CS, t)
   2.     ts    = initial_covering_array(GFS[0], ..., GFS[t-1])
   3.     foreach GF in [GFS[t], GFS[t + 1], ..., GFS[GFS.length - 1]] {
   3.0      i = indexOf(GF in GFS)
   3.1      π = compute_all_possible_partial_tuples([GFS[0], ..., GFS[i-1]], GF)
            // horizontal extention
   3.2      foreach τ in ts[] {
   3.2.1      v = choose_best_level(τ, GF, π)
   3.2.2      update(τ, GF, v)
   3.2.3      remove_subsuples(π, τ)
            }
   3.2.4    // vertical extension for parameter P i
   3.2.5    for (each combination σ in set π ) {
   3.2.6      if (there exists a test that already covers σ ) {
   3.2.7        remove σ from π
            } else {
   3.2.8      change an existing test, if possible, or otherwise add a new test
              to cover σ and remove it from π
            }
          }               

In the step 1, I just stated "transform simple factors into grouped factors". But each grouped factor is a covering array for given factors and constraints and it's very preferable to make it small. In other words, we still need to solve the same problem, "how to create a covering array from given factors under given constraints".

IPO-gc algorithm is not providing a good way to solve it. It is rather a framework to create a bigger covering array from given ones. In current implementation in JCUnit, what I created is just a very naive one. Just check all the possible combinations and exclude ones that violate any of related constraints. And then remove redundant ones (that do not cover new combinations). This approach can become easily impractical when many factors are involved in constraints. But,

  1. Maybe you should revise the test design so that we can make the model simple.
  2. It is easy to use another better algorithm to handle constraints and generate a covering array.

Another thing that needs to be achieved in this step is to group given constraints and factors into some cohorts. If a constraint C1 uses factors A and B, and another constraint C2 uses B and C, those will belong to the same group. And factors A, B, and C will belong to the same grouped factor. Plus C1 and C2 will belong to it, too. Because B is shared by C1 and C2, and this means we need to take all these 3 factors into account at once to check if a given tuple is violating any of them or not.

But C3, that only involves factor D and E, it will belong to another grouped factor, because there is no overlap between factors referenced by C1 and C2.

In step 3.2.1, original version of IPO-G just chooses one level from a simple factor that covers tuples in π the most. But in IPO-gc it is required to choose a set of levels in a manner the set of chosen levels do not violate any given constraints. This can be achieved by choosing a level of a grouped factor rather than choosing levels from individual (sub-)factors.

In step 3.2.8, the intention of the step is also same as the original one, but what we need to do is a bit different. If σ is involved in a constraint, other attributes might be required to be a specific value or in a specific range. In such case, we need to change not only the values directly mentioned in σ but also other (sub-)factors that belong to the same grouped factor.

NOTE: In step 3.1, We are calculating cartesian product of GFS[ 0 ], ..., GFS[i-1], and GF. But we should be able to make the step faster by scanning ts instead of the expensive operation.

   3.1    π = compute_all_possible_partial_tuples(ts, GF)

Because ts should cover all the desired partial tuples at the beginning of an iteration. But we are not getting into further detail of it for now since it is an implementation detail.

Advantages and limitations of this algorithm

  • Easier to make it parallel: Calculating covering arrays is an expensive operation and we can do it concurrently.
  • Easy to implement: I could write this mechanism with in 2 weekds from I came up with it.

Future works

  • Survey: I invented this algorithm but did not conducted any survey to claim it is a novel one. Maybe I'm just re-invented it since it's sort of naive. Also the assumption mentioned in IPO-gc algorithm section, where constraints should not involve so many parameters and therefore brute force algorithm is sufficient, should be surveyed to what extent it is applicable.
  • Use other algorithms to generate a covering array for a grouped factor: It is easy to enhance the implementation to make the algorithm pluggable but right now it is hard-coded because there is only one available algorithm.
  • Evaluation: Let's compare this algorithm with other ones. Sizes of test suites, performance, etc.
  • Synthesize a new level from existing levels instead of just choosing one from a "grouped factor"(covering array under constraints): This will make generated test suite's size smaller.

References

(第四回)JCUnitで2次方程式を解くプログラムをテストする。

はじめに

本ブログでご案内しているように、javacのバグによりJDK1.7.0_79以前でコンパイルエラーが生じることがわかった。 この問題を回避するために、jcunit 0.6.4をリリースしたので、pom.xmlを以下のように更新して欲しい。

    <dependency>
      <groupId>com.github.dakusui</groupId>
      <artifactId>jcunit</artifactId>
      <version>[0.6.4,)</version>
      <scope>test</scope>
    </dependency>
    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>4.12</version>
      <scope>test</scope>
    </dependency>

(第四回)JCUnitで2次方程式を解くプログラムをテストする。

前回のエントリでは、FL表を作成し、それにもとづいてJCUnitにテストスイートを生成させたところ、109件ものテストができた。 これについてすでに以下のように述べた。

  1. テストケースが多すぎる
  2. 正常系のテストと異常系のテストが混ざっていてレビューしづらい
  3. 同時に複数の制約に違反するテストケースが多い。この種のテストケースは多くの場合あまり意味がない

テストスイートを自動で生成し、かつ自動で実行するとしてもテストケースの数は大きな問題になる。 あまりに数が多すぎれば管理ができない。多くのテストが様々な理由で失敗している場合、失敗している理由を捕捉するのに手間がかかる。 また、適切にテストオラクルを作るのが難しい場合、ひとまず現在の挙動を記録しておき、プログラム修正後(リファクタリング等)の次回実行時に前回との差異を点検することでテストとする場合もあろう。 こうした時に、何千何万というテストケースがあったのでは容量を食い過ぎるという場合もある。 また、私としてはテスト対象の外部的な仕様に基づいてテストを設計・実装・実行するために、つまり結合テストシステムテストの段階で、JCUnitを使いたいのだがそうすると一件のテストの実行時間は短くても500msec、ながければ数分ということがあり得る。この場合、如何に自動で生成・実装・実行されるとしても無駄なテストをする余裕は無い。

そもそも、JCUnitは人間が与えたソフトウェアの仕様にそって、テストを生成・実行するものである。テストが意図通りに生成され、実行されているかは人間によるレビューが必要だろう。 何万件、何十万件もテストを実施してもそのテストが正しいかをレビュー・点検する方法を欠いているのでは、いささか中途半端というものではないか。

正常系と異常系のテストが入り組んでいるのも同じような理由で好ましくない。 設計者は正常系の挙動と異常系の挙動を区別してソフトウェアを設計するもので、これらのテストが交互に現れたのではレビューにならない。

「制約」と「条件」の区別

上述諸点を改善するためにどうする必要があるか?「制約」と「条件」を明確に区別してはどうか?というのがJCUnitのアイデアだ。 前回の記事で紹介した@Conditionは実を言えばもともと単にテストを実行する「条件」を記述するためのものだ。

例えばある「OS」という因子があるとして水準が「Windows」のときと「Linux」や「MaxOSX」の時では異なる事項を確認したい。そういう際に、

  @Test
  @When({ "isWindows" })
  public void openInternetExplorerAndGoToWikipedia$thenWelcomPageIsShown() {
      ...
  }

  @Test
  @When({ "isWindows","isLinux" })
  public void openFirefoxAndGoToWikipedia$thenWelcomPageIsShown() {
      ...
  }

  ...

このように使い分けるためのものだ。

「制約」も「条件」の一種と言えるが、こうした普通の条件とは重要な違いがある。まず、通常、アプリケーションやシステムというものは、異常(環境設定、ユーザ入力、内部状態等)を検出したら、その時点で処理を打ち切り、それ以降の処理(それ以外の制約検査も含め)は行わない。

  1. 一つ以上制約が破られたら、そのテストケースがカバーしようとしている値の組み合わせはそれ以降の正常な処理によって使われない可能性がある。(組み合わせ網羅率の低下)
  2. 一つのテストケースで複数の制約が同時に破られる(複数の異常が発生する)と、テスト対象システムは最初に検出した異常に反応して処理を打ち切る。したがってこれら複数の異常のうち、(たまたま)システムが検出した異常処理のみが行われる。
  3. 制約違反を検出して、異常を報告するのはそれ自体システムが備えるべき機能であって、正常機能とは独立して検査する必要がある。

組み合わせテストは、処理が最後まで正常に行われるべき場合に、システムが正しく動作するかを効率的に検証するためのテクニックである。 テスト対象システムの動作条件がWindows 7以降であるときに、以下のようなテストスイートが生成されたとしよう。

OS Browser Site's Language
Windows XP Safari English
Windows 7 Firefox Japanese
Linux Chromium English

対象システムは、稼働OSがWindows XPであることを検出した時点で、異常を報告して処理を終了する。しかしブラウザがSafariで言語がEnglishの組み合わせが別のテストケースによって網羅されている保証はどこにもない。むしろ、良い組み合わせテスト生成ツールほど、テストスイートを小さくまとめるために網羅しなくなる可能性が高いと言える。

制約違反を適切に報告できるかもシステムの機能としてテストする場合、それはまとめてではなく一個一個行う必要があることは上に述べたとおりである。10個独立な制約があったら、これらのすべてについて、1個、そして1個だけに違反するようなテストケースをそれぞれ作成する必要があることになる。

経験を積んだソフトウェアエンジニアであれば、このあたりは本能的に知っている。例えば「処理対象にして良い文字が入力できるか」をテストする場合には、テストデータに「際どいけど正常な文字」を全部いっぺんに使うように試みる。

    AZaz09ー。、.,能あをんアヲン?

こうすることによって、「処理できるべき文字がすべて処理できるか」については一度にテストが行える。 しかし、「処理を中断するべき文字がすべて拒否されるか」については一個一個テストを行う必要がある。例えば、\が拒否されるかと、"が拒否されるかは別のことなので、両方を一つのテストデータに含めてしまうとどちらによってシステムが処理を拒否したのかがわからなくなってしまう。拒否された場合のメッセージが適正かなどはそれでも検査できるにしても、不当な文字を適正に拒絶できているかは別のことである。

JCUnitでの解決方法

JCUnitでは以下のようにしてこうした問題に対処することになる。 まず、前回のコード例は以下の場所にある。

github.com

@RunWith(JCUnit.class)
public class QuadraticEquationTest {
  @FactorField(intLevels = {1, 0, -1, 100, 101, -100, -101, Integer.MAX_VALUE, Integer.MIN_VALUE})
  ...

  /**
   * 制約1: ```a```が0の場合、例外が送出される。(**問題4:a==0**)
   */
  @Condition
  public boolean aIsNonZero() {
    return this.a != 0;
  }
  ...

行うべき変更は

  1. 「制約」を前節で述べた方針にそって特別扱いするようJCUnitに指示する。
  2. @Conditionで定義していた条件が単なる条件ではなく、特別な取り扱いであることを明示する。

このニつである。 以下が変更後のファイルである。

github.com

@RunWith(JCUnit.class)
@GenerateCoveringArrayWith(checker = @Checker(value = SmartConstraintChecker.class)) // <-- 追加:1. のための変更
public class QuadraticEquationTest {
  @FactorField(intLevels = {1, 0, -1, 100, 101, -100, -101, Integer.MAX_VALUE, Integer.MIN_VALUE})
  public int   a;
  ...


  /**
   * 制約1: ```a```が0の場合、例外が送出される。(**問題4:a==0**)
   */
  @Condition(constraint = true) // <-- 修正:2. のための変更
  public boolean aIsNonZero() {
    return this.a != 0;
  }    ...

これを実行してみよう。

f:id:dakusui:20160410171812p:plain

お気づきのように、今回は34件のテストしか生成されていない。 また、前半(19まで)はすべて成功しているが、後半(20以降)はすべて失敗している。

サイズの減少はa,b,cのそれぞれに制約を設定したため、事実上水準の数が減ったためである。 しかし、複数の因子に関係する制約を加えると、その制約を回避しながら可能な組み合わせをすべて生成するようJCUnitは試みる。これが生じるとテストスイートの大きさはむしろ増すことになる。 今回、二次方程式の判別式に関する制約を(3つの因子すべてに関連する)加えている。これはテストケースの数を増す方向に作用する。が、それ以上に、100よりも大きい水準や-100よりも小さい水準が正常処理に関するテストから取り除いた効果の方が大きかったため全体としてテストケースの数が減ったと見受けられる。

前半と後半で成功・失敗がはっきり別れたのは、上述のコード変更でJCUnitが以下の手順でテストスイートを生成するようになったからである。

  1. 正常テスト(与えられた制約に一つも違反しない)の生成を行う
  2. 異常テスト(与えられた制約の一個だけに違反しているテスト)を生成する。
  3. 水準網羅テスト(正常テストのうち一件を取り出し、1., 2.,でまだ網羅されていない因子の水準を一つずつ試す)を生成する。

今回の実行結果では、20件が成功しているが第三回の例では6件のみ成功していた。正常系についてテストが不足していた可能性がある。

余談

この部分をデフォルトにしてしまえばよいような気がしてきた。

@GenerateCoveringArrayWith(checker = @Checker(value = SmartConstraintChecker.class)) 

読者のご意見をこう次第である。

0.6.4リリース

前回のポストで報告したように、JUCnit 0.6.3やそれを使ったアプリケーションはJDK 1.7.0_79ではコンパイルできない。 2016-04-05 - jcunit's blog

これはJDK 1.7.0_80で修正されたjavacの以下のバグが原因だ。

http://bugs.java.com/view_bug.do?bug_id=8013485

このバグを踏んだ場合、以下のコンパイルエラーが生じる。

annotation com.github.dakusui.jcunit.runners.standard.annotations.Checker is missing value for the attribute <clinit>

この問題を回避するため、以下の修正を含むJCUnit 0.6.4をリリースした。

github.com

上のエラーに遭遇したら、こちらを使ってみて欲しい。 以下がmaven coordinate

    <dependency>
      <groupId>com.github.dakusui</groupId>
      <artifactId>jcunit</artifactId>
      <version>[0.6.4,)</version>
      <scope>test</scope>
    </dependency>
    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>4.12</version>
      <scope>test</scope>
    </dependency>

JDK 1.6.0_45, JDK 1.8.0_25等でで発生しないことは確認してあるが、このバグがどの時点で混入したかは今のところ不明である。 不本意な内容の修正であるが、現在のメインストリームと考えられるJDK 1.7.0でやっと1年前に修正されたバグであり、現実の問題としてJDKのアップデート(すら)が困難な環境にある人々はそれなりに多くいると考えられるので、実施することにした。

JDK 1.7.0_79以前でコンパイルできない。

JDK 1.7.0_80より古いjavacを使っている場合、JCUnit及びそれを使用したライブラリのコンパイルができないことが判明した。ちなみにこれはjavacのバグだ。 これは、確認している限り、JDK 1.6.0_45では起きないし、手元のJDK 8系統でも起きたことがない。 詳報は後日このブログでお知らせするが、annotation関係のエラーが起きた場合には、JDKのアップデートを考慮してほしい。

(第三回)JCUnitで2次方程式を解くプログラムをテストする。

はじめに

本稿執筆中に、JCUnit 0.6.0にバグがあることとユーザビリティを向上する必要があることがわかり、0.6.2をリリースした。 本稿を試すにあたっては以下のようにpom.xmlを更新して欲しい。

    <dependencies>
        <dependency>
            <groupId>com.github.dakusui</groupId>
            <artifactId>jcunit</artifactId>
            <version>[0.6.2,)</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.12</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.hamcrest</groupId>
            <artifactId>hamcrest-library</artifactId>
            <version>1.3</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

hamcrestライブラリへの依存は今回のJCUnitへの変更とは関係ないのだが、本稿の記述範囲で使用するためにここに含めた。

お手数をおかけするがよろしくお願い申し上げたい。 また、今回からここに例題のソースコードを格納することにした。 本稿の記事を読む折には、git clone https://github.com/jcunit-team/jcunit-examples.gitとして欲しい。 もしなにかあればコメント欄などでご連絡頂きたい。

(第三回)JCUnitで2次方程式を解くプログラムをテストする。

第一回で多くのテストが失敗していたが、その結果を分析して二次方程式ソルバーの仕様書を更新した。(「出力される解」については言い回しを変えた)

QuadraticEquationクラス仕様 version 2

  • 入力:三つの整数a,b,c

    • 制約1: aが0の場合、例外が送出される。(問題4:a==0)
    • 制約2: a,b,cのいずれかの絶対値が100より大きい場合、例外が創出される。(問題3:巨大な係数)
    • 制約3: a,b,cb * b - 4 * c * a >= 0を満たさない場合、例外が送出される。(問題1:虚数)
  • 出力:二次方程式a x^2 + b x + c = 0を満たす実数x1x2

    • 出力される解x1またはx2を上述の2次方程式に代入した時、その誤差は0.01を越えない。(問題2:丸め誤差)

これをJCUnitを用いたテストとして実現してみよう。 なお、今回ステップ・バイ・ステップで作るJCUnitのテストは以下の場所に完成版がおいてある。

このコードの解説記事としてお読みいただくと時間の節約になるかもしれない。

因子と水準を設計・実装する。

a,b,cの三つはいずれも整数で境界値は100-100である。 これら一個一個を因子(Factor)とし、それらについてテストに用いるべき水準を列挙するとこんなふうになろうか。

水準 種別
1 正常
0 異常(a),正常(b,c)
-1 正常
100 境界
101 異常
-100 境界
-101 異常
Integer.MAX_VALUE 異常
Integer.MIN_VALUE 異常

ソフトウェアテストHAYST法入門」3などで"FL表"と呼ばれている表にあたる。 ここでは各水準は100やInteger.MIN_VALUEといった具体的な値だが、実務の大規模で複雑なテストにおいては、各水準は抽象的に定義しなけらばならない場合が多い。

また、a,b,cはそれぞれ別の因子なので、二次方程式ソルバーのような簡単なソフトウェアをテストするならともかく、普通は別の表にまとめたほうがよかろうと思う。もしも、テスト設計書をドキュメントとして作るならば、だが。

水準0についてだが、a == 0の場合は異常値(制約1)だが、b, cについてはこの制約は関係ないので正常値である。

それはともかく、これをJCUnitの記法で書くならこうなる。

  @FactorField(intLevels = {1, 0, -1, 100, 101, -100, -101, Integer.MAX_VALUE, Integer.MIN_VALUE})
  public int   a;
  @FactorField(intLevels = {1, 0, -1, 100, 101, -100, -101, Integer.MAX_VALUE, Integer.MIN_VALUE})
  public int   b;
  @FactorField(intLevels = {1, 0, -1, 100, 101, -100, -101, Integer.MAX_VALUE, Integer.MIN_VALUE})
  public int   c;

非常に単純で上で作った表をintLevels = {...}の中に写しとっているだけだ。

制約を設計・実装する。

まず、制約1を実装する。

制約1: aが0の場合、例外が送出される。(問題4:a==0)

ここで使うアノテーション@Conditionである。 因子aにはその水準が0の場合は異常であるという制約がある。 これをJavaメソッドとして実現すると以下のようになる。

  @Condition
  public boolean aIsNonZero() {
    return this.a != 0;
  }

戻り値はその制約に従っている(違反していない)場合にtrue, 違反している場合にfalseを返すことになっている。注意して欲しい。

なお制約を実装するメソッドは、booleanを返す引数なしのものである必要がある。 これに反するとJCUnitは実行時にエラーを報告する。

制約2の場合、このようになる。

制約2: a,b,cのいずれかの絶対値が100より大きい場合、例外が創出される。(問題3:巨大な係数)

Javaで書き下すと以下のようになる。これも非常に直接的だ。

  @Condition
  public boolean coefficientsAreValid() {
    return
        -100 <= a && a <= 100 &&
            -100 <= b && b <= 100 &&
            -100 <= c && c <= 100;
  }

そして最後の制約、判別式の判定だ。

制約3: a,b,cb * b - 4 * c * a >= 0を満たさない場合、例外が送出される。(問題1:虚数)

Javaで書くとこう。

  @Condition
  public boolean discriminantIsNonNegative() {
    int a = this.a;
    int b = this.b;
    int c = this.c;
    return b * b - 4 * c * a >= 0;
  }

これも単純だ。

判定基準の実装

正常の場合と異常の場合、あるいは特定の制約が満たされなかった場合等でテスト対象に対して期待するべき動作は異なる。 無論if文で、現在どの条件でテストを実施しているかを書いてみてもいいが、それでは担当者によるむらも生じるし、その判定文自体のバグも心配になる。

JCUnitでは、上で定義にした制約を参照してどのメソッドを用いてテスト対象の動作を検証するべきかを定義できる。 ここでは正常系の場合と、上で定義した各制約のうち制約1の場合だけを説明する。

まず正常系の場合だが、

出力される解x1またはx2を上述の2次方程式に代入した時、その絶対値は0.01未満になる。(問題2:丸め誤差)

ということになる。 これをJCUnitで表現すると以下のようになる。

  @Test
  @When({ "*" })
  public void solveEquation$thenSolved() {
    QuadraticEquation.Solutions s = new QuadraticEquation(a, b,
        c).solve();
    assertThat(
        String.format("(a,b,c)=(%d,%d,%d)", a, b, c),
        Math.abs(a * s.x1 * s.x1 + b * s.x1 + c),
        closeTo(0, 0.01)
    );
    assertThat(
        String.format("(a,b,c)=(%d,%d,%d)", a, b, c),
        a * s.x2 * s.x2 + b * s.x2 + c,
        closeTo(0, 0.01)
    );
  }

@Whenに指定した({ "*" })は「@Conditionメソッドがすべて成立(trueを返した)時に実行する」という意味である。 したがって、このメソッドの意図するところは

(When)制約をすべて満たした場合、 方程式を解く、 (Then)すると確かに解ける。

ということになる。

次に異常系だが、

  @Test(expected = IllegalArgumentException.class)
  @When({ "!aIsNonZero" })
  public void solveEquation1$thenThrowIllegalArgumentException() {
    new QuadraticEquation(
        a,
        b,
        c).solve();
  }

この部分はaIsNonZeroメソッドfalseになったとき、という意味だ。 @When({ "!aIsNonZero" })

そして、JUnitの機能で送出されるべき例外の型を確認している。

  @Test(expected = IllegalArgumentException.class)

このメソッド宣言部の意味はこうなる。

(When)aIsNonZero制約に違反した場合、 方程式を解く、 (Then)するとIllegalArgumentExceptionを投げる。

これも見たとおりの意味だ。

実行(その1)

さて、ここまで出来上がったテストを実行するとどうなるか?読者のIDEで実行してみて欲しい。 109件のテストを生成し、6件のみが成功する。

f:id:dakusui:20160314074912p:plain

109件にまで増えている理由は、各因子の水準が増えていることによる。実のところ上で「制約」を定義したものの「制約違反を避けるように組み合わせを選ぶ」処理がまだ作られていない。これは次回、解決方法とともに論じたいが「組み合わせテスト」の趣旨から外れるこまった問題だ。 失敗が増えている理由は、例外を送出するべきところ送出する処理がテスト対象にまだ実装されていないからだ。

生成されたテストスイートや実行結果を見てみると、いくつか改善したい点がある。

  1. テストケースが多すぎる
  2. 正常系のテストと異常系のテストが混ざっていてレビューしづらい
  3. 同時に複数の制約に違反するテストケースが多い。この種のテストケースは多くの場合あまり意味がない。3

これらについても次回はもう少し深く議論し、JCUnitでの解決方法を示したいと思う。

余談

今回の記事を書いてみて思ったのだが、@Whenアノテーション@Givenという名前の方がよかったかもしれない。 すると、

  @Test(expected = IllegalArgumentException.class)
  @Given({ "!aIsNonZero" })
  public void whenSolveEquation1$thenThrowIllegalArgumentException() {

と書け、これは

(Given)aIsNonZero制約に違反している時に (When)方程式を解く (Then)するとIllegalArgumentExceptionを投げる。

こういう意味になる。これはBDDっぽくってひょっとしてかっこいいのではなかろうか。 読者諸賢のご意見を賜りたいところである。

参考

(第ニ回)JCUnitで2次方程式を解くプログラムをテストする。

さて、39件も失敗した前回のテストだが、どのテストがどのように失敗しているかつぶさに見ていこう。 失敗するテストは以下の通り。

{ 1, 3, 4, 6, 7, 8, 9,  
 10,11,12,13,14,15,17,18,19,
 24,25,26,27,28,
 30,31,32,33,34,35,36,37,38,
 40,41,42,43,45,46,48,49,51}

これらが成功していたり、これら以外のものが失敗していたらJCUnitにバグがあることになる。ぜひ知らせて欲しい。

分析

前提として今回のテストで用いたテストメソッドはこうなっている。

  @Test
  public void solveEquation() {
    QuadraticEquation.Solutions s = new QuadraticEquation(a, b,
        c).solve();
    double v1 = a * s.x1 * s.x1 + b * s.x1 + c, v2 = a * s.x2 * s.x2 + b * s.x2 + c;

    assertThat(String.format("%d*x1^2+%d*x1+%d=%f {x1=%f}", a, b, c, v1, s.x1), v1, is(0.0));
    assertThat(String.format("%d*x2^2+%d*x2+%d=%f {x2=%f}", a, b, c, v2, s.x2), v2, is(0.0));
  }

まずテストケース1

java.lang.AssertionError: 1*x1^2+0*x1+100=NaN {x1=NaN}
Expected: is <0.0>
     but: was <NaN>

NaN浮動小数で表すことができない数に対して用いる記号であり、この場合は根を方程式で求めようとすると、虚数になってしまう=実根がないのが原因だ。(問題1:虚数) テストケース4も同様。

次にテストケース3を見てみる。

java.lang.AssertionError: 1*x1^2+100*x1+-100=0.000000 {x1=0.990195}
Expected: is <0.0>
     but: was <1.4210854715202004E-14>

これは、テストとしては根を代入して式を計算すると0になるのを期待しているのだが、実際には1.42 * 10^-14という幾らかの大きさを持つ値になってしまっていることが原因である。係数が100や−100のように比較的大きいと、実数計算を行った際の誤差も大きくなる。結果として式の計算結果が0にならなくなってしまっている。(問題2:丸め誤差

テストケース6も似ている。

java.lang.AssertionError: 1*x1^2+-2147483648*x1+1=1.000000 {x1=2147483648.000000}
Expected: is <0.0>
     but: was <1.0>

しかし、bInteger.MIN_VALUEという大きな絶対値の数であるため、誤差も1.0という大きな値になっている。(問題3:巨大な係数

次にテストケース9。これもNaNだ。

java.lang.AssertionError: 0*x1^2+-1*x1+-100=NaN {x1=Infinity}
Expected: is <0.0>
     but: was <NaN>

しかし、問題1:虚数とは少し事情が違う。aが0であるので、解の公式の分母が0になっている。浮動小数点数の演算では分母が0の計算を行った場合にもNaNが生じるのだ。(問題4:a==0)

「バグ」と「仕様」、「ドキュメント」について

上で見てきたいくつかの問題の修正に先立って「バグ」とは何か、「仕様」や「ドキュメント」とはなにかについて少しだけ論じておきたい。

ソフトウェアのバグには2種類あって2種類しか無い。コードが間違っている。つまり通常我々が呼ぶところの「バグ」(単に「バグ」と呼ぶと紛らわしいので今回のケーススタディのなかでは「製品バグ」と呼ぶことにする)。もうひとつはコードがよって立つべき仕様自体が間違っている「仕様バグ」だ。それゆえ仕様やドキュメントがない状況ならば、どんな動きをしようと「仕様です」と言い張ることが一応は可能だ。だが、どこにも書かれていないとしても実際にはプロダクト設計者の意図、関係者に対する約束や信義、暗黙の前提、業界の慣行や平均的技術水準、社会常識、技術者としての矜持等々からあるソフトウェアのある挙動がバグかどうか判断される。言うなれば「こころの中に仕様がある」という場合もある。程度にもよるがそれで良い場合も多々あろう。

さて、仕様のとおりに作られたプログラムがあり、仕様自体に瑕疵が判明した場合、仕様もプログラムも修正することになる。 しかしこれも「製品バグ」と「仕様バグ」の両方が同時に発生したと考えればよい。 所謂「仕様変更」を仕様バグと考えるかどうか。SIer的な伝統では仕様変更はバグではない、区別する必要があるということになる。お金をもらえるかもらえないかに係るから。 しかし、自分たちで作ったソフトウェアを自分たちで運用する世界ではその区別の重要性は低い。 仕様変更と仕様バグの境界はSIer的マネジメントにおいて必要に応じて決めればいいのであって、ひとまず本稿では興味の対象外である。

ところで「仕様バグ」だけが発生することがあるのか? ある。 実装者が仕様の瑕疵に気づき、より適切な実装を行ったものの、仕様書の更新が行われなかった場合や、仕様のある部分を見ずに実装し、仕様と異なっていたが結果的にその実装のほうがより適切と判明した場合、特殊な条件下で一見奇妙な動作に見えるが精密に検討してみると正しいと言わざるを得ない場合、などがこれにあたる。 この場合にはリリースノートの更新や、仕様書の修正が行われることになる。心の中にしか仕様書が無いなら心の中の仕様書を更新することになる。

実際にどのような粒度のドキュメントがどのような抽象度、どのような詳細さで書かれるべきかはこのエントリの範囲では立ち入らない。どういった粒度や抽象度の仕様が適切かはプロダクト、プロジェクト、企業文化、重要なステークホルダー、担当者の好みなど様々な要因で変わる。ある製品の仕様書は通常、その製品が何をでき何ができないかを明らかにする。「あるべき挙動」がチームや製品の状況などに照らして明々白々なときにはドキュメントの量は減ることであろう。

今回の一連のエントリの中で私が「ドキュメント」や「仕様」というとき、それは単に「ソフトウェア製品の言語化されたあるべき動作」という意味である。ものものしく定式化された体系的書類のことだけではない。

問題の整理

では問題を改めて整理してみよう。 「分析」の節で上がった問題は以下の4つ。

これらが昔風にいうならバグ表の項目、今どきならJIRAのチケットに対応する。

これらをどういう形で決着させるか。実に色々な形があり得る。なぜならばここまでのところ、我々のQuadraticEquationクラスの仕様は以下のものでしかないので様々な側面を明確にする余地があるし、その仕様にしたって正当な理由があれば適切な手順を踏んで仕様を変えることもありえるのがソフトウェア開発というものだ。

QuadraticEquationクラス仕様 version 1

  • 入力:三つの整数a,b,c

  • 出力:二次方程式a x^2 + b x + c = 0を満たす実数x1x2

だから当初予定されていた仕様を変更して虚数解をサポートするという判断に至ることだってあるかもしれない。 が、このポストは、JCUnitの使い方のあらましを示すためのものだ。可能な限り当初の仕様を変えない方向で、これらの問題への対応方法を決めていこう。カッコ内には先程述べたバグの分類(製品バグと仕様バグ)に基づいて、それぞれの問題がどちらに当たるかを記した。

  • 問題1:虚数 二次方程式の解の判別式を用い、実根がない組み合わせが与えられた場合例外を送出する。(仕様バグ、製品バグ)
  • 問題2:丸め誤差 根を方程式に代入した時、その計算結果の絶対値が0.01を下回ること。(仕様バグ)
  • 問題3:巨大な係数 a,b,cいずれも絶対値が100以下とし、その範囲外の値が与えられた場合例外を送出する。(仕様バグ、製品バグ)
  • 問題4:a==0 aに0が与えられた場合例外を送出する。(仕様バグ、製品バグ)

問題の修正(1)

これらの問題を修正するにあたっては、まずは仕様書を更新し、しかるのちテスト対象ソフトウェアを修正するという古式ゆかしい手順を踏んでみよう。

仕様書は以下のように修正されることになる。

QuadraticEquationクラス仕様 version 2

  • 入力:三つの整数a,b,c

    • aが0の場合、例外が送出される。(問題4:a==0)
    • a,b,cのいずれかの絶対値が100より大きい場合、例外が創出される。(問題3:巨大な係数)
    • a,b,cb * b - 4 * c * a >= 0を満たさない場合、例外が送出される。(問題1:虚数)
  • 出力:二次方程式a x^2 + b x + c = 0を満たす実数x1x2

    • 出力される解x1またはx2を上述の2次方程式に代入した時、その絶対値は0.01未満になる。(問題2:丸め誤差)

次回は、テストをこの仕様書に基づいてアップデートする。今風にいうなら「テストファースト」ということになるのだろうか。