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