https://www.usenix.org/system/files/sec21fall-nagy.pdf 의 내용 정리
1.1. Fuzzing
1.1.1. What is Fuzzing?
Fuzzing(퍼징)은 bug를 찾아내기 위한 소프트웨어 testing 기법이다.
Fuzzing은 다량의 test case들을 만들어내고(generation), 대상 바이너리에 test case들이 어떤 영향을 주는지-특히, bug를 유도하지는 않는지- 관찰하는 것이다.
1.1.2. Fuzzing의 구성
Fuzzer는 자동으로 소프트웨어 취약점을 찾아내도록 디자인되었다. target program과 seed test cases들이 주어진다면 일반적인(표준) fuzzing cycle은 아래와 같다.
- Instrumentation
target program을 code coverage를 측정할 수 있도록 변경한다.
target program의 basic block들 사이에 삽입된 instrumentation들을 통해서 coverage를 얻어내는 것이다(feedback collection) - Test case generation
seed 파일이 여러 개 있으면 seed 파일을 하나 선택하고, test case들을 생성한다. - Execution Monitoring and Feedback collection
각 test case들을 실행시켜보고 target program에서 어떻게 실행되는지 관찰한다. 이 과정 중에 instrumentation을 통해 feedback을 수집한다. - Feedback Decision-making
crash, bug 등과 같이 미리 지정해둔 요소들에 맞는 test case들만 따로 보관한다. - Return to Test case generation
1.1.3. Recent Fuzzers
소스코드에서 target program에 대해 instrumentation할 수 있는지에 따라,
| compiler-based | - 최근에 많이 사용되는 instrumentation 기법이다. - 짧은 실행시간으로 낮은 오버헤드 & 높은 fuzzing 처리량 - 주로 compile 단계에서 instrumentation code를 삽입하는 작업 |
| binary-only | - 실제 상황 속에서는 target source가 주어지지 않는 경우가 많다. - compiler-based 만큼 성능이 좋지는 않다. - 높은 오버헤드 (시간 및 공간 소모 ↑) |
1.1.3.1. Coverage-guided Grey-box Fuzzing
최근 가장 많이 사용되는 fuzzing 기법이다.
- coverage-guided
타겟 프로그램의 함수들을 할 수 있는 많이 테스팅하면서 깊숙히 존재하는 버그들을 찾아내기 위해 coverage의 값을 높이는 방식 - grey-box
white와 black 사이의 바이너리 파일에 대한 일부 정보만 알고 있는 상태에서 fuzzing을 하는 방식
1.2. Compiler-based Fuzzing Enhancements (발전 방향)
Coverage-guided Fuzzing은 ‘compiler-based’와 ‘binary-only’로 나뉘고, 둘 다 test case의 code coverage를 측정하기 위한 program instrumentation 을 사용한다.
- fuzzing이 성공한 경우, 대부분 compiler에서 빠르게 instrumentation을 통해 높은 처리량을 가져 성공하게 되었다.
- 다양한 종류의 fuzzer들이 계속 연구되고, 개발되고 있지만 [Figure 1]에서의 ‘the standard coverage-guided fuzzing loop’은 그대로 유지된다.
- 즉, 요점은 기존의 coverage-guided fuzzing loop의 틀을 유지하되 어떻게 성능을 향상 시킬 수 있느냐는 것이다
⇒ fuzzing 성능과 feedback을 어떻게 향상 시킬 수 있을까?
(*feedback: instrumentation의 결과, mutation 할 때 즉 seed file에서 새로운 test case들을 만들어낼 때 참고할 자료)
유명한 fuzzer들을 분석해서 coverage-guided loop를 대상으로 어떻게 fuzzing의 기능을 향상시킬 수 있는지 4가지로 분류했다.
1.2.1. Instrumentation Pruning
(*prune: 불필요한 가지(부분)를 제거한다)
graph의 환원성(reducibility) 기술들은 전체적인 런타임 오버헤드를 낮추기위해 타겟 바이너리의 몇 가지 basic block들에 대해 instrumenting 하는 것을 생략한다.
- AFL: 0~100까지의 비율로, 100일 경우 모든 block들에 대해 instrumenting하고, 0일 경우, 함수 엔트리에 대해서만 실행한다.
(단점) 랜덤하게 블록들을 선택하는 것은 coverage의 사각지대가 생길 수도 있다.
1.2.2. Instrumentation Downgrading
최근의 fuzzer의 대부분이 ‘edge’(basic block들의 연결선)를 토대로 coverage를 측정하고, 이 값은 hash의 형태로 기록해둔다.
- Edge를 hashing하는 과정은 몇 줄의 명령문들이 필요다.
- 이에 반해 block들은 매우 작고, 속도가 떨어지지 않도록 하기 위해서는 명령문들을 줄이던가 해야한다.
- CollAFL compiler instrumentation: 명령문의 길이를 줄이기 위해 바로 앞 블록을 생략한다.
ex. cov(A→B) ⇒ cov(B) : downgrading
1.2.3. Sub-instruction Profiling (하위 명령 파악)
fuzzer들은 “magic bytes”, nested checksum(중복 검사), switch 문 등 복잡한 표현들로 보호된 코드들을 뚫으려고 노력한다. (-> 그래야 code coverage가 높아지고! crash도 많이 생길테니까!)
“sub-instruction profiling”은 multi-byte의 조건들을 single-byte의 비교로 분해(?)한다.
이런식으로 다른 block으로 넘어가는 block들을 좀 더 작게 세분화시켜 code가 단순해질 수록 fuzzing code(..아마도 instrumentation code가 아닐까?..)의 적용범위를 넓혀준다.
1.2.4. Extra-coverage Behavior Tracking
추가적인 coverage에 대한 동작을 추적하기 위해서는 context-sensitivity에 중점을 둬야한다. 즉, 실행 흐름을 파악하는 것이 중요하다.
- 예를 들어, A→B→C 의 경우
- LLVM에서는 함수들, 호출 사이트 사이의 관계를 모두 고려하여 작업한다.
1.3. Binary-only Fuzzing
closed-source 바이너리(소프트웨어)에 대해서는
1.3.1. Limitations of Existing Platforms
binary-only Fuzzing(동적 instrumentation만 가능) code-coverage를 측정하는 방법에는 아래의 3가지 방법이 있다.
1.3.1.1. Hardware-assisted Tracing
최신 프로세서들은 binary code coverage를 쉽게 알아낼 수 있게 하는 메커니즘이 제공된다.
(ex. Intel PT)
- 비용 ↑
- compiler-based에 비해 50%넘는 오버헤드 발생
- 일부 성능향상에도 하드웨어 차원의 tracing은 fuzzing enhancing program을 지원하지 못한다.
1.3.1.2. Dynamic Binary Translators
동적으로 바이너리를 해석하는 방식은 프로그램이 실행되는 동안 coverage-tracing 하는 방식을 말한다.
(ex. DynamoRIO, PIN, QEMU)
- 일반적으로 많은 아키텍처, 바이너리 형식 지원
- fuzzing 성능은 최악; 오버헤드가 600% 정도까지
1.3.1.3. Static Binary Rewriters
정적으로 바이너리를 재작성하는 방식은 바이너리를 실행시키기 직전에 바이너리를 변형시키는 방식이다.
(ex. Dyninst)
- binary-only fuzzing에서는 제한적
- Linux 프로그램에서만 사용 가능
1.3.2. Fundamental Design Considerations
“how compilers support performant program transformations”
- 어떻게 컴파일러들은 프로그램 전환-instrumentation code를 삽입하는 과정-을
효과적으로 진행할 것인가?
- compiler 수준에서의 instrumentation 작업이 binary-only fuzzing(&instrumentation)에서보다 훨씬 효과적이었기 때문에 고민해볼 필요가 있다.
→ 4가지의 선택과 결정에 따라 얼마나 훌륭한 program transformation을 진행할 수 있는지 결정된다.
1.3.2.1. [Consideration 1] Rewriting(재작성) VS Translation(해석, 번역)
target을 실행하기에 앞서 정적으로 분석하게 되면 바이너리에 대한 모든 분석을 할 수 있게 된다.
ex. control-flow 복원, code/data disambiguation, instrumentation
binary-only fuzzing에서는 static rewriting을 하는 것이 컴파일러의 속도를 높이는 데에 가장 효과적이다.
결론(기준): static rewriting으로 추가되는 instrumentation code
1.3.2.2. [Consideration 2] Inlining VS Trampolining
“how to invoke instrumentation code”
| trampolining | instrumentation 기능(code)를 포함하는 다른 함수를 호출
|
| inlining | basic block 내에 instrumentation 기능을 표현
|
결론(기준): inlining 방식으로 instrumentation을 호출(사용)하자
1.3.3.3. [Consideration 3] Register Allocation
컴파일러는 레지스터의 수명을 추적해서 비활성 상태의 코드 레지스터들을 최대한 저장하거나 복원하지 않는다. (아마도 시간, 메모리의 오버헤드를 줄이기 위한 것..?)
필요한 레지스터를 할당하는 것은 컴파일러 수준의 binary-instrumentation의 속도를 가지는 것에 필수적인 조건이다.
결론(기준): 레지스터의 수명(주기) 추적을 쉽게 하자
1.3.3.4. [Consideration 4] Real-world Scalability
특히 static rewriter의 경우, 환경에 대한 여러 제약들이 존재한다.
결론(기준): 보편적으로 많이 사용되는 binary 포맷들과 플랫폼들을 지원하자