chrome/browser/profile_resetter/jtl_foundation.h

   1 // Copyright 2013 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 #ifndef CHROME_BROWSER_PROFILE_RESETTER_JTL_FOUNDATION_H_
   6 #define CHROME_BROWSER_PROFILE_RESETTER_JTL_FOUNDATION_H_
   7
   8 #include <map>
   9 #include <string>
  10
  11 #include "base/basictypes.h"
  12 #include "crypto/hmac.h"
  13
  14 namespace jtl_foundation {
  15
  16 // A JTL (JSON Traversal Language) program is composed of one or more
  17 // sentences. Each sentence consists of a sequence of operations. The input of
  18 // the program is a hierarchical JSON data structure.
  19 //
  20 // The execution of each sentence starts at the root of an input dictionary. The
  21 // operations include navigation in the JSON data structure, as well as
  22 // comparing the current (leaf) node to fixed values. The program also has a
  23 // separate dictionary as working memory, into which it can memorize data, then
  24 // later recall it for comparisons.
  25 //
  26 // Example program:
  27 // NAVIGATE_ANY
  28 // NAVIGATE(hash("bar"))
  29 // COMPARE_NODE_BOOL(1)
  30 // STORE_BOOL(hash("found_foo"), 1)
  31 // STOP_EXECUTING_SENTENCE
  32 //
  33 // Example input:
  34 // {
  35 //   'key1': 1,
  36 //   'key2': {'foo': 0, 'bar': false, 'baz': 2}
  37 //   'key3': {'foo': 0, 'bar': true, 'baz': 2}
  38 //   'key4': {'foo': 0, 'bar': true, 'baz': 2}
  39 // }
  40 //
  41 // This program navigates from the root of the dictionary to all children
  42 // ("key1", "key2", "key3", "key4") and executes the remaining program on each
  43 // of the children. The navigation happens in depth-first pre-order. On each of
  44 // the children it tries to navigate into the child "bar", which fails for
  45 // "key1", so execution stops for this sub-branch. On key2 the program navigates
  46 // to "bar" and moves the execution context to this node which has the value
  47 // "false". Therefore, the following COMPARE_NODE_BOOL is not fulfilled and the
  48 // execution does not continue on this branch, so we back track and proceed with
  49 // "key3" and its "bar" child. For this node, COMPARE_NODE_BOOL is fulfilled and
  50 // the execution continues to store "found_foo = true" into the working memory
  51 // of the interpreter. Next the interpreter executes STOP_EXECUTING_SENTENCE
  52 // which prevents the traversal from descending into the "key4" branch from the
  53 // NAVIGATE_ANY operation and can therefore speedup the processing.
  54 //
  55 // All node names, and node values of type string, integer and double are hashed
  56 // before being compared to hash values listed in |program|.
  57
  58 // JTL byte code consists of uint8 opcodes followed by parameters. Parameters
  59 // are either boolean (uint8 with value \x00 or \x01), uint32 (in little-endian
  60 // notation), or hash string of 32 bytes.
  61 // The following opcodes are defined:
  62 enum OpCodes {
  63   // Continues execution with the next operation on the element of a
  64   // dictionary that matches the passed key parameter. If no such element
  65   // exists, the command execution returns from the current instruction.
  66   // Parameters:
  67   // - a 32 byte hash of the target dictionary key.
  68   NAVIGATE = 0x00,
  69   // Continues execution with the next operation on each element of a
  70   // dictionary or list. If no such element exists or the current element is
  71   // neither a dictionary or list, the command execution returns from the
  72   // current instruction.
  73   NAVIGATE_ANY = 0x01,
  74   // Continues execution with the next operation on the parent node of the
  75   // current node. If the current node is the root of the input dictionary, the
  76   // program execution fails with a runtime error.
  77   NAVIGATE_BACK = 0x02,
  78   // Stores a boolean value in the working memory.
  79   // Parameters:
  80   // - a 32 byte hash of the parameter name,
  81   // - the value to store (\x00 or \x01)
  82   STORE_BOOL = 0x10,
  83   // Checks whether a boolean stored in working memory matches the expected
  84   // value and continues execution with the next operation in case of a match.
  85   // Parameters:
  86   // - a 32 byte hash of the parameter name,
  87   // - the expected value (\x00 or \x01),
  88   // - the default value in case the working memory contains no corresponding
  89   //   entry (\x00 or\x01).
  90   COMPARE_STORED_BOOL = 0x11,
  91   // Same as STORE_BOOL but takes a hash instead of a boolean value as
  92   // parameter.
  93   STORE_HASH = 0x12,
  94   // Same as COMPARE_STORED_BOOL but takes a hash instead of two boolean values
  95   // as parameters.
  96   COMPARE_STORED_HASH = 0x13,
  97   // Stores the current node into the working memory. If the current node is not
  98   // a boolean value, the program execution returns from the current
  99   // instruction.
 100   // Parameters:
 101   // - a 32 byte hash of the parameter name.
 102   STORE_NODE_BOOL = 0x14,
 103   // Stores the hashed value of the current node into the working memory. If
 104   // the current node is not a string, integer or double, the program execution
 105   // returns from the current instruction.
 106   // Parameters:
 107   // - a 32 byte hash of the parameter name.
 108   STORE_NODE_HASH = 0x15,
 109   // Parses the value of the current node as a URL, extracts the subcomponent of
 110   // the domain name that is immediately below the registrar-controlled portion,
 111   // and stores the hash of this subcomponent into working memory. In case the
 112   // domain name ends in a suffix not on the Public Suffix List (i.e. is neither
 113   // an ICANN, nor a private domain suffix), the last subcomponent is assumed to
 114   // be the registry, and the second-to-last subcomponent is extracted.
 115   // If the current node is not a string that represents a URL, or if this URL
 116   // does not have a domain component as described above, the program execution
 117   // returns from the current instruction.
 118   // For example, "foo.com", "www.foo.co.uk", "foo.appspot.com", and "foo.bar"
 119   // will all yield (the hash of) "foo" as a result.
 120   // See the unit test for more details.
 121   // Parameters:
 122   // - a 32 byte hash of the parameter name.
 123   STORE_NODE_REGISTERABLE_DOMAIN_HASH = 0x16,
 124   // Compares the current node against a boolean value and continues execution
 125   // with the next operation in case of a match. If the current node does not
 126   // match or is not a boolean value, the program execution returns from the
 127   // current instruction.
 128   // Parameters:
 129   // - a boolean value (\x00 or \x01).
 130   COMPARE_NODE_BOOL = 0x20,
 131   // Compares the hashed value of the current node against the given hash, and
 132   // continues execution with the next operation in case of a match. If the
 133   // current node is not a string, integer or double, or if it is either, but
 134   // its hash does not match, the program execution returns from the current
 135   // instruction.
 136   // Parameters:
 137   // - a 32 byte hash of the expected value.
 138   COMPARE_NODE_HASH = 0x21,
 139   // The negation of the above.
 140   COMPARE_NODE_HASH_NOT = 0x22,
 141   // Compares the current node against a boolean value stored in working memory,
 142   // and continues with the next operation in case of a match. If the current
 143   // node is not a boolean value, the working memory contains no corresponding
 144   // boolean value, or if they do not match, the program execution returns from
 145   // the current instruction.
 146   // Parameters:
 147   // - a 32 byte hash of the parameter name.
 148   COMPARE_NODE_TO_STORED_BOOL = 0x23,
 149   // Compares the hashed value of the current node against a hash value stored
 150   // in working memory, and continues with the next operation in case of a
 151   // match. If the current node is not a string, integer or double, or if the
 152   // working memory contains no corresponding hash string, or if the hashes do
 153   // not match, the program execution returns from the current instruction.
 154   // Parameters:
 155   // - a 32 byte hash of the parameter name.
 156   COMPARE_NODE_TO_STORED_HASH = 0x24,
 157   // Checks whether the current node is a string value that contains the given
 158   // pattern as a substring, and continues execution with the next operation in
 159   // case it does. If the current node is not a string, or if does not match the
 160   // pattern, the program execution returns from the current instruction.
 161   // Parameters:
 162   // - a 32 byte hash of the pattern,
 163   // - a 4 byte unsigned integer: the length (>0) of the pattern in bytes,
 164   // - a 4 byte unsigned integer: the sum of all bytes in the pattern, serving
 165   //   as a heuristic to reduce the number of actual SHA-256 calculations.
 166   COMPARE_NODE_SUBSTRING = 0x25,
 167   // Stop execution in this specific sentence.
 168   STOP_EXECUTING_SENTENCE = 0x30,
 169   // Separator between sentences, starts a new sentence.
 170   END_OF_SENTENCE = 0x31
 171 };
 172
 173 const size_t kHashSizeInBytes = 32u;
 174
 175 // A class that provides SHA256 hash values for strings using a fixed hash seed.
 176 class Hasher {
 177  public:
 178   explicit Hasher(const std::string& seed);
 179   ~Hasher();
 180
 181   std::string GetHash(const std::string& input) const;
 182
 183   static bool IsHash(const std::string& maybe_hash);
 184
 185  private:
 186   crypto::HMAC hmac_;
 187   mutable std::map<std::string, std::string> cached_hashes_;
 188   DISALLOW_COPY_AND_ASSIGN(Hasher);
 189 };
 190
 191 }  // namespace jtl_foundation
 192
 193 #endif  // CHROME_BROWSER_PROFILE_RESETTER_JTL_FOUNDATION_H_