"""第 26 章习题:随机抽查与按可疑度抽查的发现概率(为教学构造的数字)。 python3 tools/exercises/ch26_audit.py 设定(均为教学假设,不来自任何论文): - 一个编程智能体完成一个任务用 200 步,人工审计预算是 2%,即 4 步。 - 攻击 A 有 2 步:第 37 步读取密钥,第 150 步把它发送出去。 - 攻击 B 是攻击方知道审计按可疑度排序后的改法:读取密钥仍是 1 步, 发送拆成 10 个看起来普通的小步骤,一共 11 步。 - 按可疑度审计时,假设每个攻击步骤是否进入可疑度前 4 名相互独立,概率如下: 攻击 A:读取 0.05,发送 0.70;攻击 B:读取 0.05,每个小步骤 0.03。 - 安全性公式取 Kutasov 等(2025)的定义:安全性 = p_audit / (p_audit + p_attack), p_audit 是含攻击的任务被审计到的概率,p_attack 是含攻击的任务里攻击成功且未被审计的概率。 这里另设攻击在未被审计时成功的概率为 0.5(教学假设)。 只用标准库。 """ from fractions import Fraction from math import comb STEPS = 200 BUDGET = STEPS * 2 // 100 # 2% 的步骤:4 步 def p_random(k, n=STEPS, m=BUDGET): """从 n 步中不放回地随机抽 m 步,至少抽中 k 个攻击步骤之一的概率。""" return 1 - Fraction(comb(n - k, m), comb(n, m)) def p_ranked(probs): """每个攻击步骤以给定概率独立进入可疑度前 m 名,至少有一步被审计的概率。""" miss = 1.0 for q in probs: miss *= 1 - q return 1 - miss def safety(p_audit, success=0.5): """Kutasov 等的安全性公式;success 是攻击未被审计时成功的概率。""" p_attack = (1 - p_audit) * success return p_audit / (p_audit + p_attack) def main(): print(f"总步数 {STEPS},审计预算 {BUDGET} 步") attack_a = [0.05, 0.70] attack_b = [0.05] + [0.03] * 10 rows = [ ("攻击 A(2 步)", len(attack_a), attack_a), ("攻击 B(11 步)", len(attack_b), attack_b), ] for name, k, probs in rows: pr = p_random(k) pk = p_ranked(probs) print(f"{name}:随机抽查 {float(pr):.4f}(精确值 {pr}),按可疑度 {pk:.4f}") print(f" 安全性:随机抽查 {safety(float(pr)):.3f},按可疑度 {safety(pk):.3f}") # 随机抽查要达到按可疑度审计对攻击 A 的发现概率,需要多少预算 target = p_ranked(attack_a) m = 1 while float(p_random(2, m=m)) < target: m += 1 print(f"随机抽查对攻击 A 的发现概率达到 {target:.4f},至少要审计 {m} 步(占 {m / STEPS:.1%})") if __name__ == "__main__": main()