ACL Algorithm
From RFID Guardian
Contents |
This page is in severe need of an overhaul: it is far too compact
We need a sophisticated ACL algorithm to efficiently deal with queries that apply to a subset of tags. Most queries either apply to 'the' selected tag, or to all tags present (and then the tags will often generate a collision for a nontrivial response). The complicated case is INVENTORY (15693) or ANTICOLLISION (14443-A), where a variable subset of the set of all tags is addressed in each iteration of the anticollision algorithms.
Problem example
The problem solved here surfaced as follows: my first naive and erroneous(!) rule engine gave the SCHIPHOL reader access to some of my protected tags, because its rule said 'ALLOW $SCHIPHOL to access $PASSPORT' and the query matched $PASSPORT. It should have denied access, because the query also matched other tags in @MYTAGS.
We start looking at a situation of a single DENY rule which is refined by ALLOW rules later in the ACL. Notice: if there are multiple DENY rules, the story just repeats for each DENY rule and its refinements.
Terminology: set stuff
We can view the anticollision algorithm as operating on a (dynamic, flexible) subset of the set of all tags. We use terminology from the set world.
operators:
a in B : tag a is element of set B
A in B : set A is subset of set B
A x B : intersection of set A and B
A + B : union of set A and B
A - B : set difference of A and B (i.e. { x | x in A && x !in B })
0 : empty set
|A| : size of set A (i.e. number of elements)
R_d : rule: DENY access to tag set D R_a,i: rule: ALLOW access to tag set A_i (refinements to R_d).
Q : query: has mask M = (mask_len, mask)
A rule belongs to a certain role (== list of readers). Note: the readers and roles are reshuffled so we get a disjoint set of roles. The original rules must follow this reshuffling.
Problem and general solution
if rule R_a,i applies (i.e. the current reader can assume a role that owns R_a,i), then:
ALLOW if M x A_i != 0 unless there is some tag in D but not in A_i which matches, yielding: M x (D - A_i) != 0
Example
PASSPORT = { 0x010101010101 };
@MYTAGS = { 0x000000001, $PASSPORT };
R_d = DENY if in D = @MYTAGS
A_1 = ALLOW $PASSPORT if role = SCHIPHOL
Now Q has M = { length = 1, mask = 0x1 }
Both PASSPORT and the anonymous tag match this query, because:
M x A_i = { $PASSPORT }
D - A_i = { 0x000000001 }
M x ( D - A_i ) = { 0x000000001 }
Therefore, we deny because M x (D - A_i) != 0 (i.e. 0x000000001 also matches and it must be protected from the SCHIPHOL reader).
This is not hard to calculate, but if it must be done online the computation cost can rise high (calculate D - A_i). However, we can precompute (D - A_i) for each rule R_a,i, and then the calculation is very efficient because in our implementation calculating |M x S| is fast for any set S.
Some optimizations for special cases
Case I. |A_i| << |D|
If R_a,i, the ALLOW refinements, cover only small sets, these precomputed D - A_i are approximately of the size of D, which is big. I thought of a performance optimization for this case.
Consider X = union(A_i) for all i.
X is the set of all tags for which an exception is defined. Let K = D - X, the set of all tags in D for which no exception is defined. Mark: X is small, K is large.
Now, our problem can be solved in three fast steps:
if M x A_i != 0, then ALLOW unless (1) if M x K != 0, then DENY. There are tags in the match for which no refinement has been defined. (2) if M x (X - A_i) != 0, then DENY. There are tags for which some refinement has been defined, but not the applicable refinement R_a,i.
:::: Define: P_i = X - A_i
We can precompute K (which is large, but there is only one for each deny rule R_d). We can precompute P_i, which are small. There are as many of these as rules R_a,i. Finished in little time and reasonable space.
Case II. |A_i| =~ |D|
Now let E_i = D - A_i. Mark that E_i is small.
Now our algorithm is:
if M x A_i != 0 then ALLOW unless M x E_i != 0
Here we need to precompute E_i: one small set for each rule. Finished in little time and reasonable space.
Example:
R_a,2 : ALLOW my boyfriend to access @MYTAGS except those secret passes that I tell no-one about
BTW, how would we specify this BTW? Like:
rule : ALLOW role = $BOYFRIEND if tags != @SECRET_PASSES
or is this impractical?
Well, that's it I think. If I am too terse, or if I'm wrong, I am happy to explain, of course.
