状態遷移行列を用いて実行パスの数式表現を得る方法について
ソフトウェアの動作を状態遷移図で表すことができる場合は、状態遷移図を簡単化することで数式表現にすることができ、網羅性の確保が大切なテストケース作成においてこの数式表現を参考にすることができます。 数式表現は、 著者のブログ「ソフトウェアの実行パスの数式表現について 」で記述しているような手順で得ることができますが、ソフトウェアの構造が複雑で状態数が多くなると、手作業でこの手順を行うのは現実的ではない場合があります。数式表現を得るもう一つの方法として、状態遷移図から状態遷移行列を作成して行列計算を繰り返すことで得る方法があります。この方法について記述します。
目次
１．はじめに
ソフトウェア開発時のテストでは、開発したソフトウェアの実行パスを全て実行して適切性を確認する必要があります。 そのためにテストケースを作成しますが、全ての実行パスを漏れなく選択して最低１回は実行する必要があるため、実行パスの選択の網羅性が非常に重要になります。
網羅性を確保したテストケースを作成するためには、ソフトウェアの動作を状態遷移図で表し、それを基に実行パスの数式表現を得て、網羅的なテストケース作成の参考にする方法があります。この方法については、 著者のブログ「ソフトウェアの実行パスの数式表現について に記載しました。 この方法は、状態数が多くなりソフトウェアの構造が複雑になると、手作業でこの手順を行うことが難しくなります。
数式表現を得るもう一つの方法として、状態遷移図から状態遷移行列を作成して行列計算を繰り返すことで得る方法があります。この方法について以下で記述します。
２．状態遷移行列とは
状態遷移行列は、状態間の遷移を行列で表したもので、行列の要素はイベントになっています。図１の[1]に状態遷移図の例、[2]に[1]の状態遷移行列を示します。行列の要素は、例えば[1]で状態$q_{1}$から状態$q_{1}$の遷移はないため[2]の行列の要素は0になっていますが、[1]で状態$q_{1}$から状態$q_{2}$の遷移はイベント$e_{1}$があるので、[2]の行列の要素は$e_{1}$になっています。 このように状態遷移行列は、状態数が2の場合は、2行２列の行列になり、状態遷移図の遷移を全て表すことができます。
以下では、状態遷移行列の要素を$A_{ij}$のように表現します。図１[2]の行列を$A$とした場合、行列の要素$A_{12}$は$A_{12}=e_{1}$となります。
図１ 状態遷移図と実行パスの例
状態遷移行列の積は以下の計算で定義します。状態遷移行列$A$を \[ A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \] とした時、 \[ A^{2} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \\ = \begin{pmatrix} A_{11}A_{11}+A_{12}A_{21} & A_{11}A_{12}+A_{12}A_{22} \\ A_{21}A_{11}+A_{22}A_{21} & A_{21}A_{12}+A_{22}A_{22} \end{pmatrix} \] この行列$A^{2}$の要素に含まれる$+$は、複数のイベント列があることを表しています。
以上の状態遷移行列と行列の積の定義を用いてイベントの列である実行パスを求めてみます。
３．状態遷移行列から実行パスの数式表現を得る方法について
図２の画面遷移図から状態遷移図を作成すると図３を得ることができます。図３の状態$q_{i}$が図２の１つの画面に相当します。図２の赤の実線が実行パスの例です。以下では状態$q_{1}$から出て状態$q_{1}$に戻る状態遷移のイベント列を求める実行パスとします。
図２ 画面遷移図と実行パスの例
図３ 図２の状態遷移図
この図３の状態遷移図から状態遷移行列を作成すると図４を得ることができます。 この状態遷移行列から実行パスであるイベントの列を得るには、状態遷移行列の積の計算を複数回行います。
図４ 図３の状態遷移行列
図４の状態遷移行列を式(1-1)に示すように$R$とします。
\[ R = \begin{pmatrix} 0 & e1 & 0 & 0 & 0 & 0 \\ e10 & 0 & e2 & 0 & 0 & e8 \\ 0 & 0 & 0 & e3 & e6 & 0 \\ e4 & e5 & 0 & 0 & 0 & 0 \\ 0 & 0 & e7 & 0 & 0 & 0 \\ 0 & e9 & 0 & 0 & 0 & 0 \end{pmatrix} \qquad \ldots \text{(1-1)} \]
この$R$を使って$R^{2}$を計算すると式(1-2)を得ます。 状態遷移行列の積の計算では、行列の要素の積が$0 \cdot e_{i}$となる場合は結果を$0$と記載します。また、$e_{i} \cdot e_{j}$となる場合は、結果を$e_{i}e_{j}$のように記載します。
この$R^{2}$の行列の要素は状態$q_{i}$から出て状態$q_{j}$に２回の遷移で到達するイベントの列になります。例えば、状態$q_{1}$から出て状態$q_{1}$に戻る場合は、状態遷移行列$R^{2}$の要素は$e_{1}e_{10}$となっています。これは状態$q_{1}$から２回の遷移で状態$q_{1}$に戻ることができて、そのイベント列は$e_{1}e_{10}$であることを表しています。
\[ R^{2} = \begin{pmatrix} 0 & e1 & 0 & 0 & 0 & 0 \\ e10 & 0 & e2 & 0 & 0 & e8 \\ 0 & 0 & 0 & e3 & e6 & 0 \\ e4 & e5 & 0 & 0 & 0 & 0 \\ 0 & 0 & e7 & 0 & 0 & 0 \\ 0 & e9 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & e1 & 0 & 0 & 0 & 0 \\ e10 & 0 & e2 & 0 & 0 & e8 \\ 0 & 0 & 0 & e3 & e6 & 0 \\ e4 & e5 & 0 & 0 & 0 & 0 \\ 0 & 0 & e7 & 0 & 0 & 0 \\ 0 & e9 & 0 & 0 & 0 & 0 \end{pmatrix} \\ = \begin{pmatrix} e1e10 & 0 & e1e2 & 0 & 0 & e1e8 \\ 0 & e10e1+e8e9 & 0 & e2e3 & e2e6 & 0 \\ e3e4 & e3e5 & e6e7 & 0 & 0 & 0 \\ e5e10 & e4e1 & e5e2 & 0 & 0 & e5e8 \\ 0 & 0 & 0 & e7e3 & e7e6 & 0 \\ e9e10 & 0 & e9e2 & 0 & 0 & e9e8 \end{pmatrix} \qquad \ldots \text{(1-2)} \]
次に３回の状態遷移である$R^{3}$を計算してみます。これは$R^{2}$の計算結果と$R$の積を計算することで得ることができます。この計算結果を式(1-3)に示します。
\[ R^{3} = \begin{pmatrix} e1e10 & 0 & e1e2 & 0 & 0 & e1e8 \\ 0 & e10e1+e8e9 & 0 & e2e3 & e2e6 & 0 \\ e3e4 & e3e5 & e6e7 & 0 & 0 & 0 \\ e5e10 & e4e1 & e5e2 & 0 & 0 & e5e8 \\ 0 & 0 & 0 & e7e3 & e7e6 & 0 \\ e9e10 & 0 & e9e2 & 0 & 0 & e9e8 \end{pmatrix} \begin{pmatrix} 0 & e1 & 0 & 0 & 0 & 0 \\ e10 & 0 & e2 & 0 & 0 & e8 \\ 0 & 0 & 0 & e3 & e6 & 0 \\ e4 & e5 & 0 & 0 & 0 & 0 \\ 0 & 0 & e7 & 0 & 0 & 0 \\ 0 & e9 & 0 & 0 & 0 & 0 \end{pmatrix} \\ = \begin{pmatrix} 0 & e1e10e1+e1e8e9 & 0 & e1e2e3 & e1e2e6 & 0 \\ e10e1e10+e8e9e10+e2e3e4 & e2e3e5 & e10e1e2+e8e9e2+e2e6e7 & 0 & 0 & e10e1e8+e8e9e8 \\ e3e5e10 & e3e4e1 & e3e5e2 & e6e7e3 & e6e7e6 & e3e5e8 \\ e4e1e10 & e5e10e1+e5e8e9 & e4e1e2 & e5e2e3 & e5e2e6 & e4e1e8 \\ e7e3e4 & e7e3e5 & e7e6e7 & 0 & 0 & 0 \\ 0 & e9e10e1+e9e8e9 & 0 & e9e2e3 & e9e2e6 & 0 \end{pmatrix} \qquad \ldots \text{(1-3)} \]
このように$R^{n}$の計算では$n$が増えるとかなり計算が大変になるため、プログラムを作成して計算するのが有効です。このとき反復の行列計算になるため終了条件が必要ですが、これは「特定の行列の要素に全てのイベントが含まれる」などの条件が有効です。 例えば、状態$q_{1}$から状態$q_{1}$に戻る場合について、$R^{n}$の行列計算を行う時は、行列$R^{n}$の要素$R^{n}_{11}$に全てのイベントが含まれた時、反復計算を終了することになります。
状態遷移行列$R$について$R^{n}$を計算すると、$n=6$の時、$R^{6}_{11}$は、
\[ R^{6}_{11}= e1e2e3e5e10e1e10+e1e10e1e2e3e5e10+e1e8e9e2e3e5e10 \\\\ +e1e2e6e7e3e5e10+e1e2e3e5e8e9e10+e1e2e3e5e2e3e4 \]
になります。 この$R^{6}_{11}$には全てのイベントが含まれており、これらのイベント列を実行パスとして利用してもよいのですが、実行パスは最低１回実行すればよいので、例えば$e1e2e3e5e10e1e10$と$e1e10e1e2e3e5e10$のように重複しているイベント列を削除します。このような重複削除を行うと、 $e1e2e3e5e10e1e10$、$e1e8e9e2e3e5e10$、$e1e2e6e7e3e5e10$、$e1e2e3e5e2e3e4$ が残ります。また、必要ならば各イベント列の中でも不要なイベントがある場合はこの時点で削除をします。 例えば、$e1e2e3e5e10e1e10$の中の$e1e10$は不要であれば削除して$e1e2e3e5e10$にします。
以上のような計算により、４つのイベント列
$e1e2e3e5e10e1e10$、$e1e8e9e2e3e5e10$、$e1e2e6e7e3e5e10$、$e1e2e3e5e2e3e4$
が得られ、これが状態$q_{1}$から出て状態$q_{1}$に戻る全ての実行パスになります。 この実行パスを基にしてテストケースを作成すれば、漏れなくテストを実行することができるようになります。
４．まとめ
ソフトウェアの稼働後にバグを出さないためにはテスト時の網羅性の確保が重要です。そのためにはソフトウェアに含まれる全ての実行パスを把握し、テストで全てを実行して適切性を確認する必要があります。 著者のブログ「ソフトウェアの実行パスの数式表現について で画面遷移図などの状態遷移図から実行パスの数式表現を得る方法を示しましたが、状態数が多く状態遷移が複雑になる場合は手作業で数式表現を得ることが難しくなります。また得られた数式表現は汎用的な表現になるため、数式表現が長くなる場合はこれから漏れなくテストケースを導き出すのは難しくなります。
本ブログでは状態遷移行列を作成して行列計算によって数式表現を得る方法について記述しました。反復的に行列計算を行うことで実行パスの数式表現を得ることができるため、プログラムによって自動的に実行パスを得ることができます。
効率的で漏れがないテストを行うために、この得られた実行パスを参考にすることで、漏れがないテストケースの作成に役立てることができるようになります。
