On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> We present a novel method for detecting hit-list worms using protocol graphs. In a protocol graph, a vertex represents a single IP address, and an edge represents communications between those addresses using a specific protocol (e.g., HTTP). We show that the protocol graphs of four diverse and representative protocols (HTTP, FTP, SMTP, and Oracle), as constructed from monitoring for fixed durations on a large intercontinental network, exhibit stable graph sizes and largest connected component sizes. Moreover, we demonstrate that worm propagations, even of a sophisticated hit-list variety in which the attacker has advance knowledge of his targets and always connects successfully, perturb these properties. We demonstrate that these properties can be monitored very efficiently even in very large networks, giving rise to a viable and novel approach for worm detection. We also demonstrate extensions by which the attacking hosts (bots) can be identified with high accuracy. <s> BIB001 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> Network traffic can be represented by a Traffic Dispersion Graph (TDG) that contains an edge between two nodes that send a particular type of traffic (e.g., DNS) to one another. TDGs have recently been proposed as an alternative way to interpret and visualize network traffic. Previous studies have focused on static properties of TDGs using graph snapshots in isolation. In this work, we represent network traffic with a series of related graph instances that change over time. This representation facilitates the analysis of the dynamic nature of network traffic, providing additional descriptive power. For example, DNS and P2P graph instances can appear similar when compared in isolation, but the way the DNS and P2P TDGs change over time differs significantly. To quantify the changes over time, we introduce a series of novel metrics that capture changes both in the graph structure (e.g., the average degree) and the participants (i.e., IP addresses) of a TDG. We apply our new methodologies to improve graph-based traffic classification and to detect changes in the profile of legacy applications (e.g., e-mail). <s> BIB002 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> Network security applications often require analyzing huge volumes of data to identify abnormal patterns or activities. The emergence of cloud-computing models opens up new opportunities to address this challenge by leveraging the power of parallel computing. ::: ::: In this paper, we design and implement a novel system called BotGraph to detect a new type of botnet spamming attacks targeting major Web email providers. Bot-Graph uncovers the correlations among botnet activities by constructing large user-user graphs and looking for tightly connected subgraph components. This enables us to identify stealthy botnet users that are hard to detect when viewed in isolation. To deal with the huge data volume, we implement BotGraph as a distributed application on a computer cluster, and explore a number of performance optimization techniques. Applying it to two months of Hotmail log containing over 500 million users, BotGraph successfully identified over 26 million botnet-created user accounts with a low false positive rate. The running time of constructing and analyzing a 220GB Hot-mail log is around 1.5 hours with 240 machines. We believe both our graph-based approach and our implementations are generally applicable to a wide class of security applications for analyzing large datasets. <s> BIB003 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> State-of-the-art approaches for the detection of peer-to-peer (P2P) botnets are on the one hand mostly local and on the other hand tailored to specific botnets involving a great amount of human time, effort, skill and creativity. Enhancing or even replacing this labor-intensive process with automated and, if possible, local network monitoring tools is clearly extremely desirable. To investigate the feasibility of automated and local monitoring, we present an experimental analysis of the traffic dispersion graph (TDG)--a key concept in P2P network detection--of P2P overlay maintenance and search traffic as seen at a single AS. We focus on a feasible scenario where an imaginary P2P botnet uses some basic P2P techniques to hide its overlay network. The simulations are carried out on an AS-level model of the Internet. We show that the visibility of P2P botnet traffic at any single AS (let alone a single router) can be very limited. While we strongly believe that the automated detection and mapping of complete P2P botnets is possible, our results imply that it cannot be achieved by a local approach: it will inevitably require very close cooperation among many different administrative domains and it will require state-of-the-art P2P algorithms as well. <s> BIB004 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> A key feature that distinguishes modern botnets from earlier counterparts is their increasing use of structured overlay topologies. This lets them carry out sophisticated coordinated activities while being resilient to churn, but it can also be used as a point of detection. In this work, we devise techniques to localize botnet members based on the unique communication patterns arising from their overlay topologies used for command and control. Experimental results on synthetic topologies embedded within Internet traffic traces from an ISP's backbone network indicate that our techniques (i) can localize the majority of bots with low false positive rate, and (ii) are resilient to incomplete visibility arising from partial deployment of monitoring systems and measurement inaccuracies from dynamics of background traffic. <s> BIB005 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> As a key approach to securing large networks, existing anomaly detection techniques focus primarily on network traffic data. However, the sheer volume of such data often renders detailed analysis very expensive and reduces the effectiveness of these tools. In this paper, we propose a light-weight anomaly detection approach based on unproductive DNS traffic, namely, the failed DNS queries, with a novel tool - DNS failure graphs. A DNS failure graph captures the interactions between hosts and failed domain names. We apply a graph decomposition algorithm based on the tri-nonnegative matrix factorization technique to iteratively extract coherent co-clusters (dense subgraphs) from DNS failure graphs. By analyzing the co-clusters in the daily DNS failure graphs from a 3-month DNS trace captured at a large campus network, we find these co-clusters represent a variety of anomalous activities, e.g., spamming, trojans, bots, etc.. In addition, these activities often exhibit distinguishable subgraph structures. By exploring the temporal properties of the co-clusters, we show our method can identify new anomalies that likely correspond to unreported domain-flux bots. <s> BIB006 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> The detection and isolation of peer-to-peer botnets is an ongoing problem. We propose a novel technique for detecting P2P botnets. Detection is based on unifying behavioural analysis with structured graph analysis. First, our inference technique exploits a fundamental property of botnet design. Modern botnets use peer-to-peer communication topologies which are fundamental to botnet resilience. Second, our technique extends conventional graph-based detection by incorporating behavioural analysis into structured graph analysis, thus unifying graph-theoretic detection with behavioural detection under a single algorithmic framework. We carried out evaluation over real-world P2P botnet traffic and show that the resulting algorithm can localise the majority of bots with low false-positive rate. <s> BIB007 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Graph-Based Detection <s> Malware remains one of the most significant secu- rity threats on the Internet. Antivirus solutions and blacklists, the main weapons of defense against these attacks, have only been (partially) successful. One reason is that cyber-criminals take active steps to bypass defenses, for example, by distribut- ing constantly changing (obfuscated) variants of their malware programs, and by quickly churning through domains and IP addresses that are used for distributing exploit code and botnet commands. We analyze one of the core tasks that malware authors have to achieve to be successful: They must distribute and install malware programs onto as many victim machines as possible. A main vec- tor to accomplish this is through drive-by download attacks where victims are lured onto web pages that launch exploits against the users' web browsers and their components. Once an exploit is successful, the injected shellcode automatically downloads and launches the malware program. While a significant amount of previous work has focused on detecting the drive-by exploit step and the subsequent network traffic produced by malware programs, little attention has been paid to the intermediate step where the malware binary is downloaded. In this paper, we study how clients in real-world networks download and install malware, and present Nazca, a system that detects infections in large scale networks. Nazca does not operate on individual connections, nor looks at properties of the downloaded programs or the reputation of the servers hosting them. Instead, it looks at the telltale signs of the malicious network infrastructures that orchestrate these malware installa- tion that become apparent when looking at the collective traffic produced and becomes apparent when looking at the collective traffic produced by many users in a large network. Being content agnostic, Nazca does not suffer from coverage gaps in reputation databases (blacklists), and is not susceptible to code obfuscation. We have run Nazca on seven days of traffic from a large Internet Service Provider, where it has detected previously-unseen malware with very low false positive rates <s> BIB008
A slightly different approach for detection is to make use of graph-based detection approaches. These are becoming important due to the ability of graphs to be able to naturally represent communication patterns. These methods are still ML based, but they make use of graph-based methods as the statistical component of the algorithm. Several works BIB001  BIB002 BIB003 BIB004 have applied graph analysis to detect botnets. The technique of Collins and BIB001 detects anomalies induced in a graph of protocol-specific flows by botnet control traffic. They suggest that a botnet can be detected based on the observation that an attacker will increase the number of connected graph components due to a sudden growth of edges between unlikely neighboring nodes. Although it depends on being able to accurately model valid network growth, this is a powerful approach because it avoids depending on protocol semantics or packet statistics. However, this work only makes minimal use of spatial relationship information. Additionally, the need for historical record keeping makes it challenging in scenarios where the victim network is already infected when it seeks help and has not stored past traffic data. The system, when tested with real network traffic and artificial attacks, is able to identify bot activity with a TP rate of 65% to 90% and a low FP rate. Illiofotou et al. [2008, 2009] also exploit the dynamicity of traffic graphs to classify network flows to detect P2P networks. They use static (spatial) and dynamic (temporal) metrics centered on node-and edge-level metrics in addition to the largest-connected-component-size as a graph-level metric. BotGrep BIB005 proposes a data mining technique to discover P2P graphs based on searching for expander graphs using random walks. The results of random walks are clustered to extract all P2P networks, which can then be identified using past knowledge (e.g., hosts representing honeypots). The system is able to identify P2P networks on ISP-level datasets with a 98% TP rate and 0.4% FP rate. Botyacc BIB007 ] performs a similar operation by producing a dual graph of the communication graph, applying the Laplace-Beltrami operator to reduce the dimensionality of the data, and then applying random walks to extract P2P networks. This can achieve detection rates of up to 99% with an FP rate below 0.1%. BIB008 make use of a graph-based approach to detect the binary download stage of the malware infection process in large-scale networks. Information collected from HTTP traffic is used to build undirected neighborhood graphs, where nodes represent IP addresses, domain names, FQDNs, URLs, URL paths, file names, and downloaded files (represented as hashes). A graph is generated for each host that exhibits malware-related behavior (e.g., domain fluxing). Graphs are then assigned a metric, based on the graph properties, on the likelihood that the candidate is malicious. When tested on a week-long ISP dataset, the system can achieve 60% precision and 90% recall on the malicious class, and 99.69% precision and 98.14% recall on the benign class, and is successful in identifying numerous malicious downloads. Manadhata et al. [2014] incorporate belief propagation into a graph model for detecting malicious domains. An undirected graph is produced where nodes are hosts and domains, and edges go from hosts to domains that they access. Using a ground truth instantiated from public whitelists and blacklists, belief propagation is applied until stabilization occurs, with a domain labeled as malicious if the final belief value is above a threshold. This can achieve a TP rate of 95.2% and an FP rate of 0.68%. They also show that the system can be run in near real time (processing 3 hours of data takes 16 minutes), meaning that malicious domains could be detected within 16 minutes of first appearing. BIB006 also apply a graph-based technique for grouping suspicious domain names. In particular, they focus on DNS failures, where domain queries are returned unresolved. Although there are legitimate reasons for domain queries to be unresolved, it could be an indicator of bot activity, such as DGAs or FFSNs. The work aims to extract clusters of domains that represent similar behavior, indicating group activity. These clusters can then be used as input for further analysis to identify particular attacks. A bipartite graph is constructed with hosts and domains that result in failures as vertices, with an edge between a host and domain indicating at least one query from that host for that domain. Dense subgraphs (clusters) are then extracted, which can represent linked behavior. When tested on a campus network, the system found eight unknown clusters of domain names that could indicate malicious activity.