search

SVF-tools / SVF

Static Value-Flow Analysis Framework for Source Code
http://svf-tools.github.io/SVF/
Other
1.43k stars 436 forks source link

Question about the time overhead of LLVMModuleSet::buildSymbolTable() #1573

Open learjet5 opened 1 month ago

learjet5 commented 1 month ago

I'm using SVF to analyze Linux kernel-6.5. The LLVM-version is 14.0.6. And the inputs include 2600+ .bc files.

At first, I'm using SVF-2.5 and everything goes well. It takes less than half an hour to build the PAG of the kernel code. However, after I migrated the code to SVF-2.9, it takes more than 10 hours for the LLVMModuleSet::buildSymbolTable() step.

I know SVF has been refactored since SVF-2.6. But I didn't figure out why there can be such a large difference in time overhead between the two versions. Thank you in advance for your response!

yuleisui commented 1 month ago

Could you share us your bc file or provide a link to download?

@jumormt could you take a look at this?

jumormt commented 1 month ago

@learjet5 Could you please send us the bitcodes that exhibit significant analyzing time differences?

learjet5 commented 1 month ago

Thanks for your early reply! @yuleisui @jumormt

I conducted experiments using svf-ex of SVF-2.9 and SVF-2.7 on "25 .bc files" and "2600+ .bc files" separately.

It seems that the time overhead does not exhibit a linear relationship with the number of analyzed bc files. However, buildSymbolTable() in SVF-2.9 does indeed take more time. The difference is significant especially for 2600+ .bc files situation. (Perhaps the opaque pointer operations in newer versions caused more time overhead.)

Here are the shell commands and outputs of the above experiments (I added some debug output in the SVF code). Download Link

learjet5 commented 1 month ago

Feel free to reach me if you need all the 2600+ .bc files of Linux-6.5-defconfig.

learjet5 commented 1 month ago

Well, in SVF-2.8, the buildSymbolTable() step can finish within 3 minutes for all the kernel bitcode files. I think it's the inferObjType() related logic causes such time overhead. I'll continue my analysis with SVF-2.8 anyway.

Thanks again for your help!

yuleisui commented 1 month ago

@learjet5 thanks for reporting back. Could you help narrow down which part of ‘ inferObjType’ caused the issue?

learjet5 commented 4 weeks ago

@learjet5 thanks for reporting back. Could you help narrow down which part of ‘ inferObjType’ caused the issue?

I'll try to look into it. If there are any updates, I'll let you know.