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