Odd question

[nancylebov]

Would quantum computing alone be able to get source code out of binary, or would it take really advanced AI as well? Really advanced means substantially smarter than human, not just really good at passing Turing tests.

Comments

[sturgeonslawyer.livejournal.com]

I think the problem is at some level intractable - you can get SOME source code out of any binary by mechanical means, but to get back to something resembling what a human might have been written is problematic, because for any nontrivial binary there will be multiple possible "source codes" that could have produced it, even setting aside trivialities like the names of variables and subroutines, etc. This is even more so if the binary was produced by a compiler that does any kind of optimization at all.

[mneme]

We can get usable source code out of binaries now. It may not be the original code, but depending on the optimization, it can get pretty good (more optimization means less readable code. Java generally decompiles extremely well unless it's been run through an obfusicator).

Getting -the- original code is, of course, impossible.

Bridging the gap -- getting good code out of random working assembler, is probably intractable for perfect, but approachable in the general case without qc or ai.

[nancylebov.livejournal.com]

I'd assumed that the reason Microsoft was able to keep the workings of its programs secret was that there was nothing to be deduced from binary.

[darius.livejournal.com]

There was a book back in the 80s, Undocumented Windows, that was basically one person analyzing Microsoft's binaries and sharing the good parts of what he figured out. I haven't read it, but it's said the good parts were proof of anticompetitive business practices rather than any fancy special algorithms.

Decompiling well does seem to need human talent at the moment. I hooked up a friend recently with a job doing that -- they'd had a third-world team working on it before but not getting anywhere, while my friend finished it in a month or two. OTOH teenagers used to do it a lot to crack copy protection.

[bruhinb.livejournal.com]

I agree with both answers, so far.

I'm trying to figure out where quantum computing fits into the question, though.

[nancylebov.livejournal.com]

I mistakenly(?) thought it would take so much computing power that nothing less than quantum computing would be capable enough.