Junho Ahn, Kanghyuk Lee, Chanyoung Park, Hyungon Moon, Youngjin Kwon IEEE S&P 2025
Download: https://drive.junhoahn.kr/index.php/s/rSitKKfcz79PX5t
개요
Garbage collection을 이용한 Memory sweeper는 UAF버그를 막는데 효과적이다. 그러나 기존 논문들은 Scalability, Stop-the-world pause, CPU Utilization측면에서 문제가 있었다. 이 문제를 해결하기 위해서 본 논문은 On-demand marking과 Delta-marking을 고안하고, 이를 효율적으로 구현하기 위해서 eBPF를 사용한 Express memory path를 구현, 최종적으로 State of the art의 UAF Preventor의 성능을 보였다.
Motivation
Background
Garbage collection을 이용한 Memory sweeper는 Explict한 Free정보를 이용하여서, C나 C++의 UAF버그를 효율적으로 막기 위한 방법을 말한다. Memory sweeper는 따라서 기본적으로 Garbage collection의 방식을 따라간다.
Garbage collection은 근본적인 문제로 Stop-the-world pause가 존재한다. 이는 Marking과 Application의 흐름이 동시에 실행되어서 발생할 수 있는 문제인 Pointer relocation를 막기 위한 방식이다. Pointer relocation은 Marking thread가 체크한 영역에 새로운 포인터가 생기거나, 다른 Marking되지 않은 영역에서 Pointer가 움직임으로서 발생할 수 있는 Concurrency문제를 말한다. 이를 해결하기 위해선 Application의 수행을 Marking동안 멈추어야 한다. 기존의 MineSweeper: A “Clean Sweep” for Drop-In Use-After-Free Prevention와 같은 논문들은 이를 해결하기 위해서 TCB를 Relax시켰으나, 이러한 방식은 Corner case에 노출되는 문제가 있었다.
Three-design problem in the Memory Sweeper
결국 위 Stop-the-world pause로 인하여 다음의 문제가 발생한다.
- Stop-the-world: Stop-the-world그 자체로 문제가 된다. Stop-the-world로 인하여 C나 C++프로그램에 Unexpected한 Application pausing이 계속 발생하며, 이는 C나 C++로 작성된 프로그램들이 Latency sensitive한 경우가 많다는 점을 고려하였을때, 치명적인 문제이다.
- High CPU Utilization: 기본적으로 Marking을 수행하기 위해서 CPU Utilization을 만히 먹으며, Marking thread들이 Synchronization을 위해서 사용하는 Busy waiting또한 High cpu utilization의 주범이다.
- Low Scalability: GC는 Dirty한 Page들을 Skip하기 위해서 Dirty page를 읽어야 하는데, 여기서 in-kernel global lock에 contention이 발생하면서 Kernel operation serialization이 발생한다. 또한 Application을 멈추는 Stop-the-world도 Serialization point가 되어서 Scalability에 영향을 미친다.
Main Idea
- On-demand marking: Memory sweepeing을 별도의 스레드에서도 처리하지만, 만약 Pointer relocation문제로 인해서 오브젝트가 Marked zone에서 Unmarked zone으로 움직이는 경우, 그 오브젝트를 포함하는 Page를 On-demand하게 Marking하여서 Stop-the-world없이도 Pointer relocation문제를 제거하는 알고리즘을 사용하였다.
- Delta-marking: 기존 Garbage collection의 Drity-bit tracking에 더하여, Free된 포인터의 정보를 이용하여서 더욱 효과적으로 Garbage collection의 횟수를 줄일 수 있는 알고리즘을 제시하였다.
- eXpress Memory Path: 위의 On-demand marking과 Delta-marking은 필연적으로 Kernel의 정보인 Dirty-bit과 page fault handler와의 상호작용이 필요하다. 이를 기존의 proc file system이나 Userfaultfd와 같은 시스템을 사용하면 시스템의 성능이 저하되고 CPU Utilization이 올라간다. 이 문제를 해결하기 위해서 eBPF를 활용한 새로운 Kernel memory path인 eXpress Memory Path를 제시하였고, 이를 활용하여서 Memory Sweeping의 성능을 개선하였다.
Design
Memory Sweeper Algoraithm
- On-demand marking
- Delta-marking
eXpress Memory Path
Evaluation
본 논문은 기존 시스템과 비교하여서 매우 빠른 성능, 메모리 사용량 감소, CPU Utilization감소, Scalability의 증가를 이루었다.
SPEC CPU 2006
| SwiftSweeper | FFmalloc | MarkUs | MineSweeper | MS-STW | HushVac | HushVac-opt | |
|---|---|---|---|---|---|---|---|
| Time | 1.04x | 1.02x | 1.15x | 1.09x | 1.11x | 1.19x | 1.12x |
| Memory | 1.17x | 2.07x | 1.24x | 1.36x | 1.32x | 1.58x | 1.52x |
| CPU Utilization | 1.01x | 1.00x | 1.11x | 1.10x | 1.11x | 1.89x | 1.30x |
SPEC CPU 2006결과를 통해서 SwiftSweeper가 기존 Work대비 매우 효율적이라는 것이 증명하였다.
Conclusion
본 논문은 Memory Sweeper를 최적화한 논문이다. On-demand marking과 Delta-marking과 같은 경우는 기존의 Garbage collection에서 빌려온 방식이여서, 비록 C/C++에 적용시키는 방법을 제시하였다고 하지만, 매우 독특한 Design point라고 하기는 힘들다. 그러나 On-demand marking과 Delta-marking을 적용시키면서 발생하는 Challenge인 Kernel과 User의 Context switching으로 인한 오버헤드를 eXpress Memory Path라고 하는 새로운 기술을 제시하고, 이를 통해서 해결한 점이 본 논문의 독창적인 부분이다.
또한 이 논문은 다음과 같은 한계가 존재한다.
- eBPF를 사용하여서 커널을 확장하였기 떄문에, 기존의 커널 시스템 대비 피할수 없는 TCB증가가 있다. 그러나 이점은 커널 프로그래머의 TCB이지, User-level의 TCB가 아니라는 논리로 방어 가능하다.
- 본 방식은 UAF만 방어가능하며, Sptial bug와 같은 문제는 방어하지 못한다.