情報保護學會誌第 16 卷第 5 號, 2006. 10 버퍼오버플로우검출을위한정적분석도구의현황과전망 김유일 *, 한환수 ** 요 약 버퍼오버플로우는 C 언어로작성한소프트웨어에보안취약점을남기는대표적인원인이다. 프로그램정적분석기법을통해버퍼오버플로우취약점을검출하는방법은버퍼오버플로우취약점을활용한다양한보안공격에대한근본적인해결책이될수있다. 본고에서는버퍼오버플로우취약점을검출할수있는몇가지정적분석도구들의특징과성능을살펴보고, 보다효율적이고정확한버퍼오버플로우정적분석도구를개발하기위한우리의연구성과를소개한다. Ⅰ. 서론버퍼오버플로우 (buffer overflow) 는프로그램이배열이나동적으로할당한메모리영역의경계를넘어데이터를읽거나쓰는상황을말한다. 버퍼의경계를지나데이터를기록하면다른변수의값에영향을미치거나프로그램의제어흐름을바꿀수있는데, 이는종종소프트웨어의심각한보안취약점으로남는다. 특히 C 언어로프로그램을작성하는경우에는버퍼의경계를검사하는코드를작성하는일이프로그래머의책임이므로프로그래머의실수로버퍼오버플로우취약점이나타나기쉽다. 버퍼오버플로우는 C 언어로작성된소프트웨어가보안에취약하게만드는대표적인원인이고, 알려진보안취약점의상당수가버퍼오버플로우와관련되어있다. 예를들어, 1998년의 Morris 웜은유닉스 fingerd 소프트웨어의버퍼오버플로우취약점을이용한것이었고, 2001년의 Code Red 바이러스는마이크로소프트윈도우의 IIS 소프트웨어의버퍼오버플로우취약점을이용한것이었다. D. Wagner 등의연구를인용하면 1988년부터 1998년까지 CERT Advisories 를통해발표된보안취약점의 50% 정도가버퍼오버플로우와관련된것이었고, 최근으로갈수록그비율이증가하는추세를보이고있다 5. 프로그램정적분석은프로그램수행중에발생하는 일을프로그램을실행하지않고파악하기위한체계적인방법이다. 정적분석도구가동적분석도구에비해우수한점을세가지로요약할수있다. 첫째, 정적분석도구는사용하기쉽다. 동적분석도구를이용하기위해서는대상프로그램을실행할수있는환경을만들고적절한입력데이터를제공해주어야하지만, 정적분석도구를사용하는경우에는대상프로그램의소스코드만있으면된다. 소스코드의일부만주어지더라도정적분석은가능하다. 둘째, 정적분석도구는프로그램의모든실행가능한경로를살펴볼수있다. 동적분석도구를사용한검사는프로그램테스트와유사하게존재하는취약점을발견하지못할가능성이있다. 셋째, 정적분석도구는대상프로그램의성능에영향을미치지않는다. 동적분석기법은실행중에오류검사를수행하도록대상프로그램을변형하는방법이므로대상프로그램의성능을현저하게저하시킬가능성이있다. 이처럼정적분석도구가다수의장점을가지고있으므로, 지금까지정적분석기법을통해 C 언어로작성한소프트웨어의버퍼오버플로우취약점을검출하기위한연구가활발하게수행되었다. 본고에서는지금까지개발된버퍼오버플로우정적분석도구들의성능과한계에대해살펴보고, 보다효율적이고정확한정적분석도구를개발하기위한연구방향을제안하려고한다. * KAIST 전자전산학과전산학전공 (youil.kim@arcs.kaist.ac.kr) ** KAIST 전자전산학과전산학전공 (hshan@cs.kaist.ac.kr)
46 버퍼오버플로우검출을위한정적분석도구의현황과전망 본문의전체적인구성은다음과같다. 2 장에서는버퍼오버플로우취약점과이를이용한공격방법에대해자세히살펴본다. 3 장에서는버퍼오버플로우취약점을검출하는정적분석도구를개발하기위한기반지식을설명한다. 4 장에서는지금까지개발된정적분석도구들을살펴본다. 5 장에서는더나은정적분석도구를개발하기위한우리의연구성과와향후계획을소개하고, 6 장에서결론을맺는다. Ⅱ. 버퍼오버플로우공격의실제이장에서는버퍼오버플로우취약점이있는예제프로그램들을사용하여버퍼오버플로우취약점을이용한공격이어떤원리로이루어지는지살펴본다. 여기서소개하는공격방법은지금까지개발된공격방법중일부에지나지않는다. 점차발전하는공격방법을차례로소개하면서, 버퍼오버플로우를근본적으로방지하지않는해결책은공격을어렵게만들지라도잠재적인보안취약점을완전히해결하는것이아니라는사실을강조하고싶다. [ 그림 1] 의예제프로그램은 1996년 Aleph One 이스택스매싱 (Stack Smashing) 이라는공격기법을소개하면서사용한것이다 2. argv[1] 에저장된문자열의길이가배열 buf의크기를넘을수있으므로, 프로그램의다섯째줄에서버퍼오버플로우가발생할수있다. 이프로그램에서버퍼오버플로우가특히문제가되는이유는기존의시스템에서는이러한유형의프로그램에버퍼오버플로우를발생시켜임의의코드를수행시킬수있었기때문이다. 대상프로그램이관리자권한으로수행되는경우라면, 악의적인사용자가관리자권한으로임의의작업을수행할수있다. 스택에할당한버퍼에데이터를기록하면서버퍼오버플로우를발생시켜스택에저장되어있는함수의리턴주소 (return address) 를변경하는것이스택스 1: int main(int argc, char **argv) 3: char buf[512]; 4: if (argc > 1) 5: strcpy(buf, argv[1]); 6: return 0; 7: } [ 그림 1] 스택스매싱취약점이있는프로그램 매싱공격의핵심이다. 이러한변경이가능한이유는스택에할당한버퍼에는주소가증가하는방향으로값을기록하는반면, 스택프레임은주소가감소하는방향으로쌓아나가기때문이다. 버퍼의경계를넘어서악의적인코드로스택을덮어쓰고현재수행중인함수의리턴주소를변경하면, 함수가작업을마치고호출지점으로돌아가는대신삽입한코드를수행하도록할수있다. 지금까지스택스매싱공격을방지하기위한다양한해결방안이제안되었다 1. 프로그램을실행할때마다스택의구조가무작위로결정되도록하는방법, 함수의지역변수와리턴주소사이에비밀값을삽입해두었다가이값이바뀌었는지의여부로버퍼오버플로우발생여부를판단하는방법, 함수의리턴주소를별도의자료구조에저장하는방법, 스택에저장한코드는실행할수없도록하는방법등이있다. 제안된방법들은스택스매싱공격을어렵게만들지만, 버퍼오버플로우를근본적으로방지하는방법은아니다. 따라서이러한방법들을무력화시키는개선된공격방법들도계속발표되고있다 4. [ 그림 2] 의예제프로그램은함수의리턴주소를변경하지못하는상황에서도임의의코드를수행하는버퍼오버플로우공격이가능하다는것을보여주는예이다. 배열 buf에대해버퍼오버플로우를발생시켜함수포인터 pf의값을바꿀수있다. 스택스매싱공격과비슷하게배열 buf에수행하려는코드를저장하고버퍼오버플로우를통해함수포인터 pf가버퍼에저장한코드의시작주소를가리키도록하면, 이후에함수포인터 pf를통한함수호출이발생할때프로그래머가의도한함수가호출되는대신버퍼에삽입한코드가수행된다. 이러한유형의공격은함수의리턴주소만을보호하기위해제안된기존의많은해결책들을우회할수있다. 1: int main(int argc, char **argv) 3: char buf[512]; 4: void (*pf)() = f; 5: strcpy(buf, argv[1]); 6: pf(); 7: return 0; 8: } [ 그림 2] 포인터변조취약점이있는프로그램
情報保護學會誌 (2006. 10) 47 이러한유형의공격방법은버퍼오버플로우취약점을활용하여얼마나다양한공격이가능한지를잘보여준다. 버퍼오버플로우를통해변경되는변수가함수포인터가아닌경우에도보안취약점이발생할수있다. 만일포인터변수의값과포인터변수에저장될값을한꺼번에변경할수있다면임의의메모리주소에 4 바이트데이터를기록할수있는데, 이는다양한공격을허용하는보안취약점이된다. [ 그림 3] 의예제프로그램은 M. Kaempf가힙오버플로우를활용한언링크 (unlink) 기술이라는공격기법을소개하면서사용한예제이다 3. 이프로그램은버퍼를스택이아닌힙에할당하고있다. 힙에할당한버퍼는버퍼오버플로우가발생하더라도함수의리턴주소가변경되거나지역변수의값이변경되지않으므로, 지금까지설명한공격방법으로부터는안전하다고말할수있다. 그러나버퍼오버플로우가발생할수있다는것은여전히잠재위험으로남는다. 실제로 [ 그림 3] 의프로그램을 GNU C 라이브러리 2.3.4 이전버전이설치된리눅스시스템에서컴파일하여실행하는경우에버퍼오버플로우를활용한공격이가능하다. GNU C 라이브러리의동적메모리관리함수들은 Doug Lea의동적메모리관리함수구현에기반을두고있는데, Doug Lea의초기구현은언링크기술이라고불리는공격기법에취약하다는것이알려져있다 3. 라이브러리는 free 함수를통해해제된메모리영역들을환형이중연결리스트로관리하는데, unlink는환형이중연결리스트에서하나의항목을제거하는매크로함수의이름이다. 언링크기술의원리를간단히설명하면다음과같다. [ 그림 3] 의 malloc 함수를통해버퍼를할당하면정확히지정한만큼의공간이할당되는것이아니고버퍼의경계에 malloc 관련함수들이사용하는약간 의정보가추가되는데, 그중에는버퍼가해제되었는지의여부를나타내는비트도포함된다. [ 그림 3] 의프로그램과같이연속적으로두개의버퍼를할당한경우는이비트를조작하여여섯째줄의첫번째 free 함수호출에서 unlink 매크로가수행되도록할수있다. 버퍼가해제되면사용자데이터를저장하던공간은환형이중연결리스트를구성하는포인터를저장하는공간으로재활용되는데, 이곳에저장되는데이터를조작하면 unlink 매크로가임의의메모리주소에 4 바이트데이터를기록하도록할수있다. 임의의주소에 4 바이트데이터를기록하는것을활용한대표적인공격방법은 GOT(Global Offset Table) 을변경하는것이다. 프로그램이사용하는공유라이브러리함수가적재된위치는 GOT에기록되어있고, 프로그램은공유라이브러리를호출할때 GOT 항목을참조하여공유라이브러리함수의시작주소로분기한다. [ 그림 3] 의프로그램에서여섯째줄의 free 함수를수행할때 free 함수의시작주소를저장하고있는 GOT 항목을버퍼에삽입한코드의시작주소로변경한다면, 일곱째줄에서는 free 함수가호출되는대신버퍼에삽입한코드가수행된다. 이처럼다양한버퍼오버플로우공격에효과적으로대응하기위해서는버퍼오버플로우자체를근본적으로방지하는해결책이필요하다. 최근버전의 GNU C 라이브러리는소스코드가수정되어더이상언링크기술을통한공격은가능하지않지만, 향후계속하여지금까지알려지지않은새로운공격방법이발견되고개발될것이다. 따라서프로그램에버퍼오버플로우가능성이남아있는한잠재적인보안위험이완전히사라진것은아니다. Ⅲ. 버퍼오버플로우검출을위한정적분석 1: int main(int argc, char **argv) 3: char *first = malloc(666); 4: char *second = malloc(12); 5: strcpy(first, argv[1]); 6: free(first); 7: free(second); 8: return 0; 9: } [ 그림 3] 힙오버플로우취약점이있는프로그램 정적분석기법은모든버퍼오버플로우취약점을검출하는효과적인해결책이될수있다. 이장에서는정적분석에대한기반지식을설명하고, 버퍼오버플로우취약점을검출하기위한정적분석도구를설계할때에고려할사항들을살펴본다. 이장에서설명하는내용들은지금까지개발된정적분석도구들의특성을이해하고더나은도구를개발하기위한기반이될것이다. 우리의목표는모든버퍼오버플로우가능성을검출하는안전한정적분석도구를개발하는것이다. 이장의내용은이러한목표를기준으로하여설명하는것
48 버퍼오버플로우검출을위한정적분석도구의현황과전망 으로, 이장의예제프로그램들은 3 장의예제프로그램들에비해다소복잡하고의도적인면이있다. 1. 정수변수분석모든버퍼오버플로우검출을위한정적분석은정수변수의값이나버퍼의크기, 문자열의길이등을분석할수있어야한다. 프로그램실행중에각정수변수에저장되는모든값을계산하는것은거의불가능하고또한불필요한작업이다. 정적분석을설계할때에는정수변수가실행중에가지는값에대한정보를효과적으로표현하기위한방법을선택해야한다. 정수변수의값을분석하기위한가장간단한방법으로구간 (Interval) 도메인 16 을사용한분석을들수있다. 구간도메인을사용하여분석하면정수변수가실행중에가지는값의최소값과최대값을알수있다. 버퍼오버플로우를검출하는데에는구간도메인이효과적으로사용될수있는데, 대체적으로최소값과최대값이버퍼오버플로우여부를판단하는데중요한역할을하기때문이다. [ 그림 4] 의예제프로그램은구간도메인을사용한분석으로충분한정보를얻지못하는예이다. 구간도메인을사용한분석은분석속도를향상시키기위한축지법 (widening) 및좁히기 (narrowing) 기법과함께사용된다. [ 그림 4] 의프로그램을이러한방법으로분석하면반복문안에서변수 i의최대값이 9라는정보를얻을수있지만변수 j의최대값은분석하지못한다. 지금까지제안된방법중에서가장정확도가높은값분석방법은다각형 (Polyhedra) 도메인 17 을이용한분석방법이다. 다각형도메인을이용한분석은정수변수들사이의모든선형관계식을이끌어낸다. 예를들어 [ 그림 4] 의프로그램을다각형도메인을이 1: void figure4(void) 3: char buf[10]; 4: int i, j = 0; 5: for (i = 0; i < 10; i++) { 6: buf[j] = 0; 7: j++; 8: } 9: } [ 그림 4] 변수사이의관계가중요한예 용하여분석하면반복문안에서변수 i와변수 j가항상동일한값을가진다는정보를함께얻게된다. 이정보와변수 i의최대값이 9라는정보를종합하면변수 j의최대값도 9라는것을알수있다. 그러나다각형도메인은복잡도가지나치게높아큰프로그램에적용하기어렵다는단점이있다. A. Mine는구간도메인과다각형도메인사이의정확도및복잡도를가지는분석방법들을제안했는데 18, [ 그림 4] 의프로그램은 A. Mine가제안한분석방법으로도충분한분석결과를얻을수있다. 2. 포인터분석 C 언어로작성한프로그램을정확하게분석하기위해서는포인터연산을정확하게다루는것이필수적이다. C 언어로작성한프로그램은포인터변수를정수변수나함수의별명 (alias) 으로사용하기도하고, 포인터를통해버퍼에접근하기도한다. 포인터분석은각포인터변수가가리키는대상의집합을구하는문제인데, 정확하게분석하려면계산의시간복잡도가 O(n 3 ) 에달한다. B. Steensgaard 는기존의포인터분석방법으로소스코드가 10 만줄이상인대규모소프트웨어를한꺼번에분석하기는어렵다는것을지적하면서, 정확도가다소떨어지지만거의선형시간복잡도를보이는포인터분석방법을제안하였다 15. 버퍼오버플로우검출을위해서는포인터가버퍼를가리키는경우버퍼의크기와오프셋까지분석해야한다. [ 그림 5] 의프로그램은정확한포인터분석이필요한대상프로그램의예이다. 포인터변수 p 가크기가 10 인배열 buf 의다섯째항목을가리킨다는것과포인터변수 q 가정수변수 i 를가리킨다는것을파악해야이프로그램이버퍼오버플로우를발생시키는원인을올바르게분석할수있다. 1: void figure5(void) 3: char buf[10], *p; 4: int i, *q = &i; 5: p = &buf[5]; 6: i = 5; 7: p[*q] = 0; 8: } [ 그림 5] 포인터분석이중요한예
情報保護學會誌 (2006. 10) 49 3. 제어흐름을고려하는분석 4. 함수호출문맥을고려하는분석 제어흐름을고려하는 (flow-sensitive) 분석기법은프로그램의제어흐름이도달하는각지점에대해분석정보를구분하여유지한다. 예를들어, [ 그림 6] 의프로그램을제어흐름을고려하는분석기법으로분석하면, 변수 i가여섯째줄에서는 0과 9 사이의값을가지고일곱째줄에서는 10이된다는비교적자세한분석결과를얻을수있다. 제어흐름을무시하는 (flow-insensitive) 분석기법은프로그램에대한전체적인사실을빠르게파악하기위해서사용된다. [ 그림 6] 의프로그램을제어흐름을분석기법으로분석하면, 프로그램수행중에변수 i가 0과 10 사이의값을가진다는덜자세한분석결과를얻는다. 결과적으로 [ 그림 6] 의프로그램에대해제어흐름을고려하는분석기법을사용하면일곱째줄에서버퍼오버플로우가발생한다는것을정확하게알수있지만, 제어흐름을무시하는분석기법을사용하면여섯째줄에대해서도버퍼오버플로우가발생한다는잘못된오류메시지를출력하게된다. 제어흐름을무시하는분석은이처럼부정확한분석결과를제공하지만, 반면효율적으로수행할수있는여지가많다. 실제로 B. Steensgaard가제안한포인터분석기법은제어흐름을무시하는분석기법에속한다. B. Steensgaard의포인터분석이유용한이유는대부분의포인터변수가단순한형태로사용되는프로그램에서는제어흐름을무시하는분석기법을사용해도정확도를크게잃지않기때문이다. 예를들어, 프로그램에서변수가단한번나타나거나값이변하지않는다면, 제어흐름을무시하는분석기법을사용해도정확도를잃지않는다. 1: void figure6(void) 3: char buf[10]; 4: int i; 5: for (i = 0; i < 10; i++) 6: buf[i] = '0' + i; 7: buf[i] = '\0'; 8: } [ 그림 6] 제어흐름을고려한분석이중요한예 함수호출문맥을고려하는 (context-sensitive) 분석기법이란하나의함수가서로다른인자를이용해여러번호출되는경우에각호출문맥을구분할수있는분석기법을말한다. [ 그림 7] 의프로그램은여덟째줄의함수호출은버퍼오버플로우를발생시키지않고, 아홉째줄의함수호출은버퍼오버플로우를발생시키는프로그램이다. 함수호출문맥을고려하는분석기법을이용하여이프로그램을분석하면아홉째줄의함수호출이버퍼오버플로우를발생시킨다는것을정확히알수있다. 함수호출문맥을무시하는 (context-insensitive) 분석기법을사용하면여덟째줄과아홉째줄의함수호출을한꺼번에분석하므로여덟째줄의함수호출도버퍼오버플로우를발생시킨다는잘못된경고메시지를출력하게된다. 함수호출문맥을고려하는분석기법도여러가지방법이있다. 일반적으로는함수호출경로가서로다른함수호출을구분하는방법과인자가서로다른함수호출을구분하는방법으로분류할수있다. 실제적으로는프로그램소스코드상에서구분되는함수호출들간에만구분하는방법이간단하기때문에많이사용된다. 이방법은함수호출경로로함수호출을구분하는방법에속한다. 5. 정적분석의안전성 (Soundness) 안전한정적분석기법을사용해야만모든가능한오류를발견한다는정적분석의최대장점을살릴수 1: void figure7(char *src) 3: char buf[5]; 4: strcpy(buf, src); 5: } 6: int main() 7: { 8: figure7("abc"); 9: figure7("abcde"); 10: return 0; 11: } [ 그림 7] 함수호출문맥을고려한분석이중요한예
50 버퍼오버플로우검출을위한정적분석도구의현황과전망 있다. 정적분석이안전하다는것은정적분석을통해대상프로그램에버퍼오버플로우취약점이존재하지않는다는결론을얻었다면, 실제로대상프로그램을어떠한방법으로수행하더라도버퍼오버플로우가발생하지않는다는것이보장된다는의미이다. 정적분석을통해프로그램실행중에발생하는일을완전하게파악하는것이불가능하다는것은수학적으로증명된사실이다. 정적분석도구는대상프로그램의실행중에발생하는일을대략적으로파악할수밖에없으며, 그결과로오류를발견하지못하거나오류가아닌부분을오류라고판단하는경우가발생한다. 안전한정적분석도구는오류를놓치지않도록설계된분석기법을사용하므로오류가아닌데도오류라고판단하는경우만발생하는데, 본고에서는이런경우를잘못된경고메시지 (false alarm) 라고부른다. 실제적으로는안전하지않은정적분석기법이많이사용되는두가지이유가있다. 하나는안전한정적분석기법이다수의잘못된경고메시지를출력한다는것이고, 다른하나는안전한정적분석기법을충분히효율적으로수행하기위한연구성과가부족하다는것이다. 6. 종합 : 요약해석 (Abstract Interpretation) 다양한정적분석기법들을살펴보고버퍼오버플로우검출이라는목적에효과적일것으로판단되는기법들을선택하여정적분석을설계한다. 안전한정적분석을체계적으로설계하는좋은방법중하나는요약해석프레임워크 16 에맞추어설계하는것이다. 요약해석프레임워크의요구조건에맞추어설계한정적분석기법은정적분석의올바름이자동으로증명된다는장점이있다. 다음장에서소개할 PolySpace C Verifier 와 Airac 은모두요약해석을기반으로한안전한정적분석도구에속한다. 다만요약해석에기반을두고개발된정적분석도구는아직충분한성능을보여주지못하고있다. 그러나요약해석에기반을둔정적분석도구를실제로구현하면서얻은연구결과가국외학회에종종발표되고있는것으로미루어보면, 최근에는요약해석에기반을둔정적분석도구를효율적으로구현하기위한연구가활발히진행되고있는것으로판단된다. Ⅳ. 정적분석도구현황 인자의길이를검사하지않는 strcpy 등의함수를사용하는것이버퍼오버플로우취약점의원인이된다 는점에착안하여, 구문분석을통해보안에취약한함수의사용여부를검사하는도구들이있다. 이러한유형에속하는분석도구로는 ITS4, FlawFinder, RATS 등이있다. 이러한분석도구들도초보적인단계의정적분석도구라고말할수있지만, 프로그램의의미를고려하지않으므로, 본논문에서다루려는정적분석도구와는거리가있다. M. Zitser 등은이미알려진버퍼오버플로우보안취약점들을단순화한테스트케이스를설계하고, 이를이용해 BOON, Splint, ARCHER, Poly- Space C Verifier 등의정적분석도구들을비교평가하는연구를수행했다 8. 본고에서는이들정적분석도구들의단순한성능비교를넘어각각의정적분석도구가선택한분석기법을자세히살펴보고, 각분석기법이가지는장점과더불어근본적인한계점에대해생각해보려고한다. 1. BOON 5 BOON 은체계적인프로그램정적분석기법을활용하여버퍼오버플로우취약점을분석하려고시도한최초의정적분석도구라고할수있다. 프로그램정적분석기법을사용함으로써단순히 strcpy 함수가사용된것을문제삼지않고, 실제로대상버퍼의크기가복사하려는문자열의길이보다작은경우만을지적할수있다. BOON 은라이브러리함수에의해발생하는버퍼오버플로우취약점을보다정확하게검출하려는시도인것으로생각된다. 구간도메인을사용하여버퍼의크기나문자열의길이등정수값을분석하고, 포인터의사용은무시한다. 제어흐름및함수호출문맥을무시하는분석기법을이용하여분석의효율을높이려고시도했다. BOON 은 FlawFinder 류의분석도구에비해우수하지만, 정적분석도구로서는초보적인수준이다. 특히포인터를분석하지않는다는점에서존재하는취약점을놓칠가능성이높다. 논문의실험결과에따르면펜티엄 3 PC 를사용하여소스코드가 3 만줄정도인 Sendmail 8.9.3 버전을 15 분안에분석할수있었다. 분석결과로 44 개의경고메시지가출력되었는데, 경고메시지를분석하여새로운버퍼오버플로우오류를발견할수있었다고발표했다. 2. Splint 6 Splint 는가벼운 (light-weight) 정적분석이라고
情報保護學會誌 (2006. 10) 51 부르는정적분석기법을사용하여버퍼오버플로우취약점을검출하려고시도한것이다. 프로그램의의미를이해하고제약식을이끌어내기도하지만, 기본적으로는사용자가특별한형식의주석 (annotation) 을작성하여많은정보를제공해줄것을전제로하여개발된분석도구이다. Splint와같이특별한주석을요구하는정적분석도구들은정적분석에지식이없는사용자가사용하기는어렵다는단점이있다. 물론주석을작성하지않아도기본적인분석을수행할수있지만, 다수의잘못된경고메시지가출력되므로분석결과가유용하다고말하기어렵다. Splint는안전하지않은분석기법을사용한다. 충분한주석을작성하여대상프로그램에버퍼오버플로우취약점이없다는분석결과를얻었다하더라도실행중에버퍼오버플로우가발생하지않는다는것을보장하지못한다. Splint를사용하여 [ 그림 7] 의프로그램을분석하면넷째줄에서버퍼오버플로우가발생할수있다는경고메시지를출력한다. Splint는내부적으로 strcpy 함수를안전하게호출하기위해만족시켜야하는제약식을알고있는데, 버퍼 buf의크기가문자열 src의길이보다커야한다는것이다. 이제약식과첫째줄에서얻은버퍼 buf의크기가 5라는정보를결합하여, src의길이가 4 이하여야한다는제약식을이끌어낸다. Splint는주어진프로그램에서문자열 src 의길이가 4 이하라는정보를이끌어낼수없기에경고메시지를출력하는것이다. Splint가출력하는경고메시지는아홉째줄의함수호출과는아무런관련이없다. Splint는각함수를별도로분석하며, 함수호출을분석할때에는사용자가작성한주석에만의존하기때문이다. strcpy와같은라이브러리함수를처리하는것은제작자가미리작성해둔주석에의한것이다. 실제로아홉째줄의함수호출이없어도동일한경고메시지가출력되는데, 함수의인자가길이 4 이하의문자열이어야한다는주석을작성하면보다정확한분석을수행할수있다. 3. ARCHER 7 하게찾아내는것에중점을두어개발된도구라고판단된다. M. Zitser 등의실험에서 ARCHER는 BOON, Splint, PolySpace C Verifier와비교할때오류를발견하지못하는경우가가장많은것으로나타났다 8. ARCHER를통해 [ 그림 7] 의프로그램을분석하면아홉째줄의함수호출이문제가된다는것을정확하게지적할수있다. ARCHER의분석방식은함수 figure7을분석하여인자문자열 src의길이가 5 이상인경우버퍼오버플로우가발생한다는조건을이끌어내고, 함수 figure7을호출할때마다버퍼오버플로우발생조건을만족하는지확인하는방식이다. ARCHER는분석속도와잘못된경고메시지의비율면에서매우우수한성능을보여주고있다. 소스코드의크기가 160만줄에달하는리눅스 2.5.53 버전을 Xeon 2.8 GHz CPU와 512 MB RAM을탑재한시스템에서 4시간정도에분석하여 118개의실제오류를찾았는데, 잘못된경고메시지는 39개에불과했다는실험결과가발표되었다. 4. Coverity 11 미국의 Coverity 사는프랑스의 PolySpace Technologies 사와더불어정적분석기술을상용화시킨대표적인기업이다. Coverity 사의정적분석도구는 Stanford 대학의 D. Engler 등이개발한메타컴파일 (metacompilation) 기법과 xgcc 9 에기반을둔것으로알려져있다. 위에서설명한정적분석도구들과비슷하게안전성을희생하고복잡도가높지않은분석기법을사용하여개발된정적분석도구인데, 상용화된제품이니만큼유사한정적분석도구들중에서는가장성능이우수한것으로보인다. Coverity 사에서공개한보고서에따르면소스코드의크기가 550만줄에달하는리눅스 2.6.5 버전을분석할수있었다. 버퍼오버플로우와관련된경고메시지는총 124개였는데, 이들을분석하여 15개의버퍼오버플로우관련오류를발견했다고발표했다. ARCHER는 Splint와비슷하게복잡도가높지않은분석기법을사용하여유용한정적분석도구를개발하려는시도로볼수있다. 사용자가주석을작성할필요가없다는점과함수호출을자동으로분석한다는점에서 Splint와차별화된다. ARCHER는비교적단순한버퍼오버플로우취약점을가능한빠르고정확 5. PolySpace C Verifier 12 안전한정적분석도구로는프랑스 PolySpace Technologies 사의 PolySpace C Verifier가대표적이다. PolySpace C Verifier는요약해석에기반을둔정적분석기법을사용하여개발한정적분석도
52 버퍼오버플로우검출을위한정적분석도구의현황과전망 구로알려져있다. 요약해석에기반을둔안전한정적분석도구들은아직분석속도면에서만족할만한성능을보여주지못하고있다. M. Zitser 등은 PolySpace C Verifier를사용하여소스코드가 15만줄정도인 Sendmail 8.12.4 버전을분석하려고시도했는데, 4 일동안분석을수행해도결과를얻을수없었다고발표했다 8. 속도문제를제외하면 M. Zitser 등의실험에서도 PolySpace C Verifier가가장높은정확도를보여주는정적분석도구로판명되었다. 요약해석에기반을둔안전한정적분석도구가실제로유용하게사용되기위해서분석속도는필수적으로개선되어야할주요문제점이다. 6. Airac5 13 서울대학교의정영범등은요약해석에기반을둔정적분석도구인 Airac을개발했다 10. 최근에는 Airac을더욱개선한버전인 Airac5를개발했고, 실험결과를홈페이지를통해공개하고있다. Airac은버퍼오버플로우취약점검출에특화된정적분석도구라는점에서 PolySpace C Verifier와차별화된다. 통계적인방법으로잘못된경고메시지를걸러내는기법을사용한다는것도특징적이다. 홈페이지를통해공개되어있는실험결과에따르면 3.2 GHz CPU와 4 GB RAM을탑재한펜티엄4 PC를사용하여소스코드의크기가 3만라인정도인 GNU bison 1.875 버전을 6 시간이내에분석할수있다. 다섯개의 GNU S/W 실험결과를종합하면 Airac5는소스코드 374줄당 1개의비율로잘못된경고메시지를출력하고있는데, 안전한정적분석도구로서는비교적높은정확도를보여주고있다고판단된다. M. Zitser 등은 PolySpace C Verifier가 12줄당 1개의잘못된경고메시지를출력할것으로추정하였고, Splint가 46줄당 1개의잘못된경고메시지를출력할것으로추정하였다 8. Ⅴ. 우리의연구성과우리는모든버퍼오버플로우취약점을검출할수있는정확하고효율적인정적분석도구를개발하려는목표를가지고있다. 4 장에서살펴보았듯이기존의안전한정적분석도구들은아직만족할만한성능을보여주지못하고있다. 이장에서는우리가개발하고 [ 그림 8] Raccoon의구조있는버퍼오버플로우정적분석도구인 Raccoon을소개하려고한다. [ 그림 8] 과같은구조로정적분석도구를구현함으로써기존의한계를어느정도극복할수있을것으로기대하고있다. 버퍼오버플로우검출을위해분석해야하는정보들을몇가지로분류하고, [ 그림 8] 과같이여러종류의분석을완전히독립된단계로수행하는구조의정적분석도구를설계했다. 정적분석도구를이와같은구조로설계한이유는다음과같은세가지이점을기대하기때문이다. 첫째, 각단계에서서로다른정확도및속도를가진분석기법을사용할수있는유연성이있다. 둘째, 보다정확한결과를위해추가적인정보를분석할필요가있다면새로운단계를추가하는것으로목적을이룰수있다. 셋째, 분석과정에서메모리의최대사용량 (memory peak) 을줄일수있다. 대규모소프트웨어를분석하는경우에는메모리최대사용량이분석도구의성능을좌우하는중요한기준이될수있다. 각단계에서수행되는작업을간단히설명하면다음과같다. 1 단계는구문분석및타입분석단계이다. 대상프로그램을구문분석하고각함수별로제어흐름그래프를생성한다. 2 단계는 Steensgaard 스타일의빠른포인터분석을이용하여함수포인터와정수변수를가리키는포인터를분석한다. 이러한유형의포인터변수들은프로그램전체에서단순하게사용되는경향이있으므로, 정확도를다소희생한분석기법을사용해도전체적으로는정확도를크게잃지않으리라고기대했다. 3 단계는구간도메인을사용한요약해석으로정수변수들의값을분석한다. 3 단계는제어흐름을고려하고, 함수호출문맥을고려하는비교적정확한분석기법을사용한다. 4 단계는독자적으로설계한도메인을사용한요약해석으로버퍼를가리키는포인터들의상세정보를분석한다. 대상버퍼의크기및포인터의오프셋정보를분석하는것이다. 4 단계분석은부분적으로 3 단계분석결과를이용하여진행된다. 5 단계취약점분석단계는 4 단계까지의분석결과를이용하여프로그램의각부분의버퍼오버플로우가능성을진단하
情報保護學會誌 (2006. 10) 53 [ 표 1] GNU 소프트웨어를사용한실험결과 소프트웨어 크기 포인터분석 요약해석 경고메시지 tar 1.13 14879 0.39s 105.25s 99 bison 1.875 29903 1.51s 201.32s 109 sed 4.08 7464 0.21s 8.75s 5 gzip 1.2.4a 11298 0.23s 47.51s 323 grep 2.5.1 14879 0.37s 76.23s 122 고, 경고메시지를출력한다. Raccoon은 CIL 프레임워크 11 를활용하여 OCaml 언어로구현하였다. CIL 프레임워크는 C 언어프로그램을단순한중간언어로변환해주며구문트리수준에서프로그램을다루기위한다양한함수를제공하므로 C 언어프로그램을분석하는도구를개발하기에적합한환경이다. [ 표 1] 은 Raccoon을이용해몇가지 GNU 소프트웨어들을분석한결과이다. 크기는 CIL을이용해대상소프트웨어를하나의파일로병합한후에측정한소스코드의줄수이다. 2 단계분석에소요되는시간을셋째칸에나타냈고, 3 단계와 4 단계분석에소요되는시간을더하여넷째칸에나타냈다. 실험에는 Xeon 3.2 GHz CPU와 4.0 GB RAM을탑재한리눅스시스템을이용했다. 속도면에서만보면 Raccoon은소스코드의크기가 3만줄에달하는프로그램을 4 분이내에분석할수있었지만, 다수의잘못된경고메시지를출력하고있으므로정확도면에서는아직만족할만한결과를보여주지못하고있다. Raccoon이정확한분석을수행하지못하는대표적인원인중하나는 C 표준라이브러리함수들을모델링하지않았다는것이다. 지금까지는주로분석의속도향상에중점을두어개발을진행했는데, 분석의효율성을유지하면서정확도를개선하기위한연구를계속수행할계획이다. 실험결과는제안하는구조를통해안전한정적분석도구의분석속도를크게향상시킬수있을것이라는추측을뒷받침하고있다. 우리는분석의속도를더욱개선하는것이가능할것으로보고있다. 2 단계분석을수행할때는포인터연산만수행하는함수를빠르게건너뛰는등각단계의분석을보다특화시키는방법과프로그램의모듈성을활용하여분석의범위를줄이는방법으로분석의효율성을더욱개선할것이다. Raccoon이잘못된경고메시지를걸러내기위해취하는방식은분석의정확도를조절하여분석을반복하는것이다. [ 그림 8] 의설계에는이러한의도가반영되 어있지만, 아직구현이완료되지는않았다. 5 단계는각경고메시지의신뢰도를평가하고, 잘못된경고메시지로추측되는경우에는경고메시지와관련된부분을보다정확한분석기법으로분석하도록각분석단계를조절한다. 경고메시지와직접적으로관련되지않은부분에대해서는이전의분석결과를재사용하여추가분석에소요되는시간을최소화할수있을것이다. Ⅵ. 결론본고에서는버퍼오버플로우취약점의유형과다양한공격방법에대해소개하고, 버퍼오버플로우취약점을검출하기위한정적분석도구들의현황을살펴보았다. 다수의정적분석도구들이안전하지않은분석기법을사용하여일부버퍼오버플로우취약점을빠르게찾아내는것에중점을두고있으며, 안전한정적분석도구들은충분히만족할만한성능을보여주지못하고있다는것을알게되었다. 우리는안전한정적분석기법을사용하는효율적인버퍼오버플로우정적분석기를개발하기위한연구를수행하고있는데, 본고에서지금까지의연구성과를일부소개하였다. 본고에서제안하는방법들을통해정확하면서도효율적인정적분석도구를개발할수있을것으로기대하고있다. 본고에서설명한내용들은소프트웨어보안분야의연구자들에게프로그램정적분석분야의연구성과를소개하는기회가될것이고, 동시에프로그램정적분석분야의연구자들에게향후연구방향을제시하는참고자료가될수있을것이다. 참고문헌 [1] R. Secord, Secure Coding in C and C++, Addison Wesley, 2006. [2] Aleph One, "Smashing the Stack for Fun and Profit", Phrack, 49, 1996. [3] M. Kaempf, "Vudo - An object superstitiously believed to embody magical powers", Phrack 57, 2001. [4] J. Pincus, B. Baker, "Beyond Stack Smashing: Recent Advances in Exploiting Buffer Overruns", IEEE Security & Privacy, 2(4), pp. 20-27, Jul/Aug 2004.
54 버퍼오버플로우검출을위한정적분석도구의현황과전망 [5] D. Wagner, J. Foster, E. Brewer, A. Aiken, "A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities", NDSS'00. [6] D. Larochelle, D. Evans, "Statically Detecting Likely Buffer Overflow Vulnerabilities", USENIX Security 2001. [7] Y. Xie, A. Chou, D. Engler, "ARCHER: Using Symbolic, Path-sensitive Analysis to Detect Memory Access Errors", ESEC/FSE'03. [8] M. Zitser, R. Lippmann, T. Leek, "Testing Static Analysis Tools using Exploitable Buffer Overflows from Open Source Code", SIGSOFT'04/FSE-12. [9] S. Hallem, B. Chelf, Y. Xie, D. Engler, "A System and Language for Building System-Specific, Static Analyses", PLDI'02. [10] Y. Jung, J. Kim, J. Shin, K. Yi, "Taming False Alarms from a Domain-Unaware C Analyzer by a Bayesian Statistical Post Analysis", SAS'05. [11] http://www.coverity.com/ [12] http://www.polyspace.com/ [13] http://ropas.snu.ac.kr/2005/airac5/ [14] http://manju.cs.berkeley.edu/cil/ [15] B. Steensgaard, "Points-to Analysis in Almost Linear Time", PLDI'96. [16] P. Cousot, R. Cousot. "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints", POPL'77. [17] P. Cousot, R. Cousot, "Automatic Discovery of Linear Restraints Among Variables of a Program", POPL'78. [18] A. Mine, "Weakly Relational Abstract Domains: Theory and Applications", NSAD'05. < 著者紹介 > 김유일 (Youil Kim) 2001년 : KAIST 전자전산학과 전산학전공학사 2003년 : KAIST 전자전산학과 전산학전공석사 2003년~ 현재 : KAIST 전자전산 학과전산학전공박사과정관심분야 : 프로그램정적분석 한환수 (Hwansoo Han) 정회원 1993년 : 서울대학교컴퓨터공학과 학사 1995년 : 서울대학교컴퓨터공학과 석사 2001년 : Ph.D., Computer Science, University of Maryland 2001년 ~2003년 : Sr. Engineer, Intel Architecture Group, Intel 2003년~ 현재 : KAIST 전자전산학과전산학전공조교수 관심분야 : 프로그램정적분석, 임베디드시스템