diff --git a/syncbase/permissions_internal_test.go b/syncbase/permissions_internal_test.go
new file mode 100644
index 0000000..6447eef
--- /dev/null
+++ b/syncbase/permissions_internal_test.go
@@ -0,0 +1,10 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package syncbase
+
+func NewNonexistentBatchForTest(db Database) BatchDatabase {
+	d := db.(*database)
+	return newBatch(d.parentFullName, d.id, "sdeadbeefdeadbeef") // likely doesn't exist
+}
diff --git a/syncbase/permissions_test.go b/syncbase/permissions_test.go
index b8ffd4f..2837648 100644
--- a/syncbase/permissions_test.go
+++ b/syncbase/permissions_test.go
@@ -7,6 +7,7 @@
 import (
 	"fmt"
 	"reflect"
+	"strings"
 	"testing"
 	"time"
 
@@ -21,6 +22,7 @@
 	vsecurity "v.io/x/ref/lib/security"
 	_ "v.io/x/ref/runtime/factories/roaming"
 	tu "v.io/x/ref/services/syncbase/testutil"
+	vtestutil "v.io/x/ref/test/testutil"
 )
 
 type serviceTest struct {
@@ -64,17 +66,31 @@
 	return err
 }
 
+// checkLayer specifies the layer where the primary authorization and
+// existence check of the method is carried out.
+type checkLayer string
+
+const (
+	clService    checkLayer = "S"
+	clDatabase   checkLayer = "D"
+	clCollection checkLayer = "C"
+	clRow        checkLayer = "R"
+	clSyncgroup  checkLayer = "G"
+)
+
 type securitySpecTest struct {
-	layer   interface{}
-	name    string
-	pattern string
+	layer      interface{}
+	name       string
+	checkLayer checkLayer
+	pattern    string
 }
 
 type securitySpecTestGroup struct {
-	layer    interface{}
-	name     string
-	patterns []string
-	mutating bool
+	layer      interface{}
+	name       string
+	checkLayer checkLayer
+	patterns   []string
+	mutating   bool
 }
 
 // TODO(rogulenko): Add more test groups.
@@ -85,40 +101,45 @@
 			_, err := wire.ServiceClient(s.FullName()).DevModeGetTime(ctx)
 			return err
 		}},
-		name:     "service.DevModeGetTime",
-		patterns: []string{"A___"},
+		name:       "service.DevModeGetTime",
+		checkLayer: clService,
+		patterns:   []string{"A___"},
 	},
 	{
 		layer: serviceTest{f: func(ctx *context.T, s syncbase.Service) error {
 			return wire.ServiceClient(s.FullName()).DevModeUpdateVClock(ctx, wire.DevModeUpdateVClockOpts{})
 		}},
-		name:     "service.DevModeUpdateVClock",
-		patterns: []string{"A___"},
-		mutating: true,
+		name:       "service.DevModeUpdateVClock",
+		checkLayer: clService,
+		patterns:   []string{"A___"},
+		mutating:   true,
 	},
 	{
 		layer: serviceTest{f: func(ctx *context.T, s syncbase.Service) error {
 			_, _, err := s.GetPermissions(ctx)
 			return err
 		}},
-		name:     "service.GetPermissions",
-		patterns: []string{"A___"},
+		name:       "service.GetPermissions",
+		checkLayer: clService,
+		patterns:   []string{"A___"},
 	},
 	{
 		layer: serviceTest{f: func(ctx *context.T, s syncbase.Service) error {
 			return s.SetPermissions(ctx, tu.DefaultPerms(access.AllTypicalTags(), "root"), "")
 		}},
-		name:     "service.SetPermissions",
-		patterns: []string{"A___"},
-		mutating: true,
+		name:       "service.SetPermissions",
+		checkLayer: clService,
+		patterns:   []string{"A___"},
+		mutating:   true,
 	},
 	{
 		layer: serviceTest{f: func(ctx *context.T, s syncbase.Service) error {
 			_, err := s.ListDatabases(ctx)
 			return err
 		}},
-		name:     "service.ListDatabases",
-		patterns: []string{"R___"},
+		name:       "service.ListDatabases",
+		checkLayer: clService,
+		patterns:   []string{"R___"},
 	},
 
 	// Database tests.
@@ -126,74 +147,86 @@
 		layer: serviceTest{f: func(ctx *context.T, s syncbase.Service) error {
 			return s.DatabaseForId(wire.Id{"root", "dNew"}, nil).Create(ctx, tu.DefaultPerms(wire.AllDatabaseTags, "root"))
 		}},
-		name:     "database.Create",
-		patterns: []string{"W___"},
-		mutating: true,
+		name:       "database.Create",
+		checkLayer: clService,
+		patterns:   []string{"W___"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return d.Destroy(ctx)
 		}},
-		name:     "database.Destroy",
-		patterns: []string{"XA__", "A___"},
-		mutating: true,
+		name:       "database.Destroy",
+		checkLayer: clDatabase, // (also Service, depending on specific perms)
+		patterns:   []string{"XA__", "A___"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			_, err := d.Exists(ctx)
 			return err
 		}},
-		name:     "database.Exists",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__", "R___", "W___"},
+		name:       "database.Exists",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__", "R___", "W___"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			_, _, err := d.GetPermissions(ctx)
 			return err
 		}},
-		name:     "database.GetPermissions",
-		patterns: []string{"XA__"},
+		name:       "database.GetPermissions",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return d.SetPermissions(ctx, tu.DefaultPerms(wire.AllDatabaseTags, "root"), "")
 		}},
-		name:     "database.SetPermissions",
-		patterns: []string{"XA__"},
-		mutating: true,
+		name:       "database.SetPermissions",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			_, err := d.ListCollections(ctx)
 			return err
 		}},
-		name:     "database.ListCollections - nonbatch",
-		patterns: []string{"XR__"},
+		name:       "database.ListCollections - nonbatch",
+		checkLayer: clDatabase,
+		patterns:   []string{"XR__"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			ws := d.Watch(ctx, nil, []wire.CollectionRowPattern{util.RowPrefixPattern(wire.Id{"u", "c"}, "")})
+			defer ws.Cancel()
+			// Advance() will not block indefinitely because at least the root update
+			// is always sent for nil resume marker.
 			ws.Advance()
 			return ws.Err()
 		}},
-		name:     "database.Watch",
-		patterns: []string{"XR__"},
+		name:       "database.Watch",
+		checkLayer: clDatabase,
+		patterns:   []string{"XR__"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			_, err := d.BeginBatch(ctx, wire.BatchOptions{})
 			return err
 		}},
-		name:     "database.BeginBatch",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
+		name:       "database.BeginBatch",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			_, err := d.GetResumeMarker(ctx)
 			return err
 		}},
-		name:     "database.GetResumeMarker",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
+		name:       "database.GetResumeMarker",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
 	},
 	// TODO(ivanpi): Test Exec.
 	// TODO(ivanpi): Test RPC-only methods such as Glob.
@@ -203,25 +236,28 @@
 		layer: batchDatabaseTest{f: func(ctx *context.T, b syncbase.BatchDatabase) error {
 			return b.Commit(ctx)
 		}},
-		name:     "database.Commit",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "database.Commit",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: batchDatabaseTest{f: func(ctx *context.T, b syncbase.BatchDatabase) error {
 			return b.Abort(ctx)
 		}},
-		name:     "database.Abort",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "database.Abort",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: batchDatabaseTest{f: func(ctx *context.T, b syncbase.BatchDatabase) error {
 			_, err := b.ListCollections(ctx)
 			return err
 		}},
-		name:     "database.ListCollections - batch",
-		patterns: []string{"XR__"},
+		name:       "database.ListCollections - batch",
+		checkLayer: clDatabase,
+		patterns:   []string{"XR__"},
 	},
 	// TODO(ivanpi): Test Exec.
 
@@ -234,46 +270,58 @@
 			}
 			return err
 		}},
-		name:     "database.GetSchemaMetadata",
-		patterns: []string{"XR__"},
+		name:       "database.GetSchemaMetadata",
+		checkLayer: clDatabase,
+		patterns:   []string{"XR__"},
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return wire.DatabaseClient(d.FullName()).SetSchemaMetadata(ctx, wire.SchemaMetadata{})
 		}},
-		name:     "database.SetSchemaMetadata",
-		patterns: []string{"XA__"},
-		mutating: true,
+		name:       "database.SetSchemaMetadata",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return wire.DatabaseClient(d.FullName()).PauseSync(ctx)
 		}},
-		name:     "database.PauseSync",
-		patterns: []string{"XA__"},
-		mutating: true,
+		name:       "database.PauseSync",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return wire.DatabaseClient(d.FullName()).ResumeSync(ctx)
 		}},
-		name:     "database.ResumeSync",
-		patterns: []string{"XA__"},
-		mutating: true,
+		name:       "database.ResumeSync",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
+		mutating:   true,
 	},
 	{
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
+			ctx, cancel := context.WithCancel(ctx)
+			defer cancel()
 			s, err := wire.DatabaseClient(d.FullName()).StartConflictResolver(ctx)
 			if err != nil {
 				return err
 			}
-			go s.RecvStream().Advance()
-			<-time.After(1 * time.Second)
-			return s.RecvStream().Err()
+			cancelTimer := time.AfterFunc(5*time.Second, cancel) // slows down only the allowed case
+			defer cancelTimer.Stop()
+			s.RecvStream().Advance()
+			err = s.RecvStream().Err()
+			if verror.ErrorID(err) == verror.ErrCanceled.ID {
+				return nil
+			}
+			return err
 		}},
-		name:     "database.StartConflictResolver",
-		patterns: []string{"XA__"},
-		mutating: true,
+		name:       "database.StartConflictResolver",
+		checkLayer: clDatabase,
+		patterns:   []string{"XA__"},
+		mutating:   true,
 	},
 
 	// Blob manager tests.
@@ -282,9 +330,10 @@
 			_, err := d.CreateBlob(ctx)
 			return err
 		}},
-		name:     "database.CreateBlob",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "database.CreateBlob",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: false, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
@@ -297,33 +346,37 @@
 			}
 			return w.Close()
 		}},
-		name:     "blob.Put",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "blob.Put",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: false, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			return blob.Commit(ctx)
 		}},
-		name:     "blob.Commit",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "blob.Commit",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			_, err := blob.Size(ctx)
 			return err
 		}},
-		name:     "blob.Size",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
+		name:       "blob.Size",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			return expectNotImplemented(blob.Delete(ctx))
 		}},
-		name:     "blob.Delete",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "blob.Delete",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
@@ -331,11 +384,13 @@
 			if err != nil {
 				return err
 			}
+			defer r.Cancel()
 			r.Advance()
 			return r.Err()
 		}},
-		name:     "blob.Get",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
+		name:       "blob.Get",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
@@ -343,36 +398,41 @@
 			if err != nil {
 				return err
 			}
+			defer s.Cancel()
 			s.Advance()
 			return s.Err()
 		}},
-		name:     "blob.Fetch",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "blob.Fetch",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			return expectNotImplemented(blob.Pin(ctx))
 		}},
-		name:     "blob.Pin",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "blob.Pin",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			return expectNotImplemented(blob.Unpin(ctx))
 		}},
-		name:     "blob.Unpin",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "blob.Unpin",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: blobTest{commit: true, f: func(ctx *context.T, d syncbase.Database, blob syncbase.Blob) error {
 			return expectNotImplemented(blob.Keep(ctx, 0))
 		}},
-		name:     "blob.Keep",
-		patterns: []string{"XX__", "XR__", "XW__", "XA__"},
-		mutating: true,
+		name:       "blob.Keep",
+		checkLayer: clDatabase,
+		patterns:   []string{"XX__", "XR__", "XW__", "XA__"},
+		mutating:   true,
 	},
 	// TODO(ivanpi): Test Syncbase-to-Syncbase blob RPCs.
 
@@ -382,8 +442,9 @@
 			_, err := d.ListSyncgroups(ctx)
 			return err
 		}},
-		name:     "database.ListSyncgroups",
-		patterns: []string{"XR__"},
+		name:       "database.ListSyncgroups",
+		checkLayer: clDatabase,
+		patterns:   []string{"XR__"},
 	},
 	{
 		layer: collectionTest{noBatch: true, f: func(ctx *context.T, d syncbase.Database, c syncbase.Collection) error {
@@ -392,50 +453,56 @@
 				Collections: []wire.Id{c.Id()},
 			}, wire.SyncgroupMemberInfo{})
 		}},
-		name:     "syncgroup.Create",
-		patterns: []string{"XWR_"},
-		mutating: true,
+		name:       "syncgroup.Create",
+		checkLayer: clDatabase, // (Collection check is not recursive, Database check is sufficient against leaks locally)
+		patterns:   []string{"XWR_"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			_, err := sg.Join(ctx, "", []string{}, wire.SyncgroupMemberInfo{})
 			return err
 		}},
-		name:     "syncgroup.Join (already joined)",
-		patterns: []string{"XWRR"},
-		mutating: true,
+		name:       "syncgroup.Join (already joined)",
+		checkLayer: clDatabase, // (Collection and Syncgroup check is not recursive, Database check is sufficient against leaks locally)
+		patterns:   []string{"XWRR"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			return expectNotImplemented(sg.Leave(ctx))
 		}},
-		name:     "syncgroup.Leave",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "syncgroup.Leave",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			return expectNotImplemented(sg.Destroy(ctx))
 		}},
-		name:     "syncgroup.Destroy",
-		patterns: []string{"XW_A"},
-		mutating: true,
+		name:       "syncgroup.Destroy",
+		checkLayer: clDatabase, // (Syncgroup check is not recursive, Database check is sufficient against leaks locally)
+		patterns:   []string{"XW_A"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			return expectNotImplemented(sg.Eject(ctx, "root:nobody"))
 		}},
-		name:     "syncgroup.Eject",
-		patterns: []string{"XX_A"},
-		mutating: true,
+		name:       "syncgroup.Eject",
+		checkLayer: clSyncgroup,
+		patterns:   []string{"XX_A"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			_, _, err := sg.GetSpec(ctx)
 			return err
 		}},
-		name:     "syncgroup.GetSpec",
-		patterns: []string{"XX_R"},
+		name:       "syncgroup.GetSpec",
+		checkLayer: clSyncgroup,
+		patterns:   []string{"XX_R"},
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, c syncbase.Collection) error {
@@ -444,17 +511,19 @@
 				Collections: []wire.Id{c.Id()},
 			}, "")
 		}},
-		name:     "syncgroup.SetSpec",
-		patterns: []string{"XX_A"},
-		mutating: true,
+		name:       "syncgroup.SetSpec",
+		checkLayer: clSyncgroup,
+		patterns:   []string{"XX_A"},
+		mutating:   true,
 	},
 	{
 		layer: syncgroupTest{f: func(ctx *context.T, sg syncbase.Syncgroup, _ syncbase.Collection) error {
 			_, err := sg.GetMembers(ctx)
 			return err
 		}},
-		name:     "syncgroup.GetMembers",
-		patterns: []string{"XX_R"},
+		name:       "syncgroup.GetMembers",
+		checkLayer: clSyncgroup,
+		patterns:   []string{"XX_R"},
 	},
 	// TODO(ivanpi): Test Syncbase-to-Syncbase sync RPCs.
 
@@ -463,58 +532,66 @@
 		layer: databaseTest{f: func(ctx *context.T, d syncbase.Database) error {
 			return d.CollectionForId(wire.Id{"root", "cNew"}).Create(ctx, tu.DefaultPerms(wire.AllCollectionTags, "root"))
 		}},
-		name:     "collection.Create",
-		patterns: []string{"XW__"},
-		mutating: true,
+		name:       "collection.Create",
+		checkLayer: clDatabase,
+		patterns:   []string{"XW__"},
+		mutating:   true,
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			return c.Destroy(ctx)
 		}},
-		name:     "collection.Destroy",
-		patterns: []string{"XXA_", "XA__"},
-		mutating: true,
+		name:       "collection.Destroy",
+		checkLayer: clCollection, // (also Database, depending on specific perms)
+		patterns:   []string{"XXA_", "XA__"},
+		mutating:   true,
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			_, err := c.Exists(ctx)
 			return err
 		}},
-		name:     "collection.Exists",
-		patterns: []string{"XXR_", "XXW_", "XXA_", "XR__", "XW__"},
+		name:       "collection.Exists",
+		checkLayer: clCollection,
+		patterns:   []string{"XXR_", "XXW_", "XXA_", "XR__", "XW__"},
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			_, err := c.GetPermissions(ctx)
 			return err
 		}},
-		name:     "collection.GetPermissions",
-		patterns: []string{"XXA_"},
+		name:       "collection.GetPermissions",
+		checkLayer: clCollection,
+		patterns:   []string{"XXA_"},
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			return c.SetPermissions(ctx, tu.DefaultPerms(wire.AllCollectionTags, "root"))
 		}},
-		name:     "collection.SetPermissions",
-		patterns: []string{"XXA_"},
-		mutating: true,
+		name:       "collection.SetPermissions",
+		checkLayer: clCollection,
+		patterns:   []string{"XXA_"},
+		mutating:   true,
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			ss := c.Scan(ctx, syncbase.Prefix(""))
+			defer ss.Cancel()
 			ss.Advance()
 			return ss.Err()
 		}},
-		name:     "collection.Scan",
-		patterns: []string{"XXR_"},
+		name:       "collection.Scan",
+		checkLayer: clCollection,
+		patterns:   []string{"XXR_"},
 	},
 	{
 		layer: collectionTest{f: func(ctx *context.T, _ syncbase.Database, c syncbase.Collection) error {
 			return c.DeleteRange(ctx, syncbase.Prefix(""))
 		}},
-		name:     "collection.DeleteRange",
-		patterns: []string{"XXW_"},
-		mutating: true,
+		name:       "collection.DeleteRange",
+		checkLayer: clCollection,
+		patterns:   []string{"XXW_"},
+		mutating:   true,
 	},
 	// TODO(ivanpi): Test RPC-only methods such as Glob. (Note, Glob is non-batch only.)
 
@@ -524,33 +601,37 @@
 			_, err := r.Exists(ctx)
 			return err
 		}},
-		name:     "row.Exists",
-		patterns: []string{"XXR_", "XXW_"},
+		name:       "row.Exists",
+		checkLayer: clRow,
+		patterns:   []string{"XXR_", "XXW_"},
 	},
 	{
 		layer: rowTest{f: func(ctx *context.T, r syncbase.Row) error {
 			var value string
 			return r.Get(ctx, &value)
 		}},
-		name:     "row.Get",
-		patterns: []string{"XXR_"},
+		name:       "row.Get",
+		checkLayer: clCollection, // (Row check is only meaningful for Exists since Rows don't have separate ACLs)
+		patterns:   []string{"XXR_"},
 	},
 	{
 		layer: rowTest{f: func(ctx *context.T, r syncbase.Row) error {
 			value := "NCC-1701-D"
 			return r.Put(ctx, &value)
 		}},
-		name:     "row.Put",
-		patterns: []string{"XXW_"},
-		mutating: true,
+		name:       "row.Put",
+		checkLayer: clCollection,
+		patterns:   []string{"XXW_"},
+		mutating:   true,
 	},
 	{
 		layer: rowTest{f: func(ctx *context.T, r syncbase.Row) error {
 			return r.Delete(ctx)
 		}},
-		name:     "row.Delete",
-		patterns: []string{"XXW_"},
-		mutating: true,
+		name:       "row.Delete",
+		checkLayer: clCollection,
+		patterns:   []string{"XXW_"},
+		mutating:   true,
 	},
 }
 
@@ -597,19 +678,69 @@
 			tu.Fatalf(t, "test %v (batch: %v) didn't fail with ErrNoAccess or ErrNoExistOrNoAccess error: %v", test, batch, err)
 		}
 	}
-	runTests(t, checkDenied, deniedTests...)
+	runTests(t, csAll, checkDenied, deniedTests...)
 
 	checkAllowed := func(t *testing.T, test securitySpecTest, batch bool, err error) {
 		if err != nil {
 			tu.Fatalf(t, "test %v (batch: %v) failed with non-nil error: %v", test, batch, err)
 		}
 	}
-	runTests(t, checkAllowed, staticAllowedTests...)
+	runTests(t, csAll, checkAllowed, staticAllowedTests...)
 	for _, test := range mutatingAllowedTests {
-		runTests(t, checkAllowed, test)
+		runTests(t, csAll, checkAllowed, test)
 	}
 }
 
+// TestErrorExistLeakSpec tests that the Syncbase RPCs do not leak information
+// about database, collection, syncgroup [non]existence to unauthorized clients.
+// It uses the test group infrastructure from TestSecuritySpec.
+//
+// For simplicity and speed, tests are run only with denied tests, avoiding
+// mutable tests. Each test group specifies the layer where its primary
+// authorization and existence check is carried out in checkLayer.
+//
+// All tests are run against different configurations of layer existence as
+// specified by createSpec. Batch existence is only relevant for tests that
+// specify batch usage.
+//
+// Since the main intent is to verify that ErrNoExistOrNoAccess is returned
+// consistently when required, variance in other errors for different RPCs is
+// more loosely checked.
+func TestErrorExistLeakSpec(t *testing.T) {
+	deniedTests, _, _ := prepareTests()
+
+	createSpecs := []string{
+		"",
+		csDatabase,
+		csDatabase + csBatch,
+		csDatabase + csCollection,
+		csDatabase + csBatch + csCollection,
+		csDatabase + csCollection + csRow,
+		csDatabase + csBatch + csCollection + csRow,
+		csDatabase + csCollection + csSyncgroup,
+		csDatabase + csBlob,
+		csAll,
+	}
+	// Race tests run out of memory when all combinations are run. Run on a
+	// representative subset instead.
+	// TODO(ivanpi): Investigate further. Error encountered is:
+	// "ThreadSanitizer: DenseSlabAllocator overflow. Dying."
+	if vtestutil.RaceEnabled {
+		createSpecs = []string{
+			"",
+			csDatabase + csBatch,
+			csDatabase + csCollection + csSyncgroup,
+		}
+	}
+
+	for _, createSpec := range createSpecs {
+		runTests(t, createSpec, makeErrorChecker(createSpec), deniedTests...)
+	}
+
+	// TODO(ivanpi): Consider testing more complex scenarios, such as allowed
+	// patterns and different ACLs inside vs outside batch.
+}
+
 func prepareTests() (deniedTests, staticAllowedTests, mutatingAllowedTests []securitySpecTest) {
 	for _, testGroup := range securitySpecTestGroups {
 		// Collect allowed patterns.
@@ -620,9 +751,10 @@
 		// Fill in allowed test slices.
 		for pattern := range allowedPatterns {
 			test := securitySpecTest{
-				layer:   testGroup.layer,
-				name:    testGroup.name,
-				pattern: pattern,
+				layer:      testGroup.layer,
+				name:       testGroup.name,
+				checkLayer: testGroup.checkLayer,
+				pattern:    pattern,
 			}
 			if testGroup.mutating {
 				mutatingAllowedTests = append(mutatingAllowedTests, test)
@@ -637,7 +769,7 @@
 			for i := 0; i < len(pattern); i++ {
 				if pattern[i] != '_' {
 					patternBytes := []byte(pattern)
-					for _, c := range []byte{'X', 'R', 'W', 'A', '_'} {
+					for _, c := range []byte{'_', 'X', 'R', 'W', 'A'} {
 						patternBytes[i] = c
 						if !isSubsetOfAny(string(patternBytes), allowedPatterns) {
 							deniedPatterns[string(patternBytes)] = true
@@ -649,9 +781,10 @@
 		// Fill in denied test slice.
 		for pattern := range deniedPatterns {
 			test := securitySpecTest{
-				layer:   testGroup.layer,
-				name:    testGroup.name,
-				pattern: pattern,
+				layer:      testGroup.layer,
+				name:       testGroup.name,
+				checkLayer: testGroup.checkLayer,
+				pattern:    pattern,
 			}
 			deniedTests = append(deniedTests, test)
 		}
@@ -659,24 +792,45 @@
 	return
 }
 
+func isSubsetOf(subset, superset string) bool {
+	for i := 0; i < len(superset); i++ {
+		if superset[i] != '_' && superset[i] != subset[i] {
+			return false
+		}
+	}
+	// All perms in subset correspond to the same perm or '_' in superset.
+	return true
+}
+
 func isSubsetOfAny(needle string, haystack map[string]bool) bool {
 	for p := range haystack {
-		isSubset := true
-		for i := 0; i < len(p); i++ {
-			if p[i] != '_' && p[i] != needle[i] {
-				isSubset = false
-				break
-			}
-		}
-		if isSubset {
-			// All perms in needle correspond to the same perm or '_' in p.
+		if isSubsetOf(needle, p) {
 			return true
 		}
 	}
 	return false
 }
 
-func runTests(t *testing.T, check func(t *testing.T, test securitySpecTest, batch bool, err error), tests ...securitySpecTest) {
+const (
+	// createSpec is a concatenation of zero or more of the constants below,
+	// describing which layers should exist for a given test. Layer dependencies
+	// are not automatically handled - if a layer requires another layer, both
+	// layers must be specified.
+	csDatabase   = "D"
+	csBatch      = "T"
+	csCollection = "C"
+	csRow        = "R"
+	csSyncgroup  = "G"
+	csBlob       = "B"
+	csAll        = csDatabase + csBatch + csCollection + csRow + csSyncgroup + csBlob
+)
+
+type checkerFunc func(t *testing.T, test securitySpecTest, batch bool, err error)
+
+// runTest creates the Syncbase hierarchy according to the provided createSpec
+// (see TestErrorExistLeakSpec comment for description) and runs the provided
+// set of tests against it, running checkerFunc
+func runTests(t *testing.T, createSpec string, check checkerFunc, tests ...securitySpecTest) {
 	// Create permissions.
 	servicePerms := makePerms("root:admin", 0, access.AllTypicalTags(), tests...)
 	databasePerms := makePerms("root:admin", 1, wire.AllDatabaseTags, tests...)
@@ -686,51 +840,82 @@
 	// Create service/database/collection/row with permissions above.
 	ctx, adminCtx, sName, rootp, cleanup := tu.SetupOrDieCustom("admin", "server", nil)
 	defer cleanup()
+	// Service
 	s := syncbase.NewService(sName)
 	if err := s.SetPermissions(adminCtx, servicePerms, ""); err != nil {
 		tu.Fatalf(t, "s.SetPermissions failed: %v", err)
 	}
+	// Database
 	d := s.DatabaseForId(wire.Id{"root", "d"}, nil)
-	if err := d.Create(adminCtx, databasePerms); err != nil {
-		tu.Fatalf(t, "d.Create failed: %v", err)
+	if strings.Contains(createSpec, csDatabase) {
+		if err := d.Create(adminCtx, databasePerms); err != nil {
+			tu.Fatalf(t, "d.Create failed: %v", err)
+		}
 	}
+	// Collection
 	c := d.CollectionForId(wire.Id{"root:admin", "c"})
-	if err := c.Create(adminCtx, collectionPerms); err != nil {
-		tu.Fatalf(t, "c.Create failed: %v", err)
+	if strings.Contains(createSpec, csCollection) {
+		if err := c.Create(adminCtx, collectionPerms); err != nil {
+			tu.Fatalf(t, "c.Create failed: %v", err)
+		}
 	}
+	// Row
 	r := c.Row("prefix")
-	if err := r.Put(adminCtx, "value"); err != nil {
-		tu.Fatalf(t, "r.Put failed: %v", err)
+	if strings.Contains(createSpec, csRow) {
+		if err := r.Put(adminCtx, "value"); err != nil {
+			tu.Fatalf(t, "r.Put failed: %v", err)
+		}
 	}
+	// Syncgroup
 	sg := d.SyncgroupForId(wire.Id{"root:admin", "sg"})
-	sgSpec := wire.SyncgroupSpec{
-		Perms:       sgPerms,
-		Collections: []wire.Id{c.Id()},
+	if strings.Contains(createSpec, csSyncgroup) {
+		sgSpec := wire.SyncgroupSpec{
+			Perms:       sgPerms,
+			Collections: []wire.Id{c.Id()},
+		}
+		if err := sg.Create(adminCtx, sgSpec, wire.SyncgroupMemberInfo{}); err != nil {
+			tu.Fatalf(t, "sg.Create failed: %v", err)
+		}
 	}
-	if err := sg.Create(adminCtx, sgSpec, wire.SyncgroupMemberInfo{}); err != nil {
-		tu.Fatalf(t, "sg.Create failed: %v", err)
+	// Blob
+	blobCommitted := d.Blob("_fake_committed")
+	blobUncommitted := d.Blob("_fake_uncommitted")
+	if strings.Contains(createSpec, csBlob) {
+		var err error
+		if blobCommitted, err = d.CreateBlob(adminCtx); err != nil {
+			tu.Fatalf(t, "d.CreateBlob failed: %v", err)
+		}
+		if err = blobCommitted.Commit(adminCtx); err != nil {
+			tu.Fatalf(t, "blobCommitted.Commit failed: %v", err)
+		}
+		if blobUncommitted, err = d.CreateBlob(adminCtx); err != nil {
+			tu.Fatalf(t, "d.CreateBlob failed: %v", err)
+		}
 	}
-	blobCommitted, err := d.CreateBlob(adminCtx)
-	if err != nil {
-		tu.Fatalf(t, "d.CreateBlob failed: %v", err)
-	}
-	if err := blobCommitted.Commit(adminCtx); err != nil {
-		tu.Fatalf(t, "blobCommitted.Commit failed: %v", err)
-	}
-	blobUncommitted, err := d.CreateBlob(adminCtx)
-	if err != nil {
-		tu.Fatalf(t, "d.CreateBlob failed: %v", err)
-	}
-	dBatch, err := d.BeginBatch(adminCtx, wire.BatchOptions{})
-	if err != nil {
-		tu.Fatalf(t, "d.BeginBatch failed: %v", err)
+	// Batch
+	dBatch := syncbase.NewNonexistentBatchForTest(d)
+	if strings.Contains(createSpec, csBatch) {
+		var err error
+		if dBatch, err = d.BeginBatch(adminCtx, wire.BatchOptions{}); err != nil {
+			tu.Fatalf(t, "d.BeginBatch failed: %v", err)
+		}
+		defer dBatch.Abort(adminCtx)
 	}
 	cBatch := dBatch.CollectionForId(c.Id())
 	rBatch := cBatch.Row(r.Key())
 
 	// Verify tests.
 	for i, test := range tests {
-		clientCtx := tu.NewCtx(ctx, rootp, fmt.Sprintf("client%d", i))
+		if filteredPattern := filterPermsPattern(createSpec, test.pattern); filteredPattern != test.pattern {
+			// Skip tests whose ACL patterns are unsatisfiable because the
+			// corresponding layers are missing in createSpec.
+			continue
+		}
+
+		// Note, we run collection and row tests twice against the same hierarchy
+		// (batch and non-batch) even if they are mutable. This should be safe
+		// thanks to batch isolation.
+		clientCtx, cancelClientCtx := context.WithCancel(tu.NewCtx(ctx, rootp, fmt.Sprintf("client%d", i)))
 		switch layer := test.layer.(type) {
 		case serviceTest:
 			check(t, test, false, layer.f(clientCtx, s))
@@ -759,9 +944,26 @@
 		default:
 			tu.Fatalf(t, "test %v: unknown test type", test)
 		}
+		cancelClientCtx()
 	}
 }
 
+// filterPermsPattern filters out (sets to '_') permissions in the pattern that
+// cannot exist because the corresponding layer doesn't exist in createSpec.
+func filterPermsPattern(createSpec, pattern string) string {
+	patternBytes := []byte(pattern)
+	if !strings.Contains(createSpec, csDatabase) {
+		patternBytes[1] = '_'
+	}
+	if !strings.Contains(createSpec, csCollection) {
+		patternBytes[2] = '_'
+	}
+	if !strings.Contains(createSpec, csSyncgroup) {
+		patternBytes[3] = '_'
+	}
+	return string(patternBytes)
+}
+
 // makePerms creates a perms object with permissions for each test.
 // For each test we add a blessing pattern "root:clientXX" with a tag
 // corresponding test.pattern[index].
@@ -781,6 +983,154 @@
 	return util.FilterTags(perms, allowTags...)
 }
 
+// makeErrorChecker builds a checkerFunc for TestErrorExistLeakSpec for the
+// given createSpec.
+func makeErrorChecker(createSpec string) checkerFunc {
+	return func(t *testing.T, test securitySpecTest, batch bool, gotErr error) {
+		filteredPattern := filterPermsPattern(createSpec, test.pattern)
+		if filteredPattern != test.pattern {
+			tu.Fatalf(t, "test didn't filter out pattern %s invalid for createSpec %s", test.pattern, createSpec)
+		}
+
+		assertErrorOneOf := func(wantErrs ...verror.ID) {
+			for _, wantErr := range wantErrs {
+				if verror.ErrorID(gotErr) == wantErr {
+					return
+				}
+			}
+			tu.Fatalf(t, "setup %s, test %v (batch: %v, filtered perms: %s) didn't fail with one of %v, got error: %v", createSpec, test, batch, filteredPattern, wantErrs, gotErr)
+		}
+
+		checkPerms := func(patterns ...string) bool {
+			for _, p := range patterns {
+				if isSubsetOf(filteredPattern, p) {
+					return true
+				}
+			}
+			return false
+		}
+
+		if test.checkLayer == clService {
+			// Service always exists, its methods only fail with ErrNoAccess.
+			assertErrorOneOf(verror.ErrNoAccess.ID)
+			return
+		}
+
+		if !checkPerms("XX__", "XR__", "XW__", "XA__", "R___", "W___") {
+			// Caller is not allowed to know if Database exists, so methods on
+			// Database and above fail with ErrNoExistOrNoAccess.
+			assertErrorOneOf(verror.ErrNoExistOrNoAccess.ID)
+			return
+		}
+		if !strings.Contains(createSpec, csDatabase) {
+			// Database does not exist, so methods on Database and above fail with
+			// ErrNoExist.
+			// Exists and Destroy (idempotent case) return nil error.
+			assertErrorOneOf(verror.ErrorID(nil), verror.ErrNoExist.ID)
+			return
+		}
+		if batch {
+			if !strings.Contains(createSpec, csBatch) {
+				// Client is allowed to know that Database exists, but the batch handle
+				// is invalid.
+				assertErrorOneOf(wire.ErrUnknownBatch.ID)
+				return
+			}
+		}
+		if test.checkLayer == clDatabase {
+			// Database exists and client is allowed to know it, so its methods fail
+			// with ErrNoAccess.
+			// Some of the Syncgroup Create and Join methods have patterns that do
+			// pass the Database ACL, but fail on Collection existence check or
+			// Syncgroup remote join check (after failing Syncgroup existence check).
+			assertErrorOneOf(verror.ErrNoAccess.ID, verror.ErrNoExist.ID, wire.ErrSyncgroupJoinFailed.ID)
+			return
+		}
+		if !checkPerms("X___") {
+			// Client cannot resolve through Service, so methods above Database fail
+			// with ErrNoAccess.
+			assertErrorOneOf(verror.ErrNoAccess.ID)
+			return
+		}
+
+		if test.checkLayer == clSyncgroup {
+			// Local Syncgroup method branch:
+
+			if !checkPerms("XX_R", "XX_A", "XR__", "XW__") {
+				// Caller is not allowed to know if Syncgroup exists, so methods on
+				// Syncgroup fail with ErrNoExistOrNoAccess.
+				assertErrorOneOf(verror.ErrNoExistOrNoAccess.ID)
+				return
+			}
+			if !strings.Contains(createSpec, csSyncgroup) {
+				// Syncgroup does not exist, so methods on Syncgroup fail with
+				// ErrNoExist.
+				assertErrorOneOf(verror.ErrNoExist.ID)
+				return
+			}
+			// Syncgroup exists and client is allowed to know it, so its methods fail
+			// with ErrNoAccess.
+			assertErrorOneOf(verror.ErrNoAccess.ID)
+			return
+		}
+
+		// Collection and Row method branch:
+
+		if !checkPerms("XXR_", "XXW_", "XXA_", "XR__", "XW__") {
+			// Caller is not allowed to know if Collection exists, so methods on
+			// Collection and above fail with ErrNoExistOrNoAccess.
+			assertErrorOneOf(verror.ErrNoExistOrNoAccess.ID)
+			return
+		}
+		if !strings.Contains(createSpec, csCollection) {
+			// Collection does not exist, so methods on Collection and above fail
+			// with ErrNoExist.
+			assertErrorOneOf(verror.ErrorID(nil), verror.ErrNoExist.ID)
+			return
+		}
+		if test.checkLayer == clCollection {
+			// Collection exists and client is allowed to know it, so its methods fail
+			// with ErrNoAccess.
+			assertErrorOneOf(verror.ErrNoAccess.ID)
+			return
+		}
+
+		if !checkPerms("XX__") {
+			// Client cannot resolve through Database, so methods above Collection
+			// fail with ErrNoAccess.
+			assertErrorOneOf(verror.ErrNoAccess.ID)
+			return
+		}
+
+		if !checkPerms("XXR_", "XXW_") {
+			// Caller is not allowed to know if Row exists, so methods on Row fail
+			// with ErrNoExistOrNoAccess.
+			assertErrorOneOf(verror.ErrNoExistOrNoAccess.ID)
+			return
+		}
+		// Note, since Exists is currently the only Row-checked method, the two
+		// checks below are unnecessary.
+		/*
+			if !strings.Contains(createSpec, csRow)  {
+				// Row does not exist, so methods on Row fail with ErrNoExist.
+				assertErrorOneOf(verror.ErrNoExist.ID)
+				return
+			}
+			if test.checkLayer == clRow {
+				// Row exists and client is allowed to know it, so its methods fail
+				// with ErrNoAccess.
+				assertErrorOneOf(verror.ErrNoAccess.ID)
+				return
+			}
+		*/
+
+		// Blob layer has no permissions of its own, it is covered by Database
+		// permissions.
+
+		tu.Fatalf(t, "unknown permission check layer: %v", test.checkLayer)
+	}
+}
+
 var (
 	inferBlessingsOk = []struct {
 		exts     []string