How should I protect against relative paths in urls that try to access files outside of the served directories?

A number of different options;

1) Some sort of preg_replace expression to remove things like double-dots, the squiggly hyphen (I can't remember what there called but they look like ~), paths that start with a / etc.

2) Create a set of allowed URLs/paths that can be opened ether using reg-exps or in_array etc.

3) Enable PHP safe mode and set open_basedir or chroot PHP/Apache so they can't open any files outside of that tree

The only answer that is 100% secure against this type of attack is to never allow user input to touch commands that access the file system. Don't fopen($_GET['foo']), don't include($_POST['bar']), don't even mkdir($_COOKIE['baz']). Never. Period. No excuses.

If you must use user input to select a file from your file system, either use the user input in a database lookup (after sanitizing for the database query, of course, to defend against SQL injection), or run it through a switch statement; in both cases, you should be using hard- or soft-coded and known-safe values for the actual file names, never any variation of the user input itself.

Everything in $_POST, $_GET, $_COOKIES, $_REQUEST, and even $_FILES (except 'tmp_name' and 'error' -- yes, 'type' is user input!) is user input that you have precisely zero control over. So don't trust it, ever. Even some values in $SERVER (e.g. the 'HTTP*' values) are user input! Don't let any of these values anywhere near your file system, and don't let them anywhere near your database without escaping them first (e.g. mysql_real_escape_string()) or binding them to prepared statements (if you're using PDO).

Yes, you could sanitize the input, but what if you forget something? What if you forget that the tilde (~) character has special meaning on a *nix system? Or what if you do a perfect job sanitizing for your Linux web server, but then later move to a Windows one? Or what if something you never foresaw changes in your environment -- like a new special character? And so and and so forth. Safest option, most future-proof option, is to simply not let user input near your file system.

One thing to keep in mind, though, is that there are a lot of web apps out there that are vulnerable to the kinds of attacks you're seeing in your logs. This does not mean that anything on your server is, though: quite often script kiddies will just point their latest find at whatever servers they can find, without bothering to first find out if they're even possibly vulnerable. If you're not vulnerable, you have nothing to worry about from this background noise.

I would suggest to use chroot:

http://www.howtoforge.com/chrooting-apache2-mod-chroot-debian-etch

P.S: Sanitizing GET/POST/... parameters & input in general of course does help too ;)