Chasing Elusive Memory Bugs in GPU Programs

기술 요약: GPU 프로그램의 포착하기 어려운 메모리 버그 추적

문제 정의
메모리 안전성 버그, 특히 경계 외(out-of-bounds, OOB) 접근은 GPU 가속 소프트웨어에서 보안과 신뢰성을 모두 위협하는 치명적인 취약점으로 남아 있습니다. NVIDIA의 Compute Sanitizer, cuCatch, GMOD와 같은 기존 도구들은 런타임 동적 분석을 활용하여 OOB를 식출하려고 시도하지만, 다음과 같은 두 가지 근본적인 한계점을 가집니다:

1. 입력 의존적 OOB (Input-Dependent OOBs): 이러한 버그는 특정 입력 조건 하에서만 나타납니다. 런타임 도구는 버그가 실제로 발생해야만 이를 감지할 수 있으므로, 테스트 중에 "적절한" 입력이 제공되지 않으면 이러한 까다로운 오류를 놓치기 쉽습니다.
2. 할당 내 OOB (Intra-Allocation OOBs): CUDA 프로그램에서는 단일 메모리 할당(특히 동적 공유 메모리나 로컬 메모리)을 포인터 산술을 사용하여 여러 개의 별도 데이터 구조로 논리적으로 분할하는 경우가 흔합니다. 기존 도구들은 원시 메모리 할당의 경계만을 추적하며, 이러한 논리적 분할에는 무관심합니다. 결과적으로, 스레드가 부모 할당의 범위 내에 있더라도 자신의 논리적 파티션 외부의 데이터 구조에 접근하는 경우를 감지할 수 없습니다.

또한, 기존의 소프트웨어 전용 도구들은 인스트루멘테이션(instrumentation)으로 인해 상당한 런타임 성능 및 메모리 오버헤드를 발생시키는 반면, 하드웨어 지원 솔루션은 비표준 하드웨어 수정을 요구합니다.

방법론: SCuBA
저자들은 런타임 오버헤드나 하드웨어 수정 없이 입력 의존적 및 할당 내 OOB를 모두 감지하도록 설계된 새로운 컴파일 타임 정적 분석 도구인 SCuBA(Static CUDA Bounds Analyzer)를 제안합니다.

• 핵심 통찰: 저자들은 버그가 없는 GPU 프로그램의 경우, 메모리 할당 크기를 결정하는 변수(통상 호스트/CPU 코드에 존재)와 메모리 접근 오프셋을 계산하는 변수(GPU 커널 코드에 존재) 사이에 의미론적 관계(semantic relation)가 존재한다는 점에 주목했습니다. 이러한 바인딩 관계의 부재는 잠재적인 OKB를 나타냅니다.
• 정적 분석 및 IR: SCuBA는 MLIR(Multi-Level Intermediate Representation) 프레임워크와 CGeist 컴파일러를 활용하여 호스트 및 커널 CUDA 코드를 중간 표현(IR)으로 변환합니다. 바이너리 분석과 달리, MLIR은 논리적 분할에 사용되는 포인터 산술을 포함한 고수준의 의미론적 정보를 유지합니다.
• 제약 조건 생성 (Constraint Generation):
  • 호스트 분석: SCuBA는 메모리 할당 크기(예: cudaMalloc)와 스레드 그리드 차원이 입력 변수로부터 어떻게 유도되는지 모델링하기 위해 표현 트리(Expression Trees, ETs)를 구축합니다.
  • 커널 분석: 스레드 식별자(threadIdx, blockIdx)를 사용하여 메모리 접근 오프셋이 어떻게 계산되는지 추적하고, 포인터 산술을 분석하여 공유 및 로컬 메모리 내의 논리적 파티션을 식별합니다.
  • 논리적 분할: 동적 공유 메모리의 경우, SCuBA는 기본 할당을 추적하고 하위 구조를 나누는 데 사용되는 오프셋을 추적하여 각 파티션의 논리적 크기를 계산합니다.
• SAT 솔버 (SAT Solving): SCuBA는 탐지 문제를 만족 가능성(satisfiability, SAT) 문제로 공식화합니다. 다음을 나타내는 제약 조건을 생성합니다:
  1. CUDA 의미론 (예: 스레드 ID는 그리드 차원보다 작아야 함).
  2. 코드에서 유도된 의미론적 관계 (예: 할당 크기 방정식).
  3. OOB 조건 (오프셋 $\ge$ 할당 크기).
     SAT 솔버(Google OR-Tools)는 모든 제약 조건을 동시에 만족하는 어떠한 합법적인 입력 할당이 존재하는지 확인합니다. 만약 솔루션이 존재한다면, 특정 실행 중에 나타났는지 여부와 관계없이 OOB가 발생할 수 있음을 의미합니다.
• 사용 후 해제 (Use-After-Free, UAF): 이 도구는 활성 할당 세트를 유지하고 접근이 유효한, 해제되지 않은 메모리에서만 발생하는지 검증함으로써 UAF를 감지하기 위해 메모리 라이프사이클을 추적합니다.

주요 기여

1. 포착하기 어려운 버그의 발견: 저자들은 현재의 런타임 도구들을 회피하는 널리 사용되는 오픈 소스 CUDA 프로그램 및 라이브러리에서 입력 의존적 OOB가 존재함을 입증했습니다.
2. 할당 내 OOB 식별: 그들은 메모리 할당의 논리적 분할로 인해 발생하는 새로운 클래스의 버그를 식별하고 정의했습니다. 이는 기존 도구들이 감지할 수 없는 유형입니다.
3. 최초의 정적 도구: SCuBA는 런타임 오버헤드나 하드웨어 변경 없이 이러한 까다로운 OOB 및 할당 내 오류를 감지하기 위해 정적 분석과 SAT 솔버를 결합한 최초의 도구입니다.

결과
저자들은 Kaldi, llm.c를 포함한 인기 라이브러리, 벤치마크 제품군(Rodatia, HeCBench, Indigo), 그리고 CUDA 샘플을 포함한 다양한 20개의 워크로드에 대해 SCuBA를 평가했습니다.

• 감지 능력: NVIDIA의 Compute Sanitizer와 비교했을 때, SCuBA는 새니타이저가 놓친 45개의 OOB를 감지했습니다. 구체적으로, 30개의 미보고된 입력 의존적 OOB와 19개의 할당 내 OOB(기존에는 안전했던 프로그램에 테스트용으로 삽입된 것)를 찾아냈습니다.
• 정확도: SCuBA는 평가된 워크로드 전체에서 제로(0)의 허위 양성(false positives) 및 **제로(0)의 허위 음성(false negatives)**을 기록했습니다.
• 오버헤드: 정적 분석 도구로서 SCuBA는 런타임 성능이나 메모리 오버헤드를 발생시키지 않습니다. 분석 시간은 일회성 컴파일 비용이며, 8밀리초에서 32초 사이입니다. 이때 SAT 솔버가 주요 기여 요소입니다.

의의
본 논문은 런타임 동적 분석에 대한 의존이 GPU 메모리 안전성의 근본적인 병목 현상이라고 주장합니다. 왜냐하면 동적 분석은 특정 테스트되지 않은 입력에 의존하거나 복잡한 논리적 메모리 구조를 가진 버그를 선제적으로 감지할 수 없기 때문입니다. 의미론적 관계와 SAT 솔버를 활용하는 정적 분석 방식으로 전환함으로써, SCuBA는 배포 전에 이러한 포착하기 어려운 메모리 안전성 버그의 부재를 보장할 수 있는 방법을 제시합니다. 저자들은 간헐적인 버그를 놓치는 것이 용납되지 않는 안전 필수 애플리케이션(safety-critical applications)에서 현재의 산업 표준 새니타이저의 한계를 해결하기 위한 SCuBA의 필연적인 진화를 강조합니다.