JPH07134664A - プログラムバグ潜在域抽出方法 - Google Patents
プログラムバグ潜在域抽出方法Info
- Publication number
- JPH07134664A JPH07134664A JP5282510A JP28251093A JPH07134664A JP H07134664 A JPH07134664 A JP H07134664A JP 5282510 A JP5282510 A JP 5282510A JP 28251093 A JP28251093 A JP 28251093A JP H07134664 A JPH07134664 A JP H07134664A
- Authority
- JP
- Japan
- Prior art keywords
- program
- bug
- dependency
- variable
- statement
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Stored Programmes (AREA)
- Debugging And Monitoring (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】
【目的】 バグの潜在している文を抽出するプログラム
バグ潜在域抽出方法を提供する。 【構成】 実行された文の間のデータ依存関係を記録部
３ａに記録し、制御定義依存関係を記録部３ｂに記録
し、変数の値の設定漏れに影響を与える分岐文との依存
関係を記録部３ｃに記録し、また分岐命令において次に
依存関係を辿る対象とする使用変数の集合を分岐命令使
用変数最適化記録部５ａで最適化し、抽出された文の間
の依存関係を用いてプログラムバグ潜在域を抽出する。
バグ潜在域抽出方法を提供する。 【構成】 実行された文の間のデータ依存関係を記録部
３ａに記録し、制御定義依存関係を記録部３ｂに記録
し、変数の値の設定漏れに影響を与える分岐文との依存
関係を記録部３ｃに記録し、また分岐命令において次に
依存関係を辿る対象とする使用変数の集合を分岐命令使
用変数最適化記録部５ａで最適化し、抽出された文の間
の依存関係を用いてプログラムバグ潜在域を抽出する。
Description
【０００１】
【産業上の利用分野】本発明は、一般の手続き型言語で
記述されたプログラムのデバッグにおいて発見された変
数値エラーを基にバグの存在するプログラム内の文を限
定することによりプログラムのデバッグ作業を容易にす
るプログラムバグ潜在域抽出方法に関する。
記述されたプログラムのデバッグにおいて発見された変
数値エラーを基にバグの存在するプログラム内の文を限
定することによりプログラムのデバッグ作業を容易にす
るプログラムバグ潜在域抽出方法に関する。
【０００２】
【従来の技術】プログラムのバグは、文の記述が漏れて
いる場合（文記述漏れバグ）、余分な文の記述がある場
合（文記述過多バグ）、および文の記述に誤りがある場
合に分類できる。更に、文の記述に誤りがある場合は、
代入文において、左辺の変数の名前を誤った場合のよう
に、別の変数に値を設定するという誤りを引き起こす場
合（名前記述誤りバグ）と、代入文における右辺の式や
分岐文における分岐条件式の記述を誤った場合（文記述
誤りバグ）に分類できる。文記述誤りバグと文記述過多
バグを総称して、値誤りバグとよぶこととする。
いる場合（文記述漏れバグ）、余分な文の記述がある場
合（文記述過多バグ）、および文の記述に誤りがある場
合に分類できる。更に、文の記述に誤りがある場合は、
代入文において、左辺の変数の名前を誤った場合のよう
に、別の変数に値を設定するという誤りを引き起こす場
合（名前記述誤りバグ）と、代入文における右辺の式や
分岐文における分岐条件式の記述を誤った場合（文記述
誤りバグ）に分類できる。文記述誤りバグと文記述過多
バグを総称して、値誤りバグとよぶこととする。
【０００３】プログラム内にバグがあると、変数に誤っ
た値が設定されたり、制御の流れが変ったりする。変数
値エラー（ある実行時点において、ある変数の値が誤っ
ているエラー）に関係するプログラム内のバグの存在箇
所を限定する従来の技術としては、動的スライス技術が
ある。
た値が設定されたり、制御の流れが変ったりする。変数
値エラー（ある実行時点において、ある変数の値が誤っ
ているエラー）に関係するプログラム内のバグの存在箇
所を限定する従来の技術としては、動的スライス技術が
ある。
【０００４】動的スライスは、ある入力データを与えて
プログラムを実行した時、変数が使用されたある実行時
点において、その変数の値に実際に影響を与えた、実行
された文の集合である。実行された文を繰り返しも含め
て、順に並べたものを実行系列と呼ぶ。動的スライス
は、この実行系列の中で、データ依存関係と制御依存関
係の２つの依存関係を辿っていくことにより求められる
（文献：B.Korel and J.Laski,"Dynamic Program Slici
ng",Information Processing Letters,Vol.29,No.10,Oc
t.1988,pp.155-163 参照）。
プログラムを実行した時、変数が使用されたある実行時
点において、その変数の値に実際に影響を与えた、実行
された文の集合である。実行された文を繰り返しも含め
て、順に並べたものを実行系列と呼ぶ。動的スライス
は、この実行系列の中で、データ依存関係と制御依存関
係の２つの依存関係を辿っていくことにより求められる
（文献：B.Korel and J.Laski,"Dynamic Program Slici
ng",Information Processing Letters,Vol.29,No.10,Oc
t.1988,pp.155-163 参照）。
【０００５】動的スライス技術を利用したシステムは、
図６に示すように文の間の依存関係を記録するためのコ
ードをソースプログラムに埋め込むインストルメント部
３１と、コンパイル、リンクされた実行可能プログラム
の実行を制御するプログラム実行制御部３３と、文の間
のデータ依存関係を記録するデータ依存関係記録部３３
ａと、制御依存関係を記録する制御依存関係記録部３３
ｂと、発見された変数値エラーを基にして、それらの文
の間の依存関係を解析することにより、バグ存在箇所を
抽出する動的スライス獲得部３５とから構成されてい
る。
図６に示すように文の間の依存関係を記録するためのコ
ードをソースプログラムに埋め込むインストルメント部
３１と、コンパイル、リンクされた実行可能プログラム
の実行を制御するプログラム実行制御部３３と、文の間
のデータ依存関係を記録するデータ依存関係記録部３３
ａと、制御依存関係を記録する制御依存関係記録部３３
ｂと、発見された変数値エラーを基にして、それらの文
の間の依存関係を解析することにより、バグ存在箇所を
抽出する動的スライス獲得部３５とから構成されてい
る。
【０００６】動的スライスを説明するためのプログラム
ｍｉｎ−ｍａｘを図７に示す。プログラムｍｉｎ−ｍａ
ｘでは、２つの値ｘ，ｙを入力して、それらの最大値ｍ
ａｘ、最小値ｍｉｎを出力する。入力ｘ＝３，ｙ＝２を
与えて実行した時の実行系列（実行された命令の列）を
図２に示す。変数ｍｉｎの値３が誤っている（正しく
は、２）。この場合、出力文における変数ｍｉｎに関す
る動的スライスは、文１と文２である。
ｍｉｎ−ｍａｘを図７に示す。プログラムｍｉｎ−ｍａ
ｘでは、２つの値ｘ，ｙを入力して、それらの最大値ｍ
ａｘ、最小値ｍｉｎを出力する。入力ｘ＝３，ｙ＝２を
与えて実行した時の実行系列（実行された命令の列）を
図２に示す。変数ｍｉｎの値３が誤っている（正しく
は、２）。この場合、出力文における変数ｍｉｎに関す
る動的スライスは、文１と文２である。
【０００７】
【発明が解決しようとする課題】動的スライスでは、文
の間のデータ依存関係および制御依存関係に基づいてバ
グ存在箇所を抽出するため、プログラムｍｉｎ−ｍａｘ
の例における文１、文２のように変数ｍｉｎの値に直接
影響を与えた文を抽出することができる。しかし、この
例が示すように、実際にバグを含む文４を抽出すること
はできなかった。このように、動的スライスでは、ある
分岐文（ここでは、文４）の分岐結果の誤りのために、
ある変数（ここでは、変数ｍｉｎ）に値が設定されず、
それが原因で変数値エラーを引き起こしているような場
合には、その分岐文、およびその分岐文が依存している
文の集合がまるごと動的スライスから漏れてしまうとい
う問題点がある。
の間のデータ依存関係および制御依存関係に基づいてバ
グ存在箇所を抽出するため、プログラムｍｉｎ−ｍａｘ
の例における文１、文２のように変数ｍｉｎの値に直接
影響を与えた文を抽出することができる。しかし、この
例が示すように、実際にバグを含む文４を抽出すること
はできなかった。このように、動的スライスでは、ある
分岐文（ここでは、文４）の分岐結果の誤りのために、
ある変数（ここでは、変数ｍｉｎ）に値が設定されず、
それが原因で変数値エラーを引き起こしているような場
合には、その分岐文、およびその分岐文が依存している
文の集合がまるごと動的スライスから漏れてしまうとい
う問題点がある。
【０００８】本発明は、上記に鑑みてなされたもので、
その目的とするところは、バグの潜在している文を抽出
するプログラムバグ潜在域抽出方法を提供することにあ
る。
その目的とするところは、バグの潜在している文を抽出
するプログラムバグ潜在域抽出方法を提供することにあ
る。
【０００９】
【課題を解決するための手段】上記目的を達成するた
め、本発明のプログラムバグ潜在域抽出方法は、一般の
手続き型言語で記述されたプログラムのバグ潜在域を抽
出するプログラムバグ潜在域抽出方法であって、文の間
の依存関係を記録するためのコードをソースプログラム
に埋め込むインストルメント段階と、コンパイル、リン
クされた実行可能プログラムの実行を制御するプログラ
ム実行制御段階と、文の間のデータ依存関係を記録する
データ依存関係記録段階と、制御定義依存関係を記録す
る制御定義依存関係記録段階と、変数の値の設定漏れに
影響を与える分岐文との依存関係を記録する分岐文設定
漏れ依存関係記録段階と、分岐命令において次に依存関
係を辿る対象となる使用変数の集合を最適化する分岐命
令使用変数最適化段階と、発見された変数値エラーを基
にして、それらの文の間の依存関係を解析することによ
り、バグの潜在している文を抽出するプログラムバグ潜
在域獲得段階とを有し、バグの存在するプログラム内の
文を限定することを要旨とする。
め、本発明のプログラムバグ潜在域抽出方法は、一般の
手続き型言語で記述されたプログラムのバグ潜在域を抽
出するプログラムバグ潜在域抽出方法であって、文の間
の依存関係を記録するためのコードをソースプログラム
に埋め込むインストルメント段階と、コンパイル、リン
クされた実行可能プログラムの実行を制御するプログラ
ム実行制御段階と、文の間のデータ依存関係を記録する
データ依存関係記録段階と、制御定義依存関係を記録す
る制御定義依存関係記録段階と、変数の値の設定漏れに
影響を与える分岐文との依存関係を記録する分岐文設定
漏れ依存関係記録段階と、分岐命令において次に依存関
係を辿る対象となる使用変数の集合を最適化する分岐命
令使用変数最適化段階と、発見された変数値エラーを基
にして、それらの文の間の依存関係を解析することによ
り、バグの潜在している文を抽出するプログラムバグ潜
在域獲得段階とを有し、バグの存在するプログラム内の
文を限定することを要旨とする。
【００１０】
【作用】本発明のプログラムバグ潜在域抽出方法では、
実行された文の間のデータ依存関係を記録し、制御定義
依存関係を記録し、変数の値の設定漏れに影響を与える
分岐文との依存関係を記録し、また分岐命令において次
に依存関係を辿る対象とする使用変数の集合を最適化
し、抽出された文の間の依存関係を用いてプログラムバ
グ潜在域を抽出する。
実行された文の間のデータ依存関係を記録し、制御定義
依存関係を記録し、変数の値の設定漏れに影響を与える
分岐文との依存関係を記録し、また分岐命令において次
に依存関係を辿る対象とする使用変数の集合を最適化
し、抽出された文の間の依存関係を用いてプログラムバ
グ潜在域を抽出する。
【００１１】
【実施例】以下、図面を用いて本発明の実施例を説明す
る。
る。
【００１２】図１は、本発明の一実施例に係わるプログ
ラムバグ潜在域抽出方法を実施する装置の構成を部分的
に流れ図式に表現したブロック図である。
ラムバグ潜在域抽出方法を実施する装置の構成を部分的
に流れ図式に表現したブロック図である。
【００１３】図１に示すプログラムバグ潜在域抽出装置
は、文の間の依存関係を記録するためのコードをソース
プログラムに埋め込むインストルメント部１と、コンパ
イル、リンクされた実行可能プログラムの実行を制御す
るプログラム実行制御部３と、該プログラム実行制御部
３内に設けられ、文の間のデータ依存関係を記録するデ
ータ依存関係記録部３ａ、制御定義依存関係を記録する
制御定義依存関係記録部３ｂ、および変数の値の設定漏
れに影響を与える分岐文との依存関係を記録する分岐文
設定漏れ依存関係記録部３ｃと、分岐命令において次に
依存関係を辿る対象となる使用変数の集合を最適化する
分岐命令使用変数最適化部５ａを有し、発見された変数
値エラーを基にして、それらの文の間の依存関係を解析
することにより、バグの潜在している文を抽出するプロ
グラムバグ潜在域獲得段階５とを有する。
は、文の間の依存関係を記録するためのコードをソース
プログラムに埋め込むインストルメント部１と、コンパ
イル、リンクされた実行可能プログラムの実行を制御す
るプログラム実行制御部３と、該プログラム実行制御部
３内に設けられ、文の間のデータ依存関係を記録するデ
ータ依存関係記録部３ａ、制御定義依存関係を記録する
制御定義依存関係記録部３ｂ、および変数の値の設定漏
れに影響を与える分岐文との依存関係を記録する分岐文
設定漏れ依存関係記録部３ｃと、分岐命令において次に
依存関係を辿る対象となる使用変数の集合を最適化する
分岐命令使用変数最適化部５ａを有し、発見された変数
値エラーを基にして、それらの文の間の依存関係を解析
することにより、バグの潜在している文を抽出するプロ
グラムバグ潜在域獲得段階５とを有する。
【００１４】本発明のプログラムバグ潜在域抽出方法で
は、プログラムバグ潜在域外の文に値誤りバグがあって
も、その値誤りバグは現在着目している変数値エラーを
引き起こした原因とはならない、すなわちその値誤りバ
グを修正しても同じ変数値エラーが発生するような性質
を有するプログラム内の文の部分集合であるプログラム
バグ潜在域を抽出するものである。
は、プログラムバグ潜在域外の文に値誤りバグがあって
も、その値誤りバグは現在着目している変数値エラーを
引き起こした原因とはならない、すなわちその値誤りバ
グを修正しても同じ変数値エラーが発生するような性質
を有するプログラム内の文の部分集合であるプログラム
バグ潜在域を抽出するものである。
【００１５】デバッグ対象のプログラミング言語として
は、Ａｄａ，Ｐａｓｃａｌ，Ｃ等の一般の手続き型言語
を想定しているが、ここでは、説明を簡単にするため、
プログラム内の文は代入文、分岐文、ループ文、手続き
呼び出し文、入力文、および、出力文からなるとする。
は、Ａｄａ，Ｐａｓｃａｌ，Ｃ等の一般の手続き型言語
を想定しているが、ここでは、説明を簡単にするため、
プログラム内の文は代入文、分岐文、ループ文、手続き
呼び出し文、入力文、および、出力文からなるとする。
【００１６】代入文、手続き呼び出し文、入力文、出力
文を各々、代入命令、手続き呼び出し命令、入力命令、
出力命令、そして分岐文の条件式部分、ループ文の条件
式部分を各々、分岐命令、ループ命令と呼ぶこととす
る。ある入力を与えてプログラムを実行した場合、実行
された命令の列を実行系列と呼ぶ。ｔ番目に命令の実行
が行われた時点を実行時点ｔと呼ぶ。図２に示したプロ
グラムｍｉｍ−ｍａｘの実行系列では、ｔI は実行時点
ｔにおいて命令Ｉが実行されたことを表わしている。実
行時点ｔで実行された命令で使用された（値が参照され
た）変数の集合をＵｓｅ（ｔ）で表わす。変数ｖに関し
て、２つの実行時点ｓ，ｔ（ｓ＜ｔ）の間には、３つの
依存関係、ｓ＝Ｄｅｆ（ｔ，ｖ），ｓ∈ＣｔｌＤｅｆ
（ｔ，ｖ），ｓ∈ＯｍｓＣｏｎｄ（ｔ，ｖ）が定義され
る。
文を各々、代入命令、手続き呼び出し命令、入力命令、
出力命令、そして分岐文の条件式部分、ループ文の条件
式部分を各々、分岐命令、ループ命令と呼ぶこととす
る。ある入力を与えてプログラムを実行した場合、実行
された命令の列を実行系列と呼ぶ。ｔ番目に命令の実行
が行われた時点を実行時点ｔと呼ぶ。図２に示したプロ
グラムｍｉｍ−ｍａｘの実行系列では、ｔI は実行時点
ｔにおいて命令Ｉが実行されたことを表わしている。実
行時点ｔで実行された命令で使用された（値が参照され
た）変数の集合をＵｓｅ（ｔ）で表わす。変数ｖに関し
て、２つの実行時点ｓ，ｔ（ｓ＜ｔ）の間には、３つの
依存関係、ｓ＝Ｄｅｆ（ｔ，ｖ），ｓ∈ＣｔｌＤｅｆ
（ｔ，ｖ），ｓ∈ＯｍｓＣｏｎｄ（ｔ，ｖ）が定義され
る。
【００１７】図３はこれらの依存関係を説明している。
命令”ｖ:=”は変数ｖを定義する（値を設定する）こと
を、命令”:=ｖ”は変数ｖを使用する（値を参照する）
ことを示す。”:=”はある命令を表わす。◇は分岐命令
あるいはループ命令の実行時点を、○はそれ以外の命令
の実行時点を表わしている。図２に示したプログラムｍ
ｉｎ−ｍａｘの実行系列では、実行時点６から変数ｍｉ
ｎに関して依存関係Ｄｅｆ，ＯｍｓＣｏｎｄを辿ると、
実行時点１，２，４が抽出される。
命令”ｖ:=”は変数ｖを定義する（値を設定する）こと
を、命令”:=ｖ”は変数ｖを使用する（値を参照する）
ことを示す。”:=”はある命令を表わす。◇は分岐命令
あるいはループ命令の実行時点を、○はそれ以外の命令
の実行時点を表わしている。図２に示したプログラムｍ
ｉｎ−ｍａｘの実行系列では、実行時点６から変数ｍｉ
ｎに関して依存関係Ｄｅｆ，ＯｍｓＣｏｎｄを辿ると、
実行時点１，２，４が抽出される。
【００１８】図２で示したように、依存関係を辿ること
によって得られる有向グラフをＣｒｉｔｉｃａｌ−Ｆｌ
ｏｗグラフと呼ぶ。実行時点ｊから依存関係を辿る場合
には、その実行時点ｊにおいて使用されている各変数ｗ
∈Ｕｓｅ（ｊ）に対して、Ｄｅｆ（ｊ，ｗ），ＣｔｌＤ
ｅｆ（ｊ，ｗ），ＯｍｓＣｏｎｄ（ｊ，ｗ）となる実行
時点を辿っていく。Ｃｒｉｔｉｃａｌ−Ｆｌｏｗグラフ
内の実行時点をＣｒｉｔｉｃａｌ実行時点と呼ぶ。プロ
グラムバグ潜在域はＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフ
内の各Ｃｒｉｔｉｃａｌ実行時点で実行された命令の集
合である。
によって得られる有向グラフをＣｒｉｔｉｃａｌ−Ｆｌ
ｏｗグラフと呼ぶ。実行時点ｊから依存関係を辿る場合
には、その実行時点ｊにおいて使用されている各変数ｗ
∈Ｕｓｅ（ｊ）に対して、Ｄｅｆ（ｊ，ｗ），ＣｔｌＤ
ｅｆ（ｊ，ｗ），ＯｍｓＣｏｎｄ（ｊ，ｗ）となる実行
時点を辿っていく。Ｃｒｉｔｉｃａｌ−Ｆｌｏｗグラフ
内の実行時点をＣｒｉｔｉｃａｌ実行時点と呼ぶ。プロ
グラムバグ潜在域はＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフ
内の各Ｃｒｉｔｉｃａｌ実行時点で実行された命令の集
合である。
【００１９】次に、図１に示すプログラムバグ潜在域抽
出装置の各部について説明する。
出装置の各部について説明する。
【００２０】（１）インストルメント部１ プログラム内の各命令の実行時に、以下に説明するプロ
グラム実行制御部３における「命令実行時の処理」に記
述した処理を実行するために必要なコードをソースプロ
グラム内に埋め込む。
グラム実行制御部３における「命令実行時の処理」に記
述した処理を実行するために必要なコードをソースプロ
グラム内に埋め込む。
【００２１】（２）プログラム実行制御部３ (a)プログラム実行時に記録する情報 デバッグ対象プログラムを実行しながら、記録する情報
を以下に示す。
を以下に示す。
【００２２】・ＣｕｒＣｔｌ 現実行時点ｃにおける制御フロー。
【００２３】即ち、現在の実行時点ｃの実行を決定した
分岐実行時点（分岐命令、ループ命令、手続き呼び出し
命令の実行時点）の集合。
分岐実行時点（分岐命令、ループ命令、手続き呼び出し
命令の実行時点）の集合。
【００２４】これは、制御の流れが分岐した実行時点を
要素とするスタック構造を構成することにより、求める
ことができる。スタックＣｕｒＣｔｌに要素ｃをプッシ
ュダウンする操作を「ｐｕｓｈＣｕｒＣｔｌ
（ｃ）；」，スタックＣｕｒＣｔｌから要素を１つ、ポ
ップアップする操作を「ｐｏｐＣｕｒＣｔｌ；」で表
す。
要素とするスタック構造を構成することにより、求める
ことができる。スタックＣｕｒＣｔｌに要素ｃをプッシ
ュダウンする操作を「ｐｕｓｈＣｕｒＣｔｌ
（ｃ）；」，スタックＣｕｒＣｔｌから要素を１つ、ポ
ップアップする操作を「ｐｏｐＣｕｒＣｔｌ；」で表
す。
【００２５】実行時点ｓにおける制御フローをＣｔｌ
（ｓ）で表す。
（ｓ）で表す。
【００２６】・ＣｕｒＤｅｆ（ｘ） 各変数ｘに対して、変数ｘを定義した最新の実行時点ｐ
を記録する。
を記録する。
【００２７】・ＣｕｒＤｅｆＣｔｌ（ｘ） 各変数ｘに対して、変数ｘを定義した最新の実行時点ｐ
における制御フローＣｔｌ（ｐ）。
における制御フローＣｔｌ（ｐ）。
【００２８】・ＯｍｓＶａｒｓ（ｊ） 分岐命令を実行した各実行時点ｊに対して、実行されな
かった分岐パス上で定義される可能性のある変数の集
合。
かった分岐パス上で定義される可能性のある変数の集
合。
【００２９】この集合の求め方については、文献：エイ
ホ、ウルマン著、土居訳「コンパイラ」、培風館（198
6）を参照されたい。
ホ、ウルマン著、土居訳「コンパイラ」、培風館（198
6）を参照されたい。
【００３０】(b)命令実行時の処理 現在実行しようとしている実行時点をｃとする。
【００３１】(b-1)代入命令、入力命令を実行する場合 代入命令、入力命令で定義する変数をｗとすると、 ＣｕｒＤｅｆ（ｗ）:=ｃ； ＣｕｒＤｅｆＣｔｌ（ｗ）:=ＣｕｒＣｔｌ； (b-2)分岐命令、ループ命令、手続き呼び出し命令を実
行する場合 ｐｕｓｈＣｕｒＣｔｌ（ｃ）； スタックＣｕｒＣｔｌ
に実行時点ｃをプッシュダウンする。
行する場合 ｐｕｓｈＣｕｒＣｔｌ（ｃ）； スタックＣｕｒＣｔｌ
に実行時点ｃをプッシュダウンする。
【００３２】(b-3)分岐文、ループ文、および手続き呼
び出し文で呼び出した手続きの実行を終了する場合 ｐｏｐＣｕｒＣｔｌ； スタックＣｕｒＣｔｌから実行
時点を１つポップアップする。
び出し文で呼び出した手続きの実行を終了する場合 ｐｏｐＣｕｒＣｔｌ； スタックＣｕｒＣｔｌから実行
時点を１つポップアップする。
【００３３】但し、ループ文を終了する場合には、その
ループ文本体部の繰り返し回数だけ、「ｐｏｐＣｕｒＣ
ｔｌ；」を実行する。
ループ文本体部の繰り返し回数だけ、「ｐｏｐＣｕｒＣ
ｔｌ；」を実行する。
【００３４】(b-4)命令の実行時に、変数ｗの値を使用
する場合 （３）プログラムバグ潜在域獲得部５ プログラム実行制御部３により、全ての実行時点ｊ、お
よびその実行時点ｊにおいて使用している変数ｗ∈Ｕｓ
ｅ（ｊ）に対して、Ｄｅｆ（ｊ，ｗ），ＣｔｌＤｅｆ
（ｊ，ｗ），ＯｍｓＣｏｎｄ（ｊ，ｗ）が求められてい
る。各実行時点ｊから依存関係を辿る場合には、その実
行時点ｊにおいて使用されている変数の集合であるＵｓ
ｅ（ｊ）を、分岐命令使用変数最適化で以下に示すよう
に最適化した後、各変数ｗ∈Ｕｓｅ（ｊ）に対して、Ｄ
ｅｆ（ｊ，ｗ），ＣｔｌＤｅｆ（ｊ，ｗ），ＯｍｓＣｏ
ｎｄ（ｊ，ｗ）となる実行時点を辿っていく。実行時点
ｔにおける変数ｖに関するプログラムバグ潜在域は、実
行時点ｔを起点として、変数ｖに関して、これらの最適
化された依存関係Ｄｅｆ，ＣｔｌＤｅｆ，ＯｍｓＣｏｎ
ｄを辿った時に抽出される各実行時点において、実行さ
れた命令の集合として得られる。
する場合 （３）プログラムバグ潜在域獲得部５ プログラム実行制御部３により、全ての実行時点ｊ、お
よびその実行時点ｊにおいて使用している変数ｗ∈Ｕｓ
ｅ（ｊ）に対して、Ｄｅｆ（ｊ，ｗ），ＣｔｌＤｅｆ
（ｊ，ｗ），ＯｍｓＣｏｎｄ（ｊ，ｗ）が求められてい
る。各実行時点ｊから依存関係を辿る場合には、その実
行時点ｊにおいて使用されている変数の集合であるＵｓ
ｅ（ｊ）を、分岐命令使用変数最適化で以下に示すよう
に最適化した後、各変数ｗ∈Ｕｓｅ（ｊ）に対して、Ｄ
ｅｆ（ｊ，ｗ），ＣｔｌＤｅｆ（ｊ，ｗ），ＯｍｓＣｏ
ｎｄ（ｊ，ｗ）となる実行時点を辿っていく。実行時点
ｔにおける変数ｖに関するプログラムバグ潜在域は、実
行時点ｔを起点として、変数ｖに関して、これらの最適
化された依存関係Ｄｅｆ，ＣｔｌＤｅｆ，ＯｍｓＣｏｎ
ｄを辿った時に抽出される各実行時点において、実行さ
れた命令の集合として得られる。
【００３５】［分岐命令使用変数最適化部５ａ］実行時
点ｊにおいて辿る対象となる変数の集合であるＵｓｅ
（ｊ）をできる限り小さい集合にとることにより、プロ
グラムバグ潜在域を最適化する。変数ｗ∈Ｕｓｅ（ｊ）
に関して実行時点ｊから依存関係を辿ることによって抽
出される実行時点の集合をＣｒｉｔｉｃａｌＦｌｏｗ
（ｊ，ｗ）と表わすこととする。分岐命令（あるいはル
ープ命令）の実行時点ｊにおいて、以下のようにＵｓｅ
（ｊ）の最適化を行う。
点ｊにおいて辿る対象となる変数の集合であるＵｓｅ
（ｊ）をできる限り小さい集合にとることにより、プロ
グラムバグ潜在域を最適化する。変数ｗ∈Ｕｓｅ（ｊ）
に関して実行時点ｊから依存関係を辿ることによって抽
出される実行時点の集合をＣｒｉｔｉｃａｌＦｌｏｗ
（ｊ，ｗ）と表わすこととする。分岐命令（あるいはル
ープ命令）の実行時点ｊにおいて、以下のようにＵｓｅ
（ｊ）の最適化を行う。
【００３６】（Ｏｐｔ１）分岐命令の条件式の値を決定
した項Ｔｅｒｍに含まれる、使用された変数の集合（こ
れをＵｓｅ（Ｔｅｒｍ）で表わす）をＵｓｅ（ｊ）とす
る。
した項Ｔｅｒｍに含まれる、使用された変数の集合（こ
れをＵｓｅ（Ｔｅｒｍ）で表わす）をＵｓｅ（ｊ）とす
る。
【００３７】（Ｏｐｔ２）条件式の値を決定した項が複
数存在する場合（項Ｔｅｒｍ1 ，…
数存在する場合（項Ｔｅｒｍ1 ，…
【外１】 サイズを最小とする項Ｔｅｒｍi のＵｓｅ（Ｔｅｒ
ｍi ）をＵｓｅ（ｊ）とする。
ｍi ）をＵｓｅ（ｊ）とする。
【００３８】一例として、図４に示すプログラムｐｒｏ
ｇ−ｃｏｎｄに入力ｘ＝１，ｙ＝２を与えて実行した時
の実行系列とＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフを図５
に示す。また、分岐命令における使用変数の最適化を行
って、プログラムバグ潜在域を求めた結果を表１に示
す。
ｇ−ｃｏｎｄに入力ｘ＝１，ｙ＝２を与えて実行した時
の実行系列とＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフを図５
に示す。また、分岐命令における使用変数の最適化を行
って、プログラムバグ潜在域を求めた結果を表１に示
す。
【００３９】
【表１】 （Ｏｐｔ０）最適化を行う前の、Ｃｒｉｔｉｃａｌ−Ｆ
ｌｏｗグラフから求められるＣｒｉｔｉｃａｌ実行時点
を○で示す。
ｌｏｗグラフから求められるＣｒｉｔｉｃａｌ実行時点
を○で示す。
【００４０】（Ｏｐｔ１）実行時点１１で実行された分
岐命令の条件式”ｘ＞４orｚ＜２”の値Ｔｒｕｅを決定
した項”ｚ＜２”に含まれる変数ｚのみをＵｓｅ（１
１）として、最適化を行った結果である。変数ｘに関係
する、実行時点１０において実行された命令”ｘ:=ｗ＋
１；”，および実行時点９において実行された命令”
ｗ:=３；”が除外できる。
岐命令の条件式”ｘ＞４orｚ＜２”の値Ｔｒｕｅを決定
した項”ｚ＜２”に含まれる変数ｚのみをＵｓｅ（１
１）として、最適化を行った結果である。変数ｘに関係
する、実行時点１０において実行された命令”ｘ:=ｗ＋
１；”，および実行時点９において実行された命令”
ｗ:=３；”が除外できる。
【００４１】（Ｏｐｔ２）実行時点８で実行された分岐
命令”ｘ＋２＜０and ｙ＞１”では、どちらの項もＦａ
ｌｓｅとなり条件式の値Ｆａｌｓｅを決定している。Ｃ
ｒｉｔｉｃａｌＦｌｏｗ（８，ｘ）＝｛１，２，３，
５｝，ＣｒｉｔｉｃａｌＦｌｏｗ（８，ｙ）＝｛２，
３，６｝である。そこで、Ｃｒｉｔｉｃａｌ−Ｆｌｏｗ
グラフのサイズを最小とする項”ｙ＞１”を選択し、Ｕ
ｓｅ（８）＝｛ｙ｝として、最適化を行った結果であ
る。変数ｘに関係する、実行時点５において実行された
命令”ｘ:=ｘ＋ｙ＋ｚ−１；”，および実行時点１にお
いて実行された命令”ｇｅｔ（ｘ）；”が除外できる。
命令”ｘ＋２＜０and ｙ＞１”では、どちらの項もＦａ
ｌｓｅとなり条件式の値Ｆａｌｓｅを決定している。Ｃ
ｒｉｔｉｃａｌＦｌｏｗ（８，ｘ）＝｛１，２，３，
５｝，ＣｒｉｔｉｃａｌＦｌｏｗ（８，ｙ）＝｛２，
３，６｝である。そこで、Ｃｒｉｔｉｃａｌ−Ｆｌｏｗ
グラフのサイズを最小とする項”ｙ＞１”を選択し、Ｕ
ｓｅ（８）＝｛ｙ｝として、最適化を行った結果であ
る。変数ｘに関係する、実行時点５において実行された
命令”ｘ:=ｘ＋ｙ＋ｚ−１；”，および実行時点１にお
いて実行された命令”ｇｅｔ（ｘ）；”が除外できる。
【００４２】従って、プログラムバグ潜在域は、命令
２、命令３、命令６、命令８、命令１２、および命令１
３からなる命令の集合となる。
２、命令３、命令６、命令８、命令１２、および命令１
３からなる命令の集合となる。
【００４３】
【発明の効果】以上説明したように、本発明によれば、
実行された文の間のデータ依存関係を記録し、制御定義
依存関係を記録し、変数の値の設定漏れに影響を与える
分岐文との依存関係を記録し、また分岐命令において次
に依存関係を辿る対象とする使用変数の集合を最適化
し、抽出された文の間の依存関係を用いてプログラムバ
グ潜在域を抽出しているので、値誤りバグがあると変数
値エラーを引き起こす可能性のある文の集合であるプロ
グラムバグ潜在域を獲得することにより、値誤りバグの
存在する箇所を限定することができ、バグの究明作業を
容易に行うことができる。
実行された文の間のデータ依存関係を記録し、制御定義
依存関係を記録し、変数の値の設定漏れに影響を与える
分岐文との依存関係を記録し、また分岐命令において次
に依存関係を辿る対象とする使用変数の集合を最適化
し、抽出された文の間の依存関係を用いてプログラムバ
グ潜在域を抽出しているので、値誤りバグがあると変数
値エラーを引き起こす可能性のある文の集合であるプロ
グラムバグ潜在域を獲得することにより、値誤りバグの
存在する箇所を限定することができ、バグの究明作業を
容易に行うことができる。
【図１】本発明の一実施例に係わるプログラムバグ潜在
域抽出方法を実施する装置の構成を部分的に流れ図式に
表現したブロック図である。
域抽出方法を実施する装置の構成を部分的に流れ図式に
表現したブロック図である。
【図２】プログラムｍｉｎ−ｍａｘを実行した時の実行
系列を示す図である。
系列を示す図である。
【図３】命令の間の依存関係を説明する図である。
【図４】プログラムバグ潜在域の最適化について説明す
るために使用されたプログラムｐｒｏｇ−ｃｏｎｄを示
す図である。
るために使用されたプログラムｐｒｏｇ−ｃｏｎｄを示
す図である。
【図５】プログラムｐｒｏｇ−ｃｏｎｄを実行した時の
実行系列とそのＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフを示
す図である。
実行系列とそのＣｒｉｔｉｃａｌ−Ｆｌｏｗグラフを示
す図である。
【図６】従来技術における動的スライスを求める装置の
構成を示す図である。
構成を示す図である。
【図７】動的スライスを説明するために使用されたプロ
グラムｍｉｎ−ｍａｘを示す図である。
グラムｍｉｎ−ｍａｘを示す図である。
１ インストルメント部 ３ プログラム実行制御部 ３ａ データ依存関係記録部 ３ｂ 制御定義依存関係記録部 ３ｃ 分岐文設定漏れ依存関係記録部 ５ プログラムバグ潜在域獲得部 ５ａ 分岐命令使用変数最適化部
Claims (1)
- 【請求項１】 一般の手続き型言語で記述されたプログ
ラムのバグ潜在域を抽出するプログラムバグ潜在域抽出
方法であって、文の間の依存関係を記録するためのコー
ドをソースプログラムに埋め込むインストルメント段階
と、コンパイル、リンクされた実行可能プログラムの実
行を制御するプログラム実行制御段階と、文の間のデー
タ依存関係を記録するデータ依存関係記録段階と、制御
定義依存関係を記録する制御定義依存関係記録段階と、
変数の値の設定漏れに影響を与える分岐文との依存関係
を記録する分岐文設定漏れ依存関係記録段階と、分岐命
令において次に依存関係を辿る対象となる使用変数の集
合を最適化する分岐命令使用変数最適化段階と、発見さ
れた変数値エラーを基にして、それらの文の間の依存関
係を解析することにより、バグの潜在している文を抽出
するプログラムバグ潜在域獲得段階とを有し、バグの存
在するプログラム内の文を限定することを特徴とするプ
ログラムバグ潜在域抽出方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5282510A JPH07134664A (ja) | 1993-11-11 | 1993-11-11 | プログラムバグ潜在域抽出方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5282510A JPH07134664A (ja) | 1993-11-11 | 1993-11-11 | プログラムバグ潜在域抽出方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07134664A true JPH07134664A (ja) | 1995-05-23 |
Family
ID=17653390
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5282510A Pending JPH07134664A (ja) | 1993-11-11 | 1993-11-11 | プログラムバグ潜在域抽出方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07134664A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6757639B2 (en) | 2001-07-26 | 2004-06-29 | Kabushiki Kaisha Toshiba | Modification risk degree measurement system, modification risk degree measurement method and modification risk degree measurement program |
| WO2014141352A1 (ja) * | 2013-03-11 | 2014-09-18 | 株式会社 日立製作所 | システム制御装置 |
-
1993
- 1993-11-11 JP JP5282510A patent/JPH07134664A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6757639B2 (en) | 2001-07-26 | 2004-06-29 | Kabushiki Kaisha Toshiba | Modification risk degree measurement system, modification risk degree measurement method and modification risk degree measurement program |
| US7072796B2 (en) | 2001-07-26 | 2006-07-04 | Kabushiki Kaisha Toshiba | Modification risk degree measurement system, modification risk degree measurement method and modification risk degree measurement program |
| WO2014141352A1 (ja) * | 2013-03-11 | 2014-09-18 | 株式会社 日立製作所 | システム制御装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8966449B2 (en) | Test case pattern matching | |
| Korel et al. | Application of Dynamic Slicing in Program Debugging. | |
| US8359584B2 (en) | Debugging from a call graph | |
| US6430741B1 (en) | System and method for data coverage analysis of a computer program | |
| Soltani et al. | A guided genetic algorithm for automated crash reproduction | |
| US9582396B2 (en) | Techniques for generating an executable debugger script | |
| JPH0950389A (ja) | コンピュータシステムを使って実装される装置及び方法 | |
| US8875111B2 (en) | Intermediate language representation and modification | |
| JPH02272645A (ja) | プログラム・デバツグ支援方法 | |
| US5987248A (en) | Debugging information display device | |
| WO2017201853A1 (zh) | 基于切片模型的程序回归错误定位方法 | |
| US7624381B1 (en) | Portable detection of start and completion of object construction | |
| JPH07134664A (ja) | プログラムバグ潜在域抽出方法 | |
| US6993749B2 (en) | Conditional debug monitors | |
| JP2015069400A (ja) | ソフトウェアテストシステム | |
| JPH06202905A (ja) | クリティカルスライス・プログラムデバッグシステム | |
| JPH06214825A (ja) | プログラム・バグ潜在域抽出装置 | |
| JPH08212105A (ja) | プログラム管理装置 | |
| de Souza et al. | ValiPVM-a graphical tool for structural testing of PVM programs | |
| JPH11282722A (ja) | プログラム検証方法 | |
| US20070168978A1 (en) | Computer program code debugging method and system | |
| Khanam et al. | Aspectual Analysis of Legacy Systems: Code Smells and Transformations in C | |
| JP4894602B2 (ja) | 修正対象ファイル検索装置と修正対象ファイル検索方法および修正対象ファイル検索プログラム | |
| JP2658982B2 (ja) | 特定命令実行検出方式 | |
| US20210303444A1 (en) | Method, apparatus and computer program and user interface and technique to debug software code |