\section{Notos}
\label{sec:notos}

\subsection{General}
\label{subsec:notos_general}

\textit{Notos} has been published in 2010 by \fsAuthor{Antonakakis:2010:BDR:1929820.1929844} at the Georgia Institute of Technology. It has been introduced as ``being the first [system] to create a comprehensive dynamic reputation system around domain names'' \fsCite[Section 1]{Antonakakis:2010:BDR:1929820.1929844}. \textit{Notos} is based on the observation that malicious use of DNS usually can be distinguished from legitimate, professionally provisioned DNS services by unique characteristics. Fraudulent activities therefore usually utilize techniques to evade security countermeasures, like fast changing records \fsCite{Antonakakis:2010:BDR:1929820.1929844}. This approach is mainly using passive historical DNS information that was obtained on multiple recursive resolvers distributed across the Internet. For building a model of how resources are typically used in legitimate and malicious applications, information about vicious IP addresses and domain names is collected from different sources like honeypots, malware analysis services and spam-traps. Using this model, new domains that have never been seen before can be dynamically assigned with a reputation score of how likely this new domain is involved in malicious activities. Malicious activities in the context of \textit{Notos} are roughly described as: ``if it [a domain] has been involved with botnet C\&C servers, spam campaigns, malware propagation, etc.'' \fsCite[Section 3]{Antonakakis:2010:BDR:1929820.1929844}

\textit{Notos} uses some basic terminology which is briefly introduced here:
\begin{itemize}
    \item A domain \textit{d} consists of several substrings which are described in \nameref{subsec:domain_names}. Abbreviations used in the following Sections are: \\
        \textbf{Top-level domain:} TLD, where \(TLD(d)\) is the top-level domain of \textit{d}. \\
        \textbf{Second-level domain:} \(2LD(d)\) being the second-level domain of domain \textit{d}. \\
        \textbf{Third-level domain: } \(3LD(d)\) containing the three rightmost substrings separated by period for \textit{d}.
    \item Given domain \(d\), \(Zone(d)\) describes the set of domains that include \textit{d} and all subdomains of \textit{d}.
    \item \(D = \{d_1, d_2, ..., d_m\}\) representing a set of domains and \(A(D)\) all IP addresses that, at any time, any domain \(d \in D\) resolved to.
    \item \(BGP(a)\) consists of all IP addresses that are residing in the same \gls{bgp} prefix as \textit{a}.
    \item Analogously, \(AS(a)\) as the set of IP addresses located in the same \gls{as} as \textit{a}.
\end{itemize}


\subsection{Architecture}
\label{subsec:notos_architecture}

The main goal of \textit{Notos} is to assign a dynamic reputation score to domain names. Domains that are likely to be involved in malicious activities are tagged with a low reputation score, whereas legitimate Internet services are assigned with a high reputation score. 
\textit{Notos'} primary source of information for the training and classification is a database that contains historical data about domains and resolved IP addresses. This database is built using DNS traffic from two recursive ISP DNS servers (RDNS) and pDNS logs collected by the Security Information Exchange (SIE) which covers authoritative name servers in North America and Europe. For building a list of known malicious domain names, several honeypots and spam-traps have been deployed. A large list of known benign domains has been gathered from the top sites list on \textit{alexa.com} which ranks the most popular websites in several regions \fsCite{AlexaWebInformationOnline}. These two lists are referred to as the \textit{knowledge base} and are particularly used to train the reputation training model. 


To assign a reputation score to a domain \textit{d}, the most current set of IP addresses \(A_{c}(d) = \left\{a_{i}\right\}_{i=1..m}\), to which \textit{d} points to, is first fetched. Afterwards the pDNS database is queried for several information for this domain \textit{d}. The \textit{Related Historic IPs (RHIPs)} is the set of all IP addresses that ever pointed to this domain. In case domain \textit{d} is a third-level domain, all IP addresses that pointed to the corresponding second-level domain are also included. Also see Section~\ref{subsec:domain_names} for more information on the structure of domain names. If \textit{d} is a second-level domain, then all IPs that are pointed to from any of the third-level subdomains are also added to the RHIPs. The reason why second- and third-level domains are combined here is that according to \fsAuthor{Antonakakis:2010:BDR:1929820.1929844} most third level domains are related to their corresponding second-level domain and therefore are treated similarly. In the next step, the set of \textit{Related Historic Domains (RHDNs)} is queried and covers all domains that are related to the currently processed domain \textit{d}. Specifically, all domains which ever resolved to an IP address that is residing in any of the ASNs of those IPs that \textit{d} currently resolves to.

There are three types of features extracted from the database for \textit{Notos} that are used for training the reputation model (quotation from \fsCite[Section 3.1]{Antonakakis:2010:BDR:1929820.1929844}):

\begin{quote}
\begin{enumerate}
    \item \textbf{Network-based features:} The first group of statistical features is extracted from the set of RHIPs. We measure quantities such as the total number of IPs historically associated with \textit{d}, the diversity of their geographical location, the number of distinct autonomous systems (ASs) in which they reside, etc.
    \item \textbf{Zone-based features:} The second group of features we extract are those from the RHDNs set. We measure the average length of domain names in RHDNs, the number of distinct TLDs, the occurrence frequency of different characters, etc.
    \item \textbf{Evidence-based features:} The last set of features includes the measurement of quantities such as the number of distinct malware samples that contacted the domain \textit{d}, the number of malware samples that connected to any of the IPs pointed by \textit{d}, etc.
\end{enumerate}
\end{quote}

Figure~\ref{fig:notos_system_overview} shows the overall system architecture of \textit{Notos}. After all the features are extracted from the passive DNS database and prepared for further processing, the reputation engine is initialized. \textit{Notos'} reputation engine is operating in two modes. In offline mode, the reputation model is constructed for a set of domains using the feature set of each domain and the classification which can be calculated using the \textit{knowledge base} with black- and whitelist (also referred to as training). This model can later be used in the online mode to dynamically assign a reputation score. In online mode, the same features that are used for the initial training are extracted for a new domain (resource record or RR, see Section~\nameref{subsubsec:dns_resource_records}) and \textit{Notos} uses the trained reputation engine to calculate a dynamic reputation rating (see Figure~\ref{fig:notos_online_offline_mode}). The data for labeling domains and IPs  originates from various sources: the blacklist primarily consists of filter lists from malware services like malwaredomainlist.com and malwaredomains.com. Additional IP and domain labeling blacklists are the Sender Policy Block from Spamhaus (\fsCite{SBLOnline}) and the ZeuS blocklist from ZeuS Tracker (\fsCite{zeusblocklistInformationOnline}). The base has been downloaded before the main analyzation period (fifteen days from the first of August 2009) and as filter lists usually lag behind state-of-the art malware, the blacklists have continuously been updated. The whitelist was built using the top 500 popular Alexa websites. Additionally, the 18 most common second level domains from various content delivery networks for classifying the CDN clusters and a list of 464 dynamic DNS second level domains, for identifying domains and IPs in dynamic DNS zones, have been gathered.

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.9\textwidth, clip=true]{content/Evaluation_of_existing_Systems/Notos/Notos_System_overview.png}
    \caption{Notos: System overview \fsCite[Figure 1]{Antonakakis:2010:BDR:1929820.1929844}}
    \label{fig:notos_system_overview}
\end{figure}

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.9\textwidth, clip=true]{content/Evaluation_of_existing_Systems/Notos/Notos_offline-online_mode.png}
    \caption{Notos: online and offline mode \fsCite[Figure 3]{Antonakakis:2010:BDR:1929820.1929844}}
    \label{fig:notos_online_offline_mode}
\end{figure}


\subsection{Features}
\label{subsec:notos_features}

In this Section, all statistical features are listed and a short explanation, for what reason those have been chosen to distinguish malicious from legitimate domains, is introduced.

\subsubsection{Network-based features}
\label{subsubsec:notos_network-based_features}

The first group of features handles network-related keys. This group mostly describe how the owning operators of \textit{d} allocate network resources to achieve different goals. While most legitimate and professionally operated internet services have a rather stable network profile, malicious usage usually involves short living domain names and IP addresses with high agility to circumvent blacklisting and other simple types of resource blocking. Botnets usually contain machines in many different networks (\glspl{as} and \glspl{bgp}) operated by different organizations in different countries. Appropriate companies mostly acquire bigger IP blocks and thus use consecutive IPs for their services in the same address space. This homogeneity also applies to other registration related information like registrars and registration dates. To measure this level of agility and homogeneity, eighteen statistical network-based features are extracted from the RHIPs (see Table~\ref{tab:notos_network-based_features}).

\begin{table}[!htbp]
    \centering
    \caption{Notos: Network-based features}
    \label{tab:notos_network-based_features}
    \begin{tabularx}{\textwidth}{|l|X|}
    \hline
    \textbf{Feature Source}                         & \textbf{Feature}                                                            \\ \hline
    \multirow{9}{*}{\textit{BGP}}          & \# of distinct BGP prefixes related to \(BGP(A(d))\)                  \\ \cline{2-2} 
                                           & \# of countries in which these BGP prefixes reside                 \\ \cline{2-2} 
                                           & \# of organizations that own these BGP prefixes                    \\ \cline{2-2} 
                                           & \# of distinct IP addresses in the sets \(A_{3LD}(d)\)                  \\ \cline{2-2} 
                                           & \# of distinct IP addresses in the sets \(A_{2LD}(d)\)                  \\ \cline{2-2} 
                                           & \# of distinct BGP prefixes related to \(BGP(A_{3LD}(d)\)            \\ \cline{2-2} 
                                           & \# of distinct BGP prefixes related to \(BGP(A_{2LD}(d)\)             \\ \cline{2-2} 
                                           & \# of countries in which \(BGP(A_{3LD}(d)\)                           \\ \cline{2-2} 
                                           & \# of countries in which \(BGP(A_{2LD}(d)\)                           \\ \hline
    \multirow{3}{*}{\textit{ASN}}          & \# of distinct autonomous systems related to \(AS(A(d))\)              \\ \cline{2-2} 
                                           & \# of distinct autonomous systems related to \(AS(A_{3LD}(d)\)         \\ \cline{2-2} 
                                           & \# of distinct autonomous systems related to \(AS(A_{2LD}(d)\)         \\ \hline
    \multirow{6}{*}{\textit{Registration}} & \# of distinct registrars associated with the IPs in the \(A(d)\) set  \\ \cline{2-2} 
                                           & diversity in the registration dates related to the IPs in \(A(d)\)     \\ \cline{2-2} 
                                           & \# of distinct registrars associated with the IPs in the \(A_{3LD}(d)\) \\ \cline{2-2} 
                                           & \# of distinct registrars associated with the IPs in the \(A_{2LD}(d)\) \\ \cline{2-2} 
                                           & diversity in the registration dates for the IPs in \(A_{3LD}(d)\)       \\ \cline{2-2} 
                                           & diversity in the registration dates for the IPs in \(A_{2LD}(d)\)       \\ \hline
\end{tabularx}
\end{table}

\subsubsection{Zone-based features}
\label{subsubsec:notos_zone-based_features}

The second group is about zone-based features and is extracted from the RHDNs. In contrast to the network-based features which compares characteristics of the historic IPs, the zone-based features handles characteristics of all historically involved domains. While legitimate services often involve many domains, they usually share similarities. For example, google.com, googlemail.com, googleplus.com, etc., are all services provided by Google and contain the string 'google' in their domains. In contrast, randomly generated domains used in spam campaigns are rarely sharing similarities. By calculating the mean, median and standard deviation for some key, the overall shape of its distribution is investigated \fsCite{Antonakakis:2010:BDR:1929820.1929844}. To calculate this level of diversity, seventeen features are extracted which can be found in Table~\ref{tab:notos_zone-based_features}

\begin{table}[!htbp]
    \centering
    \caption{Notos: Zone-based features}
    \label{tab:notos_zone-based_features}
    \begin{tabularx}{\textwidth}{|l|X|}
    \hline
    \textbf{Feature Source}           & \textbf{Feature}                                                                                            \\ \hline
    \multirow{12}{*}{\textit{String}} & \# of distinct domain names in RHDNs                                                                        \\ \cline{2-2} 
                                      & average \# of distinct domain names in RHDNs                                                                \\ \cline{2-2} 
                                      & standard deviation of \# of distinct domain names in RHDNs                                                  \\ \cline{2-2} 
                                      & mean of the occurrence frequency of each single character in the domain name strings in RHDNs               \\ \cline{2-2} 
                                      & median of the occurrence frequency of each single character in the domain name strings in RHDNs             \\ \cline{2-2} 
                                      & standard deviation of the occurrence frequency of each single character in the domain name strings in RHDNs \\ \cline{2-2} 
                                      & mean distribution of 2-grams (i.e. pairs of characters)                                                     \\ \cline{2-2} 
                                      & median distribution of 2-grams                                                                              \\ \cline{2-2} 
                                      & standard deviation of 2-grams                                                                               \\ \cline{2-2} 
                                      & mean distribution of 3-grams (i.e. triples of characters)                                                   \\ \cline{2-2} 
                                      & median distribution of 3-grams                                                                              \\ \cline{2-2} 
                                      & standard deviation of the distribution of 3-grams                                                           \\ \hline
    \multirow{5}{*}{\textit{TLD}}     & \# of distinct TLD strings of each domain \(d_i\) in the RHDNs set     \\ \cline{2-2} 
                                      & ratio between \# of domains \(d_i\) whose \(TLD(d_i)=".com"\) and the total \# of TLD different from ".com"      \\ \cline{2-2} 
                                      & mean of the occurrence frequency of the TLD strings                                                         \\ \cline{2-2} 
                                      & median of the occurrence frequency of the TLD strings                                                       \\ \cline{2-2} 
                                      & standard deviation of the occurrence frequency of the TLD strings                                           \\ \hline
\end{tabularx}
\end{table}

\subsubsection{Evidence-based features}
\label{subsubsec:notos_evidence-based_features}

For the evidence-based features, public information and data from honeypots and spam-traps was collected. This \textit{knowledge base} primarily helps to discover if a domain \textit{d} is in some way interacting with known malicious IPs and domains. As domain names are much cheaper to obtain than IP addresses, malware authors tend to reuse IPs with updated domain names. Consequently, the blacklist features indicate the reuse of known malicious resources like IP addresses, \gls{bgp} prefixes and \glspl{as}. 

\begin{table}[!htbp]
    \centering
    \caption{Notos: Evidence-based features}
    \label{tab:notos_evidence-based_features}
    \begin{tabularx}{\textwidth}{|l|X|}
    \hline
    \textbf{Feature Source}             & \textbf{Feature}                                                                               \\ \hline
    \multirow{3}{*}{\textit{Honeypot}}  & \# of distinct malware samples that, when executed, try to contact \(d\) or any IP address in \(A(d)\) \\ \cline{2-2} 
                                        & \# of malware samples that contact any IP address in \(BGP(A(d)\)                                \\ \cline{2-2} 
                                        & \# of samples that contact any IP address in \(AS(A(d))\)                                          \\ \hline
    \multirow{3}{*}{\textit{Blacklist}} & \# of IP addresses in \(A(d)\) that are listed in public IP blacklists                             \\ \cline{2-2} 
                                        & \# of IPs in \(BGP(A(d)\) that are listed in public IP blacklists                                \\ \cline{2-2} 
                                        & \# of IPs in \(AS(A(d))\) that are listed in public IP blacklists                                  \\ \hline
\end{tabularx}
\end{table}

Figure~\ref{fig:notos_features} shows how the three different feature groups are computed individually and which input the corresponding feature set is using. All those features are then used as a single vector as input for the \textit{Reputation Engine}.

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.9\textwidth, clip=true]{content/Evaluation_of_existing_Systems/Notos/Notos_features.png}
    \caption{Notos: Computing network-based, zone-based, evidence-based features \fsCite[Figure 2]{Antonakakis:2010:BDR:1929820.1929844}}
    \label{fig:notos_features}
\end{figure}


\subsection{Reputation Engine}
\label{subsec:notos_reputation_engine}

The reputation engine is used to dynamically assign a reputation score to a domain \textit{d}. In the first step, the engine has to be trained with the available training set (temporal defined as the \textit{training period}). The training is performed in an offline fashion which means all data is statically available at the beginning of this step. The training mode consists of three modules: The \textit{Network Profile Model} is a model of how known good domains are using resources. This model uses popular content delivery networks (e.g., Akamai, Amazon CloudFront) and large sites (e.g., google.com, yahoo.com) as a base. In total the \textit{Network Profile Model} consists of five classes of domains: \textit{Popular Domains}, \textit{Common Domains}, \textit{Akamai Domains}, \textit{CDN Domains} and \textit{Dynamic DNS Domains}. The second module \textit{Domain Name Clusters} performs a general clustering of all domains (respectively their statistical feature vectors) of the training set. There are two consecutive clustering processes: The \textit{network-based} clustering aims to group domains with similar characteristics in terms of the agility, e.g. how often DNS resources are changed. To refine those clusters, a \textit{zone-based} clustering is performed which groups domains that are similar in terms of its RHDNs (see explanation for the \textit{zone-based features}). Those clusters of domains with similar characteristics can then be used to identify benign and malicious sets of domains. In the last step of the offline mode, the \textit{Reputation Function} is built. As seen in Figure~\ref{fig:notos_online_offline_mode}, this module takes the results of the \textit{Network Profile Model} (\(NM(d_i)\)) and the \textit{Domain Name Clusters} (\(DC(d_i)\)) for each domain \textit{d} in \(d_i, i = 1..n\) as inputs, calculates an \textit{Evidence Features Vector} \(EV(d_i)\), which basically checks if \(d_i\) or any of its resolved IPs is known to be benign or malicious, and builds a model that can assign a reputation score between zero and one to \textit{d}. This \textit{Reputation Function} is implemented as a statistical classifier. These three modules form the reputation model that can be used in the last step to compute the reputation score. A rebuild of the training model can be done at any time, for example given an updated training set.

The final stage of the reputation engine is the online (streaming like) mode. Any considered domain \textit{d} is first supplied to the \textit{network profiles} module which returns a probability vector \(NM(d) = \{c_1, c_2, ..., c_5\}\) of how likely \textit{d} belongs to one of the five classes (e.g. probability \(c_1\) that \textit{d} belongs to \textit{Popular Domains}). \(DC(d)\) is the resulting vector of the \textit{domain clusters} module and can be broken down into the following parts: For the domain \textit{d} of interest, the network-based features are extracted and the closest network-based cluster \(C_d\), generated in the training mode by the \textit{Domain Name Clusters} module, is calculated. The following step takes all zone-based feature vectors \(v_j \in C_d\) and eliminates those vectors that do not fulfill \(dist(z_d , v_j ) < R\), where \(z_d\) is the zone-based feature vector for \textit{d} and \textit{R} being a predefined radius; or \(v_j \in KNN(z_d)\), with \(KNN(z_d)\)) being the k nearest-neighbors of \(z_d\). Each vector \(v_i\) of the resulting subset \(V_d \subseteq C_d\) is then assigned one of this eight labels: \textit{Popular Domains}, \textit{Common Domains}, \textit{Akamai}, \textit{CDN}, \textit{Dynamic DNS}, \textit{Spam Domains}, \textit{Flux Domains}, and \textit{Malware Domains}. The next step is to calculate the five statistical features that form the resulting vector \(DC(d) = \{l_1, l_2, ..., l_5\}\).

\begin{enumerate}
    \item \(l_1\) the \textit{majority class label} \textit{L}, i.e. the most common label in \(v_i \in V_d\) (e.g. \textit{Spam Domains}).
    \item \(l_2\) the standard deviation of the occurrence frequency of each label.
    \item \(l_3\) mean of the distribution of distances between \(z_d\) and the vectors \(v_j \in V_{d}^{(L)}\), where \(V_{d}^{(L)} \subseteq V_d\) is the subset of those vectors, associated with the \textit{majority class label} \textit{L}.
\end{enumerate}

Having the \textit{Network Profile Model} \(NM(d)\), the \textit{Domain Name Clusters} \(DC(d_i)\), and the \textit{Evidence Features Vector} \(EV(d)\), these vectors are combined into a sixteen dimensional feature vector \(v(d)\) which is then fed into the trained reputation function. This results in a reputation score \textit{S} in the range of [0, 1], where values close to zero represent a low reputation and such more likely represent malicious usage of the domain.


\subsection{Results}
\label{subsec:notos_results}

In the last Section of the evaluation of \textit{Notos}, experimental results that have been published are listed. This covers metrics about the usage of raw data, lessons learned in the analyzation process (i.e. examined algorithms) and final acquisitions like precision and accuracy of the classification.

\textit{Notos} was the first dynamic reputation system in the context of domain names and it was able to identify malicious domain names before they appeared in public filter lists which ultimately led to the discovery of an previously unknown ZeuS botnet \fsCite{Antonakakis:2010:BDR:1929820.1929844}. To be able to assign reputation scores to new domains, \fsAuthor{Antonakakis:2010:BDR:1929820.1929844} used historic passive DNS logs of a time span of 68 days with a total volume of 27,377,461 unique, successful A-type resolutions mainly from two recursive ISP DNS servers in North America (plus pDNS logs from various networks, aggregated by the SIE \ref{subsec:notos_architecture}). Figure~\ref{fig:notos_volume_new_rr} shows that after a few days, the number of new RR stabilizes at about 100,000 to 150,000 domains a day compared to a much higher total load of unique resource records (about 94.7\% duplicates) (see Figure~\ref{fig:notos_total_volume_unique_rr}). The amount of new IPs is analogously nearly constant. After few weeks, even big content delivery networks with a large (but nearly constant) number of IP addresses will get scanned, in contrast to botnets where continuously new machines are infected. The authors infer that a relatively small pDNS database is therefor sufficient for \textit{Notos} to produce good results.

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.9\textwidth, clip=true]{content/Evaluation_of_existing_Systems/Notos/Notos_new-RR.png}
    \caption{Notos: Volume of new unseen RRs \fsCite[Figure 7b]{Antonakakis:2010:BDR:1929820.1929844}}
    \label{fig:notos_volume_new_rr}
\end{figure}

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.9\textwidth, clip=true]{content/Evaluation_of_existing_Systems/Notos/Notos_total-RR.png}
    \caption{Notos: Total volume of unique RRs \fsCite[Figure 7a]{Antonakakis:2010:BDR:1929820.1929844}}
    \label{fig:notos_total_volume_unique_rr}
\end{figure}

To get optimal results with the \textit{Reputation Function}, several classifiers have been tested and selected for the given circumstances (time complexity, detection results and precision [true positives over all positives]). A decision tree with Logit-Boost strategy (see \fsCite{Friedman98additivelogistic} for implementation details) has shown to provide the best results with a low false positive rate (FP) of 0.38\% and a high true positive rate (TP) of 96.8\%. These results have been verified using a 10-fold cross validation with a reputation score threshold of 0.5. This 10-fold cross validation method splits the dataset in ten partitions/folds (each partition optimally containing roughly the same class label distribution). One fold is then used as the validation sample (testing set) and the remaining nine partitions are used as the training set. The training set is used to train the model which is then cross validated with the testing set. This step is repeated for ten times using the same partitions, each partition being the testing set once. For the validation in \textit{Notos}, a dataset of 20,249 domains with 9,530 known bad RR has been used. As the list of known good domains, the Alexa top 500 websites have been used. Taking a bigger amount of Alexa popular sites has shown to decrease accuracy of the overall system, which could be interpreted that smaller/less popular sites are more likely to get compromised. To compare \textit{Notos}' performance with static filter lists, a pre-trained instance has been fed with 250,000 unique domains collected on 1. August 2009. 10,294 distinct entries have been reported with a reputation score below 0.5. 7,984 of this 10,294 or 77.6\% could be found in at least one blacklist (see Section~\nameref{subsec:notos_architecture} for a list of included blacklists). The remaining 22.4\% could not be precisely revealed. It is worth stating that 7,980 of the 7,984 confirmed bad domain names were assigned a reputation score of less than or equal to 0.15.


\subsection{Limitations}
\label{subsec:notos_limitations}

As \textit{Notos} is mainly using historic DNS information, new domain names that resolve to IP addresses with previously unseen prefixes, can not be reliably classified. Once IPv6, with its huge address space, will get the overall standard, a precise reputation score based on the fine grained IP address features will get harder.