주요 내용으로 건너뛰기

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

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

Input Generation

본 장에서는 Input Generation을 위해 사용되는 다양한 기법들을 설명한다. 테스트 케이스를 통해 전달되는 데이터의 내용이 곧바로 버그를 발생시키는지의 여부와 직접적인 연관이 있기 때문에, 어떠한 입력값을 만들어내는지를 주관하는 기술은 Fuzzer의 가장 핵심적인 설계 요소라고 할 수 있다. 전통적으로는 생성(generation) 기반 퍼저와 변이(Mutation) 기반 방식으로 나뉜다. 생성 기반은 PUT이 처리할 수 있는 입력값 데이터에 대한 모델을 주고 이를 기반으로 새로운 테스트 케이스를 만들도록 한다. 이를 model-based fuzzer라고 부르도록 하겠다. 반면 변이 기반 펴 저는 주어진 seed를 기반으로 하여 약간의 변이를 주면서 다음 테스트 케이스를 생성한다. 때문에 mu제목 1tation기반 퍼저를 일반적으로 model-less fuzzer라고 부르기도 하는데, 왜냐하면 seed는 극히 작은 입력일 뿐이며, PUT의 모든 예상 입력 공간을 완전히 감당하지는 못하기 때문이다.  


Model-based(Generation-based) Fuzzers

모델 기반 퍼지는 PUT이 수용할 수 있는 입력 또는 실행을 설명하는 주어진 모델을 기반으로 테스트 케이스를 생성한다. (예 : 입력 형식을 정확하게 특성화하는 문법 기반 강력한 조건이나, 파일 유형만을 식별하는 Magic value과 같은 비교적 덜 정밀한 제약 조건). 

i.Predefined Model : 

사전 정의에 따른 모델은 보통 사용자가 직접 관련된 설정값을 지정하도록 한다. 분석가가 EBNF와 같은 문법으로 해당 프로그램의 입력값 또는 프로토콜의 명세 알맞은 모델링을 수행하여 지정한다. 이러한 방식은 특정 프로그래밍 언어 혹은 문법에 대해서도 적용할 수 있다. 예를 들어 LangFuzz는 주어진 입력값을 분석하여 code fragment라는 단위로 쪼개고, 이들을 무작위로 배치하고 또 seed에 변화를 주는 방법으로 테스트 케이스를 생성한다. 이 방법은 Javascript 문법에 적확할 뿐 아니라 의미적으로도 바른 코드를 만들어낸다.  

ii.Inferred Model : 

사전 정의된 로직 또는 사용자 제공 모델에 의존하는 것보다는 모델을 스스로 추론하는 것이 최근에 주목을 받고 있다. 이는 자동화된 입력값 생성이나 프로토콜 역공학 분야에서는 많은 연구가 이루어졌지만 아직 퍼저에서는 이러한 기술이 많이 적용되지는 않았다. 모델 추론은 Preprocess 단계 혹은 ConfUpdate 단계에서 적용될 수 있다. IMF 퍼저의 경우 Preprocess 단계에서 system API Log를 분석하여 kernel API의 모델을 학습하고, 이러한 API call의 sequence를 작성하는 C code를 만드는 일명 inferred model을 만든다. 또한 최근에는 neural network 기반의 머신 러닝 기법으로 테스트 케이스를 만들어내는 Learn&Fuzz 와 같은 퍼 저도 있다. 반면 ConfUpdate 단계에서 모델을 추론하기 위해서는 각 fuzz iteration에서 모델 업데이트를 수행한다. 이와 같은 퍼저로는 네트워크 프로토콜 퍼 저인 PULSAR 등이 있다. 

Model-less(Mutation-based) Fuzzers 

고전적인 랜덤 테스팅은 특정 조건을 만족하는 path를 찾는 test case를 생성하는 데 있어서 비효율적인 접근이다. 예를 들어 if(input ==42)라는 구문이 있다고 하자. 만약 input이 32-bit 정수형이라고 생각한다면 이를 단순히 찍어서 맞출 수 있는 확률은 1/2^32로 상당히 힘든 수준이다. 게다가 만약 MP3와 같은 파일을 퍼징 한다고 생각해보자. MP3 파일을 유효하게 하기 위한 구조가 있는데, 이를 찍어서 맞춰내는 것은 현실적인 시간 안에 거의 불가능에 가깝다. 무작위로 만들어진 파일을 MP3 플레이어에 삽입해봤자 거의 대부분은 parsing 단계에서 실패하고 말 것이고, MP3 플레이어 내부의 깊은 부분에 도달하기도 전에 대부분 거절되고 말 것이다. 이때 white-box input generation에서 사용되는 seed 기반 input generation 방법이 한 가지 힌트가 될 수 있다. PUT의 입력값을 seed로 하여 그 seed 값을 mutate 하는 방식으로 새로운 테스트 케이스를 만드는 것이 대부분의 Model-less 퍼저들이 수행하는 방식이다. 이때 seed 들은 PUT에 적용될 수 있도록 구조화가 잘 되어 있는 것이며, 파일, 네트워크 패킷, 일련의 UI 이벤트들이 될 수 있다. 유효한 파일이 주어지면 그것의 일부분만을 살짝 변경함으로써, 나머지 대부분의 내용은 여전히 유효하지만 일부분의 비정상 값에 의해 PUT의 충돌을 유발하도록 하는 테스트 케이스를 만드는 것을 목표로 한다. 이처럼 seed를 mutate 하는 방법은 다양하게 존재하지만 그중 대표적인 것들은 아래와 같다. 

i.Bit-Flipping : 고정된 몇 개의 bit를 변경하거나, 그 개수마저 무작위로 변경하는 방식. mutation ratio를 사용자가 parameter로 지정하도록 하기도 한다. 
ii.Arithmetic Mutation : AFL이나 honggfuzz는 정수의 byte sequence 일부를 찾아서 그 부분을 치환한다. 예를 들어 i라는 값을 i ± r로 바꾸는데 이때 r은 0 <= r < 35에 해당하도록 한다. 
iii.Block-based Mutation : 시드의 byte sequence를 block이라고 정의하고, 해당 seed에서 무작위적인 위치에 새로운 block을 삽입하거나 기존 block을 일부 삭제하는 등의 방법이다. 그 외에 블록 내용을 변경하거나 순열의 조합을 변경, 덧붙이기, 짜깁기 등의 변형 또한 가능하다. 
iv.Dictionary-based Muation : 잠재적으로 큰 영향을 끼치는 가중치가 높은 값들을 미리 파악한 경우, 이들을 0 또는 -1, 1로 매핑시킬 수 있다. 이를 통해 Unicode string이나 스트링 포맷을 이용하여 문자열을 mutation 한다. 

White-box Fuzzers : 

화이트 박스 퍼저들 역시 model-based 방법이나 model-less 방법을 적용하는 것이 가능하다. 전통적인 dynamic symbolic execution 은 mutation-based 퍼저 같은 model을 사용하지 않았으나, [Grammar-based Whitebox Fuzzing] 논문 이후에 input grammar를symbolic executor의 가이드로 활용하는 input model을 사용하는 방법이 제시되기도 하였다. 대부분의 white-box fuzzer는 [Automated Whitebox Fuzz Testing] 논문처럼 dynamic symbolic execution을 통해 테스트 케이스를 만드는 방식을 취했으나, 일부 퍼저는 grey-나 black-에서 사용하는 방식처럼 Program analysis를 통해 PUT이 받아들이는 input 정보를 활용하기도 한다. 이 장의 나머지 부분에서는 기존의 테스트 사례 알고리즘을 기반으로 기존 화이트 박스 fuzzing 기법을 간략하게 요약한다.  

i.Dynamic Symbolic Execution: 

전통적인 symbolic execution 은 프로그램을 구동할 때 가능한 모든 값을 symbolic value를 입력값으로 하여 PUT에 실행하고, concrete value를 평가하는 대신symbolic  expression을 생성한다. conditional branch 명령어에서 분기될 때마다 True와 False 두 개의 symblic interpreter로 fork 하여 진행한다. symbolic interpreter는 실행 동안 마주하게 되는 모든 branch 경로에 대해 path formular 또는 path predicate를 생성한다. 이 경로 수식은 원하는 경로에 도달할 수 있도록 하는 구체적인 입력을 만족하도록 설정된다. 그리고 해당 경로 공식에 대한 해를 찾기 위하여 SMT Solver를 이용한다. 다이내믹 기호 실행은 다양한 기호 실행 방법론 중 하나라고 볼 수 있는데, symbolic execution의 제약 조건을 concrete execution을 통해 조건의 복잡성을 축소시키는 것이다. 해당 기술에 대한 구체적인 학술 연구 성과는 본 논문의 범위를 벗어나므로 [All You Ever Wanted to Know About Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask).]를 참고하기 바란다.  

ii.Guided Fuzzing: 

어떤 퍼저들은 프로그램에 대한 정적 분석과 동적 분석 기법을 통해 퍼징의 효과를 향상하기도한다. 이러한 기술들은 두 가지 단계로 적용되는데, 첫째는 PUT에 관한 유용한 정보를 얻기 위해 비교적 cost가 높은 프로그램 분석을 수행하는 것이고, 두 번째는 해당 정보를 토대로 테스트 케이스를 만드는 것이다. 예를 들어 TaintScope는 세밀한 taint analysis를 통해 중요한 시스템 호출이나 API 호출로 유입되는 일명 'hot bytes'를 찾아낸다. 


iii.PUT Mutation: 

실무적으로 직면하게 되는 문제가 있는데, 바로 Checksum 검증을 우회하는 일이다. 예를 들어 PUT에 자체적인 체크섬 검증 로직이 포함되어 있다면 퍼징으로 생성한 입력값이 전달되어도 대부분 checksum을 만족시키지 못해 거절되고 말 것이다. 이를 우회하기 위해서 TaintScope와 같은 퍼저는 checksum을 고려한 퍼징 기법을 적용하였다. 프로그램에서 crash를 찾았을 때, 알맞은 checksum을 계산한 후 이를 활용하는 것이다. 


To be continued .. 

[논문리뷰] 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 계정으로 간편하게 로그인하고 댓글을 남겨주세요.