[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: "Fuzzy" SPKI (was Re: Certificate Expiration)

At 01:43 20/05/98 -0400, Carl Ellison wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>At 11:29 PM 5/19/98 +0100, Frank O'Dwyer wrote:
>>I suppose it's more of a research area than something
>>for SPKI, but I think that fuzzy sets would be a natural 
>>mechanism to achieve this. In general a 'fuzzification'
>>of authorisations is interesting to contemplate.
>
>[...]
>
>>Maybe defining a fuzzy 5-tuple reduction, plus corresponding
>>fuzzy validity matching, is a possible route to overlay this
>>on the existing SPKI. The validity part, as I say, would be
>>easy to do with fuzzy sets. I guess it's another day's work 
>>though.
>
>Frank,
>
>	the idea sounds fascinating to me.  I have no experience in fuzzy logic.  
>Could you elaborate on this -- maybe show what an evaluation algorithm would 
>be like?

My own experience in fuzzy logic is limited to some reading
on the topic, but I think I know roughly how fuzzy validity 
would work, at least. It would go something like this:

* SPKI's current validity period is in effect a set of times. 
Any instant is wholly within the period, or wholly outside.

* "Fuzzify" this by using a fuzzy set of times instead. A given
instant is now to some extent (maybe wholly) within the fuzzy 
validity period, and to some extent (maybe wholly) outside.

* You might express such a fuzzy validity set as follows:

    (
      (0.1 notAfter1 notBefore1)
      (0.5 notAfter2 notBefore2)
      (1.0 notAfter3 notBefore3)
      (0.8 notAfter4 notBefore4)
      (0.2 notAfter5 notBefore5)
    )

The above says that during the period (notAfter1,notBefore1)
the object is 10% valid, 90% expired, and so forth (presumably
it should have correspondly diminished relevance in an access
decision done at a corresponding instant - the big picture
would have to make that happen).  At the extremities of the
set, instants are wholly outside (there are implicit zero
entries at the extremities). Note that vanilla SPKI is 
simply a special case of this, namely:

     (1.0 notAfter notBefore)
and  (1.0 <special tests>)

* Fuzzy sets can intersect and union, and so forth, so reduction
is essentially unchanged as regards validity.

* In the end you wind up with a bunch of 'self' issued tuples,
except that these are to some extent (maybe wholly, or
not at all) expired. I would expect that the access decision 
then becomes either this:

    if the effective acl is "very fresh", allow access

or a set of fuzzy rules:

    if the effective acl allows access and 
       is "very fresh", allow access

    if the effective acl allows access 
       but is "a little stale", allow access 
      (with warnings, or diminished functionality?).

    if the effective acl allows access 
       but is "very old", raise an alarm.

* Anything in SPKI that is either:

    - a set (e.g. groups of principals, the set of 
        certificates valid now, the set of revoked
        certificates, the set of effective acls)
    - or boolean (e.g. authorisation)

...could be potentially "fuzzified".  Allow objects
to be partly contained, and partly outside of, sets.
Allow boolean propositions to be partly true, and
partly false.  (Boolean operations can be recast
in terms of sets, and vice versa. The same is true
of fuzzy truth and fuzzy containment.) If SPKI's 
algorithms are based on natural set operations and 
logic operations, then "fuzzy SPKI" should naturally 
emerge from this process.

* Of course, any such "fuzzification" needs to be referred
back to the real-world meaning to see if it is useful.
On first sight, I think that "fuzzy validity" seems
intuitive and useful, albeit slightly weird.  I'm not 
so sure of what it means to be "90% empowered" to do 
something, however. "90% trusted" has a better ring 
(but there's that word again!). It reminds me of PGP 
and K-of-N, where a key needs to be backed up with 
multiple certs before it is 'empowered' - in PGP,
as you know, this is tied to a sort of 'trust estimate'.
To my mind, capturing these shades of grey is extremely
appealing, but YMMV. (I guess that an access system
where things are "sort of allowed kind of sometimes" 
is tough to sell - but it is perhaps more honest :-)

* A clean interop with vanilla SPKI could be done
by processing in "fuzzy" mode until the last moment,
then rounding off to the nearest "focussed" sexpr.
That is, at the last moment, round off to wholly
expired, or wholly valid; wholly empowered, or wholly
not. This result could also be used by verifiers 
with limited processing power - much as is currently
envisaged for SPKI reduction.

I'm away from my books on fuzzy logic at present,
so I'm jumping without a safety net here. However, 
if there is interest I can have a go at elaborating 
further over the next several weeks.

(BTW, as regards selecting different acls according to
context, that could be done currently without recourse 
to fuzzy stuff.  A verifier could select different
hard sets of acls according to its state.  For
example:

   * use acl set A in normal operation
   * use acl set B when under heavy load
   * use acl set C at weekends
   * use acl set D when the system is nervous 
)

Cheers,
Frank.

> - Carl
>
>-----BEGIN PGP SIGNATURE-----
>Version: PGP for Personal Privacy 5.5.3
>
>iQCVAwUBNWJtmhN3Wx8QwqUtAQE+mgP9HABpXCC1b/6PCxxAkc+GvZpPm6fzjE7g
>MAsq77lWs+F/feALcpHo5p2av5+Vs9QFihZD7hC2NyKk/ZUFymH+u2745YZdNZJh
>2QmHdRn2MnDdoiaYT+0/4VqgwLkNnYlsSCS+Y/PQC9vWvvr65oQtXag4jLaP9iKL
>8C0xr0qDCbk=
>=TUD5
>-----END PGP SIGNATURE-----
>
>
>+------------------------------------------------------------------+
>|Carl M. Ellison  cme@cybercash.com   http://www.clark.net/pub/cme |
>|CyberCash, Inc.                      http://www.cybercash.com/    |
>|207 Grindall Street  PGP 08FF BA05 599B 49D2  23C6 6FFD 36BA D342 |
>|Baltimore MD 21230-4103  T:(410) 727-4288  F:(410)727-4293        |
>+------------------------------------------------------------------+
>
>
References: