-Mapping IP addresses to physical locations is important for a host of cyber security applications. Examples include identifying the origin of cyber attacks, protecting against fraud in internet commerce, screening emails for phishing, and enforcing restrictions on commerce with sanctioned countries. Simultaneous geolocation of large numbers of IP hosts is needed for cyber situation awareness. Explicit formal representation of the geospatial aspects of the cyber domain is necessary for interoperation with other cyber security capabilities. Formally representing the uncertainty inherent in geolocation supports increased accuracy via information fusion, as well as integration of geospatial inference with inference about other aspects of the cyber landscape. This paper presents a probabilistic ontology (PO) for IP geolocation. The geolocation PO is represented in the PR-OWL language, which allows an OWL ontology to be augmented with information to support uncertainty management. We show how the PR-OWL ontology supports automated construction of a Bayesian network for simultaneously geolocating a large number of IP hosts. The ultimate aim is to integrate our probabilistic ontology into a comprehensive cyber security probabilistic ontology to support cyber situation awareness, predictive modeling, and response strategy definition.
I. INTRODUCTION
Recognition is growing of the need to establish a common
vocabulary for and a shared understanding of the cyber
security domain (e.g., [
The cyber security domain is fraught with uncertainty.
Support for uncertainty management is a key requirement for cyber
situation awareness and decision support tools. Probabilistic
ontologies augment traditional ontologies with the ability
to represent uncertainty associated with properties of and
relationships among domain entities, supporting semantically
aware automated uncertainty management [
This paper presents a case study of the use of a probabilistic ontology to represent and reason about a key problem in the cyber security domain, mapping IP addresses to physical locations. Example applications of IP geolocation include identifying the origin of cyber attacks, protecting against fraud in internet commerce, screening emails for phishing, and enforcing restrictions on commerce with sanctioned countries. Most IP geolocation methods focus on identifying the location of a single IP host. To support cyber situation awareness, a useful capability is simultaneous geolocation of a large number of hosts, with a reduced requirement for geographic resolution.
As an essential component of an overall cyber security strategy, geolocation services need to interoperate smoothly with other elements of a cyber security tooklit. For this purpose, an ontology of the geospatial aspects of the cyber domain can form a useful module in a cyber domain ontology. Available information for IP geolocation is fraught with uncertainty. Representing the uncertainty inherent in geolocation can support more accurate geolocation through information fusion, as well as integration of geospatial inference with inference about other aspects of the cyber landscape.
This paper presents a probabilistic ontology (PO) for IP geolocation and describes its application to the simultaneously IP node geolocation problem. The geolocation PO is represented in the PR-OWL language, which provides constructs for augmenting an OWL ontology with information to support uncertainty management. We show how the PR-OWL ontology supports automated construction of a Bayesian network for simultaneously geolocating a large number of IP hosts. The ultimate aim is to integrate our probabilistic ontology into a comprehensive cyber security probabilistic ontology to support cyber situation awareness, predictive modeling, and response strategy definition.
The paper is organized as follows. Section II gives a brief
overview of previous research on IP node geolocation. Section
III presents a factor graph model [
Although most work on IP geolocation focuses on
identifying the physical location of a single IP host, the problem
of simultaneous geolocation of many IP hosts is beginning
to receive attention ([
By itself, an IP address provides no information about a
host’s location. Therefore, information from external sources
is required to map an IP address to a physical location.
Available information comes from different sources, each
subject to uncertainty. Information sources for geolocation
can be classified into three broad categories: database-based,
name-based and measurement-based [
Geolocation databases [
Name-based geolocation [
Measurement-based geolocation [
From the discussion above, it is clear that geolocating a
large number of hosts requires coping with missing and/or
imperfect information. Fusing information from the geolocation
database and the location hints obtained from hostnames admit
information about mutually exclusive sets of hosts, thereby
increasing the number of hosts that can be geolocated.
However, this does not guarantee improvement in accuracy due to
the aforementioned uncertainties in the respective information
sources. Because past studies [
Our link delay measurements are taken from the DIMES
database [
Our model assumes that IP nodes are to be geolocated into a set of M discrete disjoint geographic regions. A joint probability distribution is defined over the random variables defined in Table I. The random variable Rn denotes the region in which IP node n is located; Gn represents the result of a geolocation database query for IP node n; Hn represents the result of a hostname lookup for IP node n. The random variable Ymn represents a measurement of relative host-to-host propagation delay between host m and host n.
Random Variable Rn Gn Hn Ymn
A joint probability distribution for the random variables {Rn, Gn, Hn, Ymn} is defined in factored form as follows.
In the absence of prior information on the distribution of hosts across regions, independent uniform distributions are assumed for the node locations Rn. That is, for each region r,
Pr(Rn = r) = .
Of course, if information were available about the relative density of nodes in different regions, it could be encoded as an informative prior distribution on the locations Rn.
Conditional on the region in which n is located, the geolocation database and hostname evidence are independent with distributions given by: and
Pr(Gn = s|Rn = r) = Pr(Hn = t|Rn = r) = ⇢ ⇢ ↵ 1 ↵ M 1
That is, the model assumes there is a probability ↵ that the geolocation database query returns the correct region, with the remaining probability distributed uniformly among the remaining regions. Similarly, there is a probability that the hostname lookup returns the correct region, with the remaining probability distributed uniformly among the remaining regions. Again, this simple model could be modified to incorporate additional information if available.
Finally, the distribution of a link delay measurement
depends on the distance between the starting and ending point of
the link. A measurement probe packet traveling from a source
to a destination may encounter other delays at each node.
While propagation delay is directly proportional to distance,
the true linear relation is distorted by the presence of other
delays, including queueing, transmission and nodal processing
delay. For Ymn measuring link delay between nodes m and
n, let Dmn denote the distance between the regions Rm and
Rn where nodes m and n are located. Chandekar and Paris
[
The distributions (1 - 4) are combined into a factored representation for the joint distribution of {Rn, Gn, Hn, Ymn}. The joint probability mass / density function is:
Y Pr(Rn) Pr(Gn|Rn) Pr(Hn|Rn) Y f (Ymn|Rm, Rn) (m,n)2 L n2 N (5) where N is the set of IP nodes to be localized and L is the set of links, or pairs of nodes connected by signal transmission measurements.
Fig. 1, adapted from [
From Fig. 1 it can be observed that the underlying physical topology determines the connectivity between random variables in the factor graph. The graph shows a cluster for each of the two hosts. Each of these clusters contains a factor for the prior distribution over the node’s location, as well as a factor for evidence from the geolocation database query and a factor for evidence from the hostname lookup. These evidence items local to each host are henceforth referred to as nodelocal evidence. Fig. 1 also contains a link between the two clusters, which is labeled by a factor representing the delay measurement.
Extending this model to an arbitrary network results in a factor graph containing a node-local evidence cluster for each host in the network and an edge connecting any two clusters for which there is a link delay measurement. Thus, the factor graph structure mirrors the topology of the physical network. Each node-local evidence cluster corresponds to a physical IP node and the delay evidence edge corresponds to a connection (IP link) between nodes.
This mapping between network topology and factor graph
allows for the systematic and simultaneous geolocation of a set
of interconnected nodes using the joint probability distribution
(5). This can be achieved by finding the joint posterior
distributions of the node regions {Rn}1 n M conditional on
database, hostname and delay evidence. For general network
topologies, solving for the joint posterior distribution is
intractable. However, the well-known sum-product algorithm
[
P r(Rm) Rm Rm0 = = directly connected nodes, thereby reasoning about the location of a host based on the location of its directly connected hosts that may have inaccurate or missing node-local evidence.
An algorithm for automatically constructing factor graphs
for arbitrary IP topologies is given in [
IV. IP GEOLOCATION PROBABILISTIC ONTOLOGY IP address geolocation is an important component capability for a broad variety of applications in cyber security and other information technology domains. Explicitly representing the the semantics of the IP address geolocation model can support model reuse across applications and interoperability with other kinds of models. For example, IP geolocation can contribute to predicting, diagnosing and responding to large-scale cyber attacks. Incorporating a geolocation capability into a cyber situation awareness and response system is facilitated by semantic awareness of the system and the component module.
As the factor graph in Fig. 1 makes clear, the geolocation
model consists of modular elements that are assembled into
a larger model to reason about a given network topology and
patterns of available evidence. Additional evidence types can
be added in a modular way by augmenting the graph with
additional nodes and edges representing the new evidence.
In a similar manner, the geolocation model could be used
within a more comprehensive system. For example, a graphical
probability model library for cyber attack plan recognition
(c.f. [
It is worth noting that the model of Section III does not
consider intentional efforts by users to thwart attempts at
geolocation. Reasons for evading geolocation are diverse,
including privacy concerns, overcoming geographical restrictions on
content access, and disguising the source of cyber-attacks.
To address the problem of IP spoofing, a technique common
in denial of service (DoS) attacks, it is important to draw a
distinction between user geolocation and IP geolocation. As
pointed out by [
Representing the model as a probabilistic ontology supports
this kind of model interoperability and reuse. Ideally, such a
probabilistic ontology would be built on an existing ontology
of the cyber domain (e.g., [
Our probabilisitic ontology is represented in the PR-OWL
language [
Table II lists the entities in the partial ontology and properties used by the node geolocation probabilistic ontology. The ontology has four types of entity: IP nodes, regions where IP nodes can be located, probe packets for measuring link delays, and evidence items. Because this is an OWL ontology, all four types are subtypes of Thing.
A property of an IP node is its location. A property of a region is its region ID, a unique identifier used to refer to the region. Properties of a probe packet include its starting and ending nodes. Properties of an evidence item include the IP node to which it refers for node local evidence, the content of a GeoIP query response, the content of a hostname lookup result, the probe packet measured by a link delay report, and the measured delay for a probe packet sent across a link.
Table III shows the relationships represented in the ontology. The entity types participating in the relationship are shown. The IsA relationship relates an entity and a type if the entity is of the given type. The ontology includes the relationships NodeDistance and RegionDistance to represent the distance between nodes and regions, respectively. Ideally, there would be only one Distance attribute to represent the distance between two spatial entities. However, the current UnBBayesMEBN implementation does not yet support polymorphism; this capability is slated for the next release. Thus, the ontology uses two different terms to accommodate the limitations of the reasoning tool.
Fig. 2 shows the Node Geolocation probabilistic ontology. The probabilistic ontology consists of five MFrags (MultiEntity Bayesian Network Fragments). Each MFrag defines a local probability distribution for its resident random variables, depicted by yellow ovals, conditional on their parents in the MFrag. The context random variables, depicted by green pentagons, represent conditions that must be satisfied for the local distribution definitions to be meaningful. Finally, the gray trapezoids are input random variables, which are parents of resident random variables whose distribution is defined in another MFrag.
The random variables in the MFrags define a joint probability distribution over properties and relationships in the ontology. A random variable with a single argument corresponds to a property, and a random variable with two arguments corresponds to a relationship. The arguments are placeholders (called ordinary variables to distinguish them from random variables) that can be filled in by the identifiers of individuals of the appropriate types. For example, if N1 and N2 are individuals of the IPNode type, the random variable Location(N1) represents the uncertain location of N1, and NodeDistance(N1, N2) corresponds to the distance between IP nodes N1 and N2. The second argument of the IsA random variable is always a type name, indicating the type of its first argument. Thus, IsA(N1, IPNode) has value True and IsA(N1, Region) has value False. Multiple instances of these MFrags can be constructed by filling in the ordinary variables with different entity instances. The MFrag instances can then be assembled into a Bayesian network called a situationspecific Bayesian network, or SSBN.
The MFrags and local distributions are described as follows. • Node Location: This MFrag defines a distribution for the Location random variable, representing the region in which an IP node is located. This random variable corresponds to the Location property of the IPNode entity. It also corresponds to the random variable Rn in the factor graph of Fig. 1. Its possible values are regions and it is given a uniform distribution, meaning that all regions are equally likely locations for any given node. • Distance: This MFrag defines distances between regions.
The RegionDistance random variable is initialized to a uniform distribution (or a Gaussian distribution with mean zero and very large variance). When region instances are defined, their respective RegionDistance random variables are set to the actual distance between each pair of regions. The NodeDistance random variable has a deterministic distribution, being equal to the distance between the regions in which its arguments are located. These random variables define distributions for the RegionDistance and NodeDistance relationships from Table III. • Probe Packet Definition: This MFrag defines random variables StartingNode and EndingNode for probe packets sent across links. The distributions are initialized as uniform. When a delay measurement is received, they are set to the starting and ending node for the the probe packet. These random variables define distributions for the StartingNode and EndingNode properties of a
ProbePacket entity as defined in Table II. • Evidence: This MFrag defines random variables ReportedNode and ReportedProbe for evidence items. The former defines the IP node to which a GeoIP query or a hostname lookup refers. The latter defines the probe packet to which a given link delay measurement refers. These random variables are initialized to uniform distributions and are set to the appropriate values when reports are received. These random variables define distributions for the ReportedNode and ReportedProbe properties of EvidenceItem entities as defined in Table II. • Link Delay: This MFrag defines the distribution for a link delay measurement conditional on the distance between the starting node and ending node for the corresponding probe packet. The DelayReport random variable corresponds to the random variable Ymn in the factor graph of Fig. 1. It has the normal distribution given by (4), or a mixture of normal distributions if router delay is being considered in the model. This random variable defines the distribution for the DelayReport property of an EvidenceItem entity as presented in Table II. • Node Local Information: This MFrag represents evidence local to a given node. The resident nodes GeoIPReport and HostnameReport correspond to the random variables Gn and Hn, respectively, in the factor graph of Fig. 1. The local distributions for GeoIPReport and HostnameReport are given by (2) and (3), respectively. These random variables define distributions for the GeoIPReport and HostnameReport properties of an IPNode entity shown in Table II.
The probabilistic ontology is applied to a given network topology and set of measurements as follows. Assume that we are given a set of nodes, a set of regions, a network topology defining node connectivity, link delay measurements for nodes connected by the topology, and GeoIP query and hostname lookup results for some or all of the nodes. Inference about node locations proceeds as follows.
1) Create an instance of Region for each region. Define the regions as mutually exclusive. Give each region an ID, and set the value of RegionID to the region’s ID. For each pair of regions, set the value of RegionDistance to the distance between the regions. 2) Create an instance of IPNode for each node in the network. Define the nodes as mutually exclusive. 3) Create an instance of ProbePacket for each probe packet for which the propagation delay has been measured. Set the properties StartingNode and EndingNode to the instances of IPnode corresponding to the endpoints of the link. 4) Create an instance of EvidenceItem for each GeoIP query result. For each report, set the property ReportedNode to the IPnode instance to which the report refers, and the property GeoIPReport to the region indicated by the report. 5) Create an instance of EvidenceItem for each hostname lookup result. For each report, set the property ReportedNode to the IPnode instance to which the report refers, and the property HostnameReport to the region indicated by the report. 6) Create an instance of EvidenceItem for each link delay measurement. For each report, set the property ReportedProbe to the instance of ProbePacket to which the report refers. Set the property DelayReport to the measured delay across the link. 7) Run a query to find the posterior distribution of the NodeLocation properties. This involves assembling a situation-specific Bayesian network containing the random variable instances created in the above steps. The MFrags containing the random variable instances are retrieved and instantiated, and then combined by unifying on common random variables. The result is a Bayesian network to reason about IP node locations.
Fig. 3 shows the situation-specific Bayesian network produced by the UnBBayes software for the case of a network with two nodes connected by a single link. The Bayesian network of Fig. 3 and the factor graph of Fig. 1 encode the identical joint distribution for node locations and evidence. The model of (5) and the probabilistic ontology of Fig. 2 encode formally equivalent joint distributions over node locations, node local evidence and transmission delay evidence.
The SSBN of Fig. 3 is a hybrid Bayesian network containing
both discrete and continuous random variables. The distance
random variables are real-valued and continuous; the other
random variables are discrete. The graph of Fig. ?? is a
polytree, and exact inference is possible using an algorithm
for conditional linear Gaussian (CLG) Bayesian networks.
For larger networks with complex network topologies, the
graph will contain cycles and exact inference is intractable.
Approximate inference algorithms such as the one presented
in [
Explicitly representing domain semantics in computable form supports maintainability, interoperability and extensibility of systems. For problems characterized by reasoning under uncertainty, a semantically rich representation for sources of uncertainty should be appropriately integrated with the domain ontology. This paper presented a case study of a probabilistic ontology for large-scale IP address geolocation. The probabilistic ontology integrates an existing factor graph model for IP geolocation with a domain ontology representing geolocation knowledge. Random variables in the factor graph model correspond to uncertain properties and relationships in the domain ontology. The model is represented as a PROWL probabilistic ontology that augments an OWL domain ontology by defining probability distributions for uncertain properties and relationships. Reasoning with the probabilistic ontology is performed by creating instances of the relevant entities, instantiating copies of the random variables by filling in their arguments with appropriate entity instances, and assembling them into a Bayesian network to reason about the particular problem instance. The model can be used to reason about arbitrary numbers of IP nodes and regions, arbitrary network topologies, and arbitrary numbers of evidence items.