ソフトウェアの実行パスの数式表現について
ソフトウェアのテストでは、ソフトウェアの動作の適切性を、実行パスの実行の結果が妥当であるかによって判断しています。 著者のブログ「ソフトウェアのバグ摘出モデルとバグの収束性、テストの網羅性について 」で記述しているように、 稼働後にバグを出さないためにはテストでの実行パスの網羅性が非常に重要になります。網羅性を表す尺度として網羅率がありますが、実行パスの数がソフトウェアにどのくらい存在するかはソフトウェアの構造が複雑であるため把握することが困難な場合があり、網羅率を実際に計算することは難しい場合があります。このような実行パスを分析するために実行パスの表現方法として数式表現（正規表現）について考え、実行パス数や実行パスの選択について検討してみました。
目次
１．はじめに
ソフトウェアのテストでは、ソフトウェアの動作の適切性を、実行パスの実行の結果が妥当であるかによって判断しています。 著者のブログ「ソフトウェアのバグ摘出モデルとバグの収束性、テストの網羅性について 」で記述しているように、 残存バグ数$Δ\bar{x}$は、 \[ Δ\bar{x}= a \cdot (1 - \frac{n}{N_{p}}) \qquad \ldots \text{(1-1)} \] のような関係で表すことができます。ここで、$a$はソフトウェアに作り込まれた全バグ数、$N_{p}$は実行パスの総数、$n$は実行された実行パスの数であり、$\frac{n}{N_{p}}$は実行パスの網羅率を表します。 この網羅率の分母である実行パスの総数$N_{p}$をカウントすることができるかが重要になりますが、一般にソフトウェアはループや条件分岐があり構造が複雑であるため実行パスを網羅的に把握することが困難な場合があります。
以下では、ソフトウェアを状態遷移図で表すことができる場合について実行パスを定義し、数式表現（正規表現）で表すことで、実行パス数や実行パスの選択について検討してみました。
２．ソフトウェアの実行パスについて
図１にソフトウェアの動作を画面遷移図で表した例を示します。この図１の赤の実線が実行パスの例です。 この例では１つの画面が１つの状態に相当します。赤い実線の実行パスは画面$q_{1}$から画面$q_{2}$に遷移して最終的に画面$q_{1}$に戻ります。実行パスの定義としては、開始状態と終了状態が必ず同一であるという条件は設定しません。例えば、画面$q_{2}$から画面$q_{6}$への遷移も実行パスであるとします。
状態から状態への遷移には、何らかのイベントがあるとします。このイベントは画面遷移の場合は、キーボードやマウスのボタンクリックなどの外部入力等が相当します。 図１ではこのイベントは$e_{1}$などのように表し、画面からの遷移の矢印の周辺に記載しています。
状態遷移図で実行パスを表現する場合、状態の列で表現する方法とイベントの列で表現する方法があります。 図１の赤い実線の実行パスについて、状態の列として表現すると$q_{1}$、$q_{2}$、$q_{3}$、$q_{5}$、$q_{3}$、$q_{4}$、$q_{1}$になり、これを$q_{1}q_{2}q_{3}q_{5}q_{3}q_{4}q_{1}$のように表現します。これは状態を$q_{1}$、$q_{2}$、$q_{3}$、$\ldots$のように順に遷移することを表します。 また、イベントの列については、$e_{1}$、$e_{2}$、$e_{6}$、$e_{7}$、$e_{3}$、$e_{4}$のようになるため、これを$e_{1}e_{2}e_{6}e_{7}e_{3}e_{4}$のように表現します。これはイベントを$e_{1}$、$e_{2}$、$e_{6}$、$\ldots$のように順に実行することを表します。 状態遷移は状態の列とイベントの列のどちらの表現も可能ですが、以下ではイベントの列として表現して実行パスを考えることにします。
図１ 実行パスの例
３．状態遷移図の簡単化から数式表現を作成する方法について
３．１ 簡単化のルール
状態遷移図から実行パスの数式表現（正規表現）を得るためには、状態遷移図から状態を順に削除していき、状態遷移図を簡単化することでイベントの列である実行パスの数式表現（正規表現）を得ます。 参考文献1)に記載の内容を参考にして、 状態の削除のためのルールを以下で説明します。
（１）ルール１
図２の[1]のように、状態$q_{1}$から状態$q_{2}$にイベント$e_{1}$で遷移し、状態$q_{2}$から状態$q_{3}$にイベント$e_{2}$で遷移する場合、[2]のように状態$q_{1}$から状態$q_{3}$にイベント$e_{1}e_{2}$で遷移するように書き換える。
図２ 簡単化ルール１
（２）ルール２
図３の[1]のように、状態$q_{1}$と状態$q_{2}$の間にイベント$e_{1}$とイベント$e_{2}$の２つの遷移がある場合、[2]のようにイベント$e_{1}+e_{2}$で状態$q_{1}$から状態$q_{2}$に遷移するように書き換える。$e_{1}+e_{2}$は「イベント$e_{1}$と$e_{2}$のどちらか」を数式表現で表したものである。
図３ 簡単化ルール２
（３）ルール３
図４の[1]のように、状態$q_{1}$からイベント$e_{1}$で状態$q_{2}$に、状態$q_{2}$からイベント$e_{4}$で状態$q_{4}$に、状態$q_{2}$からイベント$e_{2}$で状態$q_{3}$に、状態$q_{3}$からイベント$e_{3}$で状態$q_{2}$に遷移する場合、状態$q_{2}$と状態$q_{3}$の間の遷移を$(e_{2}e_{3})^{*}$で表し、[2]のように状態$q_{3}$を削除し、状態$q_{2}$から出る全てのイベント（この場合はイベント$e_{4}$）の先頭に$(e_{2}e_{3})^{*}$を付け状態$q_{4}$に遷移するように書き換える。$(e_{2}e_{3})^{*}$の${*}$は、０回以上の繰り返しを表す。
図４ 簡単化ルール３
（４）ルール４
図４の[1]の状態遷移図に、状態$q_{3}$から状態$q_{4}$に直接遷移するイベント$e_{5}$が図５の[1]のようにある場合、イベント$e_{5}$のために状態$q_{3}$を一度で削除できない。まずはルール３によって、イベント$e_{3}$を削除し、[2]のようにイベント$e_{4}$をイベント$(e_{1}e_{2})^{*}e_{4}$に書き換える。その後、状態$q_{2}$から状態$q_{3}$を経由して状態$q_{4}$への遷移を、[3]のようにルール１によって、状態$q_{3}$の削除と、イベント$e_{2}$とイベント$e_{5}$をイベント$e_{2}e_{5}$と書き換える。
図５ 簡単化ルール４
３．２ 簡単化の事例
図１の画面遷移図を状態遷移図で表すと、図６のようになります。 この状態遷移図を前節で説明した簡単化のルールを適用して数式表現を得るまでの流れを以下に説明します。図６ 図１の状態遷移図
まず最初に準備として、図６のように 開始と終了が同一の状態$q_{1}$になっている時は、開始状態と終了状態を、$q_{1}\_start$と$q_{1}\_end$のように分けます。この時開始状態と終了状態が同じであることを示すために、この２つの状態の間を図７のように点線で結びます。また図７に示すように開始状態は他の状態に遷移するイベントのみ存在し、終了状態は他の状態から遷移してくるイベントのみ存在します。
図７ 開始状態と終了状態を分ける
図７の状態$q_{6}$を削除するために、ルール３を適用します。状態$q_{2}$からはイベント$e_{2}$と$e_{10}$が出ているので、$(e_{8}e_{9})^{*}$を$e_{2}$と$e_{10}$の前に付けます。この結果を図８に示します。
図８ 状態$q_{6}$を削除した結果
図８の状態$q_{5}$を削除するために、ルール３を適用します。状態$q_{3}$からはイベント$e_{3}$が出ているので、$(e_{6}e_{7})^{*}$を$e_{3}$の前に付けます。この結果を図９に示します。
図９ 状態$q_{5}$を削除した結果
図９の状態$q_{3}$を削除するために、ルール１を適用します。$q_{3}$を削除することにより、状態$q_{2}$と$q_{4}$の間をイベント$(e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}$で結びます。
図１０ 状態$q_{3}$を削除した結果
図１０はルール４が適用できる状態遷移が含まれています。まず図１０のイベント$e_{5}$を削除することを考えます。ルール４の図５の[1]から[2]にするために、図１０のイベント$e_{5}$を削除して、イベント$(e_{8}e_{9})^{*}e_{10}$を$(e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}$に書き換えます。この結果を図１１に示します。
図１１ イベント$e_{5}$を削除した結果
図１１にルール４の図５の[2]から[3]（ルール１と同じ）を適用します。これによって状態$q_{4}$を削除することができます。この結果を図１２に示します。
図１２ 状態$q_{4}$を削除した結果
図１２にルール２を適用します。この結果を図１３に示します。
図１３ 状態$q_{2}$から$q_{1}\_end$間のイベントを１つにした結果
図１３にルール１を適用して状態$q_{2}$を削除します。この結果を図１４に示します。この図１４には状態が$q_{1}\_start$と$q_{1}\_end$の２つの状態しかないため、状態遷移図の簡単化は終了です。この時状態$q_{1}\_start$と$q_{1}\_end$の間のイベント $e_{1}((e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{5})^{*}(e_{8}e_{9})^{*}e_{10} + e_{1}(e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{4}$ が状態遷移図を表す数式表現であり、この中に全ての実行パスが含まれています。
図１４ 数式表現の結果
４．数式表現から得られること
４．１ 実行パス数の最小値と最大値
図１４で得られたイベントの列 \[ e_{1}((e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{5})^{*}(e_{8}e_{9})^{*}e_{10} + e_{1}(e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{4} \qquad \ldots \text{(4-1)} \] は実行パスの数式表現ですが、この式には「+」が含まれており、２つの項があります。 このことから、網羅率を1にするためには最低２つの実行パスの実行が必要であり、実行パス数の最小値は２であることがわかります。これは図７の$q_{1}\_end$に２つのイベント$e_{4}$、$e_{10}$が入っていることからも明らかです。
では、最大値はいくつになるかですが、これは$(\ldots)^{*}$によって無限の繰り返しが可能であるため特定できません。 全てのイベントを最低１回は実行するという制約を設定すれば、イベントの数が最大値になります。式(4-1)ではイベント数は１０ですので、実行パス数の最大値は１０になります。
４．２ McCabeの循環的複雑度との関係
McCabeの循環的複雑度は以下のように定義されています。 \[ Mc = E − N + 2P \] ここで、$Mc$は循環的複雑度、$E$はグラフのエッジ数、$N$はグラフのノード数、$P$は連結成分の個数です。
図６に対して適用すると、$E=10$、$N=7$、$P=1$であるため、循環的複雑度$Mc$は、 \[ Mc = 10 - 7 + 2 \cdot 1 = 5 \] となります。これは状態遷移図の中に含まれるループの数と一致しています。
循環的複雑度がループの数と一致することを参考にして、数式表現である式(4-1)について考えてみます。
式(4-1)の$(\ldots)^{*}$は０回以上の繰り返しを表していますのでループになっています。 まず、$*$を全て０回とすると、式(4-1)は \[ e_{1}e_{10} + e_{1}e_{2}e_{3}e_{4} \qquad \ldots \text{(4-2)} \] となります。式(4-2)には２つの項が含まれており、図６に示すように、状態$q_{1}$が開始状態であり終了状態であるため、この２つ項によってループが２つ存在することになります。
次に、式(4-1)の第１項$e_{1}((e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{5})^{*}(e_{8}e_{9})^{*}e_{10}$について考えます。 $(\ldots)^{*}$はループを表しますので、 \[ e_{8}e_{9} \qquad \ldots \text{(4-3)} \\\\ e_{6}e_{7} \qquad \ldots \text{(4-4)} \] がループであることがわかります。 また$((e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{5})^{*}$について考えると、 $((e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{5})^{*}$の内側の$(\ldots)^{*}$にある式(4-3)と式(4-4)の「*」を０回にすると、 \[ e_{2}e_{3}e_{5} \qquad \ldots \text{(4-5)} \] が得られ、外側の$(\ldots)^{*}$によってループになっていることがわかります。
式(4-1)の第２項 $e_{1}(e_{8}e_{9})^{*}e_{2}(e_{6}e_{7})^{*}e_{3}e_{4}$ については、式(4-2)の第２項と式(4-3)と式(4-4)が含まれており、他のループは存在しません。
以上で式(4-1)から全てのループを得ることができ、式(4-2)から式(4-5)まででループの数の合計は５になります。
以上のように、McCabeの循環的複雑度は「４．１ 実行パス数の最小値と最大値」で示した実行パス数の最小値と最大値の間の数値になっています。
５．まとめ
ソフトウェアの稼働後にバグを出さないためにはテスト時の網羅性の確保が重要です。 網羅性を確保するためにはテストで全ての実行パスを実行する必要があり、実行パスを全て把握することが必要になります。 ソフトウェアを状態遷移図で表して数式表現にすることによって網羅性を確保するために参考にすることができます。
例えば、実行パスを構成する状態遷移図のイベントの列をどのように選択すれば実行パスを網羅することができるか検討する際に参考になります。 １つのテストケースは１つの実行パスを表しているため、一般に複数のテストケースで全ての実行パスを網羅する必要があります。この時どのように実行パスをイベントの列で構成すれば良いか検討する際に数式表現は役立てることができます。
参考文献
1) Michael Sipser著, 太田和夫・田中圭介監訳, 阿部正幸・植田広樹・藤岡淳・渡辺治訳：“計算理論の基礎 原著第２版 １ オートマトンと言語”, 共立出版, 2008, P77〜P88
