What is Normal? A Big Data Observational Science Model of Anonymized Internet Traffic
Jeremy Kepner Hayden Jananthan Michael Jones William Arcand David Bestor William Bergeron Daniel Burrill Aydin Buluc Chansup Byun Timothy Davis Vijay Gadepally Daniel Grant Michael Houle Matthew Hubbell Piotr Luszczek Lauren Milechin Chasen Milner Guillermo Morales Andrew Morris Julie Mullen Ritesh Patel Alex Pentland Sandeep Pisharody Andrew Prout Albert Reuther Antonio Rosa Gabriel Wachman Charles Yee Peter Michaleas





What is Normal? A Big Data Observational Science Model of Anonymized Internet Traffic

Research was sponsored by the Department of the Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Department of the Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. Use of this work is controlled by the human-to-human license listed in Exhibit 3 of https://doi.org/10.48550/arXiv.2306.09267


    
Jeremy Kepner^1, Hayden Jananthan^1, Michael Jones^1,  William Arcand^1, David Bestor^1, William Bergeron^1, 
 Daniel Burrill^1,  Aydin Buluc^2, Chansup Byun^1, Timothy Davis^3, Vijay Gadepally^1, Daniel Grant^4, Michael Houle^1, 
 Matthew Hubbell^1,  Piotr Luszczek^1,5, Lauren Milechin^1, Chasen Milner^1, Guillermo Morales^1, Andrew Morris^4, 
 Julie Mullen^1, Ritesh Patel^1, Alex Pentland^1, Sandeep Pisharody^1, Andrew Prout^1,  Albert Reuther^1, Antonio Rosa^1, 
 Gabriel Wachman^1, Charles Yee^1, Peter Michaleas^1



^1MIT,  ^2LBNL, ^3Texas A&M, ^4GreyNoise, ^5University of Tennessee

    September 2024
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
Understanding what is normal is a key aspect of protecting a domain.  Other domains invest heavily in observational science to develop models of normal behavior to better detect anomalies.
Recent advances in high performance graph libraries, such as the GraphBLAS, coupled with supercomputers enables processing of the trillions of observations required.
We leverage this approach to synthesize low-parameter observational models of anonymized Internet traffic with a high regard for privacy.



Internet traffic, anonymized analysis, streaming graphs, traffic matrices, network models




§ INTRODUCTION



Anomaly detection and signature detection both play important roles in detecting adversarial activities on the Internet and both approaches are increasingly being enabled by big data and machine learning techniques <cit.>.
A core challenge to creating effective anomaly detection systems is the development of adequate models
<cit.> 
of typical activity

The concept of normality It is one of the main steps to build a solution to detect network anomalies. The question “how to create a precise idea of normality?” is what has driven most researchers into creating different solutions through the years. This can be considered as the main challenge related to anomaly detection and has not been entirely solved yet.
<cit.>

Other domains (land, sea, undersea, air, and space) rely on detailed observational science models of their environment to understand what is normal
<cit.>.
 Accordingly, reproducible observations of cyberspace
<cit.>
have been recommended as a core foundation  for the science of cyber-security

The highest priority should be assigned to establishing research protocols to enable reproducible [observations].
<cit.>

Significant early results from analyzing the Internet helped establish the emerging field of Network Science  
<cit.>.
Improving these results requires ever larger data sets.  A priority for expanded observation of the Internet is the need to maintain a high regard for privacy.




The Center for Applied Internet Data Analysis (CAIDA)  based at the UC San Diego Supercomputer Center operates the largest Internet telescope in the world and has pioneered trusted data sharing best practices that combine anonymization <cit.>
with data sharing agreements. These data sharing best practices include the following principles <cit.>


  * Data is made available in curated repositories

  * Standard anonymization methods are used where needed

  * Recipients register with the repository and demonstrate a legitimate research need

  * Recipients legally agree to neither repost a corpus nor deanonymize data

  * Recipients can publish analysis and data examples necessary to review research

  * Recipients agree to cite the repository and provide publications back to the repository

  * Repositories can curate enriched products developed by researchers



In the broader networking community (commercial, federal, and academia) anonymized source-to-destination traffic matrices with standard data sharing agreements have emerged as a data product that can meet many of these requirements (see Figure <ref>)
<cit.>.
Focusing on anonymized source and destination addresses has helped alleviate privacy concerns because the non-anonymized addresses of Internet packets are already handled by many entities as part of the normal functioning of the Internet.

While an anonymized traffic matrix provides very little information about individual communications on a network, the ability collect trillions of observations over years across the Internet provides a unique opportunity for developing high-precision, low-parameter observational models of anonymized Internet traffic while maintaining a high regard for privacy. These data are particularly useful for addressing the fundamental observational science question for determining what is normal in a domain: Given two observers at different locations and/or times what can they both expect to see?

The organization of the rest this paper is as follows.  First, some fundamental network quantities are presented along with how these quantities can be readily computed from anonymized traffic matrices.  Second, the statistical properties of these network quantities are examined from of largest available network data sets in the world (CAIDA, MAWI, GreyNoise, ...).  Next, these statistical results are synthesized into a low-parameter model of anonymized Internet traffic.  Finally, the papers concludes with a summary and a discussion of potential future directions.



§ TRAFFIC MATRICES AND NETWORK QUANTITIES


Network traffic data can be viewed as a traffic matrix where each row is a source and each column is a destination (see Figure <ref>). A primary benefit of constructing anonymized  traffic matrices with high performance math libraries, such as, the GraphBLAS<cit.>, is the efficient computation of a wide range of network quantities via matrix mathematics that enable trillions of events to be readily processed with supercomputers
<cit.>.
  Figure <ref> illustrates essential quantities found in all streaming dynamic networks. These quantities are all computable from anonymized traffic matrices created from the source and destinations found in Internet packet headers.








The network quantities depicted in Figure <ref> are computable from anonymized origin-destination traffic  matrices.  It is common to filter network packets down to a valid subset of packets for any particular analysis.   Such filters may limit particular sources, destinations, protocols, and time windows.   At a given time t, N_V consecutive valid packets are aggregated from the traffic into a hypersparse matrix A_t, where A_t(i,j) is the number of valid packets between the source i and destination j. The sum of all the entries in A_t is equal to N_V

    ∑_i,j A_t(i,j) = N_V

All the network quantities depicted in Figure <ref> can be readily computed from A_t using the formulas listed in Table <ref>.  Because matrix operations are generally invariant to permutation (reordering of the rows and columns), these quantities can readily be computed from anonymized data.  Furthermore, the anonymized data can be analyzed by source and destination subranges (subsets when anonymized)  using simple matrix multiplication.  For a given subrange represented by an anonymized hypersparse diagonal matrix A_r, where A_r(i,i) = 1 implies  source/destination i is in the range, the traffic within the subrange can be computed via: A_r  A_t   A_r. Likewise, for additional privacy guarantees that can be implemented at the  edge, the same method can be used to exclude a range of data from the traffic matrix

    A_t -  A_r  A_t   A_r
 

One of the important capabilities of the award-winning SuiteSparse GraphBLAS<cit.> library is direct support of hypersparse matrices where the number of nonzero entries is significantly less than either dimensions of the matrix <cit.>.
If the packet source and destination identifiers are drawn from a large numeric range, such as those used in the Internet protocol, then a hypersparse representation of A_t eliminates the need to keep track of additional indices and can significantly accelerate the computations <cit.>.




§ INTERNET STATISTICAL PROPERTIES


When considering what is normal in a particular domain from an observational science perspective a core question to address is 


  Q   Given two observers at different locations and/or times what can they both expect to see?

Answering this question sets the foundation for observational reproducibility that is essential for scientific understanding.  To simplify the investigation in the specific context of Internet traffic the above question can be decomposed into several narrower questions that can be explored individually


  Q1 Given a sample of N_V Internet packets what are the expected values of various network quantities?

  Q2 What is the probability of seeing a specific value of a network quantity?

  Q3 Having seen a source of Internet packets what is the probability of seeing that source at a later time?

  Q4 What is the probability that two observers will see the same source at a given time?

Q1 deals with number of packets or the size of a packet window in a given sample of network data.  Q2 focuses on the probability distributions obtained from the histograms of the network quantities.  Q3 deals with the temporal self-correlations within a specific Internet traffic sensor while Q4 deals with the temporal cross-correlations of separate Internet traffic sensors.

Exploring these questions requires big data.  The subsequent analysis draws from the following Internet traffic data sets which are among the largest available for scientific research


  * CAIDA Telescope: over 40 trillion mostly malicious packets collected on an Internet darkspace  over several years <cit.>

  * MAWI: several billion mostly benign packets collected at multiple sites as part the day-in-the-life of the Internet project <cit.>

  * GreyNoise: hundreds of millions of mostly malicious web interactions collected over several years from thousands of honeypot systems spread across the Internet <cit.>

  * Enterprise gateway: over 100 billion mostly benign packets collected at a large organization <cit.>






 §.§ Sample Window Size


One of the first questions encountered when analyzing Internet traffic is how many samples (packets) to collect and at what level of granularity.  It is common to filter network packets down to a valid subset of packets for any particular analysis so that at a given time t, N_V consecutive valid packet have been collected for analysis in a traffic matrix.  Statistical fluctuations between samples are significantly reduced if N_V is held fixed and the sample time window is allowed to vary.

As N_V increases, the network quantities in Figure <ref> and Table <ref> will all increase.  How will the network quantities increase as a function of N_V?  For small values of  N_V starting at 1 the network quantities may increase linearly.  For sufficiently large values of N_V the packets may fill the entire allowed range of sources and/or destinations of the network sensor and the network quantities may level off.  Exploring this question with the various large data sets indicates that for intermediate values of N_V the network quantities are often proportional to

    N_V^γ

where 0 ≤γ≤ 1.  Figure <ref> illustrates a specific example derived from 100 billion packets collected at a large enterprise gateway <cit.>.  These scaling relationships are broadly observed with the specific values of the parameters being site specific but stable over time <cit.>.






 §.§ Probability Distributions


    Perhaps one of the most significant early results from analyzing the Internet, which helped establish the emerging field of Network Science, was the observation that many network quantities follow a power-law or heavy-tail distribution  <cit.>.  In terms of Internet traffic, an example would be that a few destinations on the Internet receive packets from many sources while most destinations receive packets from a few sources.  This question is readily explored by the looking at the histograms or probability distributions of network quantities computed from anonymized traffic matrices.    The availability of larger data sets have allowed the observations of these probability distributions to become more precise <cit.>.  Specifically, the probability of a particular network quantity having a value or degree d is often well-described by the Zipf-Mandelbrot distribution

    1/(d + δ)^λ

where typically -1 ≲δ≲ 3 and 1 ≲λ≲ 3.  Given sufficient observations,  δ and λ can be determined with high-precision.  Figure <ref> illustrates the Zipf-Mandelbrot behavior observed from billions of packets from the MAWI data set <cit.>.  Similar to the window size scaling relationships,  the Zipf-Mandelbrot distribution is broadly observed with the specific values of the parameters being site specific but stable over time.

Historically, it is worth noting that initial interest in these distributions focused on the power-law parameter λ, as this parameter described the behavior of the largest and most popular sources on the Internet <cit.>.  More recently δ has emerged as a way of describing large numbers of less popular sources that may be collectively involved in adversarial network activity.






 §.§ Temporal Self-Correlations



If an observer sees a source on the Internet what is the probability that the source will be seen again at a later time?  This is the essential question that self-correlations seek to answer.  The network traffic data sets can be used to address this questions by measuring the probability of seeing a source again at time t. Figure <ref> illustrates these probabilities for the CAIDA and GreyNoise data sets over months and years <cit.>.  Intriguingly the source self-correlations are well approximated by the modified Cauchy distribution

    β/β + t^α

where typically 0 < α≲ 1 and β > 0.  These parameters are site specific and differ significantly between benign and malicious data.  The modified Cauchy distribution can be characterized by the time it takes for the probability to drop to one half

    t_ half = β^1/α

In the case of the GreyNoise benign data this timescale is years while the malicious data has much shorter times scales of days, hours, and minutes.




 §.§ Temporal Cross-Correlations


Similar to self-correlations, it is likewise possible to explore the probability that a second observer will see a source at the same or a different time.  If the self-correlations of two network sensors are observed to follow a modified Cauchy distribution it is not surprising that their cross-correlations in time are also observed to follow a modified Cauchy distribution <cit.>.   Perhaps more fundamental is the probability that a source seen by one observer will even be seen by another observer.  Figure <ref> plots the probability of a source seen by the CAIDA telescope also being seen in the same month by the GreyNoise honeyfarm.  This probability is strongly dependent upon the number of packets the source has sent to the CAIDA telescope and is well approximated by the formula

    log_2(d)/log_2(N_V^1/2)

for d < N_V^1/2.  Simply put, if a source emits a lot of packets it is more likely to be seen.





§ MODEL SYNTHESIS


The empirically motivated models from the previous section allow the core question to be refined around the variables that directly impact the observability of network traffic.  These variables include the window size N_V, the number of packets d observed from a source, and the time t between observations. The more pricess question then becomes  


  Q Given a window with N_V incoming packets, what is the probability of a source sending d packets being observed by a second observer at time t

Based on prior observations, the empirical formula for this probability can be hypothesized to be proportional to

    N_V^γ 1/(d + δ)^λ β/β + t^α log_2(d)/log_2(N_V^1/2)

where γ, δ, λ, β, and α are site specific parameters that tend to be stable over time.

The above expression is an empirically motivated formula.  Ideally, theoretical models derived from underlying first-principles will be found which are then approximated by the above formula under appropriate conditions.  While such a theoretical model does not yet exist, certain logical deductions can be made about the reasonableness of the terms in the above formula.

By definition network quantities grow monotonically with window size and the term N_V^γ is one the simplest formulas satisfying this condition.  The power-law dependence of network quantities on their observed value d has been well-observed and the successful preferential attachment model remains a reasonable underlying theoretical framework for these observations <cit.>.  Temporal self-correlation and cross-correlation measurements require continuous long-duration coeval observations from multiple observers and are subsequently rarer.  The correlation function is defined to have a peak value of 1 at t=0 and it seems intuitive that the probability of seeing a source again would slowly drop-off over time.  The modified Cauchy distribution satisfies these conditions. Finally, it is also intuitive that the probability of an observer seeing a source is related to the ratio of the number of packets from the source and the size of the observation window.




§ CONCLUSIONS AND FUTURE WORK



Modern Internet telescopes and high-performance sensors are capable of collecting trillions of observations.  Supercomputers and high performance graph analysis libraries, such as the GraphBLAS, allow these big data observations to be analyzed to develop high-precision, low-parameter observational models of Internet traffic.  These models provide detailed predictions on the visibility of Internet sources of a given intensity over time and the likelihood such sources will be seen by an observer at a different location.  For a given location the parameters of the model tend to be stable over time.  Using these models, it is possible to predict in detail many statistical properties of Internet traffic seen at a given location and time.  These predictions can assist in correctly placing network sensors by comparing what is expected with what is observed, ensuring zero trust configurations are maintained by revealing when networks have changed, and detecting anomalies due to malicious activity.

Going forward there should be an expansion of Internet observatories like CAIDA and MAWI.  The globe currently depends upon a small dedicated community to operate and maintain current network observatories. These lookouts are our only means for obtaining consensus empirical answers to critical questions. These capabilities should be significantly expanded.  Furthermore, the underlying network science at scale needs enhancement.  Understanding of the underlying processes in any field is discovered by painstaking science. Early efforts on small data sets revealed significant new discoveries and established the field of Network Science <cit.>. Current observations are a much larger and are calling out for scientific exploration.




§ ACKNOWLEDGMENTS


The authors wish to acknowledge the following individuals for their contributions and support: 
Daniel Andersen, LaToya Anderson, Sean Atkins, Chris Birardi, Bob Bond, Alex Bonn, Koley Borchard, Stephen Buckley, Aydin Buluc, K Claffy, Cary Conrad, Chris Demchak, Phil Dykstra, Alan Edelman, Garry Floyd, Jeff Gottschalk, Dhruv Gupta, Thomas Hardjono, Chris Hill, Charles Leiserson, Kirsten Malvey, Chad Meiners, Adam Michaleas, Sanjeev Mohindra, Heidi Perry, Christian Prothmann, Steve Rejto, Josh Rountree, Daniela Rus, Mark Sherman, Scott Weed, Adam Wierman, Marc Zissman.

ieeetr




