C function malloc provides a memory block with indeterminate values (which depend on the previous user of this memory block)

Correct.

Shared VPS hostings share resources such as RAM and CPU

Do they use the same Physical CPU and RAM as the other VPS, yes.

Would be possible to exploit this fact to create a C program which would repeatedly malloc and free memory and log found memory values...

That's complicated.

You're forgetting about an extra layer, and layers create abstraction. The V in VPS obviously stands for Virtual, but to create something Virtual, we need technology to Virtualize.

In simple words, Virtualization divides your physical hardware into smaller parts that can be used by virtual machines, this is done by the Hypervisor, which uses exposed Kernel functions to expose the hardware it has reserved to the VM.

If it is possible, how can we prevent it from happening?

It is possible if a bug exists in the hypervisor to escape from the Virtual borders it has set up for your VPS.

Simple examples like your malloc() have been used before by other processes to escape a low privileged user account on Linux. This is basically what that is, but more complex, if you can escape from your VM, you'll be your Hypervisor's user and thus have access to anything that's in the other VPS hosted on the same hypervisor.

We can prevent this by doing what we do, hunting these bugs before the bad guys find them!

C function malloc provides a memory block with indeterminate values (which depend on the previous user of this memory block)

Correct.

Shared VPS hostings share resources such as RAM and CPU

Do they use the same Physical CPU and RAM as the other VPS, yes.

Would be possible to exploit this fact to create a C program which would repeatedly malloc and free memory and log found memory values...

That's complicated.

You're forgetting about an extra layer, and layers create abstraction. The V in VPS obviously stands for Virtual, but to create something Virtual, we need technology to Virtualize.

In simple words, Virtualization divides your physical hardware into smaller parts that can be used by virtual machines, this is done by the Hypervisor, which uses exposed Kernel functions to expose the hardware it has reserved to the VM.

If it is not possible, why not?

It is possible if a bug exists in the hypervisor to escape from the Virtual borders it has set up for your VPS.

Simple examples like your malloc() have been used before by other processes to escape a low privileged user accounts on Linux.

This is basically what that is, but more complex, if you can escape from your VM, you'll be your Hypervisor's user and thus have access to anything that's in the other VPS hosted on the same hypervisor.

If it is possible, how can we prevent it from happening?

As an end user, there isn't much you can do, except keep an eye on websites like packetstorm and cvedetails to keep an eye for vulnerable services.

A silly example are the recent attacks on CPU architectures that allowed access to protected memory amongst other things. If someone executes that kind of attack on a VPS you're on, they can access the RAM your VPS is using as well.

The only thing you can do is wait for a patch and change all your sensitive information (passwords, keys,...) afterwards, as they may have been in memory and can be compromized.