調(diào)用模式和正確調(diào)用模式語義在Ｐｒｏｌｏｇ程序測(cè)試中的應(yīng)用

摘要：將基于調(diào)用模式語義和正確調(diào)用模式語義的程序分析技術(shù)應(yīng)用于Prolog程序的CPM測(cè)試。通過調(diào)用模式分析獲得內(nèi)部過程被調(diào)用和成功調(diào)用的條件，利用前者刪除不滿足調(diào)用條件的測(cè)試幀，或當(dāng)刪除條件不滿足時(shí)利用該條件更新測(cè)試規(guī)格中過程屬性的劃分準(zhǔn)則; 利用后者預(yù)測(cè)CPM測(cè)試的結(jié)果。該方法可較好地保持程序測(cè)試的質(zhì)量，改善Prolog程序的CPM測(cè)試過程。

關(guān)鍵詞：Prolog； 調(diào)用模式語義； 正確調(diào)用模式語義； 主屬性區(qū)分方法測(cè)試

中圖分類號(hào)：TP311．1文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)04－1008－05

0引言

Prolog是一種邏輯程序設(shè)計(jì)語言，可視為多種基于約束和基于邏輯的聲明式程序設(shè)計(jì)語言的基礎(chǔ)。Prolog是人工智能程序設(shè)計(jì)的主要語言工具之一，可方便地用于系統(tǒng)知識(shí)的表示和推理。給定目標(biāo)G，Prolog程序的執(zhí)行過程就是按照Prolog控制規(guī)則對(duì)G的推理過程。Prolog采用了最左文字優(yōu)先的文字選擇規(guī)則和按照子句在程序中的順序選擇匹配子句的子句選擇規(guī)則。按照該規(guī)則對(duì)目標(biāo)的推理被稱為目標(biāo)的SLD－推理。目標(biāo)G的調(diào)用模式是在G的SLD－推理過程中每一步所選擇的原子子目標(biāo); 正確調(diào)用模式是屬于成功SLD－推理路徑的調(diào)用模式[1]。調(diào)用模式信息通常被用于Prolog程序的優(yōu)化[2]。本文將該信息用于改善Prolog程序的CPM測(cè)試[3，4]。

傳統(tǒng)CPM測(cè)試對(duì)生成測(cè)試用例數(shù)目的控制依賴于待測(cè)試程序的功能規(guī)格。本文工作表明: 在已知待測(cè)試程序源代碼的情況下，可在生成CPM測(cè)試幀的基礎(chǔ)上采用基于實(shí)現(xiàn)的方法進(jìn)一步減少測(cè)試幀的數(shù)目，更新測(cè)試規(guī)格中過程屬性的劃分準(zhǔn)則，從而簡(jiǎn)化測(cè)試用例生成并較好地保持程序測(cè)試的質(zhì)量。此外，由于正確調(diào)用模式信息給出了調(diào)用模式成功的條件，可利用該信息對(duì)測(cè)試結(jié)果進(jìn)行預(yù)測(cè)。

假設(shè)需要測(cè)試程序P:{main(x，y):-x=5，sub(x，y).sub(x，y):-…}。其中sub是一個(gè)內(nèi)部過程。所謂內(nèi)部過程是指Prolog程序中那些不為用戶直接使用，而由程序設(shè)計(jì)人員用于構(gòu)造其他過程的過程。由于sub每次被調(diào)用時(shí)其第一個(gè)輸入?yún)?shù)x均被賦值為5，只需輸入與該性質(zhì)相一致的測(cè)試數(shù)據(jù)，而不是在所有可能的數(shù)據(jù)上測(cè)試sub過程，即可要求輸入數(shù)據(jù)中對(duì)x的賦值不包含任何變量或更具體的x=5。以上處理過程所需的信息可從過程main的調(diào)用模式分析中獲取。該分析將表明sub(5，y)是在目標(biāo)main(x，y)的執(zhí)行過程中有關(guān)sub的惟一調(diào)用模式。

目前，已經(jīng)提出了多種方法用于改善Prolog程序的測(cè)試。比如Prolog測(cè)試系統(tǒng)PROTest Ⅱ?yàn)槊恳粋€(gè)待測(cè)試的程序增加過程參數(shù)類型和應(yīng)用模式信息，利用這些信息可以有效地實(shí)現(xiàn)程序的類型錯(cuò)誤分析和測(cè)試用例生成[5]。算法調(diào)試和功能測(cè)試系統(tǒng)IDTS利用程序調(diào)試的結(jié)果更新程序測(cè)試規(guī)格，不但提高了程序調(diào)試的效率，也改善了Prolog程序的測(cè)試[6]。在CPM測(cè)試方法的研究方面，文獻(xiàn)[7]建立了一種子屬性關(guān)系框架用于CPM測(cè)試中測(cè)試用例的生成;文獻(xiàn)[8]給出了一種基于Z語言規(guī)格的CPM測(cè)試幀生成方法。與以上方法不同的是，本文將利用Prolog程序調(diào)用模式分析的結(jié)果改善程序的CPM測(cè)試過程，關(guān)于該方法的文獻(xiàn)未見報(bào)道。本文假定讀者熟悉Prolog語言的基本語法和語義。

1基礎(chǔ)知識(shí)

1．1CPM測(cè)試

CPM是一種通用的程序功能測(cè)試方法，最早由Ostrand和Balker提出[3]，Horváth 等人給出了該方法的一種形式化描述。CPM測(cè)試的基本思想如下:任意程序(或過程)的功能測(cè)試均不能覆蓋程序(或過程)參數(shù)的所有屬性，因而測(cè)試人員的首要任務(wù)是確定測(cè)試所關(guān)心的輸入?yún)?shù)的主屬性(categories)。每一個(gè)主屬性按照一定的劃分準(zhǔn)則被劃分為若干子屬性(choices)，并要求這些子屬性所覆蓋的輸入數(shù)據(jù)集互不相交，且同一數(shù)據(jù)集中的任意兩個(gè)數(shù)據(jù)對(duì)測(cè)試目的而言是等價(jià)的。一旦確定了程序的主屬性及子屬性，測(cè)試程序?qū)⒆詣?dòng)產(chǎn)生所有可能的測(cè)試幀(test frames)。測(cè)試幀是子屬性的組合，每個(gè)測(cè)試幀包含且僅包含每個(gè)主屬性的一個(gè)子屬性。顯然過程p所有測(cè)試幀的集合也構(gòu)成了p輸入域上的一個(gè)等價(jià)關(guān)系，每個(gè)測(cè)試幀f均表示一個(gè)等價(jià)類，其對(duì)應(yīng)的p的輸入數(shù)據(jù)集表示為input(p， f)。一般情況下，在生成的測(cè)試幀中將包含大量的無用幀，即這些幀中的屬性組合是不可能或沒有實(shí)際意義的。無用幀可通過與子屬性相關(guān)聯(lián)的選擇表達(dá)式刪除。每個(gè)測(cè)試幀產(chǎn)生一個(gè)滿足該子屬性組合的測(cè)試用例。在這些測(cè)試用例的基礎(chǔ)上可生成測(cè)試腳本，運(yùn)行程序(或過程)進(jìn)行測(cè)試。

5結(jié)束語

本文給出了一種利用程序分析技術(shù)輔助Prolog程序CPM測(cè)試的方法。該方法利用調(diào)用模式信息減少內(nèi)部過程CPM測(cè)試中生成測(cè)試用例的數(shù)目，對(duì)過程子屬性進(jìn)行細(xì)分，預(yù)測(cè)測(cè)試結(jié)果，同時(shí)又較好地保持了程序測(cè)試的質(zhì)量。方法所需信息可通過基于調(diào)用模式語義的Prolog程序分析獲得。為此，可利用現(xiàn)有的Prolog程序分析技術(shù)，如用于描述程序性質(zhì)的性質(zhì)描述語言[13~15]和調(diào)用模式分析技術(shù)[9]等。本文以文獻(xiàn)[9，12]中給出的調(diào)用模式語義和正確調(diào)用模式語義為例說明了該方法的有效性；此外，將調(diào)用模式信息用于CPM測(cè)試也擴(kuò)展了Prolog調(diào)用模式信息的應(yīng)用領(lǐng)域。

參考文獻(xiàn):

[1]GABBRIELLI M， LEVI G， MEO M C. Observable behaviors and equivalences of logic programs[J]. Information and Computation， 1995，122(1):1－29.

[2]GABBRIELLI M， GIACOBAZZI R. Goal independency and call patterns in the analysis of logic programs[C]//Proc of the 9th ACM Symposium on Applied Computing. New York: ACM Press， 1994:394－399.

[3]OSTRAND T J， BALKER M J. The category－partition method for specifying and generating functional tests[J]. Communications of ACM， 1988，31(6):676－686.

[4]BALCER M J， HASLING W M， OSTRAND T J. Automatic generation of test script from formal test specifications[C]//Proc of the 3rd ACM Annual Symposium on Software Testing， Analysis， and Verification. New York: ACM Press， 1989:210－218.

[5]BELLI F， JACK O. PROTest Ⅱ， testing logic programs[R].[S.l]: ADT， 1992.

[6]ALEXIN Z， GYIMTHY T， KKAI G. IDTS: integrated system for debugging and testing Prolog programs[EB/OL].(1997).http://www.inf.u－szeged.hu/~kokai/ idt.html.

[7]CHEN T Y， POON P L， TSE T H. A choice relation framework for supporting category－partition test case generation[J]. IEEE Trans on Software Engineering， 2003，29(7):577－593.

[8]AMMANN P， OFFUTT A J. Using formal methods to derive test frames in category partition testing[C]//Proc of the 9th Annual Conference on Computer Assurance. Gaithersburg， MD: IEEE Computer Society Press， 1994:69－80.

[9]SPOTO F， LEVI G. Abstract interpretation of Prolog programs[C]//Proc of the 7th International Conference on Algebraic Methodology and Software Technology， LNCS 1548. New York: Springer－Verlag， 1999:455－470.

[10]COUSOT P， COUSOT R. Abstract interpretation and applications to logic programs[J]. Journal of Logic Programming， 1992，13(2－3):103－179.

[11]ZHAO Ling－zhong， GU Tian－long， QIAN Jun－yan， et al. Designing Prolog semantics for a class of observables[C]//Proc of the 9th Paci－fic Rim International Conference on Artificial Intelligence， LNAI 4099. Berlin: Springer－Verlag， 2006:1052－1057.

[12]ZHAO Ling－zhong， GU Tian－long， QIAN Jun－yan， et al. A constraint－based correct call pattern semantics for prolog as an abstraction of decorated tree semantics[C]//Proc of the 18th International Conference on Software Engineering Knowledge Engineering. San Francisco， California: Knowledge System Institute， 2006:359－362.

[13]HOWE M， KING A. Efficient groundness analysis in Prolog[J]. Theory and Practice of Logic Programming， 2003，3(1):95－124.

[14]CHARLIER L， ROSSI S， HENTENRYCK van P. Sequence－based abstract interpretation of Prolog[J]. Theory and Practice of Logic Programming， 2002，2(1):25－84.

[15]VOLPE P. A first－order language for expressing sharing and type properties of logic programs[J]. Science of Computer Programming， 2001，39(1):125－148.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”