论文阅读

摘要

  • 引入了抽象软件水印 的概念
  • 基本思想：水印隐藏在程序代码里面，只有通过对代码具体语义的抽象解释才能把水印提取出来
  • 即使只有一小部分程序，也能恢复水印

抽象水印

  • 是静态水印：提取签名不需要执行程序（不需要特殊输入）
  • 是动态水印：隐写签名隐藏在程序的具体语义中（可能是非标准的语义），但是执行隐写程序（或仅执行插入主体程序中的隐写标记）不会显示隐写签名
  • 与现有静态/动态方法的不同点：隐写签名提取是通过对隐写程序的静态分析，即通过对其具体语义的抽象解释（由此获得这种水印方法的“抽象”限定符）

Method

1. Principals

选择某个抽象 αn\alpha_n 以及抽象提取器 εˉ(Q)\bar {\varepsilon}(Q)

用隐写签名 ss 给程序 PP 打水印，生成隐写程序 W[P](s)W[P](s) ，而水印 ss 由可以被抽象提取器 εˉ\bar \varepsilon 从它的抽象语义 $ \bar {R}_\alpha [wp]$ ,该语义完全由抽象 α\alpha 指定。通过保证 α\alpha 和 $\bar {\varepsilon}(Q) $ 机密，可以让(潜在攻击者)提取水印变得很困难。

2. 抽象软件隐写签名嵌入

2.1 签名

一个秘密的签名是一个任意大的自然数C, 实践中由于变量最大值的限制，C的取值总是存在一个上界。为了摆脱这种上界的限制，利用中国剩余定理 ，可以同构地嵌入 ℓ\ell 个密钥，使得：

c=∑i=1ℓ((∏j=1i−1nj)⋅ci⋅(∏j=i+1ℓnj))( mod ∏j=1ℓnj)c=\sum_{i=1}^{\ell}\left(\left(\prod_{j=1}^{i-1} n_j\right) \cdot c_i \cdot\left(\prod_{j=i+1}^{\ell} n_j\right)\right) \quad\left(\bmod \prod_{j=1}^{\ell} n_j\right)

故，密钥可以假设为一个元组 ⟨c1,…,cℓ⟩∈\left\langle c_1, \ldots, c_{\ell}\right\rangle \in [0,n1−1]×…×[0,nℓ−1]\left[0, n_1-1\right] \times \ldots \times\left[0, n_{\ell}-1\right]

隐写签名嵌入的原理是向程序添加一个隐写标记以隐藏常量 cic_i，知道 ℓ\ell 个隐写密钥 nℓn_\ell 后，可以接连运行 ℓ\ell 次静态分析来得到秘密签名 cc

2.2 隐写标记

分为三部分

  • 声明部分：引入一个辅助的隐写变量w, 隐藏密钥 cic_i 的值
  • 初始化阶段：给w赋值 w = P(1)
  • 迭代阶段：w = Q(w)

一旦初始化后，w 就成为常量，这一性质用于提取隐写签名cic_i

Q：Although it is constant in Z/niZ\mathbb{Z} / n_i \mathbb{Z} the value of W\mathrm{W} will appear to be stochastic随机的 in successive executions of the stegomark iteration part w=Q\mathrm{w}=Q (w).

2.3 隐写标记嵌入程序

嵌入的空间：Java 类中的方法 MM

  • 声明部分被放入方法 MM 的声明中
  • 初始化部分被嵌入到方法 MM 初始基本块的随机位置
  • 迭代部分被在之后被插入方法 MM的主体部分的随机位置（倾向于插入循环体）
2.4 混淆隐写标记

w = P(1)
w = Q(w)

P Q 都是多项式函数（以二阶多项式为例，如有需要也可使用更高阶的多项式），其中：

P(x)=(x+k1)x+k0P(x)=(x+k_1)x+k_0

k0=−(1+ci)+r1⋅nik1=ci+r2⋅ni\begin{aligned} &k_0=-\left(1+c_i\right)+r_1 \cdot n_i \\ &k_1=c_i+r_2 \cdot n_i \end{aligned}

r1r_1 、r2r_2 为随机整数，k1k_1 、k2k_2 的取法保证了在模nin_i 后(?) P(1)=ciP(1) = c_i

这一通过添加临时变量T完成上述计算

1
2
3
4
W = 1
T = W + k_1
T = W * T
W = T + k_0

Q(x)=(ax+b)x+cQ(x) = (ax+b)x+c

aa , bb 是不太大的非零随机数，cc的取值为：

c=ci−(b−ci+a∗ci2)c=c_i-(b-c_i+a*c_i^2)

来保证ci=Q(ci)c_i = Q(c_i)

同理可通过增加临时变量完成运算

3. 提取隐写标记

通过定义 αiα_i，使得$ \bar {R}_{αi} [P] $对 PP 的所有方法 MM 在 Z/niZZ/niZ 中执行恒定传播，静态分析将能够识别某个变量（即 W）在初始化后在 Z/niZZ/niZ 中具有常量值 cic_i（或者最终如果死变量已被重用），从而表明方法 M 已被水印。

*关于$ \bar {R}{α} [P] ：： \bar {R}{α} [P] 是“程序是“程序P$可到达状态的近似值”，获取它的方法看不懂

返回的结果是方法 P 的局部整数变量的常量值

静态分析
graph TB
a["从每个方法P获取具体语义"]-->b["抽象化:在对应于单个的抽象域中传播常数的连续（或同时或并行）静态分析"]
b-->c["获取抽象语义"]-->d["应用静态分析验证水印"]