A logic-programming approach to network security analysis (thesis)

Abstract:

An important problem in network security management is to uncover potential multistage, multihost attack paths due to software vulnerabilities and misconfigurations. This thesis proposes a logic-programming approach to conduct this analysis automatically. We use Datalog to specify network elements and their security interactions. The multihost, multistage vulnerability analysis can be conducted by an off-the-shelf logic-programming engine that can evaluate Datalog efficiently.

Compared with previous approaches, Datalog is purely declarative, providing a clear specification of reasoning logic. This makes it easy to leverage multiple third-party tools and data in the analysis. We built an end-to-end system, MulVAL, that is based on the methodology discussed in this thesis. In MulVAL, a succinct set of Datalog rules captures generic attack scenarios, including exploiting various kinds of software vulnerabilities, operating-system sematics that enables or prohibits attack steps, and other common attack techniques. The reasoning engine takes inputs from various off-the-shelf tools and formal security advisories, performs analysis on the network level to determine if vulnerabilities found on individual hosts can result in a condition violating a given high-level security policy.

Datalog is a language that has efficient evaluation, and in practice it runs fast in off-the-shelf logic programming engines. The flexibility of general logic programming also allows for more advanced analysis, in particular hypothetical analysis, which searches for attack paths due to unknown vulnerabilities. Hypothetical analysis is useful for checking the security robustness of the configuration of a network and its ability to guard against future threats. Once a potential attack path is discovered, MulVAL generates a visualized attack tree that helps the system administrator understand how the attack could happen and take countermeasures accordingly.