452 정보과학회논문지 : 소프트웨어및응용제 35 권제 7 호 (2008.7) 프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 (Analyzing Differences of Binary Executable Files using Program Structure and Constant Values) 박희완 최석우 서선애 한태숙 (Heewan Park) (Seokwoo Choi) (Sunae Seo) (Taisook Han) 요약바이너리코드의차이점분석은보안패치와같은매우유사한두프로그램사이의차이점을구별해주는방법이다. 이전의연구에서는분석을위하여프로그램의구조또는명령어의세부사항만을각각이용하였다. 프로그램의구조를이용하는차이점분석방법은제어흐름의변화는잘탐지해낼수있지만, 버퍼크기변화와같은상수값의변화는잘찾아낼수없다. 명령어기반의차이점분석방법은세부적인값의변화는발견할수있으나명령어재배치와같은컴파일러에의해생성되는불필요한차이점을결과로낸다는단점이있다. 이연구에서는프로그램구조를이용한비교분석방법에상수값의변화를함께추적할수있는방법을제안하고바이너리차이점분석도구를구현하였다. 구현된도구는윈도보안업데이트를이용하여평가하였다. 실험결과제안된방법은구조적인차이점분석과같이빠른속도로구조적인변화를찾아낼뿐아니라상수값의변화까지추적할수있다는것을보였다. 키워드 : 정적분석, 역공학, 이진코드분석, 프로그램차이점분석 Abstract Binary diffing is a method to find differences in similar binary executables such as two different versions of security patches. Previous diffing methods using flow information can detect control flow changes, but they cannot track constant value changes. Diffing methods using assembly instructions can detect constant value changes, but they give false positives which are due to compiling methods such as instruction reordering. We present a binary diffing method and its implementation named SCV which utilizes both structure and value information. SCV summarizes structure and constant value information from disassembled code, and matches the summaries to find differences. By analyzing a Microsoft Windows security patches, we showed that SCV found necessary differences caused by constant value changes which the state-of-the-art binary diffing tool BinDiff failed to find. Key words : static analysis, reverse engineering, binary code analysis, program difference analysis 본연구는지식경제부및정보통신연구진흥원의대학 IT연구센터지원사업의연구결과로수행되었음 (IITA-2008-C1090-0801-0020) 비회원 : 한국과학기술원전산학전공 hwpark@compiler.kaist.ac.kr 학생회원 : 한국과학기술원전산학전공 swchoi@compiler.kaist.ac.kr 비회원 : 한국과학기술원전산학전공박사후연구원 saseo@compiler.kaist.ac.kr 종신회원 : 한국과학기술원전산학전공교수 han@cs.kaist.ac.kr 논문접수 : 2007년 11월 19일심사완료 : 2008년 5월 30일 Copyright@2008 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 소프트웨어및응용제35권제7호 (2008.7) 1. 서론최근들어두개의유사한바이너리실행파일의차이점을분석하는도구가많이사용되고있다. 바이너리실행파일의차이점을분석하는목적은악성코드 (malware) 분석 [1], 운영체제보안패치 (security patch) 분석, 그리고프로그램도용 (code theft detection) 탐지등이있다. 악성코드의분석은악성코드에의해감염된파일과정상적인파일을비교하여악성코드의특징을발견하여악성코드를탐지하고감염된파일을치료하는데이용하기위한것이다. 운영체제보안패치의경우대부분의경우패치를통해수정한내용이공개된다. 그러나수정내용의공지없이패치만이루어지는
프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 453 경우가많다. 또한좀더구체적인변경내용을분석하여운영체제회사에서지원하지않는운영체제의버전에대한상용패치를구현해야할경우가존재한다. 이런경우에두바이너리실행파일의차이점을분석해야할필요가있다. 코드도용탐지를위해서도실행파일의차이점분석이이용된다. GPL(GNU Public License) 와같은오픈소스 (open source) 프로그램은소스코드를자유롭게사용할수있지만해당소스코드를이용한저작물에대해서도소스코드를공개할것을요구한다. 많은경우오픈소스코드를이용해서프로그램을만들지만소스를공개하지않는다. 바이너리코드의비교는이런경우에도코드의도용을탐지할수있는근거자료를얻는데사용될수있다 [2,3]. 바이너리실행파일의차이점을분석하는것은단지기계어명령어수준에서차이점을보여주는것이아니다. 이방법은기계어명령어의차이점을분석하여소스코드에서의변화된부분을발견하려는목적을가지고있다. 소스코드는컴파일과정을통해서분석에유용한함수또는변수의이름이나타입과같은정보들을잃게된다. 따라서기계어코드로부터소스코드의차이점을역으로찾아가는과정은소스코드가컴파일되었을때에도기계어코드에여전히남아있는제한된정보를이용하여분석을수행해야하기때문에분석의정확성이떨어지게된다. 하지만바이너리파일의차이점분석도구는보안업데이트와같은작은변화만있는매우유사한코드사이에서분석을하게되며, 대부분같은운영체제와같은컴파일러를가정하고있기때문에분석의정확성을높일수가있다. 기존의바이너리실행파일차이점분석방법은크게두가지로나눌수있다. 첫째는바이너리코드의명령어단위에서비교를시작하여차이점을요약해가며전체프로그램단위까지분석하는상향식분석 (bottom-up analysis) 방법이있다. 둘째는바이너리코드전체를함수단위로나누고함수단위에서비교를시작하여명령어단위까지차이점을세분화하여분석하는하향식 (top-down analysis) 방법이다. 상향식분석방법은기계어명령의차이점과같은세밀한분석을할수있다. 반면소스코드에서는변화가없으나컴파일단계에서다른컴파일러를사용한다거나최적화기법을다르게적용함을통하여발생할수있는기계어코드에서만나타나는불필요한차이점을찾아내는문제점이있다. 예를들면컴파일러나최적화기법등을통해서명령어순서변환 (instruction reordering) 이나레지스터할당 (register allocation) 에의한차이가생기는경우에상향식분석방법은코드에변화가있다는불필요한결과를제공한다. 하향식분석방법은소스코드가컴파일되더라도바이너리실행파일에서프로그램구조는원래의것과큰차이가없다는것을이용하는방법이다. 두그래프사이의구조를직접비교할수도있지만시간이많이걸린다는단점이있기때문에일반적으로는프로그램구조정보를요약하여비교하게된다. 먼저함수단위로구조정보를요약하고, 두프로그램사이에원래같은함수라고여겨지는함수사이에매칭 (matching) 이이루어진다. 함수단위의매칭이끝나면, 기본블록 (basic block) 사이의매칭이이루어지고, 마지막으로명령어단위의차이까지분석하게된다. 이방법의단점은프로그램의구조정보만을이용하기때문에상수값 (constant value) 의변화와같은구조가변하지않는차이점은발견할수가없다는것이다. 또한, 구조요약정보만을이용하기때문에서로다른함수가같은요약정보를가지는부정확한분석결과를내는경우가생긴다. 본연구에서는프로그램구조정보와상수값을요약하여차이점을분석하는바이너리코드비교방법을제안하고, 제안된방법을실제바이너리코드비교에적용할수있도록구현한도구를소개한다. 본연구에서제안하는바이너리코드비교방법은기존에제안된프로그램구조정보의비교뿐아니라, 코드내의상수값의변화도추적할수있으므로, 기존의방법보다좀더세밀한분석을할수있다. 우리는제안된방법을기반으로 SCV라는바이너리코드비교분석도구를개발하였다. 이도구를실제 Microsoft Windows 원격실행취약점에대한보안패치 1) 에적용하여봄으로써개발된도구의실용성및기존연구방법과의차별성을보이고자한다. 논문의구성은다음과같다. 제2장에서는기존의연구에대해서설명한다. 제3장에서는본논문에서제안하는상수값과구조에기반을둔바이너리코드비교방법에대해설명한다. 제4장에서는개발된도구인 SCV를소개하고, 실제 MS 윈도보안패치에적용한결과를제시한다. 제5장에서는내용을요약하고앞으로할일에대해기술한다. 2. 관련연구 2.1 명령어기반비교방법 T. Sabin은그래프일치 (graph isomorphism) 를이용해서바이너리실행파일을비교하는알고리즘을제안하였다 [4]. 이방법은먼저디스어셈블러를이용하여바이너리실행파일의코드와데이타를분리하고, 코드를함수단위로분리한다. 함수는각명령어를노드 1) 보안패치 KB938827과 KB931906이다.
454 정보과학회논문지 : 소프트웨어및응용제 35 권제 7 호 (2008.7) (node) 로, 제어흐름을에지 (edge) 로하는그래프형태로표시된다. 두프로그램으로부터각각한개씩함수를선택하여두그래프사이의일치를계산하게된다. 함수에는진입지점 (entry point) 이한개이상존재하므로진입지점으로부터시작하여각노드의일치를비교한다. 노드의일치, 즉명령어의일치는기계어명령어코드 (opcode) 의비교를통해서이루어진다. 명령어코드는완전히일치하는의미를가진경우 (semantically equivalent), 의미가유사한경우, 완전히다른경우의세가지구분으로일치를계산한다. 두함수사이의비교는두개의큐 (queue) 를이용하는너비우선검색 (breathfirst-search) 방식을사용한다. 이방법은명령어의순서까지고려하는비교를하기때문에의미가같지만명령어의순서만바뀌었을때변경된부분으로인식하는단점이있다. 그리고함수대함수의비교를하는방법은제시되어있지만어떤함수들을선택하여비교를시작할지에대해서는제시하고있지않다. DarunGrim[5]( 이하다른그림 ) 은 eeye Digital Security에서개발한바이너리실행파일비교프로그램이다. 다른그림은기본블록부터비교를시작하고함수단위매칭으로비교를끝내는상향식분석방법을사용한다. 기본블록의비교는분기문 (branch instruction) 을제외한명령어코드의값의순서 (sequence) 에의해이루어진다. 따라서컴파일러에의한명령어선택과명령어순서에의해변경된부분까지차이점을지적하기때문에사용자가관심없어하는차이점을보여주는단점이있다. 2.2 구조정보를이용하는비교방법 T. Dullien은실행파일을코드의구조정보를바탕으로비교하는방법을제안하였다 [6]. 구조적인정보란각함수내의제어흐름그래프와함수호출에대한요약정보를의미한다. 이방법은명령어기반의비교방법보다빠른비교가가능하다는장점이있다. 또한명령어기반의비교방법이소스코드는같지만컴파일러에의한명령어재배치 (instruction reordering) 나레지스터할당 (register allocation) 에의해바이너리실행파일이변경된경우두파일이다르다는결과를나타내던단점을개선하였다. Dullien의연구에서는실행파일이패치등에의해변형될때변형된부분만찾기위하여바이너리파일을함수단위로분리하여비교한다. 구분된각함수는각각의어셈블리코드를고려하지않고제어흐름만을이용하여요약한후그래프동치관계를계산하여두바이너리를비교한다. T. Dullien과 R. Rolles는그래프제어흐름그래프기반비교기법을일반화하여 selector와 property 개념을도입하였다 [7]. Property를사용하여매칭대상범위 를좁히고, selector를사용하여매칭대상을선택한다. Property와 selector를어떻게정하느냐에따라서매칭알고리즘의속도와정확도에차이가생긴다. T. Dullien과 R. Rolles의연구는 BinDiff[8] 라는상용도구에구현되었다. 본연구에서제안하는바이너리비교방법론은구조적인비교부분에있어서이들의연구를바탕으로개발되었다. 3. 바이너리코드비교를위한알고리즘이장에서는바이너리코드차이점분석을위해우리가제안한방법을소개한다. 제안된바이너리코드차이점분석은기본적으로구조적인비교를바탕으로하고, 명령어수준의차이점까지비교해줄수있는상수단위비교를포함한다. 구조적인비교는프로그램을구성하는함수단위구조를우선비교하고, 함수의매칭이끝나면함수를구성하는기본블록단위의비교를수행한다. 함수매칭및기본블록매칭을위해서는각각을표현하는요약이필요하다. 함수나기본블록의비교를위해서사용되는요약이너무성글게될경우중요하지만작은변화를감지할수없게된다. 예를들면 KB938827 2) 보안패치의경우구조적인정보가완전히일치하지만상수값은다르기때문에구조적인비교만을이용하는 BinDiff를통해서는패치후의실행파일에서어떤차이도발견할수없다. 4.2.2절에서이보안패치의비교에관해서자세히설명한다. 이런코드의차이점까지도감지해내기위해서우리는상수정보를각함수나기본블록의요약에포함하도록한다. 바이너리코드의구조적인정보를추출하기위해서우리는상용디스어셈블러인 IDAPro[9] 를사용한다. IDAPro는바이너리실행파일을디스어셈블하며, 어셈블리코드를함수단위로구분해주고, 함수간의호출관계및제어흐름그래프를생성한다. 이논문에서는 를프로그램으로, 를함수로, 를기본블록을나타내는기호로사용한다. 3.1 바이너리구조정보의요약 3.1.1 함수요약하기구조적인바이너리코드의차이점비교를위해서제일먼저함수정보를추출한다. 함수의정보를어떻게추출하느냐에따라매칭의정확도가결정된다. 매칭을빠르고효율적으로수행하기위해서함수를요약한정보를사용한다. 함수 에대하여, 함수의요약정보 는세정수의튜플 로나타나는데각각의정수는다음과같다. 2) http://www.microsoft.com/technet/security/bulletin/ms07-051.mspx
프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 455 그림 1 IDAPro로분석한한함수의제어흐름그래프 : 함수에포함된기본블록 (basic block) 의개수 : 함수에포함된기본블록간의연결선 (link) 의개수 : 함수에포함된함수호출 (function call) 의개수튜플내정수를가리키기위해서우리는 와같은표기법을사용한다. 예를들어 이라면, 이고 이다. 그림 1은 IDAPro 를이용해서구조가분석된함수의제어흐름그래프이다. 그림 1의바이너리코드는 5개의기본블록과 4개의블록간연결선, 그리고 2개의함수호출을가지고있다. 그림에나타난함수의 값은 (5,4,2) 이다. 3.1.2 기본블록요약하기함수단위매칭이이루어지면, 매칭이이루어진각함수쌍들의명령어비교를수행해야한다. 이때, 비교는명령어단위로이루어지는것이아니고, 함수내의기본블록단위로수행된다. 각함수의기본블록들은제어흐름그래프를따라서표현되므로, 각기본블록의정보를적절히추출하면블록단위매칭이이루어질수있다. 기본블록매칭을위해서우리는두가지요약정보를사용한다. 첫번째는블록내의함수호출개수와함수내에서블록의위치를포함하는요약정보이고, 두번째는블록내의명령어종류를나타내는요약정보이 다. 기본블록 에대해서, 첫번째요약정보는 으로나타내고세개의정수로된튜플 로정의된다. 각정수의의미는다음과같다. : 함수의시작지점 (entry point) 에서기본블록에도달할때까지의최단거리를이루는블록의개수 : 기본블록에서함수의종료지점 (exit point) 에도달할때까지의최단거리를이루는블록의개수 : 기본블록에서의함수호출개수 정도의블록정보만을가지고도많은매칭을이룰수있지만, 이것만가지고정확한기본블록매칭이이루어지지않는경우가있다. 그런경우블록내명령어들을좀더자세히살펴야하는데그것을위해서우리가사용하는것은두번째블록요약정보인핑거프린트이다. 핑거프린트정의를위해서우리는 SPP(Small Primes Product) 알고리즘을사용한다. 정의 3.1 모든명령어집합 ; 모든소수들의집합 ; 각명령어를단하나의유일한소수에매핑하는함수 가주어졌을때, 명령어를위한 SPP 값은다음과같다. 위에정의된 SPP 를바탕으로기본블록의핑거프린트가정의된다. 어떤블록 이 의명령어들로만구성되어있다면, 기본블록의핑거프린트는 이라표시되고, 다음과같이정의된다. SPP 를이용해서블록비교를위한핑거프린트로사용하는이유는블록내명령어비교를쉽고빠르게수행할수있기때문이다. 주어진두개의기본블록에대해서, 만일두값이일치한다면기본블록은같은명령어들로구성되어있음을알수있고, 매칭이완성되게된다. SPP 알고리즘의결과로나온핑거프린트값은소수들의곱으로이루어져있기때문에소인수분해를통해서언제든지원본명령어집합을구할수있다는장점이있고, 명령어순서에상관없이명령어조합만동일하면항상같은핑거프린트값을가진다. 또한, 여러명령어들로이루어진기본블록을숫자하나로요약해서표현할수있기때문에기본블록과기본블록사이의비교를숫자의비교로바꿔치기함으로, 비교속도가빠르다는장점이있다. 3.2 상수정보의요약구조적비교의단점은함수와기본블록을제어흐름정보만을이용해서요약하기때문에버퍼사이즈의변
456 정보과학회논문지 : 소프트웨어및응용제 35 권제 7 호 (2008.7) 화와같은상수정보에대한변화를추적할수없다는것이다. 따라서우리는구조적인비교방법에추가적으로상수정보를이용하여바이너리실행파일의차이점을찾을수있게하고있다. 상수정보는함수또는기본블록에나타나나는상수값의빈도 (frequency) 를이용하여나타낸다. 함수또는기본블록의상수정보를요약하기위해서우리는 라는표기법을사용한다. 여기서 는상수값, 는블록내에서 가나타나는개수이다. 예를들어어떤함수 에서상수 0 800 가 2번쓰이고상수 0 1000 가 1번쓰였다. {(0 800,2), (0 100,1)} 이된다. 3.3 바이너리비교알고리즘 3.3.1 함수의매칭알고리즘함수의기본매칭은제 3.1.1 장에서소개한함수로부터추출된함수요약정보를가지고시작한다. 함수의매칭은매핑함수 를정의함으로써이루어진다. 두함수 에대하여, 그들의요약인 와 의값이각프로그램내의함수요약들중에유일하게정의되고, 또 로일치한다면 3) 함수의매칭이이루어지게된다. 정의 3.2 주어진두프로그램이각각 개의함수로구성되어있고, 그함수들의집합이 과 이라할때, 두집합사이의매핑 는다음과같이정의된다. def = 이다. 만일운이좋아서한함수의요약정보가다른바이너리코드에서의함수요약정보와정확하게일치하고, 오직하나만존재한다면두함수사이에서매칭이일어난다. 그러나요약정보가같은함수들이여러개일경우가발생할수있다. 또한블록이나링크가추가되거나함수호출이추가되어요약정보가변경되었을경우에는요약정보값을통하여동일한함수를찾을수없는경우도발생한다. 함수가포함하고있는기본블록의개수가적을수록같은요약정보를가질가능성이많아진다. 예를들면, 다른함수호출을포함하지않는기본블록한개만으로이루어진함수일경우함수요약정보는기본블록한개로밖에표현될수없고, 이러한종류의함수들은 3) 는 인것과같다. 모두같은요약정보를가지게된다. 이런경우에는매칭대상함수를선택하는것은단순하게요약정보만으로해결할수없다. 이때는이미매칭이일어난함수를기준으로함수호출그래프에서의호출관계정보를이용하여매칭을시도하게된다. 이매칭에대해서는향상된매칭알고리즘이라는이름으로다음에더자세히설명이된다. 함수의기본매칭단계에서가장중요한것은가능한많은함수매칭을가능하게만들어서그후의알고리즘의복잡도 (complexity) 를줄이는것이다. 함수요약정보를사용한매칭기법이충분히많은매칭을성공시키지못한다면후의과정이어려워진다. 예를들어, 두개의바이너리프로그램 와 가있고, 각각은, 의함수들로구성되어있다고하자. 두프로그램의함수들이다음과같이서로같은함수요약값을가지고있다고하자. 두바이너리코드에서각각 4개의함수요약정보를추출하였고, 과 은각코드에서유일한요약값 (14,20,5) 를가지고, 과 도 (75,94,30) 의요약값을유일하게가지므로, 으로매칭을할수있다. 그러나 는모두 (5,6,5) 의값을가지므로이들간에는복수개의매칭이존재한다. 이경우, 어떤매칭이맞는것인지주어진매칭알고리즘으로는판단할수없기때문에, 좀더향상된매칭방법이필요하다. 좀더향상된함수매칭을위해서, 우리는함수들의요약값뿐만아니라, 함수들간의호출관계를고려한다. 어떤함수에대해서함수요약값이같은함수들이두개이상이더라도, 두함수가항상같은호출, 피호출관계를가질가능성은매우낮다. 따라서함수의호출관계를이용해서매칭이완성되지않은함수들끼리매칭을진행해주면더많은함수의매칭을찾을수있게된다. 다음은이미정의된기본매칭알고리즘을확장한향상된매칭알고리즘이다. 기본매칭알고리즘에서매칭함수 를미리계산해서제공한다고가정하면, 향상된매칭은아래와같이재귀적인매칭함수재정의를통해서완성된다.
프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 457 위의정의에서 는함수 의정의역, 의기호는함수호출관계를의미한다. 예를들어, 는함수 에서함수 로의호출이존재함을말한다. 향상된매칭알고리즘은이미기본매칭알고리즘으로매칭이끝난집합에서부터시작된다. 매칭이된기본블록에서향상된매칭알고리즘을반복하여적용하면서매칭집합을계속증가시킨다. 만일더이상추가적인매칭이발생하지않는다면향상된매칭알고리즘의수행이완료된상태이다. 향상된매칭알고리즘은함수의호출관계를함께보기때문에기존의매칭알고리즘이구별하지못했던함수를추가적으로매칭시킬수있다. 그러나함수의호출관계까지도일치하는경우이방법을통해서모든함수를구별해낼수는없다. 이런경우에는다음단계매칭인핑거프린트매칭과상수정보매칭을추가적으로이용하여구별해내야한다. 앞서소개된두바이너리프로그램 와 에대해서향상된매칭알고리즘을적용해보자. 이를위해서는우선함수호출관계를알아야한다. 각각의함수들에대해서다음과같은함수호출관계가있다고가정하면, 우리는다음과같이최종적으로매칭을완성할수있다. 3.3.2 기본블록의매칭알고리즘기본블록의매칭알고리즘은제 3.1.2 장에서소개된기본블록의요약값 와 를바탕으로이루어진다. 만일한블록의요약정보가다른바이너리프로그램내의한블록의요약값과일치하고, 그요약값이하나만존재한다면두블록사이에서매칭이완성된다. 정의 3.3 주어진두함수가각각 개의기본블록으로구성되어있고, 그블록들의집합이 과 이라할때, 두집합사이의매핑 는다음과같이정의된다. 4) 는 4) 쌍으로된정수들이서로다르다는것은다음과같이정의된다 : 는 과같다. 인것과같다. 함수매칭과의차이점은블록의매칭에서는두종류의요약값을바탕으로매칭을수행한다는점이다. 이정의에서우리는두블록이매칭된다함은두블록의 값이같거나혹은 값이같은것을말한다. 이렇게두가지정보를바탕으로매칭을수행하기때문에하나를이용하는것보다많은매칭을얻게된다. 하지만, 주어진블록매칭알고리즘으로도해결하지못하는경우가있다. 기본블록에대한요약값이유일하지않을경우가그렇다. 이럴때는이미매칭이일어난기본블록을기준으로제어흐름그래프에서의흐름관계정보를이용하여매칭을다시시도한다. 이같은블록매칭을위한향상된매칭알고리즘은함수의향상된매칭알고리즘과같다. 단지함수의경우함수호출관계를바탕으로추가매칭을수행하고, 블록의경우제어흐름그래프상의제어흐름관계를이용한다는차이점이있다. 다음은이미정의된블록의기본매칭에서확장한향상된매칭알고리즘이다. 기본매칭함수 를미리계산해서제공한다고가정하면, 향상된매칭은아래와같이재귀적인매칭함수재정의를통해서완성된다. 위의정의에서 의기호는제어흐름이있음을의미한다. 예를들어, 는기본블록 에서 로의제어흐름이존재함을말한다. 3.4 일치율계산 3.4.1 구조적일치율계산함수및기본블록의매칭이끝났을때완전히일치하는경우도있고, 향상된매칭알고리즘을적용한경우일부가일치하는경우가있다. 이정보를나타내기위해서일치율을계산한다. 일치율은코사인측정법 (cosine measure) 을사용한다. 함수의요약값은각각 라고하고각각을 3차원벡터로생각할때함수일치율은다음과같이정의한다.
458 정보과학회논문지 : 소프트웨어및응용제 35 권제 7 호 (2008.7) 그림 2 SCV 시스템구조도 구조적일치율 일치율은두벡터사이의코사인각도를의미하고두벡터의원소가전부양수이기때문에값의범위는 0.0 이상 1.0 이하이다. 3.4.2 상수일치율계산구조적매칭값이같더라도버퍼크기와같은상수값만변한경우구조적비교만을통해서는변화된값을찾을수가없다. 따라서이논문에서는상수일치율을계산함으로상향식바이너리실행파일비교방법의장점을함께포함하려고한다. 제 3.2 절에서정의된바와같이계산된두함수의상수요약값이다음과같이, 라고하자. 이때두함수에대한상수일치율은다음과같이정의한다. 상수일치율 = 단, 이다. 이식에서상수일치율은문서를비교할때에사용되는일종의다이스유사계수 (dice similarity measure) 이다. 분자는양함수에서의일치하는상수의총개수를의미하며, 분모는각함수의상수의개수의합을의미한다. 엄밀하게정의하면다음과같다. 4. 평가 4.1 구현바이너리실행파일비교분석도구 SCV의구조는그림 2와같다. SCV의전단부는기존의바이너리비교도구인다른그림이나 BinDiff와마찬가지로 IDAPro 디스어셈블러를사용하였다. IDAPro는바이너리실행파일을분석하여어셈블리코드, 함수정보, 기본블록정보등을생성한다. 이이정보를이용하기위해서우리는 IDA2SQLite 플러그인을구현하였다. IDA2SQLite 플러그인은 IDAPro에서생성된정보를 SQLite 5) DB 형태로저장한다. DB Extractor는 DB에저장된정보를이용하여제어흐름그래프를구성하고, 이그래프와어셈블리코드를분석하여함수요약, 기본블록요약, 상수값정보요약을수행한다. 바이너리코드매칭엔진은요약된정보를이용하여함수단위매칭, 기본블록단위매칭그리고상수값매칭을수행한다. 매칭결과는매칭된함수들과함수일치율, 함수내의매칭된블록들과블록일치율의테이블로저장된다. 시각화엔진은함수단위의비교테이블을일치율과함께나타내주고, 함수를선택했을때제어흐름그래프와기본블록의매치에대해나타내준다. 제어흐름그래프는 DOT 언어 [10] 로변환된후 GraphViz 라이브러리 [11] 를이용하여 SVG로변환된다 [12]. SVG는웹 5) http://www.sqlite.org/
프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 459 표 1 바이너리실행파일비교를위한패치샘플 KB931906 (MS 보안공지 MS07-046) KB938827 (MS 보안공지 MS07-051) 내용 GDI 의취약점으로인한원격코드실행문제점 Microsoft Agent의취약점으로인한원격코드실행문제점 비교대상 GDI32.dll agentdpv.dll 버전 5.1.2600.3099 / 5.1.2600.3159 2.0.0.3425 / 2.0.0.3426 크기 (KB) 275 / 276 52 / 52 그림 3 SCV 시스템을이용하여 GDI32.dll 을비교한실행화면 브라우저상에서볼수있는데, 어도비의 SVG Viewe r 6) 에의해표현된다. 4.2 실험구현된시스템을평가하기위하여 MS 윈도운영체제보안패치인 KB931906 7) 과 KB938827을사용하였다. 표 1은비교를위한대상에대해설명하고있다. 두보안패치를우리의도구인 SCV를통해분석하였고바이너리파일비교분석도구중잘알려진 Zynamics사의 BinDiff와비교한다. 4.2.1 KB931906 패치이취약점은이메일로첨부된이미지를열때디코딩 6) http://www.adobe.com/svg/ 7) http://www.microsoft.com/technet/security/bulletin/ms07-046.mspx 과정에서원격코드를실행할수있는권한을획득할수있도록한다. 그림 3은이취약점을보완한코드인 GetEvent 함수의변화를보여주고있다. 그림에표현된정보는함수매치테이블 (Matched Function Table), 블록매치테이블 (Matched Block Table), 명령어테이블 (Instruction Table) 그리고제어흐름그래프이다. 그림의왼편에있는다섯개의테이블은각각함수매치테이블, 매치가되지않은함수테이블 (Unmatched Function Table), 블록매치테이블, 매치가되지않은블록테이블 (Unmatched Block Table), 그리고명령어테이블이다. 그림의오른편은함수매치테이블에서선택된함수쌍의제어흐름그래프를비교해서보여준다. 제어흐름그래프에서코드가다른부분은다른색으로표현된다. 예를들어, 그림 3의 Get-
460 정보과학회논문지 : 소프트웨어및응용제 35 권제 7 호 (2008.7) 그림 4 SCV 시스템을이용하여 agentdpv.dll 를비교한실행화면 Event 함수의제어흐름그래프의경우, 두개의파란색블록이패치되어 9개의붉은색블록으로변경되었다. MS는이함수의취약점보완을위해서여러개의조건체크문을추가하였다. 각블록을구성하는명령어들은명령어테이블을통해서확인할수있는데, 어떤조건체크문이추가되었는지는이명령어테이블을참조하면알수있다. 4.2.2 KB938827 패치이취약점은 MS Agent의취약점으로인한원격코드가실행되는문제점이다. 이취약점의경우, 패치전후의파일크기가동일하며, 구조적인변경사항이전혀없고, 단지상수값만변경된것이특징이다. 따라서 BinDiff 는이패치를감지하지못하고, 변경사항이없는것으로판단한다. 그러나그림 4에서보는바와같이 SCV는상수값의변화를비교하기때문에, 이패치로부터네개의함수가변경된것을찾아낸다. 그림의왼쪽위에있는함수매치테이블에서 Structure 열의일치율은모두 1이지만, Value 열에서는네쌍의함수가 1 보다작은값을가진것을알수있다. 그림의오른쪽은특히네함수쌍중에서세번째함 수의제어흐름그래프를비교한것이다. 양쪽의제어흐름그래프에서상수값이변경된블록은육각형노드로표현되어있다. 5. 결론및향후연구본연구에서는보안패치와같은유사한형태의바이너리실행파일사이의비교방법을제안하고구현하였다. 우리는프로그램의구조정보를요약하고그정보를이용하여함수와기본블록사이의차이점을분석하여구조적인매칭을수행한다. 또한구조적인방법의한계를보완하기위하여상수값빈도수를이용하여요약하고비교하는방법을사용하였다. 이방법은기존에제안된프로그램구조정보의비교뿐아니라, 코드내의상수값의변화도추적할수있으므로, 기존의구조적비교방법을통하여찾아낼수없었던버퍼크기의변화와같은핵심적인정보까지찾아낼수있다. 또한, 명령어기반의비교방법의단점인명령어의재배치나레지스터할당의변화와같은불필요한정보를찾아내지않는다는장점이있다. 우리는제안된방법을기반으로 SCV라는바이너리코드비교분석도구를개발하였다.
프로그램의구조와상수값을이용하는바이너리실행파일의차이점분석 461 이도구를실제 MS 윈도우즈원격실행취약점에대한보안패치에적용하여개발된도구의실용성및기존연구방법과의차별성을증명하였다. 이방법은 IDAPro에전단부를의존하고있기때문에악성코드에서많이사용되고있는패킹 (packing) 이나난독화 (obfuscation)[13] 된코드에대해서는잘적용할수없다는단점이있다. 이를보완하기위하여언패커 (unpacker) 와역난독화 (deobfuscation) 도구가개발될필요가있다. 이런확장을통하여운영체제패치뿐아니라악성코드변종의분석에효과적으로사용될수있을것이다. 참고문헌 [1] Using SABRE BinDiff v1.6 for Malware analysis. http://www.zynamics.com/content/_documents/bindi ff_malware.pdf last accessed 2008.3.21. [2] Using SABRE BinDiff for Code theft detection. http://www.zynamics.com/products/code%20theft. pdf last accessed 2008.3.21. [3] Choi, S. and Park, H. and Lim, H and Han, T, "A Static Birthmark of Binary Executables Based on API Call Structure," LECTURE NOTES IN COM- PUTER SCIENCE, Vol.4846, p.2, 2007. [4] Sabin, T. 2004. Comparing binaries with graph isomorphisms. unpublished. [5] eeye Digital Security. eeye Diffing Suite. http:// research. eeye.com/html/tools/rt20060801-1.html last accessed 2008.3.21. [6] Flake, H. 2004. Structural comparison of executable objects. Proceedings of DIMVA 2004:Detection of Intrusions and Malware and Vulnerability Assessment. [ 7 ] Dullien, T. and Rolles, R. 2005. Graph-based comparison of executable objects. Symposium sur la securite des technologies de l information et des communications. [8] Zynamics BinDiff. 2007. http://www.zynamics.com/ index.php?page=bindiff last accessed 2008.3.21. [9] Hex-Rays. The IDA Pro disassembler and debugger. http://www.hex-rays.com/idapro/ last accessed 2008.3.21. [10] Koutsofios, E. and North, S.C. 1993. Drawing graphs with dot. AT&T Bell Laboratories, Murray Hill, NJ. [11] GraphViz. Graph vizualization package. AT&T Research. [12] Ferraiolo, J. and Jun, F. and Jackson, D. 2003. Scalable vector graphics (SVG) 1.1 specification. W3C Recommendation 14. [13] Linn, C. and Debray, S. 2003. Obfuscation of executable code to improve resistance to static analysis. 10th ACM Conference of Computer and Communications Security (CCS). 프로그램분석 및분석 박희완 1997 년동국대학교컴퓨터공학과학사 1999 년 KAIST 전산학과석사. 2004 년 ~2007 년삼성전자책임연구원. 1999 년 ~ 현재 KAIST 전산학과박사과정. 관심분야는프로그래밍언어및컴파일러, 소프트웨어공학 최석우 1998년 KAIST 전산학과학사. 2000년 KAIST 전자전산학과전산학전공석사 2000년~현재 KAIST 전자전산학과전산학전공박사과정. 관심분야는이진프로그램분석, 프로그램포렌식스, 컴파일러 서선애 1998년 KAIST 전산학과학사. 2000년 KAIST 전자전산학과전산학전공석사 2007년 KAIST 전자전산학과전산학전공박사. 2007년~현재 KAIST 전자전산학과박사후연구원. 관심분야는프로그래밍언어, 프로그램분석, 임베디드 한태숙 1976년서울대학교전자공학과학사. 1978 년 KAIST 전산학과석사. 1990년 Univ. of North Carolina at Chapel Hill 박사 1991년~현재한국과학기술원전자전산학과교수. 관심분야는프로그래밍언어론, 함수형언어, 임베디드시스템설계