PKU-ASAL / SeeWasm

A native symbolic execution engine for WebAssembly
40 stars 4 forks source link

Trimming the graph before generating ICFG #74

Closed HNYuuu closed 2 years ago

HNYuuu commented 2 years ago

Is your feature request related to a problem? Please describe. Once generating intervals from ICFG or visualizing the ICFG on basic block levels, it is insufferably slow. After checking the reason, we find that an extremely low-level library function, e.g., strnlen that is invoked by printf_core, will invoke memchr, which is also called by our analyzed function.

Due to the ICFG, the strnlen will be included in the ICFG, which will not be executed from the path from printf_core, as the printf_core is emulated by our engine.

Describe the solution you'd like Before generating ICFG, we need conduct graph trimming to minimize the number of nodes, i.e., unrelated candidate functions.

Specifically, we can use call graph, and traverse the call graph from the entry function to filter out all callees as a set named S. Then, in S, we firstly remove the edge (foo to bar) if the bar is emulated. Then, we will check all functions out of S (\bar{S}) to examine if there exist such edges that direct from \bar{S} and direct to S and remove them. In other words, the call graph is cut into two subgraphs, one is from entry to its un-emulated callees, the other consists of unrelated functions.

After that, the generation of ICFG on the former subgraph will be accelerated theoretically.

HNYuuu commented 2 years ago

Remove unrelated functions from self.cfg.functions before generating ICFG, refer to #75

HNYuuu commented 2 years ago

For base64-14 and uniq, can remove around 15% of unrelated functions. For those small case, like fib and fac, can remove around 70%