초록 ▼

연구의 목적 및 내용
인터넷의 발달에 따라 바이러스가 너무 쉽게 전파되고 있다. 네트웍을 기반으로 형성된 정보사회에서 이 문제는 점점 더 심각해지고 있다. 기존 바이러스의 변종을 쉽게 만들어내는 기술도 등장하여, 새로운 바이러스가 나타났을 때 기존 백신 소프트웨어들이 빠르게 대응하지 못한다. 본 연구실에서는 유전 알고리즘을 이용하여 기존에 경험하지 못한 바이러스의 변종들을 제로데이에 탐지하는 초기 기술이 성과를 보고 있는 단계에 있다. 이를 확장하여 다형변이 바이러스 감지 시스템을 개발한다. 연구는 크게 3단계로 이루어진다.

연구의 목적 및 내용
인터넷의 발달에 따라 바이러스가 너무 쉽게 전파되고 있다. 네트웍을 기반으로 형성된 정보사회에서 이 문제는 점점 더 심각해지고 있다. 기존 바이러스의 변종을 쉽게 만들어내는 기술도 등장하여, 새로운 바이러스가 나타났을 때 기존 백신 소프트웨어들이 빠르게 대응하지 못한다. 본 연구실에서는 유전 알고리즘을 이용하여 기존에 경험하지 못한 바이러스의 변종들을 제로데이에 탐지하는 초기 기술이 성과를 보고 있는 단계에 있다. 이를 확장하여 다형변이 바이러스 감지 시스템을 개발한다. 연구는 크게 3단계로 이루어진다. (1) 자동적 다형변이 바이러스 생성 기법 연구 (미리 연구를하기 위해서는 미리 만들 수밖에 없다.) (2) 다양한 다형변이 바이러스 감지 기술 개발 (3) 속도문제를 해결하기 위한 알고리즘의 개선
연구결과
1) 바이러스 변종 생성 기법 연구: 바이러스를 효과적으로 탐지하기 위해서는 미래에 등장할 바이러스들을 미리 경험해볼 수 있어야 한다. 결국 적어도 미래에 등장할 바이러스들 정도의 난이도를 가진 바이러스를 만들어낼 수 있어야 한다. 미래의 바이러스들이 사용할 전략을 미리 예상할 필요가 있다. 유전 알고리즘을 비롯한 여러 가지 최적화 알고리즘 기술을 사용할 것이다.
- 바이러스 다형변이 변종 생성 (일정 수준의 보안 기준이 필요함)
- 생성된 바이러스 변종들의 특징을 비교·분석
2) 바이러스 탐지 기법 개발: 다형변이 생성 기법에 대한 이해를 바탕으로 다양한 바이러스의 변종을 효과적으로 탐지하는 기법을 개발한다. 바이러스의 구조는 그래프 모델로 분석할 수 있다.
- Subgraph Isomorphism 문제: 그래프 이론에서 같은 구조를 갖는 그래프들을 찾는 문제다. 이 문제는 현실적인 최적해를 보장할 수 없는 NP-Hard 문제다. 현재 본 연구실에서 유전 알고리즘을 사용하여 현실적인 시간 내에 높은 확률로 해결할 수 있는 방법에 대한 초기 연구가 진행되어 있는 상태다.
- Subgraph Isomorphism 문제를 해결하는 유전 알고리즘 개발: 더 빠르고 더 정확한 알고리즘을 개발한다. 유전 알고리즘의 약점인 수행 시간을 단축시키는 연구가 포함된다. 다른 난제들에 대해 유사한 경험이 누적되어 있으므로 (그래프 분할, 회로 분할, TSP 등) 이런 연구를 하기에 가장 유리한 집단이라 할 수 있다. 바이러스의 실시간 탐지는 많은 것을 놓친다. 시간을 들이더라도 철저한 탐지가 필요한 곳들이 있다.
- 토큰 기반의 바이러스 감지 기법 개발: 토큰 기반의 방법은 프로그램을 토큰 단위로 분해하여 토큰 시퀀스를 얻은 후 그 특징을 분석하는 방법이다. 이러한 방법은 수행 속도가 매우 빠르지만 다형변이 바이러스 탐지에 다소 취약하다는 단점이 있다. 이러한 방식의 장점을 살리면서 유전 알고리즘을 활용하여 정확도를 향상시키는 방법을 개발하였다.
3) 다형변이 바이러스 감지 엔진 개발: 개발한 알고리즘을 바탕으로 정밀도에 따라 수행할 수 있는 네 가지의 다형변이 바이러스 감지 엔진을 개발하였다.
연구결과의 활용계획
- 변종 바이러스를 효과적으로 탐지하는 백신 소프트웨어 개발
- 국내 바이러스 산업의 약점 보완 및 국제적 경쟁력 강화
- 경험하지 못한 바이러스로 인한 불가피한 혼란인 제로데이(zero-day) 문제를 대폭 감소시킴
- 침입 탐지 기법에 응용
- 프로그램 표절 검사에 응용
- 유전 알고리즘의 응용 분야 확대

Abstract ▼

Purpose&contents
Computer malware is spreading very easily as internet grows. It is becoming a serious threat in the society of network based on information technology. Existing anti-virus softwares cannot detect new viruses when they come out, because of the technology which generates polymorphi

Purpose&contents
Computer malware is spreading very easily as internet grows. It is becoming a serious threat in the society of network based on information technology. Existing anti-virus softwares cannot detect new viruses when they come out, because of the technology which generates polymorphic viruses from original one easily. We show the promising result of zero-day malware detection mechanism with genetic algorithms to detect previously unknown polymorphic malwares. Extending this work, we develop a vaccination system for polymorphic viruses. The research consists of 3 steps. (1) Research on automatic generation of virus variants (which is required for detection research) (2) Develop various detection system for polymorphic viruses (3) Improvement of algorithm in terms of the speed
Result
1) Research on generation mechanism for polymorphic viruses: To detect future viruses effectively, experiencing them beforehand is required. At least, we are able to generate viruses which have the same degree of difficulty as future ones. It is necessary to predict strategies of future malwares beforehand. We use various optimization algorithms/techniques including genetic algorithms.
- Generate polymorphic malwares (a certain level of security is required)
- Compare and analysis with generated polymorphic malwares
2) Develop malware detection mechanism: Based on understanding of generation techniques for polymorphism, we develop new vaccination system for polymorphic viruses. Structures of malwares can be analyzed in graph model.
- Subgraph Isomorphism problem: finding the same graphs in graph theory. This problem is one of NP-Hard problems which cannot guarantee the optimal solution in realistic time. We have conducted the early-stage of research which solves the problem using genetic algorithms in realistic time with high probability.
- Develop genetic algorithms for Subgraph Isomorphism problem: Develop faster and more accurate algorithms. Research on reducing processing time, the weakness of genetic algorithms, is required. Based on experiences and significant results on other NP-Hard problems (Graph bisection, Circuit dividing, TSP, etc.) from our lab, we are the most eligible group to proceed the research on this area.
- Develop token-based virus detection algorithm: Token-based approaches try to analyze the program by achieving the token sequence and analyzing the properties of it. These methods are fast but relatively weak against polymorphism. We develop an algorithm which takes the advantages of token-based approach, and used genetic algorithm to improve the accuracy.
3) Develop polymorphic virus detection engines: Based on the algorithms developed, we developed four kinds of engines, which may be executed with controlling the degree of precision.
Expected Contribution
- Develop new vaccination system to detect polymorphic viruses effectively
- Alleviate weakness of domestic vaccination industry and enhance international competitiveness
- Alleviate unavoidable problem, zero-day detection problem, because of un-experienced viruses
- Apply to intrusion detection method
- Apply to software plagiarism detection
- Enlarge the application areas of genetic algorithms

목차 Contents

• 중견연구자지원사업(핵심연구) 최종보고서 ... 1
• 목차 ... 3
• 연구계획 요약문 ... 4
• 연구결과 요약문 ... 5
• 한글요약문 ... 5
• SUMMARY ... 6
• 연구내용 및 결과 ... 7
• 1. 연구개발과제의 개요 ... 7
• 2. 국내외 기술개발 현황 ... 12
• 3. 연구수행 내용 및 결과 ... 14
• 4. 목표달성도 및 관련분야에의 기여도 ... 41
• 5. 연구결과의 활용계획 ... 45
• 6. 연구과정에서 수집한 해외과학기술정보 ... 46
• 7. 주관연구책임자 대표적 연구실적 ... 48
• 8. 참고문헌 ... 49
• 9. 연구성과 ... 51
• 10. 기타사항 ... 56