[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey
원문 : https://arxiv.org/abs/1812.00140
[목차]
5. Input Generation
테스트 케이스가 버그 발생 여부와 직결되기 때문에, 입력 생성에 사용되기 때문에 입력 생성(:input generation)은 퍼저에서 가장 중요한 design decision 중 하나이다.
전통적으로 퍼저는 생성 기반(generation-based) 퍼저와 변이 기반(mutation-based) 퍼저로 분류할 수 있다. 생성 기반 퍼저는 PUT가 처리할 수 있는 입력 공간에 대한 모델을 기반으로 테스트 케이스를 생성한다. 본 논문에서는 이하 모델 기반(model-based) 퍼저라고 부르겠다.
반면 변이 기반 퍼저는 주어진 시드 입력을 기반으로 변이 시켜 테스트 케이스를 생성한다. 생성 기반 퍼저는 보통 모델이 없는 퍼저에서 사용된다. 그 이유는 시드는 단지 작은 예시일 뿐이고 대부분 PUT의 예상 입력 공간을 다 커버하지 못하기 때문이다.
본 절에서는 테스트 케이스 생성(INPUTGEN) 매커니즘을 기반으로 퍼저가 사용하는 다양한 입력 생성 방법을 다룬다.
5.1 Model-based (Generation-based) Fuzzers
생성 기반 퍼저가 테스트 케이스를 생성하기 위해 기반으로 사용하는 모델의 예시로 입력 형식을 특성화(:characterizing)하는 정확한 문법이나 파일 유형을 식벽하기 위해 magic value와 같은 덜 정확한 제약사항이 있다.
5.1.1 Predefined Model
사용자가 설정할 수 있는 모델을 사용하는 퍼저들도 있다.
Peach, PROTOS, Dharma는 사용자가 설정하는 모델을 사용다. Autodafe, Sulley, SPIKE, SPIKEfile은 사용자가 입력 모델을 생성 할 수 있는 API를 제공한다. Tavor는 EBNF(Extended Backus-Naur Form)로 작성된 명세(:specification)를 이용하여 해당 문법에 맞는 테스트 케이스를 생성한다. 유사하게 PROTOS, SNOOZE, KiF, T-Fuzz와 같은 네트워크 프로토콜 퍼저도 사용자로부터 프로토콜 명세를 받는다. 커널 API 퍼저 Trinity, syzkaller, KernelFuzzer, Triforce linux syscall fuzzer, perf fuzzer는 system call template의 형태로 입력 모델을 정의한다. 이런 템플릿은 보통 시스템 콜이 입력으로 사용하는 넘버링과 인자의 수를 지정한다. 모델을 기반으로 커널을 퍼징하는 아이디어는 Koopman의 연구 <Comparing operating systems using robustness benchmarks>에서 비롯되었다. 이 연구에서 OS의 강건함(:robustness)을 시스템 호출을 위해 선택한 유한한 테스트 케이스 set과 비교했다. Nautilus는 범용(general-purpose) 퍼징을 위해 문법(grammar) 기반 입력 생성을 사용하며, 이 문법을 시드 트리밍에서도 사용한다.
특정 언어나 문법을 대상으로 하며 언어 모델이 퍼저에 내장되어 있는 퍼저들도 있다. cross fuzz와 DOMfuzz은 랜덤한 DOM(Document Object Model) 객체를 생성한다. jsfunfuzz는 문법 모델을 기반으로 랜덤하지만 문법적으로 올바른 Javascript 코드를 생성한다. QuickFuzz는 파일 포멧을 설명하는 Haskell 라이브러리를 활용한다. Frankencerts, TLS-Attacker, tlsfuzzer, Ll-fuzzer와 같은 네트워크 프로토콜 퍼저들은 TLS나 NFC와 같은 특정 네트워크 프로토콜 모델을 기반으로 설계되었다.
Dewey는 연구 <Language fuzzing using constraint logic programming>와 <Fuzzing the rust typechecker using clp>에서 constraint logic programming을 활용하여 문법적으로 정확하면서, 의미론적으로(:semantically) 다양한 테스트 케이스를 생성하는 방법을 제안했다.
LangFuzz는 입력으로 주어지는 시드 set을 파싱 하여 코드 조각을 만든다. 그리고 랜덤하게 코드 조각(:fragment)을 결합하고 시드와 함께 변이 시켜 테스트 케이스를 생성한다. 문법(:grammar)을 기반으로 하기 때문에 문법적으로(:syntactically) 올바른 테스트 케이스를 생성할 수 있다. LangFuzz는 JavaScript와 PHP에 적용되었다. BlendFuzz는LangFuzz와 비슷한 아이디어를 기반으로 XML과 정규 표현식을 대상으로 한다.
5.1.2 Inferred Model
미리 정의되지 않거나 사용자가 제공하는 모델에 의존하지 않고, 모델을 추론(:infer)하는 방법이 최근 떠오르고 있다. 자동화된 입력 형식과 프로토콜 리버스 엔지니어링에 대한 연구가 있었다: <Tupni: Automatic reverse engineering of input formats>, <Polyglot: Automatic extraction of protocol message format using dynamic binary analysis>, <Deriving input syntactic structure from execution>, <Prospex: Protocol specification extraction>, <AUTHSCAN: Automatic extraction of web authentication protocols from implementations>. 하지만 이런 기술을 활용하는 퍼저는 거의 없었다. 모델 추론은 instrumentation처럼 PREPROCESS나 CONFUPDATE 단계에서 이루어질 수 있다.
5.1.2.1 Model Inference in PREPROCESS:
전처리 단계에서 모델을 추론하는 퍼저도 있다.
Test-Miner는 적절한 입력을 예측하기 위해 literal과 같은 PUT에서 사용 가능한 데이터를 검색한다. Skyfire는 일련의 시드와 문법이 주어지면 데이터 기반 접근 방식으로 확률론적 상황에 맞는(:context-sensitive) 문법을 추론하고, 시드 set을 생성한다. 다른 퍼저들과는 달리 의미론적으로(:semantically) 유효한 입력을 생성하는 데 중점을 둔다. IMF는 시스템 API 로그를 분석하여 커널 API 모델을 학습하고, 추론된 모델로 일련의 API call을 호출하는 C 코드를 생성한다. CodeAlchemist는 JavaScript 코드를 code brick으로 나누고 assembly 제약 조건을 계산한다. 이 제약으로 언제 의미론적으로 유효한 테스트 케이스를 생성하기 위해 서로 다른 브릭을 조합(:assemble) 하거나 병합(:merge) 할 수 있는지 알 수 있다. 이러한 제약은 정적 분석과 동적 분석을 모두 사용하여 계산된다. Neural과 Learn&Fuzz는 주어진 테스트 파일 set에서 모델을 학습하고, 추론 된 모델에서 테스트 케이스를 생성하기 위해 신경망 기반 기계 학습 기술을 사용한다. Liu는 연구 <Automatic text input generation for mobile testing>에서 텍스트 입력에 비슷한 접근 방식을 제안했다.
5.1.2.2 Model Inference in CONFUPDATE:
각 fuzz iteration 후에 모델을 업데이트할 수 있는 퍼저도 있다.
PULSAR는 프로그램에서 생성된 네트워크 패킷 set에서 네트워크 프로토콜 모델을 추론한다. 이후 학습된 네트워크 프로토콜을 이용해 프로그램을 퍼징한다. PULSAR는 내부에서 state machine을 설계하고 메시지 토큰을 state와 매핑한다. 이 정보는 더 많은 state를 커버하는 테스트 케이스를 생성하는 데 사용된다. Doupe는 연구 <Enemy of the State: A state-aware black-box web vulnerability scanner>에서 I/O 동작을 관찰하여 웹 서비스의 state machine을 추론하는 방법을 제안했다. 추론된 모델을 사용해 웹 취약점을 탐지한다. Ruiter의 연구 <Protocol state fuzzing of tls implementations>도 비슷하지만, 대상이 TLS를 대상으로 하며 LearnLib를 기반으로 구현했다. GLADE는 일련의 I/O 샘플에서 문맥 없는(:context-free) 문법을 합성하고, 추론 된 문법을 사용하여 PUT를 퍼징한다. go-fuzz는 시드 풀에 추가하는 각 시드에 대한 모델을 구축하는 그레이 박스 퍼저다. 이 모델은 해당 시드로부터 새로운 입력을 생성하는데 사용된다.
5.1.3 Encoder Model
퍼징은 특정 파일 형식을 파싱 하는 디코더 프로그램을 테스트하는데 자주 사용된다. 인코더 프로그램을 어떤 파일 형식의 암시적 모델로 생각할 수 있다.
MutaGen은 인코더 프로그램의 암시적 모델을 이용해 새로운 테스트 케이스를 생성하는 독특한 한 퍼저다. 대부분의 변이 기반 퍼저는 기존에 있던 테스트 케이스를 변이하는데, MutaGen은 인코더 프로그램을 변이한다. 특히 테스트 케이스를 생성하기 위해 인코더 프로그램의 dynamic program slice을 계산하고 실행한다. MutaGen은 program slice가 인코더 프로그램의 동작을 약간 변형하여 비정상적인 테스트 케이스를 생성한다는 아이디어를 기반으로 한다.
5.2 Model-less (Mutation-based) Fuzzers
고전적인 random testing[link1, link2]은 특정 경로 조건(:path condition)을 만족하는 테스트 케이스를 생성하는 문제에서 비효율적이다.
다음과 같은 C statement가 있다고 가정하자.
if (input == 42)입력이 32비트 integer라면, 올바른 input을 랜덤하게 맞출 확률은 이다. MP3 파일과 같이 잘 구조화된 입력을 생각해 보면 상황은 더욱 심각하다. 이 경우 random testing을 이용해 현실 시간 안에 유효한 테스트 케이스를 생성할 가능성은 매우 낮다. 이렇게 만들어진 테스트 케이스는 대부분 MP3 플레이어 프로그램의 파싱 단계에서 전부 막혀서 깊은 부분에 도달하지도 못할 것이다.
이런 문제 때문에 시드 기반 입력 생성과 화이트 박스 입력 생성이 논의되었다.
대부분의 변이 기반 퍼저는 시드를 변형하여 테스트 케이스를 생성한다. 시드는 일반적으로 PUT에서 지원하는 유형(파일, 네트워크 패킷, 일련의 UI event 등)을 잘 구조화한 입력이다. 유효한 파일의 일부만 변경하면 대부분 유효하면서, 크래시를 유발하는 비정상적인 값을 포함하는 테스트 케이스를 생성할 수 있다.
다음은 시드를 변이하는 다양한 기법들이다.
5.2.1 Bit-Flipping
Bit-flipping은 많은 변이 기반 퍼저들이 사용하는 기법이다. (AFL, hongfuzz, zuff, GPF, Radamsa)
고정된 수의 비트 수만큼만 플립(flip) 하는 경우도 있고, 플립 할 비트 수를 랜덤하게 정하는 경우도 있다. 시드를 랜덤하게 변이하기 이해, 각 INPUTGEN 실행마다 플립 할 비트 position의 수를 결정하는 mutation ratio라는 파라미터를 사용자가 설정할 수 있도록 한다. 퍼저가 N 비트의 시드 중 K 개의 비트를 플립 한다면 이때 mutation ratio는 K/N이다. SymFuzz는 퍼징 성능이 mtation ratio에 민감하며, 모든 PUT에 대해 잘 동작하는 ratio는 없다는 것을 입증했다.
적당한 mutation ratio를 찾는 몇 가지 접근 방식이 있다. BFF와 FOE는 각 시드에 대해 지수 단위로 커지는 mutaton ratio set을 이용해 통계적으로 효과가 입증된 ratio만 더 많이 반복한다. SymFuzz는 각 시드에 대해 효과적인 mutation ratio를 찾기 위해 화이트 박스 프로그램 분석 방법을 사용한다.
5.2.2 Arithmetic Mutation
AFL과 honggfuzz는 선택된 byte sequence를 integer로 취급하여 그 값에 대해 간단한 산술(:arithmetic) 연산을 수행하는 변이 기법을 사용한다.
계산된 값은 선택된 byte sequence를 대체하는데 사용된다. 변이하는 크기를 작게 제한하는 것이 중요하다. AFL은 시드에서 4 바이트 값을 선택하는데, 이를 integer 라고 하자. 랜덤하게 선택된 작은 integer 을 이용해 를 로 대체한다. 의 범위는 퍼저마다 다른데 사용자가 설정할 수 있도록 하는 경우도 있다. 예를 들어 AFL은 가 기본 설정이다.
5.2.3 Block-based Mutation
시드의 byte sequence를 block이라고 하자. 몇 가지 블록 기반 변이 기법을 소개한다.
- 랜덤하게 생성된 블록을 시드의 랜덤 한 위치에 삽입하는 방법. (AFL, LibFuzzer)
- 시드에서 랜덤하게 선택된 블록을 제거하는 방법. (AFL, radamsa, honggfuzz, LibFuzzer)
- 랜덤하게 선택된 블록을 랜덤 한 값으로 대체하는 방법. (AFL, honggfuzz, radamsa, LibFuzzer)
- 일련의 블록들의 순서를 임의로 바꾸는 방법. (radamsa, LibFuzzer)
- 랜덤 한 블록을 시드 뒤에 추가하는 방법. (honggfuzz)
- 시드끼리 랜덤 한 블럭을 추가하거나 삽입하는 방법. (AFL], LibFuzzer)
5.2.4 Dictionary-based Mutation
0이나 -1과 같이 잠재적으로 중요한 의미론적 가중치(:semantic weight) set을 미리 정의해서 사용하거나 변이를 위한 format string을 사용하는 퍼저도 있다.
AFL, hongfuzz, LibFuzzer는 integer를 변이할 때 -1, 0, 1을 사용한다. Radamsa는 유니코드 스트링을 사용한다. GPF는 %x나 %s와 같은 format string을 이용해 문자열을 변이한다.
5.3 White-box Fuzzers
화이트 박스 퍼저 역시 모델 기반 퍼저와 변이 기반 퍼저로 나눌 수 있다.
전통적인 dynamic symbolic execution(SAGE, jFuzz, FuzzBALL, Driller)은 변이 기반 퍼저처럼 모델이 필요 없지만, 일부 symbolic executor(SAGE, MoWF, CAB-Fuzz)는 input grammar와 같은 입력 모델을 사용하기도 한다.
[SAGE의 경우 전자는 <Automated Whitebox Fuzz Testing>, 후자는 <Grammar-based Whitebox Fuzzing>에 해당한다.]
Godefroid의 SAGE를 포함한 많은 화이트 박스 퍼저가 dynamic symbolic execution을 사용해 테스트 케이스를 생성하는데, 모든 화이트 박스 퍼저가 그런 것은 아니다. TaintScope, SymFuzz, GRT, FLAX와 같은 퍼저들은 white-box program analysis를 사용해 PUT가 그레이 박스와 블랙 박스 퍼징에서 사용할 수 있는 입력에 대한 정보를 찾는다.
하위 섹션에서는 기본 테스트 케이스 알고리즘을 기반으로하는 기존 화이트 박스 퍼징 기술을 간략하게 요약한다. 앞서 언급 한 것처럼 fuzzer라는 용어를 쓰지 않은 symbolic executor들은 다루지 않는다.
[생략한 symbolic executor는 다음과 같다: <DART: Directed automated random testing>, <CUTE: A concolic unit testing engine for C>, <S2E: A platform for in-vivo multi-path analysis of software systems>, <KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs>, <Pex–white box test generation for .NET>, <Unleashing mayhem on binary code>]
5.3.1 Dynamic Symbolic Execution
고전적인 symbolic execution은 모든 가능한 값을 나타내는 symbolic value을 입력으로 프로그램을 실행한다: <Symbolic execution and program testing>, <SELECT-a formal system for testing and debugging programs by symbolic execution>, <Methodology for the generation of program test data>. symbolic execution은 PUT을 실행할 때 구체적인(:concrete) 값 대신 symbolic expression을 생성한다. 그리고 조건부 분기문 instruction에 도달할 때마다 개념적으로 두 개의 symbolic interpreter를 분기한다. 하나는 진짜 분기를 위한 것이고, 다른 하나는 가짜 분기를 위한 것이다. 모든 경로에서 symbolic interpreter가 실행 중 분기문을 마주칠 때마다 path formula(또는 path predicate)를 생성한다. 원하는 경로를 실행하는 concrete 한 입력이 식(path formula)을 만족할 수 있다. path formula에 대한 해인 concrete input은 SMT solver를 이용해 계산할 수 있다.
dynamic symbolic execution(이하 DSE)은 symbolic execution의 변형으로, symbolic execution과 concrete execution 연산을 동시에 할 수 있다. 이러한 이유로 DSE를 concolic (concrete + symbolic) testing이라고도 한다. DSE는 concrete execution state가 symbolic constraint의 복잡성을 줄이는데 사용될 수 있다는 아이디어를 기반으로 하고 있다. DSE에 대한 방대한 연구를 다루는 것은 본 논문의 범위를 벗어난다. 따라서 필요한 독자들을 위해 연구를 소개한다: <An orchestrated survey of methodologies for automated software test case generation>, <All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask)>.
DSE는 PUT의 모든 instruction을 instrument하고 분석하기 때문에 그레이 박스나 블랙 박스 방식에 비해 느리다. 이런 문제를 해결하는 방법은 사용량을 줄이는 것이다.
예를 들어 사용자가 불필요해 보이는 코드 부분을 지정(Chopper)하거나 concolic testing 또는 그레이 박스 퍼징을 번갈아 가며 사용하는 방법이 있다. Driller와 Cyberdyne는 DARPA Cyber Grand Challenge에서 이 기술의 유용성을 보여주었다. QSYM은 빠른 concolic execution 엔진을 구현하여 그레이 박스 퍼징과 화이트 박스 퍼징 간의 통합을 개선하였다. DigFuzz는 먼저 그레이 박스 퍼징을 사용하여 각 경로를 실행할 확률을 추정한 다음 가장 challenging 한 경로만 화이트 박스 퍼징을 적용하여 화이트박스와 그레이 박스 퍼징 사이의 스위칭을 최적화했다.
5.3.2 Guided Fuzzing
퍼징의 효과를 높이기 위해 정적 또는 동적 프로그램 분석 기술을 사용하는 퍼저도 있다. 이러한 기술은 보통 퍼징에 다음 두 단계를 포함한다.
- PUT에 대한 유용한 정보를 얻기 위해 코스트가 많이 드는 프로그램 분석
- 이전 분석을 기반으로 테스트 케이스 생성
예를 들어 TaintScope은 중요한 system call 또는 API 호출로 유도되는 입력 바이트인 hot bytes를 찾기 위해 fine-grained taint analysis 기법을 사용한다. <Targeted taint driven fuzzing using software metrics>와 <0-knowledge fuzzing>에서도 이와 비슷한 아이디어가 제시되었다. Dowser는 컴파일 과정에서 휴리스틱(heuristic)을 기반으로 버그가 있을 것 같은 loop을 정적으로 분석한다. 특히 포인터 역참조를 포함하는 loop을 찾는다. 그런 다음 taint analysis를 통해 입력 바이트와 해당 loop 간의 관계를 계산한다. 이후 DSE를 실행하면서 중요한 바이트만 기호화(:symbolic) 하는 방법으로 성능을 향상시켰다. VUzzer와 GRT는 PUT에서 control-flow와 data-flow feature를 추출하고 이를 기반으로 PUT를 실행하기 위해 정적과 동적 분석 방법을 모두 사용한다.
Angora와 Red Queen은 분석에 대한 코스트를 줄이기 위해 코스트가 큰 instrumentation으로 각 시드를 먼저 실행하고, 이 정보로 더 가벼운 instrumentation을 생성하는 방법을 사용했다. Angora는 taint analysis를 사용해 각 path constraint를 해당 바이트에 연결하는 방법으로 "hot bytes" 아이디어를 개선했다. 그런 다음 gradient descent 알고리즘에서 영감을 받은 search 알고리즘을 기반으로 이러한 제약을 해결하기 위한 변이를 수행한다. 반면 RedQueen은 PUT에서 입력이 사용되는 방식을 감지하기 위해 모든 comparison을 instrument 하고 피연산자(:operand)와 주어진 입력 간의 대응 관계를 찾는 방법을 사용한다. 만약 일치하는 항목을 찾았다면 제약을 해결하는 데 사용할 수 있다.
5.3.3 PUT Mutation
실무에서 퍼징을 사용하다 보면 체크섬(checksum) 검사를 우회해야 하는 경우가 많다. 예를 들어 PUT가 입력을 파싱 하기 전에 체크섬을 계산한다면 많은 테스트 케이스가 파싱 되기도 전에 reject 될 것이다.
이런 문제를 해결하기 위해 TaintScope은 tiant analysis를 이용해 체크섬을 확인하는 instruction을 식별하고, PUT를 패치해 이를 우회하는 일명 체크섬-인지(:checksum-aware) 퍼징 기법을 제안했다. 크래시를 찾으면 입력에 대한 올바른 체크섬을 생성하여 패치 전 PUT에 크래시를 발생시키는 테스트 케이스를 생성한다.
Caballero는 BitFuzz에서 체크섬이 있는 상태에서 테스트 케이스를 생성할 수 있는 stitched dynamic symbolic execution 기술을 제안했다.
T-Fuzz는 이 아이디어를 확장하여, 그레이 박스 퍼징으로 모든 종류의 conditional branch를 효율적으로 침투하는 방안을 제시했다. 먼저 프로그램 로직을 수정하지 않고 변환할 수 있는 branch인 NCC(Non-Critical Checks) set을 생성한다. fuzzing campaign이 새로운 경로를 찾는 것을 멈추면 NCC를 변환한 다음 바뀐 PUT에서 fuzzing campaign을 다시 시작한다. 수정된 PUT에서 크래시를 발견하면, symbolic execution을 이용해 기존 PUT에서 재구성한다.
Uploaded by Notion2Tistory v1.1.0