diff --git a/keystore/.clang-format b/keystore/.clang-format
new file mode 100644
index 0000000..5747e19
--- /dev/null
+++ b/keystore/.clang-format
@@ -0,0 +1,10 @@
+BasedOnStyle: LLVM
+IndentWidth: 4
+UseTab: Never
+BreakBeforeBraces: Attach
+AllowShortFunctionsOnASingleLine: Inline
+AllowShortIfStatementsOnASingleLine: false
+IndentCaseLabels: false
+ColumnLimit: 100
+PointerBindsToType: true
+SpacesBeforeTrailingComments: 2
diff --git a/keystore/Android.mk b/keystore/Android.mk
index 8bf2852..eb9dd87 100644
--- a/keystore/Android.mk
+++ b/keystore/Android.mk
@@ -65,3 +65,19 @@
 LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
 LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
 include $(BUILD_SHARED_LIBRARY)
+
+# Library for unit tests
+include $(CLEAR_VARS)
+ifeq ($(USE_32_BIT_KEYSTORE), true)
+LOCAL_MULTILIB := 32
+endif
+include external/libcxx/libcxx.mk
+LOCAL_CFLAGS := -Wall -Wextra -Werror
+LOCAL_SRC_FILES := auth_token_table.cpp
+LOCAL_MODULE := libkeystore_test
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
+LOCAL_STATIC_LIBRARIES := libgtest_main
+LOCAL_SHARED_LIBRARIES := libkeymaster_messages
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+include $(BUILD_STATIC_LIBRARY)
diff --git a/keystore/auth_token_table.cpp b/keystore/auth_token_table.cpp
new file mode 100644
index 0000000..2ae10a0
--- /dev/null
+++ b/keystore/auth_token_table.cpp
@@ -0,0 +1,198 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "auth_token_table.h"
+
+#include <assert.h>
+#include <time.h>
+
+#include <algorithm>
+
+#include <keymaster/google_keymaster_utils.h>
+#include <keymaster/logger.h>
+
+namespace keymaster {
+
+//
+// Some trivial template wrappers around std algorithms, so they take containers not ranges.
+//
+template <typename Container, typename Predicate>
+typename Container::iterator find_if(Container& container, Predicate pred) {
+    return std::find_if(container.begin(), container.end(), pred);
+}
+
+template <typename Container, typename Predicate>
+typename Container::iterator remove_if(Container& container, Predicate pred) {
+    return std::remove_if(container.begin(), container.end(), pred);
+}
+
+template <typename Container> typename Container::iterator min_element(Container& container) {
+    return std::min_element(container.begin(), container.end());
+}
+
+time_t clock_gettime_raw() {
+    struct timespec time;
+    clock_gettime(CLOCK_MONOTONIC_RAW, &time);
+    return time.tv_sec;
+}
+
+void AuthTokenTable::AddAuthenticationToken(const hw_auth_token_t* auth_token) {
+    Entry new_entry(auth_token, clock_function_());
+    RemoveEntriesSupersededBy(new_entry);
+    if (entries_.size() >= max_entries_) {
+        LOG_W("Auth token table filled up; replacing oldest entry", 0);
+        *min_element(entries_) = std::move(new_entry);
+    } else {
+        entries_.push_back(std::move(new_entry));
+    }
+}
+
+inline bool KeyRequiresAuthentication(const AuthorizationSet& key_info) {
+    return key_info.find(TAG_NO_AUTH_REQUIRED) == -1;
+}
+
+inline bool KeyRequiresAuthPerOperation(const AuthorizationSet& key_info) {
+    return key_info.find(TAG_AUTH_TIMEOUT) == -1;
+}
+
+AuthTokenTable::Error AuthTokenTable::FindAuthorization(const AuthorizationSet& key_info,
+                                                        keymaster_operation_handle_t op_handle,
+                                                        const hw_auth_token_t** found) {
+    if (!KeyRequiresAuthentication(key_info))
+        return AUTH_NOT_REQUIRED;
+
+    hw_authenticator_type_t auth_type = HW_AUTH_NONE;
+    key_info.GetTagValue(TAG_USER_AUTH_TYPE, &auth_type);
+
+    std::vector<uint64_t> key_sids;
+    ExtractSids(key_info, &key_sids);
+
+    if (KeyRequiresAuthPerOperation(key_info))
+        return FindAuthPerOpAuthorization(key_sids, auth_type, op_handle, found);
+    else
+        return FindTimedAuthorization(key_sids, auth_type, key_info, found);
+}
+
+AuthTokenTable::Error AuthTokenTable::FindAuthPerOpAuthorization(
+    const std::vector<uint64_t>& sids, hw_authenticator_type_t auth_type,
+    keymaster_operation_handle_t op_handle, const hw_auth_token_t** found) {
+    if (op_handle == 0)
+        return OP_HANDLE_REQUIRED;
+
+    auto matching_op = find_if(
+        entries_, [&](Entry& e) { return e.token()->challenge == op_handle && !e.completed(); });
+
+    if (matching_op == entries_.end())
+        return AUTH_TOKEN_NOT_FOUND;
+
+    if (!matching_op->SatisfiesAuth(sids, auth_type))
+        return AUTH_TOKEN_WRONG_SID;
+
+    *found = matching_op->token();
+    return OK;
+}
+
+AuthTokenTable::Error AuthTokenTable::FindTimedAuthorization(const std::vector<uint64_t>& sids,
+                                                             hw_authenticator_type_t auth_type,
+                                                             const AuthorizationSet& key_info,
+                                                             const hw_auth_token_t** found) {
+    Entry* newest_match = NULL;
+    for (auto& entry : entries_)
+        if (entry.SatisfiesAuth(sids, auth_type) && entry.is_newer_than(newest_match))
+            newest_match = &entry;
+
+    if (!newest_match)
+        return AUTH_TOKEN_NOT_FOUND;
+
+    uint32_t timeout;
+    key_info.GetTagValue(TAG_AUTH_TIMEOUT, &timeout);
+    time_t now = clock_function_();
+    if (static_cast<int64_t>(newest_match->time_received()) + timeout < static_cast<int64_t>(now))
+        return AUTH_TOKEN_EXPIRED;
+
+    newest_match->UpdateLastUse(now);
+    *found = newest_match->token();
+    return OK;
+}
+
+void AuthTokenTable::ExtractSids(const AuthorizationSet& key_info, std::vector<uint64_t>* sids) {
+    assert(sids);
+    for (auto& param : key_info)
+        if (param.tag == TAG_USER_SECURE_ID)
+            sids->push_back(param.long_integer);
+}
+
+void AuthTokenTable::RemoveEntriesSupersededBy(const Entry& entry) {
+    entries_.erase(remove_if(entries_, [&](Entry& e) { return entry.Supersedes(e); }),
+                   entries_.end());
+}
+
+bool AuthTokenTable::IsSupersededBySomeEntry(const Entry& entry) {
+    return std::any_of(entries_.begin(), entries_.end(),
+                       [&](Entry& e) { return e.Supersedes(entry); });
+}
+
+void AuthTokenTable::MarkCompleted(const keymaster_operation_handle_t op_handle) {
+    auto found = find_if(entries_, [&](Entry& e) { return e.token()->challenge == op_handle; });
+    if (found == entries_.end())
+        return;
+
+    assert(!IsSupersededBySomeEntry(*found));
+    found->mark_completed();
+
+    if (IsSupersededBySomeEntry(*found))
+        entries_.erase(found);
+}
+
+AuthTokenTable::Entry::Entry(const hw_auth_token_t* token, time_t current_time)
+    : token_(token), time_received_(current_time), last_use_(current_time),
+      operation_completed_(token_->challenge == 0) {
+}
+
+uint32_t AuthTokenTable::Entry::timestamp_host_order() const {
+    return ntoh(token_->timestamp);
+}
+
+hw_authenticator_type_t AuthTokenTable::Entry::authenticator_type() const {
+    hw_authenticator_type_t result = static_cast<hw_authenticator_type_t>(
+        ntoh(static_cast<uint32_t>(token_->authenticator_type)));
+    return result;
+}
+
+bool AuthTokenTable::Entry::SatisfiesAuth(const std::vector<uint64_t>& sids,
+                                          hw_authenticator_type_t auth_type) {
+    for (auto sid : sids)
+        if ((sid == token_->authenticator_id) ||
+            (sid == token_->user_id && (auth_type & authenticator_type()) != 0))
+            return true;
+    return false;
+}
+
+void AuthTokenTable::Entry::UpdateLastUse(time_t time) {
+    this->last_use_ = time;
+}
+
+bool AuthTokenTable::Entry::Supersedes(const Entry& entry) const {
+    if (!entry.completed())
+        return false;
+
+    return (token_->user_id == entry.token_->user_id &&
+            token_->authenticator_type == entry.token_->authenticator_type &&
+            token_->authenticator_type == entry.token_->authenticator_type &&
+            timestamp_host_order() > entry.timestamp_host_order());
+}
+
+}  // namespace keymaster
diff --git a/keystore/auth_token_table.h b/keystore/auth_token_table.h
new file mode 100644
index 0000000..d1184e9
--- /dev/null
+++ b/keystore/auth_token_table.h
@@ -0,0 +1,160 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <memory>
+#include <vector>
+
+#include <hardware/hw_auth_token.h>
+#include <keymaster/authorization_set.h>
+
+#ifndef SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
+#define SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
+
+namespace keymaster {
+
+namespace test {
+class AuthTokenTableTest;
+}  // namespace test
+
+time_t clock_gettime_raw();
+
+/**
+ * AuthTokenTable manages a set of received authorization tokens and can provide the appropriate
+ * token for authorizing a key operation.
+ *
+ * To keep the table from growing without bound, superseded entries are removed when possible, and
+ * least recently used entries are automatically pruned when when the table exceeds a size limit,
+ * which is expected to be relatively small, since the implementation uses a linear search.
+ */
+class AuthTokenTable {
+  public:
+    AuthTokenTable(size_t max_entries = 32, time_t (*clock_function)() = clock_gettime_raw)
+        : max_entries_(max_entries), clock_function_(clock_function) {}
+
+    enum Error {
+        OK,
+        AUTH_NOT_REQUIRED = -1,
+        AUTH_TOKEN_EXPIRED = -2,    // Found a matching token, but it's too old.
+        AUTH_TOKEN_WRONG_SID = -3,  // Found a token with the right challenge, but wrong SID.  This
+                                    // most likely indicates that the authenticator was updated
+                                    // (e.g. new fingerprint enrolled).
+        OP_HANDLE_REQUIRED = -4,    // The key requires auth per use but op_handle was zero.
+        AUTH_TOKEN_NOT_FOUND = -5,
+    };
+
+    /**
+     * Add an authorization token to the table.  The table takes ownership of the argument.
+     */
+    void AddAuthenticationToken(const hw_auth_token_t* token);
+
+    /**
+     * Find an authorization token that authorizes the operation specified by \p operation_handle on
+     * a key with the characteristics specified in \p key_info.
+     *
+     * This method is O(n * m), where n is the number of KM_TAG_USER_SECURE_ID entries in key_info
+     * and m is the number of entries in the table.  It could be made better, but n and m should
+     * always be small.
+     *
+     * The table retains ownership of the returned object.
+     */
+    Error FindAuthorization(const AuthorizationSet& key_info,
+                            keymaster_operation_handle_t op_handle, const hw_auth_token_t** found);
+
+    /**
+     * Find an authorization token that authorizes the operation specified by \p operation_handle on
+     * a key with the characteristics specified in \p key_info.
+     *
+     * This method is O(n * m), where n is the number of KM_TAG_USER_SECURE_ID entries in key_info
+     * and m is the number of entries in the table.  It could be made better, but n and m should
+     * always be small.
+     *
+     * The table retains ownership of the returned object.
+     */
+    Error FindAuthorization(const keymaster_key_param_t* params, size_t params_count,
+                            keymaster_operation_handle_t op_handle, const hw_auth_token_t** found) {
+        return FindAuthorization(AuthorizationSet(params, params_count), op_handle, found);
+    }
+
+    /**
+     * Mark operation completed.  This allows tokens associated with the specified operation to be
+     * superseded by new tokens.
+     */
+    void MarkCompleted(const keymaster_operation_handle_t op_handle);
+
+    size_t size() { return entries_.size(); }
+
+  private:
+    friend class AuthTokenTableTest;
+
+    class Entry {
+      public:
+        Entry(const hw_auth_token_t* token, time_t current_time);
+        Entry(Entry&& entry) { *this = std::move(entry); }
+
+        void operator=(Entry&& rhs) {
+            token_ = std::move(rhs.token_);
+            time_received_ = rhs.time_received_;
+            last_use_ = rhs.last_use_;
+            operation_completed_ = rhs.operation_completed_;
+        }
+
+        bool operator<(const Entry& rhs) const { return last_use_ < rhs.last_use_; }
+
+        void UpdateLastUse(time_t time);
+
+        bool Supersedes(const Entry& entry) const;
+        bool SatisfiesAuth(const std::vector<uint64_t>& sids, hw_authenticator_type_t auth_type);
+
+        bool is_newer_than(const Entry* entry) {
+            if (!entry)
+                return true;
+            return timestamp_host_order() > entry->timestamp_host_order();
+        }
+
+        void mark_completed() { operation_completed_ = true; }
+
+        const hw_auth_token_t* token() { return token_.get(); }
+        time_t time_received() const { return time_received_; }
+        bool completed() const { return operation_completed_; }
+        uint32_t timestamp_host_order() const;
+        hw_authenticator_type_t authenticator_type() const;
+
+      private:
+        std::unique_ptr<const hw_auth_token_t> token_;
+        time_t time_received_;
+        time_t last_use_;
+        bool operation_completed_;
+    };
+
+    Error FindAuthPerOpAuthorization(const std::vector<uint64_t>& sids,
+                                     hw_authenticator_type_t auth_type,
+                                     keymaster_operation_handle_t op_handle,
+                                     const hw_auth_token_t** found);
+    Error FindTimedAuthorization(const std::vector<uint64_t>& sids,
+                                 hw_authenticator_type_t auth_type,
+                                 const AuthorizationSet& key_info, const hw_auth_token_t** found);
+    void ExtractSids(const AuthorizationSet& key_info, std::vector<uint64_t>* sids);
+    void RemoveEntriesSupersededBy(const Entry& entry);
+    bool IsSupersededBySomeEntry(const Entry& entry);
+
+    std::vector<Entry> entries_;
+    size_t max_entries_;
+    time_t (*clock_function_)();
+};
+
+}  // namespace keymaster
+
+#endif  // SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
diff --git a/keystore/tests/Android.mk b/keystore/tests/Android.mk
new file mode 100644
index 0000000..6374896
--- /dev/null
+++ b/keystore/tests/Android.mk
@@ -0,0 +1,32 @@
+#
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+LOCAL_PATH := $(call my-dir)
+
+# Unit test for AuthTokenTable
+include $(CLEAR_VARS)
+ifeq ($(USE_32_BIT_KEYSTORE), true)
+LOCAL_MULTILIB := 32
+endif
+include external/libcxx/libcxx.mk
+LOCAL_CFLAGS := -Wall -Wextra -Werror
+LOCAL_SRC_FILES := auth_token_table_test.cpp
+LOCAL_MODULE := auth_token_table_test
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
+LOCAL_STATIC_LIBRARIES := libgtest_main libkeystore_test
+LOCAL_SHARED_LIBRARIES := libkeymaster_messages
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+include $(BUILD_NATIVE_TEST)
diff --git a/keystore/tests/Makefile b/keystore/tests/Makefile
new file mode 100644
index 0000000..5c1117f
--- /dev/null
+++ b/keystore/tests/Makefile
@@ -0,0 +1,116 @@
+##########
+# This makefile builds local unit tests that run locally on the development machine.  Note
+# that it may be necessary to install some libraries on the dev maching to make the tests
+# build.
+#
+# The same unit tests are also built by Android.mk to run on the target device.  The tests
+# should always build and pass in both places.  The on-device test is what really matters,
+# of course, but debugging is often somewhat easier on the dev platform.
+##########
+
+BASE=../../../..
+SUBS=system/core \
+	system/keymaster\
+	hardware/libhardware \
+	external/gtest
+GTEST=$(BASE)/external/gtest
+KEYMASTER=$(BASE)/system/keymaster
+
+INCLUDES=$(foreach dir,$(SUBS),-I $(BASE)/$(dir)/include) \
+	-I $(BASE)/libnativehelper/include/nativehelper \
+	-I $(GTEST) -Iinclude
+
+# Add USE_CLANG=1 to the make command line to build with clang, which has better error
+# reporting and diagnoses some conditions that GCC doesn't.
+ifdef USE_CLANG
+CC=/usr/bin/clang
+CXX=/usr/bin/clang
+CLANG_TEST_DEFINE=-DKEYMASTER_CLANG_TEST_BUILD
+COMPILER_SPECIFIC_ARGS=-std=c++11 $(CLANG_TEST_DEFINE)
+else
+COMPILER_SPECIFIC_ARGS=-std=c++0x -fprofile-arcs
+endif
+
+CPPFLAGS=$(INCLUDES) -g -O0 -MD
+CXXFLAGS=-Wall -Werror -Wno-unused -Winit-self -Wpointer-arith	-Wunused-parameter \
+        -Werror=sign-compare -Wmissing-declarations -ftest-coverage -fno-permissive \
+	-Wno-deprecated-declarations -fno-exceptions -DKEYMASTER_NAME_TAGS \
+	$(COMPILER_SPECIFIC_ARGS)
+
+# Uncomment to enable debug logging.
+# CXXFLAGS += -DDEBUG
+
+LDLIBS=-lpthread -lstdc++ -lgcov
+
+# This list of sources is used for dependency generation and cleanup.  Add each new source
+# file here (not headers).
+CPPSRCS=\
+	../auth_token_table.cpp \
+	auth_token_table_test.cpp
+
+# This list of binaries determes what gets built and run.  Add each new test binary here.
+BINARIES=\
+	auth_token_table_test
+
+.PHONY: coverage memcheck massif clean run
+
+%.run: %
+	./$<
+	touch $@
+
+run: $(BINARIES:=.run)
+
+auth_token_table_test: auth_token_table_test.o \
+	../auth_token_table.o \
+	$(GTEST)/src/gtest-all.o \
+	$(KEYMASTER)/authorization_set.o \
+	$(KEYMASTER)/logger.o \
+	$(KEYMASTER)/serializable.o
+
+coverage: coverage.info
+	genhtml coverage.info --output-directory coverage
+
+coverage.info: run
+	lcov --capture --directory=. --directory=.. -b . --output-file coverage.info
+
+%.coverage : %
+	$(MAKE) clean && $(MAKE) $<
+	./$<
+	lcov --capture --directory=. --output-file coverage.info
+	genhtml coverage.info --output-directory coverage
+#UNINIT_OPTS=--track-origins=yes
+UNINIT_OPTS=--undef-value-errors=no
+
+MEMCHECK_OPTS=--leak-check=full \
+	--show-reachable=yes \
+	--vgdb=full \
+	$(UNINIT_OPTS) \
+	--error-exitcode=1
+
+MASSIF_OPTS=--tool=massif \
+	--stacks=yes
+
+%.memcheck : %
+	valgrind $(MEMCHECK_OPTS) ./$< && \
+	touch $@
+
+%.massif : %
+	valgrind $(MASSIF_OPTS) --massif-out-file=$@ ./$<
+
+memcheck: $(BINARIES:=.memcheck)
+
+massif: $(BINARIES:=.massif)
+
+OBJS=$(CPPSRCS:.cpp=.o)
+DEPS=$(CPPSRCS:.cpp=.d)
+GCOV=$(CPPSRCS:.cpp=.gcov) $(CPPSRCS:.cpp=.gcda) $(CPPSRCS:.cpp=.gcno)
+
+clean:
+	rm -f $(OBJS) $(DEPS) $(BINARIES) $(GCOV) \
+		$(BINARIES:=.run) $(BINARIES:=.memcheck) $(BINARIES:=.massif) \
+		*gcov *gcno *gcda coverage.info
+	rm -rf coverage
+
+-include $(CPPSRCS:.cpp=.d)
+-include $(CCSRCS:.cc=.d)
+
diff --git a/keystore/tests/auth_token_table_test.cpp b/keystore/tests/auth_token_table_test.cpp
new file mode 100644
index 0000000..0f74e77
--- /dev/null
+++ b/keystore/tests/auth_token_table_test.cpp
@@ -0,0 +1,391 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gtest/gtest.h>
+
+#include <keymaster/google_keymaster_utils.h>
+#include <keymaster/logger.h>
+
+#include "../auth_token_table.h"
+
+using std::vector;
+
+int main(int argc, char** argv) {
+    ::testing::InitGoogleTest(&argc, argv);
+    int result = RUN_ALL_TESTS();
+}
+
+inline bool operator==(const hw_auth_token_t& a, const hw_auth_token_t& b) {
+    return (memcmp(&a, &b, sizeof(a)) == 0);
+}
+
+namespace keymaster {
+namespace test {
+
+class StdoutLogger : public Logger {
+  public:
+    StdoutLogger() { set_instance(this); }
+
+    int log_msg(LogLevel level, const char* fmt, va_list args) const {
+        int output_len = 0;
+        switch (level) {
+        case DEBUG_LVL:
+            output_len = printf("DEBUG: ");
+            break;
+        case INFO_LVL:
+            output_len = printf("INFO: ");
+            break;
+        case WARNING_LVL:
+            output_len = printf("WARNING: ");
+            break;
+        case ERROR_LVL:
+            output_len = printf("ERROR: ");
+            break;
+        case SEVERE_LVL:
+            output_len = printf("SEVERE: ");
+            break;
+        }
+
+        output_len += vprintf(fmt, args);
+        output_len += printf("\n");
+        return output_len;
+    }
+};
+
+StdoutLogger logger;
+
+TEST(AuthTokenTableTest, Create) {
+    AuthTokenTable table;
+}
+
+static hw_auth_token_t* make_token(uint64_t rsid, uint64_t ssid = 0, uint64_t challenge = 0,
+                                   uint32_t timestamp = 0) {
+    hw_auth_token_t* token = new hw_auth_token_t;
+    token->user_id = rsid;
+    token->authenticator_id = ssid;
+    token->authenticator_type = hton(static_cast<uint32_t>(HW_AUTH_PASSWORD));
+    token->challenge = challenge;
+    token->timestamp = hton(timestamp);
+    return token;
+}
+
+static AuthorizationSet make_set(uint64_t rsid, uint32_t timeout = 10000) {
+    AuthorizationSetBuilder builder;
+    builder.Authorization(TAG_USER_ID, 10)
+        .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD)
+        .Authorization(TAG_USER_SECURE_ID, rsid);
+    // Use timeout == 0 to indicate tags that require auth per operation.
+    if (timeout != 0)
+        builder.Authorization(TAG_AUTH_TIMEOUT, timeout);
+    return builder.build();
+}
+
+// Tests obviously run so fast that a real-time clock with a one-second granularity rarely changes
+// output during a test run.  This test clock "ticks" one second every time it's called.
+static time_t monotonic_clock() {
+    static time_t time = 0;
+    return time++;
+}
+
+TEST(AuthTokenTableTest, SimpleAddAndFindTokens) {
+    AuthTokenTable table;
+
+    table.AddAuthenticationToken(make_token(1, 2));
+    table.AddAuthenticationToken(make_token(3, 4));
+    EXPECT_EQ(2U, table.size());
+
+    const hw_auth_token_t* found;
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(1U, found->user_id);
+    EXPECT_EQ(2U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(1U, found->user_id);
+    EXPECT_EQ(2U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+    EXPECT_EQ(3U, found->user_id);
+    EXPECT_EQ(4U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(3U, found->user_id);
+    EXPECT_EQ(4U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+}
+
+TEST(AuthTokenTableTest, TableOverflow) {
+    AuthTokenTable table(3, monotonic_clock);
+
+    table.AddAuthenticationToken(make_token(1));
+    table.AddAuthenticationToken(make_token(2));
+    table.AddAuthenticationToken(make_token(3));
+
+    const hw_auth_token_t* found;
+
+    // All three should be in the table.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(4));
+
+    // Oldest should be gone.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1), 0, &found));
+
+    // Others should be there, including the new one (4).  Search for it first, then the others, so
+    // 4 becomes the least recently used.
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(5));
+
+    // 5 should have replaced 4.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(6));
+    table.AddAuthenticationToken(make_token(7));
+
+    // 2 and 5 should be gone
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(6), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(7), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(8));
+    table.AddAuthenticationToken(make_token(9));
+    table.AddAuthenticationToken(make_token(10));
+
+    // Only the three most recent should be there.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(3), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(6), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(7), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(8), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(9), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(10), 0, &found));
+}
+
+TEST(AuthTokenTableTest, AuthenticationNotRequired) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    EXPECT_EQ(AuthTokenTable::AUTH_NOT_REQUIRED,
+              table.FindAuthorization(AuthorizationSetBuilder().Authorization(TAG_NO_AUTH_REQUIRED),
+                                      0 /* no challenge */, &found));
+}
+
+TEST(AuthTokenTableTest, OperationHandleNotFound) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1, 0, 1, 5));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */),
+                                      2 /* non-matching challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1, 0 /* no timeout */),
+                                                          1 /* matching challenge */, &found));
+    table.MarkCompleted(1);
+    EXPECT_EQ(
+        AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+        table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* used challenge */, &found));
+}
+
+TEST(AuthTokenTableTest, OperationHandleRequired) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1));
+    EXPECT_EQ(
+        AuthTokenTable::OP_HANDLE_REQUIRED,
+        table.FindAuthorization(make_set(1, 0 /* no timeout */), 0 /* no op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, AuthSidChanged) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1, 3, /* op handle */ 1));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_WRONG_SID,
+              table.FindAuthorization(make_set(2, 0 /* no timeout */), 1 /* op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, TokenExpired) {
+    AuthTokenTable table(5, monotonic_clock);
+    const hw_auth_token_t* found;
+
+    auto key_info = make_set(1, 5 /* five second timeout */);
+
+    // monotonic_clock "ticks" one second each time it's called, which is once per request, so the
+    // sixth request should fail, since key_info says the key is good for five seconds.
+    //
+    // Note that this tests the decision of the AuthTokenTable to reject a request it knows is
+    // expired.  An additional check of the secure timestamp (in the token) will be made by
+    // keymaster when the found token is passed to it.
+    table.AddAuthenticationToken(make_token(1, 0));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_EXPIRED,
+              table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, MarkNonexistentEntryCompleted) {
+    AuthTokenTable table;
+    // Marking a nonexistent entry completed is ignored.  This test is mainly for code coverage.
+    table.MarkCompleted(1);
+}
+
+TEST(AuthTokenTableTest, SupersededEntries) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    // Add two identical tokens, without challenges.  The second should supersede the first, based
+    // on timestamp (fourth arg to make_token).
+    table.AddAuthenticationToken(make_token(1, 0, 0, 0));
+    table.AddAuthenticationToken(make_token(1, 0, 0, 1));
+    EXPECT_EQ(1U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(1U, ntoh(found->timestamp));
+
+    // Add a third token, this with a different RSID.  It should not be superseded.
+    table.AddAuthenticationToken(make_token(2, 0, 0, 2));
+    EXPECT_EQ(2U, table.size());
+
+    // Add two more, superseding each of the two in the table.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 3));
+    table.AddAuthenticationToken(make_token(2, 0, 0, 4));
+    EXPECT_EQ(2U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(3U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(4U, ntoh(found->timestamp));
+
+    // Add another, this one with a challenge value.  It should supersede the old one since it is
+    // newer, and matches other than the challenge.
+    table.AddAuthenticationToken(make_token(1, 0, 1, 5));
+    EXPECT_EQ(2U, table.size());
+
+    // And another, also with a challenge.  Because of the challenge values, the one just added
+    // cannot be superseded.
+    table.AddAuthenticationToken(make_token(1, 0, 2, 6));
+    EXPECT_EQ(3U, table.size());
+
+    // Should be able to find each of them, by specifying their challenge, with a key that is not
+    // timed (timed keys don't care about challenges).
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout*/), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+
+    // Add another, without a challenge, and the same timestamp as the last one.  This new one
+    // actually could be considered already-superseded, but the table doesn't handle that case,
+    // since it seems unlikely to occur in practice.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 6));
+    EXPECT_EQ(4U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+
+    // Add another without a challenge but an increased timestamp. This should supersede the
+    // previous challenge-free entry.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 7));
+    EXPECT_EQ(4U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(7U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 2 as complete.  Since there's a newer challenge-free entry, the
+    // challenge entry will be superseded.
+    table.MarkCompleted(2);
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(7U, ntoh(found->timestamp));
+
+    // Add another SID 1 entry with a challenge.  It supersedes the previous SID 1 entry with
+    // no challenge (timestamp 7), but not the one with challenge 1 (timestamp 5).
+    table.AddAuthenticationToken(make_token(1, 0, 3, 8));
+    EXPECT_EQ(3U, table.size());
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 3 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+
+    // SID 2 entry is still there.
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0 /* challenge */, &found));
+    EXPECT_EQ(4U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 3 as complete.  Since the older challenge 1 entry is
+    // incomplete, nothing is superseded.
+    table.MarkCompleted(3);
+    EXPECT_EQ(3U, table.size());
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 1 as complete.  Since there's a newer one (with challenge 3,
+    // completed), the challenge 1 entry is superseded and removed.
+    table.MarkCompleted(1);
+    EXPECT_EQ(2U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+}
+
+}  // namespace keymaster
+}  // namespace test