KSplit: Automating Device Driver Isolation

2022 OSDI
Yongzhe Huang, Vikram Narayanan, David Detweiler, Kaiming Huang, Gang Tan, Trent Jaeger, Anton Burtsev

개요

Ksplit은 Kernel과 Device driver의 Static analysis를 통해서, Isolation된 환경에서 동작하는 동기화된 커널 드라이버를 생성해난다. KSplit은 Driver와 Kernel이 공유하는 State들을 찾아내어서, Shared state들에 대한 정보를 포함하는 Interface Definition Lanauge (IDL)로 작성하였다. 작성된 IDL은 나중에 Isolated subsystem과 User가 통신하는데 사용되었다. 이를 통해서 KSplit은 효율적으로 Kernel state을 관리하여 기존 Isolation model대비 성능 향상과, 개발자 편의성을 동시에 달성할 수 있었다.

Motivation

Device driver는 현재 커널에서 Vulnerabilities가 발생하는 주요한 원인이 되고 있다. Device driver isolation은 여러 Challenge가 있다.

• Shared state를 어떻게 관리할 것인가.
• Isolation은 어떻게 구현할 것인가.

Shared state관리는 특히 Isolation보다 어렵다. 예를 들어서 Kernel A가 실행중에, Device driver B가 실행되어서, 커널 A의 state들을 오염시켰다고 해보자. 과연 오염된 State들은 어떻게 Detect할 것이며, Concurrency는 어떻게 해결할 것이며, State들이 어디까지 접근가능한지와 같은 매우 많은 Factor들이 Isolation에 관여하게 된다. 너무 크게 Isolation도메인을 잡으면 동기화로 인해서 Bottleneck이 걸릴 것이며, 너무 작게 잡으면, State concurrency에 문제가 생길 수도 있다. 이러한 작업을 Automatically하게 하는 노력들은 따라서, 개발자의 개입을 많이 요구하거나, 아니면 다양한 Limitation들이 있어왔다. ("다양한"에 해당하는 문제는 논문을 참고)

Importance

현재 Shared state을 관리하기 위한 기법들은 Manual analysis방식을 채택하는 것이 주이지만, 아주 많은 코드 분석을 필요로 하는 일이다. 이러한 일을 자동화 한 기존의 방식들도 작은 부분만을 자동화 시켰다.

MainIdea

KSplit은 커널 state들 중에서, 디바이스 드라이버와 공유되고 있는 모든 곳을 찾는다.

ndo_start_xmit(struct sk_buff *skb, struct net_device *netdev)

와 같은 경우에는, skb와 netdev가 를 통해서 접근 가능한 모든 Kernel state들을 재귀적으로 찾아낸다. 이를 통해서, cross-domain invocation에서 필요한 state들을 동기화 하게 된다.

Main Idea는 간다할지라도, 구현은 여러 이유로 인해서 복잡하다.

• Large number of fields: 구조체의 각 field들을 어떻게 Isolation할 것인가? 예를 들어서, sk_buff와 같은 경우에는 재귀적으로 3,132개의 field들에 접근 가능하지만, 커널과 디바이스 드라이버가 jontly하게 사용하는 부분은 단지 52개일 뿐이다.
• Complex memory reference: 구조체의 사용은 복잡한 메모리 참조로 인해서 일어나는 경우가 많다. 예를 들어서 sk_buff와 같은 경우는 head와 data field를 통해서 실제 packet데이터를 참조하고 있다.

위 두 문제를 해결하기 위해서 field-sensitive data-flow analysis를 채택하였다.

• Complexity of the kernel: kernel은 data-flow analysis를 채택하기에는 너무 복잡하다.

우선 Coarse하게 dependency를 체크후 fine-grained한 알고리즘을 적용하였다.

• Concurrency and parallelism: Kernel과 Driver는 병렬적으로 작동하는 환경에 대비하기 위해서, 내부적 그리고 서로의 Concurrency컨트롤을 위해서 Atomic, Lock과 같은 방식을 사용한다. 이러한 Concurrency control이 내부적으로 필요한 것인지 서로 상호작용에서 필요한것인지를 파악해서 분리하여야 한다.
• Complex C Idioms: 디바이스 드라이버는 포인터 관리를 위해서 C의 Raw-pointer 기능을 이용하여 다양한 작업을 수행한다. 예를 들어서, array의 크기를 size로 나타내거나, list데이터, recursive한 포인터의 사용, tagged unions, opaque pointer와 같은 예를 들수 있다.

Design

Alias analysis

같은 메모리 오브젝트를 가르키는 변수들을 추적하는 것을 alias analysis라고 한다. Alias analysis은 undecidable문제로 알려져 있다. 이 문제를 해결하기 위해서 Previous work인 PtrSplit을 이용하여 이문제를 해결하였다. KSplit은 parameter tree를 통해서 function들 간의 memory dependency를 추적한다.

Shared and Private Split

커널과 드라이버가 공유하는 struct field를 찾아내는 것또한 중요한 작업이다. 그러나 interrupt handler로 인해서 Control flow graph를 그리는 것은 힘든 일이다. 또한 커널의 구조는 매우 복잡하다. 이를 위해서, KSplit은 Step-by-step 방식으로 searching space를 좁혀가는 방식을 사용하였다. 우선 (1) 구조체중 kernel, driver가 동시에 이용하는 구조체를 찾는다. (2) 커널과 드라이버의 함수중 그 구조체를 argument로 받는 함수를 찾는다. (3) 함수 내부적으로 field에 대한 접근을 추적한다. (4)만약 커널과 드라이버에서 동시에 접근하면 그 필드를 shared로 표시한다.

우와 같은 방식은 두개의 가정을 먹고 들어간다. struct의 type (즉 이름)이 type casting이 일어나지 않는다는 가정과, 각 type이 만약 공유된다면, 모든 함수에서 공유된다는 가정이다. 이 두 가정으로 인해서, under-approximate와 over-approximate가 일어나지만, 논문에서는 대부분의 경우 논문의 가정을 따른다고 defence하고 있다.

Cross-domain synchronization

KSplit이 데이터를 동기화 하는 방식은 Worklist-based 알고리즘을 사용한다. worklist-based알고리즘은 간단한 breath-first-search를 통해서 함수의 parameter로 들어온 인자가 READ접근인지 아니면 WRITE접근인지를 파악한다. 만약 READ이면, 함수를 부를때, copy해서 넘기고, WRITE이면 함수가 다시 리턴될때 COPY해서 넘기게 된다. 그러나 만약 이러한 접근이 shared된 변수가 아니면, 동기화가 필요 없음으로 copy를 통해서 부르지 않고 직접 부르게 하였다.

Handling Critical Section

Lock과 Atomic으로 보호받는 Critical section을 안전하게 동기화 시켜야 한다. CFG를 이용해서, Critical section에 들어가는 함수와 나가는 함수를 파악하였다. 파악된 Critical section에서, 수정되는 모든 변수를 추적하였다. 추적된 변수들 중에서, Shared state인 변수들은 READ일 경우 Critical section에 들어갈때 동기화가 일어나도록 하였으며, WRITE의 경우에는 Critical section에서 나올때 동기화가 일어나도록 하였다.

Low-level Kernel Programming

C는 Raw pointer를 통해서 포인터를 접근가능하게 한다. KSplit은 LXDs와 같은 방식으로 이 문제를 해결하였다. LXDs와 다르게 KSplit은 Static analysis를 사용하여서 최대한 IDL을 자동으로 생성하도록 하였다. CCured를 사용하여서, Pointer를 wild, sequential, safe로 분류하여, safe는 singleton, sequential은 array나 구조체 포인터, wild는 type cast operation으로 type information으로 infer하였다. 각각의 Pointer classification에 대한 자세한 디자인은 논문을 참조.

Implementation

KSplit은 LLVM위에서 작성되었다. KSplit을 통해서 생성된 IDL은 LVDs를 통해서 해석되어서 적용되었다. 즉 Virtualization을 이용한 Isolation은 LVDs를 통해서, IDL Generation은 KSplit으로 하였다.

Result

• KSplit은 공유되는 데이터를 분리한다. ixgbe드라이버의 경우에, shared fields가 million에서 3000정도로 줄었다.
• KSplit은 manual work을 최소화한다. ixgbe드라이버의 경우에, 27000줄이지만, Manual하게 수정한 코드의 양은 IDL에서 53줄 그리고 Driver에서 19줄이다.
• KSplit은 성능에 영향을 최소화 하였다. ixgbe와 같은 경우, UDP load를 측정하는 Memaslap을 사용한 결과에서, 대략 1-4 스레드의 경우 5.4 에서 18.7%정도의 성능 하락을 10개의 스레드 이상에서는 UDP bandwidht가 saturated되며, 비슷한 결과를 얻었다.

Contribution

• LXDs -> LVDs -> KSplit으로 이어지는 대보를 완성함. (완성이 아닐 수도 있음)
• LXDs에서 IDL을 이용한 Device driver isolation은 VMFUNC로 성능을 향상시킨 LVDs그리고 최종적으로 Static analysis로 IDL생성을 자동화한 KSplit으로 이어진다.
• Device driver isolation에서 state split문제를 어떻게 자동화 할 수 있을지에 대한 철저한 분석과 해결책을 제시한다.
• Concrete하고 납득가능한 성능 분석을 제공한다.

Limitations

논문에 명시된 대로, KSplit은 다음과 같은 Attack은 방어하지 못한다.

• Resource exhaustion
• Deny of service
• Protocol violation (Unregister itself from the kernel)
• Use-after-free와 같은 state consistency problem
• Address leak
• Speculative execution, side-channel attack

다음과 같은 문제가 있을 수도 있다.

• 논문에서는 over-approximate하게 shared state를 추적하는데, 이러할 경우, 모든 object가 taint되었다고 표시될 위험은 없지 않을까?
• Manual effort를 수정하는 LOC가 적어서 적다고 하였다. 그러나 이 LOC가 담지 못하는 코드 분석과, Optimization과 같은 것이 있지 않을까?
• LOC로 Manual effort를 측정하는 것이 맞을까? (사실 다른 방법이 없을것 같긴 하다.)
• 만약 동기화 과정에서 문제가 생겨서 Shadow copy본이 일치 하지 않거나, revert를 시켜야 하는 경우는 얼마나 생기는가. 이러한 조건은 어떻게 찾는가? 그리고 revert는 어떻게 시킬 것인가.

Reference

1. Shen Liu, Gang Tan, and Trent Jaeger. PtrSplit: Supporting General Pointers in Automatic Program Partitioning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17), pages 2359–2371, 2017.
2. http://junhoahn.kr/noriwiki/index.php/LXDs:_Towards_Isolation_of_Kernel_Subsystems