segfault in SRFI-1 partition on non-list input

segfault in SRFI-1 partition on non-list input

[Julian Graham]

[-- Attachment #1: Type: text/plain, Size: 268 bytes --]

Hi,

It looks like scm_srfi1_partition in srfi/srfi-1.c fails to verify
that it's being called on a real list, and so expressions like:

(partition symbol? '(a b . c))

cause Guile to segfault.  Attached is a patch against HEAD that adds validation.


Regards,
Julian

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0003-fix-segfault-in-scm_srfi1_partition-on-non-list-inpu.patch --]
[-- Type: text/x-diff; name=0003-fix-segfault-in-scm_srfi1_partition-on-non-list-inpu.patch, Size: 1182 bytes --]

From 587b22534a40e16adee5f06e70f4d2b633142054 Mon Sep 17 00:00:00 2001
From: Julian Graham <julian@smokebottle.(none)>
Date: Mon, 28 Apr 2008 00:32:47 -0400
Subject: [PATCH] fix segfault in scm_srfi1_partition on non-list input

---
 srfi/ChangeLog |    5 +++++
 srfi/srfi-1.c  |    3 ++-
 2 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/srfi/ChangeLog b/srfi/ChangeLog
index 65ea3e9..eeedc30 100644
--- a/srfi/ChangeLog
+++ b/srfi/ChangeLog
@@ -1,3 +1,8 @@
+2008-04-28  Julian Graham  <joolean@gmail.com>
+
+	* srfi-1.c (scm_srfi1_partition): Validate input to avoid
+	segfault when passed something that is not a list.
+
 2008-04-27  Ludovic Courtès  <ludo@gnu.org>
 
 	* srfi-1.c: Include <config.h>.
diff --git a/srfi/srfi-1.c b/srfi/srfi-1.c
index 2989a25..5036acd 100644
--- a/srfi/srfi-1.c
+++ b/srfi/srfi-1.c
@@ -1673,7 +1673,8 @@ SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0,
   SCM dropped_tail = dropped;
   
   SCM_ASSERT(call, pred, 2, FUNC_NAME);
-  
+  SCM_VALIDATE_LIST (2, list);
+
   for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) {
     SCM elt = SCM_CAR(list);
     SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL);
-- 
1.5.4.3

Re: segfault in SRFI-1 partition on non-list input

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 688 bytes --]

Hi Julian,

"Julian Graham" <joolean@gmail.com> writes:

> It looks like scm_srfi1_partition in srfi/srfi-1.c fails to verify
> that it's being called on a real list, and so expressions like:
>
> (partition symbol? '(a b . c))
>
> cause Guile to segfault.  Attached is a patch against HEAD that adds validation.

> +  SCM_VALIDATE_LIST (2, list);

The probably is that `SCM_VALIDATE_LIST' uses `scm_ilength ()', which
attempts to traverse the list it's given.  Thus, it is undesirable to
use it here (and in many other places actually).

Instead, I propose the following patch, which doesn't add any list
traversal but doesn't catch circular lists.  What do you think?

Thanks,
Ludovic.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: The patch --]
[-- Type: text/x-patch, Size: 2051 bytes --]

diff --git a/srfi/srfi-1.c b/srfi/srfi-1.c
index 2989a25..0ce834a 100644
--- a/srfi/srfi-1.c
+++ b/srfi/srfi-1.c
@@ -1667,6 +1667,7 @@ SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0,
   /* In this implementation, the output lists don't share memory with
      list, because it's probably not worth the effort. */
   scm_t_trampoline_1 call = scm_trampoline_1(pred);
+  SCM orig_list = list;
   SCM kept = scm_cons(SCM_EOL, SCM_EOL);
   SCM kept_tail = kept;
   SCM dropped = scm_cons(SCM_EOL, SCM_EOL);
@@ -1675,8 +1676,15 @@ SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0,
   SCM_ASSERT(call, pred, 2, FUNC_NAME);
   
   for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) {
-    SCM elt = SCM_CAR(list);
-    SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL);
+    SCM elt, new_tail;
+
+    /* LIST must be a proper list.
+       XXX: This does not ensure that LIST is not a circular list.  */
+    SCM_ASSERT (scm_is_pair (list), orig_list, 2, FUNC_NAME);
+
+    elt = SCM_CAR (list);
+    new_tail = scm_cons (SCM_CAR (list), SCM_EOL);
+
     if (scm_is_true (call (pred, elt))) {
       SCM_SETCDR(kept_tail, new_tail);
       kept_tail = new_tail;
diff --git a/test-suite/tests/srfi-1.test b/test-suite/tests/srfi-1.test
index 22c4a9a..8fe8097 100644
--- a/test-suite/tests/srfi-1.test
+++ b/test-suite/tests/srfi-1.test
@@ -1,6 +1,6 @@
 ;;;; srfi-1.test --- Test suite for Guile's SRFI-1 functions. -*- scheme -*-
 ;;;;
-;;;; Copyright 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+;;;; Copyright 2003, 2004, 2005, 2006, 2008 Free Software Foundation, Inc.
 ;;;;
 ;;;; This program is free software; you can redistribute it and/or modify
 ;;;; it under the terms of the GNU General Public License as published by
@@ -2068,7 +2068,11 @@
 				   (make-list 10000 1)))
       (lambda (even odd)
 	(and (= (length odd) 10000)
-	     (= (length even) 0))))))
+	     (= (length even) 0)))))
+
+  (pass-if-exception "with improper list"
+    exception:wrong-type-arg
+    (partition symbol? '(a b . c))))
 
 ;;
 ;; partition!

Re: segfault in SRFI-1 partition on non-list input

[Ludovic Courtès]

ludo@gnu.org (Ludovic Courtès) writes:

> The probably is that `SCM_VALIDATE_LIST' uses `scm_ilength ()', which

This should read "The problem is..." (and I should go on vacation).

Ludo'.

Re: segfault in SRFI-1 partition on non-list input

[Julian Graham]

>  The probably is that `SCM_VALIDATE_LIST' uses `scm_ilength ()', which
>  attempts to traverse the list it's given.  Thus, it is undesirable to
>  use it here (and in many other places actually).
>
>  Instead, I propose the following patch, which doesn't add any list
>  traversal but doesn't catch circular lists.  What do you think?


Oh, yeah, that's fine -- sorry, didn't realize that was the behavior
of SCM_VALIDATE_LIST.  Just as long as it doesn't segfault any more,
I'm happy.


Regards,
Julian

Re: segfault in SRFI-1 partition on non-list input

[Ludovic Courtès]

Hi,

"Julian Graham" <joolean@gmail.com> writes:

> Oh, yeah, that's fine -- sorry, didn't realize that was the behavior
> of SCM_VALIDATE_LIST.  Just as long as it doesn't segfault any more,
> I'm happy.

Actually, there are many places where `SCM_VALIDATE_LIST' is used where
it should be avoided.  An example is SRFI-1's `member'.  Try the
following:

  (use-modules (srfi srfi-1)
               (ice-9 time))

  (define l (make-list 1000000 0))
  (time (not (not (member (car l) l))))

  ;; ... versus...

  (time (not (not (member 0 '(0)))))

Looking at SRFI-1 specifically, the spirit is apparently to phrase
things in a way that allows implementations to not actually check
whether arguments are proper lists when proper lists are expected (see,
e.g., [0, 1]).

Thanks,
Ludovic.

[0] http://srfi.schemers.org/srfi-1/mail-archive/msg00061.html

    "[I]t's unlikely that any implementation would ever enforce the
     proper-list typing of its list parameter."

[1] http://srfi.schemers.org/srfi-1/mail-archive/msg00054.html

Re: segfault in SRFI-1 partition on non-list input

[Julian Graham]

>  Looking at SRFI-1 specifically, the spirit is apparently to phrase
>  things in a way that allows implementations to not actually check
>  whether arguments are proper lists when proper lists are expected (see,
>  e.g., [0, 1]).

Great links -- I had no idea this was such a contentious topic!

Actually, though, what Olin Shivers says in the introduction to SRFI-1
is that specific parts of SRFI-1 should work (and are documented to
work) on dotted and / or circular lists in addition to proper lists.

Coincidentally, I noticed last night that Guile's implementation of
some of these parts is a bit buggy in this regard -- `take',
`take-right', `drop', and `drop-right' don't work on dotted lists.


Regards,
Julian

Re: segfault in SRFI-1 partition on non-list input

[Ludovic Courtès]

Hi Julian,

"Julian Graham" <joolean@gmail.com> writes:

> Great links -- I had no idea this was such a contentious topic!

Actually, R5RS `list?' itself must be used with care since it's O(N).

> Actually, though, what Olin Shivers says in the introduction to SRFI-1
> is that specific parts of SRFI-1 should work (and are documented to
> work) on dotted and / or circular lists in addition to proper lists.

Well, SRFI-1, under "Improper Lists", reads this:

  Most procedures are defined only on proper lists -- that is, finite,
  nil-terminated lists.  The procedures that will also handle circular
  or dotted lists are specifically marked.

> Coincidentally, I noticed last night that Guile's implementation of
> some of these parts is a bit buggy in this regard -- `take',
> `take-right', `drop', and `drop-right' don't work on dotted lists.

Indeed, the examples of SRFI-1 for `take' and `drop' with dotted lists
work fine, but those of `take-right' and `drop-right' don't.  Something
we should fix.

The reason is that these two procedures use `scm_list_tail ()', which is
apparently not supposed to work with dotted list.

I've just opened a bug: https://savannah.gnu.org/bugs/index.php?23112 .
Anyone is welcome to fix it!  ;-)

Thanks,
Ludovic.