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 // Interprets the value of the current node as a URL, and stores the hash of 110 // its effective SLD (second-level domain) into the working memory. If the 111 // current node is not a string that represents a URL which has an SLD part, 112 // the program execution returns from the current instruction. 113 // Note: Effective SLD means the dot-separated part of the domain that is 114 // immediately below the portion that is controlled by a registrar. 115 // For instance, both "example.com" and "example.co.uk" will yield "example". 116 // See the unit test for more details. 117 // Parameters: 118 // - a 32 byte hash of the parameter name. 119 STORE_NODE_EFFECTIVE_SLD_HASH = 0x16, 120 // Compares the current node against a boolean value and continues execution 121 // with the next operation in case of a match. If the current node does not 122 // match or is not a boolean value, the program execution returns from the 123 // current instruction. 124 // Parameters: 125 // - a boolean value (\x00 or \x01). 126 COMPARE_NODE_BOOL = 0x20, 127 // Compares the hashed value of the current node against the given hash, and 128 // continues execution with the next operation in case of a match. If the 129 // current node is not a string, integer or double, or if it is either, but 130 // its hash does not match, the program execution returns from the current 131 // instruction. 132 // Parameters: 133 // - a 32 byte hash of the expected value. 134 COMPARE_NODE_HASH = 0x21, 135 // The negation of the above. 136 COMPARE_NODE_HASH_NOT = 0x22, 137 // Compares the current node against a boolean value stored in working memory, 138 // and continues with the next operation in case of a match. If the current 139 // node is not a boolean value, the working memory contains no corresponding 140 // boolean value, or if they do not match, the program execution returns from 141 // the current instruction. 142 // Parameters: 143 // - a 32 byte hash of the parameter name. 144 COMPARE_NODE_TO_STORED_BOOL = 0x23, 145 // Compares the hashed value of the current node against a hash value stored 146 // in working memory, and continues with the next operation in case of a 147 // match. If the current node is not a string, integer or double, or if the 148 // working memory contains no corresponding hash string, or if the hashes do 149 // not match, the program execution returns from the current instruction. 150 // Parameters: 151 // - a 32 byte hash of the parameter name. 152 COMPARE_NODE_TO_STORED_HASH = 0x24, 153 // Checks whether the current node is a string value that contains the given 154 // pattern as a substring, and continues execution with the next operation in 155 // case it does. If the current node is not a string, or if does not match the 156 // pattern, the program execution returns from the current instruction. 157 // Parameters: 158 // - a 32 byte hash of the pattern, 159 // - a 4 byte unsigned integer: the length (>0) of the pattern in bytes, 160 // - a 4 byte unsigned integer: the sum of all bytes in the pattern, serving 161 // as a heuristic to reduce the number of actual SHA-256 calculations. 162 COMPARE_NODE_SUBSTRING = 0x25, 163 // Stop execution in this specific sentence. 164 STOP_EXECUTING_SENTENCE = 0x30, 165 // Separator between sentences, starts a new sentence. 166 END_OF_SENTENCE = 0x31 167 }; 168 169 const size_t kHashSizeInBytes = 32u; 170 171 // A class that provides SHA256 hash values for strings using a fixed hash seed. 172 class Hasher { 173 public: 174 explicit Hasher(const std::string& seed); 175 ~Hasher(); 176 177 std::string GetHash(const std::string& input) const; 178 179 static bool IsHash(const std::string& maybe_hash); 180 181 private: 182 crypto::HMAC hmac_; 183 mutable std::map<std::string, std::string> cached_hashes_; 184 DISALLOW_COPY_AND_ASSIGN(Hasher); 185 }; 186 187 } // namespace jtl_foundation 188 189 #endif // CHROME_BROWSER_PROFILE_RESETTER_JTL_FOUNDATION_H_ 190
