the deobfuscation conjecture

posted on 2021-12-05

suppose i write a program that tries to find counterexamples to fermat's last theom: that is, numbers a>1, b>1, c>1, n>2 such that aⁿ+bⁿ=cⁿ.

suppose i now explain to you this program; you will probably shortly understand what it is doing.

now, suppose i compile it, and run its compiled code through an obfuscation algorithm such as movfuscator; with the strict requirement that the output program has the same I/O and time complexity as the input program (i believe this is the case for movfuscator).

can you, manually or with the help of a deobfuscator or even in a fully automated manner, now figure out that the program is trying to find counterexamples to fermat's last theorem?

with infinite time, surely; the conjecture that i posit here (well, that i posited, see below) is that you can do so in an amount of time that is at most linear in the amount of time it would have taken you to understand the original program.

in general, the deobfuscation conjecture says this: for any code obfuscation program that conserves I/O and time complexity, and for any reasonable notion of "understanding" what a program does that is conserved by obfuscation (such as "does this program halt" or "will this program find a counterexample to fermat's last theroem if there is one"), there exists a deobfuscation program that determines that criteria for the obfuscated program in the same time complexity (as a function of the program size) as the fastest program that determines that criteria for the unobfuscated program.

or, put another way: as long as I/O and time complexity are conserved, transforming a program does not change the time complexity in which can be tested other criteria of the program, or in which it can be reduced.

as evidence for this conjecture, i'll point to the ability of video game crackers to pretty systematically overcome software DRM, to extract the behavior of the program they care about.

a corollary to this conjecture is that shipping a program together with "hints" about what it does cannot help to understand it by more than a constant factor.

a proof that it's false

while writing this post and talking about the conjucture with a friend, they helped me figure out a proof that it must be false.

consider:

the program is a program that will sort a hardcoded list and output the result
the criteria is "what will the program output ?"
the hint being shipped with the program is a list of what position each item in the original list will occupy in the final sorted list

with the hint, the criteria can be determined in O(n): checking that the hint is indeed a correct sorting of the list is O(n), and so is checking that the program is indeed the sorting algorithm (for this proof we can just hardcode recognizing one specific sorting algorithm; the space of this proof is merely the set of hardcoded lists, while the sorting algorithm is constant).

without the hint, however, the criteria can only be determined in O(n × log(n)): after one has figured out that the program is a sorting algorithm, one has to actually sort the list to figure out what the program will output, which is known to take at least O(n × log(n)).

and so, the hint helps by more than a constant factor, and there can indeed be information shipped alongside a program that can help determine criteria about it; and thus, obfuscation can indeed make a program harder to understand by more than a constant factor.

posted on 2021-12-05