Critical infrastructures like oil & gas, power grids, water treatment facilities, domain name system (DNS) etc., are attractive targets for attackers — both due to the potential impact of attacks on such systems, and due to the enormous attack surface exposed by such systems. Unwarranted functionality in the form of accidental bugs or maliciously inserted hidden functionality in any component of a system could potentially be exploited by attackers to launch attacks on the system. As it is far from practical to root out undesired functionality in every component of a complex system, it is essential to develop security measures for protecting CI systems that rely only on the integrity of a small number of carefully constructed components, identified as the trusted computing base (TCB) for the system. The broad aim of this dissertation is to characterize elements of the TCB for critical infrastructure systems, and outline strategies to leverage the TCB to secure CI systems. A unified provider-middleman-consumer (PMC) view of systems was adopted to characterize systems as being constituted by providers of data, untrusted middlemen, and consumers of data. As the goal of proposed approach is to eliminate the need to trust most components of a system to be secured, most components of the system are considered to fall under the category of “untrusted middlemen.” From this perspective, the TCB for the system is a minimal set of trusted functionality required to verify that the tasks performed by the middle-men will not result in violation of the desired assurances. Specific systems that were investigated in this dissertation work to characterize the minimal TCB included the domain name system (DNS), dynamic DNS, and Supervisory Control and Data Acquisition (SCADA) systems that monitor/control various CI systems. For such systems, this dissertation provides a comprehensive functional specification of the TCB, and outlines security protocols that leverage the trust in TCB functionality to realize the desired assurances regarding the system.