4 ms·

Some transformations irrecoverably lose information. A recontextualization engine such as an LLM might be able to "recover" some information by comparing it to

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.

Kye 2y ago
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.
- soulofmischief 2y ago
  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.
Retr0id 2y ago
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.
- soulofmischief 2y ago
  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.
  - Asraelite 2y ago
    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.
    - soulofmischief 2y ago
      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.
      - Asraelite 2y ago
        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.
        soulofmischief 2y ago
        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!
  - willy_k 2y ago
    > 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.
brookst 2y ago
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.
- soulofmischief 2y ago
  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.
  - smallmancontrov 2y ago
    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.
    - soulofmischief 2y ago
      > 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.
gchamonlive 2y ago
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.

Kye 2y ago

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.

soulofmischief 2y ago
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.

Retr0id 2y ago

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.

soulofmischief 2y ago
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.
- Asraelite 2y ago
  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.
  - soulofmischief 2y ago
    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.
    - Asraelite 2y ago
      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.
      - soulofmischief 2y ago
        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!
- willy_k 2y ago
  > 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.

brookst 2y ago

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.

soulofmischief 2y ago
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.
- smallmancontrov 2y ago
  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.
  - soulofmischief 2y ago
    > 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.

gchamonlive 2y ago

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.