개요
FreeGuard는 Secure하고 Performance를 동시에 추구하는 Memory allocator으로서, 기존의 Dieharder와 BSD Allocator의 단점을 분석하여 그에 따른 해결책을 내놓았다.
Motivation
C/C++ 처럼 많은 Unsafe한 Langauge들은 메모리 버그에 취약하다. 이를 Memory allocator의 디자인으로 막을 수 있다.
Importance
기존의 있는 방식인 ASLR, Bum-pointer allocator, Sequential allocator, BiBOP allocator, OpenBSD Allocator, Linux Default Allocator들은 보안적인 요구와 성능에 대해서 Trade-off가 있었다.
Main Idea
Background
- Sequential allocator (Bump-pointer allocator)
- Linux의 Slub allocator, 혹은 Default MALLOC구현체에서 사용하는 방법으로 Freelist를 만들어서, 해제된 메모리가 다른 해제된 메모리를 가르키는 Freelist를 Data에 구현하는 것이다. 대부분의 Allocator들이 Metadata가 Object에 존재한다. 이 방식은 freelist찾기가 쉽고, Metadata관리가 쉬어서 빠른 성능을 보이지만, 한편으로는 Metadata가 그대로 노출되어 있기때문에 보안적으로 취약하다.
- BIBOP Allocator
- BIBOP Allocator는 bitmap을 사용하여서, free된 오브젝트를 관리하는 방식이다. 각각의 비트맵은 같은 오브젝트 크기를 가지는 bags들을 가르키며 각 bags들의 오브젝트들이 free되었는지를 관리한다. 메타데이터가 오브젝트 내부에 위치한 Sequential allocator와는 다르게 메타데이터가 오브젝트와 분리되어 있어서, 보안적으로 우수하다. 그러나 bitmap을 관리하는 오버헤드가 커서 성능적으로 매우 느리다. 예시로 DieHarder와 같은 경우에는 수십%에서 최대 10x까지 오버해드가 발생하는 것으로 리포트된다.
Idea
BIBOP스타일 처럼 각각의 bags들은 같은 크기를 가지고 오브젝트들은 bags들에 존재한다. 그러나 Free된 오브젝트를 관리하기 위해서 bitmap을 사용하는 것이 아니라 새로운 Memory layout design을 통해서 Sequential allocator처럼 freelist를 통해서 관리하도록 하였다. 이 freelist는 sequential allocator와는 다르게 분리되어 있기 때문에 보안적으로 우수하며, 성능적으로도 우수하다.
Design
- Managing Small Objects
- 분리된 freelist를 사용하며, heap layout를 정교하게 작성하여서 metadata접근이 빠르게 가능하도록 하였다. FreeGuard는 메모리를 크게 잡아두고, 여러 부분으로 쪼개서 사용하였다. 각각의 SuperHeap은 내부적으로 subheap이 존재하고, subheap은 per-thread로 존재하도록 디자인 하였다. Super heap (64 * 128MB)는 subheap (64MB) 128개로 이루어져 있으며, 각각의 sub-heap은 다시 4MB의 Bag들로 이루어져 있다. 각각의 4MB Bag은 다시 2, 4 ... 512KB 크기를 가지는 오브젝트를 담도록 설계되었다. 이 layout은 constant time에 metadata를 찾을 수 있도록 하는데, 이유는 우선 MMAP을 사용해서 크게 SuperHeap들을 나누어 두고, thread idex로 subpage를 찾기 때문이다. 따라서 Address주소만으로 해쉬와 같은 방법 없이 Metadata를 탐색할 수 있다.
- Randomization
- Guard page들이 Random하게 각각의 bag사이의 페이지들에 삽입되게 하였다. 또한 Freelist와 같은 메타데이터의 위치를 랜덤하게 설정하여서 추가적인 보안위협에 대처하였다.
- Managing Large Objects
- 512KB를 넘어서는 큰 오브젝트의 경우에는 MMAP을 사용하여서 구현하였다. Large page는 MMAP을 통해서 ASLR과 Guard page를 사용하도록 하여서, 보안적인 위협에 대처하였다. 이는 DieHard와 OpenBSD와 같은 정책이다. 각각의 오브젝트의 크기를 추적하기 위해서 hash를 사용하였다.
Result
성능은 유사하나, Memory overhead는 평균 20% 최대 3x 정도 벌어지는 결과가 나왔다.
Reasons for the memory overhead
- FreeGuard는 분리된 freelists와 bump pointer를 사용하며, Randomization을 위해서 4개를 유지함
- ASLR을 위해서 메모리에 Fragmentation이 일어나서, free할경우 Re-utilization이 떨어질 수 있음
- BIBOP Allocator의 Fragmentation도 중요한 Issue일 것 같은데... 논문에는 안 나와 있어서 확신할 순 없음
- 그외에, 자잘한 카나리로 인한 오버헤드, Large memory allocator의 Fragmentation이슈들이 있다.
Conclusion
Limitation
- Freelist가 노출된다는 점. 이는 /proc/PID/maps를 확인함으로서 더욱 잘 알 수 있다. Randomization이 이를 막긴 하지만 한계가 있을 것임
- 메모리 오버헤드가 예측 가능하지 않으며 특정 케이스에서는 매우 큼. 즉 Secure, Fast, Memory overhead의 trade-off를 생각해야 함
- 기존 Work과 비교해서, Use-after-free버그는 못 막고(vs CLING) Randomization은 더 취약함(vs DieHarder, OpenBSD)
Advantages
시스템 콜 수를 줄이고, Memory layout을 통해서 Constant metadata access가 가능하게 하여서 빠르고 안전한 메모리 Allocator을 만들어 기존 Work들을 Advance한 Memory Allocator을 만들었다.