Blackbox fuzz testing is commonly used to find security bugs of a program whose source code is unavailable. Blackbox fuzz testing can only test a small portion of code when rigorously checking the well-formedness of input values. To overcome this problem, blackbox fuzz testing is sometimes performed using a grammar that delineates the format information of input values. However, it is almost impossible to manually construct a grammar if the input specifications are not known.
We propose an alternative technique: the automatic generation of fuzzing grammars using API-level dynamic symbolic execution. API-level dynamic symbolic execution collects constraints at the library function level rather than the instruction level. This idea is based on the fact that developers generally prefer to use well-known, string-related library functions over self-implemented code when processing input strings. While API-level dynamic symbolic execution may be somewhat less accurate than instruction-level dynamic symbolic execution, it is highly useful for speedily generating fuzzing grammars that enhance code coverage for real-world programs. Fuzzing grammars explicitly differentiate fields that affect paths from those that do not. Therefore, by replacing fields that do not affect paths with random strings, lengthy strings, file paths, urls, etc, fuzzing grammars can be used to generate concrete test cases that can easily trigger security bugs such as buffer overflow vulnerabilities, etc.
To verify the feasibility of the proposed concept, we implemented a system for generating ActiveX control fuzzing grammars, named YMIR. To the best of our knowledge, the YMIR system is the first tool ever developed to carry out whitebox fuzz testing on ActiveX controls. The experiment results showed that the YMIR system was capable of generating fuzzing grammars that can raise branch coverage for ActiveX control methods using highly-structured input string by 15-50\%. In addition, the YMIR system found three vulnerabilities revealed only when input values are well-formed. Automatic fuzzing grammar generation through API-level dynamic symbolic execution is not restricted to the testing of ActiveX controls; it should also be applicable to other string processing programs whose source code is unavailable.
블랙박스 퍼징은 바이너리 프로그램에서 취약점을 찾는데 흔히 사용되는 방법이다. 블랙박스 퍼징은 입력 포멧의 유효성을 엄격하게 확인하는 프로그램에 대해서는 제한된 코드 영역만을 테스트할 수 있다는 한계를 가지고 있다. 이런 문제점을 극복하기 위해서 블랙박스 퍼징은 입력 포멧에 대한 정보를 담고 있는 문법을 이용한다. 하지만, 많은 경우에 입력 포멧에 대한 정보는 공개되어 있지 않다. 입력 포멧에 대한 정보가 공개된 경우라하더라도 사람이 수작업으로 문법을 기술하는데는 많은 시간과 노력이 필요하다. 또한, 입력 포멧에 대한 문서로부터 문법을 생성할 경우 대상 프로그램의 구현 상황이 적절히 반영되지 않을 수 있다. 예를 들어 문서 상에 기술된 기능 중 일부가 구현되지 않을 수도 있고, 구현된 기능 중 일부가 문서 상에 기술되어 있지 않을 수도 있다. 이러한 불일치로 인해 불필요한 테스트 케이스가 생성되거나 필요한 테스트 케이스가 생성되지 않을 수 있다.
블랙박스 퍼징의 다른 대안으로 최근 동적 심볼릭 실행 기법이 많이 연구되고 있다. 동적 심볼릭 실행 기법은 프로그램을 실행하는 방식과 심볼릭 실행을 결합하여 다양한 실행 경로에 도달할 수 있는 테스트 케이스를 자동으로 생성한다. 동적 심볼릭 실행 기법은 바이너리 프로그램을 실행하면서 수행되는 모든 기계어들을 기록한다. 바이너리 프로그램의 실행이 완료되면, 입력값에 의해 영향을 받은 분기문을 분석하여 실행 경로의 제약조건을 추출한다. 추출된 제약조건은 하나씩 부정된 이후에 제약조건들에 대한 풀이과정을 거쳐 다른 경로를 실행할 수 있는 테스트 케이스를 생성하는데 이용된다. 이러한 과정은 프로그램에 존재하는 모든 경로에 도달할 수 있는 테스트 케이스가 생성되거나 정해진 시간이 지날 때까지 반복된다. 동적 심볼릭 실행은 수행되는 모든 기계어들을 기록해야 하고, 기계어들로 부터 추출한 경로의 제약조건을 푸는 과정을 거쳐야 한다. 두 가지 작업 모두 많은 시간이 걸리며 특히 제약조건을 푸는 과정은 NP-Complete한 문제로 알려져 있다.
그래서 우리는 API 수준의 동적 심볼릭 실행을 수행하여 입력 포멧에 대한 정보인 퍼징 문법을 자동으로 생성하는 기술을 제시한다. API 수준의 심볼릭 실행은 기계어 수준이 아닌 함수 수준에서 경로의 제약조건을 수집한다. 이는 개발자들이 문자열을 처리할 때 직접 작성한 코드보다는 잘 알려진 라이브러리 함수들을 사용한다는 가정을 기반으로 한다. API 수준의 동적 심볼릭 실행은 기계어 수준의 동적 심볼릭 실행에 비해 다소 부정확할 수 있다는 단점이 있지만, 바이너리 프로그램에 대해 매우 빠른 속도로 퍼징 문법을 생성할 수 있다는 장점이 있다. 일반적으로 경로를 실행한다고 해서 반드시 취약점이 발견되는 것은 아니다. 가령 버퍼오버플로우 취약점의 경우 취약한 경로를 실행하는 것 뿐만 아니라 일정 길이 이상의 문자열이 입력될 필요가 있다. 우리가 제안하는 퍼징 문법은 입력 문자열 중 실행경로에 영향을 주는 부분과 그렇지 않은 부분을 명시적으로 구분한다. 따라서, 실행경로에 영향을 주지 않는 부분을 긴 문자열 등으로 대체한 테스트 케이스는 버퍼오버플로우 취약점 등도 쉽게 발현시킬 수 있다.
우리가 제안하는 API 수준의 동적 심볼릭 실행의 수행과정은 다음과 같다. 먼저 테스트 대상이 되는 함수에 대해서 문자열 인자를 식별한다. 문자열 인자에 대해서는 모든 문자열이 될 수 있음을 의미하는 초기 문법을 생성한다. 초기 문법으로부터 테스트 케이스를 생성하여 대상 함수를 실행한다. 대상 함수를 실행하는 동안 문자열 비교 함수에 대한 모니터링을 수행하여 실행되는 모든 문자열 비교 함수들을 기록한다. 대상 함수의 실행이 종료되면, 해당 기록을 분석하여 실행 경로에 대한 제약조건을 추출한다. 우리는 사용된 문자열 비교 함수들을 제약조건으로 추출하기 위한 4가지 규칙을 제공한다. 실행경로에 대한 제약조건이 추출되면, 각 제약조건을 부정하고, 현재 문법과 결합함으로써 다른 경로를 실행하기 위한 문법을 생성할 수 있다.
우리가 제안하는 방법은 문법 기반 퍼징에서 문법 생성을 자동화 한다. 이를 통해 우리의 기술은 블랙박스 퍼징의 낮은 코드 커버리지 문제를 해결할 수 있다. 또한 우리의 기술은 동적 심볼릭 실행에서 시간이 많이 걸리는 기계어 기록 과정과 실행 경로의 제약조건을 푸는 과정을 제거함으로써 매우 빠른 속도로 수행이 가능하다. 우리가 제안하는 방법의 다른 장점은 문서가 아닌 바이너리 프로그램으로부터 직접 문법을 생성한다는 점이다. 이로 인해 문서와 구현의 불일치가 존재하더라도 우리가 제안하는 방법으로는 구현된 상황을 적절히 반영한 문법을 생성할 수 있다.
우리가 제안한 방법에 대한 실효성을 검증하기 위해 우리는 YMIR 시스템을 개발하였다. YMIR 시스템은 액티브액스 컨트롤에 대한 퍼징 문법을 자동으로 생성하는 시스템으로써 우리가 아는 한 액티브액스 컨트롤에 대한 세계 최초의 화이트박스 퍼저이다. 실험결과 YMIR 시스템은 입력 포멧이 복잡한 액티브액스 컨트롤에 대해서 블랙박스 퍼징에 비해 15-50\%의 코드 커버리지를 증가시킬 수 있었다. 또한, YMIR 시스템은 복잡한 형태의 입력 포멧을 만족할 때만 발생되는 세 가지 취약점을 발견할 수 있었다. 이러한 세가지 취약점은 블랙박스 퍼징으로는 발견할 수 없다.
우리가 제안한 방법은 액티브액스 컨트롤 뿐만 아니라 입력 문자열을 처리하는 다른 프로그램들에 대해서도 적용할 수 있다. 예를 들어, 텍스트 기반 프로토콜을 이용하는 네트워크 프로그램이나 텍스트 기반 파일을 처리하는 프로그램에 대해서도 적용할 수 있다.
