[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey
원문 : https://arxiv.org/abs/1812.00140
[목차]
7. Configuration Updating
CONFUPDATE 함수는 블랙/그레이/화이트 박스 퍼저의 동작을 구분하는 데 중요한 역할을 한다. Algorithm 1에서 설명하였듯이 CONFUPDATE 함수는 현재 fuzz run 중에 수집된 configuration 및 실행 정보를 기반으로 configuration set를 수정할 수 있다. CONFUPDATE의 가장 단순한 형태는 업데이트(수정) 없이 파라미터 를 그냥 반환하는 형태이다.
블랙 박스 퍼저는 버그 오라클 를 evaluate 하는 것 외에 어떤 프로그램 introspection(프로그램 내부에서 정보 획득)도 수행하지 않는다. 따라서 를 수정할 정보를 수집하지 않았으므로 일반적으로 를 업데이트하지 않는다. (어떤 퍼저는 seed set에 violating test case를 추가하기도 한다. 예를 들어, BFF는 이런 기능을 crash recycling이라고 한다.)
반대로 그레이 박스 퍼저와 화이트 박스 퍼저의 CONFUPDATE는 더 정교하게 구분된다. 이를 통해 새로운 fuzz configuration을 통합하거나 제거할 수 있다. CONFUPDATE는 한 번의 fuzz iteration에서 수집한 정보를 향후 모든 fuzz iteraion에서 사용할 수 있도록 한다. 예를 들어, 화이트 박스 퍼저는 블랙/그레이 박스 퍼저에 비해 상대적으로 적은 수의 테스트 케이스를 생성하기 때문에, 일반적으로 생성된 모든 테스트 케이스에 대해 fuzz configuration을 만든다.
7.1 Evolutionary Seed Pool Update
진화 알고리즘(:Evolutionary Algorithm, 이하 EA)는 변이(:mutation), 재조합(:recombination), 선택(selection)과 같은 생물학적 진화 매커니즘을 포함하는 휴리스틱 기반 접근법이다. 퍼징의 관점에서, EA는 새로운 individuals이 발견되면 퍼징 캠페인 과정에서 진화하는 유망한(:promising) individuals(i.e., seeds)의 시드 풀을 유지한다. 비교적 간단한 개념의 EA는 AFL, LibFuzzer, syzkaller과 같은 여러 그레이 박스 퍼저의 기반이 되었다. 변이할 시드를 선택하는 과정과 변이 과정 자체는 4.3절에서 다루었다.
EA에서 가장 중요한 단계는 COFUPDATE 단계에서 만들어지는 fuzz configuration set 에 새로운 configuration을 추가하는 것이다. 대부분의 EA 기반 퍼저는 node 또는 branch coverage를 fitness function으로 사용한다(즉 새로운 노드나 branch를 발견하면 시드 풀에 테스트 케이스를 추가하는 방법). 도달할 수 있는 경로의 수가 시드 수보다 더 클 수도 있다. 따라서 PUT의 현재 탐색을 나타 내기 위해 시드 풀은 도달할 수 있는 모든 경로의 다양한 하위 선택(:subselection)이 된다. 또한 크기가 다른 시드 풀이 같은 커버리지를 가질 수 있다.
EA 기반 퍼저의 일반적인 전략은 더 세분화된 지표(:indicator)를 탐지할 수 있도록 fitness function을 잘 가공(:refine) 하는 것이다. 예를 들어 AFL은 branch에 hit 한 횟수를 기록하여 fitness function의 정의를 구체화했다. STADS는 fuzz 캠페인이 게속 될 경우 발견될 새로운 configuration의 수를 추정하기 위해 생태학에서 영감을 받은 통계 프레임워크를 사용한다.
또 다른 일반적인 전략은 복잡한 branch condition을 평가할 때 만족하는 조건의 비율을 측정하는 것이다. 예를 들어 LAF-INTEL은 단순히 multi-byte comparison을 여러 가지 분기(:branch)로 나눠서, 이를 통해 새로운 시드가 중간 byte comparison(이하 비교)을 통과할 때 이를 탐지할 수 있다. LibFuzzer, Honggfuzz, go-fuzz, Steelix는 모든 비교를 instrument하고, 시드 풀과 비교했을 때 진전이 있는(:makes progress) 모든 테스트 케이스를 시드 풀에 추가한다. 비슷한 아이디어 이용한 CompareCoverage는 현재 clang을 위한 독립형 instrumentaion 모듈로 제공되고있다. Steelix는 추가적으로 비교 instruction에 영향을 미치는 input offset을 확인한다. Angora는 hit한 각 branch의 calling context를 고려하여 AFL의 fitness 기준을 개선한다.
EA 기반 퍼저인 VUzzer의 fitness function은 각 basic block에 대한 가중치(:weight)를 결정하는 커스텀 프로그램의 분석 결과에 의존한다. 특히 built-in 프로그램 분석을 이용해 basic block을 normal 또는 에러 핸들링(:error handling, 이하 EH)로 분류한다. normal block의 가중치는 VUzzer에서 정의한 전이(:transition) 확률에 따라 "이 블록을 포함하는 CFG의 random walk가 이 block을 hit 할 확률"에 반비례한다. 따라서 random walk에서 더 적게 hit 한 normal block을 실행하는 configuration을 더 좋게 판단한다. EH block의 가중치는 음수이며, 크기는 이 configuration에 의해 실행되는 EH block 수와 비교한 basic block 수의 비율이다. 이러한 음의 가중치는 EH block의 실행을 억제하는 데 사용되는데, 이는 종종 버그가 unhandled error와 일치하기 때문에 EH 블록을 traversing 하면 취약점을 트리거 할 가능성이 더 낮다는 가설을 기반으로 한다.
7.2 Maintaining a Minset
새로운 configuraion을 생성하는 동작은 너무 많은 configuration을 생성할 수 있는 위험이 있다. 이런 문제를 해결하기 위해 일반적으로 minset이나 coverage metric를 최대화하는 최소한의 테스트 케이스 set을 유지하는 전략을 사용한다. 이런 minset 방법은 PREPROCESS 단계에서도 사용되며 3.2절에서 다루었다.
configuration 업데이트에 특화된 minset을 유지하는 방법을 사용하는 퍼저도 있다. 예를 들어 Cyberdyne은 minset에 없는 configuration을 완전히 제거하는데, AFL은 minset configuration을 favorable이라고 마킹하기 위해 culling procedure을 사용한다[AFL에서 fitness를 favorite라고 부름]. favorable fuzzing configuration은 SCHEDULE 함수에 의해 선택될 가능성이 훨씬 높다. AFL의 저자는 "이런 매커니즘은 queue cycling 속도와 테스트 케이스 다양성 사이에서 합리적인 균형을 제공한다"라고 말했다.
8. Related Work
2007~2008년 퍼징에 관한 3권의 책 <Open Source Fuzzing Tools>, <uzzing: Brute Force Vulnerability Discovery>, <Fuzzing: Brute Force Vulnerability Discovery>, <Fuzzing for Software Security Testing and Quality Assurance>이 출판된 이후로 퍼징에 관한 문헌이 많아졌다. 이 책들은 당시 사용 가능한 다양한 툴과 다양한 대상에 적용 가능한 사용법을 제시하는 실용적인 접근 방법을 이용했다.
<Fuzzing for Software Security Testing and Quality Assurance>에서는 공식적으로 정의한 것은 아니지만 블랙/화이트/그레이 박스 퍼저를 구별하기도 했다. 그리고 해당 책은 출판된 지 10년 뒤인 2018년에 개정되었다. 제2판인 <Fuzzing for Software Security Testing and Quality Assurance, 2nd ed>에는 AFL이나 ClusterFuzz와 같은 최신 도구를 포함하는 많은 업데이트가 있었다.
우리는 두 개의 퍼징 survey <Fuzzing: a survey>와 <Fuzzing: State of the Art>가 있다는 것을 알고 있다. 그러나 이 두 survey의 목적은 퍼징에 관한 모든 분야를 커버하려는 본 연구에 비해 더 집중적(:focus)이다. 후자인 <Fuzzing: a survey>는 퍼징에 대한 최근의 많은 발전에 대한 꼼꼼한 리뷰를 제공했지만, 저자는 커버리지 기반 퍼징의 세부 사항에 초점을 맞추었다. 본 연구와 더 비슷한 전자인 <Fuzzing: State of the Art>는 다양한 퍼징 기법을 설명하기 위해 비공식적인 모델을 제안했다. 하지만 해당 모델은 model inference이나 하이브리드 퍼징과 같이 본 논문에서 다루는 일부 퍼징 접근 방식을 포함할 만큼 유연하지 않았다.
Klees는 최근에 연구 <Evaluating fuzz testing>에서 퍼징 기법을 평가하는 일관된 방법이 없다는 것을 발견했다. 이런 문제는 퍼징 기술의 효과를 비교하는 것을 방해할 수 있다. 그러고는 퍼징 알고리즘을 평가하기 위한 몇 가지 유용한 가이드라인을 제공했다. 퍼징 알고리즘의 평가는 본 논문의 범위를 벗어나기 때문에 해당 연구가 본 연구와 직교(:orthogonal) 한다고 생각한다.
9. Concluding Remarks
전술하였듯이 본 논문의 목표는 현대 퍼징 문헌(:literature)에 대한 포괄적이고 일관된 관점(:view)을 추출(정제:distill) 하는 것이다. 따라서 현재 사용 중인 다양한 형태의 퍼징을 설명할 필요가 있었고, 먼저 범용 모델 퍼저를 제시하였다. 그런 다음 Figure 1과 Table 1을 이용해 퍼저의 분류를 제시했다. design decision을 논의하고 커뮤니티의 많은 성과들과 함께 모델 퍼저의 모든 단계를 설명했다.
Uploaded by Notion2Tistory v1.1.0