“静态信息流规则与动态信息流监测把双运行目标转成可执行准入,但其允许发散模型只保证两次均正常接受时的低值一致。安全多重执行则从相同低输入投影构造相同低副本;拒绝、终止、时间是否可观察,以及相对…”
形式陈述
两份执行看到不同输入
考虑确定性的整数IMP,全部变量初始有值,固定L/H输入标签,没有可变堆、异常、交互I/O或并发。最终只公开指定低结果out;真实秘密副本的状态和结果均留在高侧。允许while不终止,所有表达式运算总有定义。
给定固定且公开的默认整数d,定义低输入投影
为同一程序c建立两个私有状态:低副本从
这是安全多重执行的无交互、两级批处理特例。原始算法对每个安全级别分别执行,在过高输入处使用默认值,只保留与副本等级对应的输出,还协调有副作用输入的读取;本页没有这些交互通道。[1, §§II–III]
安全与透明性是两条命题
若
透明性则问:低副本是否保留原程序本来要给的低结果?一个足够条件是c满足终止不敏感NI,且本次真实运行与默认投影运行都正常终止。它们初始低等价,NI便使两份结果相同。若希望从“真实运行终止”自动推出“投影运行终止”,还需终止敏感的相应条件,不能只引用TINI。[1, §IV-C的透明性定理采用终止敏感前提]
直觉
公开副本从未拿到真实秘密
动态监测看到秘密后,设法阻止它经数据或控制流进入低结果。多重执行换了一个位置处理问题:负责公开答案的那份程序一开始只拿到固定替代值。它可以任意分支和计算,但没有真实秘密可供区别。
代价是答案可能改变。原程序若确实想把秘密写到公开结果,低副本会写出默认值相关的答案。安全性不表示保留所有不安全程序的行为;有用的透明性条件必须另写。
例子与边界
同一个秘密分支,公开值来自哪一份
执行if h then out:=1 else out:=0,默认d=0。真实h=0时,高副本输出0;真实h=1时,高副本输出1。低副本在两种真实输入下都看到h=0,所以两次公开值均为0。若选择高副本的“更真实答案”补回公开接口,就立即恢复原泄漏。
对于if h then out:=0 else out:=0,原程序的低结果已经独立于秘密。两份都正常终止,低副本输出0,保持了原结果。它无需像语法类型系统那样因为高条件中的低写入而拒绝这段代码。
不等待高副本是一项执行要求
while 0 < h do h := h - 1
out := 0
默认d=0。每次守卫测试、赋值或skip算一步,seq容器不另计步。真实h分别为0、1、3时,高副本分别需要2、4、8步;低副本始终2步。两份总工作分别4、6、10步,但低侧都可以在低副本2步完成时收到0。
若实现先跑高副本,再启动或发布低副本,低结果到达前的语义工作分别变成4、6、10步,秘密进入等待时间。若低结果已发布,但又把“全部副本完成”通知公开,同样新添了高侧观察。保护的是规定的低接口,不能顺便公开总工作日志。
默认值让原本结束的运行不结束
把循环改成while h==0 do skip; out:=0。真实h=1时两步完成,默认h=0时循环永远不改状态,故数学语义中发散。这段程序满足TINI:所有正常结束的运行都输出0;然而SME低接口无法为本次真实输入交出结果。
预算20的下载检查会给真实运行OK、低运行UNKNOWN。UNKNOWN只是“20步内未完成”,上述发散结论要另用不变的真守卫证明。此例正好说明为什么透明性必须写投影终止,不能以TINI自动代替。
推论与应用
一步相同推广到整条低轨迹
低投影相等以后,归纳对象是一份完整的低副本状态,包括待执行命令、变量值和解释栈。确定性保证相同状态选择相同下一条规则,算出相同新状态。有限前缀因此逐步相同;若某侧第T步结束,另一侧也在同一步结束。若永远不结束,另一侧也持续相同执行。
证明没有读取高副本状态,也没有让它决定低副本何时前进。只要两份共享可写计数器、资源失败或不受约束的等待,就需重新验证这个前提。本模型的相同步数不是硬件常数时间认证,缓存、调度与机器故障都未建模。
计算实际工作,不猜倍数
若两份都结束,令其语义命令步数为
语义步数便于比较算法轨迹;实际解释器还处理可能反复进入的seq容器,成本必须计K。
结构迁移
从while h==0 do skip; out:=0开始,把默认值改为1。现在低副本两步结束,即使真实h=0的高副本不结束也能公开0。低接口仍独立于真实秘密,但相对于原程序的终止行为再次改变。请分别填写真实执行、默认执行和低接口三列,不能用“程序终止”一个词同时指代它们。
再把对外接口改成“等待两副本都完成才返回”。真实h=0和h=1便有不同返回行为。该迁移改变的是发布依赖,不是投影公式;只有同时检查输入屏蔽和输出发布路径,原来的证明才能覆盖实现。完整比较见终点任务。
参考资料
[1] Dominique Devriese and Frank Piessens, “Noninterference through Secure Multi-Execution”, IEEE Symposium on Security and Privacy,2010,pp.109–124,DOI:10.1109/SP.2010.15。§III、Figures 6–7给出输入默认化、按级输出与执行选择;§IV-B Theorem 1采用低级优先选择证明强非干扰;§IV-C Theorem 2给出终止敏感非干扰程序的终止运行透明性。本文将其限制为无交互的两级初态投影,不声称实现了论文全部输入/输出协调。