PaperlayerView exact revision on arXiv

Source-linked AI summary

Eliminating Timing Side-Channel Leaks using Program Repair

Meng Wu, Shengjian Guo, Patrick Schaumont, Chao Wang

arXiv:1806.02444v2cs.CRcs.PLcs.SE

TL;DR

Secret-dependent execution time and cache behavior can expose cryptographic keys, tokens, and passwords, while manual timing analysis is difficult and labor-intensive. The paper applies static analysis and code transformation to mitigate instruction- and cache-timing leaks. Tests on cryptographic software report that both leak types were eliminated, with analysis taking seconds and transformation under a minute.

  • Problem

    Secret-dependent instruction execution and cache behavior can expose keys, tokens, and passwords, and manually analyzing timing characteristics is difficult and labor-intensive.

    Source: §1 · p. 1

  • Method

    Static analyses identify variables dependent on annotated secret inputs and potential instruction- or cache-timing leaks, then code transformations mitigate them.

    Source: §1 · p. 1

  • Results

    Across 19,708 lines of C/C++ cryptographic code, static analysis took a few seconds, transformation took less than a minute, and GEM5 confirmed both leak types were eliminated.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The LLVM-based tool was reported scalable on real cryptographic applications, with moderate increases in code size and runtime overhead.

    Source: §1 · p. 2, §9 · p. 10

    The software-only method does not address leaks exploitable by probing hidden CPU microarchitectural state, and the considered threat model leaves multicore and multilevel-cache extensions for future work.

    Source: §3 · p. 4, §7.4 · p. 10

Abstract

from arXiv · show

We propose a method, based on program analysis and transformation, for eliminating timing side channels in software code that implements security-critical applications. Our method takes as input the original program together with a list of secret variables (e.g., cryptographic keys, security tokens, or passwords) and returns the transformed program as output. The transformed program is guaranteed to be functionally equivalent to the original program and free of both instruction- and cache-timing side channels. Specifically, we ensure that the number of CPU cycles taken to execute any path is independent of the secret data, and the cache behavior of memory accesses, in terms of hits and misses, is independent of the secret data. We have implemented our method in LLVM and validated its effectiveness on a large set of applications, which are cryptographic libraries with 19,708 lines of C/C++ code in total. Our experiments show the method is both scalable for real applications and effective in eliminating timing side channels.

1 INTRODUCTION

The introduction frames secret-dependent instruction timing and cache behavior as exploitable leaks, then proposes automated static analysis and code transformation to mitigate both. SC-Eliminator was evaluated on cryptographic software, with experiments reporting scalability and elimination of both leak types.

1 INTRODUCTION

  • Timing leaks arise when secret values affect executed instructions or cache hits and misses, while manual analysis and repeated countermeasure application are labor-intensive and error-prone.Random-delay noise can be removed using statistical analysis techniques.Source: §1 · p. 1
  • The method propagates sensitivity from secret inputs, checks for sensitive unbalanced branches and memory accesses spanning cache lines, then transforms code to equalize execution time.The LLVM-based tool uses separate transformations for conditional jumps and lookup-table cache behavior.Source: §1 · p. 1
  • The introduction distinguishes this approach from instruction-only detection methods, cache-leak detection methods without mitigation, and countermeasures that hide leaks with random delays.The paper also contrasts its software-only approach with techniques requiring hardware support.Source: §1 · p. 2
  • Across 19,708 lines of C/C++ cryptographic code, static analysis took a few seconds, transformation took less than a minute, and GEM5 confirmed both leak types were eliminated.The mitigated software had moderate increases in code size and runtime overhead.Source: §1 · p. 2
  • The paper presents static analysis and transformation, an LLVM tool targeting cryptographic C/C++ software, and an evaluation on many applications.The introduction identifies Chronos, FELICS, SUPERCOP, Botan, and Libgcrypt among the evaluated software.Source: §1 · p. 2

2 MOTIVATION

The section illustrates how secret-dependent branches and lookup-table accesses create timing leaks in cryptographic code. It surveys mitigations that address instruction timing, cache behavior, and data-dependent loops.

2.1 Conditional Jumps Affected by Secret Data

  • Cross-copying equalizes branch instruction counts, but hidden microarchitectural states can preserve timing leaks; the paper instead replaces sensitive branches with branchless assignments.C-style conditional assignment and LLVM select do not guarantee constant-time execution because LLVM may compile them into conditional jumps.Source: §2.1 · pp. 2–3
  • 90,844 CPU cycles for both keys after CTSEL, versus 88,014 for k1 and 87,624 for k2 after cross-copying.The example shows that equalizing branch instruction counts did not eliminate timing variation, while the branchless mitigation produced the same cycle count for both keys.Source: §2.1 · pp. 2–3

2.2 Table Lookups Affected by Secret Data

  • Secret-dependent AES S-box indices can change cache misses: sixteen repeated accesses to sbox[0] yield one miss, while sixteen distinct bytes may yield four.The latter example assumes 64 bytes per cache line.Source: §2.2 · p. 3
  • When per-iteration timing is not observable, touching all cache lines can suffice; naive preloading may enable Flush+Reload attacks, which the Figure 5 approach avoids.The section distinguishes mitigation granularity by what the attacker can observe.Source: §2.2 · p. 3
  • For total-time observers, preloading a table that fits in cache incurs four initial misses, but safely using this optimization requires proving accesses remain MUST-HIT.Complex loops with branches, nested loops, and calls make sound static analysis necessary to establish this condition.Source: §2.2 · p. 3

2.3 Idiosyncratic Code Affected by Secret Data

  • A secret-dependent loop implementing a shift can be rewritten with a fixed MAX_C bound, then mitigated using the branch countermeasures.The RC5 example involves a rotation count aliased to sensitive c->xk.Source: §2.3 · p. 4

3 THREAT MODEL

The threat model considers a deterministic program and an attacker who can observe only total execution time. The paper excludes attackers who directly inspect microarchitectural CPU state.

3 THREAT MODEL

  • The attacker can observe variation in the program’s total execution time with respect to secret data, but not hidden CPU microarchitectural states.The paper cites remotely timing a server as an example of the assumed attacker and leaves software-only mitigation of more-capable attacks for future work.Source: §3 · p. 4
  • A program is leak-free when its execution time is independent of the secret input; a leak exists if some fixed public input yields different times for two secrets.This definition is stated for a deterministic program whose execution is fixed by its input.Source: §3 · p. 4
  • Execution time includes both CPU instruction time and memory-access time, with load and store latency determined by cache hits or misses.The method aims to equalize both components across program paths.Source: §3 · p. 4

4 DETECTING POTENTIAL LEAKS

The detection pipeline marks variables that may depend on secrets, then checks their effects on branches and lookup-table accesses. Conservative analysis flags potential leaks while field-sensitive pointer analysis helps avoid false positives.

4 DETECTING POTENTIAL LEAKS

  • The LLVM IR detection passes take user-marked secret inputs and return instructions whose execution may depend on those inputs.Sensitivity tags are propagated transitively through data and control dependencies.Source: §4 · p. 4, §4.1 · p. 4

4.1 Static Sensitivity Analysis

  • Sensitivity propagates from secret sources through data or control dependencies, while field-sensitive pointer analysis limits tags to relevant structure fields.In the Chronos example, this avoids falsely flagging an unbalanced condition on ctx->key_length as leaky when only key_enc is sensitive.Source: §4.1 · p. 4, Figure 8 · p. 5

4.2 Leaky Conditional Statements

  • Sensitive conditional statements are treated as potential leaks even when their branches have equal instruction counts, because hidden microarchitectural states can still cause timing differences.The method applies CTSEL-based mitigation to these sensitive conditionals.Source: §4.2 · p. 5

4.3 Leaky Lookup-table Accesses

  • A lookup-table access is a potential leak when its index is sensitive, but mitigation can be skipped if analysis establishes that the table is already loaded and the access must hit.The example is a secret-indexed sbox lookup; the must-hit test is described in Section 6.2.Source: §4.3 · p. 5

5 MITIGATING CONDITIONAL STATEMENTS

The method mitigates sensitive conditional statements by standardizing their control-flow form and replacing conditional jumps with branch-free value selection. It also removes redundant selections when the branches store equivalent values.

5 MITIGATING CONDITIONAL STATEMENTS

  • Sensitive conditional jumps are eliminated rather than balanced with dummy instructions, avoiding reliance on equal instruction counts.The procedure traverses the dominator tree in depth-first order so inner branches are handled before outer branches.Source: §5 · p. 5

5.1 Standardizing Conditional Statements

  • Non-standard conditionals are transformed to have unique entry and exit blocks, with auxiliary variables used to make loop bounds independent of sensitive values.MAX_B is a conservative statically computed bound; in cryptographic software it is often 64, 32, 16, or 8 depending on the number of bits of x.Source: §5.1 · p. 5, Figure 9 · p. 5, Figure 10 · p. 5

5.2 Replacing Conditional Statements

  • CTSEL selects values by condition to replace memory stores and SSA Phi-node values, after which the conditional jumps can be replaced by unconditional jumps.For stores, the selected value preserves the original branch’s effect; target-specific CTSEL implementations may reduce runtime overhead.Source: §5.2 · p. 6

5.3 Optimizations

  • When both branches store the same value, their stores can merge without CTSEL; otherwise, one CTSEL selects between the two values, reducing the original two instances to one.The transformation addresses redundant CTSEL instances introduced by the basic mitigation.Source: §5.3 · p. 6

6 MITIGATING LOOKUP-TABLE ACCESSES

Lookup-table mitigation is tailored to the attacker’s observation granularity, and static cache analysis can reduce its runtime overhead. The analysis conservatively identifies must-hit accesses and uses loop structure to skip repeated mitigation when cache residency is established.

6 MITIGATING LOOKUP-TABLE ACCESSES

  • For attackers observing only total execution time, the method exploits cache structure and software behavior to reduce overhead relative to finer-grained mitigation.The analysis-based optimization checks whether a loaded table remains in cache until its accesses complete.Source: §6.1 · pp. 6–7

6.1 Mitigation Granularity and Overhead

  • Byte-level mitigation touches all table elements per access, while line-level mitigation touches all cache lines; both produce M misses, but different numbers of hits.The byte-level hit count is K ∗ N − M and the line-level hit count is K ∗ M − M; hit-count differences may matter less because a hit often takes an order of magnitude less time than a miss.Source: §6.1 · p. 7, Table 1 · p. 7
  • If static cache analysis proves the table remains resident, mitigation needs to load each line only once, producing M misses in the first loop iteration and K − 1 hits in the remaining iterations.Figure 12 illustrates preloading only in the first iteration.Source: §6.1 · p. 7, Figure 12 · p. 7

6.2 Static Cache Analysis-based Reduction

  • The MUST-HIT analysis tracks possible cache ages and declares a memory element definitely cached when its upper-bound age is at most N.The analysis uses abstract interpretation to summarize states across paths and inputs; it assumes a fully associative cache with LRU updates.Source: §6.2 · pp. 7–8
  • At control-flow merges, the join takes the maximum possible age so an element is considered cached only if it is cached on both paths.For an access whose index is not statically known, the analysis assumes the worst-case index when updating the abstract cache state.Source: §6.2 · p. 8, Figure 14 · p. 8
  • The cache analysis is sound but not complete, and it terminates because its abstract domain is finite and its transfer and join functions are monotonic.Soundness guarantees that a variable identified as cached is actually in cache; incompleteness is accepted to avoid requiring sound and complete analysis, which could make the problem undecidable.Source: §6.2 · p. 8
  • Unrolling the first loop iteration lets the method mitigate initial misses and then skip mitigation in subsequent iterations classified as MUST-HIT.The paper reports that many cryptographic loops have first-iteration misses followed by hits, and that this cache behavior can be exploited in real applications.Source: §6.2 · pp. 7–8

7 EXPERIMENTS

Experiments on cryptographic C/C++ benchmarks evaluated leak detection, mitigation, execution costs, and machine-code behavior. GEM5 results showed timing variation in original programs becoming constant after mitigation, with one benchmark that could not be demonstrated to leak under the crafted inputs.

7 EXPERIMENTS

  • The evaluation covered 19,708 lines of cryptographic C/C++ code, and static leak analysis completed in a few seconds in all cases.The experiments examined effectiveness, scalability, and code-size and runtime overhead.Source: §7 · pp. 8–9, §7.1 · p. 9

7.1 Results: Leak Detection

  • Many lookup tables were cache-sensitive, while sensitive conditional jumps were rare: leaks appeared in twofish and three older textbook implementations.The cache analysis used a fully associative LRU cache with 512 lines of 64 bytes each.Source: §7.1 · p. 9

7.2 Results: Leak Mitigation

  • For anubis, only 10 of 868 sensitive LUT accesses needed mitigation, reducing program size from 9.08x to 1.10x and execution time from 6.90x to 1.07x.Table 4 reports mitigation results; runtime overhead is based on averages of 1,000 simulations with random keys.Source: §7.2 · p. 9, Table 4 · p. 9

7.3 Results: GEM5 Simulation

  • Original-program execution time varied but became constant after mitigation; aes_keys was the exception because leak-demonstrating inputs could not be manually crafted.GEM5 simulations used two crafted inputs per benchmark.Source: §7.3 · p. 10, Table 5 · p. 10

7.4 Threats to Validity

  • The software-based mitigation targets total-time-aware leaks, not channels exploitable only by probing hardware such as instruction pipelines or data buses.Multi-core and multi-level-cache threat models are left for future work.Source: §7.4 · p. 10

8 RELATED WORK

Related work covers timing attacks and leakage measurement, branch-oriented countermeasures, and approaches based on randomization or hardware changes. The cited work leaves cache-timing leaks outside several compiler and formal methods, while some alternatives carry substantial overhead or require hardware modifications.

8 RELATED WORK

  • Timing attacks have been demonstrated across platforms, including remotely and in the seL4 microkernel.Prior work also quantified timing leaks using channel capacity, min-entropy, d-leakage, and information-theoretic models.Source: §8 · p. 10
  • Branch-focused countermeasures include cross-copying, branch merging, unification, transactional branching, and an x86 compiler backend.A comparison on Java byte-code found none eliminated leaks completely, and these methods did not address cache-timing leaks.Source: §8 · p. 10
  • Randomization and blinding hide rather than eliminate timing leaks [23]; hardware isolation requires CPU changes, while timing obfuscation does not eliminate channels.Oblivious RAM removes data-flow leakage but requires substantial on-chip memory and incurs significant execution-time overhead.Source: §8 · p. 10
  • Compiler and formal methods have addressed other side channels, including power and faults, but none of the cited techniques addressed cache-timing side channels.The cited approaches include compiler-like tools, SMT-based verification, and inductive synthesis.Source: §8 · p. 10

9 CONCLUSIONS

The paper presents program repair for mitigating side-channel leaks, implemented in SC-Eliminator for cryptographic C/C++ libraries. Evaluation on real applications found the method scalable and effective against instruction- and cache-related timing side channels, with moderate code-size and runtime increases.

9 CONCLUSIONS

  • The paper presents a program-repair method for mitigating side-channel leaks.The method was implemented in SC-Eliminator for cryptographic libraries written in C/C++.Source: §9 · p. 10
  • Evaluation on real applications showed the method was scalable and effective in removing instruction- and cache-related timing side channels.Source: §9 · p. 10
  • Mitigated code had only moderate increases in program size and runtime overhead.Source: §9 · p. 10
Loading 1806.02444v2…