-
Notifications
You must be signed in to change notification settings - Fork 6
Optimuzz
본 문서를 이해하기 위해 다음 문서들을 먼저 읽어보는 것을 권장한다.
또한 본 문서에서는 우리말 쉬운 전문용어를 사용한다. 본 문서에서 사용되는 컴퓨터 과학 전문용어 중 일부를 소개한다.
- 덮이 (Coverage): 덮이는 프로그램의 입력이 실행한 프로그램 지점의 집합이다. 입력이 프로그램 지점들을 얼마나 덮었는가를 나타낸다.
- 번역 (Compilation): 번역이란 한 프로그램을 다른 프로그램으로 변환하는 것이다. 예를 들어 C++ 프로그램을 기계어 프로그램으로 변환하는 것을 번역이라 할 수 있다.
- 오번역 (Miscompilation): 프로그램의 의미를 보존하지 못하는 번역을 말한다.
Optimuzz는 컴파일러 최적화 과정에서 발생하는 오번역 버그를 효과적으로 탐지하기 위한 프레임워크이다. 최신 컴파일러는 매우 크고 복잡하며, 성능 향상과 새로운 언어 기능 지원을 위해 최적화 기능이 계속 추가되고 수정된다. 이러한 지속적인 변화 속에서 최적화의 올바름을 보장하는 것은 매우 어려운 일이다.
Optimuzz는 이러한 문제를 해결하기 위해 지향성 반투명 퍼징(Directed Grey-box Fuzzing)과 번역 검산(Translation Validation)을 결합한다. Optimuzz는 특정 컴파일러 최적화 규칙을 실행하는 입력 프로그램을 생성하고, 해당 입력 프로그램에 대해 최적화가 올바르게 일어났는지 검사한다. 실험을 통해 Optimuzz는 LLVM과 TurboFan 컴파일러를 대상으로 기존 방식보다 뛰어난 성능을 입증했고 다수의 새로운 버그를 발견했다. LLVM은 C/C++/Rust 등 다양한 언어의 컴파일러로 사용되며, TurboFan은 구글 V8 자바스크립트 엔진의 JIT 컴파일러이다.
본 문서에서는 Optimuzz이 어떻게 기존 방식의 한계를 극복하고 효과적으로 컴파일러 오번역 버그를 탐지하는지 설명한다.
컴파일러의 오번역 버그를 탐지하기 위해 컴파일러 퍼징과 번역 검산을 결합하는 방법이 제안되었다. 이는 번역 검산이 주어진 입력 프로그램에 대해서만 최적화의 올바름을 보장한다는 한계를 극복하기 위한 방법이다. 그러나 기존 컴파일러 퍼징은 다음과 같은 한계가 있다.
첫째, 기존 컴파일러 퍼징은 특정 최적화 규칙을 검사하는 데 비효율적이다. 기존 컴파일러 퍼징은 무작위로 입력 프로그램을 생성하여 컴파일러 전체 덮이를 넓히는 데 초점을 맞춘다. 이러한 방식은 특정 최적화 규칙을 실행하는 입력 프로그램을 효과적으로 생성하지 못한다. 만약 특정 최적화 규칙을 만족하는 입력 프로그램을 생성하지 못한다면, 번역 검산은 해당 최적화 규칙의 올바름을 검사할 수 없다.
둘째, 기존 컴파일러 퍼징은 현대 컴파일러 개발 환경에 통합되기 어렵다. 기존 컴파일러 퍼징이 특정 최적화를 실행하는 입력 프로그램을 생성하는 데 비효율적이기 때문에, 오번역 버그를 탐지하는 데 시간이 오래 걸린다. 이는 업데이트가 일어났을 때 제때 오번역 버그를 탐지하기 어렵다는 것을 의미한다. LLVM과 같은 현대 컴파일러는 매우 빠르게 업데이트되기 때문에, 오번역 버그를 제때 탐지하고 수정하는 것이 중요하다.
Optimuzz는 이러한 한계를 극복하기 위해, 특정 최적화 규칙을 실행하는 입력 프로그램을 효과적으로 생성하는 지향성 퍼저를 설계하여 빠른 시간 안에 번역 검산으로 오번역 버그를 탐지한다.
Optimuzz는 지향성 퍼징과 번역 검산의 유기적 결합을 통해 컴파일러 업데이트를 지속적으로 검증한다. 먼저, 지향성 퍼징을 위해 검증하고자 하는 특정 컴파일러 최적화 규칙이 구현된 소스 코드 위치를 목표로 설정한다. 그 다음, 탐색 유도 전략과 집중 변이 전략을 사용하여, 이 목표 최적화를 실행하는 입력 프로그램을 효율적으로 생성한다. 한편, Optimuzz는 목표 최적화를 실행시킨 생성된 입력 프로그램 대해 기존의 번역 검산기(Alive2, TurboTV)를 활용해 오번역 버그를 탐지한다.
Optimuzz는 컴파일러 검사를 위해 지속 방식와 일괄 방식을 지원한다. 지속 방식은 최적화 관련 소스코드가 변경되면 이를 목표로 검사를 수행한다. 이는 컴파일러 개발 파이프라인에 통합되어 새로운 오번역 버그 유입을 조기에 탐지할 수 있다. 또한 Optimuzz의 일괄 방식은 컴파일러 내부의 최적화 규칙 전체를 대상으로 검사를 수행한다. 일괄 방식은 지속 방식 이전에 검사되지 않은 최적화 규칙까지 포함하여 포괄적인 검사를 수행할 수 있다.
Optimuzz는 특정 최적화를 효과적으로 유발하기 위해 컴파일러 소스 코드에서 목표를 지정하고 지향성 전략을 사용한다. 우선, 컴파일러 업데이트(새로운 최적화 규칙 추가, 기존 규칙 수정 및 삭제 등)가 발생하면, Optimuzz는 해당 변경사항과 관련된 컴파일러 소스 코드 내의 특정 위치를 목표 지점으로 설정한다. 컴파일러 규칙은 주로 최적화 조건을 검사하는 조건문과 최적화 변환을 수행하는 코드 블록으로 구성되며, 여기서 Optimuzz는 이 코드 블록을 목표로 지정한다.
Optimuzz의 퍼저는 컴파일러 전체 덮이를 사용하는 대신, 정적 분석을 통해 목표 지점과 연관된 코드 영역만을 식별해 사용할 덮이 영역을 선별한다. 여기서 연관 코드 영역은 함수 호출 그래프와 제어흐름도를 이용해 구한다. 퍼저는 이 연관 영역 내에서 새로운 덮이를 달성하는 입력만을 유망한 시드(Seed)로 간주한다. 이를 통해 목표와 관련 없는 코드 영역 탐색에 낭비되는 노력을 줄이고 목표 지점에 집중한다.
또한 Optimuzz는 시드 입력과 목표 지점 사이의 거리를 계산한다. 시드 입력이 연관 영역 내에서 실행한 지점들과 목표 지점 사이의 거리를 평균을 내어 구한다. 목표 지점과 거리가 가까운 시드일수록 더 많은 변이(Mutation) 기회를 얻는다. 이는 목표 도달 가능성이 높은 방향으로 탐색을 집중시키는 효과를 낸다.
컴파일러 입력은 단순한 바이트 흐름이 아니라 프로그램이므로 구조와 의미를 가진다. Optimuzz는 이 사실을 이용해 컴파일러 퍼징을 위한 집중 변이 전략을 수행한다.
Optimuzz는 입력 프로그램의 데이터흐름도(Def-Use Graph, DUG)를 분석한다.
퍼저가 변형한 코드가 새로운 덮이를 달성한 경우, 퍼저는 해당 코드와 연관된 부분을 더 높은 확률로 선택해 변형한다.
퍼저가 특정 코드(예: x = y + z)를 마지막으로 변형했다면, 다음 변형은 그 코드와 데이터 흐름상 연관된 다른 코드(예: y나 z를 정의하는 코드, 또는 x를 사용하는 코드)를 우선적으로 변형한다. 이는 최적화 조건을 만족시키는 데 필요한 관련 코드들을 함께 생성하거나 변이할 확률을 높여주어,
무작위 변이보다 더 효과적으로 목표 최적화의 조건을 만족하는 입력을 생성한다.
Optimuzz의 효과를 검증하기 위해 LLVM과 TurboFan을 대상으로 실험을 수행하여 기존 도구들과 비교하고 새로운 오번역 버그를 발견하였다. Optimuzz는 LLVM에서 알려진 오번역 버그 24개 중 23개를 기존 도구(FLUX, ALIVE-MUTATE)보다 훨씬 빠르게 재현했다. TurboFan에서도 기존 도구(Fuzzilli)가 재현하지 못한 버그 4개를 성공적으로 재현했다. 또한 탐색 유도 전략과 집중 변이 전략을 각각 비활성화한 버전과 비교했을 때, 두 전략 모두 버그 재현 시간 단축과 목표 도달률 향상에 기여함을 확인했다. 특히 두 전략을 함께 사용했을 때 가장 좋은 성능을 보였다. 이는 Optimuzz의 지향성 전략이 효과적으로 오번역 유발 입력 프로그램을 생성하는 데 기여함을 보여준다.
또한, Optimuzz는 LLVM 최신 버전에서 57개의 새로운 오번역 버그를 발견하였으며 이를 LLVM 개발진에게 보고하였다. 지금까지 22개의 버그가 수정되었으며, 이는 Optimuzz가 실제로 컴파일러에서 버그를 찾는 데 실용적인 프레임워크임을 입증한다.
Optimuzz는 지향성 퍼징과 번역 검산을 효과적으로 결합하여, 지속적으로 변화하는 복잡한 현대 컴파일러의 최적화 올바름을 검사하는 새로운 프레임워크이다. 특정 최적화 규칙을 목표로 입력을 생성하고 검증함으로써, 기존 방식들의 한계를 극복하고 오번역 버그를 효율적으로 탐지한다. LLVM과 TurboFan에서의 실험 결과는 Optimuzz의 우수한 성능과 실용성을 보여주며, 컴파일러 개발 과정의 안정성을 높이는 데 기여할 수 있음을 시사한다.