earticle

영어

String inclusion and non-inclusion related problems are studied in many fields such as data compression, computer security, molecular biology, and etc. Most well-known notions are shortest common superstrings, longest common substrings, longest common non-superstrings, and shortest common non-substrings. Given a set of strings F over a constant size alphabet, consider a string F such that F does not include any string in F as a substring. We call x a common non-superstring (CNSS for short) of F. Among the CNSS's of F , the longest one with finite length is called the longest common non-superstring (LCNSS for short) of F. The LCNSS problem and its solutions based on graph models can be applied to the intrusion detection system which detects malicious patterns in the packets. We can set malicious patterns as F and run the solutions to detect the patterns in the network. As these kinds of malicious patterns increase, F needs to be changed frequently. We can reconstruct the graph that models the CNSS and run the solutions again for the changed set F′. But due to the long graph construction time, this approach may not be an efficient solution. In this paper, we introduce the dynamic LCNSS problem: Given a set of strings F and a graph that models the CNSS for F, find the LCNSS for the modified set F′ constructed by inserting one or more strings into or deleting one or more strings from the original set F. We present an algorithm for the dynamic LCNSS problem and show the effectiveness of our algorithm by experimental analyses.

한국어

문자열 포함 및 불포함 관련 문제는 압축 알고리즘, 컴퓨터 보안, 분자생물학 등 많은 분야에서 필요성이 대두되어 연구가 진행되고 있다. 대표적으로 최단공통상위문자열, 최장공통부분문자열, 최장공통비상위문자열, 최단공통비부분문자열 등이 연구되어 왔다. 문자열 집합 F의 모든 문자열들을 포함하지 않는 문자열을 공통비상위문자열이라 하는데 이들 중 가장 긴 문자열을 F의 최장공통비상위문자열(Longest Common Non-Superstring, LCNSS)이라 한다. LCNSS 문제 및 그래프를 이용한 해결 알고리즘은 컴퓨터보안 분야에서 패킷 내의 악성 패턴 등을 검출하는 침입탐지시스템에 활용될 수 있다. 악성 패턴으로 알려진 문자열들을 F로 정의하고 네트워크 내의 패킷 내에 악성 패턴(문자열)이 존재하면 이를 검출하는 것이다. 그런데 이러한 악성 패턴들은 계속해서 증가하고 있으며 이에 따라 F의 원소들은 계속해서 변경될 수 있다. F에 한 문자열이라도 추가되거나 삭제될 경우 LCNSS를 구하기 위해서 그래프를 재생성한 뒤 기존의 알고리즘을 적용하면 해결할 수 있지만 그래프를 생성하는데 시간이 많이 필요하므로 이러한 방법은 효율적이라 할 수 없다. 본 논문에서는 F에 하나 이상의 문자열을 추가 또는 삭제한 후 변경된 문자열 집합에 대한 LCNSS를 구하는 동적최장공통비상위문자열 문제를 정의하고, 접두사 기반의 그래프 모델에서 변경된 문자열 집합에 대한 그래프를 재생성하지 않고 기존의 그래프에서 일부분만 변경하여 LCNSS를 찾는 알고리즘을 제시한다. 또한 실제 구현 및 실험을 통해 본 논문에서 제시된 알고리즘이 기존의 알고리즘을 이용했을 때보다 성능이 우수함을 보인다.