0

I am working on creating oblivious graph algorithms, which basically hides the memory access pattern of an algorithm. The memory is assumed to be encrypted, but can be monitored by an attacker. The processor is assumed to be in the cloud, be secure, and have its own cache.

It is known that the access pattern of a graph could reveal information about that graph.

In order to make an algorithm oblivious, it is necessary to add dummy work to the algorithm. Such work includes reading and writing data, but in such a way as to not cause the results of the algorithm to be changed (such changes would make the algorithm useless, of course).

It is necessary that the dummy work be on the graph itself, otherwise the attacker would be able to trace which work is real and which work is fake.

Of course, adding dummy work creates slowdowns. Thus, as a lean solution, I would like to assign a variable to itself. This would create a read and a write to a location without actually changing anything. My question is, do compilers actually execute this code (it seems to in gdb, but is that just because it is a debugger)? I'm using gcc, but it would be best if the algorithm could be compiled with different compilers and still remain oblivious.

The alternative to setting a variable equal to itself would be to use an if statement: check if the variable equals some value, and then set the variable to that value inside the if statement. If possible, I would like to avoid if statements because they slow things down.

Lastly, this algorithm is multithreaded. If a global variable is set equal to itself, is it necessary to put a mutex lock on it? Such locks will of course slow things down, so I would like to avoid them if possible.

Alpha Bravo
  • 170
  • 12
  • 7
    The "as if" rule means that compilers can optimize out anything they can prove will have no visible effect (within the scope of the language). This includes self-assignment, or assigning a value to a variable that the compiler can prove already has that value. You have to use volatiles or maybe atomics. – Raymond Chen Jun 16 '16 at 16:23
  • You can definitively check whether a compiler does given several optimization levels by checking the assembly. – chris Jun 16 '16 at 16:24
  • I'm pretty sure that declaring the variable `volatile` should prevent optimizing out assignments, even self-assignments. – Barmar Jun 16 '16 at 16:24
  • It's unclear to me why the attacker won't see that you're reading an address and writing it back.. – lorro Jun 16 '16 at 16:26
  • Thanks, I will try volatile. The attacker will see that we are reading from an address, but it will not know that we are writing back the same value to that address. – Alpha Bravo Jun 16 '16 at 16:29
  • If an attacker has direct access to your machine's physical memory, then you can't stop them - at some point, the machine has to decrypt in order to run the algorithm itself and operate on the data, and would be much easier than monitoring changes (especially across billions of bytes!). Also, layers of onboard cache may choose to ignore writes that do not update, and unless you can specify your exact hardware with yoru cloud provider, you won't know. But, since you want to force a write, I suggest actually modifying the data in a random but reversible way, such as using the ^ (XOR) operator. – Matt Jordan Jun 16 '16 at 16:32
  • All data within the memory is assumed to be encrypted, while all data at the CPU/ cache level is decrypted (or is encrypted/decrypted on the cache). The CPU/ cache is assumed to be secure. Thus, the attacker cannot see the data itself or anything in the CPU, but can see the access patterns in memory. Also see oblivious RAM. As for if the data is actually updated in cache or in memory, that is a question that we have not considered yet. I will ask my research adviser on how we can ensure that data is actually written back to memory and not the cache without slowing everything down. – Alpha Bravo Jun 16 '16 at 16:41
  • Data in memory is encrypted, but still visible to the attacker? If so, he can still see that a particular read/write to a memory location always writes back the same value that was read. He might not know what that value means, but he does see that it's a meaningless read/write. – Jim Mischel Jun 16 '16 at 17:33
  • The attacker cannot see the values being read nor written. The attacker can only see the addresses being accessed and if a read/write is happening at that location. Thus, the attacker does not know if the values are the same or not (the cipher text should change). – Alpha Bravo Jun 16 '16 at 18:18

1 Answers1

0

The compiler optimizer would likely remove that statement altogether at compiler time so no it would likely not execute. Debugging usually doesn't use optimized code because you step through each statement so it would execute there. If you want you can turn off compiler optimization and then do your tests. The flag for gcc is -O0

How to disable compiler optimizations in gcc?

Edit: About your multithreaded question, depends. If the only access to the variable is self assignment then no because interleaved execution wouldn't change the value of the variable no matter how many threads are running. However if at least one thread is mutating the variable in some other way, then you would have to use locks.

Community
  • 1
  • 1
Garrigan Stafford
  • 1,331
  • 9
  • 20
  • Thank. I discovered in the comments that since the cipher text won't change, there's no point in doing self assignment, even though the access pattern would be oblivious. Couldn't see the forest for the trees. – Alpha Bravo Jun 16 '16 at 18:56