(A) Better not to create files or folders with user-supplied names. If you do not validate enough, you can have trouble. Instead create files and folders with randomly generated names like fg3754jk3h and store the username and this file or folder name in a table named, say, user_objects. This will ensure that whatever the user may type, the command going to the shell will contain values from a specific set only and no mischief can be done.

(B) The same applies to commands executed based on an operation that the user chooses. Better not to allow any part of the user's input to go to the command that you will execute. Instead, keep a fixed set of commands and based on what the user has input, and run those only. 

For example,
(A) Keep a table named, say, user_objects with values like:
username|chosen_name   |actual_name|file_or_dir
--------|--------------|-----------|-----------
jdoe    |trekphotos    |m5fg767h67 |D
jdoe    |notes.txt     |nm4b6jh756 |F
tim1997 |_imp_ folder  |45jkh64j56 |D

and always use the actual_name in the filesystem operations rather than the user supplied names.

(B)
<?php
$op = $_POST['op'];//after a lot of validations 
$dir = $_POST['dirname'];//after a lot of validations or maybe you can use technique (A)
switch($op){
    case "cd":
        chdir($dir);
        break;
    case "rd":
        rmdir($dir);
        break;
    .....
    default:
        mail("[email protected]", "Mischief", $_SERVER['REMOTE_ADDR']." is probably attempting an attack.");
}

All of the fixes here assume that it is necessary to allow the user to enter system sensitive information to begin with. The proper way to handle this would be to provide something like a numbered list of files to perform an unlink action on and then the chooses the matching number. There is no way for the user to specify a clever attack circumventing whatever pattern matching filename exclusion syntax that you may have.

Anytime you have a security issue, the proper behaviour is to deny all then allow specific instances, not allow all and restrict. For the simple reason that you may not think of every possible restriction.

Well, the fact that all users run under the same UID is a big problem. Userspace  security hacks (ala safe_mode) should not be substitution for proper kernel level security checks/accounting.
Good news: Apache 2 allows you to assign UIDs for different vhosts.
devik

A basic filename/directory/symlink checking may be done (and I personally do) via realpath() ...

<?php

if (isset($_GET['file'])) {
    $base = '/home/polizei/public_html/';  // it seems this one is good to be realpath too.. meaning not a symlinked path..
    if (strpos($file = realpath($base.$_GET['file']), $base) === 0 && is_file($file)) {
        unlink($file);
    } else {
        die('blah!');
    }
}
?>

when using Apache you might consider a apache_lookup_uri on the path, to discover the real path, regardless of any directory trickery.
then, look at the prefix, and compare with a list of allowed prefixes.
for example, my source.php for my website includes:
if(isset($doc)) {
    $apacheres = apache_lookup_uri($doc);
    $really = realpath($apacheres->filename);
    if(substr($really, 0, strlen($DOCUMENT_ROOT)) == $DOCUMENT_ROOT) {
        if(is_file($really)) {
            show_source($really);
        }
    }
}
hope this helps
regards,
KAT44