The trouble with symbolic links

For security, symlinks pose no "direct" problem, they are simple "look there instead" pointers that comes from a user thus is user provided data, should be input-validated when used and also resides in user space only.

The problem starts when higher privileged accounts use user data to do tasks with higher privileges. I.e. when an admin is archiving (or restoring) user homes, syncing them from one Server to another (i.e. rsync).
Or when a build-process (in one user account) uses another users data tree to act on it.
Then TOCTOU becomes interesting.

A few possible solutions:

In nearly all cases (i believe) either the root job/cronjob should have been run under lesser privileges or should have been splitted into two phases like:
- archive/restore only the user home folders (/home/*) but NOT their contents as at that directory level root privileges are needed to create the folders with their owners/permissions and
- use separated archives per home folder and archive/restore them from within user space (sudo -u $user tar -xf $archive)

Then the root task would not need symlink checking of user input as the restore task runs with user permissions only.

The build process for example should not be able to write it's own config/scripts, so that a toctou attack could only alter the data actually used for the build which could be checked after a recursive copy into the build-process user space.

Another way to prevent TOCTOU when reading (as root) user provided data (that resides in symlinks) would be to use immutable flag on the directories in the tree during the root task. The user himself cannot set the flag, so the admin already knows when this flag is set somewhere (and needs to stay) or otherwise can set it blindly and just remove it afterwards. Symlinks cannot be set immutable, but setting the directory immutable removes the users ability to remove or alter the symlinks or directories there, so after setting immutable flags to directories in user tree, the admin can once recheck, that all directories have the flag and then has no TOCTOU problems with directory/symlink changes until he removes the flags again after finishing the task. Maybe the user could still use fuse to overmount directories in is space, but the thread is about symlinks. (To prevent collusion with user scripts or cronjobs, flock could help)

Using chroot could also be used to solve the "overwriting /etc/passwd" risk.

Yet another way:
SElinux provides a way to allow a script to have root privileges (as in setting the owner of arbritary files) while by design it needs a "whitelist" which group of files /dirs (sockets .. etc) it is allowed to modify (and how exactly), before it can do so. A process that can write to home_t or samba_share_t (which i assume often needs chown privileges) would not be able to write to etc_t. Instead of getting tricked by the user with changing symlinks to write to /etc/passwd it would create an audit record of this attack vector for beeing used (and prevented).
On the other hand, the cronjob that runs as root would also not need to read shadow_t and (as it is not whitelisted) could also not leak data on beeing tricked by TOCTOU attacks.

Symlinks are not a problem here, administration with only(!) multi-decades old security mechanisms, actually is. There is a reason for SELinux to exist and there are hundreds (or more) of reasons to use it. =)
Other than by preventing symbolic links from beeing used to trick some other process by entirely removing the whole symlink mechanism, selinux prevents all not whitelisted accesses on a syscall level AND also reports the already prevented attack.