Journal of KIIT. Vol. 12, No. 4, pp. 81-88, Apr. 30, 2014. pissn 1598-8619, eissn 2093-7571 81 http://dx.doi.org/10.14801/kiitr.2014.12.4.81 비율 기반 대표 해시 기법을 이용한 파일 유사도 평가 시스템 유영준*, 김선정**, 김 진*, 고영웅*** File Similarity Evaluation System Using Rate-based Representative Hash Scheme Young-Jun Yoo*, Sun-Jeong Kim**, Jin Kim*, and Young Woong Ko*** 이 논문은 교육과학기술부의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임(No.2012R1A1A2044694) 요 약 파일 유사도 기법은 중복제거와 디지털 포렌식 분야에서 널리 사용되고 있다. 일반적으로 유사도 검색을 위 해서는 계산 및 메모리 오버헤드가 발생이 되며, 다수의 파일을 처리함에 있어서 일대일 해시 값 비교는 매우 비효율적이다. 본 논문에서는 빠르고 효율적인 파일 비교를 위해서 비율에 기반한 대표 해시 기법을 제안한다. 파일 유사도를 계산하기 위해서 파일은 다수의 청크로 분할되며, 각 청크의 해시 값이 계산된다. 상위 해시 값 을 선택하고 이를 비교함으로 두 개 파일간의 유사도를 구할 수 있다. 제안하는 기법에 대한 유용성을 보이기 위하여 ssdeep, sdhash 그리고 VLC(variable-length chunking)와 비교하는 실험을 진행하였다. 실험 결과 파일 유사도의 정확도가 향상되고 수행 시간도 단축되었음을 알 수 있었다. Abstract The file similarity scheme is widely used in various fields including data deduplication and digital forensics. Usually similarity search requires huge computation time and memory space, so all-to-all hash comparison is infeasible for large collection of files. As a fast and efficient file comparison mechanism, we exploit rate-based representative hash scheme. To generate file similarity value, a file is divided into several chunks and fingerprint of each chunk is calculated. In this paper, by selecting and comparing top hash values, we can measure the file similarity between two files. We compared the performance of the proposed scheme with ssdeep, sdhash and variable-length chunking. We showed that we can considerably improve the execution time to search file similarity with a good accuracy. Keywords representative hash, file similarity, chunk, deduplication * 한림대학교 컴퓨터공학과 ** 한림대학교 유비쿼터스 컴퓨팅학과 *** 한림대학교 컴퓨터공학과(교신저자) 접 수 일: 2014년 01월 29일 수정완료일: 2014년 02월 19일 게재확정일: 2014년 02월 22일 ž Received: Jan. 29, 2014, Revised: Feb. 19, 2014, Accepted: Feb. 22, 2014 ž Corresponding Author: Young-Woong Ko Dept. of Computer Engineering, Hallym University, Chuncheon, Gangwondo, 200-702, Korea, Tel.: +82 33 248-2329, Email: yuko@hallym.ac.kr
82 비율 기반 대표 해시 기법을 이용한 파일 유사도 평가 시스템 Ⅰ. 서 론 파일 유사도는 파일간의 유사한 정도를 나타내는 수치로 파일의 중복제거나 악성코드 검출 등에 사 용된다. 특히 클라우드 환경의 효율성을 높이기 위 한 파일 중복제거 분야에서 파일의 유사도 정보를 이용하여 효율적으로 중복 데이터를 제거할 수 있 다[1]-[3]. 중복제거는 파일을 저장할 때 다른 파일 과 동일한 부분을 찾아 동일한 부분은 저장하지 않 고 서로 다른 부분에 대해서 저장을 하는 기법이다. 대량의 파일을 관리하는 클라우드 시스템에서 중복 제거는 저장장치의 효율성을 크게 증가시키기 위한 용도로 사용된다. 또한 네트워크 데이터 전송이 제 한적인 모바일 환경에서 효율적인 중복제거는 서버 로 보내는 데이터의 양을 줄일 수 있다는 장점이 있다. 만약 클라우드 서버에 유사한 파일이 여러 개 있을 경우, 이 중 가장 유사한 파일과 파일 동기화 작업을 수행한다면, 서버로 전송하는 데이터의 양은 크게 줄어들 것이다. 하지만 효과적으로 파일 유사도를 평가하는 것은 어려운 일이다. 일반적으로 파일을 고정/가변 분할 하여 해시 연산을 수행하는 방법을 사용하는 경우 에, 해시 값은 파일의 크기에 비례해서 증가하므로 유사도 연산에 소요되는 계산 시간 및 메타 데이터 저장 공간의 증가가 필수적이다[1]. 클라우드 서버 는 대량의 파일을 처리하고 있으며, 각 파일에 대해 서 유사도 처리를 위한 정보를 생성하여 메모리에 보관하는 경우에 대규모의 물리 메모리가 필요하게 된다. 또한 많은 비교 연산을 수행해야 하기 때문에 파일의 유사도를 찾는 과정에서도 많은 시간이 소 요된다. 정보보안 분야에서도 파일의 유사도 정보는 효율 적으로 사용될 수 있다[4]. 악성코드를 검출해야 하 는 경우 특정 악성코드에 대한 해시 정보들과 감염 의심파일을 비교해 일치하는 해시 값이 발견될 경 우 해당 파일은 악성코드에 감염됐다고 판단할 수 있다. 그리고 악의적인 공격이나 물리적인 충격으로 인해 저장장치가 손상을 입고 파일의 정보가 훼손 됐을 경우에도 파일의 유사도 정보는 효율적으로 사용될 수 있다. 저장장치의 각 섹터에 저장된 정보 들을 읽어 해시 연산을 하고 이 값들을 다른 파일 과 비교하면 하드디스크의 저장됐던 정보의 내용을 추측할 수 있다. 이런 경우 파일의 유사도 정보는 높은 정확도가 함께 요구된다. 정확도가 낮을 경우 악성코드를 제대로 검출하지 못하거나 저장장치의 내용을 제대로 복원할 수 없기 때문이다. 따라서 본 논문에서는 빠른 수행속도와 높은 정 확도를 보이는 비율에 따른 대표 해시를 제안한다. 비율에 따른 대표 해시는 전체 해시 값 중 사용자 가 지정한 비율에 따라 일정 개수의 해시 값만 남 기고 나머지 해시 값은 삭제하는 방식이다. 일부의 해시 값으로 파일을 대표하기 때문에 메모리의 사 용량은 크게 줄어들며, 해시 값의 비교연산의 속도 가 크게 향상된다. 또한 실험 결과에서 볼 수 있듯 이, 현재 널리 사용되고 있는 유사도 평가 소프트웨 어인 ssdeep나 sdhash[4]에 비해서도 더 높은 성능을 보이는 장점이 있다. 본 논문의 구성은 다음과 같다. 2장 관련연구에 서는 일반적으로 사용되는 파일 유사도의 비교 방 법과 리눅스에서 파일의 유사도를 판별하는 상용 툴에 대해 설명한다. 3장 시스템 설계 및 구현에서 는 비율에 따른 대표 해시의 구성에 대해 설명한다. 4장 실험 및 고찰에서는 비율에 따른 대표 해시를 타 연구 내용과 성능의 관점에서 비교하며, 마지막 으로 5장에서 결론을 맺는다. Ⅱ. 관련 연구 전체 파일 해싱은 파일의 전체 내용을 SHA1이나 MD5와 같은 해시 연산을 통해 하나의 해시 값으로 생성하는 방식이다. 하나의 파일을 통째로 해싱하기 때문에 파일의 내용 일부만 바뀌어도 해시 값이 크 게 변한다. 따라서 작은 수정에도 두 파일은 완전히 다른 파일이라고 판단할 수 있다. 전체 파일 해싱의 단점을 보완하기 위해 사용되는 방법이 부분 파일 해싱이다. 파일을 각 부분으로 나누고 나눠진 부분 별로 해싱을 수행한다. 블록을 나눠 해시 연산을 수 행함으로 각 해시 값은 블록에 대한 정보를 대표하 며, 이 해시 값들을 비교하는 경우 파일의 수정된 위치를 알 수 있다.
Journal of KIIT. Vol. 12, No. 4, pp. 81-88, Apr. 30, 2014. pissn 1598-8619, eissn 2093-7571 83 파일 부분 해싱은 파일을 나누는 기준에 따라 FLC(Fixed Length Chunking)[5]과 VLC(Variable Length Chunking)[3]으로 나뉜다. FLC는 파일을 일정한 바 이트 크기로 나눠 블록에 대한 해시 연산을 수행한 다. 비교적 빠른 수행속도를 보이지만, 데이터 수정 이 발생할 경우 수정된 위치를 기준으로 이후의 데 이터 모두 수정됐다고 판단할 수 있는 문제가 있다. 반면 VLC는 롤링해시(rolling hash)[6]와 MD5나 SHA1해시를 함께 사용한다. 롤링해시를 이용해 특 정 해시 값이 나오는 블록을 기준으로 다시 MD5나 SHA1 해시 연산을 수행한다. 데이터의 변경이 있어 도 롤링해시는 조건에 맞춰 블록을 나누기 때문에 높은 정확도를 보이는 반면 추가적인 연산 시간을 갖는다. 파일을 부분적으로 나눠 해시 연산을 할 경 우 해시 값의 수는 크게 증가하며 동시에 메모리의 사용량도 크게 증가한다. 특히 해시 값의 수가 증가 하기 때문에 파일간의 해시 값을 비교하는 과정에 서 오랜 수행시간을 보일 수 있다. Xdelta는 파일의 유사도를 판별하고 파일의 변경 사항을 다른 파일에 적용할 때 사용하는 방법으로, 게임의 패치 과정 등에서 사용되는 방식이다. 새로 운 버전의 파일과 오래된 파일에 대해 델타 파일 (delta)이 생성되고 이 파일을 오래된 파일에 적용하 는 과정에서 게임을 패치 한다. 하지만 Xdelta는 파 일이 크기가 커질수록 오차가 커지는 단점이 있다. ssdeep는 VLC와 같은 개념을 이용해 파일에 대해 롤링해시와 MD5 해시를 함께 수행한다. 한 바이트 를 읽으며 두 개의 해시 값을 업데이트 시켜나가며 롤링해시 값이 특정 포인트를 가리키는 값이 될 경 우 생성된 MD5의 값을 64base인코딩을 이용해 6비 트만 추출한다. 이때 생성된 6비트 값들을 합쳐 하 나의 문자열을 생성하고 이때 생성된 문자열은 파 일을 대표하는 해시 값이 된다. 최종적으로 생성된 해시 값은 상당히 작기 때문에 메모리의 사용량은 적으며 파일을 비교하는 과정에서도 빠른 수행속도 를 보인다. 하지만 파일을 대표하는 스트링을 생성 하는 과정에서 여러 개의 해시 스트링이 생성되고 이 중 하나의 스트링만 가지고 파일을 대표하는 방 식을 사용하기 때문에 큰 오차를 보이거나, 일부 파 일에 대해서는 아예 유사도를 찾지 못하는 경우가 존재한다. sdhash는 파일을 일정한 크기로 나눠 블 룸 필터에 추가한다. 블룸 필터[7]는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조로써 공간 효율적으로 빠르게 검색할 수 있는 장점이 있다. 각 블록에 대한 정보를 모두 블룸필터 에 추가하고 나면 블룸필터끼리 비교 연산을 수행 해 파일의 유사도를 판별한다. 하지만 블룸필터에 해시 값을 추가하고 이를 비교하는 과정에서 연산 속도가 떨어지는 단점이 있다. 또한 델타 인코딩에 기반을 둔 중복제거 기술은 최근에 CDN(Content Delivery Network)과 같은 분야 에서 데이터 전송을 위한 효율적인 방법으로 널리 사용되고 있다[8][9]. 이외에도 데이터 중복 제거를 이용하여 효율적으로 멀티미디어 편집 시스템을 개 발한 사례[10], 앵커 기반 파일 유사도 예측을 통한 효율적인 파일 중복 제거 기법[11], 콘텐츠에서 중 복을 효과적으로 찾아주는 기술[12] 그리고 멀티 클 라우드 기반의 저장 시스템[13] 등이 사용되고 있다. Ⅲ. 시스템 설계 및 구현 3.1 유사도 평가 시스템 유사도 평가 시스템은 파일의 유사도를 비교하 고, 정보를 출력해주는 시스템이다. 그림 1에서 알 수 있듯이 비교하고자 하는 파일과 대상 파일들이 저장되어 있는 디렉터리를 지정하면 해당 모든 파 일들에 대해 해시 연산을 수행한다. 해시 연산이 끝 난 후 각 파일 간 해시 값을 비교하며 입력 파일과 디렉터리 내의 파일간의 유사도를 계산한다. 본 연 구에서는 유사도의 정확도를 높이기 위해 FLC를 사용하지 않고 VLC를 사용한다. 본 연구에서는 대표 해시 값을 기반으로 파일 유 사도를 평가하는 것을 핵심 아이디어로 한다. 즉, 각 파일을 구성하는 블록/청크의 해시 값들 중에서 상위 일부의 해시 값을 대표 해시로 선택하고 각 파일의 대표 해시들의 중복 여부를 비교하여 파일 의 유사성을 평가하는 방법이다.
84 비율 기반 대표 해시 기법을 이용한 파일 유사도 평가 시스템 그림 1. 유사도 평가 시스템 개요도 Fig. 1. Overall architecture of similarity evaluation system 본 논문에서 제안하는 비율 기반 대표 해시 방법 은 대표 해시를 생성하는 과정에서 일정한 비율의 대표 해시를 지정하는 것으로 전체 해시 값을 모두 사용하는 방식의 오버헤드를 제거하기 위해서 도입 이 되었다. 전체 해시 값을 이용하여 파일의 유사도 를 비교하는 것은 대용량의 메모리를 요구하고 계 산 과정에서 CPU 자원을 집중적으로 소모하는 문 제를 발생시킨다. 따라서 비율 기반 대표 해시 기법 은 유사도 평가를 위하여 주어진 비율에 해당하는 대표 해시만 저장하고 나머지 해시 값은 사용하지 않는 방법이다. 만약 각각 크기가 다른 두 개의 파 일에서 10만개와 5만개의 해시 값이 생성되고, 이중 선택하는 비율이 10%일 경우 각각 1만개와 5천개 의 대표 해시만 남기고 나머지 해시 값들은 모두 삭제한다. 그림 2는 비율에 따른 대표 해싱에서 해시 값을 선택하는 방법을 보인다. 예를 들어 총 100개의 해 시 값이 생성됐고, 이중 10%인 10개의 대표 해시를 생성해야 한다면 이 해시 값들을 내림차순으로 정 렬한 후 이 중 10개의 해시 값만 선택한다. 정렬을 할 경우 해시 값을 비교하는 과정에서 좀 더 빠르 게 비교할 수 있는 장점이 있다. 그림 2. 대표 해시 생성 방법 Fig. 2. Representative hash generation scheme 3.2 대표 해시 선출 알고리즘 그림 3의 알고리즘은 대표 해시 값을 선택하는 방법을 보인다. 파일에서 생성된 해시 값의 리스트 와 대표 해시 비율(ratio)이 매개변수로 전달되며 전 체 해시 값의 개수 중에서 비율에 따라 대표 해시 값의 개수를 계산한다. 그 다음 해시 리스트의 값을 오름차순으로 정렬하고, 개수만큼 대표 해시 배열을 복사함으로써 대표 해시 값을 추출한다. 본 알고리 즘에서 Sort() 함수는 해시 값 리스트를 입력으로 받아서 정렬을 수행하며, Ratio로 지정된 비율 값에 따라서 대표해시의 개수를 정한다. 대표 해시의 개 수가 정해지면 정렬된 대표 해시의 값이 복사되어 비율 기반 대표 해시 리스트가 생성된다.
Journal of KIIT. Vol. 12, No. 4, pp. 81-88, Apr. 30, 2014. pissn 1598-8619, eissn 2093-7571 85 Ⅵ. 실험 및 고찰 그림 3. 대표 해시 생성 알고리즘 Fig. 3. Representative hash generation algorithm 대표 해시의 사용은 메모리 사용량을 감소시키는 장점이 있다. SHA1을 사용함으로써 20바이트(Byte) 의 해시 값이 생성된다. 만일 100개의 해시 값이 생 성된다면 일반 VLC는 파일 1개당 2KB의 메타 데 이터가 생성된다. 하지만 대표 해시를 사용할 경우 200바이트의 대표 해시가 생성된다. 클라우드 시스 템과 같이 대용량의 시스템에서 많은 메타 데이터 정보를 메모리에 저장할 경우 메모리의 사용량은 크게 증가하며, 물리 메모리의 제약으로 인해 시스 템의 성능이 크게 저하된다. 따라서 클라우드 시스 템과 같이 대규모 파일을 가지고 있는 저장 시스템 에서 메타 데이터의 용량을 줄이는 것은 시스템 성 능 향상에 매우 중요한 기여를 하게 된다. 3.2 유사도 계산 방법 두 파일 간의 실제 유사도는 파일 간에 중복 데 이터의 비율을 의미한다. 즉 전체 파일 중에서 30% 의 데이터가 중복이 된 경우에 30%의 유사도가 있 다고 얘기할 수 있다. 본 논문에서는 실제 데이터 내부의 중복 데이터의 비율을 알 수 없기 때문에 대표 해시에 있는 파일의 특징 정보를 통해서 실제 파일간의 유사도를 유추하는 방법을 사용한다. 즉, 소스 파일과 타겟 파일의 대표 해시 값의 중복 비 율로 정의한다. 소스 파일에서 100개의 대표 해시 값을 선출하고 타겟 파일에서 100개의 대표 해시 값을 선출하였을 때, 대표 해시 값 중에서 동일한 해시가 존재하는 비율을 파일 유사도 값으로 사용 한다. 따라서 유사도 100개의 대표해시 중에서 100 개가 동일하다면 100% 동일한 파일을 의미하며, 30 개의 대표해시가 중복이 되어 있는 경우에 두 파일 간에 중복된 블록이 30% 존재할 것으로 예측한다. 본 실험은 표 1과 같은 환경에서 진행하였으며, 각 데이터는 리눅스 상에서 dd 명령어를 사용해 만 들어 졌다. 100MB파일의 경우 1개의 원본 파일과 10%단위로 변경된 9개의 파일 그리고 추가적으로 유사하지 않은 18개의 파일을 추가하여 총 28개의 파일을 비교하는 실험을 진행하였고, 1GB파일은 원 본파일 1개와 마찬가지로 10%단위로 변경된 9개의 파일을 비교였다. 표 1 실험 환경 Table 1. Experiment environment 운영체제 Linux 2.6.43.8-1 CPU Memory Platform Intel Xeon E5520 @ 2.27GHz 8GB C, C++ 클라우드 환경에서 대용량의 파일을 백업한 경우 와 작은 이미지파일 등을 업로드 했을 경우 등 다 양한 환경에서 본 시스템의 타당성을 증명하기 위 해 실험을 진행하였다. 각 파일은 가변 길이 청킹 방식을 이용해 해시 연산을 수행했으며 해시 값을 생성하는 시점부터 비교하는 연산까지 시간을 측정 하였다. 표 2는 일반 VLC의 성능을 보이는 표이다. 100MB 파일 10개를 비교할 경우 약 1분 23초로 비 교적 빠른 수행속도를 보이고 있다. 하지만 1GB파 일을 10개 비교할 때는 36분이 넘는 시간을 보이며 매우 느린 수행속도를 보인다. 작은 파일이 많아 해 시 값이 증가하는 경우에도 수행 시간은 길어진다. 100MB파일 28개를 비교하는 과정에서도 4분이 넘 는 속도를 보이며 수행시간이 증가했으며, 이보다 더 많은 파일과 비교할 때는 더 오랜 시간이 걸릴 것이다. 표 2. 일반 VLC 수행 속도와 오차 Table 2. Execution time and error variation of general VLC algorithm 시간 평균 오차 100MB(10개) 1분 23초 2.3% 100MB(28개) 4분 9.1초 2.3% 1GB(10개) 36분 21.71초 0.14%
86 비율 기반 대표 해시 기법을 이용한 파일 유사도 평가 시스템 표 3. 대표 해시 성능(100MB파일 10개) Table 3. Performance of representative hash scheme(10 files with 100MB size) 비교 시간 일반 VLC 1분 23초 2.3% 대표 해시(10%) 1분 5.8초 1.64% 대표 해시(1%) 1분 5.7초 3.05% 비교 시간 일반 VLC 3분 54초 2.3% 대표 해시(10%) 3분 4초 1.64% 대표 해시(1%) 3분 3.92초 3.05% 평균 오차 표 4. 대표 해시 성능(100MB파일 28개) Table 4. Performance of representative hash scheme(28 files with 100MB size) 평균 오차 표 5. 대표 해시 성능(1GB파일 10개) Table 5. Performance of representative hash scheme(10 files with 10GB size) 비교 시간 평균 오차 일반 VLC 36분 22초 0.15% 대표 해시 10% 11분 27초 0.54% 대표 해시 1% 11분 15초 2.19% 표 3, 4, 5는 각각 100MB파일 10개, 28개 그리고 1GB파일 10개를 비교하는 과정에서 비율에 따른 대표 해시를 적용하고 실험한 결과이다. 100MB파 일을 10개 비교하는 실험에서 일반 VLC의 수행속 도는 약 1분 23초를 보였지만 대표 해시를 10%로 지정했을 경우 1분 5.8초로 실행시간이 줄어들었다. 또한 대표 해시를 1%로 지정했을 경우 1분 5.7초를 보였다. 파일 28개를 비교하는 실험에서도 대표 해 시를 10% 지정했을 때는 3분 4초, 1% 지정했을 경 우 3분 3.92초를 보였다. 특히 1GB파일을 비교할 때 일반 VLC는 36분이 넘는 수행시간을 보였지만 대표 해시를 적용했을 경우 각각 11분 27초, 11분 15초를 보이며 수행시간이 크게 줄어들었다. 따라서 본 실험을 통하여 파일 용량과 개수에 대한 상호 관계에 있어서 파일 용량이 증가할수록 제안하는 기법은 일반 VLC와 비교하여 성능이 크게 증가하 며, 비율의 관계에 있어서는 수행 시간은 큰 차이가 나지 않지만 평균 오차에 있어서 두 배 정도의 차 이를 보이고 있다. 또한 파일의 크기가 커짐에 따라 서 이와 같은 대표 해시 비율에 따른 오차가 크게 줄어들고 있다. 따라서 큰 파일에 대해서는 일반 VLC와 비교하여 매우 우수한 성능을 보이고 평균 오차도 크게 줄이는 방법이라는 것을 알 수 있다. 앞선 결과에서는 해시 값의 생성 모듈과 비교 모 듈의 수행속도를 모두 측정하였기 때문에 줄어든 시간의 폭이 크지 않다. 표 6은 비교 모듈의 수행시 간만을 측정한 결과를 보이고 있으며, 해시 값의 줄 어듦에 따라 비교 속도가 현저하게 빨라지고 있음 을 보인다. 표 6. 수행 시간 측정 결과 Table 6. Execution time evaluation result 대표 해시 비율(%) 50 10 1 비교 모듈 수행시간(초) 9.89 0.388 0.039 하지만 대표 해시의 비율이 줄어들수록 평균 오 차와 표준편차는 크게 증가한다. 그림 4는 대표 해 시 비율에 따른 평균 오차와 표준편차를 보이고 있 다. 대표 해시의 비율이 줄어들수록 대표 해시 값이 파일 내에서 고르게 선택될 확률은 낮아진다. 대표 해시의 비율이 50%일 경우 평균 오차는 2% 미만이 고, 표준 편차 역시 크지 않다 하지만 대표 해시의 비율이 1%일 경우 평균오차는 3% 근방으로 증가하 였고 표준 편차의 범위도 약간 증가하였다. 대표 해 시의 비율을 0.1%로 매우 작게 선택했을 경우 평균 오차는 10% 이상을 보였고 표준편차 역시 매우 크 게 증가한 모습을 보이고 있다. 따라서, 본 실험을 통하여 1% 근방의 비율이 가장 적정한 값으로 추 론할 수 있다. 그림 4. 대표 해시 비율에 따른 평균 오차 Fig. 4. Standard error variation varying representative hash ratio
Journal of KIIT. Vol. 12, No. 4, pp. 81-88, Apr. 30, 2014. pissn 1598-8619, eissn 2093-7571 87 표 7. 리눅스 툴과 비교 결과 Table 7. Comparison analysis with linux tools 평균 오차 대표 해시 3% ssdeep 14% sdhash 8% 표 7에서 볼 수 있듯이, 상용 리눅스 툴과 비율 에 따른 대표 해시를 측정한 결과, ssdeep는 정확도 에 있어서 매우 낮은 결과를 보였다. sdhash는 ssdeep과 비교하여 우수한 성능을 보이나 8% 근방 의 오차를 보이고 있다. 반면 비율에 따른 대표 해 시는 파일 내부의 중복 비율에 관계없이 3% 근방 의 오차율을 보이고 있다. 그림 5. 상용 툴과 수행시간 비교 Fig. 5. Execution time analysis with commercial tools 그림 5는 기존의 알고리즘과 비율에 따른 대표 해시의 수행 시간을 비교한 그래프이다. sdhash와 비교 했을 때 대표 해시 기법이 더 빠른 성능을 보 였다. 하지만 제안하는 기법은 ssdeep에 비해서 수 행시간이 더 소요되었다. 따라서 제안하는 방식이 기존 알고리즘에 비해서 수행 시간은 중간 정도의 결과를 보이지만 정확도 부분에서는 높은 성능을 보여주는 것으로 결론 내릴 수 있다. Ⅶ. 결론 및 향후연구 본 논문에서는 높은 정확도를 보이며 빠르게 파 일의 유사도를 판별하기 위해 비율에 따른 대표 해 시를 제안하였다. 비율에 따른 대표 해시는 파일을 부분적으로 해시 연산을 한 후 전체 해시 값 중 일 정 비율의 해시 값만 저장하는 방법이다. 실험 결 과, 대표 해시 값이 줄어듦에 따라 비교 연산이 빨 라지나 정확도 오차가 증가함을 확인하였다. 실험에 서 1%의 비율로 대표 해시를 선택하는 것이 처리 속도와 오차율을 고려하여 가장 우수한 성능을 보 이는 것을 확인하였다. 또한 기존의 유사도 측정 툴 들과 성능 비교를 수행한 결과 정확도가 제안하는 방식이 처리속도는 평균적이지만 정확도는 높일 수 있음을 보였다. References [1] D. Bhagwat, K. Eshghi, D. D. E. Long, and M. Lillibridge, "Extreme binning: Scalable, parallel deduplication for chunk-based File backup", In Proceedings of the 17th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS `09), pp. 1-9, Sep. 2009. [2] Cezary Dubnicki, Leszek Gryz, Lukasz Heldt, Michal Kaczmarczyk, Wojciech Kilian, Przemyslaw Strzelczak, Jerzy Szczepkowski, Cristian Ungureanu, and Michal Welnicki, "Hydrastor: a scalable secondary storage", In FAST, Vol. 9. pp. 197-210, Feb. 2009. [3] D. T. Meyer and W. J. Bolosky, "A study of practical deduplication", In Proceedings of the 9th USENIX conference on File and storage technologies (FAST), Vol. 7, No. 3, pp. 4, Jan. 2012. [4] Vassil Roussev, "An evaluation of forensic similarity hashes", Digital Investigation, Vol. 8, pp. S34-S41, Aug. 2011. [5] Sean Quinlan and Sean Dorward, "Venti: a new approach to archival storage", In Proceedings of the 1st USENIX conference of File and storage technologies, Vol. 2, pp. 89-101, Jan. 2002. [6] M. O. Rabin, "Fingerprinting by random polynomials", Technical Report TR-15-81. Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. pp. 15-18, 1981.
88 비율 기반 대표 해시 기법을 이용한 파일 유사도 평가 시스템 [7] Broder, Andrei and Michael Mitzenmacher, "Network application of bloom filters : A survey", Internet Mathematics, pp. 636-646, 2002. [8] Noh Dae-Hee, You Dae-Young, and An Beong- Ku, "A Solution Method for DDoS Attack using CDN Technology", The Journal of IIBC, Vol. 9 No. 2, pp. 91-96, April 2009. [9] Jong-Hae Jung, Gun-Young Oh, Nam-Kyung Lee, Chang-Woo Yoon, Hyun-Woo Lee, Won Ryu, and Sung-Chang Lee, "Architecture and Server Selection for DHT-based Distributed CDN", The Journal of IIBC, Vol. 11, No. 5, pp. 217-228, Oct. 2011. [10] Seung-Ho Lim, "Efficient Multimedia Editing System with Duplicate Elimination", Journal of KIIT, Vol. 8, No. 9, pp. 21-27, Sep. 2010. [11] Ho Min Jung and Young Woong Ko, "Design and Implementation of Deduplication System Using Anchor-based File Similarity Prediction", Journal of KIISE Computer Systems and Theory, Vol. 39, No. 5, pp. 298-305, Dec. 2012. [12] Xie Fei, Condict Michael, and Shete Sandip, "Estimating Duplication by Content-based Sampling", Proceedings of the 2013 USENIX Conference on Annual Technical Conference, pp. 181-186, June 2013. [13] Seung Je Park and Heeyoul Kim, "Design and Implementation of a Secure Data Storage System for Corporations using Multi-clouds", Journal of KIIT, Vol. 11, No. 3, pp. 151-157, March 2013. 저자소개 유 영 준 (Young-Jun Yoo) 2012년 2월 : 한림대학교 컴퓨터공학 졸업(공학사) 2012년 3월 ~ 현재 : 한림대학교 컴퓨터공학 석사과정 관심분야 : 운영체제, 클라우드 스토리지, 가상화시스템 김 선 정 (Sun-Jeong Kim) 1996년 8월 : 고려대학교 컴퓨터과학과(이학사) 1998년 8월 : 고려대학교 컴퓨터과학과(이학석사) 2003년 2월 : 고려대학교 컴퓨터과학과(이학박사) 2005년 3월 ~ 현재 : 한림대학교 유비쿼터스 컴퓨팅학과 부교수 관심분야 : 컴퓨터 그래픽스, 3차원 그래픽 게임 엔진, 가상 현실, GP-GPU 프로그래밍 김 진 (Jin Kim) 1978년 ~ 1984년 : 고려대학교 물리학과 졸업(이학사) 1988년 ~ 1990년 : Computer Science, Michigan State University (공학석사) 1990년 ~ 1996년 : Computer Science, Michigan State University(공학박사) 1997년 ~ 2000년 : 건국대학교 전산과학과 2000년 ~ 현재 : 한림대학교 컴퓨터공학 교수 관심분야 : 생물정보학, 알고리즘, 컴퓨터 응용 고 영 웅 (Young Woong Ko) 1997년 2월 : 고려대학교 컴퓨터학과 졸업(이학사) 1999년 2월 : 고려대학교 대학원 컴퓨터학과(이학석사) 2003년 2월 : 고려대학교 대학원 컴퓨터학과(이학박사) 2003년 9월 ~ 현재 : 한림대학교 컴퓨터공학 교수 관심분야 : 운영체제, 임베디드 시스템, 가상화, 클라우드 스토리지