Untrusted Deterministic Functions

[Fear]

While looking into exokernel design I saw that Xok uses (or used) untrusted deterministic functions to multiplex the hard drive when multiple file systems are provided through libOSes.

I understand that a deterministic function will return the same value provided the same input values. How do you determine if the function is deterministic if it is untrusted and how can it then be used to allow an untrusted (userspace) program safe access to protected information (such as a harddrive in the case of an exokernel)?

Thank you for your time.

[AndrewAPrice]

A simple way; pass your functions the same parameters over and over again. If it returns the same result the function is deterministic.

Example of a deterministic function; pow, sqrt, sin, cos, etc in math.h
Examples of non-deterministic functions; rand, getch.

Although you could say that rand and getch are deterministic, since rand will return the same output depending on the seed and the number of times it was called, so will getch if you consider the keyboard events as one of the inputs.

The rule I go by is that a function is deterministic if it is possible for the compiler (no matter how complex) to execute it at compile time and optimise:

Code: Select all

int a = FunctionThatTakes1000000YearsToCalculateTheUltimateAnswer();

into

Code: Select all

int a = 42;

[mystran]

A simple way; pass your functions the same parameters over and over again. If it returns the same result the function is deterministic.

Not so. Simple counter example:

Code: Select all

// truely_random_value() returns truely random values
int nondet(int x) {
   static int y = truely_random_value();
   if(x == y) return truely_random_value();
   else return x;
}

Unless you happen to pass the function the exact value that it as selected as todays random non-deterministic value, it'll appear deterministic, while it clearly is not.

Another counter-example:

Code: Select all

static bool isnondet = false;
int nondet(int x) {
  if(isnondet) return truely_random_value();
  else return x;
}
int hidden_trigger(bool t) {
  isnondet = t;
}

This one appears totally deterministic, until a hidden trigger is set to make it non-deterministic instead. Unless you isolate the function (which I'd imagine Xok does if what OP says makes sense in the first place), there is no way to test for such hidden triggers.

OTOH: if you fully isolate a function, and don't allow it to query any non-deterministic state, it has to be something (Turing..) computable, and hence essentially deterministic, even if it appears non-deterministic. Examples of such functions would be any PRNG not seeded by external random entropy.

[CodeCat]

Here's more on that...
http://en.wikipedia.org/wiki/Pure_function

In short, a pure function can't access anything but its own parameters. Nothing static or global. And it can't call any function that isn't also pure.

[mystran]

Here's more on that...
http://en.wikipedia.org/wiki/Pure_function

In short, a pure function can't access anything but its own parameters. Nothing static or global. And it can't call any function that isn't also pure.

Sure. But "pure function" is further restricted case of a deterministic function; in other words, a pure function is necessarily deterministic, but a deterministic function need not be pure. Deterministic would normally just mean there's nothing random about how the function works, but you can still have state while remaining deterministic. Such state makes the function "unpure" though.