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