소셜네트워크와 유전알고리즘을 이용한 빠른 패치 전파 기법

Abstract

온라인 소셜네트워크 사이트 사용자가 늘어남에 따라 온라인 소셜네트워크 사이트를 대상으로 한 공격이 증가하고 있다. 온라인 소셜네트워크 사이트 사용자들 사이에는 강한 연결성을 가지고 있어서 사용자들의 흥미를 끄는 정보가 빠르게 전파 된다. 사용자들의 흥미를 끌게 하는 정보로 위장한 악성코드가 온라인 소셜네트워크 사이트에 퍼질 경우 큰 피해를 일으킬 수 있다. 또한 새로운 유형의 악성코드는 예방하기 어려우며, 최소한의 시간을 소요해서 패치(Patch)를 만들어 배포한다 하더라도 악성코드의 전파가 시작 된 이후에 패치 전파가 시작 된다. 따라서 악성코드의 활동을 억제 시킬 수 있는 빠른 패치 전파 기법이 필요하다. 본 논문에서는 온라인 소셜네트워크를 기반으로 하면서 페이지랭크(PageRank)를 이용한 빠른 패치 전파 기법과 유전알고리즘(Genetic Algorithm)을 이용한 빠른 패치 전파 기법을 제시하고 그 성능을 비교 분석 한다. 제안 기법들에서는 온라인 소셜네트워크 사용자들 간의 교류 관계를 그래프로 표현한다. 페이지랭크를 이용한 기법에서는 먼저 그래프를 분할 후 각 부분 그래프마다 페이지랭크 계산을 통해서 패치 전파에 가장 많이 기여 할 수 있을 것으로 기대되는 사용자들을 찾는다. 유전알고리즘을 이용한 기법에서는 반복적인 유전알고리즘 연산을 통해서 패치 전파에 가장 많이 기여 할 수 있을 것으로 기대되는 사용자들을 찾는다. 선택 된 사용자들에게 1차로 패치를 전달하고 패치를 받은 사용자들은 자신과 교류가 있는 사용자들에게 패치를 전파 한다. 나머지 사용자들도 패치를 받게 되면 자신과 교류가 있는 사용자들에게 패치를 전파 한다. 제안 기법을 검증하기 위해 온라인 소셜네트워크 사용자들의 사용 패턴을 모델링하고 제안된 기법을 구현해서 시뮬레이션 하였다. 시뮬레이션 결과, 사용자들을 무작위로 선택하는 방법과 교류하는 사용자들의 수가 많은 사용자들을 선택하는 방법에 비해서 페이지랭크를 사용하는 방법과 유전알고리즘을 사용한 방법에서 더 빠르게 패치를 전파했음을 확인 할 수 있었다. 또한 유전알고리즘을 사용한 방법이 페이지랭크를 사용하는 방법보다 더 빠르게 패치를 전파했음을 확인 할 수 있었다.