// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/certificate_transparency/single_tree_tracker.h"

#include <algorithm>
#include <iterator>
#include <list>
#include <utility>

#include "base/bind.h"
#include "base/metrics/histogram_macros.h"
#include "base/strings/string_number_conversions.h"
#include "base/values.h"
#include "components/certificate_transparency/log_dns_client.h"
#include "crypto/sha2.h"
#include "net/base/hash_value.h"
#include "net/base/net_errors.h"
#include "net/cert/ct_log_verifier.h"
#include "net/cert/merkle_audit_proof.h"
#include "net/cert/merkle_tree_leaf.h"
#include "net/cert/signed_certificate_timestamp.h"
#include "net/cert/x509_certificate.h"
#include "net/dns/host_resolver.h"
#include "net/log/net_log.h"

using net::SHA256HashValue;
using net::ct::MerkleAuditProof;
using net::ct::MerkleTreeLeaf;
using net::ct::SignedCertificateTimestamp;
using net::ct::SignedTreeHead;

// Overview of the process for auditing CT log entries
//
// In this file, obsered CT log entries are audited for inclusion in the CT log.
// A pre-requirement for auditing a log entry is having a Signed Tree Head (STH)
// from that log that is 24 hours (MMD period) after the timestamp in the SCT.
// Log entries observed while the client has no STH from that log or an STH that
// is too old start in the PENDING_NEWER_STH state.
//
// Once a fresh-enough STH is obtained, all entries that can be audited using
// this STH move to the PENDING_INCLUSION_PROOF_REQUEST state.
//
// Requests for the entry index and inclusion proof are obtained using a
// LogDnsClient instance - when an inclusion proof for an entry has been
// successfully requested (e.g. it has not been throttled), it moves to the
// INCLUSION_PROOF_REQUESTED state.
//
// Once the inclusion check is done, the entry is removed from
// |pending_entries_|. If the inclusion check has been successful, the entry
// is added to |checked_entries_|.

namespace certificate_transparency {

namespace {

// Measure how often clients encounter very new SCTs, by measuring whether an
// SCT can be checked for inclusion upon first observation.
void LogCanBeCheckedForInclusionToUMA(
    SCTCanBeCheckedForInclusion can_be_checked) {
  UMA_HISTOGRAM_ENUMERATION("Net.CertificateTransparency.CanInclusionCheckSCT",
                            can_be_checked, SCT_CAN_BE_CHECKED_MAX);
}

// Enum indicating the outcome of an inclusion check for a particular log
// entry.
//
// Note: The numeric values are used within a histogram and should not change
// or be re-assigned.
enum LogEntryInclusionCheckResult {
  // Inclusion check succeeded: Proof obtained and validated successfully.
  GOT_VALID_INCLUSION_PROOF = 0,

  // Could not get an inclusion proof.
  FAILED_GETTING_INCLUSION_PROOF = 1,

  // An inclusion proof was obtained but it is invalid.
  GOT_INVALID_INCLUSION_PROOF = 2,

  // The SCT could not be audited because the client's DNS configuration
  // is faulty.
  DNS_QUERY_NOT_POSSIBLE = 3,

  LOG_ENTRY_INCLUSION_CHECK_RESULT_MAX
};

void LogInclusionCheckResult(LogEntryInclusionCheckResult result) {
  UMA_HISTOGRAM_ENUMERATION("Net.CertificateTransparency.InclusionCheckResult",
                            result, LOG_ENTRY_INCLUSION_CHECK_RESULT_MAX);
}

// Calculate the leaf hash of the the entry in the log represented by
// the given |cert| and |sct|. If leaf hash calculation succeeds returns
// true, false otherwise.
bool GetLogEntryLeafHash(const net::X509Certificate* cert,
                         const SignedCertificateTimestamp* sct,
                         SHA256HashValue* leaf_hash) {
  MerkleTreeLeaf leaf;
  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
    return false;

  std::string leaf_hash_str;
  if (!HashMerkleTreeLeaf(leaf, &leaf_hash_str))
    return false;

  memcpy(leaf_hash->data, leaf_hash_str.data(), crypto::kSHA256Length);
  return true;
}

// Audit state of a log entry.
enum AuditState {
  // Entry cannot be audited because a newer STH is needed.
  PENDING_NEWER_STH,
  // A leaf index has been obtained and the entry is now pending request
  // of an inclusion proof.
  PENDING_INCLUSION_PROOF_REQUEST,
  // An inclusion proof for this entry has been requested from the log.
  INCLUSION_PROOF_REQUESTED
};

// Maximal size of the checked entries cache.
size_t kCheckedEntriesCacheSize = 100;

// Maximal size of the pending entries queue.
size_t kPendingEntriesQueueSize = 100;

// Maximum Merge Delay - logs can have individual MMD, but all known logs
// currently have 24 hours MMD and Chrome's CT policy requires an MMD
// that's no greater than that. For simplicity, use 24 hours for all logs.
constexpr base::TimeDelta kMaximumMergeDelay = base::TimeDelta::FromHours(24);

// The log MUST incorporate the a certificate in the tree within the Maximum
// Merge Delay, so an entry can be audited once the timestamp from the SCT +
// MMD has passed.
// Returns true if the timestamp from the STH is newer than SCT timestamp + MMD.
bool IsSCTReadyForAudit(base::Time sth_timestamp, base::Time sct_timestamp) {
  return sct_timestamp + kMaximumMergeDelay < sth_timestamp;
}

std::unique_ptr<base::Value> NetLogEntryAuditingEventCallback(
    const SHA256HashValue* log_entry,
    base::StringPiece log_id,
    bool success,
    net::NetLogCaptureMode capture_mode) {
  std::unique_ptr<base::DictionaryValue> dict(new base::DictionaryValue());

  dict->SetString("log_entry",
                  base::HexEncode(log_entry->data, crypto::kSHA256Length));
  dict->SetString("log_id", base::HexEncode(log_id.data(), log_id.size()));
  dict->SetBoolean("success", success);

  return std::move(dict);
}

}  // namespace

// The entry that is being audited.
struct SingleTreeTracker::EntryToAudit {
  base::Time sct_timestamp;
  SHA256HashValue leaf_hash;
  bool lookup_securely;

  explicit EntryToAudit(base::Time timestamp, bool lookup_securely)
      : sct_timestamp(timestamp), lookup_securely(lookup_securely) {}
};

// State of a log entry: its audit state and information necessary to
// validate an inclusion proof. Gets updated as the entry transitions
// between the different audit states.
struct SingleTreeTracker::EntryAuditState {
  // Current phase of inclusion check.
  AuditState state;

  // The audit proof query performed by LogDnsClient.
  // It is null unless a query has been started.
  std::unique_ptr<LogDnsClient::AuditProofQuery> audit_proof_query;

  // The root hash of the tree for which an inclusion proof was requested.
  // The root hash is needed after the inclusion proof is fetched for validating
  // the inclusion proof (each inclusion proof is valid for one particular leaf,
  // denoted by the leaf index, in exactly one particular tree, denoted by the
  // tree size in the proof).
  // To avoid having to re-fetch the inclusion proof if a newer STH is provided
  // to the SingleTreeTracker, the size of the original tree for which the
  // inclusion proof was requested is stored in |proof| and the root hash
  // in |root_hash|.
  std::string root_hash;

  explicit EntryAuditState(AuditState state) : state(state) {}
};

class SingleTreeTracker::NetworkObserver
    : public net::NetworkChangeNotifier::NetworkChangeObserver {
 public:
  explicit NetworkObserver(SingleTreeTracker* parent) : parent_(parent) {
    net::NetworkChangeNotifier::AddNetworkChangeObserver(this);
  }

  ~NetworkObserver() override {
    net::NetworkChangeNotifier::RemoveNetworkChangeObserver(this);
  }

  // net::NetworkChangeNotifier::NetworkChangeObserver implementation.
  void OnNetworkChanged(
      net::NetworkChangeNotifier::ConnectionType type) override {
    parent_->ResetPendingQueue();
  }

 private:
  SingleTreeTracker* parent_;
};

// Orders entries by the SCT timestamp. In case of tie, which is very unlikely
// as it requires two SCTs issued from a log at exactly the same time, order
// by leaf hash. There should never be multiple entries that are identical
// apart from the |lookup_securely| field, so this field can be excluded from
// the comparator.
bool SingleTreeTracker::OrderByTimestamp::operator()(
    const EntryToAudit& lhs,
    const EntryToAudit& rhs) const {
  return std::tie(lhs.sct_timestamp, lhs.leaf_hash) <
         std::tie(rhs.sct_timestamp, rhs.leaf_hash);
}

SingleTreeTracker::SingleTreeTracker(
    scoped_refptr<const net::CTLogVerifier> ct_log,
    LogDnsClient* dns_client,
    net::HostResolver* host_resolver,
    net::NetLog* net_log)
    : ct_log_(std::move(ct_log)),
      checked_entries_(kCheckedEntriesCacheSize),
      dns_client_(dns_client),
      host_resolver_(host_resolver),
      net_log_(net::NetLogWithSource::Make(
          net_log,
          net::NetLogSourceType::CT_TREE_STATE_TRACKER)),
      network_observer_(new NetworkObserver(this)),
      weak_factory_(this) {
  memory_pressure_listener_.reset(new base::MemoryPressureListener(base::Bind(
      &SingleTreeTracker::OnMemoryPressure, base::Unretained(this))));
}

SingleTreeTracker::~SingleTreeTracker() {
  ResetPendingQueue();
}

void SingleTreeTracker::OnSCTVerified(base::StringPiece hostname,
                                      net::X509Certificate* cert,
                                      const SignedCertificateTimestamp* sct) {
  DCHECK_EQ(ct_log_->key_id(), sct->log_id);

  // Check that a DNS lookup for hostname has already occurred (i.e. the DNS
  // resolver already knows that the user has been accessing that host). If not,
  // the DNS resolver may not know that the user has been accessing that host,
  // but performing an inclusion check would reveal that information so abort to
  // preserve the user's privacy.
  //
  // It's ok to do this now, even though the inclusion check may not happen for
  // some time, because SingleTreeTracker will discard the SCT if the network
  // changes.
  bool secure;
  if (!WasLookedUpOverDNS(hostname, &secure)) {
    LogCanBeCheckedForInclusionToUMA(NOT_AUDITED_NO_DNS_LOOKUP);
    return;
  }

  EntryToAudit entry(sct->timestamp, secure /* lookup_securely */);
  if (!GetLogEntryLeafHash(cert, sct, &entry.leaf_hash)) {
    LogCanBeCheckedForInclusionToUMA(NOT_AUDITED_INVALID_LEAF_HASH);
    return;
  }

  // Avoid queueing multiple instances of the same entry, ignoring the value of
  // the |lookup_securely| field.
  switch (GetAuditedEntryInclusionStatus(entry, nullptr)) {
    case SCT_NOT_OBSERVED:
      // No need to record UMA, will be done below.
      break;
    case SCT_INCLUDED_IN_LOG:
      LogCanBeCheckedForInclusionToUMA(NOT_AUDITED_ALREADY_CHECKED);
      return;
    default:
      // Already pending, either due to a newer STH or in the queue.
      LogCanBeCheckedForInclusionToUMA(NOT_AUDITED_ALREADY_PENDING_CHECK);
      return;
  }

  if (pending_entries_.size() >= kPendingEntriesQueueSize) {
    // Queue is full - cannot audit SCT.
    LogCanBeCheckedForInclusionToUMA(NOT_AUDITED_QUEUE_FULL);
    return;
  }

  // If there isn't a valid STH or the STH is not fresh enough to check
  // inclusion against, store the SCT for future checking and return.
  if (verified_sth_.timestamp.is_null() ||
      !IsSCTReadyForAudit(verified_sth_.timestamp, entry.sct_timestamp)) {
    pending_entries_.insert(
        std::make_pair(std::move(entry), EntryAuditState(PENDING_NEWER_STH)));

    if (verified_sth_.timestamp.is_null()) {
      LogCanBeCheckedForInclusionToUMA(VALID_STH_REQUIRED);
    } else {
      LogCanBeCheckedForInclusionToUMA(NEWER_STH_REQUIRED);
    }

    return;
  }

  LogCanBeCheckedForInclusionToUMA(CAN_BE_CHECKED);
  pending_entries_.insert(std::make_pair(
      std::move(entry), EntryAuditState(PENDING_INCLUSION_PROOF_REQUEST)));

  ProcessPendingEntries();
}

void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
  DCHECK_EQ(ct_log_->key_id(), sth.log_id);

  if (!ct_log_->VerifySignedTreeHead(sth)) {
    // Sanity check the STH; the caller should have done this
    // already, but being paranoid here.
    // NOTE(eranm): Right now there's no way to get rid of this check here
    // as this is the first object in the chain that has an instance of
    // a CTLogVerifier to verify the STH.
    return;
  }

  // In order to avoid updating |verified_sth_| to an older STH in case
  // an older STH is observed, check that either the observed STH is for
  // a larger tree size or that it is for the same tree size but has
  // a newer timestamp.
  const bool sths_for_same_tree = verified_sth_.tree_size == sth.tree_size;
  const bool received_sth_is_for_larger_tree =
      (verified_sth_.tree_size < sth.tree_size);
  const bool received_sth_is_newer = (sth.timestamp > verified_sth_.timestamp);

  if (!verified_sth_.timestamp.is_null() && !received_sth_is_for_larger_tree &&
      !(sths_for_same_tree && received_sth_is_newer)) {
    // Observed an old STH - do nothing.
    return;
  }

  verified_sth_ = sth;

  // Find the first entry in the PENDING_NEWER_STH state - entries
  // before that should be pending leaf index / inclusion proof, no
  // reason to inspect them.
  auto auditable_entries_begin = std::find_if(
      pending_entries_.begin(), pending_entries_.end(),
      [](std::pair<const EntryToAudit&, const EntryAuditState&> value) {
        return value.second.state == PENDING_NEWER_STH;
      });

  // Find where to stop - this is the first entry whose timestamp + MMD
  // is greater than the STH's timestamp.
  auto auditable_entries_end = std::lower_bound(
      auditable_entries_begin, pending_entries_.end(), sth.timestamp,
      [](std::pair<const EntryToAudit&, const EntryAuditState&> value,
         base::Time sth_timestamp) {
        return IsSCTReadyForAudit(sth_timestamp, value.first.sct_timestamp);
      });

  // Update the state of all entries that can now be checked for inclusion.
  for (auto curr_entry = auditable_entries_begin;
       curr_entry != auditable_entries_end; ++curr_entry) {
    DCHECK_EQ(curr_entry->second.state, PENDING_NEWER_STH);
    curr_entry->second.state = PENDING_INCLUSION_PROOF_REQUEST;
  }

  if (auditable_entries_begin == auditable_entries_end)
    return;

  ProcessPendingEntries();
}

void SingleTreeTracker::ResetPendingQueue() {
  // Move entries out of pending_entries_ prior to deleting them, in case any
  // have inclusion checks in progress. Cancelling those checks would invoke the
  // cancellation callback (ProcessPendingEntries()), which would attempt to
  // access pending_entries_ while it was in the process of being deleted.
  std::map<EntryToAudit, EntryAuditState, OrderByTimestamp> pending_entries;
  pending_entries_.swap(pending_entries);
}

SingleTreeTracker::SCTInclusionStatus
SingleTreeTracker::GetLogEntryInclusionStatusForTesting(
    net::X509Certificate* cert,
    const SignedCertificateTimestamp* sct,
    bool* pending_lookup_securely) {
  EntryToAudit entry(sct->timestamp, false /* lookup_securely */);
  if (!GetLogEntryLeafHash(cert, sct, &entry.leaf_hash))
    return SCT_NOT_OBSERVED;
  return GetAuditedEntryInclusionStatus(entry, pending_lookup_securely);
}

void SingleTreeTracker::ProcessPendingEntries() {
  for (auto it = pending_entries_.begin(); it != pending_entries_.end(); ++it) {
    if (it->second.state != PENDING_INCLUSION_PROOF_REQUEST) {
      continue;
    }

    it->second.root_hash =
        std::string(verified_sth_.sha256_root_hash, crypto::kSHA256Length);

    std::string leaf_hash(
        reinterpret_cast<const char*>(it->first.leaf_hash.data),
        crypto::kSHA256Length);
    net::Error result = dns_client_->QueryAuditProof(
        ct_log_->dns_domain(), leaf_hash, it->first.lookup_securely,
        verified_sth_.tree_size, &(it->second.audit_proof_query),
        base::Bind(&SingleTreeTracker::OnAuditProofObtained,
                   base::Unretained(this), it->first));
    // Handling proofs returned synchronously is not implemeted.
    DCHECK_NE(result, net::OK);
    if (result == net::ERR_IO_PENDING) {
      // Successfully requested an inclusion proof - change entry state
      // and continue to the next one.
      it->second.state = INCLUSION_PROOF_REQUESTED;
    } else if (result == net::ERR_TEMPORARILY_THROTTLED) {
      // Need to use a weak pointer here, as this callback could be triggered
      // when the SingleTreeTracker is deleted (and pending queries are
      // cancelled).
      dns_client_->NotifyWhenNotThrottled(
          base::BindOnce(&SingleTreeTracker::ProcessPendingEntries,
                         weak_factory_.GetWeakPtr()));
      // Exit the loop since all subsequent calls to QueryAuditProof
      // will be throttled.
      break;
    } else if (result == net::ERR_NAME_RESOLUTION_FAILED) {
      LogInclusionCheckResult(DNS_QUERY_NOT_POSSIBLE);
      LogAuditResultToNetLog(it->first, false);
      // Lookup failed due to bad DNS configuration, erase the entry and
      // continue to the next one.
      it = pending_entries_.erase(it);
      // Break here if it's the last entry to avoid |it| being incremented
      // by the for loop.
      if (it == pending_entries_.end())
        break;
    } else {
      // BUG: an invalid argument was provided or an unexpected error
      // was returned from LogDnsClient.
      DCHECK_EQ(result, net::ERR_INVALID_ARGUMENT);
      NOTREACHED();
    }
  }
}

SingleTreeTracker::SCTInclusionStatus
SingleTreeTracker::GetAuditedEntryInclusionStatus(
    const EntryToAudit& entry,
    bool* pending_lookup_securely) {
  const auto checked_entries_iterator = checked_entries_.Get(entry.leaf_hash);
  if (checked_entries_iterator != checked_entries_.end()) {
    return SCT_INCLUDED_IN_LOG;
  }

  auto pending_iterator = pending_entries_.find(entry);
  if (pending_iterator == pending_entries_.end()) {
    return SCT_NOT_OBSERVED;
  }
  // Found match in |pending_entries_|, so set |pending_lookup_securely|.
  if (pending_lookup_securely)
    *pending_lookup_securely = pending_iterator->first.lookup_securely;
  switch (pending_iterator->second.state) {
    case PENDING_NEWER_STH:
      return SCT_PENDING_NEWER_STH;
    case PENDING_INCLUSION_PROOF_REQUEST:
    case INCLUSION_PROOF_REQUESTED:
      return SCT_PENDING_INCLUSION_CHECK;
  }

  NOTREACHED();
  return SCT_NOT_OBSERVED;
}

void SingleTreeTracker::OnAuditProofObtained(const EntryToAudit& entry,
                                             int net_error) {
  auto it = pending_entries_.find(entry);
  // The entry may not be present if it was evacuated due to low memory
  // pressure.
  if (it == pending_entries_.end())
    return;

  DCHECK_EQ(it->second.state, INCLUSION_PROOF_REQUESTED);

  if (net_error != net::OK) {
    // TODO(eranm): Should failures be cached? For now, they are not.
    LogInclusionCheckResult(FAILED_GETTING_INCLUSION_PROOF);
    LogAuditResultToNetLog(entry, false);
    pending_entries_.erase(it);
    return;
  }

  std::string leaf_hash(reinterpret_cast<const char*>(entry.leaf_hash.data),
                        crypto::kSHA256Length);

  bool verified =
      ct_log_->VerifyAuditProof(it->second.audit_proof_query->GetProof(),
                                it->second.root_hash, leaf_hash);
  LogAuditResultToNetLog(entry, verified);

  if (!verified) {
    LogInclusionCheckResult(GOT_INVALID_INCLUSION_PROOF);
  } else {
    LogInclusionCheckResult(GOT_VALID_INCLUSION_PROOF);
    checked_entries_.Put(entry.leaf_hash, EntryAuditResult());
  }

  pending_entries_.erase(it);
}

void SingleTreeTracker::OnMemoryPressure(
    base::MemoryPressureListener::MemoryPressureLevel memory_pressure_level) {
  switch (memory_pressure_level) {
    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_NONE:
      break;
    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_CRITICAL:
      ResetPendingQueue();
      // Fall through to clearing the other cache.
      FALLTHROUGH;
    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_MODERATE:
      checked_entries_.Clear();
      break;
  }
}

void SingleTreeTracker::LogAuditResultToNetLog(const EntryToAudit& entry,
                                               bool success) {
  net::NetLogParametersCallback net_log_callback =
      base::Bind(&NetLogEntryAuditingEventCallback, &entry.leaf_hash,
                 ct_log_->key_id(), success);

  net_log_.AddEvent(net::NetLogEventType::CT_LOG_ENTRY_AUDITED,
                    net_log_callback);
}

bool SingleTreeTracker::WasLookedUpOverDNS(base::StringPiece hostname,
                                           bool* secure) const {
  net::HostCache::Entry::Source source;
  net::HostCache::EntryStaleness staleness;
  return host_resolver_->HasCached(hostname, &source, &staleness, secure) &&
         source == net::HostCache::Entry::SOURCE_DNS &&
         staleness.network_changes == 0;
}

}  // namespace certificate_transparency