- Notifications
You must be signed in to change notification settings - Fork1.7k
Java: Prune PathGraph for CsrfUnprotectedRequestType.ql#20083
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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Java: Prune PathGraph for CsrfUnprotectedRequestType.ql#20083
Conversation
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Pull Request Overview
This PR optimizes the PathGraph for the CSRF unprotected request type query by implementing a bidirectional reachability analysis to prune irrelevant edges. The optimization is intended to be behavior-preserving while significantly reducing output size (saving hundreds of MBs) and improving processing performance for the DCA tool.
Key changes:
- Introduces bidirectional flow analysis predicates (
fwdFlowandrevFlow) to identify relevant edges - Replaces direct
CallGraph::edgesusage with a prunedrelevantEdgepredicate - Updates the transitive closure computation to use the optimized edge predicate
Reviewed Changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated 3 comments.
| File | Description |
|---|---|
| CsrfUnprotectedRequestType.ql | Updates query to use pruned edge predicate instead of raw call graph edges |
| CsrfUnprotectedRequestTypeQuery.qll | Implements bidirectional reachability analysis and relevantEdge predicate for path pruning |
| /** | ||
| * Holds if `pred` has a successor node `succ` and this edge is in an | ||
| * `unprotectedStateChange` path. | ||
| */ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The predicate should include documentation about its performance characteristics and the bidirectional pruning strategy, as this is a key optimization that affects query behavior.
| */ | |
| */ | |
| /** | |
| *Holdsif `pred` has a successor node `succ`andthis edge isin an | |
| * `unprotectedStateChange` path. | |
| * | |
| *Performancecharacteristics: | |
| *-Thispredicate relies on `revFlow`, which is a recursive flowpredicate | |
| *thatcombinesforwardandreversegraph traversal. | |
| *-Theuse of `CallGraph::edges` ensures that only valid edgesin the call | |
| *graphareconsidered,reducingunnecessary computations. | |
| * | |
| *Bidirectionalpruning strategy: | |
| *-Thepredicate leverages `revFlow(pred)`and `revFlow(succ)` to prune | |
| *thesearchspacebyensuringthatboththepredecessorand successor | |
| *nodesarepartofvalidreverse flows. | |
| */ |
Copilot uses AI. Check for mistakes.
| @@ -237,12 +237,35 @@ private predicate sink(CallPathNode sinkMethodCall) { | |||
| ) | |||
| } | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Missing documentation for the fwdFlow predicate. Should explain that it computes forward reachability from sources using transitive closure over call graph edges.
| /** | |
| *Computesforward reachabilityfrom source nodes using transitive closure | |
| *overcallgraphedges.Holdsif `n` is reachablefrom a source node. | |
| */ |
Copilot uses AI. Check for mistakes.
| or | ||
| exists(CallPathNode mid | fwdFlow(mid) and CallGraph::edges(mid, n)) | ||
| } | ||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Missing documentation for the revFlow predicate. Should explain that it computes backward reachability from sinks within the forward-reachable nodes, implementing the bidirectional pruning strategy.
| /** | |
| *Computesbackward reachabilityfrom sinks within the forward-reachable nodes. | |
| *Thispredicate implements the bidirectional pruning strategyby combining | |
| *forwardreachability(`fwdFlow`)withbackwardreachabilityfrom sinks. | |
| */ |
Copilot uses AI. Check for mistakes.
The "Query result disk size" metric shows a massive reduction as expected. |
I suppose you could add a change note with the "fix" category, so that if anyone notices a change they can figure out what caused it. Up to you. |
After result interpretation the sarif is unchanged, so it's not very detectable. |
f697511 intogithub:mainUh oh!
There was an error while loading.Please reload this page.
This should be completely behaviour-preserving, but saves hundreds of MBs of output for some repos. Dca has had trouble processing the output of this query even for cases with zero alerts for several repos.
See also comments here:#19872 (comment)