search

SVF-tools / SVF

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

Report on Pointer Analysis Issues #1033

Open sherrysun0613 opened 1 year ago

sherrysun0613 commented 1 year ago

Dear SVF developer:

 ​We are several PhD students and recently do some research on open-source projects. We have used SUPA [1] to analysis them, but found the following issues:

  1. Context sensitivity. In example swap.c [2], we run the following command.

    ./dvf -cxt -query=all -max-cxt=5 -flow-bg=10000 -cxt-bg=10000 -print-query-pts swap.ll

​ The expected result should be that variable aand m point to p and p' at their own callsites, respectively. But actual results show they point to the same formal parameter p, which is the 0th arg of function swap.

​ 2. Virtual function. From program main.c [3], the call chain sequence is as following:

db->Put(wrt_opt, key, val); // 1st, in src/main.cc
Status Put(const WriteOptions& options, const Slice& key, const Slice& value); // 2nd, include/tinykv.h
Status DBImpl::Put(const Slice& key, const Slice& val); // 3rd, src/db_impl_write.cc
Status KVDB::Put(const Slice& key, const Slice& value); // 4th, src/db_impl_write.cc

 We execute the commands in README.md, and then run the following command to generate ctx result.

./dvf -cxt -query=all -max-cxt=5 -flow-bg=10000 -cxt-bg=10000 -print-query-pts bitcode/libTinyKV.a.ll

 The expected result should be that actual parameter key at 1st, key at 2nd, key at 3rd and key at 4th are all aliases to each other. But actual result shows that, only key at 3rd and key at 4th are aliases.

 We are not sure if we run SUPA in a wrong manner, or maybe the version after SVF-2.5 just not deal with them well. And we report them to you and sincerely ask for advice.

 The SVF team has been working on improving pointer analysis over the years, and we hope these suggestions also have a little help. Look forward to your reply on how to solve these problems. Thank you!

[1] https://github.com/SVF-tools/SVF/tree/f50cd0758d49d291a51fbdfa25080ea295ff870d/tools/DDA/ [2] SVF_exp_mail/context_sen_exp/swap.c [3] SVF_exp_mail/virtual_func_exp/TinyKV/main.c [4] https://figshare.com/articles/dataset/SVF_Pointer_Analysis_Issues/22274539/2

yuleisui commented 1 year ago

Would you be able to simplify both code examples as small as possible? It still looks a bit large.

sherrysun0613 commented 1 year ago

Thank you for your reply and suggestions. I will email you after the code is reedited.

------------------ 原始邮件 ------------------ 发件人: "SVF-tools/SVF" @.>; 发送时间: 2023年3月15日(星期三) 下午3:38 @.>; @.**@.>; 主题: Re: [SVF-tools/SVF] Report on Pointer Analysis Issues (Issue #1033)

Would you be able to simplify both code examples as small as possible? It still looks a bit large.

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: @.***>

sherrysun0613 commented 1 year ago

I have minimized TinyKV code to approximate 150 lines, is it small enough?

yuleisui commented 1 year ago

Would you help dig a bit more to figure out the issue of the context-sensitive implementation for your first example? It would be good if you could come back with some debug observations and problems you identified.

sherrysun0613 commented 1 year ago

After finding the issue of context-sensitivity about first example, I traced the edge relationships between variables in its SVFG according to .ll file. Would this be helpful for debug?

yuleisui commented 1 year ago

Yes, you can dig it deeper to see what are the problem. You may wish to make a pull request for a fix if you can.