A Dynamic Programming Algorithm for the Generalized Minimum Filter Placement Problem on Tree Structures

We consider a network where nodes communicate by exchanging information packets whose fields include the address of the sending node and that of the destination node. In the absence of some verification mechanism, an attacking node can send packets to another node using a forged origin address. In this study, we consider an optimization problem of identifying a minimum cardinality subset of verification nodes on a tree such that the number of attacks from any forged origin to any destination is limited to a prescribed level. For the case in which communication is permitted between every node in the tree, we develop an optimal polynomial-time dynamic programming algorithm for this problem. We compare the performance of the dynamic programming algorithm against a mixed-integer programming model on randomly generated tree networks at varied levels of security.