| Fast Pointer Nullification for Use-After-Free Prevention | |
|---|---|
| Author | Yubo Du University of Pittsburgh yubo.du@pitt.edu Youtao Zhang University of Pittsburgh youtao@pitt.edu Jun Yang University of Pittsburgh juy9@pitt.edu |
| Conference | NDSS 2026 |
| Year | 2026 |
개요
Pointer nullification기법은 Use-after-free버그를 효과적으로 막을 수 있지만, 기존의 PN (Pointer nullification)기법들은 메타데이터 Lookup에 많은 시간이 사용되기 때문에 효율적으로 사용하기는 어려웠다.
이 논문은 Fast Pointer Nullification (FPN)이라는 기법을 제안하여, 최적화된 PN을 통해 UAF 탐지 및 방지의 성능을 향상시키는 것을 목표로 한다.
기존 PN의 핵심 병목이었던 metadata lookup을 단순화하고, 공간적 지역성을 활용한 새로운 저장 구조를 통해 성능과 메모리 오버헤드를 동시에 줄인다.
Motivation & Importance
UAF 버그는 dangling pointer가 해제된 메모리를 참조하면서 발생하는 취약점으로, arbitrary code execution 등 심각한 보안 문제로 이어질 수 있다.
이를 방지하기 위한 다양한 기법이 존재하지만, 성능(Performance), 메모리 사용량(Memory consumption), 보안(Security), 호환성(Compatibility) 측면에서 trade-off가 존재한다.
그중 Pointer Nullification (PN)기법은 이러한 trade-off를 비교적 균형 있게 만족하는 방식으로 평가된다.
Background
Pointer Nullification은 다음과 같은 방식으로 동작한다:
- heap object가 생성될 때 metadata를 생성한다.
- pointer가 특정 object를 가리킬 때, 해당 pointer의 저장 위치를 metadata에 기록한다.
- object가 free될 때, 해당 object를 가리키는 모든 pointer를 찾아 null로 설정한다.
즉, dangling pointer가 생성되는 것을 사전에 제거하여 UAF를 방지하는 방식이다.
하지만 PN 기법에는 다음과 같은 문제가 존재한다:
- pointer → object 관계를 추적하기 위한 metadata lookup 비용이 매우 큼
- CAMP 기준으로 약 62.5%의 성능 오버헤드가 lookup에서 발생
- metadata를 tree/hash 구조로 저장 → cache locality가 매우 나쁨
또한 pointer 저장 위치들은 실제로는 공간적으로 밀집되어 있는 경우가 많음에도 불구하고, 이를 활용하지 못하는 비효율이 존재한다.
Main Idea
이 논문은 Fast Pointer Nullification이라는 기법을 도입하였다.
FPN은 두 가지 핵심 최적화 디자인을 포함한다:
- Constant-time and lightweight metadata address computation: pointer가 속한 metadata 위치를 bit-shift 연산으로 계산하여 O(1) 접근
- Spatial locality 활용: individual pointer storage location 대신 [math]\displaystyle{ 2^M }[/math] byte-aligned memory block 단위로 관리
즉,
- 기존 PN: pointer 단위 tracking
- FPN: block 단위 tracking
을 통해 metadata lookup과 registration 비용을 동시에 줄인다.
Challenge
- PN 방식은 pointer가 어떤 연결관계를 맺는지를 기억해야 한다. 이 metadata lookup 비용이 매우 크다.
- DangNULL: Red-black tree 사용 → O(log n)
- CAMP: 최적화했지만 여전히 높은 비용
- 전체 성능 오버헤드 중 약 62.50%가 lookup에서 발생
- metadata가 spatial locality를 전혀 반영하지 못한다.
- hash / tree 기반 구조 → 메모리 상에 무작위 배치
- pointer 저장 위치는 실제로 인접한 경우가 많음에도 불구하고 이를 활용하지 못함
- cache miss 증가 및 성능 저하 발생
Design
FPN은 기존 PN의 동작 구조를 유지하면서 내부 메커니즘을 최적화한다.
여기서 Buffer는 Allocation된 Heap메모리를, Pointer는 그 Buffer를 가르키는 포인터를 의미한다. 예를 들어서 Pointer A = Buffer; 이 있을때, Pointer B = A;면 Pointer A와 Pointer B는 동시에 같은 Buffer B를 가르키고, 과연 어떻게 이러한 종속관계를 빠르게 추적할 수 있는 자료구조를 만들 수 있을지가 이 논문의 핵심이다.
Region-based Metadata
메모리를 2^N byte 단위 region으로 분할하고 pointer가 속한 region을 다음과 같이 계산한다:
region_id = ptr >> N
각 region은 다음 정보를 포함한다:
- buffer list: 이 리전에 포함된 버퍼들의 리스트를 가지고 있다. 이 리스트는 Buffer info로 관리되며 각 Buffer info는 할당된 메모리들의 Start address와 End address가 있다.
- block list: 이 리전을 가르키는 포인터들이 어떤 Block에 속하는 지에 대한 리스트를 가지고 있다.
이를 통해 metadata lookup을 constant-time으로 수행할 수 있다.
Block-based Pointer Registration
기존 PN는 pointer 저장 위치를 개별적으로 기록하지만 FPN과 같은 경우는 pointer가 속한 block 단위로 등록한다.
block_addr = store_loc & ~(2^M - 1)
동작:
- pointer → region 계산
- region의 block list 접근
- 최근 block들과 비교하여 중복 제거
- 새로운 block만 등록 (이 Region에는 Block 1과 Block 2에 해당하는 포인터들이 있다. 즉 Possible한 Pointer의 Range를 가지고 있는 것)
효과:
- registration 횟수 감소
- metadata 크기 감소
- cache locality 향상
Nullification 과정
object free 시:
- 해당 object가 속한 region 확인
- region의 block list 순회
- 각 block 내 pointer 후보 탐색
- 해당 object를 가리키는 pointer를 null로 설정
- Region에서 Buffer info제거
특징:
- pointer를 정확히 저장하지 않고 block 단위로 탐색
- deallocation frequency가 낮기 때문에 overhead는 제한적
Status Bit (False Positive 방지)
문제: block 단위 탐색 시 pointer가 아닌 값까지 nullify될 위험 존재한다.
해결: shadow memory 기반 status bit 사용
status_table[address >> 3]
- pointer 저장 시 bit 설정
- free 시 bit 제거
효과:
- false positive 제거
- 안전한 nullification
Evaluation
성능 및 메모리 오버헤드
- SPEC CPU 2017 기준으로 분석하였을 경우
- 성능 오버헤드: 약 17.78%
- 메모리 오버헤드: 약 8.34%
- 기존 PN 대비 크게 개선된 사항
- CAMP: ~56% performance / ~173% memory
- FreeSentry: 높은 메모리 오버헤드
Conclusion
FPN은 기존 Pointer Nullification의 핵심 병목이었던 metadata lookup 비용과 pointer registration를 Corased-grained block-based region search로 변경하여 문제를 해결하였다. 그결과, 낮은 성능 및 메모리 오버헤드를 가져올 수 있었다. 논문의 몇몇 가정은 동의하기 힘든 부분도 있었지만, "E.g., Page 5, "ALthough scanning entire blocks during nullification may introduce additional performance overhead, deallocations occur infrequently in most applications", BUDAlloc과 SwiftSweeper를 평가에 반영하였기 때문에 매우 높은 점수를 주고 싶다.
Minor comments:
- Buffer information이 설명없이 그림에만 나와서, 알고리즘을 이해하는데 조금 어려웠다.
Major comments:
- Deallocation frequency가 낮기 때문에 Free성능이 병목이 되지 않는 다고 주장하고 있지만, 이 부분에 대한 명시적인 증거가 필요해 보인다. 추측해 보건데, Deallocation frequency가 낮은 것이 아니라, 단순히 Pointer tracking이 Deallocation시의 Overhead를 감수할만큼 더 많이 Overhead를 줄인 것으로 추측된다.
- Performance overhead관점에서 보았을 경우, FPN은 Pointer nullification의 단점인 Overhead를 확실히 많이 끌어 올린 것은 맞지만, 기존의 FFmalloc과 같은 논문과 비교하여 아직 부족한 부분이 있다. Pointer nullification을 좀더 빠르게 만들 수 있는 방법으로, Block tracking 내부적으로 Hash를 이용하는 방법이나, 아니면 LLVM컴파일러의 도움을 받는 부분도 탐색하면 좋을 것 같다는 생각이 든다.