Merge "Statsd Anomaly tracking for CountMetricProducer"

5 files changed, 205 insertions, 7 deletions

diff --git a/cmds/statsd/Android.mk b/cmds/statsd/Android.mk
index 56f9512f66c7..e7a31a0f8690 100644
--- a/cmds/statsd/Android.mk
+++ b/cmds/statsd/Android.mk
@@ -58,7 +58,7 @@ LOCAL_SRC_FILES := \
     src/metrics/CountMetricProducer.cpp \
     src/metrics/ConditionTracker.cpp \
     src/metrics/MetricsManager.cpp \
-
+    src/metrics/CountAnomalyTracker.cpp \
 
 LOCAL_CFLAGS += \
     -Wall \
diff --git a/cmds/statsd/src/metrics/CountAnomalyTracker.cpp b/cmds/statsd/src/metrics/CountAnomalyTracker.cpp
new file mode 100644
index 000000000000..ebd53e056249
--- /dev/null
+++ b/cmds/statsd/src/metrics/CountAnomalyTracker.cpp
@@ -0,0 +1,108 @@
+/*
+ * 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.
+ */
+
+#define LOG_TAG "CountAnomaly"
+#define DEBUG true  // STOPSHIP if true
+#define VLOG(...) \
+    if (DEBUG) ALOGD(__VA_ARGS__);
+
+#include "CountAnomalyTracker.h"
+
+#include <cutils/log.h>
+
+namespace android {
+namespace os {
+namespace statsd {
+
+CountAnomalyTracker::CountAnomalyTracker(size_t numBuckets, int thresholdGt)
+    : mNumPastBuckets(numBuckets > 0 ? numBuckets - 1 : 0),
+      mPastBuckets(mNumPastBuckets > 0 ? (new int[mNumPastBuckets]) : nullptr),
+      mThresholdGt(thresholdGt) {
+
+    VLOG("CountAnomalyTracker() called");
+    if (numBuckets < 1) {
+        ALOGE("Cannot create CountAnomalyTracker with %zu buckets", numBuckets);
+    }
+    reset(); // initialization
+}
+
+CountAnomalyTracker::~CountAnomalyTracker() {
+    VLOG("~CountAnomalyTracker() called");
+}
+
+void CountAnomalyTracker::addPastBucket(int pastBucketCount,
+                                        time_t numberOfBucketsAgo) {
+    VLOG("addPastBucket() called.");
+    if (numberOfBucketsAgo < 1) {
+        ALOGE("Cannot add a past bucket %ld units in past", numberOfBucketsAgo);
+        return;
+    }
+    // If past bucket was ancient, just empty out all past info.
+    // This always applies if mNumPastBuckets == 0 (i.e. store no past buckets).
+    if (numberOfBucketsAgo > (time_t) mNumPastBuckets) {
+        reset();
+        return;
+    }
+
+    // Empty out old mPastBuckets[i] values and update mSumPastCounters.
+    for (size_t i = mOldestBucketIndex;
+                        i < mOldestBucketIndex + numberOfBucketsAgo; i++) {
+        mSumPastCounters -= mPastBuckets[index(i)];
+        mPastBuckets[index(i)] = 0;
+    }
+
+    // Replace the oldest bucket with the new bucket we are adding.
+    mPastBuckets[mOldestBucketIndex] = pastBucketCount;
+    mSumPastCounters += pastBucketCount;
+
+    // Advance the oldest bucket index by numberOfBucketsAgo units.
+    mOldestBucketIndex = index(mOldestBucketIndex + numberOfBucketsAgo);
+
+    // TODO: Once dimensions are added to mSumPastCounters:
+    // iterate through mSumPastCounters and remove any entries that are 0.
+}
+
+void CountAnomalyTracker::reset() {
+    VLOG("reset() called.");
+    for (size_t i = 0; i < mNumPastBuckets; i++) {
+        mPastBuckets[i] = 0;
+    }
+    mSumPastCounters = 0;
+    mOldestBucketIndex = 0;
+}
+
+void CountAnomalyTracker::checkAnomaly(int currentCount) {
+    // Note that this works even if mNumPastBuckets < 1 (since then
+    // mSumPastCounters = 0 so the comparison is based only on currentCount).
+
+    // TODO: Remove these extremely verbose debugging log.
+    VLOG("Checking whether %d + %d > %d",
+         mSumPastCounters, currentCount, mThresholdGt);
+
+    if (mSumPastCounters + currentCount > mThresholdGt) {
+        declareAnomaly();
+    }
+}
+
+void CountAnomalyTracker::declareAnomaly() {
+    // TODO: check that not in refractory period.
+    // TODO: Do something.
+    ALOGI("An anomaly has occurred!");
+}
+
+}  // namespace statsd
+}  // namespace os
+}  // namespace android
diff --git a/cmds/statsd/src/metrics/CountAnomalyTracker.h b/cmds/statsd/src/metrics/CountAnomalyTracker.h
new file mode 100644
index 000000000000..449dee90e0a6
--- /dev/null
+++ b/cmds/statsd/src/metrics/CountAnomalyTracker.h
@@ -0,0 +1,79 @@
+/*
+ * 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.
+ */
+
+#ifndef COUNT_ANOMALY_TRACKER_H
+#define COUNT_ANOMALY_TRACKER_H
+
+#include <stdlib.h>
+#include <memory> // unique_ptr
+
+namespace android {
+namespace os {
+namespace statsd {
+
+class CountAnomalyTracker {
+public:
+    CountAnomalyTracker(size_t numBuckets, int thresholdGt);
+
+    virtual ~CountAnomalyTracker();
+
+
+    // Adds a new past bucket, holding pastBucketCount, and then advances the
+    // present by numberOfBucketsAgo buckets (filling any intervening buckets
+    // with 0s).
+    // Thus, the newly added bucket (which holds pastBucketCount) is stored
+    // numberOfBucketsAgo buckets ago.
+    void addPastBucket(int pastBucketCount, time_t numberOfBucketsAgo);
+
+    // Informs the anomaly tracker of the current bucket's count, so that it can
+    // determine whether an anomaly has occurred. This value is not stored.
+    void checkAnomaly(int currentCount);
+
+private:
+    // Number of past buckets. One less than the total number of buckets needed
+    // for the anomaly detection (since the current bucket is not in the past).
+    const size_t mNumPastBuckets;
+
+    // Count values for each of the past mNumPastBuckets buckets.
+    // TODO: Add dimensions. This parallels the type of CountMetricProducer.mCounter.
+    std::unique_ptr<int[]> mPastBuckets;
+
+    // Sum over all of mPastBuckets (cached).
+    // TODO: Add dimensions. This parallels the type of CountMetricProducer.mCounter.
+    //       At that point, mSumPastCounters must never contain entries of 0.
+    int mSumPastCounters;
+
+    // Index of the oldest bucket (i.e. the next bucket to be overwritten).
+    size_t mOldestBucketIndex = 0;
+
+    // If mSumPastCounters + currentCount > mThresholdGt --> Anomaly!
+    const int mThresholdGt;
+
+    void declareAnomaly();
+
+    // Calculates the corresponding index within the circular array.
+    size_t index(size_t unsafeIndex) {
+        return unsafeIndex % mNumPastBuckets;
+    }
+
+    // Resets all data. For use when all the data gets stale.
+    void reset();
+};
+
+}  // namespace statsd
+}  // namespace os
+}  // namespace android
+#endif  // COUNT_ANOMALY_TRACKER_H
diff --git a/cmds/statsd/src/metrics/CountMetricProducer.cpp b/cmds/statsd/src/metrics/CountMetricProducer.cpp
index fbd013ebf528..635777fe2267 100644
--- a/cmds/statsd/src/metrics/CountMetricProducer.cpp
+++ b/cmds/statsd/src/metrics/CountMetricProducer.cpp
@@ -20,6 +20,7 @@
     if (DEBUG) ALOGD(__VA_ARGS__);
 
 #include "CountMetricProducer.h"
+#include "CountAnomalyTracker.h"
 #include "parse_util.h"
 
 #include <cutils/log.h>
@@ -38,7 +39,9 @@ CountMetricProducer::CountMetricProducer(const CountMetric& metric,
       mConditionTracker(condition),
       mStartTime(std::time(nullptr)),
       mCounter(0),
-      mCurrentBucketStartTime(mStartTime) {
+      mCurrentBucketStartTime(mStartTime),
+      // TODO: read mAnomalyTracker parameters from config file.
+      mAnomalyTracker(6, 10) {
     // TODO: evaluate initial conditions. and set mConditionMet.
     if (metric.has_bucket() && metric.bucket().has_bucket_size_millis()) {
         mBucketSize_sec = metric.bucket().bucket_size_millis() / 1000;
@@ -78,6 +81,7 @@ void CountMetricProducer::onMatchedLogEvent(const LogEventWrapper& event) {
     if (mConditionTracker->isConditionMet()) {
         flushCounterIfNeeded(eventTime);
         mCounter++;
+        mAnomalyTracker.checkAnomaly(mCounter);
     }
 }
 
@@ -91,14 +95,17 @@ void CountMetricProducer::flushCounterIfNeeded(const time_t& eventTime) {
     // TODO: add a KeyValuePair to StatsLogReport.
     ALOGD("CountMetric: dump counter %d", mCounter);
 
+    // adjust the bucket start time
+    time_t numBucketsForward = (eventTime - mCurrentBucketStartTime)
+            / mBucketSize_sec;
+
+    mCurrentBucketStartTime = mCurrentBucketStartTime +
+            (numBucketsForward) * mBucketSize_sec;
+
     // reset counter
+    mAnomalyTracker.addPastBucket(mCounter, numBucketsForward);
     mCounter = 0;
 
-    // adjust the bucket start time
-    mCurrentBucketStartTime =
-            mCurrentBucketStartTime +
-            ((eventTime - mCurrentBucketStartTime) / mBucketSize_sec) * mBucketSize_sec;
-
     VLOG("new bucket start time: %lu", mCurrentBucketStartTime);
 }
 
diff --git a/cmds/statsd/src/metrics/CountMetricProducer.h b/cmds/statsd/src/metrics/CountMetricProducer.h
index 766579166972..7502320410ac 100644
--- a/cmds/statsd/src/metrics/CountMetricProducer.h
+++ b/cmds/statsd/src/metrics/CountMetricProducer.h
@@ -21,6 +21,7 @@
 #include <thread>
 #include <unordered_map>
 #include "../matchers/LogEntryMatcherManager.h"
+#include "CountAnomalyTracker.h"
 #include "ConditionTracker.h"
 #include "DropboxWriter.h"
 #include "MetricProducer.h"
@@ -52,12 +53,15 @@ private:
 
     const time_t mStartTime;
     // TODO: Add dimensions.
+    // Counter value for the current bucket.
     int mCounter;
 
     time_t mCurrentBucketStartTime;
 
     long mBucketSize_sec;
 
+    CountAnomalyTracker mAnomalyTracker;
+
     void flushCounterIfNeeded(const time_t& newEventTime);
 };