Home | History | Annotate | Download | only in anomaly 
      1 /*
      2  * Copyright (C) 2017 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #define DEBUG false  // STOPSHIP if true
     18 #include "Log.h"
     19 
     20 #include "AnomalyTracker.h"
     21 #include "subscriber_util.h"
     22 #include "external/Perfetto.h"
     23 #include "guardrail/StatsdStats.h"
     24 #include "subscriber/IncidentdReporter.h"
     25 #include "subscriber/SubscriberReporter.h"
     26 
     27 #include <statslog.h>
     28 #include <time.h>
     29 
     30 namespace android {
     31 namespace os {
     32 namespace statsd {
     33 
     34 AnomalyTracker::AnomalyTracker(const Alert& alert, const ConfigKey& configKey)
     35         : mAlert(alert), mConfigKey(configKey), mNumOfPastBuckets(mAlert.num_buckets() - 1) {
     36     VLOG("AnomalyTracker() called");
     37     if (mAlert.num_buckets() <= 0) {
     38         ALOGE("Cannot create AnomalyTracker with %lld buckets", (long long)mAlert.num_buckets());
     39         return;
     40     }
     41     if (!mAlert.has_trigger_if_sum_gt()) {
     42         ALOGE("Cannot create AnomalyTracker without threshold");
     43         return;
     44     }
     45     resetStorage();  // initialization
     46 }
     47 
     48 AnomalyTracker::~AnomalyTracker() {
     49     VLOG("~AnomalyTracker() called");
     50 }
     51 
     52 void AnomalyTracker::resetStorage() {
     53     VLOG("resetStorage() called.");
     54     mPastBuckets.clear();
     55     // Excludes the current bucket.
     56     mPastBuckets.resize(mNumOfPastBuckets);
     57     mSumOverPastBuckets.clear();
     58 }
     59 
     60 size_t AnomalyTracker::index(int64_t bucketNum) const {
     61     if (bucketNum < 0) {
     62         ALOGE("index() was passed a negative bucket number (%lld)!", (long long)bucketNum);
     63     }
     64     return bucketNum % mNumOfPastBuckets;
     65 }
     66 
     67 void AnomalyTracker::advanceMostRecentBucketTo(const int64_t& bucketNum) {
     68     VLOG("advanceMostRecentBucketTo() called.");
     69     if (mNumOfPastBuckets <= 0) {
     70         return;
     71     }
     72     if (bucketNum <= mMostRecentBucketNum) {
     73         ALOGW("Cannot advance buckets backwards (bucketNum=%lld but mMostRecentBucketNum=%lld)",
     74               (long long)bucketNum, (long long)mMostRecentBucketNum);
     75         return;
     76     }
     77     // If in the future (i.e. buckets are ancient), just empty out all past info.
     78     if (bucketNum >= mMostRecentBucketNum + mNumOfPastBuckets) {
     79         resetStorage();
     80         mMostRecentBucketNum = bucketNum;
     81         return;
     82     }
     83 
     84     // Clear out space by emptying out old mPastBuckets[i] values and update mSumOverPastBuckets.
     85     for (int64_t i = mMostRecentBucketNum + 1; i <= bucketNum; i++) {
     86         const int idx = index(i);
     87         subtractBucketFromSum(mPastBuckets[idx]);
     88         mPastBuckets[idx] = nullptr;  // release (but not clear) the old bucket.
     89     }
     90     mMostRecentBucketNum = bucketNum;
     91 }
     92 
     93 void AnomalyTracker::addPastBucket(const MetricDimensionKey& key,
     94                                    const int64_t& bucketValue,
     95                                    const int64_t& bucketNum) {
     96     VLOG("addPastBucket(bucketValue) called.");
     97     if (mNumOfPastBuckets == 0 ||
     98         bucketNum < 0 || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets) {
     99         return;
    100     }
    101 
    102     const int bucketIndex = index(bucketNum);
    103     if (bucketNum <= mMostRecentBucketNum && (mPastBuckets[bucketIndex] != nullptr)) {
    104         // We need to insert into an already existing past bucket.
    105         std::shared_ptr<DimToValMap>& bucket = mPastBuckets[bucketIndex];
    106         auto itr = bucket->find(key);
    107         if (itr != bucket->end()) {
    108             // Old entry already exists; update it.
    109             subtractValueFromSum(key, itr->second);
    110             itr->second = bucketValue;
    111         } else {
    112             bucket->insert({key, bucketValue});
    113         }
    114         mSumOverPastBuckets[key] += bucketValue;
    115     } else {
    116         // Bucket does not exist yet (in future or was never made), so we must make it.
    117         std::shared_ptr<DimToValMap> bucket = std::make_shared<DimToValMap>();
    118         bucket->insert({key, bucketValue});
    119         addPastBucket(bucket, bucketNum);
    120     }
    121 }
    122 
    123 void AnomalyTracker::addPastBucket(std::shared_ptr<DimToValMap> bucket,
    124                                    const int64_t& bucketNum) {
    125     VLOG("addPastBucket(bucket) called.");
    126     if (mNumOfPastBuckets == 0 ||
    127             bucketNum < 0 || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets) {
    128         return;
    129     }
    130 
    131     if (bucketNum <= mMostRecentBucketNum) {
    132         // We are updating an old bucket, not adding a new one.
    133         subtractBucketFromSum(mPastBuckets[index(bucketNum)]);
    134     } else {
    135         // Clear space for the new bucket to be at bucketNum.
    136         advanceMostRecentBucketTo(bucketNum);
    137     }
    138     mPastBuckets[index(bucketNum)] = bucket;
    139     addBucketToSum(bucket);
    140 }
    141 
    142 void AnomalyTracker::subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket) {
    143     if (bucket == nullptr) {
    144         return;
    145     }
    146     for (const auto& keyValuePair : *bucket) {
    147         subtractValueFromSum(keyValuePair.first, keyValuePair.second);
    148     }
    149 }
    150 
    151 
    152 void AnomalyTracker::subtractValueFromSum(const MetricDimensionKey& key,
    153                                           const int64_t& bucketValue) {
    154     auto itr = mSumOverPastBuckets.find(key);
    155     if (itr == mSumOverPastBuckets.end()) {
    156         return;
    157     }
    158     itr->second -= bucketValue;
    159     if (itr->second == 0) {
    160         mSumOverPastBuckets.erase(itr);
    161     }
    162 }
    163 
    164 void AnomalyTracker::addBucketToSum(const shared_ptr<DimToValMap>& bucket) {
    165     if (bucket == nullptr) {
    166         return;
    167     }
    168     // For each dimension present in the bucket, add its value to its corresponding sum.
    169     for (const auto& keyValuePair : *bucket) {
    170         mSumOverPastBuckets[keyValuePair.first] += keyValuePair.second;
    171     }
    172 }
    173 
    174 int64_t AnomalyTracker::getPastBucketValue(const MetricDimensionKey& key,
    175                                            const int64_t& bucketNum) const {
    176     if (bucketNum < 0 || mMostRecentBucketNum < 0
    177             || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets
    178             || bucketNum > mMostRecentBucketNum) {
    179         return 0;
    180     }
    181 
    182     const auto& bucket = mPastBuckets[index(bucketNum)];
    183     if (bucket == nullptr) {
    184         return 0;
    185     }
    186     const auto& itr = bucket->find(key);
    187     return itr == bucket->end() ? 0 : itr->second;
    188 }
    189 
    190 int64_t AnomalyTracker::getSumOverPastBuckets(const MetricDimensionKey& key) const {
    191     const auto& itr = mSumOverPastBuckets.find(key);
    192     if (itr != mSumOverPastBuckets.end()) {
    193         return itr->second;
    194     }
    195     return 0;
    196 }
    197 
    198 bool AnomalyTracker::detectAnomaly(const int64_t& currentBucketNum,
    199                                    const MetricDimensionKey& key,
    200                                    const int64_t& currentBucketValue) {
    201 
    202     // currentBucketNum should be the next bucket after pastBuckets. If not, advance so that it is.
    203     if (currentBucketNum > mMostRecentBucketNum + 1) {
    204         advanceMostRecentBucketTo(currentBucketNum - 1);
    205     }
    206     return mAlert.has_trigger_if_sum_gt() &&
    207            getSumOverPastBuckets(key) + currentBucketValue > mAlert.trigger_if_sum_gt();
    208 }
    209 
    210 void AnomalyTracker::declareAnomaly(const int64_t& timestampNs, const MetricDimensionKey& key) {
    211     // TODO: Why receive timestamp? RefractoryPeriod should always be based on real time right now.
    212     if (isInRefractoryPeriod(timestampNs, key)) {
    213         VLOG("Skipping anomaly declaration since within refractory period");
    214         return;
    215     }
    216     if (mAlert.has_refractory_period_secs()) {
    217         mRefractoryPeriodEndsSec[key] = ((timestampNs + NS_PER_SEC - 1) / NS_PER_SEC) // round up
    218                                         + mAlert.refractory_period_secs();
    219         // TODO: If we had access to the bucket_size_millis, consider calling resetStorage()
    220         // if (mAlert.refractory_period_secs() > mNumOfPastBuckets * bucketSizeNs) {resetStorage();}
    221     }
    222 
    223     if (!mSubscriptions.empty()) {
    224         ALOGI("An anomaly (%lld) %s has occurred! Informing subscribers.",
    225                 mAlert.id(), key.toString().c_str());
    226         informSubscribers(key);
    227     } else {
    228         ALOGI("An anomaly has occurred! (But no subscriber for that alert.)");
    229     }
    230 
    231     StatsdStats::getInstance().noteAnomalyDeclared(mConfigKey, mAlert.id());
    232 
    233     // TODO: This should also take in the const MetricDimensionKey& key?
    234     android::util::stats_write(android::util::ANOMALY_DETECTED, mConfigKey.GetUid(),
    235                                mConfigKey.GetId(), mAlert.id());
    236 }
    237 
    238 void AnomalyTracker::detectAndDeclareAnomaly(const int64_t& timestampNs,
    239                                              const int64_t& currBucketNum,
    240                                              const MetricDimensionKey& key,
    241                                              const int64_t& currentBucketValue) {
    242     if (detectAnomaly(currBucketNum, key, currentBucketValue)) {
    243         declareAnomaly(timestampNs, key);
    244     }
    245 }
    246 
    247 bool AnomalyTracker::isInRefractoryPeriod(const int64_t& timestampNs,
    248                                           const MetricDimensionKey& key) const {
    249     const auto& it = mRefractoryPeriodEndsSec.find(key);
    250     if (it != mRefractoryPeriodEndsSec.end()) {
    251         return timestampNs < (it->second *  (int64_t)NS_PER_SEC);
    252     }
    253     return false;
    254 }
    255 
    256 void AnomalyTracker::informSubscribers(const MetricDimensionKey& key) {
    257     triggerSubscribers(mAlert.id(), key, mConfigKey, mSubscriptions);
    258 }
    259 
    260 }  // namespace statsd
    261 }  // namespace os
    262 }  // namespace android
    263