💻 computer science

Selection Integrity for LLM Graph Memory: An Accumulability Criterion for Information-Flow-Blind Retrieval

이 논문은 기존의 LLM 그래프 메모리용 출처 기반 방어 기법들이 인증된 콘텐츠를 변경하지 않으면서도 신뢰할 수 없는 입력이 검색 결과를 조작하는 구조적 선택 공격(structural selection attacks)에 근본적으로 무력하다는 점을 밝히고, 인증된 서브그래프 상에서 검색을 재계산함으로써 선택 무결성을 강제하여 중요한 동작의 은밀한 오도(misdirection)를 방지하면서도 지연 시간 오버헤드는 미미한 \authselect\ 메커니즘을 제안한다.

원저자: Zeming Fei, Hongming Fei, Xiaoyang Wang, Yang yang, Prosanta Gope, Biplab Sikdar, Ying Zhang

게시일 2026-06-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Zeming Fei, Hongming Fei, Xiaoyang Wang, Yang yang, Prosanta Gope, Biplab Sikdar, Ying Zhang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 질문에 답하고 의사결정을 내릴 수 있도록 돕는, 사실들을 정리한 거대하고 체계적인 노트(기록장)를 가진 아주 똑똑하고 유능한 비서(AI 에이전트)가 있다고 상상해 보십시오. 이 노트는 단순한 목록이 아니라, 연결의 그물망(그래프)입니다. 만약 당신이 "앨리스는 밥과 친구다"라고 적으면, 비서는 그 두 이름 사이를 연결합니다. "밥은 피자를 좋아한다"라고 적으면, 비서는 밥과 피자를 연결합니다.

이 논문이 해결하고자 하는 문제는, 단 하나의 거짓말도 쓰지 않고도 이 비서를 교묘하게 속이는 방법입니다.

문제점: "보이지 않는 손" 공격

보통 우리는 해커가 노트에 가짜 사실을 주입하는 것(예: "달은 치즈로 만들어졌다"라고 쓰는 것)을 걱정합니다. 현재의 보안 시스템은 이를 잡아내는 데 능숙합니다. 그들은 다음과 같이 확인합니다: "이 특정 문장이 노트 안에 있는 내용으로서 신뢰할 수 있는가?" 만약 문장이 가짜라면, 시스템은 이를 차단합니다.

하지만 이 논문은 **선택 무결성 결함(Selection Integrity Blindness)**이라 불리는 새로운 형태의 보이지 않는 공격을 밝혀냈습니다.

비유: 사서와 지도
사서(AI)가 당신을 위해 최고의 책을 찾기 위해 지도를 사용하는 상황을 상상해 보십시오.

공격: 해커는 가짜 책을 쓰지 않습니다. 대신, 배경에서 조용히 지도의 화살표들을 옮깁니다. 그들은 "달"과 "치즈"를 연결하는 새로운 선을 그려 넣습니다.
결과: 당신이 "달은 무엇으로 만들어졌나요?"라고 물으면, 사서는 지도를 봅니다. 해커가 화살표를 옮겨 놓았기 때문에, 사서의 경로는 이제 (신뢰할 수 있는 저자가 쓴) '치즈'에 관한 실제적이고도 정당한 책으로 이어집니다. 하지만 그 책은 당신의 질문에 대한 잘못된 답이 됩니다.
맹점: 사서는 자신이 찾은 책을 검사합니다. 그 책은 실제이며 인증된 책입니다! 보안 시스템은 말합니다. "모두 통과! 이 책은 신뢰할 수 있는 출처로부터 온 것입니다." 시스템은 눈이 멀어 있습니다. 왜냐하면 시스템은 오직 책(내용)만을 확인했을 뿐, 그곳으로 이끈 지도(구조)는 확인하지 않았기 때문입니다.

이 논문은 이를 **"출처 없는 구조적 쓰기(No-Source Structural Write)"**라고 부릅니다. 공격자는 AI가 읽게 될 어떤 내용(구절)도 추가하지 않고, 오직 연결 관계(에지)만을 변경합니다. 결과적으로 AI는 "깨끗한" 사실을 바탕으로 잘못된 결정을 내리게 되는데, 이는 단지 그 사실로 향하는 경로가 탈취되었기 때문입니다.

증명: 28건의 잘못된 송금

연구진은 단순히 이론만 제시한 것이 아니라, 이를 직접 테스트했습니다.

연구진은 AI 에이전트가 올바른 사람에게 돈을 보내야 하는 시나리오를 설정했습니다.
공격자는 그래프의 연결 구조를 조용히 재구성했습니다.
결과: AI는 자신의 "신뢰할 수 있는" 논리를 따랐으나, 28건의 실제적이고 되돌릴 수 없는 송금을 엉뚱한 사람에게 보냈습니다.
보안 실패: 기존의 보안 검사(정보 흐름 제어)는 수취인을 확인하고 "이 사람은 실제 인물이며 신뢰할 수 있다"라고 판단하여 송금을 허용했습니다. 시스템은 그 사람이 선택된 이유가 오염된 지도 때문이라는 사실을 놓쳤습니다.

해결책: AUTHSELECT

비유: 더블 체크를 하는 사서
사서가 찾은 책을 확인하는 것에 그치지 않고, AUTHSELECT는 다음과 같이 묻습니다: "만약 우리가 지도에서 수상한 화살표들을 모두 제거한다면, 사서가 여전히 같은 책을 고를까?"

1단계: AI는 전체 그래프(해커의 숨겨 된 화살표를 포함한)를 사용하여 답을 선택합니다.
2단계: 시스템은 "신뢰할 수 없는" 화살표들(해커가 건드렸을 가능성이 있는 화살표들)을 일시적으로 모두 지웁니다.
3단계: AI는 "깨끗한" 지도만을 사용하여 다시 한번 답을 선택합니다.
4단계: 만약 두 답이 다르다면, 시스템은 지도가 오염되었다고 가정합니다. 시스템은 첫 번째 답을 무시하고 두 번째 답(깨끗한 지도로 얻은 답)을 사용합니다.

이 방어 기제는 빠르며(단 2~3%의 지연 시간만 추가됨), 28건의 잘못된 송금을 포함한 모든 이러한 공격을 100% 차단합니다.

"마법의" 규칙: 언제 이런 일이 발생하는가?

이 논문은 정확히 어떤 유형의 AI 메모리 시스템이 취약하고 어떤 것이 안전한지를 밝혀냈습니다. 그들은 이를 **"누적 가능성 기준(Accumulability Criterion)"**이라고 부릅니다.

취약한 시스템 (흐르는 강물): 개인화 페이지랭크(Personalized PageRank)(중요도를 계산하기 위해 그래프를 "걷는" 방식)를 사용하는 시스템은 강물과 같습니다. 만약 상류에 작은 댐(몇 개의 가짜 연결)을 건설한다면, 물줄기 전체를 새로운 곳으로 돌릴 수 있습니다. 이러한 시스템은 취약합니다.
안전한 시스템 (고정된 선반): 단어 간의 거리를 측정하거나 고정된 후보 목록을 사용하는 시스템은 책장에 꽂힌 책과 같습니다. 당신은 선반을 재배치하여 다른 책이 나타나게 할 수 없으며, 오직 이미 있는 책들을 움직일 수 있을 뿐입니다. 이러한 시스템은 면역력이 있습니다.

핵-테이크아웃: 핵심은 시스템이 지도를 얼마나 의존하느냐가 아니라, 결과값을 바꾸기 위해 지도를 재경로화(reroute) 할 수 있는지 여부입니다.

요약

위협: 공격자는 메모리 그래프의 연결을 비밀리에 변경함으로써, AI 에이전트가 잘못된 "신뢰할 수 있는" 사실을 선택하도록 속일 수 있습니다.
실패: 현재의 보안은 사실이 진짜인지만을 확인하며, 그 사실로 향하는 경로가 탈취되었는지는 확인하지 못합니다.
해결책: AUTHSELECT는 의심스러운 연결을 제거한 후 답을 다시 계산함으로써 작동합니다. 만약 답이 바뀐다면, 경로가 오염되었음을 알 수 있습니다.
교훈: 모든 그래프 기반 메모리가 동일하게 안전한 것은 아닙니다. 어떤 것들은 공격자에 의해 "경로가 재설정"될 수 있지만, 어떤 것들은 그렇지 않습니다. 우리는 데이터의 신뢰성뿐만 아니라, 시스템의 "재경로화 가능성(reroutability)"을 확인해야 합니다.

기술 요약: LLM 그래프 메모리의 선택 무결성 (Selection Integrity)

1. 문제 정의

본 논문은 그래프 기반 메모리 구조(예: HippoRAG, Graphiti)를 사용하는 대규모 언어 모델(LLM) 에이전트의 장기 메모리(Long-Term Memory, LTM) 시스템에서 발생하는 치명적인 보안 취약점을 다룹니다. 기존의 방어 기제들은 검색된 레코드의 출처(provenance of retrieved records), 즉 '내용'을 검증하는 데 집중하고 있으나, **선택 과정 자체의 출처(provenment of the selection process)**는 고려하지 못하고 있습니다.

사각지대 (The Blind Spot)

그래프 메모리 시스템에서 검색은 단순한 조회가 아니라, 쓰기가 가능한 그래프 위에서 수행되는 전역적 구조 연산(예: Personalized PageRank)입니다.

공격 벡터: 신뢰할 수 없는 주체(예: 해킹된 피어 에이전트 또는 오염된 도구 결과)는 검색 가능한 텍스트 구절을 작성하지 않고도 구조적 데이터(엣지, 엔티티 병합, 관계)를 작성할 수 있습니다.
메커니즘: 이러한 "출처 없는(no-source)" 구조적 쓰기는 그래프 토폴로지를 변경하여, 선택 알고리즘이 인증된 사실들을 우선순위에서 밀어내고 다른 곳으로 경로를 재설정하도록 만듭니다.
기존 방어 체계의 실패: 충실한 정보 흐름 제어(Faithful Information-Flow Control, IFC) 및 출처 검증 방식은 검색된 컨텍스트와 근거를 검사합니다. 하지만 선택된 사실들은 여전히 인증된 상태이며, 악의적인 구조적 쓰기는 근거(justification)에 나타나지 않기 때문에, 이러한 방어 체계들은 방어가 전혀 없는 상태와 동일한 **바이트 단위로 동일한 결정(byte-identical decision)**을 내리게 됩니다. 결과적으로 에이전트는 잘못되었지만 인증된 정보에 따라 행동하게 되어, 돌이킬 수 없는 오류(예: 잘못된 원장 이체)를 범하게 됩니다.

2. 방법론 및 이론적 프레임워크

누적 가능성 기준 (The Accumulability Criterion)

저자들은 어떤 그래프 메모리 셀렉터가 이 "선택 채널(selection channel)"에 취약한지 판단하기 위한 검증 가능한 기준을 제안합니다.

정의: 셀렉터가 구조적 항(structural term)을 통해 상위- $k$ 멤버십의 충분한 점유율을 **재배분(reallocate)**하여 선택된 집합을 뒤집을 수 있다면, 해당 셀렉터는 채널을 허용하는 것으로 간了.
핵심 차이점: 취약성은 구조에 대한 '의존성'이 아니라 **'재배분 가능성(reallocatability)'**에 의해 결정됩니다.
- 취약함: **Personalized PageRank (PPR)**와 같은 셀렉터는 주입된 엣지에 의해 보존된 랜덤 워크 질량(random-walk mass)이 재배분되어 타겟을 밀어낼 수 있습니다(특히 낮은 바닥(low-floor)을 가진 다중 홉 타겟의 경우).
- 면역 있음: 후보 멤버십이 내용에 의해 고정되어 있거나(예: 벡터 검색), 구조적 신호가 범위가 제한된 재순위화(rerank) 역할을 하는 경우(예: Graphiti의 노드 거리). 이러한 방식은 풀(pool) 외부의 항목을 도입하거나 높은 마진을 가진 타겟을 밀어낼 수 없습니다.

불가능성 정리 (The Impossibility Theorem)

본 논문은 **P-vs-S 발산 정리(P-vs-S divergence theorem)**를 증명합니다:

P (Provenance, 출처): 가시적인 내용이 인증되었는지 확인합니다.
S (Selection Integrity, 선택 무결성): 인증되지 않은 구조를 제거했을 때 결과가 변하는지 확인합니다.
결과: 근거(justification)는 완전히 인증되었으나 선택 과정이 인증되지 않은 구조에 의해 교란된 경우(발산 집합 $D$ ), $P$ 와 $S$ 는 서로 발산합니다. 이 채널을 폐쇄하려는 방어 체계는 반드시 인증된 서브그래프 상에서 선택 과정을 검사하고 재실행(replay)해야 하며, 이는 실질적으로 '선택 무결성' 방어로 기능해야 합니다. 선택 후 단계의 방어(검색된 항목의 재순위화 등)는 증명 가능한 수준에서 불충분합니다.

3. 방어 기제: AUTHSELECT

저자들은 그래프 메모리 선택 무결성을 위한 최초의 원칙적인 방어 기제인 AUTHSELECT를 소개합니다.

메커니즘:
1. 인증되지 않은 구조적 쓰기를 식별합니다(쓰기 출처/소스 채널 기준).
2. 이러한 쓰기를 제거하여 인증된 서브그래프( $G_{auth}$ )를 형성합니다.
3. 인증된 서브그래프( $G_{auth}$ ) 상에서 네이티브 셀렉터를 **재실행(Replay)**하여 후보 결과를 생성합니다( $a_{G_{auth}}$ ).
4. 네이티브 결과( $a_G$ )와 재실행된 결과를 비교합니다.
5. 두 결과가 다르면, 시스템은 $a_G$ 를 거부하고 $a_{G_{auth}}$ 를 사용합니다(또는 권한 요구 사항에 따라 에스컬레이션함).
특성: 이는 건전하며(인증되지 않은 구조를 제거한다고 해서 인증된 내용을 차단하지 않음), 비자명하며(클린 데이터에 대한 과잉 차단 없이 채널을 폐쇄함), 실용적입니다.

4. 실험 결과

평가는 세 가지 그래프 메모리 시스템(HippoRAG2, Graphiti, Mem0)과 네 가지 데이터셋(HotpotQA, MuSiQue, 2Wiki, LoCoMo)을 포함한 실제 멀티 세션 에이전트 메모리를 대상으로 수행되었습니다.

주요 결과

취약성 확인:
- **HippoRAG2 (PPR)**에서 채널이 열려 있음을 확인했습니다. 단 하나의 출처 없는 구조적 쓰기가 499회의 라이브 액션 중 28건의 돌이킬 수 없는 잘못된 원장 이체를 유발했습니다.
- 충실한 IFC 및 기존의 출처 검증 방식은 이러한 유해한 액션의 **100%**를 허용했습니다(방어가 없는 것과 동일한 결정).
- 이 채널은 텔레포트 바닥(teleport floor)이 낮은 저층(low-floor), 다중 홉 타겟을 공격할 때 가장 효과적이었습니다.
방어 효능:
- AUTHSELECT는 모든 데이터셋과 공격 시나리오에서 피해를 0.000으로 줄였습니다.
- 이는 제로 오버블로킹(클린 데이터에서의 오탐 없음)과 단 2~3%의 지연 시간 오버헤드만으로 달성되었습니다.
선택 전 무결성(Pre-Selection Integrity)의 필요성:
- 발표된 선택 후 방어 기제들(예: A-MemGuard, 베이지안 신뢰 점수 산정, 컨센서스 체크)은 이 채널에 대해 맹목적이었으며, 발산 집합에 대해 "방어가 없는 것"과 동일한 성능을 보였습니다.
- 오직 선택 전 재도출(AUTHSELECT)만이 채널을 폐쇄할 수 있었으며, 이는 불가역적 상관관계(irreducibility corollary)를 확인시켜 줍니다.
기준의 예측력:
- 제안된 기준은 Graphiti의 노드 거리(node-distance) 셀렉터가 높은 구조적 의존성에도 불구하고, 상위- $k$ 멤버십을 재배분할 수 없기 때문에 면역이 있다는 것을 정확히 예측했습니다.
- 반대로, PPR은 취약한 것으로 정확히 식별되었습니다.

5. 의의 및 주장

본 논문은 자신을 단순히 그래프 메모리 보안 연구의 첫 번째가 아니라, 콘텐츠 오염(content poisoning)과 구별되는 선택 무결성(selection integrity) 문제를 식별하고 해결한 첫 번째 연구로 포지셔닝합니다.

핵심 기여: 그래프 기반 메모리에서 **선택은 전역적 속성(global property)**이며, 가시적인 콘텐츠를 주입하지 않고도 조작될 수 있음을 입증했습니다.
이론적 전환: 보안의 초점을 "검색된 사실의 출처를 확인하는 것"에서 "선택 과정의 무결성을 확인하는 것"으로 전환합니다.
실질적 영향: 선택 무결성이 없다면, 에이전트가 완벽하게 인증된 증거를 제시하더라도 오염된 그래프 토폴로지에 의해 실세계 액션(예: 금융 이체)을 수행하도록 은밀하게 유도될 수 있음을 보여줍니다.
겸허한 태도: 저자들은 모든 그래프 메모리 보안 문제를 해결한다고 주장하지 않습니다(예: 인증된 콘텐츠를 작성하는 신뢰할 수 있는 주체가 나중에 클러스터링되는 문제 등). 그들의 주장은 조건적입니다: 그래프 메모리가 구조를 쓰기 가능한 표면으로 노출하고 누적 가능한 함수를 통해 선택을 수행할 때, 무결성은 반드시 선택 단계를 보호해야 합니다.

요약하자면, 본 논문은 그래프 메모리에서 충실한 출처(faithful provenance)만으로는 불충분하다고 주장합니다. 이 선택 채널을 닫는 유일한 방법은 인증된 서브그래프 상에서 선택을 재계산하여 선택 무결성을 강제하는 것이며, 이는 제안된 AUTHSELECT 메커니즘을 통해 수행됩니다.