A Logic-based Analysis of Network Security | Lucideus Research

Network Security plays a key role in any organization. There are different kinds of software vulnerabilities and configuration issues that might be present in different components of a network. These weaknesses can potentially cause various kinds of exploit scenarios and lead to attacks targeting critical components and information present in assets that are connected to the network. These attacks are sometimes carried out by people who have malicious intentions and are highly skilled. The security landscape for networks is highly dynamic where new weaknesses and attack methodologies are discovered quite frequently.

Hence, a robust model to analyze the entire security infrastructure of a network is highly essential. For this, we need to consider the way different network components like routers, switches, firewalls, web server, file server, etc. interact and communicate with each other. The model should be able to automatically integrate formal vulnerability specifications from the bug-reporting community. Also, the analysis must be scalable to networks with thousands of machines. In the research paper titled MulVAL: A Logic-based Network Security Analyzer written by Xinming Ou, Sudhakar Govindavajhala and Andrew W. Appel, the authors have presented MulVAL, an end-to-end framework and reasoning system that conducts multihost, multistage vulnerability analysis on a network. This article gives an overview of this model and some possible uses of its outputs.

MulVAL has adopted Datalog, a logical programming language, as the modelling language for the elements in the analysis (bug specification, configuration description, reasoning rules, operating-system permission and privilege model, etc.). It can easily leverage existing vulnerability-database and scanning tools by expressing their output in Datalog and feeding it to the MulVAL reasoning engine. Once the information is collected, the analysis can be performed in seconds for networks with thousands of machines.


The information in the vulnerability database provided by the bug-reporting community, the configuration information of each machine and the network, and other relevant information are all encoded as Datalog facts. The reasoning engine consists of a collection of Datalog rules that capture the operating system behavior and the interaction of various components in the network. Following are the various inputs used to perform the analysis in the model:

  • Advisories: vulnerabilities that have been reported, their effects and existence on the machine.
  • Host configuration: software and services running on the hosts, and their configurations.
  • Network configuration: configurations of the network routers and firewalls.
  • Principals: users of the network.
  • Interaction: interaction model of the network components.
  • Policy: permitted accesses.


Open Vulnerability Assessment Language (OVAL) is used here. A scanner runs on each host that uses the formalized OVAL definition schema to test the machine for vulnerable software. The result of the test is converted into Datalog clauses like the following:

vulExists(webServer, ’CVE-2002-0392’, httpd)

This says that the scanner identified a vulnerability with CVE-ID ’CVE-2002-0392’ in the server program httpd on the machine webServer.

The effect of the vulnerability, i.e. how it can be exploited and what is the consequence, is  fetched from the NVD Database provided by NIST and converted to datalog clauses such as:

vulProperty(’CVE-2004-00495’, localExploit, privEscalation)

This says that the vulnerability with CVE-ID ’CVE-2004-00495’ is locally exploitable and leads to privilege escalation.

Host Configuration:

MulVAL scanner is implemented by augmenting a standard OVAL scanner so that it also outputs machine configuration information by using the OVAL’s system characteristics schema. This is useful for reasoning about about multistage attacks. Some of the predicates used about machine configuration:

networkService(Host, Program, Protocol, Port, Priv).
clientProgram(Host, Program, Priv).
setuidProgram(Host, Program, Owner).
filePath(H, Owner, Path).
nfsExport(Server, Path, Access, Client).
nfsMountTable(Client, ClientPath, Server, ServerPath).

networkService describes the port number and protocol under which a service program is listening and the user privilege it has on the machine.
clientProgram describes the privilege of a client program when executed.
setuidProgram specifies an a setuid executable on the system and its owner.
filePath specifies the owner of a particular path in the file system.
nfsExport describes which portion of the file system on an NFS server is exported to a client.
nfsMountTable describes an NFS mounting table entry on the client machine.

Network Configuration:

MulVAL models network (router and firewalls) configurations as abstract host access-control lists (HACL). This information can be provided by a firewall management tool.

hacl(internet, webServer, TCP, 80).

This HACL entry allows TCP traffic to flow from internet to port 80 on webServer.

Binding Information:

1) Principal Binding:

Each datalog clause here maps a principal symbol to its user accounts on network hosts and is provided manually:

hasAccount(user, projectPC, userAccount).
hasAccount(sysAdmin, webServer, root).

2) Data Binding:

Each datalog clause here maps a data symbol to a path on a machine and this information is also provided manually:

dataBind(webPages, webServer, ’/www’).

Interaction Rules:

Semantics of vulnerability and operating system determine an adversary’s options in each stage. These are encoded as Horn clauses, where the first line is the conclusion and the remaining lines are the enabling conditions. They are represented as follows: L0 :- L1, . . . . , Ln which semantically means if L1, . . . . ,Ln are true then L0 is also true. 

Rule for remote exploit of a service program:

execCode(Attacker, Host, Priv) :-       
vulExists(Host, VulID, Program),
vulProperty(VulID, remoteExploit, privEscalation),
networkService(Host, Program, Protocol, Port, Priv),
netAccess(Attacker, Host, Protocol, Port),

This rule can be applied to any vulnerability that matches the pattern.


A policy describes which user can have what kind of access to what data. Anything which is not explicitly mentioned here is prohibited. This information is also provided manually.

allow(Everyone, read, webPages).
allow(user, Access, projectPlan).
allow(sysAdmin, Access, Data).
The main analysis algorithm has two essential parts: attack simulation and policy checking.

Attack Simulation: All possible data accesses that can result from multistage, multihost attacks are derived using the following program:

access(P, Access, Data) :-
dataBind(Data, H, Path),
accessFile(P, H, Access, Path).

The attack simulation happens in the derivation of accessFile , which involves the Datalog interaction rules and data tuple inputs from various components of MulVAL.

Policy Checking: Data access tuples output from the above step are compared with the given security policy. If an access is not allowed by the policy, a violation is detected using the following program:

policyViolation(P, Access, Data) :-
access(P, Access, Data),
not allow(P, Access, Data).

The entire MulVAL framework is depicted in the following schematic diagram:



Consider a simple network topology where there are three zones (internet, dmz and internal) separated by two firewalls (fw1 and fw2). The administrators manage the webserver, the workStation and the fileserver. The users have access to the public server workStation which they use for their computing needs. This is shown in the following figure:
Example Network

Network Topology:
hacl(internet, webServer, tcp, 80).
hacl(webServer, fileServer, rpc, 100003).
hacl(webServer, fileServer, rpc, 100005).
hacl(fileServer, AnyHost, AnyProtocol, AnyPort).
hacl(workStation, AnyHost, AnyProtocol, AnyPort).
hacl(H, H, AnyProtocol, AnyPort).

Machine configuration:
networkService(webServer , httpd, tcp , 80 , apache).
nfsMount(webServer, ’/www’, fileServer, ’/export/www’).
networkService(fileServer, nfsd, rpc, 100003, root).
networkService(fileServer, mountd, rpc, 100005, root).
nfsExport(fileServer, ’/export/share’, read, workStation).
nfsExport(fileServer, ’/export/www’, read, webServer).
nfsMount(workStation, ’/usr/local/share’, fileServer, ’/export/share’)

workStation represents many machines managed by the administrators running the same software configuration. Application binaries are maintained under /export/share on fileServer so that any change like recompilation of an application program needs to be done only once. These binaries are exported through NFS to the workStation.

Data binding:
dataBind(projectplan, workStation, ’/home’).
dataBind(webPages, webServer, ’/www’).

Principal binding:
hasAccount(user, workStation, userAccount).
hasAccount(sysAdmin, workStation, root).
hasAccount(sysAdmin, webServer, root).
hasAccount(sysAdmin, fileServer, root).
hasAccount(attacker, internet, root).

Security policy:
allow(Anyone, read, webPages).
allow(user, AnyAccess, projectPlan).
allow(sysAdmin, AnyAccess, Data).

Vulnerabilities found using the scanner:
vulExists(webServer, ’CVE-2002-0392’, httpd).
vulExists(fileServer, ’CVE-2003-0252’, mountd).

Effects of vulnerabilities:
vulProperty(’CVE-2002-0392’, remoteExploit, privEscalation).
vulProperty(’CVE-2003-0252’, remoteExploit, privEscalation).

Based on the above inputs provided to the MulVAL reasoning engine, following are the list of policy violations returned by the model for the above network:

Adversary = attacker
Access = read
Resource = projectPlan;

Adversary = attacker
Access = write
Resource = webPages;

Adversary = attacker
Access = write
Resource = projectPlan;

In addition to the list of policy violations, this model also has the capability to generate attack traces for each policy violation. Following is one such attack trace for the first policy violation mentioned above:

|-- policyViolation(attacker,read,projectPlan)
  |-- dataBind(projectPlan,workStation,/home)
  |-- accessFile(attacker,workStation,read,’/home’)
  Rule: execCode implies file access
    |-- execCode(attacker,workStation,root)
    Rule: Trojan horse installation
      |-- malicious(attacker)
      |-- accessFile(attacker,workStation,write,’/sharedBinary’)
      Rule: NFS semantics
        |-- nfsMounted(workStation,’/sharedBinary’,fileServer,’/export’,read)
        |-- accessFile(attacker,fileServer,write,’/export’)
            Rule: execCode implies file access
          |-- execCode(attacker,fileServer,root)
          Rule: remote exploit of a server program
            |-- malicious(attacker)
            |-- vulExists(fileServer,CVE-2003-0252,mountd,remoteExploit,privEscalation)
            |-- networkServiceInfo(fileServer,mountd,rpc,100005,root)
            |-- netAccess(attacker,fileServer,rpc,100005)
            Rule: multi-hop access
              |-- execCode(attacker,webServer,apache)
              Rule: remote exploit of a server program
                |-- malicious(attacker)
                |-- vulExists(webServer,CVE-2002-0392,httpd,remoteExploit,privEscalation)
                |-- networkServiceInfo(webServer,httpd,tcp,80,apache)
                |-- netAccess(attacker,webServer,tcp,80)
                  Rule: direct network access
                    |-- located(attacker,internet)
                    |-- hacl(internet,webServer,tcp,80)
              |-- hacl(webServer,fileServer,rpc,100005)
            |-- localFileProtection(fileServer,root,write,/export)
          |-- localFileProtection(workStation,root,read,/home)
        |-- not allow(attacker,read,projectPlan)

An attacker can compromise webServer by remotely exploiting CVE-2002-0392 to get control of web server through which he can compromise fileServer by exploiting CVE-2003-0252 and become root on the server. He can then modify arbitrary files on fileServer. The integrity of executable binaries on workStation mounted on fileServer will be compromised. An innocent user will execute the compromised client program which will give the attacker access to workStation and the files stored on it would also be compromised. An attacker can read the project plan leading to a policy violation. One way to fix this violation is moving webPages to webServer and blocking inbound access from DMZ zone to internal zone.


Following are the different ways in which the output of the above model can be used in enhancing the security of the information technology stack of an organization:

  • MulVAL creates attack traces which can be used to generate logical attack graphs which would give us all possible attack paths. 
  • The graphs would have attack nodes linking preconditions to postconditions of an attack. Each of these would be assigned the conditional probability of attack success given that all the preconditions are met, hence converting the graphs into Bayesian belief networks.
  • These probabilities can be aggregated over the attack graph to obtain a cumulative metric for each attack path.
  • Above metric can be used along with Control Dependency Chart to figure out control effectiveness in order to choose between different controls.
  • It can also be used to choose which vulnerabilities should be patched first by looking at their impact and the time required for the patch.
  • The probabilistic metrics can be used in combination with Threat Profiling to obtain updated maturity scores. We can identify the threat communities which would prefer to target a particular set of nodes.
  • Attack graphs can enable attack simulation by considering all possible attack paths and identifying the ones with highest likelihood and risk for the given network. We can also point out different steps in the path at which the given network is safe/vulnerable.
  • We can analyze zero-day vulnerabilities using the attack graph and get a metric that looks at the minimum number of zero-day vulnerabilities that need to be exploited across any path in the graph.
  • Attack graphs can also indicate the key critical attack assets which contribute to a large number of attack paths leading to high-risk conversion.
  • They can also aid in the creation of appropriately placed honeypots and optimal placement of monitors to observe unruly traffic.

The MulVAL model can automatically integrate with formal vulnerability specifications from bug reports. The reasoning engine scales well with the size of the network. It can handle networks with thousands of hosts in less than a minute. It is able to reason about privilege escalation and denial of service vulnerabilities. Modularity and simplicity of the design allows it to leverage existing tools and databases. Small size and declarative style of the interaction rules makes them easy to understand, debug and augment. Also, derivation in datalog is a process of accumulating facts which are polynomial in the size of the network and hence the algorithm is efficient. Thus, it's a great way to do network vulnerability analysis automatically and efficiently.

  • MulVAL: A Logic-based Network Security Analyzer: Xinming Ou, Sudhakar Govindavajhala, Andrew W. Appel
  • A Scalable Approach to Attack Graph Generation: Xinming Ou, Wayne F. Boyer, Miles A. McQueen

No comments:

Powered by Blogger.