Improved Struct Recovery Algorithms

[ReversingWithMe]

I've looked at a couple of the Ghidra extensions/scripts for struct recovery, some of which get into inter-procedural, and some get into type hints across instruction mnemonics.

• https://github.com/grimm-co/GEARSHIFT : Over-eagerly blows away primitive types with alias structs, may benefit from extra wrapper code to only apply struct inference if undefined or pointer type
  • https://web.archive.org/web/20221222174033/https://blog.grimm-co.com/2020/11/automated-struct-identification-with.html
  • gearshift script has updated API for commit params with None for missing arg
• https://github.com/trailofbits/BTIGhidra : Trail of bits implementation of Retypd algorithm from grammatech, requires parameter ID, errors for me on real programs and in some of my limited testing on toy programs solid hints within functions, if my memory is correct on toy programs also over-eargerly replaces primitive types with aliases (Will need to re-run to verify)

I'm curious if anyone has looked at the DLA, Data Layout Algorithm from the folks doing revng. (https://github.com/revng/revng/tree/develop/lib/DataLayoutAnalysis)

• This is running revng parsing the project file for structs only in return type and params that contain struct definitions only, anything else is skipped.

From limited testing parsing the results, it's able to recover some structs, and the hard struct recovery problems will still kill the algorithm. (A struct containing a struct, struct vs arrays, aliasing around the first index in a struct)

In those screenshots, was just seeing how I would expect it to perform, I did update the function signature and try the auto-struct identification from the context menu, which failed for me also. I am not certain there is anything that could be adapted from that code as there is a whole other analysis stack in that tooling, which could devolve into gearshift or btighidra techniques. There is no paper reference for that algorithm also.

I have not done extensive studies either into symbol vs stripped running that inference code to see how often its accurate vs Ghidra, and how easily stubs of structs could just be added to type manager to see if that helps clean up decompilation either.

I havn't seen any of these tools that natively handle local variables, outside of propagation of types.

Most of my testing is against gcc coreutils binaries, outside of toy example problems, from the function detection test cases from github.

[anzosasuke]

@ReversingWithMe I just came across this post. Did you find anything else? I am looking into array bounds and type detection. Will be helpful to know what you find.