Constant-Time MPC Solvers as One-Measurement Timing Certificates

A robot controller that re-solves an optimization problem every few milliseconds has to finish before its deadline every time, not just on average. Proving that it will is hard today. The solver's running time depends on the robot's state: which constraints are active, how the matrices are conditioned, how far the state moved since the last step. So the worst case has to be found by enumerating an enormous number of situations or bounded by a very loose static analysis. Cryptographers faced a similar problem and solved it differently. To stop attackers from learning secret keys by timing code, they write "constant-time" programs. These programs execute the same instructions and touch the same memory addresses whatever the secret values are.

This note proposes treating the robot's state as the secret. If a model predictive control (MPC) solver is written so that its instruction trace and memory accesses are provably independent of the state and reference it receives, then one hardware measurement of its cycle count is its exact worst-case execution time. That bound holds for every state, every horizon length the code was compiled for, and every infeasible start. Static tools built for cryptographic code can check the independence. The same property also removes a timing side channel through which co-located software can infer the robot's disturbances.

Core Claim

Let $\theta$ denote the online problem data: the measured state, the reference trajectory and any time-varying bounds. Let $T(\theta)$ be the cycle count of one full solve on a fixed processor with interrupts masked. The claim is that an interior-point QP solver can be built for which the executed instruction sequence and address sequence are identical for all $\theta$, so that

$$T(\theta) = T(\theta_0) \quad \text{for every admissible } \theta,$$

where $\theta_0$ is any single test input. Under that property, worst-case execution time (WCET) certification costs one measurement plus one static information-flow check, rather than millions of hardware runs. Achieving the property takes two things. The iteration count must be fixed analytically, which existing work already provides. Every kernel inside an iteration must also be data-oblivious, which no existing work provides.

Where This Sits

The closest work is the execution-time-certified soft-constrained MPC of Wu, Zhou and Braatz. They show that an $\ell_1$-penalty soft-constrained linear MPC is equivalent to a box-constrained QP. An interior-point method on that box QP then needs a number of iterations fixed by the tolerance and the problem dimensions alone. They accelerate the Newton step with a vectorized $LDL^\top$ factorization. This paper supplies our outer algorithm. Its certificate, however, covers the iteration count, not the time spent inside each iteration. Pivot handling, the fraction-to-boundary step-length computation, and the compiler's treatment of floating-point comparisons can all still branch on data. The file notes that nobody has checked this code with a constant-time analyzer. The method also applies only to condensed problems, and the authors leave block-sparse long-horizon structure open.

The second anchor is the exact WCET analysis of Arnström, Broman and Axehill. It splits the state space into regions where an active-set solver performs an identical operation sequence, then measures one representative per region on an ARM Cortex-M4. This motivates our proposal in two ways. It proves that "identical operation sequence implies identical time" is a sound certification principle on real embedded hardware. It also shows the cost of applying that principle region by region: the number of representatives exceeds 1.5 million at horizon $N=14$. We apply the same principle globally by forcing a single region.

On the constant-time side, the methods we reuse are as follows. Drucker et al. run iterative decoders for a fixed number of iterations and fill the remainder with bitmasked "mock" iterations; our fixed-iteration IPM needs no mock iterations, since its count is already analytic. Chen et al. replace pivot-dependent swaps in Gaussian elimination with conditional moves. Wahby handles exceptional cases with uniform formulas while staying within about 10% of variable-time code. CtChecker is a static information-flow analysis on compiler intermediate code that detects secret-dependent branches and memory accesses. It handles codebases up to 24K lines in under a minute, but it has only been applied to cryptographic libraries.

Two papers constrain the design. The Fiat Cryptography work (Erbsen et al.) and CtChecker both document that compilers can turn branchless source back into branches. Verification therefore has to target compiled code, not source.

ScheduLeak shows that an unprivileged task can reconstruct when a 50 Hz control task runs, with inference success above 97%. It supplies the secondary security motivation, and we are careful about what it implies. A constant-time solver does not hide the period of the control task, which ScheduLeak recovers from scheduling alone. It hides only the variable duration of each solve. That duration is what carries information about the state.

Research Program

The first step builds a data-oblivious box-QP interior-point solver on top of the Wu et al. formulation. Every loop bound is a compile-time constant. The fraction-to-boundary step length becomes a branchless minimum over all box constraints. Factorization uses a fixed diagonal regularization instead of conditional pivot repair, with branchless selection in the style of Chen et al. where a guard remains unavoidable. Floating-point subnormal handling is pinned by hardware flush-to-zero mode, so that data-dependent slow paths on x86 and similar cores cannot occur. The numerical price of these choices is measured against the original solver's accuracy (Wu et al. report maintaining $10^{-6}$ accuracy on ill-conditioned cases).

The second step extends the solver to long-horizon sparse problems, the case Wu et al. leave open. For block-tridiagonal Newton systems, a block factorization along the horizon has a sparsity pattern fixed by the horizon length and the dimensions alone, so its memory addresses are data-independent by construction. A condensed formulation cannot offer that. This step is where the proposal gains most over enumeration, because the horizons where enumeration becomes intractable are exactly the ones this structure handles.

The third step builds a verification pipeline. CtChecker runs on the optimized intermediate code with every component of $\theta$ labeled secret. A disassembly check of the final binary then confirms that no conditional branches or data-indexed loads survived code generation. This is the first use of a cryptographic constant-time analyzer as a WCET certification tool, and false positives specific to numerical code, such as aliasing in matrix buffers, are recorded as findings in their own right.

The fourth step is certification and characterization on three platforms. On an ARM Cortex-M4, the Arnström et al. platform, flash wait states and any flash prefetch cache are the residual hardware nondeterminism, so code runs from RAM or with the cache disabled. On a Raspberry Pi 4, the ProxQP platform, data caches make memory obliviousness matter. On an x86 desktop, subnormal slowdowns are the known hazard.

Baselines

The naive reference is OSQP (Stellato et al.) and ProxQP (Bambade et al.) run with warm starts and default early-exit tolerances. These are what practitioners deploy. OSQP reports up to 19x speedups from factorization caching. ProxQP reports solves under 1 ms on a Raspberry Pi 4 for humanoid balancing and speedups of 1.2-2.9x over OSQP on sparse MPC. Both define the typical-case speed we will lose. For certification, they are run through a large random-state campaign, and their largest observed time serves as an empirical, uncertified bound. We beat them if our single-measurement certified time falls below their maximum observed time on the same problem. If it does not, we report the overhead ratio honestly.

The strongest certification baseline is the exact complexity-certification method of Arnström et al. on the inverted pendulum. They report an exact WCET of 136,809 cycles at $N=10$ on the Cortex-M4, against 5.7 million cycles from the commercial aiT analyzer. We run our solver on the same pendulum model, horizons and board. A fixed-iteration interior-point method may well exceed 136,809 cycles at $N=10$, because it always pays its full iteration count. We count as success either a certified time within a small factor of their exact bound at short horizons, or any certified bound at $N \ge 14$, where their archetype count exceeds 1.5 million. Certification wall-clock cost is reported for both methods; they report generating the $N=10$ archetypes in 14 seconds and running them on hardware in about 10 minutes.

The closest method baseline is the released L1-penalty-QP solver of Wu et al., run unchanged with its analytic iteration count on the same boxed problems and the AFTI-F16 aircraft model. The file reports no per-state cycle-count spread for this solver (no reported result found on Lacuna for the timing variance of the Wu et al. solver). Measuring that spread is therefore the first experiment.

The key ablation keeps the fixed iteration count and swaps only the kernels, original versus oblivious. It isolates whether instruction-level obliviousness is what turns an iteration-count certificate into a time certificate. A second ablation compiles the oblivious source at high optimization without the binary check, to see whether the compiler reintroduces branches in numerical code as it does in cryptographic code.

Why not just…?

Why not just spin until the deadline after running a fast solver? Padding makes the output instant constant, but it needs a known safe deadline, and finding that deadline is the whole problem. Padding to an empirical maximum is unsound. Padding to an aiT-style bound wastes roughly 40x of the processor on the pendulum benchmark, per Arnström et al. Against a scheduler-level observer, busy-wait padding does hide solve duration nearly as well as our design, and we concede that. It does not hide cache footprints on the Raspberry Pi and x86 targets, which the leakage experiment below measures directly.

Why not just use Wu et al.'s fixed iteration count and sample random states for the residual jitter? This is the most serious threat. If their per-iteration time is already nearly flat, our kernel rewriting adds little. The kernel ablation settles it. If the spread of the unmodified solver across a very large campaign that includes infeasible and ill-conditioned starts is within measurement noise on the Cortex-M4, the contribution narrows to the sparse extension and the static proof. Sampling alone is still never a proof, because a rare pivot or subnormal path can be missed. That is exactly what CtChecker plus the binary check rules out.

Why not just scale up complexity certification with smarter enumeration? Enumeration cost grows with the number of distinct active-set sequences, which grows combinatorially in the horizon; the 1.5-million count at $N=14$ reflects that growth. Our approach makes the number of regions one by construction. What it gives up is typical-case speed, and the horizon sweep reports both costs side by side.

Why not just replace the solver with a neural policy? A fixed network does run in constant time. It loses the constraint handling and infeasibility recovery that keep the optimizer in the loop. The learned warm-starting work in the file (robot catching, ISS trajectory planning) uses networks to feed a solver, not to replace it. A learned warm start would also be pointless here, since our iteration count does not depend on initialization.

Proposed Experiments

The decisive check for the core claim is flat timing. We run $10^5$ random states per horizon on the Cortex-M4 pendulum, with interrupts masked and code in RAM, including states that start outside the feasible set. The max-minus-min cycle count should be zero for our solver and nonzero for the Wu et al. kernels. The same test on the Raspberry Pi 4 and x86 reports the residual spread under caches and dynamic frequency scaling, with frequency pinned.

The certification comparison sweeps pendulum horizons from 6 through 14 and beyond. For each horizon it plots certified cycles and certification cost for our solver, for Arnström et al., and for aiT, where their reported numbers are available. It also plots typical-case cycles for OSQP and ProxQP. The expected crossover, where our certified bound becomes available and theirs is not, lies at the horizons where enumeration stops scaling.

Closed-loop quality on the AFTI-F16 model under initial infeasibility checks that fixed regularization and branchless step lengths do not degrade accuracy or tracking relative to the original solver.

The leakage experiment follows ScheduLeak's observer model on a Raspberry Pi. An unprivileged task records the control task's per-period duration while the plant receives disturbances of varying size. We estimate the mutual information between observed duration and disturbance magnitude for warm-started OSQP, for OSQP with spin-padding, and for our solver. A Prime+Probe style cache probe, in the spirit of the public-cloud LLC attack study, then separates padding from true obliviousness.

A negative result anywhere in this program would still be informative. It would show either that fixed-iteration solvers are already flat enough in practice or that constant-time floating-point code cannot be achieved on commodity embedded cores.