USENIX Security Symposium (USENIX Security '24) Junho Ahn, Jaehyeon Lee, KangHyuk Lee, Wooseok Gwak, Minseong Hwang, and Youngjin Kwon
If you need a translation, please use the following translation site. https://papago.naver.net/website?locale=ko&source=ko&target=en&url=https%3A%2F%2Fjunhoahn.kr%2Fnoriwiki%2Findex.php%2FBUDAlloc%3A_Defeating_Use-After-Free_Bugs_by_Decoupling_Virtual_Address_Management_from_Kernel
Download https://drive.junhoahn.kr/index.php/s/tx5LgJMeN5BdCdc
개요
BUDAlloc은 User after free버그를 효과적으로 Prevent/Detect하기 위한 방법으로써 기존의 One-time-allocator들의 공통된 한계를 분석하고 그 한계를 극복한 논문이다. 공통된 한계는 Kernel와 User의 분리된 Virtual address management로 인한 Semantic갭으로 주장한다. 이를 위해서 Virtual address management를 Kernel에서 분리하여, User와 kernel이 VA를 eBPF로 Co-design하도록 하여서 문제를 해결하였다.
Motivation
Use after free 버그는 Free된 버그에 Access가 일어나서, 예측하지 못한 행동이 프로그램에 일어나는 버그를 말한다. 간단한 개념에 쉬운 작동방식을 가지고 있지만, UAF버그는 많은 사용 프로그램에서 지속적으로 발생하며, 발생할 경우 치명적인 영향을 프로그램에 미칠수도 있는 버그이다. 일례로, Chromium browser에서 UAF버그는 2011-2013년에서 680건이나 발생한 것처럼, 매우 Mature한 프로그램에서도 빈번하게 일어나는 버그이다.
Importance
UAF버그를 막기 위한 시스템은 크게 Preventor와 Detector로 구분된다. Preventor는 UAF버그를 잡지는 못하지만, malicious한 버그가 일어나는 것을 차단한다. 그에 비해서 Detector는 UAF버그가 발생하자마자, Detector를 한다. Detector가 Preventor를 포함하고 더 유용한 Debugging tool이지만, 구현하기 까다로워 성능상으로는 훨씬 느리다.
기존의 One time allocator (OTA)방식은 Virtual address (VA)를 재사용 하지 않도록 하였다. 이 방식은 TLB cache miss가 증가하고, 한번 사용된 VA를 다시 사용하지 못한다는 점과, intensive한 page table modification이 필요하지만, 안정적이고 다른 방법들에 대비하여 상대적으로 빠른 속도를 제공한다는 장점이 이었다.
Main Idea
Problem
OTA는 매 Allocation과 Deallocation마다 Page table을 설정해주어야 한다는 문제가 있다. OTA는 Virtual address는 재사용하지 않지만, Physical address를 재사용하기 때문에 Allocation에서는 새로운 Virtual address를 Physical address에 할당해 주어야 하고, Free시에는 Virtual address mapping을 Detection을 위해서 page table에서 unset해주어야 한다. 그러나 관련된 메타데이터는 User-level에 있기 때문에 Kernel-level에 존재하는 Virtual address space와의 동기화를 위해서 많은 비용이 요구된다.
기존의 OTA의 구현은 이 한계를 어떻게 극복하느냐에 따라서, Performance와 Memory에 Trade-off가 존재하였다. FFmalloc은 Performance문제를 Free를 Batching함으로써 해결하였지만, Batching으로 인한 큰 Memory overhead가 발생하였다. DangZero와 같은 경우에는 이를 Unikernel를 통해서 Allocation과 Free가 같은 Ring-level에서 작동하도록 하여써, Acceptable한 Performance, memory overhead를 달성하였지만 기존의 커널의 Copy on write나 Proc filesystem과 같은 기능을 사용못한다는 점과 기본적으로 Virtual machine위에서 돌아가기 때문에 VM의 오버헤드가 추가적으로 생긴다는 Unikernel의 한계가 있었다.
논문은 구체적으로 다음 2가지의 Trade-off를 제시한다.
- Performance and memory footprint
- Performance and bug-detect precision
Design
eBPF를 활용하여서, User가 안전하게 Custom page fault handler를 작성할 수 있도록 하였다. Custom page fault handler는 User-level과 공유되는 Metadata를 직접활용해서 바로 Page table을 조작하기에, 커널보다 훨씬 OTA구현에 최적화된 Virtual address stack을 User가 작성할 수 있게 하였다.
- Separating address management
- BUDAlloc은 Virtual address의 관리를 커널에서 분리시켜서, User에 위임하였다. 이를 통해서 중복된 VA메타데이터 관리를 피하고, System call없이 VA에 대한 정보를 Virtual address space에 반영할 수 있도록 하여서, 오버헤드를 없엤다. 또한 이 방식은 Multithreading환경에서, mem_sem과 같은 Global kernel lock을 회피함으로써, Scalability도 올릴 수 있는 장점을 가져왔다.
- Co-design user-level allocator and kernel
- VA가 커널에서 분리되었기 때문에, BUDAlloc은 semantic gap과 상관없이 VA space를 조작할 수 있었다. 또한 OTA에 최적화된 VA space를 Trie를 통해서 구현할 수 있도록 하여서, 성능상의 이점을 가져올 수 있었다.
- Fine-grained locking
- BUDAlloc은 VA space에 대한 구현을 User-level에서 하기 때문에 OTA의 Semantic정보를 가지고 VA space에 대한 locking을 직접 컨트롤 함으로써, Scalability에 유리한 Fine-grained locking구조를 구현 할 수 있었다.
Implementation
User-level components of BUDAlloc
- One-time-allocator
- OTA의 디자인은 기존 OTA들의 디자인을 따라간다. Allocation상황에서 우선 OTA는 Canonical address를 Internal allocator (BUDAlloc에서는 mimalloc)을 통해서 할당받는다. 그후, OTA는 겹치지 않는 새로운 Alias address를 할당 받아서, User-level trie메타데이터에 Alias to canonical에 대한 정보를 기록한다. Free상황에서는 이 역순으로 동작한다.
- LibMM
- LibMM은 Mimalloc과 같이 기존 system call을 사용하던 default memory allocator를 Transparent하게 만들기 위하여 사용되었으며, Systesm call을 후킹해서 적절한 BUDAlloc custom page fault handler가 사용할 수 있는 형태로 가공, Internal allocator에 전달한다.
- Page fault handling
- Page fault가 발생하면, eBPF로 작성된 BUDAlloc custom page fault handler는 주어진 page fault가 Canonical address에 해당하는 page fault인지 아니면 Alias address에 해당하는 Page fault인지를 판별하여 다음의 동작을 수행한다. Canoincal address을 경우에는 Canonical address를 page table에 세팅하며, Alias address일 경우에는 우선 User-level과 공유된 trie구조에서 Valid한 fault인지, 즉 canonical address가 존재하며 처음 일어나는 page fault인지를 확인, 하고 만약 아니면 UAF를 맞으면 Alias to Canonical에 해당하는 mapping을 생성한다.
Kernel-level components of BUDAlloc
- Decoupling address space
- 바로 Kernel의 Page table을 조작할 수 있는 권한을 User에 줘버리면 당연히 엄청큰 Security issue들이 생긴다. 이를 방지하기 위해서 BUDAlloc은 Pesudo-physical-address란 개념을 통해서 이를 해결하였다. User가 보는 Physical address는 실제 Physical address와 1대1일 대응되나, 각 Process마다 Isolate가 된 가상의 Physical address이다. 이를 통해서 Page table에 대한 조작을 하게 함으로써, BUDAlloc은 커널의 Physical address에 해당하는 Information이 Leak되는 상황과, Arbitary memory access/modificiation을 못하도록 방지하였다.
- Custom page fault handler
- BUDAlloc은 eBPF를 사용해서 User가 Custom page fault handler를 작성할 수 있도록 하였다. 이를 통해서 User는 안전하게 User의 Metadata를 가지고 원하는 OTA의 동작을 구현할 수 있게 되었다. 또한 eBPF는 sudo권한 없이도 (CAP_BPF 권한 필요), BUDAlloc에서 요구하는 기능을 구현할 수 있기 떄문에, BUDAlloc이 동작하기 위해서 추가적인 Admin permission이 필요없다는 장점또한 가져왔다.
Optimization, Scalability, and Compatibility에 대한 내용은 논문을 참고
Result
- BUDAlloc은 Security test에서 제일 좋은 UAF버그 Detectability를 보였다.
- BUDAlloc은 SPEC CPU에서 기존 OTA대비 Acceptable한 Memory그리고 Performance overhead의 Trade-off를 보였다.
- BUDAlloc은 PARSEC에서 제일 좋은 Scalability성능 향상을 보였다.
- BUDAlloc은 APACHE와 Nginx를 사용한 Real-world benchmark에서 GLIBC와 비슷한 성능, GLIBC와 비슷한 메모리 오버헤드, 그리고 Scalability를 보였다. 이는 다른 OTA, 그리고 GC기반의 UAF preventor와 비교하였을때도 좋은 성능이었다.
Contribution
- BUDAlloc은 Decoupling address space를 eBPF로 가능하게 하는 기술을 소개하였고, 장점을 입증하였다.
- BUDAlloc은 OTA의 한계를 분석하여 이를 극복할 수 있는 Virtual address decoupling을 소개하였다.
Criticize
- eBPF를 사용하게 함으로써, 예측 하지 못한 버그가 커널에서 발생할 수 있고, 이는 증가된 TCB를 가져올 수 있다.