1 // Copyright 2013 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 QuotaService 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 EXTENSIONS_BROWSER_QUOTA_SERVICE_H_ 15 #define EXTENSIONS_BROWSER_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 31 namespace extensions { 32 class QuotaLimitHeuristic; 33 34 typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics; 35 36 // The QuotaService takes care that calls to certain extension 37 // functions do not exceed predefined quotas. 38 // 39 // The QuotaService needs to live entirely on one thread, i.e. be created, 40 // called and destroyed on the same thread, due to its use of a RepeatingTimer. 41 // It is not a KeyedService because instances exist on both the UI 42 // and IO threads. 43 class QuotaService : 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 QuotaService(); 51 virtual ~QuotaService(); 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 typedef std::string ExtensionId; 64 typedef std::string FunctionName; 65 // All QuotaLimitHeuristic instances in this map are owned by us. 66 typedef std::map<FunctionName, QuotaLimitHeuristics> FunctionHeuristicsMap; 67 68 // Purge resets all accumulated data (except |violation_errors_|) as if the 69 // service was just created. Called periodically so we don't consume an 70 // unbounded amount of memory while tracking quota. Yes, this could mean an 71 // extension gets away with murder if it is timed right, but the extensions 72 // we are trying to limit are ones that consistently violate, so we'll 73 // converge to the correct set. 74 void Purge(); 75 void PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map); 76 base::RepeatingTimer<QuotaService> purge_timer_; 77 78 // Our quota tracking state for extensions that have invoked quota limited 79 // functions. Each extension is treated separately, so extension ids are the 80 // key for the mapping. As an extension invokes functions, the map keeps 81 // track of which functions it has invoked and the heuristics for each one. 82 // Each heuristic will be evaluated and ANDed together to get a final answer. 83 std::map<ExtensionId, FunctionHeuristicsMap> function_heuristics_; 84 85 // For now, as soon as an extension violates quota, we don't allow it to 86 // make any more requests to quota limited functions. This provides a quick 87 // lookup for these extensions that is only stored in memory. 88 typedef std::map<std::string, std::string> ViolationErrorMap; 89 ViolationErrorMap violation_errors_; 90 91 DISALLOW_COPY_AND_ASSIGN(QuotaService); 92 }; 93 94 // A QuotaLimitHeuristic is two things: 1, A heuristic to map extension 95 // function arguments to corresponding Buckets for each input arg, and 2) a 96 // heuristic for determining if a new event involving a particular item 97 // (represented by its Bucket) constitutes a quota violation. 98 class QuotaLimitHeuristic { 99 public: 100 // Parameters to configure the amount of tokens allotted to individual 101 // Bucket objects (see Below) and how often they are replenished. 102 struct Config { 103 // The maximum number of tokens a bucket can contain, and is refilled to 104 // every epoch. 105 int64 refill_token_count; 106 107 // Specifies how frequently the bucket is logically refilled with tokens. 108 base::TimeDelta refill_interval; 109 }; 110 111 // A Bucket is how the heuristic portrays an individual item (since quota 112 // limits are per item) and all associated state for an item that needs to 113 // carry through multiple calls to Apply. It "holds" tokens, which are 114 // debited and credited in response to new events involving the item being 115 // being represented. For convenience, instead of actually periodically 116 // refilling buckets they are just 'Reset' on-demand (e.g. when new events 117 // come in). So, a bucket has an expiration to denote it has becomes stale. 118 class Bucket { 119 public: Bucket()120 Bucket() : num_tokens_(0) {} 121 // Removes a token from this bucket, and returns true if the bucket had 122 // any tokens in the first place. DeductToken()123 bool DeductToken() { return num_tokens_-- > 0; } 124 125 // Returns true if this bucket has tokens to deduct. has_tokens()126 bool has_tokens() const { return num_tokens_ > 0; } 127 128 // Reset this bucket to specification (from internal configuration), to be 129 // valid from |start| until the first refill interval elapses and it needs 130 // to be reset again. 131 void Reset(const Config& config, const base::TimeTicks& start); 132 133 // The time at which the token count and next expiration should be reset, 134 // via a call to Reset. expiration()135 const base::TimeTicks& expiration() { return expiration_; } 136 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: ~BucketMapper()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: SingletonBucketMapper()163 SingletonBucketMapper() {} ~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: config()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 QuotaService::TimedLimit : public QuotaLimitHeuristic { 213 public: TimedLimit(const Config & config,BucketMapper * map,const std::string & name)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 QuotaService::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 232 private: 233 // Specifies how long exhaustion of buckets is allowed to continue before 234 // denying requests. 235 const int64 repeat_exhaustion_allowance_; 236 int64 num_available_repeat_exhaustions_; 237 }; 238 239 } // namespace extensions 240 241 #endif // EXTENSIONS_BROWSER_QUOTA_SERVICE_H_ 242