From: =?ISO-8859-15?Q?Andr=E9_Thieme?=
Subject: Bufferoverflows in Lisp?
Date: 
Message-ID: <d75lri$m76$1@ulric.tng.de>
We can use declarations to speed up our Lisp applications. When using
these optimizations, could it then become possible to create security
holes in a program, so that it gets vulnerable to bufferoverflow attacks?


Andr�
-- 

From: Joel Ray Holveck
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <y7cll61fq3t.fsf@sindri.juniper.net>
> We can use declarations to speed up our Lisp applications. When using
> these optimizations, could it then become possible to create security
> holes in a program, so that it gets vulnerable to bufferoverflow attacks?

Sure.  Here's some examples.  These are written using LispWorks for
Linux 4.2.7.

The following code declares two simple arrays of fixnums, and hopes
they're near each other in heap.  It then sets elements of the first,
but past its boundaries as you'd typically see in a buffer overflow.

You can have it either change the type of the box that B is stored in,
or not.

(defun test-overflow (change-box)
  (declare (optimize (speed 5) (space 2)
                     (fixnum-safety 0) (safety 0) (debug 0)))
  (let ((a (make-array '(10) :element-type 'fixnum :initial-element 42))
        (b (make-array '(10) :element-type 'fixnum :initial-element 142)))
    (declare (type (simple-array fixnum (10)) a b))
    (when change-box
      (setf (aref a 12) 105))
    (loop
     for i fixnum from 18 to 23
     do (setf (aref a i) 105))
    (pprint (list a b (aref b 5)))
    (values)))

CL-USER> (compile 'test-overflow)
TEST-OVERFLOW
NIL
NIL
CL-USER> (test-overflow nil)
(#(42 42 42 42 42 42 42 42 42 42)
 #(142 142 105 105 105 105 105 105 142 142)
 105)
; No value
CL-USER> (test-overflow t)
(#(42 42 42 42 42 42 42 42 42 42) #<general box, tag 69 2068F374> 105)
; No value
CL-USER> 

In the last example, note that the tag-- 69-- is 105 in hex.

Usually, you see buffer overflows happen by statically copying a
string past the bounds of one array, into another.  Here's an example
of code to do that.  In my case, I ran it once to find out what was
between the two arrays, then again to have it change the second array
while preserving what was between them.

(defun test-string-overflow (new-string)
  (declare (optimize (speed 5) (space 2)
                     (fixnum-safety 0) (safety 0) (debug 0)))
  (let ((a (make-string 10 :element-type 'simple-char :initial-element #\a))
        (b (make-string 10 :element-type 'simple-char :initial-element #\b)))
    (declare (type (simple-string 10) a b))
    (if new-string
        (loop
         for i from 0
         for x across new-string
         do (setf (aref a i) x))
        (loop
         initially (princ "(")
         for i from 0 to 25
         do (prin1 (aref a i))
         do (princ " ")
         finally (princ ")")))
    (pprint (list a b))
    (values)))

CL-USER> (test-string-overflow nil)
(#\a #\a #\a #\a #\a #\a #\a #\a #\a #\a #\Null #\Null #\ETB #\(
 #\Null #\U+0102 #\U+0A00 #\Null #\U+0A00 #\Null #\b #\b #\b #\b #\b
 #\b )
("aaaaaaaaaa" "bbbbbbbbbb")
CL-USER> (test-string-overflow #(#\a #\a #\a #\a #\a #\a #\a #\a #\a
    #\a #\Null #\Null #\ETB #\( #\Null #\U+0102 #\U+0A00 #\Null #\U+0A00
    #\Null #\f #\o #\o #\b #\a #\r ))
("aaaaaaaaaa" "foobarbbbb")
CL-USER> 

The most common buffer overflow problem is stack overflow into the
return address.  I played around with trying to do that by using the
DYNAMIC-EXTENT declaration, but without result.  This is probably
because I'm generating the string with a call to MAKE-STRING, which is
most likely going to heap-allocate its return value anyway.  If I were
to pursue this line, I'd probably try using CMUCL, and see if I could
use &rest lists.

Another possible avenue of attack would be to overflow literals in the
code.  I'll talk about that in a future email.

The boundaries that I put in there were found with experimentation.
While experimenting, I recommend not using the IDE, since I blew up
the GC during the process and lost my (unsaved) work.  So now I'm
using SLIME.

Cheers,
joelh
From: Pascal Bourguignon
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <87sm09h7v8.fsf@thalassa.informatimago.com>
Andr� Thieme <······························@justmail.de> writes:
> We can use declarations to speed up our Lisp applications. When using
> these optimizations, could it then become possible to create security
> holes in a program, so that it gets vulnerable to bufferoverflow attacks?

In some implementations, yes.

I would not use these implementations, or these declarations...


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
From: =?ISO-8859-15?Q?Andr=E9_Thieme?=
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <d75o6t$o7m$2@ulric.tng.de>
Pascal Bourguignon schrieb:
> Andr� Thieme <······························@justmail.de> writes:
> 
>>We can use declarations to speed up our Lisp applications. When using
>>these optimizations, could it then become possible to create security
>>holes in a program, so that it gets vulnerable to bufferoverflow attacks?
> 
> 
> In some implementations, yes.
> 
> I would not use these implementations, or these declarations...

Can you be more specific in what implementations it is possible?

I assume there are implementations from which it is known that it is
*not* possible to create bufferoverflows through declarations and some
implementations where it is not certain yet. Can you tell me more
about these too?


Andr�
-- 
From: Kent M Pitman
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <uy8a12syn.fsf@nhplace.com>
Andr� Thieme <······························@justmail.de> writes:

> Pascal Bourguignon schrieb:
> > Andr� Thieme <······························@justmail.de> writes:
> >
> >>We can use declarations to speed up our Lisp applications. When using
> >>these optimizations, could it then become possible to create security
> >>holes in a program, so that it gets vulnerable to bufferoverflow attacks?
> > In some implementations, yes.
> > I would not use these implementations, or these declarations...
> 
> Can you be more specific in what implementations it is possible?
> 
> I assume there are implementations from which it is known that it is
> *not* possible to create bufferoverflows through declarations and some
> implementations where it is not certain yet. Can you tell me more
> about these too?

It's not as binary as this.

Implementations differ as to what happens at the different safety levels,
including whether the safety levels are dealt with as absolutes, relatives,
or both.

That is, in some implementations, you get rules that say 
 "if speed exceeds safety, then do x"
while in others you get rules that say
 "if safety is [more than/equal to/less than] n, then do x"

If memory serves me correctly, LispWorks turns off all manner of checks,
including checks for stack overflow, if you set SAFETY to 0.  (I would
personally NEVER run at that level except in very tightly controlled and
heavily tested lexical contours.)  But that doesn't mean you have to worry
at other safety levels.

So implementations aren't either checking or non-checking.  A lot depends
on what you ask of them and whether what you assume is based on actually
inquiring of their doc or their implementors, or whether you just dreamed
up stuff you wish they did on your own and hoped that wishing would make
your dreams come true.
From: Steven M. Haflich
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <9npoe.2115$IE7.2035@newssvr21.news.prodigy.com>
Pascal Bourguignon wrote:
> Andr� Thieme <······························@justmail.de> writes:
> 
>>We can use declarations to speed up our Lisp applications. When using
>>these optimizations, could it then become possible to create security
>>holes in a program, so that it gets vulnerable to bufferoverflow attacks?
> 
> 
> In some implementations, yes.
> 
> I would not use these implementations, or these declarations...

Pascal's postings usually exhibit better sense.  Here is a
more-realistic view on the issue.

Common Lisp, as defined by the ANS, is rather more secure than many
other languages against buffer overflow attacks.  However, optimization
settings (aka "unsafe" code) eliminates these safeties.  Unfortunately,
competitive performance against "unsafe" languages requires often
requires bypassing safety.  How to resolve this dilemma?

It turns out that most time-critical applications spend most of their
time in a trivially-small portion of their total code.  Many CL
implementations have tools for identifying these small portions of
code.

In my experience (40 years in Lisp) a programmer should write code that
is safe, and only then should identify the small critical sections of
code responsible for significant runtime, and _carefully_ hand optimize
them.

This doesn't _guarantee_ safe attack-proof execution, but given the
current state of the art, is the practical approach to implementing
reliable, robust, and safe web services.  It is a better approach than
what I have seen offered by other languages.  Other languages can
provide efficient execution, or safe execution (sort of), but not
both.  That still requires human intervention.

Someday programmig will no longer require human intervention.  But
them my and your opinions will be irrelavant.
From: Paul F. Dietz
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <4fOdnaMN8v1s0z_fRVn-sg@dls.net>
Steven M. Haflich wrote:

> Common Lisp, as defined by the ANS, is rather more secure than many
> other languages against buffer overflow attacks.  However, optimization
> settings (aka "unsafe" code) eliminates these safeties.  Unfortunately,
> competitive performance against "unsafe" languages requires often
> requires bypassing safety.  How to resolve this dilemma?

There are many operators in CLtS that are not guaranteed to be 'safe',
even in safe code.  AREF, for example.

I'm adding some tests in the same directory tree as the gcl ansi-tests
to test some of these situations, but of course they cannot be ANSI tests
themselves.

I think plugging these holes should be high on the list of priorities
if the Common Lisp standardization process is ever revived.

	Paul
From: =?ISO-8859-15?Q?Andr=E9_Thieme?=
Subject: Re: Bufferoverflows in Lisp?
Date: 
Message-ID: <d7t95q$ag1$1@ulric.tng.de>
Steven M. Haflich schrieb:
> Pascal Bourguignon wrote:
> 
>> Andr� Thieme <······························@justmail.de> writes:
>>
>>> We can use declarations to speed up our Lisp applications. When using
>>> these optimizations, could it then become possible to create security
>>> holes in a program, so that it gets vulnerable to bufferoverflow 
>>> attacks?
>>
>>
>>
>> In some implementations, yes.
>>
>> I would not use these implementations, or these declarations...
> 
> 
> Pascal's postings usually exhibit better sense.  Here is a
> more-realistic view on the issue.
> 
> Common Lisp, as defined by the ANS, is rather more secure than many
> other languages against buffer overflow attacks.  However, optimization
> settings (aka "unsafe" code) eliminates these safeties.  Unfortunately,
> competitive performance against "unsafe" languages requires often
> requires bypassing safety.  How to resolve this dilemma?
> 
> It turns out that most time-critical applications spend most of their
> time in a trivially-small portion of their total code.  Many CL
> implementations have tools for identifying these small portions of
> code.

Yes, and I found them until now very intuitive to use.


> In my experience (40 years in Lisp) a programmer should write code that
> is safe, and only then should identify the small critical sections of
> code responsible for significant runtime, and _carefully_ hand optimize
> them.

Does this mean that in the end only XY percent (lets say 3%) of the code
should contain declarations?


> This doesn't _guarantee_ safe attack-proof execution, but given the
> current state of the art, is the practical approach to implementing
> reliable, robust, and safe web services.  It is a better approach than
> what I have seen offered by other languages.  Other languages can
> provide efficient execution, or safe execution (sort of), but not
> both.  That still requires human intervention.

Have deep experience with Lisp - how many bufferoverflows in Lisp
applications have you seen so far?


> Someday programmig will no longer require human intervention.  But
> them my and your opinions will be irrelavant.

I would love to be still around at that time. :)
Do you have any visions how that would look like?


Andr�
-- 
From: Adam Warner
Subject: Re: Buffer overflows in Lisp?
Date: 
Message-ID: <pan.2005.05.27.02.55.49.782648@consulting.net.nz>
On Fri, 27 May 2005 01:26:04 +0200, André Thieme wrote:
> We can use declarations to speed up our Lisp applications. When using
> these optimizations, could it then become possible to create security
> holes in a program, so that it gets vulnerable to buffer overflow
> attacks?

Here's a very simple and relatively portable example using displaced
arrays:

;;(declaim (optimize (safety 0)))

(defparameter *vector* (make-array 4 :initial-element nil))
(defparameter *buffer* (make-array 3 :displaced-to *vector*))

(setf *read-eval* nil)

(let ((percent 0))
  (defun format-root ()
    (cond ((zerop percent) (format t "Formatting root filesystem "))
          ((= percent 100) (error "Format complete"))
          (t (dotimes (i 5) (format t ".") (force-output) (sleep 0.1))
             (format t " ~A% " percent)))
    (force-output) (incf percent)))

(defun accept-input ()
  (format t "Input buffer index between 0 and 2 and a value~%")
  (let ((index (read)) (value (read)))
    (setf (aref *buffer* index) value)
    (format t "Buffer is ~S~%" *buffer*)))

(setf (aref *vector* 3) #'accept-input)
(loop (funcall (aref *vector* 3)))


Let's run the program in a typical Lisp at default optimisation settings:

$ sbcl
This is SBCL 0.9.0.19, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (load "buffer")
Input buffer index between 0 and 2 and a value
0 abc
Buffer is #(ABC NIL NIL)
Input buffer index between 0 and 2 and a value
2 567
Buffer is #(ABC NIL 567)
Input buffer index between 0 and 2 and a value
3 format-root

debugger invoked on a SIMPLE-TYPE-ERROR in thread 2512:
  invalid array index 3 for #(ABC NIL 567) (should be nonnegative and <3)

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

(ACCEPT-INPUT)
0]

You can see that the attempt to overwrite the end of the array named
*buffer* was thwarted by a run time check.

Now uncomment the line ;;(declaim (optimize (safety 0))) and run the
program again:

* (load "buffer")
STYLE-WARNING: redefining FORMAT-ROOT in DEFUN
STYLE-WARNING: redefining ACCEPT-INPUT in DEFUN
Input buffer index between 0 and 2 and a value
0 abc
Buffer is #(ABC NIL NIL)
Input buffer index between 0 and 2 and a value
2 567
Buffer is #(ABC NIL 567)
Input buffer index between 0 and 2 and a value
3 format-root
Buffer is #(ABC NIL 567)
Formatting root filesystem ..... 1% ..... 2% ..... [...] ..... 99%
debugger invoked on a SIMPLE-ERROR in thread 2520: Format complete

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

(FORMAT-ROOT)
0]

The input data is never explicitly evaluated. Yet I am able to overflow
*buffer* with the name of a new function that the input loop happily
evaluates.

I expect the fastest Lisp implementations to work this way.

CLISP is immune to this array overflow. ABCL (an ANSI Common Lisp running
on top of the Java Virtual Machine) currently permits this array overflow
at all levels of safety.

Regards,
Adam
From: Adam Warner
Subject: Re: Buffer overflows in Lisp?
Date: 
Message-ID: <pan.2005.05.27.22.27.29.679347@consulting.net.nz>
On Fri, 27 May 2005 14:55:55 +1200, Adam Warner wrote:

> CLISP is immune to this array overflow. ABCL (an ANSI Common Lisp
> running on top of the Java Virtual Machine) currently permits this array
> overflow at all levels of safety.

ABCL is now also immune to displaced array overflows:
<http://article.gmane.org/gmane.editors.j.devel/880>

Regards,
Adam