Minimum-norm Sparse Perturbations for Opacity in Linear Systems

The notion of opacity describes an eavesdropper's inability to infer a system's ‘secret’ states by observing the system's outputs. In this paper, we propose algorithms to compute the minimum-norm sparse perturbation to be added to a non-opaque system to make its initial states opaque. We consider two sparsity constraints for the perturbation - structured and affine. We develop an algorithm to compute the global minimum-norm perturbation for the structured case, and use this as the initial point of another algorithm to find a local minimum for the affine case. We show empirically that this local minimum is very close to the global minimum. We demonstrate our results via a running example.