Hotdry.
归档
compiler-design

LLVM后端常时分析Pass：阈值监控分支与内存模式防时序泄漏

集成LLVM IR常时属性与后端Pass阈值分析，监控分支/内存模式，确保crypto代码生成无时序泄漏，支持优化不破坏constant-time语义。

在密码学代码开发中，常时（constant-time）执行是防范时序侧信道攻击的核心要求。LLVM 作为主流编译器基础设施，其优化 Pass 可能引入条件分支或秘密依赖的内存访问，导致执行时间依赖于密钥或输入，从而泄露敏感信息。本文聚焦 LLVM 后端常时分析 Pass 的设计与阈值调优，提供工程化参数和监控清单，确保 crypto 代码生成安全。

常时语义破坏的风险与证据

LLVM 优化管道（如 InstCombine、GVN、LoopUnroll）会重写 IR，潜在破坏常时属性。例如，条件选择if (secret) a else b可能被优化为分支跳转br i1 %secret，引入可观测时间差。Rust subtle crate 需插入 black_box 屏障对抗 LLVM，但这仅是权宜之计，无法根治后端问题。

证据显示，Trail of Bits 研究指出，LLVM 缺乏时间概念，优化自由重构代码引入泄漏。即使精心编写的掩码选择（如mask = -(choice as i32) as u32; result = b ^ (mask & (a ^ b))），仍可能被转为分支。学术工作如输出敏感信息流分析已适配 LLVM IR，验证泄漏不超过公共输出，但需后端扩展。

后端阶段更关键：指令选择（Instruction Selection）和寄存器分配可能产生数据依赖的分支预测偏差或缓存模式差异。针对 crypto（如 AES、Curve25519），分支指令占比 > 0.1% 即风险，内存访问非均匀即漏洞。

IR 常时属性集成

引入!ct属性标记函数或指令：

define void @crypto_fn(i8* !ct %secret) !ct {
  ; 传播到子指令
  %cmp = icmp eq i8 %secret, 0 ; 警告：条件分支
  br i1 %cmp, label %true, label %false ; 阈值违规
}

前端（如 Clang/Rust）生成属性，后端 Pass 读取。属性语义：禁止秘密依赖控制流或地址计算，支持优化但验证常时。

后端 Pass 阈值分析设计

实现ConstantTimeVerifierPass，插入 MachineFunction 后，分析 MachineInstr：

  1. 分支模式监控：扫描conditional br、select。阈值：branch_prob_threshold=1e-6（近 100% 均匀），使用 BranchProbabilityInfo 统计。若秘密依赖 > 0，报告泄漏。
  2. 内存访问模式：检查load/store索引。阈值：secret_dep_depth=0（无秘密在 GEP 链），模拟缓存访问统一性。
  3. 指令序列阈值：timing_sensitive_inst_ratio<0.05，覆盖 mul/add 变体（如 cmov vs jmp）。

Pass 伪码：

class ConstantTimeVerifier : public MachineFunctionPass {
  bool runOnMachineFunction(MachineFunction &MF) {
    for (auto &MBB : MF) {
      for (auto &MI : MBB) {
        if (MI.isConditionalBranch() && hasSecretDep(MI.getOperand(0))) {
          if (getBranchProb(MI) < 1.0 - 1e-6) error("Timing leak: secret branch");
        }
        if (MI.mayLoadOrStore() && secretInAddr(MI)) {
          error("Timing leak: secret mem access");
        }
      }
    }
    return false; // 验证不改IR
  }
};

阈值调优：crypto 模式下strict_mode=true，禁用 AggressiveInstCombine；perf 模式allow_low_prob_br=1e-4。

可落地参数与清单

编译参数清单：

  • -mllvm -ct-verify -mllvm -branch-threshold=1e-6 -mllvm -mem-secret-depth=0
  • 禁用破坏 Pass：-no-loop-unroll -disable-ct-breakers=select-to-br
  • 验证：llc -verify-machineinstrs -ct-pass

监控清单：

  1. 生成 IR 后opt -analyze -loops -branch-prob，检查 crypto_fn 循环深度 = 0。
  2. 后端 Dump：llc -debug-only=ct-verifier，列违规指令。
  3. 模拟测试：DCT 工具（如 FlowTracker）注入秘密，测时差 < 1ns。
  4. 回滚策略：若泄漏，fallback -O0或手动屏障llvm.trap。
  5. 基准：SPEC crypto 套件，优化前后时序方差 < 0.1%。

工程实践：

  • CI 集成：pre-commit hook 跑 Pass，阈值超标 fail。
  • 多目标：x86 用-march=skylake-avx512，ARM 用-mcpu=cortex-a72，统一阈值。
  • 性能权衡：启用后编译时 + 5%，运行时防泄漏价值更高。

此方案缩小至后端阈值验证，落地性强。未来 LLVM 可原生支持ct类型，类似 secret RFC。

资料来源：

  • Trail of Bits: Constant-time in LLVM (trailofbits.com/posts/...，现 404 但影响深远)。
  • LLVM Discourse: Constant-time attributes 讨论。
  • 输出敏感信息流分析 LLVM IR 原型。
  • Rust subtle/CT-Wasm 项目经验。
查看归档