CHORUS: a Programming Framework for Building Scalable Differential Privacy Mechanisms
タイトル: CHORUS: a Programming Framework for Building Scalable Differential Privacy Mechanisms
著者: Noah Johnson, Joseph P. Near, Joseph M. Hellerstein, Dawn Song
TL;DR
最先端の差分プライバシーメカニズムを大規模に開発・展開するためのフレームワーク
データ処理タスクをカスタムコードではなく、DBMSを活用することでスケーラブルな実装をサポート
Chorusはオープンソースソフトウェアで、本番環境への導入を前提に設計されており、実際Uber社の内部分析業務にChorusを使用
本文
背景
差分プライバシーは個人のプライバシーを保護しながらデータの統計的分析を可能にするゴールドスタンダードになりつつある。しかし、学術的な研究が進んでおり、メカニズムが豊富に提供されているにもかかわらず,差分プライバシーは実際には広く採用されず、特殊なユースケースに限られている。特に差分プライバシーの実用化に向けた大きな課題の一つとして、差分プライバシーメカニズムを大規模に展開できるかどうか、つまり、スケーラビリティの課題がある。
差分プライバシーを実現する最も単純なメカニズムとして、ラプラスメカニズムのようにデータ分析者のクエリに対してそのの結果にノイズを加えるというのがある。このメカニズムは、DBMSを利用してデータ分析者のクエリを実行し、その結果に適切な量のノイズを加えることで既存の高性能DBMS上に簡単に展開することが可能であり、またDBMSを利用して実際のデータ処理タスクを実行するため、このアプローチは拡張性に優れている。このようなアプローチはポストプロセッシング・アーキテクチャと呼ばれており、適切なメカニズムであればポストプロセッシング・アーキテクチャはスケーラビリティの問題を解決が可能である。一方で、最近開発されたメカニズムの多くはポストプロセッシング・アーキテクチャでは実装できない問題がある。たとえば、合計クエリでは、外れ値の影響を適用するために、データを合計する前にデータをクリッピングするためにクエリの実行方法を変更(クエリの変更)する必要があるが、ポストプロセッシング・アーキテクチャのアプローチは、このようなメカニズムとは根本的に互換性がない(データ分析者のクエリを変更せずに実行し、その結果を後処で差分プライバシーを実現することは不可能)。その結果,近年開発された差分プライバシーメカニズムの多くには,スケーラブルな実装が存在しない。
cipepser.icon 問題提起がシステムアーキテクト的でおもしろい
Chorus
最先端の差分プライバシーメカニズムを大規模に開発・展開するためのフレームワーク
データ処理タスクをカスタムコードではなく、DBMSを活用することでスケーラブルな実装をサポート
標準のSQLデータベースとの統合をサポート
SQLは高性能の本番DBMSで最も一般的に使用される言語であるため、ChorusはSQLクエリを直接操作できるように設計されている
カスタムRuntimeの代わりに標準のSQLデータベースエンジンを使用することで、数十年にわたる研究とエンジニアリングの経験に基づいて構築された最新のデータベースの信頼性、スケーラビリティ、およびパフォーマンスを活用
最近開発された差分プライバシーメカニズムが実装可能
クエリの変更や新規生成が必要なメカニズムであっても容易に開発可能
Clippingを用いた合計処理のような単純なメカニズムと、wPINQ、MWEM、マトリックスメカニズムのような複雑なメカニズムの両方を実装済
Chorusはオープンソースソフトウェアで、本番環境への導入を前提に設計されている
Uber社の内部分析業務にChorusを使用
インサイダー攻撃から顧客のプライバシーを保護するのと、GDPRの要件に確実に準拠を目的としている
アーキテクチャ
データ分析タスクに差分プライバシーを適用するための既存のシステムは、Deep IntegrationもしくはPost Processingのアーキテクチャタイプを採用している
https://gyazo.com/c6b49cc56a107a3d756fa223a00a7358
(a) Deep Integration
独自の専用DBMSを提供
性能やスケーラビリティ、クエリの最適化、リカバリビリティ、ディストリビューションなどの点で既存のDBMSと同等の性能を実現することは困難
PINQ、Weighted PINQ、GUPT、Airavat
(b) Post Processing
拡張性が高く、DBMSに依存しない(既存のDBMSとの互換性がある)
元のクエリのセマンティクスを変更しないメカニズムのみサポートしており、元のクエリの実行方法を変更するメカニズムとは根本的に互換性がない
Elastic Sensitivity、PINQ、Restricted Sensitivity
(c) Chorus
the cooperative architecture(協調型アーキテクチャ?)
センシティブなデータを保持する既存の無修正(unmodified)SQL DBMSと統合
後処理を行ったり、クエリの実行方法を変更したりすることができ、数多くの差分プライバシーメカニズムの実装が可能
DBMSに依存しないため、データベースを変更する必要も、専用のデータベースエンジンに切り替える必要がない。そのため、既存の高性能なDBMSを活用してビッグデータに対応可能
3つのコンポーネントで構成
rewriting
Clippingのような機能を実行するためにクエリを修正
分析者のワークロードのクエリを修正したり、新しいクエリを生成したりして、新しいSQLクエリを生成することをサポート
クエリのParserはApache Calcite
code:sql
SELECT SUM(trip_distance) FROM trips
⇓
SELECT SUM(max(0, min(100, trip_distance))) AS sum FROM trips
analysis
差分プライバシーに必要なノイズの量などの性質を決定するためにクエリを分析
ワークロード内のクエリを分析し、sensitivityを決定
クエリのsenstivity
The stability of a relationは1。ベースとなるテーブルから関係を作成するために使用される変換(transformaiton)が,集約前の行数をどれだけ変化させるかを測定。stabilityが1であれば、これらの変換によって行数が変化しない
単一のテーブルから生じるrelationについてはstabilityは1、それ以外の場合はstabilityは無限大
jkcomment.icon 無限大 is...
jkcomment.icon SUMのglobal sensitivityは(u-l)・s、COUNTはs(sはstability)
https://gyazo.com/92f56000193aff986f569aef23572c21
post-processing
クエリの実行結果を処理
クエリ結果の後処理をサポート(結果の結合やノイズの追加など)
DBMSが書き換えられたクエリ(わずかな変更しかない)を実行できるかどうかだけに依存
ワークフロー
シンプルにクエリ分析 -> クエリ書き換え -> クエリ実行と後処理の流れ
クエリの例
code:sql
Original query:
SELECT COUNT(*) FROM orders
Rewritten query:
SELECT COUNT(*) + 20.0 * (CASE WHEN RAND() - 0.5 < 0 THEN -1.0 ELSE 1.0 END * LN(1 - 2 * ABS(RAND() - 0.5))) FROM public.orders
性能評価
実装したメカニズムが正確な結果を出せるかどうかではなく、CHORUSのアプローチのスケーラビリティを示すことを目的としてしている
Uberの本番データベースからサンプリングしたデータのデータベースを使用
sensitivityベースのelastic sensitivityとrestricted sensitivityで評価
Performance
8つのテーブルに格納されているtrip、rider、driver info、その他の関連データを含む3億件のレコードを使用
https://gyazo.com/d7f54d5a45f42a106c1cc01e53e1120e
実行するクエリが速い(100ms未満)場合、オーバーヘッドの割合が最も高い
WPINQは?
クエリの実行方法を大幅に変更。これによってクエリの実行時間が増加
Utility
$ \epsilon = 0.1
Elastic Sensitivityの場合、$ δ = \dfrac {1} {n^2} (nはデータベースのサイズ)
https://gyazo.com/67a0cfa3a1546044c4b0ac112b386d2e
サンプルサイズが大きいクエリの大部分は、相対的な誤差が非常に小さい
1,000人以下の集団を対象としたクエリでは,どちらも正確な結果(1%以内の誤差など)が得られなかった
Joinありのクエリでは差分プライバシーの確保がより困難になる
評価に使用した両方のメカニズムにおいて,誤差が1%未満のクエリの割合は,Joinありのクエリの方がJoinなしのクエリよりもはるかに小さくなる
参考
Clipping
属性値に上限と下限を設定(upper, lower)
Sensitivity
データベースに行が追加されたり削除されたりしたときに、クエリの出力がどれだけ変化するか、つまり、1 つの行が分析に与える影響の範囲を示す数値的尺度
Transformation
あるデータセットから別のデータセットへの決定論的なマッピングのことである。これらは、値を何らかの方法で要約または変換するために使用される。変換の例としては、測定値と連結する前にデータを前処理し、集約するために使用される