주요 내용으로 건너뛰기

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 5

앞의 포스팅 : [논문리뷰] Fuzzing: Art, Science, and Engineering - Part 4 

Input Evaluation

이 단계에서는 앞의 Input generation 을 통해 얻은 입력값을 PUT의 input으로 하는 fuzzer execute 작업을 수행하고, 그 수행결과를 어떻게 평가할 것인지를 정한다. 

이 단계에서 단순히 그냥 휙 던져버리는 정도로 단순하게 처리하는 방법도 있지만, 그 외에도 굉장히 많은 최적화 방법론들과 그에 따른 성능 측면의 이득이나 기타 다른 퍼징 효율 등을 고려할 수 있다. 때문에 퍼저의 설계 원리를 고민하는 단계라고 할 수 있다.

Bug oracle

버그 오라클이란 해당 프로그램 수행이 버그를 내포하고 있는지 아닌지를 결정하는 심판관이다. 흔히 프로그램이 segmentation fault와 같은 fatal signal 발생했다면, 이를 보안 사고로 규정하는 일종의 정책을 규정할 수 있다. 이러한 방식을 통해 다수의 메모리 취약점들의 발생여부를 탐지할 수 있다. 메모리 취약점이란 유효하지 않은 값이 데이터 영역 또는 코드 영역을 덮어씌워서 프로그램에서 이를 잘못 참조하려다가 segmentation fault 또는 abort가 발생하는 경우를 뜻한다. 

참고적으로 이러한 방식이 100% 모든 메모리 취약점의 발생유무를 탐지할 수는 없는데 왜냐하면 엄밀하게 따져서 stack buffer overflow 발생으로 메모리 주소 공간에 잘못된 값이 쓰여진 것만으로도 이미 취약점이라고 보아야 하는데, crash가 발생하지 않고 그저 적당히 잘못된 처리만 하고 지나가게 된다면 이러한 경우 탐지를 제대로 할 수 없는 맹점이 생기게 되는 것이다. 연구자들은 이러한 위협을 최소화하기 위하여 일명 sanitizer라는 기법을 통하여 unsafe하거나 unwanted한 프로그램의 동작이 보이는 즉시 강제로 abort를 발생시키는 기법을 동원하기도 하였다.

Memory and Type safety

Memory safety 버그는 크게 두가지 종류로 구분된다.

  • Spatial : 특정 객체가 의도하지 않은 대상의 외부에서 포인터 역참조가 발생할 때의 오류를 의미한다. 예를들어 버퍼 오버플로우나 언더플로우 같은 것들이 전형적인 Spatial memory error 유형이다.
  • Temporal : 더이상 유요하지 않은 포인터에 접근하게 될때 발생하는 오류이다. 예를 들어 use-after-free 같은 취약점이 대표적이며, 할당이 해제된 메모리 영역을 가리키던 포인터가 사용될 때 발생한다.

Address Sanitizer(ASan)은 프로그램의 instrument를 통해 컴파일시에 메모리 에러를 감지할 수 있는 효과적인 도구이다. ASan을 사용하면 Spatial이나 Temporal 유형 모두를 탐지할 수 있으며, 이에 따른 속도 저하는 73% 정도이기 때문에 충분히 매력적인 대안이 될 수 있다. 

MEDS라는 도구는 ASan에 비해 대용량의 메모리를 사용하는 64-bit platform에서 작동할 수 있도록 개선되었다.

SoftBound/CETS 역시 컴파일 동안 program을 instrument하여 메모리 에러를 찾아낸다. ASan의 경우 유효한 메모리 주소를 추적하는 방식이라면, SoftBound/CETS는 각 포인터들의 bound와 temporal 정보들을 이용하는데 이론적으로는 모든 spatial과 temporal 오류들을 탐지할 수 있다. 그렇지만 아쉽게도 completeness 를 높이게 되면 overhead 측면에서 손해(116%)가 발생한다.

CaVer이나 TypeSan, HexType은 C++언어의 Type casting시에 올바르지 않게 casting되는 상황을 컴파일시에 탐지하는 도구이다. 

또 하나의 memory safety protection 기법으로는 Control Flow Integrity(CFI)가 있는데, run-time에 원본 프로그램의 행위와 비교하여 불가능한 control flow transition이 발생하는지 여부를 검사하는 방식이다. 이러한 방식은 최근의 gcc나 clang 컴파일러에 채택되어 있다.


Undefined behaviors

C언어를 예로 들자면, 언어의 설계 명세에서 명확히 규정하지 않은 빈틈으로 인해 생기는 공백인 일명 Undefined behavior(미정의 동작)이 굉장히 많다. 이러한 경우 컴파일러 제조사는 각자 나름의 방식으로 이 일을 처리하게 되는데 이는 궁극적으로 굉장히 다양한 이슈를 발생시킨다. 프로그래머의 예측과는 다르게 컴파일러의 버전이나 최적화 옵션, 컴퓨터 아키텍처에 따라 다르게 동작한다는 것은 궁극적으로 다양한 버그와 취약점을 양산하게 된다.

Memory Sanitizer(MSan)은 C와 C++로 작성된 코드가 실행될 때 초기화되지 않은 메모리를 사용할 때 발생하는 Undefined behavior를 탐지할 수 있도록 컴파일시에 program instrument해주는 도구이다. MSan의 Overhead는 약 150%dlek. 

Undefined Behavior Sanitizer(UBSan)은 미정의 동작을 탐지하기 위해 컴파일시에 프로그램의 일부를 살짝 변조한다. 다른 Sanitizer들은 UB 상황의 특정 source에만 집중하는 반면, UBSan은 misaligned pointer, division by zero, null pointer dereference, integer overflow 등을 모두 탐지할 수 있다.

Thread Sanitizer(TSan)는 정밀도와 성능간의 절충을 유지하면서 data race를 컴파일타임에 탐지할 수 있는 도구이다. 두 Thread가 동시에 공유된 메모리에 접근하려고 할 때 이미 하나 이상의 접근에 점유하고 있는 경우 데이터 경쟁 조건이 발생하게 된다. 이러한 버그는 궁극적으로 data corruption을 유발할 수 있으나 행위 자체가 non-determinism하므로 이를 재현하기가 매우 어렵다.

Input validation

XSS나 SQL injection과 같은 취약점들은 모두 주어진 입력값에 대한 검증을 제대로 수행하지 않았을 때 발생한다. 그러나 이러한 취약점을 완벽히 막기 위해서는 해당 어플리케이션(웹 브라우저, 데이터베이스 엔진)의 복잡한 parser 등의 로직을 속속들이 알아야 대응이 가능하기 때문에 쉽지 않은 문제이다.

KameleonFuzz는 실제 웹 브라우저로부터 test case를 분석하여 DOM(Document Object Model) tree를 확인하고, 특정 패턴과 비교하여 성공적인 XSS attack을 수행한다.

반면 그와 유사한 방법의 μ4SQLi는 SQL injection 시도를 탐지하는데 사용된다. 웹 애플리케이션의 응답 코드만으론느 SQL 인젝션이 성공했는지 여부를 정확히 판단할 수 없기 때문에, μ4SQLi는 대상 웹 애플리케이션과 데이터베이스 간의 통신구간에 놓여있는 프록시를 사용하여, 해당 입력이 유해한 동작을 유발했는지 여부를 파악한다.

Semantic Difference

Semantic 버그란, 소위 differential testing으로 불리우는 기법에 의해 발견되며 이는 유사하지만 동일하지는 않은 프로그램들의 동작을 비교분석하는 테스트이다. NEZHA 등의 도구를 살펴보면 유사한 프로그램들간의 미묘한 불일치에 따른 버그를 식별하기 위해 차분 테스팅을 사용하였다.

Execution Optimizations

각 fuzz interation들이 sequentially하게 실행되며 각각은 개별적인 것으로 가정하였다. 그러나 PUT을 매번 프로세스 재기동시키게 하는 것은 굉장한 부하를 유발한다. 현대적인 fuzzer들은 이러한 반복적인 프로세스 로딩 작업을 생략함으로써 성능을 최적화하는데 AFL같은 경우 fork-server라는 개념을 통해 각 fuzz iteration에서 이미 초기화된 상태의 process로부터 fork하여 진행한다. 이와 유사하게 in-memory fuzzing 역시 또다른 최적화 방법의 하나로써 실행 시간을 단축시킨다. 그 밖에 fork()대신 새로운 system call 을 설계하여 fuzz iteration의 cost를 줄이려고 한 [Designing new operating primitives to improve fuzzing performance] 논문도 있다.

Triage

triage는 보안 정책 위반을 촉발한 해당 테스트 케이스에 대하여 분석하고 리포트하는 작업이다. 보통은 세가지 단계로 나뉜다.

1) Deduplication

Deduplication이란 동일한 버그를 유발하는 다수의 테스트 케이스를 식별하여 이를 가지치기하는 것이다. 이상적으로는 각각의 unique bug만을 촉발하는 고유한 test case의 집합만을 남겨두는 것이다. 이러한 중복제거 작업은 거의 모든 퍼저에서 굉장히 중요한 부분인데, 실무적인 관점에서 보면 하드드라이브에 여러개의 중복된 결괏값을 반복하여 저장하는 것은 디스크 공간 및 자원 낭비이기 때문이다. 또한 usability 측면에서도 현재 얼마나 많은 고유 버그들이 발견되었는지에 대한 현황 파악에 용이해야하기 때문이다.

현재 실무에서 주로 사용되는 deduplication 기법은 아래와 같이 3개가 대표적이다.

  • Stack Backtrace hashing : 가장 고전적이면서도 현재까지 폭넓게 사용되는 기법으로, crash가 발생한 순간의 stack backtrace에 대한 정보를 자동으로 기록하는 방식이며 이때 stack hash를 계산한다. stack hash를 계산하는 방법은 구현에 따라 굉장히 다양하다. stack backtrace hashing 이 널리 쓰이긴 하지만 단점이 없는 것은 아니다. 기본적으로 유사한 버그들은 유사한 crash 와의 상호 상관관계가 있다는 것을 가정으로 한 방법인데, 사실상 이 가설은 정확히 입증되지는 않았으며 확연한 반례도 존재한다.
  • Coverage-based Deduplication : AFL은 각 edge coverage를 소스코드 instrumentation을 통해 효율적으로 처리하는 것으로 알려져있다. 그레이 박스 퍼저인 AFL은 이러한 coverage information을 기반으로 new seed file을 선택한다. 이는 굉장히 독창적인 발상인데, AFL의 메뉴얼에 따르면 앞선 edge에서 발견된 적이 없는 crash인 경우이거나, 해당 crash가 앞선 모든 crash에 포함되지 않는 경우 이를 unique한 crash라고 간주하기 때문이다.
  • Semantics-aware Deduplication : RETracer는 각 crash로부터 데이터 흐름을 역으로 분석하여 복원한 semantic을 기반으로 하여 crash triage를 수행하는 방식을 제안했다. core dump의 내용을 분석하고, 어떤 instruction이 bad value를 할당하였는지를 찾아내는 것이다. 그러다보면 근원이 되는 'blame fuction'을 찾아낼 수 있게된다. 저자들의 말에 따르면 수백만의 Internet Explorer 버그 중복을 단 하나로 축약시킬 수 있었는데 반해 stack hasing은 이를 여러개의 다른 그룹으로 처리하였다고 한다.
2) Prioritization and Exploitability

퍼저의 taming problem이라 함은 결국 우선순위를 정하는 일이라고 할 수 있다. 버그를 유발하는 테스트 케이스가 다수 있을 때 이들 중 어떤 것이 더욱 위험도가 높다거나, 유일성을 가졌는지를 판단해야 하는 등의 문제이다. 결국 우선순위가 높다는 것은 이를 악용가능한 취약점을 통해 exploit 가능할 때와 직결된다. 공격자의 경우나 방어자의 입장에서 모두 exploit 가능 여부가 중대한 영향을 미친다.

exploitability 의 순위를 매기는 작업을 거의 최초로 수행한 것이 Microsoft의 !exploitable 이라는 WinDbg의 명령어이다. 나름대로의 heuristic 기준을 통해 4가지 단계(EXPLOITABLE > PROBABLY_EXPLOITABLE > UNKNOWN > NOT_LIKELY_EXPLOIABLE)로 구분한다(왼쪽일 수록 위험도가 높다는 의미). 이 외에도 GB의 exploitable plugin이나 Apple의 CrashWrangler라는 시스템들이 유사한 제안을 하였으나, 아직까지 이들의 정확성에 대해서 체계적인 연구나 평가분석이 진행되어 있지는 않다.

3) Test case minimization

테스트 케이스 최소화란 테스트 케이스 중 실제로 보안정책을 위반하게 되는 직접적인 원인만을 남겨둔 채 기타 부가적인 요소들은 최소화하는 것이다. 이는 결국 seed trimming과 유사한 개념으로, 입력값의 사이즈를 줄이려는 시도이다. 테스트 케이스를 최소화시킴으로써 버그 오라클의 성능을 향상시킬 수 있다.

BFF는 original seed 파일과 비교했을 때의 달라진 bit수를 최소화하는 자체적인 알고리즘을 사용하고 있으며, AFL이나 Lithum 역시 test case minimization을 통해 불필요한 부분을 제외시킴으로써 크기를 줄인다. 

퍼징 분야가 아닌 다른 쪽에서도 test case reducer에 대한 연구가 일부 있는데, delta debugging이나 C-Reduce 등이 있다. 이러한 기법들을 퍼징에 적용해보는 것도 좋은 시도가 될지도 모른다.

Configuration Update

ConfUpdate 단계는 블랙박스 테스팅을 다른 화이트, 그레이 박스 테스팅과 구분 짓는 가장 중요한 지표이다. 앞서 퍼즈 테스팅 알고리즘에서 살펴보았듯이, 기존의 수행 설정과 그에 따른 fuzzing run 수행 결과에 대한 정보를 토대로 다시금 configuration에 업데이트를 반영하는 과정이 있다. 그렇지만 블랙박스 퍼저의 경우 프로그램으로부터 어떠한 버그가 발생했는지, 버그 발생에 따라 어떠한 introspection 정보를 얻을 수가 없기 때문에 configuration을 딱히 수정할 수가 없다. 때문에 기존의 C를 변경하지 않은 채 다시 테스트를 수행할 뿐이다. 이와 반면, 그레이 박스나 화이트 박스 퍼저들은 보다 정확하게 confupdate를 하도록 구현되어 있다. 

Evolutionary Seed Pool Update

Evolutionary Algorithm(EA)는 생물학적 진화 이론에 등장하는 돌연변이, 재조합, 선택설 등의 휴리스틱 기반의 접근법이다. 퍼징의 맥락에서는 적절한 seed pool 을 구성하기 위해 EA를 적용한다. 이러한 기법은 AFL, LibFuzzer, syzkaller 등 다양한 grey box 퍼저에 영향을 주었다. 

EA에서 살펴볼 가장 중요한 것은 ConfUpdate 단계에서 새로운 conf를 어떻게 설정하느냐이다. 대부분의 EA기반 퍼저들이 택하는 방법은, 노드 혹은 브랜치 coverage를 계산하여 특정 테스트케이스에 의해 새로운 노드나 브랜치가 발견되는지를 찾는 것이다. 이것을 fitness function이라고 한다. 이러한 fitness 는 크게 두가지 전략이 있는데, 하나는 더욱 세밀하고 세분화된 개선 지표를 이용하는 것으로 AFL, STADS 등이 있다. 또 다른 기법은 복잡한 조건 분기의 식을 평가할 때 충족되는 비율을 측정하는 것으로, LAF-INTEL, LibFuzzer, Honggfuzz, go-fuzz, Steelix 등이 있다. 

VUzzer는 독특한 fitness function을 이용한 EA기반의 퍼저인데, 독자적인 방법으로 프로그램 분석을 수행하여 각 basic block들에 대한 가중치를 토대로 fitness를 측정하는 것으로 알려져있다. 

Maintaining a Minset

퍼징을 수행하며 새로운 config를 생성하는 작업은 한편으로는 다른 위험을 야기할 수 있는데, config가 지나치게 많아짐으로써 발생하는 문제이다. 대부분의 퍼저들은 이러한 위험을 완화하기 위하여 minset 전략을 사용한다. minset이란 coverage를 최대치로 만족시키는 test case의 최소 집합만을 구하는 것이다. 이는 앞서 Preprocess 단계에서 수행하는 minset 작업과 일맥상통하다. 어떤 퍼저들은 매우 독특한 기법을 confupdate에 적용하기도 하는데, 예를 들어 minset이 아닌 config들을 전부 지워버리려는 대신에, Favorable이라는 상태로 설정하여 이후의 schedule 단계에서 다른 case보다 월등히 높은 확률로 favorable 값을 선택하도록 하는 것이다. AFL 이 이러한 전략을 취하고 있는데, 그 저자는 "이러한 방식이 queue cycling speed와 test case diversity 사이에 적절한 균형을 맞춰줄 것이다"고 언급하였다. 


[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 1

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 2

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 3

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 4

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 5


Software Security Engineer

CPUU 님의 창작활동을 응원하고 싶으세요?

댓글

SNS 계정으로 간편하게 로그인하고 댓글을 남겨주세요.