面向Java的分布式程序測試系統(tǒng)（

1、顧慶 等:面向Java的分布式程序測試系統(tǒng)749面向Java的分布式程序測試系統(tǒng)*Supported by the Key Science-Technology Project of the National Ninth Five-Year-Plan of China under Grant No.98-780-01-07- 03 (國家“九五”重點科技攻關(guān)項目); the National High-Tech Research and Development Program Plan of China under Grant No.2001AA113090 (國家高技術(shù)研究發(fā)展計劃(863)

2、第一作者簡介: 顧慶(1972),男,江蘇常州人,博士,副教授,主要研究領(lǐng)域為分布式語言和系統(tǒng).顧 慶+, 陳道蓄, 謝 立, 孫鐘秀(南京大學(xué) 計算機軟件新技術(shù)國家重點實驗室,江蘇 南京 210093)A Java-Oriented Distributed Program Testing SystemGU Qing+, CHEN Dao-Xu, XIE Li, SUN Zhong-Xiu(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China)+ Corresp

3、onding author: Phn: 86-25-3592339, Fax: 86-25-3300710, E-mail: guqReceived 2002-09-03; Accepted 2002-12-04Gu Q, Chen DX, Xie L, Sun ZX. A Java-oriented distributed program testing system. Journal of Software, 2003,14(4):743749.Abstract:Because the program is running in a distributed way, both the co

4、ncurrent features and the runtime environments should be taken into account when testing a distributed program. A Java oriented distributed program test system is put forward in this paper, which is called JDPT (Java-oriented distributed program testing system). JDPT defines events based on the runt

5、ime environments, records execution processes of the distributed program as event sequences, and defines event sequencing constraints to check the validity of those feasible set of event sequences. By the technology, the JDPT can effectively estimate the correctness of concurrent executions of the t

6、ested program within distributed environments, and can be used to test Java programs running upon multiple platforms.Key words:software testing; distributed program testing; Java; concurrent program; event sequencing constraints摘 要:由于程序的分布運行,測試分布式程序必須同時考慮并發(fā)特性和運行環(huán)境.介紹了一個面向Java語言的分布式程序測試系統(tǒng)JDPT(Java-or

7、iented distributed program testing system).JDPT基于運行環(huán)境定義事件,通過事件序列記錄分布式程序的運行過程,并定義事件約束檢測可行事件序列集的有效性.通過該技術(shù),JDPT可以有效地判斷程序在運行環(huán)境中并發(fā)執(zhí)行的正確性,適用于跨平臺的Java程序測試.關(guān)鍵詞:軟件測試;分布式程序測試;Java;并發(fā)程序;事件約束中圖法分類號:TP311文獻標識碼: A隨著Internet的普及和計算機軟、硬件技術(shù)的發(fā)展,分布式程序和應(yīng)用已成為今后軟件開發(fā)的主要方向之一.與集中式的串行程序相比,分布式程序需要考慮與運行環(huán)境的合作以及分布單元間的并發(fā)問題,這為分布式程序

8、測試工具帶來了新的挑戰(zhàn).保障分布式程序的正確性需要從兩方面入手:一是從分布式程序自身出發(fā),側(cè)重并發(fā)程序的形式化表示和驗證;二是在分布運行環(huán)境中監(jiān)控和記錄分布式程序的執(zhí)行過程,分析程序在各種運行環(huán)境中的執(zhí)行狀態(tài)和性能.測試需要結(jié)合這兩個方面,從形式化表示中獲得規(guī)約,在運行環(huán)境中檢測程序?qū)崿F(xiàn)與規(guī)約的一致性.目前已有的分布式程序測試工具如MAD(monitoring and debugging environment)1,PSET(distributed program structure and event trace)2,OrcShot3,SPIN4,LTSA5等都沒有很好地考慮這兩方面的結(jié)合.

9、其中MAD,PSET和OrcShot偏重運行環(huán)境中的檢測,缺乏判斷程序正確性的依據(jù);SPIN和LTSA則偏重并發(fā)程序的驗證,不能確保程序?qū)崿F(xiàn)與運行環(huán)境的有效協(xié)作.本文提出的測試系統(tǒng)JDPT(Java-oriented distributed program testing system)較為有效地解決了這兩方面的結(jié)合問題.1 分布式程序測試1.1 分布式程序測試的主要問題分布式程序由多個相互協(xié)作的分布單元構(gòu)成.這些分布單元相對獨立且位于網(wǎng)絡(luò)中不同的機器上,單元間通過消息傳遞實現(xiàn)協(xié)作.在網(wǎng)絡(luò)環(huán)境中,支撐分布式程序運行需要一個層次式的協(xié)議架構(gòu),包括通信平臺(如TCP/IP)和支撐系統(tǒng)(如commo

10、n object request broker architecture,簡稱CORBA),兩者構(gòu)成分布式程序的運行環(huán)境.基于此,測試分布式程序主要需考慮以下兩個方面的問題:· 程序自身的問題.對于多個相對獨立的分布單元,需要處理其間的通信、同步以及它們的并發(fā)操作.· 分布運行環(huán)境的問題.包括程序與運行環(huán)境的合作、網(wǎng)絡(luò)通信的完整性(通信信息無差錯、無重復(fù)、不失序)、平臺無關(guān)性以及異構(gòu)系統(tǒng)間的互操作性等.程序測試需要考慮測試的正確性和充分性.由于并發(fā)所導(dǎo)致的不確定性,以同一個測試用例運行同一個分布式程序,多次執(zhí)行也會產(chǎn)生不同的運行結(jié)果.這時需要不同的測試手段,如以事件序列記錄

11、程序的運行過程、采用確定性測試以事件序列作為測試用例等.并發(fā)的多樣性導(dǎo)致分布式程序難以得到充分的測試,這時需要定義新的充分性準則,采用新的測試用例選擇方法等.1.2 E-CSPE約束E-CSPE(extended CSPE)6是在CSPE(constraints on succeeding and proceeding events)基礎(chǔ)上提出的一個事件約束描述規(guī)則.E-CSPE約束是指采用E-CSPE描述的事件約束.E-CSPE約束在給定狀態(tài)謂詞下定義前后兩個事件間的依賴關(guān)系以及這種關(guān)系的或然性.E-CSPE約束的基本形式是opevt1;®evt2UC.其中,U是被測程序;evt1

12、和evt2是前后相關(guān)的兩個運行事件,它們不需要緊密相連;C是一個狀態(tài)謂詞,它決定evt1和evt2之間的依賴關(guān)系是否存在;op規(guī)定依賴關(guān)系的或然性.op有3種取值,對應(yīng)3類不同的E-CSPE約束,具體如下:· aevt1;®evt2UC:(always under condition),在程序U的運行過程中,若條件C成立,則evt2發(fā)生于evt1之后總有效.· mevt1;®evt2UC:(must under condition),在程序U的運行過程中,若條件C成立,則evt1發(fā)生以后evt2必發(fā)生.· evt1;®evt2UC:(

13、never under condition),在程序U的運行過程中,若條件C成立,則evt2發(fā)生于evt1之后總無效.任意給定U的一個可行事件序列s和針對U的一個E-CSPE約束r,s與r之間可定義3種關(guān)系:(1) s覆蓋r; (2) s違反r; (3) s與r無關(guān).針對約束r,根據(jù)上述3種關(guān)系可以定義:· ConformSet(r,U):所有覆蓋r的可行事件序列集合;· ViolateSet(r,U):所有違反r的可行事件序列集合;· NonsenseSet(r,U):所有與r無關(guān)的可行事件序列組成的集合.令Feasible(U)為程序U所有可行事件序列的集合,

14、顯然有ConformSet(r, U)ViolateSet(r, U)NonsenseSet(r, U) = Feasible(U).上述集合定義可以作為測試時的依據(jù),具體為(設(shè)CSET為針對U定義的E-CSPE約束集合):· 若,則針對任一可行事件序列s,CSET中總存在與s相關(guān)(覆蓋或違反)的約束r.可以認為約束集CSET相對于U的實現(xiàn)是充分的.· 若,則針對CSET中的任一約束r,不存在違反r的可行事件序列.可以認為U的實現(xiàn)相對于約束集CSET是正確的.1.3 并發(fā)程序FSP表示和E-CSPE約束推導(dǎo)FSP(finite state processes)5是LTSA(

15、labeled transition system analyzer)中采用的一類進程代數(shù)記法.它可以描述一個并發(fā)程序并驗證其行為(behavior)與規(guī)約的一致性.FSP的優(yōu)點是可以較方便地從代數(shù)記法轉(zhuǎn)換成對應(yīng)的Java程序.在FSP中,分布單元被定義為進程(process),進程按遞歸的形式定義并抽象為動作序列,對應(yīng)的狀態(tài)機表示為LTS(labeled transition system).對于生產(chǎn)者-消費者問題,可以采用FSP表示如下:WAREHOUSE(N)=GSET0,GSETcontent:0.N=(when (content<N) put®GSETcontent+

16、1|when (content>0) get®GSETcontent-1),PRODUCER=(put®PRODUCER),CONSUMER=(get®CONSUMER),|PRO_CON=(pro1.3:PRODUCER | con1.3:CONSUMER | pro1.3, con1.3:WAREHOUSE(5).其中由大寫字母表示的是進程,小寫字母表示的是動作.FSP中的基本操作符是®,表示動作間的順序.其他操作符包括:選擇“|”、條件控制“when”、進程前綴“:”、進程共享“:”、并發(fā)組合“|”等.在操作符的基礎(chǔ)上,FSP提供3種并發(fā)控制

17、機制:共享動作、互斥及條件同步.在生產(chǎn)者-消費者的定義中即包括共享動作和條件同步機制.在操作符和并發(fā)控制機制的基礎(chǔ)上可以做E-CSPE約束的推導(dǎo)7.例如,共享動作涉及安全性,可據(jù)以推導(dǎo)類和m類約束;互斥和條件同步涉及安全性和進展性,可推導(dǎo)出a類、m類和類約束.2 基于Java語言的測試系統(tǒng)JDPT2.1 JDPT的功能和特點基于上述考慮,我們實現(xiàn)了一個針對Java語言的測試系統(tǒng)JDPT.JDPT的主要功能如下:· 以圖視的形式展示被測程序的控制結(jié)構(gòu)和執(zhí)行分布情況;GraphicaFig.2 Test Procedure of Producer-Consumer Problem圖2 生

18、產(chǎn)者-消費者問題的測試過程Fig.2 Test Procedure of Producer-Consumer Problem圖2 生產(chǎn)者-消費者問題的測試過程l InterfaceSpecificationanalysisProgramInstrumentationTest caseselectionProgram executionEventscollectionProgramverificationFig.1 System structure of JDPT圖1 JDPT的系統(tǒng)結(jié)構(gòu)· 根據(jù)程序的形式化描述推導(dǎo)E-CSPE約束,并判斷約束集的一致性;· 與支撐系統(tǒng)協(xié)作,動

19、態(tài)監(jiān)控程序的分布運行;· 利用E-CSPE約束檢測收集到的可行事件序列;· 計算程序在分布運行環(huán)境中運行時的性能指標.JDPT系統(tǒng)有如下一些特點:· 以Java語言為基礎(chǔ);· 強調(diào)形式化驗證與運行監(jiān)控分析的結(jié)合;· 以事件序列的形式記錄程序在運行環(huán)境中的執(zhí)行過程;· 強調(diào)對程序中分布特性的測試.2.2 JDPT的構(gòu)成根據(jù)TFDS(test system framework for distributed software system)8框架,JDPT的系統(tǒng)結(jié)構(gòu)如圖1所示.其中,規(guī)約分析、程序裝備和選擇測試用例模塊屬于靜態(tài)部分;程序執(zhí)

20、行、事件收集和程序驗證屬于動態(tài)部分;圖視界面是系統(tǒng)與用戶的接口.(1) 規(guī)約分析.包括兩個方面.一方面是描述并分析被測程序的FSP表示,據(jù)以推導(dǎo)用于測試的E-CSPE約束.另一方面是分析被測程序的Java源碼,獲得程序的控制結(jié)構(gòu),主要是分布單元間的調(diào)用結(jié)構(gòu);并確定測試代碼的裝備位置.測試代碼的功能是生成和記錄運行事件,主要針對的是Java中的同步語句和通信設(shè)施.例如考慮Java的RMI(remote method invocation)設(shè)施:RMI調(diào)用需要分兩步,對應(yīng)兩段代碼結(jié)構(gòu).第一步是Bind,用于Client對象(如Producer或Consumer)定位提供方法調(diào)用的服務(wù)對象(如War

21、eHouse),并在本地創(chuàng)建服務(wù)對象的stub,代碼結(jié)構(gòu)如下:try wareHouse=(WareHouse) Naming.lookup(“/”+serverAddress+“/WareHouseServer”); /* other codes */ catch (Exception e) /* code related to except manipulation */這段代碼中可以生成3個事件: Bind開始; Bind成功; Bind異常.定位并創(chuàng)建本地stub以后,第2步是通過它進行RMI方法調(diào)用.RMI調(diào)用的代碼結(jié)構(gòu)如下:try wareHouse.put(parameters)

22、; catch (Exception e) /* code related to except manipulation */對應(yīng)的服務(wù)對象類(WareHouse)需要實現(xiàn)被調(diào)用的方法,代碼結(jié)構(gòu)如下:public class WareHouseImpl extends UnicastRemoteObjectserverClassimplements WareHouse public synchronized void put(parameters) /* implementation code */ return; 由WareHouseImpl實現(xiàn)的WareHouse是一個界面類,JavaRM

23、I需要用它來生成stub和skeleton代碼.在上述兩個代碼段中需要生成5個事件: 本地RMI調(diào)用;本地RMI成功返回; RMI異常; 服務(wù)端RMI接收; 服務(wù)端RMI結(jié)束.(2) 程序裝備.在程序結(jié)構(gòu)和規(guī)約分析的基礎(chǔ)上,在源程序中裝備測試代碼.測試代碼的主要目的是收集運行信息,并將這些信息記錄成事件.在JDPT中,事件被定義為六元組áT,S,D,M,I,Oñ.各項的含義分別是:· 類型(type):事件的類型.· 源對象(source):事件的發(fā)起者,由Java的對象名或線程標識表示.· 目標對象(destination):事件針對的目標對

24、象,由Java的對象名或線程標識表示.· 對象方法名(function):指示事件對應(yīng)的對象方法.· 時間戳(timestamp):事件的發(fā)生時間,用于對事件的排序以及性能分析.· 其他(other):與事件有關(guān)的其他信息,如產(chǎn)生事件的語句及變量值等.JDPT為每個對象增加一個public方法:CollectInfo,用于生成事件信息;同時定義監(jiān)控對象Monitor,其主要的方法是RecordInfo,用于存儲事件信息.裝備的代碼即由以下兩條語句構(gòu)成:Self.CollectInfo(); Monitor.RecordInfo().(3) 選擇測試用例.考慮到用戶

25、一般通過Client對象執(zhí)行分布式程序,JDPT依據(jù)Client對象的FSM表示選擇測試用例,基于的覆蓋準則是變遷覆蓋.當(dāng)存在多個Client對象時,取針對單個對象的測試用例集的并集.JDPT還根據(jù)E-CSPE約束選擇測試用例.用例的形式一般是事件序列,所達到的目標是使生成的事件序列覆蓋或違反某個E-CSPE約束,以滿足測試的充分性要求.(4) 程序執(zhí)行.有兩種執(zhí)行被測程序的方式:一種是不加干預(yù)的正常執(zhí)行,這種方式對應(yīng)于不確定性測試,同一測試用例需要執(zhí)行多次;另一種是在Monitor的監(jiān)控下干預(yù)程序的執(zhí)行,這種方式對應(yīng)于確定性測試,測試用例一般是事件序列.有兩種方法用于確定性測試:·

26、 在程序的關(guān)鍵位置(如RMI調(diào)用、synchronized語句、wait()-notify()函數(shù)等)插入交互式或延時語句,以控制程序運行時的競爭條件.· 設(shè)定相鄰兩個事件間的最大發(fā)生間隔,超過這一間隔即判定兩個事件不具備前后相鄰的關(guān)系.(5) 事件收集.Monitor對象負責(zé)記錄和匯總運行事件,當(dāng)程序規(guī)模較大時將有多個Monitor實例在運行,此時需要指定一個Monitor為Test Center負責(zé)匯總來自各Monitor的事件.事件匯總有兩種方式:一種是即時的,所有事件一旦記錄下來立即傳遞給Test Center,這可能會導(dǎo)致通信擁塞和瓶頸,干擾被測程序的運行;另一種是延遲的,

27、事件先由各Monitor記錄在本地的緩沖區(qū)或文件中,再按一定的周期或者應(yīng)Test Center的請求將本地事件序列提交給Test Center.由于通信延遲等原因,Test Center在匯總事件時需要為事件排序.可以采用時間戳定義邏輯時間為事件排序,通過這種方法,有因果關(guān)系的事件(如send和對應(yīng)的receive)可以得到準確的排序,但無此關(guān)系的事件其前后順序就可能是隨機的.另一種方案是使用絕對時間,它的好處是可以得到惟一排序,并為性能分析提供了依據(jù);缺點是各臺機器的本地時間難以保證完全同步.(6) 程序驗證.在JDPT中,程序驗證包含兩個方面,一個是檢測程序運行的正確性,另一個是分析程序在

28、運行環(huán)境中執(zhí)行的性能指標.檢測程序的正確性需要分兩個階段:一個是就運行事件本身檢查是否出現(xiàn)了異常事件并檢查事件間的匹配情況;二是根據(jù)E-CSPE約束判定事件序列的有效性.判定方法如下:(CSET為E-CSPE約束集,F為測試產(chǎn)生的事件序列集,s為一事件序列)· ,說明當(dāng)前產(chǎn)生的事件序列集沒有錯誤;· ,說明當(dāng)前產(chǎn)生的事件序列集針對CSET充分.分析程序的性能時主要是計算各種性能指標,如各分布單元的執(zhí)行時間、通信時間和等待時間.發(fā)現(xiàn)程序運行中的瓶頸,包括資源瓶頸、通信瓶頸等.(7) 圖視界面.圖視界面是用戶使用JDPT的接口.主要完成的功能包括:通過菜單界面調(diào)用其他模塊;提供

29、編輯界面,用于源程序編寫、程序形式化描述以及E-CSPE約束的定義等;以視圖的形式反饋程序的測試結(jié)果,包括規(guī)約分析產(chǎn)生的控制流圖以及程序驗證時的事件序列圖(trace圖)等.2.3 測試實例圖2顯示了應(yīng)用JDPT測試生產(chǎn)者-消費者問題的測試過程.如圖2所示,測試一個程序分為兩條線:一條是從程序?qū)崿F(xiàn)出發(fā),考慮結(jié)構(gòu)分析、測試代碼裝備以及運行監(jiān)控和事件收集;另一條是從程序形式化描述出發(fā),根據(jù)FSP表示推導(dǎo)E-CSPE約束,再以E-CSPE約束檢測事件序列集的有效性.通過這種方式,JDPT系統(tǒng)較好地實現(xiàn)了形式化驗證與運行監(jiān)控分析的有機結(jié)合.3 相關(guān)工作比較保證分布式程序的正確性可以從兩方面入手:一方面

30、是將分布式程序視為并發(fā)程序,偏重于并發(fā)程序的形式化驗證;另一方面是考慮程序?qū)崿F(xiàn),強調(diào)分布式程序運行過程的監(jiān)控、記錄和分析.形式化驗證主要是通過代數(shù)演算和邏輯推理證明程序并發(fā)過程的正確性,包括安全屬性和進展屬性,不考慮程序的具體實現(xiàn)和運行環(huán)境.以SPIN系統(tǒng)4為例,SPIN的目的是證明進程間交互(interaction)的正確性.其中進程被定義為一個自動機,它以順序、確定的方式運行.進程間交互有3種方式:會合元語(rendezvous primitives)、緩沖信道(buffered channel)通信和共享變量(shared variables)訪問.多進程異步交互(asynchronou

31、s interleaving product of automata)構(gòu)成系統(tǒng)行為,這個系統(tǒng)行為也被描述為自動機.SPIN包含兩種描述語言:用于描述程序規(guī)約要求的時序邏輯LTL(standard linear temporal logic)和描述設(shè)計選擇(design choices,即程序形式化描述)的語言PROMELA(process meta language).程序正確性驗證即要證明兩種描述在邏輯上的一致性.驗證時涉及3個基本實體:進程,包括有限個數(shù)的狀態(tài)和謂詞條件下的變遷;變量,有限個數(shù)的取值;緩沖信道,有限的緩沖容量.Fig.2 Test procedure of producer

32、-consumer problem圖2 生產(chǎn)者-消費者問題的測試過程Java source programclass Producer extends Executor private WareHouse wareHouse;private int no;private Thread prodThread;public Producer() StructureanalysisFinite state machineCollect eventsequencesEvent sequencesáLOCAL_RMI_CALL, ñ áREMOTE_RMI_RECV, &#

33、241;,áLOCAL_RMI_CALL, ñ áREMOTE_RMI_RECV, ñ,FSP descriptionWAREHOUSE = GSET0,GSETcontent: 0.N =(when(content<N) put | (when(content>0) get PRODUCER = (put®PRODUCER) Derive E-CSPEconstraintsE-CSPE constraintsa#;®áput, proi:P, nullñ(true)aáput, proi:P

34、, nullñ®áput, proi:P, nullñ(true)a#;®áput, pro?:W, nullñ(content<N)Verify theprogramResultsseq1 covers r1, seq1 covers r2,seq1 violates r3, seq2 covers r1, seq2 covers r2,seq2 covers r3, for consumer 1, total execute time is 21s, 運行監(jiān)控分析則將實現(xiàn)的分布式程序置于運行環(huán)境中執(zhí)行,記錄并控制其

35、運行過程,對記錄信息進行正確性和性能分析,然后把運行過程以圖視的形式顯示給用戶.以MAD(monitoring and debugging environment)系統(tǒng)為例,MAD的主要目的是探測程序中的錯誤.它把程序錯誤分成兩類:只影響一個進程的局部錯誤以及影響多個進程的全局錯誤.局部錯誤可以由串行程序測試工具檢測出來,MAD不予考慮.對于全局錯誤的檢測,由于滾雪球效應(yīng)(stampede effect),MAD強調(diào)競爭條件(race condition)的探察.涉及競爭條件的事件被稱為“race condition candidates”,這類事件的發(fā)生順序是不確定的.MAD包含3個基本工具

36、:EMU(event monitoring utility),功能是裝備測試代碼,在程序運行時收集和記錄運行事件并存入文件中;ATEMPT,功能是分析運行事件信息,檢查通信中的錯誤,計算性能指標包括通信時間、執(zhí)行時間和監(jiān)控耗時,顯示和操縱運行進程的trace圖;PARASIT,功能是以事件序列(重排“race condition candidates”的順序)為輸入確定性地執(zhí)行被測程序.只考慮形式化驗證不能保證程序?qū)崿F(xiàn)與運行環(huán)境的有效協(xié)作;只考慮運行監(jiān)控和分析又缺乏對程序行為的正確性約束.JDPT實現(xiàn)了兩者間的一個橋接:形式化驗證可以保證程序形式化描述的正確性,據(jù)之推導(dǎo)的E-CSPE約束又可反

37、映規(guī)約的要求,進而有效地檢測程序?qū)崿F(xiàn)行為與規(guī)約行為的一致性.4 結(jié)束語由于網(wǎng)絡(luò)的普及和分布應(yīng)用的拓展,用于檢測分布式程序正確性和性能的測試工具有著廣闊的應(yīng)用前景.目前針對分布式程序測試的研究尚處于初期階段.就JDPT系統(tǒng)而言,下一步的工作包括:· 如何根據(jù)程序?qū)崿F(xiàn)推導(dǎo)描述可行事件序列特性的E-CSPE約束,并對比從規(guī)約導(dǎo)出的E-CSPE約束,驗證程序?qū)崿F(xiàn)的正確性.· 如何重構(gòu)JDPT,使其支持其他類型的分布式編程語言并測試其他類型的分布式應(yīng)用.目前分布式支撐系統(tǒng)如CORBA等本身尚存在缺陷,需要增加對運行環(huán)境組成構(gòu)件的測試.致謝 感謝實現(xiàn)JDPT的諸位老師和同學(xué),感謝評審專

38、家的寶貴意見.References:1 Kranzlmüller D, Grabner S, Volkert J. Debugging with the MAD environment. Parallel Computing, 1997,23(1):199217.2 Gu Q, Chen DX, Xie L. PSET: A validation system for object-oriented distributed programming language named NC+. Journal of Software, 1997,8(6):352356 (in Chinese with English abstract).3 Hofman R, Langendoen K, Bal H. Vis