The "analogue hole" is the wrong metaphor here

Posted Aug 2, 2013 8:18 UTC (Fri) by and (guest, #2883)
In reply to: The "analogue hole" is the wrong metaphor here by tialaramex
Parent article: Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software (UCLA)

> If you doubt that this could ever be tricky, take a moment to examine the remaining candidate 6 state binary Busy Beavers.

There are undecidable problems, sure. But reverse engineering prevention techniques are different, because the code which is to be executed *is* decidable (or it does seriously wrong) and in the end the CPU just follows it instruction by instruction. You may make the paths which go from input to output (much) more convoluted, but in the end you always need to go from A to B if the obfuscated code still claims to be correct. So if you know A, and B and you can follow the path from A to B, why should it be impossible to understand the path given enough determination?

The "analogue hole" is the wrong metaphor here

Posted Aug 2, 2013 10:22 UTC (Fri) by tialaramex (subscriber, #21167) [Link]

Sure, that sounds reasonable doesn't it. Let's just simulate all the A->B transitions, keeping track of each one, and then stare at it really hard and we'll achieve enlightenment. First of all, we begin with more values of A than there are particles in the observable universe, and then we ... oh dear, this is starting to sound as though we're going to need to buy more RAM. More RAM than has ever existed or could ever exist. Oops.

The reason I selected the Busy Beavers is _not_ per se because S and Σ are non-computable functions, but because our actual experience when we try to analyse this stuff (arbitrary machines/ programs which we stumble upon when examining the exhaustive set) is so different from analysing programs which are the result of human engineering. It's like the discovery that /almost all/ real numbers are irrational. The numbers we tend to think about are all nicely rational, like five, nine seventeenths, 65536. We can so easily convince ourselves that the irrational numbers are rare exceptions to be mostly ignored. But in fact they're the overwhelming majority of all reals, our intuition about "numbers" is just wrong and our intuition about understanding programs is wrong too.

Some of the simple six state machines whose behaviour /is/ understood after a great deal of research effort are _fiendish_ and they're far smaller than any program that someone's going to want to protect with obfuscation. Try something easy to start, what's going on here?

A: B1R B0L
B: C1L E0R
C: E1R D0L
D: A1L A1L
E: A0R F0R
F: E1R Z1R

The "analogue hole" is the wrong metaphor here

Posted Aug 2, 2013 13:19 UTC (Fri) by ballombe (subscriber, #9523) [Link]

> because the code which is to be executed *is* decidable (or it does seriously wrong)

You are abusing the word decidable in a way that make your statement meaningless.

(I do agree that the article is misleading)