修复不一致的XML写访问控制策略

### 修复不一致的XML写访问控制策略 #### 1. 策略一致性判定 判定策略一致性的问题属于PTIME复杂度。不过，一致性对策略设计和更新类型十分敏感。例如，对于DTD中生产规则为 $B^*$ 或 $B_1 + ... + B_n$ 形式的元素类型A，我们有意省略了更新类型 $(A, replace(B_i, B_i))$。 以会议管理系统为例，一篇论文元素包含决策和标题子元素。假设策略允许论文作者用另一个论文元素替换当前论文元素，但禁止更改决策子元素的值。这个策略是不一致的，因为通过用具有不同决策子元素的论文元素替换当前元素，我们能够执行被禁止的更新。实际上，$replace(paper, paper)$ 可以模拟应用于论文元素之下的任何其他更新类型。所以，如果策略禁止替换论文节点，那么允许对决策和标题进行任何其他操作就是不一致的。因此，我们认为策略中不应使用更新类型 $(A, replace(B_i, B_i))$，而应单独分配更具体的权限，例如允许替换标题或决策元素类型的文本值。 #### 2. 部分策略 部分策略可能比完整策略更小且更易于维护，但由于某些权限未明确指定，它们具有模糊性。访问控制机制必须允许或拒绝请求。一种解决方案（遵循最小特权原则）可能是拒绝访问未指定的操作。然而，不能保证由此产生的完整策略是一致的。实际上，一个部分策略（即使本身是一致的）是否有一致的完整扩展并不明显。 为了方便，我们用 $A_P$ 和 $F_P$ 表示策略 $P$ 的允许和禁止集合，即 $P = (A_P, F_P)$。我们引入信息序 $P \sqsubseteq Q$，定义为 $A_P \subseteq A_Q$ 且 $F_P \subseteq F_Q$，即 $Q$ 比 $P$ “定义更完整”，此时我们称 $Q$ 扩展了 $P$。如果部分策略 $P$ 有一致的完整扩展，则称其为准一致的。例如，图1的DTD上的一个部分策略，允许 $(B, insert(E))$、$(B, delete(E))$ 并拒绝 $(H, replace(str, str))$ 就不是准一致的，因为该策略的任何一致扩展都必须允许 $(H, replace(str, str))$。 我们还引入了完整策略上的特权序 $P \leq Q$，定义为 $A_P \subseteq A_Q$，即 $Q$ 允许 $P$ 中允许的每个操作。这个序有唯一的最大下界 $P \land Q$，定义为 $(A_P \cap A_Q, F_P \cup F_Q)$。每个准一致的策略都有一个最小特权的一致扩展 $P^\dagger$，即 $P^\dagger$ 是一致的，并且只要 $Q$ 是 $P$ 的一致扩展，就有 $P^\dagger \leq Q$。 下面是相关的引理和命题： - **引理1**：如果 $P_1$、$P_2$ 是 $P_0$ 的一致完整扩展，那么 $P_1 \land P_2$ 也是 $P_0$ 的一致扩展。 - **命题2**：每个准一致的策略 $P$ 都有唯一的 $\leq$-最小一致完整扩展 $P^\dagger$。 最后，我们展示如何找到最小特权的一致扩展，或者确定不存在这样的扩展（从而部分策略不是准一致的）。定义算子 $T : P(valid(D)) \to P(valid(D))$ 如下： \[ T(S) = S \cup \{(C, x) | B \leq_D C, Rg(A) = B^*, \{(A, insert(B)), (A, delete(B))\} \subseteq S\} \cup \{(C, x) | B_i \leq_D C, Rg(A) = B_1 + ... + B_n, (B_i, B_i) \in G^+_A(S)\} \cup \{(A, replace(B_i, B_k)) | Rg(A) = B_1 + ... + B_n, (B_i, B_k) \in G^+_A(S)\} \] 其中 $G^+_A(S)$ 是部分策略 $S$ 中 $A$ 的传递图。 - **引理2**：如果 $uat \in T(S)$，那么对于在 $t$ 上与 $uat$ 匹配的任何有效操作 $op_0$，存在 $S$ 在 $t$ 上允许的有效操作序列 $op$，使得 $[[op_0]](t) = [[op]](t)$。 - **定理2**：设 $P$ 是部分策略，以下条件等价：(1) $P$ 是准一致的；(2) $P$ 是一致的；(3) $T(A_P) \cap F_P = \varnothing$。 对于（准）一致的 $P$，其最小特权的一致扩展就是 $P^\dagger = (T(A_P), valid(D) \setminus T(A_P))$。因此，我们可以在PTIME内判定部分策略是否（准）一致，如果是则找到 $P^\dagger$。 #### 3. 修复策略 如果策略不一致，我们希望提出可能的最小修改方式来恢复一致性，即找到尽可能接近不一致策略的修复方案。 定义修复的方式有多种，我们可能想通过将某些操作的权限从允许改为禁止，反之亦然来进行修复；或者我们可能更倾向于某些类型的更改。此外，我们可以将修复的最小性衡量为最小的更改数量或集合包含意义下的最小更改集。 由于篇幅限制，我们专注于将UATs从允许转换为禁止并最小化更改数量的修复方式。我们认为这种修复是一个有用的特殊情况，因为修复后的策略保证比原始策略更具限制性。 我们定义策略 $P' = (A', F')$ 是定义在DTD $D$ 上的策略 $P = (A, F)$ 的修复，当且仅当： 1. $P'$ 是定义在 $D$ 上的策略； 2. $P'$ 是一致的； 3. $P' \leq P$。 如果 $F' = valid(D) \setminus A'$，则修复是完整的，否则是部分的。此外，如果不存在完整修复 $P'' = (A'', F'')$ 使得 $|A'| < |A''|$，则 $P' = (A', F')$ 是策略 $P(A, F)$ 的最小完整修复；如果 $F' = F$ 且不存在部分修复 $P'' = (A'', F)$ 使得 $|A'| < |A''|$，则 $P'$ 是最小部分修复。 给定策略 $P = (A, F)$ 和整数 $k$，完整修复（部分修复）问题在于确定是否存在策略 $P$ 的完整修复（部分修复）$P' = (A', F')$ 使得 $|A \setminus A'| < k$。这个问题可以通过从边删除传递有向图问题归约证明是NP难的。 - **定理3**：完整修复和部分修复问题是NP完全的。如果DTD没有 $A \to B_1 + \cdots + B_n$ 类型的生产规则，那么完整修复问题属于PTIME复杂度。 #### 4. 修复算法 我们讨论一种修复算法，用于找到完整或部分策略的最小修复。所有算法可在相关资料中找到。 该算法计算策略的最小修复依赖于插入/删除操作和替换操作的不一致性之间的独立性。实际上，对插入/删除操作的不一致性进行局部修复永远不会解决或产生替换操作的不一致性，反之亦然。我们将分别描述修复插入/删除不一致性的算法和修复替换不一致性的算法。 两种算法都使用标记的DTD图 $MGD = (G_D, \mu, \chi)$，其中 $\mu$ 是从 $V_D$ 中的节点到 $\{"+", "-"\}$ 的函数，$\chi$ 是从 $V_D$ 到 $\{\perp\}$ 的部分函数。在DTD $D$ 和策略 $P = (A, F)$ 的标记图中： 1. 图中的每个节点要么标记为 “+”（即该节点以下没有被禁止的操作），要么标记为 “-”（即该节点以下存在至少一种被禁止的更新访问类型）。 2. 如果对于DTD中的节点 $A$ 和 $B$，$(A, insert(B))$ 和 $(A, delete(B))$ 都在 $A$ 中，且 $\mu(A) = "-"$，则 $\chi(A) = "\perp"$。 标记图通过算法 $markGraph$ 获得，该算法以DTD图和策略 $P$ 为输入，从出度为0的节点开始遍历DTD图，并按上述方式标记节点和边。 下面是一个标记图的示例： |节点|标记| | ---- | ---- | | B | - 和 ⊥ | | E | - 和 ⊥ | | J | - 和 ⊥ | 以下是修复过程的mermaid流程图： ```mermaid graph LR A[开始] --> B[标记DTD图] B --> C{是否有插入/删除不一致} C -- 是 --> D[修复插入/删除不一致] C -- 否 --> E{是否有替换不一致} ```