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 
15 #include "src/anomaly/AnomalyTracker.h"
16 
17 #include <gtest/gtest.h>
18 #include <math.h>
19 #include <stdio.h>
20 
21 #include <vector>
22 
23 #include "src/subscriber/SubscriberReporter.h"
24 #include "tests/statsd_test_util.h"
25 
26 using namespace testing;
27 using android::sp;
28 using ::ndk::SharedRefBase;
29 using std::set;
30 using std::unordered_map;
31 using std::vector;
32 
33 #ifdef __ANDROID__
34 
35 namespace android {
36 namespace os {
37 namespace statsd {
38 
39 namespace {
40 const int kConfigUid = 0;
41 const int kConfigId = 12345;
42 const ConfigKey kConfigKey(kConfigUid, kConfigId);
43 }  // anonymous namespace
44 
getMockMetricDimensionKey(int key,string value)45 MetricDimensionKey getMockMetricDimensionKey(int key, string value) {
46     int pos[] = {key, 0, 0};
47     HashableDimensionKey dim;
48     dim.addValue(FieldValue(Field(1, pos, 0), Value(value)));
49     return MetricDimensionKey(dim, DEFAULT_DIMENSION_KEY);
50 }
51 
AddValueToBucket(const std::vector<std::pair<MetricDimensionKey,long>> & key_value_pair_list,std::shared_ptr<DimToValMap> bucket)52 void AddValueToBucket(const std::vector<std::pair<MetricDimensionKey, long>>& key_value_pair_list,
53                       std::shared_ptr<DimToValMap> bucket) {
54     for (auto itr = key_value_pair_list.begin(); itr != key_value_pair_list.end(); itr++) {
55         (*bucket)[itr->first] += itr->second;
56     }
57 }
58 
MockBucket(const std::vector<std::pair<MetricDimensionKey,long>> & key_value_pair_list)59 std::shared_ptr<DimToValMap> MockBucket(
60         const std::vector<std::pair<MetricDimensionKey, long>>& key_value_pair_list) {
61     std::shared_ptr<DimToValMap> bucket = std::make_shared<DimToValMap>();
62     AddValueToBucket(key_value_pair_list, bucket);
63     return bucket;
64 }
65 
66 // Returns the value, for the given key, in that bucket, or 0 if not present.
getBucketValue(const std::shared_ptr<DimToValMap> & bucket,const MetricDimensionKey & key)67 int64_t getBucketValue(const std::shared_ptr<DimToValMap>& bucket,
68                        const MetricDimensionKey& key) {
69     const auto& itr = bucket->find(key);
70     if (itr != bucket->end()) {
71         return itr->second;
72     }
73     return 0;
74 }
75 
76 // Returns true if keys in trueList are detected as anomalies and keys in falseList are not.
detectAnomaliesPass(AnomalyTracker & tracker,int64_t bucketNum,const std::shared_ptr<DimToValMap> & currentBucket,const std::set<const MetricDimensionKey> & trueList,const std::set<const MetricDimensionKey> & falseList)77 bool detectAnomaliesPass(AnomalyTracker& tracker, int64_t bucketNum,
78                          const std::shared_ptr<DimToValMap>& currentBucket,
79                          const std::set<const MetricDimensionKey>& trueList,
80                          const std::set<const MetricDimensionKey>& falseList) {
81     for (const MetricDimensionKey& key : trueList) {
82         if (!tracker.detectAnomaly(bucketNum, key, getBucketValue(currentBucket, key))) {
83             return false;
84         }
85     }
86     for (const MetricDimensionKey& key : falseList) {
87         if (tracker.detectAnomaly(bucketNum, key, getBucketValue(currentBucket, key))) {
88             return false;
89         }
90     }
91     return true;
92 }
93 
94 // Calls tracker.detectAndDeclareAnomaly on each key in the bucket.
detectAndDeclareAnomalies(AnomalyTracker & tracker,int64_t bucketNum,const std::shared_ptr<DimToValMap> & bucket,int64_t eventTimestamp)95 void detectAndDeclareAnomalies(AnomalyTracker& tracker, int64_t bucketNum,
96                                const std::shared_ptr<DimToValMap>& bucket, int64_t eventTimestamp) {
97     for (const auto& kv : *bucket) {
98         tracker.detectAndDeclareAnomaly(eventTimestamp, bucketNum, 0 /*metric_id*/, kv.first,
99                                         kv.second);
100     }
101 }
102 
103 // Asserts that the refractory time for each key in timestamps is the corresponding
104 // timestamp (in ns) + refractoryPeriodSec.
105 // If a timestamp value is negative, instead asserts that the refractory period is inapplicable
106 // (either non-existant or already past).
checkRefractoryTimes(AnomalyTracker & tracker,int64_t currTimestampNs,int32_t refractoryPeriodSec,const std::unordered_map<MetricDimensionKey,int64_t> & timestamps)107 void checkRefractoryTimes(AnomalyTracker& tracker, int64_t currTimestampNs,
108                           int32_t refractoryPeriodSec,
109                           const std::unordered_map<MetricDimensionKey, int64_t>& timestamps) {
110     for (const auto& kv : timestamps) {
111         if (kv.second < 0) {
112             // Make sure that, if there is a refractory period, it is already past.
113             EXPECT_LT(tracker.getRefractoryPeriodEndsSec(kv.first) * NS_PER_SEC,
114                     (uint64_t)currTimestampNs)
115                     << "Failure was at currTimestampNs " << currTimestampNs;
116         } else {
117             EXPECT_EQ(tracker.getRefractoryPeriodEndsSec(kv.first),
118                       std::ceil(1.0 * kv.second / NS_PER_SEC) + refractoryPeriodSec)
119                       << "Failure was at currTimestampNs " << currTimestampNs;
120         }
121     }
122 }
123 
TEST(AnomalyTrackerTest,TestConsecutiveBuckets)124 TEST(AnomalyTrackerTest, TestConsecutiveBuckets) {
125     const int64_t bucketSizeNs = 30 * NS_PER_SEC;
126     const int32_t refractoryPeriodSec = 2 * bucketSizeNs / NS_PER_SEC;
127     Alert alert;
128     alert.set_num_buckets(3);
129     alert.set_refractory_period_secs(refractoryPeriodSec);
130     alert.set_trigger_if_sum_gt(2);
131 
132     AnomalyTracker anomalyTracker(alert, kConfigKey);
133     MetricDimensionKey keyA = getMockMetricDimensionKey(1, "a");
134     MetricDimensionKey keyB = getMockMetricDimensionKey(1, "b");
135     MetricDimensionKey keyC = getMockMetricDimensionKey(1, "c");
136 
137     int64_t eventTimestamp0 = 10 * NS_PER_SEC;
138     int64_t eventTimestamp1 = bucketSizeNs + 11 * NS_PER_SEC;
139     int64_t eventTimestamp2 = 2 * bucketSizeNs + 12 * NS_PER_SEC;
140     int64_t eventTimestamp3 = 3 * bucketSizeNs + 13 * NS_PER_SEC;
141     int64_t eventTimestamp4 = 4 * bucketSizeNs + 14 * NS_PER_SEC;
142     int64_t eventTimestamp5 = 5 * bucketSizeNs + 5 * NS_PER_SEC;
143     int64_t eventTimestamp6 = 6 * bucketSizeNs + 16 * NS_PER_SEC;
144 
145     std::shared_ptr<DimToValMap> bucket0 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}});
146     std::shared_ptr<DimToValMap> bucket1 = MockBucket({{keyA, 1}});
147     std::shared_ptr<DimToValMap> bucket2 = MockBucket({{keyB, 1}});
148     std::shared_ptr<DimToValMap> bucket3 = MockBucket({{keyA, 2}});
149     std::shared_ptr<DimToValMap> bucket4 = MockBucket({{keyB, 5}});
150     std::shared_ptr<DimToValMap> bucket5 = MockBucket({{keyA, 2}});
151     std::shared_ptr<DimToValMap> bucket6 = MockBucket({{keyA, 2}});
152 
153     // Start time with no events.
154     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0u);
155     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL);
156 
157     // Event from bucket #0 occurs.
158     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 0, bucket0, {}, {keyA, keyB, keyC}));
159     detectAndDeclareAnomalies(anomalyTracker, 0, bucket0, eventTimestamp1);
160     checkRefractoryTimes(anomalyTracker, eventTimestamp0, refractoryPeriodSec,
161             {{keyA, -1}, {keyB, -1}, {keyC, -1}});
162 
163     // Adds past bucket #0
164     anomalyTracker.addPastBucket(bucket0, 0);
165     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u);
166     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
167     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
168     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
169     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL);
170 
171     // Event from bucket #1 occurs.
172     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 1, bucket1, {}, {keyA, keyB, keyC}));
173     detectAndDeclareAnomalies(anomalyTracker, 1, bucket1, eventTimestamp1);
174     checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec,
175             {{keyA, -1}, {keyB, -1}, {keyC, -1}});
176 
177     // Adds past bucket #0 again. The sum does not change.
178     anomalyTracker.addPastBucket(bucket0, 0);
179     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u);
180     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
181     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
182     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
183     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL);
184     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 1, bucket1, {}, {keyA, keyB, keyC}));
185     detectAndDeclareAnomalies(anomalyTracker, 1, bucket1, eventTimestamp1 + 1);
186     checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec,
187             {{keyA, -1}, {keyB, -1}, {keyC, -1}});
188 
189     // Adds past bucket #1.
190     anomalyTracker.addPastBucket(bucket1, 1);
191     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L);
192     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
193     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
194     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
195     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
196 
197     // Event from bucket #2 occurs. New anomaly on keyB.
198     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 2, bucket2, {keyB}, {keyA, keyC}));
199     detectAndDeclareAnomalies(anomalyTracker, 2, bucket2, eventTimestamp2);
200     checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec,
201             {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}});
202 
203     // Adds past bucket #1 again. Nothing changes.
204     anomalyTracker.addPastBucket(bucket1, 1);
205     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L);
206     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
207     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
208     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
209     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
210     // Event from bucket #2 occurs (again).
211     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 2, bucket2, {keyB}, {keyA, keyC}));
212     detectAndDeclareAnomalies(anomalyTracker, 2, bucket2, eventTimestamp2 + 1);
213     checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec,
214             {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}});
215 
216     // Adds past bucket #2.
217     anomalyTracker.addPastBucket(bucket2, 2);
218     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 2L);
219     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
220     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
221     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
222 
223     // Event from bucket #3 occurs. New anomaly on keyA.
224     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 3, bucket3, {keyA}, {keyB, keyC}));
225     detectAndDeclareAnomalies(anomalyTracker, 3, bucket3, eventTimestamp3);
226     checkRefractoryTimes(anomalyTracker, eventTimestamp3, refractoryPeriodSec,
227             {{keyA, eventTimestamp3}, {keyB, eventTimestamp2}, {keyC, -1}});
228 
229     // Adds bucket #3.
230     anomalyTracker.addPastBucket(bucket3, 3L);
231     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 3L);
232     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
233     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
234     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
235 
236     // Event from bucket #4 occurs. New anomaly on keyB.
237     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 4, bucket4, {keyB}, {keyA, keyC}));
238     detectAndDeclareAnomalies(anomalyTracker, 4, bucket4, eventTimestamp4);
239     checkRefractoryTimes(anomalyTracker, eventTimestamp4, refractoryPeriodSec,
240             {{keyA, eventTimestamp3}, {keyB, eventTimestamp4}, {keyC, -1}});
241 
242     // Adds bucket #4.
243     anomalyTracker.addPastBucket(bucket4, 4);
244     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 4L);
245     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
246     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
247     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 5LL);
248 
249     // Event from bucket #5 occurs. New anomaly on keyA, which is still in refractory.
250     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 5, bucket5, {keyA, keyB}, {keyC}));
251     detectAndDeclareAnomalies(anomalyTracker, 5, bucket5, eventTimestamp5);
252     checkRefractoryTimes(anomalyTracker, eventTimestamp5, refractoryPeriodSec,
253             {{keyA, eventTimestamp3}, {keyB, eventTimestamp4}, {keyC, -1}});
254 
255     // Adds bucket #5.
256     anomalyTracker.addPastBucket(bucket5, 5);
257     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 5L);
258     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
259     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
260     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 5LL);
261 
262     // Event from bucket #6 occurs. New anomaly on keyA, which is now out of refractory.
263     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 6, bucket6, {keyA, keyB}, {keyC}));
264     detectAndDeclareAnomalies(anomalyTracker, 6, bucket6, eventTimestamp6);
265     checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec,
266             {{keyA, eventTimestamp6}, {keyB, eventTimestamp4}, {keyC, -1}});
267 }
268 
TEST(AnomalyTrackerTest,TestSparseBuckets)269 TEST(AnomalyTrackerTest, TestSparseBuckets) {
270     const int64_t bucketSizeNs = 30 * NS_PER_SEC;
271     const int32_t refractoryPeriodSec = 2 * bucketSizeNs / NS_PER_SEC;
272     Alert alert;
273     alert.set_num_buckets(3);
274     alert.set_refractory_period_secs(refractoryPeriodSec);
275     alert.set_trigger_if_sum_gt(2);
276 
277     AnomalyTracker anomalyTracker(alert, kConfigKey);
278     MetricDimensionKey keyA = getMockMetricDimensionKey(1, "a");
279     MetricDimensionKey keyB = getMockMetricDimensionKey(1, "b");
280     MetricDimensionKey keyC = getMockMetricDimensionKey(1, "c");
281     MetricDimensionKey keyD = getMockMetricDimensionKey(1, "d");
282     MetricDimensionKey keyE = getMockMetricDimensionKey(1, "e");
283 
284     std::shared_ptr<DimToValMap> bucket9 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}});
285     std::shared_ptr<DimToValMap> bucket16 = MockBucket({{keyB, 4}});
286     std::shared_ptr<DimToValMap> bucket18 = MockBucket({{keyB, 1}, {keyC, 1}});
287     std::shared_ptr<DimToValMap> bucket20 = MockBucket({{keyB, 3}, {keyC, 1}});
288     std::shared_ptr<DimToValMap> bucket25 = MockBucket({{keyD, 1}});
289     std::shared_ptr<DimToValMap> bucket28 = MockBucket({{keyE, 2}});
290 
291     int64_t eventTimestamp1 = bucketSizeNs * 8 + 1;
292     int64_t eventTimestamp2 = bucketSizeNs * 15 + 11;
293     int64_t eventTimestamp3 = bucketSizeNs * 17 + 1;
294     int64_t eventTimestamp4 = bucketSizeNs * 19 + 2;
295     int64_t eventTimestamp5 = bucketSizeNs * 24 + 3;
296     int64_t eventTimestamp6 = bucketSizeNs * 27 + 3;
297 
298     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL);
299     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
300     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 9, bucket9, {}, {keyA, keyB, keyC, keyD}));
301     detectAndDeclareAnomalies(anomalyTracker, 9, bucket9, eventTimestamp1);
302     checkRefractoryTimes(anomalyTracker, eventTimestamp1, refractoryPeriodSec,
303             {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
304 
305     // Add past bucket #9
306     anomalyTracker.addPastBucket(bucket9, 9);
307     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 9L);
308     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
309     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
310     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
311     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
312     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 16, bucket16, {keyB}, {keyA, keyC, keyD}));
313     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
314     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L);
315     detectAndDeclareAnomalies(anomalyTracker, 16, bucket16, eventTimestamp2);
316     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
317     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L);
318     checkRefractoryTimes(anomalyTracker, eventTimestamp2, refractoryPeriodSec,
319             {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
320 
321     // Add past bucket #16
322     anomalyTracker.addPastBucket(bucket16, 16);
323     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 16L);
324     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
325     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);
326     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 18, bucket18, {keyB}, {keyA, keyC, keyD}));
327     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
328     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);
329     // Within refractory period.
330     detectAndDeclareAnomalies(anomalyTracker, 18, bucket18, eventTimestamp3);
331     checkRefractoryTimes(anomalyTracker, eventTimestamp3, refractoryPeriodSec,
332             {{keyA, -1}, {keyB, eventTimestamp2}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
333     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
334     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);
335 
336     // Add past bucket #18
337     anomalyTracker.addPastBucket(bucket18, 18);
338     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 18L);
339     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
340     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
341     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
342     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 20, bucket20, {keyB}, {keyA, keyC, keyD}));
343     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L);
344     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
345     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
346     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
347     detectAndDeclareAnomalies(anomalyTracker, 20, bucket20, eventTimestamp4);
348     checkRefractoryTimes(anomalyTracker, eventTimestamp4, refractoryPeriodSec,
349             {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
350 
351     // Add bucket #18 again. Nothing changes.
352     anomalyTracker.addPastBucket(bucket18, 18);
353     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L);
354     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
355     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
356     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
357     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 20, bucket20, {keyB}, {keyA, keyC, keyD}));
358     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
359     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
360     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
361     detectAndDeclareAnomalies(anomalyTracker, 20, bucket20, eventTimestamp4 + 1);
362     // Within refractory period.
363     checkRefractoryTimes(anomalyTracker, eventTimestamp4 + 1, refractoryPeriodSec,
364             {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
365 
366     // Add past bucket #20
367     anomalyTracker.addPastBucket(bucket20, 20);
368     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 20L);
369     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
370     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 3LL);
371     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
372     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 25, bucket25, {}, {keyA, keyB, keyC, keyD}));
373     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 24L);
374     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
375     detectAndDeclareAnomalies(anomalyTracker, 25, bucket25, eventTimestamp5);
376     checkRefractoryTimes(anomalyTracker, eventTimestamp5, refractoryPeriodSec,
377             {{keyA, -1}, {keyB, eventTimestamp4}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
378 
379     // Add past bucket #25
380     anomalyTracker.addPastBucket(bucket25, 25);
381     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 25L);
382     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
383     EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyD), 1LL);
384     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 28, bucket28, {},
385             {keyA, keyB, keyC, keyD, keyE}));
386     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L);
387     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
388     detectAndDeclareAnomalies(anomalyTracker, 28, bucket28, eventTimestamp6);
389     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
390     checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec,
391             {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, -1}});
392 
393     // Updates current bucket #28.
394     (*bucket28)[keyE] = 5;
395     EXPECT_TRUE(detectAnomaliesPass(anomalyTracker, 28, bucket28, {keyE},
396             {keyA, keyB, keyC, keyD}));
397     EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L);
398     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
399     detectAndDeclareAnomalies(anomalyTracker, 28, bucket28, eventTimestamp6 + 7);
400     ASSERT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
401     checkRefractoryTimes(anomalyTracker, eventTimestamp6, refractoryPeriodSec,
402             {{keyA, -1}, {keyB, -1}, {keyC, -1}, {keyD, -1}, {keyE, eventTimestamp6 + 7}});
403 }
404 
TEST(AnomalyTrackerTest,TestProbabilityOfInforming)405 TEST(AnomalyTrackerTest, TestProbabilityOfInforming) {
406     // Initiating StatsdStats at the start of this test, so it doesn't call rand() during the test
407     StatsdStats::getInstance();
408     srand(/*commonly used seed=*/0);
409     const int64_t bucketSizeNs = 30 * NS_PER_SEC;
410     const int32_t refractoryPeriodSec = bucketSizeNs / NS_PER_SEC;
411     int broadcastSubRandId = 1, broadcastSubAlwaysId = 2, broadcastSubNeverId = 3;
412 
413     // Alert with probability of informing set to 0.5
414     Alert alertRand = createAlert("alertRand", /*metric id=*/0, /*buckets=*/1, /*triggerSum=*/0);
415     alertRand.set_refractory_period_secs(refractoryPeriodSec);
416     alertRand.set_probability_of_informing(0.5);
417     AnomalyTracker anomalyTrackerRand(alertRand, kConfigKey);
418 
419     Subscription subRand = createSubscription("subRand", /*rule_type=*/Subscription::ALERT,
420                                               /*rule_id=*/alertRand.id());
421     subRand.mutable_broadcast_subscriber_details()->set_subscriber_id(broadcastSubRandId);
422     anomalyTrackerRand.addSubscription(subRand);
423 
424     // Alert with probability of informing set to 1.1 (always; set by default)
425     Alert alertAlways =
426             createAlert("alertAlways", /*metric id=*/0, /*buckets=*/1, /*triggerSum=*/0);
427     alertAlways.set_refractory_period_secs(refractoryPeriodSec);
428     AnomalyTracker anomalyTrackerAlways(alertAlways, kConfigKey);
429 
430     Subscription subAlways = createSubscription("subAlways", /*rule_type=*/Subscription::ALERT,
431                                                 /*rule_id=*/alertAlways.id());
432     subAlways.mutable_broadcast_subscriber_details()->set_subscriber_id(broadcastSubAlwaysId);
433     anomalyTrackerAlways.addSubscription(subAlways);
434 
435     // Alert with probability of informing set to -0.1 (never)
436     Alert alertNever = createAlert("alertNever", /*metric id=*/0, /*buckets=*/1, /*triggerSum=*/0);
437     alertNever.set_refractory_period_secs(refractoryPeriodSec);
438     alertNever.set_probability_of_informing(-0.1);
439     AnomalyTracker anomalyTrackerNever(alertNever, kConfigKey);
440 
441     Subscription subNever = createSubscription("subNever", /*rule_type=*/Subscription::ALERT,
442                                                /*rule_id=*/alertNever.id());
443     subNever.mutable_broadcast_subscriber_details()->set_subscriber_id(broadcastSubNeverId);
444     anomalyTrackerNever.addSubscription(subNever);
445 
446     // Bucket value needs to be greater than 0 to detect and declare anomaly
447     int bucketValue = 1;
448 
449     int alertRandCount = 0, alertAlwaysCount = 0;
450     // The binder calls here will happen synchronously because they are in-process.
451     shared_ptr<MockPendingIntentRef> randBroadcast =
452             SharedRefBase::make<StrictMock<MockPendingIntentRef>>();
453     EXPECT_CALL(*randBroadcast,
454                 sendSubscriberBroadcast(kConfigUid, kConfigId, subRand.id(), alertRand.id(), _, _))
455             .Times(3)
456             .WillRepeatedly([&alertRandCount] {
457                 alertRandCount++;
458                 return Status::ok();
459             });
460 
461     shared_ptr<MockPendingIntentRef> alwaysBroadcast =
462             SharedRefBase::make<StrictMock<MockPendingIntentRef>>();
463     EXPECT_CALL(*alwaysBroadcast, sendSubscriberBroadcast(kConfigUid, kConfigId, subAlways.id(),
464                                                           alertAlways.id(), _, _))
465             .Times(10)
466             .WillRepeatedly([&alertAlwaysCount] {
467                 alertAlwaysCount++;
468                 return Status::ok();
469             });
470 
471     shared_ptr<MockPendingIntentRef> neverBroadcast =
472             SharedRefBase::make<StrictMock<MockPendingIntentRef>>();
473     EXPECT_CALL(*neverBroadcast, sendSubscriberBroadcast(kConfigUid, kConfigId, subNever.id(),
474                                                          alertNever.id(), _, _))
475             .Times(0);
476 
477     SubscriberReporter::getInstance().setBroadcastSubscriber(kConfigKey, broadcastSubRandId,
478                                                              randBroadcast);
479     SubscriberReporter::getInstance().setBroadcastSubscriber(kConfigKey, broadcastSubAlwaysId,
480                                                              alwaysBroadcast);
481     SubscriberReporter::getInstance().setBroadcastSubscriber(kConfigKey, broadcastSubNeverId,
482                                                              neverBroadcast);
483 
484     // Trying to inform the subscription and start the refractory period countdown 10x.
485     // Deterministic sequence for anomalyTrackerRand:
486     // 0.96, 0.95, 0.95, 0.94, 0.43, 0.92, 0.92, 0.41, 0.39, 0.88
487     for (size_t i = 0; i < 10; i++) {
488         int64_t curEventTimestamp = bucketSizeNs * i;
489         anomalyTrackerRand.detectAndDeclareAnomaly(curEventTimestamp, /*bucketNum=*/i,
490                                                    /*metric_id=*/0, DEFAULT_METRIC_DIMENSION_KEY,
491                                                    bucketValue);
492         if (i <= 3) {
493             EXPECT_EQ(alertRandCount, 0);
494         } else if (i >= 4 && i <= 6) {
495             EXPECT_EQ(alertRandCount, 1);
496         } else if (i == 7) {
497             EXPECT_EQ(alertRandCount, 2);
498         } else {
499             EXPECT_EQ(alertRandCount, 3);
500         }
501         anomalyTrackerAlways.detectAndDeclareAnomaly(curEventTimestamp, /*bucketNum=*/i,
502                                                      /*metric_id=*/0, DEFAULT_METRIC_DIMENSION_KEY,
503                                                      bucketValue);
504         EXPECT_EQ(alertAlwaysCount, i + 1);
505         anomalyTrackerNever.detectAndDeclareAnomaly(curEventTimestamp, /*bucketNum=*/i,
506                                                     /*metric_id=*/0, DEFAULT_METRIC_DIMENSION_KEY,
507                                                     bucketValue);
508     }
509     SubscriberReporter::getInstance().unsetBroadcastSubscriber(kConfigKey, broadcastSubRandId);
510     SubscriberReporter::getInstance().unsetBroadcastSubscriber(kConfigKey, broadcastSubAlwaysId);
511     SubscriberReporter::getInstance().unsetBroadcastSubscriber(kConfigKey, broadcastSubNeverId);
512 }
513 
514 }  // namespace statsd
515 }  // namespace os
516 }  // namespace android
517 #else
518 GTEST_LOG_(INFO) << "This test does nothing.\n";
519 #endif
520