Algorithms/Techniques for procedural map generation (with caves) and deformation

Hello,

I'm building a procedural world generator. By now I already generate the mesh and have a random generated world using Perlin Noise.

I want to the player be able to deform the world in the game, not only by height, but creating caves for example. I am wondering how can I do that?
With the 2D height map (a matrix, which is what I have) I can't have a cave for example. How can I add caves?
Which algorithms/technics exists for that?

Thanks and Best rewards,
David

 

I would look into 3D perlin / simplex noise, and the Marching Cubes algorithm.