Dan Zhang, July 2017

Introduction

The Auto-Wipeout project is part of a Firebase project to helpFirebase developer protect privacy of their end-users. The wipeoutproject is a cloud function library which can automatically deleteuser data on end-user account deletion. In this way, our customers(Firebase developers) can focus on making their apps special with alower cost of writing safer apps.

In order to make using the wipeout library closer to a “one-click”experience, wipeout rules could be automatically generated byinformation inferred from the authorization rules. This doc explainstechnical details about the inference process from Real Time Database(RTDB) rules. For more general design and concepts, go to the maindesign doc.

RTDB rules

Quotes from page Understand Firebase Realtime Database Rules:

Firebase Realtime Database Rules determine who has read and writeaccess to your database, how your data is structured, and whatindexes exist. These rules live on the Firebase servers and areenforced automatically at all times. Every read and write requestwill only be completed if your rules allow it.

The 2^120 Ways to Ensure Unique Identifiers February 11, 2015. We get many questions from our developers about how our uniquely generated IDs work under the hood so I thought I’d explain them in more detail. Into an ID that can be used as a Firebase key, we basically base64 encode it into ASCII characters, but we use a modified base64.

More detailed references can be found here: Firebase Database SecurityRules API.

Traversal of the rule tree

Nov 07, 2019  Common Database Rules for Firebase. GitHub Gist: instantly share code, notes, and snippets. Common Database Rules for Firebase. GitHub Gist: instantly share code, notes, and snippets. Small question, new to database. All rule attributes must be under one rule or can there be multiple 'rules': with different parameters? Jan 28, 2020 Firebase allows you to do ad-hoc queries on your data using an arbitrary child key. If you know in advance what your indexes will be, you can define them via the.indexOn rule in your Firebase Realtime Database Rules to improve query performance. Defining Data Indexes. Firebase provides powerful tools for ordering and querying your data. The Firebase Realtime Database also supports multi-path updates. This means that update can now update values at multiple locations in your database at the same time, a powerful feature which allows helps you denormalize your data. Using multi-path updates, you can add nicknames to both Grace and Alan at the same time.

The authorization rule of the RTDB is parsed to be a json object whichnaturally has a tree structure. We traverse the tree in aBreadth-First search for “.write” rules. Whenever we find a writerule, we first check the status implied by the write rule (discussedin 'Single write rule analysis' below), and combine it with the statusof its ancestor (discussed 'Hierarchical write rules' below) to decidethe status of the current location. If it turns out that the currentplace holds personal data, the patterns for the location (in theformat described in the main design doc) will be recorded inwipeout configuration.

Single write rule analysis

First, we discuss how to deal with a single

Definitions:

Variable

The $location variable in firebase security rules. A variablethat can be used to reference the key of a $location that was usedearlier in a rule structure. For example, replacing the variable$uid in /users/$uid/ with the user name ‘Barney’ will produce path/users/Barney/.

Path Pattern

A sequence of constant and variables defining the path from root tothe current location of the write rule. For example, /key/$k1/$k2 isa path pattern. It could match multiple places in the database withdifferent values for the variables.

Auth placeholder

A special variable which could represent Firebase authentication uidof any single user. We use #WIPEOUT_UID as the auth placeholder toavoid potential conflicts with variables of the same name since # isnot a valid path component in Firebase RTDB rules.

Access Pattern

Path patterns with variables replaced by auth placeholders accordingto the write rule. For a particular user with #WIPEOUT_UID, anaccess pattern describes one or a set of paths to places they havewrite access to. For example, /users/#WIPEOUT_UID is an accesspattern describing a single path, and follow/$followee/#WIPEOUT_UIDdescribes a set of path.

Free variable

Variables in access patterns which are not auth placeholders. Theycould take any value which matches the access pattern to a valid pathin the database.

Principle and assumption

Principle

Only data at paths owned by the user could be deleted at wipeout.

Assumption

If a user is the only one with access to a particular path then thatimplies the user owns the path. (With the exception of creating anentry: when data.value null, anyone can write to a place, butonly the specific user can write to it afterwards. This case the userowns the data, but the write rule will be considered accessible bymultiple users. This is not currently dealt with).

Given this assumption, if there’s only one valid access pattern fora path pattern (means any instance of the pattern can only bewritten by one user), then user with #WIPEOUT_UID owns theinstance(s) of the access pattern.

Now the problem becomes how do we tell the numbers of access patterns?Recall access patterns are describe possible ways that variables in apath could be replaced by auth placeholder. And the auth placeholderswill be later replaced by Firebase auth.uid. So we go into the writerule and look for variables that must match auth.uid. E.g. with ruleauth.uid $uid at path pattern /users/$uid, $uid is the variable weare looking for.

Since write rules could be a logical combination of many sub-rules, wenormalize the equation to auth.uid EXP. The underlying meaning isthat: the write rule will not evaluates to false if and only if EXPevaluates to true (only considering auth). Here EXP can be anexpression consists of conjunctions and disjunctions of variables or afixed true or false value.

In order to make future reasoning easier, we convert EXP toDisjunctive Normal Form (DNF). In other word, EXP must bedisjunction (OR) of one or more conjunctions (AND) of one or moreliterals (variable in our case).

Now it is clear that with EXP in DNF, each conjunctive clause maps toone access pattern. In conclusion, in order to find out pathpatterns with single access pattern, we only need to find out the EXPwith single conjunctive clause in DNF.

An example

Here is an example based on the previous definition and reasoning.

Assume we have path pattern /key/$k1/$k2, the table below shows thecorresponding outcomes with different write rules.

(In this table, use #WUID instead of #WIPEOUT_UID to save space.)

As shown in the table, a write rule could lead to three access results for a path pattern

1. [No access] User with uid has no write access to the any instanceof the path pattern. EXP has a fixed False value in this case.(Note we are looking for patterns for general users , so auth.uid SOME_SPECIAL_UID also implies no access )
2. [Single access] Any instance of the path pattern could be writtenwith one specific auth uid. EXP should have only one conjunctiveclause in DNF in this case.
3. Multiple access] Instances of the path pattern could be writtenwith more than one auth uids. EXP has more than one conjunctiveclauses in DNF or has fixed True value in this case.

Implementation details

Representation

The operations of the DNF expressions are implemented inexpression.js. An expression object has two fields, booleanValue andconjunctionLists. booleanValue can be true or false or undefined.conjunctionLists represents EXP, and is a list of lists, each innerlist represents the list of literals in a conjunction clause, and theouter list represents the disjunction of all the conjunctive clauses.

When booleanValue is True or False, the value of EXP is fixed and theconjunctionList doesn’t matter, and it will be set to an empty list.When booleanValue is undefined, we go ahead and look at theconjunctionLists.

Building EXP

We build EXP for write rules in a bottom-up manners.

• Any literal with the value true or false will produce EXP = Trueor EXP = False.
• Equations (Binary expression) with auth.uid on one side willproduce a EXP = $other_side_variable.

Operations

We always keep EXP in DNF, we could do “AND” and “OR” operations of EXPs.

• AND of two DNF expressions: cross product of the two expressions,where product of two clauses means the union of the theirliterals.
• OR of two DNF expressions: concatenate clauses from twoexpressions

Simplification

The result of operations may need to be simplified according toclassical logic:

Firebase Realtime Database Example

• When there are true or false in the expression:
  • A & 0 = 0, A 1 = 1
  • A & 1 = A, A 0 = A
• For literals and conjunction clauses, sort and remove duplicatesbecause:
  • Idempotence: A & A = A, A A = A
  • Commutativity: A & B = B & A, A B = B A
• Remove redundant clauses according using absorption
  • Absorption: A (A & B) = A

Hierarchical write rules

As stated in the previous section, there are three possible accessstatus associated with a write rule, they are: NO_ACCESS,SINGLE_ACCESS, MULT_ACCESS. However, since write rules cascade,getting the access status from a single rule is not enough.

Note: Shallower security rules override rules at deeper paths. Childrules can only grant additional privileges to what parent nodes havealready declared. They cannot revoke a read or write privilege.

Child rule can grant additional access, thus the access status of thechild node not only depends on the child rule, but also the status ofits parent.

For example, parent /keys/$k1 with rule auth.uid $k1 hasSINGLE_ACCESS, and child /keys/$k1/$k2 with rule auth.uid $k2.The child rule itself is single access, but for the node, it isgranting additional access besides its parent. So for the child node,the resulting access patterns are [/keys/#WUID, /keys/$k1/#WUID] andthe access status is MULT_ACCESS then.

The table below shows ACCESS of child node according to parent nodeaccess and child rule access

Note with Parent and child node both having SINGLE_ACCESS, there aretwo possible outcomes. We need to look into the child rule and see ifit grants additional access to its parent. This is done by looking atthe conjunction list of parent and child rule. Recall withSINGLE_ACCESS, there should be only one conjunction, each literal inthe conjunction adds a restriction to auth.uid. So we look at everyliteral in the parents conjunction and see if any restriction has beenremoved in the child rule, if so the child node has MULT_ACCESS, elsethe child node will have same SINGLE_ACCESS as its parent.

Following the previous example, the parent node has conjunction [$k1]and the child rule has conjunction [$k2]. The restriction thatauth.uid $k1 has been removed in the child node this means thechild rule granted additional access and the child node hasMULT_ACCESS. If the child rule has conjunction [$k1,$k2], the childrule is adding additional restriction to the parent node while keepingthe old restriction and no additional access granted. Since childnodes can’t revoke privilege, the child node will inherit access fromits parent.

Implementation details

A new class Access is introduced to describe the access status ofnodes and rule. It has two member:

• accessStatus: NO/SINGLE/MULT_ACCESS
• variableList: Empty list if accessStatus is NO/MULT; list ofliterals in conjunction if access is SINGLE

An access object can be created from expression object of write rules.Static method nodeAccess() calculates child node access from childrule access and parent node access.

Data references

Besides variables in the path, Firebase RTDB security rule alsosupports references to data through methods like child(), andparent(). Our auto extraction also supports a subset of references aslisted below

• Predefined variables:
  • data: corresponds to the current data in RTDB at the locationof the currently rule. [supported]
  • root: corresponds to the data at the root of the RTDB.[supported]
  • newData :corresponds to the data that will result if the writeis allowed. [ignored] because the restriction on new data isnot related to the privilege to write (access) at a place().
• Referencing methods
  • child(): Gets a reference for the location at the specifiedrelative path. One single argument required to specify thepath.[supported]
  • parent(): Gets a reference for the location parent path. Noargument. [supported]
• Evaluating methods
  • val(): Gets the value from the reference. [supported]
  • exists(): Return true if the reference contains any data.[supported]

Data references are evaluated to a string and treated as a normalliteral/identifier when we parse the write rule at a particularlocation. They may imply additional conditions to the access patternHere are some examples:

With path = /user/data/$uid

• newData.val() => undefined
• data.val() => val(rules,user,data,$uid)
• data.exists() => exists(rules,user,data,$uid)
• data.child(‘name’).val() => val(rules,user,data,$uid,name)
• data.child(‘name’).parent().child(‘age’).val() => val(rules,user,data,$uid,age)
• data.parent().child(auth.uid).val() => val(rules,user,data,#WIPEOUT_UID)
• root.child(‘data’).child(data.child(‘friend’)).val() => val(rules,user,data,val(rules,user,data,$uid,friend))

Conditions

Besides restrictions on authentication id, there are also additionalconditions on variables in the path or data references. We includethese conditions in a ‘condition’ field in wipeout rules.

Condition could be

• A single data reference with exists() value, likedata.exists()
• Or a binary expression of Literal/Identifier/data referencesconnected by operators like ‘’ , ‘<’ , ‘>’, ’!=’... For example,data.val() != null.

Conditions expression additional restrictions on write accesses, andthey have a ‘AND’ relationship restrictions on authenticationinformation.

Firebase Realtime Database For Auto Generated Key Rule Pdf

In terms of implementation, conditions are associated with expressionsand access objects. An Expression object with booleanValue True orUndefined can have valid condition. Only Access objects with withSINGLE_ACCESS have conditions.

Firebase Realtime Database For Auto Generated Key Rule 2017

When we do AND and OR operations of Expressions, their conditions willbe joined by the corresponding operator. When we are calculating childnode Access based on parent node Access and child rule Access, there’sonly one case where conditions will be involved: parent and child ruleboth have SINGLE_ACCESS and child node have SINGLE_ACCESS. In thiscase the resulting condition of child node is the OR of the twoconditions.