Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Data flow: Performance improvements #14255

Open
wants to merge 1 commit into
base: main
Choose a base branch
from
Open

Data flow: Performance improvements #14255

wants to merge 1 commit into from

Conversation

hvitved
Copy link
Contributor

@hvitved hvitved commented Sep 19, 2023 •
edited

  • Split up the existing fwdFlowIn predicate into two predicates (using a parameterized module); one which is used to calculate flow in and one which is used to calculate flow through (fwdFlowIsEntered). This allows us to get rid of a lot of columns in the first predicate, specifically we don't need to record the argument that flows into the parameter. The second predicate does need to record the argument, however, we can restrict this to arguments/parameters that may actually flow through.
  • Speedup pathIntoCallable0 by joining with a pruned dispatch relation.

Timings before

Most expensive predicates for stage 18 of completed query StoredXSS.ql:
        time   | evals |   max @ iter | predicate
        -------|-------|--------------|----------
        18m14s |   406 | 52.5s @ 127  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowInCand#11#fffffffffff@403aewe8
        10m54s |   406 | 16.7s @ 89   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlow0#9#fffffffff@403ae0w8
         9m31s |   649 | 1m50s @ 151  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::pathIntoCallable0#8#ffffffff@b3c71w2o
         4m17s |   331 | 1m20s @ 87   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage4#::Stage#Stage5Param#::fwdFlowInCand#11#fffffffffff@31a9bwlg
         2m27s |   405 | 28.2s @ 88   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowIn#13#fffffffffffff@403ae2w8
          2m2s |   404 | 16.4s @ 90   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlow1#10#ffffffffff@403aeye8
         36.6s |       |              | project#DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowIn#13#fffffffffffff@3c4129hi
         28.2s |   626 |  1.4s @ 118  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowInCand#11#fffffffffff@3e737wqi
         26.9s |   975 | 244ms @ 147  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff@10f596w6
         26.2s |   731 | 340ms @ 94   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff@c5f4c6we
         25.6s |   406 | 497ms @ 110  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowOutCand#10#ffffffffff@403aeze8
         23.2s |   649 |  1.2s @ 145  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::pathStep#7#fffffff@b3c711wo
         22.4s |       |              | DataFlowPublic#e1781e31::Node::hasLocationInfo#5#dispred#ffffff@18604ds8
           21s |   649 |  1.1s @ 145  | _DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac38__#antijoin_rhs#7@L0#b3c71
         20.7s |    14 | 17.6s @ 3    | ActiveRecord#b77aa5fc::ActiveRecordAssociationMethodCall#ff@b5167w17
         18.3s |       |              | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::flowIntoCallAp#5#fffff_24013#join_rhs@cd92eclj
         15.8s |       |              | _AST#a6718388::AstNode::getLocation#0#dispred#ff_10#join_rhs_FileSystem#df18ed9a::Make#FileSystem#e9__#shared@1a42d5p4
           14s |   731 |  1.3s @ 129  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowInCand#11#fffffffffff@c5f4cwse
         13.4s |   406 |    2s @ 89   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowIsEntered#9#fffffffff#reorder_2_6_7_8_0_1_3_4_5@403ae7w8
         12.3s |   971 |    1s @ 164  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowInCand#11#fffffffffff@10f59wr6
          9.9s |       |              | Rails#a086b70b::RenderCallUtils::getSubPath#1#ff@a7b8de8u
          9.7s |       |              | TreeSitter#03eaabdd::Ruby::AstNode::getParent#0#dispred#bf@a72f6642
          9.1s |       |              | locations_default_10#join_rhs@6e0257cd

Timings after

Most expensive predicates for completed query StoredXSS.ql:
        time  | evals |   max @ iter | predicate
        ------|-------|--------------|----------
         3m0s |   267 | 20.3s @ 57   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlow0#9#fffffffff@aeccfwqb
        1m29s |   266 | 14.8s @ 58   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlow#9#fffffffff@aeccfxqb
        1m19s |   267 | 12.7s @ 56   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlowIn#6#ffffff@aeccf3wb
        35.5s |   651 | 656ms @ 93   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff@7c9b51wm
        28.1s |   485 | 558ms @ 76   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff@b07461wj
        24.3s |   649 |  1.2s @ 145  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::pathStep#7#fffffff@67c291w5
          24s |   649 |  3.6s @ 151  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::pathIntoCallable0#8#ffffffff@67c29w95
        21.5s |   649 |  1.2s @ 145  | _DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac38__#antijoin_rhs#6@L0#67c29
          21s |   649 |  1.8s @ 118  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow0#9#fffffffff@7c9b5wmm
        20.5s |   483 |  1.6s @ 92   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow0#9#fffffffff@b0746wlj
        17.4s |   312 |  3.9s @ 78   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage4#::Stage#Stage5Param#::fwdFlowIn#6#ffffff@14e6c4w8
          17s |   423 | 427ms @ 202  | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#f6f2598d::TaintFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#TaintTrackingImplSpecific#b79e579d::RubyTaintTracking#::Global#StoredXSSQuery#5ea303cf::StoredXssConfig#::C#::MkStage#Stage2#::Stage#Stage3Param#::fwdFlow0#9#fffffffff@4e3b9wmm
        16.6s |       |              | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage2#::Stage#Stage3Param#::flowIntoCallAp#4#ffff@e1cd24s5
         9.6s |   411 |  2.6s @ 33   | DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::pathOutOfCallable1#6#ffffff@67c296w5

@hvitved hvitved added the no-change-note-required This PR does not need a change note label Sep 19, 2023
@hvitved hvitved marked this pull request as ready for review September 19, 2023 18:17
@hvitved hvitved added the Ruby label Sep 20, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
no-change-note-required This PR does not need a change note Ruby
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
1 participant
@hvitved