＊WS-RI增量模式回溯的邊界收縮加速

翟治年，盧亞輝，周武杰，3，彭艷斌，鄭志軍，俞 堅，豐明坤

1.浙江科技學院 信息與電子工程學院，杭州310023

2.深圳大學 計算機與軟件學院，廣東 深圳518060

3.浙江大學 信息與電子工程學院，杭州310027

1 引言

正隨著云制造[1]等眾包業務模式的發展，更多工作流開始依賴于第三方資源。此類資源通過云平臺，以虛擬服務形式接入[2]，容易隱匿惡意，威脅業務安全。為防止惡意資源提供者獲取關鍵數據，須對有關步驟施加授權約束。但其可能破壞資源分配可行性。相應的驗證與決策，稱為工作流可滿足決策（Workflow Satisfiability Decision，*WS）[3]。*WS 屬于NP 難問題[4]，僅在少數約束配置[3]或特定約束圖規范[5]下多項式時間可解。通常的搜索會因“組合爆炸”產生性能瓶頸。而蟻群等智能算法難以保證完備性，不利于無解判定[6]。一個可能的優化方向是打破對稱（Symmetry Breaking）[7]。即分析約束集中的對稱因素，避免重復搜索對稱不可行解，從而降低驗證開銷。

2014年，Cohen等識別了多種安全約束的資源獨立（Resource Independent）性質[8]。相應約束下的*WS 記為*WS-RI。定義了*WS-RI 的合格（滿足所有約束）資源分配模式。相同模式的資源分配合格性等價。為利用這種對稱性，建立了借助模式壓縮緩存的動態規劃算法。其時間復雜度為O*(3||Vwlbw)，式中V是步驟集，w是資源分散度。但其空間復雜度仍為指數級，制約了實際性能表現。2016年，通過約束傳播、消除無用資源和預處理，使模式動態規劃獲得了優化的時間性能[9]。2015 年，Karapetyan 等將模式引入回溯搜索，建立了*WS-RI的模式回溯法[10]。其出發點是在與步驟授權集無關的模式空間上搜索真實、合格資源分配。為此，解決了模式真實性（即該模式是否可能滿足授權）的驗證問題，方法是計算模式中步驟塊到資源集的指派（二分）圖，然后求其單向完備匹配。而模式合格性可以根據文獻[8]的結論來驗證。模式回溯具有多項式空間復雜度，而時間復雜度為O*(B|V|)，其中B|V|為第 |V|個Bell數。起初，僅對葉模式進行充要的真實性驗證，而對其祖先僅做必要的快速驗證[10]。2018年，翟治年等表明對每個模式進行充要的真實性驗證，可以平衡剪枝能力與驗證代價，增強宏觀性能表現[11]。不過，在驗證模式真實性時，文獻[11]沿用了文獻[10]的做法，從頭計算完全指派圖并求其匹配。設D表示資源集，一次真實性驗證耗時O(|V|2|D|)。但其可能在每一個搜索結點處發生，且 |D|可比 |V|大得多[12-13]，故其3 次多項式的代價仍然偏高。2019 年，Karapetyan 等利用父子模式的差異，給出了增量化的真實性驗證方法。一次驗證耗時O(|V|2+|V||D|)[14]，降至二次多項式。由此建立了增量模式回溯（Incremental Pattern Backtracking，IPB）的方法。實驗表明，相對于包括文獻[9]在內的各種代表性方法，IPB 具有突出的性能優勢，是目前求解*WS-RI最高效的方法。

模式技術引起了理論和應用上的進一步探索，例如文獻[15]在強指數時間假設下，證明模式動態規劃時間復雜度的最優性，文獻[16]將模式回溯法進行推廣，應用于層次化類獨立約束*WS的求解等。

本文將對IPB 的真實性驗證過程進行改進。針對其計算差異塊鄰域時，在整個資源集中展開搜索的缺陷，給出了一種邊界收縮的加速方法。實驗表明，改進方法在時間性能上獲得了較明顯的提升，且在資源集和步驟集規模較大時更有優勢。

2 預備知識

*WS-RI是一個三元組＜V,d,C ＞。其中V是步驟集，d:V→2D是步驟授權集，D是資源集。C是約束集，每個c∈C有作用域Vc?V，值域Dc?。且|Vc|＞1 ，稱為c的元數。對任意資源分配π:V'→D(V'?V)，若任取v∈V'，π(v)∈d(v)，稱π是授權的。任取約束c∈C，若在Vc上的限制π↑Vc∈Dc，稱π滿足c。任何c∈C都具有資源獨立性，即若π滿足c，則對任意的θ:D→D,θ(π)也滿足c。稱滿足所有c∈C的π合格，授權、合格的π有效，完整（即V'=V）、有效的π可行。*WS-RI 求任意一個可行資源分配，或判定其不存在。

V'模式是V'的劃分(V'?V)。給定＜V,d,C ＞，相應*WS-RI 的任何資源分配π:V'→D都會產生一個V'模式Pπ={π-1(u)|u∈π(V')}，稱其為π的模式。任何V'模式P都會產生一個資源分配集ΠP={π:V'→D|Pπ=P}。若任取π∈ΠP都合格，稱P合格。若存在授權的π∈ΠP，稱P真實。稱真實、合格的模式有效、完整（即V'=V）、有效的模式可行。模式空間描述了向空劃分逐漸加入步驟，擴展為更大劃分的過程。每個新步驟要么放入一個已有劃分塊，要么形成一個新塊。用同一步驟擴展不同劃分，得不到同一劃分，故模式空間呈樹結構。

模式回溯法對模式空間進行深度優先搜索，通過合格與真實性驗證加以剪枝，找到可行模式后，將其轉換為可行資源分配。模式合格性通常根據約束語義來驗證。而模式P的真實性驗證分兩階段：計算其指派圖BP，再求其單向（從左到右）完備匹配。BP的左側頂集為P，右側頂集為D。任取塊b∈P和資源u∈D，(b,u)∈E(BP)當且僅當對任何v∈b均有u∈d(v)。將模式中每個塊匹配的資源分配給塊中所有變量，即可得到一個符合該模式的授權資源分配。

文獻[14]的IPB 改進了真實性驗證過程。對BP左側的每個頂點，只計算 |V|個鄰點（不足 |V|時完全計算）。當回溯搜索驗證模式P的真實性時，其父模式sup(P)已通過驗證，求得指派圖Bsup(P)及其單向完備匹配Msup(P)。而P 相對其父的差異塊bP-sup(P)是唯一的。計算該塊的鄰域，并沿用其他塊的鄰域，即可由Bsup(P)得到BP。在求BP的單向完備匹配時，以其他塊在Msup(P)中的匹配邊集為初始匹配，求一條源自bP-sup(P)的增廣路即可。

3 基于邊界收縮的塊指派算法

圖IPB 在搜索過程中頻繁進行模式真實性驗證。每次都需要計算模式的指派圖。其計算效率對算法的整體性能影響很大。對每個模式P，IPB僅計算差異塊bP-sup(P)的指派鄰域。然而，它是從整個資源集D中尋找bP-sup(P)的鄰點。對每個u∈D，為驗證是否對任何v∈bP-sup(P)均有u∈d(v) ，需要O(|bP-sup(P)|)=O(|V|) 時間。在很大的D中找一個鄰點，驗證開銷也很大。由于每個步驟v∈bP-sup(P)的授權集d(v)都是分散落入整個D的，尋找一個位于所有d(v)中的資源，可以在D中跳躍進行，減少對無效資源的驗證。為此，給出一種基于邊界收縮的塊指派（Block Assigning via Boundary Shrinking，BABS）算法，其偽代碼描述如下（next(d(vi),l)表示d(vi)中大于l的第一個值，不存在時取∞）。

算法1 BABS(b,l,h)

輸入：b 為待指派鄰點的塊，l,h ∈D 是b 鄰域的任意下界和上界（設D 上定義有全序關系）。

輸出：返回b 在[l,h]之間的 ||V 個鄰點（不足時全部返回）。

更新模式P的指派圖時，算法1 和文獻[14]的IPB一樣，僅計算差異塊bP-sup(P)的 |V|個鄰點，僅當其不足時完全計算。由于每個塊的鄰域在其為差異塊時計算完成，故整個指派圖中，塊鄰域大小均不超過 |V|。而文獻[10]和文獻[11]的模式真實性驗證使用了P的完全指派圖）。在單向匹配的存在性上，上述兩種指派圖是等價的，但文獻[14]只是默認使用了這一結論。本文補充其證明如下：根據Hall定理，二分圖BP存在左到右完備匹配，當且僅當任取Q?P,|N(Q) |≥ |Q|,這里N(Q)=N(b)，而N(b)是b在BP中的鄰域。任取塊b∈P，若其鄰域大小達到 |V|，包含該塊的任何Q滿足|N(Q) |≥|V|≥ |P|≥ |Q|。此時計算其所有鄰點或者恰好 |V|個鄰點，對整個BP的單向匹配存在性沒有影響。由b的任意性得證。

故此，算法1 和IPB 對BP結構的簡化不影響P的真實性驗證結果，也不會損失授權剪枝能力。文獻[14]的變量排序規則，可以在統計意義上增強約束剪枝能力。不過，本文沒有對此作出優化。

用算法1 計算任意塊b的鄰域，時間復雜度是O(|D||b|)=O(|D||V|)。但其既是尋找僅一個鄰點，也是尋找所有鄰點的最壞理論代價，很難準確反映實際的鄰域計算開銷。算法1 利用步驟授權資源的分布邊緣和間隙跳躍取值，可有效改善這一計算的實際性能。該算法依賴于外部指定的初始邊界l和h。在比較粗糙的情況下，可以將它們取作minD和maxD。下一章將利用IPB的搜索結構，以每個模式處常數時間的代價計算更緊的初始邊界。

4 邊界收縮增量模式回溯算法

下面給出本文的改進IPB，稱為邊界收縮增量模式回溯（Incremental Pattern Backtracking via Boundary Shrinking，IPB-BS）。它在搜索過程中以增量方式計算差異塊鄰域的初始邊界，以此為參數調用BABS完成該塊的鄰域計算。其偽代碼描述如下。

算法2 IPB-BS(P,&B,M) //遞歸函數

輸入：模式P；傳址的二分圖變量B=BP；M 是B 的單向完備匹配。初始調用置P ←?，B ←?，M ←?。

輸出：返回＜V,d,C ＞的可行解，或其不存在時，返回UNSAT

return M ；// M 可視為V →D 映射

} else {

計算將v 加入P 形成的合格模式集X(P,v)；

for (P'∈X(P,v)) {//X(P,v)是用步驟v 擴展模式P可能得到的所有子模式

if (bP'-P={v}) {//v 單獨成塊。bP'-P表示模式P' 相對其父模式P 的唯一差異塊，其中必含步驟v

將d(v)中的前 ||V 個（不足時取全部）指派給bP'-P，將B轉換為B' ，并備份更改；//B 可視為P →2D映射，為P 中每個塊確定一個指派鄰域

lbP'-P←min d(v)；//設置下界初值，lbP'-P是塊bP'-P的指派鄰域下界

hbP'-P←max d(v)；//設置上界初值，hbP'-P是塊bP'-P的指派鄰域上界

} else {//P' 是將v 加入P 中原有塊而形成的，bP'-P∈P'在P 中對應的塊為bP'-P-{v}

if (lbP'-P-{v}∈d(v)) lbP'-P←lbP'-P-{v}；//v 加入前的下界仍然有效

else lbP'-P←next(d(v),lbP'-P-{v}) ；//下界失效，用d(v)中大于lbP'-P-{v}的第一個值對其進行修正

if (hbP'-P-{v}∈d(v)) hbP'-P←hbP'-P-{v}；//v 加 入前的上界仍然有效

else hbP'-P←prev(d(v),hbP'-P-{v})；//上界失效，用d(v)中小于hbP'-P-{v}的第一個值對其進行修正

調用BABS(bP'-P,lbP'-P,hbP'-P)計算bP'-P的鄰域，將B 轉換為B'，并備份更改；

從M 中刪去bP'-P所關聯的邊；

}

以M 為初始匹配，用Hungary算法求B'的最大匹配M'；

if (| M' |= |P'|) {// M'是B'的單向完備匹配π ←IPBBS( P',B',M' )；

if (π ≠UNSAT) return π；

else {利用備份恢復B；}

} else {利用備份恢復B；}

}//for

return UNSAT；

}

在搜索時，IPB-BS 對每個當前模式相對父模式的差異塊進行判斷（第7 行）。若其為新步驟單獨形成的塊，直接設置初始下界和上界（第9 和10 行）。否則，利用新步驟的授權資源集，對差異塊的下界和上界加以修正（第12～15行）。這部分工作只需常數時間，不影響真實性驗證的時間復雜度。同時，IPB-BS改用BABS計算塊鄰域，但其時間復雜度仍為O(|V||D|)。BABS 依賴于一些全局性索引數組，可以多項式時間預計算，不占用搜索時間。故IPB-BS 的整體時間復雜度和IPB 一樣，為O(B|V|(f(|C|)+|V|2+|V||D|)) ，其中f(|C|) 是 |C|的函數，表示單結點處的約束驗證代價。特別地，單結點處的真實性驗證代價仍為O(|V|2+|V||D|)。IPB-BS為實現邊界收縮附加的全局和局部數據均只占用多項式空間，因而整體上和IPB一樣，具有多項式空間復雜度。

5 實驗研究

本章將IPB-BS與MPB[11]、IPB[14]等國內外新近工作對比。用C++實現各算法（統一采用IPB的變量排序規則，求匹配增廣路時采用寬度優先方式），編譯運行環境是：GNU C++、24 GB RAM 的CentOS 7 虛擬機、3.4 GHz Intel Core i3 CPU。單個實例執行時間上限為30 min。

實驗1 本實驗采用文獻[11]的二元隨機模型生成僅含互斥約束的測試實例。其參數有 |V|、資源比例μ%=|D|/|V|、約束密度ω%=2|C|/(|V|(|V|-1)) 和授權比例k%=|d(v)|/|D|(v∈V)。它主要通過授權比例的變化來制造困難實例的生成機會。取10 ≤ |V|≤100可以覆蓋大多數工作流的步驟集規模，50 ≤μ≤200 反映普通的資源比例，10 ≤ω≤25 反映工作流應用約束密度較低的特點。然后以不同跨度和分布，生成4組k值區間（第1 組：[1，33]、[17，49]、[34，66]、[50，82]、[68，100]；第2組：[8，27]、[24，43]、[41，60]、[57，76]、[75，94]；第3 組：[1，5]、[21，25]、[41，45]；第4 組：[2，4]、[22，24]、[42，44]），每個區間隨機生成50 個實例，共800 個實例。三種算法在四組實例上的運行結果如表1所示。

表1 三種算法四組實例結果統計

除第3組的[1，5]區間以外，三種算法在各區間的解出率均相同。在[1，5]區間，兩種IPB較MPB多解出了2個實例，解出率高了4%。在所有區間上，兩種IPB的未解出實例都相同，且其中不存在MPB 的解出實例。這表明兩種IPB 較MPB 有微弱、確定的解出率優勢。在各算法都完全解出的13個區間上，IPB的平均時間性能是MPB 的2.93 倍（各區間上平均時間之比的平均值），IPB-BS 是MPB 的2.56 倍。在其余3 個區間（第1 組的[1，33]、第3組的[1，5]和第4組的[2，4]）的共同解出實例上，IPB的平均時間性能是MPB的9.69倍，而IPB-BS是MPB 的35.9 倍。可見在共同解出實例上，兩種IPB 較MPB有顯著的時間性能優勢。這主要因為對于每個當前模式，兩種IPB 無需計算每個塊的完全鄰域，而只需計算差異塊的鄰域，且至多計算 ||V個鄰點，消除了重復計算，并進一步減少了計算的鄰點個數。在完全解出的13個區間上，IPB的平均性能是IPB-BS的1.03倍，但在其余3 個區間的共同解出實例上，IPB-BS 的平均性能是IPB 的4.57 倍（在[1，33]區間為1.14 倍，[1，5]區間4.90倍，[2，4]區間7.65倍）。出現這種反差的原因在于：IPB-BS為了實現邊界收縮，預先計算了若干索引數組，但其降低了搜索階段指派鄰點的計算代價。對于前13個區間搜索很快完成的實例，IPB-BS 的預計算負擔可能使其較IPB 處于劣勢，但對于后3 個區間搜索相對耗時的實例，IPB-BS就表現出了自己的優勢。特別地，取得了高達4.57倍的性能優勢，其原因有兩點：首先，測試實例中僅含互斥約束，其檢查非常高效，使得真實性驗證代價以及指派圖計算開銷對整體性能產生了更大的影響。進而，這3個區間（特別是[1，5]和[2，4]）的步驟授權比例很低。IPB在原始的資源集中搜索指派鄰點，需要檢查可高達數十倍的無效資源。IPB-BS避免了這種不必要的代價，從而獲得了很高的性能收益。

實驗2本實驗將采用文獻[14]的相變實例生成模型，將兩種IPB作進一步對比，探究IPB-BS的其他適用條件。該模型具有更高的資源比例，通過約束數量的調節來生成困難實例。每個實例包含互斥、五元at-most-3和五元at-least-3三種約束。其參數有 |V|、|D|、at-most-3/at-least-3 約束數γ和互斥約束數e。令 |V|從18 開始增加。將資源比例μ取作10和100，以反映第三方資源環境的特點。該模型對每個u∈D，從V中隨機選擇1～|V|/2 個不同的授權步驟。這將使得授權比例k%≈1/4。at-most-3/at-least-3約束不如綁定/互斥約束常見，故只取γ=|V|。然后根據有解概率恰為50%（即欠約束和過約束兩種易解情形中間的位置）的實例難度相變要求，通過估計和驗證，確定剩余參數e的值。每組參數都生成了100 個實例，其中有/無解的數量相當，均為理論上的困難實例。將對每組參數下的實例運行結果分有/無解情形取平均值，消除隨機性影響后，觀察參數變化的性能影響。若出現超時實例，不再計算該組參數下的平均值。同時停止實驗，不再求解更大參數的實例。

先在μ=10 的實例集上運行兩種算法。每種算法在有/無解情形下，執行時間隨 ||V值變化的對數坐標曲線如圖1。

圖1 IPB-BS與IPB執行時間對比(μ=10)

每種算法在無解實例上求解性能，通常都弱于有解實例。這主要是因為無解時必然遍歷解空間。在|V|=18～38 區間，IPB-BS 處于相對劣勢。這主要是因為IPB-BS 的預計算以及邊界維護代價。但是，對作圖數據的統計表明，由此導致的IPB-BS絕對劣勢很小，在有/無解情形下平均差距僅為0.17 s 和0.31 s，最高差距僅為1.55 s。從 |V|=39 開始，不論有/無解情形，IPB-BS都開始取得優勢：較IPB平均降低了32.8%的時間代價；最多降低了33.9%，出現在有解情形 |V|=46 處；最少降低了31.6%，出現在無解情形 |V|=39 處。整體上，隨著|V|的增大，IPB-BS 不僅開始表現出相對優勢，而且其優勢逐漸擴大。這是因為兩種IPB 的單結點真實性驗證時間為O(|V||D|)=O(10|V|2)，而在本實驗配置下的約束驗證時間為O(|V|2)，前者會隨著 |V|增加更快增長，在總代價中占據更高的比例。而IPB-BS 在真實性驗證中較IPB 具有優勢。當 |V|增加時，這種優勢隨著真實性驗證代價所占比例的提高，得到了更明顯的表現。就絕對差距而言，在 |V|=39～47 區間，在有/無解情形下，IPB-BS 較IPB 平均減少了16.9 s 和29.3 s 的執行時間，最高差距達到71 s。

進一步擴大資源比例，對μ=100 的情形進行實驗，結果如圖2所示。

圖2 IPB-BS與IPB執行時間對比(μ=100)

此時，IPB-BS的性能優勢更為明顯。在時限內，較IPB 多計算了 |V|=45 和 |V|=46 兩組實例。在 |V|=18～44 區間，相對于IPB，在有/無解情形下平均降低了45.7%和48.7%的時間代價。在有解情形下：最多降低了66.5%的時間代價，出現在 |V|=44 處；最少降低了6.0%，出現在 |V|=19 處。在無解情形下：最多降低了67.0%的時間代價，出現在 |V|=44 處；最少降低了10.6%，出現在 |V|=18 處。相對于μ=10 的情形，IPB-BS不僅取得了更大優勢，而且在不同的 |V|處始終處于優勢。這主要是因為：本組實例的原始資源集D擴大了10 倍，使得從D中搜索鄰點的IPB，其真實性驗證代價相對于約束驗證代價，以及輔助的初始和維護代價，所占比例更為突出，從而IPB-BS 在真實性驗證上的優勢表現得更為充分。

6 結論與下一步工作

本文對*WS-RI 的新近算法IPB 進行優化，給出了一種基于邊界收縮的加速方法。利用步驟授權資源的分布邊緣和間隙，通過邊界對齊和滑動的方式，逐步找出步驟塊各指派鄰點，加快了模式真實性的驗證過程。在隨機實例集上的實驗表明，本文提出的IPB-BS 算法較非增量模式回溯法優勢顯著。并且對如下的常見應用條件，較IPB有比較明顯的性能優勢：（1）工作流應用典型的低約束密度，結合此時容易導致困難實例的低授權比例，以及能夠高效驗證的約束類型。該條件下IPB-BS較IPB具有可高達數倍的性能優勢。授權比例越低，優勢越明顯。（2）第三方資源環境下典型的高資源比例，結合適當的授權比例，以及可導致相變的、適當類型和數量的約束。該條件下IPB-BS較IPB具有比較明顯的性能優勢。且資源比例越高，步驟數量越多，優勢越明顯。下一步將對塊鄰域緩存的設計利用進行研究。