基於程序依賴圖的bpel過程一致性度量方法
2023-05-02 00:16:26
專利名稱：基於程序依賴圖的bpel過程一致性度量方法
技術領域：
本發明屬於服務計算領域，具體是一種度量兩個BPEL過程行為一致性程度的方法。
背景技術：
在面向服務架構(SOA)中，BPEL(業務過程執行語言)已經成為描述基於服務的商業過程的業界標準。隨著BPEL過程的不斷豐富和擴展，許多商業團體和公司建立了 BPEL過程庫。為了更好地對庫中的眾多BPEL過程進行檢索、維護、管理和重用，提出一種合適的標準來度量兩個BPEL過程的一致性程度變得越來越迫切。例如，當管理人員向BPEL過程庫中增添一種新的過程時，他們首先應該確定該庫中是否存在此BPEL過程，然後需要考慮哪些BPEL過程與這種新添加的過程相類似，具有多少的一致性程度。在這種情況下，研究不同的BPEL過程之間一致性就具有重要意義。由於BPEL過程中的活動包含很多信息，導致難以度量兩個BPEL過程之間的一致性程度，同時對於給出它們之間的一致性的定義也成為一個挑戰。一些學者將過程模型的一致性定義為「均勻度，標準化和無矛盾」。由於BPEL過程中的活動之間的行為關係是評判兩個BPEL過程是否一致的基礎，所以，定義BPEL過程一致性為「活動關係不變性和無矛盾」。不同的標準能用於制定BPEL過程一致性。比如，從接口的角度，定義基於接口匹配程度的一致性標準。然而，由於即使兩個BPEL過程共享同一接口集合，它們的行為也可能千差萬別，所以這個標準是不合適的。因而，提出從行為的角度來研究BPEL過程之間的
一致性。在過程模型領域中，一些學者利用線性時間分支時譜中的等價標準定義過程模型之間的行為一致性，其中互模擬(bisimulation)和跡等價(trace equivalence)是最常用的方法。而它們在度量過程模型一致性時只能給出「是/否」二元判斷，卻不能區分出模型之間具有多大的差別。還有一些學者利用圖形結構(thegraphical structure)的方法評判過程模型一致性。然而，從圖形結構上看起來非常相似的模型可能差別巨大，所以圖形結構可以作為評判過程模型一致性的一個指標。Alves de Medeiros等提出了典型行為(exemplary behavior)的方法比較過程模型一致性,典型行為能夠從實際模型執行的事件日誌中獲得。這種方法給出O到1.0的具體數值來量化過程模型之間一致性程度。這些方法都是一些形式化的方法，都未能描述過程模型中的本質行為關係。於是，Weidlich等提出行為側畫(behavioral profile)的方法度量過程模型的一致性。行為側畫的方法描述了過程模型中活動之間三種本質的行為約束。可以簡單地認為只要所有對應的活動對之間的行為約束是完全相同的，那麼這兩個過程模型就是一致的。這種方法受到兩個過程模型之間活動映射的影響很小，並且也能夠給出O到1.0的具體數值來量化一致性程度。所以，行為側畫的方法在度量過程模型一致性是非常合適的。由於在軟體工程領域相似性和一致性的概念是非常接近的，所以很多度量過程模型的相似性的方法也能用於度量過程模型一致性。在評判過程模型的相似性方面，有學者根據模型結構、模型語義判斷過程模型的相似性，還有一些學者從活動行為的角度過程模型的相似性問題，比如，基於活動間因果關係(causal footprint)的方法，首要變遷序列(principal transition sequences)的方法、行為側畫和Jaccard係數(Jaccard coefficient)的方法。然而,上述的這些方法都只是應用於過程模型層面，一些重要的信息(比如數據、夥伴連結等)都被抽象掉，因此，它們不適用於度量BPEL過程一致性。
發明內容
本發明的目的在於提供一種基於程序依賴圖的BPEL過程一致性度量方法，該方法實現了對BPEL過程庫中的過程進行檢索、管理、維護和重用的功能。實現本發明目的的技術解決方案為:一種基於程序依賴圖的BPEL過程一致性度量方法，以兩個BPEL過程為輸入，以這兩個BPEL過程的一致性程度為輸出結果；該方法使用的BPEL過程必須符合WS-BPEL2.0規範，並且過程中不包含〈link〉活動；步驟如下:(I)輸入兩個BPEL過程，根據BPEL的特性將兩個BPEL過程分別轉化為控制流程圖；(2)根據每個BPEL過程的控制流程圖，分析活動間的三種依賴關係，生成程序依賴圖PDG ；(3)通過對兩個BPEL過程的程序依賴圖的分析，計算出這兩個BPEL過程的一致性程度。本發明與現有技術相比，其顯著優點:本發明基於BPEL過程中活動之間的依賴和互斥關係，提出了一種定量的BPEL過程一致性度量方法，該方法可以對兩個BPEL過程的一致性給出一個從O到I的數值，而不是像傳統方法那樣僅提供一致和不一致的定性結論，從而有效區分不同程度的一致性。
圖1為基於程序依賴圖度量BPEL過程一致性的整個流程。圖2為基於程序依賴圖度量BPEL過程一致性程度的具體步驟流程圖。圖3為兩個BPEL過程實例的控制流程圖，圖(a)為輸入的第一個BPEL過程，圖(b)為輸入的第二個BPEL過程。圖4為本發明兩個實例依賴分析得到的程序依賴圖，圖(a)為第一個BPEL過程所生成的程序依賴圖，圖(b)為第二個BPEL過程所生成的程序依賴圖。圖5為本發明兩個實例的依賴關係矩陣。圖6為本發明計算兩個實例的一致性程度。
具體實施例方式本發明提出基於程序依賴圖度量兩個BPEL過程的行為一致性程度的方法。在BPEL程序依賴圖(BTOG)中，BPEL過程中活動間的關係分為互斥關係和依賴關係，而依賴關係包含控制依賴、數據依賴和異步調用依賴關係。當BPEL過程中存在、〈switch〉或〈pick〉選擇結構活動時，由於選擇結構活動中僅一條分支上的活動能夠被執行,這樣不同分支上的活動之間也存在著一種關係，這種關係被定義為互斥關係。控制依賴被定義為一個活動Xj控制依賴於另一個活動Xi若且唯若Xi決定Xj能否執行。數據依賴又分為真數據依賴，反數據依賴和輸出數據依賴。一個活動Xj真數據依賴於它之前的另一個活動Xi，若且唯若Xj使用了 Xi定義的某個變量；一個活動Xj反數據依賴於它之前的另一個活動Xi,若且唯若Xj定義了 Xi所使用的某個變量。一個活動Xj輸出數據依賴於它之前的另一個活動Xi，若且唯若Xj重新定義了 Xi定義的某個變量。實際上，反數據依賴和輸出數據依賴可通過變量重命名的方式予以避免。BPEL過程中的一個活動Xj異步調用依賴於它之前的一個活動Xi，若且唯若Xi是一個異步調用〈invoke〉活動,而Xj是用來接收相應返回結果的〈receive〉活動。其中，一個BPEL過程中的〈invoke〉活動可能與另一個BPEL過程中具有異步調用依賴關係的〈invoke〉和〈receive〉活動構成1: 2的對應關係。本發明就是對所提出的方法度量BPEL過程一致性的具體實現。要求輸入的BPEL過程滿足WS-BPEL2.0規範，尤其是是一些判定條件〈condition〉必須嚴格遵守所設定的形式，才能夠解析出條件中所包含的輸入輸出變量，並且這些過程中並發活動之間不存在。下面結合附圖對本發明做進一步說明。本發明基於程序依賴圖的BPEL過程一致性度量方法，其整體流程如圖1所示。首先，根據BPEL的特性將兩個BPEL過程分別轉化為控制流程圖；然後，根據每個BPEL過程的控制流程圖，分析活動間的三種依賴關係，生成程序依賴圖PDG ;最後，通過對兩個BPEL過程的程序依賴圖的分析，計算出這兩個BPEL過程的一致性程度。對於符合規範的BPEL過程，本發明能夠解析出其中所包含的所有信息，包括所有類型的活動以及活動的輸入輸出、夥伴連結、埠類型等。具體步驟如下(如圖2所示):1.對BPEL過程建模，主要是根據BPEL的特性將BPEL過程轉化為控制流程圖，具體可分為以下步驟:1.1按照深度優先的方式遍歷給定的BPEL過程，獲取所有的活動結點，並且給BPEL過程的根活動設定為域〈scope〉活動；1.2根據所獲取活動的類型，選擇與此活動類型相對應的解析函數分析BPEL過程中的每個活動結點的屬性，將所有活動所共有的活動屬性提取出來存入內存中，然後根據活動類型，另行存儲每種類型的活動所特有的屬性；解析函數根據活動類型可以化分為以下幾類:基本活動的解析函數從BPEL過程中讀取的基本活動的屬性，活動的屬性主要包含名稱、類型、前驅後繼關係、輸入輸出變量、夥伴連結和埠類型，在塊結構中，只有在順序〈sequence〉活動下的活動之間才存在前驅後繼關係，而塊結構是由結構化活動與其子活動組成，具有縱向的層次感；對於結構化活動、〈switch〉、〈pick〉、〈while〉和〈repeatUtil〉，它們的輸入變量只能從條件語句〈condition〉中獲取出來，但這些條件語句必須滿足bpel: getVariableProperty ('','')或者 bpws IgetVariableDataC 1 , 1 1 )這兩種形式才能夠被解析，而輸出變量在結構化活動都為空null ；選擇和循環結構活動的解析函數從BPEL過程中讀取此類型活動的屬性，其中輸入變量從條件〈condition〉中解析出來,並且,讀取對應條件〈conditon〉下的分支活動；
並髮結構和順序結構活動的解析函數從BPEL過程中讀取此類型活動的屬性，並且讀取其每條分支下的活動。根據每個BPEL過程的控制流程圖，分析活動間的三種依賴關係，生成程序依賴圖roG，其具體包括以下步驟:2.1遍歷每個BPEL過程的控制流程圖，將控制流程圖中除順序〈sequence〉、並發〈flow〉和域〈scope〉三種類型以外的基本活動和結構化活動存入活動結點集N中；2.2遍歷活動結點集N,如果存在結構化活動,將結構化活動與其所有子活動所構成的控制依賴關係添加到依賴關係集E ；2.3給所有無控制依賴的活動增加一個共同開始活動結點Entry,使這些活動都控制依賴於Entry結點，並將Entry結點和所有無控制依賴的活動之間的控制依賴關係添加到依賴關係集E中，Entry結點添加到活動結點集N中；2.4根據每個活動的前驅後繼關係和輸入輸出變量，找到所有活動間的數據依賴關係，並添加到依賴關係集E中；2.5判斷一個異步〈invoke〉活動是否與另一個〈receive〉活動的夥伴連結的名稱和埠類型的名稱相同，若相同，這兩個活動之間存在異步調用依賴關係，將此依賴關係添加到依賴關係集E中，其中異步〈invoke〉活動只有輸入變量，其執行採用非阻塞方式:BPEL服務在執行該異步〈invoke〉活動後可繼續執行其後續活動,該異步〈invoke〉活動的調用結果會由之後的一個〈receive〉活動負責接收；2.6根據活動結點集N和依賴關係集E，從而得到BPEL過程的程序依賴圖，並且以矩陣的形式將所有活動間的依賴關係展示出來，需要注意的是:在矩陣中活動前後的位置很重要，比如兩個活動Oi1, n2)之間存在控制依賴關係，但是活動(n2，H1)之間就不存在控制依賴關係。其中，步驟2.4的方法如下:遍歷活動結點集N，判定獲取的一個活動的輸入變量名稱與該活動的前驅活動的輸出變量名稱是否相同，如果相同，將此數據依賴關係添加到依賴關係集E中，然後獲取另一個活動，尋找該活動與它的前面的活動的數據依賴關係；如果獲取的一個活動的輸入變量名稱與該活動的前驅活動的輸出變量名稱不相同，首先需要判斷與該活動的前驅活動是否為結構化活動，如果不是結構化活動，根據活動的前驅後繼關係，獲取該活動的前驅活動的前驅活動，判定該活動與它前驅活動的前驅活動的輸出變量名稱是否相同；如果是結構化活動，遍歷結構化活動的子活動，判定其所有子活動的輸出變量名稱是否與該活動的輸入變量名稱相同，如果相同，將這些數據依賴關係都添加到依賴關係集E中，如果該活動與此結構化活動的所有子活動沒有數據依賴關係，則重複上述的判定，直到找到該活動的數據依賴關係或最頂層活動為止；判斷活動自身的輸入變量名稱是否等於輸出輸出變量名稱，如果相等，將此數據依賴關係添加到依賴關係集E中；如果BPEL過程中存在〈while〉或〈repeatUntil〉循環活動,判定此類活動的輸入變量名稱是否與該活動的子活動的輸出變量名稱相同，如果相同，將此數據依賴關係添加到依賴關係集E中；還需要判定此類活動的子活動之間是否存在反數據依賴關係，如果存在，將此數據依賴關係也添加到依賴關係集E中。
分析得到這兩個BPEL過程之間不一致的對應活動對，然後基於不一致的此對應活動對的數目計算出兩個BPEL過程的一致性程度；其具體包括以下步驟:3.1根據兩個BPEL過程的程序依賴圖的活動結點集NI和N2，建立對應的活動結點集Nal和Na2，其中對應關係是指兩個活動結點集中的活動相互映射，事實上，一個BPEL過程中異步調用依賴的〈invoke〉和〈receive〉活動可能與另一個BPEL過程中的〈invoke〉活動構成2: I的映射關係；3.2如果程序依賴圖中包含選擇結構活動、〈switch〉或〈pick〉,建立選擇結構活動的不同分支上的活動之間互斥關係集R1和R2 ；3.3遍歷兩個BPEL過程的所有的活動對，判定對應活動對之間的互斥關係和依賴關係是否相同，只要有一種關係不相同，則認為這兩個活動對是不一致的，並將其分別添加到不一致的活動對集Q1和Q2,而活動對由活動節點集中任意的兩個活動組成的一對活動以及一個活動與自身組成的一對活動；3.4根據兩個BPEL過程的活動結點集Nal和Na2的中活動結點數目a和b，以及不一致的對應活動對集Q1和Q2中的活動對數目c和d，採用公式I計算出這兩個BPEL過程的一致性程度P。
權利要求
1.一種基於程序依賴圖的BPEL過程一致性度量方法，其特徵在於:以兩個BPEL過程為輸入，以這兩個BPEL過程的一致性程度為輸出結果；該方法使用的BPEL過程必須符合WS-BPEL2.0規範，並且過程中不包含〈link〉活動；步驟如下: (1)輸入兩個BPEL過程，根據BPEL的特性將兩個BPEL過程分別轉化為控制流程圖； (2)根據每個BPEL過程的控制流程圖，分析活動間的三種依賴關係，生成程序依賴圖PDG ； (3)通過對兩個BPEL過程的程序依賴圖的分析，計算出這兩個BPEL過程的一致性程度。
2.根據權利要求1所述的基於程序依賴圖的BPEL過程一致性度量方法，其特徵在於，步驟(I)具體步驟如下: 1.1按照深度優先的方式遍歷給定的BPEL過程，獲取所有的活動結點，並且給BPEL過程的根活動設定為域〈scope〉活動； 1.2根據所獲取活動的類型，選擇與此活動類型相對應的解析函數分析BPEL過程中的每個活動結點的屬性，將所有活動所共有的活動屬性提取出來存入內存中，然後根據活動類型，另行存儲每種類型的活動所特有的屬性； 解析函數根據活動類型化分為以下幾類: 基本活動的解析函數從BPEL過程中讀取基本活動的屬性，活動的屬性包含名稱、類型、前驅後繼關係、輸入輸出變量、夥伴連結和埠類型，在塊結構中，只有在順序〈sequence〉活動下的活動之間才存在如驅後繼關係； 選擇和循環結構活動的解析函數從BPEL過程中讀取此類型活動的屬性，其中輸入變量從條件〈condition〉中解析出來,並且讀取對應條件〈conditon〉下的分支活動； 並髮結構和順序結構活動的解析函數從BPEL過程中讀取此類型活動的屬性，並且讀取其每條分支下的活動。
3.根據權利要求1所述的基於程序依賴圖的BPEL過程一致性度量方法，其特徵在於，步驟(2)具體步驟如下: . 2.1遍歷每個BPEL過程的控制流程圖，將控制流程圖中除順序〈sequence〉、並發〈flow〉和域〈scope〉三種類型以外的基本活動和結構化活動存入活動結點集N中； .2.2遍歷活動結點集N,如果存在結構化活動,將結構化活動與其所有子活動所構成的控制依賴關係添加到依賴關係集E中； .2.3給所有無控制依賴的活動增加一個共同開始活動結點Entry,使這些活動都控制依賴於Entry結點，並將Entry結點和所有無控制依賴的活動之間的控制依賴關係添加到依賴關係集E中，Entry結點添加到活動結點集N中； .2.4根據每個活動的前驅後繼關係和輸入輸出變量，找到所有活動間的數據依賴關係，並添加到依賴關係集E中； .2.5判斷一個異步〈invoke〉活動是否與另一個〈receive〉活動的夥伴連結的名稱和埠類型的名稱相同，若相同，這兩個活動之間存在異步調用依賴關係，將此依賴關係添加到依賴關係集E中； .2.6根據活動結點集N和依賴關係集E，得到BPEL過程的程序依賴圖，並且以矩陣的形式將所有活動間的依賴關係展示出來。
4.根據權利要求1所述的基於程序依賴圖的BPEL過程一致性度量方法，其特徵在於:步驟2.3的方法如下: 遍歷活動結點集N，判定獲取的一個活動的輸入變量名稱與該活動前驅活動的輸出變量名稱是否相同，如果相同，將此數據依賴關係添加到依賴關係集E中，然後獲取下一個活動，尋找該活動與它前面的活動的數據依賴關係；如果獲取的一個活動的輸入變量名稱與該活動的前驅活動的輸出變量名稱不相同，首先判斷與該活動的前驅活動是否為結構化活動，如果不是結構化活動，根據活動的前驅後繼關係，獲取該活動的前驅活動的前驅活動，判定該活動與它前驅活動的前驅活動的輸出變量名稱是否相同；如果是結構化活動，遍歷結構化活動的子活動，判定其所有子活動的輸出變量名稱是否與該活動的輸入變量名稱相同，如果相同，將這些數據依賴關係都添加到依賴關係集E中，如果該活動與此結構化活動的所有子活動沒有數據依賴關係，則重複上述的判定，直到找到該活動的數據依賴關係或最頂層活動為止； 判斷活動自身的輸入變量名稱是否等於輸出輸出變量名稱，如果相等，將此數據依賴關係添加到依賴關係集E中； 如果BPEL過程中存在〈while〉或<r印eatUntil〉循環活動，判定此類活動的輸入變量名稱是否與該活動的子活動的輸出變量名稱相同，如果相同，將此數據依賴關係添加到依賴關係集E中；還需要判定此類活動的子活動之間是否存在反數據依賴關係，如果存在，將此數據依賴關係也添加到依賴關係集E中。
5.根據權利要 求1所述的基於程序依賴圖的BPEL過程一致性度量方法，其特徵在於，步驟(3)的方法如下: .3.1根據兩個BPEL過程的程序依賴圖的活動結點集N1和N2,建立對應的活動結點集Nai和Na2，其中對應關係是指兩個活動結點集中的活動相互映射； .3.2如果程序依賴圖中包含選擇結構活動、〈switch〉或〈pick〉,建立選擇結構活動的不同分支上的活動之間互斥關係集R1和R2 ; .3.3遍歷兩個BPEL過程的所有的活動對，判定對應活動對之間的互斥關係和依賴關係是否相同，只要有一種關係不相同，則認為這兩個活動對是不一致的，並將其分別添加到不一致的活動對集Q1和Q2: .3.4根據兩個BPEL過程的活動結點集Nal和Na2的中活動結點數目a和b，以及不一致的對應活動對集Q1和Q2中的活動對數目c和d，採用公式I計算出這兩個BPEL過程的一致性程度P。
全文摘要
本發明公開了一種基於程序依賴圖的BPEL過程一致性度量方法。以兩個BPEL過程為輸入，以這兩個BPEL過程的一致性程度為輸出結果；該方法使用的BPEL過程必須嚴格符合WS-BPEL2.0規範，並且過程中不包含活動；根據BPEL的特性將兩個BPEL過程分別轉化為控制流程圖；根據每個BPEL過程的控制流程圖，分析活動間的三種依賴關係，生成程序依賴圖PDG；基於兩個BPEL過程的程序依賴圖，計算出這兩個BPEL過程的一致性程度。本發明提出的方法，可以對兩個BPEL過程的一致性給出一個從0到1的數值，而不是像傳統方法那樣僅僅提供一致和不一致的定性結論，從而有效區分不同程度的BPEL過程一致性。
文檔編號G06Q10/06GK103150626SQ20131006455
公開日2013年6月12日 申請日期2013年3月1日 優先權日2013年3月1日
發明者宋巍, 張學偉, 邢建春, 楊啟亮, 張文嘉 申請人:南京理工大學