More Expressive C-like Intermediate Language then the ClangToken Trees

[fmagin]

I have been tinkering with a plugin to rewrite the decompiler output similar to https://github.com/patois/abyss
One of the main downsides with this is that the Ghidra only really has three intermediate representations:

• the lifted P-Code (seen in the disassembly view when activating P-Code)
• the "high-level" P-Code (seen e.g. in Graph AST Control Flow Action)
• the ClangToken tree returned by the decompiler only used for GUI integration of the decompiler output

e.g. the decompiled code:

HAL_StatusTypeDef HAL_Init(void)

{
  HAL_NVIC_SetPriorityGrouping(3);
  HAL_InitTick(0xf);
  HAL_MspInit();
  return HAL_OK;
}

has the ClangToken tree:

usually this tree even contains the whitespace tokens, my graphing code removes those for clarity already though.

The corresponding "high-level" P-Code via the Graph AST Control Flow action is

and as the string representations:

 ---  CALL (ram, 0x80010d4, 8) , (const, 0x3, 4)
 ---  CALL (ram, 0x80007fc, 8) , (const, 0xf, 4)
 ---  CALL (ram, 0x80004f0, 8)
(register, 0x20, 1) COPY (const, 0x0, 1)
 ---  RETURN (const, 0x0, 4) , (register, 0x20, 1)

the lifted P-Code is:

                             **************************************************************
                             *                                                            *
                             *  FUNCTION                                                  *
                             **************************************************************
                             HAL_StatusTypeDef __stdcall HAL_Init(void)
                               assume LRset = 0x0
                               assume TMode = 0x1
             HAL_StatusType    r0:1           <RETURN>
                             HAL_Init                                        XREF[3]:     Entry Point(*), main:0800046e(c), 
                                                                                          .debug_frame::000003d4(*)  
        08000848 08 b5           push                      { r3, lr }
                                                      mult_addr = COPY sp
                                                      mult_addr = INT_SUB mult_addr, 4:4
                                                      STORE ram(mult_addr), lr
                                                      mult_addr = INT_SUB mult_addr, 4:4
                                                      STORE ram(mult_addr), r3
                                                      sp = COPY mult_addr
        0800084a 03 20           movs                      r0,#0x3
                                                      r0 = COPY 3:4
                                                      tmpNG = INT_SLESS r0, 0:4
                                                      tmpZR = INT_EQUAL r0, 0:4
                                                      ZR = COPY tmpZR
                                                      NG = COPY tmpNG
        0800084c 00 f0 42 fc     bl                        HAL_NVIC_SetPriorityGrouping                     void HAL_NVIC_SetPriorityGroupin
                                                      lr = INT_OR 0x8000850:4, 1:4
                                                      ISAModeSwitch = COPY 1:1
                                                      TB = COPY ISAModeSwitch
                                                      CALL *[ram]0x80010d4:4
        08000850 0f 20           movs                      r0,#0xf
                                                      r0 = COPY 15:4
                                                      tmpNG = INT_SLESS r0, 0:4
                                                      tmpZR = INT_EQUAL r0, 0:4
                                                      ZR = COPY tmpZR
                                                      NG = COPY tmpNG
        08000852 ff f7 d3 ff     bl                        HAL_InitTick                                     HAL_StatusTypeDef HAL_InitTick(u
                                                      lr = INT_OR 0x8000856:4, 1:4
                                                      ISAModeSwitch = COPY 1:1
                                                      TB = COPY ISAModeSwitch
                                                      CALL *[ram]0x80007fc:4
        08000856 ff f7 4b fe     bl                        HAL_MspInit                                      void HAL_MspInit(void)
                                                      lr = INT_OR 0x800085a:4, 1:4
                                                      ISAModeSwitch = COPY 1:1
                                                      TB = COPY ISAModeSwitch
                                                      CALL *[ram]0x80004f0:4
        0800085a 00 20           movs                      r0,#0x0
                                                      r0 = COPY 0:4
                                                      tmpNG = INT_SLESS r0, 0:4
                                                      tmpZR = INT_EQUAL r0, 0:4
                                                      ZR = COPY tmpZR
                                                      NG = COPY tmpNG
        0800085c 08 bd           pop                       { r3, pc }
                                                      mult_addr = COPY sp
                                                      r3 = LOAD ram(mult_addr)
                                                      mult_addr = INT_ADD mult_addr, 4:4
                                                      pc = LOAD ram(mult_addr)
                                                      mult_addr = INT_ADD mult_addr, 4:4
                                                      sp = COPY mult_addr
                                                      $U0:4 = INT_AND pc, 1:4
                                                      ISAModeSwitch = INT_NOTEQUAL $U0:4, 0:4
                                                      TB = COPY ISAModeSwitch
                                                      pc = INT_AND pc, 0xfffffffe:4
                                                      RETURN pc

The problem is that the ClangToken tree is not really suitable for any kind of further analysis, but also contains significantly more information than the high level P-Code. For example the C Statement HVar1 = HAL_OK where HVar1 is defined as the type HAL_StatusTypeDef earlier
is a ClangStatement of 3 children: ClangVariableToken, ClangOpToken, ClangVariableToken. The only way to know that this is an assignment is to check the text of the ClangOpToken. The information that this is an assignment isn't present in the type of the ClangTokenGroup itself. In theory I could also check the underlying pcodeOp, but at that point I am basically starting to invent my own Intermediate Representation on top of a mix of the ClangToken tree and high level P-Code.

The high level P-Code isn't suitable on it's own, because for this statement it is simply (register, 0x20, 1) COPY (const, 0x0, 1) which has no information about the HighVariable hVar1 that is written to, and the enum that gives the meaningful name HAL_OK instead of the constant 1.

So my underlying question here is: Are there any plans for a new Intermediate Representation? How many other people in the community ran into this limitation? I know at least one person who tried implementing some vulnerability scanning tool on top of Ghidra and gave up because the provided abstractions were unsuitable compared to e.g. the Binary Ninja Intermediate Representations.
I have been tinkering with a plugin for dynamic rewrite rules on the JVM side and most interesting rules are hindered by the fact that I basically need to reinvent a C-Parser.

One possibility might be to extend the underlying decompiler to emit an XML tree that has more information. The decompiler obviously knows that it is producing e.g. an assignment or an if {} else {} block, but this is lost when the syntax tree is produced. This could be done as a new "language" in the decompiler, but the current printc.cc file is 3000 lines, and a new printcIR.cc file might be a similar amount of new code that would need to be written.

[LukeSerne]

Using decomp_dbg, a cli-binary that you need to build separately from the Ghidra source code, it is possible to gain some more information about the inner workings of the decompiler. After decompiling a function, you can use the print C command to get the C-like code you also get inside the Ghidra UI, but you can also use the print raw command, which prints the state of the P-Code. However, this is plain text, and you need to parse this. I wrote a parser for this as part of my DecompVis project, and I came across some ambiguities along the way.

Regarding the HighVariable relations, you might be able to recover some of this information by parsing the output of print varnode <varnode>, where <varnode> is a varnode that is included in the print raw output, similar to the below interaction within decomp_dbg.

[decomp]> restore /path/to/hello_world.xml
[decomp]> load function main
[decomp]> decompile
[decomp]> print C

undefined8 main(void)

{
  printf("Hello, World!");
  return 0;
}

[decomp]> print raw
0
Basic Block 0 0x0010114d-0x0010116b
0x00101160:20:  u0x10000019(0x00101160:20) = #0x102004
0x00101160:9:   call fprintf(free)(u0x10000019(0x00101160:20))
0x00101165:a:   RAX(0x00101165:a) = #0x0
0x0010116b:11:  return(#0x0) RAX(0x00101165:a)

[decomp]> print varnode u0x10000019(0x00101160:20)
Variable: UNNAMED
Type: char *

0: char * = u0x10000019(0x00101160:20) tlock implied (consumed=0xffffffffffffffff) (internal=0x5ee6ede040e0) (create=0x63)

This method might also work for getting the names of enum values, but I haven't tested that. Alternatively, you could try comparing the output of print raw and print C xml to figure out what name corresponds to a specific constant.

If that doesn't work, there are many more commands in decomp_dbg, that are barely documented. Just playing around with those commands, you might stumble upon some a command that gives you the information that you need.

---

All in all, there are some hacks / workarounds to get some more information on the decompiler in its current state. As mentioned before, there are some ambiguity issues with the output of print raw, but even though two PRs have been submitted, they have not seen any progress in years. It appears that other parts of the decompiler get priority over the debugging/introspection part.

Another interesting conclusion is that there already is code in the decompiler to print a lot more information that just the final C code. Exposing these functions to the Java-side seems like significantly less development effort, while still providing a benefit by allowing Ghidra scripts to make more meaningful improvements to the decompiler output.

[msm-code]

Exposing these functions to the Java-side seems like significantly less development effort, while still providing a benefit by allowing Ghidra scripts to make more meaningful improvements to the decompiler output.

Is there a significant difference in the amount of available information between print C xml and DecompileResult.getCCodeMarkup? From a quick look I see that in the XML there are oprefs for variables, but that's still not enough to recover full syntax tree, because operators don't have references to parent operations (so in (a * b) + c a and b have ref to * and c has a reference to +, but there is no way to estabilish relation between * and +). There are also varrefs, but they are not needed, one can just look up variable name in high function.

...I should probably learn more about the decompiler capabilities. Unfortunately most of the decomp_dbg features are not available via the decompile interface, as far as I know.

Fun fact: I wrote a ClangTokenGroup parser that can convert ClangTokenGroup expressions back into AST:

$ python3 clang_fun.py "param_1" "->" "jumpdata" "=" "(" "somestruct" "*" ")" "(" "(" "longlong" ")" "&" "param_1" "->" "jumpdata" "->" "offset" "+" "(" "longlong" ")" "param_1" "->" "jumpdata" "->" "offset" ")"
Assign(MemberAccess(Variable(param_1), ->, jumpdata), Cast(somestruct *, BinOp(+, Cast(longlong, AddressOf(MemberAccess(MemberAccess(Variable(param_1), ->, jumpdata), ->, offset))), Cast(longlong, MemberAccess(MemberAccess(Variable(param_1), ->, jumpdata), ->, offset)))))

Nice thing about this is that this representation knows about HighVariables, in contrast to high pcode which is still operating on varnodes.

I plan to play with this a bit, and see if there are useful analyses that can be done on AST but can't be efficiently expressed in PCode. If yes, I'll clean this up and opensource (but it's in a rough state right now).

[LukeSerne]

I'm not very familiar with the Java interface to the decompiler, but it seems like the information produced by print C xml is pretty much the same as a ClangTokenGroup. For finding the relation between a, b and c in (a * b) + c, it's probably more helpful to look at the p-code (as produced by print raw after decompilation). This relation should also be recoverable from a HighFunction object, since that's also what is used by the "Graph Control Flow" and "Graph Data Flow" menu items. These two actions are implemented in the PCodeCfgGraphTask class.

I think a major advantage of scripts that change how the decompiled output looks, is that it allows for much easier customisation, or for prototyping ad-hoc optimisations that are very specific to a compiler. Another analysis that might be easier to do from a scripting side is better support of inlined functions. Currently, if the same outlined function is called multiple times from the same function, and that outlined function is not a straight-line function, but instead contains jumps or calls to other functions, the decompiler can only inline the first function, which in some cases severely reduces the quality of the decompiler output.