--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -463,45 +463,43 @@ Classifier::Check(const nsACString& aSpe
       nsAutoCString checking;
       lookupHash.ToHexString(checking);
       LOG(("Checking fragment %s, hash %s (%X)", fragments[i].get(),
            checking.get(), lookupHash.ToUint32()));
     }
 
     for (uint32_t i = 0; i < cacheArray.Length(); i++) {
       LookupCache *cache = cacheArray[i];
-      bool has, complete;
+      bool has, fromCache;
       uint32_t matchLength;
 
-      rv = cache->Has(lookupHash, &has, &complete, &matchLength);
+      rv = cache->Has(lookupHash, &has, &matchLength, &fromCache);
       NS_ENSURE_SUCCESS(rv, rv);
       if (has) {
         LookupResult *result = aResults.AppendElement();
         if (!result)
           return NS_ERROR_OUT_OF_MEMORY;
 
-        int64_t age;
-        bool found = mTableFreshness.Get(cache->TableName(), &age);
-        if (!found) {
-          age = 24 * 60 * 60; // just a large number
-        } else {
-          int64_t now = (PR_Now() / PR_USEC_PER_SEC);
-          age = now - age;
+        // For V2, there is no TTL for caching, so we use table freshness to
+        // decide if matching a completion should trigger a gethash request or not.
+        // For V4, this is done by Positive Caching & Negative Caching mechanism.
+        bool confirmed = false;
+        if (fromCache) {
+          cache->IsHashEntryConfirmed(lookupHash, mTableFreshness,
+                                      aFreshnessGuarantee, &confirmed);
         }
 
-        LOG(("Found a result in %s: %s (Age: %Lds)",
+        LOG(("Found a result in %s: %s",
              cache->TableName().get(),
-             complete ? "complete." : "Not complete.",
-             age));
+             confirmed ? "confirmed." : "Not confirmed."));
 
         result->hash.complete = lookupHash;
-        result->mComplete = complete;
-        result->mFresh = (age < aFreshnessGuarantee);
+        result->mConfirmed = confirmed;
         result->mTableName.Assign(cache->TableName());
-        result->mPartialHashLength = matchLength;
+        result->mPartialHashLength = confirmed ? COMPLETE_SIZE : matchLength;
 
         if (LookupCache::Cast<LookupCacheV4>(cache)) {
           matchingStatistics |= PrefixMatch::eMatchV4Prefix;
         } else {
           matchingStatistics |= PrefixMatch::eMatchV2Prefix;
         }
       }
     }

--- a/toolkit/components/url-classifier/Classifier.h
+++ b/toolkit/components/url-classifier/Classifier.h
@@ -153,17 +153,17 @@ private:
   // Used for atomically updating the other dirs.
   nsCOMPtr<nsIFile> mBackupDirectory;
   nsCOMPtr<nsIFile> mToDeleteDirectory;
   nsCOMPtr<nsICryptoHash> mCryptoHash;
   nsTArray<LookupCache*> mLookupCaches;
   nsTArray<nsCString> mActiveTablesCache;
   uint32_t mHashKey;
   // Stores the last time a given table was updated (seconds).
-  nsDataHashtable<nsCStringHashKey, int64_t> mTableFreshness;
+  TableFreshnessMap mTableFreshness;
 
   // In-memory cache for the result of TableRequest. See
   // nsIUrlClassifierDBService.getTables for the format.
   nsCString mTableRequestResult;
 
   // Whether mTableRequestResult is outdated and needs to
   // be reloaded from disk.
   bool mIsTableRequestResultOutdated;

--- a/toolkit/components/url-classifier/Entries.h
+++ b/toolkit/components/url-classifier/Entries.h
@@ -11,16 +11,17 @@
 #define SBEntries_h__
 
 #include "nsTArray.h"
 #include "nsString.h"
 #include "nsICryptoHash.h"
 #include "nsNetUtil.h"
 #include "nsIOutputStream.h"
 #include "nsClassHashtable.h"
+#include "nsDataHashtable.h"
 
 #if DEBUG
 #include "plbase64.h"
 #endif
 
 namespace mozilla {
 namespace safebrowsing {
 
@@ -311,12 +312,14 @@ WriteTArray(nsIOutputStream* aStream, ns
   uint32_t written;
   return aStream->Write(reinterpret_cast<char*>(aArray.Elements()),
                         aArray.Length() * sizeof(T),
                         &written);
 }
 
 typedef nsClassHashtable<nsUint32HashKey, nsCString> PrefixStringMap;
 
+typedef nsDataHashtable<nsCStringHashKey, int64_t> TableFreshnessMap;
+
 } // namespace safebrowsing
 } // namespace mozilla
 
 #endif // SBEntries_h__

--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -416,20 +416,20 @@ void
 LookupCacheV2::ClearAll()
 {
   LookupCache::ClearAll();
   mUpdateCompletions.Clear();
 }
 
 nsresult
 LookupCacheV2::Has(const Completion& aCompletion,
-                   bool* aHas, bool* aComplete,
-                   uint32_t* aMatchLength)
+                   bool* aHas, uint32_t* aMatchLength,
+                   bool* aFromCache)
 {
-  *aHas = *aComplete = false;
+  *aHas = *aFromCache = false;
   *aMatchLength = 0;
 
   uint32_t prefix = aCompletion.ToUint32();
 
   bool found;
   nsresult rv = mPrefixSet->Contains(prefix, &found);
   NS_ENSURE_SUCCESS(rv, rv);
 
@@ -438,24 +438,43 @@ LookupCacheV2::Has(const Completion& aCo
   if (found) {
     *aHas = true;
     *aMatchLength = PREFIX_SIZE;
   }
 
   if ((mGetHashCache.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex) ||
       (mUpdateCompletions.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex)) {
     LOG(("Complete in %s", mTableName.get()));
-    *aComplete = true;
+    *aFromCache = true;
     *aHas = true;
     *aMatchLength = COMPLETE_SIZE;
   }
 
   return NS_OK;
 }
 
+void
+LookupCacheV2::IsHashEntryConfirmed(const Completion& aEntry,
+                                    const TableFreshnessMap& aTableFreshness,
+                                    uint32_t aFreshnessGuarantee,
+                                    bool* aConfirmed)
+{
+  int64_t age; // in seconds
+  bool found = aTableFreshness.Get(mTableName, &age);
+  if (!found) {
+    *aConfirmed = false;
+  } else {
+    int64_t now = (PR_Now() / PR_USEC_PER_SEC);
+    MOZ_ASSERT(age <= now);
+
+    // Considered completion as unsafe if its table is up-to-date.
+    *aConfirmed = (now - age) < aFreshnessGuarantee;
+  }
+}
+
 nsresult
 LookupCacheV2::Build(AddPrefixArray& aAddPrefixes,
                      AddCompleteArray& aAddCompletes)
 {
   Telemetry::Accumulate(Telemetry::URLCLASSIFIER_LC_COMPLETIONS,
                         static_cast<uint32_t>(aAddCompletes.Length()));
 
   mUpdateCompletions.Clear();

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -20,19 +20,18 @@
 namespace mozilla {
 namespace safebrowsing {
 
 #define MAX_HOST_COMPONENTS 5
 #define MAX_PATH_COMPONENTS 4
 
 class LookupResult {
 public:
-  LookupResult() : mComplete(false), mNoise(false),
-                   mFresh(false), mProtocolConfirmed(false),
-                   mPartialHashLength(0) {}
+  LookupResult() : mNoise(false), mProtocolConfirmed(false),
+                   mPartialHashLength(0), mConfirmed(false) {}
 
   // The fragment that matched in the LookupCache
   union {
     Prefix fixedLengthPrefix;
     Completion complete;
   } hash;
 
   const Completion &CompleteHash() {
@@ -48,37 +47,36 @@ public:
   nsCString PartialHashHex() {
     nsAutoCString hex;
     for (size_t i = 0; i < mPartialHashLength; i++) {
       hex.AppendPrintf("%.2X", hash.complete.buf[i]);
     }
     return hex;
   }
 
-  bool Confirmed() const { return (mComplete && mFresh) || mProtocolConfirmed; }
-  bool Complete() const { return mComplete; }
+  bool Confirmed() const { return mConfirmed || mProtocolConfirmed; }
 
   // True if we have a complete match for this hash in the table.
-  bool mComplete;
+  bool Complete() const { return mPartialHashLength == COMPLETE_SIZE; }
 
   // True if this is a noise entry, i.e. an extra entry
   // that is inserted to mask the true URL we are requesting.
   // Noise entries will not have a complete 256-bit hash as
   // they are fetched from the local 32-bit database and we
   // don't know the corresponding full URL.
   bool mNoise;
 
-  // True if we've updated this table recently-enough.
-  bool mFresh;
-
   bool mProtocolConfirmed;
 
   nsCString mTableName;
 
   uint32_t mPartialHashLength;
+
+  // True as long as this lookup is complete and hasn't expired.
+  bool mConfirmed;
 };
 
 typedef nsTArray<LookupResult> LookupResultArray;
 
 struct CacheResult {
   AddComplete entry;
   nsCString table;
 
@@ -134,18 +132,23 @@ public:
 #if DEBUG
   void DumpCache();
 #endif
 
   virtual nsresult Open();
   virtual nsresult Init() = 0;
   virtual nsresult ClearPrefixes() = 0;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete,
-                       uint32_t* aMatchLength) = 0;
+                       bool* aHas, uint32_t* aMatchLength,
+                       bool* aFromCache) = 0;
+
+  virtual void IsHashEntryConfirmed(const Completion& aEntry,
+                                    const TableFreshnessMap& aTableFreshness,
+                                    uint32_t aFreshnessGuarantee,
+                                    bool* aConfirmed) = 0;
 
   virtual void ClearAll();
 
   template<typename T>
   static T* Cast(LookupCache* aThat) {
     return ((aThat && T::VER == aThat->Ver()) ? reinterpret_cast<T*>(aThat) : nullptr);
   }
 
@@ -181,18 +184,23 @@ public:
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV2() {}
 
   virtual nsresult Init() override;
   virtual nsresult Open() override;
   virtual void ClearAll() override;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete,
-                       uint32_t* aMatchLength) override;
+                       bool* aHas, uint32_t* aMatchLength,
+                       bool* aFromCache) override;
+
+  virtual void IsHashEntryConfirmed(const Completion& aEntry,
+                                    const TableFreshnessMap& aTableFreshness,
+                                    uint32_t aFreshnessGuarantee,
+                                    bool* aConfirmed) override;
 
   nsresult Build(AddPrefixArray& aAddPrefixes,
                  AddCompleteArray& aAddCompletes);
 
   nsresult GetPrefixes(FallibleTArray<uint32_t>& aAddPrefixes);
 
 #if DEBUG
   void DumpCompletions();

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -75,42 +75,53 @@ LookupCacheV4::Init()
   nsresult rv = mVLPrefixSet->Init(mTableName);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 LookupCacheV4::Has(const Completion& aCompletion,
-                   bool* aHas, bool* aComplete,
-                   uint32_t* aMatchLength)
+                   bool* aHas, uint32_t* aMatchLength,
+                   bool* aFromCache)
 {
-  *aHas = *aComplete = false;
+  *aHas = *aFromCache = false;
   *aMatchLength = 0;
 
   uint32_t length = 0;
   nsDependentCSubstring fullhash;
   fullhash.Rebind((const char *)aCompletion.buf, COMPLETE_SIZE);
 
   nsresult rv = mVLPrefixSet->Matches(fullhash, &length);
   NS_ENSURE_SUCCESS(rv, rv);
 
   *aHas = length >= PREFIX_SIZE;
-  *aComplete = length == COMPLETE_SIZE;
   *aMatchLength = length;
 
   if (LOG_ENABLED()) {
     uint32_t prefix = aCompletion.ToUint32();
     LOG(("Probe in V4 %s: %X, found %d, complete %d", mTableName.get(),
-          prefix, *aHas, *aComplete));
+          prefix, *aHas, length == COMPLETE_SIZE));
   }
 
+  // TODO : Bug 1311935 - Implement v4 caching
+
   return NS_OK;
 }
 
+void
+LookupCacheV4::IsHashEntryConfirmed(const Completion& aEntry,
+                                    const TableFreshnessMap& aTableFreshness,
+                                    uint32_t aFreshnessGuarantee,
+                                    bool* aConfirmed)
+{
+  // TODO : Bug 1311935 - Implement v4 caching
+  *aConfirmed = true;
+}
+
 nsresult
 LookupCacheV4::Build(PrefixStringMap& aPrefixMap)
 {
   return mVLPrefixSet->SetPrefixes(aPrefixMap);
 }
 
 nsresult
 LookupCacheV4::GetPrefixes(PrefixStringMap& aPrefixMap)

--- a/toolkit/components/url-classifier/LookupCacheV4.h
+++ b/toolkit/components/url-classifier/LookupCacheV4.h
@@ -20,18 +20,23 @@ public:
   explicit LookupCacheV4(const nsACString& aTableName,
                          const nsACString& aProvider,
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV4() {}
 
   virtual nsresult Init() override;
   virtual nsresult Has(const Completion& aCompletion,
-                       bool* aHas, bool* aComplete,
-                       uint32_t* aMatchLength) override;
+                       bool* aHas, uint32_t* aMatchLength,
+                       bool* aFromCache) override;
+
+  virtual void IsHashEntryConfirmed(const Completion& aEntry,
+                                    const TableFreshnessMap& aTableFreshness,
+                                    uint32_t aFreshnessGuarantee,
+                                    bool* aConfirmed) override;
 
   nsresult Build(PrefixStringMap& aPrefixMap);
 
   nsresult GetPrefixes(PrefixStringMap& aPrefixMap);
 
   // ApplyUpdate will merge data stored in aTableUpdate with prefixes in aInputMap.
   nsresult ApplyUpdate(TableUpdateV4* aTableUpdate,
                        PrefixStringMap& aInputMap,

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -999,20 +999,19 @@ nsUrlClassifierLookupCallback::LookupCom
                                           gethashUrl,
                                           result.mTableName,
                                           this);
         if (NS_SUCCEEDED(rv)) {
           mPendingCompletions++;
         }
       } else {
         // For tables with no hash completer, a complete hash match is
-        // good enough, we'll consider it fresh, even if it hasn't been updated
-        // in 45 minutes.
+        // good enough, we'll consider it is valid.
         if (result.Complete()) {
-          result.mFresh = true;
+          result.mConfirmed = true;
           LOG(("Skipping completion in a table without a valid completer (%s).",
                result.mTableName.get()));
         } else {
           NS_WARNING("Partial match in a table without a valid completer, ignoring partial match.");
         }
       }
     }
   }

--- a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -55,23 +55,23 @@ TestHasPrefix(const _Fragment& aFragment
 
   RunTestInNewThread([&] () -> void {
     UniquePtr<LookupCache> cache = SetupLookupCacheV4(array);
 
     Completion lookupHash;
     nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
     lookupHash.FromPlaintext(aFragment, cryptoHash);
 
-    bool has, complete;
+    bool has, fromCache;
     uint32_t matchLength;
-    nsresult rv = cache->Has(lookupHash, &has, &complete, &matchLength);
+    nsresult rv = cache->Has(lookupHash, &has, &matchLength, &fromCache);
 
     EXPECT_EQ(rv, NS_OK);
     EXPECT_EQ(has, aExpectedHas);
-    EXPECT_EQ(complete, aExpectedComplete);
+    EXPECT_EQ(matchLength == COMPLETE_SIZE, aExpectedComplete);
 
     cache->ClearAll();
   });
 
 }
 
 TEST(LookupCacheV4, HasComplete)
 {