投稿記事 ( 論文 )順序列テスト基準に基づく並行処理
プログラムのテスト充分性評価

Reliability of Testing based on Ordered
Sequence Testing Criteria for Concurrent
Programs1

伊東栄典†∗ 学生会員 9111791
川口豊§

正会員

古川善吾‡

正会員

牛島和夫†

正会員

†
‡

93077527809183
6312759

九州大学工学部情報工学科

九州大学情報処理教育センター§

現在、沖電気工業株式会社

Eisuke Itoh† , Yutaka Kawaguti‡, Zengo Furukawa§
and Kazuo Ushijima††∗

Department of Computer Science and Communication
Engineering, Kyushu University.
‡
Currently, OKI Electronics Industry Corporation. §Educational Center for Information Processing,
Kyushu University.

〒 812 福岡市東区箱崎 6-10-1 Tel.(092)641-1101 (Ext.5900)
E-mail: itou@csce.kyushu-u.ac.jp2

概要
並行処理プログラムの普及に伴い, その信頼性向上手法としてテストが重要になっている. 一般にテストでプログラムの正しさを証明できない. このためテストの終了を判定するためのテスト充分性評価が必要になる. テスト充分性評価には, 被覆率をテストの終了判定の指標として用いる方法が逐
次処理プログラムで実用化されている. テスト実施前に抽出した測定事象と, テスト実施中に実行された事象との割合が被覆率である. テスト基準に基づき測定事象は定められる.
逐次処理プログラムに比べ並行処理プログラムは動作が複雑である. そのため並行処理プログラムのテスト充分性評価に逐次処理プログラムで用いられているテスト充分性評価法を利用するだけでは十分ではない. 並行処理プログラムに対する新たなテスト基準が必要である.
本稿では並行処理プログラムに対するテスト基準として, プ
ロセス間の同期や通信の実行順序に基づく「順序列テスト基準」を提案し, これを用いたテスト充分性評価法について検討する. 順序列とは, 並行に実行されるプロセス間での同期や通信を行う文の実行系列である. 列の長さを変化させることにより, プログラムのさまざまな誤りに対応できる. 長さ

1 の順序列テスト基準は文被覆テスト基準に「包含される」.
長さ 2 の順序列テスト基準は通信誤りに対し「信頼できる」.
順序列の長さをプロセス数 +1 にすれば単純なデッドロックに対し「信頼できる」.

3Abstract
Testing of concurrent programs is important for increasing reliability of the programs. Generally, it is impossible toprove correctness of programs through testing. Therefore, itis necessary to decide when the program testing is completed.
The evaluation of testing reliability reveals us on condition
for testing completion. Coverage represents the testing reliability objectively.
Because the behavior of a concurrent program is more complex than that of a sequential program, it is not suﬃcientfor concurrent programs to be evaluated of reliability withtesting criteria for sequential programs. New testing criteria
must be introduced for concurrent programs.
This paper proposes new testing criteria, Ordered Sequence
Criteria (OSC) for concurrent programs. OSC only pay attention to interprocess communication and synchronization. An
OSCk selects k-length sequences which consist of commands
related to communication or synchronization. In testing, allsequences should be executed at least once. An OSCk requires various levels of testing according to values of k. The
OSCn+1 is reliable for a program which is correct or which
includes simple deadlocks, where n represents the number ofprocesses in the program.

4

1

はじめに
プログラムを作成する場合, 開発費の約 50%がテスト費用であると言われている [1]. このため, 従来の逐次処理プログ
ラムでは, テスト費用削減のためにテスト法の研究やテスト支援ツールの開発が進んでいる. 現在, マルチプロセッサシ
ステムや Local Area Network などの普及に伴ない並行処理
プログラムが実際に用いられるようになってきた. このため並行処理プログラムの信頼性向上手法としてのテストが重要になってきている.
逐次処理プログラムに対するテスト法を, そのまま並行処
理プログラムに適用するのでは, 並行処理プログラムの特性を充分にテストできない. しかしながら, 並行処理プログラ
ムに対するテスト法は十分な研究がなされているとは言い難
く, またプログラム開発現場で実用に耐え得るツールも少ない. このため並行処理プログラムに対するテスト法の研究およびテスト支援ツールの開発が必要である.
並行処理プログラムのテストを難しくする原因の 1 つに並行処理プログラムの非決定的な動作がある. 逐次処理プログ
ラムでは, 同じ入力に対する出力は一般に一定である. これに対し並行処理プログラムでは, プロセスの実行順序によって, 同じ入力に対し出力が異ることがある. そのため並行処
理プログラムをテストする際には, プログラムの入力 (テストデータ) だけでなくプロセスの実行順序や命令の実行系列を考慮する必要がある.
テストでは, 並行処理プログラムの正しさはテストを実施した際の入力および実行系列に対してのみ主張できる. 並行処理プログラムの正しさをテストで証明するためには, プロ

5グラムの入力と実行系列との組み合わせをすべて実行しなけ
ればならない. 一般にプログラムの入力値と実行系列との組の個数は膨大になる. そのためテストでプログラムの正当性を証明することは現実的に不可能である.
テストでプログラムの正当性を証明できないため, どこま
でテストを行えば充分であるかをいかに評価するのかが問題となる. この評価をテスト充分性評価といい, テストに関する研究課題の 1 つとなっている. テスト充分性評価法の 1 つに, 被覆率 (Coverage) を指標にする技法がある. 被テストプ
ログラムからテスト実施時に実現されるべき事象である測定
事象を, テスト実施前に予め抽出する. テスト実施の際に実現された測定事象の割合が被覆率である. 測定事象はテスト
基準により定義される.
本稿では, 並行処理プログラムに対するテスト基準として順序列テスト基準 (Ordered Sequence Criteria : OSC) を提案
し, その特性を定性的に分析する. これにより順序列テスト基
準の利用可能性および理論的な限界を明確にできる. 順序列
テスト基準は, 並行処理プログラムをインターリーブモデル
で解釈した場合における命令の実行系列に基づいており, 通信文や同期文の実行系列 (順序列) を測定事象とするテスト基
準である.
第 2 章は, テスト充分性評価法について考察する. 第 3 章で順序列テスト基準背景および定義を述べる. 第 4 章では, 並行処理プログラムの例について順序列テスト基準およびテスト
例を示す. 第 5 章で, 順序列テスト基準およびそれを用いたテスト法の特性について定性的に分析する. 第 7 章ではまとめと今後の課題について述べる.

6

2

テスト充分性評価法
テストの充分性をプログラムの構造と実行時の測定とに基づいて評価するのがテスト充分性評価法である. 逐次処理プ
ログラムでテスト充分性評価に用いている被覆率 (Coverage)
を並行処理プログラムのテスト充分性評価にも用いる.
被覆率を次のように定義する. まず, テストを行う前にプログラムの中から実行 (被覆) されるべき測定事象を抽出する.
この測定事象の集合の中で, テスト実施で実際に実行された
測定事象の割合が被覆率である. 被覆率 C の形式的な定義は次の通りである.
【定義】 1

C=

被覆率 C

|W |
,
|M|

ここで M は被テストプログラム内の測定事象の集合を, W は実行された測定事象の集合を, | · | は集合の要素数を表す. 2被覆率を求めるためにはテストを実施する前に測定事象が抽出できなければならない. この測定事象はテスト基準により定義される. 現在までに様々なテスト基準が提案されている [2, 3, 4, 5, 6, 7].
逐次処理プログラムでは, 文被覆 (all-statements) テスト基準や, 枝被覆 (all-branches) テスト基準, 定義使用被覆 (all-DU-

paths) テスト基準などのテスト基準が実用化されている. 文
被覆テスト基準は C0 テスト基準と, 枝被覆テスト基準は C1
テスト基準と, 呼ばれることがある. また C0 や C1 を拡張した全路 (all-paths) テスト基準がある. これはプログラム内に存在するすべての実行経路を測定事象とするテスト基準である. 全路テスト基準は C∞ テスト基準とも呼ばれる.
7

ここに挙げたテスト基準に基づいて算出される被覆率が 100%に達しても, 被テストプログラムの正しさを証明するものではない. しかしながら, これらの被覆率はテスト充分性を定量的に表す実用的な指標の 1 つとして用いられている.
逐次処理プログラムのテスト基準を用いて, 並行処理プロ
グラムのテスト充分性を評価するのは十分ではない. これは逐次処理プログラムのテスト法が並行処理プログラム特有の通信や同期, 非決定性を考慮に入れていないためである. このことを簡単な例で示す.
図 1 のように, 並行処理プログラム P が 2 つのプロセス P1 ,P2 を持つとする. このプログラムはプロセス P1 がメモリ mに “1” を, P2 が同じ m に “2” を書き込むものである. P を 1
度実行すれば P1 , P2 内のそれぞれの全実行経路が被覆されたことになり, C∞ テスト基準を満足する. 逐次処理プログラムの場合, C∞ テスト基準の被覆率が 100%に達すればプログラ
ム内のすべての誤りを検出する可能性がある. しかしながら,並行処理プログラム P の正しさは証明できない. 2 つのプロセスの代入文の実行順序が 2 つあるのでそのどちらもテストしなければならない. このように逐次処理プログラムのテス
ト基準だけで並行処理プログラムのテスト充分性を評価するのは妥当ではない.
並行処理プログラムのテスト充分性を評価するためには, 並行処理プログラム特有の通信や同期, 非決定性を考慮に入れたテスト基準が必要である. テスト基準は, 定量的に評価が可能でかつ利用が容易でなければならない.
並行処理プログラムにおける被覆率を用いたテスト充分性
評価についてはいくつかの提案が行われている [3, 4, 6, 8].
Tai らは同期列 (Syn-Sequence) を定義し, 並行処理プログ
8ラムにおける非決定的な実行を同期列に従い決定的に再実行させる方法を提案している [8]. 並行処理プログラムを決定的に再実行させることにより誤りを再現することが可能になる.
これによりプログラムのデバッグを容易にする. またデバッ
グだけでなく同期列をテストにおける測定事象と考える方法としても提案している [9].
古川らは Ada 並行処理プログラムを対象に, タスク間の通信および同期をランデブー通路として定義し, このランデブー
通路をテストにおける測定事象とするテスト充分性評価法を提案している [3]. また, 共有変数のデータフローに着目した
広域データフローテスト基準も提案している [4]. これらはAda 並行処理プログラムにのみ注目したテスト基準であるた
め一般の並行処理プログラムのテスト充分性を評価するものとは言い難い.
Taylor らはプログラムのプロセスの状態の組合せ (並行状態) を節点とし, 並行状態を変更する事象を枝とする並行状態
グラフを定義した [6]. テストを実施したときに実現された並行状態グラフの節点や枝の被覆率によってテスト充分性を評価する. しかしながら並行状態グラフには次の 2 つの問題点がある.
(１) 並行状態グラフの節点や枝の数がプロセス数に対して組合せ論的に増大する.
(２) 並行状態グラフを定義するためにはプロセスの数が静的に決まっていなければならない.
並行処理プログラムには, 動的にプロセスが生成され, 生成されたプロセス間で通信や同期を行いながら処理を進めるプ
ログラムが多い. このためプロセス数が静的に決まっていなければならない並行状態グラフは実用的とは言い難い.
9

本稿で提案する順序列テスト基準は, ソースコードに基づ
くテスト基準である. プロセス数がテストの実施前に決まっていなくとも, テストの実施前に順序列の長さを決めておけ
ばソースコードからテストにおける測定事象が抽出できる.
従って Taylor の並行状態グラフにおける問題点の (2) は回避
できる.

3

順序列テスト基準

3.1

並行処理プログラムの動作モデル

順序列テスト基準を定義する前に, 並行処理プログラムの動作モデルについて考察する. ここではインターリーブモデ
ルに基づいた動作モデルを考える [10]. インターリーブモデ
ルは, 並行処理プログラムを単一のプロセッサで実行する場
合を表わすためのモデルである.
インターリーブモデル上では並行処理プログラムの動作を次の様に考える. 並行処理プログラム P は複数のプロセスから成るとする. プロセスは逐次的に命令を実行する. プロセッ
サは実行可能な命令を１つ選択して実行する. プロセス間の同期や通信に関する命令とそれらによる制約とを除き, どの命令を選出するかは任意である. プロセッサが実行する命令
はプログラム内のプロセスに記述されている命令のみであり,その他の命令が実行されることはない. プログラム P 全体での命令の実行系列は, プロセッサの状態により変化する.
図 1 の並行処理プログラム P を実行する際, インターリー
ブモデル上で実現可能な実行系列の集合は, 次のようになる.

E(P) = { < 123456 >,10

< 124356 >, < 124536 >, < 124563 >,< 142356 >, < 142536 >, < 142563 >,< 145236 >, < 145263 >, < 145623 >,< 412356 >, < 412536 >, < 412563 >,< 415236 >, < 415263 >, < 415623 >,< 451236 >, < 451263 >, < 451623 >,< 456123 > }.
実現可能な実行系列をすべて実行させればプログラム内のすべての誤りを検出できる可能性がある. しかしながら, 一
般の並行処理プログラムにおいて, 実現可能な実行系列の数
は組み合わせ論的に増大するし, 無限ループがある場合には無限になる. 実行可能な実行系列をすべて実行することは現実的に不可能である. 実用的時間内にテストを終了するためにはより簡易なテストでなければならない.
並行処理プログラムの特徴は, 複数のプロセスが同時に処理を行うために発生する, 非決定性とプロセス間の通信や同期との 2 つである. そこで, 並行処理プログラムの特徴を調べるテスト基準を考える.
インターリーブモデルでは, 入力データが同じ場合, 局所変数への代入文や参照文のプロセス間における実行順序がプログラム全体の実行結果を変化させることはない. 通信や同期などの並行処理に関する文 (通信同期文) の実行順序は結果を変化させる可能性がある. そこで図 2 のように, プロセス間の通信同期文だけに注目し, これらの命令を組合せた順序列を考える. この列をテストにおいて実行すべき事象とする. 測
定事象数を有限にするため, 有限長の通信同期文の列を測定事象とする.
11

並行処理プログラムの特徴として, 一つのソースコードから複数のプロセスを生成するプロセスの動的生成がある. 図

3 は, ソースコードでは一つのプロセスであるけれども, 実行
時に複数のプロセスが生成され, 互いに通信を行うプログラムである. このプログラムでは, 通信同期文 3 が連続して実行される. 同一の通信同期文を複数個含む列も測定事象含にめる必要がある.
3.2

定義

以下に順序列テスト基準の形式的な定義を示す.
【定義】 2

順序列テスト基準 : OSCk , k ≥ 1

OSCk = {< s1, s2 , · · · , sk > |sj ∈ Sync, 1 ≤ j ≤ k},
ここで, sj , 1 ≤ j ≤ k, は通信同期文, < · > は順序列, Sync
はプログラム内のすべての通信同期文からなる集合 (通信同期文集合) を表す. OSCk はテストの際に実行されるべき測定

2

事象の集合である.
以後, 通信同期文の順序列を単に順序列と表記する.

順序列テスト基準 OSCk の k に具体的な値を与えた場合, 順
序列テスト基準の持つ意味は以下の通りである.

k = 1 の場合
OSC1 = {< s >}.
OSC1 ではプログラム内に存在するすべての通信同期文それぞれがテストにおける測定事象である. OSC1 は, プログラム
内のすべての同期通信文を少なくとも 1 回実行することを要12

求するテスト基準である. C0 テスト基準が満されたならば,

OSC1 テスト基準も満される.
k = 2 の場合
OSC2 = {< s1 , s2 >}.
OSC2 では, プログラム内の通信同期文の長さ 2 の順序列がテストにおける測定事象である. OSC2 テスト基準を満足すれば, プログラム内における 2 つのプロセス間の通信や同期を少なくとも 1 回実行する. Ada 並行処理プログラムにおけるランデブーテスト基準 [3] や共有変数のデータフローテスト
基準 [4] は, この OSC2 テスト基準の特別な場合である.
k = 3 の場合
OSC3 = {< s1 , s2, s3 >}.
OSC3 では, プログラム内の通信同期文の長さ 3 の順序列がテストにおける測定事象である. OSC3 テスト基準を満足するな
らば, プログラム内における 3 つのプロセス間の通信や同期を少なくとも 1 回実行する.
k = ∞ の場合
OSC∞ = {< s1 , s2, · · · , sk , · · · >}.
ループが存在するプログラムでは, 無限長の実行系列が存在する可能性がある. その場合, 無限長の順序列を考えることが可能である. 無限長の順序列をテストにおける測定事象にするのが OSC∞ テスト基準である. OSC∞ を満足するならば, プログラム実行時に起り得る通信同期文の実行形列は少13

なくとも 1 回実行される. しかしながら, 無限長の順序列が測定事象であるため, OSC∞ テスト基準を満足する事は現実的には不可能である.

4

例題
順序列テスト基準を具体的なプログラムに適用する. 例題

として「哲学者 2 人の食事問題」を用いる. 制御フローグラ
フを図 4 に示す. 同期の機構としてセマフォを用いた.
この例では, プログラムにおけるセマフォの P 命令と V 命
令とが通信同期文集合 Sync の要素となる. まず, P,V 命令に
識別用の番号 1〜8 を付ける (図 4 参照). 哲学者 2 人の食事問
題における順序列テスト基準の測定事象は, 図 4 に示した通信同期文の番号を用いると以下のようになる.

1. OSC1= {< 1 >, < 2 >, < 3 >, < 4 >, < 5 >, < 6 >, < 7 >, < 8 >}
測定事象の数は |Sync| = 8 個である.

2. OSC2= { < 1, 1 >, < 1, 2 >, < 1, 3 >, · · · < 1, 7 >, < 1, 8 >,< 2, 1 >, < 2, 2 >,···< 2, 8 >,
..
..
...
.
.
< 8, 1 >, < 8, 2 >, < 8, 3 >, · · ·
測定事象の数は |Sync|2 = 82 = 64 個である.

14< 8, 8 > }3. OSC3= { < 1, 1, 1 >, < 1, 1, 2 >, · · · < 1, 8, 7 >, < 1, 8, 8 >,< 2, 1, 1 >, < 2, 1, 2 >, . . .
< 2, 8, 8 >,
..
..
...
.
.
< 8, 1, 1 >, < 8, 1, 2 >, · · ·< 8, 8, 8 > }

測定事象の数は |Sync|3 = 83 = 512 個である.
順序列の長さを k とすると, 順序列テスト基準 OSCk における測定事象の数は |Sync|k 個になる. 測定事象の数が k のべき乗で増加するため, k が大きな順序列テスト基準は実用的ではない可能性がある. そのために, テストに許される時間に応じて k の値を選択する必要がある. また, 測定事象数の削減
ついて 5.3 節で議論する.
上記の k = 3 の場合の測定事象, < 8, 1, 2 > という列は, 哲
学者の食事問題ではデッドロックに陥いる列である. k の値を変更することによって順序列テスト基準 OSCk において発見できる誤りの種類が変化する. 誤りに対する順序列テスト
基準の信頼性については 5.4 節で述べる.

5

議論
前節まで並行処理プログラムの新たなテスト基準として, プ

ロセス間の同期通信文の順序列に着目した順序列テスト基準を定義した. この節では順序列テスト基準とその他のテスト基準との関係, 順序列テスト基準の測定可能性, 測定事象数,
信頼性について議論する.

15

5.1

テスト基準間の関係

順序列テスト基準 OSCk , k ≥ 1, と逐次処理プログラムのテ
スト基準 Ci, i ≥ 0, とについて, テスト基準の間の関係を検討する.
まずテスト基準間の関係として以下の「包含関係」を定義
する.
【定義】 3

包含関係

テスト基準 Cr1 を満足すれば, 必ずテスト基準 Cr2 も満足する場合, Cr1 が Cr2 を「包含する」といい, これを Cr1 ⊃ Cr2

2

で表す.

順序列テスト基準, 路解析に基づく逐次処理プログラムのテスト基準において, それぞれ以下の包含関係が成立することは自明である.

(1) Ci+1 ⊃ Ci , i ≥ 0(2) OSCk+1 ⊃ OSCk , k ≥ 1
また, C0 テスト基準は, プログラム内のすべての実行文を少くとも 1 回実行するというテスト基準である. プログラム
内のすべての文が少くとも 1 回実行されれば, プログラム内のすべての通信同期文が少くとも 1 回実行される. 故に以下の包含関係が成立する.

(3) C0 ⊃ OSC1
OSC1 はプログラム内のすべての通信同期文を少なくとも一回実行したという以上の意味を持たない。しかしながら、通信や同期を行なう通信同期文の組が 1 組しかない場合や、通信や同期の仕様が決定しているプログラムでは、OSC1 でテスト
16

充分性を評価することができる。しかしながら, OSCk , k ≥ 2,
テスト基準は並行に実行されるプロセス間での通信同期文の組み合わせを含んでいるので, Ci, i ≥ 1, との包含関係はない.
プログラム P 全体での命令の実行系列は, P を構成するプ
ロセス Pi における命令の実行順序を保存している. そのために, 実行系列の集合は, 各プロセスにおける順序を保存した命
令列をシャッフル [11] した列の系列である. この系列すべてをテストにおける測定事象とし, 被覆率を 100%にすることを要求するテスト基準を考える. これを全実行系列テスト基準と呼び CC∞ と表すことにする.
【定義】 4

全実行系列テスト基準 : CC∞

CC∞ = { すべての実現可能な実行系列 }.

2
全実行系列テスト基準 CC∞ と順序列テスト基準 OSCk , k ≥1, 逐次処理プログラムの路解析のテスト基準 Ci, i ≥ 0, の間に以下の包含関係が成立することは明らかである.
(4) CC∞ ⊃ OSC∞
(5) CC∞ ⊃ C∞
以上の包含関係をまとめたものを図 5 に示す. ただし, 矢印
は包含関係を表し, 矢の根本のテスト基準が矢の先のテスト基準を包含することを意味する.

5.2

測定可能性

テスト基準を用いてテスト充分性を評価するためには, 被テストプログラムの実行時に被覆率を測定できなければなら17

ない. 順序列テスト基準における被覆率測定の可能性について検討する [12, 13].
被覆率を用いたテスト充分性の評価は, 逐次処理, 並行処理に関わらず, 次の手順で行われる.

(1) 測定事象の抽出(2) 実行された測定事象の記録(3) 被覆率の算出
それぞれの段階について検討する.

(1) 測定事象の抽出
順序列テスト基準はプロセス間の通信同期文からなる順序
列を測定事象にしたテスト基準である. プログラムから通信
同期文を取り出し, 取り出した通信同期文の順序列を作成して定義 1 に示した測定事象の集合 M とする [13].

(2) 実行された測定事象の記録実行された測定事象の記録にはいくつかの方法がある. 例
えば実行時に実行状況の記録 (トレース) を保存し, 実行終了
後にトレースから測定事象を抽出する方法がある. しかしながら, この方法は, トレースの量が膨大になるために, テスト
充分性評価に用いるのには適していない. そこで, ソースコー
ドに挿入した探針 (Probe) によって実行した測定事象を記録する方法を用いる. 探針とは被テストプログラムに挿入される測定用のプログラム片である.
順序列テスト基準では, プロセス間の通信同期文の順序列
が測定事象である. そこで, 被覆率を測定する探針の機能と18

しては, 並行に処理されるはずの同期通信文を何らかの形で逐次的に実行させることが必要である. 逐次的に実行された
通信同期文を順序列の長さ-1 だけ保存すれば, 測定事象である順序列が実行されたことを知ることが可能になる.
探針としては, 監視用プログラム (モニタ) が考えられる. モ
ニタは本来デバッグのために使用されてきた [8, 14, 15]. プロ
グラムの実行列を記録し, その実行列に従いプログラムを再実行させれば, 並行処理プログラムを決定的に実行できるため, 誤りが再現できデバッグが容易になる.
モニタを被覆率測定の探針として利用する手順は以下の通りである.

(i) 被テストプログラムにモニタとなるプロセスを生成させるプログラム片を追加する.
(ii) 被テストプログラムの通信同期文に, モニタプロセスと通信をするための通信同期文を追加する.
(iii) 各プロセスでは通信同期文の実行前に, 新たに追加された通信同期文を通じてモニタに自分のプロセス番号及び次に実行される通信同期文の文番号を知らせ実行許可を求める.
(iv) モニタは実行許可要求を記録する.
(v) モニタは実行要求を出した通信同期文の実行許可を出す.
モニタは被覆率を増大させるために用いることも可能である. 実行させたい順序列をモニタに予め知らせ, その順序列が実行されるようにモニタが各プロセスの実行順序を調節す
れば良い.
19

モニタ挿入後のプログラムでは, 並行に処理されるはずの通信同期文を逐次的に処理する. しかしながら, 探針挿入後のプログラムの動作は元のプログラムの動作の 1 つである. な
ぜなら探針を挿入しても元のプログラムの実行系列における半順序関係を損なうものではないからである [16]. そのため探針挿入後のプログラムで発生する誤りは, 探針挿入前の被テストプログラムでも発生する.

(3) 被覆率の算出
最後に被覆率の算出を行う. 一般にプログラムを一度実行しただけでは被覆率が 100%になることはない. そのために,プログラムの実行を繰り返し, 実行された測定事象を累積して被覆率を計算する必要がある.
プログラムの実行終了後にモニタが記録している実行した順序列を実行済み測定事象集合 M に加える. 順序列テスト基
準の被覆率 C を定義 1 の計算式で計算する.

5.3

測定事象数

長さ k の順序列テスト基準では, mk 個 (m = |Sync|) の組合
せを測定事象とする. 測定事象の数は順序列の長さのべき乗で増加するので, 長い組合せを用いたテスト基準は実際的ではない可能性がある. そのために, 測定事象を減らす必要がある.
測定事象の削減方法として考えられるのは, 第 1 に, プログ
ラムの意味を考慮することにより測定事象を削除することである. 第 2 に, 仕様に反する組合せを削除することである. しかしながらどちらの方法も採用しない. それぞれについて理由を述べる.
20

第 1 に, プログラムの意味を考慮することにより測定事象を削除することについて考える. 3 章で述べた < 1, 1, 1 > のよ
うな同一の通信同期文が並ぶ測定事象は, プログラムの意味
から実現不可能と考えられる. しかし同一の通信同期文の列も実現可能な場合がある.
例えば, Ada のタスク型や UNIX 上における C プログラムで用いられるシステムコール fork 文などのように [17], 同じ
ソースコードに対し複数のプロセスが生成される場合がある.
このような場合 < 1, 1, 1 > といった同一の通信同期文の列がプログラムの実行系列に現れることがある.
次に生産者消費者問題を例に考える. バッファがすべて使用済みで空領域が無い場合, バッファに空領域ができるまで生産者プロセスは何度も通信を試みる. この場合にも, 同一の通信同期文の列が実行系列に現れる.
第 2 に, 仕様に反する系列を測定事象から削除することについて考える. 被テストプログラムを計算機上で実際に実行するテストでは, 仕様に反する事象あるいは仕様に記述されていない事象を発見することが目的である. 仕様に反するという理由で測定事象から削除するのは主客転倒であり, この方法は採用できない.
つまりソースコードからだけでは, 同一命令の組合せや仕様に反する組合せが実行系列に現れるか否かを判定できない.
プログラムの動作を詳細に解析し, 本当に実行できない測定
事象を削除する, などの測定事象の削減法を今後検討する必
要がある.

21

5.4

信頼性

テスト法が「信頼できる」とは, プログラムに誤りがあるな
らば, テスト法に従って作成したテストデータによって誤りを必ず発見できることをいう [5]. したがって, 信頼できるテスト法により作成したテスト集合 (テストデータ) に対してテストの実施結果がすべて正当であるならば, プログラムは正当である. 任意のプログラムに対して信頼できるテスト法は「徹底テスト (exhaustive testing)」のみである. しかしながら徹底テストは一般に実現不可能であるため, 現実に用いられているテスト法は部分的にしか信頼できない. そこで, 特定の誤りを含んだプログラムに対してテスト法が信頼できるか否かを検討する必要がある.

5.1 節の定義に従って, テスト基準 Cr1 と Cr2 に包含関係
Cr1 ⊃ Cr2 があると仮定する. ここでテスト基準 Cr2 がある
種類の誤りに対し信頼できるならば, Cr2 を包含するテスト
基準 Cr1 も同じ種類の誤りに対し信頼できる.
並行処理プログラムの誤りは, 誤りの発生原因により次の 3
種類に分類することが考えられる [10, 18].
(i) プロセス内誤り · · · 逐次処理プログラムにおいて考えられる誤り.
(ii) 通信誤り · · · 並行に実行されるプロセス間でのデータの受け渡し時に発生する誤り.
(iii) 同期誤り · · · 次の 3 種類がある.
(a) 安全性の破壊 · · · 相互排除の失敗によるデータの一
貫性の喪失.

22

(b) 生存性の破壊 · · · プログラム中のプロセスが実行不可能になる. デッドロックとも呼ばれる.
(c) 公平性の破壊 · · · ある特定のプロセスだけが実行を不当に待たされる. ライブロックとも呼ばれる.
順序列テスト基準は, プロセス間の通信や同期に着目したテスト基準である. すなわち, 各プロセスの中で発生するプ
ロセス内誤りに対しては何ら考慮されていない. 以下に通信誤りと生存性の破壊 (デッドロック) との, 2 種類の誤りに対する順序列テスト基準の信頼性を考察する.
5.4.1

通信誤りに対する信頼性評価

通信誤りに対する順序列テスト基準の信頼性を検討する. 通信誤りは次の 2 つに分類できる [3].
【定義】 5

完全通信誤りプロセス間における通信の際, 常に誤ったデータを受け渡す.

2【定義】 6

部分通信誤りプロセス間における通信の際, 誤ったデータを受け渡す場合

2がある.
プロセス間の通信を対[s1(σ), s2(σ)]
で表現する. ここで, σ は通信の際の識別子である. この通信が起る場合の通信同期文の実行順序は < s1 , s2 >, < s2 , s1 > のいずれかである. 2 つの列は長さ 2 の順序列テスト基準 OSC2の測定事象に含まれている.
23

テスト実施後に OSC2 テスト基準を満足するならば, プログ
ラム内の任意の 2 つのプロセス間のすべての通信が少くとも

1 回は実行されたことになる. ゆえに, OSC2 テスト基準を満足するテスト法は, 完全通信誤りに対し信頼できるテスト法
である.
しかしながら, ある通信が部分通信誤りを含む場合, テスト
実施においてその通信が 1 度しか実行されず, その際誤りが顕在しない場合がある. そのため OSC2 テスト基準は部分通信誤りに対しては信頼できない.
5.4.2

同期誤りに対する信頼性評価

同期誤りの中で, 生存性の破壊であるデッドロックに対する順序列テスト基準の信頼性を検討する. デッドロックを定義
する.
【定義】 7 デッドロック :プログラム内の少なくとも一つのプロセスが実行可能になることができない場合, これをデッドロックと呼ぶ.

2

デッドロックを, その発生要因に基づき次のようにクラス分けする.
【定義】 8

クラス 0プログラム内のある 1 つの通信同期文を実行すれば, 必ず発

2

生するデッドロック.
【定義】 9クラス 1

変数の値には関わらずに, プロセス間の通信同期文が, ある特定の順序列に従った場合にのみ発生するデッドロック.
242

【定義】 10

クラス 2

通信同期文の順序列に関係なく, プログラム内の変数がある
特定の値を持つ場合に発生するデッドロック.
【定義】 112

クラス 3

プログラム内の変数がある特定の値を持ち, かつ通信同期文がある特定の順序列を持つ場合にのみ発生するデッドロック.

2

それぞれのクラスのデッドロックに対する順序列テスト基
準の信頼性は以下の通りである.

[定理] 1
OSC1 テスト基準はクラス 0 のデッドロックに対し信頼できる.
[証明]
クラス 0 のデッドロックでは, プログラム内のある 1 つの通信同期文を少なくとも 1 回実行すれば, 必ずデッドロックが発生する. OSC1 は, プログラム内のすべての通信同期文の少なくとも 1 回の実行を要求する. もし OSC1 テスト基準を満足するならば, すべての通信同期文は少なくとも 1 回は実行されている.
故に, OSC1 テスト基準はクラス 0 のデッドロックに対し信頼できる.

2[定理] 2
並行に実行されるプロセス数が n の場合, n + 1 長の順序列テスト基準を満足するテスト法は, 通信同期文により発生する
クラス 0 および 1 のデッドロックに対し信頼できる.
25

[証明]
クラス 1 のデッドロックは変数の値には関係せず, 通信同期
文の実行順序により発生する. 変数の値に依存しないために,
プロセス間の相互依存関係が循環する場合にのみデッドロッ
クに陥る. プログラム中の並行に動作するプロセス数が n 個であるとする. プロセス間の相互依存関係の長さは高々n + 1
である. つまりプログラムにクラス 1 のデッドロックが存在する場合, 長さ n + 1 の順序列をすべて実行すれば, 必ずデッドロックが発生する.
故に, 並行に実行されるプロセス数が n の場合, n + 1 長の順序列テスト基準を満足するテスト法は, 通信同期文により発生するクラス 0 および 1 のデッドロックに対し信頼できる.

2[定理] 3
順序列テスト基準は, クラス 2 およびクラス 3 のデッドロック
に対し信頼できない.
[証明]
反例を示す.
例えば, 図 6 に示すような, 変数に起因するデッドロックの場合, 順序列テスト基準ではいかに列の長さを長くしても, このデッドロックを必ず発見するとはいえない.

2
クラス 2 のデッドロックは, 通信同期文の実行順序には関わらず, 変数の値に起因するデッドロックである. 順序列テスト
26

基準は通信同期文にのみ着目したテスト基準であるため, プ
ロセス内での変数の値の変化を何ら考慮していない. 故に順
序列テスト基準はクラス 2 のデッドロックに対して信頼できない.
クラス 3 のデッドロックを発生する可能性のあるプログラ
ムとしては, 例えば複数のプロセスが資源を獲得しつつ処理を行い, しかもその資源の必要量が動的に変化するプログラ
ムが考えられる. クラス 3 のデッドロックもクラス 2 と同様に変数の値に起因するデッドロックであるため, 順序列テス
ト基準はクラス 3 のデッドロックに対して信頼できない.

6

おわりに並行処理プログラムに対するテスト充分性評価法の 1 つとして, プロセス間の通信や同期に着目した順序列テスト基準を提案した. その順序列テスト基準の測定可能性, 包含関係,
信頼性について議論した. 包含関係の議論で, 従来のテスト
基準と順序列テスト基準との関係を示した. 信頼性の議論の中で, 順序列テスト基準が信頼できるプログラムの限界を示した. 順序列テスト基準は, 正しいプログラム, 完全通信誤りを含むプログラム, クラス 0 およびクラス 1 のデッドロックを含むプログラムに対して信頼できる.
今後の課題として, 実際の開発現場における順序列テスト基
準の有効性の評価がある. テストは実際の開発現場で使用されることを目的とする手法であるため, 開発現場で有効でなければならない. そこで定性的な信頼性の検討だけでなく, 実
際のプログラム開発に適用して有効性を実証する必要がある.
本稿の考察に基づいて, 順序列テスト基準の被覆率を用いた
27

テスト充分性評価ツールの試作を現在進めている [13]. ツー
ルは基本的な長さ 2 の順序列テスト基準の被覆率を測定する.
ツールの対象は UNIX SYSTEM V および UNIX 4.3BSD 上で実行可能な C 並行処理プログラムである. C 言語や UNIXは広く用いられているため, ツールは実際のプログラム開発
における実用的な利用が期待できる.
既に, 小さいものではあるが, 実際に使用されている並行処
理プログラムにツールの適用を始めている. テスト基準およびツールの評価結果については別の機会に報告したい. 今後は多くの並行処理プログラムにツールを適用し, 順序列テス
ト基準の有効性を実証する予定である.

28

謝辞
並行処理プログラムのテスト/デバッグ/検証法について議論していただいた奈良先端科学技術大学院大学の荒木啓二郎
教授および九州大学工学部情報工学科の程京徳助教授に感謝いたします.

29

参考文献[1] 玉井哲雄, 三嶋良武, 松田茂広 : ソフトウェアのテスト技法, 共立出版 (1988).
[2] Clarke, L. A., Podgurski, A., Richardson, D. J. and Zeil,
S. J. : A Formal Evaluation of Data Flow Path Selection
Criteria , IEEE Trans. Softw. Eng., Vol.15, No.11, pp.13181332 (1989).
[3] 古川善吾, 牛島和夫 : ランデブー通路を用いた Ada 並行
処理プログラムのテスト十分性評価, 電子情報通信学会論文誌, Vol.J75-D-I, No.5, pp.288-297 (1992).
[4] 古川善吾, 有村耕治, 牛島和夫 : 並行処理プログラムにおける共有変数のデータフローテスト基準, 情報処理学会論文誌, Vol.33, No.11, pp.1394-1401 (1992).
[5] Howden, W. E. : Reliability of the Path Analysis Testing
Strategy, IEEE Trans. Softw. Eng., Vol.SE-3, No.4, pp.226278 (1976).
[6] Taylor, R. N., Levine, D. L. and Kelly, C. D. : Structural
Testing of Concurrent Programs, IEEE Trans. Softw. Eng.,
Vol 18, No.3, pp.206-215 (1992).
[7] Weyuker, E. J. : The Complexity of Data Flow Criteria
for Test Data Selection, Information Processing Letters,
Vol.19, pp.103-109 (1984).
[8] Tai, K. C., Carver, R. H. and Obaid, E. E. : Debugging Concurrent Ada Programs by Deterministic Execu30

tion, IEEE Trans. Softw. Eng., Vol.17, No.1, pp.45-63(1992).
[9] Hwang G.H., Tai, K. C., and Huang, T. : Reachability
Testing : An Approach to Testing Concurrent Software,
Proc. of APSEC94, pp.246-255, (1994).
[10] Ben-Ari, M. : Principles of Concurrent Programming,
Prentice Hall International, Inc. (1982).
翻訳 渡辺 榮一 : 並行プログラミングの原理, 啓学出版
(1986).
[11] 荒木俊郎, 香西省治, 都倉信樹 : シャッフル文法, 電子情報通信学会論文誌, Vol.J66-D No.8, pp.170-177 (1983).
[12] Itoh, E., Kawaguti, K., Furukawa, Z., and Ushijima, K.
: Ordered Sequence Testing Criteria for Concurrnet Programs and The Support Tool, Proc. of APSEC94, pp.236245, (1994).
[13] 川口豊, 伊東栄典, 古川善吾, 牛島和夫 : 順序列テスト
基準を用いたテスト充分性評価システムの試作, 情処研報,
96-SE-14, pp.107-114 (1994).
[14] 程京徳, 荒木啓二郎, 牛島和夫 : Ada 並列プログラムの事象駆動型実行モニタ EDEN の開発と応用, 情報処理学会
論文誌, Vol.30, No.1, pp.12-24 (1989).
[15] German, S. M., Helmbold, D. P. and Luckman, D. C. :Monitoring for deadlocks in Ada tasking, Proc. AdaTEC
Conf. on Ada(Arlington, VA), pp.10-25 (1982).

31

[16] Cheng, J. and Ushijima, K. : Partial Order Transparency
as a Tool to Reduce Interference in Monitoring Concurrent Systems , “Distributed Environments”, Y.Ohno(Ed.),
Springer-Verlag, pp.156-171 (1991).
[17] Rockkind, M. j. : Advanced UNIX Programming, Prentice Hall International, Inc. (1985).
翻訳 福崎 俊博 : UNIX システムコール・プログラミン
グ, アスキー出版局 (1991).
[18] 古川善吾, 牛島和夫 : 並行処理プログラムのテスト法に関する一考察, 日本ソフトウェア科学会第 6 回大会論文集,
pp.185-188 (1989).

32

図 1: 非決定的実行の例.

Fig.1: An example of nondeterministic program.
図 2: 同期・通信命令のみに注目した実行系列の例.

Fig.2 : An example of ordered sequences constructed byinterprocess communication and synchronization.
図 3: プロセスの動的生成.
Fig.3 Dynamic Process Generation.
図 4: 哲学者 2 人の食事問題の制御フローグラフ.

Fig.4 A control ﬂow graph of two dining philosophers.
図 5: テスト基準の間の包含関係.

Fig.5: Subsumption relationship of testing criteria.
図 6: 順序列テスト基準で発見不可能なデッドロックの例.
Fig.6 A program which can not detect deadlock with OSC.

33

P1

P2

1: begin

4: begin

2: m

5: m

1;

3: end;2;

6: end;

図 1: 非決定的実行の例.

P1

P2

P3

2

1

P1

4

3

P2

2

1

P3

4

3

実行系列

1 2
2 4
3 3
4 1
2 1
1 4
. 2
. 3
.

図 2: 同期・通信命令のみに注目した実行系列の例.

34

4
1
2 ...
3
2
4
1
2
.

Proc1

Proc2

1

1’

2

2’

3

3’

4

4’

図 3: プロセスの動的生成.

Philosopher1

Pilosopher2

1

P(fork1)

P(fork2)

5

2

P(fork2)

P(fork1)

6

EAT

EAT

3

V(fork2)

V(fork1)

7

4

V(fork1)

V(fork2)

8

THINK

THINK

図 4: 哲学者の食事問題の制御フローグラフ.

35

CC∞

PPPP

P





)


PPPP
PPq
C∞

OSC∞

?

?

OSC3

C2

?

?

C1

OSC2

?

OSC1

?



C0

図 5: テスト基準の間の包含関係.

1: begin
2: disk を x kbyte 確保
3: プロセス内の処理
4: end5: begin
6: disk を y kbyte 確保
7: プロセス内の処理
8: end

図 6: 順序列テスト基準で発見できないデッドロックを含むプログラムの
例. 変数 disk の上限値が決っていて, かつ文 2 と文 6 の必要量 (x+y) がその上限を越えている場合, デッドロックになる可能性がある.

36