Anomaly detection systems (ADSs) were proposed more than two decades ago and since then considerable research efforts have been vested in designing and evaluating these systems. However, accuracy in terms of detection and false alarm rates, has been a major limiting factor in the widespread deployment of these systems. Hence, in this thesis we (i) Propose and evaluate information theoretic techniques to improve the performance of existing general-purpose anomaly detection systems; (ii) Design and evaluate a novel and specific-purpose machine learning-based anomaly detec- tion solution for bot detection; (iii) Stochastically model general-purpose anomaly detection systems and show that these systems are inherently susceptible to param- eter estimation attacks; and (iv) Propose novel design philosophies to combat these attacks. To improve the performance of current general-purpose anomaly detection systems, we propose (i) a feature space slicing framework; and (ii) a multi-classifier ADS. The feature space slicing framework operates as a pre-processor, that segregates the feature instances at the input of an ADS. We provide statistical analysis of mixed traffic highlighting that there are two factors that limit the performance of current ADSs: high volume of benign features; and attack instances that exhibit strong similarity with benign feature instances. To mitigate these accuracy limiting factors, we propose a statistical information theoretic framework that segregates the ADS feature space into multiple subspaces before anomaly detection. Thorough evaluations on real-world traffic datasets show that considerable performance improvements can be achieved by judiciously segregating feature instances at the input of a general-purpose ADS. The multi-classifier ADS, on the other hand, defines a standard deviation normalized entropy-of-accuracy based post-processor that judiciously combines outputs of diverse general-purpose anomaly detection classifiers, thus building on their strengths and mitigating their weaknesses. Evaluations on diverse datasets show that the proposed technique provides significant improvements over existing techniques. During the course of this research, the threat landscape changed considerably with botnets emerging as the most potent threat. However, existing general-purpose anomaly detection systems are largely ineffective in detecting this evolving threat be- cause botnets are distinctively different from their predecessors. Since botnets follow a somewhat invariant lifecycle, instead of pure behavior-based solutions, current bot detection tools employ the bot lifecycle for detection. However, these specific-purpose tools use rigid rule-based detection logic that falls short of providing acceptable ac- curacy with evolving botnet behavior [1]. Extending the design philosophy of this thesis, we propose a post-processing detection logic, for specific-purpose bot detec- tion. The proposed post-processor models the high level bot lifecycle as a Bayesian network. Experimental evaluations on diverse real-world botnet traffic datasets show that the use of Bayesian inference based post-processor provides considerable perfor- mance improvements over existing approaches. Lastly, we stochastically model a few existing general-purpose anomaly detection systems and demonstrate that these systems are highly susceptible to parameter es- timation attacks. Since current day malware is becoming increasingly stealthy and difficult to mine in overwhelming volumes of benign traffic, we argue that anomaly detection systems need to be significantly redesigned to cope with the evolving threat landscape. To this end, we propose cryptographically-inspired and moving target based ADS design philosophies. The crypto-inspired ADS design aims at randomiz- ing the learnt normal network profile while the moving target-based ADS design ran- domizes the feature space employed by an ADS for anomaly detection. We provide some preliminary evaluations that show that randomizing ADS parameters greatly improves the robustness of anomaly detection systems against parameter estimation attacks.