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.
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.
14 #ifndef CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_
15 #define CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_
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"
29 class ExtensionFunction;
30 class QuotaLimitHeuristic;
31 typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics;
33 namespace extensions {
34 class TestResetQuotaFunction;
37 // The ExtensionsQuotaService takes care that calls to certain extension
38 // functions do not exceed predefined quotas.
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 {
45 // Some concrete heuristics (declared below) that ExtensionFunctions can
46 // use to help the service make decisions about quota violations.
50 ExtensionsQuotaService();
51 virtual ~ExtensionsQuotaService();
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);
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;
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.
76 void PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map);
77 base::RepeatingTimer<ExtensionsQuotaService> purge_timer_;
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_;
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_;
92 DISALLOW_COPY_AND_ASSIGN(ExtensionsQuotaService);
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 {
101 // Parameters to configure the amount of tokens allotted to individual
102 // Bucket objects (see Below) and how often they are replenished.
104 // The maximum number of tokens a bucket can contain, and is refilled to
106 int64 refill_token_count;
108 // Specifies how frequently the bucket is logically refilled with tokens.
109 base::TimeDelta refill_interval;
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.
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; }
126 // Returns true if this bucket has tokens to deduct.
127 bool has_tokens() const { return num_tokens_ > 0; }
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);
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_; }
138 base::TimeTicks expiration_;
140 DISALLOW_COPY_AND_ASSIGN(Bucket);
142 typedef std::list<Bucket*> BucketList;
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.
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;
159 // Maps all calls to the same bucket, regardless of |args|, for this
160 // QuotaLimitHeuristic.
161 class SingletonBucketMapper : public BucketMapper {
163 SingletonBucketMapper() {}
164 virtual ~SingletonBucketMapper() {}
165 virtual void GetBucketsForArgs(const base::ListValue* args,
166 BucketList* buckets) OVERRIDE;
170 DISALLOW_COPY_AND_ASSIGN(SingletonBucketMapper);
173 // Ownership of |map| is given to the new QuotaLimitHeuristic.
174 QuotaLimitHeuristic(const Config& config,
176 const std::string& name);
177 virtual ~QuotaLimitHeuristic();
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);
186 // Returns an error formatted according to this heuristic.
187 std::string GetError() const;
190 const Config& config() { return config_; }
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;
197 friend class QuotaLimitHeuristicTest;
199 const Config config_;
201 // The mapper used in Map. Cannot be NULL.
202 scoped_ptr<BucketMapper> bucket_mapper_;
204 // The name of the heuristic for formatting error messages.
207 DISALLOW_COPY_AND_ASSIGN(QuotaLimitHeuristic);
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 {
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;
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 {
225 SustainedLimit(const base::TimeDelta& sustain,
226 const Config& config,
228 const std::string& name);
229 virtual bool Apply(Bucket* bucket,
230 const base::TimeTicks& event_time) OVERRIDE;
232 // Specifies how long exhaustion of buckets is allowed to continue before
234 const int64 repeat_exhaustion_allowance_;
235 int64 num_available_repeat_exhaustions_;
238 #endif // CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_