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