3 PRIVANALYZER：強制執行隱私政策的靜態分析

本節介紹PRIVANALYZER，這是一個用于強制執行由PRIVGUARD追蹤的隱私政策的靜態分析器**。我們首先回顧LEGALEASE政策語言，我們使用它來正式編碼政策，然后描述如何靜態地強制執行它們**。正式模型推遲到附錄A。

3.1 背景與設計挑戰

LEGALEASE是一個不斷增長的工作體系中的一個例子，這個體系探索了編碼隱私政策的正式語言。相關工作的完整討論出現在第5節。我們采用LEGALEASE來表達PRIVGUARD政策，因為它具有表達能力強、正式語義和可擴展性。

Sen等人開發了一個名為GROK的系統，該系統結合靜態和動態分析來強制執行LEGALEASE政策。GROK構建了一個數據依賴圖，該圖編碼了所有敏感數據的流動，然后應用一組推理規則來檢查圖中的每個節點是否滿足政策。GROK結合了系統日志的分析和有限的靜態分析來構建圖表。

GROK方法提出了兩個挑戰。首先，該方法是一種啟發式：它檢查程序的語法屬性和程序的個別執行（通過系統日志），因此可能會因為隱式流而錯過政策違規行為。其次，GROK方法要求使整個數據流圖顯式化；在具有許多數據流的大型系統中，構造這樣的圖可能是不可行的。

PRIVANALYZER被設計為一種替代方案，旨在解決這兩個挑戰。它使用基于抽象解釋的靜態分析，而不是GROK的啟發式分析，并通過構建可組合的剩余政策來避免使數據流圖顯式化。

3.2 策略語法與語義

PRIVANALYZER執行在LEGALEASE 中指定的隱私策略，一個用于使用各種類型的屬性表達策略的框架。屬性在概念格中被組織起來，提供了屬性值的偏序關系。我們根據圖3中的語法來表達策略（這與LEGALEASE的語法略有不同）。一個策略由頂級的ALLOW關鍵字開始，其后是用AND（表示合取）和OR（表示析取）分隔的條款。例如，以下簡單的策略指定醫生或研究者可以檢查分析結果，只要分析中沒有使用未成年人的記錄：

ALLOW (ROLE Doctor OR ROLE Researcher)
AND FILTER age >= 18

Sen等人使用一組推理規則和每個屬性的概念格給出的偏序關系定義了LEGALEASE策略的形式語義。我們采取相同的方法，但是使用基于抽象域的新屬性框架而不是概念格。我們的方法使PRIVPOLICY能夠以更具表達力的要求編碼策略，如基于行的訪問控制和使用隱私增強技術等屬性。屬性是LEGALEASE中的基本構建塊。Sen等人描述了一組有用的屬性。我們用兩個新屬性擴展了這個集合：FILTER編碼基于行的訪問控制要求，PRIVACY要求使用隱私增強技術。

角色：ROLE屬性控制誰可以檢查數據的內容。角色被組織成部分有序的層次結構。一個特定個體可能擁有多個角色，一個特定的角色規范可能代表多個個體。例如，醫生角色可能代表具有許多不同專業的醫生。以下策略說明只有具有腫瘤學家角色的個體可以檢查其涵蓋的數據：

ALLOW ROLE Oncologist

模式：SCHEMA屬性控制可以檢查數據的哪些列。例如，以下策略允許腫瘤學家檢查年齡和病情列，但不允許檢查其他列：

ALLOW ROLE Oncologist
AND SCHEMA age, condition

隱私：PRIVACY屬性通過要求使用隱私增強技術來控制數據的使用方式。作為可用機制譜系的代表性樣本，我們的實現支持以下（易于添加）：（1）去標識化（或偽名化）；（2）聚合；（3）k-匿名性；（4）`-多樣性[41]；（5）t-接近性[40]；（6）差分隱私。例如，以下策略允許腫瘤學家在特定隱私預算的差分隱私保護下檢查年齡和病情列：

ALLOW ROLE Oncologist
AND SCHEMA age, condition
AND PRIVACY DP (1.0, 1e-5)

過濾器：FILTER屬性允許策略指定必須從分析中排除某些數據項。例如，以下策略說明腫瘤學家可以在差分隱私保護下檢查年齡超過18歲個體的年齡和病情：

ALLOW ROLE Oncologist
AND SCHEMA age, condition
AND PRIVACY DP (1.0, 1e-5)
AND FILTER age > 18

編輯：REDACT屬性允許策略要求部分或完全編輯列中的信息。例如，以下策略要求分析時編輯ZIP代碼的最后3位數字（例如，用星號替換）。(2:)符號取自Python的切片語法，表示從字符串的第三個字符到結尾的子字符串。

ALLOW ROLE Oncologist
AND SCHEMA age, condition
AND PRIVACY DP (1.0, 1e-5)
AND FILTER age > 18
AND REDACT zip (2 : )

目的：PURPOSE屬性允許策略限制數據可被分析的目的。例如，以下策略允許在滿足所有上述要求的情況下，出于公共利益目的使用年齡和醫療狀況：

ALLOW ROLE Oncologist
AND SCHEMA age, condition
AND PRIVACY DP (1.0, 1e-5)
AND FILTER age > 18
AND REDACT zip (2 : )
AND PURPOSE PublicInterest

3.3 PRIVANALYZER 概覽

PRIVANALYZER 通過抽象解釋來執行其靜態分析，這是一種用于程序正確性分析的通用框架。抽象解釋通過在抽象值而非具體（常規）值上運行程序來工作。抽象值被組織在抽象域中：部分有序的抽象值集合，能夠代表編程語言中所有可能的具體值。一個抽象值通常代表其所代表的具體值共有的特定屬性。在PRIVANALYZER中，抽象值基于前文描述的抽象域。

我們對靜態分析的方法基于抽象解釋框架的一個新穎實例化，在此實例化中，我們將策略編碼為抽象值。該方法在圖4中進行了總結。抽象解釋的使用使我們能夠系統地構建靜態分析系統，確保它與屬性值的預期語義相對應。

分析Python程序。抽象解釋的典型方法是構建一個計算抽象值的抽象解釋器。對于像Python這樣的復雜、通用目的語言，這種方法需要大量的工程工作。我們沒有從頭開始構建一個抽象解釋器，而是重用了標準。我們將附有隱私策略的抽象值嵌入為Python對象，并定義在這些對象上的抽象值操作作為方法。

例如，Pandas庫定義了對具體數據幀的操作；PRIVANALYZER定義了用于抽象數據幀的AbsDataFrame類。AbsDataFrame類具有與Pandas DataFrame類相同的接口，但其方法被重新定義為對附有策略的抽象值進行計算。我們稱重新定義的方法為函數摘要，因為它總結了原始方法的與策略相關的行為。例如，Pandas的索引函數__getitem__用于過濾，因此PRIVANALYZER對這個函數的函數摘要會從策略中移除已滿足的FILTER屬性。

def __getitem__(self, key):...if isinstance(key, AbsIndicatorSeries):# ‘runFilter‘ removes satisfied FILTER attributesnewPolicy = self.policy.runFilter(...)return Dataframe(..., newPolicy)...

多步驟分析和剩余策略。如圖4所示，PRIVANALYZER的輸出是一個剩余策略。剩余策略是程序具體輸出的新策略——它包含分析程序尚未滿足的要求。對于多步驟分析，每個分析步驟可以作為一個單獨的分析程序輸入到PRIVANALYZER中，前一步驟的剩余策略成為下一步驟的輸入策略。PRIVANALYZER是組合式的：如果將多個分析合并為一個單一的分析程序，那么PRIVANALYZER為多步驟分析返回的最終剩余策略將至少與單步版本一樣嚴格。在PRIVGUARD中使用剩余策略使得不需要明確構建全局數據流圖就可以進行組合分析，解決了之前提到的GROK面臨的挑戰。

處理庫問題。對于許多靜態分析方法，包括抽象解釋器，擴展到大型程序是一個主要挑戰。庫通常呈現最大的挑戰，因為它們往往既龐大又復雜；如果目標程序依賴于一個大型庫，那么甚至可能無法分析一個相對較小的程序。在我們的設置中（用于數據處理的Python程序），這一點尤其正確，這些程序通常利用大型庫，如pandas（327,007行代碼）、scikit-learn（184,144行代碼）、PyTorch（981,753行代碼）和Tensorflow（2,490,119行代碼）。更糟糕的是，許多庫出于性能原因是用多種語言（例如Python和C/C++）編寫的，因此需要對這些每一種語言進行分析。

我們的解決方案是開發這些庫的抽象功能規范，如之前顯示的AbsDataFrame示例，以函數摘要的形式。我們在分析過程中使用函數摘要，而不是庫本身的具體實現。這種方法允許PRIVGUARD即使對于利用用多種語言編寫的極大型庫的分析程序也能執行策略。

處理庫的方法需要一個具有庫知識的領域專家來實現其規范。根據我們的經驗，數據科學社區大體上已經同意了一組重要的常用庫（例如NumPy、pandas、scikit-learn等），因此為少數幾個庫提供規范就足以處理大多數程序。為了從經驗上驗證這一猜想，我們從Kaggle平臺隨機選取了200個程序，并計算了它們使用的庫（圖5）。結果確認了大多數數據分析程序使用類似的庫。我們已經為最常用的庫實現了規范（第4節）。幸運的是，庫函數的抽象行為往往比其具體行為簡單。我們已經實現了主要針對Numpy、Pandas和scikit-learn的380個函數摘要，并且正在積極添加更多庫的函數摘要。

我們需要正確的規范來嚴格執行隱私策略。正確實現規范重要性的一個示例是重命名函數。狡猾的內部攻擊者可能想通過重命名敏感列來繞過靜態分析。一個在架構和隱私條款中都重命名列的正確規范應該能夠緩解這種攻擊。為了減少由于此類錯誤帶來的風險，函數摘要應該是開源的，以便社區可以幫助檢查其正確性。

與動態方法的比較。我們選擇對PRIVANALYZER進行靜態分析的動機，主要基于兩個方面超過動態方法的優勢：(1) 能夠處理隱式數據流；(2) 目標是添加最小的運行時開銷。檢測隱式流的能力是靜態分析系統，包括PRIVANALYZER的一大優勢。不像動態方法，PRIVANALYZER不能被設計來混淆執行流程的復雜控制流所擊敗。例如，數據主體可能指定策略ALLOW REDACT name (1 : )，要求對大部分姓名列進行編輯。分析師可能編寫以下程序：

if data.name == 'Alice':return 1
else:return 2

即使這個程序沒有直接返回data.name的值，它顯然違反了策略。這種違反是由于姓名列到返回值的隱式流造成的。返回值為1允許分析師確定數據主體的名字是Alice。這種類型的隱式流對于動態分析來說是一個重大挑戰，因為動態分析只執行每個條件的一個分支，并且不能對未采取的分支做出結論。動態分析必須對在條件中使用敏感值施加重大限制，或者允許由于隱式流導致的不準確性。

另一方面，像PRIVANALYZER這樣的靜態分析器可以進行最壞情況分析，檢查兩個分支。PRIVANALYZER的分析使用抽象解釋器執行兩個分支，并返回兩個分支的最壞情況結果。對于迭代次數沒有上限的循環，分析結果代表了最壞情況的結果，無論運行時執行了多少次迭代。這種能力以可能缺乏精確性為代價——分析可能會拒絕實際上是安全運行的程序。然而，我們的評估表明，PRIVANALYZER分析對于執行數據分析的程序而言足夠精確。像PRIVANALYZER這樣的靜態分析工具不要求策略規范意識到隱式流，因為它在其結果中結合了兩種類型的流。

3.4 通過示例了解PRIVANALYZER

1. 示例：一個用于數據預處理和執行KMeans聚類分析的程序

df = pd.read_csv('german_credit_data.csv')# 定義數值型變量的列表。
numerical = ['Credit', 'Age', 'Duration']
# 定義類別型變量的列表。
categorical = ['Sex', 'Job', 'Housing', 'Saving accounts', 'Checking account', 'Purpose']
# 定義未使用變量的列表。
unused = ['Unnamed: 0']# 從數據框中刪除未使用的列。
df = df.drop(columns=unused)
# 過濾數據框，只保留年齡大于25歲的記錄。
df = df[df['Age'] > 25]# 對于每個類別型變量，填充缺失值為該列的眾數。
for cat in categorical:df[cat] = df[cat].fillna(df[cat].mode().values[0])# 對數值型變量進行對數轉換以正態化其分布。
df_cluster_log = np.log(df[['Age', 'Credit', 'Duration']])
# 初始化StandardScaler實例。
scaler = StandardScaler()
# 對經過對數轉換的數據進行標準化處理。
cluster_scaled = scaler.fit_transform(df_cluster_log)
# 初始化一個空列表，用于存儲不同k值下的總平方距離。
Sum_of_squared_distances = []# 定義一個范圍，從1到15，用于KMeans聚類的不同k值。
K = range(1, 15)
# 對于每個k值，進行KMeans聚類，并計算總平方距離。
for k in K:km = KMeans(n_clusters=k)km = km.fit(cluster_scaled)Sum_of_squared_distances.append(km.inertia_)

“抽象數據框架”（Abstract Data Frameworks, ADFs）

“抽象數據框架”（Abstract Data Frameworks, ADFs），是假想的或概念性的框架，用于在數據處理和分析中表示和跟蹤數據隱私策略。每個ADF代表一組與數據相關的隱私策略和結構（schema），可以用于確保數據處理活動符合特定的隱私要求。下面是對每個ADF表達內容的解釋：

1. ADF(SCHEMA = {age, credit, duration}, FILTER(age)=[18,inf], PRIVACY DeId):

   • 這個ADF定義了一個數據架構，包括三個字段：年齡（age）、信用（credit）和期限（duration）。同時，它指定了一個過濾策略，要求只包含年齡在18歲及以上的記錄（FILTER(age)=[18,inf]）。此外，它還應用了一個隱私策略（PRIVACY DeId），可能意味著對數據進行去標識化處理以保護個人隱私。

2. ADF(SCHEMA = {age, credit, duration}, PRIVACY DeId):

   • 這個ADF同樣定義了包含三個字段的數據架構，但沒有明確的年齡過濾策略（與前兩個不同）。它仍然應用了去標識化的隱私策略（PRIVACY DeId），用于保護隱私。

3. ADF(PRIVACY DeId):

   • 這個ADF不指定具體的數據架構，僅僅強調隱私策略，即數據需要經過去標識化處理（DeId）。這可能意味著它適用于任何數據集，只要數據被適當地去標識化。

4. ADF():

   • 這表示一個空的ADF，沒有指定數據架構或隱私策略。這可能表示數據處理的某個階段不涉及特定的隱私限制，或者所有先前的隱私策略已經得到滿足和處理。

3. ADF工作的原理以及作用

1. 初始狀態（ADF(SCHEMA = {age, credit, duration}, FILTER(age)=[18,inf], PRIVACY DeId)）:

   • 在數據處理的初始階段，我們有一個數據集的架構，包含年齡（age）、信用（credit）和期限（duration）。對應的隱私策略要求（1）過濾掉18歲以下的個體（FILTER(age)=[18,inf]），以及（2）對數據進行去標識化處理（PRIVACY DeId）。這個ADF代表數據處理開始時的隱私要求和數據結構。

2. 數據預處理（去除未使用的列和過濾年齡）:

   • 當代碼刪除未使用的列和過濾掉25歲以下的個體時（對應圖中的操作2和3），這些操作對隱私策略沒有直接影響，但是幫助進一步滿足年齡過濾的要求。盡管圖中沒有明確改變ADF，但實際上這可以視為在進一步滿足和細化初始ADF中的FILTER條件。

3. 填充缺失值（對于每個類別型變量）:

   • 圖中的操作4涉及填充缺失值，這是常見的數據預處理步驟，目的是讓數據更完整，準備進行更深入的分析。這個步驟不直接影響隱私策略，因此在ADF的上下文中不會引起變化。

4. 特征變換和標準化（對數變換和標準化）:

   • 圖中的操作5和6展示了對特定數值型變量進行的對數變換和標準化。這些操作可能改變數據的原始含義和范圍，與隱私策略相關，因為它們可能影響數據的識別風險。在這一步驟，我們可能需要重新評估數據的隱私策略，確保去標識化的要求仍被滿足。然而，具體的ADF變化在圖片中沒有直接展示，但原則上，這應該考慮到如何維持或調整PRIVACY DeId策略。

5. KMeans聚類:

   • 圖中的操作7和8涉及使用KMeans算法對處理后的數據進行聚類。這一步是數據分析過程的一部分，可能不直接影響隱私策略，除非聚類結果需要公開。在聚類分析后，如果分析結果需要共享，我們需要確保這些結果遵循隱私DeId策略，即不泄露任何個人信息。

在整個過程中，每個ADF的變化和更新反映了在數據處理和分析的每個階段對隱私策略的遵守情況。通過使用ADF，數據科學家可以系統地追蹤和確保他們的數據處理流程遵循所有相關的隱私要求，從而保護個人數據免受濫用。

3.5 挑戰性語言特性

我們現在討論PRIVANALYZER對幾種挑戰性語言特性采取的方法。

條件判斷。依賴抽象值的條件判斷要求抽象解釋器運行兩個分支并計算兩個結果的上界。由于Python不允許重定義if語句，我們在PRIVGUARD中添加了一個預處理步驟，這一步驟通過運行兩個分支來轉換條件判斷。

循環。循環傳統上是抽象解釋器處理起來最具挑戰性的結構。幸運的是，用于數據分析的Python程序中的循環通常屬于受限類別，就像圖6中的示例那樣。這個示例中的兩個循環都是在常數值上進行的——因此我們的抽象解釋器可以簡單地按照常數所要求的次數運行每個循環體。

在抽象值上的循環更具挑戰性，簡單的方法可能永遠不會終止。為了解決這個問題，我們為PRIVANALYZER中使用的每個抽象域定義了一個擴展操作符。擴展操作符強制循環到達一個固定點；在我們的示例中，擴展對應于假設循環體將在整個數據框上執行。

別名。抽象解釋面臨的另一個挑戰來自別名問題，其中兩個變量指向同一個值。有時，分析無法確定變量引用哪個抽象值。在這種情況下，也無法確定對變量的副作用的結果。

我們利用現有Python解釋器的方法有助于解決這個挑戰：在PRIVANALYZER中，所有變量引用都是具體評估的。在大多數情況下，引用指向具體對象，所以分析與具體執行完全相符。然而，在少數情況下，這種方法導致分析精度降低。例如，如果一個變量在條件的兩個分支中都被重新賦值，PRIVANALYZER必須假設最壞情況的抽象值（即具有最嚴格策略的值）在兩種情況下都被分配給變量。這種方法在我們的設置中效果很好，其中條件判斷和別名都相對罕見。

3.6 屬性執行

我們現在描述我們合規分析的一些屬性特定細節。SCHEMA（模式），FILTER（過濾器）和REDACT（刪除）屬性可以被正式定義，并且可以通過PRIVANALYZER進行合規性檢查。在我們的實現中，相關的函數摘要會在庫的具體實現滿足相應要求的情況下，從隱私政策中移除該屬性。因此，我們的摘要實現了這些函數的抽象解釋。請注意，PRIVANALYZER假設沒有摘要的函數不滿足任何政策要求。因此，PRIVANALYZER是不完整的：盡管滿足相關政策，但由于缺乏足夠的函數摘要，一些程序可能會被拒絕。

隱私。隱私屬性也由PRIVANALYZER檢查。分析程序可以通過調用刪除識別信息的函數（例如，聚合記錄或訓練機器學習模型）來滿足去標識化要求。程序可以通過調用提供這些屬性的特定函數來滿足k-匿名，多樣性，t-相似性或差分隱私要求。我們的函數摘要包括當前文獻中的代表性實現：IBM差分隱私庫，K-匿名庫和Google的Tensorflow隱私庫。

在執行差分隱私屬性時存在兩個微妙之處。首先，滿足差分隱私的程序還需要跟蹤隱私預算。默認情況下，PRIVGUARD為每個提交數據源跟蹤單個全局累積隱私成本（ε和δ的值），并在隱私成本超過預算金額后拒絕新的分析程序。PRIVANALYZER報告單個分析程序的隱私成本，使得PRIVGUARD能夠更新全局隱私成本。在具有許多分析員執行不同分析的環境中，單個全局隱私預算可能會迅速耗盡。解決此問題的一種方法是生成差分隱私合成數據，這些數據可以在以后的分析中使用而無需進一步的隱私成本。高維矩陣機制（HDMM）是一個用于此目的的算法示例，美國人口調查局用于發布差分隱私數據。在PRIVGUARD中，可以在像HDMM這樣的算法輸出上執行任意多的附加分析，而不會消耗隱私預算。另一個解決方案是在記錄級別進行細粒度的預算控制（如ProPer）或在靜態定義的“區域”級別進行（如UniTraX）。前者更精確，但需要在隱私預算耗盡時靜默丟棄記錄，從而導致偏倚的結果。這兩種方法都允許在不斷增長的數據庫中對新數據進行持續分析（例如，每天僅對當天獲得的新數據運行特定的查詢工作負載）。其次，為了計算隱私預算，PRIVGUARD 初始化一個變量來跟蹤差分隱私函數之前的預處理步驟的敏感性。預處理函數摘要應該操縱該變量以指定它們對敏感性的影響。如果在差分隱私函數之前的任何函數中缺少此類規范，PRIVGUARD將拋出警告并將識別差分隱私要求為未滿足。

角色：角色屬性由身份驗證技術強制執行，例如密碼、兩因素身份驗證，甚至生物識別身份驗證。此外，角色屬性還記錄在下一段描述的可審計系統日志中，分析員和數據管理員將對虛假身份負責。

目的：目的屬性本質上是非正式的。因此，我們采取一種基于問責制的方法來檢查目的的合規性。分析員在提交分析程序時可以指定其目的，并可能無意或惡意指定無效目的。這些目的將由PRIVANALYZER用于滿足目的要求。PRIVGUARD生成一個審計日志，記錄分析員、分析程序和聲明的目的。因此，系統中發生的所有分析都可以在事后進行驗證，并且分析員可以因使用無效目的而在法律上承擔責任。