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