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 14namespace 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: 62enum 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 173const size_t kHashSizeInBytes = 32u; 174 175// A class that provides SHA256 hash values for strings using a fixed hash seed. 176class 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_ 194