퍼지 해시 편집하기

퍼지 해시(fuzzy hashing, 또는 similarity hashing)는 입력 데이터가 완전히 일치하지 않더라도 유사한 경우를 감지할 수 있도록 설계된 해시 기법이다. 일반 해시 함수(예: SHA-256, MD5)처럼 입력이 조금만 바뀌어도 해시 값 전체가 완전히 달라지는 성질(아발란체 효과)을 지향하지 않고, 유사한 입력에 대해서는 유사한 해시 값을 만드는 특성을 갖는다.
==정의 및 배경==
퍼지 해시는 ‘비슷하지만 동일하지 않은’ 데이터를 비교하거나 탐지하기 위한 해시 방식이다.  즉, 두 개의 입력이 완전히 동일하지 않아도 어느 정도 유사성이 있다면, 퍼지 해시는 그 유사성을 반영한 해시 결과를 만들어 준다.  반면 암호학적 해시 함수는 아주 작은 변화도 해시 결과 전체를 급격히 변화시키도록 설계되며, 유사성 정보는 보존하지 않는다.  퍼지 해시 기법은 보통 “유사도 비교 → 후보군 좁히기 → 정밀 비교” 흐름으로 사용된다.
==주요 기법과 알고리즘==
퍼지 해시를 구현하는 대표적인 기법들과 알고리즘은 다음과 같다.
*'''CTPH (Context-Triggered Piecewise Hashing)''': 입력을 여러 구간으로 나누고, 각 구간에 대해 전통적 해시를 적용한 뒤 이를 조합하는 방식 (예: ssdeep)
*'''LSH (Locality-Sensitive Hashing)''': 유사한 입력이 동일한 해시 버킷으로 매핑될 확률을 높이도록 설계된 해시 함수 군
*'''SimHash''': 벡터 표현에서 코사인 유사도를 근사해 유사 해시를 만드는 기법, 문서 유사도 탐색에 활용
*'''MinHash''': 집합 기반 유사도 (예: Jaccard 유사도)를 추정하기 위해 최소 해시 값을 이용하는 방식
*'''Nilsimsa Hash''': 이메일/스팸 필터링을 위해 고안된 해시 방식으로, 유사 메시지에 대해 유사한 해시를 생성
최근에는 전통적 방식 대신 머신러닝 기반 퍼지 해시도 연구되고 있다. 예를 들어, Perturbation-Consistent Adversarial Kernel Embedding 방식은 데이터 분포에 맞게 해시 함수를 학습하는 접근이다.
==장단점==
===장점===
*입력이 일부 변형되었더라도 유사성을 감지할 수 있다.
*변형된 파일, 코드, 문서 등 간의 유사 탐지에 유용하다.
*유사성 기반 검색, 중복 제거, 악성코드 변종 탐지 등에서 효과적이다.
===단점 / 한계===
*오탐(false positive)과 누락(false negative)이 발생할 수 있다.
*유사도 임계값 설정이 중요하다.
*계산 비용이 전통적 해시보다 높다.
*퍼지 해시만으로는 완전한 판별이 어려우며 후보군에 대한 정밀 비교가 필요하다.
==응용 사례==
*악성코드 탐지 및 변종 분석
*문서 유사도 검색 및 중복 문서 탐지
*로그 패턴 유사 탐지
*파일 버전 관리 및 변형 탐지
*이메일 스팸 필터링 (예: Nilsimsa)
*웹 콘텐츠 유사 탐지, 피싱 사이트 탐지
==파이썬 예제 코드==
다음은 문자열을 대상으로 간단한 퍼지 해시/유사도 비교 예제이다.<syntaxhighlight lang="\&quot;python\&quot;">
import hashlib
from collections import defaultdict

def ngram_hashes(s: str, n: int = 3):
    """문자열 s를 n-그램으로 나눈 후 각 n-그램에 MD5 해시를 취해 Set 반환."""
    hashes = set()
    for i in range(len(s) - n + 1):
        gram = s[i : i + n]
        h = hashlib.md5(gram.encode('utf-8')).hexdigest()
        hashes.add(h)
    return hashes

def jaccard_similarity(set1: set, set2: set) -> float:
    """자카드 유사도 계산."""
    if not set1 or not set2:
        return 0.0
    return len(set1 & set2) / len(set1 | set2)

class FuzzyHashStore:
    def __init__(self):
        self.store = defaultdict(list)

    def insert(self, key: str, value):
        sig = frozenset(ngram_hashes(key))
        self.store[sig].append((key, value))

    def query(self, key: str, threshold: float = 0.5):
        sig = frozenset(ngram_hashes(key))
        results = []
        for sig2, items in self.store.items():
            sim = jaccard_similarity(sig, sig2)
            if sim >= threshold:
                results.extend(items)
        return results

# 사용 예시
if __name__ == "__main__":
    store = FuzzyHashStore()
    store.insert("hello world", "A")
    store.insert("helo world", "B")
    store.insert("goodbye", "C")

    print(store.query("helloo world", threshold=0.4))
    # 출력 예: [('hello world', 'A'), ('helo world', 'B')]
</syntaxhighlight>
==같이 보기==

* [[해시 함수]]  
* [[로컬리티 민감 해싱]]  
* [[ssdeep]]  
* [[유사도 검색]]  
* [[악성코드 분석]]

==참고 문헌==
*[https://arxiv.org/abs/1812.07071 A. Azarafrooz & J. Brock, “Fuzzy Hashing as Perturbation-Consistent Adversarial Kernel Embedding.” arXiv:1812.07071]
*[https://arxiv.org/abs/2004.06563 Yuping Li, Jiong Jang, Xinming Ou, “Topology-Aware Hashing for Effective Control Flow Graph Similarity Analysis.” arXiv:2004.06563]
==각주==
[[분류:자료 구조]]