Esthetics (or worse?) of Secure Pointers

Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

My apologies for the length of this message...

Thanks to John Gilmore, I'm getting my feet (and other body
parts) wet by picking up Greg McGary's Bounded Pointers work
on GCC, with the goal of improving application security
by preventing programs from violating array/string bounds,
while minimizing performance loss.

There are a few design issues to be dealt with. This message
asks for recommendations on two of them: glibc and bounds-checking
control.

The glibc change is difficult: due to internal changes in
pointer structure, glibc has to be recompiled in toto.
Programs compiled with bounds checking are incompatible
[from a linker/loader standpoint] with existing [non-bounds-chedked]
programs: the function call interface has to change for
pointers.

From a sanity standpoint, we'd like to be able to
intermix bounds-checked and non-bounds-checked functions.
John, Greg, and I discussed possible resolutions to this problem.
John and Greg may wish to correct me on my appreciation of our
discussion, which follows.

We discarded the function-level intermixing as too low-level
and complicated in practice. This left us with larger approaches to
the problem of intermixing checked and non-checked code:

a. Multiple libraries: discarded as too fragile and
   unstable, at least in their current state.

b. Rebuild entire applications with the new library. John's opinion
   is that, at least in Linux, we have complete source
   code availalbe, so building an entirely new distribution
   is reasonable.
   Obviously, non-Linux GCC users may not have this degree
   of control, but come the revolution... Oops, sorry. 8^}

   This is messy, in my view, as it is be possible,
   in practice, to introduce bounds checking into
   a bazllion lines of code and have it all work.
   So, we'd like to have a NudgeWare(tm) solution, in which
   we can migrate applications in a more controlled manner.

c. (Bear with me...) Greg's work controls bounds checking
   by a compiler flag:  --enabled-bounded.
   This means that we use the same glibc for both checked and
   non-checked output.
   John suggested an alternate approach which may work fine,
   but Greg is a bit leery of it, and I don't know enough about
   the issues: Bounds-checked code would be produced by
   introducing a new target architecture. My understanding of
   this us that it would let us have multiple glibcs lying
   around, in a manner that we could control easily.

   One of our concerns here is that this is like using
   a wrench as a hammer.

So, the question boils down to:

	What is the appropriate way to introduce an incompatible
        glibc, preferably in a way that lets it coexist with
        the existing glibc?

Thanks.
Bob


Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

Re: Esthetics (or worse?) of Secure Pointers

[Geoff Keating]

Robert Bernecky <bernecky@acm.org> writes:

> 	What is the appropriate way to introduce an incompatible
>         glibc, preferably in a way that lets it coexist with
>         the existing glibc?

This should really be asked on the glibc mailing lists, but since it's
here, I think that the existing bounded-pointer approach in glibc is 
as good or better than the alternatives you listed.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Robert Bernecky <bernecky@acm.org> writes:

> The glibc change is difficult: due to internal changes in
> pointer structure, glibc has to be recompiled in toto.
> Programs compiled with bounds checking are incompatible
> [from a linker/loader standpoint] with existing [non-bounds-chedked]
> programs: the function call interface has to change for
> pointers.

I see no trouble here.  Recompile libs for BPs.  No biggie.  You want
to do that anyway so that bounds checks are active for the libraries.

> From a sanity standpoint, we'd like to be able to
> intermix bounds-checked and non-bounds-checked functions.
> John, Greg, and I discussed possible resolutions to this problem.
> John and Greg may wish to correct me on my appreciation of our
> discussion, which follows.

Bob, I think you are hallucinating! John and I agreed long ago
that trying to mix bounded and unbounded code is an exercise in
frustration, and a poor use of time, since the resulting program has
holes in its checking.  IMO, the only sort of mixing that's desirable
is at the program level: you want to be able to run 100% BP programs
and 100% non-BP programs on the same OS.  IIRC, John doesn't even care
for any mixing: he wants the BP system to be an entirely different
architecture that's incompatible with non-BP.

> We discarded the function-level intermixing as too low-level
> and complicated in practice.

You stopped hallucinating so soon.  Good!  8^)

> This left us with larger approaches to
> the problem of intermixing checked and non-checked code:
> 
> a. Multiple libraries: discarded as too fragile and
>    unstable, at least in their current state.

I don't recall discarding that idea.  I think it's the only way to go.

> b. Rebuild entire applications with the new library. John's opinion
>    is that, at least in Linux, we have complete source
>    code availalbe, so building an entirely new distribution
>    is reasonable.
>    Obviously, non-Linux GCC users may not have this degree
>    of control, but come the revolution... Oops, sorry. 8^}
> 
>    This is messy, in my view, as it is be possible,
>    in practice, to introduce bounds checking into
>    a bazllion lines of code and have it all work.
>    So, we'd like to have a NudgeWare(tm) solution, in which
>    we can migrate applications in a more controlled manner.

Assuming you have a kernel that accommodates both BP and non-BP
programs, it's not so difficult to bootstrap an 100% BP system since
you can build things with a cross-compiler (BP target, non-BP host)
and test in a chroot'ed tree.

> c. (Bear with me...) Greg's work controls bounds checking
>    by a compiler flag:  --enabled-bounded.

Correction: the options are -fbounded-pointers and -fcheck-bounds.
The first tells GCC to make pointers "fat", the second tells GCC to
emit bounds checking code.  Using the first implies the second.  One
can explicitly turn off the second to get fat-pointer interfaces
without having runtime bounds checks.  This could be used for
partitioning the debugging task, or for assessing the performance
impact of fat-pointer handling in isolation from that of runtime
checks.

>    This means that we use the same glibc for both checked and
>    non-checked output.

That it doesn't necessarily follow.  Compiler options can trigger use
of alternate library sets.  That's what multilibs are all about.

>    John suggested an alternate approach which may work fine,
>    but Greg is a bit leery of it, and I don't know enough about
>    the issues: Bounds-checked code would be produced by
>    introducing a new target architecture. My understanding of
>    this us that it would let us have multiple glibcs lying
>    around, in a manner that we could control easily.

With multilibs, it is possible to have a single compiler executable
produce code that requires different library variants.  I'm not so
leery about handling BPs as a different target architecture, I just
think it might be inconvenient.  OTOH, maintaining multilibs just so
one can use the same compiler for BP and non-BP might be more
inconvenient.  I'd appreciate the input of someone experienced with
maintaining multilibs.

> So, the question boils down to:
> 
> 	What is the appropriate way to introduce an incompatible
>       glibc, preferably in a way that lets it coexist with
>       the existing glibc?

It must be a different glibc (and different every-other-lib).  The
only question is:

1) should BP compilation be done with a cross compiler (non-BP host, BP
target), and BP libs found in the place reserved for that target.

2) should BP compilation be done with a compiler option and BP libs
found via multilib mechanisms.

I favor #2 because whereas it's useful to think of BPs as being a
different architecture in some contexts, they really aren't so
different as that.  The same machine insn set is used, and both kinds
of programs can run natively and simultaneously on the same OS.  (If we
go with #1, is there any barrier or added inconvenience to running BP
programs with shared libraries?)

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

Greg's right on all of the following: I'm the newcomer
on the project, and am not up to speed on much of this;
Greg's done all the work up to this point.
Answers to his questions (or new ideas) at the bottom are still
desired, as would be some more info on multilibs.

Bob

On 17 Apr 2001, Greg McGary wrote:

> Robert Bernecky <bernecky@acm.org> writes:
>
> > The glibc change is difficult: due to internal changes in
> > pointer structure, glibc has to be recompiled in toto.
> > Programs compiled with bounds checking are incompatible
> > [from a linker/loader standpoint] with existing [non-bounds-chedked]
> > programs: the function call interface has to change for
> > pointers.
>
> I see no trouble here.  Recompile libs for BPs.  No biggie.  You want
> to do that anyway so that bounds checks are active for the libraries.
>
> > From a sanity standpoint, we'd like to be able to
> > intermix bounds-checked and non-bounds-checked functions.
> > John, Greg, and I discussed possible resolutions to this problem.
> > John and Greg may wish to correct me on my appreciation of our
> > discussion, which follows.
>
> Bob, I think you are hallucinating! John and I agreed long ago
> that trying to mix bounded and unbounded code is an exercise in
> frustration, and a poor use of time, since the resulting program has
> holes in its checking.  IMO, the only sort of mixing that's desirable
> is at the program level: you want to be able to run 100% BP programs
> and 100% non-BP programs on the same OS.  IIRC, John doesn't even care
> for any mixing: he wants the BP system to be an entirely different
> architecture that's incompatible with non-BP.
>
> > We discarded the function-level intermixing as too low-level
> > and complicated in practice.
>
> You stopped hallucinating so soon.  Good!  8^)
>
> > This left us with larger approaches to
> > the problem of intermixing checked and non-checked code:
> >
> > a. Multiple libraries: discarded as too fragile and
> >    unstable, at least in their current state.
>
> I don't recall discarding that idea.  I think it's the only way to go.
>
> > b. Rebuild entire applications with the new library. John's opinion
> >    is that, at least in Linux, we have complete source
> >    code availalbe, so building an entirely new distribution
> >    is reasonable.
> >    Obviously, non-Linux GCC users may not have this degree
> >    of control, but come the revolution... Oops, sorry. 8^}
> >
> >    This is messy, in my view, as it is be possible,
> >    in practice, to introduce bounds checking into
> >    a bazllion lines of code and have it all work.
> >    So, we'd like to have a NudgeWare(tm) solution, in which
> >    we can migrate applications in a more controlled manner.
>
> Assuming you have a kernel that accommodates both BP and non-BP
> programs, it's not so difficult to bootstrap an 100% BP system since
> you can build things with a cross-compiler (BP target, non-BP host)
> and test in a chroot'ed tree.
>
> > c. (Bear with me...) Greg's work controls bounds checking
> >    by a compiler flag:  --enabled-bounded.
>
> Correction: the options are -fbounded-pointers and -fcheck-bounds.
> The first tells GCC to make pointers "fat", the second tells GCC to
> emit bounds checking code.  Using the first implies the second.  One
> can explicitly turn off the second to get fat-pointer interfaces
> without having runtime bounds checks.  This could be used for
> partitioning the debugging task, or for assessing the performance
> impact of fat-pointer handling in isolation from that of runtime
> checks.
>
> >    This means that we use the same glibc for both checked and
> >    non-checked output.
>
> That it doesn't necessarily follow.  Compiler options can trigger use
> of alternate library sets.  That's what multilibs are all about.
>
> >    John suggested an alternate approach which may work fine,
> >    but Greg is a bit leery of it, and I don't know enough about
> >    the issues: Bounds-checked code would be produced by
> >    introducing a new target architecture. My understanding of
> >    this us that it would let us have multiple glibcs lying
> >    around, in a manner that we could control easily.
>
> With multilibs, it is possible to have a single compiler executable
> produce code that requires different library variants.  I'm not so
> leery about handling BPs as a different target architecture, I just
> think it might be inconvenient.  OTOH, maintaining multilibs just so
> one can use the same compiler for BP and non-BP might be more
> inconvenient.  I'd appreciate the input of someone experienced with
> maintaining multilibs.
>
> > So, the question boils down to:
> >
> > 	What is the appropriate way to introduce an incompatible
> >       glibc, preferably in a way that lets it coexist with
> >       the existing glibc?
>
> It must be a different glibc (and different every-other-lib).  The
> only question is:
>
> 1) should BP compilation be done with a cross compiler (non-BP host, BP
> target), and BP libs found in the place reserved for that target.
>
> 2) should BP compilation be done with a compiler option and BP libs
> found via multilib mechanisms.
>
> I favor #2 because whereas it's useful to think of BPs as being a
> different architecture in some contexts, they really aren't so
> different as that.  The same machine insn set is used, and both kinds
> of programs can run natively and simultaneously on the same OS.  (If we
> go with #1, is there any barrier or added inconvenience to running BP
> programs with shared libraries?)
>
> Greg
>

Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

Re: Esthetics (or worse?) of Secure Pointers

[Joe Buck]

Greg McGary writes:
> Bob, I think you are hallucinating! John and I agreed long ago
> that trying to mix bounded and unbounded code is an exercise in
> frustration, and a poor use of time, since the resulting program has
> holes in its checking.

It might be possible, for specific libraries, to write a set of thunks
that would allow bounds-checked code to call the non-bounds-checked C
library.  Such things might be necessary for people on OSes that don't
have a free C library to use the bounds checking compiler.  This thunks
layer would assume that the C library is correct, and use the known
properties of the library function to determine bounds in cases where
pointers are returned (e.g. for malloc we set the lower bound to result
and the upper bound to result+size).  And yes, I know there are lots of
problems with functions like strchr that assume strings are properly
null-terminated.

But even if this is done, in the end it perhaps doesn't make a great
deal of difference: if you use bounds checking you need a different libc.
Perhaps this is produced by building a libc from source with a bounds
checking compiler, or perhaps it is produced by some other form of
trickery as described above.

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Joe Buck <jbuck@racerx.synopsys.com> writes:

> It might be possible, for specific libraries, to write a set of thunks
> that would allow bounds-checked code to call the non-bounds-checked C
> library.

To some degree it is possible.  I did this in the early going as a
necessity of bootstraping so that I could run the C torture tests with
a non-BP glibc.  Once GCC passed enough torture tests, I moved on to
glibc, and now that I have a BP glibc, I no longer need thunks to run
torture tests or to port anything else.

> Such things might be necessary for people on OSes that don't
> have a free C library to use the bounds checking compiler.

We have limited resources.  Bending over backwards to support non-free
OSes is a poor use of those resources.  Much better to press forward
in the land of the free.

> This thunks layer would assume that the C library is correct, and
> use the known properties of the library function to determine bounds
> in cases where pointers are returned (e.g. for malloc we set the
> lower bound to result and the upper bound to result+size).  And yes,
> I know there are lots of problems with functions like strchr that
> assume strings are properly null-terminated.
> 
> But even if this is done, in the end it perhaps doesn't make a great
> deal of difference: if you use bounds checking you need a different libc.
> Perhaps this is produced by building a libc from source with a bounds
> checking compiler, or perhaps it is produced by some other form of
> trickery as described above.

IMO, it's an interesting academic research project, but has no
priority over the important work of finding and fixing bugs & security
holes in free software.

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Joe Buck]

I wrote:
> > It might be possible, for specific libraries, to write a set of thunks
> > that would allow bounds-checked code to call the non-bounds-checked C
> > library...
> > Such things might be necessary for people on OSes that don't
> > have a free C library to use the bounds checking compiler.

Greg writes:
> We have limited resources.  Bending over backwards to support non-free
> OSes is a poor use of those resources.  Much better to press forward
> in the land of the free.

By mentioning it I didn't mean to imply that you should do it!

Certainly you shouldn't waste your time implementing this.  Once BP-gcc
is successful, other folks might be interested in contributing it.
There might be speed advantages to doing it this way even with the free
glibc, or memory savings for folks running a mix of BP and non-BP apps,
but then improving gcc's optimization might make it unnecessary.

Re: Esthetics (or worse?) of Secure Pointers

[Per Abrahamsen]

Excuse me for side-tracking for a moment.

It is clear that John Gilmore's main interest in BP is security
concerns, and given that he fund the project that use obviously has
priority.

However, I suspect most GCC users interest in BP will be as a debug
tool.  As such, some parameters change: It doesn't matter whether GC
ever get used in production systems.  It will be nice, just like many
developers leave assertions enabled in shipped code, but is not
essential.  Fast is nice, but again not essential.  A 200% overhead
doesn't reduce the utility much.  A guarentee that all bounds in the
system is checked is no requirement, this will be an extra tool, not a
replacement of whatever else is used to eliminate errors.  On the
other hand, having to recompile all external libraries, and switching
between the two versions, will be a major obstacle.

So while "securing free software" have to be the main goal because of
funding, I hope you won't totally forget "a new debug tool" as a
secondary goal.  It will not be worthless even if it doesn't get
mainstream.

Re: Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

On Wed, 18 Apr 2001, Jimen Ching wrote:

> Robert Bernecky <bernecky at acm dot org> said:
> >As computing professionals, we have a responsibility to
> >provide provably reliable tools. C without secure pointers
> >is not reliable. We (the computing community) are going to
> >be forced to move programming from a craft to an engineering
> >discipline. Issues of performance and memory use are going
> >to be swept aside by the threat of lawsuits.
>
> Why is it that people think software professionals should always look for
> silver bullets?

BP is a stone club, not a silver bullet. It does, howver, detect
one set of EXTREMELY serious security holes in
C programs. A silver bullet might be a switch to languages
that treat collections of data in a more disciplined manner
that is more amenable to static analysis.

> Btw, isn't one of the motto's of the C programming language go something
> like--trust the programmer.  Now, if we could do that, then we would have
> finally become a professional discipline.

Unfortunately, time has shown that we can not trust the programmer.
Programmers are good at algorithm creation, and lousy at memory
management, loop-bounds writing, etc. That's why there's a huge
demand for find-the-dangling-pointer-finder products.

> Don't get me wrong, I think BP is a great tool.  But until the overhead is
> reduced to less than 3%, I don't think it should be forced on anyone.

I don't think anyone disagrees that lower is better, except maybe
Intel.

Bob

Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

Re: Esthetics (or worse?) of Secure Pointers

[Jimen Ching]

Robert Bernecky <bernecky at acm dot org> said:
>As computing professionals, we have a responsibility to
>provide provably reliable tools. C without secure pointers
>is not reliable. We (the computing community) are going to
>be forced to move programming from a craft to an engineering
>discipline. Issues of performance and memory use are going
>to be swept aside by the threat of lawsuits.

Why is it that people think software professionals should always look for
silver bullets?

	As professionals, we must use GC to eliminate all memory heap
	problems.

	As professionals, we must use BP to eliminate all buffer overflow
	problems.

Would real professionals look for silver bullets to solve their problems?  
Should we not see each tool for what it is, i.e. just another tool in our
toolbox?

Btw, isn't one of the motto's of the C programming language go something
like--trust the programmer.  Now, if we could do that, then we would have
finally become a professional discipline.

Don't get me wrong, I think BP is a great tool.  But until the overhead is
reduced to less than 3%, I don't think it should be forced on anyone.

--jc
--
Jimen Ching (WH6BRR)      jching@flex.com     wh6brr@uhm.ampr.org

Re: Esthetics (or worse?) of Secure Pointers

[Fergus Henderson]

On 18-Apr-2001, Robert Bernecky <bernecky@acm.org> wrote:
> Think of John's proposal as a stepping stone. We introduce a new
> architecture (bounded-x86) that lives alongside the existing
> x86 architecture. In the fullness of time, everyone buys
> into the secure-x86 architecture, we retire the x86 architecture
> completely, and everyone lives happily ever after.
> 
> Will this work? I believe that there are strong
> engineering and liability reasons that will make it work.
...
> John's position, and mine, is that good optimization work should
> let us get the cpu time overheads down to acceptable levels.
> We are stuck with the memory overhead, but memory is cheaper
> every day, so that's probably acceptable, particularly now that
> 64-bit architectures are becoming reasonably priced.

If you can't avoid significant memory overhead, then due to memory
hierarchy effects you're going to have an unavoidable significant
time overhead for a lot of applications.  Memory may be cheap, but
cache is still expensive, and on-chip cache sizes are limited by
the technology.  CPU speeds are increasing faster than memory speeds,
so more and more applications are limited by memory bandwidth.

So, although I admire your aims, I don't see the bounded-x86 architecture
replacing x86 any time soon.  Rather, the two will have to coexist.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: < http://www.cs.mu.oz.au/~fjh >  |     -- the last words of T. S. Garp.

Re: Esthetics (or worse?) of Secure Pointers

[Toon Moene]

John Gilmore wrote:

> The whole idea, from my point of view, is to implement secure pointers
> efficiently enough that people just accept the 10-15% overhead, since
> for most people CPU cycles are close to free anyway.

Hey - you're killing my next project !  Given the non-advancing BP
effort, I thought of converting all of the free software base to Fortran
- starting Q2 next year.

That way, bounded pointers would just mean g77 -fbounds-check and you
could mix checking and non-checking code freely ...

1/2 :-)

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: Esthetics (or worse?) of Secure Pointers

[Joern Rennecke]

> I know what you're trying to say, but "provably reliable tools" is
> somewhat too strong.  You'd have to prove compiler correctness first.
> Modulo compiler correctness it might be possible.

Application correctness is also more important than bounds checking.
If the application is coded bug-free, it does not need any bounds checking.
Even with bounds checking, you can inadvertently write an application
that has security holes, you merely lower the probability of doing that.

Moreover, how are you going to prove that the user is going to use the
application in such a way as to ascertain reliable operation?

You can hurt yourself when you try to drive in a nail by pounding on it
with a microscope.

Re: Esthetics (or worse?) of Secure Pointers

[Neil Booth]

Robert Bernecky wrote:-

> As computing professionals, we have a responsibility to
> provide provably reliable tools. C without secure pointers
> is not reliable.

I know what you're trying to say, but "provably reliable tools" is
somewhat too strong.  You'd have to prove compiler correctness first.
Modulo compiler correctness it might be possible.

Neil.

Re: Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

Well, sort of.

[I don't want to start a religious war here; I do want to  make
my position clearer.]

Think of John's proposal as a stepping stone. We introduce a new
architecture (bounded-x86) that lives alongside the existing
x86 architecture. In the fullness of time, everyone buys
into the secure-x86 architecture, we retire the x86 architecture
completely, and everyone lives happily ever after.

Will this work? I believe that there are strong
engineering and liability reasons that will make it work.
Here is a tiny picture of the future of the programming
world, as lawyers exploit their y2k experiences:

http://www.theregister.co.uk/content/8/18324.html

As computing professionals, we have a responsibility to
provide provably reliable tools. C without secure pointers
is not reliable. We (the computing community) are going to
be forced to move programming from a craft to an engineering
discipline. Issues of performance and memory use are going
to be swept aside by the threat of lawsuits.

As someone who has worked with array languages since the dark
ages (a bit earlier, actually), I have to emphasize that code
safety (in the sense of having array buonds checks and automatic
memory management) is an incredibly powerful tool for creating
secure and robust applications. Buffer overflows simply do not
and CAN NOT exist in array languages (modulo compiler bugs, of
course).

Secure pointers are not a complete solution to the problems in
C (dangling pointers can still exist, and the absence of
real arrays (N-dimensional objects rather than vectors of
vectors) causes increased overhead and opportunity for
more code faults), but they move us a long way toward
reliability.

John's position, and mine, is that good optimization work should
let us get the cpu time overheads down to acceptable levels.
We are stuck with the memory overhead, but memory is cheaper
every day, so that's probably acceptable, particularly now that
64-bit architectures are becoming reasonably priced.

Bob

On Wed, 18 Apr 2001, Joern Rennecke wrote:

> >
> > On Tue, Apr 17, 2001 at 10:45:44PM -0400, David Edelsohn wrote:
> > > 	The ELF architecture field in the header is assigned, not
> > > something that one can "pick a new specifier" without causing conflicts.
> >
> > But since the ABI is effectively different anyways, one could argue it is a
> > different machine (John's proposal) and/or uses a data encoding (my proposal)
> > or even using some other field.
>
> John's proposal is not practical, since it means that you have to allocate
> a new machine identifier for every machine identifier in existance where
> you would contemplate using the BP checking compiler.  And also for all
> future non-BP machine identifiers.  And you have to make sure you don't
> step on someone's elses toes while doing these allocations.
>
> The data encoding proposal seems much more practical to me.  You just have
> to add two more types, and cover all architectures.
>

Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

Re: Esthetics (or worse?) of Secure Pointers

[Joern Rennecke]

> 
> On Tue, Apr 17, 2001 at 10:45:44PM -0400, David Edelsohn wrote:
> > 	The ELF architecture field in the header is assigned, not
> > something that one can "pick a new specifier" without causing conflicts. 
> 
> But since the ABI is effectively different anyways, one could argue it is a
> different machine (John's proposal) and/or uses a data encoding (my proposal)
> or even using some other field.

John's proposal is not practical, since it means that you have to allocate
a new machine identifier for every machine identifier in existance where
you would contemplate using the BP checking compiler.  And also for all
future non-BP machine identifiers.  And you have to make sure you don't
step on someone's elses toes while doing these allocations.

The data encoding proposal seems much more practical to me.  You just have
to add two more types, and cover all architectures.

Re: Esthetics (or worse?) of Secure Pointers

[Joern Rennecke]

> Hmmm... I suppose I was looking at it from a different perspective.  It
> seems that if all pointers are bounded pointers, it becomes trivial to
> propogate information about the "real" pointed to object (ie, because I
> pointer could be at an offset from the 'real' object).  Now if you
> introduce transitions between bounded and unbounded pointers, you somehow
> have to do a search to resolve what an unbounded pointer points to.

No search is needed - you just have to accept that an unbounded pointer is
just that, unbounded.  So when you translate it into a bounded pointer,
the bounds become the start and end of the address space.

Re: Esthetics (or worse?) of Secure Pointers

[Joe Buck]

John Gilmore writes:

> The whole idea, from my point of view, is to implement secure pointers
> efficiently enough that people just accept the 10-15% overhead, since
> for most people CPU cycles are close to free anyway.  And eventually
> to influence chip architecture for more efficient support.

I like the work on bounded pointers very much.  But there are many
applications where very large data structures are needed, and we can't
get around the fact that pointers now require three times the memory.
We may be able to get down to 10-15% time overhead, since most checks
won't have to be made and many bounds are the same.  But the space
overhead is another matter.

For some algorithms that some people care deeply about (e.g. static timing
verification of an ASIC) we're already having trouble fitting in 2^32
bytes (5 million gates, with 1Kbyte or so of data for each gate to represent
all the pins and the time delays between transitions on each pin pair,
you get the idea) -- of course, folks can and are moving to 64-bit
machines, but many are reluctant to do so before they have to.  We could
still do bounded pointers, if we force the designers of such algorithms to
change their data structures, maybe by using integers for pointers and put
all the objects into one space ... oops, looks a lot what malloc and thin
pointers do now.

Evil memories of all those 16-bit Windows C pointer types come creeping
back ...

> I see little
> point in implementing a curiosity that nobody will use; if it doesn't
> have a shot to become the mainstream, then it isn't worth doing.

Despite my caveats above, I'd feel much better about things if every
program that runs as root or is setuid used bounded pointers.  Buffer
overruns become impossible; one less nasty to worry about.

Re: Esthetics (or worse?) of Secure Pointers

[Michael Meissner]

On Tue, Apr 17, 2001 at 10:45:44PM -0400, David Edelsohn wrote:
> 	The ELF architecture field in the header is assigned, not
> something that one can "pick a new specifier" without causing conflicts. 

But since the ABI is effectively different anyways, one could argue it is a
different machine (John's proposal) and/or uses a data encoding (my proposal)
or even using some other field.

-- 
Michael Meissner, Red Hat, Inc.  (GCC group)
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886, USA
Work:	  meissner@redhat.com		phone: +1 978-486-9304
Non-work: meissner@spectacle-pond.org	fax:   +1 978-692-4482

Re: Esthetics (or worse?) of Secure Pointers

[Michael Meissner]

On Tue, Apr 17, 2001 at 07:40:48PM -0700, John Gilmore wrote:
> > For a backup plan, I think it's sufficient to mandate no mixing of BP
> > and non-BP compilation units, distinguished by a special symbol,
> > enforced by ld.  Anyone violently disagree?
> 
> Yes, I disagree.
> 
> ELF and many other formats have a field in the file header for what
> architecture the object file contains.  Pick a new architecture
> specifier when compiling for an architecture with larger pointers.
> Just as big-endian and little-endian code compiled for the same chip
> gets different architecture types, big-pointer and little-pointer code
> for the same chip should be distinguished in this way.

Actually I would recomend using the data encoding field (byte #5), which
currently has 2 possible values (ELFDATA2LSB and ELFDATA2MSB for little endian
and big endian respectively), rather than try to duplicate N number of
different architectures.

> I'm pretty sure the linker already checks that you aren't mixing
> architecture types in your object files.
> 
> Use the abstractions we already have for what they are designed for,
> rather than making up new kludges for every special case...
> 
> 	John

-- 
Michael Meissner, Red Hat, Inc.  (GCC group)
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886, USA
Work:	  meissner@redhat.com		phone: +1 978-486-9304
Non-work: meissner@spectacle-pond.org	fax:   +1 978-692-4482

Re: Esthetics (or worse?) of Secure Pointers

[David Edelsohn]

	The ELF architecture field in the header is assigned, not
something that one can "pick a new specifier" without causing conflicts. 

David

Re: Esthetics (or worse?) of Secure Pointers

[John Gilmore]

> For a backup plan, I think it's sufficient to mandate no mixing of BP
> and non-BP compilation units, distinguished by a special symbol,
> enforced by ld.  Anyone violently disagree?

Yes, I disagree.

ELF and many other formats have a field in the file header for what
architecture the object file contains.  Pick a new architecture
specifier when compiling for an architecture with larger pointers.
Just as big-endian and little-endian code compiled for the same chip
gets different architecture types, big-pointer and little-pointer code
for the same chip should be distinguished in this way.

I'm pretty sure the linker already checks that you aren't mixing
architecture types in your object files.

Use the abstractions we already have for what they are designed for,
rather than making up new kludges for every special case...

	John

Re: Esthetics (or worse?) of Secure Pointers

[John Gilmore]

> John  eventually convinced me that there's no way to decide
> at compile time what a subfunction's boundedness is. Bummer.
> This led us to the compile-the-whole-thing approach, which
> we all find scary. Hence, this request for more brain cells.

I don't find it scary at all, I find it the obvious thing to do.

The whole idea, from my point of view, is to implement secure pointers
efficiently enough that people just accept the 10-15% overhead, since
for most people CPU cycles are close to free anyway.  And eventually
to influence chip architecture for more efficient support.  I see little
point in implementing a curiosity that nobody will use; if it doesn't
have a shot to become the mainstream, then it isn't worth doing.

With these goals for the project, it makes no sense to waste any
effort trying for backward calling sequence compatability.  It would
be like trying to make x86 code be able to call ARM code or SPARC
code.  Yes, you could work very hard to make that happen (like Apple
did for intermixing 68000 and PowerPC code by emulation).  You could
mangle the debugger, the compiler, the linker, the runtimes, all in
pursuit of this crazy goal.  But why would you bother?

	John

PS:  One place where you could build calling sequence translators
is on the Unix system call boundary between kernel and user space.  That
work has already been done, so you could run a secure-pointers application
on an insecure-pointers kernel, or vice verse.  Handily, the system calls
all take length parameters, so you can calculate good bounds if you need to.

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Chris Lattner <sabre@nondot.org> writes:

> If possible, that definately sounds like the best idea... GDB will still
> need to be enhanced however.

John recommends, and I agree, that we handle BP programs as a
different architecture for gdb.  GCC needs to be fixed so that it
doesn't emit debug symbols that type fat pointers as structs, which
they are internal to GCC.  GCC can and should handle fat pointers
internally as multi-word structs, but when it comes time to write
the compiled output, it should emit debug symbols that identify
them merely as large, indivisible pointers.

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Fergus Henderson]

On 17-Apr-2001, Chris Lattner <sabre@nondot.org> wrote:
> 
> > We discarded the function-level intermixing as too low-level
> > and complicated in practice. This left us with larger approaches to
> > the problem of intermixing checked and non-checked code:
> 
> Another alternative way to implement this (which would allow a single libc
> that contains both bounded pointer code and nonbounded pointer code to
> exist in the same library), would be to mangle function names, ala
> C++.  Of course you could do this really simply by simply prefixing all
> functions (C as well) with __BP_ or some such ugly thing.

Actually that's not always sufficient; to handle the general case,
you need to also add the prefix to data symbols.

Note that GNU C++ and most other current C++ implementations don't
mangle data symbols.  Nor do they mangle function return types.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: < http://www.cs.mu.oz.au/~fjh >  |     -- the last words of T. S. Garp.

Re: Esthetics (or worse?) of Secure Pointers

[Chris Lattner]

> For a backup plan, I think it's sufficient to mandate no mixing of BP
> and non-BP compilation units, distinguished by a special symbol,
> enforced by ld.  Anyone violently disagree?  (Yes, I know this is the
> purview of the binutils list, so we'll need to ask there about ld's
> role as enforcer)

If possible, that definately sounds like the best idea... GDB will still
need to be enhanced however.  If nothing else, printing out and
dereferencing fat pointers is different than normal pointers.  I assume
that this enhancement would be more clean than an outright hack (which GDB
doesn't need) to remove the prefix...

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/MagicStats/
http://www.nondot.org/~sabre/

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

"Zack Weinberg" <zackw@stanford.edu> writes:

> I've been considering some sort of toggle to make gcc emit mangled
> symbols for C code for awhile.  The original idea was to catch
> prototype mismatches at link time; there'd be no change to C
> semantics.

That's a fine idea in general, and with BP keyletters integrated, that
solves the problems, but we also need a backup plan in the absence of
mangling.

For a backup plan, I think it's sufficient to mandate no mixing of BP
and non-BP compilation units, distinguished by a special symbol,
enforced by ld.  Anyone violently disagree?  (Yes, I know this is the
purview of the binutils list, so we'll need to ask there about ld's
role as enforcer)

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Zack Weinberg]

On Tue, Apr 17, 2001 at 04:36:01PM -0700, Greg McGary wrote:
> Chris Lattner <sabre@nondot.org> writes:
> 
> > Another alternative way to implement this (which would allow a single libc
> > that contains both bounded pointer code and nonbounded pointer code to
> > exist in the same library), would be to mangle function names, ala
> > C++.  Of course you could do this really simply by simply prefixing all
> > functions (C as well) with __BP_ or some such ugly thing.
> 
> I want to move in the opposite direction, and drop the __BP_ prefix,
> since it complicates symbolic debugging, and I don't want to burden
> gdb with hiding the prefix.  OTOH, the reason I introduced the prefix
> in the first place remains valid: I wanted to catch unintentional
> mixing of BP and non-BP code at link time, so as to prevent
> much-more-painful-to-debug runtime incompatibilities.  Perhaps that
> can be accomplished some other way.

Could we maybe (ab)use the C++ name mangler for this?  'BPi' for
bounded pointer to int, say, and instead of __BP_memcpy, we have
_Z6memcpyBPvBPvm.  gdb then just works.

I've been considering some sort of toggle to make gcc emit mangled
symbols for C code for awhile.  The original idea was to catch
prototype mismatches at link time; there'd be no change to C
semantics.

zw

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Robert Bernecky <bernecky@acm.org> writes:

> Consider an app, APP, that calls both XFree86 code and also calls
> something else large, like tcp/ip code.

TCP/IP APs are already done as part of glibc.

> In order to convert APP to use bounded pointers, Xfree86 and tcp/ip
> have to be compiled as bounded first.

The X protocol doesn't transmit pointers, so BP X apps should run on a
non-BP X server.  Assuming you have your multilibs configured properly,
non-BP X apps continue to work using the non-BP X libs, while you slog
away building BP versions of X libs, and step by step, you get them up
and now you can run BP X apps too.

> All their callers must then be converted at the same
> time. It's right up there with budgie jumping and parrot shoot
> jumping: a high level of committment is called for.

Bob, try to relax.  You just haven't lived with the problem long
enough.  In time, you'll feel much less intimidated.  Start small:
port some ncurses programs before you tackle X11!  8^)

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Chris Lattner <sabre@nondot.org> writes:

> ... It
> seems that if all pointers are bounded pointers, it becomes trivial to
> propogate information about the "real" pointed to object (ie, because I
> pointer could be at an offset from the 'real' object).

Yes, exactly.

> Now if you introduce transitions between bounded and unbounded
> pointers, you somehow have to do a search to resolve what an
> unbounded pointer points to.

Just don't do it.  Waaay too much rutime overhead.

> The only practical way I can see to do this ... is to compile a whole
> program at a time with bounded pointer support.  This isn't neccesarily
> hard, except that all of the libraries that it links to also have to be
> compiled with bounded pointer support. 

Yes, exactly.

> If the libraries have a dual nature (ie, they have 2x the amount of code
> as normal, one as bounded and one as unbounded), you wouldn't have a
> problem.  In fact for a 'secure' OS distro, for example, this is perfectly
> reasonable.

Don't mix BP and and non-BP code in libraries.  Keep libraries
distinct.  Arrange for GCC, ld and dynamic linker to find libraries
appropriate to the boundeness of the program.

> So I guess the question is, is it really reasonable to mix bounded and
> unbounded code in the same dynamic instance of a program?

No, no, never, never, uuuh, uuuh, uuuh!

> I assume that bounded pointers would still have to be *somewhat*
> efficient to maintain their usefulness...

Exactly.  Space and time overhead at this time runs 150%..200%
(2.5x..3x bloat & slowdown) because some crucial optimizations are
missing from GCC.  Once GCC has those optimizations, space & time
overhead can drop to under 50%.  John thinks we have to get it down to
20% to be viable.  My gut is that 20% *might* be attainable on
register-rich RISCy machines, but is not on register-poor CISCy
machines.

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Robert Bernecky <bernecky@acm.org> writes:

> John  eventually convinced me that there's no way to decide
> at compile time what a subfunction's boundedness is. Bummer.
> This led us to the compile-the-whole-thing approach, which
> we all find scary.

I don't find that scary.  You'll get used to it as well.  It's only
scary if you can't run the BP programs alongside your non-BP programs,
i.e., if BP is a distinct and completely incompatible architecture and
thus requires a ground-up OS+libs+utils port.  That's not the case
here.  Since we already have a BP glibc, all you gotta do is tackle
one program and library at a time and you can build & test natively on
your non-BP OS.

> Thunks almost work, but it  has the unsolved problem of identifying
> bounded vs non-bounded pointers in a precise manner.

Gaaaack!  Please, let's not waste another sentence on mixing code at
function granularity.  The only useful question is how we are going to
accommodate BP and non-BP libraries (shared and non) on the same
system so as to allow both to run natively.

Greg

Re: Esthetics (or worse?) of Secure Pointers

[Greg McGary]

Chris Lattner <sabre@nondot.org> writes:

> Another alternative way to implement this (which would allow a single libc
> that contains both bounded pointer code and nonbounded pointer code to
> exist in the same library), would be to mangle function names, ala
> C++.  Of course you could do this really simply by simply prefixing all
> functions (C as well) with __BP_ or some such ugly thing.

I want to move in the opposite direction, and drop the __BP_ prefix,
since it complicates symbolic debugging, and I don't want to burden
gdb with hiding the prefix.  OTOH, the reason I introduced the prefix
in the first place remains valid: I wanted to catch unintentional
mixing of BP and non-BP code at link time, so as to prevent
much-more-painful-to-debug runtime incompatibilities.  Perhaps that
can be accomplished some other way.  Since we all agree that
compilation units will either be 100% or 0% BP, we needn't have a
mechanism that operates at the granularity of functions as the current
__BP_ prefix does.  We could introduce a special symbol that marks a
BP object (analogous to gcc2_compiled.), and make ld gripe if it sees
any mixing of BP and non-BP objects.

> This isn't a wonderful solution from a cleanliness standpoint, but it
> would make it "impossible" to accidentally mismatch code.  It would also
> make it possible to have a library with both bounded pointer and
> nonbounded pointer code linked into it, which would be nice.

The libs should remain separate just as they do for other multilibs.

Greg

RE: Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

On Tue, 17 Apr 2001, Chris Lattner wrote:

> The only practical way I can see to do this (although I don't really know
> what I'm talking about, so please remember that.  :) is to compile a whole
> program at a time with bounded pointer support.  This isn't neccesarily
> hard, except that all of the libraries that it links to also have to be
> compiled with bounded pointer support.

The crux of the problem is that it's a
Tar Baby~\cite{ http://www.savonvideo.com/tarbaby.htm} .
Consider an app, APP, that calls both XFree86 code and also calls
something else large, like tcp/ip code. In order to convert APP
to use bounded pointers, Xfree86 and tcp/ip have to be compiled
as bounded first. All their callers must then be converted at the same
time. It's right up there with budgie jumping and parrot shoot
jumping: a high level of committment is called for.

Bob

Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

RE: Esthetics (or worse?) of Secure Pointers

[Chris Lattner]

> John  eventually convinced me that there's no way to decide
> at compile time what a subfunction's boundedness is. Bummer.
> This led us to the compile-the-whole-thing approach, which
> we all find scary. Hence, this request for more brain cells.

Hmmm... I suppose I was looking at it from a different perspective.  It
seems that if all pointers are bounded pointers, it becomes trivial to
propogate information about the "real" pointed to object (ie, because I
pointer could be at an offset from the 'real' object).  Now if you
introduce transitions between bounded and unbounded pointers, you somehow
have to do a search to resolve what an unbounded pointer points to.

The only practical way I can see to do this (although I don't really know
what I'm talking about, so please remember that.  :) is to compile a whole
program at a time with bounded pointer support.  This isn't neccesarily
hard, except that all of the libraries that it links to also have to be
compiled with bounded pointer support. 

If the libraries have a dual nature (ie, they have 2x the amount of code
as normal, one as bounded and one as unbounded), you wouldn't have a
problem.  In fact for a 'secure' OS distro, for example, this is perfectly
reasonable.

So I guess the question is, is it really reasonable to mix bounded and
unbounded code in the same dynamic instance of a program?  I assume that
bounded pointers would still have to be *somewhat* efficient to maintain
their usefulness... and don't transitions (even if you knew where they
are) significantly effect this performance?

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/MagicStats/
http://www.nondot.org/~sabre/

RE: Esthetics (or worse?) of Secure Pointers

[Robert Bernecky]

We discussed name mangling, but discarded it.
Let me try to recall our
line of reasoning: You have just compiled foo, which calls
goo and hoo. Are the calls to goo and hoo bounded or not?

If you answer the question either way, you have a problem:
If bounded, then all functions down that call tree must be bounded,
because the calling sequences differ for bounded and non-bounded
pointers.
If not bounded, then the whole exercise is moot, as the
callees are not bounded either. The other choice is to require the
user to declare the boundedness of EVERY function in the compilation
unit. This is evil, as it entails non-portable source code changes
for what we hope is a temporary stage of affairs.

Now, let's refuse to answer the question of boundedness.
In that case, we have to deduce which glibc functions
to include (mangling in use), or pick an appropriate glibc (no
mangling). the whole compilation unit is either bounded or not.

The fundamental issue is this: if we want to intermix bounded
and non-bounded code, either the code says it explicitly
(bad -- non-portable), or the compiler has to figure it out
(good -- command-line option). But, how can the compiler
figure which kind of code to emit for a specific function call
for glibc? glibc may change long after the compilation is done,
just to make things more fun.

John  eventually convinced me that there's no way to decide
at compile time what a subfunction's boundedness is. Bummer.
This led us to the compile-the-whole-thing approach, which
we all find scary. Hence, this request for more brain cells.

Thunks almost work, but it  has the unsolved problem of identifying
bounded vs non-bounded pointers in a precise manner.

Bob


On Tue, 17 Apr 2001, Chris Lattner wrote:

>
> > We discarded the function-level intermixing as too low-level
> > and complicated in practice. This left us with larger approaches to
> > the problem of intermixing checked and non-checked code:
>
> Another alternative way to implement this (which would allow a single libc
> that contains both bounded pointer code and nonbounded pointer code to
> exist in the same library), would be to mangle function names, ala
> C++.  Of course you could do this really simply by simply prefixing all
> functions (C as well) with __BP_ or some such ugly thing.
>
> This isn't a wonderful solution from a cleanliness standpoint, but it
> would make it "impossible" to accidentally mismatch code.  It would also
> make it possible to have a library with both bounded pointer and
> nonbounded pointer code linked into it, which would be nice.
>
> -Chris
>
> http://www.nondot.org/~sabre/os/
> http://www.nondot.org/MagicStats/
> http://www.nondot.org/~sabre/
>

Robert Bernecky                  Snake Island Research Inc.
bernecky@acm.org                 18 Fifth Street, Ward's Island
+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com

RE: Esthetics (or worse?) of Secure Pointers

[Chris Lattner]

> We discarded the function-level intermixing as too low-level
> and complicated in practice. This left us with larger approaches to
> the problem of intermixing checked and non-checked code:

Another alternative way to implement this (which would allow a single libc
that contains both bounded pointer code and nonbounded pointer code to
exist in the same library), would be to mangle function names, ala
C++.  Of course you could do this really simply by simply prefixing all
functions (C as well) with __BP_ or some such ugly thing.

This isn't a wonderful solution from a cleanliness standpoint, but it
would make it "impossible" to accidentally mismatch code.  It would also
make it possible to have a library with both bounded pointer and
nonbounded pointer code linked into it, which would be nice.

-Chris

http://www.nondot.org/~sabre/os/
http://www.nondot.org/MagicStats/
http://www.nondot.org/~sabre/