How effective is ASLR in preventing arbitrary code execution in a buffer overflow type exploit? How hard is it for an attacker to bypass this without simply guessing where the addresses are?
ASLR is a defense-in-depth mechanism. It is effective, but can be bypassed (the 2010 PWN2OWN contest break included an ASLR bypass).
ASLR's primary purpose is to defeat "ret-to-libc" attacks which are a mechanism of bypassing DEP. IMHO ASLR is only really effective when bundled with other protection mechanisms like DEP (ASLR without DEP can typically be trivially bypassed).
Mark Dowd and Alex Sotirov - Black Hat 2008 are the experts on defeating ASLR.
Alex Sotirov and I are presenting at BlackHat USA today on bypassing the Windows Vista memory protections in the context of the web browser in a speech titled “How to Impress Girls with Browser Memory Protection Bypasses”. Specifically, we will be discussing how rich browser functionality can be utilized to help lessen the impact of memory protections (and in some cases, completely negate them). Some of the techniques we will be discussing are known ones, whereas others are new approaches that we haven’t seen discussed in public forums before.