security: Add Validator

Change-Id: Ib97bbb1a95f43684f14f02d0e50b1b6b6f93979b
diff --git a/log4cxx.properties b/log4cxx.properties
index 6252595..9a76448 100644
--- a/log4cxx.properties
+++ b/log4cxx.properties
@@ -12,7 +12,7 @@
 log4j.appender.A1.layout.ConversionPattern=%d{ss,SSS}  %-12c  %m%n
 
 log4j.logger.SyncLogic = TRACE
-log4j.logger.SyncPolicyManager = DEBUG
+log4j.logger.SyncValidator = DEBUG
 #log4j.logger.SyncInterestTable = TRACE
 #log4j.logger.AppDataFetch = TRACE
 log4j.logger.Test = TRACE
diff --git a/src/sync-intro-certificate.h b/src/sync-intro-certificate.h
new file mode 100644
index 0000000..48dae45
--- /dev/null
+++ b/src/sync-intro-certificate.h
@@ -0,0 +1,154 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Yingdi Yu
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_INTRO_CERTIFICATE_H
+#define SYNC_INTRO_CERTIFICATE_H
+
+#include <ndn-cpp-dev/security/identity-certificate.hpp>
+#include <ndn-cpp-dev/security/signature-sha256-with-rsa.hpp>
+
+namespace Sync {
+
+class IntroCertificate : public ndn::Data
+{
+public:
+  struct Error : public ndn::Data::Error { Error(const std::string &what) : ndn::Data::Error(what) {} };
+
+  IntroCertificate()
+  {}
+  
+  /**
+   * @brief Construct IntroCertificate from IdentityCertificate
+   *
+   * @param syncPrefix
+   * @param introduceeCert
+   * @param introducerName
+   */
+  IntroCertificate(const ndn::Name& syncPrefix,
+                   const ndn::IdentityCertificate& introduceeCert,
+                   const ndn::Name& introducerName); //without version number
+
+  /**
+   * @brief Construct IntroCertificate using a plain data.
+   * 
+   * if data is not actually IntroCertificate, Error will be thrown out.
+   *
+   * @param data
+   * @throws ndn::IntroCertificate::Error.
+   */
+  IntroCertificate(const ndn::Data& data);
+
+  virtual
+  ~IntroCertificate() {};
+
+  const ndn::IdentityCertificate&
+  getIntroduceeCert() const
+  {
+    return m_introduceeCert;
+  }
+
+  const ndn::Name&
+  getIntroducerName() const
+  {
+    return m_introducerName;
+  }
+
+  const ndn::Name&
+  getIntroduceeName() const
+  {
+    return m_introduceeName;
+  }
+
+private:
+  ndn::Name m_syncPrefix;
+  ndn::IdentityCertificate m_introduceeCert;
+  ndn::Name m_introducerName;
+  ndn::Name m_introduceeName;
+};
+
+inline
+IntroCertificate::IntroCertificate(const ndn::Name& syncPrefix,
+                                   const ndn::IdentityCertificate& introduceeCert,
+                                   const ndn::Name& introducerName)
+  : m_syncPrefix(syncPrefix)
+  , m_introduceeCert(introduceeCert)
+  , m_introducerName(introducerName)
+  , m_introduceeName(introduceeCert.getName().getPrefix(-1))
+{
+  // Naming convention /<sync_prefix>/intro-cert/introducee_certname/introducer_certname/version/
+  ndn::Name dataName = m_syncPrefix;
+  dataName.append("intro-cert").append(introduceeCert.getName().getPrefix(-1).wireEncode()).append(introducerName.wireEncode()).appendVersion();
+  
+  setName(dataName);
+  setContent(introduceeCert.wireEncode());
+}
+
+inline
+IntroCertificate::IntroCertificate(const ndn::Data& data)
+  : Data(data)
+{
+  ndn::Name dataName = data.getName();
+  ndn::Name introduceeCertName;
+  ndn::Name introducerName;
+
+  if(dataName.size() < 4 || dataName.get(-4).toEscapedString() != "intro-cert")
+    throw Error("Not a Sync::IntroCertificate");
+
+  m_syncPrefix = dataName.getPrefix(-4);
+
+  try
+    {
+      m_introduceeCert.wireDecode(data.getContent().blockFromValue());
+      m_introducerName.wireDecode(dataName.get(-2).blockFromValue());
+      introduceeCertName.wireDecode(dataName.get(-3).blockFromValue());
+    }
+  catch(ndn::IdentityCertificate::Error& e)
+    {
+      throw Error("Cannot decode introducee cert");
+    }
+  catch(ndn::Name::Error& e)
+    {
+      throw Error("Cannot decode name");
+    }
+  catch(ndn::Block::Error& e)
+    {
+      throw Error("Cannot decode block name");
+    }
+
+  if(introduceeCertName != m_introduceeCert.getName().getPrefix(-1))
+    throw Error("Invalid Sync::IntroCertificate (inconsistent introducee name)");
+
+  m_introduceeName = introduceeCertName;
+
+  try
+    {
+      ndn::SignatureSha256WithRsa sig(data.getSignature());
+      introducerName = sig.getKeyLocator().getName();
+    }
+  catch(ndn::KeyLocator::Error& e)
+    {
+      throw Error("Invalid Sync::IntroCertificate (inconsistent introducer name#1)");
+    }
+  catch(ndn::SignatureSha256WithRsa::Error& e)
+    {
+      throw Error("Invalid Sync::IntroCertificate (inconsistent introducer name#2)");
+    }
+
+  if(m_introducerName != introducerName)
+    throw Error("Invalid Sync::IntroCertificate (inconsistent introducer name#3)");
+
+  if(m_introducerName != introducerName)
+    throw Error("Invalid Sync::IntroCertificate (inconsistent introducer name#3)");
+}
+
+
+} // namespace Sync
+
+#endif //SYNC_INTRO_CERTIFICATE_H
diff --git a/src/sync-logic.cc b/src/sync-logic.cc
index ec4d63e..5bbd83c 100644
--- a/src/sync-logic.cc
+++ b/src/sync-logic.cc
@@ -58,6 +58,7 @@
 int SyncLogic::m_instanceCounter = 0;
 
 SyncLogic::SyncLogic (const Name& syncPrefix,
+                      const Name& identity,
                       shared_ptr<Validator> validator, 
                       shared_ptr<Face> face,
                       LogicUpdateCallback onUpdate,
@@ -65,6 +66,7 @@
   : m_state (new FullState)
   , m_syncInterestTable (*face->ioService(), time::seconds(m_syncInterestReexpress))
   , m_syncPrefix (syncPrefix)
+  , m_identity (identity)
   , m_onUpdate (onUpdate)
   , m_onRemove (onRemove)
   , m_perBranch (false)
@@ -89,12 +91,14 @@
 }
 
 SyncLogic::SyncLogic (const Name& syncPrefix,
+                      const Name& identity,
                       shared_ptr<Validator> validator,
                       shared_ptr<Face> face,
                       LogicPerBranchCallback onUpdateBranch)
   : m_state (new FullState)
   , m_syncInterestTable (*face->ioService(), time::seconds (m_syncInterestReexpress))
   , m_syncPrefix (syncPrefix)
+  , m_identity (identity)
   , m_onUpdateBranch (onUpdateBranch)
   , m_perBranch(true)
   , m_validator(validator)
@@ -164,6 +168,10 @@
     {
       _LOG_DEBUG_ID ("<< I " << name);
 
+      if(name.get(m_syncPrefix.size()).toEscapedString() == "intro-cert")
+        // it is a certificate, validator will take care of it.
+        return;
+
       DigestConstPtr digest;
       string type;
       tie (digest, type) = convertNameToDigestAndType (name);
@@ -636,7 +644,7 @@
   syncData.setContent(reinterpret_cast<const uint8_t*>(wireData), size);
   syncData.setFreshnessPeriod(m_syncResponseFreshness);
   
-  m_keyChain->sign(syncData);
+  m_keyChain->signByIdentity(syncData, m_identity);
   
   m_face->put(syncData);
   
diff --git a/src/sync-logic.h b/src/sync-logic.h
index fc63fca..423c8d7 100644
--- a/src/sync-logic.h
+++ b/src/sync-logic.h
@@ -77,12 +77,14 @@
    * the app data when new remote names are learned
    */
   SyncLogic (const ndn::Name& syncPrefix,
+             const ndn::Name& identity,
              ndn::shared_ptr<ndn::Validator> validator,
              ndn::shared_ptr<ndn::Face> face,
              LogicUpdateCallback onUpdate,
              LogicRemoveCallback onRemove);
 
   SyncLogic (const ndn::Name& syncPrefix,
+             const ndn::Name& identity,
              ndn::shared_ptr<ndn::Validator> validator,
              ndn::shared_ptr<ndn::Face> face,
              LogicPerBranchCallback onUpdateBranch);
@@ -182,6 +184,7 @@
   SyncInterestTable m_syncInterestTable;
 
   ndn::Name m_syncPrefix;
+  ndn::Name m_identity;
   LogicUpdateCallback m_onUpdate;
   LogicRemoveCallback m_onRemove;
   LogicPerBranchCallback m_onUpdateBranch;
diff --git a/src/sync-socket.cc b/src/sync-socket.cc
index f590338..b37d657 100644
--- a/src/sync-socket.cc
+++ b/src/sync-socket.cc
@@ -30,17 +30,20 @@
 
 using ndn::shared_ptr;
 
-SyncSocket::SyncSocket (const Name &syncPrefix, 
+SyncSocket::SyncSocket (const Name& syncPrefix,
+                        const Name& identity,
                         shared_ptr<Validator> validator,
                         shared_ptr<Face> face,
                         NewDataCallback dataCallback, 
                         RemoveCallback rmCallback )
   : m_newDataCallback(dataCallback)
+  , m_identity(identity)
   , m_validator(validator)
   , m_keyChain(new KeyChain())
   , m_face(face)
   , m_ioService(face->ioService())
   , m_syncLogic (syncPrefix,
+                 identity,
                  validator,
                  face,
                  bind(&SyncSocket::passCallback, this, _1),
@@ -71,7 +74,7 @@
   dataName.append(boost::lexical_cast<string>(session)).append(boost::lexical_cast<string>(sequence));
   data->setName(dataName);
 
-  m_keyChain->sign(*data);  
+  m_keyChain->signByIdentity(*data, m_identity);
   m_face->put(*data);
 
   SeqNo s(session, sequence + 1);
diff --git a/src/sync-socket.h b/src/sync-socket.h
index ee02ae8..f796fed 100644
--- a/src/sync-socket.h
+++ b/src/sync-socket.h
@@ -56,7 +56,8 @@
    * @param syncPrefix the name prefix for Sync Interest
    * @param dataCallback the callback to process data
    */
-  SyncSocket (const ndn::Name &syncPrefix, 
+  SyncSocket (const ndn::Name& syncPrefix, 
+              const ndn::Name& identity,
               ndn::shared_ptr<ndn::Validator> validator,
               ndn::shared_ptr<ndn::Face> face,
               NewDataCallback dataCallback, 
@@ -116,6 +117,7 @@
   typedef std::map<ndn::Name, SeqNo> SequenceLog;
   NewDataCallback m_newDataCallback;
   SequenceLog m_sequenceLog;
+  ndn::Name m_identity;
   ndn::shared_ptr<ndn::Validator> m_validator;
   ndn::shared_ptr<ndn::KeyChain> m_keyChain;
   ndn::shared_ptr<ndn::Face> m_face;
diff --git a/src/sync-validator.cc b/src/sync-validator.cc
new file mode 100644
index 0000000..03c292b
--- /dev/null
+++ b/src/sync-validator.cc
@@ -0,0 +1,259 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Yingdi Yu
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#include "sync-validator.h"
+#include "sync-logging.h"
+#include <ndn-cpp-dev/security/certificate-cache-ttl.hpp>
+#include <queue>
+
+using namespace ndn;
+using namespace std;
+
+INIT_LOGGER ("SyncValidator");
+
+namespace Sync {
+
+const shared_ptr<CertificateCache> SyncValidator::DefaultCertificateCache = shared_ptr<CertificateCache>();
+const shared_ptr<SecRuleRelative> SyncValidator::DefaultDataRule = shared_ptr<SecRuleRelative>();
+
+SyncValidator::SyncValidator(const Name& prefix,
+                             const IdentityCertificate& anchor,
+                             shared_ptr<Face> face,
+                             shared_ptr<SecRuleRelative> rule,
+                             shared_ptr<CertificateCache> certificateCache, 
+                             const int stepLimit)
+  : Validator(face)
+  , m_prefix(prefix)
+  , m_anchor(anchor)
+  , m_stepLimit(stepLimit)
+  , m_certificateCache(certificateCache)
+  , m_dataRule(rule)
+{
+  if(!static_cast<bool>(face))
+    throw Error("Face is not set!");
+
+  if(!static_cast<bool>(m_certificateCache))
+    m_certificateCache = make_shared<CertificateCacheTtl>(m_face->ioService());
+
+  Name certPrefix = prefix;
+  certPrefix.append("intro-cert");
+  m_prefixId = m_face->setInterestFilter (certPrefix, 
+                                          bind(&SyncValidator::onCertInterest, this, _1, _2), 
+                                          bind(&SyncValidator::onCertRegisterFailed, this, _1, _2));
+
+  setAnchor(m_anchor);
+}
+
+void
+SyncValidator::deriveTrustNodes()
+{
+  queue<Name> nodeQueue;
+
+  // Clear existing trust nodes.
+  m_trustedNodes.clear();
+
+  // Add the trust anchor.
+  IntroNode origin(m_anchor);
+  m_trustedNodes[origin.name()] = m_anchor.getPublicKeyInfo();
+  nodeQueue.push(origin.name());
+
+  // BFS trusted nodes.
+  while(!nodeQueue.empty())
+    {
+      // Get next trusted node to process.
+      Nodes::const_iterator it = m_introNodes.find(nodeQueue.front());
+      const PublicKey& publicKey = m_trustedNodes[nodeQueue.front()];
+
+      if(it != m_introNodes.end())
+        {
+          // If the trusted node exists in the graph.
+          IntroNode::const_iterator eeIt = it->second.introduceeBegin();
+          IntroNode::const_iterator eeEnd = it->second.introduceeEnd();
+          for(; eeIt != eeEnd; eeIt++)
+            {
+              // Check the nodes introduced by the trusted node.
+              Edges::const_iterator edgeIt = m_introCerts.find(*eeIt);
+              if(edgeIt != m_introCerts.end() 
+                 && m_trustedNodes.find(edgeIt->second.getIntroduceeName()) == m_trustedNodes.end()
+                 && verifySignature(edgeIt->second, publicKey))
+                {
+                  // If the introduced node can be validated, add it into trusted node set and the node queue.
+                  m_trustedNodes[edgeIt->second.getIntroduceeName()] = edgeIt->second.getIntroduceeCert().getPublicKeyInfo();
+                  nodeQueue.push(edgeIt->second.getIntroduceeName());
+                }
+            }
+        }
+      nodeQueue.pop();
+    }
+}
+
+void
+SyncValidator::checkPolicy (const Data& data, 
+                            int stepCount, 
+                            const OnDataValidated& onValidated, 
+                            const OnDataValidationFailed& onValidationFailed,
+                            std::vector<shared_ptr<ValidationRequest> >& nextSteps)
+{
+  if(m_stepLimit == stepCount)
+    return onValidationFailed(data.shared_from_this(), 
+                              "Maximum steps of validation reached: " + data.getName().toUri());
+
+  if(m_prefix.isPrefixOf(data.getName()))
+    {
+      try
+        {
+          SignatureSha256WithRsa sig(data.getSignature());
+          Name keyLocatorName = sig.getKeyLocator().getName();
+
+          TrustNodes::const_iterator it = m_trustedNodes.find(keyLocatorName);
+          if(m_trustedNodes.end() != it)
+            {
+              if(verifySignature(data, sig, it->second))
+                return onValidated(data.shared_from_this());
+              else
+                return onValidationFailed(data.shared_from_this(), 
+                                          "Cannot verify signature: " + data.getName().toUri());
+            }
+          else
+            {
+              Name interestName = m_prefix;
+              interestName.append("intro-cert").append(keyLocatorName.wireEncode());
+              Interest interest(interestName);
+              interest.setInterestLifetime(500);
+
+              OnDataValidated onKeyValidated = bind(&SyncValidator::onCertificateValidated, this, 
+                                                    _1, data.shared_from_this(), onValidated, onValidationFailed);
+              
+              OnDataValidationFailed onKeyValidationFailed = bind(&SyncValidator::onCertificateValidationFailed, this, 
+                                                                  _1, _2, data.shared_from_this(), onValidationFailed);              
+
+              shared_ptr<ValidationRequest> nextStep = make_shared<ValidationRequest>(interest, 
+                                                                                      onKeyValidated,
+                                                                                      onKeyValidationFailed,
+                                                                                      1,
+                                                                                      stepCount + 1);
+              nextSteps.push_back(nextStep);
+
+              return;
+            }
+        }
+      catch(SignatureSha256WithRsa::Error& e)
+        {
+          return onValidationFailed(data.shared_from_this(), 
+                                    "Not SignatureSha256WithRsa signature: " + string(e.what()));
+        }
+      catch(KeyLocator::Error& e)
+        {
+          return onValidationFailed(data.shared_from_this(),
+                                    "Key Locator is not a name: " + data.getName().toUri());
+        }
+    }
+
+  if(static_cast<bool>(m_dataRule) && m_dataRule->satisfy(data))
+    {
+      try
+        {
+          SignatureSha256WithRsa sig(data.getSignature());
+          Name keyLocatorName = sig.getKeyLocator().getName();
+          
+          TrustNodes::const_iterator it = m_trustedNodes.find(keyLocatorName);
+          if(m_trustedNodes.end() != it)
+            {
+              if(verifySignature(data, sig, it->second))
+                return onValidated(data.shared_from_this());
+              else
+                return onValidationFailed(data.shared_from_this(), 
+                                          "Cannot verify signature: " + data.getName().toUri());
+            }
+          else
+            return onValidationFailed(data.shared_from_this(), 
+                                      "Signer cannot be trusted: " + keyLocatorName.toUri());
+        }
+      catch(SignatureSha256WithRsa::Error& e)
+        {
+          return onValidationFailed(data.shared_from_this(), 
+                                    "Not SignatureSha256WithRsa signature: " + string(e.what()));
+        }
+      catch(KeyLocator::Error& e)
+        {
+          return onValidationFailed(data.shared_from_this(),
+                                    "Key Locator is not a name: " + data.getName().toUri());
+        }
+    }
+  else
+    return onValidationFailed(data.shared_from_this(),
+                              "No data rule or rule is not satisfied: " + data.getName().toUri());
+}
+
+void
+SyncValidator::checkPolicy (const Interest& interest, 
+                            int stepCount, 
+                            const OnInterestValidated& onValidated, 
+                            const OnInterestValidationFailed& onValidationFailed,
+                            std::vector<shared_ptr<ValidationRequest> >& nextSteps)
+{
+  onValidationFailed(interest.shared_from_this(),  "No policy for signed interest checking");
+}
+
+void
+SyncValidator::onCertificateValidated(const shared_ptr<const Data>& signCertificate, 
+                                      const shared_ptr<const Data>& data, 
+                                      const OnDataValidated& onValidated, 
+                                      const OnDataValidationFailed& onValidationFailed)
+{
+  try
+    {
+      IntroCertificate introCert(*signCertificate);
+      addParticipant(introCert);
+      
+      if(verifySignature(*data, introCert.getIntroduceeCert().getPublicKeyInfo()))
+        return onValidated(data);
+      else
+        return onValidationFailed(data, 
+                                  "Cannot verify signature: " + data->getName().toUri());
+    }
+  catch(IntroCertificate::Error& e)
+    {
+      return onValidationFailed(data, 
+                                "Intro cert decoding error: " + string(e.what()));
+    }
+}
+
+void
+SyncValidator::onCertificateValidationFailed(const shared_ptr<const Data>& signCertificate, 
+                                             const string& failureInfo,
+                                             const shared_ptr<const Data>& data, 
+                                             const OnDataValidationFailed& onValidationFailed)
+{
+  onValidationFailed(data, failureInfo);
+}
+
+void
+SyncValidator::onCertInterest(const Name& prefix, const Interest& interest)
+{
+  Name name = interest.getName(); 
+  Edges::const_iterator it = m_introCerts.begin();
+  for(; it != m_introCerts.end(); it++)
+    {
+      if(name.isPrefixOf(it->first))
+        {
+          m_face->put(it->second);
+          return;
+        }
+    }
+}
+
+void
+SyncValidator::onCertRegisterFailed(const Name& prefix, const string& msg)
+{
+  _LOG_DEBUG("SyncValidator::onCertRegisterFailed: " << msg);
+}
+
+} // namespace Sync
diff --git a/src/sync-validator.h b/src/sync-validator.h
new file mode 100644
index 0000000..b3cff00
--- /dev/null
+++ b/src/sync-validator.h
@@ -0,0 +1,296 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Yingdi Yu
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_VALIDATOR_H
+#define SYNC_VALIDATOR_H
+
+#include "sync-intro-certificate.h"
+#include <ndn-cpp-dev/security/validator.hpp>
+#include <ndn-cpp-dev/security/key-chain.hpp>
+#include <ndn-cpp-dev/security/sec-rule-relative.hpp>
+#include <ndn-cpp-dev/security/certificate-cache.hpp>
+#include <map>
+
+namespace Sync {
+
+class SyncValidator : public ndn::Validator
+{
+public:
+  struct Error : public ndn::Validator::Error { Error(const std::string &what) : ndn::Validator::Error(what) {} };
+
+  static const ndn::shared_ptr<ndn::CertificateCache> DefaultCertificateCache;
+  static const ndn::shared_ptr<ndn::SecRuleRelative> DefaultDataRule;
+
+  SyncValidator(const ndn::Name& prefix,
+                const ndn::IdentityCertificate& anchor,
+                ndn::shared_ptr<ndn::Face> face,
+                ndn::shared_ptr<ndn::SecRuleRelative> rule = DefaultDataRule,
+                ndn::shared_ptr<ndn::CertificateCache> certificateCache = DefaultCertificateCache, 
+                const int stepLimit = 10);
+
+  virtual
+  ~SyncValidator()
+  {
+    m_face->unsetInterestFilter(m_prefixId);
+  }
+
+  /**
+   * @brief Set the trust anchor
+   *
+   * The anchor should be the participant's own certificate.
+   * This anchor node is the origin of the derived trust graph.
+   * Once the new anchor is set, derive the TrustNode set.
+   * 
+   * @param anchor.
+   */
+  inline void
+  setAnchor(const ndn::IdentityCertificate& anchor);
+
+  /**
+   * @brief Add a node into the trust graph.
+   * 
+   * The method also create an edge from trust anchor to the node.
+   *
+   * @param introducee.
+   * @return IntroCertificate for the introducee.
+   */
+  inline ndn::shared_ptr<const IntroCertificate>
+  addParticipant(const ndn::IdentityCertificate& introducee);
+
+  /**
+   * @brief Add an edge into the trust graph.
+   *
+   * Create nodes if it is one of the edge's ends and does not exist in the graph.
+   *
+   * @param introCert.
+   */
+  inline void
+  addParticipant(const IntroCertificate& introCert);
+
+#ifdef _TEST
+  bool
+  canTrust(const ndn::Name& certName)
+  {
+    return (m_trustedNodes.find(certName.getPrefix(-1)) != m_trustedNodes.end());
+  }
+#endif //_DEBUG
+  
+protected:
+  /***********************
+   * From ndn::Validator *
+   ***********************/
+  virtual void
+  checkPolicy (const ndn::Data& data, 
+               int stepCount, 
+               const ndn::OnDataValidated& onValidated, 
+               const ndn::OnDataValidationFailed& onValidationFailed,
+               std::vector<ndn::shared_ptr<ndn::ValidationRequest> >& nextSteps);
+
+  virtual void
+  checkPolicy (const ndn::Interest& interest, 
+               int stepCount, 
+               const ndn::OnInterestValidated& onValidated, 
+               const ndn::OnInterestValidationFailed& onValidationFailed,
+               std::vector<ndn::shared_ptr<ndn::ValidationRequest> >& nextSteps);
+private:
+  void
+  deriveTrustNodes();
+
+  
+  void
+  onCertificateValidated(const ndn::shared_ptr<const ndn::Data>& signCertificate, 
+                         const ndn::shared_ptr<const ndn::Data>& data, 
+                         const ndn::OnDataValidated& onValidated, 
+                         const ndn::OnDataValidationFailed& onValidationFailed);
+  
+  void
+  onCertificateValidationFailed(const ndn::shared_ptr<const ndn::Data>& signCertificate,
+                                const std::string& failureInfo,
+                                const ndn::shared_ptr<const ndn::Data>& data, 
+                                const ndn::OnDataValidationFailed& onValidationFailed);
+
+  void
+  onCertInterest (const ndn::Name& prefix, const ndn::Interest& interest);
+
+  void
+  onCertRegisterFailed(const ndn::Name& prefix, const std::string& msg);
+
+private:
+  class IntroNode;
+
+  // Syncprefix
+  ndn::Name m_prefix;
+  
+  // The map
+  typedef std::map<const ndn::Name, IntroNode> Nodes;
+  typedef std::map<const ndn::Name, IntroCertificate> Edges;
+  Nodes m_introNodes;
+  Edges m_introCerts;
+
+  // The derived trust info
+  typedef std::map<const ndn::Name, ndn::PublicKey> TrustNodes;
+  ndn::IdentityCertificate m_anchor;
+  TrustNodes m_trustedNodes;
+  
+  // others
+  int m_stepLimit;
+  ndn::shared_ptr<ndn::CertificateCache> m_certificateCache;
+  ndn::KeyChain m_keychain;
+  const ndn::RegisteredPrefixId* m_prefixId;
+  ndn::shared_ptr<ndn::SecRuleRelative> m_dataRule;
+
+  class IntroNode
+  {
+  public:
+    typedef std::vector<ndn::Name>::const_iterator const_iterator;
+
+    IntroNode()
+    {}
+
+    IntroNode(const ndn::IdentityCertificate& idCert)
+      : m_nodeName(idCert.getName().getPrefix(-1))
+    {}
+    
+    IntroNode(const IntroCertificate& introCert, bool isIntroducer)
+    {
+      if(isIntroducer)
+        {
+          m_nodeName = introCert.getIntroducerName();
+          m_introduceeCerts.push_back(introCert.getName());
+        }
+      else
+        {
+          m_nodeName = introCert.getIntroduceeName();
+          m_introducerCerts.push_back(introCert.getName());
+        }
+    } 
+    
+    ~IntroNode()
+    {}
+
+    const ndn::Name&
+    name() const
+    {
+      return m_nodeName;
+    }
+
+    const_iterator
+    introducerBegin() const
+    {
+      return m_introducerCerts.begin();
+    }
+
+    const_iterator
+    introducerEnd() const
+    {
+      return m_introducerCerts.end();
+    }
+
+    const_iterator
+    introduceeBegin() const
+    {
+      return m_introduceeCerts.begin();
+    }
+
+    const_iterator
+    introduceeEnd() const
+    {
+      return m_introduceeCerts.end();
+    }
+
+    void
+    addIntroCertAsIntroducer(const ndn::Name& introCertName)
+    {
+      if(std::find(m_introduceeCerts.begin(), m_introduceeCerts.end(), introCertName) == m_introduceeCerts.end())
+        m_introduceeCerts.push_back(introCertName);
+    }
+    
+    void
+    addIntroCertAsIntroducee(const ndn::Name& introCertName)
+    {
+      if(std::find(m_introducerCerts.begin(), m_introducerCerts.end(), introCertName) == m_introducerCerts.end())
+        m_introducerCerts.push_back(introCertName);
+    }
+  
+  private:
+    ndn::Name m_nodeName;
+    std::vector<ndn::Name> m_introducerCerts;
+    std::vector<ndn::Name> m_introduceeCerts;
+  };
+
+};
+
+inline void
+SyncValidator::setAnchor(const ndn::IdentityCertificate& anchor)
+{
+  m_anchor = anchor;
+  
+  // Add anchor into trust graph if it does not exist.
+  IntroNode origin(m_anchor);
+  Nodes::const_iterator nodeIt = m_introNodes.find(origin.name());
+  if(nodeIt == m_introNodes.end())
+    m_introNodes[origin.name()] = origin;
+
+  deriveTrustNodes();
+}
+
+inline void
+SyncValidator::addParticipant(const IntroCertificate& introCert)
+{
+  // Check if the edge has been added before.
+  ndn::Name certName = introCert.getName();
+  Edges::const_iterator edgeIt = m_introCerts.find(certName);
+  if(edgeIt != m_introCerts.end())
+    return; // the edge has been added before.
+
+  m_introCerts[certName] = introCert;
+
+  // Check if the introducer has been added.
+  Nodes::iterator nodeIt = m_introNodes.find(introCert.getIntroducerName());
+  if(nodeIt == m_introNodes.end())
+    {
+      IntroNode node(introCert, true);
+      m_introNodes[node.name()] = node;
+    }
+  else
+    nodeIt->second.addIntroCertAsIntroducer(certName);
+
+  // Check if the introducee has been added.
+  nodeIt = m_introNodes.find(introCert.getIntroduceeName());
+  if(nodeIt == m_introNodes.end())
+    {
+      IntroNode node(introCert, false);
+      m_introNodes[node.name()] = node;
+    }
+  else
+    nodeIt->second.addIntroCertAsIntroducee(certName);
+
+  // Check if the introducer is one of the trusted nodes.
+  TrustNodes::const_iterator trustNodeIt = m_trustedNodes.find(introCert.getIntroducerName());
+  if(trustNodeIt != m_trustedNodes.end() && verifySignature(introCert, trustNodeIt->second))
+    // If the introducee, add it into trusted node set.
+    m_trustedNodes[introCert.getIntroduceeName()] = introCert.getIntroduceeCert().getPublicKeyInfo();
+}
+
+inline ndn::shared_ptr<const IntroCertificate>
+SyncValidator::addParticipant(const ndn::IdentityCertificate& introducee)
+{
+  ndn::shared_ptr<IntroCertificate> introCert = ndn::make_shared<IntroCertificate>(m_prefix, introducee, m_anchor.getName().getPrefix(-1));
+
+  m_keychain.sign(*introCert, m_anchor.getName());
+  
+  addParticipant(*introCert);
+
+  return introCert;
+}
+
+} // namespace Sync
+
+#endif //SYNC_VALIDATOR_H
diff --git a/tests/test_data_fetch_and_publish.cc b/tests/test-data-fetch-and-publish.cc
similarity index 100%
rename from tests/test_data_fetch_and_publish.cc
rename to tests/test-data-fetch-and-publish.cc
diff --git a/tests/test_digest.cc b/tests/test-digest.cc
similarity index 100%
rename from tests/test_digest.cc
rename to tests/test-digest.cc
diff --git a/tests/test_interest_table.cc b/tests/test-interest-table.cc
similarity index 100%
rename from tests/test_interest_table.cc
rename to tests/test-interest-table.cc
diff --git a/tests/test_leaf.cc b/tests/test-leaf.cc
similarity index 100%
rename from tests/test_leaf.cc
rename to tests/test-leaf.cc
diff --git a/tests/test_pit.cc b/tests/test-pit.cc
similarity index 100%
rename from tests/test_pit.cc
rename to tests/test-pit.cc
diff --git a/tests/test_scheduler.cc.tmp b/tests/test-scheduler.cc.tmp
similarity index 100%
rename from tests/test_scheduler.cc.tmp
rename to tests/test-scheduler.cc.tmp
diff --git a/tests/test_socket.cc b/tests/test-socket.cc
similarity index 78%
rename from tests/test_socket.cc
rename to tests/test-socket.cc
index 60a87f3..e4791c2 100644
--- a/tests/test_socket.cc
+++ b/tests/test-socket.cc
@@ -29,6 +29,7 @@
 
 #include "sync-logging.h"
 #include "sync-socket.h"
+#include "sync-validator.h"
 #include <ndn-cpp-dev/security/validator-null.hpp>
 
 extern "C" {
@@ -138,21 +139,48 @@
 class TestSet1{
 public:
   TestSet1(ndn::shared_ptr<boost::asio::io_service> ioService)
-    : m_validator(new ndn::ValidatorNull())
-    , m_face1(new ndn::Face(ioService))
+    : m_face1(new ndn::Face(ioService))
     , m_face2(new ndn::Face(ioService))
     , m_face3(new ndn::Face(ioService))
     , m_p1("/irl.cs.ucla.edu")
     , m_p2("/yakshi.org")
     , m_p3("/google.com")
     , m_syncPrefix("/let/us/sync")
-  {}
+  {
+    ndn::KeyChain keyChain;
+    m_name1 = m_p1;
+    m_name1.append(boost::lexical_cast<std::string>(ndn::time::now()));
+    ndn::Name certName1 = keyChain.createIdentity(m_name1);
+    m_id1 = keyChain.getCertificate(certName1);
+
+    m_name2 = m_p2;
+    m_name2.append(boost::lexical_cast<std::string>(ndn::time::now()));
+    ndn::Name certName2 = keyChain.createIdentity(m_name2);
+    m_id2 = keyChain.getCertificate(certName2);
+
+    m_name3 = m_p3;
+    m_name3.append(boost::lexical_cast<std::string>(ndn::time::now()));
+    ndn::Name certName3 = keyChain.createIdentity(m_name3);
+    m_id3 = keyChain.getCertificate(certName3);
+
+    ndn::shared_ptr<ndn::SecRuleRelative> rule = ndn::make_shared<ndn::SecRuleRelative>("^(<>*)<><>$",
+                                                                                        "^(<>*)<><KEY><ksk-.*><ID-CERT>$",
+                                                                                        "==", "\\1", "\\1", true);
+
+    m_v1 = ndn::make_shared<SyncValidator>(m_syncPrefix, *m_id1, m_face1, rule);
+    m_v1->addParticipant(*m_id2);
+    m_v2 = ndn::make_shared<SyncValidator>(m_syncPrefix, *m_id2, m_face2, rule);
+    m_v2->addParticipant(*m_id1);
+    m_v2->addParticipant(*m_id3);
+    m_v3 = ndn::make_shared<SyncValidator>(m_syncPrefix, *m_id3, m_face3, rule);
+    m_v3->addParticipant(*m_id2);
+  }
 
   void
   createSyncSocket1()
   {
     _LOG_DEBUG ("s1");
-    m_s1 = make_shared<SyncSocket>(m_syncPrefix, m_validator, m_face1, 
+    m_s1 = ndn::make_shared<SyncSocket>(m_syncPrefix, m_name1, m_v1, m_face1, 
                                    bind(&TestSocketApp::fetchAll, &m_a1, _1, _2), 
                                    bind(&TestSocketApp::pass, &m_a1, _1));
   }
@@ -161,7 +189,7 @@
   createSyncSocket2()
   {
     _LOG_DEBUG ("s2");
-    m_s2 = make_shared<SyncSocket>(m_syncPrefix, m_validator, m_face2, 
+    m_s2 = ndn::make_shared<SyncSocket>(m_syncPrefix, m_name2, m_v2, m_face2, 
                                    bind(&TestSocketApp::fetchAll, &m_a2, _1, _2), 
                                    bind(&TestSocketApp::pass, &m_a2, _1));
   }
@@ -170,7 +198,7 @@
   createSyncSocket3()
   {
     _LOG_DEBUG ("s3");
-    m_s3 = make_shared<SyncSocket>(m_syncPrefix, m_validator, m_face3, 
+    m_s3 = ndn::make_shared<SyncSocket>(m_syncPrefix, m_name3, m_v3, m_face3, 
                                    bind(&TestSocketApp::fetchAll, &m_a3, _1, _2), 
                                    bind(&TestSocketApp::pass, &m_a3, _1));
   }
@@ -236,12 +264,23 @@
     m_s1.reset();
     m_s2.reset();
     m_s3.reset();
+    m_v1.reset();
+    m_v2.reset();
+    m_v3.reset();
+
+    ndn::KeyChain keyChain;
+    keyChain.deleteIdentity(m_name1);
+    keyChain.deleteIdentity(m_name2);
+    keyChain.deleteIdentity(m_name3);
+
   }
 
 
   TestSocketApp m_a1, m_a2, m_a3;
-  ndn::shared_ptr<ndn::ValidatorNull> m_validator;
+  ndn::shared_ptr<ndn::IdentityCertificate> m_id1, m_id2, m_id3;
+  ndn::shared_ptr<Sync::SyncValidator> m_v1, m_v2, m_v3;
   ndn::shared_ptr<ndn::Face> m_face1, m_face2, m_face3;
+  ndn::Name m_name1, m_name2, m_name3;
   ndn::Name m_p1, m_p2, m_p3;
   ndn::shared_ptr<SyncSocket> m_s1, m_s2, m_s3;
   ndn::Name m_syncPrefix;
@@ -250,19 +289,39 @@
 class TestSet2{
 public:
   TestSet2(ndn::shared_ptr<boost::asio::io_service> ioService)
-    : m_validator(new ndn::ValidatorNull())
-    , m_face1(new ndn::Face(ioService))
+    : m_face1(new ndn::Face(ioService))
     , m_face2(new ndn::Face(ioService))
     , m_p1("/xiaonei.com")
     , m_p2("/mitbbs.com")
     , m_syncPrefix("/this/is/the/prefix")
-  {}
+  {
+    ndn::KeyChain keyChain;
+    m_name1 = m_p1;
+    m_name1.append(boost::lexical_cast<string>(ndn::time::now()));
+    ndn::Name certName1 = keyChain.createIdentity(m_name1);
+    m_id1 = keyChain.getCertificate(certName1);
+
+    m_name2 = m_p2;
+    m_name2.append(boost::lexical_cast<string>(ndn::time::now()));
+    ndn::Name certName2 = keyChain.createIdentity(m_name2);
+    m_id2 = keyChain.getCertificate(certName2);
+
+    ndn::shared_ptr<ndn::SecRuleRelative> rule = ndn::make_shared<ndn::SecRuleRelative>("^(<>*)<><>$",
+                                                                                        "^(<>*)<><KEY><ksk-.*><ID-CERT>$",
+                                                                                        "==", "\\1", "\\1", true);
+
+    m_v1 = ndn::make_shared<SyncValidator>(m_syncPrefix, *m_id1, m_face1, rule);
+    m_v1->addParticipant(*m_id2);
+    m_v2 = ndn::make_shared<SyncValidator>(m_syncPrefix, *m_id2, m_face2, rule);
+    m_v2->addParticipant(*m_id1);
+
+  }
 
   void
   createSyncSocket1()
   {
     _LOG_DEBUG ("s1");
-    m_s1 = make_shared<SyncSocket>(m_syncPrefix, m_validator, m_face1, 
+    m_s1 = ndn::make_shared<SyncSocket>(m_syncPrefix, m_name1, m_v1, m_face1, 
                                    bind(&TestSocketApp::fetchNumbers, &m_a1, _1, _2), 
                                    bind(&TestSocketApp::pass, &m_a1, _1));
   }
@@ -271,7 +330,7 @@
   createSyncSocket2()
   {
     _LOG_DEBUG ("s2");
-    m_s2 = make_shared<SyncSocket>(m_syncPrefix, m_validator, m_face2, 
+    m_s2 = ndn::make_shared<SyncSocket>(m_syncPrefix, m_name2, m_v2, m_face2, 
                                    bind(&TestSocketApp::fetchNumbers, &m_a2, _1, _2), 
                                    bind(&TestSocketApp::pass, &m_a2, _1));
   }
@@ -319,12 +378,20 @@
   {
     m_s1.reset();
     m_s2.reset();
+    m_v1.reset();
+    m_v2.reset();
+
+    ndn::KeyChain keyChain;
+    keyChain.deleteIdentity(m_name1);
+    keyChain.deleteIdentity(m_name2);
   }
 
   TestSocketApp m_a1, m_a2;
-  ndn::shared_ptr<ndn::ValidatorNull> m_validator;
+  ndn::shared_ptr<ndn::IdentityCertificate> m_id1, m_id2;
+  ndn::shared_ptr<Sync::SyncValidator> m_v1, m_v2;
   ndn::shared_ptr<ndn::Face> m_face1, m_face2;
   ndn::Name m_p1, m_p2;
+  ndn::Name m_name1, m_name2;
   ndn::shared_ptr<SyncSocket> m_s1, m_s2;
   ndn::Name m_syncPrefix;
 };
diff --git a/tests/test_state.cc.outdated b/tests/test-state.cc.outdated
similarity index 100%
rename from tests/test_state.cc.outdated
rename to tests/test-state.cc.outdated
diff --git a/tests/test_sync_logic.cc b/tests/test-sync-logic.cc
similarity index 96%
rename from tests/test_sync_logic.cc
rename to tests/test-sync-logic.cc
index d2444e7..76c5fc5 100644
--- a/tests/test_sync_logic.cc
+++ b/tests/test-sync-logic.cc
@@ -101,8 +101,11 @@
   createSyncLogic(int index, 
                   ndn::shared_ptr<Handler> h)
   { 
+    ndn::Name identity("/tmp-" + boost::lexical_cast<std::string>(ndn::time::now()));
+    m_keyChain.createIdentity(identity);
     m_faces[index] = ndn::make_shared<ndn::Face>(m_ioService);
     m_l[index] = new SyncLogic(ndn::Name("/bcast"), 
+                               identity,
                                m_validator, m_faces[index], 
                                bind (&Handler::wrapper, &*h, _1), 
                                bind (&Handler::onRemove, &*h, _1)); 
@@ -140,6 +143,7 @@
 
 
 public:
+  ndn::KeyChain m_keyChain;
   ndn::shared_ptr<boost::asio::io_service> m_ioService;
   SyncLogic* m_l[2];
   ndn::shared_ptr<ndn::Face> m_faces[2];
diff --git a/tests/test-sync-validator.cc b/tests/test-sync-validator.cc
new file mode 100644
index 0000000..ca7078b
--- /dev/null
+++ b/tests/test-sync-validator.cc
@@ -0,0 +1,249 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ */
+
+#include <boost/test/unit_test.hpp>
+#include "sync-validator.h"
+
+BOOST_AUTO_TEST_SUITE(TestSyncValidator)
+
+void onValidated(const ndn::shared_ptr<const ndn::Data>& data)
+{
+  BOOST_CHECK(true);
+}
+
+void onValidationFailed(const ndn::shared_ptr<const ndn::Data>& data,
+			const std::string& failureInfo)
+{
+  BOOST_CHECK(false);
+}
+
+void onValidated2(const ndn::shared_ptr<const ndn::Data>& data)
+{
+  BOOST_CHECK(false);
+}
+
+void onValidationFailed2(const ndn::shared_ptr<const ndn::Data>& data,
+			const std::string& failureInfo)
+{
+  BOOST_CHECK(true);
+}
+
+BOOST_AUTO_TEST_CASE (Graph)
+{
+  using namespace Sync;
+  using namespace ndn;
+
+  Name prefix("/Sync/TestSyncValidator/AddEdge");
+  KeyChain keychain;
+
+  Name identity1("/TestSyncValidator/AddEdge-1/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName1 = keychain.createIdentity(identity1);
+  shared_ptr<IdentityCertificate> anchor = keychain.getCertificate(certName1);
+
+  Name identity2("/TestSyncValidator/AddEdge-2/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName2 = keychain.createIdentity(identity2);
+  shared_ptr<IdentityCertificate> introducer = keychain.getCertificate(certName2);
+
+  Name identity3("/TestSyncValidator/AddEdge-3/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName3 = keychain.createIdentity(identity3);
+  shared_ptr<IdentityCertificate> introducee = keychain.getCertificate(certName3);
+
+  Name identity4("/TestSyncValidator/AddEdge-4/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName4 = keychain.createIdentity(identity4);
+  shared_ptr<IdentityCertificate> introducer2 = keychain.getCertificate(certName4);
+
+  Name identity5("/TestSyncValidator/AddEdge-5/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName5 = keychain.createIdentity(identity5);
+  shared_ptr<IdentityCertificate> introducee2 = keychain.getCertificate(certName5);
+
+  shared_ptr<boost::asio::io_service> ioService = make_shared<boost::asio::io_service>();
+  shared_ptr<Face> face = make_shared<Face>(ioService);
+  SyncValidator validator(prefix, *anchor, face);
+
+  validator.addParticipant(*introducer);
+  BOOST_CHECK(validator.canTrust(certName2));
+  
+  IntroCertificate introCert(prefix, *introducee, certName2.getPrefix(-1));
+  keychain.sign(introCert, certName2);
+  validator.addParticipant(introCert);
+  BOOST_CHECK(validator.canTrust(certName3));
+
+  IntroCertificate introCert1(prefix, *anchor, certName3.getPrefix(-1));
+  keychain.sign(introCert1, certName3);
+  validator.addParticipant(introCert1);
+  validator.setAnchor(*introducer);
+  BOOST_CHECK(validator.canTrust(certName2));
+  BOOST_CHECK(validator.canTrust(certName3));
+  BOOST_CHECK(validator.canTrust(certName1));
+
+  IntroCertificate introCert2(prefix, *introducee2, certName4.getPrefix(-1));
+  keychain.sign(introCert2, certName4);
+  validator.addParticipant(introCert2);
+  BOOST_CHECK(validator.canTrust(certName5) == false);
+  BOOST_CHECK(validator.canTrust(certName4) == false);
+
+  IntroCertificate introCert3(prefix, *introducee, certName5.getPrefix(-1));
+  keychain.sign(introCert3, certName5);
+  validator.addParticipant(introCert3);
+  BOOST_CHECK(validator.canTrust(certName5) == false);
+  BOOST_CHECK(validator.canTrust(certName4) == false);
+
+  validator.setAnchor(*introducee2);
+  BOOST_CHECK(validator.canTrust(certName1));
+  BOOST_CHECK(validator.canTrust(certName2));
+  BOOST_CHECK(validator.canTrust(certName3));
+  BOOST_CHECK(validator.canTrust(certName4) == false);
+  BOOST_CHECK(validator.canTrust(certName5));
+  
+
+  keychain.deleteIdentity(identity1);
+  keychain.deleteIdentity(identity2);
+  keychain.deleteIdentity(identity3);
+  keychain.deleteIdentity(identity4);
+  keychain.deleteIdentity(identity5);
+}
+
+BOOST_AUTO_TEST_CASE (OfflineValidate)
+{
+  using namespace Sync;
+  using namespace ndn;
+
+  Name prefix("/Sync/TestSyncValidator/OfflineValidate");
+  KeyChain keychain;
+
+  Name identity1("/TestSyncValidator/OfflineValidate-1/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName1 = keychain.createIdentity(identity1);
+  shared_ptr<IdentityCertificate> anchor = keychain.getCertificate(certName1);
+
+  Name identity2("/TestSyncValidator/OfflineValidate-2/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName2 = keychain.createIdentity(identity2);
+  shared_ptr<IdentityCertificate> introducer = keychain.getCertificate(certName2);
+
+  Name identity3("/TestSyncValidator/OfflineValidate-3/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName3 = keychain.createIdentity(identity3);
+  shared_ptr<IdentityCertificate> introducee = keychain.getCertificate(certName3);
+
+  Name identity4("/TestSyncValidator/OfflineValidate-4/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName4 = keychain.createIdentity(identity4);
+  shared_ptr<IdentityCertificate> introducer2 = keychain.getCertificate(certName4);
+
+  Name identity5("/TestSyncValidator/OfflineValidate-5/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName5 = keychain.createIdentity(identity5);
+  shared_ptr<IdentityCertificate> introducee2 = keychain.getCertificate(certName5);
+
+  shared_ptr<boost::asio::io_service> ioService = make_shared<boost::asio::io_service>();
+  shared_ptr<Face> face = make_shared<Face>(ioService);
+  SyncValidator validator(prefix, *anchor, face);
+
+  validator.addParticipant(*introducer);
+  BOOST_CHECK(validator.canTrust(certName2));
+  
+  IntroCertificate introCert(prefix, *introducee, certName2.getPrefix(-1));
+  keychain.sign(introCert, certName2);
+  validator.addParticipant(introCert);
+  BOOST_CHECK(validator.canTrust(certName3));
+
+  IntroCertificate introCert2(prefix, *introducee2, certName4.getPrefix(-1));
+  keychain.sign(introCert2, certName4);
+  validator.addParticipant(introCert2);
+  BOOST_CHECK(validator.canTrust(certName5) == false);
+  BOOST_CHECK(validator.canTrust(certName4) == false);
+
+  validator.setAnchor(*introducer2);
+  BOOST_CHECK(validator.canTrust(certName1) == false);
+  BOOST_CHECK(validator.canTrust(certName2) == false);
+  BOOST_CHECK(validator.canTrust(certName3) == false);
+  BOOST_CHECK(validator.canTrust(certName4));
+  BOOST_CHECK(validator.canTrust(certName5));
+
+  Name dataName1 = prefix;
+  dataName1.append("data-1");
+  shared_ptr<Data> data1 = make_shared<Data>(dataName1);
+  keychain.sign(*data1, certName5);
+
+  validator.validate(*data1,
+		     bind(&onValidated, _1),
+		     bind(&onValidationFailed, _1, _2));
+
+  Name dataName2 = prefix;
+  dataName2.append("data-2");
+  shared_ptr<Data> data2 = make_shared<Data>(dataName2);
+  keychain.sign(*data2, certName1);
+
+  validator.validate(*data2,
+		     bind(&onValidated2, _1),
+		     bind(&onValidationFailed2, _1, _2));
+
+  ioService->run();
+
+  keychain.deleteIdentity(identity1);
+  keychain.deleteIdentity(identity2);
+  keychain.deleteIdentity(identity3);
+  keychain.deleteIdentity(identity4);
+  keychain.deleteIdentity(identity5);
+}
+
+BOOST_AUTO_TEST_CASE (OnlineValidate)
+{
+  using namespace Sync;
+  using namespace ndn;
+
+  Name prefix("/Sync/TestSyncValidator/OnlineValidate");
+  KeyChain keychain;
+
+  Name identity1("/TestSyncValidator/OnlineValidate-1/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName1 = keychain.createIdentity(identity1);
+  shared_ptr<IdentityCertificate> anchor = keychain.getCertificate(certName1);
+
+  Name identity2("/TestSyncValidator/OnlineValidate-2/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName2 = keychain.createIdentity(identity2);
+  shared_ptr<IdentityCertificate> introducer = keychain.getCertificate(certName2);
+
+  Name identity3("/TestSyncValidator/OnlineValidate-3/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName3 = keychain.createIdentity(identity3);
+  shared_ptr<IdentityCertificate> introducee = keychain.getCertificate(certName3);
+
+  Name identity4("/TestSyncValidator/OfflineValidate-4/" + boost::lexical_cast<std::string>(time::now()));
+  Name certName4 = keychain.createIdentity(identity4);
+  shared_ptr<IdentityCertificate> introducee2 = keychain.getCertificate(certName4);
+
+  shared_ptr<boost::asio::io_service> ioService = make_shared<boost::asio::io_service>();
+  shared_ptr<Face> face = make_shared<Face>(ioService);
+  SyncValidator validator(prefix, *anchor, face);
+
+  validator.addParticipant(*introducer);
+  BOOST_CHECK(validator.canTrust(certName2));
+  
+  IntroCertificate introCert(prefix, *introducee, certName2.getPrefix(-1));
+  keychain.sign(introCert, certName2);
+  face->put(introCert);
+  BOOST_CHECK(validator.canTrust(certName3) == false);
+
+  IntroCertificate introCert2(prefix, *introducee2, certName3.getPrefix(-1));
+  keychain.sign(introCert2, certName3);
+  face->put(introCert2);
+  BOOST_CHECK(validator.canTrust(certName4) == false);
+
+  Name dataName1 = prefix;
+  dataName1.append("data-1");
+  shared_ptr<Data> data1 = make_shared<Data>(dataName1);
+  keychain.sign(*data1, certName4);
+
+  validator.validate(*data1,
+		     bind(&onValidated, _1),
+		     bind(&onValidationFailed, _1, _2));
+
+  ioService->run();
+
+  BOOST_CHECK(validator.canTrust(certName3));
+  BOOST_CHECK(validator.canTrust(certName4));
+
+  keychain.deleteIdentity(identity1);
+  keychain.deleteIdentity(identity2);
+  keychain.deleteIdentity(identity3);
+  keychain.deleteIdentity(identity4);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/wscript b/wscript
index 4d5e5b0..ad6a1f9 100644
--- a/wscript
+++ b/wscript
@@ -12,8 +12,8 @@
     syncopt = opt.add_option_group ("ChronoSync Options")
 
     syncopt.add_option('--debug',action='store_true',default=False,dest='debug',help='''debugging mode''')
-    syncopt.add_option('--log4cxx', action='store_true',default=False,dest='log4cxx',help='''Compile with log4cxx''')
-    syncopt.add_option('--test', action='store_true',default=False,dest='_test',help='''build unit tests''')
+    syncopt.add_option('--with-log4cxx', action='store_true',default=False,dest='log4cxx',help='''Compile with log4cxx''')
+    syncopt.add_option('--with-tests', action='store_true',default=False,dest='_test',help='''build unit tests''')
 
 def configure(conf):
     conf.load('compiler_c compiler_cxx gnu_dirs boost')
@@ -68,6 +68,7 @@
           features=['cxx', 'cxxprogram'],
           use = 'ChronoSync',
           includes = ['src'],
+          install_path = None,
           )
 
     if bld.get_define ("HAVE_LOG4CXX"):