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.
5 #include "chrome/browser/profile_resetter/jtl_interpreter.h"
9 #include "base/memory/scoped_vector.h"
10 #include "base/strings/string_number_conversions.h"
11 #include "base/strings/string_util.h"
12 #include "chrome/browser/profile_resetter/jtl_foundation.h"
13 #include "crypto/hmac.h"
14 #include "crypto/sha2.h"
15 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
20 class ExecutionContext;
22 // An operation in an interpreted program.
25 virtual ~Operation() {}
26 // Executes the operation on the specified context and instructs the context
27 // to continue execution with the next instruction if appropriate.
28 // Returns true if we should continue with any potential backtracking that
30 virtual bool Execute(ExecutionContext* context) = 0;
33 // An execution context of operations.
34 class ExecutionContext {
36 // |input| is the root of a dictionary that stores the information the
37 // sentence is evaluated on.
38 ExecutionContext(const jtl_foundation::Hasher* hasher,
39 const std::vector<Operation*>& sentence,
40 const base::DictionaryValue* input,
41 base::DictionaryValue* working_memory)
44 next_instruction_index_(0u),
45 working_memory_(working_memory),
47 stack_.push_back(input);
49 ~ExecutionContext() {}
51 // Returns true in case of success.
52 bool ContinueExecution() {
53 if (error_ || stack_.empty()) {
57 if (next_instruction_index_ >= sentence_.size())
60 Operation* op = sentence_[next_instruction_index_];
61 next_instruction_index_++;
62 bool continue_traversal = op->Execute(this);
63 next_instruction_index_--;
64 return continue_traversal;
67 std::string GetHash(const std::string& input) {
68 return hasher_->GetHash(input);
71 // Calculates the |hash| of a string, integer or double |value|, and returns
72 // true. Returns false otherwise.
73 bool GetValueHash(const base::Value& value, std::string* hash) {
75 std::string value_as_string;
77 double tmp_double = 0.0;
78 if (value.GetAsInteger(&tmp_int))
79 value_as_string = base::IntToString(tmp_int);
80 else if (value.GetAsDouble(&tmp_double))
81 value_as_string = base::DoubleToString(tmp_double);
82 else if (!value.GetAsString(&value_as_string))
84 *hash = GetHash(value_as_string);
88 const base::Value* current_node() const { return stack_.back(); }
89 std::vector<const base::Value*>* stack() { return &stack_; }
90 base::DictionaryValue* working_memory() { return working_memory_; }
91 bool error() const { return error_; }
94 // A hasher used to hash node names in a dictionary.
95 const jtl_foundation::Hasher* hasher_;
96 // The sentence to be executed.
97 const std::vector<Operation*> sentence_;
98 // Position in |sentence_|.
99 size_t next_instruction_index_;
100 // A stack of Values, indicating a navigation path from the root node of
101 // |input| (see constructor) to the current node on which the
102 // sentence_[next_instruction_index_] is evaluated.
103 std::vector<const base::Value*> stack_;
104 // Memory into which values can be stored by the program.
105 base::DictionaryValue* working_memory_;
106 // Whether a runtime error occurred.
108 DISALLOW_COPY_AND_ASSIGN(ExecutionContext);
111 class NavigateOperation : public Operation {
113 explicit NavigateOperation(const std::string& hashed_key)
114 : hashed_key_(hashed_key) {}
115 ~NavigateOperation() override {}
116 bool Execute(ExecutionContext* context) override {
117 const base::DictionaryValue* dict = NULL;
118 if (!context->current_node()->GetAsDictionary(&dict)) {
119 // Just ignore this node gracefully as this navigation is a dead end.
120 // If this NavigateOperation occurred after a NavigateAny operation, those
121 // may still be fulfillable, so we allow continuing the execution of the
122 // sentence on other nodes.
125 for (base::DictionaryValue::Iterator i(*dict); !i.IsAtEnd(); i.Advance()) {
126 if (context->GetHash(i.key()) != hashed_key_)
128 context->stack()->push_back(&i.value());
129 bool continue_traversal = context->ContinueExecution();
130 context->stack()->pop_back();
131 if (!continue_traversal)
138 std::string hashed_key_;
139 DISALLOW_COPY_AND_ASSIGN(NavigateOperation);
142 class NavigateAnyOperation : public Operation {
144 NavigateAnyOperation() {}
145 ~NavigateAnyOperation() override {}
146 bool Execute(ExecutionContext* context) override {
147 const base::DictionaryValue* dict = NULL;
148 const base::ListValue* list = NULL;
149 if (context->current_node()->GetAsDictionary(&dict)) {
150 for (base::DictionaryValue::Iterator i(*dict);
151 !i.IsAtEnd(); i.Advance()) {
152 context->stack()->push_back(&i.value());
153 bool continue_traversal = context->ContinueExecution();
154 context->stack()->pop_back();
155 if (!continue_traversal)
158 } else if (context->current_node()->GetAsList(&list)) {
159 for (base::ListValue::const_iterator i = list->begin();
160 i != list->end(); ++i) {
161 context->stack()->push_back(*i);
162 bool continue_traversal = context->ContinueExecution();
163 context->stack()->pop_back();
164 if (!continue_traversal)
168 // Do nothing, just ignore this node.
174 DISALLOW_COPY_AND_ASSIGN(NavigateAnyOperation);
177 class NavigateBackOperation : public Operation {
179 NavigateBackOperation() {}
180 ~NavigateBackOperation() override {}
181 bool Execute(ExecutionContext* context) override {
182 const base::Value* current_node = context->current_node();
183 context->stack()->pop_back();
184 bool continue_traversal = context->ContinueExecution();
185 context->stack()->push_back(current_node);
186 return continue_traversal;
190 DISALLOW_COPY_AND_ASSIGN(NavigateBackOperation);
193 class StoreValue : public Operation {
195 StoreValue(const std::string& hashed_name, scoped_ptr<base::Value> value)
196 : hashed_name_(hashed_name),
197 value_(value.Pass()) {
198 DCHECK(base::IsStringUTF8(hashed_name));
201 ~StoreValue() override {}
202 bool Execute(ExecutionContext* context) override {
203 context->working_memory()->Set(hashed_name_, value_->DeepCopy());
204 return context->ContinueExecution();
208 std::string hashed_name_;
209 scoped_ptr<base::Value> value_;
210 DISALLOW_COPY_AND_ASSIGN(StoreValue);
213 class CompareStoredValue : public Operation {
215 CompareStoredValue(const std::string& hashed_name,
216 scoped_ptr<base::Value> value,
217 scoped_ptr<base::Value> default_value)
218 : hashed_name_(hashed_name),
219 value_(value.Pass()),
220 default_value_(default_value.Pass()) {
221 DCHECK(base::IsStringUTF8(hashed_name));
223 DCHECK(default_value_);
225 ~CompareStoredValue() override {}
226 bool Execute(ExecutionContext* context) override {
227 const base::Value* actual_value = NULL;
228 if (!context->working_memory()->Get(hashed_name_, &actual_value))
229 actual_value = default_value_.get();
230 if (!value_->Equals(actual_value))
232 return context->ContinueExecution();
236 std::string hashed_name_;
237 scoped_ptr<base::Value> value_;
238 scoped_ptr<base::Value> default_value_;
239 DISALLOW_COPY_AND_ASSIGN(CompareStoredValue);
242 template<bool ExpectedTypeIsBooleanNotHashable>
243 class StoreNodeValue : public Operation {
245 explicit StoreNodeValue(const std::string& hashed_name)
246 : hashed_name_(hashed_name) {
247 DCHECK(base::IsStringUTF8(hashed_name));
249 virtual ~StoreNodeValue() {}
250 virtual bool Execute(ExecutionContext* context) override {
251 scoped_ptr<base::Value> value;
252 if (ExpectedTypeIsBooleanNotHashable) {
253 if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN))
255 value.reset(context->current_node()->DeepCopy());
258 if (!context->GetValueHash(*context->current_node(), &hash))
260 value.reset(new base::StringValue(hash));
262 context->working_memory()->Set(hashed_name_, value.release());
263 return context->ContinueExecution();
267 std::string hashed_name_;
268 DISALLOW_COPY_AND_ASSIGN(StoreNodeValue);
271 // Stores the hash of the registerable domain name -- as in, the portion of the
272 // domain that is registerable, as opposed to controlled by a registrar; without
273 // subdomains -- of the URL represented by the current node into working memory.
274 class StoreNodeRegisterableDomain : public Operation {
276 explicit StoreNodeRegisterableDomain(const std::string& hashed_name)
277 : hashed_name_(hashed_name) {
278 DCHECK(base::IsStringUTF8(hashed_name));
280 ~StoreNodeRegisterableDomain() override {}
281 bool Execute(ExecutionContext* context) override {
282 std::string possibly_invalid_url;
284 if (!context->current_node()->GetAsString(&possibly_invalid_url) ||
285 !GetRegisterableDomain(possibly_invalid_url, &domain))
287 context->working_memory()->Set(
288 hashed_name_, new base::StringValue(context->GetHash(domain)));
289 return context->ContinueExecution();
293 // If |possibly_invalid_url| is a valid URL having a registerable domain name
294 // part, outputs that in |registerable_domain| and returns true. Otherwise,
296 static bool GetRegisterableDomain(const std::string& possibly_invalid_url,
297 std::string* registerable_domain) {
298 namespace domains = net::registry_controlled_domains;
299 DCHECK(registerable_domain);
300 GURL url(possibly_invalid_url);
303 std::string registry_plus_one = domains::GetDomainAndRegistry(
304 url.host(), domains::INCLUDE_PRIVATE_REGISTRIES);
305 size_t registry_length = domains::GetRegistryLength(
307 domains::INCLUDE_UNKNOWN_REGISTRIES,
308 domains::INCLUDE_PRIVATE_REGISTRIES);
309 // Fail unless (1.) the URL has a host part; and (2.) that host part is a
310 // well-formed domain name consisting of at least one subcomponent; followed
311 // by either a recognized registry identifier, or exactly one subcomponent,
312 // which is then assumed to be the unknown registry identifier.
313 if (registry_length == std::string::npos || registry_length == 0)
315 DCHECK_LT(registry_length, registry_plus_one.size());
316 // Subtract one to cut off the dot separating the SLD and the registry.
317 registerable_domain->assign(
318 registry_plus_one, 0, registry_plus_one.size() - registry_length - 1);
322 std::string hashed_name_;
323 DISALLOW_COPY_AND_ASSIGN(StoreNodeRegisterableDomain);
326 class CompareNodeBool : public Operation {
328 explicit CompareNodeBool(bool value) : value_(value) {}
329 ~CompareNodeBool() override {}
330 bool Execute(ExecutionContext* context) override {
331 bool actual_value = false;
332 if (!context->current_node()->GetAsBoolean(&actual_value))
334 if (actual_value != value_)
336 return context->ContinueExecution();
341 DISALLOW_COPY_AND_ASSIGN(CompareNodeBool);
344 class CompareNodeHash : public Operation {
346 explicit CompareNodeHash(const std::string& hashed_value)
347 : hashed_value_(hashed_value) {}
348 ~CompareNodeHash() override {}
349 bool Execute(ExecutionContext* context) override {
350 std::string actual_hash;
351 if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
352 actual_hash != hashed_value_)
354 return context->ContinueExecution();
358 std::string hashed_value_;
359 DISALLOW_COPY_AND_ASSIGN(CompareNodeHash);
362 class CompareNodeHashNot : public Operation {
364 explicit CompareNodeHashNot(const std::string& hashed_value)
365 : hashed_value_(hashed_value) {}
366 ~CompareNodeHashNot() override {}
367 bool Execute(ExecutionContext* context) override {
368 std::string actual_hash;
369 if (context->GetValueHash(*context->current_node(), &actual_hash) &&
370 actual_hash == hashed_value_)
372 return context->ContinueExecution();
376 std::string hashed_value_;
377 DISALLOW_COPY_AND_ASSIGN(CompareNodeHashNot);
380 template<bool ExpectedTypeIsBooleanNotHashable>
381 class CompareNodeToStored : public Operation {
383 explicit CompareNodeToStored(const std::string& hashed_name)
384 : hashed_name_(hashed_name) {}
385 virtual ~CompareNodeToStored() {}
386 virtual bool Execute(ExecutionContext* context) override {
387 const base::Value* stored_value = NULL;
388 if (!context->working_memory()->Get(hashed_name_, &stored_value))
390 if (ExpectedTypeIsBooleanNotHashable) {
391 if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN) ||
392 !context->current_node()->Equals(stored_value))
395 std::string actual_hash;
396 std::string stored_hash;
397 if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
398 !stored_value->GetAsString(&stored_hash) ||
399 actual_hash != stored_hash)
402 return context->ContinueExecution();
406 std::string hashed_name_;
407 DISALLOW_COPY_AND_ASSIGN(CompareNodeToStored);
410 class CompareNodeSubstring : public Operation {
412 explicit CompareNodeSubstring(const std::string& hashed_pattern,
413 size_t pattern_length,
415 : hashed_pattern_(hashed_pattern),
416 pattern_length_(pattern_length),
417 pattern_sum_(pattern_sum) {
418 DCHECK(pattern_length_);
420 ~CompareNodeSubstring() override {}
421 bool Execute(ExecutionContext* context) override {
422 std::string value_as_string;
423 if (!context->current_node()->GetAsString(&value_as_string) ||
424 !pattern_length_ || value_as_string.size() < pattern_length_)
426 // Go over the string with a sliding window. Meanwhile, maintain the sum in
427 // an incremental fashion, and only calculate the SHA-256 hash when the sum
428 // checks out so as to improve performance.
429 std::string::const_iterator window_begin = value_as_string.begin();
430 std::string::const_iterator window_end = window_begin + pattern_length_ - 1;
432 std::accumulate(window_begin, window_end, static_cast<uint32>(0u));
433 while (window_end != value_as_string.end()) {
434 window_sum += *window_end++;
435 if (window_sum == pattern_sum_ && context->GetHash(std::string(
436 window_begin, window_end)) == hashed_pattern_)
437 return context->ContinueExecution();
438 window_sum -= *window_begin++;
444 std::string hashed_pattern_;
445 size_t pattern_length_;
447 DISALLOW_COPY_AND_ASSIGN(CompareNodeSubstring);
450 class StopExecutingSentenceOperation : public Operation {
452 StopExecutingSentenceOperation() {}
453 ~StopExecutingSentenceOperation() override {}
454 bool Execute(ExecutionContext* context) override { return false; }
457 DISALLOW_COPY_AND_ASSIGN(StopExecutingSentenceOperation);
462 explicit Parser(const std::string& program)
464 next_instruction_index_(0u) {}
466 bool ParseNextSentence(ScopedVector<Operation>* output) {
467 ScopedVector<Operation> operators;
468 bool sentence_ended = false;
469 while (next_instruction_index_ < program_.size() && !sentence_ended) {
471 if (!ReadOpCode(&op_code))
473 switch (static_cast<jtl_foundation::OpCodes>(op_code)) {
474 case jtl_foundation::NAVIGATE: {
475 std::string hashed_key;
476 if (!ReadHash(&hashed_key))
478 operators.push_back(new NavigateOperation(hashed_key));
481 case jtl_foundation::NAVIGATE_ANY:
482 operators.push_back(new NavigateAnyOperation);
484 case jtl_foundation::NAVIGATE_BACK:
485 operators.push_back(new NavigateBackOperation);
487 case jtl_foundation::STORE_BOOL: {
488 std::string hashed_name;
489 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
492 if (!ReadBool(&value))
494 operators.push_back(new StoreValue(
496 scoped_ptr<base::Value>(new base::FundamentalValue(value))));
499 case jtl_foundation::COMPARE_STORED_BOOL: {
500 std::string hashed_name;
501 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
504 if (!ReadBool(&value))
506 bool default_value = false;
507 if (!ReadBool(&default_value))
509 operators.push_back(new CompareStoredValue(
511 scoped_ptr<base::Value>(new base::FundamentalValue(value)),
512 scoped_ptr<base::Value>(
513 new base::FundamentalValue(default_value))));
516 case jtl_foundation::STORE_HASH: {
517 std::string hashed_name;
518 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
520 std::string hashed_value;
521 if (!ReadHash(&hashed_value))
523 operators.push_back(new StoreValue(
525 scoped_ptr<base::Value>(new base::StringValue(hashed_value))));
528 case jtl_foundation::COMPARE_STORED_HASH: {
529 std::string hashed_name;
530 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
532 std::string hashed_value;
533 if (!ReadHash(&hashed_value))
535 std::string hashed_default_value;
536 if (!ReadHash(&hashed_default_value))
538 operators.push_back(new CompareStoredValue(
540 scoped_ptr<base::Value>(new base::StringValue(hashed_value)),
541 scoped_ptr<base::Value>(
542 new base::StringValue(hashed_default_value))));
545 case jtl_foundation::STORE_NODE_BOOL: {
546 std::string hashed_name;
547 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
549 operators.push_back(new StoreNodeValue<true>(hashed_name));
552 case jtl_foundation::STORE_NODE_HASH: {
553 std::string hashed_name;
554 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
556 operators.push_back(new StoreNodeValue<false>(hashed_name));
559 case jtl_foundation::STORE_NODE_REGISTERABLE_DOMAIN_HASH: {
560 std::string hashed_name;
561 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
563 operators.push_back(new StoreNodeRegisterableDomain(hashed_name));
566 case jtl_foundation::COMPARE_NODE_BOOL: {
568 if (!ReadBool(&value))
570 operators.push_back(new CompareNodeBool(value));
573 case jtl_foundation::COMPARE_NODE_HASH: {
574 std::string hashed_value;
575 if (!ReadHash(&hashed_value))
577 operators.push_back(new CompareNodeHash(hashed_value));
580 case jtl_foundation::COMPARE_NODE_HASH_NOT: {
581 std::string hashed_value;
582 if (!ReadHash(&hashed_value))
584 operators.push_back(new CompareNodeHashNot(hashed_value));
587 case jtl_foundation::COMPARE_NODE_TO_STORED_BOOL: {
588 std::string hashed_name;
589 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
591 operators.push_back(new CompareNodeToStored<true>(hashed_name));
594 case jtl_foundation::COMPARE_NODE_TO_STORED_HASH: {
595 std::string hashed_name;
596 if (!ReadHash(&hashed_name) || !base::IsStringUTF8(hashed_name))
598 operators.push_back(new CompareNodeToStored<false>(hashed_name));
601 case jtl_foundation::COMPARE_NODE_SUBSTRING: {
602 std::string hashed_pattern;
603 uint32 pattern_length = 0, pattern_sum = 0;
604 if (!ReadHash(&hashed_pattern))
606 if (!ReadUint32(&pattern_length) || pattern_length == 0)
608 if (!ReadUint32(&pattern_sum))
610 operators.push_back(new CompareNodeSubstring(
611 hashed_pattern, pattern_length, pattern_sum));
614 case jtl_foundation::STOP_EXECUTING_SENTENCE:
615 operators.push_back(new StopExecutingSentenceOperation);
617 case jtl_foundation::END_OF_SENTENCE:
618 sentence_ended = true;
624 output->swap(operators);
628 bool HasNextSentence() const {
629 return next_instruction_index_ < program_.size();
633 // Reads an uint8 and returns whether this operation was successful.
634 bool ReadUint8(uint8* out) {
636 if (next_instruction_index_ + 1u > program_.size())
638 *out = static_cast<uint8>(program_[next_instruction_index_]);
639 ++next_instruction_index_;
643 // Reads an uint32 and returns whether this operation was successful.
644 bool ReadUint32(uint32* out) {
646 if (next_instruction_index_ + 4u > program_.size())
649 for (int i = 0; i < 4; ++i) {
651 *out |= static_cast<uint8>(program_[next_instruction_index_]) << 24;
652 ++next_instruction_index_;
657 // Reads an operator code and returns whether this operation was successful.
658 bool ReadOpCode(uint8* out) { return ReadUint8(out); }
660 bool ReadHash(std::string* out) {
662 if (next_instruction_index_ + jtl_foundation::kHashSizeInBytes >
665 *out = program_.substr(next_instruction_index_,
666 jtl_foundation::kHashSizeInBytes);
667 next_instruction_index_ += jtl_foundation::kHashSizeInBytes;
668 DCHECK(jtl_foundation::Hasher::IsHash(*out));
672 bool ReadBool(bool* out) {
675 if (!ReadUint8(&value))
686 std::string program_;
687 size_t next_instruction_index_;
688 DISALLOW_COPY_AND_ASSIGN(Parser);
693 JtlInterpreter::JtlInterpreter(
694 const std::string& hasher_seed,
695 const std::string& program,
696 const base::DictionaryValue* input)
697 : hasher_seed_(hasher_seed),
700 working_memory_(new base::DictionaryValue),
702 DCHECK(input->IsType(base::Value::TYPE_DICTIONARY));
705 JtlInterpreter::~JtlInterpreter() {}
707 void JtlInterpreter::Execute() {
708 jtl_foundation::Hasher hasher(hasher_seed_);
709 Parser parser(program_);
710 while (parser.HasNextSentence()) {
711 ScopedVector<Operation> sentence;
712 if (!parser.ParseNextSentence(&sentence)) {
713 result_ = PARSE_ERROR;
716 ExecutionContext context(
717 &hasher, sentence.get(), input_, working_memory_.get());
718 context.ContinueExecution();
719 if (context.error()) {
720 result_ = RUNTIME_ERROR;
726 bool JtlInterpreter::GetOutputBoolean(const std::string& unhashed_key,
727 bool* output) const {
728 std::string hashed_key =
729 jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
730 return working_memory_->GetBoolean(hashed_key, output);
733 bool JtlInterpreter::GetOutputString(const std::string& unhashed_key,
734 std::string* output) const {
735 std::string hashed_key =
736 jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
737 return working_memory_->GetString(hashed_key, output);
740 int JtlInterpreter::CalculateProgramChecksum() const {
741 uint8 digest[3] = {};
742 crypto::SHA256HashString(program_, digest, arraysize(digest));
743 return static_cast<uint32>(digest[0]) << 16 |
744 static_cast<uint32>(digest[1]) << 8 |
745 static_cast<uint32>(digest[2]);