diff --git a/src/security/conf/filter.hpp b/src/security/conf/filter.hpp
index fb2c15d..8d0601c 100644
--- a/src/security/conf/filter.hpp
+++ b/src/security/conf/filter.hpp
@@ -28,6 +28,7 @@
 #include "../../data.hpp"
 #include "../../interest.hpp"
 #include "../../util/regex.hpp"
+#include "../security-common.hpp"
 #include <boost/algorithm/string.hpp>
 
 #include "common.hpp"
@@ -36,19 +37,42 @@
 namespace security {
 namespace conf {
 
+/**
+ * @brief Filter is one of the classes used by ValidatorConfig.
+ *
+ * The ValidatorConfig class consists of a set of rules.
+ * The Filter class is a part of a rule and is used to match packet.
+ * Matched packets will be checked against the checkers defined in the rule.
+ */
+
 class Filter
 {
 public:
+
   virtual
   ~Filter()
   {
   }
 
-  virtual bool
-  match(const Data& data) = 0;
+  bool
+  match(const Data& data)
+  {
+    return matchName(data.getName());
+  }
 
+  bool
+  match(const Interest& interest)
+  {
+    if (interest.getName().size() < signed_interest::MIN_LENGTH)
+      return false;
+
+    Name unsignedName = interest.getName().getPrefix(-signed_interest::MIN_LENGTH);
+    return matchName(unsignedName);
+  }
+
+protected:
   virtual bool
-  match(const Interest& interest) = 0;
+  matchName(const Name& name) = 0;
 };
 
 class RelationNameFilter : public Filter
@@ -72,25 +96,9 @@
   {
   }
 
+protected:
   virtual bool
-  match(const Data& data)
-  {
-    return match(data.getName());
-  }
-
-  virtual bool
-  match(const Interest& interest)
-  {
-    if (interest.getName().size() < 2)
-      return false;
-
-    Name signedName = interest.getName().getPrefix(-2);
-    return match(signedName);
-  }
-
-private:
-  bool
-  match(const Name& name)
+  matchName(const Name& name)
   {
     switch (m_relation)
       {
@@ -99,7 +107,7 @@
       case RELATION_IS_PREFIX_OF:
         return m_name.isPrefixOf(name);
       case RELATION_IS_STRICT_PREFIX_OF:
-        return (m_name.isPrefixOf(name) && m_name != name);
+        return (m_name.isPrefixOf(name) && m_name.size() < name.size());
       default:
         return false;
       }
@@ -124,20 +132,11 @@
   {
   }
 
+protected:
   virtual bool
-  match(const Data& data)
+  matchName(const Name& name)
   {
-    return m_regex.match(data.getName());
-  }
-
-  virtual bool
-  match(const Interest& interest)
-  {
-    if (interest.getName().size() < 2)
-      return false;
-
-    Name signedName = interest.getName().getPrefix(-2);
-    return m_regex.match(signedName);
+    return m_regex.match(name);
   }
 
 private:
diff --git a/src/security/conf/key-locator-checker.hpp b/src/security/conf/key-locator-checker.hpp
index 21ff8b6..52cf888 100644
--- a/src/security/conf/key-locator-checker.hpp
+++ b/src/security/conf/key-locator-checker.hpp
@@ -27,6 +27,7 @@
 #include "../../common.hpp"
 #include "../../data.hpp"
 #include "../../interest.hpp"
+#include "../security-common.hpp"
 #include <boost/algorithm/string.hpp>
 
 #include "common.hpp"
@@ -37,6 +38,15 @@
 
 class KeyLocatorCheckerFactory;
 
+/**
+ * @brief KeyLocatorChecker is one of the classes used by ValidatorConfig.
+ *
+ * The ValidatorConfig class consists of a set of rules.
+ * The KeyLocatorChecker class is part of a rule and is used to check if the KeyLocator field of a
+ * packet satisfy the requirements.
+ */
+
+
 class KeyLocatorChecker
 {
 public:
@@ -65,13 +75,13 @@
         const KeyLocator& keyLocator,
         std::string& failInfo)
   {
-    if (interest.getName().size() < 2)
+    if (interest.getName().size() < signed_interest::MIN_LENGTH)
       {
         failInfo = "No Signature";
         return false;
       }
 
-    Name signedName = interest.getName().getPrefix(-2);
+    Name signedName = interest.getName().getPrefix(-signed_interest::MIN_LENGTH);
     return check(signedName, keyLocator, failInfo);
   }
 
diff --git a/src/security/key-chain.cpp b/src/security/key-chain.cpp
index 240bab6..22a25b3 100644
--- a/src/security/key-chain.cpp
+++ b/src/security/key-chain.cpp
@@ -41,6 +41,7 @@
 KeyChain::KeyChain()
   : m_pib(0)
   , m_tpm(0)
+  , m_lastTimestamp(time::toUnixTimestamp(time::system_clock::now()))
 {
 
   ConfigFile config;
@@ -102,6 +103,7 @@
                    const std::string& tpmName)
   : m_pib(0)
   , m_tpm(0)
+  , m_lastTimestamp(time::toUnixTimestamp(time::system_clock::now()))
 {
   if (pibName == "sqlite3")
     m_pib = new SecPublicInfoSqlite3;
diff --git a/src/security/key-chain.hpp b/src/security/key-chain.hpp
index 191eeda..043f437 100644
--- a/src/security/key-chain.hpp
+++ b/src/security/key-chain.hpp
@@ -32,6 +32,7 @@
 
 #include "../interest.hpp"
 #include "../util/crypto.hpp"
+#include "../util/random.hpp"
 
 
 namespace ndn {
@@ -680,6 +681,7 @@
 private:
   SecPublicInfo* m_pib;
   SecTpm* m_tpm;
+  time::milliseconds m_lastTimestamp;
 };
 
 template<class T>
@@ -687,6 +689,7 @@
 KeyChain::KeyChain(T)
   : m_pib(new typename T::Pib)
   , m_tpm(new typename T::Tpm)
+  , m_lastTimestamp(time::toUnixTimestamp(time::system_clock::now()))
 {
 }
 
@@ -917,15 +920,24 @@
 KeyChain::signPacketWrapper(Interest& interest, const SignatureSha256WithRsa& signature,
                             const Name& keyName, DigestAlgorithm digestAlgorithm)
 {
+  time::milliseconds timestamp = time::toUnixTimestamp(time::system_clock::now());
+  if (timestamp <= m_lastTimestamp)
+    {
+      timestamp = m_lastTimestamp + time::milliseconds(1);
+    }
+
   Name signedName = interest.getName();
-  signedName.append(signature.getInfo());
+  signedName
+    .append(name::Component::fromNumber(timestamp.count()))        // timestamp
+    .append(name::Component::fromNumber(random::generateWord64())) // nonce
+    .append(signature.getInfo());                                  // signatureInfo
 
   Block sigValue = m_tpm->signInTpm(signedName.wireEncode().value(),
                                     signedName.wireEncode().value_size(),
                                     keyName,
                                     digestAlgorithm);
   sigValue.encode();
-  signedName.append(sigValue);
+  signedName.append(sigValue);                                     // signatureValue
   interest.setName(signedName);
 }
 
diff --git a/src/security/security-common.hpp b/src/security/security-common.hpp
index 072ea74..f795863 100644
--- a/src/security/security-common.hpp
+++ b/src/security/security-common.hpp
@@ -24,6 +24,19 @@
 
 namespace ndn {
 
+namespace signed_interest{
+
+enum {
+  POS_SIG_VALUE = -1,
+  POS_SIG_INFO = -2,
+  POS_RANDOM_VAL = -3,
+  POS_TIMESTAMP = -4,
+
+  MIN_LENGTH = 4
+};
+
+} // namespace signed_interest
+
 enum KeyType {
   KEY_TYPE_RSA,
   KEY_TYPE_ECDSA,
@@ -59,6 +72,6 @@
   ACL_TYPE_PRIVATE
 };
 
-}
+} // namespace ndn
 
 #endif
diff --git a/src/security/validator-config.cpp b/src/security/validator-config.cpp
index a0a35d8..4589d82 100644
--- a/src/security/validator-config.cpp
+++ b/src/security/validator-config.cpp
@@ -32,14 +32,23 @@
 namespace ndn {
 
 const shared_ptr<CertificateCache> ValidatorConfig::DEFAULT_CERTIFICATE_CACHE;
+const time::milliseconds ValidatorConfig::DEFAULT_GRACE_INTERVAL(3000);
+const time::system_clock::Duration ValidatorConfig::DEFAULT_KEY_TIMESTAMP_TTL = time::hours(1);
 
 ValidatorConfig::ValidatorConfig(Face& face,
                                  const shared_ptr<CertificateCache>& certificateCache,
-                                 const int stepLimit)
+                                 const time::milliseconds& graceInterval,
+                                 const size_t stepLimit,
+                                 const size_t maxTrackedKeys,
+                                 const time::system_clock::Duration& keyTimestampTtl)
   : Validator(face)
   , m_shouldValidate(true)
   , m_stepLimit(stepLimit)
   , m_certificateCache(certificateCache)
+  , m_graceInterval(graceInterval < time::milliseconds::zero() ?
+                    DEFAULT_GRACE_INTERVAL : graceInterval)
+  , m_maxTrackedKeys(maxTrackedKeys)
+  , m_keyTimestampTtl(keyTimestampTtl)
 {
   if (!static_cast<bool>(m_certificateCache))
     m_certificateCache = make_shared<CertificateCacheTtl>(ref(m_face.getIoService()));
@@ -469,33 +478,172 @@
   if (!m_shouldValidate)
     return onValidated(interest.shared_from_this());
 
-  bool isMatched = false;
-  int8_t checkResult = -1;
+  // If interestName has less than 4 name components,
+  // it is definitely not a signed interest.
+  if (interest.getName().size() < signed_interest::MIN_LENGTH)
+    return onValidationFailed(interest.shared_from_this(),
+                              "Interest is not signed: " + interest.getName().toUri());
 
-  for (InterestRuleList::iterator it = m_interestRules.begin();
-       it != m_interestRules.end(); it++)
-    {
-      if ((*it)->match(interest))
-        {
-          isMatched = true;
-          checkResult = (*it)->check(interest, onValidated, onValidationFailed);
-          break;
-        }
-    }
-
-  if (!isMatched)
-    return onValidationFailed(interest.shared_from_this(), "No rule matched!");
-
-  if (checkResult == 0)
+  try
     {
       const Name& interestName = interest.getName();
-      Name signedName = interestName.getPrefix(-2);
-      Signature signature(interestName[-2].blockFromValue(),
-                          interestName[-1].blockFromValue());
+      Signature signature(interestName[signed_interest::POS_SIG_INFO].blockFromValue(),
+                          interestName[signed_interest::POS_SIG_VALUE].blockFromValue());
 
-      checkSignature(interest, signature, nSteps,
-                     onValidated, onValidationFailed, nextSteps);
+      if (signature.getType() != Signature::Sha256WithRsa)
+        return onValidationFailed(interest.shared_from_this(),
+                                  "Require SignatureSha256WithRsa");
+
+      SignatureSha256WithRsa sig(signature);
+
+      const KeyLocator& keyLocator = sig.getKeyLocator();
+
+      if (keyLocator.getType() != KeyLocator::KeyLocator_Name)
+        return onValidationFailed(interest.shared_from_this(),
+                                  "Key Locator is not a name");
+
+      Name keyName = IdentityCertificate::certificateNameToPublicKeyName(keyLocator.getName());
+
+      bool isMatched = false;
+      int8_t checkResult = -1;
+
+      for (InterestRuleList::iterator it = m_interestRules.begin();
+           it != m_interestRules.end(); it++)
+        {
+          if ((*it)->match(interest))
+            {
+              isMatched = true;
+              checkResult = (*it)->check(interest,
+                                         bind(&ValidatorConfig::checkTimestamp, this, _1,
+                                              keyName, onValidated, onValidationFailed),
+                                         onValidationFailed);
+              break;
+            }
+        }
+
+      if (!isMatched)
+        return onValidationFailed(interest.shared_from_this(), "No rule matched!");
+
+      if (checkResult == 0)
+        {
+          checkSignature<Interest, OnInterestValidated, OnInterestValidationFailed>
+            (interest, signature, nSteps,
+             bind(&ValidatorConfig::checkTimestamp, this, _1,
+                  keyName, onValidated, onValidationFailed),
+             onValidationFailed,
+             nextSteps);
+        }
     }
+  catch (Signature::Error& e)
+    {
+      return onValidationFailed(interest.shared_from_this(),
+                                "No valid signature");
+    }
+  catch (Tlv::Error& e)
+    {
+      return onValidationFailed(interest.shared_from_this(),
+                                "Cannot decode signature");
+    }
+  catch (KeyLocator::Error& e)
+    {
+      return onValidationFailed(interest.shared_from_this(),
+                                "No valid KeyLocator");
+    }
+  catch (IdentityCertificate::Error& e)
+    {
+      return onValidationFailed(interest.shared_from_this(),
+                                "Cannot determine the signing key");
+    }
+}
+
+void
+ValidatorConfig::checkTimestamp(const shared_ptr<const Interest>& interest,
+                                const Name& keyName,
+                                const OnInterestValidated& onValidated,
+                                const OnInterestValidationFailed& onValidationFailed)
+{
+  const Name& interestName = interest->getName();
+  time::system_clock::TimePoint interestTime;
+
+  try
+    {
+      interestTime =
+        time::fromUnixTimestamp(
+          time::milliseconds(interestName.get(-signed_interest::MIN_LENGTH).toNumber()));
+    }
+  catch (Tlv::Error& e)
+    {
+      return onValidationFailed(interest,
+                                "Cannot decode signature related TLVs");
+    }
+
+  time::system_clock::TimePoint currentTime = time::system_clock::now();
+
+  LastTimestampMap::iterator timestampIt = m_lastTimestamp.find(keyName);
+  if (timestampIt == m_lastTimestamp.end())
+    {
+      if (!(currentTime - m_graceInterval <= interestTime &&
+            interestTime <= currentTime + m_graceInterval))
+        return onValidationFailed(interest,
+                                  "The command is not in grace interval: " +
+                                  interest->getName().toUri());
+    }
+  else
+    {
+      if (interestTime <= timestampIt->second)
+        return onValidationFailed(interest,
+                                  "The command is outdated: " +
+                                  interest->getName().toUri());
+    }
+
+  //Update timestamp
+  if (timestampIt == m_lastTimestamp.end())
+    {
+      cleanOldKeys();
+      m_lastTimestamp[keyName] = interestTime;
+    }
+  else
+    {
+      timestampIt->second = interestTime;
+    }
+
+  return onValidated(interest);
+}
+
+void
+ValidatorConfig::cleanOldKeys()
+{
+  if (m_lastTimestamp.size() < m_maxTrackedKeys)
+    return;
+
+  LastTimestampMap::iterator timestampIt = m_lastTimestamp.begin();
+  LastTimestampMap::iterator end = m_lastTimestamp.end();
+
+  time::system_clock::TimePoint now = time::system_clock::now();
+  LastTimestampMap::iterator oldestKeyIt = m_lastTimestamp.begin();
+  time::system_clock::TimePoint oldestTimestamp = oldestKeyIt->second;
+
+  while (timestampIt != end)
+    {
+      if (now - timestampIt->second > m_keyTimestampTtl)
+        {
+          LastTimestampMap::iterator toDelete = timestampIt;
+          timestampIt++;
+          m_lastTimestamp.erase(toDelete);
+          continue;
+        }
+
+      if (timestampIt->second < oldestTimestamp)
+        {
+          oldestTimestamp = timestampIt->second;
+          oldestKeyIt = timestampIt;
+        }
+
+      timestampIt++;
+    }
+
+  if (m_lastTimestamp.size() >= m_maxTrackedKeys)
+    m_lastTimestamp.erase(oldestKeyIt);
 }
 
 void
diff --git a/src/security/validator-config.hpp b/src/security/validator-config.hpp
index f768efc..f5882d6 100644
--- a/src/security/validator-config.hpp
+++ b/src/security/validator-config.hpp
@@ -46,11 +46,16 @@
   };
 
   static const shared_ptr<CertificateCache> DEFAULT_CERTIFICATE_CACHE;
+  static const time::milliseconds DEFAULT_GRACE_INTERVAL;
+  static const time::system_clock::Duration DEFAULT_KEY_TIMESTAMP_TTL;
 
   explicit
   ValidatorConfig(Face& face,
                   const shared_ptr<CertificateCache>& certificateCache = DEFAULT_CERTIFICATE_CACHE,
-                  const int stepLimit = 10);
+                  const time::milliseconds& graceInterval = DEFAULT_GRACE_INTERVAL,
+                  const size_t stepLimit = 10,
+                  const size_t maxTrackedKeys = 1000,
+                  const time::system_clock::Duration& keyTimestampTtl = DEFAULT_KEY_TIMESTAMP_TTL);
 
   virtual
   ~ValidatorConfig()
@@ -96,11 +101,17 @@
   void
   checkSignature(const Packet& packet,
                  const Signature& signature,
-                 int nSteps,
+                 size_t nSteps,
                  const OnValidated& onValidated,
                  const OnFailed& onValidationFailed,
                  std::vector<shared_ptr<ValidationRequest> >& nextSteps);
 
+  void
+  checkTimestamp(const shared_ptr<const Interest>& interest,
+                 const Name& keyName,
+                 const OnInterestValidated& onValidated,
+                 const OnInterestValidationFailed& onValidationFailed);
+
   template<class Packet, class OnValidated, class OnFailed>
   void
   onCertValidated(const shared_ptr<const Data>& signCertificate,
@@ -132,6 +143,17 @@
   void
   refreshAnchors();
 
+  void
+  cleanOldKeys();
+
+#ifdef NDN_CXX_HAVE_TESTS
+  size_t
+  getTimestampMapSize()
+  {
+    return m_lastTimestamp.size();
+  }
+#endif
+
 
 private:
 
@@ -220,7 +242,7 @@
    */
   bool m_shouldValidate;
 
-  int m_stepLimit;
+  size_t m_stepLimit;
   shared_ptr<CertificateCache> m_certificateCache;
 
   InterestRuleList m_interestRules;
@@ -230,6 +252,11 @@
   TrustAnchorContainer m_staticContainer;
   DynamicContainers m_dynamicContainers;
 
+  time::milliseconds m_graceInterval;
+  size_t m_maxTrackedKeys;
+  typedef std::map<Name, time::system_clock::TimePoint> LastTimestampMap;
+  LastTimestampMap m_lastTimestamp;
+  const time::system_clock::Duration& m_keyTimestampTtl;
 };
 
 inline void
@@ -261,7 +288,7 @@
 void
 ValidatorConfig::checkSignature(const Packet& packet,
                                 const Signature& signature,
-                                int nSteps,
+                                size_t nSteps,
                                 const OnValidated& onValidated,
                                 const OnFailed& onValidationFailed,
                                 std::vector<shared_ptr<ValidationRequest> >& nextSteps)
diff --git a/src/util/command-interest-generator.hpp b/src/util/command-interest-generator.hpp
index 9d69228..8f97b7b 100644
--- a/src/util/command-interest-generator.hpp
+++ b/src/util/command-interest-generator.hpp
@@ -65,44 +65,16 @@
 CommandInterestGenerator::generate(Interest& interest,
                                    const Name& certificateName /*= Name()*/)
 {
-  time::milliseconds timestamp = time::toUnixTimestamp(time::system_clock::now());
-  while (timestamp <= m_lastTimestamp)
-    {
-      timestamp += time::milliseconds(1);
-    }
-
-  Name commandInterestName = interest.getName();
-  commandInterestName
-    .append(name::Component::fromNumber(timestamp.count()))
-    .append(name::Component::fromNumber(random::generateWord64()));
-  interest.setName(commandInterestName);
-
   if (certificateName.empty())
     m_keyChain.sign(interest);
   else
     m_keyChain.sign(interest, certificateName);
-
-  m_lastTimestamp = timestamp;
 }
 
 inline void
 CommandInterestGenerator::generateWithIdentity(Interest& interest, const Name& identity)
 {
-  time::milliseconds timestamp = time::toUnixTimestamp(time::system_clock::now());
-  while (timestamp <= m_lastTimestamp)
-    {
-      timestamp += time::milliseconds(1);
-    }
-
-  Name commandInterestName = interest.getName();
-  commandInterestName
-    .append(name::Component::fromNumber(timestamp.count()))
-    .append(name::Component::fromNumber(random::generateWord64()));
-  interest.setName(commandInterestName);
-
   m_keyChain.signByIdentity(interest, identity);
-
-  m_lastTimestamp = timestamp;
 }