binary_data_histogram.h 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_ZUCCHINI_BINARY_DATA_HISTOGRAM_H_
  5. #define COMPONENTS_ZUCCHINI_BINARY_DATA_HISTOGRAM_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <memory>
  9. #include <string>
  10. #include "components/zucchini/buffer_view.h"
  11. namespace zucchini {
  12. // A class to detect outliers in a list of doubles using Chauvenet's criterion:
  13. // Compute mean and standard deviation of observations, then determine whether
  14. // a query value lies beyond a fixed number of standard deviations (sigmas) from
  15. // the mean. The purpose of this test is to reduce the chance of false-positive
  16. // ensemble matches.
  17. class OutlierDetector {
  18. public:
  19. OutlierDetector();
  20. OutlierDetector(const OutlierDetector&) = delete;
  21. const OutlierDetector& operator=(const OutlierDetector&) = delete;
  22. ~OutlierDetector();
  23. // Incorporates |sample| into mean and standard deviation.
  24. void Add(double sample);
  25. // Prepares basic statistics for DecideOutlier() calls. Should be called after
  26. // all samples have been added.
  27. void Prepare();
  28. // Renders current statistics as strings for logging.
  29. std::string RenderStats();
  30. // Heuristically decides whether |sample| is an outlier. Returns 1 if |sample|
  31. // is "too high", 0 if |sample| is "normal", and -1 if |sample| is "too low".
  32. // Must be called after Prepare().
  33. int DecideOutlier(double sample);
  34. private:
  35. size_t n_ = 0;
  36. double sum_ = 0;
  37. double sum_of_squares_ = 0;
  38. double mean_ = 0;
  39. double standard_deviation_ = 0;
  40. };
  41. // A class to compute similarity score between binary data. The heuristic here
  42. // preprocesses input data to a size-65536 histogram, counting the frequency of
  43. // consecutive 2-byte sequences. Therefore data with lengths < 2 are considered
  44. // invalid -- but this is okay for Zucchini's use case.
  45. class BinaryDataHistogram {
  46. public:
  47. BinaryDataHistogram();
  48. BinaryDataHistogram(const BinaryDataHistogram&) = delete;
  49. const BinaryDataHistogram& operator=(const BinaryDataHistogram&) = delete;
  50. ~BinaryDataHistogram();
  51. // Attempts to compute the histogram, returns true iff successful.
  52. bool Compute(ConstBufferView region);
  53. bool IsValid() const { return static_cast<bool>(histogram_); }
  54. // Returns distance to another histogram (heuristics). If two binaries are
  55. // identical then their histogram distance is 0. However, the converse is not
  56. // true in general. For example, "aba" and "bab" are different, but their
  57. // histogram distance is 0 (both histograms are {"ab": 1, "ba": 1}).
  58. double Distance(const BinaryDataHistogram& other) const;
  59. private:
  60. enum { kNumBins = 1 << (sizeof(uint16_t) * 8) };
  61. static_assert(kNumBins == 65536, "Incorrect constant computation.");
  62. // Size, in bytes, of the data over which the histogram was computed.
  63. size_t size_ = 0;
  64. // 2^16 buckets holding counts of all 2-byte sequences in the data. The counts
  65. // are stored as signed values to simplify computing the distance between two
  66. // histograms.
  67. std::unique_ptr<int32_t[]> histogram_;
  68. };
  69. } // namespace zucchini
  70. #endif // COMPONENTS_ZUCCHINI_BINARY_DATA_HISTOGRAM_H_