Statsd Anomaly tracking for CountMetricProducer
CountMetricProducer now has a CountAnomalyTracker which stores past
bucket information. Anomalies can be determined by seeing if the
information from the past and current buckets exeeds a threshold.
Test: manual
Change-Id: I35103c01dd32dcc31cb155f5685161cbaf969d03
diff --git a/cmds/statsd/Android.mk b/cmds/statsd/Android.mk
index e2e1a7f..5c2831c 100644
--- a/cmds/statsd/Android.mk
+++ b/cmds/statsd/Android.mk
@@ -57,7 +57,7 @@
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 0000000..ebd53e0
--- /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 0000000..449dee9
--- /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 fbd013e..635777f 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 @@
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 @@
if (mConditionTracker->isConditionMet()) {
flushCounterIfNeeded(eventTime);
mCounter++;
+ mAnomalyTracker.checkAnomaly(mCounter);
}
}
@@ -91,13 +95,16 @@
// TODO: add a KeyValuePair to StatsLogReport.
ALOGD("CountMetric: dump counter %d", mCounter);
- // reset counter
- mCounter = 0;
-
// adjust the bucket start time
- mCurrentBucketStartTime =
- mCurrentBucketStartTime +
- ((eventTime - mCurrentBucketStartTime) / mBucketSize_sec) * mBucketSize_sec;
+ time_t numBucketsForward = (eventTime - mCurrentBucketStartTime)
+ / mBucketSize_sec;
+
+ mCurrentBucketStartTime = mCurrentBucketStartTime +
+ (numBucketsForward) * mBucketSize_sec;
+
+ // reset counter
+ mAnomalyTracker.addPastBucket(mCounter, numBucketsForward);
+ mCounter = 0;
VLOG("new bucket start time: %lu", mCurrentBucketStartTime);
}
diff --git a/cmds/statsd/src/metrics/CountMetricProducer.h b/cmds/statsd/src/metrics/CountMetricProducer.h
index 7665791..7502320 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 @@
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);
};