Repository: oasis-open/cti-python-stix2
Pull request #222 (2018-11-02 17:05:02)

Multi version filesystem store
Added support for storing/retrieving multiple versions of the same object ID.  Restructured stix2 test data corpus, and added some new versions of existing objects to it.  Updated some tests to test multi-versioning.

This also includes significant updates to search optimization:
- The old optimization strategy was pretty conservative.  It has been made a bit more sophisticated.  Examples include:
    * if you had filters ("type", "=", "foo") and ("type", "=", "bar"), the old algorithm would restrict searches to the "foo" and "bar" type directories.  But you could also recognize that no object can have a type property with two different values at the same time, and not search at all.  Now, it will effectively skip the search.
    * if you had filters like ("type", "=", "foo") and ("type", "!=", "foo"), the old algorithm used the "=" filter and ignored "!=".  The new algorithm will recognize that this is an impossible filter.
    * ID filters now affect type-based optimization, since type names appear in IDs.  E.g. if you had ("type", "=", "foo") and ("id", "=", "bar-123..."), this is recognized as an impossible filter.
    * The "in" filter operator is now used for optimizations (one wonders why there isn't a "not in"...)
- The old algorithm did a recursive search through a type directory.  The new algorithm doesn't.  I don't know if it was ever intended that the json files would be spread out over an arbitrarily nested subdirectory structure.
- The old algorithm did name extension checks, but not file type checks (e.g. regular file vs directory).  The new algorithm will check types.  This would ensure, for example, that a directory named "foo.json" wouldn't be mistaken for a regular JSON file.  Not that it's likely that a directory would be named like that...




Patch:
diff --git a/docs/Makefile b/docs/Makefile
index 0c4ce84..e1582e8 100644
--- a/docs/Makefile
+++ b/docs/Makefile
@@ -17,4 +17,4 @@ help:
 # Catch-all target: route all unknown targets to Sphinx using the new
 # "make mode" option.  $(O) is meant as a shortcut for $(SPHINXOPTS).
 %: Makefile
-	@$(SPHINXBUILD) -M $@ "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
\ No newline at end of file
+	@$(SPHINXBUILD) -M $@ "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
diff --git a/docs/api/datastore/stix2.datastore.filesystem.rst b/docs/api/datastore/stix2.datastore.filesystem.rst
index 665df66..2b0d2ee 100644
--- a/docs/api/datastore/stix2.datastore.filesystem.rst
+++ b/docs/api/datastore/stix2.datastore.filesystem.rst
@@ -2,4 +2,4 @@ filesystem
 ==========================
 
 .. automodule:: stix2.datastore.filesystem
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/datastore/stix2.datastore.filters.rst b/docs/api/datastore/stix2.datastore.filters.rst
index b556754..3c9f0b1 100644
--- a/docs/api/datastore/stix2.datastore.filters.rst
+++ b/docs/api/datastore/stix2.datastore.filters.rst
@@ -2,4 +2,4 @@ filters
 =======================
 
 .. automodule:: stix2.datastore.filters
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/datastore/stix2.datastore.memory.rst b/docs/api/datastore/stix2.datastore.memory.rst
index b0521c7..eda42cb 100644
--- a/docs/api/datastore/stix2.datastore.memory.rst
+++ b/docs/api/datastore/stix2.datastore.memory.rst
@@ -2,4 +2,4 @@ memory
 ======================
 
 .. automodule:: stix2.datastore.memory
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/datastore/stix2.datastore.taxii.rst b/docs/api/datastore/stix2.datastore.taxii.rst
index 68389a0..f1c43bf 100644
--- a/docs/api/datastore/stix2.datastore.taxii.rst
+++ b/docs/api/datastore/stix2.datastore.taxii.rst
@@ -2,4 +2,4 @@ taxii
 =====================
 
 .. automodule:: stix2.datastore.taxii
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/markings/stix2.markings.granular_markings.rst b/docs/api/markings/stix2.markings.granular_markings.rst
index b4a7160..d64ebc9 100644
--- a/docs/api/markings/stix2.markings.granular_markings.rst
+++ b/docs/api/markings/stix2.markings.granular_markings.rst
@@ -2,4 +2,4 @@ granular_markings
 ================================
 
 .. automodule:: stix2.markings.granular_markings
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/markings/stix2.markings.object_markings.rst b/docs/api/markings/stix2.markings.object_markings.rst
index d861c87..8e8de67 100644
--- a/docs/api/markings/stix2.markings.object_markings.rst
+++ b/docs/api/markings/stix2.markings.object_markings.rst
@@ -2,4 +2,4 @@ object_markings
 ==============================
 
 .. automodule:: stix2.markings.object_markings
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/markings/stix2.markings.utils.rst b/docs/api/markings/stix2.markings.utils.rst
index ee59b6c..66793aa 100644
--- a/docs/api/markings/stix2.markings.utils.rst
+++ b/docs/api/markings/stix2.markings.utils.rst
@@ -2,4 +2,4 @@ utils
 ====================
 
 .. automodule:: stix2.markings.utils
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.core.rst b/docs/api/stix2.core.rst
index f0e98d4..dbd5256 100644
--- a/docs/api/stix2.core.rst
+++ b/docs/api/stix2.core.rst
@@ -2,4 +2,4 @@ core
 ==========
 
 .. automodule:: stix2.core
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.datastore.rst b/docs/api/stix2.datastore.rst
index 4af05a9..0d90987 100644
--- a/docs/api/stix2.datastore.rst
+++ b/docs/api/stix2.datastore.rst
@@ -2,4 +2,4 @@ datastore
 ===============
 
 .. automodule:: stix2.datastore
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.environment.rst b/docs/api/stix2.environment.rst
index fb5c7b7..6b44ba5 100644
--- a/docs/api/stix2.environment.rst
+++ b/docs/api/stix2.environment.rst
@@ -2,4 +2,4 @@ environment
 =================
 
 .. automodule:: stix2.environment
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.exceptions.rst b/docs/api/stix2.exceptions.rst
index a8d498e..ad8ddf3 100644
--- a/docs/api/stix2.exceptions.rst
+++ b/docs/api/stix2.exceptions.rst
@@ -2,4 +2,4 @@ exceptions
 ================
 
 .. automodule:: stix2.exceptions
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.markings.rst b/docs/api/stix2.markings.rst
index 9819fe7..881fda1 100644
--- a/docs/api/stix2.markings.rst
+++ b/docs/api/stix2.markings.rst
@@ -2,4 +2,4 @@ markings
 ==============
 
 .. automodule:: stix2.markings
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.patterns.rst b/docs/api/stix2.patterns.rst
index ec7b42c..f95ec34 100644
--- a/docs/api/stix2.patterns.rst
+++ b/docs/api/stix2.patterns.rst
@@ -2,4 +2,4 @@ patterns
 ==============
 
 .. automodule:: stix2.patterns
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.properties.rst b/docs/api/stix2.properties.rst
index c3db9ff..e357ef4 100644
--- a/docs/api/stix2.properties.rst
+++ b/docs/api/stix2.properties.rst
@@ -2,4 +2,4 @@ properties
 ================
 
 .. automodule:: stix2.properties
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.utils.rst b/docs/api/stix2.utils.rst
index 4091fb5..49a1e16 100644
--- a/docs/api/stix2.utils.rst
+++ b/docs/api/stix2.utils.rst
@@ -2,4 +2,4 @@ utils
 ===========
 
 .. automodule:: stix2.utils
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.v20.common.rst b/docs/api/stix2.v20.common.rst
index 0c7a296..8cec059 100644
--- a/docs/api/stix2.v20.common.rst
+++ b/docs/api/stix2.v20.common.rst
@@ -2,4 +2,4 @@ common
 ================
 
 .. automodule:: stix2.v20.common
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.v20.observables.rst b/docs/api/stix2.v20.observables.rst
index d31f75f..4d9803a 100644
--- a/docs/api/stix2.v20.observables.rst
+++ b/docs/api/stix2.v20.observables.rst
@@ -2,4 +2,4 @@ observables
 =====================
 
 .. automodule:: stix2.v20.observables
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.v20.sdo.rst b/docs/api/stix2.v20.sdo.rst
index c4c97f8..a115d5b 100644
--- a/docs/api/stix2.v20.sdo.rst
+++ b/docs/api/stix2.v20.sdo.rst
@@ -2,4 +2,4 @@ sdo
 =============
 
 .. automodule:: stix2.v20.sdo
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.v20.sro.rst b/docs/api/stix2.v20.sro.rst
index 379ed18..397cf29 100644
--- a/docs/api/stix2.v20.sro.rst
+++ b/docs/api/stix2.v20.sro.rst
@@ -2,4 +2,4 @@ sro
 =============
 
 .. automodule:: stix2.v20.sro
-   :members:
\ No newline at end of file
+   :members:
diff --git a/docs/api/stix2.workbench.rst b/docs/api/stix2.workbench.rst
index 19345f0..8fa2544 100644
--- a/docs/api/stix2.workbench.rst
+++ b/docs/api/stix2.workbench.rst
@@ -2,4 +2,4 @@ workbench
 ===============
 
 .. automodule:: stix2.workbench
-   :members:
\ No newline at end of file
+   :members:
diff --git a/stix2/datastore/filesystem.py b/stix2/datastore/filesystem.py
index c13b02c..95c9050 100644
--- a/stix2/datastore/filesystem.py
+++ b/stix2/datastore/filesystem.py
@@ -3,13 +3,362 @@ Python STIX 2.0 FileSystem Source/Sink
 
 """
 
+import errno
 import json
 import os
+import stat
 
+import pytz
+import six
+
+from stix2.base import _STIXBase
 from stix2.core import Bundle, parse
 from stix2.datastore import DataSink, DataSource, DataStoreMixin
 from stix2.datastore.filters import Filter, FilterSet, apply_common_filters
-from stix2.utils import deduplicate, get_class_hierarchy_names
+from stix2.utils import get_type_from_id, is_marking
+
+
+def _timestamp2filename(timestamp):
+    """
+    Encapsulates a way to create unique filenames based on an object's
+    "modified" property value.  This should not include an extension.
+
+    :param timestamp: A timestamp, as a datetime.datetime object.
+    """
+    # Different times will only produce different file names if all timestamps
+    # are in the same time zone!  So if timestamp is timezone-aware convert
+    # to UTC just to be safe.  If naive, just use as-is.
+    if timestamp.tzinfo is not None:
+        timestamp = timestamp.astimezone(pytz.utc)
+
+    return timestamp.strftime("%Y%m%d%H%M%S%f")
+
+
+class AuthSet(object):
+    """
+    Represents either a whitelist or blacklist of values, where/what we
+    must/must not search to find objects which match a query.  (Maybe "AuthSet"
+    isn't the right name, but determining authorization is a typical context in
+    which black/white lists are used.)
+
+    The set may be empty.  For a whitelist, this means you mustn't search
+    anywhere, which means the query was impossible to match, so you can skip
+    searching altogether.  For a blacklist, this means nothing is excluded
+    and you must search everywhere.
+    """
+
+    BLACK = 0
+    WHITE = 1
+
+    def __init__(self, allowed, prohibited):
+        """
+        Initialize this AuthSet from the given sets of allowed and/or
+        prohibited values.  The type of set (black or white) is determined
+        from the allowed and/or prohibited values given.
+
+        :param allowed: A set of allowed values (or None if no allow filters
+            were found in the query)
+        :param prohibited: A set of prohibited values (not None)
+        """
+        if allowed is None:
+            self.__values = prohibited
+            self.__type = AuthSet.BLACK
+
+        else:
+            # There was at least one allow filter, so create a whitelist.  But
+            # any matching prohibited values create a combination of conditions
+            # which can never match.  So exclude those.
+            self.__values = allowed - prohibited
+            self.__type = AuthSet.WHITE
+
+    @property
+    def values(self):
+        """
+        Get the values in this white/blacklist, as a set.
+        """
+        return self.__values
+
+    @property
+    def auth_type(self):
+        """
+        Get the type of set: AuthSet.WHITE or AuthSet.BLACK.
+        """
+        return self.__type
+
+    def __repr__(self):
+        return "{}list: {}".format(
+            "white" if self.auth_type == AuthSet.WHITE else "black",
+            self.values
+        )
+
+
+# A fixed, reusable AuthSet which accepts anything.  It came in handy.
+_AUTHSET_ANY = AuthSet(None, set())
+
+
+def _update_allow(allow_set, value):
+    """
+    Updates the given set of "allow" values.  The first time an update to the
+    set occurs, the value(s) are added.  Thereafter, since all filters are
+    implicitly AND'd, the given values are intersected with the existing allow
+    set, which may remove values.  At the end, it may even wind up empty.
+
+    :param allow_set: The allow set, or None
+    :param value: The value(s) to add (single value, or iterable of values)
+    :return: The updated allow set (not None)
+    """
+    adding_seq = hasattr(value, "__iter__") and \
+        not isinstance(value, six.string_types)
+
+    if allow_set is None:
+        allow_set = set()
+        if adding_seq:
+            allow_set.update(value)
+        else:
+            allow_set.add(value)
+
+    else:
+        # strangely, the "&=" operator requires a set on the RHS
+        # whereas the method allows any iterable.
+        if adding_seq:
+            allow_set.intersection_update(value)
+        else:
+            allow_set.intersection_update({value})
+
+    return allow_set
+
+
+def _find_search_optimizations(filters):
+    """
+    Searches through all the filters, and creates white/blacklists of types and
+    IDs, which can be used to optimize the filesystem search.
+
+    :param filters: An iterable of filter objects representing a query
+    :return: A 2-tuple of AuthSet objects: the first is for object types, and
+        the second is for object IDs.
+    """
+
+    # The basic approach to this is to determine what is allowed and
+    # prohibited, independently, and then combine them to create the final
+    # white/blacklists.
+
+    allowed_types = allowed_ids = None
+    prohibited_types = set()
+    prohibited_ids = set()
+
+    for filter_ in filters:
+        if filter_.property == "type":
+            if filter_.op in ("=", "in"):
+                allowed_types = _update_allow(allowed_types, filter_.value)
+            elif filter_.op == "!=":
+                prohibited_types.add(filter_.value)
+
+        elif filter_.property == "id":
+            if filter_.op == "=":
+                # An "allow" ID filter implies a type filter too, since IDs
+                # contain types within them.
+                allowed_ids = _update_allow(allowed_ids, filter_.value)
+                allowed_types = _update_allow(allowed_types,
+                                              get_type_from_id(filter_.value))
+            elif filter_.op == "!=":
+                prohibited_ids.add(filter_.value)
+            elif filter_.op == "in":
+                allowed_ids = _update_allow(allowed_ids, filter_.value)
+                allowed_types = _update_allow(allowed_types, (
+                    get_type_from_id(id_) for id_ in filter_.value
+                ))
+
+    opt_types = AuthSet(allowed_types, prohibited_types)
+    opt_ids = AuthSet(allowed_ids, prohibited_ids)
+
+    # If we have both type and ID whitelists, perform a type-based intersection
+    # on them, to further optimize.  (Some of the cross-property constraints
+    # occur above; this is essentially a second pass which operates on the
+    # final whitelists, which among other things, incorporates any of the
+    # prohibitions found above.)
+    if opt_types.auth_type == AuthSet.WHITE and \
+            opt_ids.auth_type == AuthSet.WHITE:
+
+        opt_types.values.intersection_update(
+            get_type_from_id(id_) for id_ in opt_ids.values
+        )
+
+        opt_ids.values.intersection_update(
+            id_ for id_ in opt_ids.values
+            if get_type_from_id(id_) in opt_types.values
+        )
+
+    return opt_types, opt_ids
+
+
+def _get_matching_dir_entries(parent_dir, auth_set, st_mode_test=None, ext=""):
+    """
+    Search a directory (non-recursively), and find entries which match the
+    given criteria.
+
+    :param parent_dir: The directory to search
+    :param auth_set: an AuthSet instance, which represents a black/whitelist
+        filter on filenames
+    :param st_mode_test: A callable allowing filtering based on the type of
+        directory entry.  E.g. just get directories, or just get files.  It
+        will be passed the st_mode field of a stat() structure and should
+        return True to include the file, or False to exclude it.  Easy thing to
+        do is pass one of the stat module functions, e.g. stat.S_ISREG.  If
+        None, don't filter based on entry type.
+    :param ext: Determines how names from auth_set match up to directory
+        entries, and allows filtering by extension.  The extension is added
+        to auth_set values to obtain directory entries; it is removed from
+        directory entries to obtain auth_set values.  In this way, auth_set
+        may be treated as having only "basenames" of the entries.  Only entries
+        having the given extension will be included in the results.  If not
+        empty, the extension MUST include a leading ".".  The default is the
+        empty string, which will result in direct comparisons, and no
+        extension-based filtering.
+    :return: A list of directory entries matching the criteria.  These will not
+        have any path info included; they will just be bare names.
+    :raises OSError: If there are errors accessing directory contents or
+        stat()'ing files
+    """
+
+    results = []
+    if auth_set.auth_type == AuthSet.WHITE:
+        for value in auth_set.values:
+            try:
+                filename = value + ext
+                s = os.stat(os.path.join(parent_dir, filename))
+                if not st_mode_test or st_mode_test(s.st_mode):
+                    results.append(filename)
+            except OSError as e:
+                if e.errno != errno.ENOENT:
+                    raise e
+                # else, file-not-found is ok, just skip
+
+    else:  # auth_set is a blacklist
+        for entry in os.listdir(parent_dir):
+            if ext:
+                auth_name, this_ext = os.path.splitext(entry)
+                if this_ext != ext:
+                    continue
+            else:
+                auth_name = entry
+
+            if auth_name in auth_set.values:
+                continue
+
+            try:
+                s = os.stat(os.path.join(parent_dir, entry))
+                if not st_mode_test or st_mode_test(s.st_mode):
+                    results.append(entry)
+            except OSError as e:
+                if e.errno != errno.ENOENT:
+                    raise e
+                # else, file-not-found is ok, just skip
+
+    return results
+
+
+def _check_object_from_file(query, filepath):
+    """
+    Read a STIX object from the given file, and check it against the given
+    filters.
+
+    :param query: Iterable of filters
+    :param filepath: Path to file to read
+    :return: The STIX object, as a dict, if the object passes the filters.  If
+        not, None is returned.
+    :raises TypeError: If the file had invalid content
+    :raises IOError: If there are problems opening/reading the file
+    """
+    try:
+        with open(filepath, "r") as f:
+            stix_obj = json.load(f)
+
+        if stix_obj["type"] == "bundle":
+            stix_obj = stix_obj["objects"][0]
+
+        # naive STIX type checking
+        stix_obj["type"]
+        stix_obj["id"]
+
+    except (ValueError, KeyError):  # likely not a JSON file
+        raise TypeError(
+            "STIX JSON object at '{0}' could either not be parsed "
+            "to JSON or was not valid STIX JSON".format(
+                filepath))
+
+    # check against other filters, add if match
+    result = next(apply_common_filters([stix_obj], query), None)
+
+    return result
+
+
+def _search_versioned(query, type_path, auth_ids):
+    """
+    Searches the given directory, which contains data for STIX objects of a
+    particular versioned type (i.e. not markings), and return any which match
+    the query.
+
+    :param query: The query to match against
+    :param type_path: The directory with type-specific STIX object files
+    :param auth_ids: Search optimization based on object ID
+    :return: A list of all matching objects
+    :raises TypeError: If any objects had invalid content
+    :raises IOError, OSError: If there were any problems opening/reading files
+    """
+    results = []
+    id_dirs = _get_matching_dir_entries(type_path, auth_ids,
+                                        stat.S_ISDIR)
+    for id_dir in id_dirs:
+        id_path = os.path.join(type_path, id_dir)
+
+        # This leverages a more sophisticated function to do a simple thing:
+        # get all the JSON files from a directory.  I guess it does give us
+        # file type checking, ensuring we only get regular files.
+        version_files = _get_matching_dir_entries(id_path, _AUTHSET_ANY,
+                                                  stat.S_ISREG, ".json")
+        for version_file in version_files:
+            version_path = os.path.join(id_path, version_file)
+
+            try:
+                stix_obj = _check_object_from_file(query, version_path)
+                if stix_obj:
+                    results.append(stix_obj)
+            except IOError as e:
+                if e.errno != errno.ENOENT:
+                    raise e
+                # else, file-not-found is ok, just skip
+
+    return results
+
+
+def _search_markings(query, markings_path, auth_ids):
+    """
+    Searches the given directory, which contains markings data, and return any
+    which match the query.
+
+    :param query: The query to match against
+    :param markings_path: The directory with STIX markings files
+    :param auth_ids: Search optimization based on object ID
+    :return: A list of all matching objects
+    :raises TypeError: If any objects had invalid content
+    :raises IOError: If there were any problems opening/reading files
+    """
+    results = []
+    id_files = _get_matching_dir_entries(markings_path, auth_ids, stat.S_ISREG,
+                                         ".json")
+    for id_file in id_files:
+        id_path = os.path.join(markings_path, id_file)
+
+        try:
+            stix_obj = _check_object_from_file(query, id_path)
+            if stix_obj:
+                results.append(stix_obj)
+        except IOError as e:
+            if e.errno != errno.ENOENT:
+                raise e
+            # else, file-not-found is ok, just skip
+
+    return results
 
 
 class FileSystemStore(DataStoreMixin):
@@ -77,15 +426,23 @@ class FileSystemSink(DataSink):
     def _check_path_and_write(self, stix_obj):
         """Write the given STIX object to a file in the STIX file directory.
         """
-        path = os.path.join(self._stix_dir, stix_obj["type"], stix_obj["id"] + ".json")
+        type_dir = os.path.join(self._stix_dir, stix_obj["type"])
+        if is_marking(stix_obj):
+            filename = stix_obj["id"]
+            obj_dir = type_dir
+        else:
+            filename = _timestamp2filename(stix_obj["modified"])
+            obj_dir = os.path.join(type_dir, stix_obj["id"])
+
+        file_path = os.path.join(obj_dir, filename + ".json")
 
-        if not os.path.exists(os.path.dirname(path)):
-            os.makedirs(os.path.dirname(path))
+        if not os.path.exists(obj_dir):
+            os.makedirs(obj_dir)
 
         if self.bundlify:
             stix_obj = Bundle(stix_obj, allow_custom=self.allow_custom)
 
-        with open(path, "w") as f:
+        with open(file_path, "w") as f:
             f.write(str(stix_obj))
 
     def add(self, stix_data=None, version=None):
@@ -104,25 +461,18 @@ class FileSystemSink(DataSink):
             the Bundle contained, but not the Bundle itself.
 
         """
-        if any(x in ('STIXDomainObject', 'STIXRelationshipObject', 'MarkingDefinition')
-               for x in get_class_hierarchy_names(stix_data)):
+        if isinstance(stix_data, Bundle):
+            # recursively add individual STIX objects
+            for stix_obj in stix_data.get("objects", []):
+                self.add(stix_obj, version=version)
+
+        elif isinstance(stix_data, _STIXBase):
             # adding python STIX object
             self._check_path_and_write(stix_data)
 
         elif isinstance(stix_data, (str, dict)):
             stix_data = parse(stix_data, allow_custom=self.allow_custom, version=version)
-            if stix_data["type"] == "bundle":
-                # extract STIX objects
-                for stix_obj in stix_data.get("objects", []):
-                    self.add(stix_obj, version=version)
-            else:
-                # adding json-formatted STIX
-                self._check_path_and_write(stix_data,)
-
-        elif isinstance(stix_data, Bundle):
-            # recursively add individual STIX objects
-            for stix_obj in stix_data.get("objects", []):
-                self.add(stix_obj, version=version)
+            self.add(stix_data, version=version)
 
         elif isinstance(stix_data, list):
             # recursively add individual STIX objects
@@ -176,12 +526,15 @@ class FileSystemSource(DataSource):
                 a python STIX object and then returned
 
         """
-        query = [Filter("id", "=", stix_id)]
-
-        all_data = self.query(query=query, version=version, _composite_filters=_composite_filters)
+        all_data = self.all_versions(stix_id, version=version, _composite_filters=_composite_filters)
 
         if all_data:
-            stix_obj = sorted(all_data, key=lambda k: k['modified'])[0]
+            if is_marking(stix_id):
+                # Markings are unversioned; there shouldn't be more than one
+                # result.
+                stix_obj = all_data[0]
+            else:
+                stix_obj = sorted(all_data, key=lambda k: k['modified'])[-1]
         else:
             stix_obj = None
 
@@ -206,7 +559,8 @@ class FileSystemSource(DataSource):
                 a python STIX objects and then returned
 
         """
-        return [self.get(stix_id=stix_id, version=version, _composite_filters=_composite_filters)]
+        query = [Filter("id", "=", stix_id)]
+        return self.query(query, version=version, _composite_filters=_composite_filters)
 
     def query(self, query=None, version=None, _composite_filters=None):
         """Search and retrieve STIX objects based on the complete query.
@@ -239,105 +593,25 @@ class FileSystemSource(DataSource):
         if _composite_filters:
             query.add(_composite_filters)
 
-        # extract any filters that are for "type" or "id" , as we can then do
-        # filtering before reading in the STIX objects. A STIX 'type' filter
-        # can reduce the query to a single sub-directory. A STIX 'id' filter
-        # allows for the fast checking of the file names versus loading it.
-        file_filters = self._parse_file_filters(query)
-
-        # establish which subdirectories can be avoided in query
-        # by decluding as many as possible. A filter with "type" as the property
-        # means that certain STIX object types can be ruled out, and thus
-        # the corresponding subdirectories as well
-        include_paths = []
-        declude_paths = []
-        if "type" in [filter.property for filter in file_filters]:
-            for filter in file_filters:
-                if filter.property == "type":
-                    if filter.op == "=":
-                        include_paths.append(os.path.join(self._stix_dir, filter.value))
-                    elif filter.op == "!=":
-                        declude_paths.append(os.path.join(self._stix_dir, filter.value))
-        else:
-            # have to walk entire STIX directory
-            include_paths.append(self._stix_dir)
-
-        # if a user specifies a "type" filter like "type = <stix-object_type>",
-        # the filter is reducing the search space to single stix object types
-        # (and thus single directories). This makes such a filter more powerful
-        # than "type != <stix-object_type>" bc the latter is substracting
-        # only one type of stix object type (and thus only one directory),
-        # As such the former type of filters are given preference over the latter;
-        # i.e. if both exist in a query, that latter type will be ignored
-
-        if not include_paths:
-            # user has specified types that are not wanted (i.e. "!=")
-            # so query will look in all STIX directories that are not
-            # the specified type. Compile correct dir paths
-            for dir in os.listdir(self._stix_dir):
-                if os.path.abspath(os.path.join(self._stix_dir, dir)) not in declude_paths:
-                    include_paths.append(os.path.abspath(os.path.join(self._stix_dir, dir)))
-
-        # grab stix object ID as well - if present in filters, as
-        # may forgo the loading of STIX content into memory
-        if "id" in [filter.property for filter in file_filters]:
-            for filter in file_filters:
-                if filter.property == "id" and filter.op == "=":
-                    id_ = filter.value
-                    break
-            else:
-                id_ = None
-        else:
-            id_ = None
-
-        # now iterate through all STIX objs
-        for path in include_paths:
-            for root, dirs, files in os.walk(path):
-                for file_ in files:
-                    if not file_.endswith(".json"):
-                        # skip non '.json' files as more likely to be random non-STIX files
-                        continue
-
-                    if not id_ or id_ == file_.split(".")[0]:
-                        # have to load into memory regardless to evaluate other filters
-                        try:
-                            stix_obj = json.load(open(os.path.join(root, file_)))
-
-                            if stix_obj["type"] == "bundle":
-                                stix_obj = stix_obj["objects"][0]
-
-                            # naive STIX type checking
-                            stix_obj["type"]
-                            stix_obj["id"]
+        auth_types, auth_ids = _find_search_optimizations(query)
 
-                        except (ValueError, KeyError):  # likely not a JSON file
-                            raise TypeError("STIX JSON object at '{0}' could either not be parsed to "
-                                            "JSON or was not valid STIX JSON".format(os.path.join(root, file_)))
+        type_dirs = _get_matching_dir_entries(self._stix_dir, auth_types,
+                                              stat.S_ISDIR)
+        for type_dir in type_dirs:
+            type_path = os.path.join(self._stix_dir, type_dir)
 
-                        # check against other filters, add if match
-                        all_data.extend(apply_common_filters([stix_obj], query))
+            if type_dir == "marking-definition":
+                type_results = _search_markings(query, type_path, auth_ids)
+            else:
+                type_results = _search_versioned(query, type_path, auth_ids)
 
-        all_data = deduplicate(all_data)
+            all_data.extend(type_results)
 
         # parse python STIX objects from the STIX object dicts
-        stix_objs = [parse(stix_obj_dict, allow_custom=self.allow_custom, version=version) for stix_obj_dict in all_data]
+        stix_objs = [
+            parse(stix_obj_dict, allow_custom=self.allow_custom,
+                  version=version)
+            for stix_obj_dict in all_data
+        ]
 
         return stix_objs
-
-    def _parse_file_filters(self, query):
-        """Extract STIX common filters.
-
-        Possibly speeds up querying STIX objects from the file system.
-
-        Extracts filters that are for the "id" and "type" property of
-        a STIX object. As the file directory is organized by STIX
-        object type with filenames that are equivalent to the STIX
-        object ID, these filters can be used first to reduce the
-        search space of a FileSystemStore (or FileSystemSink).
-
-        """
-        file_filters = []
-        for filter_ in query:
-            if filter_.property == "id" or filter_.property == "type":
-                file_filters.append(filter_)
-        return file_filters
diff --git a/stix2/datastore/memory.py b/stix2/datastore/memory.py
index 4b82c34..3e065ad 100644
--- a/stix2/datastore/memory.py
+++ b/stix2/datastore/memory.py
@@ -10,6 +10,7 @@ from stix2.base import _STIXBase
 from stix2.core import Bundle, parse
 from stix2.datastore import DataSink, DataSource, DataStoreMixin
 from stix2.datastore.filters import FilterSet, apply_common_filters
+from stix2.utils import is_marking
 
 
 def _add(store, stix_data=None, allow_custom=True, version=None):
@@ -43,7 +44,7 @@ def _add(store, stix_data=None, allow_custom=True, version=None):
 
         # Map ID directly to the object, if it is a marking.  Otherwise,
         # map to a family, so we can track multiple versions.
-        if _is_marking(stix_obj):
+        if is_marking(stix_obj):
             store._data[stix_obj.id] = stix_obj
 
         else:
@@ -56,22 +57,6 @@ def _add(store, stix_data=None, allow_custom=True, version=None):
             obj_family.add(stix_obj)
 
 
-def _is_marking(obj_or_id):
-    """Determines whether the given object or object ID is/is for a marking
-    definition.
-
-    :param obj_or_id: A STIX object or object ID as a string.
-    :return: True if a marking definition, False otherwise.
-    """
-
-    if isinstance(obj_or_id, _STIXBase):
-        id_ = obj_or_id.id
-    else:
-        id_ = obj_or_id
-
-    return id_.startswith("marking-definition--")
-
-
 class _ObjectFamily(object):
     """
     An internal implementation detail of memory sources/sinks/stores.
@@ -255,7 +240,7 @@ class MemorySource(DataSource):
         """
         stix_obj = None
 
-        if _is_marking(stix_id):
+        if is_marking(stix_id):
             stix_obj = self._data.get(stix_id)
         else:
             object_family = self._data.get(stix_id)
@@ -291,7 +276,7 @@ class MemorySource(DataSource):
         """
         results = []
         stix_objs_to_filter = None
-        if _is_marking(stix_id):
+        if is_marking(stix_id):
             stix_obj = self._data.get(stix_id)
             if stix_obj:
                 stix_objs_to_filter = [stix_obj]
diff --git a/stix2/utils.py b/stix2/utils.py
index 64c4a32..63b3d45 100644
--- a/stix2/utils.py
+++ b/stix2/utils.py
@@ -7,6 +7,8 @@ import json
 from dateutil import parser
 import pytz
 
+import stix2.base
+
 from .exceptions import (InvalidValueError, RevokeError,
                          UnmodifiablePropertyError)
 
@@ -364,3 +366,20 @@ def remove_custom_stix(stix_obj):
 
 def get_type_from_id(stix_id):
     return stix_id.split('--', 1)[0]
+
+
+def is_marking(obj_or_id):
+    """Determines whether the given object or object ID is/is for a marking
+    definition.
+
+    :param obj_or_id: A STIX object or object ID as a string.
+    :return: True if a marking definition, False otherwise.
+    """
+
+    if isinstance(obj_or_id, (stix2.base._STIXBase, dict)):
+        result = obj_or_id["type"] == "marking-definition"
+    else:
+        # it's a string ID
+        result = obj_or_id.startswith("marking-definition--")
+
+    return result


Test patch:
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--0a3ead4e-6d47-4ccb-854c-a6a4f9d96b22.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--0a3ead4e-6d47-4ccb-854c-a6a4f9d96b22/20170531213019735010.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--0a3ead4e-6d47-4ccb-854c-a6a4f9d96b22.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--0a3ead4e-6d47-4ccb-854c-a6a4f9d96b22/20170531213019735010.json
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--0f20e3cb-245b-4a61-8a91-2d93f7cb0e9b.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--0f20e3cb-245b-4a61-8a91-2d93f7cb0e9b/20170531213026496201.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--0f20e3cb-245b-4a61-8a91-2d93f7cb0e9b.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--0f20e3cb-245b-4a61-8a91-2d93f7cb0e9b/20170531213026496201.json
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--774a3188-6ba9-4dc4-879d-d54ee48a5ce9.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--774a3188-6ba9-4dc4-879d-d54ee48a5ce9/20170531213029458940.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--774a3188-6ba9-4dc4-879d-d54ee48a5ce9.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--774a3188-6ba9-4dc4-879d-d54ee48a5ce9/20170531213029458940.json
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--7e150503-88e7-4861-866b-ff1ac82c4475.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--7e150503-88e7-4861-866b-ff1ac82c4475/20170531213045139269.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--7e150503-88e7-4861-866b-ff1ac82c4475.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--7e150503-88e7-4861-866b-ff1ac82c4475/20170531213045139269.json
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--ae676644-d2d2-41b7-af7e-9bed1b55898c.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--ae676644-d2d2-41b7-af7e-9bed1b55898c/20170531213041022897.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--ae676644-d2d2-41b7-af7e-9bed1b55898c.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--ae676644-d2d2-41b7-af7e-9bed1b55898c/20170531213041022897.json
diff --git a/stix2/test/stix2_data/attack-pattern/attack-pattern--b3d682b6-98f2-4fb0-aa3b-b4df007ca70a.json b/stix2/test/stix2_data/attack-pattern/attack-pattern--b3d682b6-98f2-4fb0-aa3b-b4df007ca70a/20170531213032662702.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/attack-pattern/attack-pattern--b3d682b6-98f2-4fb0-aa3b-b4df007ca70a.json
rename to stix2/test/stix2_data/attack-pattern/attack-pattern--b3d682b6-98f2-4fb0-aa3b-b4df007ca70a/20170531213032662702.json
diff --git a/stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f.json b/stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f/20170531213026495974.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f.json
rename to stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f/20170531213026495974.json
index bf14aa7..541ede1
--- a/stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f.json
+++ b/stix2/test/stix2_data/course-of-action/course-of-action--95ddb356-7ba0-4bd9-a889-247262b8946f/20170531213026495974.json
@@ -13,4 +13,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd.json b/stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd/20170531213041022744.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd.json
rename to stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd/20170531213041022744.json
index cb9cfe2..669aae5
--- a/stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd.json
+++ b/stix2/test/stix2_data/course-of-action/course-of-action--d9727aee-48b8-4fdb-89e2-4c49746ba4dd/20170531213041022744.json
@@ -6,4 +6,4 @@
     "modified": "2017-05-31T21:30:41.022744Z",
     "name": "Data from Network Shared Drive Mitigation",
     "type": "course-of-action"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5.json b/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20170601000000000000.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5.json
rename to stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20170601000000000000.json
index 77d4464..d110a09
--- a/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5.json
+++ b/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20170601000000000000.json
@@ -12,4 +12,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20181101232448446000.json b/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20181101232448446000.json
new file mode 100644
index 0000000..7528b44
--- /dev/null
+++ b/stix2/test/stix2_data/identity/identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5/20181101232448446000.json
@@ -0,0 +1,11 @@
+{
+    "type": "identity",
+    "id": "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5",
+    "created": "2017-06-01T00:00:00.000Z",
+    "modified": "2018-11-01T23:24:48.446Z",
+    "name": "The MITRE Corporation",
+    "identity_class": "organization",
+    "labels": [
+        "version two"
+    ]
+}
diff --git a/stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064.json b/stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064/20170531213149412497.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064.json
rename to stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064/20170531213149412497.json
index 10ef3a5..648ed94
--- a/stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064.json
+++ b/stix2/test/stix2_data/intrusion-set/intrusion-set--a653431d-6a5e-4600-8ad3-609b5af57064/20170531213149412497.json
@@ -51,4 +51,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a.json b/stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a/20170531213153197755.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a.json
rename to stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a/20170531213153197755.json
index 84b75b1..bf3daa6
--- a/stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a.json
+++ b/stix2/test/stix2_data/intrusion-set/intrusion-set--f3bdec95-3d62-42d9-a840-29630f6cdc1a/20170531213153197755.json
@@ -41,4 +41,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38.json b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20170531213258226477.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38.json
rename to stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20170531213258226477.json
index 669f00c..c60200b
--- a/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38.json
+++ b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20170531213258226477.json
@@ -31,4 +31,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448456000.json b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448456000.json
new file mode 100644
index 0000000..af47f27
--- /dev/null
+++ b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448456000.json
@@ -0,0 +1,27 @@
+{
+    "type": "malware",
+    "id": "malware--6b616fc1-1505-48e3-8b2c-0d19337bff38",
+    "created_by_ref": "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5",
+    "created": "2017-05-31T21:32:58.226Z",
+    "modified": "2018-11-01T23:24:48.456Z",
+    "name": "Rover",
+    "description": "Rover is malware suspected of being used for espionage purposes. It was used in 2015 in a targeted email sent to an Indian Ambassador to Afghanistan.[[Citation: Palo Alto Rover]]",
+    "labels": [
+        "version two"
+    ],
+    "external_references": [
+        {
+            "source_name": "mitre-attack",
+            "url": "https://attack.mitre.org/wiki/Software/S0090",
+            "external_id": "S0090"
+        },
+        {
+            "source_name": "Palo Alto Rover",
+            "description": "Ray, V., Hayashi, K. (2016, February 29). New Malware \u2018Rover\u2019 Targets Indian Ambassador to Afghanistan. Retrieved February 29, 2016.",
+            "url": "http://researchcenter.paloaltonetworks.com/2016/02/new-malware-rover-targets-indian-ambassador-to-afghanistan/"
+        }
+    ],
+    "object_marking_refs": [
+        "marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168"
+    ]
+}
diff --git a/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448457000.json b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448457000.json
new file mode 100644
index 0000000..446fb26
--- /dev/null
+++ b/stix2/test/stix2_data/malware/malware--6b616fc1-1505-48e3-8b2c-0d19337bff38/20181101232448457000.json
@@ -0,0 +1,27 @@
+{
+    "type": "malware",
+    "id": "malware--6b616fc1-1505-48e3-8b2c-0d19337bff38",
+    "created_by_ref": "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5",
+    "created": "2017-05-31T21:32:58.226Z",
+    "modified": "2018-11-01T23:24:48.457Z",
+    "name": "Rover",
+    "description": "Rover is malware suspected of being used for espionage purposes. It was used in 2015 in a targeted email sent to an Indian Ambassador to Afghanistan.[[Citation: Palo Alto Rover]]",
+    "labels": [
+        "version three"
+    ],
+    "external_references": [
+        {
+            "source_name": "mitre-attack",
+            "url": "https://attack.mitre.org/wiki/Software/S0090",
+            "external_id": "S0090"
+        },
+        {
+            "source_name": "Palo Alto Rover",
+            "description": "Ray, V., Hayashi, K. (2016, February 29). New Malware \u2018Rover\u2019 Targets Indian Ambassador to Afghanistan. Retrieved February 29, 2016.",
+            "url": "http://researchcenter.paloaltonetworks.com/2016/02/new-malware-rover-targets-indian-ambassador-to-afghanistan/"
+        }
+    ],
+    "object_marking_refs": [
+        "marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168"
+    ]
+}
diff --git a/stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841.json b/stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841/20170531213326565056.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841.json
rename to stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841/20170531213326565056.json
index 9eaf8ad..50c8a5d
--- a/stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841.json
+++ b/stix2/test/stix2_data/malware/malware--92ec0cbd-2c30-44a2-b270-73f4ec949841/20170531213326565056.json
@@ -31,4 +31,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/malware/malware--96b08451-b27a-4ff6-893f-790e26393a8e.json b/stix2/test/stix2_data/malware/malware--96b08451-b27a-4ff6-893f-790e26393a8e/20170531213248482655.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/malware/malware--96b08451-b27a-4ff6-893f-790e26393a8e.json
rename to stix2/test/stix2_data/malware/malware--96b08451-b27a-4ff6-893f-790e26393a8e/20170531213248482655.json
diff --git a/stix2/test/stix2_data/malware/malware--b42378e0-f147-496f-992a-26a49705395b.json b/stix2/test/stix2_data/malware/malware--b42378e0-f147-496f-992a-26a49705395b/20170531213215263882.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/malware/malware--b42378e0-f147-496f-992a-26a49705395b.json
rename to stix2/test/stix2_data/malware/malware--b42378e0-f147-496f-992a-26a49705395b/20170531213215263882.json
diff --git a/stix2/test/stix2_data/marking-definition/marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168.json b/stix2/test/stix2_data/marking-definition/marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168.json
index bcae183..be93c62 100755
--- a/stix2/test/stix2_data/marking-definition/marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168.json
+++ b/stix2/test/stix2_data/marking-definition/marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168.json
@@ -13,4 +13,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883.json b/stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883/20170531213327182784.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883.json
rename to stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883/20170531213327182784.json
index ac59925..0f4a32a
--- a/stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883.json
+++ b/stix2/test/stix2_data/relationship/relationship--0d4a7788-7f3b-4df8-a498-31a38003c883/20170531213327182784.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227.json b/stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227/20170531213327082801.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227.json
rename to stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227/20170531213327082801.json
index ee97edf..e5e1e87
--- a/stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227.json
+++ b/stix2/test/stix2_data/relationship/relationship--0e55ee98-0c6d-43d4-b424-b18a0036b227/20170531213327082801.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432.json b/stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432/20170531213327018782.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432.json
rename to stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432/20170531213327018782.json
index ff0d8cc..9651425
--- a/stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432.json
+++ b/stix2/test/stix2_data/relationship/relationship--1e91cd45-a725-4965-abe3-700694374432/20170531213327018782.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e.json b/stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e/20170531213327100701.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e.json
rename to stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e/20170531213327100701.json
index 36d1482..7e355fc
--- a/stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e.json
+++ b/stix2/test/stix2_data/relationship/relationship--3a3084f9-0302-4fd5-9b8a-e0db10f5345e/20170531213327100701.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1.json b/stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1/20170531213327143973.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1.json
rename to stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1/20170531213327143973.json
index 888cc3b..f537309
--- a/stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1.json
+++ b/stix2/test/stix2_data/relationship/relationship--3a3ed0b2-0c38-441f-ac40-53b873e545d1/20170531213327143973.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719.json b/stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719/20170531213327021562.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719.json
rename to stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719/20170531213327021562.json
index d9078d1..47008f0
--- a/stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719.json
+++ b/stix2/test/stix2_data/relationship/relationship--592d0c31-e61f-495e-a60e-70d7be59a719/20170531213327021562.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1.json b/stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1/20170531213327044387.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1.json
rename to stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1/20170531213327044387.json
index ef1c4b2..d697277
--- a/stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1.json
+++ b/stix2/test/stix2_data/relationship/relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1/20170531213327044387.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d.json b/stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d/20170531213327051532.json
old mode 100755
new mode 100644
similarity index 99%
rename from stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d.json
rename to stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d/20170531213327051532.json
index 1f20179..d7f2ff7
--- a/stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d.json
+++ b/stix2/test/stix2_data/relationship/relationship--8797579b-e3be-4209-a71b-255a4d08243d/20170531213327051532.json
@@ -17,4 +17,4 @@
     ],
     "spec_version": "2.0",
     "type": "bundle"
-}
\ No newline at end of file
+}
diff --git a/stix2/test/stix2_data/tool/tool--03342581-f790-4f03-ba41-e82e67392e23.json b/stix2/test/stix2_data/tool/tool--03342581-f790-4f03-ba41-e82e67392e23/20170531213231601148.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/tool/tool--03342581-f790-4f03-ba41-e82e67392e23.json
rename to stix2/test/stix2_data/tool/tool--03342581-f790-4f03-ba41-e82e67392e23/20170531213231601148.json
diff --git a/stix2/test/stix2_data/tool/tool--242f3da3-4425-4d11-8f5c-b842886da966.json b/stix2/test/stix2_data/tool/tool--242f3da3-4425-4d11-8f5c-b842886da966/20170531213212684914.json
old mode 100755
new mode 100644
similarity index 100%
rename from stix2/test/stix2_data/tool/tool--242f3da3-4425-4d11-8f5c-b842886da966.json
rename to stix2/test/stix2_data/tool/tool--242f3da3-4425-4d11-8f5c-b842886da966/20170531213212684914.json
diff --git a/stix2/test/test_datastore_filesystem.py b/stix2/test/test_datastore_filesystem.py
index 17661d0..0f0ca0a 100644
--- a/stix2/test/test_datastore_filesystem.py
+++ b/stix2/test/test_datastore_filesystem.py
@@ -1,12 +1,20 @@
+import datetime
+import errno
 import json
 import os
 import shutil
+import stat
 
 import pytest
+import pytz
 
 from stix2 import (Bundle, Campaign, CustomObject, FileSystemSink,
                    FileSystemSource, FileSystemStore, Filter, Identity,
-                   Indicator, Malware, Relationship, properties)
+                   Indicator, Malware, MarkingDefinition, Relationship,
+                   TLPMarking, parse, properties)
+from stix2.datastore.filesystem import (AuthSet, _find_search_optimizations,
+                                        _get_matching_dir_entries,
+                                        _timestamp2filename)
 from stix2.test.constants import (CAMPAIGN_ID, CAMPAIGN_KWARGS, IDENTITY_ID,
                                   IDENTITY_KWARGS, INDICATOR_ID,
                                   INDICATOR_KWARGS, MALWARE_ID, MALWARE_KWARGS,
@@ -97,7 +105,20 @@ def rel_fs_store():
     yield fs
 
     for o in stix_objs:
-        os.remove(os.path.join(FS_PATH, o.type, o.id + '.json'))
+        filepath = os.path.join(FS_PATH, o.type, o.id,
+                                _timestamp2filename(o.modified) + '.json')
+
+        # Some test-scoped fixtures (e.g. fs_store) delete all campaigns, so by
+        # the time this module-scoped fixture tears itself down, it may find
+        # its campaigns already gone, which causes not-found errors.
+        try:
+            os.remove(filepath)
+        except OSError as e:
+            # 3 is the ERROR_PATH_NOT_FOUND windows error code.  Which has an
+            # errno symbolic value, but not the windows meaning...
+            if e.errno in (errno.ENOENT, 3):
+                continue
+            raise e
 
 
 def test_filesystem_source_nonexistent_folder():
@@ -132,27 +153,32 @@ def test_filesystem_source_bad_stix_file(fs_source, bad_stix_files):
         assert "could either not be parsed to JSON or was not valid STIX JSON" in str(e)
 
 
-def test_filesytem_source_get_object(fs_source):
-    # get object
+def test_filesystem_source_get_object(fs_source):
+    # get (latest) object
     mal = fs_source.get("malware--6b616fc1-1505-48e3-8b2c-0d19337bff38")
     assert mal.id == "malware--6b616fc1-1505-48e3-8b2c-0d19337bff38"
     assert mal.name == "Rover"
+    assert mal.modified == datetime.datetime(2018, 11, 1, 23, 24, 48, 457000,
+                                             pytz.utc)
 
 
-def test_filesytem_source_get_nonexistent_object(fs_source):
+def test_filesystem_source_get_nonexistent_object(fs_source):
     ind = fs_source.get("indicator--6b616fc1-1505-48e3-8b2c-0d19337bff38")
     assert ind is None
 
 
-def test_filesytem_source_all_versions(fs_source):
-    # all versions - (currently not a true all versions call as FileSystem cant have multiple versions)
-    id_ = fs_source.get("identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5")
-    assert id_.id == "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5"
-    assert id_.name == "The MITRE Corporation"
-    assert id_.type == "identity"
+def test_filesystem_source_all_versions(fs_source):
+    ids = fs_source.all_versions(
+        "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5"
+    )
+    assert len(ids) == 2
+    assert all(id_.id == "identity--c78cb6e5-0c4b-4611-8297-d1b8b55e40b5"
+               for id_ in ids)
+    assert all(id_.name == "The MITRE Corporation" for id_ in ids)
+    assert all(id_.type == "identity" for id_ in ids)
 
 
-def test_filesytem_source_query_single(fs_source):
+def test_filesystem_source_query_single(fs_source):
     # query2
     is_2 = fs_source.query([Filter("external_references.external_id", '=', "T1027")])
     assert len(is_2) == 1
@@ -182,14 +208,16 @@ def test_filesystem_sink_add_python_stix_object(fs_sink, fs_source):
 
     fs_sink.add(camp1)
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", camp1.id + ".json"))
+    filepath = os.path.join(FS_PATH, "campaign", camp1.id,
+                            _timestamp2filename(camp1.modified) + ".json")
+    assert os.path.exists(filepath)
 
     camp1_r = fs_source.get(camp1.id)
     assert camp1_r.id == camp1.id
     assert camp1_r.name == "Hannibal"
     assert "War Elephant" in camp1_r.aliases
 
-    os.remove(os.path.join(FS_PATH, "campaign", camp1_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_sink_add_stix_object_dict(fs_sink, fs_source):
@@ -200,19 +228,30 @@ def test_filesystem_sink_add_stix_object_dict(fs_sink, fs_source):
         "objective": "German and French Intelligence Services",
         "aliases": ["Purple Robes"],
         "id": "campaign--8e2e2d2b-17d4-4cbf-938f-98ee46b3cd3f",
-        "created": "2017-05-31T21:31:53.197755Z"
+        "created": "2017-05-31T21:31:53.197755Z",
+        "modified": "2017-05-31T21:31:53.197755Z"
     }
 
     fs_sink.add(camp2)
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", camp2["id"] + ".json"))
+    # Need to get the exact "modified" timestamp which would have been
+    # in effect at the time the object was saved to the sink, which determines
+    # the filename it would have been saved as.  It may not be exactly the same
+    # as what's in the dict, since the parsing process can enforce a precision
+    # constraint (e.g. truncate to milliseconds), which results in a slightly
+    # different name.
+    camp2obj = parse(camp2)
+    filepath = os.path.join(FS_PATH, "campaign", camp2obj["id"],
+                            _timestamp2filename(camp2obj["modified"]) + ".json")
+
+    assert os.path.exists(filepath)
 
     camp2_r = fs_source.get(camp2["id"])
     assert camp2_r.id == camp2["id"]
     assert camp2_r.name == camp2["name"]
     assert "Purple Robes" in camp2_r.aliases
 
-    os.remove(os.path.join(FS_PATH, "campaign", camp2_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_sink_add_stix_bundle_dict(fs_sink, fs_source):
@@ -228,53 +267,74 @@ def test_filesystem_sink_add_stix_bundle_dict(fs_sink, fs_source):
                 "objective": "Bulgarian, Albanian and Romanian Intelligence Services",
                 "aliases": ["Huns"],
                 "id": "campaign--b8f86161-ccae-49de-973a-4ca320c62478",
-                "created": "2017-05-31T21:31:53.197755Z"
+                "created": "2017-05-31T21:31:53.197755Z",
+                "modified": "2017-05-31T21:31:53.197755Z"
             }
         ]
     }
 
     fs_sink.add(bund)
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", bund["objects"][0]["id"] + ".json"))
+    camp_obj = parse(bund["objects"][0])
+    filepath = os.path.join(FS_PATH, "campaign", camp_obj["id"],
+                            _timestamp2filename(camp_obj["modified"]) + ".json")
+
+    assert os.path.exists(filepath)
 
     camp3_r = fs_source.get(bund["objects"][0]["id"])
     assert camp3_r.id == bund["objects"][0]["id"]
     assert camp3_r.name == bund["objects"][0]["name"]
     assert "Huns" in camp3_r.aliases
 
-    os.remove(os.path.join(FS_PATH, "campaign", camp3_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_sink_add_json_stix_object(fs_sink, fs_source):
     # add json-encoded stix obj
     camp4 = '{"type": "campaign", "id":"campaign--6a6ca372-ba07-42cc-81ef-9840fc1f963d",'\
-            ' "created":"2017-05-31T21:31:53.197755Z", "name": "Ghengis Khan", "objective": "China and Russian infrastructure"}'
+            ' "created":"2017-05-31T21:31:53.197755Z",'\
+            ' "modified":"2017-05-31T21:31:53.197755Z",'\
+            ' "name": "Ghengis Khan", "objective": "China and Russian infrastructure"}'
 
     fs_sink.add(camp4)
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", "campaign--6a6ca372-ba07-42cc-81ef-9840fc1f963d" + ".json"))
+    camp4obj = parse(camp4)
+    filepath = os.path.join(FS_PATH, "campaign",
+                            "campaign--6a6ca372-ba07-42cc-81ef-9840fc1f963d",
+                            _timestamp2filename(camp4obj["modified"]) + ".json")
+
+    assert os.path.exists(filepath)
 
     camp4_r = fs_source.get("campaign--6a6ca372-ba07-42cc-81ef-9840fc1f963d")
     assert camp4_r.id == "campaign--6a6ca372-ba07-42cc-81ef-9840fc1f963d"
     assert camp4_r.name == "Ghengis Khan"
 
-    os.remove(os.path.join(FS_PATH, "campaign", camp4_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_sink_json_stix_bundle(fs_sink, fs_source):
     # add json-encoded stix bundle
     bund2 = '{"type": "bundle", "id": "bundle--3d267103-8475-4d8f-b321-35ec6eccfa37",' \
             ' "spec_version": "2.0", "objects": [{"type": "campaign", "id": "campaign--2c03b8bf-82ee-433e-9918-ca2cb6e9534b",' \
-            ' "created":"2017-05-31T21:31:53.197755Z", "name": "Spartacus", "objective": "Oppressive regimes of Africa and Middle East"}]}'
+            ' "created":"2017-05-31T21:31:53.197755Z",'\
+            ' "modified":"2017-05-31T21:31:53.197755Z",'\
+            ' "name": "Spartacus", "objective": "Oppressive regimes of Africa and Middle East"}]}'
     fs_sink.add(bund2)
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", "campaign--2c03b8bf-82ee-433e-9918-ca2cb6e9534b" + ".json"))
+    bund2obj = parse(bund2)
+    camp_obj = bund2obj["objects"][0]
+
+    filepath = os.path.join(FS_PATH, "campaign",
+                            "campaign--2c03b8bf-82ee-433e-9918-ca2cb6e9534b",
+                            _timestamp2filename(camp_obj["modified"]) + ".json")
+
+    assert os.path.exists(filepath)
 
     camp5_r = fs_source.get("campaign--2c03b8bf-82ee-433e-9918-ca2cb6e9534b")
     assert camp5_r.id == "campaign--2c03b8bf-82ee-433e-9918-ca2cb6e9534b"
     assert camp5_r.name == "Spartacus"
 
-    os.remove(os.path.join(FS_PATH, "campaign", camp5_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_sink_add_objects_list(fs_sink, fs_source):
@@ -289,13 +349,23 @@ def test_filesystem_sink_add_objects_list(fs_sink, fs_source):
         "objective": "Central and Eastern Europe military commands and departments",
         "aliases": ["The Frenchmen"],
         "id": "campaign--122818b6-1112-4fb0-b11b-b111107ca70a",
-        "created": "2017-05-31T21:31:53.197755Z"
+        "created": "2017-05-31T21:31:53.197755Z",
+        "modified": "2017-05-31T21:31:53.197755Z"
     }
 
     fs_sink.add([camp6, camp7])
 
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", camp6.id + ".json"))
-    assert os.path.exists(os.path.join(FS_PATH, "campaign", "campaign--122818b6-1112-4fb0-b11b-b111107ca70a" + ".json"))
+    camp7obj = parse(camp7)
+
+    camp6filepath = os.path.join(FS_PATH, "campaign", camp6.id,
+                                 _timestamp2filename(camp6["modified"]) +
+                                 ".json")
+    camp7filepath = os.path.join(
+        FS_PATH, "campaign", "campaign--122818b6-1112-4fb0-b11b-b111107ca70a",
+        _timestamp2filename(camp7obj["modified"]) + ".json")
+
+    assert os.path.exists(camp6filepath)
+    assert os.path.exists(camp7filepath)
 
     camp6_r = fs_source.get(camp6.id)
     assert camp6_r.id == camp6.id
@@ -306,8 +376,24 @@ def test_filesystem_sink_add_objects_list(fs_sink, fs_source):
     assert "The Frenchmen" in camp7_r.aliases
 
     # remove all added objects
-    os.remove(os.path.join(FS_PATH, "campaign", camp6_r.id + ".json"))
-    os.remove(os.path.join(FS_PATH, "campaign", camp7_r.id + ".json"))
+    os.remove(camp6filepath)
+    os.remove(camp7filepath)
+
+
+def test_filesystem_sink_marking(fs_sink):
+    marking = MarkingDefinition(
+        definition_type="tlp",
+        definition=TLPMarking(tlp="green")
+    )
+
+    fs_sink.add(marking)
+    marking_filepath = os.path.join(
+        FS_PATH, "marking-definition", marking["id"] + ".json"
+    )
+
+    assert os.path.exists(marking_filepath)
+
+    os.remove(marking_filepath)
 
 
 def test_filesystem_store_get_stored_as_bundle(fs_store):
@@ -323,8 +409,9 @@ def test_filesystem_store_get_stored_as_object(fs_store):
 
 
 def test_filesystem_store_all_versions(fs_store):
-    # all versions() - (note at this time, all_versions() is still not applicable to FileSystem, as only one version is ever stored)
-    rel = fs_store.all_versions("relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1")[0]
+    rels = fs_store.all_versions("relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1")
+    assert len(rels) == 1
+    rel = rels[0]
     assert rel.id == "relationship--70dc6b5c-c524-429e-a6ab-0dd40f0482c1"
     assert rel.type == "relationship"
 
@@ -347,7 +434,7 @@ def test_filesystem_store_query_single_filter(fs_store):
 
 def test_filesystem_store_empty_query(fs_store):
     results = fs_store.query()  # returns all
-    assert len(results) == 26
+    assert len(results) == 29
     assert "tool--242f3da3-4425-4d11-8f5c-b842886da966" in [obj.id for obj in results]
     assert "marking-definition--fa42a846-8d90-4e51-bc29-71d5b4802168" in [obj.id for obj in results]
 
@@ -361,7 +448,7 @@ def test_filesystem_store_query_multiple_filters(fs_store):
 
 def test_filesystem_store_query_dont_include_type_folder(fs_store):
     results = fs_store.query(Filter("type", "!=", "tool"))
-    assert len(results) == 24
+    assert len(results) == 27
 
 
 def test_filesystem_store_add(fs_store):
@@ -375,8 +462,11 @@ def test_filesystem_store_add(fs_store):
     assert camp1_r.id == camp1.id
     assert camp1_r.name == camp1.name
 
+    filepath = os.path.join(FS_PATH, "campaign", camp1_r.id,
+                            _timestamp2filename(camp1_r.modified) + ".json")
+
     # remove
-    os.remove(os.path.join(FS_PATH, "campaign", camp1_r.id + ".json"))
+    os.remove(filepath)
 
 
 def test_filesystem_store_add_as_bundle():
@@ -387,7 +477,10 @@ def test_filesystem_store_add_as_bundle():
                      aliases=["Ragnar"])
     fs_store.add(camp1)
 
-    with open(os.path.join(FS_PATH, "campaign", camp1.id + ".json")) as bundle_file:
+    filepath = os.path.join(FS_PATH, "campaign", camp1.id,
+                            _timestamp2filename(camp1.modified) + ".json")
+
+    with open(filepath) as bundle_file:
         assert '"type": "bundle"' in bundle_file.read()
 
     camp1_r = fs_store.get(camp1.id)
@@ -412,6 +505,26 @@ def test_filesystem_store_add_invalid_object(fs_store):
     assert 'JSON formatted STIX bundle' in str(excinfo.value)
 
 
+def test_filesystem_store_add_marking(fs_store):
+    marking = MarkingDefinition(
+        definition_type="tlp",
+        definition=TLPMarking(tlp="green")
+    )
+
+    fs_store.add(marking)
+    marking_filepath = os.path.join(
+        FS_PATH, "marking-definition", marking["id"] + ".json"
+    )
+
+    assert os.path.exists(marking_filepath)
+
+    marking_r = fs_store.get(marking["id"])
+    assert marking_r["id"] == marking["id"]
+    assert marking_r["definition"]["tlp"] == "green"
+
+    os.remove(marking_filepath)
+
+
 def test_filesystem_object_with_custom_property(fs_store):
     camp = Campaign(name="Scipio Africanus",
                     objective="Defeat the Carthaginians",
@@ -527,3 +640,357 @@ def test_related_to_by_target(rel_fs_store):
     assert len(resp) == 2
     assert any(x['id'] == CAMPAIGN_ID for x in resp)
     assert any(x['id'] == INDICATOR_ID for x in resp)
+
+
+def test_auth_set_white1():
+    auth_set = AuthSet({"A"}, set())
+
+    assert auth_set.auth_type == AuthSet.WHITE
+    assert auth_set.values == {"A"}
+
+
+def test_auth_set_white2():
+    auth_set = AuthSet(set(), set())
+
+    assert auth_set.auth_type == AuthSet.WHITE
+    assert len(auth_set.values) == 0
+
+
+def test_auth_set_white3():
+    auth_set = AuthSet({"A", "B"}, {"B", "C"})
+
+    assert auth_set.auth_type == AuthSet.WHITE
+    assert auth_set.values == {"A"}
+
+
+def test_auth_set_black1():
+    auth_set = AuthSet(None, {"B", "C"})
+
+    assert auth_set.auth_type == AuthSet.BLACK
+    assert auth_set.values == {"B", "C"}
+
+
+def test_optimize_types1():
+    filters = [
+        Filter("type", "=", "foo")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"foo"}
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types2():
+    filters = [
+        Filter("type", "=", "foo"),
+        Filter("type", "=", "bar")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert len(auth_types.values) == 0
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types3():
+    filters = [
+        Filter("type", "in", ["A", "B", "C"]),
+        Filter("type", "in", ["B", "C", "D"])
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"B", "C"}
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types4():
+    filters = [
+        Filter("type", "in", ["A", "B", "C"]),
+        Filter("type", "in", ["D", "E", "F"])
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert len(auth_types.values) == 0
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types5():
+    filters = [
+        Filter("type", "in", ["foo", "bar"]),
+        Filter("type", "!=", "bar")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"foo"}
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types6():
+    filters = [
+        Filter("type", "!=", "foo"),
+        Filter("type", "!=", "bar")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.BLACK
+    assert auth_types.values == {"foo", "bar"}
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types7():
+    filters = [
+        Filter("type", "=", "foo"),
+        Filter("type", "!=", "foo")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert len(auth_types.values) == 0
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types8():
+    filters = []
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.BLACK
+    assert len(auth_types.values) == 0
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types_ids1():
+    filters = [
+        Filter("type", "in", ["foo", "bar"]),
+        Filter("id", "=", "foo--00000000-0000-0000-0000-000000000000")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"foo"}
+    assert auth_ids.auth_type == AuthSet.WHITE
+    assert auth_ids.values == {"foo--00000000-0000-0000-0000-000000000000"}
+
+
+def test_optimize_types_ids2():
+    filters = [
+        Filter("type", "=", "foo"),
+        Filter("id", "=", "bar--00000000-0000-0000-0000-000000000000")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert len(auth_types.values) == 0
+    assert auth_ids.auth_type == AuthSet.WHITE
+    assert len(auth_ids.values) == 0
+
+
+def test_optimize_types_ids3():
+    filters = [
+        Filter("type", "in", ["foo", "bar"]),
+        Filter("id", "!=", "bar--00000000-0000-0000-0000-000000000000")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"foo", "bar"}
+    assert auth_ids.auth_type == AuthSet.BLACK
+    assert auth_ids.values == {"bar--00000000-0000-0000-0000-000000000000"}
+
+
+def test_optimize_types_ids4():
+    filters = [
+        Filter("type", "in", ["A", "B", "C"]),
+        Filter("id", "in", [
+            "B--00000000-0000-0000-0000-000000000000",
+            "C--00000000-0000-0000-0000-000000000000",
+            "D--00000000-0000-0000-0000-000000000000",
+        ])
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"B", "C"}
+    assert auth_ids.auth_type == AuthSet.WHITE
+    assert auth_ids.values == {
+        "B--00000000-0000-0000-0000-000000000000",
+        "C--00000000-0000-0000-0000-000000000000"
+    }
+
+
+def test_optimize_types_ids5():
+    filters = [
+        Filter("type", "in", ["A", "B", "C"]),
+        Filter("type", "!=", "C"),
+        Filter("id", "in", [
+            "B--00000000-0000-0000-0000-000000000000",
+            "C--00000000-0000-0000-0000-000000000000",
+            "D--00000000-0000-0000-0000-000000000000"
+        ]),
+        Filter("id", "!=", "D--00000000-0000-0000-0000-000000000000")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"B"}
+    assert auth_ids.auth_type == AuthSet.WHITE
+    assert auth_ids.values == {"B--00000000-0000-0000-0000-000000000000"}
+
+
+def test_optimize_types_ids6():
+    filters = [
+        Filter("id", "=", "A--00000000-0000-0000-0000-000000000000")
+    ]
+
+    auth_types, auth_ids = _find_search_optimizations(filters)
+
+    assert auth_types.auth_type == AuthSet.WHITE
+    assert auth_types.values == {"A"}
+    assert auth_ids.auth_type == AuthSet.WHITE
+    assert auth_ids.values == {"A--00000000-0000-0000-0000-000000000000"}
+
+
+def test_search_auth_set_white1():
+    auth_set = AuthSet(
+        {"attack-pattern", "doesntexist"},
+        set()
+    )
+
+    results = _get_matching_dir_entries(FS_PATH, auth_set, stat.S_ISDIR)
+    assert results == ["attack-pattern"]
+
+    results = _get_matching_dir_entries(FS_PATH, auth_set, stat.S_ISREG)
+    assert len(results) == 0
+
+
+def test_search_auth_set_white2():
+    auth_set = AuthSet(
+        {
+            "malware--6b616fc1-1505-48e3-8b2c-0d19337bff38",
+            "malware--92ec0cbd-2c30-44a2-b270-73f4ec949841"
+
+        },
+        {
+            "malware--92ec0cbd-2c30-44a2-b270-73f4ec949841",
+            "malware--96b08451-b27a-4ff6-893f-790e26393a8e",
+            "doesntexist"
+        }
+    )
+
+    results = _get_matching_dir_entries(
+        os.path.join(FS_PATH, "malware"),
+        auth_set, stat.S_ISDIR
+    )
+
+    assert results == ["malware--6b616fc1-1505-48e3-8b2c-0d19337bff38"]
+
+
+def test_search_auth_set_white3():
+    auth_set = AuthSet({"20170531213258226477", "doesntexist"}, set())
+
+    results = _get_matching_dir_entries(
+        os.path.join(FS_PATH, "malware",
+                     "malware--6b616fc1-1505-48e3-8b2c-0d19337bff38"),
+        auth_set, stat.S_ISREG, ".json"
+    )
+
+    assert results == ["20170531213258226477.json"]
+
+
+def test_search_auth_set_black1():
+    auth_set = AuthSet(
+        None,
+        {"tool--242f3da3-4425-4d11-8f5c-b842886da966", "doesntexist"}
+    )
+
+    results = _get_matching_dir_entries(
+        os.path.join(FS_PATH, "tool"),
+        auth_set, stat.S_ISDIR
+    )
+
+    assert set(results) == {
+        "tool--03342581-f790-4f03-ba41-e82e67392e23"
+    }
+
+
+def test_search_auth_set_white_empty():
+    auth_set = AuthSet(
+        set(),
+        set()
+    )
+
+    results = _get_matching_dir_entries(FS_PATH, auth_set, stat.S_ISDIR)
+
+    assert len(results) == 0
+
+
+def test_search_auth_set_black_empty(rel_fs_store):
+    # Ensure rel_fs_store fixture has run so that the type directories are
+    # predictable (it adds "campaign").
+    auth_set = AuthSet(
+        None,
+        set()
+    )
+
+    results = _get_matching_dir_entries(FS_PATH, auth_set, stat.S_ISDIR)
+
+    # Should get all dirs
+    assert set(results) == {
+        "attack-pattern",
+        "campaign",
+        "course-of-action",
+        "identity",
+        "indicator",
+        "intrusion-set",
+        "malware",
+        "marking-definition",
+        "relationship",
+        "tool"
+    }
+
+
+def test_timestamp2filename_naive():
+    dt = datetime.datetime(
+        2010, 6, 15,
+        8, 30, 10, 1234
+    )
+
+    filename = _timestamp2filename(dt)
+    assert filename == "20100615083010001234"
+
+
+def test_timestamp2filename_tz():
+    # one hour west of UTC (i.e. an hour earlier)
+    tz = pytz.FixedOffset(-60)
+    dt = datetime.datetime(
+        2010, 6, 15,
+        7, 30, 10, 1234,
+        tz
+    )
+
+    filename = _timestamp2filename(dt)
+    assert filename == "20100615083010001234"