3 ms·
I've been designing a programming language where nothing is a side-effect – including calling conventions, processor caches, branch predictors, locks, graphics
by wizzwizz4 6y ago
I've been designing a programming language where nothing is a side-effect – including calling conventions, processor caches, branch predictors, locks, graphics modes, etc.. “Runtime has to be independent of the value of the input” would be how that language expresses "constant time" – and it would take into account every part of the compiler's model of the target architecture (which, by the way, is also described in the code) so for a sufficiently-simple, sufficiently-well-modelled architecture, the generated code could be provably Spectre-proof – given sufficient assumptions (Eis's take on Rust's `unsafe`).
It's very early days, but I hope to get something usable by 2025.
- pjc50 6y ago> processor caches, branch predictors You can't "take this into account" because it requires state that isn't visible to you and also requires you to know the design of future hardware!
- wizzwizz4 6y agoIt requires state that can be inferred and manipulated. For the cache, assuming you know how large the cache is, you can just fill up the cache with useless pages, evicting whatever might be vulnerable to a timing attack, before having it loaded back in. Very slow, but it works. (You might be able to get away with less, depending on the OS's guarantees and what you can assume about how your program will run – and the language requires you to make those assumptions explicit, even if it's a case of "assume this manually-written assembly does the right thing without violating any invariants".) Yes, these tricks don't have forwards-compatible guarantees in the general case – but if the processor manufacturer makes guarantees about all members of a family, then you can optimise to those, and in any case having something that provably works in all supported processors (and can be ported to later processors if necessary, just by using an extra library (if the library is correct)) is still useful.
- sherbert-santa 6y agoNo. You cannot infer the layout of the cache based on size alone. You don’t know how many ways there are, how many sets their are etc. you don’t even know their LRU scheme. For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache. You could maybe restrict your target to open source hardware and come up with something.
- sherbert-santa 6y agoSelf modifying *code
- wizzwizz4 6y ago> You cannot infer the layout of the cache based on size alone. No – but the compiler would presumably be told how the specific processor's cache works. If it's possible for a human to write cache-flushing code, it's possible to describe it to a computer. (And that was just an example.) > For mutating branch predictor state at will, you will need your compiler to write self modifying code. Only for arbitrary modifications. For specific modifications, it's fine to go with ordinary code – though self-modifying code isn't actually all that hard to model, if you generalise “state” to also encompass the state of the self-modifying section. (Compilers already have “all branches” type things.) > You could maybe restrict your target to open source hardware There's no need to make this restriction. You only need sufficiently-understood hardware; you underestimate the ability of reverse-engineers.
- sherbert-santa 6y agoHow exactly would you modify branch predictor state without self modifying code? I am very interested in this. Another major question: a lot of x86 ops for manipulating things you want to manipulate are ring 0 instructions. We haven’t even discussed the effect of somewhat non deterministic delays caused by contention from other processes. This can change the true execution order of instruction inside the pipes, even if you somehow manage to enforce in order issue.
- atty 6y agoUnless I’m misunderstanding your point, I don’t think what you want is possible, due to microcode. You give the AMD/Intel/Arm/etc platform some instructions to execute, and then they execute it in ways that are not guaranteed to stay the same, between microcode updates and between hardware revisions. The only guarantee is that the results you get should be the same as if the instructions you requested were executed in the order you requested them.
- wizzwizz4 6y agoThe sophisticated version is difficult, but there are a lot of things you can treat as "opaque, everything mutates this, lots of stuff depends on it" and still be able to make decent optimisations based on what you know.