Skip to content

JS: Fix performance regression in the GetLaterAccess module. #12592

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.

Sign up for GitHub

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

Merged
erik-krogh merged 4 commits into from
Mar 22, 2023
Merged

JS: Fix performance regression in the GetLaterAccess module. #12592

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
34fe1a8
use SSA in the GetLaterAccess module
erik-krogh Feb 6, 2023
070468a
fix performance
erik-krogh Mar 20, 2023
c023af7
manual recursion, and other join-order
erik-krogh Mar 21, 2023
bdab57b
Update javascript/ql/lib/semmle/javascript/GlobalAccessPaths.qll
erik-krogh Mar 22, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
57 changes: 40 additions & 17 deletions javascript/ql/lib/semmle/javascript/GlobalAccessPaths.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -270,6 +270,19 @@ module AccessPath {

/** A module for computing an access to a variable that happens after a property has been written onto it */
private module GetLaterAccess {
/**
* Gets an reference to the SSA variable `variable`.
* Either the definition or a use of the SSA variable
*/
private VarRef getAVariableRef(SsaVariable variable) {
(
result = variable.getAUse()
or
result = variable.getDefinition().(SsaExplicitDefinition).getDef().getTarget()
) and
variable = getARelevantVariableSimple()
}

/**
* Gets an access to a variable that is written to in `write`, where the access is after the write.
*
Expand All @@ -286,7 +299,7 @@ module AccessPath {
pragma[noopt]
DataFlow::Node getLaterBaseAccess(DataFlow::PropWrite write) {
exists(
ControlFlowNode writeNode, BindingPattern access, VarRef otherAccess, Variable variable,
ControlFlowNode writeNode, BindingPattern access, VarRef otherAccess, SsaVariable variable,
StmtContainer container
|
access = getBaseVar(write) and
Expand All @@ -303,7 +316,7 @@ module AccessPath {
i < j
)
or
otherAccess.getBasicBlock() = getASuccessorBBThatReadsVar(write) // more manual magic - outlined into a helper predicate.
otherAccess.getBasicBlock() = getASuccessorBBThatReadsVar(write)
)
}

Expand All @@ -323,24 +336,34 @@ module AccessPath {
}

/** Gets an access to `var` inside `container` where `usedInWrite` indicates whether the access is the base of a property write. */
private VarRef getAnAccessInContainer(Variable var, StmtContainer container, boolean usedInWrite) {
result.getVariable() = var and
private VarRef getAnAccessInContainer(
SsaVariable var, StmtContainer container, boolean usedInWrite
) {
result = getAVariableRef(var) and
result.getContainer() = container and
var.isLocal() and
if result = getBaseVar(_) then usedInWrite = true else usedInWrite = false
}

/** Gets a variable that is relevant for the computations in the `GetLaterAccess` module. */
private Variable getARelevantVariable() {
/**
* Gets a variable that is relevant for the computations in the `GetLaterAccess` module.
* This predicate restricts as much as it can, but without depending on `getAVariableRef`.
*/
pragma[inline]
private SsaVariable getARelevantVariableSimple() {
// The variable might be used where `getLaterBaseAccess()` is called.
exists(DataFlow::Node node |
exists(fromRhs(node, _)) and
node.asExpr().(VarAccess).getVariable() = result
) and
node.asExpr() = result.getAUse()
)
}

/**
* Gets a variable that is relevant for the computations in the `GetLaterAccess` module.
* This predicate depends on `getAVariableRef`, which in turn depends on `getARelevantVariableSimple`.
*/
private SsaVariable getARelevantVariable() {
// There is a write that writes to the variable.
getBaseVar(_).getVariable() = result and
// It's local.
result.isLocal() and // we skip global variables, because that turns messy quick.
getBaseVar(_) = getAVariableRef(result) and
// There is both a "write" and "read" in the same container of the variable.
exists(StmtContainer container |
exists(getAnAccessInContainer(result, container, true)) and // a "write", an access to the variable that is the base of a property reference.
Expand All @@ -350,15 +373,15 @@ module AccessPath {

/** Gets a basic-block that has a read of the variable that is written to by `write`, where the basicblock occurs after `start`. */
private ReachableBasicBlock getASuccessorBBThatReadsVar(DataFlow::PropWrite write) {
exists(VarAccess baseExpr, Variable var, ControlFlowNode writeNode |
exists(VarRef baseExpr, SsaVariable var, ControlFlowNode writeNode |
baseExpr = getBaseVar(write) and
var = baseExpr.getVariable() and
getAVariableRef(var) = baseExpr and
var = getARelevantVariable() and
writeNode = write.getWriteNode() and
writeNode.getBasicBlock().(ReachableBasicBlock).strictlyDominates(result) and
// manual magic.
result = getAnAccessInContainer(getARelevantVariable(), _, false).getBasicBlock()
result.getImmediateDominator() = writeNode.getBasicBlock()
)
or
result.getImmediateDominator() = getASuccessorBBThatReadsVar(write)
}
}

Expand Down
8 changes: 8 additions & 0 deletions ...script/ql/test/query-tests/Security/CWE-094/CodeInjection/UnsafeCodeConstruction.expected
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -42,8 +42,11 @@ nodes
| lib/index.js:112:17:112:21 | taint |
| lib/index.js:112:17:112:21 | taint |
| lib/index.js:113:20:113:24 | taint |
| lib/index.js:115:38:115:42 | taint |
| lib/index.js:121:34:121:38 | taint |
| lib/index.js:129:32:129:36 | taint |
| lib/index.js:135:23:135:49 | this.op ... dOption |
| lib/index.js:135:23:135:49 | this.op ... dOption |
| lib/index.js:136:23:136:49 | this.op ... dOption |
| lib/index.js:136:23:136:49 | this.op ... dOption |
| lib/index.js:137:23:137:49 | this.op ... dOption |
Expand Down Expand Up @@ -94,12 +97,16 @@ edges
| lib/index.js:98:30:98:34 | taint | lib/index.js:105:21:105:47 | this.op ... dOption |
| lib/index.js:112:17:112:21 | taint | lib/index.js:113:20:113:24 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:113:20:113:24 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:115:38:115:42 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:115:38:115:42 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:121:34:121:38 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:121:34:121:38 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:129:32:129:36 | taint |
| lib/index.js:112:17:112:21 | taint | lib/index.js:129:32:129:36 | taint |
| lib/index.js:113:20:113:24 | taint | lib/index.js:138:23:138:32 | this.taint |
| lib/index.js:113:20:113:24 | taint | lib/index.js:138:23:138:32 | this.taint |
| lib/index.js:115:38:115:42 | taint | lib/index.js:135:23:135:49 | this.op ... dOption |
| lib/index.js:115:38:115:42 | taint | lib/index.js:135:23:135:49 | this.op ... dOption |
| lib/index.js:121:34:121:38 | taint | lib/index.js:136:23:136:49 | this.op ... dOption |
| lib/index.js:121:34:121:38 | taint | lib/index.js:136:23:136:49 | this.op ... dOption |
| lib/index.js:129:32:129:36 | taint | lib/index.js:137:23:137:49 | this.op ... dOption |
Expand All @@ -114,6 +121,7 @@ edges
| lib/index.js:104:21:104:47 | this.op ... dOption | lib/index.js:86:15:86:19 | taint | lib/index.js:104:21:104:47 | this.op ... dOption | This string concatenation which depends on $@ is later $@. | lib/index.js:86:15:86:19 | taint | library input | lib/index.js:104:10:104:67 | " var ... ing();" | interpreted as code |
| lib/index.js:105:21:105:47 | this.op ... dOption | lib/index.js:86:15:86:19 | taint | lib/index.js:105:21:105:47 | this.op ... dOption | This string concatenation which depends on $@ is later $@. | lib/index.js:86:15:86:19 | taint | library input | lib/index.js:105:10:105:67 | " var ... ing();" | interpreted as code |
| lib/index.js:106:21:106:30 | this.taint | lib/index.js:86:15:86:19 | taint | lib/index.js:106:21:106:30 | this.taint | This string concatenation which depends on $@ is later $@. | lib/index.js:86:15:86:19 | taint | library input | lib/index.js:106:10:106:50 | " var ... ing();" | interpreted as code |
| lib/index.js:135:23:135:49 | this.op ... dOption | lib/index.js:112:17:112:21 | taint | lib/index.js:135:23:135:49 | this.op ... dOption | This string concatenation which depends on $@ is later $@. | lib/index.js:112:17:112:21 | taint | library input | lib/index.js:135:12:135:69 | " var ... ing();" | interpreted as code |
| lib/index.js:136:23:136:49 | this.op ... dOption | lib/index.js:112:17:112:21 | taint | lib/index.js:136:23:136:49 | this.op ... dOption | This string concatenation which depends on $@ is later $@. | lib/index.js:112:17:112:21 | taint | library input | lib/index.js:136:12:136:69 | " var ... ing();" | interpreted as code |
| lib/index.js:137:23:137:49 | this.op ... dOption | lib/index.js:112:17:112:21 | taint | lib/index.js:137:23:137:49 | this.op ... dOption | This string concatenation which depends on $@ is later $@. | lib/index.js:112:17:112:21 | taint | library input | lib/index.js:137:12:137:69 | " var ... ing();" | interpreted as code |
| lib/index.js:138:23:138:32 | this.taint | lib/index.js:112:17:112:21 | taint | lib/index.js:138:23:138:32 | this.taint | This string concatenation which depends on $@ is later $@. | lib/index.js:112:17:112:21 | taint | library input | lib/index.js:138:12:138:52 | " var ... ing();" | interpreted as code |