多級(jí)共享緩存性能和安全性聯(lián)合改進(jìn)

劉 洋

(池州職業(yè)技術(shù)學(xué)院 教育系，安徽 池州 247000)

高密度單核處理器因性能和功率問題而發(fā)展受限[1]，為提高整體性能，多處理器系統(tǒng)芯片越來越多地用于電腦和服務(wù)器平臺(tái)[2]。典型的多核處理器系統(tǒng)在一個(gè)域的處理核心上并行運(yùn)行線程(也稱為線程級(jí)并行[3-4])，可能會(huì)引發(fā)對(duì)共享資源的競(jìng)爭(zhēng)，從而降低芯片的性能[5-6]。在所有類型的資源競(jìng)爭(zhēng)中，緩存競(jìng)爭(zhēng)已被證明對(duì)整體芯片性能的影響最不利[7]。緩存競(jìng)爭(zhēng)導(dǎo)致的不良結(jié)果主要是1個(gè)線程驅(qū)逐了屬于其他共同運(yùn)行線程的活動(dòng)數(shù)據(jù)塊[8]。緩存競(jìng)爭(zhēng)會(huì)增加額外的內(nèi)存訪問，導(dǎo)致性能下降。許多研究都集中在這個(gè)主題上，并且已經(jīng)設(shè)計(jì)了各種方法來減少競(jìng)爭(zhēng)。然而，這些技術(shù)會(huì)增加巨大的運(yùn)行開銷。文獻(xiàn)[9-10]提出了一種緩存分區(qū)技術(shù)，但存在一些效率低下的問題。Huang等人[11]建議在緩存架構(gòu)中使用元數(shù)據(jù)，但硬件開銷非常大。在基于軟件的技術(shù)中，研究人員主要使用調(diào)度算法來減少緩存競(jìng)爭(zhēng)。Zhuravlev等[8]提出的基于分離域的方法，具有高緩存缺失率的線程，往往會(huì)占用所有的緩存塊，從而影響性能。Sahneh等人[12]使用每周期指令數(shù)(IPC)作為檢測(cè)沖突線程的指標(biāo)，提出的算法會(huì)反復(fù)檢查系統(tǒng)中每個(gè)域的IPC，導(dǎo)致效率較低。

針對(duì)前人研究存在的缺點(diǎn)，本文采用基于軟件的解決方案，不會(huì)增加硬件開銷。并且，在前人工作中，系統(tǒng)資源的可用性并沒有作為安全目標(biāo)直接在多級(jí)緩存中得到解決，因此將可用性作為本文研究安全性的重點(diǎn)。通過引入安全性和性能感知的線程映射，將線程映射到域的核心上，使線程之間的競(jìng)爭(zhēng)最小化，改進(jìn)多級(jí)共享緩存處理器的性能和安全性問題。該方法的基本特點(diǎn)是簡(jiǎn)單，開銷非常低。

1 攻擊模型

本文提出的緩存攻擊通過故意誘導(dǎo)緩存競(jìng)爭(zhēng)，增加任務(wù)/線程在多核系統(tǒng)特定核心上的執(zhí)行時(shí)間，如圖1所示。該攻擊的關(guān)鍵特征是獨(dú)立訪問私有代碼/數(shù)據(jù)空間，將執(zhí)行時(shí)間延長(zhǎng)5倍。

圖1 本文提出的攻擊概念模型

該攻擊包括正常任務(wù)、共享內(nèi)存、攻擊任務(wù)3部分。攻擊任務(wù)遵循算法1，實(shí)現(xiàn)緩存競(jìng)爭(zhēng)攻擊。它在運(yùn)行時(shí)分配的內(nèi)存中執(zhí)行隨機(jī)訪問，以占用共享緩存，增加正常任務(wù)的缺失率。為度量攻擊任務(wù)成功攻擊所需的時(shí)間，定義了一個(gè)大于1 K的整數(shù)數(shù)組，并發(fā)出順序地址，將該數(shù)組的所有單元初始化為1個(gè)常量。該操作所需的時(shí)間(Δt)將被記錄為該操作的正常時(shí)間，即參考時(shí)間。然后，攻擊任務(wù)向數(shù)組發(fā)出隨機(jī)地址跟蹤，并再次捕獲時(shí)間。當(dāng)隨機(jī)訪問需要至少2倍時(shí)間訪問數(shù)組時(shí)，攻擊任務(wù)將此視為成功攻擊。為解決多級(jí)共享緩存的動(dòng)態(tài)行為，攻擊任務(wù)每2個(gè)周期調(diào)用算法1。

算法1：

Function Attack_Algorithm():

Allocate a memory of 1KB→ A[];

Start_timer()→ t0;

for i ← 1 to size of A[]do

A[i]= ConstantInteger;

end

End_timer()→ t1;

Δt=t1+ t0;

for j ← 1 to 10 do

Start_timer()→ t0;

Tj←random trace of addresses to A[];

For all addressesm∈Tj: A[m]++;

End_timer()→ t1;

if((t1-t0)≥ 2Δt)then

Save theTj;

Exit the For loop;/*attack successful*/

end

end

if(attackhasnotbeensuccessful)then

ReleaseArrayA[];

CallAttack_Algorithm();

end

End Function

本文已經(jīng)在一個(gè)Linux操作系統(tǒng)上實(shí)現(xiàn)了攻擊，該系統(tǒng)運(yùn)行的是Mibench套件[13]的不同應(yīng)用程序。然后，使用OProfile性能監(jiān)視工具[14]記錄應(yīng)用程序的執(zhí)行時(shí)間。如圖2所示，在出現(xiàn)提出的攻擊時(shí)，任務(wù)的原始執(zhí)行時(shí)間已經(jīng)延長(zhǎng)。在這個(gè)實(shí)驗(yàn)中，使用500和5 000入口長(zhǎng)度的數(shù)組來實(shí)現(xiàn)攻擊，相比500的數(shù)組，5 000的數(shù)組執(zhí)行時(shí)間更長(zhǎng)，受到了更嚴(yán)重的延遲。這是因?yàn)檩^長(zhǎng)的數(shù)組使攻擊任務(wù)有機(jī)會(huì)進(jìn)行更遠(yuǎn)的跳轉(zhuǎn)和更不可預(yù)測(cè)的地址模式。另一個(gè)觀察結(jié)果是，攻擊任務(wù)對(duì)應(yīng)用程序執(zhí)行時(shí)間的影響并不總是相同的。例如，在快速排序(qsort)和拼湊(sha)任務(wù)中，輸入長(zhǎng)度為500和5 000的攻擊可以將執(zhí)行時(shí)間延長(zhǎng)5倍。然而，在循環(huán)冗余檢查(crc32)基準(zhǔn)測(cè)試中，500和5 000的攻擊延長(zhǎng)時(shí)間的倍數(shù)分別為1.5倍和2.5倍。這是由于crc32發(fā)布的擴(kuò)展地址比sha和qsort的少。

圖2 不同基準(zhǔn)測(cè)試集下所提緩存攻擊對(duì)執(zhí)行時(shí)間的影響

2 性能和安全性敏感的線程映射

本節(jié)提出了一個(gè)線程映射算法來聯(lián)合改進(jìn)多級(jí)共享緩存的性能和安全性問題。該算法基于IPC的平均數(shù)量對(duì)每個(gè)域的核進(jìn)行動(dòng)態(tài)線程映射/重映射。平均IPC是該域中所有運(yùn)行線程的算術(shù)平均值。假設(shè)1個(gè)域中存在1個(gè)緩存競(jìng)爭(zhēng)，它將導(dǎo)致緩存意外的丟失，降低域的性能。具有競(jìng)態(tài)條件的域顯示的IPC比無競(jìng)態(tài)條件的其他域要低。將IPC1，IPC2，...，IPCm分別定義為多核系統(tǒng)中D1到Dm域的平均IPC。關(guān)于每個(gè)域的平均IPC，定義以下工作狀態(tài)(如圖3所示)。

圖3 所提線程映射算法的狀態(tài)轉(zhuǎn)變

狀態(tài)S1：一種正常的狀態(tài)，所有域都工作，沒有緩存競(jìng)爭(zhēng)。當(dāng)所有域的平均IPC大于預(yù)期的IPC閾值(即IPC1，IPC2，...，IPCm≥ThIPC)時(shí)，可以檢測(cè)到。

狀態(tài)S2：在這種未充分利用狀態(tài)下，至少有一個(gè)域的平均IPC低于預(yù)期的IPC，即?i，使得滿足條件：IPCi

狀態(tài)S3：在這種未充分利用狀態(tài)下，至少有一個(gè)域的平均IPC低于預(yù)期的IPC，即?i，使得滿足條件：IPCi

該算法的目標(biāo)是保持域的平均IPC盡可能高。因此，該算法試圖在最大和最小平均IPC之間保持最小可能的差異。在這種狀態(tài)下，線程將基于Naive擴(kuò)散算法[3]分配到核心。

在S1狀態(tài)下，算法反復(fù)檢查所有運(yùn)行域的平均IPCs，分別找到運(yùn)行域Di和Dj的平均IPCs最小值和最大值。檢查域Di的平均IPC，如果大于或等于預(yù)期的IPC閾值，ThIPC，算法保持S1狀態(tài)。否則，算法將根據(jù)Max(IPC)和Min(IPC)的差值移動(dòng)到S2或S3狀態(tài)。算法2展示了算法的虛擬代碼，以及它在上述狀態(tài)下是如何工作的。輸入是線程和一個(gè)指定的采樣周期P。輸出是映射的線程。根據(jù)該算法，當(dāng)最大IPC和最小IPC差值小于閾值時(shí)，即Max(IPC)-Min(IPC)

算法2：

Input: Threads,P

Output: Mapped threads

Function Thread Mapping Algorithm():

forAllthreadsthatarereadytorundo

Schedule each thread with Naive spread algorithm;

repeat

Calculate averageIPCfor all domains;

Di← domain with the minimumIPC;

Dj← domain with the maximumIPC;

if(IPC(Di)

if(IPC(Dj)-IPC(Di)

Freeze a random number of threads inDifor100K cycles;

else

Swap threadT1∈Diwith threadT2∈Dj;

if(thisisthefifthmigrationofDi/Dj)then

Terminate the threadDi/Dj;

end

end

Wait forP;

end

untilallthreadsarefinished

end

End Function

該算法試圖在競(jìng)爭(zhēng)線程之間創(chuàng)建一個(gè)時(shí)間間隔，從而解決緩存競(jìng)爭(zhēng)問題。線程在凍結(jié)期結(jié)束后再次被激活，并繼續(xù)運(yùn)行。該算法在凍結(jié)期間不執(zhí)行任何其他競(jìng)爭(zhēng)，保持狀態(tài)S2，并在100K循環(huán)后返回狀態(tài)S1。另一方面，Di域和Dj域的IPCs 存在較大差異，即Max(IPC)-Min(IPC)≥Thδ，說明線程映射不合適。在這種情況下，提出的算法基于Naive擴(kuò)散，改變最初的線程映射。域Di中IPC最低的線程將被域Dj中IPC最大的線程所取代。

該算法還跟蹤已遷移的線程，以檢查它們是否可能參與連續(xù)的遷移。對(duì)于給定線程，連續(xù)三次遷移將該線程放入警報(bào)列表，第五次遷移后，該線程將被終止。線程遷移完成后，算法返回狀態(tài)S1，繼續(xù)檢查所有域的平均IPCs。所提出的算法很簡(jiǎn)單，且不需要硬件輔助，可以很好地提高基準(zhǔn)測(cè)試的性能，這將在下一節(jié)中得到展示。

3 算法評(píng)估

該算法使多級(jí)高速緩存系統(tǒng)在保持高性能的同時(shí)，對(duì)引入的攻擊具有魯棒性。為了進(jìn)一步研究這一問題，將本文提出的線程映射算法與SPEC CPU 2006基準(zhǔn)測(cè)試包中不同任務(wù)集下的分布式強(qiáng)度(DI)[11]、基于閾值(threshold-based)[11]、Naive集群(Naive-cluster)[3]和Naive分散(Naive-spread)[3]線程映射算法進(jìn)行了比較。

3.1 在模擬中使用線程集

使用Akula模擬器[3]進(jìn)行仿真，在仿真中考慮了不同的情況，研究了本文所提算法的優(yōu)缺點(diǎn)。所有情況都選擇SPEC CPU 2006基準(zhǔn)套件中的線程。在SPEC CPU 2006基準(zhǔn)測(cè)試套件中，線程可以細(xì)分為以下2類：高內(nèi)存需求(HI-MD)；低內(nèi)存需求(LO-MD)。HI-MD和LO-MD線程的各種組合被用來形成線程集，以覆蓋自然和攻擊情況。為了研究?jī)?nèi)存需求強(qiáng)度對(duì)性能的影響，定義了線程集以顯示4種不同級(jí)別的內(nèi)存需求：

級(jí)別1：該線程集由6個(gè)HI-MD線程和2個(gè)LO-MD線程組成，作為內(nèi)存需求最高的集合。

級(jí)別2：這個(gè)集合由5個(gè)HI-MD和3個(gè)LO-MD線程組成。

級(jí)別3：這個(gè)集合由4個(gè)HI-MD和4個(gè)LO-MD線程組成。

級(jí)別4：這個(gè)集合由3個(gè)HI-MD和5個(gè)LO-MD線程組成，作為內(nèi)存需求最低的集合。

對(duì)于每個(gè)模擬實(shí)驗(yàn)，從SPEC CPU 2006基準(zhǔn)測(cè)試套件中選擇10個(gè)不同的線程來滿足上述內(nèi)存需求。進(jìn)行了10次模擬，從Akula模擬器得到結(jié)果后，記錄最差和平均情況下的性能。結(jié)果需要計(jì)算算術(shù)平均值。

3.2 實(shí)驗(yàn)結(jié)果和分析

根據(jù)平均和最差情況下的性能退化(APD)這2個(gè)指標(biāo)，對(duì)上述線程集的DI、基于閾值、Naive集群、Navie分散和本文提出的算法的性能進(jìn)行評(píng)估。性能退化因子指的是，與在單核芯片上運(yùn)行而不共享緩存相比，在多級(jí)共享緩存平臺(tái)上運(yùn)行的給定線程的性能退化情況。這里說的退化是由緩存競(jìng)爭(zhēng)造成的。第i個(gè)線程的性能退化因子由式(1)計(jì)算。

(1)

用式(2)計(jì)算APD，即

(2)

式中：n是線程在芯片上運(yùn)行的核數(shù)。

最壞情況下的性能下降是運(yùn)行在n個(gè)核上的線程的最大性能下降，用式(3)計(jì)算得

(3)

改善平均情況下性能退化有利于整個(gè)系統(tǒng)，系統(tǒng)可提前關(guān)機(jī)，節(jié)省功耗。改善最壞情況下的退化有利于服務(wù)質(zhì)量(QoS)，因?yàn)楦?jìng)爭(zhēng)感知調(diào)度程序提供了穩(wěn)定的執(zhí)行時(shí)間，以保證更好的應(yīng)用服務(wù)質(zhì)量(QoS)。

為了評(píng)估所提算法的廣泛性，對(duì)表1中介紹的配置執(zhí)行了所有步驟。表2描述了在不同的內(nèi)存需求水平下，與其他4種映射算法相比，本文提出的算法在最差情況和平均情況下性能改善的百分比。由表2可以看出，本文提出的算法能夠很好地減少線程之間的競(jìng)爭(zhēng)，提高性能，特別是在性能退化最差的情況下。所提出的映射算法比Navier集群算法平均高出78.2%，而相比DI算法，改善值低于10%。平均情況下，平均性能改進(jìn)(即退化減少)的趨勢(shì)與最差情況幾乎相同，所提出的算法比DI提高了31%。在一些罕見的情況下，所提出的映射并不是最佳解決方案，例如，在3級(jí)內(nèi)存需求中，DI的性能損失最低，在最差和平均情況下比本文所提算法的要好28%和7%。表2中分別對(duì)4種算法性能提高的平均值再進(jìn)行求平均，可以得出，在最差情況和平均情況下，系統(tǒng)整體性能分別提高了46.4%和55.9%。

表1 模擬中的核和域的數(shù)量

表2 所提線程映射算法性能的提高 %

圖4～5分別顯示了所有5種算法在不同處理器中不同線程在最差和平均情況下的性能退化，表明本文所提的算法有了明顯的改進(jìn)。如圖6所示，評(píng)估了完成1個(gè)線程集所需的線程遷移數(shù)量。所提的算法所需的遷移梳理比DI算法少得多。在DI算法中，當(dāng)核數(shù)增加時(shí)，遷移會(huì)呈指數(shù)增長(zhǎng)，而本文所提算法改善了這種情況。

圖4 最差情況下的性能退化

圖5 平均性能退化

圖6 DI和所提算法所需的線程遷移數(shù)量

4 安全分析

假設(shè)數(shù)據(jù)緩存的總大小是n塊，受害線程占用了緩存的m個(gè)指令塊。當(dāng)受害線程執(zhí)行其目標(biāo)數(shù)據(jù)訪問(讀和寫)時(shí)，攻擊線程的行為是隨機(jī)的，使競(jìng)爭(zhēng)最大化。攻擊線程在無限循環(huán)中不斷地運(yùn)行，試圖將隨機(jī)塊引入共享數(shù)據(jù)緩存。雖然受害線程對(duì)數(shù)據(jù)緩存進(jìn)行了有針對(duì)性的訪問，但攻擊線程試圖通過發(fā)出隨機(jī)訪問來指向同一個(gè)塊。

受害線程運(yùn)行m個(gè)指令塊所需的平均時(shí)間為

(4)

式中：m是受害線程在指令緩存中準(zhǔn)備由本地核心執(zhí)行的指令塊的數(shù)量；ˉTblock是執(zhí)行一個(gè)指令塊所需的平均時(shí)間。

將ˉTblock用式(5)表示為

(5)

(6)

對(duì)于特定的i=j，受害者訪問第i塊數(shù)據(jù)緩存的概率為1，否則為0，即

(7)

由于攻擊隨機(jī)且一致地訪問所有數(shù)據(jù)緩存塊，因此訪問受害者已經(jīng)訪問過的同一個(gè)數(shù)據(jù)緩存塊的概率為

(8)

計(jì)算所有數(shù)據(jù)緩存塊在同一時(shí)間訪問的概率如式(9)所示。

(9)

式中：P(Att(Bi))、P(Vic(Bi))分別為攻擊和受害線程訪問數(shù)據(jù)緩存第i塊的概率。

(10)

(11)

因此，受害線程中故意缺失的概率為

(12)

式中：P(Att(Bi))和P(Vic(Bi))是2個(gè)獨(dú)立的概率。

將它們相乘，得到受害線程新的命中概率，即

(13)

在這種情況下，攻擊線程將有更多的機(jī)會(huì)將故意缺失注入到受害線程，實(shí)現(xiàn)成功攻擊的機(jī)會(huì)更高。

使用Intel Pin工具進(jìn)行實(shí)驗(yàn)，運(yùn)行了2個(gè)正常的程序，并計(jì)算了每個(gè)基本塊的指令數(shù)(跳躍指令作為最后一條指令的一系列指令)。圖7描述了5個(gè)不同程序中基本塊的數(shù)量和每個(gè)基本塊的平均指令數(shù)。雖然每個(gè)程序的基本塊的數(shù)量不同，但每個(gè)基本塊的平均指令數(shù)量都低于5條。幾乎有15%的指令需要訪問內(nèi)存，通過相同的測(cè)量工具計(jì)算，攻擊程序的這個(gè)百分比為30%。

圖7 不同程序下基本塊數(shù)量和基本塊平均指令數(shù)

5 結(jié)論

1)為了延長(zhǎng)特定線程的執(zhí)行時(shí)間，引入了一種新的攻擊方法，該方法獨(dú)立于訪問私有數(shù)據(jù)空間。這種攻擊可以將正常程序的執(zhí)行延遲5倍。

2)提出了一種基于軟件的競(jìng)爭(zhēng)感知線程映射算法來緩解緩存競(jìng)爭(zhēng)，該算法根據(jù)IPC參數(shù)檢測(cè)同一域上的競(jìng)線程，定期檢查系統(tǒng)狀態(tài)。與其他算法相比，它需要的線程遷移數(shù)量更少。

3)平均和最壞情況下，系統(tǒng)整體性能分別提高了46.4%和55.9%，證實(shí)了所提的線程映射算法通過減少緩存競(jìng)爭(zhēng)而顯著地節(jié)省了性能。并且，僅僅依靠任務(wù)遷移來減少競(jìng)爭(zhēng)并不是一個(gè)有效的解決方案。

4)通過闡述提出的緩存攻擊對(duì)受害線程性能的影響，對(duì)提出的攻擊進(jìn)行了全面的安全性分析。發(fā)現(xiàn)每個(gè)程序的基本塊的數(shù)量不同，但每個(gè)基本塊的平均指令數(shù)量都低于5條。