Modeling Attacks in Prolog

I've been tinkering this week with the use of first-order logic as a way of modeling network attacks. It turns out not to be too difficult at all, if you know a language like Prolog. In my case, it's been over 20 years since I'd programmed in that language - and I hadn't done anything serious in it back then anyway - so I had to pull out the textbooks and start banging the axons and dendrites together. It turns out that two of my old Prolog books relate to LPA MicroProlog (which I used to run on CP/M!) and the third is the second edition of Clocksin & Mellish from 1984. I discovered that the language has changed a bit since then. I also found a copy of Borland Turbo Prolog, but since I don't have a 5 1/4" drive in a machine, I'm not even going to bother.

So I downloaded SWI-Prolog (http://www.swi-prolog.com) and installed it on both Linux and Windows systems. A few experiments and a couple of days of head-scratching later (most of it down to using a hyphen in a term in one place, and an underscore in another - doh!) I'm making some progress. Here's a simple example:

We define information assets as being managed by program/products which have vulnerabilities. An attacker can use an exploit against these vulnerabilities. Controls (patches, firewalls, IPS, etc.) remove or defend against the vulnerabilities and protect the programs. Now it becomes quite easy to state some facts and rules:

%% Facts
%% A more sophisticated approach would build these from CVE

%% Example: X11.org X font server has three vulns
%% has_vulnerability(Program, Vuln)
has_vulnerability(xfs,cve-2007-2103).
has_vulnerability(xfs,cve-2007-4568).
has_vulnerability(xfs,cve-2007-4990).

%% Postulate some exploits for these vulns
%% exploits(Vuln,Exploit)
exploits(cve-2007-2103, attack-tool-1).
exploits(cve-2007-4568, attack-tool-2).
exploits(cve-2007-4990, attack-tool-3).
exploits(cve-1000-0001, attack-tool-4).

%% Some controls, safeguards, (patches?)
%% removes_vulnerability(Control, Vuln)
removes_vulnerability(patch-xfs-1, cve-2007-2103).
removes_vulnerability(patch-xfs-2, cve-2007-4568).

%% Programs are protected by controls or patches
%% protects(Control, Program)
protects(patch-xfs-1, xfs).

%% Assets are managed by programs
%% manages(Program, Asset)
manages(xfs,fonts).

%% Some rules
%% An asset A is vulnerable to an exploit E if
%% the asset is managed by a product X which has vulnerability Y
%% and exploit E exploits vulnerability Y
%% and the program is protected by control C which remove vulnerability Y

vulnerable(Asset,Exploit) :-
manages(Program,Asset),
exploits(Vuln,Exploit),
has_vulnerability(Program,Vuln),
protects(Control, Program),
not(removes_vulnerability(Control, Vuln)).

Loading this into SWI-Prolog, one can now ask some questions, like:

22 ?- [approach4].
% approach4 compiled 0.00 sec, 0 bytes

Yes
23 ?- vulnerable(fonts,X).

X = attack-tool-2 ;

X = attack-tool-3 ;

No

This indicates that the fonts (a slightly silly asset, but I just happened to pick three vulnerabilities in xfs) are vulnerable to attack-tool-2 and attack-tool-3. Attack-tool-1 cannot exploit cve-2007-2103 because there's a (hypothetical) patch for it.

This approach needs to be extended quite a lot to be useful. The two obvious first extensions are a) an automatic loading of program/product vulnerabilities and exploits, perhaps from CVE and b) a model of the system under examination, perhaps as a graph relating assets, program/products and the controls which defend them. It would then be possible to have the system identify which controls are redundant or which patches need to be applied.

Another extension relates to the fact that some controls are themselves programs/products which may have their own vulnerabilities. An attack could therefore consist of a sequence of exploits which defeat or disable multiple levels of controls.

I guess now it's time to hit the books and coax SWI-Prolog into reading CVE from the XML, as well as representing the system as a graph.