  The ever-evolving capabilities of cyber attackers force security
administrators to focus on the early identification of emerging threats.
Targeted cyber attacks usually consist of several phases, from initial
reconnaissance of the network environment to final impact on objectives. This
paper investigates the identification of multi-step cyber threat scenarios
using kill chain and attack graphs. Kill chain and attack graphs are threat
modeling concepts that enable determining weak security defense points. We
propose a novel kill chain attack graph that merges kill chain and attack
graphs together. This approach determines possible chains of attacker's actions
and their materialization within the protected network. The graph generation
uses a categorization of threats according to violated security properties. The
graph allows determining the kill chain phase the administrator should focus on
and applicable countermeasures to mitigate possible cyber threats. We
implemented the proposed approach for a predefined range of cyber threats,
especially vulnerability exploitation and network threats. The approach was
validated on a real-world use case. Publicly available implementation contains
a proof-of-concept kill chain attack graph generator.
