search

secure-software-engineering / FlowDroid

FlowDroid Static Data Flow Tracker
GNU Lesser General Public License v2.1
1.02k stars 292 forks source link

Sparse Analysis Optimization Of Low Code Intrusion #611

Open notify-bibi opened 1 year ago

notify-bibi commented 1 year ago

SparseIFDS

Can improve speed and reduce memory usage. ( Be able to reduce propgeate edges by 20 times

Now this optimization will cause some test cases to fail and is still being resolved

[ERROR]   ImplicitFlowTests>ImplicitFlowTests.userCodeTest2:667->JUnitTests.negativeCheckInfoflow:146 expected:<0> but was:<1>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.implicitFlowTaintWrapperNegativeTest:483->JUnitTests.negativeCheckInfoflow:146 expected:<0> but was:<1>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.userCodeTest1:654->JUnitTests.negativeCheckInfoflow:146 expected:<0> but was:<1>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.classTypeTest:583->JUnitTests.checkInfoflow:124 expected:<1> but was:<0>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.switchTest:85->JUnitTests.checkInfoflow:124 expected:<1> but was:<0>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.arrayIndexTest1:620->JUnitTests.checkInfoflow:124 expected:<1> but was:<0>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.conditionalAliasingTest2:516->JUnitTests.negativeCheckInfoflow:146 expected:<0> but was:<1>
[ERROR]   ImplicitFlowTests>ImplicitFlowTests.afterCallNegativeTest:550->JUnitTests.negativeCheckInfoflow:146 expected:<0> but was:<1>
StevenArzt commented 1 year ago

If you can ensure that all test cases still work with your optimization and can show a significant speedup, that would be greatly appreciated. Please provide precise data on your measurements, i.e., on which apps with which configuration you tested.

Concerning the implicit flows, you could propgate them non-sparse. Since these are control-flow dependencies, a lot of locals will be tainted anyway, so I guess you won't see much of a speedup there with a sparse propagation. It would then maybe make sense to distinguish between explicit flows (wich you propagate through a sparse graph) and implicit flows (which you propgate as normal). That would also resolve the correctness issues from the test cases.

notify-bibi commented 1 year ago

Thanks for the technical reminder, I'll get these things done quickly