Multi-taint Analysis for Constant-Time Verification: From False Positives to Confirmed Leaks

Side-channel timing attacks let an attacker recover secret keys and other sensitive data just by measuring how long a program takes to run, or by watching which memory addresses it touches. The standard defense, constant-time programming, sounds simple in principle: never branch on secret data and never use secret data to compute a memory address. In practice it is notoriously easy to get wrong, and compilers can silently introduce violations that were not present in the source code.

In this talk, we walk through taint analysis, a popular automated technique for finding these violations, starting from minimal examples. We show, step by step, how a taint tracker propagates through assignments, branches, and memory accesses, and why this simple idea already catches real bugs.

We then hit the wall every overapproximating analyser eventually runs into: false positives. To scale to real binaries, taint analyzers must approximate, and approximation inevitably manufactures alarms that look like leaks but are not. We live-demo this problem on a small crafted example, and explain why it forces practitioners into manual triage after every run, even on programs that are perfectly safe.

Finally, we introduce our fix: a multi-taint system that distinguishes data that is definitely secret-dependent from data that merely might be, due to analysis imprecision. We show, on the same demo and on real cryptographic library, how this single idea collapses the manual-review burden from "every finding" to a handful, without giving up the guarantee that no real leak is missed. The talk closes with our open-source tool, SCOUT-CT, showing reported violations get automatically sorted into confirmed leaks and merely-potential ones.