고속 패킷 필터링 알고리즘 개발 = Development of A Fast Packet Filtering Algorithm

국문 초록 (Abstract)

현대를 사는 우리들에게 인터넷 이라는 단어는 이젠 일반 생활과도 같이 느껴지는 단계에 이르렀다. 이러한 인터넷의 보편화, 대중화는 인터넷 트래픽 규모를 확장시켰으며, 이로 인한 대용량의 네트워크 장비 및 고속의 암호화 알고리즘, 우수한 프로토콜의 개발이 계속해서 큰 이슈로 부각되고 있는 실정이다. 또한 인터넷의 보편화, 대중화는 개인, 기업 혹은 국가 정보보호(Information Security)의 필요성을 더욱더 부각 시키고 있다. 이러한 정보보호의 필요성으로 인하여 침입차단시스템(Firewall, 이하 방화벽) 및 침입탐지시스템(Intrusion Detection System : IDS)은 인터넷 보안을 위한 기본 장비로 정착하였으며, IPSEC(IP Security)과 PKI(Public Key Infrastructure)등도 ITEF(Internet Task Engineering Force)의 워킹그룹을 통하여 VPN(Virtual Private Network) 및 전자서명을 위한 표준으로 자리 잡았다. 위와 같은 여러 보안 장비 혹은 프로그램 중 방화벽은 가장 기초적이며, 근본적인 네트워크 보안 장비라 할 수 있다. 또한 현대의 네트워크 구조상 게이트웨이(Gateway) 역할을 수행해야하는 방화벽의 패킷 필터링 성능 (Performance)은 전체 네트워크 성능을 결정지을 수 있는 중요한 요소로 작용한다. 네트워크의 대형화 및 대용량화는 이를 관리하기 위한 방화벽 정책개수를 작게는 수십 개에서 수천 개 이상으로 증가 시키고 있으며, 이러한 방화벽 정책 개수의 증가는 방화벽의 패킷 필터링 속도를 현격하게 저하시키는 원인을 제공하게 된다. 따라서 대형화하는 이러한 네트워크 구조에서도 방화벽이 전체적인 네트워크 성능을 저하 시키지 않는 고성능의 패킷 필터링 알고리즘의 개발이 시급한 과제가 되고 있다.
기본적으로 방화벽의 패킷 필터는 패킷을 처리하기 위한 보안 정책(Security Policy)을 연결리스트(Linked-List) 형태로 메모리에 저장하여 방화벽을 통과하는 각각의 패킷에 대하여 정책을 적용한다. 방화벽은 패킷 필터로 들어오는 모든 패킷에 대해 보안 정책을 적용하기 위하여 첫 번째 정책부터 해당 패킷의 헤더 정보와 비교여 정책과 부합할 경우 보안 정책 (Accept, Deny, Reject)을 패킷에 적용 패킷의 운명을 결정짓는다. 만약 보안 정책과 부합하지 않는 경우, 다음의 보안 정책과 계속해서 비교한다. 만약 마지막까지 부합하는 정책이 없다면 패킷 필터는 기본정책 (Default Policy)을 적용한다. 이와 같이 연결리스트 구조로 되어 있는 방화벽 필터링 엔진 구조상 모든 패킷에 대하여 패킷 필터는 방화벽 보안 정책과 부합할 때까지 순차적으로 비교하게 된다. 따라서 방화벽의 보안 정책이 수천개 이상 정의된다면, 네트워크의 성능은 심각하게 저하되는 것이다.
방화벽의 패킷 필터가 해쉬(Hash) 혹은 btree와 같은 좋은 검색 속도를 가지는 알고리즘을 사용하지 않고 연결리스트 형태의 구조를 가질 수밖에 없는 단 하나의 이유는 보안 정책 설정시 필수적으로 쓸 수밖에 없는 방화벽 정책 우선순위 설정 문제 때문이다. 만약 해쉬 혹은 btree와 같은 알고리즘을 사용한다면 정책 적용에 있어 우선순위를 적용할 수 없기 때문에 현재까지는 연결리스트 구조의 패킷 필터링 방법을 사용하고 있는 것이다. 따라서 이와 같은 난점을 극복하기 위한 해결책으로 본 논문에서는 연결리스트와 해쉬 알고리즘을 동시에 사용하는 고속 패킷 필터링 알고리즘을 제시하고자 한다.

다국어 초록 (Multilingual Abstract)

In the modern world, people is accustomed to the word 'INTERNET' as a basic living environment. The generalization and popularity of using the internet make the internet traffic bigger than ever and it requires the network equipments having bigger capacities and developing of the fast encryption algorithms and excellent internet protocols. Also it is becoming gradually bigger and hotter issues in the internet engineering fields now a days. However, the generalization and popularity of using the internet brought out the importance of the information security of individual, corporation and nation. Because of the importance of information security, a firewall and an IDS (Intrusion Detection System) became basic internet security equipments. VPN(Virtual Private Network) and digital signature are being standardized by IPSEC(IP Security) and PKI(Public Key Infrastructure) through ITEF(Internet Engineering Task Force)'s working groups. The firewall in all of the above security equipments or programs is the fundamental and basic network security equipment. And in the modern network structure, the packet filtering performance of the firewall as the gateway is important and critical fact of determination for the network performance. As long as the network is being over-sized, the firewall security policies will be increased from several tens to over several thousands to control the network securely. Therefore, increased the security policies of the firewall make the network performance down very seriously. As the result, developing the fast packet filtering algorithm is becoming important issue in the over-sized network not to make network performance lower.
Basically the packet filter of firewall stores the security policies in the system memory as the type of linked-list and applies the security policies when the packets go through the packet filter. The packet filter compares the all of packets coming in the packet filter to the security policies and applies the security policy to the packets when the policy matches the packet header information. If there is no match security policy, the packet filter will apply the default policy. In the packet filter architecture using linked-list search algorithm, the packet filter will search security policy until the packet and security policy will be matched to the all of packets. Therefore, if the packet filter has several thousands or several ten thousands security policies, the network performance will be seriously down.
The reason why the firewall packet filter is not using hash or btree search algorithms which are much better than linked-list search algorithm is security policy priority. If the packet filter uses hash or btree search algorithms instead of linked-list, the packet filter will not be able to apply security policy priority. There was no choice but to use linked-list search algorithm for the packet filter until now. To solve the all of the above problems. This paper will show the fast packet filtering algorithm which is applied hash algorithm on the linked-list algorithm base.

목차 (Table of Contents)

• 목차 = ⅰ
• 國文抄錄 = ⅶ
• ABSTRACT = ⅸ
• 제1장 서론 = 1
• 1.1 연구목적 및 필요성 = 1
• 1.2 연구 방법 = 2
• 1.3 구성 = 2
• 1.4 기대효과 = 3
• 제2장 방화벽에 대한 고찰 = 4
• 2.1 방화벽 기능 = 4
• 2.2 방화벽의 구성 요소 = 6
• 제3장 패킷 필터링에 대한 고찰 = 11
• 3.1 패킷 필터링이란? = 11
• 3.2 패킷 필터링의 장점 = 12
• 3.3 패킷 필터링의 단점 = 13
• 제4장 리눅스 커널 패킷 필터링 기능 분석 = 14
• 4.1 Netfilter의 기본 구조 = 17
• 4.2 Netfilter의 내부 패킷 흐름 = 22
• 제5장 연결리스트 패킷 필터링의 문제점 분석 = 24
• 5.1 연결 리스트(Linked-List) = 24
• 5.2 연결 리스트 패킷 필터 = 25
• 제6장 Hash를 이용한 연결리스트 패킷 필터링 알고리즘 성능 개선 = 29
• 6.1 해쉬 (Hash) = 29
• 6.2 해쉬 테이블 = 30
• 6.3 해쉬를 이용한 패킷 필터링 구조개선 모델 = 33
• 제7장 패킷 필터링 성능 비교 테스트 = 37
• 7.1 실험 제목 = 37
• 7.2 실험 목적 = 37
• 7.3 실험 장비 및 소프트웨어 = 37
• 7.4 실험 방법 = 42
• 7.5 실험 조건(Test Condition) = 43
• 7.6 실험 데이터 = 45
• 7.7 실험 결과 = 48
• 제8장 결론 = 49
• 8.1 연구결과 요약 및 평가 = 49
• 8.2 향후 연구과제 = 50
• 참고문헌 = 51