CuCatch: A Debugging Tool for Efficiently Catching Memory Safety Violations in CUDA Applications

cuCatch: A Debugging Tool for Efficiently Catching Memory Safety Violations in CUDA Applications
Author	Mohamed Tarek Ibn Ziad, Sana Damani, Aamer Jaleel, Stephen W. Keckler, Mark Stephenson
Conference	ACM PLDI
Year	2023

개요

이 논문은 CUDA 애플리케이션에서 GPU의 메모리 버그를 감지 하기 위해서 2-level hashing을 이용한 Pointer tagging기법을 제시하였다.

Motivation

GPU 프로그램도 C/C++ 프로그램처럼 Out-of-bounds access, Use-after-free, invalid free, double free 같은 memory safety violation을 가질 수 있다. 오히려 CUDA에서는 global, local, shared memory가 서로 다른 주소 체계와 접근 규칙을 갖고, 수천 개 thread가 SIMT 방식으로 실행되므로 CPU용 sanitizer를 그대로 가져오기 어렵다.

기존 GPU 도구들은 coverage와 overhead 사이에서 한쪽을 포기했다. Compute Sanitizer는 임의의 GPU binary를 다룰 수 있지만 Dynamic binary instrumentation에 의존해 매우 느리고, GMOD나 clARMOR 같은 compiler 기반 도구는 canary/tripwire 방식이라 non-adjacent overflow나 read-only OOB를 놓치기 쉽다. GPUShield는 bounds checking을 제안하지만 hardware modification이 필요하므로 commodity GPU에서 바로 쓸 수 없다.

Importance

논문은 CUDA의 global/local/shared/generic pointer semantics를 기준으로 bug taxonomy를 나누고, 각 memory space에 맞는 metadata 관리와 check 삽입 방식을 설계한다.

Main Idea

Allocation마다 정확한 base, size, temporal tag를 별도 metadata table에 저장하고, pointer가 실제 memory access에 쓰일 때 이 metadata를 빠르게 찾아 bounds와 tag를 검사하는 것이다. 논문은 이를 Shadow Tagged Base & Bounds, 즉 Shadow TBB라고 부른다.

Shadow TBB는 두 경로를 함께 쓴다. 사용 가능한 upper pointer bit에 BST(Base and Size Table) entry index를 넣을 수 있으면 pointer tag만으로 metadata를 직접 찾는다. 이 공간이 부족하거나 unified memory처럼 pointer를 tag할 수 없는 경우에는 pointer value로 shadow map을 lookup해 BST entry를 찾는다.

성능 측면의 핵심은 모든 memory access마다 비싼 metadata lookup을 하지 않는 것이다. cuCatch는 base pointer analysis로 root pointer를 찾아 metadata를 한 번 읽고 register에 유지한 뒤, 파생 pointer들의 access에는 check만 삽입한다. 이 register-level fat pointer 효과를 ABI나 memory layout 변경 없이 얻는 것이 설계의 중심이다.

Design

Shadow TBB metadata model

Memory Allocation

cuCatch는 allocation 생성 시 BST entry에 base address, allocation size, random tag를 저장한다. Prototype은 upper pointer bit를 8bit로 가정하며, 처음 2^8-16=240개 device allocation은 pointer upper bits로 BST entry를 직접 가리킨다. 그 이후 allocation이나 unified memory는 32B virtual memory region마다 32bit BST index를 저장하는 2-level shadow map을 사용한다.

Memory Deallocation

Allocation이 해제되면 BST tag와 shadow map entry를 invalid 상태로 바꾸어 dangling pointer access가 temporal error로 드러나게 한다. Direct BST-index pointer에서는 delayed UAF도 대체로 deterministic하게 잡을 수 있지만, shadow-map 경로에서는 4bit random tag가 일치하면 놓칠 수 있어 probabilistic detection이 된다.

Compiler backend instrumentation

Compiler instrumentation

cuCatch는 CUDA front-end가 만든 PTX 이후 backend compiler에 instrumentation pass를 추가한다. 분석 단계에서는 memory instruction에서 pointer arithmetic을 거꾸로 따라가며 reaching base pointer를 찾는다. 변환 단계에서는 base pointer에 대해 READMETADATA를 삽입하고, 실제 load/store/atomic 앞에는 OOBCHECK, TAGCHECK, SAFETYCHECK 같은 check를 넣는다.

이 위치를 선택한 이유는 여러 GPU 언어가 PTX로 내려올 수 있고, backend optimization과 scheduling의 효과를 유지할 수 있기 때문이다. 반대로 frontend semantic 정보 일부가 사라져 local buffer 내부 구조 같은 세밀한 bounds를 알기 어렵다는 tradeoff가 생긴다.

Memory-space-specific protection

Global memory

Global memory는 driver가 cudaMalloc/cudaFree 계열 API를 interpose하여 BST와 shadow map을 관리한다. Unified memory는 CPU에서도 pointer가 유효해야 하므로, Top Byte Ignore가 없는 Intel CPU 환경에서는 pointer tag를 쓰지 않고 shadow map만 사용한다.

Shared memory

Shared memory는 kernel 실행 중 free되지 않으므로 temporal tag가 필요 없다. Static shared buffer는 compiler가 알 수 있는 base/bounds로 check하고, dynamic shared memory는 kernel launch parameter로 만들어지는 하나의 region으로 다룬다.

Local memory

Local memory는 thread-private stack 성격을 가지므로 per-thread 31-entry BST를 local memory에 둔다. Pointer upper 8bit 중 5bit는 BST index, 3bit는 temporal tag로 쓰며, function frame entry/exit 시 push/pop 방식으로 stack frame metadata를 관리한다.

Generic pointer

Generic pointer는 실제로 shared/local/global 중 어디를 가리키는지 runtime check로 분기한 뒤 각 memory space에 맞는 check를 수행한다.

Redundant check optimization

cuCatch는 같은 allocation에 대한 straight-line access의 min/max address만 검사하거나, loop-invariant bounds check를 loop 밖으로 hoist하거나, loop iteration 전체의 min/max access 범위를 한 번에 검사한다. Global memory에서는 temporal error를 놓치지 않도록 제거된 OOBCHECK 자리에 TAGCHECK를 남기는 식으로 spatial optimization과 temporal checking을 분리한다.

Result

Coverage 평가는 GPU memory safety bug를 담은 56개 CUDA test suite로 수행했다. cuCatch는 전체 56개 중 71.4%를 detect했으며, baseline 7.1%, Compute Sanitizer 35.7%, GMOD 14.2%, GPUShield 42.8%보다 높았다.

cuCatch Shadow TBB configuration의 geometric mean runtime slowdown은 1.19x, 즉 19%였고, upper pointer bit를 쓰지 않고 항상 shadow map을 거치는 Shadow BB-only configuration은 1.25x slowdown을 보였다. NVIDIA Compute Sanitizer memcheck와 비교하면 cuCatch가 평균 63x 빠르다.

Memory overhead는 고정 비용과 scaling 비용으로 나뉜다. 고정 비용은 BST 32MB와 first-level shadow map 128MB이고, scaling 비용은 필요할 때 할당되는 second-level shadow map으로 32B memory region마다 32bit entry, 즉 12.5% 수준이다. 논문은 realistic-size application에서는 전체 memory overhead가 20% 미만으로 내려간다고 보고한다.

Optimization의 평균 효과는 전체 workload 기준 4% 성능 개선이다. 특히 shared memory strided access가 많은 app5에서는 bounds check 제거가 instruction 수와 scheduling pressure를 줄여 80% 성능 개선을 만들었다.

Contribution

1. GPU memory safety error를 global, unified, shared, local memory space와 spatial/temporal category로 나누어 정리하고, CUDA 특유의 bug coverage 문제를 구체화했다.
2. Shadow TBB를 제안해 tagged base & bounds의 빠른 metadata lookup과 shadow-map 기반 scalability를 결합했다.
3. Backend compiler instrumentation, base pointer analysis, CUDA driver interposition, memory-space별 metadata structure를 묶어 commodity NVIDIA GPU에서 실행 가능한 debugging tool로 구현했다.
4. 56개 error-detection benchmark와 176개 performance workload를 통해 기존 GPU memory safety tool 대비 더 높은 coverage와 낮은 runtime overhead를 제시했다.

Criticisms

우선 논문을 읽기가 너무 힘들었다. Implementation이 Convention과는 다르게 Design이 나왔으며, 불필요하게 과장된 표현들 + 필요 없는 정의들이 논문을 따라가는 흐름을 방해하였다. 특히 논문이 Top-down방식이 아니라 Bottom-up방식으로 쓰여진 부분들도 많았으며, 뒤를 읽어야 앞을 이해할 수 있는 표현들도 많아서 Writing quality가 조금 떨어지는 느낌이 들었다. 또한 논문에서 제시한 방법들은 Sanitizer 방법론에서 많이 Discussion된 부분들이다. 또한 Globa, Shared, Local, Generic으로 나뉘는 것은 좋은데, 각각 어떻게 막고 있는지 표라도 있었으면 더 쉽게 이해할 수 있었을 것 같다.

Conclusion

이 연구는 GPU memory safety debugging을 "CPU sanitizer를 GPU에 포팅하는 문제"가 아니라, CUDA memory space와 compiler/runtime boundary에 맞춘 metadata 설계 문제로 보게 만든다. cuCatch는 Shadow TBB, base pointer analysis, backend instrumentation, driver support를 결합해 높은 bug detection coverage와 평균 19% runtime overhead를 동시에 달성할 수 있음을 보였다.