Partially Observable Contingent Planning for Penetration Testing

Dorin Shmaryahu, Tom Gonda, Joerg Hoffman, Guy Shani

28th International Workshop on Principles of Diagnosis (DX) (2017)

Penetration Testing (pentesting), where network administrators
automatically attack their own network to identify
and fix vulnerabilities, has recently received attention
from the AI community. Smart algorithms that can
identify robust and efficient attack plans may imitate
human hackers better than simple protocols. Classical
planning methods for pentesting model poorly the real
world, where the attacker has only partial information
concerning the network. On the other hand POMDPbased
approaches provide a strong model, but fail to
scale up to reasonable model sizes. In this paper we offer
a middle ground, allowing for partial observability
and non-deterministic action effects, by modeling pentesting
as a partially observable contingent problem. We
experiment with a real network of a large organization,
showing our solver to scale to realistic problem sizes.
We also experiment with sub-sampled networks, comparing
the expected reward of a contingent plan graph
to that of a POMDP policy.