過程模型中控制流反模式的定義和檢測方法

韓兆剛，鞏 朋，張 莉，呂方興

(1.北京航空航天大學軟件工程研究所，北京100191;2.菏澤學院計算機與信息工程系，山東荷澤274015)

過程模型［1］中的反模式是指“導致過程模型錯誤的典型設計缺陷”［2］，它是評估過程模型正確性的有效手段。過程模型反模式以控制流反模式(控制結構方面的反模式)最為常見［2］。文獻［3］對過程模型進行化簡并根據化簡結果判斷過程模型中是否存在死鎖或乏同步，但該方法無法定位反模式。文獻［4］使用編譯技術中的控制流塊分析技術［5］分析過程模型并利用啟發式方法檢測并定位控制流反模式，但該方法只支持一些既定的控制流反模式，擴展性不足。文獻［6］利用 BPMN-Q［7］定義并查詢BPMN模型中的常見控制流反模式，該方法允許用戶自定義反模式，但它的效率較低，而且不支持BPMN以外的建模語言。為了提高過程模型的控制流反模式檢測的實用性和靈活性，筆者提出一種過程模型中控制流反模式的定義和檢測方法。

1 過程模型預處理

為了支持不同的過程建模語言，提取過程模型的控制流結構，并將其轉化為過程建模語言無關的工作流圖［3］。為了方便，使用 BPMN［8］的建模符號來表示工作流圖中的元素(圖1)，并在下文中使用ANDSplit、ANDJoin、XORSplit和 XORJoin 來表示工作流圖中的并行分支、同步合并、排他選擇和簡單合并。

圖1 工作流圖中的基本元素Fig.1 Basic notations in workflow graph

使用文獻［2］提出的過程結構樹來分析過程模型的控制流結構。過程結構樹由工作流圖中的規則單入口單出口過程塊和節點構成。通過環路等價算法［4］對工作流圖進行處理，可以在線性時間得到工作流圖中的規則單入口單出口過程塊(除非特殊說明，過程塊均為規則單入口單出口過程塊)。稱該處理過程為工作流圖歸約。

圖2給出了一個示例工作流圖，過程從起始節點start出發到達g1，然后并行地執行g1的兩個后繼分支。其中一個分支串行地執行a1、a2和a3這幾個活動，另外一個分支則執行由g2、a4和g3構成的循環。接下來這兩個分支在g4進行匯合，最后過程到達終止節點end，該過程結束。值得注意的是，由于使用并行分支作為循環出口，過程塊C中的g2和g3構成了無窮循環。圖中的虛線框表示對工作流圖實施規約后得到的不同過程塊。

圖2 示例工作流圖及其歸約結果Fig.2 Sample workflow graph and its reduction result

對于給定過程塊F，稱F的母過程塊為包含F的最小過程塊F'，并稱F為F'的子過程塊。把過程塊的子過程塊替換為一個活動節點不會影響該過程塊的正確性［6］。以圖2為例，過程塊A是過程塊B、C的母過程塊，而過程塊B、C均為A的子過程塊。處理過程塊A時，可以把過程塊B、C作為一個活動節點來處理，而無需考慮其內部結構，這可以顯著地提升處理速度。

文獻［4］證明了規則單入口單出口過程塊之間只存在嵌套和不相交這兩種關系，因此工作流圖中的過程塊可以構成一個樹形結構，這個樹形結構就是過程結構樹［9］。圖3給出了圖2所對應的過程結構樹。

圖3 示例工作流圖對應的過程結構樹Fig.3 Corresponding process structure tree of sample workflow graph

過程結構樹中的葉子節點對應于工作流圖的節點，非葉子節點對應于與工作流圖中的過程塊。以圖2的工作流圖和圖3的過程結構樹之間的關系為例，圖3中的根節點A對應圖2中的過程塊A，圖3中的葉子節點g1和g4對應于圖2中的節點g1和g4。工作流圖中的控制流信息則保存在過程結構樹的葉子節點中。

由于過程結構樹中的節點和工作流圖中的元素之間存在這種映射，并且工作流圖總可以轉換為與之對應的過程結構樹［10］，因此可以通過分析過程結構樹來分析過程模型的控制流結構。

2 反模式描述語言CAPDL

為了描述控制流反模式，設計了控制流反模式描述語言CAPDL。

2.1 CAPDL的設計思路

控制流反模式是一類導致過程模型異常的特殊控制流結構，描述控制流反模式也就是描述其對應的控制流結構。由于控制流結構由活動、分支、合并等模型元素構成，因此可以利用模型元素的屬性來描述過程模型中的控制流結構。過程模型中的控制流結構可以分為兩類:簡單控制流結構和復合控制流結構。簡單控制流結構對應于節點;復合控制流結構對應于過程塊。對于簡單控制流結構，利用模型節點的屬性就可以對其進行描述;對于復合控制流結構，則需要利用過程塊內部的節點信息對其進行描述?；谶@個思路，本文設計了控制流反模式描述語言CAPDL。

2.2 CAPDL的核心概念和元模型

CAPDL的基本概念是謂詞，根據謂詞的目標類型，謂詞可以分為屬性謂詞和節點謂詞:屬性謂詞應用于節點上的屬性;節點謂詞應用于過程塊中的節點。表1給出了一些謂詞的使用示例。

表1 CAPDL的謂詞示例Table 1 Examples of predicates in CAPDL

比謂詞高一級的概念是規則，規則由一系列謂詞組成。規則根據其目標類型可以分為節點規則和塊規則:節點規則由若干屬性謂詞組成，用于描述過程模型中的模型節點;塊規則由若干節點謂詞組成，用于描述過程模型中的過程塊。規則的使用示例見表2。

?

比規則高一級的概念是反模式。由于過程模型中的控制流反模式可能具有多種實現形式［11］，因此一個反模式由一個到多個規則組成。對于指定的反模式，只要過程塊或模型節點滿足該反模式規則集合中的一條規則，就稱該過程塊或模型節點滿足該反模式。

為了復用已有的反模式定義和規則定義，CAPDL中引入了模塊的概念。模塊可以包含一個到多個規則或反模式;模塊可以通過導入其他模塊來引用已定義的規則或反模式。以“錯誤循環”反模式為例，它由InfiniteLoop規則和DeadLoop規則組成，并引用了BasicPatterns模塊中的節點規則來定義自己的謂詞。具體如下:

import BasicPatterns\引用BasicPatterns模塊

antipattern Badloop:\定義Badloop反模式

rule InfiniteLoop on block:\定義InfiniteLoop規則

start with BasicPatterns.XORJoin\引用 BasicPatterns模塊中的節點規則

end with BasicPatterns.ANDSplit

rule DeadLoop on block:\定義DeadLoop規則

start with BasicPatterns.ANDJoin

end with BasicPatterns.XORSplit

通過謂詞、規則、反模式、模塊等概念，CAPDL提供了一種簡潔的控制流反模式定義方法。圖4給出了CAPDL的元模型。

圖4 CAPDL元模型Fig.4 CAPDL meta-model

3 控制流反模式查詢算法

利用預處理過程中得到的過程結構樹，以及控制流反模式的CAPDL定義，可以在過程結構樹上查詢滿足目標反模式的過程模型節點和過程塊。

3.1 查詢算法

基于CAPDL的控制流反模式查詢算法步驟如下:

(1)讀取工作流圖對應的過程結構樹PST，并初始化PST上每個葉子節點的謂詞集合。

(2)分析待查詢反模式的CAPDL定義，對其中節點規則NodeRule中的屬性謂詞和塊規則Block-Rule中的塊謂詞進行等價謂詞合并，并將去重后的謂詞保存在屬性謂詞集合和塊謂詞集合中。

(3)遍歷 PST上的葉子節點 LeafNode，記錄LeafNode所滿足的屬性謂詞并將其添加至節點的謂詞集合，并根據該節點滿足的謂詞判斷其所屬的NodeRule。

(4)遍歷 PST的非葉子節點 Non-LeafNode，并根據該節點滿足的塊謂詞判斷其所屬的BlockRule。

(5)根據PST節點所屬的 NodeRule或Block-Rule判斷其所屬的控制流反模式，并記錄其信息。

3.2 反模式查找過程

當使用二叉鏈表作為存儲結構時，過程結構樹的后序遍歷可借用二叉樹的先序遍歷和中序遍歷的算法實現，由于二叉樹的遍歷算法的時間復雜度與節點數存在線性關系，因此過程結構樹上的反模式檢測算法的時間復雜度也與節點數存在線性關系。

以檢測圖2的示例工作流圖中的錯誤循環為例，介紹基于CAPDL的控制流反模式查詢過程。圖2的工作流圖可以使用圖3中的過程結構樹表示。

(1)首先讀取圖3中的過程結構樹，并初始化過程結構樹中每個葉子節點的謂詞集合。以葉子節點a1、a2、a3、a4為例，它們的謂詞集合均被初始化為:inputedgescount=1;outputedgescount=1。

(2)為了提高查詢效率，本文對CAPDL代碼中重復的謂詞/規則進行了合并處理，從而保證同樣的謂詞/規則不會查詢多次。以“錯誤循環”反模式的CAPDL定義為例，謂詞inputedgescount=1在規則Sequential和規則ANDSplit均有出現(這些規則定義在模塊BasicPatterns中)。

(3)通過遍歷過程結構樹上的葉子節點，判斷其滿足的屬性謂詞，可以得到它們所滿足的節點規則。以圖3中的葉子節點g2為例，由于謂詞type=XOR、inputedgescount＞1和 outputedgescount=1在g2上均為真，因此g2滿足規則XORJoin。同理a1、a2、a3、a4 滿足規則 Sequential，g3 滿足規則 ANDSplit。節點規則的結果見圖5，圖中所有葉子節點滿足的節點規則均由節點規則查詢得到。

(4)通過遍歷過程結構樹上的非葉子節點，并利用其子節點滿足的節點規則來判斷其滿足的節點謂詞，可以得到它們滿足的塊規則。以過程塊C為例，由于C的起始節點g2滿足規則XORJoin，終止節點g3滿足規則ANDSplit，因此C滿足規則InfiniteLoop。塊查詢的結果見圖5，圖中過程塊C滿足規則InfiniteLoop這一結果由塊規則查詢得到。

(5)根據過程結構樹中節點的節點規則和塊規則，得到過程模型的控制流反模式信息:由于滿足“InfiniteLoop”規則，工作流圖中的過程塊C構成了一個錯誤循環。

圖5 節點規則和塊規則查詢結果Fig.5 Querying results of node rules ＆ block rules

4 試驗結果分析

為了驗證本文方法的有效性，對215個實際過程模型進行控制流反模式檢測試驗，試驗以文獻［2］提出的4種常見控制流反模式為檢測目標。這4種反模式分別是:異或分支(XORSplit)和同步合并(ANDJoin)的組合(會產生死鎖錯誤)、并行分支(ANDSplit)和簡單合并(XORJoin)的組合(會產生乏同步錯誤)、同步合并(ANDJoin)作為循環入口(會產生死鎖錯誤)和并行分支(ANDSplit)作為循環出口(會產生無窮循環錯誤)。這些控制流反模式的詳細信息參見文獻［2］。使用CAPDL定義了這些反模式，并基于這些反模式的CAPDL定義，對ILog建模工具(http://www-01.ibm.com/software/integration/visualization/java/)繪制的215個 BPMN過程模型進行了控制流反模式檢測。圖6給出了這些模型的規模信息。

圖6 模型的規模信息Fig.6 Model scale information

檢測程序運行在一臺裝有4G內存和2.93 GHz的雙核Intel處理器的臺式機上，檢測環境為Windows 7 SP1。檢測過程分為預處理過程和反模式檢測過程。圖7給出了檢測過程所耗時間和模型節點數的關系，其中反模式檢測時間和模型節點數呈預期的線性關系;預處理時間與模型節點數也呈現線性關系，這印證了文獻［4］中的論斷:通過環路等價算法對工作流圖進行處理，可以在線性時間得到與之對應的過程結構樹。

圖7 檢測時間和模型節點數的對應關系Fig.7 Relationship between detection time and model edge number

與文獻［6］提出的利用BPMN-Q檢測控制流反模式的方法相比，本文的檢測方法具有較快的速度。對相近規模的過程模型檢測同樣的控制流反模式，本文的平均檢測時間為0.33 s，文獻［6］的平均檢測時間為1.9～2.1 s。表3給出了具體的比較數據(本文的方法會對四種控制流反模式進行同時檢測，這里計入的是檢測總時間，所以檢測時間相同)。

表3 兩種反模式檢測方法的平均查詢時間比較Table 3 Average querying time comparison of two anti-pattern detection approaches

文獻［6］中的模式查詢方法受系統架構限制，每查詢一個控制流模式就需要遍歷一次過程模型，因此在查詢多個控制流模式時需要遍歷過程模型多次，從而造成相當的性能損耗。本文方法通過對過程模型進行預處理，將過程模型轉化為過程結構樹，并對控制流反模式的CPDL描述進行等價謂詞合并以減少不必要的查詢判斷。從而在查詢多個控制流反模式時只需一次預處理和四次過程結構樹遍歷，從而顯著提升了控制流模式查找的效率。

文獻［6］采用圖匹配的方式進行控制流模式查詢。每一次查詢均需要遍歷整個過程模型;本文利用文獻［9］的過程結構樹，把對指定模式的查詢限制在過程模型的子過程塊中，從而減少了查詢時間。

筆者選取了215個過程模型中的100個模型進行人工檢測，然后與檢測結果進行比較。結果見表4?？梢钥闯?，出現最多的控制流反模式是XORSplit和ANDJoin的組合(15次)，其次是 XORJoin和ANDSplit的組合和ANDJoin作為循環入口(各出現6次)，同文獻［6］中的過程模型中常見控制流反模式統計結果相一致。

表4 反模式檢測結果Table 4 Anti-pattern detection results

從表4可以看出，檢測過程中存在少數誤判現象。一般來講，只有基于狀態空間搜索的正確性驗證方法才能完全避免錯判和漏判。

5 結束語

為了提高過程模型中控制流反模式檢測的實用性和靈活性，本文提出一種過程模型中控制流反模式的定義和檢測方法。與已有方法相比，該方法既支持不同的過程建模語言，又可以有效地檢測過程模型中用戶自定義的控制流反模式。同時極大地提高了反模式檢測的檢測效率。

［1］ SMITH H，FINGAR P.Business Process Management:The Third Wave［M/OL］.Meghan-Kiffer Press，2003.http://www.bpmi.org/downloads/LIB-2002-08-2.pdf.

［2］ KOEHLER J，VANHATALO J.Process anti-patterns:how to avoid the common traps of business process modeling［J］.IBM WebSphere Developer Technical Journal，2007，10(2):4.

［3］ SADIQ W，ORLOWSKA M E.Analyzing process models using graph reduction techniques［J］.Information Systems，2000，25(2):117-134.

［4］ VANHATALO J，VOLZER H，LEYMANN F.Faster and more focused control-flow analysis for business process models through sese decom-position［M/OL］.Service-O-riented computing-ICSOC 2007， Vienna， Austria.Springer Berlin Heidelberg，2007:43-55.http://link.springer.com/chapter/10.1007/978-3-540-74974-5_4.

［5］ AHO A V，LAM M S，SETHI R，et al.Compilers:principles，techniques，and tools［M/OL］.Pearson/Addison Wesley，2007.http://www.lavoisier.fr/livre/notice.asp?ouvrage=1184227.

［6］ GRUHN V，LAUE R.A heuristic method for detecting problems in business process models［J］.Business Process Management Journal，2010，16(5):806-821.

［7］ AWAD A.BPMN-Q:a language to query business processes［C/OL］//Proceedings of EMISA 2007，Nanjing China.2007:115-128.http://dbis.eprints.uniulm.de/205/1/EMISA-Proceedings-Komplett.pdf#page=117.

［8］ Business Process Modeling Notation(BPMN)Version 2.0［S］.Object Management Group(OMG)，Jun 2010.http://www.omg.org/spec/BPMN/2.0/PDF/.

［9］ VANHATALO J，VOLZER H，KOEHLER J.The refined process structure tree［J］.Data ＆ Knowledge Engineering，2009，68(9):793-818.

［10］ POLYVYANYY A，VANHATALO J，VOLZER H.Simplified computation and generalization of the refined process structure tree［M］//Web Services and Formal Methods.2010，Hoboken，NJ，USA:Springer Berlin Heidelberg，2011:25-41.

［11］ WHITE S A.Process modeling notations and workflow patterns［J］.Workflow Handbook，2004:265-294.

［12］ VAN DER AALST W M P，TER HOFSTEDE A H M.YAWL:yet another workflow language［J］.Information Systems，2005，30(4):245-275.