Skip to content

Commit dc4e361

Browse files
erik-krogherik-krogh
committed
add data-flow steps for arrays
1 parent 8e3cf5c commit dc4e361

2 files changed

Lines changed: 211 additions & 1 deletion

File tree

‎javascript/ql/src/semmle/javascript/Arrays.qll‎

Lines changed: 199 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ private import semmle.javascript.dataflow.InferredTypes
33

44
/**
55
* Classes and predicates for modelling TaintTracking steps for arrays.
6-
*/
6+
*/
77
module ArrayTaintTracking {
88
/**
99
* A taint propagating data flow edge caused by the builtin array functions.
@@ -92,3 +92,201 @@ module ArrayTaintTracking {
9292
pred = call.getAnArgument()
9393
}
9494
}
95+
96+
/**
97+
* Classes and predicates for modelling data-flow for arrays.
98+
*/
99+
private module ArrayDataFlow {
100+
/**
101+
* Gets a pseudo-field representing an element inside an array.
102+
*/
103+
private string arrayElement() { result = "$arrayElement$" }
104+
105+
/**
106+
* A step for storing an element on an array using `arr.push(e)` or `arr.unshift(e)`.
107+
*/
108+
private class ArrayAppendStep extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
109+
ArrayAppendStep() {
110+
this.getMethodName() = "push" or
111+
this.getMethodName() = "unshift"
112+
}
113+
114+
/**
115+
* Holds if `pred` should be stored in the object `succ` under the property `prop`.
116+
*/
117+
override predicate storeStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
118+
prop = arrayElement() and
119+
(pred = this.getAnArgument() or pred = this.getASpreadArgument()) and
120+
succ = this.getReceiver().getALocalSource()
121+
}
122+
}
123+
124+
/**
125+
* A step for reading/writing an element from an array inside a for-loop.
126+
* E.g. a read from `foo[i]` to `bar` in `for(var i = 0; i < arr.length; i++) {bar = foo[i]}`.
127+
*/
128+
private class ArrayIndexingStep extends DataFlow::AdditionalFlowStep, DataFlow::Node {
129+
DataFlow::PropRef read;
130+
131+
ArrayIndexingStep() {
132+
read = this and
133+
forex(InferredType type | type = read.getPropertyNameExpr().flow().analyze().getAType() |
134+
type = TTNumber()
135+
) and
136+
exists(VarAccess i, ExprOrVarDecl init |
137+
i = read.getPropertyNameExpr() and init = any(ForStmt f).getInit()
138+
|
139+
i.getVariable().getADefinition() = init or
140+
i.getVariable().getADefinition().(VariableDeclarator).getDeclStmt() = init
141+
)
142+
}
143+
144+
/**
145+
* Holds if the property `prop` of the object `pred` should be loaded into `succ`.
146+
*/
147+
override predicate loadStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
148+
prop = arrayElement() and
149+
pred = this.(DataFlow::PropRead).getBase() and
150+
succ = this
151+
}
152+
153+
/**
154+
* Holds if `pred` should be stored in the object `succ` under the property `prop`.
155+
*/
156+
override predicate storeStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
157+
prop = arrayElement() and
158+
pred = this.(DataFlow::PropWrite).getRhs() and
159+
this = succ.(DataFlow::SourceNode).getAPropertyWrite()
160+
}
161+
}
162+
163+
/**
164+
* A step for retrieving an element from an array using `.pop()` or `.shift()`.
165+
* E.g. `array.pop()`.
166+
*/
167+
private class ArrayPopStep extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
168+
ArrayPopStep() {
169+
getMethodName() = "pop" or
170+
getMethodName() = "shift"
171+
}
172+
173+
/**
174+
* Holds if the property `prop` of the object `pred` should be loaded into `succ`.
175+
*/
176+
override predicate loadStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
177+
prop = arrayElement() and
178+
pred = this.getReceiver() and
179+
succ = this
180+
}
181+
}
182+
183+
/**
184+
* A step for iterating an array using `map` or `forEach`.
185+
*
186+
* Array elements can be loaded from the array `arr` to `e` in e.g: `arr.forEach(e => ...)`.
187+
*
188+
* And array elements can be stored into a resulting array using `map(...)`.
189+
* E.g. in `arr.map(e => foo)`, the resulting array (`arr.map(e => foo)`) will contain the element `foo`.
190+
*/
191+
private class ArrayIteration extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
192+
ArrayIteration() {
193+
this.getMethodName() = "map" or
194+
this.getMethodName() = "forEach"
195+
}
196+
197+
/**
198+
* Holds if the property `prop` of the object `pred` should be loaded into `succ`.
199+
*/
200+
override predicate loadStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
201+
prop = arrayElement() and
202+
pred = this.getReceiver() and
203+
succ = getCallback(0).getParameter(any(int i | i = 0 or i = 2))
204+
}
205+
206+
/**
207+
* Holds if `pred` should be stored in the object `succ` under the property `prop`.
208+
*/
209+
override predicate storeStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
210+
this.getMethodName() = "map" and
211+
prop = arrayElement() and
212+
pred = this.getCallback(0).getAReturn() and
213+
succ = this
214+
}
215+
}
216+
217+
/**
218+
* A step for creating an array and storing the elements in the array.
219+
*/
220+
private class ArrayCreationStep extends DataFlow::AdditionalFlowStep, DataFlow::Node {
221+
ArrayCreationStep() {
222+
this = DataFlow::globalVarRef("Array").getAPropertyRead("from").getACall() or
223+
this instanceof DataFlow::ArrayCreationNode
224+
}
225+
226+
/**
227+
* Holds if `pred` should be stored in the object `succ` under the property `prop`.
228+
*/
229+
override predicate storeStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
230+
prop = arrayElement() and
231+
succ = this and
232+
(
233+
pred = this.(DataFlow::CallNode).getAnArgument() or
234+
pred = this.(DataFlow::ArrayCreationNode).getAnElement()
235+
)
236+
}
237+
}
238+
239+
/**
240+
* A step modelling that `splice` can insert elements into an array.
241+
* For example in `array.splice(i, del, e)`: if `e` is tainted, then so is `array
242+
*/
243+
private class ArraySpliceStep extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
244+
ArraySpliceStep() { this.getMethodName() = "splice" }
245+
246+
/**
247+
* Holds if `pred` should be stored in the object `succ` under the property `prop`.
248+
*/
249+
override predicate storeStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
250+
prop = arrayElement() and
251+
pred = getArgument(2) and
252+
succ = this.getReceiver().getALocalSource()
253+
}
254+
}
255+
256+
/**
257+
* A step for modelling `concat`.
258+
* For example in `e = arr1.concat(arr2, arr3)`: if any of the `arr` is tainted, then so is `e`.
259+
*/
260+
private class ArrayConcatStep extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
261+
ArrayConcatStep() { this.getMethodName() = "concat" }
262+
263+
/**
264+
* Holds if the property `prop` should be copied from the object `pred` to the object `succ`.
265+
*/
266+
override predicate loadStoreStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
267+
prop = arrayElement() and
268+
(pred = this.getReceiver() or pred = this.getAnArgument()) and
269+
succ = this
270+
}
271+
}
272+
273+
/**
274+
* A step for modelling that elements from an array `arr` also appear in the result from calling `slice`/`splice`/`filter`.
275+
*/
276+
private class ArraySliceStep extends DataFlow::AdditionalFlowStep, DataFlow::MethodCallNode {
277+
ArraySliceStep() {
278+
this.getMethodName() = "slice" or
279+
this.getMethodName() = "splice" or
280+
this.getMethodName() = "filter"
281+
}
282+
283+
/**
284+
* Holds if the property `prop` should be copied from the object `pred` to the object `succ`.
285+
*/
286+
override predicate loadStoreStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
287+
prop = arrayElement() and
288+
pred = this.getReceiver() and
289+
succ = this
290+
}
291+
}
292+
}

‎javascript/ql/test/library-tests/Arrays/DataFlow.expected‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
| arrays.js:2:16:2:23 | "source" | arrays.js:5:8:5:14 | obj.foo |
2+
| arrays.js:2:16:2:23 | "source" | arrays.js:11:10:11:15 | arr[i] |
3+
| arrays.js:2:16:2:23 | "source" | arrays.js:15:27:15:27 | e |
4+
| arrays.js:2:16:2:23 | "source" | arrays.js:16:23:16:23 | e |
5+
| arrays.js:2:16:2:23 | "source" | arrays.js:20:8:20:16 | arr.pop() |
6+
| arrays.js:18:22:18:29 | "source" | arrays.js:18:50:18:50 | e |
7+
| arrays.js:22:25:22:32 | "source" | arrays.js:23:8:23:17 | arr2.pop() |
8+
| arrays.js:25:15:25:22 | "source" | arrays.js:26:8:26:17 | arr3.pop() |
9+
| arrays.js:29:21:29:28 | "source" | arrays.js:30:8:30:17 | arr4.pop() |
10+
| arrays.js:29:21:29:28 | "source" | arrays.js:33:8:33:17 | arr5.pop() |
11+
| arrays.js:29:21:29:28 | "source" | arrays.js:35:8:35:26 | arr5.slice(2).pop() |
12+
| arrays.js:29:21:29:28 | "source" | arrays.js:41:8:41:17 | arr6.pop() |

0 commit comments

Comments
 (0)