diff --git a/tests/Android.bp b/tests/Android.bp
index abb5e35..670d29d 100644
--- a/tests/Android.bp
+++ b/tests/Android.bp
@@ -63,3 +63,11 @@
     required: ["libsepolwrap"],
     defaults: ["py2_only"],
 }
+
+python_binary_host {
+    name: "combine_maps",
+    srcs: [
+        "combine_maps.py",
+        "mini_parser.py",
+    ],
+}
diff --git a/tests/combine_maps.py b/tests/combine_maps.py
new file mode 100644
index 0000000..a2bf38d
--- /dev/null
+++ b/tests/combine_maps.py
@@ -0,0 +1,66 @@
+# Copyright 2018 - 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.
+
+"""Tool to combine SEPolicy mapping file.
+
+Say, x, y, z are platform SEPolicy versions such that x > y > z. Then given two
+mapping files from x to y (top) and y to z (bottom), it's possible to construct
+a mapping file from x to z. We do the following to combine two maps.
+1. Add all new types declarations from top to bottom.
+2. Say, a new type "bar" in top is mapped like this "foo_V_v<-bar", then we map
+"bar" to whatever "foo" is mapped to in the bottom map. We do this for all new
+types in the top map.
+
+More generally, we can correctly construct x->z from x->y' and y"->z as long as
+y">y'.
+
+This file contains the implementation of combining two mapping files.
+"""
+import argparse
+import re
+from mini_parser import MiniCilParser
+
+def Combine(top, bottom):
+    bottom.types.update(top.types)
+
+    for top_ta in top.typeattributesets:
+        top_type_set = top.typeattributesets[top_ta]
+        if len(top_type_set) == 1:
+            continue
+
+        m = re.match(r"(\w+)_\d+_\d+", top_ta)
+        # Typeattributes in V.v.cil have _V_v suffix, but not in V.v.ignore.cil
+        bottom_type = m.group(1) if m else top_ta
+
+        for bottom_ta in bottom.rTypeattributesets[bottom_type]:
+            bottom.typeattributesets[bottom_ta].update(top_type_set)
+
+    return bottom
+
+if __name__ == "__main__":
+    parser = argparse.ArgumentParser()
+    parser.add_argument("-t", "--top-map", dest="top_map",
+                        required=True, help="top map file")
+    parser.add_argument("-b", "--bottom-map", dest="bottom_map",
+                        required=True, help="bottom map file")
+    parser.add_argument("-o", "--output-file", dest="output_file",
+                        required=True, help="output map file")
+    args = parser.parse_args()
+
+    top_map_cil = MiniCilParser(args.top_map)
+    bottom_map_cil = MiniCilParser(args.bottom_map)
+    result = Combine(top_map_cil, bottom_map_cil)
+
+    with open(args.output_file, "w") as output:
+        output.write(result.unparse())
diff --git a/tests/mini_parser.py b/tests/mini_parser.py
index 9182c5d..cba9e39 100644
--- a/tests/mini_parser.py
+++ b/tests/mini_parser.py
@@ -12,6 +12,7 @@
     def __init__(self, policyFile):
         self.types = set() # types declared in mapping
         self.pubtypes = set()
+        self.expandtypeattributes = {}
         self.typeattributes = set() # attributes declared in mapping
         self.typeattributesets = {} # sets defined in mapping
         self.rTypeattributesets = {} # reverse mapping of above sets
@@ -27,6 +28,32 @@
         if m:
             self.apiLevel = m.group(1)
 
+    def unparse(self):
+        def wrapParens(stmt):
+            return "(" + stmt + ")"
+
+        def joinWrapParens(entries):
+            return wrapParens(" ".join(entries))
+
+        result = ""
+        for ty in sorted(self.types):
+            result += joinWrapParens(["type", ty]) + "\n"
+
+        for ta in sorted(self.typeattributes):
+            result += joinWrapParens(["typeattribute", ta]) + "\n"
+
+        for eta in sorted(self.expandtypeattributes.items(),
+                          key=lambda x: x[0]):
+            result += joinWrapParens(
+                    ["expandtypeattribute", wrapParens(eta[0]), eta[1]]) + "\n"
+
+        for tas in sorted(self.typeattributesets.items(), key=lambda x: x[0]):
+            result += joinWrapParens(
+                    ["typeattributeset", tas[0],
+                     joinWrapParens(sorted(tas[1]))]) + "\n"
+
+        return result
+
     def _getNextStmt(self, infile):
         parens = 0
         s = ""
@@ -55,6 +82,11 @@
         self.types.add(m.group(1))
         return
 
+    def _parseExpandtypeattribute(self, stmt):
+        m = re.match(r"expandtypeattribute\s+\((.+)\)\s+(true|false)", stmt)
+        self.expandtypeattributes[m.group(1)] = m.group(2)
+        return
+
     def _parseTypeattribute(self, stmt):
         m = re.match(r"typeattribute\s+(.+)", stmt)
         self.typeattributes.add(m.group(1))
@@ -73,7 +105,7 @@
         for t in tas:
             if self.rTypeattributesets.get(t) is None:
                 self.rTypeattributesets[t] = set()
-            self.rTypeattributesets[t].update(set(ta))
+            self.rTypeattributesets[t].update([ta])
 
         # check to see if this typeattributeset is a versioned public type
         pub = re.match(r"(\w+)_\d+_\d+", ta)
@@ -88,6 +120,8 @@
             self._parseTypeattribute(stmt)
         elif re.match(r"typeattributeset\s+.+", stmt):
             self._parseTypeattributeset(stmt)
+        elif re.match(r"expandtypeattribute\s+.+", stmt):
+            self._parseExpandtypeattribute(stmt)
         return
 
 if __name__ == '__main__':
diff --git a/tests/treble_sepolicy_tests.py b/tests/treble_sepolicy_tests.py
index 05549a1..f2d600a 100644
--- a/tests/treble_sepolicy_tests.py
+++ b/tests/treble_sepolicy_tests.py
@@ -240,8 +240,8 @@
     if len(violators) > 0:
         ret += "SELinux: The following public types were found added to the "
         ret += "policy without an entry into the compatibility mapping file(s) "
-        ret += "found in private/compat/" + compatMapping.apiLevel + "/"
-        ret +=  compatMapping.apiLevel + "[.ignore].cil\n"
+        ret += "found in private/compat/V.v/V.v[.ignore].cil, where V.v is the "
+        ret += "latest API level.\n"
         ret += " ".join(str(x) for x in sorted(violators)) + "\n"
     return ret
 
@@ -263,7 +263,8 @@
     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 += "found in private/compat/V.v/V.v[.ignore].cil, where V.v is the "
+        ret += "latest API level.\n"
         ret += " ".join(str(x) for x in sorted(violators)) + "\n"
     return ret