Get Ready for VSA

RSoC

After about two-days thinking in the weekend, I have some new ideas for VSA in Radeco, which is more mature and viable. Thanks for Anton and other core team members' help, some problems mentioned in this blog have been solved.

The remainder of this blog is organized as follows:

• Which problems have been solved
• Why some new ideas are needed
• How my new idea is organized
• Some remaining problems

Which problems have been solved

Thanks for all the help, most of old problems have been solved. Specifically, these problems are as follows:

Initial Global Data

The difficulty in the obstacle is that we cannot get the global variables' initial value in every function entry if we analyze functions in parallel.

Anton has advised me to build Call Flow Graph to analyze functions in order, rather a supergraph. It's a good idea and it's this idea that triggered the new idea, which may also solved this problems.

Call Site

There used to be many problems for call site. Thanks for strong help from r2, some of them have been solve:

• We could finger argument and return registers because of afcr command in r2
• We could calculater the sp_delta by the new idea
• We could also solve some problems caused by recursive function or functions called in loop by the new idea

Why some new ideas are needed

The key point for solving Call Site and Initial Global Data problems is to analyze functions in order, but there are two shortages that we cannot avoid:

• The time consumption and The inaccuracy. If we are analyzing a very huge binary, decompiling a single function will cause Radeco analyze all the functions. It will not only waste too much time, but also get wrong output beceuse of so many indirect calls and jumps in the whole binary. This will become the mortal shortage of our decompiler. After all, IDA F5 could decompile a single function in a short time even though the target binanry is huge. We can do better.

• The difficulty of dealing with recursive functions or functions called in a loop. Because dislike in basic blooks, at fucntion level, it's not an easy way to find the register which controls the execution of the loop. By the way, it's also hard to find a suitable order used in visit functions, for Call Flow Graph is a complex graph, not a simple tree.

Above problems are the biggest obstacles in developing a suitable algorithm to analyze functions in order. Thus, a new algorithm was came out. I will disclose it in the next chapter, and hope anyone could give me some suggestions or point out some problems.

How my new idea is organized

Let's look back the problem in Call site. The biggest problem is that we do not know which registers are the same value after the call. Argument and return registers will influence the analysis, but not the biggest ones. The key point is the reserved registers of callee, which we could get without analyzing the whole callee body.

Thus, I came up with an idea that we could cut VSA into some stages, preparing stage, analyzing stage and improving stage. Move reserved registers calcualtion into preparing stage, and move return and argument registers, which could improve out analysis accuracy, into improving stage. More details are as follows:

Preparing Stage

The aim of preparing stage is to find reserved registers and other prepare.

The basic assumption of this stage is:
All the reserved registers are stored by push at the beginning of the functions, and meanwhile, are restored by pop at the end of the functions

Thus, the preparing stage consists of the following steps:

1. Split middle/ssa/memoryssa.rs into two files. The first part becomes the base code of analysis/rfnAnalysis.r for preparing stage. The second part are still middle/ssa/memoryssa.rs, which purely receive variables list, may-alias set and ssa to generate Memory SSA

2. Expand SSA_Extra, to maintain two HashMaps. The first one maps from ssa node to corresponding register, while the second one maps from every OpCall node to corresponding radecoFunction

3. For every function we analyze, consider all the callee of them. We should calculate reserved registers for them.

   • At the first basic block (the only child node of start node), finding all the OpStore node, which store a register comment node into a stack offset address.
   • At the last basic block (thy only parent node of exit node), finding all the OpLoad node, which load a value from a stack offset address into a register.
   • Compare the results, get the corresponding ones as reserved registers.

4. Fix all the OpCall nodes using the information about the callees' reserved registers

5. Calculate a_locs for every function.

Preparing Stage may be finished at the (mid)night of Tuesday

Analyzing Stage

Analyzing Stage concentrates on VSA itself, for every function in parallel.

The algorithm are the same as the old blog, for soundness, I copy them here.

1. The program maintains a heap, which consist of basic blocks. The sort key of the heap is the number of unvisited predecessor, from small to big. The aim of this heap is that we could distinguish whether the block is a loop entry. When Heap pops a basic block, if the number of unvisited predecessor is zero, it means is's not a loop entry block, otherwise, it is.

2. Push the start node into heap with the initial abstract store and a_locs.

3. If the heap is empty, go to step 7.

4. Pop a basic block, if it's a loop entry, use limited widening for every phi node, otherwise, use simple union/join.

5. Trave the Opcode node in order within the poped block, and calculate the abstract store at the exit of this block.

6. Push all the successor of the poped block. Go to step 4.

7. End the program.

Maybe I could reuse some code from the old VSA.

Analyzing Stage may be finish at the (mid)night of Thursday

Improving Stage

The aim of improving stage is to improve accuracy by argument and return registers and some other information.

After all, we have to build APIs for ASI in future work, Thus this stage will become the part which could gather information from other analyzers and renew abstract store for VSA

Actually, I haven't find a way to develop this stage. For ASI haven't been finished. Maybe I will consider it at the same time with ASI

Some remaining problems

There are still some problems haven't been overcame.

• In call site, how could we get the abstract store from library functions?

• Both problems in Condition and Loop.