2015년에 미국 국방성 산하의 연구 계획국인 DARPA에서 사이버 그랜드 챌린지(CGC)를 개최하여 완전 자동화된 소프트웨어 취약점 분석에 대한 연구를 독려한 바 있다. 치열한 예선을 거쳐 선발된 7개 팀은 2016년 DEFCON 컨퍼런스에서 결선을 치렀다. 본선 진출팀은 대학 연구기관도 있었고 일반 기업도 있었다. 그중 한 팀이었던 University of Idaho의 CSDS팀은 비록 높은 순위를 기록하지는 못하였지만, 자신들이 경험한 기록들을 정리하여 IEEE에 기고하였다. (국내에서는 KAIST의 , KaisHack GoN 홈페이지에서 Cyber Grand Challenge 후기 라는 제목으로 남겨진 Sang Kil Cha 교수님의 글이 유일한 참관 후기이다.)

또한 Usenix Security Symposium 에서 DARPA가 직접 발표한 Machine vs. Machine: Lessons from the First Year of Cyber Grand Challenge 내용도 참고했다.

본 블로그 포스팅에서는 University of Idaho의 Jia Song 이 남긴 2개의 기고글을 하나로 엮어서 해당 내용의 요지를 정리해보았다. (전체 문장 번역이 아닌, 요약 번역임)

*대회 영상 Youtube : 

자동화된 소프트웨어 취약점 분석은 굉장히 어려운(일반적으로 풀이 해법이 존재하지 않는) 문제이다. 2014년 미국 국방성 산하의 방위 고등 연구 계획국(Defense Advanced Research Projects Agency, 이하 DARPA)에서는 일명 사이버 그랜드 챌린지(Cyber Grand Challenge, CGC)라는 대회를 개최하여 
완전 자동화된 소프트웨어 취약점 분석 및 패치하는 기술의 혁신을 촉진을 꾀하였다. 본 기고글에서는 당시 대회에 참가팀이었던 University of Idaho의 Jia Song 및 Jim Alves-Foss의 경험담을 토대로 해당 경연 과정을 전달하고자 한다.


경연 방식

CGC를 주최한 위원들은 먼저 문제의 범위(Problem Space)를 설정하였다. 어려우면서도 현실적인 수준에서 측정이 가능하도록 기준을 제시하였고 이를 기반으로 DECREE라는 실험 환경을 구축하였다. 이는 오픈소스 리눅스 기반으로 설계하였으며 다양한 사이버 보안 실습이 가능하도록 설정하였다. DECREE 운영체제에 포함되어 있는 파일들은 실행 가능한 바이너리 또는 링킹 하여 사용하는 라이브러리 형식이었는데, 이들은 오직 7개의 system call(terminate, send, receive, fdwait, rand, allocate, deallocate)만을 지원하였다. DARPA는 또한 이들을 자동으로 테스트하고 그 결과를 평가할 수 있는 도구도 개발하였다. 이처럼 챌린지를 위하여 구성된 프로그램들은 DECREE에서 구동되며, 기존의 network application level의 protocol을 사용하지 않고 inetd 형식의 네트워크 서비스를 제공하였다. 이 CB(Challenge Binaries)들은 오직 C/C++ 만을 사용하여 작성되었으며 assembly로 직접 코딩하는 것은 허용하지 않았다. 이후 Intel 32-bit 환경에서 Clang 컴파일러를 사용해 빌드되었고, 해당 바이너리에는 하나 혹은 그 이상의 취약점들이 포함되어 있었으며 그에 대한 문서화된 자료 역시 제공되었다. 모든 디버그 정보와 심볼 테이블은 전부 삭제된 채로 제공되었다. 경연에 참여할 팀들은 해당 바이너리에 구체적인 메모리 오류와 그를 이용한 불법적인 접근을 통해 실제로 해킹하는 것 까지를 입증 해야 했다. DARPA가 이렇게 고심해서 환경을 직접 구축한 이유는, 이미 기존에 알려져 있는 운영체제 또는 프로토콜의 취약점에 대하여 경연자(사람)의 배경지식에 의해 좌지우지되는 것을 막고 오로지 소프트웨어 자체만으로 자동화된 취약점 분석에 집중할 수 있도록 하기 위함이었다. 

혁신적이고 획기적인 새로운 방안 연구를 장려하기 위하여, DARPA는 연구 용역을 통해 7개의 팀에 연구비를 지원하였고, 그 외에 연구비 지원을 받지 않은 독립 팀들도 경연에 참가할 수 있도록 기회를 개방하였다.

DECREE의 최초 버전이 2014년 6월에 공개되었고, 곧이어 연구 용역 대상 팀에 대한 수주가 진행되었다. 이듬해 챌린지를 위한 문제집과 DECREE가 업데이트되었고, 경연 참여자를 위한 개발 도구가 제공되었다. 이후 2014년 12월과 2015년 4월에 두 차례의 연습 경기를 운영하였다. 이때에는 자동으로 솔루션을 통합 테스트할 수 있는 CRS 시스템 방식을 통해 진행하였다. CGC의 예선 이벤트인 Qualifying Event (CQE)에 지원하기 위해 100개 이상의 팀이 몰려들었고, DARPA 가 심사 후 최종적으로 28개의 팀에 대하여 출전권을 부여하였다. 각 팀들은 131개의 문제집을 분석하여 잠재적인 취약점을 식별하고, 이를 자동으로 패치한 후 이를 증빙하는 보고서(Proof of vulnerability)를 DARPA에 송부하는 형식으로 진행되었다. 이 POV 결과물에 기반하여 점수를 부여하였는데, 이때 단순히 취약점을 고치는 것에만 초점을 맞춘 것이 아니라 패치 방식이 효율적인지 여부도 중요한 채점 기준에 속하였다. 예를 들어 런타임 시간이 길어진다거나 메모리 누수, 디스크 저장공간 낭비 등의 비용 증가 이슈들은 오히려 페널티가 부과되었다. 

DARPA는 최종적으로 팀 순위를 매기고, 상위 7개 그룹에 대하여 본선인 Final Event (CFE) 출전권을 부여하였다. 본선 경기는 매년 개최되는 해커들의 축제인 DEF CON 2016 콘퍼런스에서 진행할 예정이었으며 1등 상금은 2백만 달러(한화 약 23억 원)이었다. 당시 본선에 진출한 팀은 아래와 같다.

  • Funded-track(3)
    • ForAllSecure ( from Carnegie Mellon University ) : Mayhem
    • TechX ( from GrammaTech, University of Virginia) : Xandra
    • Codejitsu ( from University of California, Berkeley) : Galactica
  • Open-track(4)
    • CSDS ( from University of Idaho ) : Jima
    • Deep Red ( from Raytheon) : Rubeus
    • Disekt ( from Athens, Georgia) : Crspy
    • Shellphish ( from University of California at Santa Barbara) : Mechanical Phish

(*역자 주 : 본 기고글의 저자가 속한 팀은 미국 Moscow의 아이다호 대학 및 해당 대학의 CSDS(Secure and Dependable System) 연구 센터이다. 시스템 명칭인 JIMA는 본 기고글 저자인 JIM과 JIA의 이름을 합친 것이다.) 

출처 : University of Idaho 학과 소개 자료


대회는 컴퓨터 대 컴퓨터 방식으로 CTF(Capture the flag)를 수행하는 형태였다. 각 컴퓨터들은 사람이 운영하는 것이 아닌 자동화된 방식으로 작동하였다. 각 팀들은 CRS 시스템을 설계하고 이를 통해 DARPA의 Framework와 통신하면서, 자신이 관리하는 대상 서버에 대해서는 패치를 통해 취약점으로부터 보호하고, 이와 동시에 다른 팀의 CS에 대해서는 공격을 시도하여 점수를 획득하는 방식이었다. 

취약점의 입증(POV)은 두 가지 종류로 구성되는데, 한 가지는 프레임워크의 특정 메모리 주소에서 어떤 값을 이용한 범용 레지스터 조작을 통해 memory fault를 유발하는 것이다. 또 다른 유형은, 프레임워크의 특정 메모리 영역의 범위 안에 저장된 flag 값을 찾아내는 것이다. POV는 메모리 주소나 데이터 값이 프레임워크에서 정의한 것과 최소 20 bits가 일치하는지 여부로 판단하였다. 현재 본 기고를 작성하는 시점에도 DARPA는 이를 전체적으로 확장 적용할 수 있는 방안을 계속해서 개발하는 중으로 알려져 있다. 

예선이었던 CQE와 본선 CFE 대회 모두에서 성공적인 결과를 얻기 위해서는, CRS를 구축할 때에 바이너리에 대한 리버스 엔지니어링 및 자동화된 취약점 분석 기술을 반드시 적용해야만 했다. 


Binary Reverse Engineering

각 팀들은 제시된 각 바이너리를 분석하고 취약점을 발견하면 이를 적절하게 패치할 수 있는 CRS 시스템을 설계해야 했다. 이 과정에는 거의 필연적으로 디스어셈블 작업이 요구되는데, 바이너리 자체만으로는 알 수 없는 다양한 정보들을 복원해내는 것이 핵심이었다. 

CGC에 참가하는 팀들은 취약점을 찾고 패치하기 위해서 반드시 바이너리에 대한 역공학 작업을 수행해야만 했다. 특히 CQE 에서는 단순히 주어진 바이너리에 대한 취약점을 찾기 위함이었다면 CFE에서는 다른 팀이 패치한 바이너리에 대해서 또 다른 취약점이 있지는 않은지 확인하기 위해서 또다시 리버싱을 수행해야만 했다. 

사실 이는 굉장히 어려운 일인데, 컴파일시에 여러가지 코드/데이터 섹션 정보들이 사라지기도 하고 각 명령어의 배치된 순열을 조금이라도 잘못 해석할 경우 전혀 엉뚱한 결과를 낳을수도 있기 때문이다. 오픈소스로 널리 사용되는 objdump나 상용 도구인 IDA Pro의 경우 적절한 휴리스틱 기법을 사용하여 이러한 어려움을 해결하고자 했는데 이는 사실 이론적으로 문제를 완벽히 풀어낼 수 있는 방법은 아니다. 

결승에 진출한 팀들의 경우 나름대로의 아이디어를 통해 굉장히 어려운 종류의 리버싱 문제를 해결하긴 했지만 이를 완전히 해결했던 팀은 거의 없었다. 

바이너리로 부터 정보를 얻기 위해서, 어떠한 곳에 중요한 데이터가 있는지를 파악하는 것이 필요하다.

그림 1은 DARPA 챌린지 바이너리 중 하나에 속한 함수를 디스어셈블한 것이다. 예를 들어 초반부 작업을 보면 베이스포인터(ebp)를 스택에 저장하고, 현재 스택 포인터(esp)를 베이스포인터에 저장한다. 또한 함수가 종료되는 부분에서는 현재 스택 포인터를 베이스포인터로 복구한 후 ret을 통해 다음에 수행할 주소로 이동한다. 이 때 표현식에서 사용되는 계산들을 살펴보면 모두 0x80497b0 와 같은 하드 코딩된 주소를 사용하고 있는데 이렇게 되는 이유는 바이너리에서는 소스코드에 있던 다양한 정보들이 심볼 테이블 형태로 변환된 뒤 그 주소값만 남겨두고 나머지 정보들이 전부 지워지기 때문이다.

역공학을 수행할 때에는 보통 원래의 프로그래머가 C/C++ 언어로 구현했을 때에 그가 어떤 의도를 가지고 있었는지를 파악하는 것이 필요하다. 만약 그것을 알 수 있다면, 해당 구현에서 어떤 결함이 있었는지를 쉽게 파악할 수 있다. 하지만 서로 다른 두개의 C언어 코드가 결국에는 동일한 어셈블리 코드를 만들어내는 경우도 있는데 이는 High-level 언어는 사실 자동으로 다양한 sematic을 맞추어주는 것일 뿐 실제 동작하는 코드는 다르게 작동하는 것일수도 있기 때문이다. 이러한 점을 감안하여 디스어셈블을 수행해야만 하는데, 본 팀에서 파악한, 리버싱에서의 중요한 요소들(함수의 리버싱을 기준으로)은 크게 다음과 같다.

1) 함수가 시작되는 지점과 끝 지점.

2) 함수의 속성. 즉, 몇 개의 파라미터를 전달하는지 등

3) 데이터 영역에 위치한 변수 주소

4) 취약점이 발생하는 코드의 위치


Vulnerability Analysis

대회에 출전한 대다수의 팀들은 취약점 분석을 수행하기 위해 대체적으로 아래의 기술들을 적용하였다.

  • Black-box testing : fuzzing을 사용하여 입력값 범위 내에서 무작위로 생성된 값으로 테스트하고, 프로그램에 crash가 발생하는지 점검하였다. 
  • White-box testing : 일종의 guided fuzzing을 위하여 정적 분석 및 code instrumentation을 통한 simulation을 적용하였다. 최근에는 symbolic execution 으로 퍼징의 효율을 높이는 연구들도 많다. 
  • Simulation and symbolic execution : 실행시간에 inspection 과 analysis를 수월하게 사용할 수 있도록 하는 시뮬레이션 환경을 구축함으로써 특정 code path나 array bounds 의 overrun 을 파악할 수 있다. 

CGC 대회 중에는 취약점이 발견되면 자동화된 도구에 의해 POV 보고서를 생성해야만 했다. CQE에서는 단지 XML 형식으로 정의된 내용을 출럭하기만 하면 됐지만, CFE에서는 실제로 경기 framework와 상호작용하는 동작가능한 코드를 제출함으로써  type 1 또는 type 2 error에 대한 발생 여부를 점검하는 방식으로 비교적 더 까다로워졌다. 


Patching Stripped Binaries

대회에 출제된 문제의 바이너리들은 debug symbol과 기타 분석을 위한 정보들이 제거된 채로 제공되었다. 이러한 것을 극복하기 위해서는 다음과 같은 작업들이 필요했다.

- Static Analysis : 정적 분석이란 바이너리를 byte들의 집합으로 보고 이를 적절히 명령어와 데이터 부분으로 분리해내는 작업이다. 하지만 이 작업은 적절한 경계선을 찾아내지 못한다면 완전히 잘못 해석될 수 있다.

- Dynamic Analysis : 동적 분석이란 프로그램이 실행되는 상태에서의 분석을 의미한다. 프로그램이 실제로 동작할 때 발생하는 instruction을 분석하긴 해도 그렇다고 해서 코드의 모든 부분을 파악할 수 있는 것은 아니다. 왜냐하면 코드에 포함되어는 있지만 control flow에 따라 실행되지 않고 지나치는 코드 부분이 있을 수도 있기 때문이다. 동적 분석에서는 이러한 점을 고려하여, dynamic binary instrumentation이나 symbolic execution을 통해 보다 정확한 분석을 수행할 수 있도록 하였다.

- Which Representation? : 동적이나 정적 분석을 통해 프로그램의 동작을 이해하고 취약점을 찾을 때 결국에는 프로그램을 일종의 중간 언어(Intermediate Language representation) 형식으로 표현하는 것이 중요하다. 최근에는 LLVM 이 대세를 이루고 있다. 

- Artificial Intelligence : 흔히 '인공지능'이라고 지칭하는 기술이 최근 유행하고 있다. 하지만 이를 위해서는 다량의 데이터를 통한 분석과 그 안에서 의미를 찾아내고 분류하는 방법을 학습시키는 과정이 수반된다. 하지만 이러한 문맥을 바이너리 수준에서 완벽히 적용한 연구는 아직 턱없이 부족한 실정이다. 본 팀은 결국 인공지능 방식이라기보다는 사람이 직접 분석하는 과정을 알고리즘화 시켜서 이를 구현하는 쪽으로 진행하였다. 예를 들면 CALL 함수가 호출되는 순간이라던지, NOP operation의 사용 등을 토대로 휴리스틱 기반의 판단 조건을 설정하고 분석을 진행하였다. 만약 조금 더 깊이 있는 연구가 진행된다면 머신 러닝을 통하여 자동으로 feature들을 선별할 수 있는 날이 올지도 모르겠다.

- Site-Specific or Generic patching? : CQE는 결국 최종적으로는 취약점에 대한 패치를 성공적으로 내놓았는지를 득점 요인으로 두고 있었다. 아무리 분석을 잘해도 패치를 하지 못한다면 소용없으므로 각 팀들은 patch를 성공할 수 있는 방법을 찾기에 몰두하였다. 앞서 언급했듯이 overhead가 더 커진다거나 하면 해당 패치는 거절되었다. 이는 패치하는 방법에 대하여 고민을 가져오는데, 취약점을 '일반적'으로 수정할 수 있는 방법을 쓸 것인지, 아니면 해당 문제에 특화된 해법을 적용할지의 문제이다. 일반적으로 수정할 수 있는 방안을 택한다면 구현은 쉽겠지만 overhead에 대한 고민이 문제일 것이고 그 반대의 경우는 특정 문제에 대해서는 최적의 해법을 찾겠지만 모든 문제에 대해 계속해서 새로운 해법을 고민해야만 하기 때문이다.

- What is Safe code? : 과연 무엇이 '안전한' 코드를 만드는 것일까? 앞서 말한 것처럼 무작정 일반적으로 안전하게 만드는 방법은 생각보다 쉽다. 함수가 호출되는 부분이나 리턴 주소 등에 canary 등의 검사 값을 강제로 추가하도록 만들면 되는 것이다. 하지만 이렇게 되면 overpatch 문제가 발생한다. 너무 과도하게 불필요한 기능을 보안이랍시고 마구 집어넣는다면 오히려 성능을 저하시키게 된다.

- What impacts performance : 성능에 영향을 미치는 요소가 무엇인지를 정확하게 분별해야 한다. 본 팀에서는 나름대로 고민을 하여 복잡한 명령어를 단순화시킴으로써 패치된 바이너리의 크기를 줄이고자 했다. 하지만 이때 xchng 명령어를 통해 두 값을 바꾸는 작업을 수행하도록 하였었는데, 이는 오히려 runtime에서 실행시간을 엄청나게 지연시키는 결과를 낳고 말았다.  또한, Java의 result += instruction.toString() 이라는 코드와 tmp = instruction.toString(); result += temp; 라는 코드는 실제로 동일한 동작을 수행함에도 불구하고 전자가 굉장히 효율에 좋지 않음을 깨닫게 되었다. 후자로 바꾸어 테스트한 경우 runtime이 절반 수준으로 줄어들었다. 


Lessons learned (실패로부터의 교훈)

본 단락은 CSDS 팀의 개인적인 후회되는 회고이다. 내용은 축약하였다.

- Starting from scratch : 밑바닥부터 설계를 다시 했어야 했다. 처음부터 전체 흐름을 인지한 채 진행을 했다면 조금 더 효율적인 구조를 만들 수 있었을 텐데 중간중간에 디자인을 바꾸게 되면서 어려워지는 점이 많았다. 어떤 작업을 먼저 전처리해주고 그다음 어떤 것을 하고 마지막으로 무엇을 할지를 구상해두는 편이 좋았다.

- Small team dynamics : 팀 구성원의 분야 전문성과 이를 폭넓게 교류할 수 있는 분위기의 중요성 

- Code Benefit Tradeoffs :  한정된 대회 일정과 기간을 고려하여 보다 필요한 작업을 우선적으로 수행할 수 있도록 역할을 배분함. 목표와 마감기한을 정하고 각 임무를 영역별로 해결하도록 하였음. 아무래도 일정에 의해 중요하지만 수행하지는 못하고 포기했던 지점들이 아쉬웠음.


CGC Corpus Challenges

DARPA는 CGC를 운영하기 위하여 131개의 바이너리를 생성하였다. 이들은 기본적인 메시지 전송 프로그램, 가상 머신 에뮬레이터, 물리엔진 시뮬레이터, 주차 관리 시스템 등의 기능을 위해 사용되는 것들이었다. 이 바이너리들은 내부 동작 과정 중에 몇 가지 취약한 지점이 포함되어 있었고, 참가자들은 이를 찾아낸 후 적절히 패치할 수 있어야 했다. 취약점에는 버퍼 오버플로우 형식 몇 가지와 정수 오버플로우, Use After Free 등등이 포함되어 있었으며, 이를 유발하기 위한 결정적인 trigger 상태를 찾아내야만 했다. 예를 들어 메시지 전송 프로그램은 256개 이상의 읽지 않은 메시지가 있을 때 문제가 발생하였으며, 라우터 프로그램은 input value 가 0이 주어지는 경우 스택에서 buffer underflow가 발생하는 등이었다. 각 바이너리의 원본 소스코드는 DARPA CGC Github에서 확인 가능하며, 포함된 취약점에 대한 정리된 문서들도 제공된다. 

아래는 본선에 출전한 7개의 팀의 풀이에 대한 현황을 비교 분석한 자료이다. 데이터를 분석해보면, CB에 대한 취약점 40개를 찾아낸 팀은 없었으며 20 CB 한 팀이 최고점이었다. 

표의 가장 마지막 줄은 패치된 결과물에 대한 기능의 효율성과 보안성 정도를 곱한 값을 나타내는데, 일부의 경우 오히려 패치가 정상적인 작동을 저해한다는 이유로 페널티가 부과되기도 하였다.


DARPA는 DECREE 환경과 각종 도구를 구축하고 이를 공개했다. (https://cgc.darpa.mil). 소스코드 및 취약점에 대한 일람, 각각의 문제들을 대회용으로 컴파일하기 위한 makefile 설정 등도 포함되어 있다. 또한, 참가팀들이 취약점을 패치하여 제출한 결과물, POV, 그리고 그에 따른 채점 결과까지 공개하였다.  이처럼 본 대회의 기록을 친절하고 자세하게 공개함으로써 향후 이어질 자동화된 프로그램 분석 분야에 대한 후속 연구를 강력히 지원하였다. 여러분도 이 자료를 통해 다각도의 실험을 직접 반복적으로 수행해볼 수 있다. 

Software Security Engineer

CPUU님의 창작활동을 응원하고 싶으세요?