4 ms·

In my almost 15 years in this community this is the first comment where I don’t have a fucking clue of what is described.

sureglymop 1y ago
When you write and compile code, there is a phase called "linking". For example, one could compile pieces of code and then link them together into one binary. A common challenge is decompiling and reverse engineering a compiled program, e.g. a game. The author realized that it's an interesting approach to do a sort of reverse-linking (or I guess unlinking) process of a program into pieces and then focusing on reverse engineering or reimplementing those pieces instead of the whole. When it comes to decompiling games, enthusiasts in that hobby want to be able to reproduce/obtain source code that compiles to exactly the same instructions as the original game. I think there is usually also a differentiation between instruction matching and byte for byte matching reproduction. But it definitely seems like a simpler and better approach to do this piece by piece and be able to test with each new piece of progress. That's my layman understanding of it having only dabbled in decompiling stuff.
- boricj 1y ago
  This is pretty much spot on. The key insight of delinking is that object files are relocatable and the process of linking them together (laying their sections in memory, computing all the symbol addresses, applying all the relocations) removes that property. But by reversing this process (creating a symbol table, unapplying the relocations/resynthesizing relocation tables, slicing new sections), code and data can be made relocatable again. Since properly delinked object files are relocatable, the linker can process them and stitch everything back together seamlessly, even if the pieces are moved around or no longer fit where they used to be (this makes for a particularly powerful form of binary patching, as constraints coming from the original program's memory map no longer apply). Alternatively, they can be fed to anything that can process object files, like a disassembler for example. Of course, the real fun begins when you start reusing delinked object files to make new programs. I like to say that it breaks down the linear flow of toolchain from compilation to assembly to linking into a big ball of wibbly-wobbly, bitsy wimey stuff. Especially if you start cross-delinking to a different platform than the original pieces of the program came from.
  - krackers 1y ago
    I think this finally answers a question I've had since I started learning programming. All my life I've been told "you can't convert a shared library to a static library". When you try to probe for more details, all you get is some mumbling about how a shared library is already prelinked for mapping into memory so the relocation table is lost. When you press further about the precise information loss that prevents you from reconstructing it, you get the equivalent of "you just can't ok!". That was never satisfying to me because recompilation (decompiling to source code or IR that can be recompiled for another platform) is an academic field of study [1], so the problem of converting a shared library to a static one should be easier. After all, you have all the assembly and symbol information right there, it seemed like all you needed to do was massage it the right way. [1] https://rev.ng/ https://rev.ng/
    - mjanx123 1y ago
      You flipped the static and shared. Shared objects are compiled in a way that the exact same code works when loaded at any address, which typically requires base+offset addressing and is less performant, but the same physical pages holding the object can be mapped into different processes at different addresses, ie shared. Static object addresses the code and and data directly and does not waste a register and requires the addresses in its code to be modified depending on where it is loaded, and the code cannot be shared between different processes. You can't convert a static library to shared because you can't. You can convert a shared library to static but there is no point.
      - krackers 1y ago
        I'm not sure I follow why 'I flipped them'. My understanding a shared library is closer to an executable than it is to an object file, so it is in that sense that it is "prelinked and ready to map into memory" just as an executable is. (Once loaded dyld still has to do fixups in the GOT, but that's not touching the text segment.) I mostly agree with your definitions, but you _can_ create a shared library out of a static library assuming the static library was compiled with fPIC, no? I mean I've never tried it but most linkers seem to allow it [1], and given that creating a full executable is similar to created a shared library, I don't see why it wouldn't work. And if the code wasn't compiled with fPIC, I still feel that it should be possible in theory since the whole point of object files is that they support relocation. Linking a non-PIC object to produce a shared object would just require patches within the text segment at runtime right? Modern linkers probably don't like doing this for security reasons. But otherwise seems isn't some fundamental limitation, just modern OSs and linkers not supporting an obscure use-case with security risk. When people say that you can't convert a shared library to a static one (or equivalently statically link against a shared library), they usually cite the lack of relocation table info as the reason. Like they have some hierarchy in mind that goes from source code -> object file -> executable/shared library, and so they say it's "obvious" that you can't go the other way. Which is mostly true in terms of the "golden path" and what you'd want to limit yourself to for production, but in a hacker sense you can obviously go the other way with assemblers and decompilers. So if someone claims that it's impossible to convert a shared library into a static library, there better be good justification for such a hard claim. And on the face of it, the claim doesn't seem watertight because the _stronger_ claim that you can't convert an executable back into recompilable code is falsified by the existence of decompilers that lower down to LLVM IR. [1] https://stackoverflow.com/questions/655163/convert-a-static-library-to-a-shared-library https://stackoverflow.com/questions/655163/convert-a-static-...
boricj 1y ago
This comment has made my day in ways words cannot express. But yeah, one recurring problem is that without literature on this esoteric and complex topic, any discussion remotely technical about it (especially without prior context) quickly bogs down, as it needs to be bootstrapped from first principles in order to make any sense. I've been meaning to write the Necronomicon of delinking to at least be able to point people to a document that contains everything they need to know in order to understand or at least decently grasp this. At the very least it should make for a good horror bed time story for linker developers.
chinchilla2020 1y ago
I've read some literature on this decompiling and reverse engineering work. It always blows my mind that there is a community of experts in it, toiling in science. Yet the academic and learning communities do not know anything about it. It's like an underground CS topic.

sureglymop 1y ago

When you write and compile code, there is a phase called "linking". For example, one could compile pieces of code and then link them together into one binary. A common challenge is decompiling and reverse engineering a compiled program, e.g. a game. The author realized that it's an interesting approach to do a sort of reverse-linking (or I guess unlinking) process of a program into pieces and then focusing on reverse engineering or reimplementing those pieces instead of the whole. When it comes to decompiling games, enthusiasts in that hobby want to be able to reproduce/obtain source code that compiles to exactly the same instructions as the original game. I think there is usually also a differentiation between instruction matching and byte for byte matching reproduction. But it definitely seems like a simpler and better approach to do this piece by piece and be able to test with each new piece of progress. That's my layman understanding of it having only dabbled in decompiling stuff.

boricj 1y ago
This is pretty much spot on. The key insight of delinking is that object files are relocatable and the process of linking them together (laying their sections in memory, computing all the symbol addresses, applying all the relocations) removes that property. But by reversing this process (creating a symbol table, unapplying the relocations/resynthesizing relocation tables, slicing new sections), code and data can be made relocatable again. Since properly delinked object files are relocatable, the linker can process them and stitch everything back together seamlessly, even if the pieces are moved around or no longer fit where they used to be (this makes for a particularly powerful form of binary patching, as constraints coming from the original program's memory map no longer apply). Alternatively, they can be fed to anything that can process object files, like a disassembler for example. Of course, the real fun begins when you start reusing delinked object files to make new programs. I like to say that it breaks down the linear flow of toolchain from compilation to assembly to linking into a big ball of wibbly-wobbly, bitsy wimey stuff. Especially if you start cross-delinking to a different platform than the original pieces of the program came from.
- krackers 1y ago
  I think this finally answers a question I've had since I started learning programming. All my life I've been told "you can't convert a shared library to a static library". When you try to probe for more details, all you get is some mumbling about how a shared library is already prelinked for mapping into memory so the relocation table is lost. When you press further about the precise information loss that prevents you from reconstructing it, you get the equivalent of "you just can't ok!". That was never satisfying to me because recompilation (decompiling to source code or IR that can be recompiled for another platform) is an academic field of study [1], so the problem of converting a shared library to a static one should be easier. After all, you have all the assembly and symbol information right there, it seemed like all you needed to do was massage it the right way. [1] https://rev.ng/ https://rev.ng/
  - mjanx123 1y ago
    You flipped the static and shared. Shared objects are compiled in a way that the exact same code works when loaded at any address, which typically requires base+offset addressing and is less performant, but the same physical pages holding the object can be mapped into different processes at different addresses, ie shared. Static object addresses the code and and data directly and does not waste a register and requires the addresses in its code to be modified depending on where it is loaded, and the code cannot be shared between different processes. You can't convert a static library to shared because you can't. You can convert a shared library to static but there is no point.
    - krackers 1y ago
      I'm not sure I follow why 'I flipped them'. My understanding a shared library is closer to an executable than it is to an object file, so it is in that sense that it is "prelinked and ready to map into memory" just as an executable is. (Once loaded dyld still has to do fixups in the GOT, but that's not touching the text segment.) I mostly agree with your definitions, but you _can_ create a shared library out of a static library assuming the static library was compiled with fPIC, no? I mean I've never tried it but most linkers seem to allow it [1], and given that creating a full executable is similar to created a shared library, I don't see why it wouldn't work. And if the code wasn't compiled with fPIC, I still feel that it should be possible in theory since the whole point of object files is that they support relocation. Linking a non-PIC object to produce a shared object would just require patches within the text segment at runtime right? Modern linkers probably don't like doing this for security reasons. But otherwise seems isn't some fundamental limitation, just modern OSs and linkers not supporting an obscure use-case with security risk. When people say that you can't convert a shared library to a static one (or equivalently statically link against a shared library), they usually cite the lack of relocation table info as the reason. Like they have some hierarchy in mind that goes from source code -> object file -> executable/shared library, and so they say it's "obvious" that you can't go the other way. Which is mostly true in terms of the "golden path" and what you'd want to limit yourself to for production, but in a hacker sense you can obviously go the other way with assemblers and decompilers. So if someone claims that it's impossible to convert a shared library into a static library, there better be good justification for such a hard claim. And on the face of it, the claim doesn't seem watertight because the _stronger_ claim that you can't convert an executable back into recompilable code is falsified by the existence of decompilers that lower down to LLVM IR. [1] https://stackoverflow.com/questions/655163/convert-a-static-library-to-a-shared-library https://stackoverflow.com/questions/655163/convert-a-static-...

boricj 1y ago

This comment has made my day in ways words cannot express. But yeah, one recurring problem is that without literature on this esoteric and complex topic, any discussion remotely technical about it (especially without prior context) quickly bogs down, as it needs to be bootstrapped from first principles in order to make any sense. I've been meaning to write the Necronomicon of delinking to at least be able to point people to a document that contains everything they need to know in order to understand or at least decently grasp this. At the very least it should make for a good horror bed time story for linker developers.

chinchilla2020 1y ago

I've read some literature on this decompiling and reverse engineering work. It always blows my mind that there is a community of experts in it, toiling in science. Yet the academic and learning communities do not know anything about it. It's like an underground CS topic.