diff --git a/main.cc b/main.cc
index f449fa4..251b10a 100644
--- a/main.cc
+++ b/main.cc
@@ -9,6 +9,7 @@
 #include <gflags/gflags.h>
 #include <glib.h>
 
+#include "base/at_exit.h"
 #include "base/command_line.h"
 #include "base/logging.h"
 #include "base/string_util.h"
@@ -45,16 +46,29 @@
 
 namespace {
 
+const int kTimeoutOnce = 7 * 60;  // at 7 minutes
+const int kTimeoutPeriodic = 45 * 60;  // every 45 minutes
+const int kTimeoutFuzz = 10 * 60;  // +/- 5 minutes
+
+// Schedules an update check |seconds| from now, while adding some fuzz.
+void ScheduleUpdateCheck(int seconds,
+                         GSourceFunc update_function,
+                         UpdateAttempter* update_attempter) {
+  seconds = utils::FuzzInt(seconds, kTimeoutFuzz);
+  g_timeout_add_seconds(seconds, update_function, update_attempter);
+}
+
 gboolean UpdateOnce(void* arg) {
   UpdateAttempter* update_attempter = reinterpret_cast<UpdateAttempter*>(arg);
   update_attempter->Update("", "");
-  return FALSE;
+  return FALSE;  // Don't run again.
 }
 
 gboolean UpdatePeriodically(void* arg) {
   UpdateAttempter* update_attempter = reinterpret_cast<UpdateAttempter*>(arg);
   update_attempter->Update("", "");
-  return TRUE;
+  ScheduleUpdateCheck(kTimeoutPeriodic, &UpdatePeriodically, update_attempter);
+  return FALSE;  // Don't run again.
 }
 
 void SchedulePeriodicUpdateChecks(UpdateAttempter* update_attempter) {
@@ -62,16 +76,13 @@
     LOG(WARNING) << "Non-official build: periodic update checks disabled.";
     return;
   }
-
   if (utils::IsRemovableDevice(utils::RootDevice(utils::BootDevice()))) {
     LOG(WARNING) << "Removable device boot: periodic update checks disabled.";
     return;
   }
-
-  // Kick off periodic updating. First, update after 2 minutes. Also, update
-  // every 30 minutes.
-  g_timeout_add_seconds(2 * 60, &UpdateOnce, update_attempter);
-  g_timeout_add_seconds(30 * 60, &UpdatePeriodically, update_attempter);
+  // Kick off periodic updating.
+  ScheduleUpdateCheck(kTimeoutOnce, &UpdateOnce, update_attempter);
+  ScheduleUpdateCheck(kTimeoutPeriodic, &UpdatePeriodically, update_attempter);
 }
 
 void SetupDbusService(UpdateEngineService* service) {
@@ -118,6 +129,7 @@
   ::g_type_init();
   g_thread_init(NULL);
   dbus_g_thread_init();
+  base::AtExitManager exit_manager;  // Required for base/rand_util.h.
   chromeos_update_engine::Subprocess::Init();
   google::ParseCommandLineFlags(&argc, &argv, true);
   CommandLine::Init(argc, argv);
diff --git a/testrunner.cc b/testrunner.cc
index 933c25d..3e40e1f 100644
--- a/testrunner.cc
+++ b/testrunner.cc
@@ -10,6 +10,7 @@
 #include <glib.h>
 #include <glib-object.h>
 #include <gtest/gtest.h>
+#include "base/at_exit.h"
 #include "base/command_line.h"
 #include "update_engine/subprocess.h"
 
@@ -17,6 +18,7 @@
   ::g_type_init();
   g_thread_init(NULL);
   dbus_g_thread_init();
+  base::AtExitManager exit_manager;
   chromeos_update_engine::Subprocess::Init();
   CommandLine::Init(argc, argv);
   ::testing::InitGoogleTest(&argc, argv);
diff --git a/utils.cc b/utils.cc
index cf1c3f5..246bfaa 100644
--- a/utils.cc
+++ b/utils.cc
@@ -20,6 +20,7 @@
 
 #include "base/file_path.h"
 #include "base/file_util.h"
+#include "base/rand_util.h"
 #include "base/string_util.h"
 #include "base/logging.h"
 #include "update_engine/file_writer.h"
@@ -457,6 +458,12 @@
   return static_cast<int>(priority_rhs) - static_cast<int>(priority_lhs);
 }
 
+int FuzzInt(int value, unsigned int range) {
+  int min = value - range / 2;
+  int max = value + range - range / 2;
+  return base::RandInt(min, max);
+}
+
 const char* const kStatefulPartition = "/mnt/stateful_partition";
 
 }  // namespace utils
diff --git a/utils.h b/utils.h
index 8438313..8b070ed 100644
--- a/utils.h
+++ b/utils.h
@@ -125,6 +125,10 @@
 // Initiates a system reboot. Returns true on success, false otherwise.
 bool Reboot();
 
+// Fuzzes an integer |value| randomly in the range:
+// [value - range / 2, value + range - range / 2]
+int FuzzInt(int value, unsigned int range);
+
 // Log a string in hex to LOG(INFO). Useful for debugging.
 void HexDumpArray(const unsigned char* const arr, const size_t length);
 inline void HexDumpString(const std::string& str) {
diff --git a/utils_unittest.cc b/utils_unittest.cc
index 70eb6c7..3514f8a 100644
--- a/utils_unittest.cc
+++ b/utils_unittest.cc
@@ -5,9 +5,11 @@
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <errno.h>
+
 #include <string>
 #include <vector>
-#include <gtest/gtest.h>
+
+#include "gtest/gtest.h"
 #include "update_engine/utils.h"
 
 using std::string;
@@ -157,7 +159,7 @@
   EXPECT_EQ("3", utils::PartitionNumber("/dev/mmc0p3"));
 }
 
-TEST(UtilsTest, ComparePriorities) {
+TEST(UtilsTest, ComparePrioritiesTest) {
   EXPECT_LT(utils::ComparePriorities(utils::kProcessPriorityLow,
                                      utils::kProcessPriorityNormal), 0);
   EXPECT_GT(utils::ComparePriorities(utils::kProcessPriorityNormal,
@@ -168,4 +170,17 @@
                                      utils::kProcessPriorityNormal), 0);
 }
 
+TEST(UtilsTest, FuzzIntTest) {
+  static const unsigned int kRanges[] = { 0, 1, 2, 20 };
+  for (size_t r = 0; r < arraysize(kRanges); ++r) {
+    unsigned int range = kRanges[r];
+    const int kValue = 50;
+    for (int tries = 0; tries < 100; ++tries) {
+      int value = utils::FuzzInt(kValue, range);
+      EXPECT_GE(value, kValue - range / 2);
+      EXPECT_LE(value, kValue + range - range / 2);
+    }
+  }
+}
+
 }  // namespace chromeos_update_engine