기술 요약: 가짜 데이터 주입을 통한 확률적 밴드에 대한 실용적 적대적 공격

1. 문제 정의

다중 팔 밴드 (Multi-armed bandit, MAB) 알고리즘은 개인화된 추천, 온라인 광고, 임상 시험과 같은 응용 분야에서 탐색과 활용을 균형 있게 조절하는 온라인 의사결정 시스템의 기초를 이룹니다. 기존 연구는 MAB 알고리즘이 적대적 공격에 취약하다는 점을 입증해 왔으나, 기존 위협 모델은 실제 시스템과의 관련성을 제한하는 비현실적인 가정에 의존해 왔습니다.

구체적으로, 이전 연구들 (예: Jun et al., 2018; Liu and Shroff, 2019; Zuo, 2024) 은 주로 피드백 교란 (feedback-perturbation) 모델을 채택했습니다. 이 모델에서 공격자는 매 라운드 학습자가 선택한 팔과 그 보상을 관찰한 후, 해당 보상이 학습자에게 공개되기 전에 임의로 수정합니다. 이 모델은 공격자에게 매 시간 단계에서 피드백 채널에 대한 완전한 통제권을 부여하며, 무제한의 교란 능력을 가정합니다.

실제로 이러한 능력은 종종 불가능합니다. 예를 들어, 레스토랑 추천 플랫폼에서 적대자는 수천 명의 실제 고객으로부터의 진정한 사용자 평점을 지속적으로 덮어쓸 수 없습니다. 대신, 현실적인 공격은 가짜 계정을 만들어 조작된 리뷰나 합성 상호작용 (예: 클릭 사기) 을 주입하는 것을 포함합니다. 이러한 공격은 기존 데이터를 변경하는 것이 아니라 가짜 데이터를 추가하는 것이며, 시스템 수준의 탐지나 자원 제한을 받으며 유효한 피드백 범위 (예: 1~5 점 평점) 에 부합해야 합니다.

본 논문은 이론적 공격 모델과 실제 제약 조건 간의 격차를 해소하기 위해 새로운 위협 모델인 **가짜 데이터 주입 (Fake Data Injection)**을 제안합니다. 핵심 과제는 다음과 같은 제약 하에 학습자를 특정 비최적 (목표) 팔을 거의 모든 라운드에서 선택하도록 오도하면서 오직 아선형 (sublinear) 비용만 발생시키는 공격 전략을 설계하는 것입니다:

1. 진짜 피드백 수정 금지: 공격자는 실제 사용자 데이터를 덮어쓸 수 없습니다.
2. 유계 보상: 주입된 가짜 보상은 유효한 피드백 범위 $[r_l, r_u]$ 내에 있어야 합니다.
3. 시간적 제약: 공격자는 매 라운드 주입할 수 있는 가짜 샘플 수 (배치 크기) 나 주입 빈도에 제한을 받을 수 있습니다.

2. 방법론 및 핵심 개념

2.1 가짜 데이터 주입 위협 모델

저자들은 공격자가 $N_F$개의 가짜 데이터 샘플 $\{(a^F_s, r^F_s)\}$을 학습자의 기록에 주입하는 상황을 형식화했습니다. 학습자는 이러한 주입된 샘플을 정당한 상호작용과 구별하지 못하며, 이에 따라 경험적 평균, 풀 (pull) 횟수, 내부 라운드 카운터를 업데이트합니다.

• 공격 비용: $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$로 정의됩니다.
• 성공 기준: 공격이 성공하려면 학습자가 $T - o(T)$라운드 동안 목표 팔을 선택하도록 유도하면서 $C_F(T) = o(T)$를 보장해야 합니다.

2.2 억제 원리 (Suppression Principle)

핵심 기술적 통찰은 억제 원리입니다. 공격자는 보상을 지속적으로 교란하는 대신, 목표 팔의 안정적인 하한 기준치 이하로 비목표 팔의 경험적 추정을 억제할 만큼 충분한 유계 가짜 피드백을 주입하는 것을 목표로 합니다. 비목표 팔이 충분히 억제되면, 학습자 자신의 탐색 메커니즘이 상당 기간 동안 해당 팔이 다시 선택되는 것을 방지합니다.

지수적 억제 보조정리 (UCB 의 경우)

Upper Confidence Bound(UCB) 알고리즘의 경우, 저자들은 비목표 팔 $i$가 충분히 풀려 ($N_i(t) \geq \log T/\delta_0^2$) 그 경험적 평균이 목표 팔 $K$의 특정 하한 $\hat{\ell}_K(t)$ 이하로 밀려날 경우, 팔 $i$는 높은 확률로 적어도 $\exp(N_i(t)\delta_0^2)$라운드까지 다시 선택되지 않음을 증명했습니다. 이러한 "지수적 억제"는 공격자가 팔당 단일 주입 사건으로 장기적인 조작을 달성할 수 있게 합니다.

2.3 공격 전략

A. 동시 주입 (Simultaneous Injection, SI)

공격자가 엄격한 라운드별 제한 없이 필요할 때 데이터를 주입할 수 있는 상황을 위해 설계되었습니다.

• 메커니즘: 각 비목표 팔 $i$에 대해, 공격자는 해당 팔이 $\lceil \log T/\delta_0^2 \rceil$번 풀릴 때까지 기다린 후, 해당 팔의 경험적 평균을 목표 팔의 하한 신뢰 구간 이하로 낮추기 위해 최소 유효 보상 $r_l$을 가진 가짜 샘플 배치로 주입합니다.
• 결과: 이는 UCB 알고리즘이 누적 비용 $\tilde{O}(K\sigma\sqrt{\log T})$로 $T - o(T)$라운드 동안 목표 팔을 선택하도록 강제하며, 알려진 하한과 일치합니다.

B. 주기적 유계 주입 (Periodic Bounded Injection, PBI)

공격자가 배치 크기 제한 (라운드당 $f$개 샘플) 을 받고 이상 탐지를 피해야 하는 현실적인 제약 조건을 위해 설계되었습니다.

• 메커니즘: 단일 대규모 주입 대신, 공격자는 필요한 가짜 샘플을 시간에 걸쳐 분배합니다. 비목표 팔이 풀 임계치에 도달하면, 공격자는 필요한 총 샘플 수와 "쿨다운" 기간 $R_i$를 계산합니다. 공격자는 주입 간 $R_i$라운드를 두고 주기적으로 크기 $f$의 배치를 주입하여, 주입 사이에 팔이 억제된 상태를 유지하도록 합니다.
• 결과: PBI 는 엄격한 시간적 및 크기 제약 하에서도 아선형 비용으로 성공적인 공격을 달성하여 은밀성과 효과성 사이의 균형을 맞춥니다.

C. 일반 억제 - 유계 프레임워크

저자들은 이러한 발견을 UCB 를 넘어 **억제 - 유계 (Suppression-Bounded)**라고 명명된 알고리즘 클래스로 확장했습니다. 알고리즘이 비최적 팔이 목표 팔에 의해 경험적으로 지배당하게 되면, 해당 팔을 추가로 유계된 횟수만큼만 풀 경우, 해당 알고리즘은 억제 - 유계입니다.

• 이 프레임워크는 Thompson Sampling 및 $\epsilon$-greedy 알고리즘에 적용됩니다.
• 공격 전략은 비목표 팔의 경험적 평균이 목표의 기준치 아래에 머무는 조건을 만족시키기 위해 최소한의 가짜 샘플을 주입하는 것으로, 알고리즘의 억제 후 풀에 대한 고유한 유계성을 활용합니다.

3. 주요 기여

1. 새로운 위협 모델: 이전 피드백 교란 모델이 간과한 현실적인 제약 (유계 보상, 제한된 주입 빈도, 진짜 데이터 덮어쓰기 불가) 을 반영하는 가짜 데이터 주입의 도입.
2. 억제 원리: 유계 가짜 주입이 비목표 팔을 영구적으로 억제할 수 있는 메커니즘의 형식화. 이를 통해 공격을 지속적인 교란이 아닌 억제 설정 및 유지 문제로 전환.
3. 알고리즘적 전략:
   • 동시 주입 (SI): 최소 제약 하의 UCB 를 위한 최적 전략.
   • 주기적 유계 주입 (PBI): 배치 크기와 시간적 제약 하의 UCB 를 위한 강력한 전략.
   • 일반 프레임워크: 억제 분석을 Thompson Sampling 및 $\epsilon$-greedy 로 확장.
4. 이론적 보장: 유계 보상 값으로도 이러한 공격이 학습자를 $T - o(T)$라운드 동안 목표 팔을 선택하도록 오도할 수 있으며, 공격 비용은 아선형 ($o(T)$) 임을 증명.
5. 실증적 검증: 합성 데이터와 MovieLens 25M데이터셋을 통한 실험으로, 희소하고 유계된 가짜 데이터가 실제로 밴드 학습자를 크게 편향시킬 수 있음을 입증.

4. 실험 결과

저자들은 다음에서 전략을 평가했습니다:

• 합성 데이터: $K=10$개의 팔을 가진 가우시안 보상 분포.
• 실제 데이터: 10 개의 팔 (영화) 과 사용자 상호작용을 가진 추천 시스템을 시뮬레이션한 MovieLens 25M 데이터셋.

주요 발견:

• 효과성: 초기 억제 단계 후 SI 와 PBI 모두 UCB 및 Thompson Sampling 학습자를 라운드의 95% 이상에서 목표 팔을 선택하도록 성공적으로 강제했습니다.
• 비용 효율성: PBI 는 SI 와 유사한 성능을 달성하면서도 주입을 시간에 걸쳐 분산시킴으로써 장기 시나리오에서 더 낮은 공격 비용을 달성했습니다.
• 베이스라인과의 비교: 남은 시간에 비례하여 무작위로 샘플을 주입하는 휴리스틱 베이스라인은 학습자가 목표 팔로 수렴하지 못하게 하여, 주입 일정과 억제 원리의 결정적 중요성을 부각시켰습니다.
• 제약에 대한 강건성: PBI 는 배치 크기 ($f=5$ 또는 $f=10$) 에 대한 엄격한 제한이 있더라도 공격이 효과적임을 보여주었으며, 반면 무제한 전략 (Least Injection 등) 은 이론적 비용이 가장 낮지만 탐지가 활발한 환경에서는 덜 실용적일 수 있음을 보여주었습니다.

5. 의의 및 한계

의의:
본 논문은 온라인 학습의 이론적 적대적 강건성과 실제 보안 간의 격차를 해소합니다. "무제한, 라운드별 보상 조작"이라는 가정이 실제 시스템을 공격하는 난이도를 과대평가한다는 점을 입증합니다. 희소하고 유계되며 시간적으로 분산된 가짜 데이터가 표준 밴드 알고리즘을 전복시킬 수 있음을 보여줌으로써, 고위험 분야에서 사용되는 순차적 의사결정 시스템의 치명적인 취약점을 드러냈습니다. 제안된 억제 보조정리는 경험적 평균과 탐색 보너스에 의존하는 알고리즘의 취약성을 분석하는 일반적인 도구를 제공합니다.

한계 (저자들이 명시한 바):

• 수동 학습자: 분석은 방어 메커니즘 (예: 필터링 또는 감사) 없이 모든 피드백을 처리하는 수동 학습자를 가정합니다.
• 확률적 설정: 현재 프레임워크는 확률적 밴드로 제한되어 있으며, 컨텍스트 밴드나 강화 학습으로 확장하는 것은 여전히 미해결 문제입니다.
• 탐지 위험: 현재 모델은 이상 탐지 또는 팔 단위 감사를 수행하는 적응형 학습자와의 동적 상호작용을 명시적으로 포착하지는 않습니다.

저자들은 결과가 고전적 강건성 보장과 실제 보안 간의 격차를 노출하지만, 향후 연구는 이상 탐지 및 공격자와 적응형 방어 학습자 간의 역동적 상호작용과 같은 방어책을 조사해야 한다고 결론지었습니다.