The increasingly tight coupling of cyber (computing/communication) and physical (sensing/actuation) components has opened the door for developing many engineering systems with increasing complexity. On the one hand, these systems (commonly termed cyber-physical systems, or CPS for short) have enabled a multitude of applications where decisions are taken at various time-scales, driven by the sensory information, and are used for purposes such as automated control and adaptive interventions. On the other hand, there has been a corresponding increase in attacks targeting the integrity and security of these systems. These attacks pose a significant threat to often sensitive devices, potentially impairing our relation with these technologies. Various unique attributes of sensory information make it particularly challenging to formalize and address these concerns, and approaches thus far to handle them have been largely insufficient. The objective of this dissertation is to develop a principled understanding of these emerging concerns and develop formalisms, algorithms, and system mechanisms to effectively address them. The contributions of this dissertation are multi-fold. We start by playing the role of an adversarial attacker trying to discover new attack vectors for which traditional security mechanisms provide no defense guarantees. In particular, we focus on attacks that take place on sensors that collect information about the physical process in CPS. We show that by exploiting the weakness in securing sensor information, a malicious attacker can cause life-threatening situations which plays as a motivation for the rest of this dissertation. Next, we explore two countermeasures called sensor-level countermeasures and system-level countermeasures. In the sensor-level countermeasures, we propose a physical challenge-response authentication (PyCRA) scheme for sensors that is designed to provide an authorization mechanism that not only detects malicious attacks but provides resilience against them. The majority of this dissertation focuses on designing system-level counter measures to sensor attacks. In the system-level countermeasures, we consider the problem of designing algorithms for CPS whose sensor measurements are corrupted by a malicious attacker. The attacker capabilities are limited in the sense that only a subset of all the sensors can be attacked although this subset is unknown. In particular, we focus on the setup where all measurements from various sensors are sent to a central unit whose functionality is to fuse all these measurements in order to estimate the state of the CPS regardless of the existence of the malicious attacker. We call this problem the secure state estimation problem. We analyze sufficient and necessary conditions for the solvability of the secure state estimation problem under three different setups namely, linear deterministic systems, linear stochastic systems, and nonlinear deterministic systems. We propose the notion of s-sparse observability and show how it plays a vital role in solving the secure state estimation problem. We show that the secure state estimation problem is a combinatorial problem. The most notable contribution of this dissertation is a novel Satisfiability Modulo Theory (SMT) solver that splits the reasoning, about the combinatorial complexity of the secure state estimation problem, over Boolean and real domains and uses a powerful tool from each domain. By leveraging results from formal methods over real numbers, we provide guarantees on the soundness and completeness of our algorithm. We also extend the SMT-solver to estimate the state under sensor attacks to the context of stochastic linear dynamical system and nonlinear differentially flat systems Finally, we touch upon the related problem of privacy attacks in cyber-physical systems. Unlike sensor attacks, privacy attacks are a form of passive attacks that target data collection that can be used to leak sensitive information. We present a novel model-based obfuscation approach with strong formal guarantees. Our approach preserves both the utility of the event trace and its spatio-temporal-plausibility while providing strong privacy guarantees.