[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey
원문 : https://arxiv.org/abs/1812.00140
[목차]
6. Input Evaluation
입력을 생성하고 나면 퍼저는 그 입력으로 PUT를 실행하고 resulting execution으로 무엇을 수행할지 결정하는데, 이 과정을 input evaluation이라고 한다.
단순하게 PUT 실행하는 것이 퍼징의 매력 중 하나이지만, 퍼저의 성능과 효과에 영향을 미치는 많은 최적화 방법과 design decision들이 있다.
6.1 Bug Oracles
segmentation fault와 같은 fatal signal에 의해 프로그램이 종료될 경우 대표적인 보안 정책을 위반한다고 말할 수 있다. 데이터나 코드 포인터가 잘못된 값으로 overwritnig되는 메모리 취약점으로 인해 segmentation fault가 발생하거나 역참조로 인해 abort가 발생했을 때 프로그램이 종료되기 때문에 이 보안 정책으로 많은 메모리 취약점을 탐지할 수 있다. 또한 OS가 이런 예외 상황으로 trap하기 때문에 이런 보안 정책은 효과적이고 구현도 쉽다.
그러나 크래시만 탐지하는 기존의 보안 정책으로 모든 메모리 취약점을 탐지할 수는 없다. 예를 들어 스택 버퍼 오버플로우가 발생했는데, 스택 포인터가 유효한 메모리 주소로 덮어씌워질 수 있다. 이 경우 프로그램은 오작동하겠지만 크래시가 발생하지는 않아서 퍼저가 이를 감지할 수 없다.
이런 문제를 해결하기 위해 안전하지 않거나 원하지 않는 동작을 탐지하고 abort 하는 다양한 sanitizer라는 방법이 고안되었다.
6.1.1 Memory and Type Safety
memory safety bug는 크게 두 가지로 분류할 수 있다.
- spatial : 포인터가 가리키는 객체 외부에서 포인터가 역참조 되는 경우. 버퍼 오버플로우와 언더 플로우가 대표적인 예시이다.
- temporal : 더 이상 유효하지 않은 주소를 가리키는 포인터에 접근하는 경우. 메모리 할당 이후 반환된 주소를 가리키는 포인터에 접근할 때 발생하는 use-after-free 취약점이 대표적인 예시이다.
ASan(Address Sanitizer)은 instrument를 통해 컴파일 시간에 빠르게 메모리 버그를 탐지할 수 있는 도구다. Asan은 spatial/temporal 메모리 버그를 모두 탐지할 수 있으며, 속도 저하가 73%밖에 되지 않아 매력적인 대안이 될 수 있다. Asan은 각 메모리 주소가 역참조되기 전에 빠르게 유효성을 검사할 수 있는 shadow memory를 사용한다. 덕분에 크래시가 발생하지 않더라도 unsafe memory에 접근하는 많은 경우들을 탐지할 수 있다.
MEDS는 64비트 환경에서 사용할 수 있는 큰 메모리 공간을 활용하여 할당된 개체 사이에 접근할 수 없는 memory redzone chunk를 생성하는 방법으로 Asan을 개선했다. redzone은 corrupted pointer가 잘못된 메모리를 가리키면 크래시를 일으킬 확률을 높였다.
SoftBound/CETS(link1, link2)도 instrument를 통해 컴파일 시간에 메모리 버그를 탐지할 수 있는 도구다. 유효한 메모리 주소를 추적하는 Asan과 달리, bound와 temporal 정보를 모든 포인터와 연결하여 이론적으로 모든 spatial/temporal 메모리 버그를 탐지할 수 있다. 하지만 평균 116%의 높은 오버 헤드를 감안해야 한다는 단점이 있다.
CaVer, TypeSan, HexType instrument 프로그램은 컴파일 시간에 C++ 타입 캐스팅 버그를 탐지할 수 있다. 타입 캐스팅 버그는 base class 객체가 derived type으로 캐스팅 되는 경우와 같이 호환되지 않는 타입으로 캐스팅될 때 발생한다. CaVer는 타입 캐스팅 버그가 많이 발견된 웹 브라우저로 대상을 확장하였고, 7.6% ~ 64.6%의 오버헤드가 발생하는 것을 보였다.
또 다른 종류의 memory safety protection인 CFI(Control Flow Integrity)는 원본 프로그램과 실행 중인 프로그램의 control flow를 비교하여, 원본 프로그램에서 불가능한 control flow를 런타임에 감지한다(link1, link2). 이는 프로그램의 흐름을 비정상적으로 수정한 테스트 케이스를 탐지하는 데 사용할 수 있다. 프로그램을 CFI 위반 관련 버그로부터 보호하는 것에 초점을 맞춘 최근 프로젝트는 gcc와 clang 컴파일러에 포함되었다(link).
6.1.2 Undefined Behaviors
C와 같은 언어에서는 언어 자체 명세에 정의하지 않은 일명 undefined behavior가 많다. 이런 경우 컴파일러가 다양한 방식으로 처리할 수 있다. 많은 경우 일부 컴파일러에서만 적합한 코드를 작성한다. 아주 위험해 보이진 않지만 최적화 설정, 아키텍쳐, 컴파일러, 컴파일러 버전 등 많은 요소들이 undefined behavior로 이어질 수 있다. undefined behavior의 구현이 개발자의 의도와 컴파일러의 구현이 일치하지 않을 경우 종종 취약점과 버그가 발생하곤 한다(link).
MSan(Memory Sanitizer)은 C/C++에서 초기화하지 않은 메모리에 접근할 때 발생하는 undefined behavior를 컴파일 도중에 탐지하는 instrument 프로그램이다. 각 addressable bit는 초기화 여부를 나타내는 shadow memory를 사용한다. Msan의 오버헤드는 약 150%이다.
UBSan(Undefined Behavior Sanitizer)은 undefined behavior를 탐지하기 위해 컴파일 시간에 프로그램을 수정한다. undefined bebavior의 한 가지 특정 원인에 초점을 맞춘 다른 sanitizer들과 달리 잘못된 포인터, zero division, 널 포인터 역참조, integer 오버플로우과 같이 다양한 undefined behavior를 탐지한다.
TSan(Thread Sanitizer)은 컴파일 시간에 수정하는데, 정확도와 성능의 균형을 유지하면서 data race를 감지한다. data race는 두 개의 스레드가 동시에 공유 메모리에 접근하고 최소 하나의 스레드가 write를 수행할 때 발생한다. 이런 버그는 data corruption을 발생시키는데, 비결정론적이기 때문에 버그를 재현하는 것이 매우 어렵다.
6.1.3 Input Validation
XSS(ceoss site scripting)과 SQL injection과 같은 input validation 취약점을 테스팅 하는 것은 매우 어렵다. 이런 취약점은 매우 복잡한 웹 브라우저와 db 엔진 파서의 동작을 이해해야 하기 때문이다.
KameleonFuzz는 실제 웹 브라우저로 테스트 케이스를 분석하고, Document Object Model tree를 추출하고, XSS 공격이 성공했음을 나타내는 패턴과 비교하여 XSS 공격의 성공을 감지합니다.
μ4SQLi는 SQL injection을 탐지하기 위해 비슷한 방법을 사용한다. 웹 어플리케이션에 프로그램의 response에서 SQL injection을 안정적으로 탐지할 수는 없다. 따라서 μ4SQLi는 타겟 웹 어플리케이션에 프로그램과 DB 사이의 통신을 차단하는 DB proxy를 사용하여 입력이 유해한 동작을 트리거 했는지 여부를 탐지한다.
6.1.4 Semantic Difference
semantic 버그는 유사하지만 동일하지는 않은 프로그램의 동작을 비교하는 차분 테스팅(:differential testing) 기술에서 종종 볼 수 있다.
비슷한 프로그램 간의 (버그로 동작할 수 있는) 불일치(:discrepancies)를 식별하기 위해 차분 테스트를 사용한 퍼저들도 있다: Frankencerts, NEZHA, classfuzz. orangfuzz는 단일 프로그램에서 여러 입력의 차분 테스트를 사용하여, PUT의 입력에서 출력으로의 변이를 매핑하는 블랙 박스 차분 퍼징을 도입했다. 이런 매핑은 information leak을 탐지하는데 사용된다.
6.2 Execution Optimizations
제안한 model fuzzer는 개별적인 각 fuzz iteration들이 순차적으로 실행되는 모형이었다. 이런 접근 방식으로 단순하게 생각해 본다면 fuzz iteration 초기에 PUT를 로드하기 위해 매번 새로운 프로세스를 생성해야 할 것이다. 하지만 이런 방식은 성능 저하가 클 것이다. 이런 문제를 해결하기 위해 현대 퍼저는 반복적인 프로세스 로딩 과정을 건너 뛸 수 있는 방법을 제시했다.
예를 들어 AFL은 각 fuzz iteration마다 이미 초기화 과정이 끝난 상태의 프로세스를 fork 해주는 fork-server를 제공한다. 이와 유사한 in-memory 퍼징 기법도 실행 속도를 최적화할 수 있다. Xu는 연구 <Designing New Operating Primitives to Improve Fuzzing Performance>에서 fork() 함수를 대체하는 새로운 system call을 설계하여 반복의 비용을 더욱 낮추었다.
6.3 Triage
triage는 보안 정책을 위반하는 테스트 케이스를 분석하고 보고하는 과정이다.
보통 다음 세 단계로 나눌 수 있다: 중복제거(deduplication), 우선순위 지정(prioritization), 테스트 케이스 최소화(test case minimization)
6.3.1 Deduplication
중복제거(deduplication)란 발견한 버그 set에서 동일한 버그를 트리거 하는 테스트 케이스를 정리하는 과정이다. unique한 버그를 트리거 하는 테스트 케이스들만 남길 수 있다면 아주 이상적이다.
중복 제거는 퍼저에서 아주 중요한 과정이다.
실무에서 중복된 버그를 저장해두면 하드디스크 공간이나 다른 자원이 낭비될 수 있다. 또한 중복된 버그를 제거하면 사용자 관점에서 얼마나 많은 버그를 발견했는데 쉽게 이해하고 분석할 수 있다.
이는 다양한 퍼저 사용자에게 유리하다. 예를 들어 공격자는 reliable exploitation이 가능한 취약점만 찾으려 할 것이다.
현재 실무에서 주로 사용되는 중복제거 기법 세 가지는 다음과 같다: stack backtrace hashing, coverage-based deduplication, semantics-aware deduplication.
6.3.1.1 Stack Backtrace Hashing:
stack backtrace hashing은 크래시의 중복제거를 위해 가장 오래되고 널리 사용되는 방법 중 하나이다. 크래시 발생 시 자동화 도구가 stack backtrace를 기록하고 이를 기반으로 stack hash를 할당한다.
예를 들어, 어떤 프로그램의 foo() 함수에서 코드를 실행하는데 크래시가 발생했고 이때 call stack이 아래 Figure 2처럼 main() -> d() -> c() -> b() -> a() -> foo()라고 가정하자.
- Figure 2: Stack backtrace hashing example.
이 경우 n=5인 stack backtrace hashing이 d() -> c() -> b() -> a() -> foo() call stack을 가지면서 크래시가 발생한 다른 테스트 케이스들과 그룹화한다.
stack hashing의 구현 방식은 다양하다. 해시에 포함된 stack frame의 수를 예로 들자면, CrashWrangler는 1개, SmartFuzz와 Woo의 퍼저는 3개, gdb-exploitable이나 BFF는 5개, 그리고 제한이 없는 경우도 있다. stack frame에 포함 된 정보의 양도 구현 방식마다 다르다. 함수명이나 주소의 해시값만 정보에 포함시키는 경우도 있고, 함수명과 함께 offset이나 line number을 함게 해싱하는 경우도 있다.
두 경우 모두가 항상 잘 동작하는 것은 아니어서, 이를 보완하기 위해 major/minor 두 개로 나누어 hash하는 경우도 있다: (!exploitable, gdb-exploitable). major hash는 함수명만 해시하여 서로 다른 크래시들을 같은 그룹으로 묶을 가능성이 높다. minor hash는 함수명과 line number를 해시하고 stack frame의 수에 제한이 없기 때문에 더 정확하다.
stack backtrace hashing도 단점이 있다. stack backtrace hashing는 유사한 크래시가 유사한 버그로 인해 발생하고, 그 역도 성립한다는 것을 전제로 하고 있다. 그러나 아직까지 이 가설이 명확하게 규명된 것은 아니다. 일부 크래시는 그 크래시를 일으킨 코드 근처에서 발생하지 않기 때문에, 이 전제를 의심해볼 만하다. 예를 들어, heap corruption 취약점은 힙 오버플로우가 아닌 코드의 관련 없는 부분이 메모리를 할당하려 할 때마 크래시가 발생한다.
6.3.1.2 Coverage-based Deduplication:
AFL은 PUT의 각 실행에 대한 edge coverage를 기록하고 각 edge에 대한 대략적인 hit count를 측정하기 위해 효율적인 소스 코드 instrumentation을 사용한다. 그레이 퍼저인 AFL은 주로 이 edge 커버리지 정보를 사용해 새로운 시드 파일을 선택한다.
게다가 이 방식은 독특한 중복 제거 기법으로 이어진다. 이전에 볼 수 없었던 edge를 커버했거나, 모든 이전 크래시들에 존재하던 edge를 커버하지 않은 경우 AFL은 이를 unique 한 크래시라고 간주한다.
6.3.1.3 Semantics-aware Deduplication:
RETracer는 각 크래시에서 reverse data-flow analysis로부터 복구된 semantic을 기반으로 crash triage(분류)를 수행한다. 특히 RETracer는 crash dump(core dump)를 분석하여 어떤 포인터가 충돌을 일으키는지 확인하고, 어떤 instruction이 비정상적인 값을 할당했는지 재귀적으로 식별한다. 그리고 maximum frame level이 있는 함수를 찾아 blame한다. 문제를 일으킨 blame function은 cluster crash에 사용할 수 있다.
RETracer의 저자들은 그들의 기술이 성공적으로 수백만 개의 인터넷 익스플로러 버그를 하나로 통합(dedupe)했다는 것을 보여주었다. 반대로, stack hashing 기술은 동일한 크래시를 다른 종류의 버그라고 분류했다고 한다.
6.3.2 Prioritization and Exploitability
fuzzer taming problem이라고도 불리는 prioritization(이하 우선순위 설정)은 그 심각도(:severity)와 고유성(:uniqueness)에 따라 보안 정책을 위반하는 테스트 케이스의 순위를 매기거나 분류하는 과정이다.
퍼징은 전통적으로 메모리 취약점을 발견하는데 사용되어 왔으며, 이런 관점에서 prioritization은 크래시의 exploit 가능성을 결정하는 문제로 더 잘 알려져 있다. exploit 가능성은 테스트 케이스의 취약점을 이용해 실질적인 exploit을 할 수 있는 가능성을 의미한다.
방어자와 공격자 모두 exploit 가능한 버그에 관심이 있다. 방어자는 일반적으로 exploit 불가능한 버그보다 exploit 가능한 버그를 먼저 패치(:fix)한다. 공격자는 추후 악용을 위해 exploit 가능한 버그에 관심이 있다.
최초의 exploitability ranking system은 Microsoft의 !exploitable이다. !exploitable은 WinDbg의 명령어에서 이름을 따왔다. !exploitable은 단순화 된 taint analysis(link1, link2)와 쌍을 이루는 몇 가지 휴리스틱(:heuristics)을 사용한다.
각 크래시를 다음과 같은 severity scale로 분류된다: EXPLOITABLE > PROBABLY_EXPLOITABLE > UNKNOWN > NOT_LIKELY_EXPLOITABLE (왼쪽이 더 심각함)
이러한 분류가 공식적으로 정의되어 있지는 않지만, !exploitable은 비공식적으로 전통적(:conservative)이고 exploitable 한 것을 더 잘 report 하는 편이다. 예를 들어, 공격자가 control flow를 제어할 수 있었다는 가정을 바탕으로 잘못된 instruction이 실행될 경우 크래시가 EXPLOITABLE 하다고 판단한다. 반면 division by zero crash는 NOT_LIKELY_EXPLOITABLE라고 판단한다.
!exploitable이 도입된 이후, GDB 용 exploitable plugin과 Apple의 CrashWangler를 포함한 rule-based 휴리스틱 시스템이 제안되었다. 그러나 그 정확성은 아직 체계적으로 연구되고 평가되지 않았다.
6.3.3 Test case minimization
테스트 케이스 최소화(:test case minimization) 역시 triage의 중요한 부분이다. 테스트 케이스 최소화는 보안 정책 위반을 트리거 하는 데 필요한 violating test case의 부분(:portion)을 식별하는 과정이다. 또한 선택적으로 원본보다 더 작고 단순하지만. 여전히 violation을 유도하는 테스트 케이스를 생성한다.
테스트 케이스 최소화와 시드 트리밍은 입력의 크기를 줄인다는 점에서 개념적으로 유사하지만, minimizer는 버그 오라클을 활용할 수 있다는 점이 다르다.
테스트 케이스 최소화를 위해 자체 구현 방식이나 알고리즘을 사용하는 퍼저도 있다.
BFF는 oiginal seed file과 다른 비트 수를 최소화하는 알고리즘을 사용한다. AFL의 test case minimizer는 (opportunistically) 바이트를 0으로 설정하여 테스트 케이스의 길이를 줄인다. Lithium은 인접한 라인(:adjacent line) 또는 바이트의 "chunk"를 지수 단위로 감소하는 크기로 제거해 최소화하는 범용(:general purpose) 테스트 케이스 최소화 도구다. Lithium은 jsfunfuzz와 같은 자바 스크립트 퍼저에 의해 생성 된 복잡한 테스트 케이스에서 아이디어를 얻었다.
퍼징을 위해 설계되지는 않았으나 퍼징으로 식별된 테스트 케이스에 사용할 수 있는 다양한 테스트 케이스 최소화 기법이 있다. delta debugging과 같이 형식에 구애받지 않는 기법이나, C/C++ 파일 용 C-Reduce와 같이 특정 형식에 대한 기법이 이에 해당한다. 후자의 경우 적용할 수 있는 파일 형식에 제한이 있지만, 문법에 대한 이해가 있기 때문에 훨씬 더 효율적일 수 있다.
Uploaded by Notion2Tistory v1.1.0