디지털 라이브러리[ 검색결과 ]
극대공통부분서열을 찾는 개선된 알고리즘
http://doi.org/10.5626/JOK.2023.50.9.737
두 문자열의 극대공통부분서열(MCS)은 어떤 문자를 삽입하여도 더 긴 공통부분서열을 만들 수 없는 공통부분서열이다. 최장공통부분서열(LCS)과 달리 MCS의 길이는 다양하고, 가장 긴 MCS가 LCS이다. LCS는 일반적으로 두 서열의 유사도를 비교할 때 사용되지만, 계산하는데 매우 긴 시간이 걸린다. MCS는 LCS보다 빠르게 계산할 수 있으므로 더 긴 MCS를 찾는 문제는 중요하다. 길이의 합이 n인 두 문자열 X와 Y의 MCS 중 하나를 O(n) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 계산하는 알고리즘이 제시되었고 이를 개선한 알고리즘들도 제시되었다. 본 논문에서는 기존의 알고리즘들보다 더 많은 문자를 확인하여, 상수 k가 주어졌을 때 O(kn) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 MCS를 계산하는 알고리즘을 제시한다. 실제 데이터와 무작위로 생성한 데이터를 이용하여 실험을 진행한 결과, 본 논문에서 제시한 알고리즘으로 계산된 MCS의 길이가 기존의 알고리즘으로 계산된 MCS보다, 최대 6.31배 길다.
더 긴 극대 공통 부분 서열을 찾기 위한 알고리즘
http://doi.org/10.5626/JOK.2022.49.7.507
극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 어떤 문자라도 추가하면 더 이상 공통 조건을 만족하지 않는 공통 부분 서열이다. 최근에 두 문자열의 MCS를 찾는 알고리즘이 제시되었는데, 이 알고리즘은 제곱 시간이 걸리는 최장 공통 부분 서열(Longest Common Subsequence, LCS) 계산 알고리즘에 비해 매우 빠르다. 하지만 이 알고리즘에 의해 계산된 MCS는 LCS보다 훨씬 짧다는 것이 실험적으로 밝혀졌다. 본 논문에서는 기존 알고리즘을 개선하여 더 긴 MCS를 찾는 두 가지 알고리즘을 제시하고, 다양한 실제 데이터와 랜덤 생성 데이터에 대한 실험을 통해 성능의 개선을 확인한다. 본 논문에서 제시한 알고리즘은 실제 데이터에서는 1.47～3.17배, 랜덤 데이터에서는 1.50～3.08배 길이의 MCS를 찾는다.
난독화된 악성코드 판별을 위한 2차원 배열 기반의 기술 연구
http://doi.org/10.5626/JOK.2018.45.8.769
일평균 20만개 이상의 악성코드가 출현하고 있으며, 대부분의 침해사고는 악성코드를 이용하여 발생한다. 그런데, 공격자의 악성코드 제작기술이 점차 지능화되고 있으며 역 공학 분석을 방지하기 위해 패킹이나 암호화를 하여 악성코드를 제작한다. 정적 분석의 경우 분석 파일이 난독화가 되면 분석을 하는데 한계가 있으며, 이에 대응할 수 있는 방안이 필요하다. 본 논문에서는 난독화 시에도 악성코드를 판별할 수 있는 방안으로 문자열, 심볼, 엔트로피 기반 접근 방법을 제시하였다. 특히, 고정된 feature-set 뿐 아니라, 고정되지 않은 Feature-set 처리를 위해 2차원 배열을 적용하였으며, 15,000개의 악성/정상 샘플을 DNN(Deep Neural Network)를 통해 검증을 진행하였다. 본 연구는 향후 여러 악성코드 탐지기법과 연계되어 동작 시 보완적인 형태로 동작할 것으로 예상하며, 난독화된 악성코드 변종 분석에서 활용 가능할 것으로 기대한다.
정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘
http://doi.org/10.5626/JOK.2017.44.8.760
반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 δ-근사주기와 최소 γ-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 O(n²)시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 O(n²)개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 δ-근사주기를 계산하는데 약 19.7배, 최소 γ-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다.
가변길이 그램의 역리스트 생성을 이용한 효율적인 유사 문자열 검색 기법
유사 문자열 검색을 위해 기존의 기법들은 우선 후보 문자열 집합을 생성한 후에 후보 문자열을 검증하는 방법을 사용한다. 이때, 유사 문자열 검색의 성능을 결정짓는 가장 중요한 요소는 후보 생성방법이다. 기존의 기법들은 질의 문자열로부터 고정길이 q-그램들을 선택하고, 선택된 q-그램에 해당하는 역리스트를 이용해 후보 문자열을 생성한다. 본 논문에서는 질의 문자열 내의 가변길이 그램들을 사용하여 후보 문자열을 생성할 수 있는 기법과 질의 문자열로부터 최적의 가변길이 그램들의 조합을 선택하는 동적 프로그래밍 알고리즘을 제안한다. 실험을 통해 제안하는 기법이 기존의 기법들 보다 유사 문자열 검색의 성능을 향상시킴을 보인다.
정수문자집합에 대한 문자열의 δ-근사주기와 γ-근사주기
정수로 표현된 문자열에 대한 (δ, γ)-매칭은 음악서열이나 주가 연구에 응용될 수 있다. 본 논문에서는 정수문자집합에 대한 문자열의 δ-근사주기와 γ-근사주기의 개념을 제시한다. 또한 최소 δ-근사주기와 최소 γ-근사주기를 각각 O(n²) 시간에 찾는 알고리즘들을 제시하고 수행시간을 측정한 결과를 보인다.
유사도 검색을 위한 데이터 재배열을 이용한 공간 효율적인 역 색인 기법
유사도 검색에서는 효율적으로 유사성을 만족하는 문자열을 찾기 위해서 데이터에 대한 역 색인을 구축하여 이용한다. 일반적으로 기존의 기법들은 빠른 응답속도의 질의처리를 위해서 역 색인을 메모리에 상주시킨다. 하지만 구축된 역 색인은 그 크기가 매우 크다는 문제점을 가지고 있다. 따라서 데이터의 크기가 매우 큰 경우나 자원이 제약적인 환경에서는 역 색인을 이용한 질의처리가 불가능할 수 있다. 본 논문에서는 동일한 q-그램을 포함하는 문자열들이 서로 인접한 위치가 되도록 재배치시킨 후 해당 문자열들을 범위로 표현한다. 실험을 통하여 질의처리의 성능을 희생하지 않으면서도 색인의 크기가 줄어드는 것을 보인다.
실행시간 침입 방지 평가 프로그램(RIPE)의 개선
이현규, 이담호, 김태환, 조동황, 이상훈, 김훈규, 표창우
2011년에 발표된 RIPE는 프로그램 공격에 대한 완화 기법 평가 도구로서 850 가지 패턴의 버퍼 오버플로우 기반 공격에 대한 완화 기법만을 평가한다. RIPE는 공격과 방어 루틴이 하나의 프로세스로 실행되도록 구성되어, RIPE가 실행될 때에는 공격과 방어 루틴이 프로세스 상태와 주소 공간 배치를 공유할 수밖에 없게 된다. 그 결과 공격 루틴은 방어 루틴의 메모리 공간을 아무런 제약 없이 접근할 수 있게 된다. 이 논문에서는 RIPE의 공격과 방어 루틴이 독립적인 2개의 프로세스로 동작하도록 하여 주소 공간배치 난독화와 같은 기밀성에 근거한 방어 기법을 정확히 평가할 수 있도록 개선하였다. 또한 억지 공격에 대한 방어 능력을 실험할 수 있도록 실행 모드를 추가하였다. 마지막으로 vtable 포인터 공격과 형식문자열 공격을 수행하도록 38 가지 패턴의 공격을 추가하여 확장하였다. 개선 결과 공격 패턴이 다양하게 되었고, 보호 효과 평가의 정확성도 높아졌다.
환형문자열에 대한 대표문자열을 찾는 병렬 알고리즘
대표문자열 문제는 k 개의 문자열로 구성된 집합 S 가 주어졌을 때 S 를 대표하는 한 문자열인 대표문자열을 찾는 문제이다. 환형문자열은 일반적인 문자열과는 달리 문자열의 첫 글자와 마지막 글자가 연결되어 원 모양을 이루는 문자열이다. 본 논문에서는 먼저 k=3 이고 길이 n인 환형문자열들로 구성된 S에 대해, 거리반경과 거리합을 동시에 고려한 대표문자열 문제를 O(n) 개의 쓰레드를 사용하여 O(｜∑｜nlogn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이때, ∑ 는 각 문자열을 구성하는 문자집합이다. 다음으로 k=4 이고 길이 n인 환형문자열들로 구성된 S 에 대해 거리합 기반 대표문자열 문제를 O(n)개의 쓰레드를 사용하여 O(｜∑｜n²logn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이후 두 문제에 대한 병렬 알고리즘들을 CUDA를 이용하여 구현하고 순차 알고리즘들과의 실행 속도를 비교한 결과를 제시한다.
