🔨

Breaking Through Binaries: Compiler-quality Instrumentation for Better Binary-only Fuzzing

Created

2022/04/13 05:41

Abstract

Fuzzing은 자동화된 과정을 통해 프로그램이 가지고 있는 잠재적인 취약점을 식별하는데 사용되는 기술입니다. 본 연구는 compiler-based 환경보다 binary-only 환경에서의 fuzzing이 더 어렵고, 비효율적이라는 점에 주목하고 있습니다. Compiler-based 환경의 경우 compiler를 직접적으로 사용할 수 있기 때문에 성능 향상에 용이하고, 이 때문에 대부분의 fuzzing 기법들은 compiler-based fuzzing을 중심으로 발전되고 있습니다. 반면 binary-only fuzzing의 경우 이런 이점들을 전혀 활용할 수 없기 때문에 비교적 낮은 성능을 보여주고 있습니다.

그러나 현실에서 대부분의 fuzzing은 closed-source등의 이유로 소스코드에 접근할 수 없기 때문에 binary-only 환경에서 진행해야 합니다. 따라서 본 연구에서는 binary-only fuzzing에서도 compiler-based fuzzing의 성능이 나올 수 있도록 돕는 fuzzing-enhancing program인 ZAFL을 소개합니다.

Background on Fuzzing

이 파트에서는 fuzzing에 대한 전반적인 설명과, binary-only fuzzing에서의 어려움을 정리했습니다.

An Overview of Fuzzing

Fuzzing은 test case를 생성하고, 이 케이스들이 대상 프로그램에 미치는 영향을 관찰하는 것을 반복하며, 최종적으로 버그나 크래시를 유발하는 것이 목표입니다. 기본적으로 fuzzing의 과정은 아래 Figure 1과 같습니다.

Figure 1: A high-level overview of the basic fuzzing overflow

Instrumentation: 타겟 프로그램을 code coverage tracking등을 위해 수정

Test Case Generation: 선택된 시드를 기반으로 mutation을 통해 test case 생성

Execution Monitoring and Feedback Collection: 각 test case를 실행시켜보고, 그에 대한 feedback인 instrumentation을 수집

Feedback Decision-making: 새로운 code coverage 발견 등의 조건을 충족하는 test case만 유지

1번 과정부터 반복

위와 같은 과정으로 진행이 되며, mutation 방법이나 decision-making 방식에 따라 fuzzer를 분류할 수 있지만, 본 연구에서는 이 부분에 대해서 집중적으로 다루지 않았습니다.

Coverage-guided Grey-box Fuzzing

Coverage-guided Grey-box Fuzzing은 가장 많이 쓰이는 fuzzing 기법 중 하나입니다. 이 방식은 타겟 프로그램에 단위 블록(basic block)별로 삽입 되어있는 instrumentation을 기반으로, code coverage를 측정하여 fuzzing을 진행합니다. 또한 white-box와 black-box의 분석 방법을 모두 사용하기 때문에 ‘grey-box’라고 칭합니다.

대부분의 fuzzer들은 낮은 overhead를 위해 컴파일링 과정에서 instrumentation을 삽입하고, 이를 위해 소스코드가 필요한 경우가 대부분입니다. 소스코드 접근이 불가능한 binary-only 환경에서도 instrumentation을 삽입하여 fuzzing을 진행할 수는 있지만, 이 경우 컴파일링 단계 수준의 instrumentation이 불가능하여 coverage tracing에서만 최대 1000%의 overhead를 유발합니다. ‘유의미한’ test case에 한해서만 계속 fuzzing을 진행한다는 점에서 매우 강력한 방법이지만, binary-only 환경에서는 이를 효율적으로 활용하지 못하고 있습니다.

Compiler-based Fuzzing Enhancements

Binary-only 환경에서의 fuzzing에 대해서 알아보기 전에, 기존의 compiler-based fuzzing에서는 어떤 방법을 통해 성능 향상을 이루었는지 정리하였습니다. 본 연구에서는 연산 과정을 향상시키는 Instrumentation Pruning과 Instrumentation Downgrading, 그리고 Feedback 과정을 향상시키는 Sub-instruction Profiling과 Extra-coverage Behavior Tracking에 대해서 설명합니다.

Table 1: Popular compiler-based fuzzing-enhancing program transformations, listed by category and effect

[Performance] Instrumentation Pruning

Graph reducibility technique는 중요하지 않은 기본 블록을 무시하는 방법을 통해 런타임 overhead를 낮추는 방법입니다. AFL의 경우 일정 비율에 한해서 임의적으로 graph reduction을 허용하고 있습니다. 그러나 이의 경우 중요한 coverage를 무시할 가능성이 생기기 때문에, AFL++와 INSTRIM은 실제로 의미가 없는 블록인지 확인하고 무시하는 방법으로 발전시켜 사용하고 있습니다.

[Performance] Instrumentation Downgrading

현재 대부분의 fuzzer들은 edge를 통해 coverage를 측정합니다. 여기서 edge란, 단위 블록 사이의 branches를 칭합니다. 보통 이 edge를 coverage 측정에 있어 일종의 해시값으로 사용합니다. 다만 edge hashing은 연산이 필요하기 때문에 최소한의 연산을 사용하는 것이 전반적인 performance에서 중요한 역할을 하고 있습니다. 따라서 CollAFL등의 fuzzer들은 block에서 instruction을 삽입할 때 더 간단하게 구성하여 overhead를 감소시킵니다.

[Feedback] Sub-instruction Profiling

대부분의 coverage-guided fuzzing은 magic bytes와 체크섬 같은 복잡한 요소가 있는 경우 이를 파악하는 것에 어려움을 겪고 있습니다. 대부분의 fuzzer들은 앞서 설명한 edge와 block을 기준으로 coverage를 측정하기 때문에, 체크섬 등의 과정을 잘 인식하지 못합니다. 이를 해결하기 위해 honggFuzz, CmpCov, laf-Intel과 같은 fuzzer들은 단일 바이트 비교 및 하위 명령어 프로파일링을 통해 coverage를 높이려고 노력합니다.

[Feedback] Extra-coverage Behavior Tracking

전통적인 코드 범위에서 벗어나 실행 동작까지 포함하여 coverage를 측정하는 것은 현재 fuzzing의 연구 분야 중 하나입니다. 기존의 fuzzer들은 edge를 하나의 집합으로 간주하여 coverage를 측정하기 때문에, 순서, 즉 context에 대해서는 측정하지 못합니다. 예를 들어 A → B →C와 B → A →C와 같은 edge들의 경우 context-insensible coverage는 두 edge가 같다고 간주합니다. 그러나 context-sensitive coverage는 B → C와 A → C로 구분하여 coverage를 고려하게 됩니다.

Binary-only Fuzzing: the Bad & the Ugly

Binary-only fuzzing은 compiler-based 환경에서의 장점들을 활용할 수 없기 때문에 성능과 효율이 비교적 낮은 편입니다. 본 장에서는 기존의 binary-only fuzzing이 가지고 있는 한계점에 대해서 탐구합니다.

Limitations of Existing Platforms

Compiler-based 환경에서는 컴파일러의 빠른 처리 속도를 이용하여 coverage 측정을 하지만, binary-only 환경에서는 다음 세 가지 방법 중 하나를 통해 추적됩니다.

[1] Hardware-assisted Tracing

Intel PT등의 최신 프로세서들의 경우, binary code coverage를 쉽게 알아낼 수 있도록 하는 메커니즘이 제공됩니다. 하지만 이 경우는 비용이 매우 높고, compiler-based에 비해 50%넘는 오버헤드가 발생한다는 단점이 존재합니다.

[2] Dynamic Binary Translators

Dynamic binary translating은 프로그램이 실행되는 동안 coverage-tracing 하는 방식을 말합니다. 대표적으로 DynamoRIO, PIN, QEMU등의 프로그램이 사용합니다. 많은 아키텍처와 바이너리 형식을 지원한다는 것이 큰 장점이지만, fuzzing의 관점으로 보았을 때는 오버헤드가 600%까지 발생하여 효율성이 많이 떨어진다는 단점이 있습니다.

[3] Static Binary Rewriters

마지막으로 static binary rewriting 기법의 경우, 바이너리를 실행시키기 직전에 바이너리를 변형시키는 방법입니다. Static binary rewriting기법의 경우 AFL-Dynist, RetroWrite, Uroboros, Ramblr 등 다양한 fuzzer들이 이 기법을 사용합니다. 그러나 모두 binary-only 환경의 경우 제한적으로 기능을 제공하거나 Linux 프로그램에서만 사용 가능하다는 단점 이 존재합니다.

Table 2: A qualitative comparison of the leading coverage-tracing methodologies currently used in binary-only coverage-guided fuzzing, alongside compiler instrumentation (LLVM).

위의 Table을 보면 알 수 있듯이, 기존 binary-only 환경의 platform들의 성능을 분석해보았을 때, compiler-based fuzzer들의 성능을 따라가지 못하는 것을 알 수 있습니다.

Fundamental Design Considerations

다시 compiler-based fuzzing으로 돌아와서, compiler 수준에서의 instrumentation 작업이 binary-only fuzzing에서보다 훨씬 효과적이었기 때문에 해당 방법론에 대해 고민해볼 필요가 있습니다. 연구팀에서는 compiler-based 환경에서 fuzzer들이 transformation 방법에서 크게 4가지 선택을 하는 것을 발견하였고, 본 장에서는 각각의 중요성에 대해 논의하고 compiler-quality instrumentation에 가장 적합한 특성을 선정합니다.

[1] Rewriting versus Translation

Dynamic translation은 기본적으로 emulation을 통해 바이너리의 소스 명령어 스트림을 실행하고 변경(translate)하기 때문에 많은 비용을 필요로 합니다. 반면에 타겟을 실행하기에 앞서서 정적으로 우선 분석하여 재작성(rewrite)할 경우, 훨씬 적은 양의 비용(런타임 등등)을 필요로 하며, 이 경우 compiler-quality 속도를 따라갈 수 있습니다. 따라서 ZAFL의 경우에도 static rewriting을 통한 instrumentation code를 추가하였습니다.

[2] Inlining versus Trampolining

다음은 coverage를 측정할 방법을 선택해야 합니다. 대부분 inlining과 trampolining 사이에서 선택을 합니다. Trampolining의 경우, instrumentation을 만났을 때 별도의 페이로드 함수를 추가적으로 호출하는 방법을 뜻합니다. 당연히 payload 함수를 호출하고, 호출한 함수에게 다시 돌아가야 하기 때문에 높은 오버헤드가 발생하게 된다. 반면 inlining의 경우, basic block 내에 instrumentation 기능을 삽입하는 것을 의미한다. 아 경우 trampolining과 같이 기존의 control flow를 벗어날 필요가 없기 때문에 오버헤드를 줄이는 데 필수적이다. 따라서 ZAFL의 경우에도 inlining 기법을 채택하였습니다.

[3] Register Allocation

메모리 접근은 성능에 있어서 지연을 발생시킵니다. 오버헤드를 줄이기 위해서 필요한 레지스터만 접근하는 것이 꼭 필요합니다. 컴파일러는 보통 잘 사용하지 않는 코드 레지스터를 가능한 많이 저장/복원하지 않도록 레지스터 활성 상태를 추적합니다. 따라서 컴파일러 품질의 이진 계측 속도를 달성하기 위해서는 스마트 레지스터 할당이 필수적입니다.

[4] Real-world Scalability

현대의 컴파일러들은 다양한 컴파일 언어, 바이너리 형식, 플랫폼을 지원합니다. 그러나 위에서 살펴본 많은 프로그램들은 일부 인기있는 형식들만 지원하는 것을 알 수 있습니다. 대표적으로 많은 fuzzer들이 Linux에만 호환 가능하며 Windows 64bit PE32+의 경우 지원되지 않는 경우가 대다수입니다. 따라서 본 연구팀이 추구하는 compiler-quality binary-only fuzzing instrumenting의 경우 다양한 바이너리 형식을 지원하는 것을 목표로 합니다.

The ZAFL Platform

본 연구팀은 compiler-based 환경에서의 장점과, binary-only 환경에서의 단점을 취합하여 하나의 새로운 플랫폼을 탄생시켰습니다. ZAFL은 컴파일러 수준의 처리량을 closed-source 바이너리에 대해서 구현합니다. ZAFL의 특징은 static하게 inline instrumentation이 진행되며, liveness awareness또한 고려하여 수행됩니다. 나아가 x86-64 ELF 바이너리뿐만 아니라 PE32+의 형식도 지원합니다. 아래는 ZAFL의 전반적인 구조를 diagram으로 표현한 것입니다.

Figure 2: A high-level depiction of the ZAFL platform architecture and its four ZAX transformation and instrumentation phases.

Figure 3: Figure 2의 과정을 zafl 실행 log를 기반으로 3개의 step으로 나눈 모습.

Figure 2에 보이는 것처럼, ZAFL은 크게 1) static rewriting을 진행한 뒤, 2) ZAX transformation을 수행하여 최적화된 IR(Intermediate Representation)을 추출하게 됩니다. 마지막으로 3) 최적화된 IR을 다시 재구성을 하게 되면 output binary가 생성됩니다. 이렇게 추출된 binary는 AFL등의 fuzzer에 input으로 사용될 수 있습니다. 자세한 과정은 다음과 같습니다.

Static Rewriting

ZAFL은 효율적인 instrumentation을 위해 dynamic transformation이 아닌 static writing 기법을 채택합니다. 기본적으로 static writing은 Zipr이라는 binary rewriting 프로그램을 통해 이루어집니다.

Zipr은 순서대로 rida, pda_register, fill_in_cfg, fill_in_indtargs, fix_calls의 단계를 거쳐 수행됩니다. 결론적으로 이 과정을 통해서 input 바이너리에 대한 IR data structure가 생성됩니다. 각 단계에 대한 자세한 설명은 논문의 범위를 벗어나기 때문에 추가적으로 조사하지 않았습니다.

ZAX Transformation

Zipr을 통해 생성된 IR을 기반으로 ZAFL은 ZAX transformation을 수행하게 됩니다. ZAX Transformation은 optimization, analysis, point selection, 그리고 application으로 이루어져 있습니다. 이 과정을 통해 최적화된 IR data structure을 생성하게 됩니다.

참고로 ZAX Transformation은 핵심 내용을 정리함과 동시에 실제 코드를 함께 분석하였습니다. ZAFL 사용시 옵션에 따라 과정이 조금씩 달라지지만, ZAX Transformation 자체에 집중하고자 옵션 없이 실행했을 때를 가정하여 Transformation 과정을 분석하였습니다.

[1] Optimization

ZAX Transformation의 첫 번째 단계인 Optimization 단계를 통해서는 주어진 조건에 따라서 최적화를 진행합니다. 이 과정은 control flow를 변경시키기 때문에, 이 과정을 가장 먼저 진행합니다. Optimization 단계는 filterBlocksByDomgraph 함수로 구현되었습니다. 이 함수의 핵심 내용은 아래 for문입니다.

Figure 4: filterBlocksByDomgraph의 일부.

과정은 다음과 같습니다. 함수 실행 시 전달받은 basic block set을 기반으로, dominator tree를 생성합니다. 생성된 dominator tree를 기반으로, 각 branch에 대해 successor 여부에 따라서 CFG 최적화 여부를 결정합니다. 이 과정에서 왜 dominator tree를 활용하는지에 대해서는 아래 Extending Compiler-quality Transforms to Binary-only Fuzzing에서 서술하였습니다.

결론적으로 Compiler-based Fuzzing Enhancements에서 다룬 instrumentation pruning 과정과 매우 비슷한 것을 확인할 수 있습니다. 이 과정을 통해 최적의 Control-Flow graph를 생성하게 됩니다.

[2] Analysis & Point Selection

1단계에서 생성된 Control-Flow Graph를 기반으로, Control-Flow 분석을 진행하게 됩니다. 이 과정을 통해서는 predecessor successor, data-flow, and dominance relationships 등의 Meta-characteristics를 추출합니다. 추출된 Meta-characteristics를 기반으로, 실제로 instruction을 삽입할 블록을 판단합니다. 이 방법은 모든 블록을 나열한 뒤, 조건에 부합하지 않는 부분을 제거하는 방식으로 진행합니다. Analysis와 Point Selection 단계는 getBlocksToInstrument함수에 구현되어 있습니다. 아래는 함수의 핵심 내용입니다.

Figure 5: getBlocksToInstrument의 일부.

해당 for문을 보면, if문을 통해서 instrumentation을 포함하지 않을 블록을 제외하는 방식으로 구현한 것을 볼 수 있습니다. 이 방법은 compiler-based 환경에서의 fuzzing enhancements기법 중 하나인 instrumentation downgrading을 채택하였습니다. 이 과정에 대한 자세한 설명은 아래 Extending Compiler-quality Transforms to Binary-only Fuzzing에서 서술하였습니다.

[3] Application

마지막으로 ZAX Transformation에서 변환한 것들을 적용시킵니다. 이 과정에서 중요한 것은 어떻게 각 위치에 instrument를 삽입하는지가 중요합니다. 프로그램이 정상적으로 처리되는 선 안에서 instrumentation이 진행되어야 하기 때문에, 레지스터가 현재 사용되고 있는지 판별하여(논문에서는 liveness를 판별한다고 표현하였습니다) instrumentation을 진행합니다.

또한, 상태 레지스터는 다른 레지스터보다 더 비용이 많이 들기 때문에 성능 향상에 있어 고려해야 하는 부분 중 하나입니다. 따라서 앞서 말했던 liveness 판별을 통해 기존의 과정을 해치지 않으면서, 최대의 효율을 가질 수 있도록 설계하였습니다. 코드상에서는 이 과정을 instrumentBasicBlock이라는 함수에서 처리하였습니다.

Figure 6: instrumentBasicBlock의 일부(1).

해당 함수에서 가장 먼저 사용 가능한 레지스터를 파악합니다. 이 과정에서 따로 비용을 계산하여 우선순위를 매기지는 않지만, eflags등의 상태 레지스터가 없는 것으로 미루어 보아 적은 비용을 필요로 하는 레지스터들만 사용하는 것 같습니다.

Figure 7: instrumentBasicBlock의 일부(2).

다음으로는 실제 instrumentation을 진행합니다. Instrument를 삽입할 때는 처음 진행하는 경우 insertAssemblyBefore, 이후로는 insertAssemblyAfter를 사용하는 것을 볼 수 있습니다. 앞서 설명한 것처럼, ZAFL은 instrumentation을 진행할 때 함수를 이용하는 trampolining이 아닌, 바로 어셈블리어를 삽입하는 inlining 기법을 사용한 것을 볼 수 있습니다.

Figure 8: instrumentBasicBlock의 일부(3).

마지막으로 사용했던 레지스터들을 다시 복구하여 프로그램 실행에 지장이 없도록 합니다. 위의 과정과 비교하였을 때 assembly의 순서가 반대인 것을 볼 수 있습니다.

특히 이 과정에서 getContextSensitivity등의 함수를 통해 context-sensitive tracking을 진행하는 것을 볼 수 있습니다. 이 과정 또한 아래 Extending Compiler-quality Transforms to Binary-only Fuzzing에서 자세히 서술하였습니다.

Reconstitute Modified IR

마지막으로 ZAX Transformation까지 거친 IR data structure을 기반으로, 마지막으로 binary rewriting을 수행합니다. 이 과정 또한 Figure 3에서 볼 수 있듯이 Zipr이 진행하게 됩니다. 이렇게 binary rewriting이 완료된 바이너리는 ‘.zafl’이라는 확장자를 가진 상태로 output 바이너리가 됩니다. 이 상태의 바이너리는 AFL의 input으로 사용할 수 있게 됩니다.

Extending Compiler-quality Transforms to Binary-only Fuzzing

본 연구팀은 ZAFL을 개발하는 과정에서 총 5가지의 LLVM 기반 fuzzing transformation을 구현하였습니다. 본 리뷰에서는 추가적으로 ZAFL 팀이 어떤 방식으로 각 transform을 구현했는지 분석하였습니다.

Performance Transforms

Single-Successor Path Pruning

Single-Successor Path Pruning은 flow graph를 최적화하는 방법 중 하나로, ZAFL의 경우에는 AFL-Dynist에서 사용하는 방법을 구현하였습니다. AFL-Dynist에서는 entry block이 아니면서, 단일 successor를 가질 경우 최적화를 진행합니다. 이 경우에는 무조건 도달할 것으로 예상할 수 있기 때문에 추가적으로 instrumentation을 진행하지 않는 것입니다. ZAX Transformation의 단계에서는 Analysis단계에서 삽입이 되었으며, filterEntryBlock에서 구현된 것을 확인할 수 있습니다.

Figure 9: filterEntryBlock의 일부.

코드에서도 확인할 수 있듯이, 우선적으로 successor의 개수를 확인하여 단일 successor인 경우 input값인 p_in_out에서 제외되는 것을 확인할 수 있습니다.

Dominator Tree CFG Pruning

ZAX Transformation의 Optimization 과정에서 언급했다시피, ZAFL은 dominator tree를 통해 CFG 최적화를 진행합니다. Dominator tree는 기본적으로 A라는 코드 부분이 실행되었을 때, B라는 코드 부분 또한 실행되었는지 찾기 위해 사용되는 개념입니다.

결론적으로 이 이론을 사용하기 위해서는 모든 Flow Graph에 대응하는 Dominator Tree가 존재한다는 것을 증명해야 합니다. 증명은 [6]으로 대체합니다.

그러면 처음에 언급했던 ‘A라는 코드 부분이 실행되었을 때, B라는 코드 부분 또한 실행되었는지’에 대해서도 알 수 있습니다. 앞서 증명한 내용을 바탕으로 판단하였을 때, dominator tree상에서 A라는 정점이 B라는 정점의 조상인지를 판별하는 것과 동치입니다. 따라서 dominator tree를 이용하면 그래프의 경로 존재 여부를 단순화할 수 있기 때문에 instrumentation을 최소화하기 위한 선택으로 보입니다.

Edge Instrumentation Downgrading

CollAFL은 기존의 AFL의 edge coverage를 기반으로, 블록을 최소화하여 커버리지를 최적화합니다. 이는 앞서서도 논의했던 Single-Successor Path Pruning방법과 비슷합니다. 만약 블록이 단일 predecessor를 가진다면, 해당 블록은 그 edge를 대표한다고 말할 수 있습니다. 이 방법을 이용할 경우 start와 end point의 해싱하는 비용을 아낄 수 있습니다. ZAFL팀은 이 방법을 적용했고, 전체 단위 블록 중 35~45%가 이 최적화를 적용할 수 있었습니다.

Feedback Transforms

Sub-instruction Profiling

Sub-instruction Profiling이란 복잡한 조건부 부분을 single-byte 비교문으로 분해하여 fuzzing을 진행하도록 하는 과정입니다. 이렇게 함으로서 이런 제약조건을 맞추는 과정을 추적할 수 있고, mutation과정을 아낄 수 있습니다.

Compiler-based 환경에서는 이를 중첩 비교를 기존의 비교문을 대체하여 구현합니다. 그러나 feedback을 증가시키는 것이 주된 목표이기 때문에, ZAFL에서는 기존의 비교문 앞에 중첩 비교를 삽입하는 방식으로 구현하였습니다. 이 방법으로 구현할 경우 compiler-based 환경에서 구현했을 때와 동일한 결과를 가져오기 때문에 이 방법을 선택한 것으로 보입니다. 특히 IR에서 cmp같은 비교 구문을 찾아서 바이트마다 중첩 비교를 하게끔 구현하였습니다.

Context-sensitive Tracking

마지막으로 context-sensitive tracking입니다. 앞서 조사했던 Extra-coverage Behavior Tracking처럼, 호출할 때의 상황까지 고려하여 tracking하는 것을 뜻합니다. ZAFL에서는 각 함수를 랜덤 값으로 배정하여 기능 수준의 컨텍스트 감도를 생성하고, 이 값은 함수 입력/종료 시 edge hashing 연산에 사용되었습니다. ZAFL에서는 addContextSensitivity 등의 함수를 통해 구현했습니다.

결론적으로 ZAFL에는 위와 같이 5가지의 low-level의 API를 삽입하여 binary fuzzing이 가지지 못했던 높은 성능을 구현하였습니다.

Evaluation

개발진들은 ZAFL이 실제로 좋은 성능을 가진 fuzzer인지 평가하기 위해 몇 가지 평가들을 진행하였습니다. 평가를 진행할 때 다음과 같은 기준으로 진행하였습니다.

•

대상: 8개의 open-source와 5개의 closed-source 바이너리

•

기간: 8일동안 fuzzing을 진행

•

성능: 발생하는 overhead를 기준으로 측정

•

정확도: open-source에서 복구되지 않은 instruction에 대해 AFL-LLVM과 비교

•

확장성: 자동화된 smoke-test나 직접 실행하여 여부 확인

자세한 평가 내용은 아래와 같습니다.

Does ZAFL enhance binary fuzzing?

가장 먼저 ZAFL이 binary-only 환경의 fuzzing에서 더 나은 성능을 보여주는지 측정하였습니다. 이 과정에서는 AFL-Dynist, AFL-QEMU, 그리고 ZAFL을 비교하였습니다.

Figure 11: Real-world software fuzzing unique triaged crashes averaged over 8*24 hour trials.

위 그림의 경우 실제 software을 대상으로 fuzzing을 진행하였을 때 주어진 test case에 비해 평균적으로 얼마나 크래시를 발견해내는지에 대해 기록한 것입니다. 그래프에서도 볼 수 있듯이, ZAFL이 대부분 더 높은 성능을 보여주고 있음을 알 수 있습니다. 계산 결과 ZAFL이 평균적으로 AFL-Dynist보다는 26%, 그리고 AFL-QEMU보다는 131% 더 많이 크래시를 발견했습니다.

Is ZAFL’s speed near compilers’?

다음으로는 ZAFL의 속도가 실제 컴파일러의 속도와 비슷한 지에 대해서 평가해보았습니다. 비교 대상은 컴파일러, 어셈블러, AFL-Dynist, 그리고 AFL-QEMU입니다. 또한 ZAFL-none과 ZAFL의 다양한 version인 ZAFL-fsrvr, ZAFL-perf, ZAFL-all이 적용된 경우를 나누어 결과를 측정하였습니다.

Figure 12: Compiler, assembler, AFL-Dynist, AFL-QEMU, and ZAFL fuzzing instrumentation performance relative to baseline (higher is better).

결론적으로 ZAFL은 컴파일러에 비해 크게 뒤떨어지지 않는 속도를 보여주었습니다. 컴파일러와 어셈블러의 경우 각각 24%와 34%의 overhead가 발생하였는데, ZAFL의 경우 버전에 따라 상이함을 보였지만 27~32%의 overhead가 발생하였습니다. 비록 컴파일러에 비교했을 때는 더 낮은 성능을 보여줬지만, AFL-Dynist와 AFL-QEMU가 각 88%, 256%의 overhead를 발생시키는 것을 고려하였을 때 엄청난 성장을 이루었다고 볼 수 있습니다.

Can ZAFL support real closed-source?

다음으로는 ZAFL이 실제로 closed-source에 대해서 좋은 성과를 보여주는지에 대해서 평가하였습니다. 평가는 5개의 취약점에 종류에 대해서 얼마나 빨리, 그리고 많이 발견해내는지에 대해서 평가하였습니다. 비교 대상은 AFL-Dynist와 AFL-QEMU입니다.

Table 13: Mean time-to-discovery of closed-source binary bugs found for AFL-Dyninst, AFL-QEMU, and ZAFL over 5×24-hour fuzzing trials. ✗ = bug is not reached in any trials for that instrumenter configuration.

그 결과, ZAFL이 AFL-Dynist보다는 55%, 그리고 AFL-QEMU보다는 38% 더 크래시를 많이 발견한 것을 알아낼 수 있었습니다. 더불어, 평균적으로 ZAFL은 이 버그들을 찾아내는데 660%, 113%(각각 AFL-Dynist, AFL-QEMU) 더 빠른 것을 알 수 있었습니다.

Is ZAFL precise?

다음으로는 ZAFL의 정확도에 대해서 평가하였습니다. 정확도를 평가하기 위해서 LLVM-10 objdump와 정확도를 비교하였습니다. 비교군은 IDA Pro와 Binary Ninja가 감지해낼 수 있는 instrumentation을 비교하였습니다.

Table 14: Instruction recovery statistics for IDA Pro, Binary Ninja, and ZAFL, with ground-truth disassembly from LLVM-10’s objdump. Reached = mean unrecovered instructions reached by fuzzing (hence, erroneouslyunrecovered); FalseNeg = erroneously-unrecovered instructions over total.

결론적으로 ZAFL이 가장 높은 정확도를 보였습니다. 특히 LLVM-10의 objdump와 비교해보았을 때, ZAFL을 통해 도달하지 못하는 instruction은 없었습니다. 또한 커버리지 정확도의 평균을 내보았을 때 99.99%라는 결과를 도출할 수 있었습니다.

Does ZAFL Scale?

마지막으로 ZAFL이 다양한 형식을 지원하는지(scalability)에 대해서 평가하였습니다. ZAFL은 open-source, closed-source, 그리고 Windows 바이너리까지 모두 호환 가능합니다. 본 연구팀은 결론적으로 총 56개의 바이너리에서 ZAFL이 정상적으로 동작한다는 것을 확인하였습니다. 이 56개의 바이너리는 1) Linux와 Window 바이너리, 2) stripped, PIE, 그리고 non-PIE형식, 3) 100KB와 100MB사이의 크기의 바이너리, 그리고 4)100에서 1,000,000개의 단위 블록을 가진 바이너리를 모두 지원한다는 것을 검증하였습니다.

Conclusion

본 연구는 compiler-based fuzzing과 binary-only fuzzing 사이의 간극을 줄이기 위해 진행했던 연구였습니다. 특히 performance와 feedback의 측면으로 나누어 성능 향상을 이룬 것이 가장 인상깊었습니다.

다만 아쉬웠던 점은 ZAFL이 static rewriting의 부분에 있어서는 기존의 binary rewriter인 Zipr에 대부분 의존한 점입니다. Zipr도 좋은 binary rewriter이지만, 이 때문에 난독화가 진행된 바이너리의 경우에는 좋은 성능이 나오지 않았습니다. 그러나 최근 automatic deobfuscation 등의 연구가 계속되고 있기 때문에, 추후 연구에서 이를 적용할 경우 더 좋은 성능을 보일 수 있을 것으로 예상됩니다.

논문 review를 진행하면서, ZAFL에 대해서 직접 소스코드를 분석하고 구조를 파악해보았습니다. 특히 ZAFL을 성능을 향상시키기 위해 개발진들이 했던 선택을 왜 했는지에 대해 직접 증명해본 것이 재미있었습니다. 이번 과제를 통해 기술을 최적화하는 과정과, 그리고 다른 환경에서 기술을 구현하는 방법에 대해 많이 배울 수 있었습니다.

References

[1] Nagy, S., Nguyen-Tuong, A., Hiser, J. D., Davidson, J. W., & Hicks, M. (2021, September). Breaking Through Binaries: Compiler-quality Instrumentation for Better. USENIX. https://www.usenix.org/system/files/sec21-nagy.pdf

[2] USENIX. (2021.09.04). USENIX Security '21 - Breaking Through Binaries: Compiler-quality Instrumentation for Better [Video]. Youtube. https://www.youtube.com/watch?v=8Z-5aTpk_l0

[4] ZAFL (2021). https://git.zephyr-software.com/opensrc/zafl

[3] J. Hiser, A. Nguyen-Tuong, W. Hawkins, M. McGill, M. Co, J. Davidson. (2017, November). Zipr++: Exceptional Binary Rewriting. FEAST’ 17. https://dl.acm.org/doi/pdf/10.1145/3141235.3141240

[5] Zipr (2017). https://git.zephyr-software.com/opensrc/zipr

[6] T. Lengauer, R.E. Tarjan. (1979). A Fast Algorithm for Finding Dominators in a Flowgraph. Stanford University. https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf