[논문]프로그램 분석을 위한 정적분석 기반 역추적 제어흐름그래프 생성 방안 모델

박성현; 김연수; 노봉남

doi:10.13089/jkiisc.2019.29.5.1039

프로그램 분석을 위한 정적분석 기반 역추적 제어흐름그래프 생성 방안 모델
Static Analysis Based on Backward Control Flow Graph Generation Method Model for Program Analysis 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.29 no.5, 2019년, pp.1039 - 1048

박성현 (전남대학교 정보보안협동과정) , 김연수 (전남대학교 정보보안협동과정) , 노봉남 (전남대학교 정보보안협동과정)

초록
AI-Helper

프로그램 자동 분석 방법 중 하나인 기호 실행은 지난 몇 해 동안 기술적으로 크게 향상 되었다. 그러나 여전히 기호실행 그 자체만을 이용하여 프로그램을 분석하는 것은 실용적이지 않다. 가장 큰 이유로는 프로그램 분석 중에 발생하는 경로 폭발 문제로 인한 메모리 부족으로, 기호 실행을 이용해 프로그램의 모든 경로의 해를 구할 수 없다. 따라서 분석가는 모든 경로의 해를 구하는 것이 아닌 취약성을 갖는 지점으로 기호 실행 탐색 경로를 구성하는 것이 실용적이다. 본 논문에서는 기호 실행 과정에서 사용될 수 있는 정적분석 기반 바이너리 역방향 제어 흐름 그래프 생성 방법 기술을 제안한다. 역방향 제어 흐름 그래프 생성을 통해 분석가는 바이너리 내의 잠재적인 취약지점을 선정할 수 있고, 해당 지점으로부터 생성된 역추적 경로는 향후 기호 실행을 위해 효율적으로 사용될 수 있다. 우리는 리눅스 바이너리(x86)를 대상으로 실험을 진행하였고, 실제로 잠재적인 취약점 선정 및 역추적 경로 생성이 바이너리의 다양한 상황에서 가능함을 보였다.

Abstract ▼ AI-Helper

Symbolic execution, an automatic search method for vulnerability verification, has been technically improved over the last few years. However, it is still not practical to analyze the program using only the symbolic execution itself. One of the biggest reasons is that because of the path explosion problem that occurs during program analysis, there is not enough memory, and you can not find the solution of all paths in the program using symbolic execution. Thus, it is practical for the analyst to construct a path for symbolic execution to a target with vulnerability rather than solving all paths. In this paper, we propose a static analysis - based backward CFG(Control Flow Graph) generation technique that can be used in symbolic execution for program analysis. With the creation of a backward CFG, an analyst can select potential vulnerable points, and the backward path generated from that point can be used for future symbolic execution. We conducted experiments with Linux binaries(x86), and indeed showed that potential vulnerability selection and backward CFG path generation were possible in a variety of binary situations.

주제어

표/그림 (13)

그림 Fig. 1. Insecure route acquisition issues
그림 Fig. 2. Static data flow graph with SSA Form
그림 Fig. 3. Static Backward Tracing Overview
그림 Fig. 4. I / O and data transfer function symbols for code reference identification
그림 Fig. 5. Backward Static Program Code-snippet for Dependent Variable Tracking
그림 Fig. 6. BNIL(Binary Ninja IL) Tree
그림 Fig. 7. Function Call Process in vtable
그림 Fig. 8. Indirect call recovery due to the use of function pointer table
그림 Fig. 9. Backtrace failed due to memory pointers
그림 Fig. 10. Comparison of search depth before and after indirect call recovery
그림 Fig. 11. CVE-2014-0160 Experiment result
그림 Fig. 12. CGC Binary Experiment result
표 Table 1. Experimental CGC Binary Vulnerability

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

또한 sub2는 sub1로부터 호출된 함수이다. 따라서 sub3에서 호출되는 취약 함수 후보군인 memcpy의 size 인자를 추적하여 sub1의 입력 함수로부터 전달되었는지 경로를 파악하는것이 본 정적 모델링의 목표이다.
본 논문에서는 효율적인 기호 실행을 위한 역방향 CFG(Control Flow Graph, 이하 CFG) 생성 방법에 대해 소개한다. 역방향 CFG는 프로그램을 분석하는 과정에서 잠재적인 취약점을 선정할 수 있고, 기호 실행을 위한 사전 탐색 경로를 생성하기 위한 방법이 될 수 있다.
본 논문에서는 효율적인 프로그램 분석을 위한 역방향 CFG 생성 방법에 대해 소개하였다. 역방향 CFG는 프로그램 분석 방법 중 하나인 기호 실행 과정에서 발생하는 경로 폭발 문제를 간접적으로 완화시킬 수 있다.
이는 메모리 복사 함수를 호출하는 인스트럭션을 대상으로 하였다. 이후 역추적 분석을 통해 후보군 중에서 사용자 입력에 영향을 미치는 인스트럭션 및 역추적 경로를 파악하는 경로를 생성하는 것을 목표로 한다. 이는 프로그램 분석에 있어서 흥미로운 영역만을 탐색하도록 유도함으로써 향후 기호 실행에서 발생할 수 있는 경로 폭발 문제를 간접적으로 완화시키는 것 또한 가능하다.

제안 방법

4는 POSIX에서 제공하는 메모리 복사 함수 및 입력 입출력 함수를 보여준다. 각 함수의 심볼(symbol)을 이용하여 해당하는 모든 코드 참조를 식별하고 검토한다. 여기서 심볼은 디버깅 과정에서 발견할 수 있는 함수 명을 가리킨다.
그림에서 각각은 소스라인과 그에 해당하는 소스코드를 가리킨다. 그리고 SSA Form을 통해 포인터 u(version)에 대한 프로시저 내 데이터 흐름을 분석한다. 포인터의 모든 역 참조는 데이터 흐름 그래프를 공유하므로 단일 분석 그룹을 형성한다는 것 을 알 수 있다.
이러한 두 가지 접근 방식을 모두 활용하고 Crash 가 발생한 순간에 Crash 상황에 영향을 주는 입력 영역 매핑, 잠재적 기능 분석을 제공하는 단일 프레임 워크에 코드 실행 달성을 위한 접근 방식을 통합하였다. 마지막으로, 저자가 발견, 분석 / 악용 및 보고 한 몇 가지 사항을 포함하여 공개된 취약점이 있는 통합 도구의 사례를 보여주었다.
Openssl 바이너리의 온전한 역방향 CFG를 생성하기 위해 간접 호출(indirect calls) 지점을 복구한다. 먼저 간접 호출 복구를 위해 호출 되는 함수 오프셋과 전달되는 파라미터 정보를 수집한다. 수집한 정보를 기존에 존재하는 Openssl 함수 테이블의 함수 정보(오프셋, 파라미터)와 대조한다.
따라서 수집된 메모리 복사 함수의 호출 지점 중 실제로 취약하다고 판단되는 지점만을 식별해야 한다. 먼저, 데이터 전달 함수에서 사용되는 크기 파라미터가 사용자 입력 데이터에 영향을 받는지 확인한다. 이는 가장 먼저 함수 내 탐색(Infra-procedure) 과정에서 레지스터 변수의 상태를 확인할 수 있다.
생성된 역방향 CFG 생성은 향후 기호 실행의 탐색을 효율적으로 가이드 할 수 있다. 우리는 바이너리를 대상으로 정적 모델링 방법을 제안했다. 모델링 과정에서 발생하는 가상 함수 및 함수 포인터 호출에 따른 문제, 그리고 메모리 포인터 변수에 따른 역추적 문제를 해결하였다.
우리는 정적 모델링 방법을 제안하고, 먼저 잠재적인 취약 지점 후보군을 선정한다. 이는 메모리 복사 함수를 호출하는 인스트럭션을 대상으로 하였다.
이러한 두 가지 접근 방식을 모두 활용하고 Crash 가 발생한 순간에 Crash 상황에 영향을 주는 입력 영역 매핑, 잠재적 기능 분석을 제공하는 단일 프레임 워크에 코드 실행 달성을 위한 접근 방식을 통합하였다. 마지막으로, 저자가 발견, 분석 / 악용 및 보고 한 몇 가지 사항을 포함하여 공개된 취약점이 있는 통합 도구의 사례를 보여주었다.
제안하는 방법의 검증을 위해 정적 분석 기술을 기반으로 초기 취약점이 발생할 수 있는 함수 호출 지점을 수집하고, 제안하는 모델링 과정을 통해 이와 관련된 입출력 함수식별을 수행한다. 해당 실험을 위해 Binary Ninja Version 1.
해당 연구는 LLVM 컴파일러의 중간 표현식을 통해 구현되었다. LLVM에서 제공되는 정적 단일 할당(SSA Form : Static Single Assignment Form)[16]형식은 데이터 흐름 그래프로 직접 변환된다.
해당 연구는 동적 분석을 기반으로 프로그램이 시작하는 과정에서부터 Crash가 발생할 때까지의 모든 인스트럭션을 기록하였다. 그리고 최종적으로 Crash가 발생하였다면, 해당 지점에서부터 수집된 인스트럭션을 기준으로 역방향 오염분석을 진행한다.

대상 데이터

CGC 바이너리[19]는 총 6종을 대상으로 실험하였다. 2014년도부터 DARPA는 100개 이상의 취약한 프로그램에 대한 소스코드를 공개했다.
Dowser의 핵심 아이디어는 프로그램 분석을 통해 소스코드에서 예비 타겟 지점을 추출하고, 그에 대한 입력 값을 생성하는 테스트 케이스를 추출할 수 있음을 보여준다. 그 중에서 취약점에 사용될 수 있는 복잡한 포인터 연산을 타겟으로 분석을 진행한다.
본 논문에서는 기본적으로 Out-of-bounds 취약점을 유발하는 함수를 대상으로 하였다. 일반적으로 모든 메모리 복사 함수를 호출하는 인스트럭션을 취약 대상 후보군으로 선정하는 것은 옳지 않다.

이론/모형

이 문제를 해결하기 위하여 정적 오염분석 알고리즘이 활용되었다. 정적 오염분석 알고리즘은 변수의 데이터 의존관계를 식별하는데 적합하다.
이러한 문제는 변수의 임시적 요소(temporal element)를 전혀 고려하지 않았기 때문에 발생한다. 임시적 요소를 극복하고, eax와 같은 변수를 정확하게 추적하기 위해 이 논문에서는 BNIL(Binary Ninja Intermediate Language)[16]을 활용한다. BNIL 형식의 SSA Form[17]은 Binary Ninja Platform에서 제공하는 중간언어(IL) 형식으로 주로 함수 호출 및 메모리, 스택 관리 등을 좀 더 직관적으로 관찰할 수 있다.
제안하는 방법의 검증을 위해 정적 분석 기술을 기반으로 초기 취약점이 발생할 수 있는 함수 호출 지점을 수집하고, 제안하는 모델링 과정을 통해 이와 관련된 입출력 함수식별을 수행한다. 해당 실험을 위해 Binary Ninja Version 1.1.1470 Personal (a3b48b43)[17] 의 BNIL을 활용하여 Plugin Code을 작성하였다.
후보군 중 하나인 데이터 전달함수의 크기 파라미터를 시작점으로 크기 파라미터가 의존하는 모든 변수를 추적하기 위해 역방향 정적 프로그램 분석(backward static program analysis) 기법을 사용한다.

성능/효과

모델을 적용하지 않을 경우 낮은 깊이에서 추적이 중단된 반면(Indirect Call로 인한 추적 중단)에, 모델을 적용할 경우 입력지점까지의 높은 깊이까지의 추적이 가능함을 보였다. 검증을 위해 실제 소스코드에 존재하는 함수 호출 정보를 확인한 결과 깊이에 따른 올바른 매칭이 이루어졌음을 확인할 수 있었다.
10는 Openssl의 간접 호출을 복구한 역추적 CFG의 함수 호출 깊이를 비교한 것이다. 모델을 적용하지 않을 경우 낮은 깊이에서 추적이 중단된 반면(Indirect Call로 인한 추적 중단)에, 모델을 적용할 경우 입력지점까지의 높은 깊이까지의 추적이 가능함을 보였다. 검증을 위해 실제 소스코드에 존재하는 함수 호출 정보를 확인한 결과 깊이에 따른 올바른 매칭이 이루어졌음을 확인할 수 있었다.
제안하는 방법을 통해 분석가는 생성된 역방향 CFG는 바이너리 내의 취약점이 발생할 수 있는 타겟 후보군을 추출할 수 있고, 해당 지점으로부터 사용자 입력 지점까지의 탐색 경로 추출을 통해 향후 프로그램 분석을 용이하게 할 수 있다. 실제 취약점을 갖는 Openssl 바이너리와 CGC 바이너리를 대상으로 실험을 진행한 결과 바이너리의 다양한 상황에서 역방향 CFG가 생성 가능함을 보였다.
모델링 과정에서 발생하는 가상 함수 및 함수 포인터 호출에 따른 문제, 그리고 메모리 포인터 변수에 따른 역추적 문제를 해결하였다. 제안하는 방법을 통해 분석가는 생성된 역방향 CFG는 바이너리 내의 취약점이 발생할 수 있는 타겟 후보군을 추출할 수 있고, 해당 지점으로부터 사용자 입력 지점까지의 탐색 경로 추출을 통해 향후 프로그램 분석을 용이하게 할 수 있다. 실제 취약점을 갖는 Openssl 바이너리와 CGC 바이너리를 대상으로 실험을 진행한 결과 바이너리의 다양한 상황에서 역방향 CFG가 생성 가능함을 보였다.

후속연구

해당 연구는 동적 분석을 기반으로 프로그램이 시작하는 과정에서부터 Crash가 발생할 때까지의 모든 인스트럭션을 기록하였다. 그리고 최종적으로 Crash가 발생하였다면, 해당 지점에서부터 수집된 인스트럭션을 기준으로 역방향 오염분석을 진행한다. 결국 크래시가 발생하였을 때, 분석가는 입력의 오프셋 및 해당 테스트 케이스 값을 추출할 수 있다.
역방향 CFG는 프로그램 분석 방법 중 하나인 기호 실행 과정에서 발생하는 경로 폭발 문제를 간접적으로 완화시킬 수 있다. 생성된 역방향 CFG 생성은 향후 기호 실행의 탐색을 효율적으로 가이드 할 수 있다. 우리는 바이너리를 대상으로 정적 모델링 방법을 제안했다.

질의응답

핵심어	질문	논문에서 추출한 답변
	기호 실행이란 무엇인가?	이러한 자동화 기술 중 기호 실행(Symbolic Execution)[5] 기술이 각광 받고 있다. 기호 실행은 말 그대로 추적하고 싶은 변수를 기호적인 표현으로 두고 해당 기호 변수로 인해 발생하는 방정식의 해를 풀어내는 기술이다. 즉, 기호 실행은 특정 경로에 도달하기 위핸 하를 풀어내는 방식으로 소프트웨어의 특징이나 행위를 분석하는 연구가 가능하다.
	기호실행 그 자체만을 이용하여 프로그램을 분석하는 것의 한계점은 무엇인가?	그러나 여전히 기호실행 그 자체만을 이용하여 프로그램을 분석하는 것은 실용적이지 않다. 가장 큰 이유로는 프로그램 분석 중에 발생하는 경로 폭발 문제로 인한 메모리 부족으로, 기호 실행을 이용해 프로그램의 모든 경로의 해를 구할 수 없다. 따라서 분석가는 모든 경로의 해를 구하는 것이 아닌 취약성을 갖는 지점으로 기호 실행 탐색 경로를 구성하는 것이 실용적이다.
	역방향 제어 흐름 그래프 생성의 장점은 무엇인가?	본 논문에서는 기호 실행 과정에서 사용될 수 있는 정적분석 기반 바이너리 역방향 제어 흐름 그래프 생성 방법 기술을 제안한다. 역방향 제어 흐름 그래프 생성을 통해 분석가는 바이너리 내의 잠재적인 취약지점을 선정할 수 있고, 해당 지점으로부터 생성된 역추적 경로는 향후 기호 실행을 위해 효율적으로 사용될 수 있다. 우리는 리눅스 바이너리(x86)를 대상으로 실험을 진행하였고, 실제로 잠재적인 취약점 선정 및 역추적 경로 생성이 바이너리의 다양한 상황에서 가능함을 보였다.

참고문헌 (19)

Heelan, Sean. Automatic generation of control flow hijacking exploits for software vulnerabilities. 2009.
Avgerinos, Thanassis, et al. "Automatic exploit generation." Communications of the ACM 57.2. 2014.

상세보기
Cha, Sang Kil, et al. "Unleashing mayhem on binary code." Security and Privacy (SP), 2012 IEEE Symposium on. IEEE. 2012.
Huang, Shih-Kun, et al. "Software crash analysis for automatic exploit generation on binary programs." IEEE Transactions on Reliability 63.1 : 270-289. 2014.

상세보기
Cadar, Cristian, et al. "Symbolic execution for software testing in practice: preliminary assessment." Proceedings of the 33rd International Conference on Software Engineering. ACM. 2011.
Cadar, Cristian, Daniel Dunbar, and Dawson R. Engler. "KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs." OSDI. Vol. 8. 2008.
Sen, Koushik, Darko Marinov, and Gul Agha. "CUTE: a concolic unit testing engine for C." ACM SIGSOFT Software Engineering Notes. Vol. 30. No. 5. ACM. 2005.
Godefroid, Patrice, Nils Klarlund, and Koushik Sen. "DART: directed automated random testing." ACM Sigplan Notices. Vol. 40. No. 6. ACM. 2005.

상세보기
Burnim, Jacob, and Koushik Sen. "Heuristics for scalable dynamic test generation." Automated Software Engineering, 2008. ASE 2008. 23rd IEEE/ACM International Conference on. IEEE. 2008.
Chipounov, Vitaly, Volodymyr Kuznetsov, and George Candea. "S2E: a platform for in-vivo multi-path analysis of software systems." ACM SIGPLAN Notices 46.3 : 265-278. 2011.

상세보기
Cadar, Cristian, and Koushik Sen. "Symbolic execution for software testing: three decades later." Commun. ACM 56.2 : 82-90. 2013.

상세보기
Sanjay Rawat, Laurent Mounier, and Marie-Laure Potet, "Lightweight Static Taint Analysis for Binary Executables Vulnerability Testing", University of Grenoble, 2009.
Rohit Mothe, "DPTrace: Dual Purpose Trace for Exploitability Analysis of Program", BlackHat US. 2016.
Haller, Istvan, et al. "Dowsing for Overflows: A Guided Fuzzer to Find Buffer Boundary Violations." Presented as part of the 22nd USENIX Security Symposium pp. 49-64. 2013.
Neugschwandtner, "The borg: Nanoprobing binaries for buffer overreads". In Proceedings of the 5th ACM Conference on Data and Application Security and Privacy (pp.87-97). ACM. 2015
Static simgle assignment form, https://en.wikipedia.org/wiki/Static_single_assignment_form. 2019
Binary Ninja, https://binary.ninja/. 2019
CVE-2016-0160, https://cve.mitre.org/cgi-bin/cvename.cgi?nameCVE-2016-0160
CGC-Binary, https://github.com/CyberGrandChallenge/

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증