cmds/statsd/tests/anomaly/AnomalyTracker_test.cpp

// Copyright (C) 2017 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "src/anomaly/AnomalyTracker.h"
#include "../metrics/metrics_test_helper.h"

#include <gtest/gtest.h>
#include <stdio.h>
#include <vector>

using namespace testing;
using android::sp;
using std::set;
using std::unordered_map;
using std::vector;

#ifdef __ANDROID__

namespace android {
namespace os {
namespace statsd {

const ConfigKey kConfigKey(0, "test");

HashableDimensionKey getMockDimensionKey(int key, string value) {
    KeyValuePair pair;
    pair.set_key(key);
    pair.set_value_str(value);

    vector<KeyValuePair> pairs;
    pairs.push_back(pair);

    return HashableDimensionKey(pairs);
}

void AddValueToBucket(const std::vector<std::pair<HashableDimensionKey, long>>& key_value_pair_list,
                      std::shared_ptr<DimToValMap> bucket) {
    for (auto itr = key_value_pair_list.begin(); itr != key_value_pair_list.end(); itr++) {
        (*bucket)[itr->first] += itr->second;
    }
}

std::shared_ptr<DimToValMap> MockBucket(
        const std::vector<std::pair<HashableDimensionKey, long>>& key_value_pair_list) {
    std::shared_ptr<DimToValMap> bucket = std::make_shared<DimToValMap>();
    AddValueToBucket(key_value_pair_list, bucket);
    return bucket;
}

TEST(AnomalyTrackerTest, TestConsecutiveBuckets) {
    const int64_t bucketSizeNs = 30 * NS_PER_SEC;
    Alert alert;
    alert.set_number_of_buckets(3);
    alert.set_refractory_period_secs(2 * bucketSizeNs / NS_PER_SEC);
    alert.set_trigger_if_sum_gt(2);

    AnomalyTracker anomalyTracker(alert, kConfigKey);
    HashableDimensionKey keyA = getMockDimensionKey(1, "a");
    HashableDimensionKey keyB = getMockDimensionKey(1, "b");
    HashableDimensionKey keyC = getMockDimensionKey(1, "c");

    std::shared_ptr<DimToValMap> bucket0 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}});
    int64_t eventTimestamp0 = 10;
    std::shared_ptr<DimToValMap> bucket1 = MockBucket({{keyA, 1}});
    int64_t eventTimestamp1 = bucketSizeNs + 11;
    std::shared_ptr<DimToValMap> bucket2 = MockBucket({{keyB, 1}});
    int64_t eventTimestamp2 = 2 * bucketSizeNs + 12;
    std::shared_ptr<DimToValMap> bucket3 = MockBucket({{keyA, 2}});
    int64_t eventTimestamp3 = 3 * bucketSizeNs + 13;
    std::shared_ptr<DimToValMap> bucket4 = MockBucket({{keyB, 1}});
    int64_t eventTimestamp4 = 4 * bucketSizeNs + 14;
    std::shared_ptr<DimToValMap> bucket5 = MockBucket({{keyA, 2}});
    int64_t eventTimestamp5 = 5 * bucketSizeNs + 15;
    std::shared_ptr<DimToValMap> bucket6 = MockBucket({{keyA, 2}});
    int64_t eventTimestamp6 = 6 * bucketSizeNs + 16;

    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0u);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(0, *bucket0));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp0, 0, *bucket0);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, -1L);

    // Adds past bucket #0
    anomalyTracker.addPastBucket(bucket0, 0);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(1, *bucket1));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp1, 1, *bucket1);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, -1L);

    // Adds past bucket #0 again. The sum does not change.
    anomalyTracker.addPastBucket(bucket0, 0);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3u);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 0LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(1, *bucket1));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp1 + 1, 1, *bucket1);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, -1L);

    // Adds past bucket #1.
    anomalyTracker.addPastBucket(bucket1, 1);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(2, *bucket2));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp2, 2, *bucket2);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);

    // Adds past bucket #1 again. Nothing changes.
    anomalyTracker.addPastBucket(bucket1, 1);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 1L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(2, *bucket2));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp2 + 1, 2, *bucket2);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);

    // Adds past bucket #2.
    anomalyTracker.addPastBucket(bucket2, 2);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 2L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(3, *bucket3));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp3, 3, *bucket3);
    // Within refractory period.
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);

    // Adds bucket #3.
    anomalyTracker.addPastBucket(bucket3, 3L);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 3L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(4, *bucket4));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp4, 4, *bucket4);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);

    // Adds bucket #4.
    anomalyTracker.addPastBucket(bucket4, 4);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 4L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(5, *bucket5));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp5, 5, *bucket5);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp5);

    // Adds bucket #5.
    anomalyTracker.addPastBucket(bucket5, 5);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 5L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(6, *bucket6));
    // Within refractory period.
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp6, 6, *bucket6);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp5);
}

TEST(AnomalyTrackerTest, TestSparseBuckets) {
    const int64_t bucketSizeNs = 30 * NS_PER_SEC;
    Alert alert;
    alert.set_number_of_buckets(3);
    alert.set_refractory_period_secs(2 * bucketSizeNs / NS_PER_SEC);
    alert.set_trigger_if_sum_gt(2);

    AnomalyTracker anomalyTracker(alert, kConfigKey);
    HashableDimensionKey keyA = getMockDimensionKey(1, "a");
    HashableDimensionKey keyB = getMockDimensionKey(1, "b");
    HashableDimensionKey keyC = getMockDimensionKey(1, "c");
    HashableDimensionKey keyD = getMockDimensionKey(1, "d");
    HashableDimensionKey keyE = getMockDimensionKey(1, "e");

    std::shared_ptr<DimToValMap> bucket9 = MockBucket({{keyA, 1}, {keyB, 2}, {keyC, 1}});
    std::shared_ptr<DimToValMap> bucket16 = MockBucket({{keyB, 4}});
    std::shared_ptr<DimToValMap> bucket18 = MockBucket({{keyB, 1}, {keyC, 1}});
    std::shared_ptr<DimToValMap> bucket20 = MockBucket({{keyB, 3}, {keyC, 1}});
    std::shared_ptr<DimToValMap> bucket25 = MockBucket({{keyD, 1}});
    std::shared_ptr<DimToValMap> bucket28 = MockBucket({{keyE, 2}});

    int64_t eventTimestamp1 = bucketSizeNs * 8 + 1;
    int64_t eventTimestamp2 = bucketSizeNs * 15 + 11;
    int64_t eventTimestamp3 = bucketSizeNs * 17 + 1;
    int64_t eventTimestamp4 = bucketSizeNs * 19 + 2;
    int64_t eventTimestamp5 = bucketSizeNs * 24 + 3;
    int64_t eventTimestamp6 = bucketSizeNs * 27 + 3;

    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, -1LL);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(9, *bucket9));
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp1, 9, *bucket9);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, -1);

    // Add past bucket #9
    anomalyTracker.addPastBucket(bucket9, 9);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 9L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 3UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyA), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 2LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(16, *bucket16));
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp2, 16, *bucket16);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 15L);

    // Add past bucket #16
    anomalyTracker.addPastBucket(bucket16, 16);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 16L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(18, *bucket18));
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);
    // Within refractory period.
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp3, 18, *bucket18);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp2);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 4LL);

    // Add past bucket #18
    anomalyTracker.addPastBucket(bucket18, 18);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 18L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(20, *bucket20));
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp4, 20, *bucket20);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp4);

    // Add bucket #18 again. Nothing changes.
    anomalyTracker.addPastBucket(bucket18, 18);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 19L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_TRUE(anomalyTracker.detectAnomaly(20, *bucket20));
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 1LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp4 + 1, 20, *bucket20);
    // Within refractory period.
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp4);

    // Add past bucket #20
    anomalyTracker.addPastBucket(bucket20, 20);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 20L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 2UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyB), 3LL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyC), 1LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(25, *bucket25));
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 24L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp5, 25, *bucket25);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp4);

    // Add past bucket #25
    anomalyTracker.addPastBucket(bucket25, 25);
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 25L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 1UL);
    EXPECT_EQ(anomalyTracker.getSumOverPastBuckets(keyD), 1LL);
    EXPECT_FALSE(anomalyTracker.detectAnomaly(28, *bucket28));
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp6, 28, *bucket28);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp4);

    // Updates current bucket #28.
    (*bucket28)[keyE] = 5;
    EXPECT_TRUE(anomalyTracker.detectAnomaly(28, *bucket28));
    EXPECT_EQ(anomalyTracker.mMostRecentBucketNum, 27L);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    anomalyTracker.detectAndDeclareAnomaly(eventTimestamp6 + 7, 28, *bucket28);
    EXPECT_EQ(anomalyTracker.mSumOverPastBuckets.size(), 0UL);
    EXPECT_EQ(anomalyTracker.mLastAnomalyTimestampNs, eventTimestamp6 + 7);
}

}  // namespace statsd
}  // namespace os
}  // namespace android
#else
GTEST_LOG_(INFO) << "This test does nothing.\n";
#endif