1 // Copyright (c) 2009 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 #include "base/stl_util-inl.h"
6 #include "base/string_util.h"
7 #include "chrome/browser/extensions/extension_function.h"
8 #include "chrome/browser/extensions/extensions_quota_service.h"
9 #include "testing/gtest/include/gtest/gtest.h"
10
11 using base::TimeDelta;
12 using base::TimeTicks;
13
14 typedef QuotaLimitHeuristic::Bucket Bucket;
15 typedef QuotaLimitHeuristic::Config Config;
16 typedef QuotaLimitHeuristic::BucketList BucketList;
17 typedef ExtensionsQuotaService::TimedLimit TimedLimit;
18 typedef ExtensionsQuotaService::SustainedLimit SustainedLimit;
19
20 static const Config kFrozenConfig = { 0, TimeDelta::FromDays(0) };
21 static const Config k2PerMinute = { 2, TimeDelta::FromMinutes(1) };
22 static const Config k20PerHour = { 20, TimeDelta::FromHours(1) };
23 static const TimeTicks kStartTime = TimeTicks();
24 static const TimeTicks k1MinuteAfterStart =
25 kStartTime + TimeDelta::FromMinutes(1);
26
27 namespace {
28 class Mapper : public QuotaLimitHeuristic::BucketMapper {
29 public:
Mapper()30 Mapper() {}
~Mapper()31 virtual ~Mapper() { STLDeleteValues(&buckets_); }
GetBucketsForArgs(const ListValue * args,BucketList * buckets)32 virtual void GetBucketsForArgs(const ListValue* args, BucketList* buckets) {
33 for (size_t i = 0; i < args->GetSize(); i++) {
34 int id;
35 ASSERT_TRUE(args->GetInteger(i, &id));
36 if (buckets_.find(id) == buckets_.end())
37 buckets_[id] = new Bucket();
38 buckets->push_back(buckets_[id]);
39 }
40 }
41 private:
42 typedef std::map<int, Bucket*> BucketMap;
43 BucketMap buckets_;
44 DISALLOW_COPY_AND_ASSIGN(Mapper);
45 };
46
47 class MockMapper : public QuotaLimitHeuristic::BucketMapper {
48 public:
GetBucketsForArgs(const ListValue * args,BucketList * buckets)49 virtual void GetBucketsForArgs(const ListValue* args, BucketList* buckets) {}
50 };
51
52 class MockFunction : public ExtensionFunction {
53 public:
MockFunction(const std::string & name)54 explicit MockFunction(const std::string& name) { set_name(name); }
SetArgs(const ListValue * args)55 virtual void SetArgs(const ListValue* args) {}
GetError()56 virtual const std::string GetError() { return std::string(); }
GetResult()57 virtual const std::string GetResult() { return std::string(); }
Run()58 virtual void Run() {}
59 };
60
61 class TimedLimitMockFunction : public MockFunction {
62 public:
TimedLimitMockFunction(const std::string & name)63 explicit TimedLimitMockFunction(const std::string& name)
64 : MockFunction(name) {}
GetQuotaLimitHeuristics(QuotaLimitHeuristics * heuristics) const65 virtual void GetQuotaLimitHeuristics(
66 QuotaLimitHeuristics* heuristics) const {
67 heuristics->push_back(new TimedLimit(k2PerMinute, new Mapper()));
68 }
69 };
70
71 class ChainedLimitsMockFunction : public MockFunction {
72 public:
ChainedLimitsMockFunction(const std::string & name)73 explicit ChainedLimitsMockFunction(const std::string& name)
74 : MockFunction(name) {}
GetQuotaLimitHeuristics(QuotaLimitHeuristics * heuristics) const75 virtual void GetQuotaLimitHeuristics(
76 QuotaLimitHeuristics* heuristics) const {
77 // No more than 2 per minute sustained over 5 minutes.
78 heuristics->push_back(new SustainedLimit(TimeDelta::FromMinutes(5),
79 k2PerMinute, new Mapper()));
80 // No more than 20 per hour.
81 heuristics->push_back(new TimedLimit(k20PerHour, new Mapper()));
82 }
83 };
84
85 class FrozenMockFunction : public MockFunction {
86 public:
FrozenMockFunction(const std::string & name)87 explicit FrozenMockFunction(const std::string& name) : MockFunction(name) {}
GetQuotaLimitHeuristics(QuotaLimitHeuristics * heuristics) const88 virtual void GetQuotaLimitHeuristics(
89 QuotaLimitHeuristics* heuristics) const {
90 heuristics->push_back(new TimedLimit(kFrozenConfig, new Mapper()));
91 }
92 };
93 } // namespace
94
95 class ExtensionsQuotaServiceTest : public testing::Test {
96 public:
ExtensionsQuotaServiceTest()97 ExtensionsQuotaServiceTest()
98 : extension_a_("a"), extension_b_("b"), extension_c_("c") {}
SetUp()99 virtual void SetUp() {
100 service_.reset(new ExtensionsQuotaService());
101 }
TearDown()102 virtual void TearDown() {
103 service_.reset();
104 }
105 protected:
106 std::string extension_a_;
107 std::string extension_b_;
108 std::string extension_c_;
109 scoped_ptr<ExtensionsQuotaService> service_;
110 };
111
112 class QuotaLimitHeuristicTest : public testing::Test {
113 public:
DoMoreThan2PerMinuteFor5Minutes(const TimeTicks & start_time,QuotaLimitHeuristic * lim,Bucket * b,int an_unexhausted_minute)114 static void DoMoreThan2PerMinuteFor5Minutes(const TimeTicks& start_time,
115 QuotaLimitHeuristic* lim,
116 Bucket* b,
117 int an_unexhausted_minute) {
118 for (int i = 0; i < 5; i++) {
119 // Perform one operation in each minute.
120 int m = i * 60;
121 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(10 + m)));
122 EXPECT_TRUE(b->has_tokens());
123
124 if (i == an_unexhausted_minute)
125 continue; // Don't exhaust all tokens this minute.
126
127 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(15 + m)));
128 EXPECT_FALSE(b->has_tokens());
129
130 // These are OK because we haven't exhausted all buckets.
131 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(20 + m)));
132 EXPECT_FALSE(b->has_tokens());
133 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(50 + m)));
134 EXPECT_FALSE(b->has_tokens());
135 }
136 }
137 };
138
TEST_F(QuotaLimitHeuristicTest,Timed)139 TEST_F(QuotaLimitHeuristicTest, Timed) {
140 TimedLimit lim(k2PerMinute, new MockMapper());
141 Bucket b;
142
143 b.Reset(k2PerMinute, kStartTime);
144 EXPECT_TRUE(lim.Apply(&b, kStartTime));
145 EXPECT_TRUE(b.has_tokens());
146 EXPECT_TRUE(lim.Apply(&b, kStartTime + TimeDelta::FromSeconds(30)));
147 EXPECT_FALSE(b.has_tokens());
148 EXPECT_FALSE(lim.Apply(&b, k1MinuteAfterStart));
149
150 b.Reset(k2PerMinute, kStartTime);
151 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart - TimeDelta::FromSeconds(1)));
152 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart));
153 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(1)));
154 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(2)));
155 EXPECT_FALSE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(3)));
156 }
157
TEST_F(QuotaLimitHeuristicTest,Sustained)158 TEST_F(QuotaLimitHeuristicTest, Sustained) {
159 SustainedLimit lim(TimeDelta::FromMinutes(5), k2PerMinute, new MockMapper());
160 Bucket bucket;
161
162 bucket.Reset(k2PerMinute, kStartTime);
163 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1);
164 // This straw breaks the camel's back.
165 EXPECT_FALSE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6)));
166
167 // The heuristic resets itself on a safe request.
168 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromDays(1)));
169
170 // Do the same as above except don't exhaust final bucket.
171 bucket.Reset(k2PerMinute, kStartTime);
172 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1);
173 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(7)));
174
175 // Do the same as above except don't exhaust the 3rd (w.l.o.g) bucket.
176 bucket.Reset(k2PerMinute, kStartTime);
177 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, 3);
178 // If the 3rd bucket were exhausted, this would fail (see first test).
179 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6)));
180 }
181
TEST_F(ExtensionsQuotaServiceTest,NoHeuristic)182 TEST_F(ExtensionsQuotaServiceTest, NoHeuristic) {
183 scoped_refptr<MockFunction> f(new MockFunction("foo"));
184 ListValue args;
185 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime));
186 }
187
TEST_F(ExtensionsQuotaServiceTest,FrozenHeuristic)188 TEST_F(ExtensionsQuotaServiceTest, FrozenHeuristic) {
189 scoped_refptr<MockFunction> f(new FrozenMockFunction("foo"));
190 ListValue args;
191 args.Append(new FundamentalValue(1));
192 EXPECT_FALSE(service_->Assess(extension_a_, f, &args, kStartTime));
193 }
194
TEST_F(ExtensionsQuotaServiceTest,SingleHeuristic)195 TEST_F(ExtensionsQuotaServiceTest, SingleHeuristic) {
196 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
197 ListValue args;
198 args.Append(new FundamentalValue(1));
199 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime));
200 EXPECT_TRUE(service_->Assess(extension_a_, f, &args,
201 kStartTime + TimeDelta::FromSeconds(10)));
202 EXPECT_FALSE(service_->Assess(extension_a_, f, &args,
203 kStartTime + TimeDelta::FromSeconds(15)));
204
205 ListValue args2;
206 args2.Append(new FundamentalValue(1));
207 args2.Append(new FundamentalValue(2));
208 EXPECT_TRUE(service_->Assess(extension_b_, f, &args2, kStartTime));
209 EXPECT_TRUE(service_->Assess(extension_b_, f, &args2,
210 kStartTime + TimeDelta::FromSeconds(10)));
211
212 TimeDelta peace = TimeDelta::FromMinutes(30);
213 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, kStartTime + peace));
214 EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
215 kStartTime + peace + TimeDelta::FromSeconds(10)));
216 EXPECT_FALSE(service_->Assess(extension_b_, f, &args2,
217 kStartTime + peace + TimeDelta::FromSeconds(15)));
218
219 // Test that items are independent.
220 ListValue args3;
221 args3.Append(new FundamentalValue(3));
222 EXPECT_TRUE(service_->Assess(extension_c_, f, &args, kStartTime));
223 EXPECT_TRUE(service_->Assess(extension_c_, f, &args3,
224 kStartTime + TimeDelta::FromSeconds(10)));
225 EXPECT_TRUE(service_->Assess(extension_c_, f, &args,
226 kStartTime + TimeDelta::FromSeconds(15)));
227 EXPECT_TRUE(service_->Assess(extension_c_, f, &args3,
228 kStartTime + TimeDelta::FromSeconds(20)));
229 EXPECT_FALSE(service_->Assess(extension_c_, f, &args,
230 kStartTime + TimeDelta::FromSeconds(25)));
231 EXPECT_FALSE(service_->Assess(extension_c_, f, &args3,
232 kStartTime + TimeDelta::FromSeconds(30)));
233 }
234
TEST_F(ExtensionsQuotaServiceTest,ChainedHeuristics)235 TEST_F(ExtensionsQuotaServiceTest, ChainedHeuristics) {
236 scoped_refptr<MockFunction> f(new ChainedLimitsMockFunction("foo"));
237 ListValue args;
238 args.Append(new FundamentalValue(1));
239
240 // First, test that the low limit can be avoided but the higher one is hit.
241 // One event per minute for 20 minutes comes in under the sustained limit,
242 // but is equal to the timed limit.
243 for (int i = 0; i < 20; i++) {
244 EXPECT_TRUE(service_->Assess(extension_a_, f, &args,
245 kStartTime + TimeDelta::FromSeconds(10 + i * 60)));
246 }
247
248 // This will bring us to 21 events in an hour, which is a violation.
249 EXPECT_FALSE(service_->Assess(extension_a_, f, &args,
250 kStartTime + TimeDelta::FromMinutes(30)));
251
252 // Now, check that we can still hit the lower limit.
253 for (int i = 0; i < 5; i++) {
254 EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
255 kStartTime + TimeDelta::FromSeconds(10 + i * 60)));
256 EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
257 kStartTime + TimeDelta::FromSeconds(15 + i * 60)));
258 EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
259 kStartTime + TimeDelta::FromSeconds(20 + i * 60)));
260 }
261
262 EXPECT_FALSE(service_->Assess(extension_b_, f, &args,
263 kStartTime + TimeDelta::FromMinutes(6)));
264 }
265
TEST_F(ExtensionsQuotaServiceTest,MultipleFunctionsDontInterfere)266 TEST_F(ExtensionsQuotaServiceTest, MultipleFunctionsDontInterfere) {
267 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
268 scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar"));
269
270 ListValue args_f;
271 ListValue args_g;
272 args_f.Append(new FundamentalValue(1));
273 args_g.Append(new FundamentalValue(2));
274
275 EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f, kStartTime));
276 EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g, kStartTime));
277 EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f,
278 kStartTime + TimeDelta::FromSeconds(10)));
279 EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g,
280 kStartTime + TimeDelta::FromSeconds(10)));
281 EXPECT_FALSE(service_->Assess(extension_a_, f, &args_f,
282 kStartTime + TimeDelta::FromSeconds(15)));
283 EXPECT_FALSE(service_->Assess(extension_a_, g, &args_g,
284 kStartTime + TimeDelta::FromSeconds(15)));
285 }
286
TEST_F(ExtensionsQuotaServiceTest,ViolatorsWillBeViolators)287 TEST_F(ExtensionsQuotaServiceTest, ViolatorsWillBeViolators) {
288 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
289 scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar"));
290 ListValue arg;
291 arg.Append(new FundamentalValue(1));
292 EXPECT_TRUE(service_->Assess(extension_a_, f, &arg, kStartTime));
293 EXPECT_TRUE(service_->Assess(extension_a_, f, &arg,
294 kStartTime + TimeDelta::FromSeconds(10)));
295 EXPECT_FALSE(service_->Assess(extension_a_, f, &arg,
296 kStartTime + TimeDelta::FromSeconds(15)));
297
298 // We don't allow this extension to use quota limited functions even if they
299 // wait a while.
300 EXPECT_FALSE(service_->Assess(extension_a_, f, &arg,
301 kStartTime + TimeDelta::FromDays(1)));
302 EXPECT_FALSE(service_->Assess(extension_a_, g, &arg,
303 kStartTime + TimeDelta::FromDays(1)));
304 }
305