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:
Thanks for all the help, most of old problems have been solved. Specifically, these problems are as follows:
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.
There used to be many problems for call site. Thanks for strong help from r2, some of them have been solve:
afcrcommand in r2
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.
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:
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:
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
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
For every function we analyze, consider all the callee of them. We should calculate reserved registers for them.
Fix all the OpCall nodes using the information about the callees' reserved registers
Calculate a_locs for every function.
Preparing Stage may be finished at the (mid)night of Tuesday
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.
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.
Push the start node into heap with the initial abstract store and a_locs.
If the heap is empty, go to step 7.
Pop a basic block, if it's a loop entry, use
limited widening for every phi node, otherwise, use
Trave the Opcode node in order within the poped block, and calculate the abstract store at the exit of this block.
Push all the successor of the poped block. Go to step 4.
End the program.
Maybe I could reuse some code from the old VSA.
Analyzing Stage may be finish at the (mid)night of Thursday
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
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.