Method, product and apparatus for monitoring for security threats from lateral movements. A method comprises obtaining a graph of network lateral movements, that comprises nodes, representing network assets, and directed edges, representing a network lateral movement from a source asset to a target asset. An event that affects the graph of network lateral movements is detected. The event affects at least one of: the payload utility of the node and the probability of penetration to the node. The graph of network lateral movements is updated based on the event. The updated graph is analyzed to determine one or more mitigation actions to be applied. The one or more mitigation actions are applied automatically, manually or the like.