diff --git a/tests/Android.bp b/tests/Android.bp
index 1ce577b..8fe89e5 100644
--- a/tests/Android.bp
+++ b/tests/Android.bp
@@ -31,6 +31,27 @@
     name: "treble_sepolicy_tests",
     srcs: [
         "treble_sepolicy_tests.py",
+        "mini_parser.py",
+        "policy.py",
+    ],
+    required: ["libsepolwrap"],
+    defaults: ["py2_only"],
+}
+
+python_binary_host {
+    name: "sepolicy_tests",
+    srcs: [
+        "sepolicy_tests.py",
+        "policy.py",
+    ],
+    required: ["libsepolwrap"],
+    defaults: ["py2_only"],
+}
+
+python_binary_host {
+    name: "searchpolicy",
+    srcs: [
+        "searchpolicy.py",
         "policy.py",
     ],
     required: ["libsepolwrap"],
diff --git a/tests/include/sepol_wrap.h b/tests/include/sepol_wrap.h
index 0683a3b..2357421 100644
--- a/tests/include/sepol_wrap.h
+++ b/tests/include/sepol_wrap.h
@@ -4,12 +4,14 @@
 #endif
 
 int get_allow_rule(char *out, size_t len, void *policydbp, void *avtab_iterp);
-bool init_libsepol(const char *policy_path);
 void *load_policy(const char *policy_path);
 void destroy_policy(void *policydbp);
 void *init_avtab(void *policydbp);
 void *init_cond_avtab(void *policydbp);
 void destroy_avtab(void *avtab_iterp);
+void *init_expanded_avtab(void *policydbp);
+void *init_expanded_cond_avtab(void *policydbp);
+void destroy_expanded_avtab(void *avtab_iterp);
 int get_type(char *out, size_t max_size, void *policydbp, void *type_iterp);
 void *init_type_iter(void *policydbp, const char *type, bool is_attr);
 void destroy_type_iter(void *type_iterp);
diff --git a/tests/mini_parser.py b/tests/mini_parser.py
new file mode 100644
index 0000000..fbeaff8
--- /dev/null
+++ b/tests/mini_parser.py
@@ -0,0 +1,100 @@
+from os.path import basename
+import re
+import sys
+
+# A very limited parser whose job is to process the compatibility mapping
+# files and retrieve type and attribute information until proper support is
+# built into libsepol
+
+# get the text in the next matching parens
+
+class MiniCilParser:
+    types = set() # types declared in mapping
+    pubtypes = set()
+    typeattributes = set() # attributes declared in mapping
+    typeattributesets = {} # sets defined in mapping
+    rTypeattributesets = {} # reverse mapping of above sets
+    apiLevel = None
+
+    def _getNextStmt(self, infile):
+        parens = 0
+        s = ""
+        c = infile.read(1)
+        # get to first statement
+        while c and c != "(":
+            c = infile.read(1)
+
+        parens += 1
+        c = infile.read(1)
+        while c and parens != 0:
+            s += c
+            c = infile.read(1)
+            if c == ';':
+                # comment, get rid of rest of the line
+                while c != '\n':
+                    c = infile.read(1)
+            elif c == '(':
+                parens += 1
+            elif c == ')':
+                parens -= 1
+        return s
+
+    def _parseType(self, stmt):
+        m = re.match(r"type\s+(.+)", stmt)
+        self.types.add(m.group(1))
+        return
+
+    def _parseTypeattribute(self, stmt):
+        m = re.match(r"typeattribute\s+(.+)", stmt)
+        self.typeattributes.add(m.group(1))
+        return
+
+    def _parseTypeattributeset(self, stmt):
+        m = re.match(r"typeattributeset\s+(.+?)\s+\((.+?)\)", stmt, flags = re.M |re.S)
+        ta = m.group(1)
+        # this isn't proper expression parsing, but will do for our
+        # current use
+        tas = m.group(2).split()
+
+        if self.typeattributesets.get(ta) is None:
+            self.typeattributesets[ta] = set()
+        self.typeattributesets[ta].update(set(tas))
+        for t in tas:
+            if self.rTypeattributesets.get(t) is None:
+                self.rTypeattributesets[t] = set()
+            self.rTypeattributesets[t].update(set(ta))
+
+        # check to see if this typeattributeset is a versioned public type
+        pub = re.match(r"(\w+)_\d+_\d+", ta)
+        if pub is not None:
+            self.pubtypes.add(pub.group(1))
+        return
+
+    def _parseStmt(self, stmt):
+        if re.match(r"type\s+.+", stmt):
+            self._parseType(stmt)
+        elif re.match(r"typeattribute\s+.+", stmt):
+            self._parseTypeattribute(stmt)
+        elif re.match(r"typeattributeset\s+.+", stmt):
+            self._parseTypeattributeset(stmt)
+        else:
+            m = re.match(r"(\w+)\s+.+", stmt)
+            ret = "Warning: Unknown statement type (" + m.group(1) + ") in "
+            ret += "mapping file, perhaps consider adding support for it in "
+            ret += "system/sepolicy/tests/mini_parser.py!\n"
+            print ret
+        return
+
+    def __init__(self, policyFile):
+        with open(policyFile, 'r') as infile:
+            s = self._getNextStmt(infile)
+            while s:
+                self._parseStmt(s)
+                s = self._getNextStmt(infile)
+        fn = basename(policyFile)
+        m = re.match(r"(\d+\.\d+).+\.cil", fn)
+        self.apiLevel = m.group(1)
+
+if __name__ == '__main__':
+    f = sys.argv[1]
+    p = MiniCilParser(f)
diff --git a/tests/policy.py b/tests/policy.py
index 74a8ef7..a0ddb90 100644
--- a/tests/policy.py
+++ b/tests/policy.py
@@ -3,6 +3,33 @@
 import os
 import sys
 
+###
+# Check whether the regex will match a file path starting with the provided
+# prefix
+#
+# Compares regex entries in file_contexts with a path prefix. Regex entries
+# are often more specific than this file prefix. For example, the regex could
+# be /system/bin/foo\.sh and the prefix could be /system. This function
+# loops over the regex removing characters from the end until
+# 1) there is a match - return True or 2) run out of characters - return
+#    False.
+#
+def MatchPathPrefix(pathregex, prefix):
+    for i in range(len(pathregex), 0, -1):
+        try:
+            pattern = re.compile('^' + pathregex[0:i] + "$")
+        except:
+            continue
+        if pattern.match(prefix):
+            return True
+    return False
+
+def MatchPathPrefixes(pathregex, Prefixes):
+    for Prefix in Prefixes:
+        if MatchPathPrefix(pathregex, Prefix):
+            return True
+    return False
+
 class TERule:
     def __init__(self, rule):
         data = rule.split(',')
@@ -14,10 +41,33 @@
         self.rule = rule
 
 class Policy:
-    __Rules = None
+    __ExpandedRules = set()
+    __Rules = set()
     __FcDict = None
     __libsepolwrap = None
     __policydbP = None
+    __BUFSIZE = 2048
+
+    # Check that path prefixes that match MatchPrefix, and do not Match
+    # DoNotMatchPrefix have the attribute Attr.
+    # For example assert that all types in /sys, and not in /sys/kernel/debugfs
+    # have the sysfs_type attribute.
+    def AssertPathTypesHaveAttr(self, MatchPrefix, DoNotMatchPrefix, Attr):
+        # Query policy for the types associated with Attr
+        TypesPol = self.QueryTypeAttribute(Attr, True)
+        # Search file_contexts to find paths/types that should be associated with
+        # Attr.
+        TypesFc = self.__GetTypesByFilePathPrefix(MatchPrefix, DoNotMatchPrefix)
+        violators = TypesFc.difference(TypesPol)
+
+        ret = ""
+        if len(violators) > 0:
+            ret += "The following types on "
+            ret += " ".join(str(x) for x in sorted(MatchPrefix))
+            ret += " must be associated with the "
+            ret += "\"" + Attr + "\" attribute: "
+            ret += " ".join(str(x) for x in sorted(violators)) + "\n"
+        return ret
 
     # Return all file_contexts entries that map to the input Type.
     def QueryFc(self, Type):
@@ -29,25 +79,68 @@
     # Return all attributes associated with a type if IsAttr=False or
     # all types associated with an attribute if IsAttr=True
     def QueryTypeAttribute(self, Type, IsAttr):
-        init_type_iter = self.__libsepolwrap.init_type_iter
-        init_type_iter.restype = c_void_p
-        TypeIterP = init_type_iter(c_void_p(self.__policydbP),
-                        create_string_buffer(Type), c_bool(IsAttr))
+        TypeIterP = self.__libsepolwrap.init_type_iter(self.__policydbP,
+                        create_string_buffer(Type), IsAttr)
         if (TypeIterP == None):
             sys.exit("Failed to initialize type iterator")
-        buf = create_string_buffer(2048)
-
+        buf = create_string_buffer(self.__BUFSIZE)
+        TypeAttr = set()
         while True:
-            ret = self.__libsepolwrap.get_type(buf, c_int(2048),
-                    c_void_p(self.__policydbP), c_void_p(TypeIterP))
+            ret = self.__libsepolwrap.get_type(buf, self.__BUFSIZE,
+                    self.__policydbP, TypeIterP)
             if ret == 0:
-                yield buf.value
+                TypeAttr.add(buf.value)
                 continue
             if ret == 1:
                 break;
             # We should never get here.
             sys.exit("Failed to import policy")
-        self.__libsepolwrap.destroy_type_iter(c_void_p(TypeIterP))
+        self.__libsepolwrap.destroy_type_iter(TypeIterP)
+        return TypeAttr
+
+    def __TERuleMatch(self, Rule, **kwargs):
+        # Match source type
+        if ("scontext" in kwargs and
+                len(kwargs['scontext']) > 0 and
+                Rule.sctx not in kwargs['scontext']):
+            return False
+        # Match target type
+        if ("tcontext" in kwargs and
+                len(kwargs['tcontext']) > 0 and
+                Rule.tctx not in kwargs['tcontext']):
+            return False
+        # Match target class
+        if ("tclass" in kwargs and
+                len(kwargs['tclass']) > 0 and
+                not bool(set([Rule.tclass]) & kwargs['tclass'])):
+            return False
+        # Match any perms
+        if ("perms" in kwargs and
+                len(kwargs['perms']) > 0 and
+                not bool(Rule.perms & kwargs['perms'])):
+            return False
+        return True
+
+    # resolve a type to its attributes or
+    # resolve an attribute to its types and attributes
+    # For example if scontext is the domain attribute, then we need to
+    # include all types with the domain attribute such as untrusted_app and
+    # priv_app and all the attributes of those types such as appdomain.
+    def ResolveTypeAttribute(self, Type):
+        types = self.GetAllTypes(False)
+        attributes = self.GetAllTypes(True)
+
+        if Type in types:
+            return self.QueryTypeAttribute(Type, False)
+        elif Type in attributes:
+            TypesAndAttributes = set()
+            Types = self.QueryTypeAttribute(Type, True)
+            TypesAndAttributes |= Types
+            for T in Types:
+                TypesAndAttributes |= self.QueryTypeAttribute(T, False)
+            return TypesAndAttributes
+        else:
+            return set()
 
     # Return all TERules that match:
     # (any scontext) or (any tcontext) or (any tclass) or (any perms),
@@ -58,35 +151,75 @@
     # Will return any rule with:
     # (tcontext="foo" or tcontext="bar") and ("entrypoint" in perms)
     def QueryTERule(self, **kwargs):
-        if self.__Rules is None:
+        if len(self.__Rules) == 0:
             self.__InitTERules()
+
+        # add any matching types and attributes for scontext and tcontext
+        if ("scontext" in kwargs and len(kwargs['scontext']) > 0):
+            scontext = set()
+            for sctx in kwargs['scontext']:
+                scontext |= self.ResolveTypeAttribute(sctx)
+            kwargs['scontext'] = scontext
+        if ("tcontext" in kwargs and len(kwargs['tcontext']) > 0):
+            tcontext = set()
+            for tctx in kwargs['tcontext']:
+                tcontext |= self.ResolveTypeAttribute(tctx)
+            kwargs['tcontext'] = tcontext
         for Rule in self.__Rules:
-            # Match source type
-            if "scontext" in kwargs and Rule.sctx not in kwargs['scontext']:
+            if self.__TERuleMatch(Rule, **kwargs):
+                yield Rule
+
+    # Same as QueryTERule but only using the expanded ruleset.
+    # i.e. all attributes have been expanded to their various types.
+    def QueryExpandedTERule(self, **kwargs):
+        if len(self.__ExpandedRules) == 0:
+            self.__InitExpandedTERules()
+        for Rule in self.__ExpandedRules:
+            if self.__TERuleMatch(Rule, **kwargs):
+                yield Rule
+
+    def GetAllTypes(self, isAttr):
+        TypeIterP = self.__libsepolwrap.init_type_iter(self.__policydbP, None, isAttr)
+        if (TypeIterP == None):
+            sys.exit("Failed to initialize type iterator")
+        buf = create_string_buffer(self.__BUFSIZE)
+        AllTypes = set()
+        while True:
+            ret = self.__libsepolwrap.get_type(buf, self.__BUFSIZE,
+                    self.__policydbP, TypeIterP)
+            if ret == 0:
+                AllTypes.add(buf.value)
                 continue
-            # Match target type
-            if "tcontext" in kwargs and Rule.tctx not in kwargs['tcontext']:
-                continue
-            # Match target class
-            if "tclass" in kwargs and Rule.tclass not in kwargs['tclass']:
-                continue
-            # Match any perms
-            if "perms" in kwargs and not bool(Rule.perms & set(kwargs['perms'])):
-                continue
-            yield Rule
+            if ret == 1:
+                break;
+            # We should never get here.
+            sys.exit("Failed to import policy")
+        self.__libsepolwrap.destroy_type_iter(TypeIterP)
+        return AllTypes
+
+    def __GetTypesByFilePathPrefix(self, MatchPrefixes, DoNotMatchPrefixes):
+        Types = set()
+        for Type in self.__FcDict:
+            for pathregex in self.__FcDict[Type]:
+                if not MatchPathPrefixes(pathregex, MatchPrefixes):
+                    continue
+                if MatchPathPrefixes(pathregex, DoNotMatchPrefixes):
+                    continue
+                Types.add(Type)
+        return Types
 
 
-    def __GetTERules(self, policydbP, avtabIterP):
-        if self.__Rules is None:
-            self.__Rules = set()
-        buf = create_string_buffer(2048)
+    def __GetTERules(self, policydbP, avtabIterP, Rules):
+        if Rules is None:
+            Rules = set()
+        buf = create_string_buffer(self.__BUFSIZE)
         ret = 0
         while True:
-            ret = self.__libsepolwrap.get_allow_rule(buf, c_int(2048),
-                        c_void_p(policydbP), c_void_p(avtabIterP))
+            ret = self.__libsepolwrap.get_allow_rule(buf, self.__BUFSIZE,
+                        policydbP, avtabIterP)
             if ret == 0:
                 Rule = TERule(buf.value)
-                self.__Rules.add(Rule)
+                Rules.add(Rule)
                 continue
             if ret == 1:
                 break;
@@ -94,32 +227,78 @@
             sys.exit("Failed to import policy")
 
     def __InitTERules(self):
-        init_avtab = self.__libsepolwrap.init_avtab
-        init_avtab.restype = c_void_p
-        avtabIterP = init_avtab(c_void_p(self.__policydbP))
+        avtabIterP = self.__libsepolwrap.init_avtab(self.__policydbP)
         if (avtabIterP == None):
             sys.exit("Failed to initialize avtab")
-        self.__GetTERules(self.__policydbP, avtabIterP)
-        self.__libsepolwrap.destroy_avtab(c_void_p(avtabIterP))
-        init_cond_avtab = self.__libsepolwrap.init_cond_avtab
-        init_cond_avtab.restype = c_void_p
-        avtabIterP = init_cond_avtab(c_void_p(self.__policydbP))
+        self.__GetTERules(self.__policydbP, avtabIterP, self.__Rules)
+        self.__libsepolwrap.destroy_avtab(avtabIterP)
+        avtabIterP = self.__libsepolwrap.init_cond_avtab(self.__policydbP)
         if (avtabIterP == None):
             sys.exit("Failed to initialize conditional avtab")
-        self.__GetTERules(self.__policydbP, avtabIterP)
-        self.__libsepolwrap.destroy_avtab(c_void_p(avtabIterP))
+        self.__GetTERules(self.__policydbP, avtabIterP, self.__Rules)
+        self.__libsepolwrap.destroy_avtab(avtabIterP)
+
+    def __InitExpandedTERules(self):
+        avtabIterP = self.__libsepolwrap.init_expanded_avtab(self.__policydbP)
+        if (avtabIterP == None):
+            sys.exit("Failed to initialize avtab")
+        self.__GetTERules(self.__policydbP, avtabIterP, self.__ExpandedRules)
+        self.__libsepolwrap.destroy_expanded_avtab(avtabIterP)
+        avtabIterP = self.__libsepolwrap.init_expanded_cond_avtab(self.__policydbP)
+        if (avtabIterP == None):
+            sys.exit("Failed to initialize conditional avtab")
+        self.__GetTERules(self.__policydbP, avtabIterP, self.__ExpandedRules)
+        self.__libsepolwrap.destroy_expanded_avtab(avtabIterP)
 
     # load ctypes-ified libsepol wrapper
     def __InitLibsepolwrap(self, LibPath):
         if "linux" in sys.platform:
-            self.__libsepolwrap = CDLL(LibPath + "/libsepolwrap.so")
+            lib = CDLL(LibPath + "/libsepolwrap.so")
         elif "darwin" in sys.platform:
-            self.__libsepolwrap = CDLL(LibPath + "/libsepolwrap.dylib")
+            lib = CDLL(LibPath + "/libsepolwrap.dylib")
         else:
             sys.exit("only Linux and Mac currrently supported")
 
+        # int get_allow_rule(char *out, size_t len, void *policydbp, void *avtab_iterp);
+        lib.get_allow_rule.restype = c_int
+        lib.get_allow_rule.argtypes = [c_char_p, c_size_t, c_void_p, c_void_p];
+        # void *load_policy(const char *policy_path);
+        lib.load_policy.restype = c_void_p
+        lib.load_policy.argtypes = [c_char_p]
+        # void destroy_policy(void *policydbp);
+        lib.destroy_policy.argtypes = [c_void_p]
+        # void *init_expanded_avtab(void *policydbp);
+        lib.init_expanded_avtab.restype = c_void_p
+        lib.init_expanded_avtab.argtypes = [c_void_p]
+        # void *init_expanded_cond_avtab(void *policydbp);
+        lib.init_expanded_cond_avtab.restype = c_void_p
+        lib.init_expanded_cond_avtab.argtypes = [c_void_p]
+        # void destroy_expanded_avtab(void *avtab_iterp);
+        lib.destroy_expanded_avtab.argtypes = [c_void_p]
+        # void *init_avtab(void *policydbp);
+        lib.init_avtab.restype = c_void_p
+        lib.init_avtab.argtypes = [c_void_p]
+        # void *init_cond_avtab(void *policydbp);
+        lib.init_cond_avtab.restype = c_void_p
+        lib.init_cond_avtab.argtypes = [c_void_p]
+        # void destroy_avtab(void *avtab_iterp);
+        lib.destroy_avtab.argtypes = [c_void_p]
+        # int get_type(char *out, size_t max_size, void *policydbp, void *type_iterp);
+        lib.get_type.restype = c_int
+        lib.get_type.argtypes = [c_char_p, c_size_t, c_void_p, c_void_p]
+        # void *init_type_iter(void *policydbp, const char *type, bool is_attr);
+        lib.init_type_iter.restype = c_void_p
+        lib.init_type_iter.argtypes = [c_void_p, c_char_p, c_bool]
+        # void destroy_type_iter(void *type_iterp);
+        lib.destroy_type_iter.argtypes = [c_void_p]
+
+        self.__libsepolwrap = lib
+
+
     # load file_contexts
     def __InitFC(self, FcPaths):
+        if FcPaths is None:
+            return
         fc = []
         for path in FcPaths:
             if not os.path.exists(path):
@@ -141,9 +320,8 @@
 
     # load policy
     def __InitPolicy(self, PolicyPath):
-        load_policy = self.__libsepolwrap.load_policy
-        load_policy.restype = c_void_p
-        self.__policydbP = load_policy(create_string_buffer(PolicyPath))
+        cPolicyPath = create_string_buffer(PolicyPath)
+        self.__policydbP = self.__libsepolwrap.load_policy(cPolicyPath)
         if (self.__policydbP is None):
             sys.exit("Failed to load policy")
 
@@ -154,4 +332,4 @@
 
     def __del__(self):
         if self.__policydbP is not None:
-            self.__libsepolwrap.destroy_policy(c_void_p(self.__policydbP))
+            self.__libsepolwrap.destroy_policy(self.__policydbP)
diff --git a/tests/searchpolicy.py b/tests/searchpolicy.py
new file mode 100644
index 0000000..ff9318b
--- /dev/null
+++ b/tests/searchpolicy.py
@@ -0,0 +1,73 @@
+#!/usr/bin/env python
+
+import argparse
+import policy
+
+parser = argparse.ArgumentParser(
+    description="SELinux policy rule search tool. Intended to have a similar "
+        + "API as sesearch, but simplified to use only code availabe in AOSP")
+parser.add_argument("policy", help="Path to the SELinux policy to search.", nargs="?")
+parser.add_argument("--libpath", dest="libpath", help="Path to the libsepolwrap.so", nargs="?")
+tertypes = parser.add_argument_group("TE Rule Types")
+tertypes.add_argument("--allow", action="append_const",
+                    const="allow", dest="tertypes",
+                    help="Search allow rules.")
+expr = parser.add_argument_group("Expressions")
+expr.add_argument("-s", "--source",
+                  help="Source type/role of the TE/RBAC rule.")
+expr.add_argument("-t", "--target",
+                  help="Target type/role of the TE/RBAC rule.")
+expr.add_argument("-c", "--class", dest="tclass",
+                  help="Comma separated list of object classes")
+expr.add_argument("-p", "--perms", metavar="PERMS",
+                  help="Comma separated list of permissions.")
+
+args = parser.parse_args()
+
+if not args.tertypes:
+    parser.error("Must specify \"--allow\"")
+
+if not args.policy:
+    parser.error("Must include path to policy")
+if not args.libpath:
+    parser.error("Must include path to libsepolwrap library")
+
+if not (args.source or args.target or args.tclass or args.perms):
+    parser.error("Must something to filter on, e.g. --source, --target, etc.")
+
+pol = policy.Policy(args.policy, None, args.libpath)
+
+if args.source:
+    scontext = {args.source}
+else:
+    scontext = set()
+if args.target:
+    tcontext = {args.target}
+else:
+    tcontext = set()
+if args.tclass:
+    tclass = set(args.tclass.split(","))
+else:
+    tclass = set()
+if args.perms:
+    perms = set(args.perms.split(","))
+else:
+    perms = set()
+
+TERules = pol.QueryTERule(scontext=scontext,
+                       tcontext=tcontext,
+                       tclass=tclass,
+                       perms=perms)
+
+# format rules for printing
+rules = []
+for r in TERules:
+    if len(r.perms) > 1:
+        rules.append("allow " + r.sctx + " " + r.tctx + ":" + r.tclass + " { " +
+                " ".join(r.perms) + " };")
+    else:
+        rules.append("allow " + r.sctx + " " + r.tctx + ":" + r.tclass + " " +
+                " ".join(r.perms) + ";")
+
+for r in sorted(rules):
+    print r
diff --git a/tests/sepol_wrap.cpp b/tests/sepol_wrap.cpp
index a12d438..d537b7e 100644
--- a/tests/sepol_wrap.cpp
+++ b/tests/sepol_wrap.cpp
@@ -17,8 +17,11 @@
 #include <android-base/strings.h>
 #include <sepol_wrap.h>
 
-
+#define TYPE_ITER_LOOKUP   0
+#define TYPE_ITER_ALLTYPES 1
+#define TYPE_ITER_ALLATTRS 2
 struct type_iter {
+    unsigned int alltypes;
     type_datum *d;
     ebitmap_node *n;
     unsigned int length;
@@ -36,23 +39,33 @@
         return NULL;
     }
 
-    out->d = static_cast<type_datum *>(hashtab_search(db->p_types.table, type));
-    if (is_attr && out->d->flavor != TYPE_ATTRIB) {
-        std::cerr << "\"" << type << "\" MUST be an attribute in the policy" << std::endl;
-        free(out);
-        return NULL;
-    } else if (!is_attr && out->d->flavor !=TYPE_TYPE) {
-        std::cerr << "\"" << type << "\" MUST be a type in the policy" << std::endl;
-        free(out);
-        return NULL;
-    }
-
-    if (is_attr) {
-        out->bit = ebitmap_start(&db->attr_type_map[out->d->s.value - 1], &out->n);
-        out->length = ebitmap_length(&db->attr_type_map[out->d->s.value - 1]);
+    if (type == NULL) {
+        out->length = db->p_types.nprim;
+        out->bit = 0;
+        if (is_attr)
+            out->alltypes = TYPE_ITER_ALLATTRS;
+        else
+            out->alltypes = TYPE_ITER_ALLTYPES;
     } else {
-        out->bit = ebitmap_start(&db->type_attr_map[out->d->s.value - 1], &out->n);
-        out->length = ebitmap_length(&db->type_attr_map[out->d->s.value - 1]);
+        out->alltypes = TYPE_ITER_LOOKUP;
+        out->d = static_cast<type_datum *>(hashtab_search(db->p_types.table, type));
+        if (is_attr && out->d->flavor != TYPE_ATTRIB) {
+            std::cerr << "\"" << type << "\" MUST be an attribute in the policy" << std::endl;
+            free(out);
+            return NULL;
+        } else if (!is_attr && out->d->flavor !=TYPE_TYPE) {
+            std::cerr << "\"" << type << "\" MUST be a type in the policy" << std::endl;
+            free(out);
+            return NULL;
+        }
+
+        if (is_attr) {
+            out->bit = ebitmap_start(&db->attr_type_map[out->d->s.value - 1], &out->n);
+            out->length = ebitmap_length(&db->attr_type_map[out->d->s.value - 1]);
+        } else {
+            out->bit = ebitmap_start(&db->type_attr_map[out->d->s.value - 1], &out->n);
+            out->length = ebitmap_length(&db->type_attr_map[out->d->s.value - 1]);
+        }
     }
 
     return static_cast<void *>(out);
@@ -65,7 +78,7 @@
 }
 
 /*
- * print allow rule into *out buffer.
+ * print type into *out buffer.
  *
  * Returns -1 on error.
  * Returns 0 on successfully reading an avtab entry.
@@ -77,20 +90,30 @@
     policydb_t *db = static_cast<policydb_t *>(policydbp);
     struct type_iter *i = static_cast<struct type_iter *>(type_iterp);
 
-    for (; i->bit < i->length; i->bit = ebitmap_next(&i->n, i->bit)) {
-        if (!ebitmap_node_get_bit(i->n, i->bit)) {
-            continue;
+    if (!i->alltypes) {
+        for (; i->bit < i->length; i->bit = ebitmap_next(&i->n, i->bit)) {
+            if (!ebitmap_node_get_bit(i->n, i->bit)) {
+                continue;
+            }
+            break;
         }
-        len = snprintf(out, max_size, "%s", db->p_type_val_to_name[i->bit]);
-        if (len >= max_size) {
-               std::cerr << "type name exceeds buffer size." << std::endl;
-               return -1;
-        }
-        i->bit = ebitmap_next(&i->n, i->bit);
-        return 0;
     }
-
-    return 1;
+    while (i->bit < i->length &&
+           ((i->alltypes == TYPE_ITER_ALLATTRS
+            && db->type_val_to_struct[i->bit]->flavor != TYPE_ATTRIB)
+            || (i->alltypes == TYPE_ITER_ALLTYPES
+            && db->type_val_to_struct[i->bit]->flavor != TYPE_TYPE))) {
+        i->bit++;
+    }
+    if (i->bit >= i->length)
+        return 1;
+    len = snprintf(out, max_size, "%s", db->p_type_val_to_name[i->bit]);
+    if (len >= max_size) {
+        std::cerr << "type name exceeds buffer size." << std::endl;
+        return -1;
+    }
+    i->alltypes ? i->bit++ : i->bit = ebitmap_next(&i->n, i->bit);
+    return 0;
 }
 
 void *load_policy(const char *policy_path)
@@ -158,7 +181,7 @@
 
 /* items needed to iterate over the avtab */
 struct avtab_iter {
-    avtab_t avtab;
+    avtab_t *avtab;
     uint32_t i;
     avtab_ptr_t cur;
 };
@@ -175,9 +198,9 @@
 {
     size_t len;
 
-    for (; avtab_i->i < avtab_i->avtab.nslot; (avtab_i->i)++) {
+    for (; avtab_i->i < avtab_i->avtab->nslot; (avtab_i->i)++) {
         if (avtab_i->cur == NULL) {
-            avtab_i->cur = avtab_i->avtab.htable[avtab_i->i];
+            avtab_i->cur = avtab_i->avtab->htable[avtab_i->i];
         }
         for (; avtab_i->cur; avtab_i->cur = (avtab_i->cur)->next) {
             if (!((avtab_i->cur)->key.specified & AVTAB_ALLOWED)) continue;
@@ -210,6 +233,37 @@
     return get_avtab_allow_rule(out, len, db, avtab_i);
 }
 
+static avtab_iter *init_avtab_common(avtab_t *in)
+{
+    struct avtab_iter *out = (struct avtab_iter *)
+                            calloc(1, sizeof(struct avtab_iter));
+    if (!out) {
+        std::cerr << "Failed to allocate avtab iterator" << std::endl;
+        return NULL;
+    }
+
+    out->avtab = in;
+    return out;
+}
+
+void *init_avtab(void *policydbp)
+{
+    policydb_t *p = static_cast<policydb_t *>(policydbp);
+    return static_cast<void *>(init_avtab_common(&p->te_avtab));
+}
+
+void *init_cond_avtab(void *policydbp)
+{
+    policydb_t *p = static_cast<policydb_t *>(policydbp);
+    return static_cast<void *>(init_avtab_common(&p->te_cond_avtab));
+}
+
+void destroy_avtab(void *avtab_iterp)
+{
+    struct avtab_iter *avtab_i = static_cast<struct avtab_iter *>(avtab_iterp);
+    free(avtab_i);
+}
+
 /*
  * <sepol/policydb/expand.h->conditional.h> uses 'bool' as a variable name
  * inside extern "C" { .. } construct, which clang doesn't like.
@@ -217,45 +271,57 @@
  */
 extern "C" int expand_avtab(policydb_t *p, avtab_t *a, avtab_t *expa);
 
-static avtab_iter *init_avtab_common(avtab_t *in, policydb_t *p)
+static avtab_iter *init_expanded_avtab_common(avtab_t *in, policydb_t *p)
 {
     struct avtab_iter *out = (struct avtab_iter *)
                             calloc(1, sizeof(struct avtab_iter));
     if (!out) {
-        std::cerr << "Failed to allocate avtab" << std::endl;
+        std::cerr << "Failed to allocate avtab iterator" << std::endl;
         return NULL;
     }
 
-    if (avtab_init(&out->avtab)) {
-        std::cerr << "Failed to initialize avtab" << std::endl;
+    avtab_t *avtab = (avtab_t *) calloc(1, sizeof(avtab_t));
+
+    if (!avtab) {
+        std::cerr << "Failed to allocate avtab" << std::endl;
         free(out);
         return NULL;
     }
 
-    if (expand_avtab(p, in, &out->avtab)) {
+    out->avtab = avtab;
+    if (avtab_init(out->avtab)) {
+        std::cerr << "Failed to initialize avtab" << std::endl;
+        free(avtab);
+        free(out);
+        return NULL;
+    }
+
+    if (expand_avtab(p, in, out->avtab)) {
         std::cerr << "Failed to expand avtab" << std::endl;
+        free(avtab);
         free(out);
         return NULL;
     }
     return out;
 }
 
-void *init_avtab(void *policydbp)
+void *init_expanded_avtab(void *policydbp)
 {
     policydb_t *p = static_cast<policydb_t *>(policydbp);
-    return static_cast<void *>(init_avtab_common(&p->te_avtab, p));
+    return static_cast<void *>(init_expanded_avtab_common(&p->te_avtab, p));
 }
 
-void *init_cond_avtab(void *policydbp)
+void *init_expanded_cond_avtab(void *policydbp)
 {
     policydb_t *p = static_cast<policydb_t *>(policydbp);
-    return static_cast<void *>(init_avtab_common(&p->te_cond_avtab, p));
+    return static_cast<void *>(init_expanded_avtab_common(&p->te_cond_avtab, p));
 }
 
-void destroy_avtab(void *avtab_iterp)
+void destroy_expanded_avtab(void *avtab_iterp)
 {
     struct avtab_iter *avtab_i = static_cast<struct avtab_iter *>(avtab_iterp);
-    avtab_destroy(&avtab_i->avtab);
+    avtab_destroy(avtab_i->avtab);
+    free(avtab_i->avtab);
     free(avtab_i);
 }
 
diff --git a/tests/sepolicy_tests.py b/tests/sepolicy_tests.py
new file mode 100644
index 0000000..3f93ff4
--- /dev/null
+++ b/tests/sepolicy_tests.py
@@ -0,0 +1,85 @@
+from optparse import OptionParser
+from optparse import Option, OptionValueError
+import os
+import policy
+import re
+import sys
+
+#############################################################
+# Tests
+#############################################################
+def TestDataTypeViolations(pol):
+    return pol.AssertPathTypesHaveAttr(["/data/"], [], "data_file_type")
+
+def TestSysfsTypeViolations(pol):
+    return pol.AssertPathTypesHaveAttr(["/sys/"], ["/sys/kernel/debug/",
+                                    "/sys/kernel/tracing"], "sysfs_type")
+
+def TestDebugfsTypeViolations(pol):
+    # TODO: this should apply to genfs_context entries as well
+    return pol.AssertPathTypesHaveAttr(["/sys/kernel/debug/",
+                                    "/sys/kernel/tracing"], [], "debugfs_type")
+###
+# extend OptionParser to allow the same option flag to be used multiple times.
+# This is used to allow multiple file_contexts files and tests to be
+# specified.
+#
+class MultipleOption(Option):
+    ACTIONS = Option.ACTIONS + ("extend",)
+    STORE_ACTIONS = Option.STORE_ACTIONS + ("extend",)
+    TYPED_ACTIONS = Option.TYPED_ACTIONS + ("extend",)
+    ALWAYS_TYPED_ACTIONS = Option.ALWAYS_TYPED_ACTIONS + ("extend",)
+
+    def take_action(self, action, dest, opt, value, values, parser):
+        if action == "extend":
+            values.ensure_value(dest, []).append(value)
+        else:
+            Option.take_action(self, action, dest, opt, value, values, parser)
+
+Tests = ["TestDataTypeViolators"]
+
+if __name__ == '__main__':
+    usage = "sepolicy_tests.py -f nonplat_file_contexts -f "
+    usage +="plat_file_contexts -p policy [--test test] [--help]"
+    parser = OptionParser(option_class=MultipleOption, usage=usage)
+    parser.add_option("-f", "--file_contexts", dest="file_contexts",
+            metavar="FILE", action="extend", type="string")
+    parser.add_option("-p", "--policy", dest="policy", metavar="FILE")
+    parser.add_option("-l", "--library-path", dest="libpath", metavar="FILE")
+    parser.add_option("-t", "--test", dest="test", action="extend",
+            help="Test options include "+str(Tests))
+
+    (options, args) = parser.parse_args()
+
+    if not options.libpath:
+        sys.exit("Must specify path to host libraries\n" + parser.usage)
+    if not os.path.exists(options.libpath):
+        sys.exit("Error: library-path " + options.libpath + " does not exist\n"
+                + parser.usage)
+
+    if not options.policy:
+        sys.exit("Must specify monolithic policy file\n" + parser.usage)
+    if not os.path.exists(options.policy):
+        sys.exit("Error: policy file " + options.policy + " does not exist\n"
+                + parser.usage)
+
+    if not options.file_contexts:
+        sys.exit("Error: Must specify file_contexts file(s)\n" + parser.usage)
+    for f in options.file_contexts:
+        if not os.path.exists(f):
+            sys.exit("Error: File_contexts file " + f + " does not exist\n" +
+                    parser.usage)
+
+    pol = policy.Policy(options.policy, options.file_contexts, options.libpath)
+
+    results = ""
+    # If an individual test is not specified, run all tests.
+    if options.test is None or "TestDataTypeViolations" in options.tests:
+        results += TestDataTypeViolations(pol)
+    if options.test is None or "TestSysfsTypeViolations" in options.tests:
+        results += TestSysfsTypeViolations(pol)
+    if options.test is None or "TestDebugfsTypeViolations" in options.tests:
+        results += TestDebugfsTypeViolations(pol)
+
+    if len(results) > 0:
+        sys.exit(results)
diff --git a/tests/treble_sepolicy_tests.py b/tests/treble_sepolicy_tests.py
index 3d6a480..2c0cef3 100644
--- a/tests/treble_sepolicy_tests.py
+++ b/tests/treble_sepolicy_tests.py
@@ -1,7 +1,9 @@
 from optparse import OptionParser
 from optparse import Option, OptionValueError
 import os
+import mini_parser
 import policy
+from policy import MatchPathPrefix
 import re
 import sys
 
@@ -69,26 +71,13 @@
 appdomains = set()
 vendordomains = set()
 
-###
-# Check whether the regex will match a file path starting with the provided
-# prefix
-#
-# Compares regex entries in file_contexts with a path prefix. Regex entries
-# are often more specific than this file prefix. For example, the regex could
-# be /system/bin/foo\.sh and the prefix could be /system. This function
-# loops over the regex removing characters from the end until
-# 1) there is a match - return True or 2) run out of characters - return
-#    False.
-#
-def MatchPathPrefix(pathregex, prefix):
-    for i in range(len(pathregex), 0, -1):
-        try:
-            pattern = re.compile('^' + pathregex[0:i] + "$")
-        except:
-            continue
-        if pattern.match(prefix):
-            return True
-    return False
+# compat vars
+alltypes = set()
+oldalltypes = set()
+compatMapping = None
+
+# Distinguish between PRODUCT_FULL_TREBLE and PRODUCT_FULL_TREBLE_OVERRIDE
+FakeTreble = False
 
 def GetAllDomains(pol):
     global alldomains
@@ -107,12 +96,11 @@
             alldomains[d].appdomain = True
             appdomains.add(d)
 
-
 def GetCoreDomains():
     global alldomains
     global coredomains
     for d in alldomains:
-        # TestCoredomainViolators will verify if coredomain was incorrectly
+        # TestCoredomainViolations will verify if coredomain was incorrectly
         # applied.
         if "coredomain" in alldomains[d].attributes:
             alldomains[d].coredomain = True
@@ -144,7 +132,7 @@
 #
 def GetDomainEntrypoints(pol):
     global alldomains
-    for x in pol.QueryTERule(tclass="file", perms=["entrypoint"]):
+    for x in pol.QueryExpandedTERule(tclass=set(["file"]), perms=set(["entrypoint"])):
         if not x.sctx in alldomains:
             continue
         alldomains[x.sctx].entrypoints.append(str(x.tctx))
@@ -167,6 +155,12 @@
         for result in pol.QueryTypeAttribute(domain, False):
             alldomains[domain].attributes.add(result)
 
+def GetAllTypes(pol, oldpol):
+    global alltypes
+    global oldalltypes
+    alltypes = pol.GetAllTypes(False)
+    oldalltypes = oldpol.GetAllTypes(False)
+
 def setup(pol):
     GetAllDomains(pol)
     GetAttributes(pol)
@@ -174,6 +168,21 @@
     GetAppDomains()
     GetCoreDomains()
 
+# setup for the policy compatibility tests
+def compatSetup(pol, oldpol, mapping):
+    global compatMapping
+
+    GetAllTypes(pol, oldpol)
+    compatMapping = mapping
+
+def DomainsWithAttribute(attr):
+    global alldomains
+    domains = []
+    for domain in alldomains:
+        if attr in alldomains[domain].attributes:
+            domains.append(domain)
+    return domains
+
 #############################################################
 # Tests
 #############################################################
@@ -209,6 +218,75 @@
     return ret
 
 ###
+# Make sure that any new type introduced in the new policy that was not present
+# in the old policy has been recorded in the mapping file.
+def TestNoUnmappedNewTypes():
+    global alltypes
+    global oldalltypes
+    global compatMapping
+    newt = alltypes - oldalltypes
+    ret = ""
+    violators = []
+
+    for n in newt:
+        if compatMapping.rTypeattributesets.get(n) is None:
+            violators.append(n)
+
+    if len(violators) > 0:
+        ret += "SELinux: The following types were found added to the policy "
+        ret += "without an entry into the compatibility mapping file(s) found "
+        ret += "in private/compat/" + compatMapping.apiLevel + "/"
+        ret +=  compatMapping.apiLevel + "[.ignore].cil/n"
+        ret += " ".join(str(x) for x in sorted(violators)) + "\n"
+    return ret
+
+###
+# Make sure that any public type removed in the current policy has its
+# declaration added to the mapping file for use in non-platform policy
+def TestNoUnmappedRmTypes():
+    global alltypes
+    global oldalltypes
+    global compatMapping
+    rmt = oldalltypes - alltypes
+    ret = ""
+    violators = []
+
+    for o in rmt:
+        if o in compatMapping.pubtypes and not o in compatMapping.types:
+            violators.append(o)
+
+    if len(violators) > 0:
+        ret += "SELinux: The following formerly public types were removed from "
+        ret += "policy without a declaration in the compatibility mapping "
+        ret += "file(s) found in prebuilts/api/" + compatMapping.apiLevel + "/\n"
+        ret += " ".join(str(x) for x in sorted(violators)) + "\n"
+    return ret
+
+def TestTrebleCompatMapping():
+    ret = TestNoUnmappedNewTypes()
+    ret += TestNoUnmappedRmTypes()
+    return ret
+
+def TestViolatorAttribute(attribute):
+    global FakeTreble
+    ret = ""
+    if FakeTreble:
+        return ret
+
+    violators = DomainsWithAttribute(attribute)
+    if len(violators) > 0:
+        ret += "SELinux: The following domains violate the Treble ban "
+        ret += "against use of the " + attribute + " attribute: "
+        ret += " ".join(str(x) for x in sorted(violators)) + "\n"
+    return ret
+
+def TestViolatorAttributes():
+    ret = TestViolatorAttribute("binder_in_vendor_violators")
+    ret += TestViolatorAttribute("socket_between_core_and_vendor_violators")
+    ret += TestViolatorAttribute("vendor_executes_system_violators")
+    return ret
+
+###
 # extend OptionParser to allow the same option flag to be used multiple times.
 # This is used to allow multiple file_contexts files and tests to be
 # specified.
@@ -225,18 +303,27 @@
         else:
             Option.take_action(self, action, dest, opt, value, values, parser)
 
-Tests = ["CoredomainViolators"]
+Tests = {"CoredomainViolations": TestCoredomainViolations,
+         "TrebleCompatMapping": TestTrebleCompatMapping,
+         "ViolatorAttributes": TestViolatorAttributes}
 
 if __name__ == '__main__':
-    usage = "sepolicy-trebletests -f nonplat_file_contexts -f "
-    usage +="plat_file_contexts -p policy [--test test] [--help]"
+    usage = "treble_sepolicy_tests.py -l out/host/linux-x86/lib64 "
+    usage += "-f nonplat_file_contexts -f plat_file_contexts "
+    usage += "-p curr_policy -b base_policy -o old_policy "
+    usage +="-m mapping file [--test test] [--help]"
     parser = OptionParser(option_class=MultipleOption, usage=usage)
+    parser.add_option("-b", "--basepolicy", dest="basepolicy", metavar="FILE")
     parser.add_option("-f", "--file_contexts", dest="file_contexts",
             metavar="FILE", action="extend", type="string")
-    parser.add_option("-p", "--policy", dest="policy", metavar="FILE")
     parser.add_option("-l", "--library-path", dest="libpath", metavar="FILE")
-    parser.add_option("-t", "--test", dest="test", action="extend",
+    parser.add_option("-m", "--mapping", dest="mapping", metavar="FILE")
+    parser.add_option("-o", "--oldpolicy", dest="oldpolicy", metavar="FILE")
+    parser.add_option("-p", "--policy", dest="policy", metavar="FILE")
+    parser.add_option("-t", "--test", dest="tests", action="extend",
             help="Test options include "+str(Tests))
+    parser.add_option("--fake-treble", action="store_true", dest="faketreble",
+            default=False)
 
     (options, args) = parser.parse_args()
 
@@ -245,9 +332,14 @@
     if not os.path.exists(options.libpath):
         sys.exit("Error: library-path " + options.libpath + " does not exist\n"
                 + parser.usage)
-
+    if not options.basepolicy:
+        sys.exit("Must specify the current platform-only policy file\n" + parser.usage)
+    if not options.mapping:
+        sys.exit("Must specify a compatibility mapping file\n" + parser.usage)
+    if not options.oldpolicy:
+        sys.exit("Must specify the previous monolithic policy file\n" + parser.usage)
     if not options.policy:
-        sys.exit("Must specify monolithic policy file\n" + parser.usage)
+        sys.exit("Must specify current monolithic policy file\n" + parser.usage)
     if not os.path.exists(options.policy):
         sys.exit("Error: policy file " + options.policy + " does not exist\n"
                 + parser.usage)
@@ -259,16 +351,35 @@
             sys.exit("Error: File_contexts file " + f + " does not exist\n" +
                     parser.usage)
 
+    if options.faketreble:
+        FakeTreble = True
+
     pol = policy.Policy(options.policy, options.file_contexts, options.libpath)
     setup(pol)
+    basepol = policy.Policy(options.basepolicy, None, options.libpath)
+    oldpol = policy.Policy(options.oldpolicy, None, options.libpath)
+    mapping = mini_parser.MiniCilParser(options.mapping)
+    compatSetup(basepol, oldpol, mapping)
 
     if DEBUG:
         PrintScontexts()
 
     results = ""
     # If an individual test is not specified, run all tests.
-    if options.test is None or "CoredomainViolations" in options.tests:
-        results += TestCoredomainViolations()
+    if options.tests is None:
+        for t in Tests.values():
+            results += t()
+    else:
+        for tn in options.tests:
+            t = Tests.get(tn)
+            if t:
+                results += t()
+            else:
+                err = "Error: unknown test: " + tn + "\n"
+                err += "Available tests:\n"
+                for tn in Tests.keys():
+                    err += tn + "\n"
+                sys.exit(err)
 
     if len(results) > 0:
         sys.exit(results)