I'm trying to track down this strange behavoir for years now.

Always after installing software-updates the permissions of a lot of system-tools are broken as you can see below. I am reasonable convinced that the machine is not owned by someone else. Regular security updates + grsecurity kernel + pax + daily rkhunter runs. Besides that there is no incentive for an attacker to fiddle in such obvious ways with the system.

I installed bastille linux (http://bastille-linux.sourceforge.net/) und tried to deinstall it later, so the problems could be related to that. However I don't see how this can happen in a regular way after updates.

System: Ubuntu 10.04, recently updated to Ubuntu 12.04 but the problem persists.

Apt-Configuration in /etc/apt/ looks sane to me. But nevertheless - could here be the source of the trouble?

DPkg::Pre-Install-Pkgs {"/usr/sbin/dpkg-preconfigure --apt || true";};
DPkg::Post-Invoke { "if [ -x /usr/bin/debsums ]; then /usr/bin/debsums --
generate=nocheck -sp /var/cache/apt/archives; fi"; };
// Makes sure that rkhunter file properties database is updated 
// after each remove or install only APT_AUTOGEN is enabled
DPkg::Post-Invoke { "if [ -x /usr/bin/rkhunter ] && grep -qiE '^APT_AUTOGEN=.? 
(true|yes)' /etc/default/rkhunter;
then /usr/share/rkhunter/scripts/rkhupd.sh; fi" }
DPkg::Post-Invoke {"if [ -d /var/lib/update-notifier ]; 
then touch /var/lib/update-    notifier/dpkg-run-stamp; fi; 
if [ -e /var/lib/update-notifier/updates-available ];
then echo > /var/lib/update-notifier/updates-available; fi "; };

Where do these chmod 000 come from? I'm feeling really uneasy with this problem.

root@besen:~# find /usr/bin/ -perm 0 -ls
14721496  196 ----------   1 root     root       192592 Oct 15 11:58 /usr/bin/apt-get
14721144   68 ----------   1 root     root        63848 Sep 13 00:29 /usr/bin/gpasswd
root@besen:~# find /usr/sbin/ -perm 0 -ls
1727732   92 ----------   1 root     root        86984 Sep 13 00:29 /usr/sbin/usermod
1727727   64 ----------   1 root     root        57640 Sep 13 00:29 /usr/sbin/userdel
1727719   64 ----------   1 root     root        57680 Sep 13 00:29 /usr/sbin/newusers
1727718   40 ----------   1 root     root        38632 Sep 13 00:29 /usr/sbin/grpunconv
1727728   48 ----------   1 root     root        47088 Sep 13 00:29 /usr/sbin/groupadd
1727724   32 ----------   1 root     root        29584 Sep 13 00:29 /usr/sbin/pwunconv
19031620   84 ----------   1 root     root        81880 Jan  3  2012 /usr/sbin/edquota
14877113   48 ----------   1 root     root        46880 Sep 13 00:29 /usr/sbin/grpck
1727722   40 ----------   1 root     root        38632 Sep 13 00:29 /usr/sbin/pwck
1727730   96 ----------   1 root     root        91464 Sep 13 00:29 /usr/sbin/useradd
19031619   16 ----------   1 root     root        14600 Jan  3  2012     /usr/sbin/quotastats
1727720   44 ----------   1 root     root        42760 Sep 13 00:29 /usr/sbin/groupdel
1727733   36 ----------   1 root     root        34504 Sep 13 00:29 /usr/sbin/pwconv
19031621   80 ----------   1 root     root        77632 Jan  3  2012    /usr/sbin/rpc.rquotad
19030041   76 ----------   1 root     root        73600 Jan  3  2012 /usr/sbin/repquota
1727731   40 ----------   1 root     root        38624 Sep 13 00:29 /usr/sbin/grpconv
1727725   56 ----------   1 root     root        49472 Sep 13 00:29 /usr/sbin/vipw
1727723   64 ----------   1 root     root        57672 Sep 13 00:29 /usr/sbin/groupmod
root@besen:~# find /sbin/ -perm 0 -ls
16760927   76 ----------   1 root     root        73464 Jan  3  2012 /sbin/quotaon

Any tipps? I really can't pinpoint the problem in more detail. It happens after installing updates but I can't find no hooks in the dpkg/apt system.