沖突型緩存側信道攻擊的構建驅逐集研究綜述

李真真，宋 威

(1.中國科學院信息工程研究所，北京 100085；2.中國科學院大學 網絡空間安全學院，北京 100049)

0 引言

CPU漏洞為硬件安全的研究重點，特別是利用CPU微架構的漏洞，具有攻擊方式多樣、隱蔽性強、難以防御等特點，威脅用戶信息和設備的安全[1]。傳統的信息安全主要通過加密來保護隱私數據或密鑰。從微觀角度來看，計算機系統處理數據的信道，又可細分為2段：加密算法執行前的信道和加密算法運行后的信道。各種網絡攻擊技術，即使獲得加密算法運行后的信道中的數據，依然需要通過密碼破解來獲得有用信息。軟硬件的隔離機制和安全機制等，通常位于緩存層級之上。而緩存側信道技術，針對加密算法執行前的信道部分，通過在計算機底層硬件系統的緩存存儲器中獲取有效信息，繞過了大部分依賴密碼學的防御手段和系統的隔離和安全機制。此外，對于加解密的信道，如果能夠從側面獲取一些信息，也能用于密碼特征的推測，從而為密碼破解提供一些幫助。

基于計算機系統微架構的側信道攻擊，只需要攻擊者和受害者共享部分硬件資源就可以攻擊。不同進程間共享緩存，為緩存側信道攻擊提供了條件。攻擊者可以利用緩存側信道攻擊突破瀏覽器的沙盒保護，破解內核態的地址隨機化，破解英特爾處理器的末級緩存分片算法，從而跨進程、跨處理器核、跨虛擬機，甚至跨SGX飛地發起緩存側信道攻擊[2]。隨著緩存側信道技術的不斷發展，側信道泄漏信息的帶寬也越來越大。部分更復雜的微架構攻擊中，緩存側信道攻擊是常見的關鍵子步驟。例如，廣泛存在于高性能處理器中的幽靈攻擊(Spectre)[3]和熔斷攻擊(Meltdown)[4]等。

本文重點介紹沖突型緩存側信道攻擊的共性且關鍵的子步驟：驅逐集構建，綜述了緩存側信道攻擊中驅逐集構建方法的發展，梳理總結了驅逐集的三類實現技術，并對影響攻擊性能的主要因素進行了分析。

1 驅逐集構建方法的發展

緩存側信道攻擊是攻擊者通過檢測特定數據在目標緩存的訪問延遲的差異，來推測被攻擊程序的行為。沖突型緩存側信道攻擊，是指使用一組特殊選取的地址(即驅逐集)誘發并利用目標緩存的沖突，從而推斷出關鍵信息[5]。驅逐集由一組地址集合組成，這組地址集合擁有足夠多個和目標地址緩存塊映射到相同緩存組的地址(即沖突地址)，它能夠利用替換策略將目標地址從緩存中驅逐。構建驅逐集的過程為學習虛擬地址到緩存組的映射。在沖突型緩存側信道攻擊中，攻擊者先使用驅逐集把目標地址清除出緩存，或者讀入受控的驅逐集地址，控制目標緩存組的狀態。接著收集攻擊目標運行時的緩存狀態變化，再結合先驗知識還原出密鑰、用戶行為信息、系統運行狀態、內核空間的數據等。構建驅逐集是沖突型緩存側信道攻擊的首要步驟和關鍵步驟。

沖突型緩存側信道攻擊中，任何兩個同時使用緩存的進程皆可成為攻守雙方。不需要共享內存和特殊計算機指令等限制，而只需要在共享緩存上成功構建驅逐集。構建驅逐集不但影響攻擊的可行性，同時影響攻擊效果。因為緩存被多進程并發使用，所以容易受噪聲干擾。為了減少噪聲干擾，攻擊者通過對內存使用情況進行緩存組級別的細粒度監控。Rowhammer攻擊中，需要對某緩存塊的驅逐頻率足夠高，從而提高位翻轉的成功率。實際攻擊中，對攻擊目標的操作是受限的。減少無關數據的讀入，從而減少對攻擊目標的操作。驅逐集中包含的無關地址，會引起噪聲，影響攻擊速度和準確度。而減少目標地址的操作，能減少攻擊受限和被檢測的可能。

驅逐集構建方法的發展與沖突型緩存側信道攻擊的發展緊密相關。圖1顯示驅逐集的構建方法研究的發展時間線。早期的沖突型緩存側信道攻擊針對L1/L2緩存。因為L1/L2緩存的組數較小，且采用直接位映射方式，構建驅逐集的方法為直接計算出驅逐集。比如候選地址與目標地址以頁面大小相同或數倍的偏移量進行對齊。直接計算驅逐集的構建方法可以追溯到Osvik等[6]在2006年實現的針對L1緩存沖突型緩存側信道攻擊。由于攻擊者與受害者同駐一個內核比較困難，一定限度限制攻擊的使用效果。對于多核處理器，共享末級緩存更容易。2015年成功實施了末級緩存(Last Level Cache，LLC)上的跨核攻擊，攻擊效果開始顯現[7]。但是在末級緩存上直接計算出驅逐集困難。即使攻擊者已知微架構的物理地址與切片索引的映射，開啟大頁，但是在真正的攻擊中，物理地址的受控信息仍是不夠的，驅逐集中仍包含大量非沖突地址。為解決末級緩存上構建驅逐集問題，第一個構建驅逐集算法(基礎裁減法)被提出。2018年，Qureshi[5]首先提出動態隨機化緩存CEASER，通過挫敗基礎裁減法來防御沖突型緩存側信道攻擊。2019年，比基礎裁減法更快的分組裁減法[8]被提出。同年，Qureshi[9]發現更快的分組裁減法能突破動態隨機化緩存的限制，并提出動態隨機化的分組式(Skewed)緩存CEASER-S。隨后基礎沖突測試法[9]、PPP法[10]和W+W[11]等構造驅逐集算法不斷被提出，突破動態隨機化的分組式緩存的限制，仍能實施沖突型緩存側信道攻擊。2022年，Purnal等[12]在異構處理器上首次實施沖突型緩存側信道攻擊，并提出針對異構處理器的聯合沖突測試法。2023年，Katzman[13]成功利用低精度時鐘實施攻擊，并同時證明使用低精度時鐘，仍能創建構建驅逐集。

圖1 構建驅逐集研究的發展時間線

2 構建驅逐集算法的分類

現有構建驅逐集算法主要有三大類：裁減類算法、沖突測試類算法和探測(Probe)類算法。構建驅逐集算法的分類見表1。從該表看出不同類型算法在準備候選地址(集合)、沖突前需緩存命中的地址類型和識別沖突方式三個過程中存在區別。下面對三類算法的基本原理、發展和代表性算法進行詳細分析。

表1 構建驅逐集算法的分類

2.1 裁減類算法

2015年，Liu等[14]提出減少驅逐集中的非沖突地址從而減少噪聲的方法，即第一個構建驅逐集算法：基礎裁減法(Single-Holdout Method，SHM)。2019年，Vila等[8]對裁減法的理論和實現進行研究，并最早提出了初始的分組裁減法(Group Elimination Method，GEM)。2019年，Song等[15]分析了基礎裁減法和初始的分組裁減法的時間復雜度上限、實現問題等，并提出了隨機分組裁減法。

裁減類算法中，候選集合是目標地址的驅逐集的檢測條件為：讀取候選集合后，成功驅逐目標地址。訪問足夠大的虛擬地址集就足以驅逐出緩存中任何內容，這意味著只要虛擬地址集合足夠大，該虛擬地址集合一定是目標緩存組的驅逐集。裁減類算法的基本原理如下：先選擇一個足夠大的候選集合，然后不斷裁減候選地址集合，再次檢測裁減后的候選集合是否仍是驅逐集，從而快速提升沖突地址在驅逐集中的占比。

裁減算法一般由兩個步驟組成：(1)構建出一個大的驅逐集，作為候選集合，(2)將這個集合減少到它的最小驅逐集。即一組隨機地址集合撞擊目標地址，然后裁減隨機地址集合。先讀入攻擊目標地址，然后讀入攻擊者控制的一組較大的候選地址集合，再觀測攻擊目標是否被擠出；如果被擠出，說明候選地址集合是驅逐集。

2.2 沖突測試類算法

沖突測試類算法先把目標地址讀入緩存，然后讀取一個候選地址，接著觀測是否驅逐目標地址。若該候選地址的讀入引起目標的擠出，則該候選地址與目標地址沖突。沖突測試類算法的基本流程如圖2所示。假設攻擊者可以獲取無限多的隨機地址，該攻擊者可通過逐個測試每個地址是否與目標地址沖突來收集一個驅逐集。首先選擇一個隨機地址，檢測該隨機地址是否與目標地址沖突。如果隨機地址與目標地址沖突，則把目標地址的沖突地址加入目標集合。如果該地址不是目標地址的沖突地址，或者已經找到的沖突地址不足以構成驅逐集，則再次隨機選擇一個地址，并檢測該地址，直到已經找到足夠多的沖突地址。

圖2 沖突測試類算法的基本流程圖

沖突測試類算法的識別沖突方式呈現多樣化。基礎沖突測試法(Conflict Testing，CT)，通過測試目標地址的延時是否超過末級緩存未命中的閾值，來觀測攻擊目標是否被擠出末級緩存；W+W法(Write+Write)的沖突檢測方式是觀察寫效應；聯合沖突測試法的識別沖突的方式為觀測數據直接交換(Data-Direct IO，DDIO)域的擠出。

2019年，基礎沖突測試法由Qureshi等提出，并用在末級緩存采用隨機替換算法的分組式緩存上[9]。2021年，Song等[16]提出基礎沖突測試法也對末級緩存采用LRU和RRIP替換算法的隨機化的分組式緩存也有效。Purnal等[17]在英特爾i7處理器上實現了基礎沖突測試法。2022年，Thoma等[11]發現了英特爾處理器的寫效應，并把寫效應作為沖突測試的方式，從而提出了基礎沖突測試法的變體W+W法。2022年，Purnal等[12]使用異構處理器的硬件結構特點對沖突測試類算法進行性能優化，并首次發現了非隨機化緩存情況下，最小驅逐集的沖突地址數比緩存路數小的場景。

2.3 探測類算法

探測類算法的基本原理為先選取候選集合的子集，然后把該子集的地址全部讀入緩存，使多個緩存組受控。越多緩存組受控時，攻擊越容易受噪聲干擾。驅逐集的實際使用中，驅逐集需要減少到只含有目標緩存組的驅逐集。探測步驟解決了該問題。在探測步驟中，攻擊者讀入目標地址后，被擠出的地址為與目標地址沖突的候選地址。

探測類算法的代表性算法有PPP法。PPP法(Prime，Prune and Probe，PPP)[10，18]采用目標地址撞擊隨機地址的方式。PPP算法的流程圖如圖3所示。每輪PPP過程包含Prime、Prune和Probe三個步驟。

圖3 PPP算法的流程圖

在Prime步驟，攻擊者讀入初始候選集合的地址。因為初始候選集合的地址會相互擠出，所以需要裁減出部分地址。在Prune步驟，所有被擠出地址都被裁減掉。裁減過程結束，所有攻擊者控制的候選地址全部安裝入緩存。最后的Probe步驟中，攻擊者或受害者讀入攻擊目標的地址，然后觀測攻擊者控制的地址是否有擠出。被擠出的地址是目標地址的緩存沖突地址。執行一輪PPP過程或者反復執行PPP過程。收集足夠多的緩存沖突地址，得到驅逐集。

PPP法采用了一種自底向上的方法：攻擊者從一個空集開始，增量地增加與目標地址存在緩存沖突的地址。當攻擊者無法訪問攻擊目標時，唯一可用的過程是準備緩存狀態，等待受害者執行，并觀察緩存狀態的變化。

2019年，Werner等[19]提出了動態隨機化的分組式緩存結構ScatterCache，從而增加使用裁減類算法尋找驅逐集的難度。2019年，Purnal等[10]提出了PPP法，并在ScatterCache上成功創建驅逐集。實驗證明PPP法顯著減少所需的受害者訪問次數。2021年，Purnal等[18]對動態隨機化的分組式緩存進行系統評估，并提出了針對動態隨機化的分組式緩存的三種PPP優化算法。

通過對不同構建驅逐集算法的關鍵特性，結合實際攻擊場景、攻擊目標，選擇出合適的算法，能提高攻擊效果。表2對這些算法的關鍵特性進行對比。其中末級緩存的路數為W，緩存組數為S，切片數為C。初始候選集的大小為n。D為DDIO的路數。對于具體的計算機體系結構，W、S、C、D均為常數。

表2 構建驅逐集算法的關鍵特性對比

3 影響算法性能的因素分析

在構建驅逐集研究中，需要發現并解決構建驅逐集中的不利因素。這些不利因素是真實處理器上構建驅逐集的成功率下降的關鍵。現代處理器為了提升性能，采用多級緩存、TLB、硬件預取、分支預測等架構設計。現代操作系統的多任務并發等設計，也同時給算法程序帶來背景噪聲。本節總結了緩存、TLB、操作系統和時鐘等因素對構建驅逐集算法性能的影響。

3.1 緩存結構的影響

緩存替換算法決定緩存塊的擠出順序，故緩存替換算法是構建驅逐集算法的重要因素。以裁減類算法為例。Vila等[8]發現采用LRU替換算法的緩存組比采用其他替換算法的緩存組上，構建驅逐集的成功率更高。Song等[15]對驅逐集地址訪問模式進行優化，從而提高驅逐的成功率。英特爾的服務器級處理器從Skylake-SP開始采用非包含型末級緩存，即私有緩存中的地址不一定存在于末級緩存。兩種提高驅逐成功率的優化方法，使裁減類算法突破了非包含型末級緩存的限制：2019年，Yan等[20]對裁減法的檢測方法進行優化：先構建一個與候選集合映射到相同L2緩存組的L2驅逐集。在目標地址和候選集合的地址讀入緩存后，讀入L2驅逐集，把候選集合中的地址從L2緩存擠到末級緩存。另外，2019年Song等[15]發現英特爾Xeon 4110上使用單線程訪問方法不能構建驅逐集。但是采用多線程多核并行訪問驅逐集的方式訪問驅逐集時，能驅逐成功目標地址。因為采用多線程多處理器核并行訪問一個地址時，同一個地址被同時讀入多個私有處理器核，迫使該地址存在于末級緩存。

3.2 TLB的影響

為了加速虛擬地址到物理地址的轉換，TLB存放部分虛擬地址到物理地址的轉換關系。虛擬地址和物理地址轉換中，先查詢TLB，TLB未命中，再進行緩慢的查詢多級頁表模式。訪問虛擬地址，涉及虛擬地址轉換物理地址，會進行非常頻繁的TLB訪問。虛擬地址翻譯數量增加，TLB的容量有限，故TLB的未命中率同步增加，并最終會導致觸發大量的頁表訪問。頁表的訪問需要讀取緩存獲得數據，這導致了緩存狀態的改變，干擾構建驅逐集過程。為保證檢測緩存延時的正確性，需要防止訪問某地址的延時包含TLB未命中的時間。一種減少TLB影響的方式為開啟大頁，頁面大小從4 KB變成2 MB，訪問候選集合需要訪問的頁面數量減少，從而減少TLB未命中的概率[21，14]。另外一種方式為TLB preload[22]。攻擊者可以在測量地址的讀取時間前，先訪問同頁面的不同地址，確保檢測延時的時候，對應的頁面不會缺頁從而訪問TLB。

3.3 操作系統的影響

現代操作系統是多任務運行的，任務共享軟硬件資源。任務切換、上下文切換、中斷等帶來抖動，從而帶來噪聲和干擾。構建驅逐集算法的程序不是唯一正在運行的進程，可能同時存在較高CPU負載的其他程序。操作系統的線程調度算法會定期中斷代碼并執行上下文切換，甚至還會涉及切換虛擬機等更多的上下文切換。采用多次測量或驗證方式，能減少噪聲的影響。常見的方法有：重復多次測量，直到收集到一致的結果[17]；對多次測量的延時結果求平均值[8，11，15]。

3.4 時鐘

確定某個地址是否在某級緩存命中，通常需要使用適當的高精度時鐘來測試某個地址的訪問時間。部分高精度時鐘不可用時，仍能找到可替代的高精度的時鐘源[23]。2023年，Katzman等[13]提出了低精度時鐘能測量納秒級別的延時差異。Katzman等[13]只使用一個分辨率為0.1 ms的定時器時，把信號放大了6個數量級，使讀入地址是否在緩存兩種情況下的時間差超過100 ms，并且平均15 s創建一個驅逐集。這表明降低時鐘分辨率并不能阻止驅逐集的建立。

4 結論

雖然計算機的算力在飛速發展，但是依然難以在合理的時間內破解加密算法。計算機系統的隔離和安全機制隨著技術和威脅的不斷發展而演進。緩存側信道攻擊作為推斷密鑰和繞過系統的隔離和安全的方案，讓信息安全防不勝防。

然而，緩存側信道攻擊還存在一些待解決待優化的問題。比如，存儲器目標地址的訪問受限、緩存側信道數據噪聲大、緩存結構隨著硬件設計在發展變化等。因此，緩存側信道攻擊技術中驅逐集的構建，需要考慮目標地址的訪問次數。需要根據具體型號的計算機體系結構中的緩存結構、TLB機制等硬件設計進行算法的選擇和優化。還需要研究不同操作系統和程序軟件下的驅逐集的自適應構建算法。隨著計算機時鐘精度的提高和時鐘測量技術的進步，結合緩存結構逆向技術和網絡通信技術，未來構建驅逐集算法的攻擊應用會更多，緩存側信道攻擊的影響將會更廣泛。