Source-linked AI summary
FreeSBee: A Constant-Time Compilation Pipeline
Julian Ganz, David Knothe, David Oswald, Sebastian Reiter, Thorben Schneider, Simon Wegener
TL;DR
Execution-time variation dependent on confidential data can leak sensitive information, and achieving constant-time behavior on realistic devices is difficult. The paper combines taint analysis with compiler control-flow transformations and evaluates the workflow using static timing analysis and statistical measurements. The results show reduced timing variation and constant-time behavior under several basic timing models, but not cycle-accurate constant-time execution across microarchitectural effects.
Problem
Timing side-channels can leak confidential information through execution-time variation, while achieving cycle-level constant-time execution on realistic devices is difficult.
Source: §1 · p. 1Method
Results
Standard deviation fell from 78.8 to 19.3 cycles after hardening, while static best- and worst-case times matched in the simple, memory, and const-i timing models.
Source: §5 · p. 4Takeaways & Limitations
The evaluation demonstrates automated hardening of C code against control-flow timing variation, with effectiveness assessed using static timing analysis and statistical methods.
Source: §7 · p. 7
Abstract
from arXiv · showhide
Constant-time execution is an important security property, especially for IoT devices, that prevents the leakage of sensitive information over timing side-channels. However, achieving constant-time execution is very hard when going down to the cycle level, at least on realistic devices. A lot of research is concerned with producing tools that either determine whether code is constant-time or that ensure it is compiled into a constant-time binary, with various degrees of accuracy. In this work, we present and evaluate a full workflow for hardening against timing side-channels during compilation. It starts with taint analysis to determine the code locations that depend on sensitive information. These are then the object of automated control-flow transformations inside the compiler to seal possible timing side-channels. We evaluate our workflow in detail on a realistic application running on a RISC-V core using both static timing analysis and statistical methods. Even though we do not reach cycle-accurate constant-time execution, our statistical results suggest that our hardened binary is safe against timing attacks.
1 Introduction
Timing variation dependent on confidential data can leak sensitive information, making constant-time execution important for connected embedded systems. This paper presents a compiler-based workflow to harden sensitive execution paths, while focusing mainly on control-flow variability and, to some extent, caching.
1 Introduction
- Timing side-channels arise when execution time varies with confidential data, so instruction sequences should execute independently of secrets such as cryptographic keys.The concern is especially relevant to connected embedded systems, including IoT devices.Source: §1 · p. 1
- Source-level constant-time coding can constrain expressiveness and depends on compiler and build settings, making it increasingly impractical in real applications.Compiler optimizations may also introduce execution-time variation despite manual coding practices.Source: §1 · p. 1
- The proposed approach combines information-flow analysis with a CompCert transformation pass to automatically eliminate timing fluctuations from sensitive execution paths.The pass is evaluated on an AES test application using statistical measurements and binary-level static timing analysis.Source: §1 · p. 1
- The work mainly addresses execution-time variability from control flow and, to some extent, caching, while acknowledging operand-dependent instruction variability.The workflow is designed for deployment without further assumptions or knowledge of target hardware.Source: §1 · p. 1
2 Related Work
Prior work includes tools for detecting timing leaks and compiler techniques for removing them, while manual constant-time coding faces practical constraints. This work combines taint analysis and compilation with user control over where partial control-flow linearization occurs, and evaluates the workflow on a RISC-V application.
2 Related Work
- Existing compilers may introduce side-channels despite manual techniques intended to prevent optimizations, and hardware can introduce execution-time leaks as well.The cited discussion argues that such manual techniques become unfeasible as compiler analyses deepen.Source: §2 · p. 1
- Binary-level assessments can detect leaks introduced during compilation, whereas source-level assessments rely on strong assumptions about the compiler.The passage also notes that tools exist to assess timing leaks at both source and binary levels.Source: §2 · pp. 1–2
- The evaluation combines static timing analysis of best- and worst-case execution time with Welch’s t-test on real measurements to assess timing variation.The paper uses the static analyzer to assess constancy under a timing model and the statistical test to examine whether remaining variation is related to secrets.Source: §2 · p. 2
- The pipeline combines taint analysis and compilation, lets users control where PCFL is applied, and is evaluated with static analysis and dynamic tests on a RISC-V application.Part of the implementation was formally verified in separate work.Source: §2 · p. 2
3 Workflow
The workflow marks secrets, tracks taint through the program, and uses a compiler pass to linearize secret-dependent control flow. Its hardening includes handling loops and predicating memory accesses while preserving program behavior.
3 Workflow
- The workflow begins with user annotations marking secret values, then propagates taint and applies a compiler pass that linearizes the control-flow graph before lowering to RISC-V.Astrée and Annotator process annotations and information-flow results; CompCert performs the middle- and backend compilation.Source: §3 · p. 2
3.1 Information-Flow Analysis
- Astrée’s static taint analysis identifies variables dependent on user-marked secrets and Annotator adds maybe_tainted attributes to possibly tainted parameters and globals.Astrée soundly over-approximates value ranges and tracks variable accesses; its structured dependency report feeds Annotator.Source: §3.1 · p. 2
3.2 Compilation and Hardening
- At CompCert’s RTL level, PCFL transforms the control-flow graph to avoid branching on secret conditions while preserving equivalent behavior through predication.The algorithm aims to linearize as few additional branches as possible; the compiler can harden affected functions independently.Source: §3.2 · p. 2
- PCFL handles nested loops with public or secret exits by removing secret exits and requiring loops to exit only through public exits.When loop variables are reused after transformation, copies can restore their original exit values.Source: §3.2 · pp. 2–3
- When linearization affects a memory-access condition, predication uses a dummy memory location to prevent crashes but may introduce cache effects.The constant-time property is then preserved by subsequent lowering passes.Source: §3.2 · pp. 2–3
4 Evaluation
The evaluation applies the workflow to an AES rolling-code door opener on a RISC-V-based IoT application. It assesses timing with empirical measurements and static best- and worst-case analysis.
4 Evaluation
- The workflow is evaluated on a RIOT-based AES rolling-code door opener, with empirical measurements and static best- and worst-case timing analysis.The application receives an encrypted packet, verifies its payload, and drives an output according to the command.Source: §4 · p. 3
- The pipeline rejects loops that have only secret exits, since transformation could otherwise make them loop forever.The paper describes this case as rare.Source: §4 · p. 3
4.1 Sample Application
- The sample application runs on an FPGA-based SoC with a single RISC-V core, LRU caches, and 128kB of on-chip SRAM.The SRAM is described as ensuring deterministic instruction loads and memory accesses.Source: §4.1 · p. 3
4.2 Empirical Measurements
- Empirical analysis compares repeated timings for one fixed input against multiple random inputs using Welch’s t-test.The t-value is computed incrementally as data arrives, and the process is repeated with different fixed inputs.Source: §4.2 · p. 3
4.3 Static Timing Analysis
- Static analysis uses TimingProfiler’s tunable processor-and-cache timing models to assess whether best- and worst-case estimates coincide.Its path analysis formulates an integer linear program to minimize or maximize execution time.Source: §4.3 · pp. 3–4
- The timing models separate pipeline and memory effects from instruction-level variability, with var-i modeling multiplication times of 2–7 cycles.The simple, memory, icache, and dcache models address pipeline and memory timing; const-i and var-i focus on instruction execution.Source: §4.3 · p. 4
5 Results
CFG hardening removes the secret-dependent early exit in aes_mul, lowering measured timing variation and equalizing best- and worst-case times in several static models. Cache-related variation remains after CFG hardening, but the added cache countermeasure yields t-test results with no values above the threshold.
5 Results
- In the baseline, aes_mul’s early exit makes execution faster when a parameter is zero; across 144 calls, the tainted parameter’s zero probability is 1/256, producing Bernoulli-like timing spikes.The baseline t-value for every fixed input rises above 4.5.Source: §5 · pp. 4–5, Figure 5 · p. 6
- 78.8 to 19.3 cycles: after hardening, the standard deviation fell and the decryption-time spikes disappeared, although average execution time increased.Only aes_mul was linearized in the sample application.Source: §5 · p. 4, Figure 2 · p. 5, Figure 3 · p. 5
- After CFG hardening, best- and worst-case times coincide in the simple, memory, and const-i models; icache retains smaller jitter, while var-i exposes possible multiplication-instruction timing variation.The var-i concern is associated with mul and mulh used for the modulo operation.Source: §5 · pp. 4–5, Table 1 · p. 5
- After hardening, the tainted-parameter branch is removed and predication makes the instruction sequence independent of whether the parameter is zero.Some t-values nevertheless exceed 4.5 and show a rising trend, consistent with remaining secret-related cache effects.Source: §5 · pp. 5–6, Figure 6 · p. 6
5.1 Eliminating Cache Effects
- The cache countermeasure replaces lookup-table element accesses with ordered accesses spanning the array’s cache lines, selecting the requested value afterward.The approach aims to make remaining cache-induced variance independent of the secret.Source: §5.1 · p. 6
- The added cache countermeasure carries a large performance penalty, but the t-test shows no values above 4.5 or identifiable rising trends.Static analysis reports an 8.4-kcycle icache spread with the countermeasure versus 1.1 kcycles without it; it analyzes one isolated aes_mul execution with unknown initial cache state.Source: §5.1 · p. 6, Table 2 · p. 6
6 Future Work
The future work discussion identifies secret-dependent array accesses as a path toward automating cache countermeasures, while noting that operand-dependent instruction timing remains outside the work’s scope. Addressing such effects may require instruction timing specifications and constant-time replacements.
6 Future Work
- For arrays whose size is known at compile time, data-flow analysis can identify secret-dependent indices, making the cache countermeasure automatable as a compiler transformation.The cache countermeasure described here was carried out semi-manually in source code.Source: §6 · p. 6
- The work does not consider microarchitectural effects beyond caching, including operand-dependent instruction timing such as early-out multiplication.Such effects could be addressed during instruction selection if instruction timing specifications and, where needed, replacement patterns are available.Source: §6 · p. 7
7 Conclusion
The authors present an automated, build-flow-compatible approach to eliminating timing side-channels from C code and evaluate its effectiveness with static and statistical analyses. The implemented extension eliminates control-flow-induced variance; addressing microarchitectural effects depends on knowing those effects.
7 Conclusion
- The implemented compiler extension eliminates only execution-time variance introduced by control flow.The general approach could also handle target-CPU microarchitectural side-channels if those effects are known.Source: §7 · p. 7