Attacking unexplored networks - The probe-and-attack problem

Attackers generally do not have complete information about the structure and function of a target network, and thus have to distribute resources between actions that directly achieve an objective to return some utility (‘Attack’), and actions that expose new knowledge about the network (‘Probe’) allowing new actions to be taken. We introduce the NP-hard two-action Probe-and-Attack Problem (PAP) and provide methods to compute upper and lower bounds on the optimal solution. We then compare the bounds to the performance of two greedy algorithms on specialized instances of the problem.