[paper review] Measuring Information Leakage in Website Fingerprinting Attacks and Defenses

[ updated : 2024-02-17:  요약본 하단 참조]

[Paper review]Seminar1_Measuring Information Leakage in Website Fingerprinting Attacks and.pdf

1.59MB

논문 선택 이유

: Augmentation Project를 위한 인사이트 얻기.

WeFDE의 feature들 가져다가 활용해보기 (trace에서 정보 유출양을 feature별로 보여줌)

⇒ 수학적 서술의 Idea를 얻는게 이 논문을 읽는 것의 목표.

 

Goal

Tor가 traffic overhead를 minimize하기 위해 website에 대해 불가피하게 leak하는 information의 amount를 측정함.

ex. leaked information : volum, timing, direction of communications

Keys

1. validating WF defenses by accuracy alone is flawed
2. joint information leakage from a large set of features
3. first large-scale information leakage measurement
4. new information-theoretic insights upon WF features

Introduction

• Defense Evaluation
  • accuracy가 낮은 것 ≠ 낮은 information leakage
  • 즉 accuracy는 information leakage를 underestimate함.
  • low accuracy doesn’t necessarily mean low information leakage.
  ⇒ the fingerprint can contain a great deal of information about the web page even if the classifier cannot accurately identify the correct page

• Feature Evaluation
  • 기존 = information leakage순으로 feature들을 ranking즉 Feature들간의 relationships를 quantify할 필요가 있다.
  • (= coarse-grained evaluations of features)
  • → 문제점 : A가 B, C보다 좋을 수 있는데 B&C일때는 모름
  • Two Challenges
    1. Modeling behavior & interaction of WF features
    2. 정보손실 계산시 curse of dimensionality (차원의 저주)
       • 보통 SOTA feature sets는 high-dimensional함.
• WeFDE (Website Fingerprinting Density Estimation, WF 밀도 추정) = Information leakage measurement framework
• Challenges에 관한 Solution
  1. adaptive kernel density estimation (KDE)
  2. dimension reduction approaches
     • 중복 feature 제거를 위해 feature들의 pairwise mutual information 측정
     • Kononenko’s Algorithm, DBSCAN→ threshold 보다 높은 상호정보를 가지도록 그룹화
     • 그룹별로 차원축소 및 adaptive kernels 적용

       

Traffic and its features

T(C) = website C를 방문했을때의 Traffic

• $l_i$
• ≤0 : user가 전송한 패킷
• 0 : server가 전송한 패킷

features (존재하는 traffic features in WF 모두 실험)

System Design

Methodology

Different features may carry different amount of information

(feature 마다 정보량이 다르다.)

ex. 해당 논문의 예제 : Total packet count > transmission time

⇒ 이를 어떻게 정량화할까?(quantify할까?)

⇒ “Mutual Information”

Architecture

1. Website Fingerprint Modeler

traffic feature들은 range가 넓어 histogram대신 AKDE(Adaptive Kernel Density Estimate)

• Proper bandwidths
  • continuous features
  • → plug-in estimator
  • if fails → the-rule-of-thumb approach
  • discrete features(→ continuous로 다룸)
  • → bandwidth very small (0.001) (각 website가 동일한 constant 사용시 측정에 impact x)
• Properties
  1. a mixture of continuous & discrete random variables                                                                                          ex. BuFLO : time T안에 complete하면 discrete, 아니면 continuous
  2. distinguish a continuous-like discrete feature                                                                                                    ex. Tamaraw : continuous feature을 discrete하게 만듦 →이런 feature을 recognize
  3. multivariate form of AKDE                                                                                                                                      (-) The curse of dimensionality ⇒ Mutual information Analyzer를 통한 dim reduction

Mutual Information Analyzer

• Goal = mitigating the curse of dimensionality in multivariate AKDE
• ⇒ dimension reduction 🌟
• normalization → Kvalseth’s method

Entropy and Correlation: Some Comments

• Group by Dependency (의존성에 따라 그룹 나누기)
  • Navie Bayes method를 통한 차원 축소
    • 조건 = feature set이 conditionally independent → x, 대안 필요! ⇒ 💡 A hybrid of the AKDE and Naive Bayes
      • Knononenko’s algorithm (KA)
        • 고의존성 feature들을 disjoint group으로 clustering
        • 이때 각 group의 conditional independence를 가정함.
        • 이후 AKDE를 통해 그룹별로 feature들의 joint PDF 모델링
        • 의의
        • : Naive bayes가 차원의 저주를 해결하는 방식을 가져오면서도 realistic한 가정을 고려한다는 점에서 의의가 있는 알고리즘.
      • DBSCAN
        • Threshold $\epsilon$보다 크면 same group, 작으면 diff group 원리
        • 구체적으로 threshold보다 작으면 new cluster을 시작함.
        • density-based clustering algorithm
        • mutual information matrix M → distance matrix D = 1 - M
        • → $\epsilon$ tuning을 통한 degree of independence 결정(=0.4)

          

      • Dimension Reduction other approaches
        • 다른 feature들로 표현되는 feature들 제거
          • theshold(0.9)보다 높은 mutual information을 갖는 feature쌍들을 구함
          • 이후 feature들중 하나씩 제거해보면서 찾음
        • ⇒ pairwise mutual information
        • 모든 feature들의 정보손실을 추론하게 위해 가장 informative한 feature들을 선택함.
          • sorting → top n features를 pick out
          ex. top100, top1000, top2000일때의 Information Leakage 비교

          

        • 결론 = the information leakage of sufficient top informative features is able to approximate that of the overall features
        • +) PCA는 해당 도메인에 쓰기 적절한 차원축소기법이 아니다. 기본적으로 variance도 작아서 성능이 안좋음.
        •  results

          

          • redundant features are pervasive among the highly informative features
          • features from different categories may share much information (that’s why they are clustered together).
          • features from same category are not necessarily in the same cluster.
          • categories do not necessarily have features to be included in clusters

Closed-world information leakage

• settings
  • Alexa top 100 websites with 55779 visits
  • assume : equal prior prob for sites
  • feature 3043개의 각 information leakage 계산, categories에 따라 joint leakage 계산-
• results (individual features)

  

  1. feature들중 0.02만큼(64개 정도)이 3bit 넘게 information leakage 발생함. 공격자가 이 feature들을 통해 0.125(1/8)만큼으로 가능성을 줄일 수 있다.
  2. 54.55% features는 1bit보다 덜 잃음 → 거의 feauture들 절반이 공격자가 anonymity set 크기를 절반으로 줄이는데 도움을 주었음. 정보 손실 1bit일때 줄어든 가능성은 p=1/2 → 3bit여서 p=1/(2^3)=1/8
  3. outgoing packet count ⇒ 반올림 안했을때보다 0.19bit 적은 3.26bit만큼 leak info                                                total packet count와 incoming packet count를 반올림했을때 similar leak increase  ⇒ packet count를 반올림하는데 attack에 좋음.
  4. packet더 많은 download stream보다 incoming stream이 leak bit더 큼
  5. information leakage of timing features has little difference for upload and download stream.
  6. the impact of world size on individual feature’s information leakage → x 
     • Question = 충분히 큰 world size일때 최대 information leakage는 얼마일까
     • Closed world
       • combined larger world size가 information leakage에 영향 미미
     • Open world
       • world size가 커질때 ⇒ information leakage 감소
       • 측정에 미미함.증명(Theorem 2)

• Joint Information measurement (Category)
• *categories → Time, Ngram, Transposition, Interval, packet dist, …, CUMUL… 
  • results
    • redundant features가 prevalent했음.
    • 그래프를 보면 feature가 더 늘어나도 leakage 증가x(=reach plateau)
    • the impact of world size → size 증가시 leakage 증가

Validation

• bootstrapping (appendix A)
  • 목적
  • : 정보 측정값의 정확도 측정
  • 정의
  • : 복원 추출을 이용한 통계 기법
  • 순서
    1. 관찰하려는 크기만큼 복원 추출(사이트 마다)
    2. 1번 가지고 measurement 적용해 information leakage 계산
    3. 1,2번을 K번 반복해 얻은 information leakage값 K개 기반 CI confidence interval을 찾음.
• measurement validation
  • bootstrapping 활용
    • (a) top 100 feature들에 대한 confidence intervals
      • interval들의 폭이 0.178bit보다 작음
    • (b) 15개의 category에 대한 것
• dataset validation
  • bootstrapping 활용(2200개 사이트)
  • subsampling
  • = bootstrapping용 데이터셋→ 100개 사이트 랜덤 추출(복원x)
• results
  • Including different websites in the closed-world setting does make a difference in the measurement, but Figure 10 shows such impact is very limited.
  • By bootstrapping, we validate our information leakage results even when the true representative websites are still unknown

Informaton leakage in WF defenses (closed world)

1. Acuracy의 WF defense 입증에 관한 한계성

• 불학실성의 이유 = “all-or-nothing”
  • miss했을때 다음 두세번의 시도에 hit한다면 high information leakage
  • 한방에 hit → low information leakage
  → accuracy는 이러한 case에 대한 판단 불가(맞거나/틀리거나 only)
• Accuracy is inaccurate
  • Accuracy는 특정 classifier에 대한 의존성 때문에 fail할 것이다.
  • 같은 정확도를 갖는 Defense들은 leak하는 정보의 양이 vary하다.
    • BuFLO, Tamaraow의 정확도 거의 동일→ 그나마 BuFLO가 더 acc낮아서 얘가 secure하가도 했는데 정보손실량 계산해보니 BuFLO가 2.31bits만큼 더 leak함을 찾아냄.(즉 BuFLO가 덜 secure)
  • 정확도로 더 secore한 것 ⇒ leak more information

    

    증명

 

2. WF defenses’ information leakage의 measurement

• Tamaraw, BuFLO, Supersequence, WTF-PAD, CS-BuFLO로 quantify
• 얘네로 defensed traffic을 생성
• closed-world setting
• information leakage, classification accuracy 동시 평가
• site들에 대해 동일 prior 적용
• 각 defense에 대해 dimension reduction 적용
• 일괄적 KNN classifier

Open-world information leakage

• #가능한 outcome = n+1
• unmon이 많아질수록 오히려 엔트로피가 감소했음.(정보 손실 감소)
  • 부분적으로 mon에 대한 prior때문에 정보량이 감소했을것
• world setting의 변화는 카테코리들의 정보손실양에 큰 영향x

  

  

Discussion

응용

• Attack = test case의 사이트 방문 확률 계산 + likely destinationd에 대한 prior information → Bayesian 추론
• Bootstrap a defense design

한계

• feature set에 의존함.

WeFDE_Measuring Information Leakage1710.06080.pdf

0.71MB