diff --git a/SConstruct b/SConstruct
index 39842ea..2fb23bc 100644
--- a/SConstruct
+++ b/SConstruct
@@ -241,6 +241,7 @@
                    policy_manager/evaluation_context.cc
                    policy_manager/event_loop.cc
                    policy_manager/policy_manager.cc
+                   policy_manager/policy.cc
                    policy_manager/real_config_provider.cc
                    policy_manager/real_device_policy_provider.cc
                    policy_manager/real_random_provider.cc
@@ -300,6 +301,7 @@
                             payload_signer_unittest.cc
                             payload_state_unittest.cc
                             policy_manager/boxed_value_unittest.cc
+                            policy_manager/chromeos_policy_unittest.cc
                             policy_manager/evaluation_context_unittest.cc
                             policy_manager/event_loop_unittest.cc
                             policy_manager/generic_variables_unittest.cc
diff --git a/policy_manager/chromeos_policy.cc b/policy_manager/chromeos_policy.cc
index 4a9f601..436dc73 100644
--- a/policy_manager/chromeos_policy.cc
+++ b/policy_manager/chromeos_policy.cc
@@ -2,19 +2,31 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/policy_manager/chromeos_policy.h"
+#include "update_engine/policy_manager/policy_utils.h"
+
 #include <string>
 
-#include "update_engine/policy_manager/chromeos_policy.h"
-
+using base::Time;
+using base::TimeDelta;
 using std::string;
 
 namespace chromeos_policy_manager {
 
-EvalStatus ChromeOSPolicy::UpdateCheckAllowed(EvaluationContext* ec,
-                                              State* state, string* error,
-                                              bool* result) const {
-  // TODO(deymo): Write this policy implementation with the actual policy.
-  *result = true;
+EvalStatus ChromeOSPolicy::UpdateCheckAllowed(
+    EvaluationContext* ec, State* state, string* error,
+    UpdateCheckParams* result) const {
+  Time next_update_check;
+  if (NextUpdateCheckTime(ec, state, error, &next_update_check) !=
+      EvalStatus::kSucceeded) {
+    return EvalStatus::kFailed;
+  }
+
+  if (!ec->IsTimeGreaterThan(next_update_check))
+    return EvalStatus::kAskMeAgainLater;
+
+  // It is time to check for an update.
+  result->updates_enabled = true;
   return EvalStatus::kSucceeded;
 }
 
@@ -27,4 +39,66 @@
   return EvalStatus::kSucceeded;
 }
 
+EvalStatus ChromeOSPolicy::NextUpdateCheckTime(EvaluationContext* ec,
+                                               State* state, string* error,
+                                               Time* next_update_check) const {
+  // Don't check for updates too often. We limit the update checks to once every
+  // some interval. The interval is kTimeoutInitialInterval the first time and
+  // kTimeoutPeriodicInterval for the subsequent update checks. If the update
+  // check fails, we increase the interval between the update checks
+  // exponentially until kTimeoutMaxBackoffInterval. Finally, to avoid having
+  // many chromebooks running update checks at the exact same time, we add some
+  // fuzz to the interval.
+  const Time* updater_started_time =
+      ec->GetValue(state->updater_provider()->var_updater_started_time());
+  POLICY_CHECK_VALUE_AND_FAIL(updater_started_time, error);
+
+  const base::Time* last_checked_time =
+      ec->GetValue(state->updater_provider()->var_last_checked_time());
+
+  const uint64_t* seed = ec->GetValue(state->random_provider()->var_seed());
+  POLICY_CHECK_VALUE_AND_FAIL(seed, error);
+
+  PRNG prng(*seed);
+
+  if (!last_checked_time || *last_checked_time < *updater_started_time) {
+    // First attempt.
+    *next_update_check = *updater_started_time + FuzzedInterval(
+        &prng, kTimeoutInitialInterval, kTimeoutRegularFuzz);
+    return EvalStatus::kSucceeded;
+  }
+  // Check for previous failed attempts to implement the exponential backoff.
+  const unsigned int* consecutive_failed_update_checks = ec->GetValue(
+      state->updater_provider()->var_consecutive_failed_update_checks());
+  POLICY_CHECK_VALUE_AND_FAIL(consecutive_failed_update_checks, error);
+
+  int interval = kTimeoutInitialInterval;
+  for (unsigned int i = 0; i < *consecutive_failed_update_checks; ++i) {
+    interval *= 2;
+    if (interval > kTimeoutMaxBackoffInterval) {
+      interval = kTimeoutMaxBackoffInterval;
+      break;
+    }
+  }
+
+  *next_update_check = *last_checked_time + FuzzedInterval(
+      &prng, interval, kTimeoutRegularFuzz);
+  return EvalStatus::kSucceeded;
+}
+
+TimeDelta ChromeOSPolicy::FuzzedInterval(PRNG* prng, int interval, int fuzz) {
+  int half_fuzz = fuzz / 2;
+  int lower_bound = interval - half_fuzz;
+  int upper_bound = interval + half_fuzz + 1;
+
+  // This guarantees the output interval is non negative.
+  if (lower_bound < 0)
+    lower_bound = 0;
+
+  int fuzzed_interval = lower_bound;
+  if (upper_bound - lower_bound > 0)
+    fuzzed_interval = lower_bound + prng->rand() % (upper_bound - lower_bound);
+  return TimeDelta::FromSeconds(fuzzed_interval);
+}
+
 }  // namespace chromeos_policy_manager
diff --git a/policy_manager/chromeos_policy.h b/policy_manager/chromeos_policy.h
index 3ade8d0..09d937e 100644
--- a/policy_manager/chromeos_policy.h
+++ b/policy_manager/chromeos_policy.h
@@ -5,7 +5,10 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_CHROMEOS_POLICY_H_
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_CHROMEOS_POLICY_H_
 
+#include <gtest/gtest_prod.h>  // for FRIEND_TEST
+
 #include "update_engine/policy_manager/policy.h"
+#include "update_engine/policy_manager/prng.h"
 
 namespace chromeos_policy_manager {
 
@@ -16,9 +19,9 @@
   virtual ~ChromeOSPolicy() {}
 
   // Policy overrides.
-  virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
-                                        std::string* error,
-                                        bool* result) const override;
+  virtual EvalStatus UpdateCheckAllowed(
+      EvaluationContext* ec, State* state, std::string* error,
+      UpdateCheckParams* result) const override;
 
   virtual EvalStatus UpdateDownloadAndApplyAllowed(EvaluationContext* ec,
                                                    State* state,
@@ -26,6 +29,31 @@
                                                    bool* result) const override;
 
  private:
+  FRIEND_TEST(PmChromeOSPolicyTest,
+              FirstCheckIsAtMostInitialIntervalAfterStart);
+  FRIEND_TEST(PmChromeOSPolicyTest, ExponentialBackoffIsCapped);
+  FRIEND_TEST(PmChromeOSPolicyTest, UpdateCheckAllowedWaitsForTheTimeout);
+
+  // Default update check timeout interval/fuzz values used to compute the
+  // NextUpdateCheckTime(), in seconds. Actual fuzz is within +/- half of the
+  // indicated value.
+  static const int kTimeoutInitialInterval    =  7 * 60;
+  static const int kTimeoutPeriodicInterval   = 45 * 60;
+  static const int kTimeoutQuickInterval      =  1 * 60;
+  static const int kTimeoutMaxBackoffInterval =  4 * 60 * 60;
+  static const int kTimeoutRegularFuzz        = 10 * 60;
+
+  // A private policy implementation returning the wallclock timestamp when
+  // the next update check should happen.
+  EvalStatus NextUpdateCheckTime(EvaluationContext* ec, State* state,
+                                 std::string* error,
+                                 base::Time* next_update_check) const;
+
+  // Returns a TimeDelta based on the provided |interval| seconds +/- half
+  // |fuzz| seconds. The return value is guaranteed to be a non-negative
+  // TimeDelta.
+  static base::TimeDelta FuzzedInterval(PRNG* prng, int interval, int fuzz);
+
   DISALLOW_COPY_AND_ASSIGN(ChromeOSPolicy);
 };
 
diff --git a/policy_manager/chromeos_policy_unittest.cc b/policy_manager/chromeos_policy_unittest.cc
new file mode 100644
index 0000000..c4968ad
--- /dev/null
+++ b/policy_manager/chromeos_policy_unittest.cc
@@ -0,0 +1,136 @@
+// Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/policy_manager/chromeos_policy.h"
+
+#include <string>
+
+#include <base/time/time.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/fake_clock.h"
+#include "update_engine/policy_manager/evaluation_context.h"
+#include "update_engine/policy_manager/fake_state.h"
+#include "update_engine/policy_manager/pmtest_utils.h"
+
+using base::Time;
+using base::TimeDelta;
+using chromeos_update_engine::FakeClock;
+using std::string;
+
+namespace chromeos_policy_manager {
+
+class PmChromeOSPolicyTest : public ::testing::Test {
+ protected:
+  virtual void SetUp() {
+    SetUpDefaultClock();
+    eval_ctx_ = new EvaluationContext(&fake_clock_);
+  }
+
+  // Sets the clock to fixed values.
+  void SetUpDefaultClock() {
+    fake_clock_.SetMonotonicTime(Time::FromInternalValue(12345678L));
+    fake_clock_.SetWallclockTime(Time::FromInternalValue(12345678901234L));
+  }
+
+  void SetUpDefaultState() {
+    fake_state_.updater_provider()->var_updater_started_time()->reset(
+        new Time(fake_clock_.GetWallclockTime()));
+    fake_state_.updater_provider()->var_last_checked_time()->reset(
+        new Time(fake_clock_.GetWallclockTime()));
+    fake_state_.updater_provider()->var_consecutive_failed_update_checks()->
+        reset(new unsigned int(0));
+
+    fake_state_.random_provider()->var_seed()->reset(
+        new uint64_t(4));  // chosen by fair dice roll.
+                           // guaranteed to be random.
+  }
+
+  // Runs the passed |policy_method| policy and expects it to return the
+  // |expected| return value.
+  template<typename T, typename R, typename... Args>
+  void ExpectPolicyStatus(
+      EvalStatus expected,
+      T policy_method,
+      R* result, Args... args) {
+    string error = "<None>";
+    eval_ctx_->ResetEvaluation();
+    EXPECT_EQ(expected,
+              (policy_.*policy_method)(eval_ctx_, &fake_state_, &error, result))
+        << "Returned error: " << error;
+    // TODO(deymo): Dump the context of the EvaluationContext on failure.
+  }
+
+  FakeClock fake_clock_;
+  FakeState fake_state_;
+  scoped_refptr<EvaluationContext> eval_ctx_;
+  ChromeOSPolicy policy_;  // ChromeOSPolicy under test.
+};
+
+TEST_F(PmChromeOSPolicyTest, FirstCheckIsAtMostInitialIntervalAfterStart) {
+  Time next_update_check;
+
+  SetUpDefaultState();
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
+
+  EXPECT_LE(fake_clock_.GetWallclockTime(), next_update_check);
+  EXPECT_GE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+      ChromeOSPolicy::kTimeoutInitialInterval +
+      ChromeOSPolicy::kTimeoutRegularFuzz), next_update_check);
+}
+
+TEST_F(PmChromeOSPolicyTest, ExponentialBackoffIsCapped) {
+  Time next_update_check;
+
+  SetUpDefaultState();
+  fake_state_.updater_provider()->var_consecutive_failed_update_checks()->
+      reset(new unsigned int(100));
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
+
+  EXPECT_LE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+      ChromeOSPolicy::kTimeoutMaxBackoffInterval -
+      ChromeOSPolicy::kTimeoutRegularFuzz - 1), next_update_check);
+  EXPECT_GE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+      ChromeOSPolicy::kTimeoutMaxBackoffInterval +
+      ChromeOSPolicy::kTimeoutRegularFuzz), next_update_check);
+}
+
+TEST_F(PmChromeOSPolicyTest, UpdateCheckAllowedWaitsForTheTimeout) {
+  // We get the next update_check timestamp from the policy's private method
+  // and then we check the public method respects that value on the normal
+  // case.
+  Time next_update_check;
+  Time last_checked_time =
+      fake_clock_.GetWallclockTime() + TimeDelta::FromMinutes(1234);
+
+  SetUpDefaultClock();
+  SetUpDefaultState();
+  fake_state_.updater_provider()->var_last_checked_time()->reset(
+      new Time(last_checked_time));
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
+
+  UpdateCheckParams result;
+
+  // Check that the policy blocks until the next_update_check is reached.
+  SetUpDefaultClock();
+  SetUpDefaultState();
+  fake_state_.updater_provider()->var_last_checked_time()->reset(
+      new Time(last_checked_time));
+  fake_clock_.SetWallclockTime(next_update_check - TimeDelta::FromSeconds(1));
+  ExpectPolicyStatus(EvalStatus::kAskMeAgainLater,
+                     &Policy::UpdateCheckAllowed, &result);
+
+  SetUpDefaultClock();
+  SetUpDefaultState();
+  fake_state_.updater_provider()->var_last_checked_time()->reset(
+      new Time(last_checked_time));
+  fake_clock_.SetWallclockTime(next_update_check + TimeDelta::FromSeconds(1));
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &Policy::UpdateCheckAllowed, &result);
+}
+
+}  // namespace chromeos_policy_manager
diff --git a/policy_manager/default_policy.h b/policy_manager/default_policy.h
index 1eeb54b..e019950 100644
--- a/policy_manager/default_policy.h
+++ b/policy_manager/default_policy.h
@@ -18,10 +18,10 @@
   virtual ~DefaultPolicy() {}
 
   // Policy overrides.
-  virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
-                                        std::string* error,
-                                        bool* result) const override {
-    *result = true;
+  virtual EvalStatus UpdateCheckAllowed(
+      EvaluationContext* ec, State* state, std::string* error,
+      UpdateCheckParams* result) const override {
+    result->updates_enabled = true;
     return EvalStatus::kSucceeded;
   }
 
diff --git a/policy_manager/mock_policy.h b/policy_manager/mock_policy.h
index 118a24b..7aa9d66 100644
--- a/policy_manager/mock_policy.h
+++ b/policy_manager/mock_policy.h
@@ -13,20 +13,20 @@
 
 // A mocked implementation of Policy.
 class MockPolicy : public Policy {
-public:
+ public:
   MockPolicy() {}
   virtual ~MockPolicy() {}
 
   // Policy overrides.
   MOCK_CONST_METHOD4(UpdateCheckAllowed,
                      EvalStatus(EvaluationContext*, State*, std::string*,
-                                bool*));
+                                UpdateCheckParams*));
 
   MOCK_CONST_METHOD4(UpdateDownloadAndApplyAllowed,
                      EvalStatus(EvaluationContext*, State*, std::string*,
                                 bool*));
 
-private:
+ private:
   DISALLOW_COPY_AND_ASSIGN(MockPolicy);
 };
 
diff --git a/policy_manager/pmtest_utils.cc b/policy_manager/pmtest_utils.cc
index 569648e..1c53099 100644
--- a/policy_manager/pmtest_utils.cc
+++ b/policy_manager/pmtest_utils.cc
@@ -10,4 +10,8 @@
 
 const unsigned PmTestUtils::kDefaultTimeoutInSeconds = 1;
 
+void PrintTo(const EvalStatus& status, ::std::ostream* os) {
+  *os << ToString(status);
+}
+
 }  // namespace chromeos_policy_manager
diff --git a/policy_manager/pmtest_utils.h b/policy_manager/pmtest_utils.h
index d9f98ce..79a7733 100644
--- a/policy_manager/pmtest_utils.h
+++ b/policy_manager/pmtest_utils.h
@@ -5,10 +5,13 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PMTEST_UTILS_H_
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PMTEST_UTILS_H_
 
+#include <iostream>
+
 #include <base/memory/scoped_ptr.h>
 #include <base/time/time.h>
 #include <gtest/gtest.h>
 
+#include "update_engine/policy_manager/policy.h"
 #include "update_engine/policy_manager/variable.h"
 
 // Convenience macros for checking null-ness of pointers.
@@ -58,6 +61,10 @@
   static const unsigned kDefaultTimeoutInSeconds;
 };
 
+// PrintTo() functions are used by gtest to print these values. They need to be
+// defined on the same namespace where the type was defined.
+void PrintTo(const EvalStatus& status, ::std::ostream* os);
+
 }  // namespace chromeos_policy_manager
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PMTEST_UTILS_H_
diff --git a/policy_manager/policy.cc b/policy_manager/policy.cc
new file mode 100644
index 0000000..32c6439
--- /dev/null
+++ b/policy_manager/policy.cc
@@ -0,0 +1,25 @@
+// Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/policy_manager/policy.h"
+
+#include <string>
+
+using std::string;
+
+namespace chromeos_policy_manager {
+
+string ToString(EvalStatus status) {
+  switch (status) {
+    case EvalStatus::kFailed:
+      return "kFailed";
+    case EvalStatus::kSucceeded:
+      return "kSucceeded";
+    case EvalStatus::kAskMeAgainLater:
+      return "kAskMeAgainLater";
+  }
+  return "Invalid";
+}
+
+}  // namespace chromeos_update_engine
diff --git a/policy_manager/policy.h b/policy_manager/policy.h
index 7c7ec0c..334a5bd 100644
--- a/policy_manager/policy.h
+++ b/policy_manager/policy.h
@@ -5,6 +5,8 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_H_
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_H_
 
+#include <string>
+
 #include "update_engine/policy_manager/evaluation_context.h"
 #include "update_engine/policy_manager/state.h"
 
@@ -17,6 +19,15 @@
   kAskMeAgainLater,
 };
 
+std::string ToString(EvalStatus status);
+
+// Parameters of an update check. These parameters are determined by the
+// UpdateCheckAllowed policy.
+struct UpdateCheckParams {
+  bool updates_enabled;  // Whether the auto-updates are enabled on this build.
+};
+
+
 // The Policy class is an interface to the ensemble of policy requests that the
 // client can make. A derived class includes the policy implementations of
 // these.
@@ -36,9 +47,9 @@
 
   // UpdateCheckAllowed returns whether it is allowed to request an update check
   // to Omaha.
-  virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
-                                        std::string* error,
-                                        bool* result) const = 0;
+  virtual EvalStatus UpdateCheckAllowed(
+      EvaluationContext* ec, State* state, std::string* error,
+      UpdateCheckParams* result) const = 0;
 
   // Returns whether an update can be downloaded/applied.
   virtual EvalStatus UpdateDownloadAndApplyAllowed(EvaluationContext* ec,
diff --git a/policy_manager/policy_manager_unittest.cc b/policy_manager/policy_manager_unittest.cc
index 15553a5..5272bcd 100644
--- a/policy_manager/policy_manager_unittest.cc
+++ b/policy_manager/policy_manager_unittest.cc
@@ -50,7 +50,7 @@
 class FailingPolicy : public DefaultPolicy {
   virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
                                         string* error,
-                                        bool* result) const {
+                                        UpdateCheckParams* result) const {
     *error = "FailingPolicy failed.";
     return EvalStatus::kFailed;
   }
@@ -60,7 +60,7 @@
 class LazyPolicy : public DefaultPolicy {
   virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
                                         string* error,
-                                        bool* result) const {
+                                        UpdateCheckParams* result) const {
     return EvalStatus::kAskMeAgainLater;
   }
 };
@@ -75,41 +75,19 @@
   acc->push_back(std::make_pair(status, result));
 }
 
-TEST_F(PmPolicyManagerTest, PolicyRequestCallReturnsSuccess) {
+// Tests that policy requests are completed successfully. It is important that
+// this tests cover all policy requests as defined in Policy.
+TEST_F(PmPolicyManagerTest, PolicyRequestCallUpdateDownloadAndApplyAllowed) {
   bool result;
-  EvalStatus status;
-
-  // Tests that policy requests are completed successfully. It is important that
-  // this test covers all policy requests as defined in Policy.
-  //
-  // TODO(garnold) We may need to adapt this test as the Chrome OS policy grows
-  // beyond the stub implementation.
-  status = pmut_->PolicyRequest(&Policy::UpdateCheckAllowed, &result);
-  EXPECT_EQ(EvalStatus::kSucceeded, status);
-  status = pmut_->PolicyRequest(&Policy::UpdateDownloadAndApplyAllowed,
-                                &result);
-  EXPECT_EQ(EvalStatus::kSucceeded, status);
+  EXPECT_EQ(EvalStatus::kSucceeded,
+            pmut_->PolicyRequest(&Policy::UpdateDownloadAndApplyAllowed,
+                                 &result));
 }
 
-TEST_F(PmPolicyManagerTest, PolicyRequestCallsPolicy) {
-  StrictMock<MockPolicy>* policy = new StrictMock<MockPolicy>();
-  pmut_->set_policy(policy);
-  bool result;
-  EvalStatus status;
-
-  // Tests that the policy methods are actually called on the policy instance.
-  // It is important that this test covers all policy requests as defined in
-  // Policy.
-  EXPECT_CALL(*policy, UpdateCheckAllowed(_, _, _, _))
-      .WillOnce(Return(EvalStatus::kSucceeded));
-  status = pmut_->PolicyRequest(&Policy::UpdateCheckAllowed, &result);
-  EXPECT_EQ(EvalStatus::kSucceeded, status);
-
-  EXPECT_CALL(*policy, UpdateDownloadAndApplyAllowed(_, _, _, _))
-      .WillOnce(Return(EvalStatus::kSucceeded));
-  status = pmut_->PolicyRequest(&Policy::UpdateDownloadAndApplyAllowed,
-                                &result);
-  EXPECT_EQ(EvalStatus::kSucceeded, status);
+TEST_F(PmPolicyManagerTest, PolicyRequestCallUpdateCheckAllowed) {
+  UpdateCheckParams result;
+  EXPECT_EQ(EvalStatus::kSucceeded, pmut_->PolicyRequest(
+      &Policy::UpdateCheckAllowed, &result));
 }
 
 TEST_F(PmPolicyManagerTest, PolicyRequestCallsDefaultOnError) {
@@ -117,16 +95,17 @@
 
   // Tests that the DefaultPolicy instance is called when the method fails,
   // which will set this as true.
-  bool result = false;
+  UpdateCheckParams result;
+  result.updates_enabled = false;
   EvalStatus status = pmut_->PolicyRequest(
       &Policy::UpdateCheckAllowed, &result);
   EXPECT_EQ(EvalStatus::kSucceeded, status);
-  EXPECT_TRUE(result);
+  EXPECT_TRUE(result.updates_enabled);
 }
 
 TEST_F(PmPolicyManagerTest, PolicyRequestDoesntBlock) {
+  UpdateCheckParams result;
   pmut_->set_policy(new LazyPolicy());
-  bool result;
 
   EvalStatus status = pmut_->PolicyRequest(
       &Policy::UpdateCheckAllowed, &result);
@@ -140,9 +119,9 @@
   // the main loop in both cases even when we could evaluate it right now.
   pmut_->set_policy(new FailingPolicy());
 
-  vector<pair<EvalStatus, bool>> calls;
-  Callback<void(EvalStatus, const bool& result)> callback =
-      Bind(AccumulateCallsCallback<bool>, &calls);
+  vector<pair<EvalStatus, UpdateCheckParams>> calls;
+  Callback<void(EvalStatus, const UpdateCheckParams& result)> callback =
+      Bind(AccumulateCallsCallback<UpdateCheckParams>, &calls);
 
   pmut_->AsyncPolicyRequest(callback, &Policy::UpdateCheckAllowed);
   // The callback should wait until we run the main loop for it to be executed.
diff --git a/policy_manager/policy_utils.h b/policy_manager/policy_utils.h
new file mode 100644
index 0000000..61e0413
--- /dev/null
+++ b/policy_manager/policy_utils.h
@@ -0,0 +1,26 @@
+// Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_UTILS_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_UTILS_H_
+
+#include "update_engine/policy_manager/policy.h"
+
+// Checks that the passed pointer value is not null, returning kFailed on the
+// current context and setting the *error description when it is null. The
+// intended use is to validate variable failures while using
+// EvaluationContext::GetValue, for example:
+//
+//   const int* my_value = ec->GetValue(state->my_provider()->var_my_value());
+//   POLICY_CHECK_VALUE_AND_FAIL(my_value, error);
+//
+#define POLICY_CHECK_VALUE_AND_FAIL(ptr, error) \
+    do { \
+      if ((ptr) == nullptr) { \
+        *(error) = #ptr " is required but is null."; \
+        return EvalStatus::kFailed; \
+      } \
+    } while (false)
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_UTILS_H_