주요 내용으로 건너뛰기

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

 KAIST CSRC(사이버보안연구센터)의 VALENTIN J.M. MANÈS 연구원과, 소프트웨어보안 연구실 소속(출신) 학생들, 그리고 차상길 교수님과 MAVERICK WOO 등 Fuzzing 분야의 기라성과 같은 거장 교수님들이 참여하신 Fuzzing survey 논문이 arxiv에 공개되었다. 

특히 유수의 학회 뿐만 아니라 Github을 통해 오픈소스화 되어 있는 다수의 Fuzzer 도구들을 일일이 분석하여 각각의 관계를 꼼꼼하게 정리한 것이 인상적이다.(참고문헌 219개)

이 논문을 통해 퍼징에 처음 입문하려는 사람이나, 사내 프로젝트에서 어떤 Fuzzing 을 적용하면 좋을지 고민할 때 굉장히 유용하게 사용할 수 있을 것 같다. 

VALENTIN J.M. MANÈS, HYUNGSEOK HAN, CHOONGWOO HAN, SANG KIL CHA, MANUEL EGELE, EDWARD J. SCHWARTZ, MAVERICK WOO. 2018. Fuzzing: Art, Science, and Engineeringhttps://arxiv.org/abs/1812.00140.

https://arxiv.org/pdf/1812.00140.pdf 

*주의 : 본 포스트 내용은 개인 공부용 및 회사 업무상 사내 스터디용으로 작성한 것입니다. 아래의 설명은 논문 전체를 번역한 것이 아니라, 블로그 저자의 개인 주관으로 내용을 선별하여 강조한 것이므로 원문의 의도와 완전히 일치하지는 않을 수 있으며, 필요하다면 반드시 상기 링크를 통해 원저자의 논문을 확인하기 바랍니다. (혹시 틀린 부분 발견하시면 알려주세요.) 


0. Abstract 

소프트웨어의 보안 취약점을 탐지하는 다양한 기법들이 있다. 그중 퍼징(Fuzzing)은 굉장히 단순한 개념으로 누구나 접하기에 용이하며, 실제 real-world에서 다양한 취약점을 찾아내었다는 실험적인 입증자료들이 즐비하다. 퍼징을 연구하는 사람들과 실무진들은 최근 몇 년간 다양하고 전폭적인 연구를 통해 퍼징을 개선하기 위해 많은 노력을 기울여왔지만, 한편으로는 퍼징에 대해 포괄적이면서도 일관된 관점을 정의하는 것이 어지럽게 느껴지는 측면이 있다. 본 논문에서는 현재까지의 집대성된 퍼징 논문들을 비교하고 분석하여 범주화하고, 이를 범주화할 수 있는 통일된 모델을 제시하고자 한다. 이를 위해 방대한 참고 문헌을 일관성 있게 정리하고자 한다. 


1. Introduction

  • 1990년대 초반 Barton P. Miller 교수가 발표한 논문 <An Empirical Study of the Reliability of UNIX Utilities> 에서 처음 Fuzzing이라는 용어가 사용된 이후, 퍼징은 소프트웨어의 보안 취약점을 찾기 위한 방법으로 널리 사용되고 있음 
  • 퍼징이란 문법적(Syntaticallly)또는 의미적(Semantically)으로 비정상적인 입력값을 생성해 프로그램에 주입하여 작동시키는 과정을 반복하는 것으로, 익스플로잇 생성이나 모의 침투 분야에서 널리 활용되고 있다. 2016년 DARPA CGC 대회에 참여한 다수의 팀들도 퍼징을 활용했다.
  • 이러한 이유로 이제는 보안을 강화하는 목적으로도 퍼징을 활용하고 있는데, 공격자들이 해킹을 수행하기 이전에 먼저 개발단계에서부터 퍼징을 통해 취약점을 찾아 보완하는 것이다. 실제로 Adobe, Cisco, Google, Microsoft가 SDL 활동의 일환으로 퍼징을 수행하고 있으며 보안 감사 활동이나 오픈소스 생태계에서도 퍼징이 널리 전파되고 있다.
  • 퍼징을 연구하는 커뮤니티도 굉장히 많이 활개를 치고 있다. Github를 통해 Fuzzing 관련된 프로젝트를 검색해보면 다수의 많은 결과가 표출되며(추후 그림을 통해 대략적으로 살펴볼 것이다), 보안 분야의 최상위 학회로 꼽히는 곳들에서도 퍼징과 관련한 연구 논문이 갈수록 늘어가고 있다.
  • 하지만 퍼징이 연구자들과 실무진들에 의해 산발적으로 다루어지고 있다 보니 조금씩 진통이 찾아온다. 퍼저를 개발한 사람들이 소스코드나 매뉴얼 페이지를 구체적으로 제공하지 않기도 하고, 어떠한 설계 원리를 기초로 하였는지 불분명하다. 특히 AFL이나 funfuzz, BFF 등의 도구들이 저마다 사용하는 용어가 통일되어 있지 않다. 이러한 단절은 퍼징 관련 지식을 집대성하는 일에 방해가 되어 장기적으로는 분야의 발전을 저해하는 요소가 될 수 있다. 
  • 본 연구진들은 퍼징 관련 학술연구와 실무경험들을 토대로, 해당 분야의 방대한 지식을 종합적으로 정리하는 것의 필요성을 느끼고 지금이 바로 가장 시의적절한 때라는 판단을 내렸다. 그간 퍼징과 관련한 책으로는 2007~2008년 사이에 출간된 <Fuzzing: Brute Force Vulnerability Discovery>, <Open Source Fuzzing Tools>, <Fuzzing for Software Security Testing and Quality Assurance(*이 책은 2018년에 개정 2판이 출간되었음)> 등이 있으며, coverage-based 퍼징에 한하여 동향을 다룬 <Fuzzing: a survey> 논문이 있었다. 하지만 본 논문에서 다루고자 하는 차별점은, 해당 분야에서의 최신 연구들을 아우르는 포괄적인 정보를 폭넓게 담으려는데에 있다. 
  • 본 눈문의 이어지는 2장에서는 퍼징 분야에서 사용되는 용어들을 설명하고 일관성 있는 모델 기준을 제시할 것이다. 그리고 이를 바탕으로 3장부터 7장까지 각각의 Fuzzer Model 단계들을 설명할 것이다. 또한, 발표된 이후 지금까지 널리 사용되고 있는 다양한 Fuzzer 도구들을 본 논문의 기준에 맞게 각 단계별로 분류하여 전체적인 맥락을 살펴볼 것이다. 각 단계마다 다수의 참고문헌을 조사하였으며, 그들의 설계 방식을 분석하고 그로 인한 득과 실을 파악하며 그중 특히 현대의 퍼징 도구들을 효과적으로 개선한 놀랄만한 공학적인 기여에 대해서 강조할 것이다.


2. 체계화, 분류, 테스트 프로그램 선정

1) 관련 용어의 정의

Fuzz라는 용어는 최초 1990년 Miller 교수가 쓴 논문에서 "대상 프로그램에서 사용할 임의의 문자 스트림을 생성하는 것"을 지칭하는 뜻으로 사용되었다. 하지만 그 이후 Fuzz라는 동사와 및 그 행위를 뜻하는 명사 Fuzzing 이 아래와 같은 매우 다양한 분야에서 혼용되고 있다.

  • Dynamic symbolic execution
  • Grammar-based test case generation
  • Permission testing
  • Behavioral testing
  • Representation dependence testing
  • Function detection
  • Robustness evaluation
  • Exploit development
  • GUI testing
  • Signature generation
  • Penetration testing 

이에 따라 방대한 퍼징 관련 논문이 다루고 있는 내용을 보다 체계적으로 정리하기 위해 현대적 상황에 입각한 정확한 용어를 먼저 정의하고자 한다. 

직관적으로, 퍼징은 "PUT(테스트 대상 프로그램)에 Fuzz 된 입력값을 넣고 실행하는 행위"를 지칭한다. Miller 교수의 연구를 계승하여, 'Fuzz 된 입력값'이란 대상 프로그램이 예측하지 못한 입력, 즉 PUT이 해당 값을 잘못된 방식으로 처리하게 만듦으로써 PUT 프로그램의 원개발자가 전혀 의도하지 않은 행동을 유발할 수 있게 된다. 이러한 관점에 입각하여, Fuzzing 관련 용어를 아래와 같이 정의하도록 한다. 

Definition 2.1 (Fuzzing).
Fuzzing is the execution of PUT using input(s) sampled from an input space (the “fuzzinput space”) that protrudes the expected input space of the PUT.
퍼징(Fuzzing)은 PUT(테스트 대상 프로그램)의 예상 입력 공간을 벗어나는 입력 공간(이를 "퍼즈 입력 공간"이라 한다)에서 추출한 입력을 사용하여 PUT에 대해 실행하는 것이다. 

이때, 다음과 같은 3가지 사항을 염두해야 한다.

  1. 일반적으로 퍼즈 입력이 예상된 입력 범위 안에 포함되어야 하는 것처럼 보이지만, 이것은 꼭 필수적인 사항은 아니다. 후자에 없는 입력이 전자에 포함될 수 있다.
  2. 실무적으로 퍼징을 수행할 때에는 거의 필연적으로 많은 작업을 반복 실행하게 된다. 때문에 "반복된 실행"이라고 지칭하는 것이 적절하다.
  3. 샘플링을 수행하는 과정이 반드시 무작위적이어야 할 필요는 없다.

퍼즈 테스팅(Fuzz testing)은 fuzzing을 이용하는 소프트웨어 테스팅 기술의 한 형태라고 볼 수 있다. 다른 테스팅 분야와 차별화되는 가장 큰 목적성은 프로그램의 충돌(Crash) 현상을 비롯한 '보안 관련 버그'를 찾아내려는 데에 중대한 관심이 있다는 것이다. 그리하여 이와 관련된 퍼즈 테스팅, 퍼저, 퍼즈 캠페인이라는 용어들을 아래와 같이 정의할 수 있다.

Definition 2.2 (Fuzz Testing). Fuzz testing is the use of fuzzing where the goal is to test a PUT against a security policy.
퍼즈테스팅은 "대상 프로그램이 보안 정책을 준수하는지 여부를 퍼징을 통해 점검하는 것"으로 정의할 수 있다.

Definition 2.3 (Fuzzer). A fuzzer is a program that performs fuzz testing on a PUT.
퍼저는 대상 프로그램에 퍼즈 테스팅을 수행하기 위한 프로그램이다. 

Definition 2.4 (Fuzz Campaign). A fuzz campaign is a specific execution of a fuzzer on a PUT with a specific security policy.
퍼즈 캠페인은 대상 프로그램이 특정한 어느 보안 정책을 준수하는지 점검하기 위한 퍼저의 특정한 수행을 일컫는다. 

PUT에 퍼즈 캠페인을 수행하는 목적은, 요구되는 특정 보안 정책을 위반하는 버그를 찾아내기 위함이다. 예를 들면, 초창기의 퍼저들이 채택한 보안 정책은 생성된 입력('테스트 케이스'라고 지칭한다)이 대상 프로그램에 Crash를 발생시키는 여부만을 확인하는데 그쳤다. 그러나 사실 퍼즈 테스팅은 관찰 가능한 그 어떤 보안 정책이더라도(ex: EM-enforceable) 점검할 수 있다. 이때 해당 수행이 특정 보안 정책을 위반하는지 여부를 판단하는 특별한 메커니즘을 버그 오라클(bug oracle)이라고 부른다. 

Definition 2.5 (Bug Oracle). A bug oracle is a program, perhaps as part of a fuzzer, that determines whether a given execution of the PUT violates a specific security policy.
버그 오라클은 대상 프로그램이 주어진 실행에서 특정 보안 정책을 위반하는지를 판별하는 프로그램으로, 퍼저의 일부분으로 포함되어 있다. 

퍼저를 구현할 때 사용된 알고리즘을 일명 "퍼즈 알고리즘"이라고 부른다. 거의 모든 퍼즈 알고리즘은 PUT으로 전달되는 매개 변수에 따라 좌우된다. 각 매개 변수의 구체적인 설정을 퍼즈 환경설정이라고 부른다. 

Definition 2.6 (Fuzz Configuration). A fuzz configuration of a fuzz algorithm comprises the parameter value(s) that control(s) the fuzz algorithm.
퍼즈 환경설정은 퍼즈 알고리즘을 제어하는 파라미터 값들을 포함한다. 

퍼즈 환경설정은 보통 튜플(Tuple)의 형태로 작성된다. 퍼즈 환경설정에 사용되는 변수 값들의 형식은 퍼즈 알고리즘의 형식에 따라 정해진다. 예를 들면, 대상 프로그램에 무작위의 바이트 스트림을 전송하는 퍼즈 알고리즘이라면(Miller의), 이 경우의 환경설정 범위는 {(PUT)}이 된다. 한편, 정교한 퍼저들은 집합 형태의 환경설정이나, 시간이 지남에 따라 진보하는 방식의 알고리즘을 채택하기도 하는데, 이들은 환경설정을 스스로 추가하거나 삭제하는 작업도 수행한다. 예를 들어 CERT BFF는 캠페인을 수행하는 과정에서 뮤테이션 비율과 시드에 변화를 가하므로, 이 경우의 환경설정 범위는 {(PUT, s1, r1), (PUT, s2, r2),...} 이 된다. 마지막으로, 각 환경설정마다 퍼저가 여기에 추가적인 데이터를 저장할 수 있도록 하는 방식도 가능하다. 예를 들면 coverage-guided 퍼저의 경우 각 환경설정에 coverage 도달 범위를 기록해 두는 경우도 있다. 


2) 분석 대상 논문 선정의 기준

본 논문에서는 퍼징 관련 논문의 동향을 살펴보기 위해서 다음과 같은 보안 분야의 4대 주요 콘퍼런스 위주로 조사하였다. (알파벳 순서)

또한, 다음과 같은 소프트웨어 공학분야의 3대 주요 학회도 기준으로 하였다.

  • ACM International Symposium on the Foundations of SoftwareEngineering (FSE)
  • IEEE/ACM International Conference on Automated Software Engineering (ASE)
  • International Conference on Software Engineering (ICSE)

해당 학회에서 2008년 1월부터 2018년 5월 사이에 게재된 논문들을 토대로 선정하였으며, 또한 기타 학회 혹은 다른 매체에서 보고된 내용도 적절한 판단 기준에 따라 일부는 포함시켰다. 한편 일반적으로 소프트웨어공학에서 다루는 '테스팅'이라는 분야가 퍼즈 테스트와 일부 겹치는 부분도 있는데, '버그 오라클'이라는 이론을 차용했다는 점에서는 유사하지만 실무적으로는 굉장히 상이한 기술을 사용한다고 볼 수 있다. 특히 테스트 도구는 설계할 때 소스코드와 PUT에 대한 관련 지식이 충분히 있는 상태라고 가정하고 시작하는데 반해, Fuzzer 개발에서는 그렇지 않다는 차이점이 있다. 그럼에도 불구하고 두 분야는 여전히 서로 많은 상관관계를 가지며 공유하는 측면이 크기 때문에 명확히 둘 사이를 구분할 수 없는 경우가 많았는데, 이런 경우 본 연구진은 가장 단순한 원칙을 세웠다. "논문 내용에 'Fuzz'라는 단어가 출현하는지 여부"에 따라 선정하기로 했다. 


3) 퍼즈 테스팅 알고리즘

본 절에서는 퍼즈 테스팅에 사용되는 일반적인 알고리즘을 설명한다. 

그림의 Pseudo code는 model fuzzer를 구현할 때 사용할 수 있는 예시이며, 후술 할 <퍼저의 분류>에서 다루는 현존하는 대다수의 블랙박스, 그레이 박스, 화이트박스 퍼징을 충분히 아우를 수 있는 알고리즘이다. 이 알고리즘은 먼저 입력값(input)으로 퍼즈 환경설정(C)과, 타임아웃(t_limit)을 갖는다. 그리고 발견된 버그의 집합(B) 를 결과물로써 제시한다. 진행 과정은 크게 두 가지 단계로 나뉜다. 

첫 번째로는 전처리(Preprocess) 단계이다. 이 단계는 퍼즈 캠페인을 처음 시작할 때 수행된다. 

두 번째 과정으로는 반복문 안에서 일련의 함수들(Schedule, InputGen, InputEval, ConfUpdate, Continue)이 수행된다. 각 루프를 수행하는 것을 'Fuzz iteration'이라고 하고, 하나의 테스트 케이스에 대해 InputEval 이 수행되는 것을 'Fuzz run'이라고 한다. 단, 모든 퍼 저가 반드시 이러한 5개의 함수들을 포함하는 것은 아니다. 예를 들어 Radamsa의 경우 Configuration을 업데이트하는 ConfUpdate 단계가 별도로 존재하지 않고 그저 반환만 할 뿐이다. 

  1. Preprocess (C) →  C
    전처리 단계에서는 사용자가 퍼즈 환경설정으로 사용할 값들을 지정하면, 이를 적절히 수정한 상태로 다시 반환하게 된다. 
  2. Schedule(C, t_elapsed, t_limit) → conf
    Schedule 함수는 현재의 퍼즈 환경설정(C) 집합과, 수행 시간(t_elapsed), 종료 시점(t_limit)을 입력값으로 하여, 이번 fuzz iteration에서 사용할 특정 설정값 conf를 지정한다.
  3. InputGen(conf) → tcs
    InputGen 함수는 퍼즈 환경설정을 토대로 구체적인 테스트 케이스의 집합(tcs)을 생성한다. 테스트 케이스를 생성할 때에는 현재 conf에 설정된 특정 파라미터들을 이용한다. 일부 퍼저는 seed 방식을 사용하기도 하고, 나머지는 model 또는 grammar를 파라미터로 사용하기도 한다. 
  4. InputEval(conf, tcs, O_bug) → B', execinfos
    InputEval함수는 퍼즈 환경설정과, 테스트 케이스, 그리고 버그 오라클을 입력으로 받는다. 이 단계에서 테스트 케이스를 대상 프로그램에 주입한 후, 해당 실행 과정에서 보안정책 위반이 발생하는지를 버그 오라클을 사용하여 점검한다. 이때 버그가 발견되었다면 그 버그 결과와 해당 fuzz run에서 사용된 기타 정보들(execinfos)이 함께 반환된다. 이때 버그 오라클은 bug oracle 내부에 포함되어 있다고 가정한다. 
  5. ConfUpdate(C, conf, execinfos) → C
    ConfUpdate 함수는 퍼즈 환경설정(C)과, 현재 설정된 값(conf), 그리고 각각의 fuzz run이 수행될 때의 관련 정보(execinfos)를 입력으로 하여, 퍼즈 환경설정(C)을 업데이트한 값을 결과로 반환한다. 예를 들어 상당수의 그레이 박스 퍼저들은 execinfos의 정보를 기반으로 fuzz configuration 집합 C의 범위를 축소시킨다.
  6. Continue(C) → {True, False}
    Continue 함수는 퍼즈 환경설정(C)을 기반으로 하여, 다음 Fuzz iteration을 수행할지 말지를 참과 거짓으로 판정하는 Boolean 형식의 응답을 반환한다. 화이트박스 퍼저의 경우 더 이상 탐색할 path가 없는 것으로 확인되었을 때 수행을 종료시키는 방식으로 사용하면 유용하다.



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