In this work, we study a class of deception planning problems in which an agent aims to alter a security monitoring system’s sensor readings to disguise its adversarial itinerary as an allowed itinerary in the environment. Both the adversarial and allowed itinerary sets are defined by regular languages. We investigate whether there exists a strategy for the agent to alter the sensor readings, with a minimal cost, such that for any adversarial paths it takes, the system thinks the agent took a path within the allowed itinerary. Our formulation assumes an offline sensor alteration where the agent determines the sensor alteration strategy and implements it, and then carries out any path in its adversarial itinerary. We prove that the problem of solving the optimal sensor alteration is NP-hard and present an exact algorithm based on integer linear programming. We demonstrate the correctness and the efficacy of the algorithm using several experiments.