Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.cc

 // 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 "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"
 
+using net::SHA256HashValue;
+using net::ct::LogEntry;
+using net::ct::MerkleTreeLeaf;
+using net::ct::SignedCertificateTimestamp;
 using net::ct::SignedTreeHead;
 
 namespace {
 
 // Enum indicating whether an SCT can be checked for inclusion and if not,
 // the reason it cannot.
 //
 // Note: The numeric values are used within a histogram and should not change
 // or be re-assigned.
 enum SCTCanBeCheckedForInclusion {
   // If the SingleTreeTracker does not have a valid STH, then a valid STH is
   // first required to evaluate whether the SCT can be checked for inclusion
   // or not.
   VALID_STH_REQUIRED = 0,
   // If the STH does not cover the SCT (the timestamp in the SCT is greater than
   // MMD + timestamp in the STH), then a newer STH is needed.
   NEWER_STH_REQUIRED = 1,
   // When an SCT is observed, if the SingleTreeTracker instance has a valid STH
   // and the STH covers the SCT (the timestamp in the SCT is less than MMD +
   // timestamp in the STH), then it can be checked for inclusion.
   CAN_BE_CHECKED = 2,
+  // This SCT was not audited because the queue of pending entries was
+  // full.
+  NOT_AUDITED_QUEUE_FULL = 3,
   SCT_CAN_BE_CHECKED_MAX
 };
 
 // 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,

[Ryan Sleevi, 2016/12/22 21:33:21]

nit: My inclination is to suggest vertical whitespace in between these
variables, to aid readability. I can see an argument against, but especially
when reviewing code (e.g. no syntax highlighting), it makes it easier to
visually distinguish at a glance.

I would argue the same for 32-52 as well.

That said, this is not a hill I'm going to die on fighting for, especially in
the effort to minimize the delta of this CL, and as you've written it now, it's
internally consistent, so that's probably for the best.

[Eran Messeri, 2017/01/03 23:07:41]

Done here and lines 32-52.

+  // 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.

[Ryan Sleevi, 2016/12/22 21:33:21]

Since this represents a finite flow, perhaps it's worth explaining here the
logical process for how audit stats progress. I couldn't find any good "high
level" overview that explains how auditing works.

Alternatively, if you want more robust control of formatting, markdown may be
useful. However, I suspect some integrated "overview" documentation about the
state machine that an STT embodies may be useful - either around line 29 (to
give the general "This is what the file does") or perhaps here ("These are the
states and their transitions"). My gut is line 29.

I mention this because right now, much of the documentation is associated with
the members/variables/types, which is good (yay documentation), but the
comprehensive overview of the interconnections and what's going on is less clear
- so there's a lot more jumping around code to grok (I think an example of this
is 154-162 gets to documenting some of the state machine flow, but it's not
obvious without understanding the relationship between both 105-113 and the
inline comments in 237-291)

I suspect this is *largely* for the .cc file - I think you've got the right
level of detail in the .h.

To some extent, something like
https://cs.chromium.org/chromium/src/base/message_loop/message_pump.h?rcl=0&l=49
is a fairly detailed processing model, but that's more suited for the public
interface.

The goal here is to explain a bit more about "the lifecycle of an audit request"
- so that the implementation itself has a good overview of the states.

However, happy to discuss further if you feel differently. Mostly, my goal is:
Can someone who has limited knowledge about CT pick up this file and reasonably
get an understanding of what's going on? Obviously, further reading is expected,
but are the concepts and transitions clear?

[Eran Messeri, 2017/01/03 23:07:41]

Done - I've added documentation with an overview of the process to line 29.
Please let me know if it needs further refining - obviously it is tied to the
SingleTreeTracker's implementation.

+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;
+}
+
 }  // namespace
 
 namespace certificate_transparency {

[Ryan Sleevi, 2016/12/22 21:33:21]

note: Nothing wrong with moving this line up to 29/30

[Eran Messeri, 2017/01/03 23:07:41]

Done.

+// The entry that is being audited. Immutable - once created, the entry

[Ryan Sleevi, 2016/12/22 21:33:21]

linebreak between 136/137

[Eran Messeri, 2017/01/03 23:07:41]

Shouldn't be needed now that the namespace declaration is on line 29, right?

+// to audit does not change.

[Ryan Sleevi, 2016/12/22 21:33:21]

As a class comment, "Immutable" isn't a guarantee you can make about the type -
merely about how it's used, and unless someone checks every single EntryToAudit
(including its indirection through iterators), it's hard to guarantee.

I'd be more inclined to drop the "Immutable" (as a promise) - but happy to
explore if you feel it's appropriate to indicate something about "How it should
be used" (rather than "How it is used")

[Eran Messeri, 2017/01/03 23:07:41]

Done - removed the 2nd sentence entirely.

+struct SingleTreeTracker::EntryToAudit {
+  base::Time sct_timestamp;
+  SHA256HashValue leaf_hash;
+
+  explicit EntryToAudit(base::Time timestamp) : sct_timestamp(timestamp) {}
+};
+
+// 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;

[Ryan Sleevi, 2016/12/22 21:33:21]

same remarks about newlines for large blocks, especially when transitioning from
something like 153-154

[Eran Messeri, 2017/01/03 23:07:41]

Done.

+  // The proof to be filled in by the LogDnsClient
+  net::ct::MerkleAuditProof proof;

[Ryan Sleevi, 2016/12/22 21:33:21]

It's a little surprising (and seemingly inconsistent) here about the use of the
net::ct:: type here, versus the using declarations above (warning; I'm not a big
fan of 'using' in general, but I recognize the style guide permitting both)

It just stood out when (re-)reading this code.

[Eran Messeri, 2017/01/03 23:07:41]

Done - added a using declaration at the top, removed the net::ct:: namespace
qualification.

+  // 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) {}
+};
+
+// 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.
+bool SingleTreeTracker::OrderByTimestamp::operator()(
+    const EntryToAudit& lhs,
+    const EntryToAudit& rhs) const {
+  if (lhs.sct_timestamp != rhs.sct_timestamp)
+    return lhs.sct_timestamp < rhs.sct_timestamp;
+
+  return net::SHA256HashValueLessThan()(lhs.leaf_hash, rhs.leaf_hash);
+}
+
+struct SingleTreeTracker::EntryAuditResult {};
 
 SingleTreeTracker::SingleTreeTracker(
-    scoped_refptr<const net::CTLogVerifier> ct_log)
-    : ct_log_(std::move(ct_log)) {}
+    scoped_refptr<const net::CTLogVerifier> ct_log,
+    LogDnsClient* dns_client)
+    : ct_log_(std::move(ct_log)),
+      checked_entries_(kCheckedEntriesCacheSize),
+      dns_client_(dns_client),
+      weak_factory_(this) {
+  memory_pressure_listener_.reset(new base::MemoryPressureListener(base::Bind(
+      &SingleTreeTracker::OnMemoryPressure, base::Unretained(this))));
+}
 
 SingleTreeTracker::~SingleTreeTracker() {}
 
 void SingleTreeTracker::OnSCTVerified(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
   DCHECK_EQ(ct_log_->key_id(), sct->log_id);
 
-  // SCT was previously observed, so its status should not be changed.
-  if (entries_status_.find(sct->timestamp) != entries_status_.end())
+  EntryToAudit entry(sct->timestamp);
+  if (!GetLogEntryLeafHash(cert, sct, &entry.leaf_hash))
     return;
 
+  // Avoid queueing multiple instances of the same entry.
+  if (GetAuditedEntryInclusionStatus(entry) != SCT_NOT_OBSERVED)
+    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() ||
-      (verified_sth_.timestamp <
-       (sct->timestamp + base::TimeDelta::FromHours(24)))) {
-    entries_status_.insert(
-        std::make_pair(sct->timestamp, SCT_PENDING_NEWER_STH));
+      !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()) {
+    if (verified_sth_.timestamp.is_null()) {
+      LogCanBeCheckedForInclusionToUMA(VALID_STH_REQUIRED);
+    } else {
       LogCanBeCheckedForInclusionToUMA(NEWER_STH_REQUIRED);
-    } else {
-      LogCanBeCheckedForInclusionToUMA(VALID_STH_REQUIRED);
     }
 
     return;
   }
 
   LogCanBeCheckedForInclusionToUMA(CAN_BE_CHECKED);
-  // TODO(eranm): Check inclusion here.
-  entries_status_.insert(
-      std::make_pair(sct->timestamp, SCT_PENDING_INCLUSION_CHECK));
+  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);
+      (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)) {
-    verified_sth_ = sth;
+  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;
   }
 
-  // Find out which SCTs can now be checked for inclusion.
-  // TODO(eranm): Keep two maps of MerkleTreeLeaf instances, one for leaves
-  // pending inclusion checks and one for leaves pending a new STH.
-  // The comparison function between MerkleTreeLeaf instances should use the
-  // timestamp to determine sorting order, so that bulk moving from one
-  // map to the other can happen.
-  auto entry = entries_status_.begin();
-  while (entry != entries_status_.end() &&
-         entry->first < verified_sth_.timestamp) {
-    entry->second = SCT_PENDING_INCLUSION_CHECK;
-    ++entry;
-    // TODO(eranm): Check inclusion here.
+  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 first_entry_to_audit = 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 entry_to_stop_at = std::lower_bound(

[Ryan Sleevi, 2016/12/22 21:33:21]

nit: another symmetry remark: [first_entry_to_audit, entry_to_stop_at] represent
a bounding range, but aren't named in a way that reflects that. A simple way to
address this might be "last_entry_to_audit" or go further (and more mirror
std::begin()/std::end() style naming) or "auditable_entries_begin" /
"auditable_entries_end"...

There's probably other ways to word that too, and if it ends up too unnatural,
then it may not be worth doing, but I wanted to highlight it in case you had any
ideas.

[Eran Messeri, 2017/01/03 23:07:41]

Done - changed to auditable_entries_begin / auditable_entries_end.

+      first_entry_to_audit, 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 = first_entry_to_audit; curr_entry != entry_to_stop_at;
+       ++curr_entry) {
+    DCHECK_EQ(curr_entry->second.state, PENDING_NEWER_STH);
+    curr_entry->second.state = PENDING_INCLUSION_PROOF_REQUEST;
   }
+
+  ProcessPendingEntries();
 }
 
 SingleTreeTracker::SCTInclusionStatus
 SingleTreeTracker::GetLogEntryInclusionStatus(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
-  auto it = entries_status_.find(sct->timestamp);
+  EntryToAudit entry(sct->timestamp);
+  if (!GetLogEntryLeafHash(cert, sct, &entry.leaf_hash))
+    return SCT_NOT_OBSERVED;
+  return GetAuditedEntryInclusionStatus(entry);
+}
 
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+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);

[Ryan Sleevi, 2016/12/22 21:33:21]

nit: More copying that we might want to optimize in the future to avoid.

[Eran Messeri, 2017/01/03 23:07:41]

Acknowledged - as mentioned, I'll do a pass to see where copying can be avoided
once this CL lands.

+    net::Error result = dns_client_->QueryAuditProof(
+        ct_log_->dns_domain(), leaf_hash, verified_sth_.tree_size,
+        &(it->second.proof),
+        base::Bind(&SingleTreeTracker::OnAuditProofObtained,
+                   weak_factory_.GetWeakPtr(), 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) {
+      dns_client_->NotifyWhenNotThrottled(
+          base::Bind(&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);
+      // 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) {
+  const auto checked_entries_iterator = checked_entries_.Get(
+      std::string(reinterpret_cast<const char*>(entry.leaf_hash.data),
+                  crypto::kSHA256Length));
+  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()) {
+    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;

[Ryan Sleevi, 2016/12/22 21:33:21]

Does it make more sense to inverse this conditional, following the "error
checking first" argument?

auto pending_iterator = pending_entries_.find(entry);
if (pending_iterator == pending_entries_.end()) {
  return SCT_NOT_OBSERVED;
}

switch (pending_iterator->second.state) {
  ...
}


I realize that this may have been written as such due to MSVC complaining about
a possible lack of return (that is, I don't think the warnings engine considers
the fact that the switch statement would be a complete switch state, if only
because it's considering invalid enum values and we don't want to explicitly add
a default to the switch), so you'll likely *still* need a return value here
(which you could annotate with a NOTREACHED(), like you did on 370), but I think
it may make the flow clearer by reducing a level of nesting of complex logic.

[Eran Messeri, 2017/01/03 23:07:41]

Done (I suspect you have to make this comment a lot because of my preference to
have as few return statements as possible, I'll make a note to short-circuit and
return early if it simplifies the logic).

+}
+
+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) {
+    // XXX(eranm): Should failures be cached? For now, they are not.
+    LogInclusionCheckResult(FAILED_GETTING_INCLUSION_PROOF);
+    pending_entries_.erase(it);
+    return;
+  }
+
+  std::string leaf_hash(reinterpret_cast<const char*>(entry.leaf_hash.data),
+                        crypto::kSHA256Length);
+
+  if (ct_log_->VerifyAuditProof(it->second.proof, it->second.root_hash,
+                                leaf_hash)) {
+    checked_entries_.Put(leaf_hash, EntryAuditResult());
+    LogInclusionCheckResult(GOT_VALID_INCLUSION_PROOF);
+  } else {
+    LogInclusionCheckResult(GOT_INVALID_INCLUSION_PROOF);
+  }

[Ryan Sleevi, 2016/12/22 21:33:20]

Similar remarks about error handling first. Does it make sense to

bool verified = ct_log_->...
pending_entries_.erase(it);

if (!verified) {
  LogInclusionCheckResult(GOT_INVALID_INCLUSION_PROOF);
  return;
}

checked_entries_.Put(leaf_hash, EntryAuditResult());
LogInclusionCheckResult(GOT_VALID_INCLUSION_PROOF);

[Eran Messeri, 2017/01/03 23:07:41]

Partly done:
Because I've changed checked_entries_ to store net::SHA256HashValue, then
entry.leaf_hash must live until it's added to checked_entries_, so the entry
cannot be erased beforehand.

+  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:
+      pending_entries_.clear();
+    // Fall through to clearing the other cache.
+    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_MODERATE:
+      checked_entries_.Clear();
+      break;
+  }
 }
 
 }  // namespace certificate_transparency