diff --git a/tests-integrated/test-validator.cpp b/tests-integrated/test-validator.cpp
index 9364811..308bc77 100644
--- a/tests-integrated/test-validator.cpp
+++ b/tests-integrated/test-validator.cpp
@@ -1,7 +1,8 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  University of Memphis,
- *                     Regents of the University of California
+ * Copyright (c) 2014-2015,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
  *
  * This file is part of NLSR (Named-data Link State Routing).
  * See AUTHORS.md for complete list of NLSR authors and contributors.
@@ -16,17 +17,17 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Yingdi Yu <yingdi@cs.ucla.edu>
- *
  **/
 
 #include "validator.hpp"
-#include <ndn-cxx/util/scheduler.hpp>
-#include <ndn-cxx/security/key-chain.hpp>
+
 #include <ndn-cxx/security/certificate-cache-ttl.hpp>
+#include <ndn-cxx/security/key-chain.hpp>
+#include <ndn-cxx/util/scheduler.hpp>
+
 #include "boost-test.hpp"
 #include "common.hpp"
+#include "security/certificate-store.hpp"
 
 namespace nlsr {
 
@@ -39,12 +40,13 @@
   ValidatorFixture()
     : m_face2(m_face.getIoService())
     , m_scheduler(m_face.getIoService())
+    , m_keyPrefix("/ndn/broadcast/KEYS")
     , m_certificateCache(new ndn::CertificateCacheTtl(m_face.getIoService()))
-    , m_validator(m_face2, ndn::Name("/ndn/broadcast"), m_certificateCache)
+    , m_validator(m_face2, ndn::Name("/ndn/broadcast"), m_certificateCache, m_certStore)
     , m_identity("/TestValidator/NLSR")
+    , m_wasValidated(false)
   {
-    ndn::Name keyPrefix("/ndn/broadcast/KEYS");
-    m_face.setInterestFilter(keyPrefix,
+    m_face.setInterestFilter(m_keyPrefix,
                              ndn::bind(&ValidatorFixture::onKeyInterest, this, _1, _2),
                              ndn::bind(&ValidatorFixture::onKeyPrefixRegSuccess, this, _1),
                              ndn::bind(&ValidatorFixture::registrationFailed, this, _1, _2));
@@ -89,7 +91,7 @@
       "  filter\n"
       "  {\n"
       "    type name\n"
-      "    regex ^<TestValidator><NLSR><KEY><ksk-.*><><>$\n"
+      "    regex ^<TestValidator>([^<KEY><NLSR>]*)<NLSR><KEY><ksk-.*><><>$\n"
       "  }\n"
       "  checker\n"
       "  {\n"
@@ -135,11 +137,11 @@
     if (certName != m_cert->getName().getPrefix(-1))
       return; //No such a cert
 
-    ndn::Data data(interestName);
-    data.setContent(m_cert->wireEncode());
-    m_keyChain.signWithSha256(data);
+    shared_ptr<ndn::Data> data = make_shared<ndn::Data>(interestName);
+    data->setContent(m_cert->wireEncode());
+    m_keyChain.signWithSha256(*data);
 
-    m_face.put(data);
+    m_face.put(*data);
   }
 
   void
@@ -158,7 +160,7 @@
   void
   onValidated(const ndn::shared_ptr<const ndn::Data>& data)
   {
-    BOOST_CHECK(true);
+    m_wasValidated = true;
   }
 
   void
@@ -166,7 +168,7 @@
                      const std::string& failureInfo)
   {
     std::cerr << "Failure Info: " << failureInfo << std::endl;
-    BOOST_CHECK(false);
+    m_wasValidated = false;
   }
 
   void
@@ -187,12 +189,16 @@
   ndn::Face m_face;
   ndn::Face m_face2;
   ndn::Scheduler m_scheduler;
+  const ndn::Name m_keyPrefix;
   ndn::shared_ptr<ndn::CertificateCacheTtl> m_certificateCache;
+  security::CertificateStore m_certStore;
   nlsr::Validator m_validator;
 
   ndn::KeyChain m_keyChain;
   ndn::Name m_identity;
   ndn::shared_ptr<ndn::IdentityCertificate> m_cert;
+
+  bool m_wasValidated;
 };
 
 BOOST_FIXTURE_TEST_CASE(InfoCertFetch, ValidatorFixture)
@@ -207,6 +213,58 @@
   m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
                             ndn::bind(&ValidatorFixture::terminate, this));
   BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+
+  BOOST_CHECK(m_wasValidated);
+}
+
+BOOST_FIXTURE_TEST_CASE(CertificateStorage, ValidatorFixture)
+{
+  std::vector<ndn::CertificateSubjectDescription> subjectDescription;
+
+  // Create an operator identity
+  ndn::Name opIdentity("/TestValidator/operator/NLSR");
+  m_keyChain.createIdentity(opIdentity);
+
+  // Create an operator cert signed by the trust anchor
+  ndn::Name keyName = m_keyChain.generateRsaKeyPairAsDefault(opIdentity, true);
+  shared_ptr<ndn::IdentityCertificate> opCert =
+    m_keyChain.prepareUnsignedIdentityCertificate(keyName,
+                                                  m_identity,
+                                                  ndn::time::system_clock::now(),
+                                                  ndn::time::system_clock::now()
+                                                    + ndn::time::days(1),
+                                                  subjectDescription);
+  m_keyChain.signByIdentity(*opCert, m_identity);
+  m_keyChain.addCertificateAsIdentityDefault(*opCert);
+
+  // Sign data with operator cert
+  ndn::Name dataName = opIdentity;
+  dataName.append("INFO").append("neighbor").append("version");
+  ndn::shared_ptr<ndn::Data> data = ndn::make_shared<ndn::Data>(dataName);
+  m_keyChain.signByIdentity(*data, opIdentity);
+
+  // Check without cert in CertificateStore
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(200),
+                            ndn::bind(&ValidatorFixture::validate, this, data));
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
+                            ndn::bind(&ValidatorFixture::terminate, this));
+
+  BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+  BOOST_CHECK_EQUAL(m_wasValidated, false);
+
+  // Check with cert in CertificateStore
+  m_certStore.insert(opCert);
+
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(200),
+                            ndn::bind(&ValidatorFixture::validate, this, data));
+  m_scheduler.scheduleEvent(ndn::time::milliseconds(1000),
+                            ndn::bind(&ValidatorFixture::terminate, this));
+
+  BOOST_REQUIRE_NO_THROW(m_face.processEvents());
+  BOOST_CHECK(m_wasValidated);
+
+  // Cleanup
+  m_keyChain.deleteIdentity(opIdentity);
 }
 
 BOOST_AUTO_TEST_SUITE_END()