1 // Copyright (c) 2012 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 5 // The ExtensionsQuotaService uses heuristics to limit abusive requests 6 // made by extensions. In this model 'items' (e.g individual bookmarks) are 7 // represented by a 'Bucket' that holds state for that item for one single 8 // interval of time. The interval of time is defined as 'how long we need to 9 // watch an item (for a particular heuristic) before making a decision about 10 // quota violations'. A heuristic is two functions: one mapping input 11 // arguments to a unique Bucket (the BucketMapper), and another to determine 12 // if a new request involving such an item at a given time is a violation. 13 14 #ifndef CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_ 15 #define CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_ 16 17 #include <list> 18 #include <map> 19 #include <string> 20 21 #include "base/compiler_specific.h" 22 #include "base/containers/hash_tables.h" 23 #include "base/memory/scoped_ptr.h" 24 #include "base/threading/non_thread_safe.h" 25 #include "base/time/time.h" 26 #include "base/timer/timer.h" 27 #include "base/values.h" 28 29 class ExtensionFunction; 30 class QuotaLimitHeuristic; 31 typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics; 32 33 namespace extensions { 34 class TestResetQuotaFunction; 35 } 36 37 // The ExtensionsQuotaService takes care that calls to certain extension 38 // functions do not exceed predefined quotas. 39 // 40 // The ExtensionsQuotaService needs to live entirely on one thread, i.e. 41 // be created, called and destroyed on the same thread, due to its use 42 // of a RepeatingTimer. 43 class ExtensionsQuotaService : public base::NonThreadSafe { 44 public: 45 // Some concrete heuristics (declared below) that ExtensionFunctions can 46 // use to help the service make decisions about quota violations. 47 class TimedLimit; 48 class SustainedLimit; 49 50 ExtensionsQuotaService(); 51 virtual ~ExtensionsQuotaService(); 52 53 // Decide whether the invocation of |function| with argument |args| by the 54 // extension specified by |extension_id| results in a quota limit violation. 55 // Returns an error message representing the failure if quota was exceeded, 56 // or empty-string if the request is fine and can proceed. 57 std::string Assess(const std::string& extension_id, 58 ExtensionFunction* function, 59 const base::ListValue* args, 60 const base::TimeTicks& event_time); 61 62 private: 63 friend class extensions::TestResetQuotaFunction; 64 typedef std::string ExtensionId; 65 typedef std::string FunctionName; 66 // All QuotaLimitHeuristic instances in this map are owned by us. 67 typedef std::map<FunctionName, QuotaLimitHeuristics> FunctionHeuristicsMap; 68 69 // Purge resets all accumulated data (except |violation_errors_|) as if the 70 // service was just created. Called periodically so we don't consume an 71 // unbounded amount of memory while tracking quota. Yes, this could mean an 72 // extension gets away with murder if it is timed right, but the extensions 73 // we are trying to limit are ones that consistently violate, so we'll 74 // converge to the correct set. 75 void Purge(); 76 void PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map); 77 base::RepeatingTimer<ExtensionsQuotaService> purge_timer_; 78 79 // Our quota tracking state for extensions that have invoked quota limited 80 // functions. Each extension is treated separately, so extension ids are the 81 // key for the mapping. As an extension invokes functions, the map keeps 82 // track of which functions it has invoked and the heuristics for each one. 83 // Each heuristic will be evaluated and ANDed together to get a final answer. 84 std::map<ExtensionId, FunctionHeuristicsMap> function_heuristics_; 85 86 // For now, as soon as an extension violates quota, we don't allow it to 87 // make any more requests to quota limited functions. This provides a quick 88 // lookup for these extensions that is only stored in memory. 89 typedef std::map<std::string, std::string> ViolationErrorMap; 90 ViolationErrorMap violation_errors_; 91 92 DISALLOW_COPY_AND_ASSIGN(ExtensionsQuotaService); 93 }; 94 95 // A QuotaLimitHeuristic is two things: 1, A heuristic to map extension 96 // function arguments to corresponding Buckets for each input arg, and 2) a 97 // heuristic for determining if a new event involving a particular item 98 // (represented by its Bucket) constitutes a quota violation. 99 class QuotaLimitHeuristic { 100 public: 101 // Parameters to configure the amount of tokens allotted to individual 102 // Bucket objects (see Below) and how often they are replenished. 103 struct Config { 104 // The maximum number of tokens a bucket can contain, and is refilled to 105 // every epoch. 106 int64 refill_token_count; 107 108 // Specifies how frequently the bucket is logically refilled with tokens. 109 base::TimeDelta refill_interval; 110 }; 111 112 // A Bucket is how the heuristic portrays an individual item (since quota 113 // limits are per item) and all associated state for an item that needs to 114 // carry through multiple calls to Apply. It "holds" tokens, which are 115 // debited and credited in response to new events involving the item being 116 // being represented. For convenience, instead of actually periodically 117 // refilling buckets they are just 'Reset' on-demand (e.g. when new events 118 // come in). So, a bucket has an expiration to denote it has becomes stale. 119 class Bucket { 120 public: 121 Bucket() : num_tokens_(0) {} 122 // Removes a token from this bucket, and returns true if the bucket had 123 // any tokens in the first place. 124 bool DeductToken() { return num_tokens_-- > 0; } 125 126 // Returns true if this bucket has tokens to deduct. 127 bool has_tokens() const { return num_tokens_ > 0; } 128 129 // Reset this bucket to specification (from internal configuration), to be 130 // valid from |start| until the first refill interval elapses and it needs 131 // to be reset again. 132 void Reset(const Config& config, const base::TimeTicks& start); 133 134 // The time at which the token count and next expiration should be reset, 135 // via a call to Reset. 136 const base::TimeTicks& expiration() { return expiration_; } 137 private: 138 base::TimeTicks expiration_; 139 int64 num_tokens_; 140 DISALLOW_COPY_AND_ASSIGN(Bucket); 141 }; 142 typedef std::list<Bucket*> BucketList; 143 144 // A helper interface to retrieve the bucket corresponding to |args| from 145 // the set of buckets (which is typically stored in the BucketMapper itself) 146 // for this QuotaLimitHeuristic. 147 class BucketMapper { 148 public: 149 virtual ~BucketMapper() {} 150 // In most cases, this should simply extract item IDs from the arguments 151 // (e.g for bookmark operations involving an existing item). If a problem 152 // occurs while parsing |args|, the function aborts - buckets may be non- 153 // empty). The expectation is that invalid args and associated errors are 154 // handled by the ExtensionFunction itself so we don't concern ourselves. 155 virtual void GetBucketsForArgs(const base::ListValue* args, 156 BucketList* buckets) = 0; 157 }; 158 159 // Maps all calls to the same bucket, regardless of |args|, for this 160 // QuotaLimitHeuristic. 161 class SingletonBucketMapper : public BucketMapper { 162 public: 163 SingletonBucketMapper() {} 164 virtual ~SingletonBucketMapper() {} 165 virtual void GetBucketsForArgs(const base::ListValue* args, 166 BucketList* buckets) OVERRIDE; 167 168 private: 169 Bucket bucket_; 170 DISALLOW_COPY_AND_ASSIGN(SingletonBucketMapper); 171 }; 172 173 // Ownership of |map| is given to the new QuotaLimitHeuristic. 174 QuotaLimitHeuristic(const Config& config, 175 BucketMapper* map, 176 const std::string& name); 177 virtual ~QuotaLimitHeuristic(); 178 179 // Determines if sufficient quota exists (according to the Apply 180 // implementation of a derived class) to perform an operation with |args|, 181 // based on the history of similar operations with similar arguments (which 182 // is retrieved using the BucketMapper). 183 bool ApplyToArgs(const base::ListValue* args, 184 const base::TimeTicks& event_time); 185 186 // Returns an error formatted according to this heuristic. 187 std::string GetError() const; 188 189 protected: 190 const Config& config() { return config_; } 191 192 // Determine if the new event occurring at |event_time| involving |bucket| 193 // constitutes a quota violation according to this heuristic. 194 virtual bool Apply(Bucket* bucket, const base::TimeTicks& event_time) = 0; 195 196 private: 197 friend class QuotaLimitHeuristicTest; 198 199 const Config config_; 200 201 // The mapper used in Map. Cannot be NULL. 202 scoped_ptr<BucketMapper> bucket_mapper_; 203 204 // The name of the heuristic for formatting error messages. 205 std::string name_; 206 207 DISALLOW_COPY_AND_ASSIGN(QuotaLimitHeuristic); 208 }; 209 210 // A simple per-item heuristic to limit the number of events that can occur in 211 // a given period of time; e.g "no more than 100 events in an hour". 212 class ExtensionsQuotaService::TimedLimit : public QuotaLimitHeuristic { 213 public: 214 TimedLimit(const Config& config, BucketMapper* map, const std::string& name) 215 : QuotaLimitHeuristic(config, map, name) {} 216 virtual bool Apply(Bucket* bucket, 217 const base::TimeTicks& event_time) OVERRIDE; 218 }; 219 220 // A per-item heuristic to limit the number of events that can occur in a 221 // period of time over a sustained longer interval. E.g "no more than two 222 // events per minute, sustained over 10 minutes". 223 class ExtensionsQuotaService::SustainedLimit : public QuotaLimitHeuristic { 224 public: 225 SustainedLimit(const base::TimeDelta& sustain, 226 const Config& config, 227 BucketMapper* map, 228 const std::string& name); 229 virtual bool Apply(Bucket* bucket, 230 const base::TimeTicks& event_time) OVERRIDE; 231 private: 232 // Specifies how long exhaustion of buckets is allowed to continue before 233 // denying requests. 234 const int64 repeat_exhaustion_allowance_; 235 int64 num_available_repeat_exhaustions_; 236 }; 237 238 #endif // CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_ 239