NCorr-FP基于邻域的数据库指纹水印方案分析
字数 3620 2025-08-30 06:50:27

NCorr-FP基于邻域的数据库指纹水印方案分析

1. 引言

NCorr-FP是一种基于邻域相关性的数据库指纹水印方案，旨在保护结构化数据集的所有权。该系统通过在数据中嵌入独特的、特定于接收者的标记（指纹），使得未来可以追溯到数据泄露的来源。

2. 核心概念

2.1 邻域相关性

邻域相关性是指在一条记录或数据点周围选取"相似邻居"，观察这些邻居里各属性之间的统计依赖关系。这种局部层面的依赖关系称为邻域相关性。

概念解析表：

概念 直观含义 常见做法 关联度量
邻域 (Neighbourhood) 选出与目标记录在特征空间距离最近的k个记录，或落在半径γ内的记录集合 k-NN、ε-ball、基于相关属性集C的加权距离等 欧氏/曼哈顿/Cosine距离，或混合型记录的范数
相关性 (Correlation) 衡量两个(或多维)随机变量一起变化的强弱 皮尔逊r、斯皮尔曼ρ、互信息、卡方相关系数等 邻域相关性=局部相似样本几何中的属性相关性

2.2 攻击模型

  1. 串谋攻击：多个授权用户串通合作，将他们各自拥有的不同版本的数据合并分析，试图发现嵌入其中的指纹/水印位置，并生成一份"干净"的新副本以逃避追责。
  2. 自适应对手：可以根据系统行为"逐步试探→调整策略"的攻击者，虽然可能不知道算法内部细节，但能通过试验和反馈不断学习。
  3. 白盒对手：完全了解系统内部工作机制与参数细节的攻击者。

3. 系统设计与要求

3.1 系统目标

  1. 指纹能够被可靠提取，并能准确归属给对应接收者
  2. 嵌入后数据仍然可用，且在统计特性上与原始数据保持相似
  3. 指纹应能抵抗部分数据损毁或故意修改

3.2 系统流程

指纹系统主要包含两个过程：指纹嵌入和指纹检测，具体分为四个子过程：

  1. 指纹生成：使用密钥K和收件人ID生成收件人特定的序列F
  2. 嵌入算法：通过内容感知、密度和相关性驱动的方案将F注入数据集
  3. 检测算法：从(可能修改的)副本中提取候选指纹，而无需访问原始文件
  4. 指纹解码和指控：将提取到的指纹和已知指纹进行匹配，以识别来源或找到负责的合谋者

3.3 Tardos指纹码

系统整合了Tardos codes以实现抗串谋溯源：

Tardos指纹码长度计算公式：

L = 100c² log(n/ϵ)

其中：

  • L：指纹码长度(每个用户所持有的码字位数)
  • n：系统中合法用户的总数
  • c：系统期望能抵抗的最大串谋人数
  • ϵ：系统可接受的错误指控概率(false accusation rate)
  • log(n/ϵ)：为保证低误报的对数项

指控机制(Accusation Mechanism)：

  1. 对每个用户s计算"指控得分"Tₛ
  2. 计算全体用户得分的均值μ和标准差σ
  3. 设定指控阈值Zₓ = μ + xσ (x通常取3或4)
  4. 如果用户s的得分Tₛ > Zₓ，则判定为泄漏者

Tscore计算：
对于每个用户s，他的指纹是Fₛ，从被泄露的数据中提取出嵌入码F̃，然后计算该用户的指控得分：

Tₛ = ∑ᵢ w(F̃ᵢ, Fₛᵢ)

其中w是基于概率设计的得分权重函数。

4. NCORR-FP算法详解

4.1 指纹嵌入算法

  1. 使用伪随机序列生成器(种子为持有者的密钥以及记录的主键)
  2. 通过嵌入比率为γ的伪随机输出，对记录r是否被选中标记做二元决策
  3. 使用KNN策略选择邻域
  4. 将属性空间划分为相关属性组C = {C₁, C₂, ..., Cₖ}，每个Cᵢ包含相互且传递相关联的属性

Algorithm1关键点：

  • 对连续属性使用高斯核密度估计方法划分高低密度区域
  • 对分类属性通过目标值中的价值频率来划分高低密度区域
    • 设V为分类属性中唯一目标值的有限集合，按出现频率升序排列
    • 定义分位数q用于区分低密度和高密度组别

4.2 指纹检测算法

  1. 判断目标值是位于高密度区还是低密度区，确定标记位
  2. 根据标记位和掩码位计算指纹位
  3. 使用提取的位置更新投票系统计数，根据多数表决决定最后的指纹序列
  4. 当出现未投票或投票平局时保留指纹模板中的未决定值

5. 评估方法

5.1 数据集

使用UCI Adult数据集，具备以下特性：

  1. 包含数值型和类别型特征
  2. 存在特征之间的相关性
  3. 含有缺失值

5.2 评估指标

有效性指标：

  1. VER(Vote Error Rate)：投票错误率，所有指纹位的错误投票数与总投票数之间的比率
  2. DC(Detection Confidence)：检测可信度，检测到的指纹和正确的指纹位之间的匹配率
  3. FAC(False Accusation Confidence)：错误指控可信度，检测到的指纹与其他接收者的指纹之间的匹配度

保真度指标：

  1. 数据集统计：测量整个数据集的变化
    • 数据准确率公式：DA = 1 - (|D̃ - D|)/|D|
  2. 单变量统计：测量属性统计
    • 使用Hellinger距离和KL散度
  3. 多变量统计：测量数据属性之间的相关性
    • Pearson's correlation coefficient
    • Cramér's V
    • Eta-squared (η²)

实用性评估：
采用预测建模(机器学习)的方法，评估嵌入指纹后的数据是否还能被有效用于下游任务，使用四种分类模型：

  1. Logistic Regression
  2. Multi-layer Perceptron (MLP)
  3. Random Forest
  4. XGBoost

5.3 鲁棒性评估

单用户攻击：

  1. 水平/垂直子集攻击
  2. 翻转攻击：
    • 随机值翻转
    • 基于影响力记录子集的翻转
    • 使用近似或准确参数的定向翻转

串谋攻击：

  1. Averaging attack(均值攻击)
  2. Substitution attack(替代攻击)
  3. Substitution + Flip(替换并翻转)

串谋攻击抵抗评估指标：

  1. Precision(精确率)：正确识别出的串谋者人数 ÷ 总共被指控的人数
  2. False Accusation Rate(错误指控率)：被误指控的无辜者人数 ÷ 总指控人数
  3. Recall(召回率)：被指控的串谋者人数 ÷ 实际所有串谋者人数

6. 评估结果与分析

6.1 有效性

  • VER与嵌入标记数成正比增加，最差情况下约为0.013
  • 随着邻域大小的增大，VER增加
  • 指纹长度越长，性能更优
  • 嵌入比率越高，检测能力更稳定

6.2 保真度

  • NCorr-FP方法比基线方法更优秀
  • 二元属性与其他属性之间的相关性更容易受到破坏
  • 在最糟情况下，相关性的相对变化不超过10%

6.3 实用性

  • XGBoost始终能获得最高的准确率，性能下降幅度最大为0.016
  • Logistic Regression的下降幅度与XGBoost相同，但绝对准确率得分明显更低
  • RandomForest对指纹识别的鲁棒性最强，分类准确率最多下降0.008
  • MLP表现出强大的弹性，准确率下降约1%

6.4 鲁棒性

单用户攻击：

  • 水平和垂直子集会根据指纹参数的选择破坏指纹提取的置信度
  • 邻域大小k影响不大，但嵌入比例1/γ影响显著
  • 损坏指纹比嵌入指纹带来的保真度损耗更高

翻转攻击：

  • 随机翻转比集群翻转更有效破坏指纹
  • 攻击者为"消除指纹"付出的代价远大于嵌入指纹本身造成的扰动

串谋攻击：

  • 指纹长度的提高是检测更大规模串通的关键要求
  • 对于少量串谋者(c ≤ 3)，使用512-bit或1024-bit Tardos code可实现完美检测
  • 对于中等串谋人数(c = 5)，需要≥1024-bit指纹以保持高recall
  • 对于大规模串谋(c = 10)，即使使用1024-bit，系统依然识别困难

7. 参数设计指南

  1. 冗余因子ω：ω ≥ 16是确保100%检测置信度(DC)的经验阈值
  2. 指纹长度L：
    • 减少L可以降低冗余度ω，提高DC和对单用户攻击的鲁棒性
    • 增加L能减少FAC，同时增强共谋的抗性
  3. 嵌入比率1/γ：
    • 增加1/γ对保真度和效用有负面影响，但这种影响不显著
    • 建议选择接近最大值1.0的较高范围内的1/γ
  4. 邻域大小k：
    • 较小的k值通过聚焦高度相似的记录，提高效率和准确性
    • 较大的k值通过稳定密度估计，增强对数据变化的鲁棒性
    • 建议将k设置为数据集大小的≤1%

多目标权衡：

  • 提升检测效果 → 增加冗余因子ω(减L或增嵌入比)
  • 提升保真与实用性 → 选择更稀疏嵌入(增1/γ)与更小扰动(减L)
  • 提升鲁棒性 → 增加L、k，维持ω ≥ 16

8. 结论

NCorr-FP的实证结果显示：

  1. 指纹几乎无法被察觉，Hellinger距离低于0.023，KL散度低于6×10⁻³
  2. 对广泛数据修改具有极强的鲁棒性
  3. 与以往研究相比，指纹的不可见性得到了显著提升

该系统通过基于邻域的相关性保持策略，在保证数据实用性的同时，实现了强大的指纹嵌入和检测能力，能够有效抵抗各种攻击，特别是串谋攻击。

NCorr-FP基于邻域的数据库指纹水印方案分析 1. 引言 NCorr-FP是一种基于邻域相关性的数据库指纹水印方案，旨在保护结构化数据集的所有权。该系统通过在数据中嵌入独特的、特定于接收者的标记（指纹），使得未来可以追溯到数据泄露的来源。 2. 核心概念 2.1 邻域相关性 邻域相关性是指在一条记录或数据点周围选取"相似邻居"，观察这些邻居里各属性之间的统计依赖关系。这种局部层面的依赖关系称为邻域相关性。 概念解析表： | 概念 | 直观含义 | 常见做法 | 关联度量 | |------|----------|----------|----------| | 邻域 (Neighbourhood) | 选出与目标记录在特征空间距离最近的k个记录，或落在半径γ内的记录集合 | k-NN、ε-ball、基于相关属性集C的加权距离等 | 欧氏/曼哈顿/Cosine距离，或混合型记录的范数 | | 相关性 (Correlation) | 衡量两个(或多维)随机变量一起变化的强弱 | 皮尔逊r、斯皮尔曼ρ、互信息、卡方相关系数等 | 邻域相关性=局部相似样本几何中的属性相关性 | 2.2 攻击模型 串谋攻击 ：多个授权用户串通合作，将他们各自拥有的不同版本的数据合并分析，试图发现嵌入其中的指纹/水印位置，并生成一份"干净"的新副本以逃避追责。 自适应对手 ：可以根据系统行为"逐步试探→调整策略"的攻击者，虽然可能不知道算法内部细节，但能通过试验和反馈不断学习。 白盒对手 ：完全了解系统内部工作机制与参数细节的攻击者。 3. 系统设计与要求 3.1 系统目标 指纹能够被可靠提取，并能准确归属给对应接收者 嵌入后数据仍然可用，且在统计特性上与原始数据保持相似 指纹应能抵抗部分数据损毁或故意修改 3.2 系统流程 指纹系统主要包含两个过程：指纹嵌入和指纹检测，具体分为四个子过程： 指纹生成 ：使用密钥K和收件人ID生成收件人特定的序列F 嵌入算法 ：通过内容感知、密度和相关性驱动的方案将F注入数据集 检测算法 ：从(可能修改的)副本中提取候选指纹，而无需访问原始文件 指纹解码和指控 ：将提取到的指纹和已知指纹进行匹配，以识别来源或找到负责的合谋者 3.3 Tardos指纹码 系统整合了Tardos codes以实现抗串谋溯源： Tardos指纹码长度计算公式 ： 其中： L：指纹码长度(每个用户所持有的码字位数) n：系统中合法用户的总数 c：系统期望能抵抗的最大串谋人数 ϵ：系统可接受的错误指控概率(false accusation rate) log(n/ϵ)：为保证低误报的对数项 指控机制(Accusation Mechanism) ： 对每个用户s计算"指控得分"Tₛ 计算全体用户得分的均值μ和标准差σ 设定指控阈值Zₓ = μ + xσ (x通常取3或4) 如果用户s的得分Tₛ > Zₓ，则判定为泄漏者 Tscore计算 ： 对于每个用户s，他的指纹是Fₛ，从被泄露的数据中提取出嵌入码F̃，然后计算该用户的指控得分： 其中w是基于概率设计的得分权重函数。 4. NCORR-FP算法详解 4.1 指纹嵌入算法 使用伪随机序列生成器(种子为持有者的密钥以及记录的主键) 通过嵌入比率为γ的伪随机输出，对记录r是否被选中标记做二元决策 使用KNN策略选择邻域 将属性空间划分为相关属性组C = {C₁, C₂, ..., Cₖ}，每个Cᵢ包含相互且传递相关联的属性 Algorithm1关键点 ： 对连续属性使用高斯核密度估计方法划分高低密度区域 对分类属性通过目标值中的价值频率来划分高低密度区域 设V为分类属性中唯一目标值的有限集合，按出现频率升序排列 定义分位数q用于区分低密度和高密度组别 4.2 指纹检测算法 判断目标值是位于高密度区还是低密度区，确定标记位 根据标记位和掩码位计算指纹位 使用提取的位置更新投票系统计数，根据多数表决决定最后的指纹序列 当出现未投票或投票平局时保留指纹模板中的未决定值 5. 评估方法 5.1 数据集 使用UCI Adult数据集，具备以下特性： 包含数值型和类别型特征 存在特征之间的相关性 含有缺失值 5.2 评估指标 有效性指标 ： VER(Vote Error Rate)：投票错误率，所有指纹位的错误投票数与总投票数之间的比率 DC(Detection Confidence)：检测可信度，检测到的指纹和正确的指纹位之间的匹配率 FAC(False Accusation Confidence)：错误指控可信度，检测到的指纹与其他接收者的指纹之间的匹配度 保真度指标 ： 数据集统计：测量整个数据集的变化 数据准确率公式：DA = 1 - (|D̃ - D|)/|D| 单变量统计：测量属性统计 使用Hellinger距离和KL散度 多变量统计：测量数据属性之间的相关性 Pearson's correlation coefficient Cramér's V Eta-squared (η²) 实用性评估 ： 采用预测建模(机器学习)的方法，评估嵌入指纹后的数据是否还能被有效用于下游任务，使用四种分类模型： Logistic Regression Multi-layer Perceptron (MLP) Random Forest XGBoost 5.3 鲁棒性评估 单用户攻击 ： 水平/垂直子集攻击 翻转攻击： 随机值翻转 基于影响力记录子集的翻转 使用近似或准确参数的定向翻转 串谋攻击 ： Averaging attack(均值攻击) Substitution attack(替代攻击) Substitution + Flip(替换并翻转) 串谋攻击抵抗评估指标 ： Precision(精确率)：正确识别出的串谋者人数 ÷ 总共被指控的人数 False Accusation Rate(错误指控率)：被误指控的无辜者人数 ÷ 总指控人数 Recall(召回率)：被指控的串谋者人数 ÷ 实际所有串谋者人数 6. 评估结果与分析 6.1 有效性 VER与嵌入标记数成正比增加，最差情况下约为0.013 随着邻域大小的增大，VER增加 指纹长度越长，性能更优 嵌入比率越高，检测能力更稳定 6.2 保真度 NCorr-FP方法比基线方法更优秀 二元属性与其他属性之间的相关性更容易受到破坏 在最糟情况下，相关性的相对变化不超过10% 6.3 实用性 XGBoost始终能获得最高的准确率，性能下降幅度最大为0.016 Logistic Regression的下降幅度与XGBoost相同，但绝对准确率得分明显更低 RandomForest对指纹识别的鲁棒性最强，分类准确率最多下降0.008 MLP表现出强大的弹性，准确率下降约1% 6.4 鲁棒性 单用户攻击 ： 水平和垂直子集会根据指纹参数的选择破坏指纹提取的置信度 邻域大小k影响不大，但嵌入比例1/γ影响显著 损坏指纹比嵌入指纹带来的保真度损耗更高 翻转攻击 ： 随机翻转比集群翻转更有效破坏指纹 攻击者为"消除指纹"付出的代价远大于嵌入指纹本身造成的扰动 串谋攻击 ： 指纹长度的提高是检测更大规模串通的关键要求 对于少量串谋者(c ≤ 3)，使用512-bit或1024-bit Tardos code可实现完美检测 对于中等串谋人数(c = 5)，需要≥1024-bit指纹以保持高recall 对于大规模串谋(c = 10)，即使使用1024-bit，系统依然识别困难 7. 参数设计指南 冗余因子ω ：ω ≥ 16是确保100%检测置信度(DC)的经验阈值 指纹长度L ： 减少L可以降低冗余度ω，提高DC和对单用户攻击的鲁棒性 增加L能减少FAC，同时增强共谋的抗性 嵌入比率1/γ ： 增加1/γ对保真度和效用有负面影响，但这种影响不显著 建议选择接近最大值1.0的较高范围内的1/γ 邻域大小k ： 较小的k值通过聚焦高度相似的记录，提高效率和准确性 较大的k值通过稳定密度估计，增强对数据变化的鲁棒性 建议将k设置为数据集大小的≤1% 多目标权衡 ： 提升检测效果 → 增加冗余因子ω(减L或增嵌入比) 提升保真与实用性 → 选择更稀疏嵌入(增1/γ)与更小扰动(减L) 提升鲁棒性 → 增加L、k，维持ω ≥ 16 8. 结论 NCorr-FP的实证结果显示： 指纹几乎无法被察觉，Hellinger距离低于0.023，KL散度低于6×10⁻³ 对广泛数据修改具有极强的鲁棒性 与以往研究相比，指纹的不可见性得到了显著提升 该系统通过基于邻域的相关性保持策略，在保证数据实用性的同时，实现了强大的指纹嵌入和检测能力，能够有效抵抗各种攻击，特别是串谋攻击。