3 ms·
Determinism is related to purity ("functional programming"), but is a weaker notion. For example, this function var c = 0 function deterministic_not_p
by voidmain 8y ago
Determinism is related to purity ("functional programming"), but is a weaker notion. For example, this function
var c = 0
function deterministic_not_pure() {
return c++
}
is not pure, and you can't reason over it equationally. But it is deterministic: if I make a series of calls to this function in my browser, and you make the same series of calls in your browser, and someone else emulates the code using a Turing machine made of rocks in the desert [1] we will all see the same results. (And consequently, there is nothing that such code can do to learn about its environment!)
As far as I know everything in Javascript-the-language has this property! [2] (Equally, so does WebAssembly). And most of the browser's APIs do as well, though the sheer size of that surface means that any attempt to fix the rare cracks will still be daunting. The vast majority of information that browser JS gets is either through events (i.e. function arguments) and I think most of the rest could be safely forced to be deterministic during the execution of a JS function.
It's still obviously possible for these events to leak timing information about the execution of JS, but I think that can be fought. For example, you could delay the delivery of every event by the number of nanoseconds that JS has executed on the page so far, though of course that naive approach will gradually degrade in performance. But I think for example doing that until you have 10ms of delay and then resetting would probably make timing attacks totally impractical.
All of this needs way more thought, and I'm not at all suggesting that it's easy. But browser JS is closer to an actually-securable-against-side-channels state than almost any other widely deployed platform, and I think it's sad for the people that control the platform (which is, let's face it, basically the Chrome team) to throw it away because they love performance.now() and SharedArrayBuffer.
[1] https://xkcd.com/505/ https://xkcd.com/505/
[2] Well, ECMAScript probably doesn't specify a random number generator, for example. But it could.
- lioeters 8y agoThank you, I was hoping to learn something by posting a comment, and was richly rewarded by your reply. Hadn't seen the "computer of rocks", brilliant. Yes, I'm starting to see the difference between pure and deterministic. It seems like the latter is a description of a particular type of predictable/repeatable "program flow". I found a related Wikipedia topic [1], "What makes algorithms non-deterministic?" Quote: - If it uses external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data. - If it operates in a way that is timing-sensitive, for example if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result. - If a hardware error causes its state to change in an unexpected way. Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most programming languages and especially functional programming languages make an effort to prevent the above events from happening except under controlled conditions. The prevalence of multi-core processors has resulted in a surge of interest in determinism in parallel programming. --- The above includes a number of topics you raised, about events and timing information, and the possibility of making a language deterministic with some exceptions "under controlled conditions". This part feels relevant too: "easier for humans as well as other programs to reason about". [1] https://en.wikipedia.org/wiki/Deterministic_algorithm#What_makes_algorithms_non-deterministic https://en.wikipedia.org/wiki/Deterministic_algorithm#What_m...?