又快又好的上下文一致性檢測

01-31

這篇文章科普了上下文一致性檢測的話題，並介紹了我們發表在ICSME2017的研究工作「GEAS: Generic Adaptive Scheduling for High-efficiency Context Inconsistency Detection」[1]。

大家都知道，智能手機，app給我們的生活帶來了極大的便利，吃飯找點評，打車用滴滴，不認路開地圖，等等。這些app給我們提供了許多服務，讓我們的生活更加的智能。既然是智能服務，肯定不是那麼容易的啦，這些app都依託於大量的數據，而且需要與環境進行交互。舉一個簡單的例子，所有這些app都需要進行定位，那麼GPS數據就是必不可少的。而由於環境的不可控性，GPS數據不可避免的會出現不準確，丟失等情況。這些不準確甚至是錯誤的數據，可能就會影響應用的運行，出現一些用戶不友好的行為。假想一下，如果你自駕出去玩，在通過一條隧道時，GPS受到干擾不在線了(錯誤或者丟失)，出隧道後導航告訴你前方20米右轉，而實際目的地卻在相反方向，於是，在你辛辛苦苦開了一段時間後，你發現，鬼知道這是什麼地方......(圖片來自網路)

在這裡，app用到的GPS數據其實就是上下文信息(環境信息)，簡單來講就是應用利用感測器獲取的環境信息，如溫度、濕度、速度，位置等等。每個上下文集合包含有限數目的上下文元素。一個簡單的例子，我們可以把某個時刻南京市棲霞區的所有車輛看做一個上下文集合 $C$ ，其中每個元素代表一輛單獨的車，包含 $id$ ，位置，速度等屬性信息。

利用上下文信息給用戶提供服務的應用就叫做環境感知型應用。在普適計算環境中，上下文信息由於受到雜訊等不可控因素的干擾，面臨著一致性錯誤的問題。這些錯誤會影響應用的正常運行，使其表現異常甚至失效[2]，出現用戶不友好的情況。為了避免這些情況，應用在使用上下文信息之前，需要經過「過濾」，來保證上下文信息的正確性。

這個「過濾」就是上下文一致性檢測和修復的過程。換句話說，我們研究實現了一個連接環境（上下文信息）和應用的中間件系統，主要負責對從環境中獲取的上下文信息進行檢測和修復，然後將處理後的一致的上下文信息傳輸給應用。這篇文章只涉及檢測部分，修復是一個更複雜的問題，今天我們暫不討論。

在運行時刻，我們接收上下文信息流，每當發生上下文更新時，就對滿足應用需求的一致性約束[2]進行檢測，判斷是否有約束被違反，以此避免將不一致的上下文傳播到應用中去。這就是上下文一致性檢測。

上下文信息發生更新是指上下文集合發生改變，如棲霞區新進入一輛車， $C$ 集合就會增加一個元素。一致性約束，通俗來說就是應用必須滿足的要求，可能是物理環境限制引發的條件，比如說「一輛車不能同時出現在兩個地方」，也可能是應用本身的需求，比如說用戶在南京市打開地圖進行導航，應用不能將其定位到南京市之外的地方。我們用一階邏輯公式（全稱量詞，存在量詞，取反，交，並，推出以及函數符號）來表示一致性約束[3]。以「一輛車不能同時出現在兩個地方」為例，定義 $R_x$ 和 $R_y$ 分別代表兩個不同的區 $x$ 和 $y$ 中車的集合，該約束可以表示如下：

$forall v_1in R_x. neg( exists v_2in R_y. (equal(v_1,v_2)))$

如果某條一致性約束被違反（返回布爾值為false），我們就說檢測到了一致性錯誤（ $inc$ ，inconsistency）。

我們解決什麼問題？

環境感知型應用對環境是敏感的，它依賴於上下文信息進行分析推理，進而調節自身的行為。當數據量非常大，上下文信息變換非常頻繁時（比如GPS數據，幾秒甚至幾毫秒就會發生更新），我們的上下文一致性檢測過程也應該足夠快，才能保證不會影響應用的後續處理。因此我們希望解決的問題是，如何更快的進行上下文一致性檢測。

區別於完全檢測（ECC [4]），在每次上下文信息發生更新時，就對所有的一致性約束全部重新進行檢測，增量檢測（PCC [3]，每次更新時只對發生改變的部分重新計算，未發生改變的部分復用之前的計算結果），基於CPU和GPU的並行檢測（CON-C [5]和GAIN [6]，都是利用多線程，並行處理不同的任務）已經在一定程度上提高了檢測的效率。不過，目前已有的這幾種檢測技術都是考慮如何把一次檢測做的更快，而沒有考慮減少檢測次數，它們都需要在上下文信息發生更新的時候立即進行檢測。

舉一個通俗的例子，你是一個船工，往返拉客養家糊口，為了能賺更多的錢，你考慮買一個電動的馬達來代替手搖櫓，很顯然，你在考慮縮短一次行程的時間來提高效率。可是你的拉客策略是在每當出現一個乘客的時候，你會立即開船把乘客帶到對岸。試想一下，在不改變你的拉客策略的情況下，就算你換一個很強大的發動機，每次行程都用很短的時間，你能跟得上乘客的流量，進而賺到更多的錢嗎？

因此，我們考慮是否能夠同時處理多條上下文信息的更新，減少上下文檢測的次數，從而進一步提高檢測效率。我們期望這個提升能夠適配於所有的檢測技術，也就是說，在保持一次檢測的效率提升的情況下，在另一個維度進一步提高檢測的效率。

想像一下，在你換了電動馬達之後，你適當改變了你的拉客策略，每次搭載10個乘客。那麼在每個乘客付給你的錢一定的情況下，是不是你能更快的賺到一個iPhone X呢？

當然，我們還需要考慮把這些上下文信息的更新放在一起處理會不會產生什麼副作用？我們的目的是檢測到上下文一致性錯誤，那麼同時處理多條上下文信息的更新會不會對檢測結果產生影響呢？實驗發現簡單的批處理策略（同時處理多條上下文信息的更新）和立即檢測策略（每次處理一條上下文信息的更新）相比，確實減少了大量的檢測時間，但是同時帶來了嚴重的漏報問題[1]，很多一致性錯誤被忽略。簡單來說，當發生一次上下文更新時，檢測發現一致性錯誤，而當第二次上下文更新發生時，一致性錯誤消失。那麼如果我們把這兩次上下文更新放在一起進行處理，這條一致性錯誤就會被忽略。

還是上面那個例子，為了保證安全，每個搭載的乘客需要穿戴救生衣，而救生衣可承載的重量有限，因此你設計了約束限制乘客的平均體重。假設某次行程中，10位乘客中包含A，B兩位，經檢測10位乘客的平均體重在可控範圍內，於是你放心的開船了。可是真的不會出現問題嗎？我們把10位乘客放在一組，確實只需要進行一次計算，有效地節省了時間。可是B乘客「掩蓋」了A乘客可能觸發的錯誤，給行程埋下了隱患。

回到我們的問題上來，多條上下文信息的更新同時處理很有可能會「掩蓋」本該發現的一致性錯誤。因此我們需要判斷，哪些上下文信息更新可以放在一起，而哪些上下文信息更新不能放在一起，有選擇的將可以同時處理的上下文放在一組。我們期望能夠做到在保證檢測結果正確的情況下提高效率，也就是我們要解決的難點，如何又快又好地進行上下文一致性檢測。

又快又好的上下文一致性檢測

我們考慮兩個因素：

快，通過將多條上下文信息更新同時處理來減少檢測次數，以達到提高檢測速度的效果。需要說明的是，我們的策略和現有的幾種一致性檢測技術都能進行適配，在保持已有提升的情況下從另一維度進一步提高檢測效率。
好，保證檢測結果的正確性，也就是避免一致性錯誤的漏報。我們通過增加判斷，有選擇的將多條上下文信息更新同時處理，保證所有的一致性錯誤不被漏掉。

首先我們思考為什麼會發生漏報？

當發生一條上下文更新時，一致性約束的檢測會受到影響，具體表現為，增加一條一致性錯誤（ $inc^+$ ）減少一條一致性錯誤（ $inc^-$ ），或者保持不變。如果第一條上下文更新（ $chg_1$ ）對一致性約束的影響表現為 $inc^+$ ，而第二條上下文更新（ $chg_2$ ）對一致性約束的影響表現為 $inc^-$ ，那麼將這兩條更新同時處理的話，可能就會有一條一致性錯誤被忽略。

我們將這兩條上下文更新的組合 $langle chg_1,chg_2rangle$ 稱為可疑上下文組合，如果有任意兩條上下文滿足可疑上下文組合的條件，它們就不能放在一起進行處理。

基於此，我們的檢測策略GEneric Adaptive Scheduling (GEAS)具體執行過程大致可以分為三步（整體架構如下圖）：

約束分析：獲取所有一致性約束的可疑上下文組合。

每條一致性約束可以轉換成一棵一致性計算樹，包含多分支結點（存在/任意量詞），雙分支結點（and/or/implies），單分支結點（not）以及葉子結點（bfunc）。當有一條上下文更新發生時，一致性計算樹的結構會發生改變（增加或刪除一個子分支），相應地，計算結果也會發生改變。布爾值由true變為false，可能導致一致性錯誤的增加；布爾值由false變為true，可能導致一致性錯誤的減少。
每條上下文一致性約束可接受不同類型的上下文輸入，其中部分上下文可能導致該約束檢測結果中一致性錯誤增加，構成一致性錯誤增加上下文集（ $inc^+$ 集合），部分上下文可能導致該約束檢測結果中一致性錯誤減少，構成一致性錯誤減少上下文集（ $inc^-$ 集合）。兩個集合中的上下文組合起來就可能導致該約束的某些一致性錯誤被忽略，也就是我們期望得到的可疑上下文組合。

上下文匹配調度：根據可疑上下文組合對每一條新獲取的上下文更新進行匹配和調度，判斷此時是否應該進行上下文一致性檢測。

我們維護一個待處理的上下文隊列，存儲所有已接收但未檢測的上下文信息更新，並且這些上下文信息更新經判斷是可以放在一起處理的。
在這一步中，我們的方法接收上下文信息流的輸入，對於每條輸入的上下文，將隊列中的上下文與輸入的上下文逐一組合，根據上一步驟得到的可疑上下文組合進行匹配。
如果該組合屬於可疑上下文組合，則匹配結果為真，表明新輸入的上下文與待處理上下文隊列中某條上下文組合會對一致性約束的檢測結果造成影響，造成一致性錯誤被忽略，因此該輸入上下文不能與待處理上下文隊列同時處理，應該在此進行上下文一致性檢測，同時清空待處理上下文隊列。
如果匹配結果為假，即待處理上下文隊列中任何一條上下文與輸入的上下文組合都不會影響一致性約束的檢測結果，則該輸入上下文可以加入待處理上下文隊列，與其同時處理。經過匹配和判斷，待處理上下文隊列中有選擇的包含了可以被同時處理的多條上下文，減少了上下文一致性檢測的頻率，以此來達到更高的檢測效率。

上下文一致性檢測：對所有待處理的上下文進行一致性檢測。

經過約束分析，上下文匹配調度之後，我們開始對得到的待處理上下文隊列進行上下文一致性檢測。這裡可以採用不同的上下文一致性檢測技術，但要求選用的檢測技術能夠接收待處理上下文隊列的輸入，即能夠同時處理多條上下文。
我們對原始檢測技術進行預處理來滿足該要求。給定一個原始檢測技術，經過預處理過程，改進檢測語義，得到可適配的上下文一致性檢測技術。將經過匹配調度得到的待處理上下文隊列作為輸入，經過分組後，服務於上下文一致性檢測技術，再根據上下文一致性約束進行檢測，得到檢測結果，最終獲得一致性錯誤。

實驗結果

我們選取了四種上下文一致性檢測技術，ECC [4]，PCC [3]，CON-C [5]和GAIN [6]，以及三種檢測策略，立即檢測（ImmedSched），簡單的批處理檢測（BatchSched）和我們的策略（GEAS），兩兩配合進行對比實驗，以此來驗證策略的有效性和高效性。所用的數據集就是某城市的計程車真實GPS數據。

批處理檢測需要額外確定一個參數，每次處理上下文的數量（例子中每次搭載乘客的數量）。我們考慮3個不同的參數做代表，2，4，6。GEAS策略能夠有選擇的將上下文分批處理，我們記錄每次處理上下文的數量，計算其平均值，並將其作為批處理策略的參數（BatchSched-mimic），進行比較。

高效性：我們通過檢測時間來衡量檢測的高效性。我們採用歸一化的方法來比較檢測時間，將立即檢測（ImmedSched）的檢測時間定為100%。實驗結果表明對於所有的一致性檢測技術，我們的策略都能與其適配，並顯著地提高檢測效率，達到檢測「快」的目標。

有效性：我們通過漏報率（1 - 漏報的一致性錯誤數目/總的一致性錯誤數目）來衡量檢測的有效性。實驗結果表明我們的策略能夠保證檢測結果的正確性，基本避免一致性錯誤的漏報，達到檢測「好」的目標。

總結

現存的一致性檢測技術嘗試通過增量，並行等方式來提高檢測效率，但為了避免檢測結果的漏報，它們必須和立即檢測的策略進行配合，這在一定程度上限制了效率的提升。我們提出了GEAS的策略來解決這個問題，通過有選擇的將多條上下文同時處理，在提高檢測效率的同時保證檢測結果的正確性。GEAS是一個通用的檢測策略，和現存的幾種一致性檢測技術均可適配，在保證檢測技術本身效率提升的情況下進一步減少檢測時間，效果顯著。

參考文獻

[1] B. Guo, H. Wang, C. Xu, J. Lu J, "GEAS: Generic Adaptive Scheduling for High-efficiency Context Inconsistency Detection", Proc. of International Conference on Software Maintenance and Evolution (ICSME), pp. 137-147, 2017.

[2] C. Nentwich, W. Emmerich, A. Finkelsteiin, and E. Ellmer, 「Flexible consistency checking,」 ACM Transaction on Software Engineering and Methodology (TOSEM), vol. 12, no. 1, pp. 28–63, Jan 2003.

[3] C. Xu, S. C. Cheung,W. K. Chan, and C. Ye, 「Partial constraint checking for context consistency in pervasive computing,」 ACM Transaction on Software Engineering and Methodology (TOSEM), vol. 19, no. 3, pp. 9:1–9:61, Jan 2010.

[4] C. Nentwich, L. Capra, W. Emmerich, and A. Finkelsteiin, 「xlinkit: A consistency checking and smart link generation service,」 ACM Transaction on Internet Technology (TOIT), vol. 2, no. 2, pp. 151–185, may 2002.

[5] C. Xu, Y. Liu, S. C. Cheung, C. Cao, and J. Lu, 「Towards context consistency by concurrent checking for internetware applications,」 Science China Information Sciences, vol. 56, no. 8, pp. 1–20, Aug 2013.

[6] J. Sui, C. Xu, S. C. Cheung, W. Xi, Y. Jiang, C. Cao, X. Ma, and J. Lu, 「Hybrid CPU–GPU constraint checking: Towards efficient context consistency,」 Information and Software Technology (IST), vol. 74, pp. 230–242, 2016.

論文信息："GEAS: Generic Adaptive Scheduling for High-efficiency Context Inconsistency Detection"。論文。

作者簡介：本文作者包括南京大學計算機軟體研究所的碩士生郭冰瑩、博士生王慧妍、許暢和呂建教授。