Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 1 | // Copyright (C) 2017 The Android Open Source Project |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 15 | #include "src/anomaly/AnomalyTracker.h" |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 16 | |
| 17 | #include <gtest/gtest.h> |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 18 | #include <math.h> |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 19 | #include <stdio.h> |
Muhammad Qureshi | b635b3a | 2020-04-22 20:57:41 -0700 | [diff] [blame] | 20 | |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 21 | #include <vector> |
| 22 | |
Muhammad Qureshi | b635b3a | 2020-04-22 20:57:41 -0700 | [diff] [blame] | 23 | #include "tests/statsd_test_util.h" |
| 24 | |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 25 | using namespace testing; |
| 26 | using android::sp; |
| 27 | using std::set; |
| 28 | using std::unordered_map; |
| 29 | using std::vector; |
| 30 | |
| 31 | #ifdef __ANDROID__ |
| 32 | |
| 33 | namespace android { |
| 34 | namespace os { |
| 35 | namespace statsd { |
| 36 | |
Yangster-mac | 94e197c | 2018-01-02 16:03:03 -0800 | [diff] [blame] | 37 | const ConfigKey kConfigKey(0, 12345); |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 38 | |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 39 | MetricDimensionKey getMockMetricDimensionKey(int key, string value) { |
Yao Chen | 8a8d16c | 2018-02-08 14:50:40 -0800 | [diff] [blame] | 40 | int pos[] = {key, 0, 0}; |
| 41 | HashableDimensionKey dim; |
| 42 | dim.addValue(FieldValue(Field(1, pos, 0), Value(value))); |
| 43 | return MetricDimensionKey(dim, DEFAULT_DIMENSION_KEY); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 44 | } |
| 45 | |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 46 | void AddValueToBucket(const std::vector<std::pair<MetricDimensionKey, long>>& key_value_pair_list, |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 47 | std::shared_ptr<DimToValMap> bucket) { |
| 48 | for (auto itr = key_value_pair_list.begin(); itr != key_value_pair_list.end(); itr++) { |
| 49 | (*bucket)[itr->first] += itr->second; |
| 50 | } |
| 51 | } |
| 52 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 53 | std::shared_ptr<DimToValMap> MockBucket( |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 54 | const std::vector<std::pair<MetricDimensionKey, long>>& key_value_pair_list) { |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 55 | std::shared_ptr<DimToValMap> bucket = std::make_shared<DimToValMap>(); |
| 56 | AddValueToBucket(key_value_pair_list, bucket); |
| 57 | return bucket; |
| 58 | } |
| 59 | |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 60 | // Returns the value, for the given key, in that bucket, or 0 if not present. |
| 61 | int64_t getBucketValue(const std::shared_ptr<DimToValMap>& bucket, |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 62 | const MetricDimensionKey& key) { |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 63 | const auto& itr = bucket->find(key); |
| 64 | if (itr != bucket->end()) { |
| 65 | return itr->second; |
| 66 | } |
| 67 | return 0; |
| 68 | } |
| 69 | |
| 70 | // Returns true if keys in trueList are detected as anomalies and keys in falseList are not. |
| 71 | bool detectAnomaliesPass(AnomalyTracker& tracker, |
| 72 | const int64_t& bucketNum, |
| 73 | const std::shared_ptr<DimToValMap>& currentBucket, |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 74 | const std::set<const MetricDimensionKey>& trueList, |
| 75 | const std::set<const MetricDimensionKey>& falseList) { |
Chih-Hung Hsieh | a1b644e | 2018-12-11 11:09:20 -0800 | [diff] [blame] | 76 | for (const MetricDimensionKey& key : trueList) { |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 77 | if (!tracker.detectAnomaly(bucketNum, key, getBucketValue(currentBucket, key))) { |
| 78 | return false; |
| 79 | } |
| 80 | } |
Chih-Hung Hsieh | a1b644e | 2018-12-11 11:09:20 -0800 | [diff] [blame] | 81 | for (const MetricDimensionKey& key : falseList) { |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 82 | if (tracker.detectAnomaly(bucketNum, key, getBucketValue(currentBucket, key))) { |
| 83 | return false; |
| 84 | } |
| 85 | } |
| 86 | return true; |
| 87 | } |
| 88 | |
| 89 | // Calls tracker.detectAndDeclareAnomaly on each key in the bucket. |
| 90 | void detectAndDeclareAnomalies(AnomalyTracker& tracker, |
| 91 | const int64_t& bucketNum, |
| 92 | const std::shared_ptr<DimToValMap>& bucket, |
| 93 | const int64_t& eventTimestamp) { |
| 94 | for (const auto& kv : *bucket) { |
Yao Chen | 4ce0729 | 2019-02-13 13:06:36 -0800 | [diff] [blame] | 95 | tracker.detectAndDeclareAnomaly(eventTimestamp, bucketNum, 0 /*metric_id*/, kv.first, |
| 96 | kv.second); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 97 | } |
| 98 | } |
| 99 | |
| 100 | // Asserts that the refractory time for each key in timestamps is the corresponding |
| 101 | // timestamp (in ns) + refractoryPeriodSec. |
| 102 | // If a timestamp value is negative, instead asserts that the refractory period is inapplicable |
| 103 | // (either non-existant or already past). |
| 104 | void checkRefractoryTimes(AnomalyTracker& tracker, |
| 105 | const int64_t& currTimestampNs, |
| 106 | const int32_t& refractoryPeriodSec, |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 107 | const std::unordered_map<MetricDimensionKey, int64_t>& timestamps) { |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 108 | for (const auto& kv : timestamps) { |
| 109 | if (kv.second < 0) { |
| 110 | // Make sure that, if there is a refractory period, it is already past. |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 111 | EXPECT_LT(tracker.getRefractoryPeriodEndsSec(kv.first) * NS_PER_SEC, |
| 112 | (uint64_t)currTimestampNs) |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 113 | << "Failure was at currTimestampNs " << currTimestampNs; |
| 114 | } else { |
| 115 | EXPECT_EQ(tracker.getRefractoryPeriodEndsSec(kv.first), |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 116 | std::ceil(1.0 * kv.second / NS_PER_SEC) + refractoryPeriodSec) |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 117 | << "Failure was at currTimestampNs " << currTimestampNs; |
| 118 | } |
| 119 | } |
| 120 | } |
| 121 | |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 122 | TEST(AnomalyTrackerTest, TestConsecutiveBuckets) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 123 | const int64_t bucketSizeNs = 30 * NS_PER_SEC; |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 124 | const int32_t refractoryPeriodSec = 2 * bucketSizeNs / NS_PER_SEC; |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 125 | Alert alert; |
Yangster-mac | a7fb12d | 2018-01-03 17:17:20 -0800 | [diff] [blame] | 126 | alert.set_num_buckets(3); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 127 | alert.set_refractory_period_secs(refractoryPeriodSec); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 128 | alert.set_trigger_if_sum_gt(2); |
| 129 | |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 130 | AnomalyTracker anomalyTracker(alert, kConfigKey); |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 131 | MetricDimensionKey keyA = getMockMetricDimensionKey(1, "a"); |
| 132 | MetricDimensionKey keyB = getMockMetricDimensionKey(1, "b"); |
| 133 | MetricDimensionKey keyC = getMockMetricDimensionKey(1, "c"); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 134 | |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 135 | int64_t eventTimestamp0 = 10 * NS_PER_SEC; |
| 136 | int64_t eventTimestamp1 = bucketSizeNs + 11 * NS_PER_SEC; |
| 137 | int64_t eventTimestamp2 = 2 * bucketSizeNs + 12 * NS_PER_SEC; |
| 138 | int64_t eventTimestamp3 = 3 * bucketSizeNs + 13 * NS_PER_SEC; |
| 139 | int64_t eventTimestamp4 = 4 * bucketSizeNs + 14 * NS_PER_SEC; |
| 140 | int64_t eventTimestamp5 = 5 * bucketSizeNs + 5 * NS_PER_SEC; |
| 141 | int64_t eventTimestamp6 = 6 * bucketSizeNs + 16 * NS_PER_SEC; |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 142 | |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 143 | std::shared_ptr<DimToValMap> bucket0 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}}); |
| 144 | std::shared_ptr<DimToValMap> bucket1 = MockBucket({{keyA, 1}}); |
| 145 | std::shared_ptr<DimToValMap> bucket2 = MockBucket({{keyB, 1}}); |
| 146 | std::shared_ptr<DimToValMap> bucket3 = MockBucket({{keyA, 2}}); |
| 147 | std::shared_ptr<DimToValMap> bucket4 = MockBucket({{keyB, 5}}); |
| 148 | std::shared_ptr<DimToValMap> bucket5 = MockBucket({{keyA, 2}}); |
| 149 | std::shared_ptr<DimToValMap> bucket6 = MockBucket({{keyA, 2}}); |
| 150 | |
| 151 | // Start time with no events. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 152 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0u); |
| 153 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 154 | |
| 155 | // Event from bucket #0 occurs. |
| 156 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 0, bucket0, {}, {keyA, keyB, keyC})); |
| 157 | detectAndDeclareAnomalies(anomalyTracker, 0, bucket0, eventTimestamp1); |
| 158 | checkRefractoryTimes(anomalyTracker, eventTimestamp0, refractoryPeriodSec, |
| 159 | {{keyA, -1}, {keyB, -1}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 160 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 161 | // Adds past bucket #0 |
| 162 | anomalyTracker.addPastBucket(bucket0, 0); |
| 163 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 164 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL); |
| 165 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL); |
| 166 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 167 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 168 | |
| 169 | // Event from bucket #1 occurs. |
| 170 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 1, bucket1, {}, {keyA, keyB, keyC})); |
| 171 | detectAndDeclareAnomalies(anomalyTracker, 1, bucket1, eventTimestamp1); |
| 172 | checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec, |
| 173 | {{keyA, -1}, {keyB, -1}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 174 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 175 | // Adds past bucket #0 again. The sum does not change. |
| 176 | anomalyTracker.addPastBucket(bucket0, 0); |
| 177 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 178 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL); |
| 179 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL); |
| 180 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 181 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 182 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 1, bucket1, {}, {keyA, keyB, keyC})); |
| 183 | detectAndDeclareAnomalies(anomalyTracker, 1, bucket1, eventTimestamp1 + 1); |
| 184 | checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec, |
| 185 | {{keyA, -1}, {keyB, -1}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 186 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 187 | // Adds past bucket #1. |
| 188 | anomalyTracker.addPastBucket(bucket1, 1); |
| 189 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L); |
| 190 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 191 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL); |
| 192 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL); |
| 193 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 194 | |
| 195 | // Event from bucket #2 occurs. New anomaly on keyB. |
| 196 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 2, bucket2, {keyB}, {keyA, keyC})); |
| 197 | detectAndDeclareAnomalies(anomalyTracker, 2, bucket2, eventTimestamp2); |
| 198 | checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec, |
| 199 | {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 200 | |
| 201 | // Adds past bucket #1 again. Nothing changes. |
| 202 | anomalyTracker.addPastBucket(bucket1, 1); |
| 203 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L); |
| 204 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 205 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL); |
| 206 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL); |
| 207 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 208 | // Event from bucket #2 occurs (again). |
| 209 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 2, bucket2, {keyB}, {keyA, keyC})); |
| 210 | detectAndDeclareAnomalies(anomalyTracker, 2, bucket2, eventTimestamp2 + 1); |
| 211 | checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec, |
| 212 | {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 213 | |
| 214 | // Adds past bucket #2. |
| 215 | anomalyTracker.addPastBucket(bucket2, 2); |
| 216 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 2L); |
| 217 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 218 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL); |
| 219 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 220 | |
| 221 | // Event from bucket #3 occurs. New anomaly on keyA. |
| 222 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 3, bucket3, {keyA}, {keyB, keyC})); |
| 223 | detectAndDeclareAnomalies(anomalyTracker, 3, bucket3, eventTimestamp3); |
| 224 | checkRefractoryTimes(anomalyTracker, eventTimestamp3, refractoryPeriodSec, |
| 225 | {{keyA, eventTimestamp3}, {keyB, eventTimestamp2}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 226 | |
| 227 | // Adds bucket #3. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 228 | anomalyTracker.addPastBucket(bucket3, 3L); |
| 229 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 3L); |
| 230 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 231 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL); |
| 232 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 233 | |
| 234 | // Event from bucket #4 occurs. New anomaly on keyB. |
| 235 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 4, bucket4, {keyB}, {keyA, keyC})); |
| 236 | detectAndDeclareAnomalies(anomalyTracker, 4, bucket4, eventTimestamp4); |
| 237 | checkRefractoryTimes(anomalyTracker, eventTimestamp4, refractoryPeriodSec, |
| 238 | {{keyA, eventTimestamp3}, {keyB, eventTimestamp4}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 239 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 240 | // Adds bucket #4. |
| 241 | anomalyTracker.addPastBucket(bucket4, 4); |
| 242 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 4L); |
| 243 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 244 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 245 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 5LL); |
| 246 | |
| 247 | // Event from bucket #5 occurs. New anomaly on keyA, which is still in refractory. |
| 248 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 5, bucket5, {keyA, keyB}, {keyC})); |
| 249 | detectAndDeclareAnomalies(anomalyTracker, 5, bucket5, eventTimestamp5); |
| 250 | checkRefractoryTimes(anomalyTracker, eventTimestamp5, refractoryPeriodSec, |
| 251 | {{keyA, eventTimestamp3}, {keyB, eventTimestamp4}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 252 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 253 | // Adds bucket #5. |
| 254 | anomalyTracker.addPastBucket(bucket5, 5); |
| 255 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 5L); |
| 256 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 257 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 258 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 5LL); |
| 259 | |
| 260 | // Event from bucket #6 occurs. New anomaly on keyA, which is now out of refractory. |
| 261 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 6, bucket6, {keyA, keyB}, {keyC})); |
| 262 | detectAndDeclareAnomalies(anomalyTracker, 6, bucket6, eventTimestamp6); |
| 263 | checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec, |
| 264 | {{keyA, eventTimestamp6}, {keyB, eventTimestamp4}, {keyC, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 265 | } |
| 266 | |
| 267 | TEST(AnomalyTrackerTest, TestSparseBuckets) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 268 | const int64_t bucketSizeNs = 30 * NS_PER_SEC; |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 269 | const int32_t refractoryPeriodSec = 2 * bucketSizeNs / NS_PER_SEC; |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 270 | Alert alert; |
Yangster-mac | a7fb12d | 2018-01-03 17:17:20 -0800 | [diff] [blame] | 271 | alert.set_num_buckets(3); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 272 | alert.set_refractory_period_secs(refractoryPeriodSec); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 273 | alert.set_trigger_if_sum_gt(2); |
| 274 | |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 275 | AnomalyTracker anomalyTracker(alert, kConfigKey); |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 276 | MetricDimensionKey keyA = getMockMetricDimensionKey(1, "a"); |
| 277 | MetricDimensionKey keyB = getMockMetricDimensionKey(1, "b"); |
| 278 | MetricDimensionKey keyC = getMockMetricDimensionKey(1, "c"); |
| 279 | MetricDimensionKey keyD = getMockMetricDimensionKey(1, "d"); |
| 280 | MetricDimensionKey keyE = getMockMetricDimensionKey(1, "e"); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 281 | |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 282 | std::shared_ptr<DimToValMap> bucket9 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}}); |
| 283 | std::shared_ptr<DimToValMap> bucket16 = MockBucket({{keyB, 4}}); |
| 284 | std::shared_ptr<DimToValMap> bucket18 = MockBucket({{keyB, 1}, {keyC, 1}}); |
| 285 | std::shared_ptr<DimToValMap> bucket20 = MockBucket({{keyB, 3}, {keyC, 1}}); |
| 286 | std::shared_ptr<DimToValMap> bucket25 = MockBucket({{keyD, 1}}); |
| 287 | std::shared_ptr<DimToValMap> bucket28 = MockBucket({{keyE, 2}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 288 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 289 | int64_t eventTimestamp1 = bucketSizeNs * 8 + 1; |
| 290 | int64_t eventTimestamp2 = bucketSizeNs * 15 + 11; |
| 291 | int64_t eventTimestamp3 = bucketSizeNs * 17 + 1; |
| 292 | int64_t eventTimestamp4 = bucketSizeNs * 19 + 2; |
| 293 | int64_t eventTimestamp5 = bucketSizeNs * 24 + 3; |
| 294 | int64_t eventTimestamp6 = bucketSizeNs * 27 + 3; |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 295 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 296 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL); |
| 297 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 298 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 9, bucket9, {}, {keyA, keyB, keyC, keyD})); |
| 299 | detectAndDeclareAnomalies(anomalyTracker, 9, bucket9, eventTimestamp1); |
| 300 | checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec, |
| 301 | {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 302 | |
| 303 | // Add past bucket #9 |
| 304 | anomalyTracker.addPastBucket(bucket9, 9); |
| 305 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 9L); |
| 306 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 307 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL); |
| 308 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL); |
| 309 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 310 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 16, bucket16, {keyB}, {keyA, keyC, keyD})); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 311 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 312 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 313 | detectAndDeclareAnomalies(anomalyTracker, 16, bucket16, eventTimestamp2); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 314 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 315 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 316 | checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec, |
| 317 | {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 318 | |
| 319 | // Add past bucket #16 |
| 320 | anomalyTracker.addPastBucket(bucket16, 16); |
| 321 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 16L); |
| 322 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 323 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 324 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 18, bucket18, {keyB}, {keyA, keyC, keyD})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 325 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 326 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 327 | // Within refractory period. |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 328 | detectAndDeclareAnomalies(anomalyTracker, 18, bucket18, eventTimestamp3); |
| 329 | checkRefractoryTimes(anomalyTracker, eventTimestamp3, refractoryPeriodSec, |
| 330 | {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 331 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 332 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 333 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 334 | // Add past bucket #18 |
| 335 | anomalyTracker.addPastBucket(bucket18, 18); |
| 336 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 18L); |
| 337 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 338 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
| 339 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 340 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 20, bucket20, {keyB}, {keyA, keyC, keyD})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 341 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L); |
| 342 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 343 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
| 344 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 345 | detectAndDeclareAnomalies(anomalyTracker, 20, bucket20, eventTimestamp4); |
| 346 | checkRefractoryTimes(anomalyTracker, eventTimestamp4, refractoryPeriodSec, |
| 347 | {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 348 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 349 | // Add bucket #18 again. Nothing changes. |
| 350 | anomalyTracker.addPastBucket(bucket18, 18); |
| 351 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L); |
| 352 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 353 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
| 354 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 355 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 20, bucket20, {keyB}, {keyA, keyC, keyD})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 356 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 357 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL); |
| 358 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 359 | detectAndDeclareAnomalies(anomalyTracker, 20, bucket20, eventTimestamp4 + 1); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 360 | // Within refractory period. |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 361 | checkRefractoryTimes(anomalyTracker, eventTimestamp4 + 1, refractoryPeriodSec, |
| 362 | {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 363 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 364 | // Add past bucket #20 |
| 365 | anomalyTracker.addPastBucket(bucket20, 20); |
| 366 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 20L); |
| 367 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 368 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 3LL); |
| 369 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 370 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 25, bucket25, {}, {keyA, keyB, keyC, keyD})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 371 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 24L); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 372 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 373 | detectAndDeclareAnomalies(anomalyTracker, 25, bucket25, eventTimestamp5); |
| 374 | checkRefractoryTimes(anomalyTracker, eventTimestamp5, refractoryPeriodSec, |
| 375 | {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 376 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 377 | // Add past bucket #25 |
| 378 | anomalyTracker.addPastBucket(bucket25, 25); |
| 379 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 25L); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 380 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL); |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 381 | EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyD), 1LL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 382 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 28, bucket28, {}, |
| 383 | {keyA, keyB, keyC, keyD, keyE})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 384 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 385 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 386 | detectAndDeclareAnomalies(anomalyTracker, 28, bucket28, eventTimestamp6); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 387 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 388 | checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec, |
| 389 | {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, -1}}); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 390 | |
| 391 | // Updates current bucket #28. |
Yao Chen | d5aa01b3 | 2017-12-19 16:46:36 -0800 | [diff] [blame] | 392 | (*bucket28)[keyE] = 5; |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 393 | EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 28, bucket28, {keyE}, |
| 394 | {keyA, keyB, keyC, keyD})); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 395 | EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 396 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 397 | detectAndDeclareAnomalies(anomalyTracker, 28, bucket28, eventTimestamp6 + 7); |
Bookatz | d27ab45 | 2018-05-24 10:35:02 -0700 | [diff] [blame] | 398 | EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 399 | checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec, |
| 400 | {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, eventTimestamp6 + 7}}); |
Yang Lu | 3eba621 | 2017-10-25 19:54:45 -0700 | [diff] [blame] | 401 | } |
| 402 | |
| 403 | } // namespace statsd |
| 404 | } // namespace os |
| 405 | } // namespace android |
| 406 | #else |
| 407 | GTEST_LOG_(INFO) << "This test does nothing.\n"; |
| 408 | #endif |