execstack program can be used to mark ELF-binaries as needing an executable stack.
Is there a similar way to mark the heap as executable? Preferably for a single binary but if that's not possible, a system-wide solution would be useful too.
Setting an executable stack (or setting a non-executable stack) made no difference on any version of Linux I tried it on (2.6.9 on x86_64, 2.4.21 on x86_64, 22.214.171.124 x86, 3.1.4 x86). I don't have access to Solaris or *BSD machines at the moment. I'm guessing that the kernels in question aren't compiled to disallow execution of code "on the stack". See this wikipedia article, which says either a patch or a compile option is necessary.
I have written a C program that runs in malloc-ed memory. It works on all the same kernels and architecutres I mentioned above. I doubt you will find a specific tool like execstack to mark an executable file as "heap executable". About the best I could tell you is that you'll have to use the