ITADN

Statistical CT tests

#220Pull Requestdvdplm 创建于 2025-05-08
D
dvdplmcommented
## Description This PR adds a few tests (in the form of an example) that exercises a few selected pieces of the `synedrion` code base from a constant time perspective. It uses the statistical approach from the ["Dude, is my code constant time" paper](https://eprint.iacr.org/2016/1123.pdf), which is based on a pretty simple statistical test, ["Welch's t-test"](https://en.wikipedia.org/wiki/Welch%27s_t-test). Tests proceed as follows: - Prepare a set of test inputs by generating two "classes", one with random or "normal" input data, and the other with plausibly "special" characteristics. - Measure the time it takes to execute the code. - Compute the "max t" for the set If the "normal" and "special" sets of inputs have the same mean values, then the code is possibly CT. If they disagree, we're likely not CT; in the test output, the smaller the absolute value of `max t` is, the better. The paper (and rust crate) suggests using 5 as the threshold, so a |max t| >= 5 means "not CT". The tests take the form of a piece of example code, and are ran by invoking `cargo run --example`. Given the statistical nature of the tests it is not obvious how big an input set needs to be for a given piece of code, and to that end the `dudect-bencher` crate provides a `--continuous` flag to keep testing until interrupted manually. As part of the test output there's an estimate of how many samples are needed to reach the threshold of |5| (but if the code is actually CT it will never reach |5| of course). ## Discussion ### CT is a spectrum When reading about constant time-ness in blog posts and papers, it's often presented as a binary CT/not-CT. In reality it's a bit more complex than just checking the assembly and check for branches. A piece of code can be "reasonably CT" in the sense that yes, there is a leak but it requires hundreds of millions of repetitions to tease out a signal, which may or may not be feasible in an actual deployment. As an example, take the `SecretBox::init_with` test. It is not CT, but it takes more than 600 million operations to make `|t|` go above 5. Is this non-CT-ness realistically possible to exploit in the `synedrion` setting? I'd argue it is not. ### Are dudect tests the way to go? The rust implementation that comes with the paper is a bit rough. The test setup presented in this PR is not very elegant: - uses `--example` for code that isn't really an example - requires many slow manual runs to determine the threshold - from a technical POV the `run_one` method takes a `Fn` closure, which means that we can't pass owned values without cloning - There is no off-the-shelf solution to store test results long-term to get a proper time series as the code base evolves (opened an issue [here](https://github.com/entropyxyz/devops-infrastructure/issues/131)) In short, it's competent academic-level quality code, and it works ok-ish for a single dev wanting to check if some code is or isn't CT, but is it a good solution for long-term CT assurance? If we adopt this we might end up frustrated enough to spend some time fixing its warts. ### What needs to be CT and what doesn't? This PR is nor here or there; it doesn't offer a complete view of the CT-ness of `synedrion` and in its current state it also doesn't contain a mechanism to set off an alarm if/when a piece of code that *must* be CT lands on `master`. I am not sure what we do with this. The results are interesting for sure, and does offer a useful tool to measure PRs like #213, but it's incomplete.
合并状态:未合并 2 条评论