--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -1358,41 +1358,55 @@ Classifier::GetLookupCacheFrom(const nsA
 }
 
 nsresult
 Classifier::ReadNoiseEntries(const Prefix& aPrefix,
                              const nsACString& aTableName,
                              uint32_t aCount,
                              PrefixArray* aNoiseEntries)
 {
-  // TODO : Bug 1297962, support adding noise for v4
-  LookupCacheV2 *cache =
-    LookupCache::Cast<LookupCacheV2>(GetLookupCache(aTableName));
+  FallibleTArray<uint32_t> prefixes;
+  nsresult rv;
+
+  LookupCache *cache = GetLookupCache(aTableName);
   if (!cache) {
     return NS_ERROR_FAILURE;
   }
 
-  FallibleTArray<uint32_t> prefixes;
-  nsresult rv = cache->GetPrefixes(prefixes);
+  LookupCacheV2* cacheV2 = LookupCache::Cast<LookupCacheV2>(cache);
+  if (cacheV2) {
+    rv = cacheV2->GetPrefixes(prefixes);
+  } else {
+    rv = LookupCache::Cast<LookupCacheV4>(cache)->GetFixedLengthPrefixes(prefixes);
+  }
+
   NS_ENSURE_SUCCESS(rv, rv);
 
-  size_t idx = prefixes.BinaryIndexOf(aPrefix.ToUint32());
-
-  if (idx == nsTArray<uint32_t>::NoIndex) {
+  if (prefixes.Length() == 0) {
     NS_WARNING("Could not find prefix in PrefixSet during noise lookup");
     return NS_ERROR_FAILURE;
   }
 
-  idx -= idx % aCount;
+  for (size_t i = 0; i < aCount; i++) {
+    // Pick some prefixes from cache as noise
+    // We pick a random prefix index from 0 to prefixes.Length() - 1;
+    uint32_t idx = rand() % prefixes.Length();
 
-  for (size_t i = 0; (i < aCount) && ((idx+i) < prefixes.Length()); i++) {
-    Prefix newPref;
-    newPref.FromUint32(prefixes[idx+i]);
-    if (newPref != aPrefix) {
-      aNoiseEntries->AppendElement(newPref);
+    Prefix newPrefix;
+    uint32_t hash = prefixes[idx];
+    // In the case V4 little endian, we did swapping endian when converting from char* to
+    // int, should revert endian to make sure we will send hex string correctly
+    // See https://bugzilla.mozilla.org/show_bug.cgi?id=1283007#c23
+    if (!cacheV2 && !bool(MOZ_BIG_ENDIAN)) {
+      hash = NativeEndian::swapFromBigEndian(prefixes[idx]);
+    }
+
+    newPrefix.FromUint32(hash);
+    if (newPrefix != aPrefix) {
+      aNoiseEntries->AppendElement(newPrefix);
     }
   }
 
   return NS_OK;
 }
 
 nsresult
 Classifier::LoadMetadata(nsIFile* aDirectory, nsACString& aResult)

--- a/toolkit/components/url-classifier/Classifier.h
+++ b/toolkit/components/url-classifier/Classifier.h
@@ -108,16 +108,19 @@ public:
                                            const nsACString& aTableName,
                                            const nsACString& aProvider,
                                            nsIFile** aPrivateStoreDirectory);
 
   // Swap in in-memory and on-disk database and remove all
   // update intermediaries.
   nsresult SwapInNewTablesAndCleanup();
 
+  LookupCache *GetLookupCache(const nsACString& aTable,
+                              bool aForUpdate = false);
+
 private:
   void DropStores();
   void DeleteTables(nsIFile* aDirectory, const nsTArray<nsCString>& aTables);
   void AbortUpdateAndReset(const nsCString& aTable);
 
   nsresult CreateStoreDirectory();
   nsresult SetupPathNames();
   nsresult RecoverBackups();
@@ -142,19 +145,16 @@ private:
   nsresult UpdateHashStore(nsTArray<TableUpdate*>* aUpdates,
                            const nsACString& aTable);
 
   nsresult UpdateTableV4(nsTArray<TableUpdate*>* aUpdates,
                          const nsACString& aTable);
 
   nsresult UpdateCache(TableUpdate* aUpdates);
 
-  LookupCache *GetLookupCache(const nsACString& aTable,
-                              bool aForUpdate = false);
-
   LookupCache *GetLookupCacheForUpdate(const nsACString& aTable) {
     return GetLookupCache(aTable, true);
   }
 
   LookupCache *GetLookupCacheFrom(const nsACString& aTable,
                                   nsTArray<LookupCache*>& aLookupCaches,
                                   nsIFile* aRootStoreDirectory);
 

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -135,16 +135,22 @@ LookupCacheV4::Build(PrefixStringMap& aP
 
 nsresult
 LookupCacheV4::GetPrefixes(PrefixStringMap& aPrefixMap)
 {
   return mVLPrefixSet->GetPrefixes(aPrefixMap);
 }
 
 nsresult
+LookupCacheV4::GetFixedLengthPrefixes(FallibleTArray<uint32_t>& aPrefixes)
+{
+  return mVLPrefixSet->GetFixedLengthPrefixes(aPrefixes);
+}
+
+nsresult
 LookupCacheV4::ClearPrefixes()
 {
   // Clear by seting a empty map
   PrefixStringMap map;
   return mVLPrefixSet->SetPrefixes(map);
 }
 
 nsresult

--- a/toolkit/components/url-classifier/LookupCacheV4.h
+++ b/toolkit/components/url-classifier/LookupCacheV4.h
@@ -33,16 +33,17 @@ public:
                                     uint32_t aFreshnessGuarantee,
                                     bool* aConfirmed) override;
 
   virtual bool IsEmpty() override;
 
   nsresult Build(PrefixStringMap& aPrefixMap);
 
   nsresult GetPrefixes(PrefixStringMap& aPrefixMap);
+  nsresult GetFixedLengthPrefixes(FallibleTArray<uint32_t>& aPrefixes);
 
   // ApplyUpdate will merge data stored in aTableUpdate with prefixes in aInputMap.
   nsresult ApplyUpdate(TableUpdateV4* aTableUpdate,
                        PrefixStringMap& aInputMap,
                        PrefixStringMap& aOutputMap);
 
   nsresult WriteMetadata(TableUpdateV4* aTableUpdate);
   nsresult LoadMetadata(nsACString& aState, nsACString& aChecksum);

--- a/toolkit/components/url-classifier/VariableLengthPrefixSet.cpp
+++ b/toolkit/components/url-classifier/VariableLengthPrefixSet.cpp
@@ -32,17 +32,17 @@ const uint32_t VariableLengthPrefixSet::
 // they will be passed to nsUrlClassifierPrefixSet because of better optimization.
 VariableLengthPrefixSet::VariableLengthPrefixSet()
   : mLock("VariableLengthPrefixSet.mLock")
   , mMemoryReportPath()
 {
   mFixedPrefixSet = new nsUrlClassifierPrefixSet();
 }
 
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::Init(const nsACString& aName)
 {
   mMemoryReportPath =
     nsPrintfCString(
       "explicit/storage/prefix-set/%s",
       (!aName.IsEmpty() ? PromiseFlatCString(aName).get() : "?!")
     );
 
@@ -51,17 +51,17 @@ VariableLengthPrefixSet::Init(const nsAC
   return NS_OK;
 }
 
 VariableLengthPrefixSet::~VariableLengthPrefixSet()
 {
   UnregisterWeakMemoryReporter(this);
 }
 
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::SetPrefixes(const PrefixStringMap& aPrefixMap)
 {
   MutexAutoLock lock(mLock);
 
   // Prefix size should not less than 4-bytes or greater than 32-bytes
   for (auto iter = aPrefixMap.ConstIter(); !iter.Done(); iter.Next()) {
     if (iter.Key() < PREFIX_SIZE_FIXED ||
         iter.Key() > COMPLETE_SIZE) {
@@ -147,20 +147,26 @@ VariableLengthPrefixSet::GetPrefixes(Pre
   // Copy variable-length prefix set
   for (auto iter = mVLPrefixSet.ConstIter(); !iter.Done(); iter.Next()) {
     aPrefixMap.Put(iter.Key(), new nsCString(*iter.Data()));
   }
 
   return NS_OK;
 }
 
+nsresult
+VariableLengthPrefixSet::GetFixedLengthPrefixes(FallibleTArray<uint32_t>& aPrefixes)
+{
+  return mFixedPrefixSet->GetPrefixesNative(aPrefixes);
+}
+
 // It should never be the case that more than one hash prefixes match a given
 // full hash. However, if that happens, this method returns any one of them.
 // It does not guarantee which one of those will be returned.
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::Matches(const nsACString& aFullHash, uint32_t* aLength)
 {
   MutexAutoLock lock(mLock);
 
   // Only allow full-length hash to check if match any of the prefix
   MOZ_ASSERT(aFullHash.Length() == COMPLETE_SIZE);
   NS_ENSURE_ARG_POINTER(aLength);
 
@@ -184,30 +190,30 @@ VariableLengthPrefixSet::Matches(const n
       *aLength = iter.Key();
       return NS_OK;
     }
   }
 
   return NS_OK;
 }
 
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::IsEmpty(bool* aEmpty)
 {
   MutexAutoLock lock(mLock);
 
   NS_ENSURE_ARG_POINTER(aEmpty);
 
   mFixedPrefixSet->IsEmpty(aEmpty);
   *aEmpty = *aEmpty && mVLPrefixSet.IsEmpty();
 
   return NS_OK;
 }
 
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::LoadFromFile(nsIFile* aFile)
 {
   MutexAutoLock lock(mLock);
 
   NS_ENSURE_ARG_POINTER(aFile);
 
   Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_VLPS_FILELOAD_TIME> timer;
 
@@ -236,17 +242,17 @@ VariableLengthPrefixSet::LoadFromFile(ns
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = LoadPrefixes(in);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;;
 }
 
-NS_IMETHODIMP
+nsresult
 VariableLengthPrefixSet::StoreToFile(nsIFile* aFile)
 {
   NS_ENSURE_ARG_POINTER(aFile);
 
   MutexAutoLock lock(mLock);
 
   nsCOMPtr<nsIOutputStream> localOutFile;
   nsresult rv = NS_NewLocalFileOutputStream(getter_AddRefs(localOutFile), aFile,

--- a/toolkit/components/url-classifier/VariableLengthPrefixSet.h
+++ b/toolkit/components/url-classifier/VariableLengthPrefixSet.h
@@ -20,23 +20,24 @@ namespace mozilla {
 namespace safebrowsing {
 
 class VariableLengthPrefixSet final
   : public nsIMemoryReporter
 {
 public:
   VariableLengthPrefixSet();
 
-  NS_IMETHOD Init(const nsACString& aName);
-  NS_IMETHOD SetPrefixes(const mozilla::safebrowsing::PrefixStringMap& aPrefixMap);
-  NS_IMETHOD GetPrefixes(mozilla::safebrowsing::PrefixStringMap& aPrefixMap);
-  NS_IMETHOD Matches(const nsACString& aFullHash, uint32_t* aLength);
-  NS_IMETHOD IsEmpty(bool* aEmpty);
-  NS_IMETHOD LoadFromFile(nsIFile* aFile);
-  NS_IMETHOD StoreToFile(nsIFile* aFile);
+  nsresult Init(const nsACString& aName);
+  nsresult SetPrefixes(const mozilla::safebrowsing::PrefixStringMap& aPrefixMap);
+  nsresult GetPrefixes(mozilla::safebrowsing::PrefixStringMap& aPrefixMap);
+  nsresult GetFixedLengthPrefixes(FallibleTArray<uint32_t>& aPrefixes);
+  nsresult Matches(const nsACString& aFullHash, uint32_t* aLength);
+  nsresult IsEmpty(bool* aEmpty);
+  nsresult LoadFromFile(nsIFile* aFile);
+  nsresult StoreToFile(nsIFile* aFile);
 
   size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf);
 
   NS_DECL_THREADSAFE_ISUPPORTS
   NS_DECL_NSIMEMORYREPORTER
 
 private:
   virtual ~VariableLengthPrefixSet();

--- a/toolkit/components/url-classifier/tests/gtest/Common.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/Common.cpp
@@ -72,8 +72,45 @@ PrefixArrayToPrefixStringMap(const nsTAr
 
   for (uint32_t i = 0; i < prefixArray.Length(); i++) {
     const nsCString& prefix = prefixArray[i];
     nsCString* prefixString = out.LookupOrAdd(prefix.Length());
     prefixString->Append(prefix.BeginReading(), prefix.Length());
   }
 }
 
+nsresult
+PrefixArrayToAddPrefixArrayV2(const nsTArray<nsCString>& prefixArray,
+                              AddPrefixArray& out)
+{
+  out.Clear();
+
+  for (size_t i = 0; i < prefixArray.Length(); i++) {
+    // Create prefix hash from string
+    Prefix hash;
+    static_assert(sizeof(hash.buf) == PREFIX_SIZE, "Prefix must be 4 bytes length");
+    memcpy(hash.buf, prefixArray[i].BeginReading(), PREFIX_SIZE);
+    MOZ_ASSERT(prefixArray[i].Length() == PREFIX_SIZE);
+
+    AddPrefix *add = out.AppendElement(fallible);
+    if (!add) {
+      return NS_ERROR_OUT_OF_MEMORY;
+    }
+
+    add->addChunk = i;
+    add->prefix = hash;
+  }
+
+  return NS_OK;
+}
+
+nsCString
+GeneratePrefix(const nsCString& aFragment, uint8_t aLength)
+{
+  Completion complete;
+  nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+  complete.FromPlaintext(aFragment, cryptoHash);
+
+  nsCString hash;
+  hash.Assign((const char *)complete.buf, aLength);
+  return hash;
+}
+

--- a/toolkit/components/url-classifier/tests/gtest/Common.h
+++ b/toolkit/components/url-classifier/tests/gtest/Common.h
@@ -19,8 +19,13 @@ void ApplyUpdate(nsTArray<TableUpdate*>&
 
 void ApplyUpdate(TableUpdate* update);
 
 // This function converts lexigraphic-sorted prefixes to a hashtable
 // which key is prefix size and value is concatenated prefix string.
 void PrefixArrayToPrefixStringMap(const nsTArray<nsCString>& prefixArray,
                                   PrefixStringMap& out);
 
+nsresult PrefixArrayToAddPrefixArrayV2(const nsTArray<nsCString>& prefixArray,
+                                       AddPrefixArray& out);
+
+// Generate a hash prefix from string
+nsCString GeneratePrefix(const nsCString& aFragment, uint8_t aLength);

new file mode 100644
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestClassifier.cpp
@@ -0,0 +1,138 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Common.h"
+#include "Classifier.h"
+#include "LookupCacheV4.h"
+
+#define GTEST_TABLE_V4 NS_LITERAL_CSTRING("gtest-malware-proto")
+#define GTEST_TABLE_V2 NS_LITERAL_CSTRING("gtest-malware-simple")
+
+typedef nsCString _Fragment;
+typedef nsTArray<nsCString> _PrefixArray;
+
+static UniquePtr<Classifier>
+GetClassifier()
+{
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+
+  UniquePtr<Classifier> classifier = MakeUnique<Classifier>();
+  nsresult rv = classifier->Open(*file);
+  EXPECT_TRUE(rv == NS_OK);
+
+  return Move(classifier);
+}
+
+static nsresult
+SetupLookupCacheV4(Classifier* classifier,
+                   const _PrefixArray& aPrefixArray,
+                   const nsACString& aTable)
+{
+  LookupCacheV4* lookupCache =
+    LookupCache::Cast<LookupCacheV4>(classifier->GetLookupCache(aTable, false));
+  if (!lookupCache) {
+    return NS_ERROR_FAILURE;
+  }
+
+  PrefixStringMap map;
+  PrefixArrayToPrefixStringMap(aPrefixArray, map);
+
+  return lookupCache->Build(map);
+}
+
+static nsresult
+SetupLookupCacheV2(Classifier* classifier,
+                   const _PrefixArray& aPrefixArray,
+                   const nsACString& aTable)
+{
+  LookupCacheV2* lookupCache =
+    LookupCache::Cast<LookupCacheV2>(classifier->GetLookupCache(aTable, false));
+  if (!lookupCache) {
+    return NS_ERROR_FAILURE;
+  }
+
+  AddPrefixArray prefixes;
+  AddCompleteArray completions;
+  nsresult rv = PrefixArrayToAddPrefixArrayV2(aPrefixArray, prefixes);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
+  EntrySort(prefixes);
+  return lookupCache->Build(prefixes, completions);
+}
+
+static void
+TestReadNoiseEntries(Classifier* classifier,
+                     const _PrefixArray& aPrefixArray,
+                     const nsCString& aTable,
+                     const nsCString& aFragment)
+{
+  Completion lookupHash;
+  nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+  lookupHash.FromPlaintext(aFragment, cryptoHash);
+  LookupResult result;
+  result.hash.complete = lookupHash;
+
+  PrefixArray noiseEntries;
+  uint32_t noiseCount = 3;
+  nsresult rv;
+  rv = classifier->ReadNoiseEntries(result.hash.fixedLengthPrefix,
+                                    aTable, noiseCount,
+                                    &noiseEntries);
+  ASSERT_TRUE(rv == NS_OK);
+  EXPECT_TRUE(noiseEntries.Length() > 0);
+
+  for (uint32_t i = 0; i < noiseEntries.Length(); i++) {
+    // Test the noise entry should not equal the "real" hash request
+    EXPECT_NE(noiseEntries[i], result.hash.fixedLengthPrefix);
+    // Test the noise entry should exist in the cached prefix array
+    nsAutoCString partialHash;
+    partialHash.Assign(reinterpret_cast<char*>(&noiseEntries[i]), PREFIX_SIZE);
+    EXPECT_TRUE(aPrefixArray.Contains(partialHash));
+  }
+
+}
+
+TEST(Classifier, ReadNoiseEntriesV4)
+{
+  UniquePtr<Classifier> classifier(GetClassifier());
+  _PrefixArray array = { GeneratePrefix(_Fragment("bravo.com/"), 5),
+                         GeneratePrefix(_Fragment("browsing.com/"), 9),
+                         GeneratePrefix(_Fragment("gound.com/"), 4),
+                         GeneratePrefix(_Fragment("small.com/"), 4),
+                         GeneratePrefix(_Fragment("gdfad.com/"), 4),
+                         GeneratePrefix(_Fragment("afdfound.com/"), 4),
+                         GeneratePrefix(_Fragment("dffa.com/"), 4),
+                       };
+  array.Sort();
+
+  nsresult rv;
+  rv = SetupLookupCacheV4(classifier.get(), array, GTEST_TABLE_V4);
+  ASSERT_TRUE(rv == NS_OK);
+
+  TestReadNoiseEntries(classifier.get(), array, GTEST_TABLE_V4, _Fragment("gound.com/"));
+}
+
+TEST(Classifier, ReadNoiseEntriesV2)
+{
+  UniquePtr<Classifier> classifier(GetClassifier());
+  _PrefixArray array = { GeneratePrefix(_Fragment("helloworld.com/"), 4),
+                         GeneratePrefix(_Fragment("firefox.com/"), 4),
+                         GeneratePrefix(_Fragment("chrome.com/"), 4),
+                         GeneratePrefix(_Fragment("safebrowsing.com/"), 4),
+                         GeneratePrefix(_Fragment("opera.com/"), 4),
+                         GeneratePrefix(_Fragment("torbrowser.com/"), 4),
+                         GeneratePrefix(_Fragment("gfaads.com/"), 4),
+                         GeneratePrefix(_Fragment("qggdsas.com/"), 4),
+                         GeneratePrefix(_Fragment("nqtewq.com/"), 4),
+                       };
+
+  nsresult rv;
+  rv = SetupLookupCacheV2(classifier.get(), array, GTEST_TABLE_V2);
+  ASSERT_TRUE(rv == NS_OK);
+
+  TestReadNoiseEntries(classifier.get(), array, GTEST_TABLE_V2, _Fragment("helloworld.com/"));
+}

--- a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -6,29 +6,16 @@
 #include "Common.h"
 
 #define GTEST_SAFEBROWSING_DIR NS_LITERAL_CSTRING("safebrowsing")
 #define GTEST_TABLE NS_LITERAL_CSTRING("gtest-malware-proto")
 
 typedef nsCString _Fragment;
 typedef nsTArray<nsCString> _PrefixArray;
 
-// Generate a hash prefix from string
-static const nsCString
-GeneratePrefix(const _Fragment& aFragment, uint8_t aLength)
-{
-  Completion complete;
-  nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
-  complete.FromPlaintext(aFragment, cryptoHash);
-
-  nsCString hash;
-  hash.Assign((const char *)complete.buf, aLength);
-  return hash;
-}
-
 static UniquePtr<LookupCacheV4>
 SetupLookupCacheV4(const _PrefixArray& prefixArray)
 {
   nsCOMPtr<nsIFile> file;
   NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
 
   file->AppendNative(GTEST_SAFEBROWSING_DIR);
 

--- a/toolkit/components/url-classifier/tests/gtest/moz.build
+++ b/toolkit/components/url-classifier/tests/gtest/moz.build
@@ -6,16 +6,17 @@
 
 LOCAL_INCLUDES += [
     '../..',
 ]
 
 UNIFIED_SOURCES += [
     'Common.cpp',
     'TestChunkSet.cpp',
+    'TestClassifier.cpp',
     'TestFailUpdate.cpp',
     'TestFindFullHash.cpp',
     'TestLookupCacheV4.cpp',
     'TestPerProviderDirectory.cpp',
     'TestProtocolParser.cpp',
     'TestRiceDeltaDecoder.cpp',
     'TestSafebrowsingHash.cpp',
     'TestSafeBrowsingProtobuf.cpp',