1. A method, comprising: receiving, by a processor, a database containing records; determining, by a processor, a number of artificial records to add to the database to achieve a false negative mark detection rate less than a specified threshold; and marking, by the processor, said database by adding the determined number of artificial records to the database, each artificial record containing at least one value that, when said database is used following said marking, is detectable by a third party, and wherein each added artificial record is in addition to records already present in the database; wherein said false negative rate comprises a probability of failing to detect the mark in a discovered subset of the database.