Questions about internal mechanism of cwe_checker

[M4tsuri]

Hello, I'm a beginner in static analysis trying to understand the mechanism of cwe_checker. However, I've got some questions as follows:

1. It tokes me a long time to figure out how PcodeExtractor extracts pcodes from each instruction and place them in the right block. However, I found Ghidra already provides an API to get optimized pcode-level basic blocks. I'm confused why do you choose not to use the API (efficiency or accuracy consideration?)
2. I'm trying to understand the inter-procedural analysis algorithm used by cwe_checker. However, I'm still confused which approach did you choose to make the analysis. I'd be grateful if you could share some more detailed documentation or papers with me.
   Thank you very much.

[Enkelmann]

Regarding 1.: There several reasons why we do not use Ghidras basic blocks:

• The first is a purely historical one: The cwe_checker was originally based on BAP, not on Ghidra. When we made the transition to Ghidra we supported both BAP and Ghidra for a while. For that we had to translate between the intermediate representations of them. This lead to some design decisions that look strange now that we do not support BAP anymore. This (and some potential bug sources) is also the reason why the PcodeExtractor is on my shortlist of things I want to refactor. I just have to find the time for it somehow... 😅
• The second is that as far as I remember all the basic block abstractions we looked at in Ghidra did not agree with what we wanted to define as basic block. For us, a basic block should only contain jumps at the end of the block. On the other hand, basic blocks in Ghidra have a start and an end address and each assembly instruction is only contained in one basic block. That means that if an assembly instruction contains some Pcode-relative jumps inside the instruction, then Ghidra cannot generate more than one basic block for that instruction, which would break our assumption. In summary, this is an accuracy consideration.

Also, my hope was that users would only need to look at the intermediate representation module, but never at the PcodeExtractor code itself. So this part of the code is also not as well-documented as the rest of the code.

Regarding 2.:

• In general, the cwe_checker performs fixpoint algorithms over the control flow graph of the program, where the state of the program at a specific point in the CFG is represented by abstract domains. The graph has some additional nodes and edges to allow for data flows between the caller site and the return-to site of calls. You can look at the online documentation for a better description of the graph.
• More specifically, at the heart of the analysis is the Pointer Inference analysis. It is a combination of Points-To-Analysis and Value-Set-Analysis. But it is still under heavy development, so everything I say here about the details might change in the coming months. That is also the reason why there is no paper about it yet.

Feel free to ask more questions (including beginner questions!) either here or in the FACT Gitter channel (FACT is the sister project of the cwe_checker), whatever you prefer. The field of static analysis is vast, so I might need some more questions before I figure out an efficient way how to answer them for you.

[M4tsuri]

Thank you for your explanation.
As for the second reason of the first question, if I'm not mistaken, you are talking about the situation where a BRANCH may appears at the middle of the pcodeBlock from an instruction. However, It seems that Ghidra do split one instruction to multiple blocks. I wrote a little demo to demonstrate it:

The PcodeBasicBlocks we get from it with the previous mentioned API is:

As you can see, the cmovz instruction at 0x0400087 is correctly splitted into two blocks.

Moreover, as mentioned here the pcode basic blocks provided by this API is already optimized, so we can also simplify some code in cwe_checker main program.

For the second question, I have a more specific observation on cwe_checker. And I wonder if I'm right:

Is cwe_checker using context-sensitive analysis to avoid facts pollute each other when multiple caller calls the same callee? It seems that cwe_checker uses a stack-like structure to keep the call-stack information. Can we totally avoid inter-procedural infeasible paths caused by incorrect call-return pairs with this approach?

The sample file and the script I used to extract PcodeBasicBlocks is attached below.

PcodeBasicBlockPOC.zip

[Enkelmann]

Ah, that is not raw P-Code anymore. We decided to use the raw P-Code instead of the processed one since we weren't sure what exactly is done by Ghidra's analysis passes. Especially whether or not these analyses use heuristics, which may introduce errors that we do not want. But this decision was also made when we still had to support BAP (and thus we wanted the P-Code to look as similar to BAP's IR as possible). So when the big PcodeExtractor refactoring happens, we will take a second look and decide if we can now use the processed P-Code instead of the raw one (or not).

For the second question: In the current implementation we cannot totally avoid polluting state with incorrect call-return pairs:
What the analysis does is to check that the state from the callee contains the call address corresponding to the call-return pair to ensure that the returned state does not come from a totally different call. So the returned state is at least a summary (merged) state where the correct call site contributed to the state.
But we can still pollute the state through infeasible paths: If functions A and B both call function C, but the call only returns when B is the caller, then the algorithm will still think that it may also return to A (with a summary (merged) state from both calls), despite the path being infeasible.
So this is still a best-effort approach, which fortunately works most of the time and does not produce a lot of imprecision (at least compared to other sources of imprecision).
But in general we always have to cope with infeasible paths leading to imprecision, since the analysis is simply not path-sensitive.

[M4tsuri]

Thanks to your help, I finally got some understanding about the interprocedural analysis approach used by cwe_checker. Now I'm trying to learn the pointer inference and abstract domain parts. I wonder if domain theory is required for understanding the abstract domain module.

[Enkelmann]

If you know the basic ideas and terminology of abstract interpretation and abstract domains (e.g. you know what a partially ordered set is), then it should be fine. Else you may want to read up on that first, since the documentation assumes familiarity with the basic concepts.

[M4tsuri]

OK, thank you very much