A traitor tracing system generates a hypothesized model of the circumvention device that models a hypothesized set of device keys compromised by the circumvention device. The system iteratively invokes a subset tracing system to identify a compromised device key until substantially all the compromised device keys in the set of compromised device keys are identified so as to disable the circumvention device. A subset tracing system generates a circumvention device model that models behavior of a circumvention device using prior knowledge and The system iteratively selects and applies to the circumvention device a test based on the hypothesized model and the circumvention device model and receives a response from the circumvention device indicating a success of the test in playing protected content on the circumvention device. The system updates the hypothesized model using the received response, the selected test, a current version of the hypothesized model, and a current version of the circumvention device model to focus the test selecting process in determining the device keys obtained from the traitor.