CODEWITHSUNDEEP
crandommalloc
joelsa
joelsa

Reputation: 65

What is the randomness of the return value of the malloc function?

I found this code snippet in an old and dusty project:

int *p = (int*)malloc(sizeof(p));           // generate random number
free(p);                                    // free up space
int rand = p%3;                             // get random value in between 0-2

Apart from it being bad style and unnecessary as we got srand in the C standard lib, what is the actual randomness of the return value?

While true randomness is not needed in the context it is used, I tested it several times for 99999999 iterations each and for every single test run rand == 0 was less often true than both other cases (rand == 1 and rand == 2).

One example:

Upvotes: 1

Views: 1225

Answers (1)

Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'

Reputation: 107829

This is a really silly way of getting a random number. Its behavior is extremely dependent on the platform and on what else the application code is doing. For example, if you call it in a loop with no other memory allocation going on, then on many systems malloc will keep returning the same block over and over because free returns it to the front of the free list, so p will be the same each time. On many others, you'll get a cycle eventually as the heap grows to a certain size and then the allocator cycles through a number of slots.

This particular possibility is evidently what's happening in your experiment: you get rand==0 in 70/256 cases and rand==1 and rand==2 in 93/256 cases (apart, presumably, from the first few allocations where the cycle has not been reached yet and the last, partial cycle). I'm not familiar enough with malloc implementations to explain this particular distribution; possibly the control structures used by malloc have a size that's a multiple of 3 which would create a bias modulo 3.

Modulo a power of 2, you'd get a bias on every realistic platform as the return values are guaranteed to be correctly aligned for any type and most platforms have alignment constraints on powers of 2. Or, in other words, a few of the lowest-order bits of p are always 0.

rand is standard C and, bad as it is on most platforms (don't even think of using it for anything related to security, and even for probabilistic algorithms it often isn't good enough), it would rarely be worse than malloc output.

There are probably a few platforms out there where the return value of malloc is randomized to make exploitation of bugs such as buffer overflows and use-after-free harder (because the attacker can't predict where interesting objects will be, in the same vein as ASLR), but such platforms would have a better random generator API anyway.

Upvotes: 2

Related Questions