Skip to content

Commit 01743de

Browse files
aschackmullaschackmull
authored
Merge pull request #22296 from aschackmull/ruby/regex-via-dataflow
Ruby: Switch regex tracking from TypeTracking to DataFlow.
2 parents 4e31516 + f4b041e commit 01743de

3 files changed

Lines changed: 74 additions & 176 deletions

File tree

‎ruby/ql/lib/change-notes/2026-08-11-regex-tracking.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
---
2+
category: minorAnalysis
3+
---
4+
* The algorithm for tracking regexes has been replaced. This can cause result changes in related queries, for example, `rb/polynomial-redos`.

‎ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowPrivate.qll‎

Lines changed: 33 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -676,26 +676,28 @@ private module Cached {
676676
)
677677
}
678678

679+
private predicate fieldName(string name) {
680+
name = any(InstanceVariable v).getName()
681+
or
682+
name = "@" + any(SetterMethodCall c).getTargetName()
683+
or
684+
// The following equation unfortunately leads to a non-monotonic recursion error:
685+
// name = any(AccessPathToken a).getAnArgument("Field")
686+
// Therefore, we use the following instead to extract the field names from the
687+
// external model data. This, unfortunately, does not included any field names used
688+
// in models defined in QL code.
689+
exists(string input, string output |
690+
ModelOutput::relevantSummaryModel(_, _, input, output, _, _)
691+
|
692+
name = [input, output].regexpFind("(?<=(^|\\.)Field\\[)[^\\]]+(?=\\])", _, _).trim()
693+
)
694+
}
695+
679696
cached
680697
newtype TContent =
681698
TKnownElementContent(ConstantValue cv) { trackKnownValue(cv) } or
682699
TUnknownElementContent() or
683-
TFieldContent(string name) {
684-
name = any(InstanceVariable v).getName()
685-
or
686-
name = "@" + any(SetterMethodCall c).getTargetName()
687-
or
688-
// The following equation unfortunately leads to a non-monotonic recursion error:
689-
// name = any(AccessPathToken a).getAnArgument("Field")
690-
// Therefore, we use the following instead to extract the field names from the
691-
// external model data. This, unfortunately, does not included any field names used
692-
// in models defined in QL code.
693-
exists(string input, string output |
694-
ModelOutput::relevantSummaryModel(_, _, input, output, _, _)
695-
|
696-
name = [input, output].regexpFind("(?<=(^|\\.)Field\\[)[^\\]]+(?=\\])", _, _).trim()
697-
)
698-
} or
700+
TFieldContent(string name) { fieldName(name) } or
699701
deprecated TSplatContent(int i, Boolean shifted) { i in [0 .. 10] } or
700702
deprecated THashSplatContent(ConstantValue::ConstantSymbolValue cv) or
701703
TCapturedVariableContent(VariableCapture::CapturedVariable v) or
@@ -716,12 +718,20 @@ private module Cached {
716718
)
717719
}
718720

721+
cached
722+
int fieldNameBucket(string name) {
723+
exists(int r | name = rank[r](string n | fieldName(n)) and result = r % 30)
724+
}
725+
719726
cached
720727
newtype TContentApprox =
721728
TUnknownElementContentApprox() or
722729
TKnownIntegerElementContentApprox() or
723730
TKnownElementContentApprox(string approx) { approx = approxKnownElementIndex(_) } or
724-
TNonElementContentApprox(Content c) { not c instanceof Content::ElementContent } or
731+
TFieldContentApprox(int bucket) { bucket = fieldNameBucket(_) } or
732+
TNonElementContentApprox(Content c) {
733+
not c instanceof Content::ElementContent and not c instanceof Content::FieldContent
734+
} or
725735
TCapturedVariableContentApprox(VariableCapture::CapturedVariable v)
726736

727737
cached
@@ -2268,6 +2278,10 @@ class ContentApprox extends TContentApprox {
22682278
result = "approximated element " + approx
22692279
)
22702280
or
2281+
exists(int bucket |
2282+
this = TFieldContentApprox(bucket) and result = "field bucket " + bucket.toString()
2283+
)
2284+
or
22712285
exists(Content c |
22722286
this = TNonElementContentApprox(c) and
22732287
result = c.toString()
@@ -2307,6 +2321,8 @@ ContentApprox getContentApprox(Content c) {
23072321
result =
23082322
TKnownElementContentApprox(approxKnownElementIndex(c.(Content::KnownElementContent).getIndex()))
23092323
or
2324+
result = TFieldContentApprox(fieldNameBucket(c.(Content::FieldContent).getName()))
2325+
or
23102326
result = TNonElementContentApprox(c)
23112327
}
23122328

‎ruby/ql/lib/codeql/ruby/regexp/internal/RegExpTracking.qll‎

Lines changed: 37 additions & 159 deletions
Original file line numberDiff line numberDiff line change
@@ -55,175 +55,61 @@ DataFlow::Node stringSink() {
5555
/** Gets a node where regular expressions that flow to the node are used. */
5656
DataFlow::Node regSink() { result = any(RegexExecution exec).getRegex() }
5757

58-
private signature module TypeTrackInputSig {
59-
DataFlow::LocalSourceNode start(TypeTracker t, DataFlow::Node start);
58+
private module RegexConfig implements DataFlow::StateConfigSig {
59+
private newtype TFlowState =
60+
TStringState() or
61+
TRegExpState()
6062

61-
predicate end(DataFlow::Node n);
63+
class FlowState = TFlowState;
6264

63-
predicate additionalStep(DataFlow::Node nodeFrom, DataFlow::LocalSourceNode nodeTo);
64-
}
65-
66-
/**
67-
* Provides a version of type tracking where we first prune for reachable nodes,
68-
* before doing the type tracking computation.
69-
*/
70-
private module PrunedTypeTrack<TypeTrackInputSig Input> {
71-
private predicate additionalStep(
72-
DataFlow::LocalSourceNode nodeFrom, DataFlow::LocalSourceNode nodeTo
73-
) {
74-
Input::additionalStep(nodeFrom.getALocalUse(), nodeTo)
75-
}
76-
77-
/** Gets a node that is forwards reachable by type-tracking. */
78-
pragma[nomagic]
79-
private DataFlow::LocalSourceNode forward(TypeTracker t) {
80-
result = Input::start(t, _)
65+
predicate isSource(DataFlow::Node source, FlowState state) {
66+
state = TStringState() and source = strStart()
8167
or
82-
exists(TypeTracker t2 | result = forward(t2).track(t2, t))
83-
or
84-
exists(TypeTracker t2 | t2 = t.continue() | additionalStep(forward(t2), result))
68+
state = TRegExpState() and source = regStart()
8569
}
8670

87-
bindingset[result, tbt]
88-
pragma[inline_late]
89-
pragma[noopt]
90-
private DataFlow::LocalSourceNode forwardLateInline(TypeBackTracker tbt) {
91-
exists(TypeTracker tt |
92-
result = forward(tt) and
93-
tt = tbt.getACompatibleTypeTracker()
94-
)
71+
predicate isSink(DataFlow::Node sink, FlowState state) {
72+
state = TStringState() and sink = stringSink()
73+
or
74+
state = TRegExpState() and sink = regSink()
9575
}
9676

97-
/** Gets a node that is backwards reachable by type-tracking. */
98-
pragma[nomagic]
99-
private DataFlow::LocalSourceNode backwards(TypeBackTracker t) {
100-
result = forwardLateInline(t) and
77+
predicate isAdditionalFlowStep(
78+
DataFlow::Node node1, FlowState state1, DataFlow::Node node2, FlowState state2
79+
) {
80+
regFromString(node1, node2) and state1 = TStringState() and state2 = TRegExpState()
81+
or
82+
state1 = TStringState() and
83+
state2 = TStringState() and
10184
(
102-
t.start() and
103-
Input::end(result.getALocalUse())
85+
// include taint flow through `String` summaries
86+
TaintTrackingPrivate::summaryThroughStepTaint(node1, node2, any(String::SummarizedCallable c))
10487
or
105-
exists(TypeBackTracker t2 | result = backwards(t2).backtrack(t2, t))
88+
// string concatenations, and
89+
exists(CfgNodes::ExprNodes::OperationCfgNode op |
90+
op = node2.asExpr() and
91+
op.getAnOperand() = node1.asExpr() and
92+
op.getExpr().(Ast::BinaryOperation).getOperator() = "+"
93+
)
10694
or
107-
exists(TypeBackTracker t2 | t2 = t.continue() | additionalStep(result, backwards(t2)))
108-
)
109-
}
110-
111-
bindingset[result, tt]
112-
pragma[inline_late]
113-
pragma[noopt]
114-
private DataFlow::LocalSourceNode backwardsInlineLate(TypeTracker tt) {
115-
exists(TypeBackTracker tbt |
116-
result = backwards(tbt) and
117-
tt = tbt.getACompatibleTypeTracker()
118-
)
119-
}
120-
121-
/** Holds if `n` is forwards and backwards reachable with type tracker `t`. */
122-
pragma[nomagic]
123-
private predicate reached(DataFlow::LocalSourceNode n, TypeTracker t) {
124-
n = forward(t) and
125-
n = backwardsInlineLate(t)
126-
}
127-
128-
pragma[nomagic]
129-
private TypeTracker stepReached(
130-
TypeTracker t, DataFlow::LocalSourceNode nodeFrom, DataFlow::LocalSourceNode nodeTo
131-
) {
132-
exists(StepSummary summary |
133-
step(nodeFrom, nodeTo, summary) and
134-
reached(nodeFrom, t) and
135-
reached(nodeTo, result) and
136-
result = append(t, summary)
95+
// string interpolations
96+
node1.asExpr() =
97+
node2.asExpr().(CfgNodes::ExprNodes::StringlikeLiteralCfgNode).getAComponent()
13798
)
138-
or
139-
additionalStep(nodeFrom, nodeTo) and
140-
reached(nodeFrom, pragma[only_bind_into](t)) and
141-
reached(nodeTo, pragma[only_bind_into](t)) and
142-
result = t.continue()
14399
}
144100

145-
/** Gets a node that has been tracked from the start node `start`. */
146-
DataFlow::LocalSourceNode track(DataFlow::Node start, TypeTracker t) {
147-
t.start() and
148-
result = Input::start(t, start) and
149-
reached(result, t)
150-
or
151-
exists(TypeTracker t2 | t = stepReached(t2, track(start, t2), result))
152-
}
101+
int accessPathLimit() { result = 1 }
153102
}
154103

155-
/** Holds if `inputStr` is compiled to a regular expression that is returned at `call`. */
156-
pragma[nomagic]
157-
private predicate regFromString(DataFlow::LocalSourceNode inputStr, DataFlow::CallNode call) {
158-
exists(DataFlow::Node mid |
159-
inputStr.flowsTo(mid) and
160-
call = API::getTopLevelMember("Regexp").getAMethodCall(["compile", "new"]) and
161-
mid = call.getArgument(0)
162-
)
163-
}
104+
private module RegexTracking = DataFlow::GlobalWithState<RegexConfig>;
164105

165-
private module StringTypeTrackInput implements TypeTrackInputSig {
166-
DataFlow::LocalSourceNode start(TypeTracker t, DataFlow::Node start) {
167-
start = strStart() and t.start() and result = start
168-
}
169-
170-
predicate end(DataFlow::Node n) {
171-
n = stringSink() or
172-
regFromString(n, _)
173-
}
174-
175-
predicate additionalStep(DataFlow::Node nodeFrom, DataFlow::LocalSourceNode nodeTo) {
176-
// include taint flow through `String` summaries
177-
TaintTrackingPrivate::summaryThroughStepTaint(nodeFrom, nodeTo,
178-
any(String::SummarizedCallable c))
179-
or
180-
// string concatenations, and
181-
exists(CfgNodes::ExprNodes::OperationCfgNode op |
182-
op = nodeTo.asExpr() and
183-
op.getAnOperand() = nodeFrom.asExpr() and
184-
op.getExpr().(Ast::BinaryOperation).getOperator() = "+"
185-
)
186-
or
187-
// string interpolations
188-
nodeFrom.asExpr() =
189-
nodeTo.asExpr().(CfgNodes::ExprNodes::StringlikeLiteralCfgNode).getAComponent()
190-
}
191-
}
192-
193-
/**
194-
* Gets a node that has been tracked from the string constant `start` to some node.
195-
* This is used to figure out where `start` is evaluated as a regular expression against an input string,
196-
* or where `start` is compiled into a regular expression.
197-
*/
198-
private predicate trackStrings = PrunedTypeTrack<StringTypeTrackInput>::track/2;
199-
200-
/** Holds if `strConst` flows to a regex compilation (tracked by `t`), where the resulting regular expression is stored in `reg`. */
106+
/** Holds if `inputStr` is compiled to a regular expression that is returned at `call`. */
201107
pragma[nomagic]
202-
private predicate regFromStringStart(DataFlow::Node strConst, TypeTracker t, DataFlow::CallNode reg) {
203-
regFromString(trackStrings(strConst, t), reg) and
204-
exists(t.continue())
108+
private predicate regFromString(DataFlow::Node inputStr, DataFlow::CallNode call) {
109+
call = API::getTopLevelMember("Regexp").getAMethodCall(["compile", "new"]) and
110+
inputStr = call.getArgument(0)
205111
}
206112

207-
private module RegTypeTrackInput implements TypeTrackInputSig {
208-
DataFlow::LocalSourceNode start(TypeTracker t, DataFlow::Node start) {
209-
start = regStart() and
210-
t.start() and
211-
result = start
212-
or
213-
regFromStringStart(start, t, result)
214-
}
215-
216-
predicate end(DataFlow::Node n) { n = regSink() }
217-
218-
predicate additionalStep(DataFlow::Node nodeFrom, DataFlow::LocalSourceNode nodeTo) { none() }
219-
}
220-
221-
/**
222-
* Gets a node that has been tracked from the regular expression `start` to some node.
223-
* This is used to figure out where `start` is executed against an input string.
224-
*/
225-
private predicate trackRegs = PrunedTypeTrack<RegTypeTrackInput>::track/2;
226-
227113
/** Gets a node that references a regular expression. */
228114
private DataFlow::LocalSourceNode trackRegexpType(TypeTracker t) {
229115
t.start() and
@@ -240,12 +126,4 @@ DataFlow::Node trackRegexpType() { trackRegexpType(TypeTracker::end()).flowsTo(r
240126

241127
/** Gets a node holding a value for the regular expression that is evaluated at `re`. */
242128
cached
243-
DataFlow::Node regExpSource(DataFlow::Node re) {
244-
exists(DataFlow::LocalSourceNode end | end = trackStrings(result, TypeTracker::end()) |
245-
end.getALocalUse() = re and re = stringSink()
246-
)
247-
or
248-
exists(DataFlow::LocalSourceNode end | end = trackRegs(result, TypeTracker::end()) |
249-
end.getALocalUse() = re and re = regSink()
250-
)
251-
}
129+
DataFlow::Node regExpSource(DataFlow::Node re) { RegexTracking::flow(result, re) }

0 commit comments

Comments
 (0)