2017 Usenix Annual Technical Conference

1. Intruduction

• 낮은 오버헤드로 record / replay를 하려는 많은 시도가 있었다.
  • vm workstation, Simics, UndoDB, TotalView
• 그러나 많은 한계가 존재
  • 전체 가상머신을 기록하고 재생하며 매우 무겁다
  • 커널 수정이 필요해서 보안, 안전성 문제 야기
  • 맞춤형 하드웨어 필요
• 이러한 한계를 극복하는 RR 개발
  • 이미 알려져 있지만, 이전 기술들에서 활용되지않은 기술들을 결합
    1. ptrace를 이용한 system call, signal 기록 재생
    2. 한번에 하나의 스레드만을 실행하여 nondeterministic 데이터 경쟁 방지
    3. 비동기 신호, 정확한 순간에 context switching이 이루어지도록 어플리케이션 진행률을 계산하여 CPU 하드웨어 performance 카운터 사용

2. Design

2.1 Summary

• 상태와 계산의 경계를 식별 후, 경계 내에서 nondeterministic한 모든 소스와 인풋을 기록하고, nondeterministic 소스와 인풋을 재생하여 경계의 모든 계산을 재실행
• 유저 영역의 모든 세부사항을 record / replay
• 재생중에는 최소한의 커널상태만 재생됨.
  • ex) 파일 입출력시 파일 디스크립터는 안열리고, 파일시스템 작업은 수행되지 않으며, 유저 영역에서 재생 가능한 것만 재생
• 경계는 주로 유저 / 커널 사이의 인터페이스로, nondeterministic 인풋과 소스는 주로 시스템콜의 결과나 asynchronous 이벤트의 타이밍

2.2 Avoiding Data Races

• 서로 다른 스레드가 동일한 메모리에 대한 접근을 경쟁하는것은 nondeterminism의 원인
• RR은 이를 해결하기 위해 한번에 스레드 하나씩 실행
• context switching 타이밍이 기록되어야 하는 nondeterministic element
• parallelism이 낮은 워크로드에 효율적

2.3 System Calls

• 시스템 콜은 레지스터와 메모리를 수정하여 유저영역으로 반환하기 때문에 기록되어야함
• ptrace를 이용해 타겟 프로세스의 시스템 콜 모니터링
• 타겟 스레드가 시스템 콜을 위해 커널에 들어가면 일시정지 되고, RR에 알림
• RR은 한번에 하나씩 스레드를 실행하기 때문에 시스템 콜 출력 버퍼를 스크래치 메모리로 리다이렉션 시킴
• 하나의 스레드가 완료되면 스크래치 버퍼의 내용을 유저영역으로 복사하여 경쟁을 제거

• 재생될 다음 이벤트가 한번에 하나씩 실행될 스레드의 차단된 시스템 콜일때 시스템 콜 명령주소에 임시 Break Point 설정
• ptrace를 이용해 Break Point에 도달할 때 까지 실행하고, 도달했을 때 PC를 시스템 콜을 지나도록 진행하고, 기록된 레지스터 및 메모리 내용 적용

2.4 Asynchronous Events

• context switching과 signal 이라는 2가지 비동기 이벤트를 지원해야함
• signal을 통해 context switching을 강제함
• HPC를 통해 어플리케이션 진행률을 측정하고, 많은 명령이 진행되면 인터럽트 시그널 발생시킴

2.4.1 nondeterministic performance counters (register)

• 대부분의 PC는 nondeterministic
• 다행히 "사용 중지된 조건부 분기(RCB)" 라는 오직 하나의 deterministic한 성능 카운터가 존재
• 이를 이용해 실행지점을 식별하고, 범용 레지스터의 완전한 상태와 쌍으로 만듦

2.4.2 late interrupt firing

• 인터럽트 시그널이 즉시 발생하지 않을 수 있음
• 때문에 먼저 몇가지 이벤트를 트리거 하도록 인터럽트를 프로그래밍함
• 그 후에 도달하려는 상태에 대한 PC값에 Break Point를 설정하고, RCB 카운트와 범용 레지스터값이 기록된 값과 일치할 때 까지 BP를 반복적으로 실행

2.5 Shared Memory

• 한번에 하나의 스레드만 스케쥴링 함으로써 RR은 recorded 프로세스가 다른 프로세스, 심지어 커널 드라이버와 메모리를 공유하는것이 가능

2.6 Nondeterministic Instructions

• RDTSC 명령어는 타임스탬프 카운터를 읽는데, prctl API를 통해 트랩, 에뮬레이션이 가능해 상대적으로 처리하기 용이
• RDRAND 명령어는 난수를 생성하기 때문에 처리하기 까다롭지만, libstdc++에서도 한곳에서만 사용하기 때문에 명시적으로 패치해서 해결
• XBEGIN 명령어는 CPU 캐시 상태에 따라 하드웨어 트랜잭션이 성공하거나 실패할 수 있기 때문에 nondeterministic, 다행히 pthreads에서만 사용하기 때문에 사용자 지정 패치를 동적으로 적용
• CPUID는 실행중인 코어의 인덱스를 반환하는데, glibc의 깊은 동작에 영향을 미침. sched.setaffinity API를 통해 모든 스레드가 특정한 고정코어에서 실행되도록 해서 해결

2.7 Reducing Trace Sizes

• 메모리 매핑된 파일을 모든 실행파일과 라이브러리에 대해 복사하면 상당한 오버헤드가 발생하기 때문에 RR은 복사대신 하드링크를 사용
• 이러한 하드링크 복제 작업은 원본이 수정 / 삭제 되지 않는한 본질적으로 시공간에서 자유로움
• RR은 zlib을 이용해 복제된 파일 및 블록을 제외한 모든 추적데이터를 압축

3. In-process System-call Interception

• a novel in-process system call interception technique
• 이전 섹션에서 설명한 시스템 콜 접근 방식은 효과가 있지만 오버헤드가 존재
• Figure 1과 같이 4가지 context switching 때문
• 오버헤드를 줄이려면 공통적인 시스템콜을 처리할때 context switching을 피해야함
• RR에서 공통 시스템 콜을 가로채서, ptrace 트랩을 트리거 하지않고 시스템콜을 수행하고, RR과 공유하는 전용 버퍼에 결과를 기록하는 라이브러리를 타겟 프로세스에 삽입.

3.1 Intercepting System Calls

• RR은 ptrace 트랩을 통해 알림을 받고 시스템콜을 다시 작성하여 intercept 라이브러리를 호출
• intercept 라이브러리에서는 시스템 콜 명령과 stub code(5byte)로 대체
• stub code는 많은 시스템 콜에서 호출 후 결과를 테스트 하는 cmpl $0xfffff001, %eax
• 공통적인 시스템 콜만 intercept 라이브러리로 리다이렉션 하고 나머지는 일반 ptrace - trapping 시스템 콜을 수행하는것으로 대체

3.2 Selectively Trapping System Calls

• what is trap?
  • 소프트웨어엥서 발생시키는 인터럽트 (devide by zero, Segmentation Fault)
• seccomp-bpf를 통해 선택적으로 ptrace 트랩 생성을 회피하는 필터링 생성

• read 시스템 콜의 예제로 solid border는 intercept 라이브러리, gray box는 커널 코드
• RR은 모든 시스템 콜에 대해 ptrace 트랩을 트리거하는 프로세스를 대상으로 seccomp-bpf 필터링 적용

3.3 Detecting Blocked System Calls

• 시스템콜은 때때로 차단될 수 있는데 RR에서 하나씩 실행하는 스레드가 RR에게 알리지 않고 차단되면 전체 recording이 교착상태에 빠질 수 있음
• 때문에 시스템 콜이 차단될 경우 커널이 RR에게 알리고 스레드를 일시정지 해야함
• what is perf?
  • 스레드 스케쥴링이 취소될 때 마다 커널이 발생시키는 이벤트
• intercept 라이브러리에서 perf를 이용해 PERF_COUNT_SW_CONTEXT_SWITCHES를 모니터링 하며 커널이 차단된 스레드에 signal을 보내도록 요청

• Figure 3은 차단된 시스템 콜 read()를 기록하는 모습
• 커널은 스레드 스케쥴을 취소하고, perf 이벤트를 트리거하고 스케쥴 재설정, 시스템 콜 block, recorder에 ptrace 알림을 보냄

3.4 Handling Replay

• record / replay를 동일한 코드를 실행해야 하기 때문에 문제가 생길 수 있음
• 이를 해결하기 위해 intercept 라이브러리는 시스템 콜이 trace buffer를 직접 쓰도록 리다이렉션
• 재생하는 동안 추적되지 않은 시스템 콜은 nop로 대체
• 결과는 이미 trace buffer에 있으므로 post 시스템 콜이 trace buffer에서 output buffer로의 필요한 작업을 수행
• replay는 trace buffer의 결과를 레지스터에서 읽어야함
• 제어 흐름이 record /replay간에 완벽히 일치되도록 조건부 이동 명령을 사용
• 조건은 is_replay 전역변수로 판단
• 시스템 콜에서 인자를 포인터로 처리하는것은 까다로움
  1. 입력버퍼를 추적버퍼로 복사
  2. 시스템 콜의 인자로 추적버퍼의 포인터 전달
  3. 추적버퍼의 내용을 다시 입력버퍼에 복사

4. Results

4.1 Workloads

• All tests run on a Dell XPS15 laptop with a quad-core Intel Skylake CPU (8 SMT threads), 16GB RAM and a 512GB SSD using Btrfs in Fedora Core 23 Linux.
• cp를 제외한 모든 테스팅 타겟은 30초간 실행
• cp는 단일 스레드 이므로 synchronous한 읽기 및 파일시스템 관련 시스템 콜을 집중적으로 사용
• make는 dynamoRio를 빌드하여 -j8 옵션을 통해 병렬 테스트
• octane은 CPU를 많이 사용하는 코드 성능 테스트
• htmltest는 Firefox html 양식을 테스트
• sambatest는 UDP 에코 테스트

4.2 Overhead

• single core : taskset 명령어로 모든 스레드를 single core로 제한하는 오버헤드
• Record / Replay no intercept : 시스템 콜 차단이 비활성화된 오버헤드
• Record no cloning : 블록 복제가 비활성화된 오버헤드
• DynamoRio-null : Dynamic Code Instrumentation 오버헤드 하한 추정치

4.3 Observations

• make의 오버헤드는 상대적으로 높은데, 2430개의 단기 프로세스를 fork / exec 하기 때문
• In-process system call interception은 intercept 라이브러리가 로드된 이후에 작업을 시작하지만, 로드가 완료되기전 최소 80개 이상의 system call이 수행되기 때문에 make가 실행하는 단기 프로세스들에는 제한적

• make 이외의 다른 workload는 매우 안정적인 모습을 보여줌
• make 이외의 다른 workload에서는 record / replay는 2배도 되지않음
• cp의 경우 시스템 콜이 더 작은 작업을 수행하기 때문에 일반실행보다 replay가 더 빠를 수 있음
• octane은 유일하게 멀티코어를 사용하기 때문에 octane의 오버헤드가 RR 전체 오버헤드의 대부분을 차지

• DynamoRio를 통해 code instrumentation을 한것과 RR의 record를 비교
• cp는 유저레벨에서 코드를 실행하지 않아서 오버헤드 거의 없음
• make와 sambatest는 오버헤드가 얼추 유사
• htmltest의 경우 테스트가 동적으로 생성되기 때문에 DynamoRio의 오버헤드가 현저히 높음

4.4 Storage Space Usage

RR Record List

1. 메모리 맵 작업에 사용된 복제(또는 하드링크) 파일 (주로 executable 또는 library로 일반적인 추가공간 차지하지 않음)
2. 복제된 파일 블록
3. 기타 모든 trace 데이터 (이벤트 메타데이터, 시스템 콜 결과)

• space consumption은 실행마다 거의 변동 없음
• workload마다 space consumption rates는 다양하지만, 최신 시스템에서 몇 MB/S 정도는 쉽게 처리 가능하기 때문에 리얼월드에서 trace storage는 문제가 아님

4.5 Memory Usage

• 프로세스가 메모리를 차지하는 비율을 PSS로 수치화
• RR이 사용하는 PSS는 주황색
• cp는 메모리 사용 거의 없음
• make는 single core 사용만으로도 메모리 사용 줄임
• octane과 sambatest는 record시 메모리 사용 증가
• htmltest는 메모리 사용 감소
• 이러한 다양성은 executable의 복잡성 때문에 설명하기 어렵지만, 타이밍 이슈 또는 OS 메모리 관리 휴리스틱등의 이유 때문일 수 있음
• replay시 htmltest를 제외하고 record와 비슷
• htmltest는 test harness를 replay하지 않기 때문에 훨씬 낮음

5. Hardware / Software Design Constraints

5.1 Hardware

• RR은 deterministic한 하드웨어 performance 카운터 필요
• 유저 영역에서 관찰된대로 정확한 retired 명령어 수를 계산할 수 있어야 함
• 일부 X86 CPU 명령어는 nondeterministic한데 이들 중 CPUID, XBEGIN과 같은 명령어들은 패치를 통해 해결
• ARM에서는 nondeterministic한 "load-linked / store-conditional" 접근 방식을 사용하기 때문에 RR을 ARM으로 포팅 실패
• X86에서는 유저영역의 상태관점에서 deterministic하기 때문에 문제 없음

5.2 Software

• RR은 기록되지 않은 프로세스와의 메모리 공유를 하지 않도록 함
• 시스템 콜을 선택적으로 trap 하기위해 seccomp-bpf 활용
• 효율적으로 record / replay 하기위해 deterministic 하게 replay되는 경계를 명확히 식별하고, 해당 경계에서 모든 입력 타이밍과 같은 내용을 record / replay하는게 중요
• RR에서 그 답은 user - kernel 영역 사이의 인터페이스인데 이는 Linux에 적합
• Windows에서는 user - kernel 영역 사이의 인터페이스가 공개되어있지 않기 때문에 적용이 힘듦

6. Related Works

6.1 Whole System Replay

• ReVirt는 전체 가상머신을 실행하고 기록하는 초기 프로젝트
• Vmware Workstation에서 record / replay를 지원했으나 기능 중단
• QEMU / Xen에서도 일부 record / replay 시도
• 전체 시스템을 replay 하는것은 비용문제가 큼

6.2 Replaying User-Space with Kernel Support

• Scribe, dOS, Arnold는 record / replay 기능으로 커널을 확장하여 프로세스 재생
• 커널에 새 기능을 추가하는것은 위험이 있으므로 record / replay를 커널로 옮기는것은 바람직하지 않음

6.3 Pure User-Space Replay

• 유저 레벨에서의 record / replay는 MEC, Jockey, liblog등이 존재
• 이들은 asynchronous 이벤트 타이밍 및 기타 OS 기능을 처리하지 않음
• PinPlay, iDNA, UndoDB 등은 Code Instrumentation을 이용해 asynchronous 이벤트 타이밍을 record / replay
• 이들은 Code Instrumentation을 통해 모든 로드를 측정하기 때문에 병렬기록을 지원하지만 오버헤드가 높음

6.4 Higher-Level Replay

• 언어 레벨에서의 record / replay
• Dejavu는 JVM에 record / replay 기능 추가
• Microsoft IntelliTrace는 CLR 바이트 코드를 Instrumentation하여 매개변수 / 함수 리턴값을 record
• 일반적인 유저레벨에서의 실행을 replay하는것 보다 기능의 범위가 좁음

6.5 Parallel Replay

• 애초에 매우 어려운 문제
• PinPlay, iDNA / Nirvana, SMP-ReVirt, QuickRec등이 있지만 오버헤드가 낮은 parallel record에 대한 최고의 방식은 하드웨어 지원으로 보임

7. Future Work

• 모든 스레드를 single core로 강제 실행하기 때문에 RR 외부에서 나타나는 버그는 재현 불가
• 커널에서 record / replay 하는것은 context swtiching을 기록하는 비용 절감 가능
• 유저레벨에서의 record / replay 성능 향상을 위해 커널영역에서 추가할 수 있는 기본 요소를 찾아야함
• 병렬 프로세스를 기록하는것은 기존 기술에서 영감을 받아 적용 가능해 보임

8. Conclusion

• Code Instrumentation 없이 낮은 오버헤드로 single core 유저레벨 record / replay 실현
• 의도된 목적이 아닌 다른 이유로써 sw / hw 기능들을 통해 구현
• 기존에 없었고 최근에 나타난 seccomp-bpf, Linux 파일 복사 API 이용
• record / replay가 용이한 프레임워크 Mozilla RR을 오픈소스로 공개

P2IM

• Scalable and Hardware-independent Firmware Testing via Automatic Peripheral Interface Modeling(Usenix 2020)
• Processor-Peripheral Interface Modeling
• 펌웨어를 MCU의 펌웨어로 국한
  
  
  

[Open Challenges]

1. Hardware Dependence

하드웨어 의존은 퍼징하는데 delay를 만들고, 병렬처리를 하는데 한계가 존재.
즉, 병렬 퍼징이 힘들다.

2. Wide Range of Peripherals

최근에는 펌웨어의 에뮬레이션 기반 퍼징만 제안이 있어왔음.
그러나 에뮬레이팅된 MCU를 생성하는것은 비 실용적이고, 존재하는 에뮬레이터는 MCU를 지원하지 않음.
때문에 보통 퍼징이나 테스팅을 위해 에뮬레이터를 커스터마이징함.
이른 에러도 많고, MCU의 종류가 많아 현실적으로 힘든 부분이 존재.

3. Diverse OS & System Design

기존의 퍼저들을 펌웨어 퍼징에 적용하기 어렵다.
MCU는 일반적인 OS(Linux)가 아닌 MCU를 위해 설계된 OS를 사용.

4. Incompatible Fuzzing Interface

펌웨어의 모든 인풋은 다양한 종류의, 자신만의 convention을 가진 peripheral을 통해 들어옴.
그래서 일반 퍼저들의 인풋 인터페이스는 MCU 펌웨어에 부적절.

[Processor-Peripheral Interfaces]

• 펌웨어는 직접 off-chip에 접근할 수 없기 때문에 On-chip peripheral만 다룸.
• 레지스터와 인터럽트를 통한 peripheral I/O 인터페이스를 다룸.
• DMA를 통한 peripheral I/O 인터페이스는 제외.
  
  

[P2IM]

1. Abstract Model

- P2IM에 접근할때 펌웨어가 따르는 컨벤션이나 패턴들을 MCU Device 데이터 시트 또는 프로세서 Doc를 통해 수집.
- 이 단계는 전문가들에 의해 이루어지는 오프라인 수작업 단계(only manual step in P2IM).
- 일단 ARM Cortex-M 프로세서만 available.
- 다른 아키텍쳐를 위한 abstract model을 정의하는건 미리 정의된 템플릿이 있기때문에 많은 노력없이도 가능.
- 이 단계는 MCU 아키텍쳐별로 한번만 이루어지는 과정이고, 대부분의 MCU는 동일한 아키텍쳐(ARM Cortex-M)를 사용.
- first, peripheral 레지스터를 4개로 분류후, 각 레지스터별 엑세스 패턴과 엑세스 핸들링 방법을 제공.
    * Control Register(CR)
    * Status Register(SR)
    * Data Register(DR)
    * Control-Status Register(C&SR)
- second, peripheral을 대신해 에뮬레이터가 인터럽트할 방법을 정의.
    * ex) 인터럽트가 인풋이 준비되었다는 신호를 펌웨어에 보내면, ISR(Interrupt service routine)이 동작하고, 데이터 레지스터에 있는 인풋을 읽음
    * 인터럽트 전략은 간단한 방식인 Round-Robin.

2. Model Instantiation

- abstract model을 인스턴스화 하여 분석할 펌웨어를 완전한 모델로 생성하는 단계.
- firmware-specific한 정보를 자동으로 추론.
- deterministic하고 repeatable한 작업.
- 인스턴스화 된 모델은 펌웨어 특화된 정보를 포함.
    1. 식별된 memory mapped 레지스터, 메모리 위치, 타입
    2. 레지스터 타입별 엑세스 핸들링 전략.
    3. enabled 인터럽트 전략.
- peripheral config 관련정보는 불포함.

- peripheral을 에뮬리이팅 하지않은 에뮬레이터에서 펌웨어를 실행.
- 펌웨어가 Processor Peripheral Interface에 접근할때 계속적으로 모델을 인스턴스화 함.

[Implementation]

• QEMU + AFL
• AFL은 유저모드 에뮬레이션만 지원하는데, AFL을 QEMU의 full system 에뮬레이션 모드에 연결되도록 브릿지 해야함.
• TriforceAFL은 full system 에뮬레이션을 지원하기 때문에, TriforceAFL의 코드를 통해 AFL을 QEMU에 연결.
• 퍼저에 의해 생성된 인풋은 DR(Data Register)를 통해 펌웨어에 전달.
• QEMU를 통해 코드커버리지 정보를 수집후 퍼저에 전달.
  
  
  

[Unit Test on MCU Peripheral & OS]

• On-Chip에서 가장 popular한 8개의 Peripherals.
• OS/system libraries(NuttX, RIOT, and Arduino)
• SoCs (STM32 F103RB, NXP MK64FN1M0VLL12, and Atmel SAM3X8E)

[Real MCU Firmware Test]

드론 펌웨어 : MCU기반 Autopilot 컨트롤러. 센서, 라디오, 모터등을 조종하고, PID 제어기같은 컨트롤 알고리즘 구현.

• Quad-copter drone, Pluto drone
  
  
  

• ACC : 레지스터 분류 정확도
• SR : Status Register
• Time : 모델 인스턴스화 하는데 걸리는 시간

[Fuzzing]

• AFL 퍼저말고 다른 퍼저는 고려하지않음.
• Data Register를 통해 인풋을 펌웨어에 전달.
• memory error detector는 NDSS18 What you corrupt is not what you crash에서 소개한 segment tracking heuristic을 사용.

• 코드 커버리지 측면에서 수치적으로 여전히 낮게 보일수있음.
• dead code(사용하지 않는 라이브러리), 복잡한 path 조건에 최적화되지않은 AFL등의 이유를 원인으로 볼수있음.
• 그러나 input value 뿐만 아니라, input duration(얼마나 오래 인풋 값/신호가 지속되는지)이 펌웨어 실행에 영향을 줄 수 있음.
• MCU 펌웨어 퍼징에 대한 유일한 Challenge는 input duration으로 보고있음.

kvm: the Linux Virtual Machine Monitor (Linux symposium '07)

www.kernel.org/doc/ols/2007/ols2007v1-pages-225-230.pdf

[Kernel-based Virtual Machine]

1. 배경

   • 다른 유사한 시스템을 실행하는 컴퓨터를 사용하는 아이디어는 자원을 유틸화 하고 테스팅 하는 목적에 유용하다고 일찍이 인식댐.
   • ibm, vmware, xen등 최근에 기업에서 여러 가상시스템기술을 움직이고있음

2. x86 가상화 확장

   -   x86은 가상화 하기 어려운데
   -   가상화의 중요성을 인식하고 인텔,amd에서 가상화를 좀더 쉽게 만들기위해 x86에 extension들을 추가함
   -   이 extension들은 서로 호환이 잘 안되서 그들은 서로 반드시 유사해야했음
       -   새로운 guest operating 모드 : 시스템이 선택적으로 특정한 명령이나 레지스터접근을 요청하는것 말고는 일반적인 운영모드의 권한을 가지는 guest 모드로 프로세서가 switch 할수있다.
       -   하드웨어 상태 switch : guest모드로 switch할때, 하드웨어는 프로세서 운영모드에 영향을 주는 control 레지스터를 switch한다.
       -   종료 사유를 기록하기 : guest모드에서 다시 호스트 모드로 switch가 발생하면 하드웨어는 switch하는 이유를 기록해서 소프트웨어가 적당한 action을 취하도록 할수있다.

3. 일반적인 kvm 구조

   • kvm은 /dev/kvm에 device node를 열어서 가상머신을 만듬

   • 게스트는 자신의 메모리를 가지고 userspace와 분리댐

   • 가상 CPU는 스스로 스케쥴링 못함

     /dev/kvm

     • kvm은 꽤 전형적인 linux character device로 구성댐

     • 새로운 가상머신 만들고, 가상머신에 메모리 할당, 가상cpu 레지스터 읽고쓰기, 가상cpu로 인터럽트 삽입, 가상 cpu실행

     • user 메모리처럼 커널은 guest address 공간에 형성하기위해 비연속적인 페이지를 할당함.

     • 커널모드 유저모드 이외의 새로운 실행모드인 guest 모드가 추가댐(Figure 2 -> guest mode execution loop 설명)

       명령어 셋의 차이점 조화하기

     • x86 명령어셋과 달리 하드웨어 가상화 extensions는 표준화되지 않음, 인텔과 amd는 명령어, 문법 모두 다름

     • kvm은 커널모듈을 통해 이러한 차이점을 조절함

4. Memory Management Unit 가상화

   • x86은 사용자가 볼수있는 가상 주소를 bus에 접근하기위해 사용되는 물리주소로 변환하는 가상 메모리 시스템을 제공함 => MMU.
     [MMU의 구성]
     • virtual <-> physical 변환하는 radix tree
     • 시스템에 변환오류를 알리는 mechanism
     • page table lookup 을 가속화하는 단일 캐시
     • 독립적인 주소공간을 공급하기 위해 translation root를 변환하는 명령어
     • TLB(Translation Lookaside Buffer)를 관리하는 명령어
   • MMU는 한가지 레벨에서의 변환(guest-virtual => guest-physical)은 제공하지만, 가상화가 요구되는 두가지 레벨(guest-physical => host-physical)에서의 변환은 불가하다.
   • 이에대한 근본적인 해결책은 guest가 제공한 원본 page를 가지고 하드웨어 interaction을 에뮬레이션 하는동안, guset-virtual에서 host-physical로의 변환을 인코딩하는 분리된 page table을 실제 MMU에 나타내는 하드웨어 가상화 능력 사용하는것이다.
   • shadow page table 생산은 증가세이다. 그것은 비워지고 있으며, 변환 실패가 host에 기록되어 missing entry가 추가되었다.
   • guest page table은 원본 메모리에 존재하기 때문에 shadow page table과 동기화하는것은 어렵고 문제가 된다.

   4.1 가상 TLB 실행

    - kvm에서 shadow page table의 초기버전은 성능을 희생하여 코드내 많은 버그를 줄이는 복잡하지 않은 방법을 사용했다.
    - 이러한 방법은 guest가 tlb 관리 명령어를 tlb를 동기화 하는데 사용해야한다는 사실에 의존했다.
    - 그러나 tlb 관리 명령어의 대부분은 컨택스트 스위칭이 대부분이었고, 이는 모든 tlb를 무효화했다.
    - 이것은 shadow page table이 tlb를 refill 하는것보다 좀더 많은 비용을 요구했기 때문에, 다양한 프로세스들의 작업량에 많은 고통을 받는다는것을 의미했다.  

   4.2 가상 MMU 캐싱

    - guest system의 성능을 개선하기 위해, 가상 mmu 실행은 page table이 컨택스트 스위칭을 통해 캐시되도록 하는것을 가능하도록 함으로써 강화되었다.
    - 이것은 code complexity가 증가하는 대신 막대한 성능 증가를 실현했다.
    - guest의 write에 대한 notification을 받기위해 guest page table에 쓰기권한을 protect로 설정했으나, 이것은 추가적인 연쇄적 요구사항을 만들어 이를 충족시켰고, kvm 컨택스트 스위칭 성능이 현재는 적절하게 되었다.
    [요구사항]
        1. 각각의 guest page를 참조하는 모든 writable 변환의 reverse mapping이 유지되어야한다.
        2. x86 명령어 인터프리터를 사용하는 access를 에뮬레이팅 함으로써, 우리는 미리 guest memory와 shadow page table에 미치는 영향을 알 수 있다.
        3. guest는 page table page를 kvm에게 알리지않고 일반 page로 재활용한다.  

5. I/O 가상화

   • VMM은 실제 s/w, h/w에서 처럼 pio(Programmed I/O), mmio(memory mapped I/O)를 에뮬레이팅 하고 가상 하드웨어에서 인터럽트를 받아 시뮬레이션 할 수 있어야함

   5.1 guest측 I/O 명령어 가상화

    - pio를 trap하는것은 복잡하지 않고, mmio를 trap하는것은 꽤 복잡함
    - kvm에서 I/O 가상화는 user 영역에서 진행됨
    - kvm은 user 영역이 guest로 인터럽트를 보내는 메커니즘을 제공함

   5.2 host측 가상 인터럽트

    - guest가 인터럽트를 받을 준비가 되었을때 인터럽트 플래그가 set되고, guest가 준비되면 인터럽트가 보내진다.
    - 이는 kvm이 x86기반의 시스템에 있는 복잡한 인터럽트 컨트롤러들을 에뮬레이팅 하도록한다.

   5.3 Framebuffer 가상화

    - Framebuffer는 memory-mapped I/O 장치의 중요한 부분
    - 전형적인 mmio와 다른 특성(대역폭, 메모리 등가)
    - kvm은 임의의 주소에 비 mmio 메모리를 맵핑하도록 함, 이것은 물리적으로 메모리를 alias하도록하는 VGA windows에 포함됨
    - 또한 framebuffer의 변화를 기록함으로써, display window가 점차 최신화 될수있음  

6. Linux Intergration

   • 리눅스로 통합되는것은 kvm에 중요한 이익을 줌
   • 개발자 측면에서 커널 내 존재하는 기능을 재사용하도록 많은 기회를줌
   • 사용자 측면에서 기존에 있던 리눅스의 프로세스 관리 인프라(top, taskset, kill)를 재사용 하도록함

7. Live Migration

   • 가상화를 진행하는 이유중 하나
   • 이는 한 guest를 한 host에서 다른 host로 쉽게 옮길 수 있도록함
   • 병렬적으로 guest 메모리를 타겟 호스트로 복사함
   • guest page를 복사 후 수정이 발생하면 다시 복사함
   • 마지막에 kvm은 page 로그를 제공하는데 이는 마지막 호출 후 수정된 페이지의 비트맵을 user 영역에 제공함

8. 추후 방향성

   • Guest OS에서 symmetric multiprocessing 지원하기
   • 반가상화 적용하기
   • 메모리 관리 통합하기
   • CPU 스케쥴링 통합하기
   • 새로운 하드웨어 가상화 기법들을 kvm으로 통합하기
   • CPU 아키텍처 확장하기

9. Conclusion

   • kvm 짱