Lo unico que pruebas, al menos con el programa de test que pusiste previamente, es que la funcion rand() tiene un comportamiento como el que esperas, o sea, que 1 de cada 100 elementos sea elegido, pero esto no implica que 1 de cada 100 elementos tu eligiras de los primeros 100 bits.  

Si le dieras a la funcion rand() los 100 primeros elementos, esta elegiria solo 1 de alli, pero tu no haces esto, le dices a la funcion rand() que eliga uno por uno, cada bit, con probabilidad 1/100. Con ello, tu programa podria elegir varios bits en el camino, y es esto efectivamente lo que ocurre. Varias veces rand() elige alguno de los bits. Aunque rand() este bien, eso no implica que cualquier uso de rand() hara que los resultados esten correctos. No importa cuantas veces lo ejecutes.

El no generar elecciones ya hechas se puede resolver, por ejemplo, manteniendo lo disponible. En vez de guardar lo elegido y comparar si ya ha sido elegido antes., por ejemplo asi:

int noise(char * data_stream, int len_data, unsigned char cuantos, unsigned char valor) {
  int index;
  int bit;
  int cantidad_bits = len_data * 8;
 
  int disponible[100];
 
  for (int offset = 0; offset < cantidad_bits; offset += 100) {
    for (int i = 0; i < 100; i++) disponible[i] = i;
    for (int bits_modificados = 0; bits_modificados < cuantos; bits_modificados++) {
      int r = rand() % (100 - bits_modificados);
      int bit_offset = disponible[r] + offset;
      disponible[r] = disponible[99 - bits_modificados];
 
      if (bit_offset >= cantidad_bits) {
        continue;
      }
      index = bit_offset / 8;
      bit = bit_offset % 8;
      if (valor) {
        data_stream[index] |= 1 << bit;
      } else {
        data_stream[index] &= ~(1 << bit);
      }
    }
  }
}
 

free libera la memoria, delete es mas poderoso, pues si se trata de un puntero a un objeto, invoca al destructor del mismo (y libera la memoria despues).

La combinacion alloc (o malloc) y free, no se intercambia con new y delete, si solicitaste memoria con new, libera con delete, si pediste con alloc (o alguno de sus parientes), liberas con free.

Estoy de acuerdo que la cuenta se puede mejorar, lo indique también en el comentario que acompaña. Gracias!

La manera de probar que el codigo original es cercano a lo que se pide no esta bien.
El test solo muestra que la funcion de probabilidad te sirve, no que su uso esta bien,

Recuerda que tienes que modificar a lo mas <cuantos> bits por cada 100 de ellos.
Esto no te lo da la solucion propuesta, porque usas la probabilidad en tamanos distintos de 100 (aunque usas el 100 para controlar si aplicar el cambio o no al bit visitado), por lo que es bien posible que se modifiquen mas que <cuantos> bits, como te ocurre. Contabilizar los cambios para corregir esto solamente va a tener bias favoreciendo a los primeros cambios.

Si modificas tu funcion noise original, para avanzar a traves del conjunto de caracteres cada 100 bits, aun usando la funcion de probabilidad, tu resultado sera mas cercano al correcto, nunca modificando mas de los bits que son necesarios.

Mucha teoria, lo que indico, usando parte de lo que enviaste, corrigiendo de acuerdo a lo que propongo.

int noise(char *data_stream,int len_data,unsigned char cuantos, unsigned char valor)	{
	int index;
	int bit;
	int offset;
	int bit_offset;
	int bits_modificados;
	int cantidad_bits = len_data * 8;
 
	for(int offset = 0; offset < cantidad_bits; offset += 100)	{
    	for( bits_modificados = cuantos; bits_modificados > 0; bits_modificados--) {
	     	bit_offset = rand() % 100 + offset;
     		if( bit_offset > cantidad_bits) {
	     	    continue;
		}
    		index = bit_offset / 8;
	    	bit = bit_offset % 8;
	    	if(valor) {
		   data_stream[index] |= 1 << bit;
		} else {
                    data_stream[index] &= ~(1 << bit);
		}
    	   }
	}
}

Lo pruebas asi:

#define LARGO 100 // 1 cambio cada 100 bits seran 8 cambios en total (a lo mas).
 
int main()	{
	srand(time(NULL));
	char data[LARGO+1] = {0};
	for( int test = 0; test < 100; test++ ) {
           memset(data,0,LARGO);
	   noise(data,LARGO,1,1);
           // lo correcto es contar los bits modificados, pero si tenemos suerte
           // solo se ha modificado 1 bit por caracter
	   int count = 0;
	   for(int i = 0; i < LARGO; i++) {
	       if(data[i] != 0) {
	           count++;
	       }
	   }
	   printf("Mensaje despues del ruido: %d modificaciones\n", count);
	}
}
 
 

Elimina la invocacion del destructor explicita. Deja que el objeto se destruya solo al morir el programa.

Repito, porque decidiste ignorar la pregunta:

Si "cuantos" tiene valor 1, y tienes 100 bits en total.

cuantos bits tienes que modificar de esos 100 bits?
cuantos modificas?

Para entender lo que tu crees que estas haciendo, comparado con lo que se pide:

Si "cuantos" tiene valor 1, y tienes 100 bits en total.

cuantos bits tienes que modificar de esos 100 bits?

yo digo que tienes que modificar 1 de ellos, aleatoriamente elegido, y no es lo que haces.

El que muestres que los datos han sido modificados, no implica que las modificaciones estan bien hechas.

Mira la descripcion que mandaste:

a) cuantos bits con ruido por cada 100 bits.

no es lo que haces.

floor() es superfluo. La division de enteros da entero siempre.

Sugiero revisar la logica, pues el codigo no parece calzar con lo que se pide.

"cuantos" deberia indicar cuantos bits modificar cada 100 bits, pero el codigo modifica los primeros "cuantos" bits, no es lo mismo.

Dicho en numeros:
no es lo mismo modificar 3 bits aleatoriamente, que modificar los primeros 3 bits.

Tener referencias hacia nodos liberados tendrá problemas si decides desrefenciarlas, si no es así, no habrá problema alguno.