# [Automatic Firmware Emulation through Invalidity-guided Knowledge Inference](https://www.usenix.org/conference/usenixsecurity21/presentation/zhou)

## 摘要

* 提出一個叫做µEmu的方法來模擬有未知外部設備的韌體。
* 使用符號執行來推斷出外部設備存取的規則。
* 規則存在一個知識庫中，動態分析期間會參考知識庫。
* 在單元測試中實現了93%的通過率。

## 介紹

* 動態分析MCU韌體需要實現各種外部設備的邏輯，例如當韌體讀取外部設備的暫存器時，模擬器需要根據外部設備的狀態回傳正確的值。
* MCU SoC擁有高度的多樣性，如果不能自動化實現外部設備邏輯，人工成本會太大。
* 有些人將外部設備轉發到真實設備上處理，有些人則抽象化外部設備來避免問題。
* 前者不適用大規模的loop測試
* 後者需要設備遵守標準化流程
* 最新的方法是全系統模擬，代表方法是P2IM和Laelaps，但依然有缺點。
* P2IM在SR的操作算是用猜的。
* Laelaps探索深度不夠。
* 上面這些缺點都可能造成崩潰或是中止，因為外部設備的存取可能是根據多個暫存器共同影響的。
* 因此像P2IM那樣單獨處理每個外部設備可能就會出錯。
* 為此想要動態分析，就必須包含外部設備的行為全部模擬。
* 去分析每個外部設備的交互是不必要的，只需要在存取時給予適當的回應即可。
* 如何判斷外部設備輸入是否合適？
* 如何得到合適的輸入？
* 觀察：
* 如果錯誤的回應送到韌體，就會反映到執行狀態，導致模擬無效。
* 無效的執行狀態反映無效的執行路徑。
* 開發了µEmu，用於ARM MCU的動態分析工具。
* 使用符號執行找到模擬所需要的必要知識。
* 系統分為知識提取階段和動態分析階段：
* 知識提取階段，以韌體為輸入，混和一般執行和符號執行(concolic execution)，為後續提取訊息，訊息放在知識庫中。
* 深度優先，不會像Laelaps一樣路徑爆炸。
* 分級儲存機制，會根據增加的上下文來決定不同的回傳。
* 動態分析階段，在讀取外部設備的暫存器時，從找到知識庫中對應的條目回傳。
* 70個單元測試，成功率從P2IM的79%達到了93%。
* [開源的](https://github.com/MCUSec/uEmu)

## 背景

### MCU外部設備

* 外部設備很多樣化，必須準確、單獨的模擬每個外部設備的邏輯。

### 動態符號執行

* 符號執行是自動化測試和分析的技術，將程式的輸入變成符號變數模擬程式執行，所有的變數都會成符號表達式(symbolic expressions)。
* 而動態符號執行(concolic execution)結合一般執行和符號執行的優點，最流行的開源符號執行平台是S2E。
* 原始的S2E是利用QEMU的動態二進制轉換(DBT)模擬CPU，並與KLEE結合進行concolic。
* S2E 2.0版本後重構，將其和QEMU分離，自己維護DBT程式碼。
* S2E會在KLEE和DBT之間切換。

### 術語

* 分支
* 分支指令一定是block中最後一條指令，它會導致程式不是按照順序執行。
* 分支目標
* 分支指令後的目標。
* 條件暫存器
* 每個分支中會有一個或多個外設暫存器決定分支目標。
* 執行路徑/追蹤
* 程序控制流程圖中的動態流程。從進入點開始，結束點結束。
* 執行狀態
* 執行路徑中的中斷點，包含程式的記憶體、暫存器、外部設備狀態等等。
* S2E在執行狀態之間切換來探索程式，當韌體退出時，當前的執行狀態會對應到為一個執行路徑。
* 無效的執行狀態
* 會中斷韌體執行，包含崩潰、停止、跳過設計的操作(crashing or stalling firmware execution, and skipping designed operations)。
* µEmu的系統核心就是不斷避免外部設備讀取導致的無效執行狀態。
* 有效的執行狀態
* 不是無效的，就是有效。
* µEmu的目標就是透過知識庫中的值回傳給韌體，讓模擬保持在有效執行狀態。

## 總覽

* µEmu的目標是發現錯誤，其錯誤是因為不當處理I/O接口的暫存器得到的不正常輸入。
* 需要透過存取未知外部設備暫存器來自動生成合適的回傳值來模擬，雖然不保證和真實設備的值一樣，但至少可以動作。

### 想法

* 三個觀察：
1. MCU韌體中，條件暫存器會直接影響執行路徑。
2. 透過將外部設備暫存器表示為符號，外部暫存器和路徑之間的關係可以表示成符號表達式。
3. 選擇錯誤路徑，韌體就會進入無效狀態。
* 因此將未知的外部設備值全部表示成符號，利用符號執行和無效狀態檢測，就可以自動得到如何回應外部設備的知識。
* 知識包含如何回應外部設備和用於操作I/O的暫存器。
* 知識提取階段會從簡單的匹配規則開始，當暫存值會進行無效檢查時，會升級匹配規則考慮上下文。

### 威脅模型

* 不考慮攻擊者可以更改控制暫存器或狀態暫存器，因此這些由µEmu來控制適當的值，以免進入錯誤狀態。

### 方法

* µEmu的模擬和分析分為兩階段。
* 知識提取和動態分析
* 
* 動態分析的時候如果知識庫裡面都沒找到，就會重新回到知識提取階段來豐富知識庫。
* 知識提取階段的核心是以無效狀態為目標的符號執行引擎。
* 將外部設備暫存器當作一個符號，如果影響分支，就選擇一個分支目標並存下解決的值供之後使用。
* 一開始的匹配規則很簡單，為了就是讓緩存的值能匹配更多的外部設備。
* 如果發現值錯誤，就會升級規則來符合更複雜的條件。
* 發現當前執行狀態無效就會切到另一個分支目標，更新匹配規則和知識庫，當兩個分支目標都會導致執行狀態無效，就退回父分支(DFS)。
* 重複執行到韌體關閉(exit)或是長時間沒有找到新的block。

### 範例

* 以上面[方法](#方法)的圖為例。
* 我們在`0x40064006`的地方遇到分支，且值與外部設備暫存器有關。
* 在第一個分支我們使用求解器，希望可以往左邊走，算出值`0x30`。
* 這時在KB紀錄該值為Entry 1 for Trace 1。
* 結果後面發現左邊會讓執行狀態無效，因此將Trace從1改為2，重新計算暫存值，得到`0x00`。
* 這時在KB紀錄該值為Entry 1 for Trace 2。
* 遇到第二個分支，先繼續採用`0x00`走下去。
* 發現還是會遇到狀態無效，所以變成Trace 3。
* Trace 3 的時候發現Entry在不同的分支需要是不同的值，因此將規則升級(T1變T2)，創造了兩個Entry來符合不同分支。
* 為了在動態分析階段知識庫能可匹配，必要時使用hash的技術來記錄資訊。

## 實作

1. 描述μEmu系統架構
2. 闡述KB儲存策略
3. 無效狀態的檢測
4. 引導至無效狀態的KB提取演算法
5. 中斷處理
6. µEmu和AFL(一種模糊器)結合

### 框架

* µEmu是基於S2E 2.0開發的，而S2E是基於QENU的concolic執行工具。
* µEmu是作為S2E的插件開發的，主要的貢獻：
1. 將 ARM 的 DBT 移植到 S2E CPU emulation 使其可以模擬 ARM MCU。
2. 使模擬出來的 ARM Cortex-M CPU 可透過 KVM interface 存取。
* S2E 提供一個可以做符號執行的 vCPU，QEMU 再透過 KVM 接口來管理該 vCPU。

### KB儲存策略

* 使用分級儲存的策略，根據上下文自動選擇四種匹配規則，捕獲外部設備的行為。

#### T0 - 儲存模型

* T0其實不算一種匹配規則，他只是記錄最近寫入的值，用於後續的操作(讀取)。
* 當發現T0是錯的，會被升級到T1。

#### T1 - 基於PC

* 為了避免路徑爆炸，這個規則不看上下文。
* 在特定的PC(甚至任意的PC)要求存取特定的地址時，時常都是回傳固定值。
* T1通常是最常見的規則。
* 當發現T1是錯的，會被升級到T2。

#### T2 - 基於上下文

while( huart -> TxXferCount ){
    ...
    if(UART_WaitOnFlagUntilTimeout (huart, 0x80, 0, tickstart, Timeout) != HAL_OK)
        return HAL_TIMEOUT;
    huart -> Instance -> DR = * pDataa ++;
}
if(UART_WaitOnFlagUntilTimeout (huart, 0x40, 0, tickstart, Timeout) != HAL_OK)
    return HAL_TIMEOUT;

* 上面就是一個需要上下文的例子。第三行需要確認狀態暫存器為`0x80`，然後發送相關數據，接著同樣的暫存器需要設為`0x40`才表示通過檢查。
* 實作上使用hash編碼儲存需要的資訊。

int timestart = ticker_read();
do
    cur_time = ticker_read();
while(cur_time - timestart < timeout);

* 這是另一個T2的例子，真實設備中，`ticker_read()`會讀取一個外部設備的counter。
* 因為PC不同，T2可以區分兩次的存取。
* 當發現T2是錯的，會被升級到T3。

#### T3 - 基於重複

rf_read_buf(&buf, len);
if(strncmp((const char*)&buf, "OK\r\n", 4))
    while(1);

* 以上是一段T2無法處理的code，從外部設備讀取四個字元，必須符合`OK\r\n`。
* 因為上下文完全一樣，所以T2無法處理。
* 這種陣列形式的目標就使用陣列形式去儲存，只要按照一樣的順序重放就可以回復同樣的流程。
* T3很少被使用到，通常被使用到時用於接受外部數據，因此動態分析階段T3被視為模糊器的輸入點。

### 無效狀態的檢測

* 因為正常執行的時候，應該永不進入無效狀態中，因此如果進入了，代表KB中有一個或多個錯誤。

#### 無限循環

* 當韌體出現不可恢復的錯誤，通常使用無限循環來停止自己。
* 確認無限循環的方式是去檢查暫存器中的值是否一樣。
* 只有上下文涉及至少一個符號才去監控，且只監控最後30個block(為了避免成本太高)。
* main function 也是無限循環，不過長度長很多所以不會誤判。

#### 長循環

* 外部暫存器經常等待某個特定值(代表操作完成)，而這種等待通常伴隨Timeout的機制。為了避免每次跑都真的要跑很久，必須事先給予緩存值。
* 和無限循環的檢查機制大致相同，不過會額外檢查迴圈是否經過超過2000次。

#### 無效的存取空間

* 無效的存取空間代表空間沒有被mapping到。
* 會出現這種狀況有兩種可能：
* 實際設備就有問題(該paper的實驗測試沒有遇到這問題)
* µEmu學習的回傳值錯誤。

#### 使用者自訂無效點

* 支援使用者手動分配無效點，可以指定永遠不該執行到的地方。

### 引導至無效狀態的KB提取

#### KB_Learn(分支選擇和切換的演算法)

symbol ← get_symbol(); // 取得分支的符號
KB_Update(KB, symbol); // 更新KB，下面會有這個function
do //while主體，檢查所有block
    targets[] ← execute_BB(selected_target);
    if meet termination condition then
        return KB;
    end
    if current state is invalid then //狀態是否有效
        break;
    end
    if sizeof(targets) == 1 then //沒有分支，執行下一個Block
        selected_target ← next_BB(selected_target);
    else //有分支，根據KB選一個目標執行
        selected_target ← favorable_target(targets);
        other_target ← non_favorable_target(targets);
        unexplored.push(other_target); //沒有被選擇的目標會被push進stack，之後可能會跑
        symbol ← get_symbol();
        KB_Update(KB, symbol);
    end
while true;
// switch execution state
selected_target ← unexplored.pop(); //break出來，代表碰到無效狀態，從stack選其他分之執行
KB_Learn(selected_target);

#### KB_Update (KB更新演算法)

new_entry ← solver(symbol); //從符號執行引擎拿一個解
if new_entry conflicts with KB then //如果衝突，升級Tier
    // upgrade caching rules
    if type(symbol) == T0 then
        type(symbol) ← T1;
    else if type(symbol) == T1 then
        type(symbol) ← T2;
    else if type(symbol) == T2 then
        type(symbol) ← T3;
    end
    replace the conflicting entry with new_entry;
else //如果和前面的不衝突，直接更新到KB的暫存
    KB ← KB | new_entry;
end

#### 中止執行

* 現實的韌體通常會無限執行，所以一般執行之下，知識提取會永遠執行。
* 預設會監控最後30000個block，如果沒有到達新的block就停止。

#### 強化學習

* 有些code可能在特定事件才會執行，為了避免學習階段沒有覆蓋到，可能需要進行多幾輪的學習，稱為強化學習。

### 中斷

#### 中斷傳遞

* QEMU雖然有內建中斷控制器(NVIC)，不過針對其他的外部設備中斷支援度不好。
* InterruptControl 插件負責處理，跟NVIC互動。
* 和P2IM一樣，數個block後就會觸發中斷。
* 知識提取2000個bolck一次中斷、分析1000個一次。

#### 中斷暫存

* 外部設備中斷的部分，會受到暫存器的值而執行不同路徑，這些路徑都是有效的，導致通常都執行一樣的路徑，程式碼覆蓋率下降。
* 為了解決上述問題，在偵測到中斷時，符號執行引擎會探索所有可能的路徑。
* 而分析階段，選擇的KB值是隨機的。

### 模糊器

* FuzzerHelper插件把模糊器和µEmu接起來，還會自動找輸入點讓模糊器測試。
* AFL 雖然支援對 QEMU binary 模糊測試，但只有 userspace，因此 AFL 只用來生成 test case，其餘工作(覆蓋檢測、分叉服務器和崩潰/掛起檢測)通通交給 FuzzerHelper 插件。
* Firmware 第一次讀取到 test case 時會對整個執行狀態做 snapshot，每次發生 crashes/hangs 都會回到這個狀態繼續 fuzzing。
* 崩潰檢測的部分，實作了一個暫存錯誤檢測器，並將HardFault視為崩潰指標，檢測的Timeout為10秒。
* MCU中，數據暫存器常常是攻擊的輸入管道，對應到T3暫存器。

## 評估

1. 是否能正確模擬未知外部設備的行為
2. 性能是否在可實際使用的接受範圍
3. 是否能啟用模糊器等分析工具並發現韌體程式碼的錯誤
* 實驗環境：48GB RAM、Ubuntu 18.04、8-core/16-thread Xeon server。

### 單元測試

* 和P2IM一樣的設置。
* 沒有使用 AFL 產生的 test cases，而且使用預期的輸入來確保模擬正常。
* 結果：
* 所有測試都在1分鐘內完成知識提取
* 70個樣本中65個成功，通過率93%(P2IM 79%)

int i2c_read_bytes(...){
I2C_TypeDef *i2c_dev = i2c_config[dev].dev;
if (( i2c_dev -> SR & 6) == 2)
    return Error;
...
data = i2c_dev -> DR;
}

* 上面是常見的失敗例子，因為引導至無效狀態的關係，第5行中若有錯誤並不會被處理。
* 70個測試中失敗的5個都是類似的問題。
* 可以使用前面說的手動自訂無效點來解決該問題。

### 模糊測試

* 樣本使用10個P2IM的、2個HALucinator的、2個Pretender的、1個WYCINWYC的和6個真實商業設備上的。
* 涵蓋十多個MCU模型、每一個都有不同的外部設備和操作系統。
* 沒有人工輸入的前提下，成功了17個；剩餘的4個都只需要增加無效程式點即可。
* P2IM需要事先知道一些內存相關的訊息，而μEmu也是。
* 先進行一輪知識提取，然後模糊測試24小時。
* 
* 知識提取最差不須10分鐘，大部分只需2分鐘。
* 表中可以發現，使用暫存的KB效率大幅提升。
* 和P2IM比，程式碼覆蓋率略為提升。
* 除了WYCNINWYC中的XML錯誤，其他錯誤都可以重現，甚至發現兩個以前未知的錯誤。
* 時間方面，µEmu大概比P2IM慢了1.2~1.7倍，但他們認為是S2E比較慢的關係。
* 誤報的部分都是因為DMA(直接記憶體存取)，因為µEmu不支援DMA。

### P2IM失敗的原因

* 暫存器分類錯誤：
* 這個P2IM論文中就有提過，但他們發現這不只會讓模糊測試變慢，有時會直接造成崩潰。
* 暫存器無效假設：
* P2IM假設了一種結合控制和狀態的暫存器，但認為裡面的bits不重疊；實際上有時候會重疊導致錯誤。
* 有限的探索：
* P2IM的探索式執行沒有嘗試所有可能，有時找不到預期值而出錯。

## 限制

* 如[前面](#單元測試)測試失敗的部分，無法發現外部設備的輸入引起的錯誤。
* 大量合法的長循環被判定為無效點。
* 檢查如果大量路徑因相同原因，在同一點判定無效，則排除該點的無效狀態。
* 有時數據暫存器會歸類到T1或T2，導致模糊輸入點缺少。
* 可透過手動設定補回去。
* 長循環如果符號再循環外可能會被錯過。

## 相關工作

* 以前MCU的研究大多將外部設備轉到真實設備上。
* Laelaps也使用符號執行，但效率太差(路徑爆炸)且不支援暫存(每次存取都要跑一次符號執行)。
* PRETENDER用機器學習識別外部設備，缺點是沒有學習到的外部設備就不能用。
* P2IM在[前面](#P2IM失敗的原因)已經講過缺點和錯誤。
* HALucinator透過HAL(high-level hardware abstraction)代替外部設備模擬，但他可能跳過了底層的錯誤。
* µEmu除了模擬的能力之外，因為是在S2E上開發的，因此可以使用或自行開發其他的插件來加強工作。

## 結論

* µEmu可以自動找到未知外部設備的回傳，允許MCU的模擬。
* 使用的是符號執行，將學習到的值存在KB中。
* 在S2E實作，並開發了模糊測試的插件。
* 實驗表示可以成功模擬MCU並發現新的錯誤。

###### tags: `paper`