`@SmashStack`

`2017-08-14T12:34:05.000000Z`

`字数 5264`

`阅读 451`

`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

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:

- 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

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:

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 SSAExpand 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.

- 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.

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`simple union/join`

.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.

添加新批注

在作者公开此批注前，只有你和作者可见。

回复批注