diff --git a/ndn-cxx/security/validator-config/checker.cpp b/ndn-cxx/security/validator-config/checker.cpp
index 057ec54..04d427c 100644
--- a/ndn-cxx/security/validator-config/checker.cpp
+++ b/ndn-cxx/security/validator-config/checker.cpp
@@ -32,33 +32,65 @@
 inline namespace v2 {
 namespace validator_config {
 
-bool
+Checker::Result::Result(std::string error)
+  : m_error(std::move(error))
+{
+}
+
+class Checker::NegativeResultBuilder
+{
+public:
+  template<typename T>
+  NegativeResultBuilder&
+  operator<<(const T& value)
+  {
+    m_ss << value;
+    return *this;
+  }
+
+  operator Checker::Result() const
+  {
+    auto error = m_ss.str();
+    return Checker::Result(error.empty() ? "checker failed" : std::move(error));
+  }
+
+private:
+  std::ostringstream m_ss;
+};
+
+Checker::NegativeResultBuilder
+Checker::reject()
+{
+  return NegativeResultBuilder();
+}
+
+Checker::Result
 Checker::check(uint32_t pktType, const Name& pktName, const Name& klName,
-               const shared_ptr<ValidationState>& state)
+               const ValidationState& state)
 {
   BOOST_ASSERT(pktType == tlv::Interest || pktType == tlv::Data);
 
   if (pktType == tlv::Interest) {
-    auto fmt = state->getTag<SignedInterestFormatTag>();
+    auto fmt = state.getTag<SignedInterestFormatTag>();
     BOOST_ASSERT(fmt);
 
     if (*fmt == SignedInterestFormat::V03) {
       // This check is redundant if parameter digest checking is enabled. However, the parameter
       // digest checking can be disabled in API.
       if (pktName.size() == 0 || pktName[-1].type() != tlv::ParametersSha256DigestComponent) {
-        return false;
+        return reject() << "ParametersSha256DigestComponent missing";
       }
-      return checkNames(pktName.getPrefix(-1), klName, state);
+      return checkNames(pktName.getPrefix(-1), klName);
     }
     else {
       if (pktName.size() < signed_interest::MIN_SIZE)
-        return false;
+        return reject() << "name too short";
 
-      return checkNames(pktName.getPrefix(-signed_interest::MIN_SIZE), klName, state);
+      return checkNames(pktName.getPrefix(-signed_interest::MIN_SIZE), klName);
     }
   }
   else {
-    return checkNames(pktName, klName, state);
+    return checkNames(pktName, klName);
   }
 }
 
@@ -68,21 +100,17 @@
 {
 }
 
-bool
-NameRelationChecker::checkNames(const Name& pktName, const Name& klName,
-                                const shared_ptr<ValidationState>& state)
+Checker::Result
+NameRelationChecker::checkNames(const Name& pktName, const Name& klName)
 {
   // pktName not used in this check
   Name identity = extractIdentityNameFromKeyLocator(klName);
-  bool result = checkNameRelation(m_relation, m_name, identity);
-  if (!result) {
-    std::ostringstream os;
-    os << "KeyLocator check failed: name relation " << m_name << " " << m_relation
-       << " for packet " << pktName << " is invalid"
-       << " (KeyLocator=" << klName << ", identity=" << identity << ")";
-    state->fail({ValidationError::POLICY_ERROR, os.str()});
+  if (checkNameRelation(m_relation, m_name, identity)) {
+    return accept();
   }
-  return result;
+
+  return reject() << "identity " << identity << " and packet name do not satisfy "
+                  << m_relation << " relation";
 }
 
 RegexChecker::RegexChecker(const Regex& regex)
@@ -90,17 +118,14 @@
 {
 }
 
-bool
-RegexChecker::checkNames(const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state)
+Checker::Result
+RegexChecker::checkNames(const Name& pktName, const Name& klName)
 {
-  bool result = m_regex.match(klName);
-  if (!result) {
-    std::ostringstream os;
-    os << "KeyLocator check failed: regex " << m_regex << " for packet " << pktName << " is invalid"
-       << " (KeyLocator=" << klName << ")";
-    state->fail({ValidationError::POLICY_ERROR, os.str()});
+  if (m_regex.match(klName)) {
+    return accept();
   }
-  return result;
+
+  return reject() << "KeyLocator does not match regex " << m_regex;
 }
 
 HyperRelationChecker::HyperRelationChecker(const std::string& pktNameExpr, const std::string pktNameExpand,
@@ -112,27 +137,25 @@
 {
 }
 
-bool
-HyperRelationChecker::checkNames(const Name& pktName, const Name& klName,
-                                 const shared_ptr<ValidationState>& state)
+Checker::Result
+HyperRelationChecker::checkNames(const Name& pktName, const Name& klName)
 {
-  if (!m_hyperPRegex.match(pktName) || !m_hyperKRegex.match(klName)) {
-    std::ostringstream os;
-    os << "Packet " << pktName << " (" << "KeyLocator=" << klName << ") does not match "
-       << "the hyper relation rule pkt=" << m_hyperPRegex << ", key=" << m_hyperKRegex;
-    state->fail({ValidationError::POLICY_ERROR, os.str()});
-    return false;
+  if (!m_hyperPRegex.match(pktName)) {
+    return reject() << "packet name does not match p-regex " << m_hyperPRegex;
   }
 
-  bool result = checkNameRelation(m_hyperRelation, m_hyperKRegex.expand(), m_hyperPRegex.expand());
-  if (!result) {
-    std::ostringstream os;
-    os << "KeyLocator check failed: hyper relation " << m_hyperRelation
-       << " pkt=" << m_hyperPRegex << ", key=" << m_hyperKRegex
-       << " of packet " << pktName << " (KeyLocator=" << klName << ") is invalid";
-    state->fail({ValidationError::POLICY_ERROR, os.str()});
+  if (!m_hyperKRegex.match(klName)) {
+    return reject() << "KeyLocator does not match k-regex " << m_hyperKRegex;
   }
-  return result;
+
+  auto kExpand = m_hyperKRegex.expand();
+  auto pExpand = m_hyperPRegex.expand();
+  if (checkNameRelation(m_hyperRelation, kExpand, pExpand)) {
+    return accept();
+  }
+
+  return reject() << "expanded names " << kExpand << " and " << pExpand
+                  << " do not satisfy " << m_hyperRelation << " relation";
 }
 
 unique_ptr<Checker>
diff --git a/ndn-cxx/security/validator-config/checker.hpp b/ndn-cxx/security/validator-config/checker.hpp
index b698226..8d6e75e 100644
--- a/ndn-cxx/security/validator-config/checker.hpp
+++ b/ndn-cxx/security/validator-config/checker.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2020 Regents of the University of California.
+ * Copyright (c) 2013-2021 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -38,22 +38,52 @@
 class Checker : noncopyable
 {
 public:
+  class Result
+  {
+  public:
+    /**
+     * @brief Return true if the check matches, false otherwise.
+     * @retval false packet does not pass the checker.
+     * @retval true  packet passes the checker. Further verification may be needed.
+     */
+    explicit operator bool() const
+    {
+      return m_error.empty();
+    }
+
+    /**
+     * @brief Return checker error message.
+     * @pre !bool(*this)
+     */
+    const std::string&
+    getErrorMessage() const
+    {
+      return m_error;
+    }
+
+  private:
+    explicit
+    Result(std::string error);
+
+  private:
+    std::string m_error;
+
+    friend Checker;
+  };
+
   virtual
   ~Checker() = default;
 
   /**
-   * @brief Check if packet name ane KeyLocator satisfy the checker's conditions
+   * @brief Check if packet name and KeyLocator satisfy the checker's conditions
    *
    * @param pktType tlv::Interest or tlv::Data
    * @param pktName packet's name
    * @param klName  KeyLocator's name
    * @param state Validation state
-   *
-   * @retval false data is immediately invalid. Will call state::fail() with proper code and message.
-   * @retval true  further signature verification is needed.
    */
-  bool
-  check(uint32_t pktType, const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state);
+  Result
+  check(uint32_t pktType, const Name& pktName, const Name& klName, const ValidationState& state);
 
   /**
    * @brief create a checker from configuration section
@@ -65,6 +95,21 @@
   static unique_ptr<Checker>
   create(const ConfigSection& configSection, const std::string& configFilename);
 
+protected:
+  virtual Result
+  checkNames(const Name& pktName, const Name& klName) = 0;
+
+  static Result
+  accept()
+  {
+    return Result("");
+  }
+
+  class NegativeResultBuilder;
+
+  static NegativeResultBuilder
+  reject();
+
 private:
   static unique_ptr<Checker>
   createCustomizedChecker(const ConfigSection& configSection, const std::string& configFilename);
@@ -77,10 +122,6 @@
 
   static unique_ptr<Checker>
   createKeyLocatorNameChecker(const ConfigSection& configSection, const std::string& configFilename);
-
-protected:
-  virtual bool
-  checkNames(const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state) = 0;
 };
 
 class NameRelationChecker : public Checker
@@ -89,8 +130,8 @@
   NameRelationChecker(const Name& name, const NameRelation& relation);
 
 protected:
-  bool
-  checkNames(const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state) override;
+  Result
+  checkNames(const Name& pktName, const Name& klName) override;
 
 private:
   Name m_name;
@@ -104,8 +145,8 @@
   RegexChecker(const Regex& regex);
 
 protected:
-  bool
-  checkNames(const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state) override;
+  Result
+  checkNames(const Name& pktName, const Name& klName) override;
 
 private:
   Regex m_regex;
@@ -119,8 +160,8 @@
                        const NameRelation& hyperRelation);
 
 protected:
-  bool
-  checkNames(const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state) override;
+  Result
+  checkNames(const Name& pktName, const Name& klName) override;
 
 private:
   Regex m_hyperPRegex;
diff --git a/ndn-cxx/security/validator-config/rule.cpp b/ndn-cxx/security/validator-config/rule.cpp
index b320ad1..025f871 100644
--- a/ndn-cxx/security/validator-config/rule.cpp
+++ b/ndn-cxx/security/validator-config/rule.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2020 Regents of the University of California.
+ * Copyright (c) 2013-2021 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -20,6 +20,7 @@
  */
 
 #include "ndn-cxx/security/validator-config/rule.hpp"
+#include "ndn-cxx/security/validation-state.hpp"
 #include "ndn-cxx/util/logger.hpp"
 
 #include <boost/algorithm/string/predicate.hpp>
@@ -76,23 +77,30 @@
 Rule::check(uint32_t pktType, const Name& pktName, const Name& klName,
             const shared_ptr<ValidationState>& state) const
 {
-  NDN_LOG_TRACE("Trying to check " << pktName << " with keyLocator " << klName);
+  NDN_LOG_TRACE("Trying to check " << pktName << " with KeyLocator " << klName);
 
   if (pktType != m_pktType) {
     NDN_THROW(Error("Invalid packet type supplied (" + to_string(pktType) +
                     " != " + to_string(m_pktType) + ")"));
   }
 
-  bool hasPendingResult = false;
+  std::vector<Checker::Result> checkerResults;
+  checkerResults.reserve(m_checkers.size());
   for (const auto& checker : m_checkers) {
-    bool result = checker->check(pktType, pktName, klName, state);
-    if (!result) {
-      return result;
+    auto result = checker->check(pktType, pktName, klName, *state);
+    if (result) {
+      return true;
     }
-    hasPendingResult = true;
+    checkerResults.push_back(std::move(result));
   }
 
-  return hasPendingResult;
+  std::ostringstream err;
+  err << "Packet " << pktName << " (KeyLocator=" << klName << ") cannot pass any checker.";
+  for (size_t i = 0; i < checkerResults.size(); ++i) {
+    err << "\nChecker " << i << ": " << checkerResults[i].getErrorMessage();
+  }
+  state->fail({ValidationError::POLICY_ERROR, err.str()});
+  return false;
 }
 
 unique_ptr<Rule>
diff --git a/ndn-cxx/security/validator-config/rule.hpp b/ndn-cxx/security/validator-config/rule.hpp
index 73410b2..08efedd 100644
--- a/ndn-cxx/security/validator-config/rule.hpp
+++ b/ndn-cxx/security/validator-config/rule.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2020 Regents of the University of California.
+ * Copyright (c) 2013-2021 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -73,17 +73,18 @@
   match(uint32_t pktType, const Name& pktName, const shared_ptr<ValidationState>& state) const;
 
   /**
-   * @brief check if packet satisfies rule's condition
+   * @brief Check if packet satisfies rule's condition.
    *
    * @param pktType tlv::Interest or tlv::Data
    * @param pktName packet name, for signed Interests the last two components are not removed
    * @param klName KeyLocator name
    * @param state Validation state
    *
-   * @retval false packet violates at least one checker. Will call state::fail() with proper code and message.
-   * @retval true  packet satisfies all checkers, further validation is needed
+   * @retval false packet violates all checkers. `fail()` will have been called on @p state with
+   *               proper code and message.
+   * @retval true  packet satisfies at least one checker, further validation is needed.
    *
-   * @throw Error the supplied pktType doesn't match one for which the rule is designed
+   * @throw Error the supplied pktType doesn't match one for which the rule is designed.
    */
   bool
   check(uint32_t pktType, const Name& pktName, const Name& klName, const shared_ptr<ValidationState>& state) const;
diff --git a/tests/unit/security/validator-config/checker.t.cpp b/tests/unit/security/validator-config/checker.t.cpp
index 2485a82..84901ec 100644
--- a/tests/unit/security/validator-config/checker.t.cpp
+++ b/tests/unit/security/validator-config/checker.t.cpp
@@ -66,6 +66,21 @@
     return Name(name).append(suffix);
   }
 
+  template<typename PktType, typename C>
+  static void
+  testChecker(C& checker, const Name& pktName, const Name& klName, bool expectedOutcome)
+  {
+    BOOST_TEST_CONTEXT("pkt=" << pktName << " kl=" << klName) {
+      auto state = PktType::makeState();
+      auto result = checker.check(PktType::getType(), pktName, klName, *state);
+      BOOST_CHECK_EQUAL(bool(result), expectedOutcome);
+      BOOST_CHECK(boost::logic::indeterminate(state->getOutcome()));
+      if (!result) {
+        BOOST_CHECK_NE(result.getErrorMessage(), "");
+      }
+    }
+  }
+
 public:
   std::vector<Name> names;
 };
@@ -305,27 +320,16 @@
   BOOST_REQUIRE_EQUAL(this->outcomes.size(), this->names.size());
   for (size_t i = 0; i < this->names.size(); ++i) {
     BOOST_REQUIRE_EQUAL(this->outcomes[i].size(), this->names.size());
+
+    auto pktName = PktType::makeName(this->names[i], this->m_keyChain);
     for (size_t j = 0; j < this->names.size(); ++j) {
-      auto pktName = PktType::makeName(this->names[i], this->m_keyChain);
       bool expectedOutcome = this->outcomes[i][j];
 
-      {
-        auto klName = this->makeKeyLocatorKeyName(this->names[j]);
+      auto klName = this->makeKeyLocatorKeyName(this->names[j]);
+      this->template testChecker<PktType>(this->checker, pktName, klName, expectedOutcome);
 
-        auto state = PktType::makeState();
-        BOOST_CHECK_EQUAL(this->checker.check(PktType::getType(), pktName, klName, state), expectedOutcome);
-        BOOST_CHECK_EQUAL(boost::logic::indeterminate(state->getOutcome()), expectedOutcome);
-        BOOST_CHECK_EQUAL(bool(state->getOutcome()), false);
-      }
-
-      {
-        auto klName = this->makeKeyLocatorCertName(this->names[j]);
-
-        auto state = PktType::makeState();
-        BOOST_CHECK_EQUAL(this->checker.check(PktType::getType(), pktName, klName, state), expectedOutcome);
-        BOOST_CHECK_EQUAL(boost::logic::indeterminate(state->getOutcome()), expectedOutcome);
-        BOOST_CHECK_EQUAL(bool(state->getOutcome()), false);
-      }
+      klName = this->makeKeyLocatorCertName(this->names[j]);
+      this->template testChecker<PktType>(this->checker, pktName, klName, expectedOutcome);
     }
   }
 }
diff --git a/tests/unit/security/validator-config/rule.t.cpp b/tests/unit/security/validator-config/rule.t.cpp
index 04c6e8d..0410d9f 100644
--- a/tests/unit/security/validator-config/rule.t.cpp
+++ b/tests/unit/security/validator-config/rule.t.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2020 Regents of the University of California.
+ * Copyright (c) 2013-2021 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -96,23 +96,36 @@
 
 BOOST_FIXTURE_TEST_CASE_TEMPLATE(Checkers, PktType, PktTypes, RuleFixture<PktType>)
 {
-  this->rule.addChecker(make_unique<HyperRelationChecker>("^(<>+)$", "\\1",
-                                                        "^<not>?(<>+)$", "\\1",
-                                                        NameRelation::EQUAL));
+  auto testChecker = [this] (const Name& klName, bool expectedOutcome) {
+    BOOST_TEST_CONTEXT(klName << " expected=" << expectedOutcome) {
+      this->state = PktType::makeState(); // reset state
+      BOOST_CHECK_EQUAL(this->rule.check(PktType::getType(), this->pktName, klName, this->state),
+                        expectedOutcome);
 
-  BOOST_CHECK_EQUAL(this->rule.check(PktType::getType(), this->pktName, "/foo/bar", this->state), true);
-
-  this->state = PktType::makeState(); // reset state
-  BOOST_CHECK_EQUAL(this->rule.check(PktType::getType(), this->pktName, "/not/foo/bar", this->state), true);
+      auto outcome = this->state->getOutcome();
+      if (expectedOutcome) {
+        BOOST_CHECK(boost::logic::indeterminate(outcome));
+      }
+      else {
+        BOOST_CHECK(!boost::logic::indeterminate(outcome));
+        BOOST_CHECK(!bool(outcome));
+      }
+    }
+  };
 
   this->rule.addChecker(make_unique<HyperRelationChecker>("^(<>+)$", "\\1",
-                                                        "^(<>+)$", "\\1",
-                                                        NameRelation::EQUAL));
-  this->state = PktType::makeState(); // reset state
-  BOOST_CHECK_EQUAL(this->rule.check(PktType::getType(), this->pktName, "/foo/bar", this->state), true);
+                                                          "^<always>(<>+)$", "\\1",
+                                                          NameRelation::EQUAL));
+  testChecker("/always/foo/bar", true);
+  testChecker("/seldomly/foo/bar", false);
+  testChecker("/never/foo/bar", false);
 
-  this->state = PktType::makeState(); // reset state
-  BOOST_CHECK_EQUAL(this->rule.check(PktType::getType(), this->pktName, "/not/foo/bar", this->state), false);
+  this->rule.addChecker(make_unique<HyperRelationChecker>("^(<>+)$", "\\1",
+                                                          "^<seldomly>(<>+)$", "\\1",
+                                                          NameRelation::EQUAL));
+  testChecker("/always/foo/bar", true);
+  testChecker("/seldomly/foo/bar", true);
+  testChecker("/never/foo/bar", false);
 }
 
 BOOST_AUTO_TEST_SUITE(Create)