Wen Xu, Sanidhya Kashyap, Changwoo Min, Taesoo Kim CCS’17, October 30-November 3, 2017, Dallas, TX, USA
개요
Fuzzing의 성능에 영향을 미치는 Operating system의 Bottle neck을 분석하여, 이를 새로운 Process abstraction으로 설계, 최종적으로 Fuzzer의 Scalability를 향상시켰다.
Motivation
Fuzzing이 많이 사용되고 있으며 이에따라 Fuzzing의 성능을 향상시키는 연구또한 많이 이루어지고 있다. 그러나 Fuzzing의 성능을 향상시키는 중요한 요소중 하나인 Execution time을 줄이는 것은 이 연구전에는 잘 연구되지 않았다. Fuzzer의 중요한 성능 특징중 하나는 Fuzzing이 기존 OS의 Abstraction을 사용하면 Scalability가 떨어진 다는 사실이다.
- 우선
fork()시스템 콜은 Scalable하지 않다. Fork와 같은 경우에는 Process를 복사하기 위해서 사용되는데, Fuzzing같은 경우에는 프로그램의 많은 부분이 겹치기 때문에 필요없게 중복되는 부분이 생긴다. 예를 들어서, reverse mapping, global memory allocator, scheduler queue와 같은 커널 부분에서 bottleneck을 일으킨다. - 다음으로, File system을 사용하게 될 경우, 파일에 대한 업데이트는 보통
write,read를 사용하는데, 이 두 Operation은 Metadata management를 위한 Synchronization으로 인하여 Bottleneck으로 Scalability가 떨어지게 만든다. - 마지막으로, Fuzzer가 Test case를 서로다른 Fuzzer agent끼리 Synchronize하기 위해서 사용하는 Directory scan operation이 Scalable하지 않다.
Main Idea
- snapshot이라는 새로운 OS기능 제공
- Dual file system으로 Small files들에 대한 Scalability bottleneck극복
- Shared in-memory test case log를 통하여 test case execution information을 scalable하고 collaborative한 방식으로 저장할 수 있도록 함
Design
- Snapshot System Call
- Fork는 Generality를 위해서 Scalability와 Performance를 포기하였다. 따라서 Swapping을 위한 Reverse mapping처럼 Fuzzer의 Fork()모델에서는 사용하지 않는 기능을 제거하여
snapshot이라는 새로운 OS First-class오브젝트를 제공하였다. Snapshot은 다음의 기능을 수행한다.
- Virtual memory area: VM의 시작 그리고 끝 주소를 저장한다.
- Pages: Writable page를 Read-only로 만들어 CoW가 일어나도록 하였다.
- brk: stack allocation에 사용되는 brk주소를 카피하였다.
- File descariptor: File descriptor를 복구하기 위한 정보를 저장한다.
- Dual File System Service
- Fuzzer는 File syste를 reliable하게 저장할 필요가 없기 때문에, Memory file system과 Disk file system으로 구분하여, Consistency를 포기하는 대신에 Small 파일에 대한 성능을 확보하였다. Fuzzer가 사용하는 모든 Directory를 Private하게 만들어 Contention을 없앴다. 또한 Memory file system의 할당량이 특정 수치를 넘기면 Symbolic file을 메모리 시스템에 남기고 데몬이 Fuzzer에서 사용하는 Age가 큰 순서대로 Disk file에 옮겨서, Load balancing이 되도록 하였다.
- Shared In-memory Test-Case Log
- Test case log은 Fixed size의 In-memory circular log로 구현하였다. 이 로그를 통해서 Fuzzer는 각각의 퍼징 에이전트가 생성한 Test case들을 효율적으로 공유할 수 있도록 하였다. Circular log은 대표적인 Lock-free list로, 쉽게 Contention없게 구현 가능하다.
AFL과 Libfuzzer에 위의 디자인을 적용시키는 Implementation detail은 논문을 참조.
Result
Multicore환경에서 기존 Work보다 확연히 좋은 Scalability성능을 보여주었다.
Conclusion
본 논문은 Fuzzer의 Scalability를 저하시키는 커널의 요소를 분석하여 그에 해당하는 Optimization design과 Implementation을 제시한 논문이다. Fuzzer의 성능향상을 확실히 보였고, 제시한 디자인이 Somewhat 많이들 사용하던 방식이지만, Fuzzer에 적용하여 효율적인 Mechanism을 제공할 수 있음을 보인것은 후에 많은 연구에 도움이 될 수 있는 좋은 논문이라 생각한다.