Organizations in all sectors of business have become highly dependent upon information systems for the conduct of business operations. Of necessity, these information systems are designed with many points of ingress, points of exposure that can be leveraged by a motivated attacker seeking to compromise the confidentiality, integrity or availability of an organization's information assets. To protect its assets, an organization needs to implement information security controls that mitigate the risks associated with these techniques. One of the key controls available to an organization today is the intrusion detection system (IDS), which is used to detect specific events associated with unauthorized or suspicious activity. Traditional IDS systems have two limitations that this research addresses. First, most IDS systems are tuned to detect specific attacks, but do not attempt to automatically reason across multiple attacks. Such emphasis on "single-step" attacks, as opposed to "multi-step" attacks puts the entire burden of reasoning across multiple steps of a potential attack on the security analyst. Second, traditional IDS systems do not explicitly consider uncertainty, which limits the analyst's ability to model situations in which uncertainty might be a significant factor. This research examines the issue of multi-step attack detection in the presence of uncertainty in order to provide guidance to practitioners regarding the design and implementation of intrusion detection systems. First, we consider the bounding of uncertainty in a linear Bayesian model of multi-step attacks. In this work we outline a tradeoff between uncertainty and latency in the multi-step case: low inference uncertainty can be achieved but only at the price of latency in terms of the attack stage at which uncertainty levels become small. Next, we consider the problem of detection in a general attack topology. In this work, we show how to formulate queries for general definitions of intrusion and how to propagate parameter uncertainty through the model to a query result. In the case of zero parameter uncertainty, we provide an efficient algorithm to enumerate useful operating points within the 2-dimensional design space of detection rate x false positive rate. For the uncertain parameter case, we show how operating points become 2-dimensional operating boxes and show that the general problem of operating box enumeration is highly computationally complex, necessitating heuristic solutions. Next, we return our focus to the linear attack topology and theoretically show specific cases under which model parameter uncertainty cannot produce output uncertainty. Finally, we conduct experiments evaluating two heuristic solutions to the general detection problem under uncertainty, heuristics based on our theoretical results. We show that a heuristic solution based on our operating point enumeration algorithm provides results very close to those of full enumeration. Additionally, our experimental results show the significance of uncertainty in the multi-step attack detection cases considered, illustrating the importance of considering uncertainty when designing detection systems in the multi-step case. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]