VSEVOLOD LIVINSHII, DMITRY BABOKIN, JOHN REGEHR ACM OOPSLA 2020
개요
컴파일러 테스팅을 위하여 프로그램을 랜덤 생성할시 커버리지를 높이기 위하여 코드 특성을 체계적으로 변경하는 매커니즘을 제공하고, 언어의 제한된 하위 집합에 머물지 않으면서도 정의되지 않은 동작이 없는 코드를 생성해내는 새로운 Compiler fuzzing test generator을 고안하였다.
Motivation
컴파일러는 절대 실패해서도 안돼며, 프로그래머가 작성한 그대로 완전한 바이너리 파일을 생성해야 한다. 그러나 컴파일러는 자주 변경되며, 소스 언어, 새로운 타겟 플랫폼 지원, 추가적인 최적화 지원으로 인하여 이를 완전히 보장하는 것은 거의 불가능하다.
Importance
Random test case generation과 같은 경우에는 컴파일러 버그를 찾을 수 있는 효과적인 방법이지만, 결국 포화 상태 (Saturation)에 도달하여, 새로운 버그를 찾을 수 없게 된다. 본 논문은 C혹은 C++ 컴파일러를 위한 새로운 Random test case generator로 다음과 같은 질문을 해결하였다.
- 이전 테스트 방법으로 놓친 버그는 무었인가?
- Random testing에 의존하지 않고 더 Coverage가 높은 프로그램을 생성하는 방법이 있는가?
- 생성한다면, 컴파일러의 특정 부분을 타겟팅 할 수 있도록 유도할 수 있는 매커니즘을 구현 가능한가?
Main Idea
- 컴파일러 버그를 두가지 카테고리로 분류하였다.
- Internal compiler error: Compiler가 crash하거나 abort되는 경우
- Wrond code bug: 출력이 입력과 다른 경우 (i.e., miscompilation)
- 다음 3개의 Background정보를 설명한다.
- Undefined Behavior: C/C++과 같은 프로그래밍 언어는 오류가 발생할 수 있다 (e.g., UAF나 Double free). 만약 차등 테스트가 잘못된 프로그램을 사용하면, 컴파일러 테스팅이 무용지물이 된다. C/C++과 같은 경우에는 몇 백가지 이상의 정의되지 않은 동작이 있으며, 이는 모두 랜덤으로 생성된 코드에서 반드시 피해야 한다.
- Unspecified Behavior: C/C++이 여러 대안중 하나를 선택할 수 있지만, 일관성을 요구하지 않는 동작이다. 예를 들어서 함수의 인자를 어떤 레지스터에 넣을지는 컴파일러마다 다르다. 그러나 이러한 Unspecified Behavior는 컴파일러로 생성된 프로그램의 동작과는 무관해야 한다.
- Implementation-Defined Behavior: Unspecfied Behavior와는 다르게, 명세서에 적혀있는 컴파일러가 선택할 수 있는 동작이다. 이 동작은 일관적으로 구현되어야 한다.
YarpGen은 loop-free C/C++프로그램을 생성해내며, Undefined Behavior를 회피하도록 디자인 하였다.
Design
- Avoiding Undefined Behavior
- 표면적으로 대부분의 Undefined Behavior과 같은 경우에는 쉽게 회피 가능하다. 그러나 몇몇 버그들은 어려운데, 예를 들어서, Integer overflow와 같은 경우에는 생성된 프로그램의 동작에 달려있기 떄문에 쉽게 회피는 불가능하다. 크게 3가지의 방식이 있다. Dynamic check삽입하기, checking tool로 확인하기, Static anslysis를 통해서 미연에 방지하기. YarpGen은 Static analysis방식을 채택하였다.
- Generating Code
- YarpGen은 Data type에 따라서 table을 만들어 type table이라 명명하였다. 그후 YarpGen은 global변수를 symbol table에 정리하였다. Generation단계에서 YarpGen은 Top-down방식을 채택하였다. 우선 큰 함수 블럭을 생성한후, 다음 세가지의 step을 랜덤하게 수행하였다.
- 새로운 랜덤 타입, 랜덤 값을 가지는 local변수를 선언
- 변수에 랜덤한 산술 표현식을 삽입한다.
- 새로운 Conditional branch를 삽입한다. 각각의 Branch는 랜덤한 Boolean표현식에 의해서 정의되며, 새로운 하나 혹은 두개의 statement블럭으로 구성된다. Branch nesting이 특정 조건에 도달하면 더이상 생성하지 않는다.
생성된 Program은 Input에 대해서 나오는 Ouput과 Global variable에 대한 참조를 바탕으로 checksum을 계산하는 Hash funciton을 main함수로 가지며, 서로 다른 컴파일러가 같은 checksum value를 가질 경우에만, 문제가 없는 경우로 판별된다.
- Generation Policies
- 만일 랜덤한 선택이 같은 distribution에서 발생한다면 컴파일러가 내부적으로 Optimization을 수행하기 떄문에, 결국에는 모든 프로그램들이 다 고만고만한, 즉 Coverage를 늘리지 못하는 형태로 만들어 진다. 이를 회피하기 위해서, YarpGen은 Compiler의 특정 Optimization을 더 많이 일으키도록 하는 방향으로 유도하는 Generation policies를 적용하였다. Generation policies들은 function-level, global-level등 다양한 범위에 적용되며, 서로 같이 작동할 수 있도록 하였다. 이러한 정책은 Compiler가 작동하는 방식, 보통 어디서 버그가 자주 발생하는지에 대한 경험적인 지식을 바탕으로 Heuristic하게 작성하였다. 또한 내부적으로 사용하는 Parameter들은 시작전에 Random하게 생성하여 더욱 Variation을 증가하였다.
- Automation
- YarpGen은 테스트에 사용하는 각 단계를 자동화 하여서, 개입을 최소화 하였다. 이를 위해서 YarpGen은 Test case를 생성하고, 이를 Compiler Input으로 넣어 Differential testing을 수행, 만약 결과가 다르면 이러한 원인을 C-Reduce를 통하여 추출, 핵심이 되는 원인을 Report하도록 하였다.
- Expreimental Features
- Evaluation에는 추가하지 않았지만, 흥미로운 포인트들을 정리하였다. 1. Floating point와 같은 경우 Precision으로 인해서 정확한 Checksum이 불가능하다. 따라서 어느정도 Plausible한 범위까지만 checksum계산에 포함해야 한다. 2. LLVM은 OpenCL의 Vector을 내부적으로 지원하는데, 특정 조건을 걸어주어야만 Undefined Behavior을 가져오는 것을 피할 수 있다. 3. Loop와 같은 경우에는 Arithemtic연산에 제약을 주어서 Undefined Behavior를 첫번째 Loop만 체크해도 알 수 있도록 하였다.
- Limitations
- Pointer arithmetic, function calls, classes, preprocessor, templates, lambdas, dynamic memory allocation, compound assignment, side-effecting operator를 지원하지 않는다. 또한 위의 특정 조건으로 인하여 Floating point와 Loop는 제약이 크다. YarpGen의 주된 목적은 Scalar optimization에서 발생하는 문제를 찾는 것에 있기에, 큰 문제가 아니라고 서술하였다.
Conclusion
YarpGen은 많은 버그를 찾고, Developer들이 그 버그를 고치도록 도움을 주었다. YarpGen에서 소개한 방식은 Compiler Fuzzing이라는 방법을 제시함으로써, Compiler testing을 효율적으로 할 수 있는 방법을 제시하였다.