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

Re: A (Low-Level) Opaque Object Proposal for R5RS



> Alan Bawden writes:
> 
>      Date: Fri, 26 Apr 96 12:29:53 -0400
>      From: Michael R. Blair <ziggy@martigny.ai.mit.edu>
>
>      I propose the following four procedures be standardized for Scheme and
>      their names be added to the list of reserved identifiers:
>      -----------------------------------------------------------------------
>      [1].     (MAKE-OPAQUE-TYPE                              . <passkey>)
>      [2].     (     OPAQUE-UP   <opaque-type>       <object> . <passkey>)
>      [3].     (     OPAQUE-DOWN              <opaque-object> . <passkey>)
>      [4].     (     OPAQUE-TYPE                     <object>            )
>      -----------------------------------------------------------------------
>      Both MAKE-OPAQUE-TYPE and OPAQUE-UP must be reserved identifiers so that
>      users cannot re-define them to subvert the abstraction barriers they are
>      designed to enforce.  By contrast, however, OPAQUE-DOWN and OPAQUE-TYPE
>      need be reserved keywords only so they can be recognized syntactically
>      by clever compilers to permit potentially more efficient code.  If they
>      are re-bound by a user, no security breach could ensue.)
> 
> Hmm...  I must have missed this remark on the first reading.  I don't
> understand why these identifiers need to be treated specially.  I don't
> understand why all four of your operations can't be ordinary procedures.
> So I guess I don't understand your security model.
>--------------------------------------------------------------------------

First, note that this text was from the first page of the 8-page message I
sent that contained the opacity proposal.  This text did not appear in the
body of the formal proposal itself.  That is because I am not myself
convinced that it is really necessary.

Originally the proposal said nothing about reserving any identifiers.  Then
I convinced myself that for a compiler to be able to flatten out all the
opaque up/down stuff, it would need to be able to syntactically recognize
instances of all four and know that they are not being re-defined at top
level.  Afterward, I convinced myself that unless MAKE-OPAQUE-TYPE and
OPAQUE-UP really truly do result in an opaque type and an opaque datum,
respectively, then a programmer could re-define them at top level and argue
that loading some compiled file that used them should still work under
their new re-definitions (along with appropriate re-definitions of
OPAQUE-DOWN and OPAQUE-TYPE). This could allow one to subvert the intended
opacity. [A detailed scenario demonstrating this appears at the end of
this message.]

I thought some people would object strongly if any sort of subversion
like this were possible so I sought to defuse that objection by reserving
a minimal set (the constructors) so they could not be re-defined in any
conforming implementation.

Maybe I was misguided.  If those who demand opacity would not object to
re-definition then they would not need to be reserved.  If compiler writers
don't believe that these need to be reserved in order to be compiled
efficiently, then none would need to be reserved for that reason either.

As you (Alan) pointed out to me earlier, this is really just an apology for
not having identifier namespace control (modules).  I guess I'm guilty of
the same sort of mixing of orthogonal issues as those who inspired me to
draft this proposal in the first place.  Still, I assumed that if we could
not ensure the integrity of MAKE-OPAQUE-TYPE and OPAQUE-UP that the opacity
proposal as a whole would not appease those clamoring for it in the first
place.

In short, I will not insist the four identifiers be reserved if nobody
would object to their not being reserved.

>-----------------------------------------------------------
> Exactly what is it that you are trying to defend against?
>-----------------------------------------------------------

[Lots of good questions expounding on this are omitted for brevity.]

To be honest, I'm not really sure.  I am not a strong advocate of opacity
and I would not mind, for instance, if the record proposal allowed easy,
fast abstraction breaking.  But this would surely bring a veto from those
who insist on opacity.

I know very well what Abstract Data Types are and what purpose they serve.
Those who demand ``opacity'', however, seem to be demanding something much
stronger: they seem to want something like a native, new, unique type for
which _no_ unregulated abstraction violation is possible.  I was hoping
that passkey-based opaque types would satisfy their demand for
regulation... especially if they had the option of concealing the passkeys
so nobody but the implementor themselves might engage in abstraction
breaking within an abstract data type definition (like the
``widget-package'' example below).

>--------------------------------------------------------------------------
> Can you give me a
> realistic scenario in which this passkey stuff protects some realistic
> thing from some realistic threat?
>--------------------------------------------------------------------------

I touched on this in my reply to Aubrey's query.  What this proposal is
trying to get at is some very general mechanism for building opaque data
types and opaque data with a variety of underlying security models.

Frankly, I have a feeling that not everyone on this list who insists on
`opaque' records has exactly the same thing in mind when they say `opaque'.
It would help me tremendously if one of them could clearly define just
what it is they demand.

I was trying to offer a proposal broad enough that it could encompass many
different underlying security systems.  Burstall and Lampson's introduction
of ``implementation passwords'' in their abstract data type definitions for
Pebble (which I cited in an earlier message) inspired me to think that just
this sort of passkey-based approach would offer a general trap door
mechanism for controlling opacity in Scheme.

In short, the passkeys are just a ``capability'' based mechanism a) for
regulating who can cross the abstraction barrier (they must know the
passkey), and b) for making it clear to those crossing the abstraction
barrier that they are crossing it (by making them use OPAQUE-DOWN... even
if the passkey for some opaque type is trivial or public information).

>--------------------------------------------------------------------------
> Once I understand that, then perhaps you can explain to me why allowing
> 
>   (let ((opaque-up ...)) ...)
> 
> would compromise that kind of security (whatever it is).
>--------------------------------------------------------------------------

It is not LET that is the problem.  It is top-level re-definition of
OPAQUE-UP that might worry some folks:


Here is the scenario I think would alarm the proponents of strong opacity
(that is, opacity with some capability-based control mechanism, like secret
passkey's):

Programmer A defines a nice `widget' abstract data type and procedures for
manipulating data instances of it, using OPAQUE-UP and so on, in a file
"widget". She compiles "widget" and distributes it to her Scheme friends.
She does not distribute source code since she does not want folks to know
the `widget' passkey. This way, she can distribute a different
implementation later w/o breaking anyone's code who may have exposed the
underlying data representation because, by withholding the passkey, they
_cannot_ expose the rep: only her widget package can do that and it never
lets the rep escape so it is never exposed.

The file "widget" contains:

;--------------------
; Begin file "widget"

(define (widget-package)
  (let ((widget-type (make-opaque-type "Wudjit")))
    (let ((make-widget (lambda (value)
                          (opaque-up widget-type (list value) "Wudjit")))
          (widget-value (lambda (widget)
                          (car (opaque-down widget "Wudjit"))))
          (set-widget-value! (lambda (widget new-value)
                                (set-car! (opaque-down widget "Wudjit")
                                          new-value))))
      (vector widget-type make-widget widget-value set-widget-value!))))

(define *widget-package* (widget-package))

(define widget-type       (vector-ref *widget-package* 0))
(define make-widget       (vector-ref *widget-package* 1))
(define widget-value      (vector-ref *widget-package* 2))
(define set-widget-value! (vector-ref *widget-package* 3))

; End file "widget"
;------------------

If OPAQUE-UP is not a reserved identifier, then it is an normal identifier
that scopes to a global variable bound to the procedure for coercing
concrete data up to their opaque-data counterparts, using the opaque type
passkey, in accordance with the interface in the opacity proposal
(duplicated at the top of this message).  Since we do not have a module
system or in-lined procedures in standard Scheme, this will resolve to the
top-level (or lexically nearest) binding of OPAQUE-UP in the environment
where WIDGET-PACKAGE is defined (presumably, the top-level environment into
which the "widget" file gets loaded).  Therein lies the problem.


Now programmer B defines the following renegade code at top level:


(define system-opaque-up opaque-up) ; Capture the system def before re-def

(define *passkey-witness-table* '())  ; An assq list keyed on opaque types
(define *abstraction-cracker*   '())  ; An assq list keyed on opaque data

(define (renegade-opaque-up opaque-type datum . passkey)
  (let ((real-opaque-datum
          (apply system-opaque-up `(,opaque-type ,datum ,@passkey))))
    (set! *passkey-witness-table*
          (cons (cons opaque-type passkey)
                *passkey-witness-table*))
    (set! *abstraction-cracker*
          (cons (cons real-opaque-datum datum)
                *abstraction-cracker*))
    real-opaque-datum))

;; Renegade opaque cracking code

(define opaque-up renegade-opaque-up)  ; The dreaded renegade re-definition

(define (opaque-type-passkey opaque-type)
  (let ((frame (assq opaque-type *passkey-witness-table*)))
    (if frame
        (cdr frame)
        #f)))

(define (opaque-crack-down opaque-datum)
  (let ((frame (assq opaque-datum *abstraction-cracker*)))
    (if frame
        (cdr frame)
        #f)))

;; Renegade printer

(define (display/crack object)
  (let ((ot (opaque-type object))) ; Returns #f if not opaque
    (if ot
        (display/crack (opaque-crack-down object)) ; Possibly multiple layers
        (display object))))

;; Renegade non-opaque widgets

(define (make-widget/cracked value)
  (opaque-crack-down (make-widget value)))

...etc.

He then loads in the abstract date type file "widget".  Programmer A's
widget instances can now be violated whenever programmer B wants by just
using (opaque-crack-down <widget>).  He can even run around creating non-
opaque widgets using his renegade `make-widget/cracked '.

It is not even necessary that the "widget" file be loaded _after_ the
renegade code redefines OPAQUE-UP.  At any moment, Programmer B could
type in the renegade re-definition and thereafter all new widgets created
would be crackable.

This defeats the whole purpose of OPAQUE-UP since it completely compromises
the opacity of any opaque widget by providing trivial abstraction breaking
procedures simply through re-definition of top-level OPAQUE-UP.  It does
_not_ require that Programmer B even know what the opacity passkey is for
`widgets'.

--

If this doesn't bother any of the opacity proponents, it sure doesn't
bother me either, so I will retract the statement that OPAQUE-UP and
MAKE-OPAQUE-TYPE need to be reserved identifiers for purposes of safety.

My suspicion, however, is that without this sort of restriction against
compromising the opacity of opaque data, this kind of opacity proposal
will never satisfy the demands of those who insist, for example, on some
guaranteed opacity of record types in the record proposal.

So the next time anyone proposes a module system, or whatever, this issue
of opacity will come back to haunt us again... and again.