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

Conclusion

논문에 명시된 대로, 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되었다고 표시될 위험은 없지 않을까?

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.