Differential Privacy 정리

들어가며

머신러닝 기술이 발전함에 따라 어마어마한 양의 데이터들이 서버로 보내지고 있다. 이는 모델들을 학습하는 데에 많은 데이터와 컴퓨팅 자원이 필요하기 때문이다. 하지만 사용자들은 자신들의 정보, 데이터들을 서버로 보내는 것을 좋아할 리 없다. 해커들이 중간에 민감한 정보들을 훔쳐갈 수도 있고, 최근의 이루다 사건처럼 개인정보가 제대로 처리되는지 확신할 수 없기 때문이다. 오늘은 이를 해결하기 위한 방법인 Differential Privacy (DP) 에 대해 정리하고자 한다. 물론 DP는 머신러닝을 위해서 존재하는 것이 아닌 다양한 곳에 사용될 수 있는 보안에서의 용어이다.

Differential Privacy

제일 먼저 알아둘 것은 DP가 적용되는 상황이다. 우리는 데이터가 필요한 사람이고 query를 날려 데이터베이스로부터 answer를 받고 싶다. 데이터가 필요한 사람은 데이터 분석가, 머신러닝 엔지니어, 혹은 해커일 수도 있다. query는 해당 데이터셋의 평균값이나 Count값 등이 될 수 있다. 즉, 우리는 query를 여러 번 데이터셋으로 날릴 수 있으며 그로부터 여러 번의 answer를 받을 수 있는데 이 때에 dataset을 지키는 방법에 대한 내용인 것이다.

에이즈 감염 여부와 같은 민감한 설문조사를 한다고 생각해보자. 당신을 포함한 모든 응답자들은 자신이 에이즈에 감염됐는지에 대한 정보를 일절 공개하고 싶지 않을 것이다. 설문지에서 “본 설문조사는 전체 데이터에 따른 Count 값만을 결과로 제공합니다”라는 문구를 본다면 당신은 개인정보 유출이 되지 않으니 안심해도 되는걸까? 전혀 아니다. 왜냐하면, 당신이라는 한 명의 데이터가 포함되느냐 되지 않느냐에 따라 Count 값이 달라질 것이고 이는 곧 당신이 에이즈에 감염되었는지를 알려주는 것과 같기 때문이다.

위 그림에서 알 수 있듯 query가 되는 데이터셋에 Bob이 포함되었느냐 아니냐에 따라 Yes의 Count값이 달라지게 되는데, 이를 통해 Bob이 에이즈에 감염되었다는 사실을 유추할 수 있다. 이처럼 데이터셋이 “단 하나만 다를 때”를 이용하여 사용자를 식별하는 문제를 해결하는 것이 DP이다. 이름에 “Differential”이라는 단어가 쓰인 이유를 확인할 수 있다.

DP의 핵심을 짧게 요약하자면, “노이즈를 추가”하는 것이다. 만일 우리가 얼굴을 인식하는 머신러닝 모델을 만든다고 하자. 우리의 모델이 사람들의 얼굴을 input으로 받아야하는 것은 자명하지만, 이 얼굴이 누구의 얼굴인지까지 알 필요가 있을까? 위의 그림을 예시로 든다면, 정 가운데의 정도의 얼굴 사진으로도 충분히 얼굴을 인식하는 모델을 학습할 수 있다. 이 얼굴이 실제로 어떤 사람의 얼굴인지 구별할 수 있을만큼 정확한 데이터는 오히려 서버에 개인정보를 남겨두는 위험을 초래한다. 즉, DP는 “적당히” 노이즈를 추가함으로써 개인 정보 유출을 막으면서 동시에 모델의 성능/정확도도 챙기기 위한 방법인 것이다. 따라서 이 “적당히”라는 것을 찾는 방법이라고 할 수 있다.

이제 이 “적당히 노이즈를 추가”하는 것을 수식으로 쓰면 위와 같으며 이를 Epsilon Differential Privacy라고 한다. D1과 D2는 각각 두 개의 데이터셋인데, 위에서 말한 단 하나의 row만 다른 Dataset을 의미한다. 그리고 M은 mechanism이라고 불리는데 알고리즘을 의미하며 이는 AVG, COUNT, ML모델 등 데이터셋에 적용되는 알고리즘들이 될 수 있다. 따라서 이 식이 의미하는 것은 단 하나만 다른 Differential Dataset에 대해 적용한 알고리즘 M의 결과가 구분이 불가능해야함을 의미한다. 단, 이 구분 불가능이 \(e^\epsilon\) 의 비율만큼만 차이가 나도록 해야한다는 것인데 이는 차후에 자세히 설명하겠다.

간단히 생각해보자, 만일 \(\epsilon\) 이 0이 된다고 생각해보자. 이는 Differential Dataset에 대해 결과가 항상 같아지기 때문에 완전한 Privacy를 보존한다는 의미이다. 왜냐하면 어떤 유저 (예컨대 이전 예시에서 Bob)가 데이터셋에 포함되든 포함되지 않든 결과 (Yes의 Count)가 같아져야한다는 뜻이기 때문이다. 쉽게 생각해보면 Count값을 반환하되 무조건 1로 반환하는 알고리즘(메커니즘)의 경우 결과를 가지고 Bob이 에이즈에 걸렸는지 아닌지 확신할 수 없게 된다(완전한 Privacy). 반대로 \(\epsilon\) 이 커진다면 결과가 달라진다는 의미이기 때문에 Privacy를 점점 잃고 있는 그대로 결과를 전달한다는 의미이다. 이렇게 Privacy Loss를 \(\epsilon\) 으로 수량화할 수 있다는 것 자체도 DP의 장점이다.

Examples

나는 분포의 차이가 \(e^\epsilon\) 의 비율만큼만 나도록 한다는 것이 쉽사리 이해되지 않았다. 왜냐하면 Count, Average같은 값들을 반환하는 알고리즘에 무슨 분포가 존재하며 또 여기서 비율을 일정하게 차이나게 한다는 것도 받아들이기 어려웠기 때문이다. 이를 이해하기 쉽게 예시를 들어보도록 하겠다.

다시 우리의 친구 Bob의 사례를 보자. 문제를 조금 바꾸어서 알고리즘은 “No 의 Count”수를 알려준다고 생각해보자. DP가 적용되기 전에는 자명하게 No의 Count수가 각각 2와 3인 것을 확인할 수 있다. 그런데 여기서 우리가 두 개의 동전던지기를 통해 이 Count 수에 Noise를 섞어서 output을 준다고 생각해보자. 물론 Noise를 섞는 이유는 DP를 적용해 Bob이 에이즈에 걸렸다는 사실을 유출하지 않기 위함이다.

즉, 각각의 row에 대해 에이즈에 감염되었는지 아닌지를 return할 때 동전던지기를 통해 실제 값을 전달할 지 Noise를 전달할 지 결정하는 것이다. 이 때 처음 던지는 동전을 동전A, 두 번째로 던지는 동전을 동전 B라고 하자. 여기서 동전B는 앞면이 나올 확률이 0.5, 뒷면이 나올 확률이 0.5인 일반 동전이라고 가정한다. 이 때 동전A의 앞면이나올 확률에 따라 원래의 메커니즘 (“No의 Count를 반환”) 에 얼마나 Noise가 반영되는 지가 결정된다.

먼저 동전A의 앞면이 나올 확률이 1이라고 하자. 이 땐 무조건 정확한 사실만을 반환해야하기 때문에 D1 (Alice, Bob, Charlie의 데이터셋을 D1, 나머지를 D2라고 하자) 의 경우 No: 2, D2의 경우 No: 3이 Output으로 반환되며 확률 분포는 존재하지 않고 Deterministic하게 결과를 얻어낼 수 있다. 하지만 우리가 알고 있듯이 이는 전혀 Privacy를 보장할 수 없다.

이번엔 반대로 동전A의 앞면이 나올 확률이 0이라고 하자. 이 때에는 결과값이 완전히 랜덤으로 결정되게 된다. 따라서, 두 데이터셋 D1, D2에 대한 메커니즘 M (No 의 Count) 은 평균이 1.5 (데이터 Row는 3개, 확률은 0.5) 인 정규분포의 형태로 Output을 반환하게 된다. 이처럼 Noise가 추가됨으로써 기존의 Deterministic한 메커니즘도 확률분포의 형태로 Output을 반환하는 것이다. 이 경우에는 완전한 Privacy가 보장이 된다. 하지만, 해당 결과값은 쓸모가 없는 쓰레기값이다.

따라서 동전A의 앞면이 나올 확률을 적당히 조절해준다면, 확률분포를 비슷하게 가져가면서도 유의미한 결과를 반환할 수 있다. 이 때 두 확률 분포의 비율의 차이 (그림에서 녹색 선) 를 최대 \(e^\epsilon\) 로 가져가는 것이 이전에 설명했던 epsilon differential privacy이다. 결과적으로 두 Differential Dataset에 대한 메커니즘 M의 결과가 어느 정도의 비율로 구분 불가능하도록 Noise를 추가하는 과정임을 확인할 수 있다. 예컨대 우리가 해커이고 DP가 적용된 메커니즘 M을 통해 D1에 대해 query를 날렸을 때 2가 output으로, D2에 대해 3이 output으로 나왔다면 쉽사리 Bob이 에이즈라고 결정내릴 수 있을까? 이젠 아니다. 왜냐하면 메커니즘 M의 output은 DP에 의해 Noise가 추가된 output이기 때문에 Bob이 에이즈가 아니었음에도 2, 3을 output으로 반환받았을 수도 있기 때문이다.

하지만 명확히도 실행횟수, 즉 query 횟수가 많아지면 많아질 수록 우리는 output의 분포를 그려볼 수 있으며 이렇게 많은 query 이후에는 어쩔 수 없이 Privacy breach가 발생하게 된다. 즉, 위 사례에서 D1, D2에 대한 많은 query 후에는 실제로 분포를 그려볼 수 있으며 Bob이 에이즈에 감염되었다는 사실을 유추할 수 있는 것이다. 이처럼 DP에는 “Composition Theorem”이라는 것이 존재하는데, 이는 DP가 적용된 메커니즘을 n번 반복하면 privacy breach의 양이 n배가 됨을 의미한다. 따라서 DP가 실제로 적용된 곳들에서는 Max Query Number를 사전에 정의하여 privacy를 보호하고 있다.

How much noise?

하지만 도대체 얼만큼의 noise를 추가해야하는가? 라는 질문이 남는다. 이 부분은 수학적으로 복잡하게 증명도 해야하고 각 서비스의 목적, 허용하는 Privacy breach에 따라 천차만별이다. 따라서 일반적으로 정리할 수는 없는데, 아주 간단하게만 noise의 양에 영향을 주는 변수를 생각해보자. 바로 메커니즘 M의 sensitivity, 즉 메커니즘이 얼마나 예민하냐에 따라 다르다고 할 수 있다. 왜냐하면 메커니즘의 output 확률분포가 굉장히 급격하게 변한다면 (기울기가 가파르다면, 예민하다면) noise를 많이 주어야 M(D1), M(D2)를 구분 불가능하게 만들 수 있을 것이기 때문이다. 따라서 output의 확률분포의 분산에 따라서 noise를 얼마나 주어야 할지를 정할 수 있을 것이다.

Machine Learning?

머신러닝 모델들이 좋은 성능을 보여줌과 동시에 각종 데이터들을 서버로 올리는 일이 많아졌고, 이에 따라 개인정보가 유출되는 일들이 잦아지고 있다. 예컨대 Netflix Prize 라는 영화 예측을 위한 익명 평점정보들을 IMDb라는 공개 평점 사이트 (우리나라로 치면 왓챠피디아) 의 정보와 결합하여 사용자를 식별하는 연구 등을 예로 들 수 있다. 사람들마다 본 영화가 다르고 user-item matrix가 굉장히 sparse하다는 것을 이용한 것이다. 또한, 얼굴 인식 모델의 경우 어떤 사용자가 Training set에 있는 지 등을 역으로 추적할 수도 있다고 한다.

결국 머신러닝에서의 DP는 큰 그림에서는 동일하다. 두 개의 Differential Dataset에 대해 ML 모델의 output을 구분 불가능(indistinguishable)하게 만들고 개인정보를 유추할 수 없게 만드는 것이다.

DP를 적용하는 데에는 여러 가지 방법이 있지만 대표적인 방법은 아래와 같다.

우리의 머신러닝 모델은 언제 개인정보를 유출할 수 있을까? 바로 특이한 training data에 대해서 학습할 때이다. 왜냐하면 특이한 Data의 경우 학습 과정에 Gradient가 커질 것이고 해당 input에 더욱 예민하게 반응하는 모델이 형성될 것이기 때문이다. 따라서 학습 과정의 gradient에 noise를 추가하게 된다면 특정데이터에 편향된 update를 막을 수 있다.

머신러닝 모델에서 위와 같은 DP 방법은 더욱 특별한 의미가 있는데, 바로 regularization과 동일한 역할을 한다는 것이다. 똑똑한 분들은 눈치 챘겠지만 noise를 더한다는 것과 regularization term을 두는 것은 언뜻보기에도 비슷하다. 따라서 해당 방법을 소개한 연구 에서는 DP가 generalization 성능에도 기여를 할 수 있다는 점(regularization의 장점과 마찬가지) 을 어필하고 있다.

정리

DP는 애플, 마이크로소프트, 구글, 우버와 같은 많은 IT 기업들이 이미 활발하게 사용하고 있는 기술이다. 예컨대 애플은 아이폰 내에서 사용자의 이모지 사용 로그를 서버로 올리는 데에 DP를 적용하고 있고, 마이크로소프트는 사용자의 위치 기록에 Noise를 추가하여 수집한다. 또한 머신러닝 분야에서도 활발히 연구되면서 Federated Learning과 함께 자주 논문에서 등장하는 것을 확인할 수 있다. 앞으로는 머신러닝 모델 자체의 발전도 중요하지만 이를 현실에 seamless하게 적용하기 위한 많은 방법들이 각광받을 것 같다는 생각이 든다.

References

1. https://www.youtube.com/watch?v=lg-VhHlztqo
2. https://aircloak.com/explaining-differential-privacy/
3. https://www.nist.gov/blogs/cybersecurity-insights/differential-privacy-privacy-preserving-data-analysis-introduction-our
4. https://towardsdatascience.com/understanding-differential-privacy-85ce191e198a
5. https://blog.tensorflow.org/2019/03/introducing-tensorflow-privacy-learning.html