After reading through a page on memory protection changes in Windows XP SP2, I e-mailed Microsoft's Technical Support for XP SP2 and requested confirmation on my understanding of the product. This resulted in a support contact sending me a link to a detailed description of DEP. The given page doesn't conflict with or add to my understanding of DEP, so I assume I have a fair grasp on how it works.
DEP provides fairly basic memory protections, similar to the anciet POSIX memory protections established probably (guess?) in the 1970s-1980s, when UNIX was invented. Microsoft just caught up to 30 year old technology; although the Virtual*() functions have always been defined as if they actually work. Still, POSIX systems have always run on platforms with NX capabilities, such as SPARC.
No emulation of an NX bit is done by Windows at all. Back in 2000, the plex86 developers pointed out a curious situation in which an NX bit could be emulated on a standard 32 bit x86 CPU. This method would be slow and complex, involving using the separated ITLB/DTLB logic to allow the OS to control which pages could be used for instructions and which could be used for data.
The PaX Team implemented the plex86 suggestion as a proof of concept by October of the same year; then later enhanced the implementation, and went on to create a new method which was much faster. Later, in 2003, OpenBSD released W^X, and Ingo Molnar of Red Hat released Exec Shield. These use a much simpler and faster, but inaccurate, method of NX emulation which sometimes loses protections.
Microsoft has made no advancement with DEP in this sense. The functionality DEP proports to supply already exists in all versions of Windows. The only difference is that newer processors supply an NX bit for Windows to use. There are numerous ways in which Microsoft could have emulated or partially emulated an NX bit for older CPUs.
DEP does not protect against unsafe VirtualProtect() usage. Restrictions can be controlled per program with DEP, but this restriction doesn't exist. It makes sense to allow memory to be made X|W for some programs like JIT compilers and realtime CPU emulators; but most of them shouldn't need that functionality.
PaX is the only system right now which supplies mprotect() restrictions. These restrictions prevent any memory from being marked Writable and eXecutable at the same time. They also prevent any memory from transitioning from -X to +X; executable memory must be created +X against a file resource containing executable code.
The concept of least privileges is at the heart of any security setting, so this restriction deserves some consideration. Certain attacks do not need to inject code. They can instead alter the program so that it naturally goes to existing code. These alterations could include using VirtualProtect() or mprotect() to make the stack executable, followed by a return to code on the stack.
This sequence could be done by overflowing a buffer with a large amount of data, including an overwrite of the return pointer and stackframe pointer to call a VirtualProtect() or mprotect() function; a stack frame for the function; and executable code. This would allow successful evasion of DEP in one step by making the injected code executable in the same pass.
DEP has no Address Space Layout Randomization. With ASLR, the address of the VirtualProtect() functions is different for every run of the same program. This helps to prevent the above described attack and any other attack relying on executing existing code, unless information about the address space can be leaked to the attacker during the attack.
PaX provides ASLR for the stack, heap, any mmap() base including PIC/PIE executables and libraries, and optionally for non-PIC executables. Basically everything is placed randomly and has to be located by reading the Global Offset Table. The GOT is stored in a register, so it can't be examined by classical format string bugs. There are also patches, such as the one included with GrSecurity, to prevent the leaking of the address space layout.
Exec Shield and W^X also supply limited ASLR. While the mprotect() function can still be abused in the way described above, an attacker will have to take a blind guess at where that function lies. Note that local access to an Exec Shield protected Linux system still allows address space information to be leaked through /proc/[pid]/maps unless an obscurity patch like the one in GrSecurity is used.
Software DEP and SafeSEH don't look too usful. It appears that Microsoft is trying to prevent people from changing exception handlers; however, replacing an exception and triggering it is a more complex attack than simply using one-step return-to-VirtualProtect()/code injection sequences, which only require one overflow. ASLR would probably protect against this too anyway. It is important to note, however, that I'm not quite sure what problem SafeSEH was trying to solve.
When I started, I intended to give DEP a good review. Proper use of the NX bit is a great step forward in security, especially in advanced implementations such as PaX. However, by giving DEP closer examination, I have noticed that it's theoretically very simple to simply evade DEP in a single step. This won't stop any half-serious blackhat cracker. 100% of attacks where some other system (like Stack Smash Protection) doesn't stop the attack should be possible in one slightly modified step.