Hacker News Reader

Comment by haolez | Hacker News Reader

But it should be easy to generate such data to train an AI to do that, if someone wants, no?

Some transformations irrecoverably lose information. A recontextualization engine such as an LLM might be able to "recover" some information by comparing it to other code in its training set, but it's still a guess and not all code will have representation in the training set.

This is exactly what skilled human reverse engineers do. Almost no code is truly novel, at best it's a novel recombination of existing ideas. So yes, some information is lost, but all information relevant to the execution of the program can certainly be recovered.

That's simply untrue, since you don't know if I named a minified variable "x" as "foo", "bar", "mungus" or "chungus". You can guess that it might be mungus based on context, but it could very well be chungus. Recovering lost information is an example of extrapolation, and it is inherently probabilistic.

> all information relevant to the execution of the program can certainly be recovered.

This is moving goalposts as it has little to do with my original premise.

It doesn't really matter if it needs to extrapolate. Whether or not you called the variable "mungus", a sufficiently powerful LLM could infer that this is the best possible name for that variable to make it understandable for humans. Doing this across the entire codebase, it could create source code that is actually more readable than the original.

Of course we're a long way off from this, but there's no reason it couldn't be done in theory.

Please just look at my other comments because I find myself repeating myself over and over, my comment went past a lot of people's heads and they rushed towards defensiveness instead of understanding the simple, unarguable fact of life I laid out in my comment.

Sorry, I didn't mean to come across as disagreeing with you, I just wanted to point out what I thought was an interesting fact. Yes, the original source code is unrecoverable.

I tend to be username-blind and thought you were the person my comment replied to. Reading your comment on its own, I have no issue with it and I apologize for mistaking you for them!

> This is moving goalposts as it has little to do with my original premise.

Your original comment was (replying to one) about “decompilation” of binaries. You seem to be talking about some fantasy perfect decompilation that gets variable names too, but no such decompilation tool or human-employable method does this, and I would argue that variable names aren’t information so much as they’re implicit context - proper code implies certain variable names (stylistic differences notwithstanding) and vice versa.

My original comment, in full text:

> Some transformations irrecoverably lose information. A recontextualization engine such as an LLM might be able to "recover" some information by comparing it to other code in its training set, but it's still a guess and not all code will have representation in the training set.

It is a completely generalized statement about lossy transformations, aka transformations that aren't reversible with a 1 to 1 map. It says nothing in particular about decompilation, or getting variable names.

> I would argue that variable names aren’t information so much as they’re implicit context

You are free to argue what you want, but that doesn't change reality--variable names are information about the original state before it was irreversibly transformed. Is the information important to you and your current task? Who knows. But my original comment is absolutely correct.

None of that matters. Nobody cares if a variable is named "mungus" or "chungus", as long as the code is idiomatic and functions equivalently.

1:1 Source recovery is never the goal of decompilation, or reverse engineering in general. You just want functionally equivalent, idiomatic code.

Do you understand what information is and why my original comment about lossy transformations is entirely correct? It doesn't matter if you don't care about the information. It is still lost.

> 1:1 Source recovery is never the goal of decompilation

I am aware, but I appreciate the lesson. Now try to consider why that has no bearing on the points I've made.

The points you've made are "correct" but irrelevant.

Irrelevant to whom? Did I miss the meeting?

LLMs can synthesize info not in the training set. They should be just as capable of looking at a binary where info has been lost and recreating source just like a human would. Stuff like variable names won’t be exact (for either human or LLM) but can be reasonable inferences based on usage.

It’s a guess, sure, but I don’t see why it would be a less good guess than a human’s.

I agree, I am aware that LLMs can synthesize data, I am a huge advocate of them for this purpose and use them daily for such. This is where I derive the authority in making such a statement about them. I never made any statement relating the performance of LLMs to humans.

> Stuff like variable names won’t be exact

Yes, this is the point of my comment around information loss. Lossy transformations inherently cannot be recovered with absolute certainty, and the degree of certainty depends on available context.

This is true for absolutely any system which produces lossy transformations, not just in the context of code and LLMs, but encoders, etc.

Sure, but the ability to synthesize data challenges the implicit assumption that all reconstruction error is bad. Who is to say the LLM won't come up with better variable names than the original source? It probably won't, but I could see it often hitting roughly equal quality. The reconstruction error metric would complain but a human would not, so the problem is now with reconstruction error as a metric.

> Who is to say the LLM won't come up with better variable names than the original source?

This is still a loss of information. You're completely misunderstanding the point: Minification is an irreversible process unless you happen to have exactly the context you need, and can verify the provenance of the source in question. Coming up with "better" variable names is not recovering information, it's extrapolating information about the old state to the point of error.

Sure, but for the purposes of decompilation, does it matter if a variable name is exact versus merely being a good description of its function? The issue isn’t an idealized “let’s get the source including meaningless whitespace”, it’s “let’s construct source that can be used interchangeably with the original”.

For that purpose there is no reason LLMs can’t be as good as the best humans.

No, it doesn't matter, and as I explained above, I never mentioned humans once in my comment, nor did I make any comparisons. I simply described a mathematical fact that a lot of people are having trouble understanding and digesting.

I do appreciate your comment as it's not defensive, it's made in earnest, so please don't take my above statement to be a reflection of you in particular.

> “let’s construct source that can be used interchangeably with the original”.

You lose a lot more than whitespace, you lose semantics, metadata, and lots of other information that makes it so

Obviously byte coded languages are a bit easier, and you may get lucky and experts help a lot, and perhaps LLMS can help a little.

Both Rice's theorem and the system identification problem from the cybernetics days relate to why it is so hard.

> Given a system in the form of a black box (BB) allowing finite input-output interactions, deduce a complete specification of the system’s machine table (i.e., algorithm or internal dynamics).

AND

> Given a complete specification of a machine table (i.e., algorithm or internal dynamics), recognize any BB having that description.

Decompilation doesn't give you the equivalent of the original source code, it gives you new source code that appears to be functionally similar to it, and many people who has been forced to use decompilation to recover from lost source code or consultant time-bombs have run into the problems that admittently seem pretty counter intuitive.

Remember that Rice-Shapiro and Kreisel-Lacombe-Shoenfield-Tseitin extend Rice to partial and total functions in finite time.

Telling if a program is equivalent to a fixed other program, even for total functions is still undecidable as they are 'non-trivial' properties.

Most of the time you can make it work, but it isn't a case of:

> “let’s construct source that can be used interchangeably with the original”

I wonder if this would be an ideal use case for diffusion-based LLMs slowly piecing it together with each pass from what it could determine from the last.

I've experimented with building diffusion-based LLMs but didn't scale them up enough to draw any worthwhile conclusions about their strength vs transformer-based LLMs. In this case however, theoretical ability to unminify a piece of code mainly comes down to the training set and amount of relevant context baked into the system, not the model architecture itself.

With information loss what you previously had as a single solution becomes a generalisation which can be decompiled into many different equally valid solutions.

That means even though information is irrecoverably transformed during compilation, LLM could come up with semantically valid expanded solution that both fits the compiled information, that is it can be recompiled successfully, and makes sense semantically for whoever would eventually want to evolve the decompiled code with an understanding of the domain.

So the goal isn't to recover exactly what code really was, but to provide a possible solution that fits and is useful.

Replace the word easy there with the phrase "technically may be possible with great effort and expense, probably"

Decent optimizing compiler would necessarily loose a fair bit of source information - loop unrolling, function inlining, tail-call optimizations, etc...

There is no good way to reconstruct that, AI/ML or not.

For loop unrolling at least, wouldn’t most human reverse engineers see the original loop? It’s far more likely that the source had a loop than that some high level language programmer did the unrolling in source.

Reply on news.ycombinator.com