2025-11-15T15:52:10.939408

DEHYDRATOR: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation

Ying, Zhu, Lv et al.
As the scope and impact of cyber threats have expanded, analysts utilize audit logs to hunt threats and investigate attacks. The provenance graphs constructed from kernel logs are increasingly considered as an ideal data source due to their powerful semantic expression and attack historic correlation ability. However, storing provenance graphs with traditional databases faces the challenge of high storage overhead, given the high frequency of kernel events and the persistence of attacks. To address this, we propose Dehydrator, an efficient provenance graph storage system. For the logs generated by auditing frameworks, Dehydrator uses field mapping encoding to filter field-level redundancy, hierarchical encoding to filter structure-level redundancy, and finally learns a deep neural network to support batch querying. We have conducted evaluations on seven datasets totaling over one billion log entries. Experimental results show that Dehydrator reduces the storage space by 84.55%. Dehydrator is 7.36 times more efficient than PostgreSQL, 7.16 times than Neo4j, and 16.17 times than Leonard (the work most closely related to Dehydrator, published at Usenix Security'23).
academic

DEHYDRATOR: 계층적 인코딩 및 시퀀스 생성을 통한 프로비넌스 그래프 저장소 향상

기본 정보

  • 논문 ID: 2501.00446
  • 제목: DEHYDRATOR: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation
  • 저자: Jie Ying, Tiantian Zhu*, Mingqi Lv, Tieming Chen (저장공업대학교)
  • 분류: cs.CR (암호화 및 보안)
  • 게재 저널: IEEE Transactions on Information Forensics and Security
  • 논문 링크: https://arxiv.org/abs/2501.00446

요약

네트워크 위협의 범위와 영향이 확대됨에 따라 분석가들은 감사 로그를 활용하여 위협을 추적하고 공격을 조사합니다. 커널 로그로부터 구성된 프로비넌스 그래프는 강력한 의미론적 표현 능력과 공격 이력 연관성으로 인해 이상적인 데이터 소스로 인식되고 있습니다. 그러나 커널 이벤트의 높은 빈도와 공격의 지속성으로 인해 기존 데이터베이스를 사용한 프로비넌스 그래프 저장은 높은 저장 오버헤드의 문제에 직면하고 있습니다. 이 문제를 해결하기 위해 본 논문은 효율적인 프로비넌스 그래프 저장 시스템인 DEHYDRATOR를 제안합니다. 감사 프레임워크에서 생성된 로그에 대해 DEHYDRATOR는 필드 매핑 인코딩으로 필드 수준 중복을 필터링하고, 계층적 인코딩으로 구조 수준 중복을 필터링하며, 마지막으로 심층 신경망을 학습하여 배치 쿼리를 지원합니다. 총 10억 개 이상의 로그 항목을 포함하는 7개의 데이터셋에서 평가한 결과, DEHYDRATOR는 저장 공간을 84.55% 감소시켰으며, PostgreSQL보다 7.36배, Neo4j보다 7.16배, Leonard보다 16.17배 효율적입니다.

연구 배경 및 동기

문제 배경

  1. 증가하는 네트워크 위협: 2024년 5월 현재 9,478건의 데이터 유출 사건이 발생했으며, 2024년 1월의 MOAB 사건에서는 260억 개의 레코드가 유출됨
  2. 프로비넌스 그래프의 중요성: 프로비넌스 그래프는 방향성 그래프 구조로, 노드는 시스템 엔티티(프로세스, 파일, 소켓)를 나타내고 간선은 시스템 이벤트를 나타내며, 강력한 의미론적 표현과 공격 이력 연관성을 제공합니다
  3. 저장 문제: 저장 어려움을 야기하는 4가지 현상:
    • 비가역적 증가: 데이터 무결성 유지를 위해 데이터만 추가하고 삭제하지 않음
    • 빠른 확장: 머신당 일일 GB 규모의 로그 생성
    • 장기간 지속: 침입이 평균 188일 후에 발견됨
    • 쿼리 요구사항: 위협 사냥 및 인과 분석을 위한 대규모 쿼리 지원 필요

기존 방법의 한계

기존의 효율적인 프로비넌스 그래프 저장 시스템(ESSPGs)은 두 가지로 분류됩니다:

  1. 가지치기 기반 방법(LogGC, CPR, NodeMerge, DPR 등): 손실 압축으로 상위 계층 컴포넌트에서 거짓 음성 발생 가능
  2. 인코딩 기반 방법(SEAL, SLEUTH, ELISE, Leonard 등): 쿼리 지원 불가능하거나 보조 컴포넌트가 많은 저장 공간 차지

연구 동기

기존 방법은 3가지 핵심 요구사항을 동시에 만족할 수 없습니다:

  • 콘텐츠 무손실: 거짓 음성을 피하기 위해 모든 데이터 보존
  • 저장 효율성: 저장 오버헤드 최소화
  • 쿼리 지원: 대규모 쿼리 요구사항 처리

핵심 기여

  1. DEHYDRATOR 시스템 제안: 기존 방법의 한계를 극복하는 효율적인 프로비넌스 그래프 저장 시스템으로, 필드 매핑 인코딩으로 필드 수준 중복을 필터링하고, 계층적 인코딩으로 구조 수준 중복을 필터링하며, 심층 신경망으로 배치 쿼리를 지원합니다
  2. 프로토타입 시스템 구축 및 대규모 평가: 7개의 데이터셋(총 10억 개 이상의 로그)에서 평가하여 저장 공간을 84.55% 감소시켰으며, PostgreSQL, Neo4j, Leonard보다 각각 7.36배, 7.16배, 16.17배 효율적입니다
  3. 포괄적 평가 분석: 컴포넌트 영향, 적용 시나리오 및 성능 하한을 탐색하고, 저장 오버헤드와 지연을 균형 있게 조정하는 지연 저장 비율(LSR) 지표를 정의합니다

방법론 상세 설명

작업 정의

입력: 감사 프레임워크에서 수집한 원본 커널 로그 출력: 효율적으로 저장된 프로비넌스 그래프로 상위 계층 컴포넌트의 쿼리 요구사항 지원 제약: 콘텐츠 무손실, 저장 효율성, 쿼리 지원

시스템 아키텍처

DEHYDRATOR는 3단계 프레임워크를 채택합니다:

1. 전처리 단계 (Pretreatment)

  • 로그 파싱: 정규식을 사용하여 원본 로그에서 핵심 필드 추출
  • 프로비넌스 그래프 구성: 노드 테이블 NT(IdentiID, Name, Type)와 간선 테이블 ET(SrcID, DstID, TimeStamp, Operation) 구성
  • 필드 매핑 인코딩: 3가지 필드 수준 중복 처리
    • 고유값: 더 짧은 숫자 문자로 대체
    • 반복값: 인덱스로 대체
    • 증분값: 오프셋으로 대체

2. 저장 단계 (Storage)

계층적 인코딩:

  • 프로비넌스 그래프를 계층적 방향 그래프로 모델링
  • 각 노드 v에 대해 모든 소스 노드 및 입력 간선 정보 기록
  • 병합 매핑 테이블 MMT 및 계층적 간선 테이블 EThi 구성
  • 중첩 리스트 구조: Operation: timeOffset: nodeOffset

모델 훈련:

  • 단일 계층 디코더 전용 Transformer 선택
  • 저장 작업을 시퀀스 생성 작업으로 모델링
  • char2vec 인코딩 사용, 자동회귀 생성
  • 모델 예측 오류 처리를 위한 오류 수정 테이블 ECT 구성

3. 쿼리 단계 (Query)

  • 노드 정보: 매핑 테이블 MT를 통해 인덱스 획득, 노드 정보 검색
  • 간선 정보: 인덱스를 DNN 모델에 입력, 시퀀스 생성, ECT 오류 수정, 계층적 디코딩으로 읽을 수 있는 정보 획득

기술 혁신점

  1. 계층적 인코딩 설계:
    • 인과 분석의 역방향 쿼리 특성 기반
    • 여러 병렬 간선을 컴팩트 인코딩 형식으로 압축
    • 정보 밀도 증가, 모델 훈련 가속화
  2. DNN 모델 선택:
    • 다층 LSTM 대신 단일 계층 디코더 Transformer 사용
    • 더 나은 병렬화 능력 및 특성 추출 능력
    • 저수준 반복 패턴 인식에 적합한 저장 작업
  3. 오류 수정 메커니즘:
    • ECT 테이블이 위치 및 올바른 문자 기록
    • DNN 압축을 지원하면서 콘텐츠 무손실 보장

실험 설정

데이터셋

7개의 데이터셋, 총 10억 개 이상의 로그:

  • G1-G4: DARPA TC E3의 CADETS, THEIA, TRACE 그룹
  • G5-G6: DARPA TC E4의 TRACE 그룹
  • G7: DEPIMACT 데이터셋 부분집합
  • 평균 간선 수: 17,754,566 (Leonard보다 9.6배 큼)

평가 지표

  • 저장 오버헤드: BPpre(전처리) 및 BPpost(후처리) 바이트 수
  • 저장 지연: Ts 시간 비용
  • 지연 저장 비율: LSR = (BPpre - BPpost)/Ts

비교 방법

  • PostgreSQL: 관계형 데이터베이스
  • Neo4j: 그래프 데이터베이스
  • Leonard: DNN 기반 저장 시스템 (Usenix Security'23)

구현 세부사항

  • 환경: Python 3.9, PyTorch 1.13.1, AMD EPYC 7513 프로세서, RTX A6000 GPU
  • 하이퍼파라미터: 배치 크기 4096, Adam 옵티마이저, 학습률 0.001, 최대 훈련 에포크 5

실험 결과

주요 결과

시스템평균 저장 오버헤드(MB)평균 지연(초)DEHYDRATOR 대비 개선
PostgreSQL1,818457.36×
Neo4j1,770217.16×
Leonard3,99130,23316.17×
DEHYDRATOR2473,205-

쿼리 성능

다양한 깊이의 BFS 쿼리 테스트에서:

  • Neo4j 최고 성능 (~4.92초)
  • DEHYDRATOR 차선 (~32.02초)
  • PostgreSQL 최악 (~32.08초)

제거 실험

컴포넌트 기여도 분석:

  • 원본 그래프: 1598.69MB
  • 필드 매핑 인코딩 후: 405.2MB (25.3%)
  • 계층적 인코딩 후: 75.98MB (4.7%)
  • 모델 훈련 후: 192.42MB (12%)

계층적 인코딩 영향:

  • 계층적 인코딩 포함: EThi 20.19M, 훈련 시간 660.69초, ECT 50.79M
  • 계층적 인코딩 미포함: EThi 268.31M, 훈련 시간 5814.42초, ECT 1064.25M
  • 계층적 인코딩으로 훈련 시간 8.8배 감소, ECT 크기 20.95배 감소

적용 시나리오 분석

이론적 도출: 평균 차수 davg ≥ 3일 때 계층적 인코딩 효과적 실험 검증: 차수 3, 4, 5인 데이터셋에서 계층적 인코딩 모두 효과적

관련 연구

침입 탐지

  • 휴리스틱 방법: HOLMES, SLEUTH, Poirot 등 MITRE ATT&CK 기반 매칭 규칙 구성
  • 이상 탐지: Streamspot, Unicorn, KAIROS 등 정상 행동 편차 인식을 통한 침입 탐지

공격 조사

  • RapSheet, HERCULE, NODOZE 등 시스템이 위협 점수 및 인과 분석 수행
  • DEPIMPACT, ATLAS 등 의존성 분석 및 공격 패턴 인식 수행

그래프 압축

  • 손실 방법: LogGC, CPR, NodeMerge, DPR 등 가지치기 기술
  • 무손실 방법: SEAL, ELISE, Leonard 등 인코딩 기술

결론 및 토론

주요 결론

  1. DEHYDRATOR는 프로비넌스 그래프 저장의 3가지 문제를 성공적으로 해결: 콘텐츠 무손실, 저장 효율성, 쿼리 지원
  2. 계층적 인코딩은 구조 수준 중복을 효과적으로 처리하는 핵심 혁신
  3. 단일 계층 Transformer는 다층 LSTM보다 저장 작업에 더 적합
  4. 대규모 데이터셋에서 기존 방법을 크게 능가

한계

  1. 높은 저장 지연: 평균 3205초로 데이터셋 시간 구간의 13.29% 차지
  2. 쿼리 효율성: 자동회귀 생성으로 인한 긴 시퀀스 쿼리 지연 증가
  3. 모델 용량 선택: 최적 모델 용량 η 결정을 위한 이론적 지침 부족
  4. 적용 범위: 주로 콜드 저장 시나리오에 적용, ACID 속성 미지원

향후 방향

  1. AI 가속 기술을 활용한 훈련 및 추론 효율성 향상
  2. 최적 모델 용량 선택에 대한 이론적 분석
  3. 범용 그래프 데이터베이스 애플리케이션으로 확장
  4. 쿼리 알고리즘 최적화로 지연 감소

심층 평가

장점

  1. 문제의 중요성: 네트워크 보안 분야의 실제 문제 해결
  2. 방법의 혁신성: 계층적 인코딩이 도메인 특성과 DNN 장점을 교묘하게 결합
  3. 실험의 충분성: 대규모 데이터셋 검증, 포괄적인 제거 실험 및 비교 분석
  4. 공학적 가치: 현저한 저장 효율성 향상, 높은 실용성

부족한 점

  1. 지연 문제: 저장 및 쿼리 지연이 여전히 높아 실시간 애플리케이션 제한
  2. 이론적 분석: 모델 용량 선택에 대한 이론적 지침 부족
  3. 적용 범위: 특정 프로비넌스 그래프 시나리오에 주로 초점, 일반화 제한
  4. 기준선 비교: Leonard 구현에서 불공정한 비교 가능성

영향력

  1. 학술적 기여: 프로비넌스 그래프 저장을 위한 새로운 기술 경로 제공
  2. 실용적 가치: 네트워크 보안 기반 시설에 중요한 의미
  3. 재현성: 코드 및 데이터 오픈소스 약속
  4. 확산성: 방법을 다른 그래프 저장 시나리오로 확장 가능

적용 시나리오

  1. 네트워크 보안: EDR 시스템, 위협 사냥, 공격 조사
  2. 콜드 저장: 역사 데이터 아카이빙 및 분석
  3. 대규모 그래프 데이터: 높은 차수, 높은 중복도의 그래프 구조 저장
  4. 배치 쿼리: 많은 병렬 쿼리가 필요한 애플리케이션 시나리오

참고문헌

논문은 93개의 관련 문헌을 인용하며, 네트워크 보안, 그래프 압축, 심층 학습 등 여러 분야의 중요한 연구를 포함하여 연구에 견고한 이론적 기초를 제공합니다.