signature 와어플리케이션 signature 의포맷을재정의하고, LCS 의 modification 에필요한제약사항들과 modified LCS 알고리즘을실제트래픽에적용하는방법을설명한다. 또한 4 장에서는 modified LCS 알고리즘을기반으로실제 signature

Transcription

1 자동화된어플리케이션레벨의 Signature 생성 박병철 1, 원영준 1, 김명섭 2, 홍원기 1 1 포항공과대학교컴퓨터공학과 2 고려대학교컴퓨터공학과 1 {fates, yjwon, jwkhong}@postech.ac.kr, 2 tmskim@korea.ac.kr 요 약 어플리케이션트래픽의정확한분류는네트워크 monitoring 과분석측면에서매우중요한부분을차지하고있다. 가장전통적인트래픽분류방법은미리정의된 well-known 포트와비교하는방법이사용되었지만이러한분석방법은높은정확도를보장하지못하고있다. 대체방법인어플리케이션레벨의 signature 비교방법은좀더높은정확도를제공하지만신뢰도가높은 signature 를찾기위해트래픽에대한 exhaustive search 가요구된다. 사전에어플리케이션의프로토콜에대한정보를알고있다면높은정확도의 signature 를보장할수있지만, 대부분의인터넷어플리케이션프로토콜정보는공개가되고있지않다. 본논문에서는어플리케이션프로토콜에대한사전조사없이선행적인프로토콜분석을통한 signature 생성과동일한정확도의어플리케이션레벨의 signature 를생성할수있는효과적인방법을제시한다. 1. 서론 어플리케이션트래픽분류는네트워크의운용관리, 트래픽엔지니어링, 과금, 그리고 QoS 관리등을위한정보인현재네트워크상태를제공하기위한중요한연구분야이다. 최근들어웹 ( 인터넷 ) storage 와 Peer-to-Peer (P2P) 파일공유어플리케이션들의종류가급격하게증가하였고, 이들이발생시키는트래픽의량이전체인터넷트래픽에서매우많은부분을차지하고있다 [2]. 특히최신의 P2P 어플리케이션들은동적인 port 할당이나 relay 노드를사용하는것과같은방법들을통해 detection 과 filtering 을피하고있다. 이러한인터넷트래픽의변화로인해 port 기반의트래픽분류와같은초기의단순한분류방법들은점차적으로일정수준이상의정확도를보장하지못하게되었다. Moore 의연구 [4] 에서도 port 기반의분류방법은 50~70% 의정확도를넘지못한다고주장하고있다. 기존의분류방법들 [5] 의문제점들을해결하기위한새로운해결책으로 signature 기반의분류방법이제안되었다. 어플리케이션 signature 는어플리케이션의종류를구분지을수있는, packet payload 데이터상의고정적으로나타나는 string 이나 hex 값의패턴을의미한다. 이러한접근방법은 Internet 웜 community ( 예 : Intrusion Detection Systems) 에서먼저사용되었던방법이지만목표하는바가비정상트래픽만을 detect 하는것으로트래픽을각각의종류별로분류하는것과는차이가있다. 어플리케이션 signature 는네트워크관리자나보안전문가들에의 해 manual 한방법으로만들어져왔다. 이러한방법은공통적으로나타나는패턴을추출하기위해프로토콜에대한조사나 packet payload 에대한정밀한검사가선행되어야만한다. 따라서새로운어플리케이션이등장하였을때 signature 를만들기위해서는상대적으로많은시간이소요된다. 이러한문제점들을해결하기위해서는 signature 를생성하는체계적인시스템이필요하다. 본논문에서는선행적인프로토콜조사없이자동적으로어플리케이션 signature 를생성하는새로운방법으로구현된 semi-automatic signature 생성시스템을소개하고이시스템의효용성을검증한다. 그리고 semi-automatic 시스템의문제점인사용자의개입없이 fully-automatic 한방법으로 signature 를생성할수있는시스템의가능성을제시한다. 웜 signature 의자동생성에관한몇몇의연구들이존재하지만웜과정상적인인터넷트래픽의차이점들때문에이들연구에서사용한 sliding window 알고리즘 [9] 을적용하는데에는어려움이따른다. 따라서본연구에서는 sliding windows 알고리즘과전혀다르고 linear time 에동작할수있는 Longest Common Substring (LCS) 알고리즘 [13] 을수정하여적용하였다. 최근에조사한바로는웜과같은비정상트래픽이아닌일반적인인터넷트래픽에대해자동적으로 signature 를생성하는것에관한연구시도는없었다. 본논문의구성은다음과같다. 2 장에서는관련연구에대해기술하고본연구에서목적으로하는문제의범위를정의한다. 3 장의 modified LCS 를이용한 signature 생성에서는자주사용되는웜 110

2 signature 와어플리케이션 signature 의포맷을재정의하고, LCS 의 modification 에필요한제약사항들과 modified LCS 알고리즘을실제트래픽에적용하는방법을설명한다. 또한 4 장에서는 modified LCS 알고리즘을기반으로실제 signature 를생성하는두시스템에대한설명과검증을다룬다. 6 장에서결론과앞으로의연구방향을제시함으로써본논문을마무리한다. 2. 문제의범위 (Problem Domain) 이번장에서는기존에존재하는 signature 기반의트래픽분류연구에대한개략적인소개를하고, 웜 signature 생성에사용되었던접근방법을일반적인어플리케이션분류에사용하기어려운이유에대한간략한설명을한다. 그리고본논문의범위내에서 signature 생성의문제의범위를재정의한다. 2.1 관련연구 다음에언급되는연구들은 signature 비교방법을기반으로한자신들만의트래픽분류방법을보여주고있다. Gummadi 의연구 [3] 는 KaZaA 의다운로드트래픽의분류를위해어플리케이션레벨의 signature 를사용하였지만, 생성된 signature 에대해정확도측정과같은검증과정을제시하지않았다. 물론전체적인접근방법이논리적이지만트래픽분류결과의정확성에대한의문이남는다. Sen 의연구 [5] 에서는어플리케이션의프로토콜을분석하여 P2P 어플리케이션의 signature 를생성하였다. 이러한분석방법은 signature 의정확도를높일수있지만수동적인방법으로 signature 를생성해야하므로효율성이떨어지고실시간시스템에적용하기에는부적절하다. 종합적으로보았을때에이와비슷한연구들은 signature 비교방법을통한어플리케이션트래픽의분석률을제시하지만 signature 를생성하는방법이나그 signature 자체의정확도에대한검증을중요하게언급하지않고있다. Signature 기반의트래픽분류는웜 detection 을위한 Intrusion Detection System (IDS) 들에서주로사용되어왔다 [6]. 이연구들은웜 signature 를자동으로생성할수있는시스템의개발에대해기술하고있는데, 이들모두공통적으로 port scanning 과같은웜의대표적인특성을보이는비정상트래픽에대한 signature 생성을목적으로한다. 이와같은목적이일반적인어플리케이션 signature 생성과가장큰차이점은각각의어플리케이션들이자신만의유일한 signature 를갖는것과달리웜 signature 의경우는여러개의웜들이하나의 signature 를공유할수있다는점이다. 이는어떠한의미에서웜 signature 가좀더약한제약사항을갖는다고볼수있다. 일반적으로웜 signature 생성에관련된연구에서는 sliding-windows 알고리즘과자신들이정의한 break point 를사용하고있다. Scheirer 의연구 [10] 에서는이러한 break point 의선정에관한설명을기술하고있는데, 이들 break point 는웜들이공통적으로갖고있는특정동작에해당하는 instruction code 와같은 hex 값들이다. 따라서웜과같은비정상트래픽과특성이다른일반적인인터넷어플리케이션트래픽분류에 break point 를사용하는 slidingwindows 알고리즘을직접적용하는것에는어려움이따른다. 이러한점들이기존의웜 signature 생성에관한연구와본연구사이의차이점을시사한다. Longest common subsequence problem (LCS) [13] 은모든 sequence 들에 ( 일반적으로 2 개 ) 공통적으로나타나는가장긴 subsequence 를찾는문제이다. 이는전통적인컴퓨터과학문제중에하나이며생물정보학의응용으로주로사용되어왔다. 가장주된응용은생명정보학에서의 DNA sequence matching 이다. DNA 는각각서로다른특정한의미를갖는 4 가지의구성요소 (A, C, G, T) 만으로이루어있는반면어플리케이션트래픽은이보다더욱복잡한구성요소들로이루어져있으며모든구성요소가의미를갖고있는것이아니기때문에자동화된어플리케이션레벨의 signature 생성시스템을위해서 LCS 알고리즘을수정 / 적용하였다. LCS 의동작에대한자세한사항은 3.3 장에서예제를통해기술한다. 2.2 문제정의와자동화 우리의시스템은어플리케이션의 signature 로특정어플리케이션의 packet stream 으로부터하나이상의 string 이나 hex 값이이루는 sequence 들을자동적으로추출해낸다. 본논문에서는모든어플리케이션들이그들만의독특하고유일한 signature 를갖는다는가정하에모든네트워크기반의어플리케이션의 signature 를생성하는것을목적으로한다. Modified LCS 알고리즘의입력으로 signature 생성을원하는대상 application 에서발생한 raw packet 들만을수집하여사용한다. 이러한입력데이터의수집은수동적인방법과트래픽수집 agent 를통해이루어진다. 수동적인방법의경우에는대상어플리케이션을독립적으로실행시켜 data 를수집하고트래픽수집 agent 를사용하는경우에는 agent 가탑재된컴퓨터에서발생한트래픽을프로세스 ( 어플리케이션 ) 별로구분하여저장하는동작을한다. 위의두가지방법으로수집된데이터는 semiautomatic 시스템과 fully-automatic 시스템에서각각입력으로사용된다. Signature 생성시스템의자동화정도와 signature 의정확도사이에는교환조건이존재하기때문에서로다른자동화의정도를갖는시스템을사용하며두시스템의차이에대해서는 4 장에서더욱자세히설명을한다. 3. Modified LCS 를사용한 Signature 생성 111

3 이번장에서는여러연구에서사용된 signature 포맷에대하여기술하고일반적인인터넷어플리케이션 signature 에적합한포맷을제안한다. 또한어플리케이션 signature 를위한제약사항들과 modified LCS 알고리즘을적용하여 signature 를생성하는동작에대해설명한다. 3.1 Signature 의포맷 A. 웜 Signature 포맷 Newsome 의연구 [15] 에서는 polymorphic 웜들에적합한 signature 포맷을몇가지로분류하였다. Polymorphic 웜은새로운감염을시도할때마다 payload 의내용을변화시키는웜을의미한다. 이연구에서분류한 signature 들은웜을제외한다른트래픽에적용되지못한다. 이들 signature 는아주단순한 substring 의 sequence 로이루어져있는데, 본연구에서는이를바탕으로일반적인인터넷어플리케이션에적합한조건들을추가하여새로운포맷들을정의하였다. 이들에대해서는다음장에서자세히소개되며, 아래의 signature 포맷들은 Newsome 의연구에서정의한웜 signature 의포맷들이다. Conjunction signatures: signature 는 substring ( 또는 token) 들의집합으로이루어져있으며, token 들의순서는상관이없다. Token-subsequence signatures: signature 는특정순서의 token 들의집합으로이루어진다. Bayes signatures: signature 는각각 score 와 threshold 값을갖는 token 들의집합으로이루어진다. Brumle 의연구 [14] 역시몇가지의웜 signature 의포맷을제안하고있다. Turing machine signature, symbolic constraint signature, 그리고 regular expression signature 가이에해당한다. 하지만이러한 signature 포맷으로 signature 를기술할경우 matching 효율이낮아지기때문에 signature 들을모든 packet 들과비교하는경우에는접합하지못하다. B. 인터넷어플리케이션 signature 포맷지금까지진행되었던 signature 기반의트래픽분류에관한연구들에서는자신들만의 signature 포맷을정의하고이에맞는 signature 들을생성하여트래픽을분류해왔다. 우리는기존에사용되어오던 signature 을다음과같이몇가지로분류하였다. Common string with fixed offset: 이는어플리케이션에서발생하는 packet 의 payload 의특정위치에반복적으로나타나는 string 이나 hex 값을어플리케이션 signature 로정의한다. 그리고 대부분의경우는 offset 이 payload 의시작점에해당한다. Common string with variable offset: 이포맷은앞의포맷과유사하지만반복적으로나타나는 string 이나 hex 값이고정된위치가아닌다양한위치에나타날수있다는점에서다르다. Sequence of common substrings: 하나의짧은 string 이나 hex 값은정확도를보장하지못하기때문에이포맷은앞의두정의와달리하나의 string 이아닌여러개의 substring 들이일정한순서를갖고 payload 상에나타나는것을 signature 로정의한다. Behavioral signature: 이는어플리케이션트래픽의 packet inter-arrival time 이나최소 / 최대 packet 사이즈등과같은특징들을 signature 로정의한다. 본논문에서는 packet payload 에대한조사를통해자동으로 signature 를생성하는것을목적으로하기때문에이 signature 포맷은고려하지않는다. Karagiannis 는자신의논문 [10] 에서 common string with fixed offset 포맷을사용하였다. 하지만이러한포맷의 signature 를사용할경우에는정확도가상당히떨어질수있다. 어플리케이션프로토콜에대한조사가없이생성한 signature 이기때문에이러한문제가발생하게되는데, 예를들어프로토콜의 signature 앞에가변적인길이를가진 string 이존재하는경우에는 signature 의 offset 또한변화할수있기때문에 fixed offset 을사용하는경우에는트래픽을정확히분류해낼수가없다. 최근많은어플리케이션들이편의성을위해 HTTP 프로토콜을이용하면서많은 packet 들의 payload 에 GET 또는 HTTP 라는 string 이빈번이나타난다. 하지만이와같은 string 들은어플리케이션을분류하는역할을하지못한다. 따라서앞에서설명한 signature 포맷을사용할경우에는이러한 string 들은어플리케이션레벨의 signature 로써아무런의미를갖지못한다. Sen [5] 은마지막에언급했던 sequence of substrings 라는 signature 포맷을이용하여 signature 의정확도를높이고있다. 이러한 signature 포맷을사용하면 HTTP 와같은 string 또한 signature 의일부로써의미를갖게된다. 전체적으로살펴보면 behavioral signature 를제외한세가지포맷중 sequence of substrings 가다른나머지두개의포맷을포함하는 superset 이되며정확도가높다. 따라서앞으로설명할 signature 생성을위한접근방법에서는 sequence of substring 을 signature 포맷으로삼는다. 3.2 어플리케이션 signature 를위한제약사항 LCS 를사용하여어플리케이션 signature 를생 112

4 성하는것은 DNA sequence matching 과는차이점이있다. 기본적으로어플리케이션 signature 는 DNA 보다더많은구성요소로이루어지고또한구성요소각각이모두의미를갖는것이아니기때문에다음에설명할제약사항들이포함되도록 LCS 알고리즘을수정해야한다. 이러한제약사항들은전체적인 signature 생성시스템의효율성을증가시키고 signature 의정확도를증가시키는것을목적으로한다. A. Flow 를이루는 packet 의수 Flow 는동일한 source IP, destination IP, source port, destination port, 그리고프로토콜을갖는 packet 들의집합이다. [5] 에서 signature 가존재하는 packet 은 flow 초반의몇개의 packet 에제한됨을설명하였다. Flow 상에는수많은 packet 들이존재하는데, 이모든 packet 에대해 payload 를조사할필요가없음을의미한다. 적절한하나의 flow 를이루는 packet 의수를결정하는것은 LCS 알고리즘을이용하여 signature 를생성할때에비교횟수를감소시켜계산의효율성을증가시키기위해중요한제약사항이다. 가큰 downloading packet 들을서로비교하는과정은필요가없다. 결과적으로효율성을향상시키기위해비슷한크기범위내에있는 packet 들사이에서만비교가이루어지도록하는제약조건이필요하다. 실제적인예로 Gnutella 계열의유명한 P2P 어플리케이션인 LimeWire 의경우, connection control 이나 search 와같은 signaling packet 의크기는평균적으로 390byte 인것에반해 downloading packet 의 size 는 1460byte 이다. 이러한두가지종류의트래픽들은어플리케이션내에서수행하는동작이다르기때문에동일한 signature 를포함할확률이적다. B. Substring 의최소길이자동으로생성된 signature 는한개이상의 substring 들로이루어지게되는데, substring 의길이는정확한트래픽분류를할수있는신뢰할수있는 signature 로써의중요도를반영한다. 의미가없는 substring 들이 signature 에포함되는것을방지하기위해 substring 의최소길이가 modified LCS 알고리즘의제약사항로고려되어야한다. 예를들어하나의 character 가 common substring 중하나로결정되었을때에이 character 가 fixed offset 에서반복적으로나타나지않는한, 실제 signature 에포함시키기는어렵다. 실제로 HTTP 프로토콜을사용하는어플리케이션들에서는 / 와같은 character 가자주쓰이는데, 본제약조건을통해다른 string 들과의조합이아닌이러한 character 하나만이 signature 에포함되는것을방지한다. C. Packet 크기의비교서로비교되는 packet 들의목적과 ( 예 : signaling packet, download packet) 트래픽특성이비슷할경우에신뢰할수있는 signature 를찾을확률이증가하게된다. Packet 들간의유사성을판단하기위한가장기본적인특성이 packet 의크기이다. 그림 1 은세가지 P2P 어플리케이션들이파일을다운로드시작할때에 flow 상의초기 100 개 packet 의크기분포를나타내고있다. 초기의몇개 packet 들은 connection handshake 나다운로드요청을위한 packet 들이다. 이들의크기는실제 downloading packet 들보다상대적으로작다. 명확한 signature 는초기의 signaling packet 에만존재하므로 signature 를생성하는과정에서크기가작은 signaling packet 들과크기 그림 1. 파일다운로드를시작할때생성되는초기 100 개 packet 들의크기분포 113

5 3.3 Modified LCS 를이용한 signature 생성이번장에서는앞에서설명한제약사항들을적용한 modified LCS 알고리즘을통해 sequence of common substrings 포맷의 signature 를생성하는과정에대해설명한다. LCS 알고리즘의두개의 string 을입력으로사용하여둘사이의 longest common substring 을찾아낸다. 여기에서 substring 은두입력 string 들에서공통적으로존재하는작은단위의 substring 을의미하고 longest common subsequence (substring) 는두입력 string 들에서공통적으로나타나는 substring 들이동일한순서를보일때에이들 substring 들의길이의합이최대가되는 substring 들의 sequence 를말한다. 이때, substring 들은연속적으로나타나야만할필요는없다. 입력 string 1 - XXXAAXXBCDXXXEFGHXX 입력 string 2 YYYYAAYBCYYYYEFHYYY 예를들어위의두개의입력 string 이주어졌을때에 (bold 체는 common substring 을의미 ), 두 string 간의 LCS 는 AA*BC*DF*H 와같이표현될수있다. substring 들은각각의입력 string 에서서로다른위치에존재할수는있지만이들의 sequence 는각입력 string 에서동일하게유지됨을알수있다. LCS 알고리즘에서는 substring 을선택할때에 first match 가아닌 best match (longest length 를갖는 match) 가되도록선택한다. 이러한선택의기본가정은 substring 의길이가길수록두입력 string 의유사성이높아질수있다는것이다. 예를들면, 다음과같은입력이주어졌을때에, first match 를통해 substring 을선택하면 LCS 는 A*A 형태를갖게된다. 입력 string 1 - AXXXAAXX 입력 string 2 AAYYYYYY 하지만 LCS A*A 의형태는 best match 로선택한 LCS AA 보다정확한 signature 가될수없기때문에 first match 가아닌 best match 즉, substring 의길이를최대로하는 LCS 를생성하게된다. 입력 string 1 - AXXXAAXX 입력 string 2 - AAYYYYYY Modified LCS 의입력으로는서로다른두개의 packet payload 상의 byte stream 이사용되는데각 packet 들은같은어플리케이션에서발생한두개의서로다른 flow 에서선택된다. 그림 2 는두개의 LimeWire flow 에서 packet 크기와 flow 를이루는 packet 수에관한제약조건을적용하여 packet 을선정한후에 signature 를생성하는단계를설명하고 있다. 각각의 byte stream 은 P2P 사용자가 Gnutella 프로토콜을사용하는 Morpheus 와 LimeWire 서버에접속하여파일다운로드를시도할때에발생한것이다. 그림에서표현된 candidate signature 는낮은정확도를갖는완성되지않은 signature 를의미한다. 최종적인 signature 를생성하는과정에대해서는다음장에서자세히설명한다. 그림 2. LimeWire 에서발생한 Packet 에 modified LCS 를적용하는예 두개의입력 byte stream 을이용하여 LCS 를구하면 HTTP 200 OK Server:*e*Content-type:*e* 과같은형태가된다. 하지만 substring e 는 signature 로써의미를갖기에는길이가너무짧기때문에이처럼모호한 substring 을 substring 의최소길이에관한제약조건을통해제거한다. 이러한과정을거치면 HTTP 200 OK Server:*Content-type:* 와같은형태의 candidate signature 를얻게된다. Payload 상의 string 은모든 packet 에서반복해서나타나는고정적인 string ( 예 : HTTP) 과길이나내용이가변적인 string ( 예 : 사용자 ID 또는 host name) 으로나누어볼수있는데 signauture 에는가변적인 string 이포함되면안되기때문에 modified LCS 를적용하여이러한 string 들을제거한다. 또한 HTTP 200 OK 와같은 substring 은 HTTP 프로토콜을사용하는어플리케이션에서는자주나타날수있기때문에그자체로는의미를갖기힘들지만다른 substring 과이루는 sequence 는어플리케이션마다서로다른특징이있기때문에 sequence 의일부로써의미있는 substring 이될수있다. 4. Signature 생성시스템 이번장에서는 3 장에서설명한 modified LCS 알고리즘을적용하여최종적으로어플리케이션레벨의 signature 를생성해내는시스템들에대하여설명한다. 자동화의정도에따라 semi-automatic 시스템과 fullyautomatic 시스템으로나뉜다. Semi-automatic 시스템은사용자의개입이일부필요하지만정확한 signature 를생성한다. 이러한 system 에서사용자의개입이라는단점을보완하기위해 fully-automatic 한시스템을개발하게되었다. 이들두시스템간의동작의차이에대해서는다음에서설명을한다. 4.1 Semi-automatic 시스템 114

6 Semi-automatic signature 생성시스템은입력으로사용될데이터를수집하는과정에서 signature 생성을원하는어플리케이션을독립적으로실행시키고트래픽을 capture 하는사용자의개입이필요하다. 자동화정도가 fully-automatic 시스템보다낮지만그보다더높은정확도의 signature 를생성하는시스템이다. A. 데이터의수집이시스템의입력으로사용되는데이터는사용자에의해수동적으로수집된다. Signature 를생성하고자하는특정어플리케이션을독립적으로실행시키고해당어플리케이션이발생시키는트래픽만을선택적으로수집한다. 특정어플리케이션이발생시키는트래픽만을수집하는것은다음에설명할트래픽수집 agent 를통해서도가능하지만이와같은방법을사용하는이유는다음과같다. 하나의독립된어플리케이션이발생시키는트래픽은어플리케이션의동작에따라다른특성을띤다. 예를들어 P2P 어플리케이션의경우는 login, search, download 등과같은다양한기능을갖고있는데이러한동작들이수행될때발생되는트래픽은서로다른트래픽패턴을보인다. 만약서로다른기능을수행하는트래픽을입력으로 signature 를생성할경우에는부정확한 signature 가생성될수있으며 signature 가전혀생성되지않는경우가생길수있다. 따라서정확한 signature 를생성할수있도록수동적으로어플리케이션에서특정동작을할때에발생하는트래픽을선별적으로수집하여입력데이터로사용하는것이다. 이때에수집된트래픽은동일한 5-tuple 정보를갖는 flow 형태로이루어진다. B. Signature 의생성 그림 3. Training model 을이용한최종 Signature 의생성 최종적인 signature 는 candidate signature 에서의미가없는 string 들을제거하는과정을통해얻어진다. 그림 3 은최종적인 signature 를생성하기위한 training model 을설명하고있다. 처음의 training 단계의입력으로는서로두개의 flow 가사용된다. Signature extractor 는 modified LSC 알고리즘을이용하여 candidate signature 를생성하는컴포넌트이다. 이컴포넌트를통해처음으로생성된 signature 는두개의 flow 만을비교하여생성된것이기때문에정확성이현저하게떨어진다 ( 불필요한 string 들이많이포함되어있음 ). 이러한문제를해결하기위해위의그림과같은 training model 을사용하여 training 이반복될때마다불필요한 string 들을줄여나간다. 한번의 training 이이루어질때생성되는결과값은전단계의결과값보다불필요한 string 들 (e.g IP address, user ID, host name, etc) 이줄어들지만완벽한 signature 가아니라면다음 training 단계의입력으로재사용된다. 이와같은 training 이계속해서반복될수록불필요한 common substring 의수는감소하게되며점차정확한 signature 에가까워진다. 여기에서반복적인 training 은무한한것이아니라특정조건을만족하게되면 training 이중지되며최종 output 인 signature 를얻을수있다. 특정한종료조건은더이상 candidate signature 에서제거될 substring 이존재하지않는것을의미한다. Signature 생성의단계를다음과같이표현할수있다. Candidate signature_1 = Sig(Input 1, Input 2) Candidate signature_2 = Sig(Input 3, Candidate_signature_1) Candidate signature_n = Sig(Input n+1, Candidate_signature_n-1) 만약 Candidate signature_n = Candidate signature_n-1 이라면 Candidate signature_n 은최종 signature 가된다. C. 실험결과 Modified LCS 알고리즘이 signature 생성에있어서유용함을확인하기위하여세가지의어플리케이션들을선정하여각각의 signature 를생성해보았다. 선정된어플리케이션들은대표적으로많이사용되는 P2P 어플리케이션 LimeWire, BitTorrent, 그리고 Fileguri 이다. LimeWire 는 Gnutella 프로토콜을사용하는대표적인어플리케이션이며 BitTorrent 는동시에수많은 peer 들로부터동시에파일을다운로드할수있는전세계적으로매우널리사용되고있는어플리케이션이다. 두어플리케이션은다른 signature 기반의트래픽분류연구 [5] 에서도사용되었던어플리케이션이며, 마지막의 Fileguri 는국내에서많이사용되는어플리케이션으로이역시다른연구 [11] 에서사용되었다. Modified LCS 의유용성을판단하기위해다른연구에서수작업을통해생성한 signature 와 modified LCS 를통해생성된 signature 를비교분석하였다. 표 1 은선정된세가지어플리케이션에대해각각 packet 분석, 프로토콜분석, modified LCS 를사용하여생성한 signature 를나타낸다. Packet 분석은 115

7 Packet analysis Protocol analysis Modified LCS 표 1. 세가지방법으로생성된 signature 의비교 LimeWire BitTorrent Fileguri GNUT 0x13Bit Freechal GET or HTTP followed User-Agent: Limewire or UserAgent: Limewire or Server: Limewire Sequence of 24 substrings GET, uri-res, urn, sha, HTTP, HOST, User-Agent, LimeWire, X-Queue, X- Gnutella-Content-URN, urn, sha, X-Alt, Range, bytes, X-Node, Chat, X-Features, fwalt, browse, chat, queue, X-Downloaded 0x13BitTorrent protocol Sequence of 1 substring 0x13BitTorrent protocol N/A Sequence of 6 substrings GET, HTTP, Accept, User- Agent, Freechal, P-Authentication 어플리케이션의프로토콜에대한사전정보가없이 raw packet 의 payload 를직접분석하여 signature 를생성하는방법을의미하며 [2], 프로토콜분석은어플리케이션프로토콜정보를분석하여 signature 를생성하는방법이다 [2]. 따라서프로토콜의정보가공개된어플리케이션의 signature 를생성한다면정확한프로토콜정보를확인하여생성한 signature 가가장정확한방법이라고가정한다. 이러한가정하에각방법들을통해생성한 signature 결과를다음과같이정리하였다. 실제실험에사용한 modified LCS 알고리즘의제약조건들은다음과같이설정되었다. [5] 와그림 1 의결과에따라 flow 를이루는 packet 의수는 flow 상의초기 10 개의 packet 으로설정되었으며 substring 의최소길이는 3 으로설정하였다. 마지막으로비교될 packet 들의크기차이는 100byte 이하로제안하였다. 이러한제약조건들의설정의어플리케이션의종류에따라조정이가능하다. LimeWire: packet 분석을통해생성된 signature 인 GNUT 는다른것들과비교했을때에상대적으로길이가짧다. Signature 의길이가짧을수록다른어플리케이션의 signature 와충돌이될가능성이높아지므로이러한 signature 를이용하여트래픽을분류할경우에는정확도를보장하기어렵다. 프로토콜분석을통해생성한 signature 와 modified LCS 가만들어낸 signature 를비교하면 modified LCS signature 가다른두 signature 들을포함하고있는형태이다. 이러한결과는프로토콜분석을통해 signature 를생성할때정확한 signature 가될최소한의 substring 들만을선택하였기때문이다. 실제로 X-Gnutella-Content-URN 와같은 string 은 LimeWire 의프로토콜에존재하는값이다. Modified LCS 를사용하면이처럼의도적으로포함시키지않은 string 들또한판단할수있다. BitTorrent: packet 분석을통해생성된 signature 는프로토콜분석을통해생성한 signature 보다길이가짧지만 modified LCS signature 는프로토콜분석을이용한프로토콜과동일한 signature 를생성해냈다. Fileguri: 이어플리케이션의경우는공개되지않은자체적인프로토콜을사용한다. 따라서프로토콜분석을통한 signature 는존재하지않는다. 나머지두 signature 를서로비교하면 LimeWire 와비슷하게 modified LCS signature 가 packet 분석을통한 signature 를포함하고있는형태이다. 다음으로 training model 의효율성에대해분석을한다. Modified LCS 알고리즘을통해서프로토콜이나 packet payload 에대한조사가필요없이자동으로 signature 를생성할수있지만앞서서설명한것과같이반복을통한 training 을필요로한다. 만약 training 을위한반복의횟수가많이요구된다면효율적이지못한것이된다. 그림 4. Training 횟수에따른 Candidate signature 길이변화그림 4 는 training 의반복에따른 candidate 116

8 signature 의길이의변화를나타낸다. Training 의횟수가증가할수록 candidate signature 의길이가감소하는데, 이는반복이이루어질때마다불필요한 signature 들이제거되는것을의미한다. Candidate signature 의길이가더이상줄지않을때에 training 과정이종료되며최종 signature 가완성되는데, 그래프에서확인할수있듯이모든경우에있어서 10 회이하의 training 을통해 signature 가생성되었다. 이는적은량의입력 data 와빠른시간내에 signature 를생성해낼수있음을의미한다. 결과적으로 training 을활용한 modified LCS 알고리즘은수동적인방법으로 signature 를생성하는것보다효율적으로 signature 를생성할수있다. 4.1 Fully-automated 시스템 Semi-automated signature 생성시스템은자동으로정확한 signature 를생성할수는있지만입력으로사용할데이터수집에있어서사용자의개입이필요하다는단점을가지고있다. 이러한점을보완하기위해서트래픽수집을자동적으로수행할수있는 agent 를탑재한시스템이요구되었다. 이시스템은기존에사용되었던 modified LCS 알고리즘을그대로사용하면서 training 과정대신 grouping 알고리즘을통해서 signature 를생성한다. A. 데이터의수집 Full-automated 시스템에는 input data 를자동으로수집할수있는 agent 가탑재된다. Data 수집 agent 는 windows 기반으로개발되었으며 agent 가탑재된컴퓨터에서발생하는모든트래픽을어플리케이션 ( 또는프로세스 ) 별로수집하는기능을수행한다. 이때에수집된트래픽역시동일한 5-tupe 정보를갖는 flow 형태로이루어진다. Agent 는 libpcap library 와 windows system call 을이용하여트래픽 capture 와저장을수행한다. Packet 이 capture 되었을때새로운 TCP 의 Syn flag 가설정된경우에는새로운세션이맺어진것으로판단하고어떠한어플리케이션이맺는세션인지를확인하기위해 windows system call 을통해세션이맺어질때사용한네트워크 port 를사용하고있는프로세스정보를운영체제로부터받아오게된다. 따라서트래픽수집 agent 는자동적으로어떠한 packet 이어떠한어플리케이션에서발생한것인지를판단할수있고트래픽을어플리케이션별로수집한다. 이러한 agent 를통해트래픽을수집하는경우에는특정어플리케이션만을독립적으로실행시킬필요가없이동시에여러어플리케이션의트래픽을수집할수있으므로사용자가수동으로수집하는방법에비해많은량의데이터를빠르게수집할수있다. 하지만해당트래픽이어떠한어플리케이션동작 (e.g. login, search, download) 을위한것인지를판단하지못하기때문에 semi-automated 시스템의 training 과다른방법으로 signature 를생성해야만 하는문제가따른다. B. Signature 생성 Fully-automatic 시스템의 input 은같은어플리케이션에서발생한트래픽을자동으로수집한것이지만 semi-automatic 시스템과달리하나의어플리케이션에서발생한모든종류의트래픽이섞여있는형태이다. 이러한경우입력으로사용될트래픽이하나의어플리케이션에서발생한것이지만여러종류의트래픽패턴이존재하기때문에 training model 을그대로사용한다면 signature 가생성되지않을수있다. 그리고생성되어야할 signature 또한한개가아니라어플리케이션이가지고있는여러동작의종류에해당되는수가생성되어야한다. Signature 를생성하고자하는어플리케이션의트래픽데이터를해당되는동작별로구분지을수있는정확한방법이존재하지않기때문에 modified LCS 에의존하여 grouping 을하는방법을사용하였다. 그림 5. Grouping 의동작 그림 5는 signature 생성을위한 grouping 알고리즘의동작을설명하고있다. 그림의위쪽줄에표현된 flow 들이시스템의입력값으로사용되는 flow 들이며 type 은어플리케이션의동작의종류를의미한다. 3 가지종류의서로다른동작을하는어플리케이션의 flow 6 개를입력으로사용한다. 그림의아랫줄에표현된것은입력으로사용된 flow 들을 modified LCS 를통해 grouping 한후의결과를나타낸다. 여기서하나의 group 은여러개의입력 flow 들가운데 LCS 가가장긴 (common substring 이가장많이존재하는 ) 두개의 flow 의쌍으로만들어진다. LCS 의길이가가장길다는것은두 flow 간의유사성이가장높다는것으로판단할수있다. Grouping 알고리즘을통해서나온결과는 2 개의동작 type 의 signature 이다. Type 1 signature 는 (flow 1, flow3) 의쌍에서얻어진 signature 이며 Type 2 signature 는 (flow 2, flow 6) 의쌍에서얻어진 signature 이다. 나머지쌍을이루지못한 flow 4 와 flow 5 는결과에서제외되게된다. 그림 5 는 grouping 을단순한예제를통해설명한것이지만입력으로사용되는 flow 가많아지게되면더욱복잡한알고리즘이필요하게된다. N 개의 flow 가입력값으로사용된다면결과로나올수있는그룹 signature 는최대 N/2 개가되며각각은 semiautomatic 시스템에서한번의 training 단계를거친 117

9 표 2. Grouping 알고리즘을통해생성한 signature BitTorrent Fileguri 0x13BitTorrent protocolex BC (8) 0x13BitTorrent protocolex (1) HTTP Server Freechal User-Type Date Mon Feb GMT P-Authentication Content-Length 0x13BitTorrent protocol (2) Content-Type text plain path keyword extension file-count process-time downloadwaiting (4) GET app asp HTTP Accept User-Agent Freechal Host www fileguri com Connection Keep-Alive (3) 것과같은형태를띄게된다. 따라서이들을 optimize 할필요가있다. Optimization 은두단계를통해이루어질수가있다. 첫번째단계는어플리케이션의동작에따른트래픽별로구분을하는것으로어플리케이션 flow 들은네트워크 port 가할당된 range 별로구분을짓는것이다. 어플리케이션이랜덤한방법으로 port 를할당하지만같은동작을수행할때에는비슷한 range 의 port 를할당한다는점에서이러한 optimization 이가능하다. 이구분에있어서는 100% 정확한방법은존재하지않는다. 다만다음단계에서이루어질 optimization 을좀더단순화시키기위해필요한단계이다. 두번째단계에서는 grouping 의결과로생성된 n (< N/2) 개의 signature 를앞단계에서같은동일한 port range 로구분지어진 group signature 끼리다시 modified LCS 를통하여하나의 signature 를만들어낸다. 이러한경우이상적인결과는어플리케이션의여러동작에해당되는 signature 가각각생성되는것이다. 만약동작에해당하는트래픽을구분짓는것이완벽하지않는다면하나의동작에해당하는 signature 가여러개존재할수있지만이들모두를 signature 로사용하여트래픽을분류할수있다. C. 실험결과 Modified LCS 와 grouping 알고리즘의결과를확인하기위하여 training 모델에서사용한 2 개의어플리케이션의 signature 를생성해보았다. 이때사용한어플리케이션들은 BitTorrent 와 Fileguri 이다. 표 2 는앞에서설명한 optimization 과 grouping 알고리즘을이용하여두어플리케이션의 signature 를생성한결과이다. 괄호안의숫자는이러한 signature 를공유하는 flow 쌍의개수이다. BitTorrent: 25 개의 flow 를입력으로이용해생성한 signature 의결과가크게 3 가지 group 의 signature 로종합되었다. Semi-automatic 시스템에서생성한 signature 와비교해볼때에, 3 가지 signature 모두 semi-automatic 시스템에서생성한 signature 를 포함하고, 그뒤에다른 substring 이붙어있는형태이다. 더이상의 optimization 이불가능할경우에는이들 3 개의 signature 모두를이용하여트래픽을분류할수있다. Matching 비용이단일 signature 보다높지만정확한분류가가능하다. 또한 BitTorrent 는 download 기능만을가지고있는어플리케이션이므로이들을 optimization 과정을통해정확한 signature 인 0x13BitTorrent 프로토콜 이라는정확한 signature 를얻을수도있다. Fileguri: 25 개의 flow 를입력으로사용하여생성한 signature 의결과가크게 2 가지 group signature 로종합되었다. Fileguri 의 signature 는 BitTorrent 와달리불필요한 string 들이많이포함되어있는결과를보였는데, 이는 Fileguri 가 HTTP 프로토콜을사용하고있기때문에 signature 에 HTTP 에자주나타나는 common string 들포함된것이다. 또한어플리케이션내에웹브라우저가포함되어있어단순한 html 파일의내용이 signature 에포함되었을가능성또한있다. 하지만 packet 분석을이용하여생성한 signature 인 Freechal 을포함하고있는것을확인할수있다. 두어플리케이션에 fully-automatic 시스템을적용해본결과 HTTP 프로토콜을사용하지않는어플리케이션의경우사용자의개입없이도정확한 signature 를생성할수있는반면, HTTP 프로토콜을사용하는어플리케이션은불필요한 string 들이다수포함됨을확인하였다. 이러한불필요한 string 들을제외시키고더욱효과적으로 grouping 을수행할수있도록 HTTP parser 를시스템에탑재시켜 HTTP 프로토콜을사용하는어플리케이션에대해서도정확한 signature 를생성할수있도록하는연구가진행중에있다. 5. 결론및향후과제 본논문에서는 modified LCS 에대해설명하고이를기반으로 training model, grouping 알고리즘을사용하여자동적으로어플리케이션 signature 를생성할수있는시스템들의구현과실험결과를제시하 118

10 였다. Semi-automatic 시스템은어느정도의사용자개입을요구하는대신에매우정확한 signature 를효율적으로생성할수있다. 이보다자동화정도를높여사용자의개입이없이 signature 를생성할수있는 fully-automatic 시스템은 HTTP 프로토콜을사용하지않는어플리케이션에대해서정확한 signature 를생성하지만다른어플리케이션의 signature 는상대적으로완성도가낮다. 이러한문제를해결하기위해 HTTP parser 를통한 filter 기능추가에대한연구가현재진행중이다. 또한트래픽수집 agent 에서트래픽을어플리케이션종류별뿐만아니라수행하는동작에따라수집할수있도록한다면 semi-automatic 시스템에서사용한 training 모델을 fully-automatic 하게수정할수있기때문에이러한기능의 data 수집 agent 의관한연구와 fully-automatic 시스템에서다른방법으로정확한 signature 를생성할수있는효과적인 grouping 알고리즘과 optimization 알고리즘에관한연구도향후과제이다. [11] Young J. Won, Byung-Chul Park, Hong-Taek Ju, Myung-Sup Kim, and James W. Hong. A Hybrid Approach for Accurate Application Traffic Identification, IEEE/IFIP E2EMON, Vancouver, April 2006, pp [12] Tcpdump. [13] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 2nd Edition, MIT Press, [14] David Brumley, James Newsome, Dawn Song, Hao Wang, and Somesh Jha. Towards Automatic Generation of Vulnerability Signatures, In the Proceedings of the IEEE Symposium on Security and Privacy, May [15] James Newsome, Brad Karp, Dawn Song. Polygraph: Automatic Signature Generation for Polymorphic worms, In IEEE Security and Privacy Symposium, California, USA, May 2005 [16] James Newsome and Dawn Song. Dynamic Taint analysis: Automatic Detection, analysis, and Signature Generation of Exploit Attacks on Commodity Software, In Network and Distributed Systems Security Symposium, San Diego, California, USA, 2005 참고문헌 [1] A. Gerber, J. Houle, H. Nguyen, M. Roughan, and S. Sen. P2P The Gorilla in the Cable, National Cable & Telecommunications Association (NCTA) 2003 National Show, Chicago, IL, June [2] S. Sen and J. Wang. Analyzing peer-to-peer traffic across large networks, Proceedings of ACM SIGCOMM Internet Measurement Workshop, Marseilles, France, November [3] K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan. Measurement, modeling, and analysis of a peer-to-peer File-sharing workload, Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP-19), Bolton Landing, NY USA,October [4] A. Moore and K. Papagiannaki. Toward the Accurate Identification of Network Applications, Passive and Active Measurements Workshop, Boston, MA, USA, March 31, April 1, [5] Subhabrata Sen, Oliver Spatscheck, Dongmei Wang. Accurate, Scalable In-Network Identification of P2P Traffic Using Application Signatures, New York, USA, WWW 2004 Conference. [6] H. Kim, B. Karp. Autograph: Toward automated, distributed worm signature detection, Proceedings of the 13th Usenix Security Symposium, San Diego, CA, [7] S. Singh, C. Estan, G. Varghese, S. Savage. Automated worm Fingerprinting, Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, San Francisco, California,2004. [8] Sumeet Singh, Cristian Estan, George Varghese and Stefan Savage. The EarlyBird System for Real-time Detection of Unknown worms, UCSD Tech Report CS , August [9] W. Scheirer, M. Chuah. Comparison of Three Sliding-Window Based worm Signature Generation Schemes,, Lehigh University Technical Report LU- CSE [10] Thomas Karagiannis, Andre Broido, Michalis Faloutsos, and KC Claffy. Transport layer identification of p2p traffic, Internet Measurement Conference (IMC), Taormina, Sicily, Italy,