1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #define DEBUG false // STOPSHIP if true
17 #include "Log.h"
18
19 #include "frameworks/base/cmds/statsd/src/statsd_config.pb.h"
20 #include "matchers/LogMatchingTracker.h"
21 #include "matchers/matcher_util.h"
22 #include "stats_util.h"
23
24 using std::set;
25 using std::string;
26 using std::vector;
27
28 namespace android {
29 namespace os {
30 namespace statsd {
31
combinationMatch(const vector<int> & children,const LogicalOperation & operation,const vector<MatchingState> & matcherResults)32 bool combinationMatch(const vector<int>& children, const LogicalOperation& operation,
33 const vector<MatchingState>& matcherResults) {
34 bool matched;
35 switch (operation) {
36 case LogicalOperation::AND: {
37 matched = true;
38 for (const int childIndex : children) {
39 if (matcherResults[childIndex] != MatchingState::kMatched) {
40 matched = false;
41 break;
42 }
43 }
44 break;
45 }
46 case LogicalOperation::OR: {
47 matched = false;
48 for (const int childIndex : children) {
49 if (matcherResults[childIndex] == MatchingState::kMatched) {
50 matched = true;
51 break;
52 }
53 }
54 break;
55 }
56 case LogicalOperation::NOT:
57 matched = matcherResults[children[0]] == MatchingState::kNotMatched;
58 break;
59 case LogicalOperation::NAND:
60 matched = false;
61 for (const int childIndex : children) {
62 if (matcherResults[childIndex] != MatchingState::kMatched) {
63 matched = true;
64 break;
65 }
66 }
67 break;
68 case LogicalOperation::NOR:
69 matched = true;
70 for (const int childIndex : children) {
71 if (matcherResults[childIndex] == MatchingState::kMatched) {
72 matched = false;
73 break;
74 }
75 }
76 break;
77 case LogicalOperation::LOGICAL_OPERATION_UNSPECIFIED:
78 matched = false;
79 break;
80 }
81 return matched;
82 }
83
tryMatchString(const UidMap & uidMap,const FieldValue & fieldValue,const string & str_match)84 bool tryMatchString(const UidMap& uidMap, const FieldValue& fieldValue, const string& str_match) {
85 if (isAttributionUidField(fieldValue) || isUidField(fieldValue)) {
86 int uid = fieldValue.mValue.int_value;
87 auto aidIt = UidMap::sAidToUidMapping.find(str_match);
88 if (aidIt != UidMap::sAidToUidMapping.end()) {
89 return ((int)aidIt->second) == uid;
90 }
91 std::set<string> packageNames = uidMap.getAppNamesFromUid(uid, true /* normalize*/);
92 return packageNames.find(str_match) != packageNames.end();
93 } else if (fieldValue.mValue.getType() == STRING) {
94 return fieldValue.mValue.str_value == str_match;
95 }
96 return false;
97 }
98
matchesSimple(const UidMap & uidMap,const FieldValueMatcher & matcher,const vector<FieldValue> & values,int start,int end,int depth)99 bool matchesSimple(const UidMap& uidMap, const FieldValueMatcher& matcher,
100 const vector<FieldValue>& values, int start, int end, int depth) {
101 if (depth > 2) {
102 ALOGE("Depth > 3 not supported");
103 return false;
104 }
105
106 if (start >= end) {
107 return false;
108 }
109
110 // Filter by entry field first
111 int newStart = -1;
112 int newEnd = end;
113 // because the fields are naturally sorted in the DFS order. we can safely
114 // break when pos is larger than the one we are searching for.
115 for (int i = start; i < end; i++) {
116 int pos = values[i].mField.getPosAtDepth(depth);
117 if (pos == matcher.field()) {
118 if (newStart == -1) {
119 newStart = i;
120 }
121 newEnd = i + 1;
122 } else if (pos > matcher.field()) {
123 break;
124 }
125 }
126
127 // Now we have zoomed in to a new range
128 start = newStart;
129 end = newEnd;
130
131 if (start == -1) {
132 // No such field found.
133 return false;
134 }
135
136 vector<pair<int, int>> ranges; // the ranges are for matching ANY position
137 if (matcher.has_position()) {
138 // Repeated fields position is stored as a node in the path.
139 depth++;
140 if (depth > 2) {
141 return false;
142 }
143 switch (matcher.position()) {
144 case Position::FIRST: {
145 for (int i = start; i < end; i++) {
146 int pos = values[i].mField.getPosAtDepth(depth);
147 if (pos != 1) {
148 // Again, the log elements are stored in sorted order. so
149 // once the position is > 1, we break;
150 end = i;
151 break;
152 }
153 }
154 ranges.push_back(std::make_pair(start, end));
155 break;
156 }
157 case Position::LAST: {
158 // move the starting index to the first LAST field at the depth.
159 for (int i = start; i < end; i++) {
160 if (values[i].mField.isLastPos(depth)) {
161 start = i;
162 break;
163 }
164 }
165 ranges.push_back(std::make_pair(start, end));
166 break;
167 }
168 case Position::ANY: {
169 // ANY means all the children matchers match in any of the sub trees, it's a match
170 newStart = start;
171 newEnd = end;
172 // Here start is guaranteed to be a valid index.
173 int currentPos = values[start].mField.getPosAtDepth(depth);
174 // Now find all sub trees ranges.
175 for (int i = start; i < end; i++) {
176 int newPos = values[i].mField.getPosAtDepth(depth);
177 if (newPos != currentPos) {
178 ranges.push_back(std::make_pair(newStart, i));
179 newStart = i;
180 currentPos = newPos;
181 }
182 }
183 ranges.push_back(std::make_pair(newStart, end));
184 break;
185 }
186 case Position::ALL:
187 ALOGE("Not supported: field matcher with ALL position.");
188 break;
189 case Position::POSITION_UNKNOWN:
190 break;
191 }
192 } else {
193 // No position
194 ranges.push_back(std::make_pair(start, end));
195 }
196 // start and end are still pointing to the matched range.
197 switch (matcher.value_matcher_case()) {
198 case FieldValueMatcher::kMatchesTuple: {
199 ++depth;
200 // If any range matches all matchers, good.
201 for (const auto& range : ranges) {
202 bool matched = true;
203 for (const auto& subMatcher : matcher.matches_tuple().field_value_matcher()) {
204 if (!matchesSimple(uidMap, subMatcher, values, range.first, range.second,
205 depth)) {
206 matched = false;
207 break;
208 }
209 }
210 if (matched) return true;
211 }
212 return false;
213 }
214 // Finally, we get to the point of real value matching.
215 // If the field matcher ends with ANY, then we have [start, end) range > 1.
216 // In the following, we should return true, when ANY of the values matches.
217 case FieldValueMatcher::ValueMatcherCase::kEqBool: {
218 for (int i = start; i < end; i++) {
219 if ((values[i].mValue.getType() == INT &&
220 (values[i].mValue.int_value != 0) == matcher.eq_bool()) ||
221 (values[i].mValue.getType() == LONG &&
222 (values[i].mValue.long_value != 0) == matcher.eq_bool())) {
223 return true;
224 }
225 }
226 return false;
227 }
228 case FieldValueMatcher::ValueMatcherCase::kEqString: {
229 for (int i = start; i < end; i++) {
230 if (tryMatchString(uidMap, values[i], matcher.eq_string())) {
231 return true;
232 }
233 }
234 return false;
235 }
236 case FieldValueMatcher::ValueMatcherCase::kNeqAnyString: {
237 const auto& str_list = matcher.neq_any_string();
238 for (int i = start; i < end; i++) {
239 bool notEqAll = true;
240 for (const auto& str : str_list.str_value()) {
241 if (tryMatchString(uidMap, values[i], str)) {
242 notEqAll = false;
243 break;
244 }
245 }
246 if (notEqAll) {
247 return true;
248 }
249 }
250 return false;
251 }
252 case FieldValueMatcher::ValueMatcherCase::kEqAnyString: {
253 const auto& str_list = matcher.eq_any_string();
254 for (int i = start; i < end; i++) {
255 for (const auto& str : str_list.str_value()) {
256 if (tryMatchString(uidMap, values[i], str)) {
257 return true;
258 }
259 }
260 }
261 return false;
262 }
263 case FieldValueMatcher::ValueMatcherCase::kEqInt: {
264 for (int i = start; i < end; i++) {
265 if (values[i].mValue.getType() == INT &&
266 (matcher.eq_int() == values[i].mValue.int_value)) {
267 return true;
268 }
269 // eq_int covers both int and long.
270 if (values[i].mValue.getType() == LONG &&
271 (matcher.eq_int() == values[i].mValue.long_value)) {
272 return true;
273 }
274 }
275 return false;
276 }
277 case FieldValueMatcher::ValueMatcherCase::kLtInt: {
278 for (int i = start; i < end; i++) {
279 if (values[i].mValue.getType() == INT &&
280 (values[i].mValue.int_value < matcher.lt_int())) {
281 return true;
282 }
283 // lt_int covers both int and long.
284 if (values[i].mValue.getType() == LONG &&
285 (values[i].mValue.long_value < matcher.lt_int())) {
286 return true;
287 }
288 }
289 return false;
290 }
291 case FieldValueMatcher::ValueMatcherCase::kGtInt: {
292 for (int i = start; i < end; i++) {
293 if (values[i].mValue.getType() == INT &&
294 (values[i].mValue.int_value > matcher.gt_int())) {
295 return true;
296 }
297 // gt_int covers both int and long.
298 if (values[i].mValue.getType() == LONG &&
299 (values[i].mValue.long_value > matcher.gt_int())) {
300 return true;
301 }
302 }
303 return false;
304 }
305 case FieldValueMatcher::ValueMatcherCase::kLtFloat: {
306 for (int i = start; i < end; i++) {
307 if (values[i].mValue.getType() == FLOAT &&
308 (values[i].mValue.float_value < matcher.lt_float())) {
309 return true;
310 }
311 }
312 return false;
313 }
314 case FieldValueMatcher::ValueMatcherCase::kGtFloat: {
315 for (int i = start; i < end; i++) {
316 if (values[i].mValue.getType() == FLOAT &&
317 (values[i].mValue.float_value > matcher.gt_float())) {
318 return true;
319 }
320 }
321 return false;
322 }
323 case FieldValueMatcher::ValueMatcherCase::kLteInt: {
324 for (int i = start; i < end; i++) {
325 if (values[i].mValue.getType() == INT &&
326 (values[i].mValue.int_value <= matcher.lte_int())) {
327 return true;
328 }
329 // lte_int covers both int and long.
330 if (values[i].mValue.getType() == LONG &&
331 (values[i].mValue.long_value <= matcher.lte_int())) {
332 return true;
333 }
334 }
335 return false;
336 }
337 case FieldValueMatcher::ValueMatcherCase::kGteInt: {
338 for (int i = start; i < end; i++) {
339 if (values[i].mValue.getType() == INT &&
340 (values[i].mValue.int_value >= matcher.gte_int())) {
341 return true;
342 }
343 // gte_int covers both int and long.
344 if (values[i].mValue.getType() == LONG &&
345 (values[i].mValue.long_value >= matcher.gte_int())) {
346 return true;
347 }
348 }
349 return false;
350 }
351 default:
352 return false;
353 }
354 }
355
matchesSimple(const UidMap & uidMap,const SimpleAtomMatcher & simpleMatcher,const LogEvent & event)356 bool matchesSimple(const UidMap& uidMap, const SimpleAtomMatcher& simpleMatcher,
357 const LogEvent& event) {
358 if (event.GetTagId() != simpleMatcher.atom_id()) {
359 return false;
360 }
361
362 for (const auto& matcher : simpleMatcher.field_value_matcher()) {
363 if (!matchesSimple(uidMap, matcher, event.getValues(), 0, event.getValues().size(), 0)) {
364 return false;
365 }
366 }
367 return true;
368 }
369
370 } // namespace statsd
371 } // namespace os
372 } // namespace android
373