You'd probably want more than just setuid files as immutable.  On my
system, the following are immutable :
-all of /bin
-all of /usr/bin
-all of /sbin
-all of /usr/sbin
-all of /usr/lib
-everything called from inetd 
-everything called from the rc files
-all rc files and inetd.conf
-/usr/X11R6/bin
-/usr/X11R6/lib

Making all of /bin, /usr/bin, etc immutable probably isn't critical;
however, you will need more than just the setuid files immutable.  (I
did it all on my system since it doesn't change much).
Anything called as root must be immutable, especially if it's called
from the rc files before the system switches to secure level 1 (or 2).
Otherwise, someone could alter the file and reboot the machine so the
altered program could unmark immutable files and change them before the
system is in secure mode.

Alex Rolfe
arolfe@mit.edu

 > scanning my 1.3.3-system I noted that the SF_IMMUTABLE bit is not set on any
 > security relevant files (like /usr/bin/login or /usr/bin/su). Setting this b
    it
 > would greatly enhance system security as hackers could not stealthly modify
 > these files when the system runs at securelevel > 0.
 > I'd like to suggest to set the SF_IMMUTABLE bit on all security relevant fil
    es
 > (I have all setuid files in mind) and the SF_APPEND bit on critical system l
    og
 > files.