[PAPER] Automatic Firmware Emulation through Invalidity-guided Knowledge

Introduction

1. MCU 펌웨어 동적 분석 위한 기존 연구 방향들

1) harware-in-the-loop

실제 하드웨어를 사용해서 지원하지 않는 주변장치를 지원하게 하는 방법으로, 큰 스케일의 동적 분석에 부적절하다.

2) abstraction-base approach

HALucinator는 HAL(Hardware Abstraction Layer) API를 펌웨어에 매칭시켜서 교체하는 방식을 사용한다.표준화가 필요하고 custom SoC에는 적용 불가능하다.

3) full-system emulation

실제 하드웨어 없이 펌웨어 전체를 에뮬레이트하는 방법으로, high fidelity를 가진다. P2IM는 주변장치에 적절한 응답을 찾기 위해 전문가 기반 휴리스틱 방법과 알지 못하는 주변장치의 접근 패턴을 추론한 interaction 모델을 사용한다. Laelaps는 symbolic execution을 사용하여 가능한 모든 branch를 탐색하고 휴리스틱 방법을 사용하여 따라가기 좋은 경로를 예측한다.

2. 기존 full-system emulation 한계

1. P2IM - read 연산에서 주변장치의 상태 레지스터의 적합한 응답을 블라인드로 게싱하는 방식을 사용하는데, 큰 탐색 공간을 가질 때는 비실용적이다. emulation이 hang 또는 crash 발생 가능하다.
2. Laelaps - 실행이 짧은 경우에만 좋은 branch를 찾을 수 있다. emulation이 hang 또는 crash 발생 가능하다.
3. 펌웨어 emulation 시 여러 주변장치 레지스터 전체적으로 영향을 받는다는 사실을 간과했다. 시간 t 동안 하나의 주변장치 접근을 처리해야 할 때, 시간 t 동안 여러 레지스터에 의존적이라는 의미이다. P2IM은 각 주변장치를 독립적으로 처리하고 이 의존성을 고려하지 않았다.

3. 아이디어

1. 주변장치 입력의 적합성 여부를 알 수 있는 방법
   • 부적절한 응답이 펌웨어에 주어지면, 에러가 발생해서 emulation은 무효한 실행 상태가 된다. 무효한 실행 상태는 무효한 경로를 이끌기 때문에 이것으로 알 수 있다.
2. 주변장치 입력을 적절히 주는 방법
   • 모든 주변장치 응답을 심볼화하고, symbolic execution을 수행하면서 주변장치 응답이 무효한 상태나 경로를 피할 수 있는지 전체적으로 파악한다. symbolic execution을 수행하면서 constraint 충족 기반으로 응답을 탐색할 수 있다.

4. uEmu 제안

ARM MCU 펌웨어의 task 코드에서 버그를 찾기 위한 동적 분석 도구인 uEmu를 제안한다. uEmu는 invalidity-guided symbolic execution을 기반으로 펌웨어 이미지를 에뮬레이트하여 필요한 지식을 추론한다. 평가 결과 70개의 unit test 중 93% 통과했고, AFL을 결합하여 만든 fuzzing 도구를 리얼월드 펌웨어 샘플의 task 코드에 적용한 결과 새로운 버그 발견할 수 있었다.

5. contribution

1. 실제 하드웨어 없이 MCU 펌웨어를 에뮬레이트하는데 invalidity-guided 재귀적 지식 추출 알고리즘을 기반으로 symbolic execution을 사용하는 방법 제안
2. S2E 기반으로 접근법을 구현하였고, 30개의 서로 다른 주변장치를 갖는 21개의 리얼월드 펌웨어 샘플 대상으로 평가함
3. uEmu와 AFL fuzzer를 결합하여 fuzzing 분석 진행했고, 새로운 버그 발견

---

Overview

1. High-level Idea

1) three insights

1. MCU 펌웨어에서 conditional register 읽기는 execution path에 직접적으로 영향을 준다.
2. peripheral register를 심볼화함으로써 symbolic 표현에서 peripheral register와 path 사이 관계를 알 수 있다.
3. 잘못된 path가 선택되면, 펌웨어는 invalid state에 도달한다.

2) 추출하는 knowledge 정보

1. 실행 상태를 valid하게 만들 수 있는 알지 못하는 peripheral 접근의 응답으로 사용할 knowledge base
2. I/O 연산에 사용할 data register 집합

3) simple matching rule/context-aware matching rule

peripheral 문맥 기반으로 hardware state machine을 만들고, 현재 hardware state machine 기반으로 peripheral는 값을 반환한다. 문맥은 cache entry를 매칭하는데 사용되는데, peripheral 접근 매칭되는 rule을 매칭해보고 만약 틀렸으면 더 복잡한 execution 문맥을 사용해서 업그레이드된 rule을 매칭한다. 응답에 사용될 값을 찾기 위해 cache entry는 점진적으로 더 많은 문맥 정보를 사용한다.
simple matching rule은 symbolic execution의 탐색 공간을 줄일 수 있는데, 만약 simple matching rule로 복잡한 문제를 처리하지 못하면 context-aware matching rule이 사용된다.

2. Our Approach

1) Knowledge Extraction Phase

knowledge extraction phase
invalid-guided symbolic execution을 사용하여 peripheral access에 적절히 응답하기 위한 knowledge base(KB)를 구축하는 과정이다. Dynamic Analysis phase에서 주어진 peripheral access를 처리할 값이 KB에 없는 경우, knowledge extraction phase를 다시 진행한다.
tiered caching strategy

• symbolic execution 수행 시, 이전에 접근한 peripheral에 대해서는 이전 탐색 시 KB에 캐싱된 값을 활용하여 constraint solver를 이용한 peripheral reading 계산
• simple matching rule 적용: 우선적으로 적용되는 규칙으로, 비슷한 peripheral access에 대해서는 가능한 동일한 cache entry에 매칭한다.
• upgraded matching rule 적용: simple matching rule을 적용해서 캐싱된 값이 틀려서 invalid execution state로 이끄는 경우, 대응하는 peripheral register에 대해서는 upgraded matching rule을 적용

symbolic execution 과정
새로운 peripheral access인 경우(unknown peripheral access), 이 unknown peripheral access를 심볼화하고 symbolic execution 수행한다. 한 branch에서 이 심볼화된 값이 branch target에 영향을 주는 경우, 해당 peripheral access에 대한 디폴트 branch target으로 선택하고 이 solved 값을 KB에 캐싱한다. KB에 캐싱된 값은 symbolic execution 과정 동일한 peripheral access가 발생하는 경우, 대응하는 값을 사용해서 branch target을 결정할 수 있도록 한다.
depth-first search (DFS) algorithm 사용
현재 execution state가 invalid하면, symbolic execution engine은 다른 branch target을 선택하여 matching rule을 업데이트하고 KB 내 branch target에 대응하는 cache entry를 선택한다. 한 branch 내 branch target에서 execution state가 모두 invalid한 경우, parent branch로 rollback하여 탐색하지 않은 target을 선택하여 탐색을 계속 진행한다. 펌웨어 실행이 종료하거나 더 이상 새로운 basic block을 찾을 수 없을 때까지 알고리즘이 실행된다.

2) Dynamic Analysis Phase

dynamic analysis 접근법을 사용하여 펌웨어를 실행 시 peripheral access가 발생할 때, KB를 참조해서 적합한 응답값을 리턴한다.

4. A Running Example

그림 1의 가장 왼쪽 그림인 펌웨어 이미지에서 3개의 실행 추적이 있을 때, 각 branch는 node로 표현된다. 각 branch node는 하나의 branch target을 결정하는데 대응되는 peripheral register의 주소가 표시된다.

1) Knowledge Extraction Phase

1. 첫 번째 branch에서 디폴트로 왼쪽 branch target이 선택된다.
2. solver는 해당 branch target에 도달하기 위해서는 branch에서 constraint가 0x30임을 계산한다. 이 값은 KB 내 Entry 1에서 trace 1에 대한 값으로 기록된다. 추후에 PC 0x1a9a에서 0x40064006 위치의 peripheral register에 접근이 발생하면, 유망한 branch target으로 가기 위해 0x30 값이 사용될 것이다. 이때 caching rule은 T1으로 라벨된다.
3. symbolic execution engine은 trace 1을 추적하면서 execution state가 invalid함을 발견하고 trace 2로 전환한다. Entry 1은 trace 2를 위해 계산되는데, trace 2에서 왼쪽 branch target에 도달하기 위한 constraint가 0x0임을 계산하고 이를 Entry 1에 대한 KB에 캐싱한다.
4. 하지만, trace 2에서 왼쪽 branch target은 잘못되었으므로 실행 흐름이 trace 3로 이동한다. trace 3는 trace 2에서 fork되었으므로 KB도 상속된다. branch 2에서 오른쪽 branch target에 도달하기 위한 constraint 값이 0x20인데, Entry 1과 충돌된다. 따라서 caching rule이 T2로 업그레이드된다. T2는 peripheral register를 읽을 때, 실행 문맥에 따라 Entry를 선택하도록 rule이 업그레이드된 것으로 T1과 차이가 있다. T2에는 각 branch에 대한 두 개의 entry가 생성된다.

2) Dynamic Analysis Phase

그림 2의 가장 오른쪽 그림에 해당한다. 이 과정에서 uEmu는 peripheral register access에 대해 KB에 query를 해서 KB 내 어떤 Entry에 매칭되는지 확인한다.

---

System Design & Implementation

1. uEmu Framework

uEmu는 S2E 2.0 기반으로 개발되었다. S2E 2.0에서는 symbolic execution engine에서 hypervisor 의존성을 없애기 위해 KVM interface로 바꿨는데, KVM interface에서 모든 아키텍처를 관리하는 것은 어렵기 때문에 몇 가지 아키텍처 지원이 없어졌고, 그 중 ARM이 지원 중단되었다.
ARM을 지원하도록 S2E에서 변경한 2가지

1. S2E CPU emulation에서 ARM MCU를 에뮬레이트하기 위해 DBT를 포팅했다.
2. 에뮬레이트된 ARM Cortex-M CPU가 KVM interface를 통해 접근 가능하도록 만들었다.

uEmu 기능 위한 4개의 플러그인

1. InvalidStateDetection : invalid state detection plugin
2. KnowledgeExtraction : invalidity-guided KB extraction plugin
3. InterruptControl : interrupt injection plugin
4. FuzzerHelper : fuzzer integration plugin

2. KB Caching Strategy

1) T0 - Storage Model

T0는 peripheral register의 storage model로, peripheral register는 가장 최근에 적힌 값을 저장하고 read operation 시 저장한 값으로 응답해준다. T0은 다른 caching rule 전에 사용되고, 만약 T0가 틀렸으면 caching rule T1으로 업그레이드된다.

2) T1 - PC-based Matching

T1 matching rule은 greedy 알고리즘 특성을 반영하여 가장 많은 peripheral access를 매칭하도록 했고, 이것으로 path explosion 문제를 피했다. 문맥을 고려하지 않고 PC(pc)와 peripheral address(addr)로만 값을 결정하는데 사용된다.

KB에서 entry는 T1_addr_pc_NULL_value와 같이 인코딩된다. T1_0x40023800_0x10000_NULL_0x00은 펌웨어가 PC 0x10000에서 주소 0x40023800를 읽으면, 유망한 branch target에 도달하기 위해 0x00 값이 사용되어야 한다.

만약 T1이 틀렸다고 입증되면, caching rule T2로 업그레이드된다.

3) T2 - Context-based Matching

동일한 peripheral register의 리턴값이 실행 문맥에 따라 바뀌어야 할 때와 같은 복잡한 상황을 T1 matching rule은 처리하지 못한다.

T2 matching rule에서는 peripheral에 접근 시 T1에서 고려한 PC와 peripheral register에 추가로 실행 문맥을 고려한다. 따라서 실행 문맥을 이어서 만든 hash value를 cache entry 인코딩 시 사용한다. entry는 T2_addr_pc_contextHash_value로 표현된다.

만약 T2가 틀렸다고 입증되면, caching rule T3로 업그레이드된다.

4) T3 - Replay-based Matching

디바이스가 부팅되지 않은 상태인 디바이스 초기화 코드와 같은 경우에는 T2 matching rule을 사용할 수 없다.

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

Code Listing 4에서 실행 문맥이 동일하기 때문에 T2는 UART data register 에서 4개의 read operation을 구별하지 못한다. 따라서 T3로 업그레이드되고, T3는 라인 2에서 "OK\r\n"을 얻기 위해 rf_read_buf()에서 얻어야 하는 UART data register 의 4개의 바이트를 모두 cache entry에 저장한다. 즉, caching rule T3는 T3_addr_pc_null_{v1, v2, ...} 과 같이 인코딩된다. 펌웨어 dynamic analysis phase에서는, 배열 내 값들이 순서대로 사용 되어서 실행 시 동일한 흐름을 따를 수 있다.

평가 결과, 외부 데이터를 수신하는데 사용하는 레지스터 등이 아니면 T3 caching rule은 거의 활성화되지 않았다.

3. Invalid Execution State Detection

이 섹션에서는 InvalidStateDetection plugin이 어떻게 invalid state를 탐지하고, KnowledgeExtraction plugin에 탐지된 invalid state를 알리는지 설명한다.

1) Infinite Loop

펌웨어 실행 시 회복 불가능한 에러가 발생하면, 간단한 infinite loop을 돌려서 스스로 실행을 중단한다. 따라서 infinite loop이 탐지가 된다는 것은 캐싱된 peripheral reading이 잘못되었다는 것이다.

InvalidStateDetection plugin은 각 execution path마다 control flow를 기록하고, 만약 control flow에서 반복적인 cycle이 발견되면 loop이 탐지된 것으로 간주한다.

uEmu는 마지막 BB#_INV1 수의 translation block에서만 infinite loop 발생 여부를 검사한다.

문맥 상에 최소 하나의 symbol이 포함된 경우에만 infinite loop detection이 활성화된다.

2) Long Loop

펌웨어는 peripheral이 특정 연산을 마쳤는지 확인하기 위해 timeout 메커니즘을 통해 peripheral register의 특정 값을 기다릴 수 있다. Code Listing 1에서와 같이 register가 조건에 맞지 않는 값을 가지면 long loop에 들어가서 몇 초 동안 register에 원하는 값이 있을 때까지 기다린다.

InvalidStateDetection 은 long loop을 식별하기 위해 반복되는 사이클을 카운팅해서 지정된 값을 초과하면 long loop으로 간주한다. long loop를 확인하기 위해 지정된 값은 BB#_INV2 로 디폴트 값은 2000이다.

문맥 상에 최소 하나의 symbol이 포함된 경우에만 long loop detection이 활성화된다.

3) Invalid Memory Access

invalid memory region은 주소 공간에 매핑되지 않은 메모리 지역을 의미한다. 주소 공간에 매핑된 지역은 ROM, RAM, system region, external peripheral region이 있으며 이외의 지역은 매핑되지 않은 것이다.
펌웨어가 매핑되지 않은 주소에 접근하는 경우

1. 펌웨어에 버그가 있어서 메모리 에러가 발생하는 경우 → 이 경우는 거의 발생하지 않았음
2. peripheral read operation에서 잘못된 응답으로 학습한 경우 → 이 경우 InvalidStateDetection plugin이 invalid state로 보고하게 된다.

4) User-defined Invalid Program Points

실행되지 않아야 하는 execution point를 분석가가 invalid point로 정의할 수 있다.

4. Invalidity-guided KB Extraction

1) Branch Target Selection and Switch Algorithm

Input :KB
Input :selected_target
Output:KB
symbol <- get_symbol();
KB_Update(KB, symbol);
do
    targets[] <- execute_BB(selected_target);
    if meet termination condition then
        return KB;
    end
    if current state is invalid then
        break;
    end
    if sizeof(targets) == l then
        selected_target <- next_BB(selected_target);
    else
        selected_target <- favorable_target(targets);
        other_target <- non_favorable_target(targets);
        unexplored.push(other_target);
        symbol <- get_symbol();
        KB_Update(KB, symbol);
    end
while true;
// switch execution state
selected_target <- unexplored.pop();
KB_Learn(selected_target);

Algorithm 1은 DFS 기반의 KB_Learn() 함수로, basic block과 현재 KB를 입력으로 받고 심볼릭하게 실행한다. 출력은 학습 후 업데이트된 KB이다.
KB_Learn() 과정

1. 하나의 branch target에서 시작해서 펌웨어를 실행하는 동안 unknown peripheral의 레지스터 값을 읽는다.
2. uEmu는 unknown peripheral의 register에 symbol을 할당해서 branch를 만날 때까지 실행한다.
3. 해당 branch에서 유망한 branch target 도달하는데 필요한 symbol 값을 구해서 KB Update Algorithm(Algorithm 2)를 사용해서 KB를 업데이트한다.
4. 반복문에서 반복적으로 basic block을 처리한다.
   • 종결 조건에 도달하면 현재 KB를 반환한다.
   • 종결 조건에 도달하지 않으면, 현재 execution state가 유효한지 확인한다.
   • 상태가 유효하면, branch에 도달했는지 확인한다.
   • branch에 도달하지 않았으면 다음 basic block을 가져와서 반복문을 계속 진행한다.
   • branch에 도달한 경우, KB에서 유망한 target을 선택해서 다음 branch target으로 설정한다. 유망하지 않은 target은 다음 탐색에 사용하기 위해 스택에 넣는다.
5. 상태가 유효하지 않는 경우 반복문을 끝내고 스택에서 branch target을 꺼내서 해당 지점부터 재귀적으로 알고리즘 실행을 계속한다.

2) KB Update Algorithm

Input:KB
Input:Symbol
new_entry <- solver(symbol);
if new_entry conflicts with KB then
    // 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|new_entry;
end

Algorithm 2인 KB_Update()는 knowledge base update algorithm이다. symbolic execution engine은 현재 branch target로 실행을 이끌 수 있는 symbol의 concrete 값을 계산해서 리턴한다. 리턴값은 새로운 cache entry를 구성하는데 사용되는데, 이 새로운 cache entry가 현재 KB 내에서 충돌되지 않으면 현재 KB에 추가되고, 충돌이 발생하는 경우 caching rule을 업그레이드한다.

3) Termination Condition

리얼월드 펌웨어는 외부 이벤트에 응답하기 위해 infinite loop에서 실행된다. 따라서 knowledge extraction 과정이 끝나지 않을 수 있기 때문에 가장 마지막에 실행된 30,000개의 basic block을 모니터링해서 새로운 basic block에 도달하지 않으면 해당 knowledge extraction 과정이 종료된다. 모니터링하는 basic block 수는 BB#_Term 으로 조절할 수 있다.

4) Reinforced Learning

현재 KB에 매칭될 수 없는 특정 레지스터나 context hash/PC가 cache entry에 없으면 다른 knowledge extraction을 수행하는 방식으로 학습하는 강화 학습 방식이 사용된다.

5. Interrupt Handling

주변장치가 외부와 통신하기 위해 interrupt가 필요하다.

1) Interrupt Delivery

InterruptControl plugin

• 어떤 interrupt가 활성화되었는지 확인하기 위해 NVIC Interrupt Set Enable Register(ISER) 값 체크
• interrupt 순서를 결정적으로 재연하는데 P2IM의 전략 차용 → 활성화된 interrupt를 내부에 정의된 라운드 로빈 방식에 따라 전달한다.

2) Caching Strategy for Interrupts

cache 메커니즘은 한 번에 한 경로만 실행될 수 있기 때문에 에뮬레이트된 경로가 고정되는 문제가 있다. 이 문제를 해결하기 위해 interrupt handler 내부에서 서로 다른 경로를 실행하도록 한다. uEmu는 실행 문맥을 모니터링해서 interrupt context가 탐지되면, symbolic execution engine은 모든 가능한 경로를 탐색한다. valid state로 이끄는 peripheral register에 대한 읽기는 cache entry에 저장된다.
펌웨어 dynamic analysis phase에서는 각 cache entry 내 값이 랜덤으로 선택되어서 interrupt handler 내에서 경로가 랜덤으로 실행되도록 한다.
peripheral에서 status register는 보통 control register에 의존성이 있는데, control register는 일반적으로 T0으로 인식된다. 따라서 interrupt event prediction의 정확도를 높이기 위해 uEmu는 T0 타입의 peripheral register부터 살펴본다.

6. Fuzzer Integration

FuzzerHelper plugin은 AFL이 uEmu와 연결될 수 있도록 하고, 자동으로 fuzzing input point를 찾아서 데이터를 feed 해준다.

1) AFL Accommodation

AFL은 test-case generation에만 사용하고, FuzzerHelper plugin에서 coverage instrumentation, fork server, crash/hang detection을 수행하도록 구현했다.

coverage instrumentation

• AFL과 동일한 path coverage algorithm 구현
• translation block transition을 추적해서 code coverage 정보를 수집하고, shared memory에 code coverage 정보의 bitmap을 AFL과 공유한다.

fork server

• 펌웨어가 test-case의 첫 번째 바이트를 읽을 때를 fork point로 고려
• 실행이 처음 fork point에 도달 시 S2E의 forkAndConcretize 인터페이스 사용해서 모든 execution state 정보 구함
• 디폴트로 fork point는 펌웨어가 data register를 처음 읽을 때로 지정
• 실행이 test-case나 crash/hang를 읽는데 끝나면, 다시 fork point로 roll back해서 클론 후 fuzzing 진행

crash detection

• memory error detector로 지역에 따라 memory 접근 권한을 체크
  • ROM: R+X
  • RAM, peripheral, system control block: R+W
  • other: no access
• HardFault를 crash indicator로 사용 → unrecoverable error

hang detection

• hang 탐지 위해 timeout 10초 설정

2) Data Register Identification

fuzzing 시 공격자가 제어할 수 있는 input channel이 있는데, MCU의 경우 peripheral data register에 해당한다. 따라서 data register를 식별하기 위한 data register의 특성을 다음과 같이 정의했다.
data register 특징

1. T3 register는 대부분 protocol data와 같은 것에서 읽기 때문에 대부분 data register이다.
2. data register는 보통 interrupt handler에서 읽는데, non-interrupt 문맥에서 읽힌다.
3. data register는 빈번하게 실행 중에 접근된다.

만약 한 register가 위의 특성 중 하나를 가지면 data register로 체크된다.

---

Evaluation

Evaluation point

1. 서로 다른 unknown peripheral을 정확하게 에뮬레이트할 수 있는가?
2. 성능이 사용하기에 타당한가?
3. 펌웨어 task code에서 실제 버그를 찾는데 사용할 fuzzer와 같은 분석 도구로 사용할 수 있는가?

실험 환경

• 8-core/16-thread Xeon Server
• 48GB RAM
• Ubuntu 18.04 OS

1. Unit Tests

1) Experimental Setup

P2IM 실험에서 사용한 70개의 펌웨어 샘플 대상으로 실험을 진행했다. 각 unit test마다 먼저 knowledge extraction phase를 돌리고 dynamic analysis phase를 진행했다.

2) Experiment Results

실험 결과
모든 유닛 테스트에서 knowledge extraction phase는 한 라운드 당 1분 이내에 완료된 것으로 knowledge extraction algorithm이 높은 효율성을 보임을 알 수 있다. 70개 샘플 중 5개의 유닛 테스트만 실패하여, passing rate가 93%으로 P2IM(79%)보다 높음을 확인할 수 있다.
Failed Tests in P2IM
섹션 5.3에서 실패 원인을 mis-categorization(MC), invalid assumption(IA), limited exploration(LE)로 분류하여 설명한다.
Failed Tests in uEmu
uEmu에서는 invalidity checking이 가장 중요한 기능으로, 모든 실패한 테스트의 경우 invalid로 인식되지 못한 예상하지 못한 경로를 에뮬레이트하는 경우였다. 70개의 샘플 중 5개의 실패한 테스트의 경우 이 상황에 해당했다. 이 문제는 펌웨어에서 에러 코드를 탐지해서 바로 처리하도록 해서 해결할 수 있다. 각 실패한 샘플에서 invalid point를 추가 후 다시 테스트했을 때 100% passing rate가 나왔다.

2. Fuzzing with uEmu

1) Experimental Setup

평가 시 사용한 펌웨어 (21개)

• P2IM에서 사용된 펌웨어 10개
• HALucinator에서 사용된 펌웨어 2개
• Pretender에서 사용된 펌웨어 2개
• WYCUNWYC 논문에서 사용된 펌웨어 1개
• 상용 디바이스에서 사용하는 펌웨어 샘플 6개

테스트 방법

• 펌웨어 17개: default configuration (manual input X)
• 펌웨어 4개: invalid checking 위해 하나의 user-defined invalid program point 추가
• 비교 위해 P2IM도 동일한 펌웨어 샘플 대상으로 실험 진행

2) Experiment Results

실험 과정
각 펌웨어 샘플마다 knowledge extraction 수행 후, 24시간 동안 fuzzing 진행
결과 평가 관점
1. Knowledge Extraction Performance
KB extraction에서 강화 학습에 필요한 round 수와 KB extraction 전체 시간 측정를 측정했다.
2. Coverage Improvement
uEmu 사용했을 때의 path coverage, uEmu 사용하지 않았을 때의 path coverage를 비교했을 때, QEMU에서 peripheral emulation 없을 때보다 10배부터 140배까지 code coverage 증가했다.
3. Fuzzing

식별된 data register를 입력으로 펌웨어 샘플 내 task code를 퍼징하는데 uEmu 사용한 결과, Steering_Control 에서 double-free로 인한 arbitrary write 취약점과 uTaskerUSB 에서 out-of-bound write 취약점을 새롭게 발견했다. S2E에서의 실행 속도 때문에 P2IM보다 uEmu이 더 느렸다.

False Crashes/Hangs

Steering_Control ,GPS_Tracker ,3DPrinter 에서 발견된 False positive의 경우 uEmu에서의 Direct Memory Access (DMA) 부족이 원인이었다.

3. Failure Reasons in P2IM

1) MC - Mis-categorization of Registers

1. P2IM은 access pattern 기반으로 peripheral register를 분류하는데, P2IM에서의 잘못된 판단으로 peripheral register를 잘못 분류할 수 있다. peripheral register를 잘못 분류하면, fuzzing이 느리게 되고 이는 coverage 향상에 영향을 준다.
2. P2IM은 공간 인접성 기반으로 레지스터를 그룹화하는데, 이는 복잡한 주변장치에 적용하기에 적합하지 않아서 레지스터를 잘못 분류하게 될 수 있다.

2) IA - Invalid Assumption about Registers

P2IM에서는 control bit와 status bit가 겹치지 않는다는 가정으로 control register와 status register를 결합한 레지스터를 모델링해서 사용한다. 하지만 이 가정은 항상 맞지 않는다. 따라서 P2IM에서의 잘못된 인식으로 펌웨어가 중간에 멈추게 한다.

3) LE - Limited Exploration

P2IM에서의 휴리스틱 방법으로는 status register의 값을 적절히 찾을 수 없기 때문에 explorative execution을 사용한다. explorative execution는 레지스터 읽기 지점에서 멈춰서 실행을 기록하는 것이다. explorative execution는 모든 검색 공간을 대상으로 적용할 수 없어서 single bit set만을 가진다고 보고 조사를 하는데, 복잡한 주변장치의 경우 multi-bit status register가 흔하기 때문에 이 multi-bit status register에 대해서는 예상값을 찾을 수 없고, 펌웨어가 멈추게 한다.

---

Limitations

1. invalid checking으로 모든 invalid state를 커버할 수 없다. 이상적으로는 peripheral 연산 후 바로 에러 코드를 체크해서 예외처리를 할 수 있어야 하는데, 펌웨어가 계속 일반적인 실행을 진행하면 계속 branch target을 랜덤으로 선택해서 더 좋은 branch target인지 식별하지 못할 수 있다.
2. data register 특성에 의존해서 data register를 식별하는데, 이 특성을 갖지 않는 data register 케이스도 있었다. 정의한 특성을 따르지 않는 data register가 잘못 분류되면, 퍼저는 입력인 data register을 기반으로 경로에 도달하지 못할 수 있다.
3. 문맥 상에 하나 이상의 symbol이 있는 경우에만 infinite/long loop를 탐지하는데, 루프 내에서 모든 레지스터는 concrete value이기 때문에 concrete value인 루프의 counter가 루프 밖의 symbol에 의존적일 수 있다. 실험에서는 이 케이스가 없었다.

---

Conclusions

논문에서는 펌웨어 내 task code에서 잘못된 I/O interface 입력에 의한 버그를 찾는 목적으로 펌웨어를 에뮬레이트하는 도구인 uEmu를 제안했다.
invalid checking으로 펌웨어가 invalid state에 가지 않게 하고, symbolic execution을 통해 새로운 경로를 탐색한다. knowledge extraction phase에서 peripheral access에 적합한 값을 학습하고 KB에 저장하고, dynamic analysis phase에서 peripheral reading 연산 시 적절한 값을 KB에서 찾아서 응답해준다. 이러한 기술을 사용해서 uEmu는 실제 하드웨어 없이 unknown peripheral 접근 시 적합한 응답을 자동으로 찾아서 펌웨어를 실행할 수 있게 한다.
퍼징 플러그인을 결합해서 퍼징한 결과 리얼월드 펌웨어에서 새로운 버그를 찾을 수 있었다.