JPH06175884A

JPH06175884A - プログラムエラー原因究明装置

Info

Publication number: JPH06175884A
Application number: JP4325684A
Authority: JP
Inventors: Takao Shimomura; 隆夫下村
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1992-12-04
Filing date: 1992-12-04
Publication date: 1994-06-24

Abstract

(57)【要約】【目的】バグの存在し得る場所をさらに小さく特定で
き、エラーの原因すなわちバグを容易に究明できるプロ
グラムエラー原因究明装置を提供する。【構成】プログラムの実行時に各実行時点ごとに制御
依存関係およびデータ依存関係からなる実行依存関係情
報を抽出する実行履歴獲得部２２と、実行依存関係情報
参照してエラー原因の推定に必要となる制御依存関係と
データ依存関係を取り出す制御／データフロー解析部２
３を設ける。さらに、制御依存関係および前記データ依
存関係を参照して、各実行時点のうち正しい値を示して
いる変数の値の生成に関与する実行時点を除外し誤った
値を示している各変数の値の生成に共通に関与している
実行時点を抽出してエラーの原因となる可能性のある実
行箇所として推定するエラー原因推定部２４を設ける。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般の手続き型言語で
記述されたプログラムのデバッグ時にエラー原因の分析
作業を容易に行なえるようにするため使用されるプログ
ラムエラー原因究明装置に関する。

【０００２】

【従来の技術】一般に、プログラムデバッグ作業では、
デバッグ対象のプログラムの実行中にエラーを見つける
と、そのエラーの原因に対する仮説を立て、仮説を検証
することを繰り返しながらエラー原因を次々とたどり、
最後に最終的な原因であるバグを究明する。プログラマ
によるこのようなデバッグ作業の遂行を支援するため
に、「エラーに関係している場所である」としてプログ
ラマによって推定された（プログラム中の）場所が実際
に実行されたとき（エラーに関係する実行時点）を自動
的に見つけ出し、その実行時点でのプログラム状態を再
現するシステムが、提案されている。このような支援シ
ステムとしては、例えばＰＥＬＡＳ(BogdanKorel, "PEL
AS - Program Error-Locating Assistant System", IEE
E Transactions on Software Engineering, Vol. 14, N
o. 9, Sept. 1988, pp. 1253-1260)、Ｓｐｙｄｅｒ(Hir
alal Agrawal, Richard A. DeMillo and Eugene H. Spa
fford, "An Execution-Backtracking Approach to Debu
gging", IEEE Software, May1991, pp.21-26)、ＣＨＡ
ＳＥ(Takao Shimomura and Sadahiro Isoda, "CHASE:A
Bug-Locating Assistant System", COMPSAC'91, Sept.
1991, pp. 412-417)などが挙げられる。

【０００３】これらの支援システムでは、プログラム中
のバグによってある変数の値が誤っている場合には、そ
のエラーの発生している実行時点を基準にして、プログ
ラム実行順序とは逆向きに制御フローやデータフローを
順にたどることができるようになっている。制御フロー
およびデータフローは、各々、以下に示す制御依存関
係、データ依存関係をたどることによって得られる実行
時点の集合である。

【０００４】(1) 制御依存関係：実行時点ｔ₁およびｔ₂
があって、実行時点ｔ₂で分岐文あるいはループ文が実
行されており、実行時点ｔ₁において実行された文の実
行の有無がその分岐文あるいはループ文の制御移行結果
に直接依存していたとき、「実行時点ｔ₁が実行時点ｔ₂
に制御依存関係がある」という。

【０００５】(2) データ依存関係：実行時点ｔ₁におい
て実行された文で使用した変数を最後に定義したのが実
行時点ｔ₂であるとき、「実行時点ｔ₁が実行時点ｔ₂に
データ依存関係にある」という。

【０００６】図１は、制御依存関係とデータ依存関係と
を説明するためのサンプルプログラムを示している。こ
のプログラムは、アルゴル系言語によるものであって、
１つのWhileループと２つのif文（分岐文）を含んでい
る。このプログラムの入力文inputにｎ＝２,ａ＝(２,
４)を与えて実行した場合の、出力文outputの変数sumに
関する制御フローおよびデータフローの一部が図２に示
されている。図２において、矢印で示されたＣ,Ｄは、
それぞれ制御依存関係、データ依存関係があることを示
している。なお、矢印の先端側が上述の説明における実
行時点ｔ₁であり、根元側が実行時点ｔ₂である。ま
た、"◇"は分岐文やループ文など条件判断を伴う文を表
わし、"○"は代入文などを示している。

【０００７】例えば、図１のプログラム中の「while i<
=n do begin」（６行目）は、図２中の「i<=n」に対応
する。図２において最初に出現する（上から６行目）
「i<=n」（これは、whileループの第１回目の実行に対
応する）に注目すると、ここにある変数ｉおよびｎは、
それぞれ代入文「i:=2」（上から５行目）と入力文inpu
tによって最後に定義されているので、これらの間にデ
ータ依存関係Ｄが存在する。また、図２において上から
１０行目の「sum:=sum+a[i]」は上述のwhileループの内
部にあるので、この文が実行されるかどうかは図２の上
から６行目の「i<=n」（ループ文）に制御移行結果に直
接依存している。したがって、これらの間には制御依存
関係Ｃが存在する。

【０００８】次に、従来の支援システムの代表的な構成
について、図３を用いて説明する。従来の支援システム
は、デバッグ対象のプログラムを保持するプログラムフ
ァイル５１と、プログラム状態を表示するための表示画
面５２と、これらプログラムファイル５１および表示画
面５２が接続された実行部５０と、実行部５０に接続さ
れた実行依存関係情報ファイル５３とによって構成され
ている。そして実行部５０の内部には、プログラム実行
制御部６１と実行履歴獲得部６２と制御／データフロー
追跡部６３とが設けられている。プログラム制御実行部
６１は、プログラムファイル５１に保持されたプログラ
ムの実行を制御し、このプログラムの実行状態の表示画
面５２への表示を行なうためのものである。実行履歴獲
得部６２は、プログラムの各実行時点ごとに、当該実行
時点に関する制御依存関係とデータ依存関係とを抽出
し、これらを実行依存関係情報として実行依存関係情報
ファイル５３に格納するためのものである。そして制御
／データフロー追跡部６３は、実行依存関係情報ファイ
ル５３を参照し、制御依存関係とデータ依存関係から制
御フローとデータフローを追跡し、プログラム実行制御
部６１を介してこの追跡結果を表示画面５２に表示する
ためのものである。

【０００９】この支援システムを用いてデバッグを行な
うには、プログラムを実行して変数の値が異常であるな
どのエラーを発見したときに、制御フローとデータフロ
ーを表示させてこれを遡る方向にたぐりエラーの最終的
な原因となるバグを見出せばよい。

【００１０】

【発明が解決しようとする課題】上述の従来の支援シス
テムでは、１つ１つの実行時点ごとに制御フローやデー
タフローを順にたどっていくため、プログラム規模が大
きくなった場合に、エラーの最終的な原因であるバグに
なかなか行き着くことができず、バグを究明するのが容
易でないという問題点がある。

【００１１】本発明の目的は、バグの存在し得る場所を
さらに小さく特定でき、エラーの原因すなわちバグを容
易に究明できるプログラムエラー原因究明装置を提供す
ることにある。

【００１２】

【課題を解決するための手段】本発明のプログラムエラ
ー原因究明装置は、手続き型言語で記述されたプログラ
ムのデバッグを行なう際に使用され、前記プログラムの
エラー原因の究明を支援するプログラムエラー原因究明
装置において、前記プログラムの実行を制御し前記プロ
グラムの実行状態および推定されたエラー箇所を外部に
出力するプログラム実行制御手段と、前記プログラムの
実行時に、前記プログラムの各実行時点ごとに制御依存
関係およびデータ依存関係からなる実行依存関係情報を
抽出して記憶する実行履歴獲得手段と、前記実行履歴獲
得手段を参照してエラー原因の推定に必要となる前記制
御依存関係と前記データ依存関係を取り出す制御／デー
タフロー解析手段と、前記プログラムがエラーが発生し
ている状態にあり、かつ前記状態において正しい値を示
している変数と誤った値を示している複数の変数がある
とき、前記制御依存関係および前記データ依存関係を参
照して、前記各実行時点のうち前記正しい値を示してい
る変数の値の生成に関与する実行時点を除外し前記誤っ
た値を示している各変数の値の生成に共通に関与してい
る実行時点を抽出して前記エラーの原因となる可能性の
ある実行箇所として推定するエラー原因推定手段とを有
する。

【００１３】

【作用】本発明のプログラムエラー原因究明装置は、あ
る実行時点でエラーが発生している場合、プログラム中
の変数のうちその実行時点で正しい値を示す変数につい
てこの変数の値の定義に関係する部分にはバグのある可
能性が少なく、その実行時点で誤った値を示す複数の変
数についてこれら各変数の値の定義に共通に関与してい
る部分にはバグのある可能性が大きいということに基づ
いて、エラーの原因を究明する。したがって、バグの存
在する可能性のある場所を狭く限定でき、より迅速なエ
ラー原因の究明が可能となる。

【００１４】以下、図４を用いて本発明の作用をさらに
詳しく説明する。

【００１５】図４(A),(B)は、ある同一のプログラムを
実行した場合のデータフロー図である。ここでは３つの
変数Ｘ,Ｙ,Ｚが存在する場合を示している。実際のデバ
ッグ作業では、ある実行時点におけるプログラム状態を
調べたとき、プログラム中の変数のうちいくつかのもの
は誤った値を示しているが、その他の変数は正しい値を
示しているというのが普通である。ここでは変数Ｘ,Ｙ
が誤っている値を示し、変数Ｚが正しい値を示している
ものとする。

【００１６】図４(A)から明らかなように、変数Ｘの値
が誤っていることに関し、データフロー図において変数
Ｘの上流側にある文すなわちサブデータフローＰ１内の
文には、いずれもバグが存在する可能性がある。ところ
で、変数Ｚは正しい値を示しているので、変数Ｘと変数
Ｚに共通の上流部分すなわちサブデータフローＤ１（図
４(B)参照）は、変数Ｘの誤っている値に影響を与えた
可能性は低いと考えられる。したがって、サブデータフ
ローＰ１からサブデータフローＤ１を除外した部分すな
わちサブデータフローＰ２内にのみが、誤った値に影響
を与えていると結論付けることができる。誤った値に影
響を与えている可能性のあるデータフローをさらに小さ
い範囲に限定できたわけである。

【００１７】ところで、変数Ｙも誤った値を示してい
る。バグの発生確率を考えれば、独立な２つのバグによ
ってそれぞれ変数Ｘと変数Ｙが誤った値を示したとは考
え難く、変数Ｘ,Ｙが共通のバグによって誤った値を示
していると考えられる。そこで（変数Ｚが正しい値を示
していることを考慮しなければ）、バグの存在箇所は、
図４(B)のサブデータフローＤ２の内部に限られること
になる。ここで変数Ｚが正しい値を示していることを考
慮すれば、上述のようにサブデータフローＤ１は除外さ
れるので、結局、バグの存在する可能性のあるのはサブ
データフローＰ３（図４(A)）内ということになる。つ
まり、調べるべきデータフローが、サブデータフローＰ
３内に縮退されたことになる。

【００１８】本発明では、各実行時点のうち正しい値を
示している変数の値の生成に関与する実行時点を除外し
誤った値を示している各変数の値の生成に共通に関与し
ている実行時点を抽出してエラーの原因となる可能性の
ある実行箇所として推定するので、エラーを含む可能性
のある部分をより小さい範囲に限定することができ、エ
ラー原因の分析を効率化できる。

【００１９】

【実施例】次に本発明の実施例について図面を参照して
説明する。図５は本発明の一実施例のプログラムエラー
原因究明装置の構成を示すブロック図である。

【００２０】このプログラムエラー原因究明装置は、デ
バッグ作業の支援を行なうものであって、デバッグ対象
のプログラムを保持するプログラムファイル１１と、プ
ログラム状態や推定されたエラー箇所を表示するための
表示画面１２と、これらプログラムファイル１１および
表示画面１２が接続された実行部１０と、実行部１０に
接続された実行依存関係情報ファイル１３とによって構
成されている。そして実行部１０の内部には、プログラ
ム実行制御部２１と実行履歴獲得部２２と制御／データ
フロー解析部２３とエラー原因推定部２４が設けられて
いる。

【００２１】このプログラムエラー原因究明装置におけ
るデバッグ対象のプログラミング言語としては、Ａｄ
ａ、Ｐａｓｃａｌ、Ｃなどの一般の手続き型言語であ
る。以下においては、説明を簡単にするため、プログラ
ム内の文（ステートメント）は、代入文、if文などの分
岐文、while文などのループ文、関数呼び出し文および
入出力文からなるものとする。

【００２２】プログラム制御実行部２１は、プログラム
ファイル１１に保持されたプログラムの実行を制御し、
このプログラムの実行状態の表示画面１２への表示を行
なうためのものである。そしてプログラム制御実行部２
１は、プログラム実行時に実行履歴獲得部２２を呼び出
し、実行履歴獲得部２２によって後述するように制御依
存関係およびデータ依存関係からなる実行依存関係情報
を実行依存関係情報ファイル１３に記録させる。また、
プログラマーがエラーの発生を発見した場合すなわち値
の誤っている変数を発見した場合には、エラー原因推定
部２４を呼び出し実行依存関係情報から得られる制御依
存関係およびデータ依存関係を基にエラー原因の推定を
行なわせ、エラーを含む可能性が高いと推定された箇所
のプログラム状態を表示画面１２に表示させるようにな
っている。

【００２３】実行履歴獲得部２２は、プログラム実行時
にプログラム制御実行部２１から呼び出され、実行時点
ごとに実行依存関係情報を獲得して、実行依存関係情報
ファイル１３に格納する。ここで、実行依存関係情報と
して記録される情報について説明する。

【００２４】(1) 集合ＣＣ：現実行時点ｃにおける制御
フロー、すなわち、現在の実行時点ｃの実行を決定した
分岐実行時点（分岐文、ループ文、関数呼び出し文）の
集合である。後述するように、実行時点には連続番号が
ふられるので、この付与された番号からなる集合として
表わされる。この集合は、各分岐実行時点を要素とする
スタック構造を構成することにより、容易に求めること
ができる。ここでは集合とスタックとを同一視できるの
で、スタックＣＣに要素（実行時点）ｃをプッシュダウ
ンする操作を「ｐｕｓｈＣＣ(ｃ)」、スタックＣＣから
要素ｃを一つポップアップする操作を「ｐｏｐＣＣ」、
スタックＣＣの先頭要素の値を返す関数を「ｔｏｐＣ
Ｃ」で表わすことにする。

【００２５】(2) データ依存関係に対応する関数ＣＤｅ
ｆ(ｘ)：プログラム中の各変数ｘに対して、変数ｘを定
義した最新の実行時点ｐを返す関数である。変数ｘを定
義する実行時点があるごとに、ＣＤｅｆ(ｘ)の値を更新
すればよい。

【００２６】次に、プログラム中の各文を実行したとき
に実行履歴獲得部２２の行なう処理について説明する。
まず、現在実行しようとしている実行時点をｃとすると
き、実行開始時点（プログラムの実行に関し一番最初の
実行時点）から１つの文を実行するごとに順に１,２,
３,…と実行時点を表わす番号をふる。したがって、ｃ
を自然数として扱えば、このｃは対応する実行時点の実
行順を表わしていることになる。そして、現実行時点ｃ
における文の種類に応じ、以下のような処理を行なう。

【００２７】(1) 代入文、入力文を実行する場合：代入
文、入力文で定義する変数をｗとすると、ＣＤｅｆ(ｗ)：＝ｃ；Ｃ(ｃ)：＝ｔｏｐＣＣ；を実行する。ここでＣ(ｃ)は、実行時点ｃに対して制御
依存関係がある実行時点を表わしている。

【００２８】(2) 分岐文、ループ文、関数呼び出し文を
実行する場合：Ｃ(ｃ)：＝ｔｏｐＣＣ；ｐｕｓｈＣＣ(ｃ)；を実行する。すなわち、スタックＣＣに実行時点ｃをプ
ッシュダウンする。

【００２９】(3) 分岐文、ループ文、関数呼び出し文を
終了する場合：ｐｏｐＣＣ；を実行する。すなわちスタックＣＣから実行時点を一つ
ポップアップする。ただしループ文を終了する場合に
は、そのループ文本体部の繰り返し回数だけ、「ｐｏｐ
ＣＣ；」を実行するものとする。

【００３０】(4) 文の実行時に変数ｗの値を使用する場
合：Ｄ(ｃ,ｗ)：＝ＣＤｅｆ(ｗ)；Ｕｓｅ(ｃ)：＝｛ｗ｜変数ｗを使用する｝；を実行する。ここでＤ(ｃ,ｗ)は、実行時点ｃでの変数
ｗのデータ依存関係を表わす関数であり、その値は当該
データ依存関係先となる実行時点である。また、Ｕｓｅ
(ｃ)は、実行時点ｃで使用している変数の集合である。

【００３１】以上の説明から明らかなように、実行依存
関係情報ファイル１３に格納されたスタックＣＣの内容
を先頭から一番奥までたぐることにより、その実行時点
ｃに関する制御フローが得られることになる。関数Ｄ
(ｃ,ｗ)に関し、その値を再帰的に変数ｃとして代入す
ることにより、プログラム中の変数ｗについてのデータ
フローが得られることになる。

【００３２】制御／データフロー解析部２３は、エラー
原因推定部２４から呼び出され、実行依存関係情報ファ
イル１３を参照しエラー原因の推定に必要となる制御依
存関係およびデータ依存関係を取り出すためのものであ
る。この制御／データフロー解析部２３は、エラー原因
推定部２４からの求めに応じ、以下の関数で表わされる
機能を実現する。

【００３３】Ｄｅｐｅｎｄ(ｊ,ｖ)：＝｛Ｄ(ｊ,ｖ),Ｃ(ｊ)｝この関数は、実行時点ｊにおいて、変数ｖに関して制御
依存関係あるいはデータ依存関係にある実行時点の集合
を返すものである。

【００３４】Ｄｅｐｅｎｄ(ｊ)：＝∪Ｄｅｐｅｎｄ
(ｊ,ｖ) ただしｖ∈Ｕｓｅ(ｊ) この関数は、実行時点ｊにおいて使用された変数の集合
Ｕｓｅ(ｊ)に関して、制御依存関係あるいはデータ依存
関係にある実行時点の集合を返すものである。

【００３５】Ｄｅｐｅｎｄ(Ｊ)：＝∪Ｄｅｐｅｎｄ
(ｊ) ただしｊ∈Ｊこの関数は、実行時点ｊの集合Ｊに関し、この集合内の
いずれかの実行時点について制御依存関係あるいはデー
タ依存関係にある実行時点の集合を返すものである。

【００３６】エラー原因推定部２４は、エラーが発生し
た状態にありかつ正しい値を示している変数と誤った値
を示している複数の変数があるとき、制御／データフロ
ー解析部２３によって取り出された制御依存関係および
データ依存関係を参照して、各実行時点のうち正しい値
を示している変数の値の生成に関与する実行時点を除外
し誤った値を示している各変数の値の生成に共通に関与
している実行時点を抽出して前記エラーの原因となる可
能性のある実行箇所として推定し、推定結果をプログラ
ム実行制御部２１に出力するものである。

【００３７】ここで、３つの変数Ｘ,Ｙ,Ｚに関し、実行
時点ｔにおいて変数Ｘ,Ｙが誤った値を示し、変数Ｚが
正しい値を示している場合のエラー原因推定部２４の動
作について、図６を用いて説明する。ここでは、バグを
含む可能性が高いと推定される実行時点の中で、最後に
実行された実行時点ｓを求める場合について説明する。
なお、図６は、一般のアルゴル(Algol)型言語の記法に
したがったプログラムリストの形式で動作手順を示して
いる。while文の終りはend loop文で、if文の終りはend
if文で、戻り値ｘをもってプログラム実行を終えるこ
とをreturn xで表わしている。また、φは集合が空集合
であることを示している。ｌａｓｔ(Ｐ)は、実行時点の
集合Ｐ内の最後に実行された実行時点を返す関数であ
り、Ｐ＝φの場合には、０を返す。ｇｅｔ＿ｌａｓｔ
(Ｐ)は、実行時点の集合Ｐから最後に実行された実行時
点を１つ取り出し（集合Ｐの要素の数が１つ減る）、そ
れを返す関数である。

【００３８】行番号１〜３において、変数Ｘ,Ｙ,Ｚごと
に制御依存関係あるいはデータ依存関係にある実行時点
の集合が、それぞれOldX,OldY,OldZ（いずれも集合を表
わす変数）に代入される。変数Ｚは正しい値なので、変
数Ｚに関し制御依存関係あるいはデータ依存関係にある
実行時点にはバグがないとし、エラー原因の推定対象か
ら除外する（行番号４）。そして、変数ＸおよびＹの両
方に制御依存関係あるいはデータ依存関係にある実行時
点の集合Comを求める（行番号７）。そして変数Ｚに関
して制御依存関係あるいはデータ依存関係のある実行時
点について、これら実行時点で使用された変数の集合に
関して制御依存関係あるいはデータ依存関係のある実行
時点というように、正しい値を示した変数Ｚに関係して
いるとする実行時点の集合（すなわちバグ探索から除外
される実行時点の集合）を大きくしながら、前記除外さ
れる集合に属するものを除いて集合Comの中から最後に
実行された実行時点ｓを求め（行番号９〜２７）、この
実行時点ｓを戻り値とし動作を終了する（行番号２
５）。このようにしても実行時点ｓが定まらない場合に
は、変数ＸやＹに制御依存関係あるいはデータ依存関係
にある実行時点の集合を拡張し（行番号３３〜４０）、
同様の動作を繰り返す。どうしても見つからなかった場
合には、０を戻り値として動作を終了する（行番号４
２）。

【００３９】以上のようにしてエラー原因推定部２４
は、バグを含む可能性が高いと推定される実行時点の中
から、最後に実行された実行時点ｓを見つけ出す。

【００４０】

【発明の効果】以上説明したように本発明は、制御依存
関係およびデータ依存関係を参照して、各実行時点のう
ち正しい値を示している変数の値の生成に関与する実行
時点を除外し誤った値を示している各変数の値の生成に
共通に関与している実行時点を抽出してエラーの原因と
なる可能性のある実行箇所として推定するエラー原因推
定手段を有するので、エラーの原因を含む可能性の高い
場所をより狭く限定でき、バグの究明作業が容易になっ
てデバッグ作業の効率が向上するという効果がある。

【図面の簡単な説明】

【図１】サンプルプログラムを説明する図である。

【図２】図１のプログラムにおける制御依存関係とデー
タ依存関係を説明する図である。

【図３】従来の支援システムの構成を示すブロック図で
ある。

【図４】(A),(B)は、それぞれ本発明のプログラムエラ
ー原因究明支援装置の動作原理を説明するデータフロー
図である。

【図５】本発明の一実施例のプログラムエラー原因究明
支援装置の構成を示すブロック図である。

【図６】エラー原因推定部の動作を説明する図である。

【符号の説明】

１０実行部１１プログラムファイル１２表示画面１３実行依存関係情報ファイル２１プログラム実行制御部２２実行履歴獲得部２３制御／データフロー解析部２４エラー原因推定部Ｄ１,Ｄ２,Ｐ１〜Ｐ３サブデータフローＸ,Ｙ,Ｚ変数

Claims

【特許請求の範囲】

【請求項１】手続き型言語で記述されたプログラムの
デバッグを行なう際に使用され、前記プログラムのエラ
ー原因の究明を支援するプログラムエラー原因究明装置
において、前記プログラムの実行を制御し前記プログラムの実行状
態および推定されたエラー箇所を外部に出力するプログ
ラム実行制御手段と、前記プログラムの実行時に、前記プログラムの各実行時
点ごとに制御依存関係およびデータ依存関係からなる実
行依存関係情報を抽出して記憶する実行履歴獲得手段
と、前記実行履歴獲得手段を参照してエラー原因の推定に必
要となる前記制御依存関係と前記データ依存関係を取り
出す制御／データフロー解析手段と、前記プログラムがエラーが発生している状態にあり、か
つ前記状態において正しい値を示している変数と誤った
値を示している複数の変数があるとき、前記制御依存関
係および前記データ依存関係を参照して、前記各実行時
点のうち前記正しい値を示している変数の値の生成に関
与する実行時点を除外し前記誤った値を示している各変
数の値の生成に共通に関与している実行時点を抽出して
前記エラーの原因となる可能性のある実行箇所として推
定するエラー原因推定手段とを有することを特徴とする
プログラムエラー原因究明装置。