Restricting client queries

Graph QL and om.next like systems with client-side queries need to make sure that the client's cannot receive data they don't have access to. We want to make it easy for developers to express which data a user has access to. We've solved this by having arbitrary levels of authentication at each "root-query" aka read, and every attribute walked by the client-side provided query is checked against a filter, that can decide whether the user should have access to the data.

Example

Let's go through how we'd specify a read for reading a user's shopping cart. We define this read as:

(defread query/cart
  [{:keys [db db-history query auth]} _ _]
  {:auth ::auth/any-user}
;; this  ^^^^^^^^^^^^^^^ value specifies the level of auth the request needs
;; to access this read.
  {:value (query/one db db-history query {:where   [[?u :user/cart ?e]]
                                          :symbols {'?u (:user-id auth)}})})

The value of :auth is used together with our auth namespace to create a query to see if the user is authorized enough.

If the user has auhtorization to access the data, we get it from the :value key. This endpoint executes a database query, retrieving a user's cart entity. The databases db and db-history is filtered with our database filters. These filters verify that every datom retrieved in the query should be accessible by the user querying.

About our database filters

We're being very defensive with our database filters. The way they're implemented is that, for every datom, traverse datomic's index in a specific way, making sure the user should have access to the data. The specific way is a path defined by each attribute.

A more relaxed way of filtering the data would be to remove unauthorized attributes from the pull pattern and making sure that the query only access the right data. With our approach, we're guarding ourselves from implementation bugs at the cost of performance (which I'll get to). For example:

A user X should only ever access its own shopping cart. 
If I'm authorized as user X and I execute query:
  {:find [[?cart ...]]
   :where [[_ :user/cart ?cart]]}
It will only return user A's cart, as the other carts are filtered out.

Performance

As mentioned, we're traversing a path to check if a user has access to the data. This path is a vector of ref attributes, going from the datom we're authorizing to a datom with authorization (e.g. a user or a store-owner). Example:

• Problem:
  • Given a user.
  • Given an order datom [id :order/amount amount]
  • Permit access to this datom if the order belongs to a user.
• Strategy:
  • Order entities have a reference to the user they belong to via :order/user.
  • Given that we've got the user-id and the order-id (from the order datom we're given), traverse the database from the user-id to the order-id via :order/user.
  • Example code:

(fn [user-id [order-id attribute value]]
  (can-traverse? db {:from order-id
                     :to   user-id
                     :via  [:order/user]))
;; => true

The time complexity of the filter function is O(k * n), where k is the length of the path (number of calls to datomic.api/datoms) and n is the amount of datoms returned from the call, and we'll have to try all the datoms in worst case. In practice though, most of our attributes are public attributes and the paths are usually pretty short.

Micro-benchmark

I ran some tests queries that require checking paths and here's what they resulted in.

    ;; Results on my MacBook Pro 13" early 2015
    ;;
    ;; All times are specified in micro-seconds
    ;; :mean represents execution time mean.
    ;; :lower represents lower quantile ( 2.5%)
    ;; :upper represents upper quantile (97.5%)

    {
     ;; These times are baselines filters. Database filters
     ;; equal to (constantly false) and (constantly true).
     ;; Our test includes calling datomic.api/pull which requires
     ;; creating nested data structures. 

     ;; The :no-access filter skips both traversing the database 
     ;; when filtering datoms as well as pulling the data. It's 
     ;; the lowest possible value. 
     :no-access     {:mean 338 :lower 334 :upper 347}
     ;; The :all-access can access everything and represents the
     ;; worst case.
     :all-access    {:mean 412 :lower 404 :upper 449}

     ;; All of these results use the our database traversing filters.
     ;; Even for the slowest result, which happen to have access to
     ;; all the data in the tests, it's not that much slower than the
     ;; :all-access case. It's 34% slower than without the filter, but
     ;; it also guarantees the data is accessed properly.
     :no-auth       {:mean 425 :lower 417 :upper 452}
     :user2         {:mean 436 :lower 426 :upper 469}
     :store-owner   {:mean 509 :lower 501 :upper 534}
     :user          {:mean 518 :lower 508 :upper 571}
     :user+store    {:mean 525 :lower 508 :upper 660}
     :user2+store   {:mean 555 :lower 544 :upper 629}}

These results can be recreated with the eponai.server.datomic.filter-test namespace by running the code at the bottom in the commented section.

Files of interest

• src/eponai/server/parser/read.clj
• src/eponai/common/auth.cljc
• src/eponai/server/datomic/filter.clj
• eponai.server.datomic.filter-test