Embodiments detect unauthorized access to cloud-based resources. One technique analyzes cloud-based events to distinguish potentially malicious velocity incidents from benign velocity incidents. A velocity incident occurs when the same user causes events from two geographically remote locations in a short time. Benign velocity incidents are distinguished from malicious velocity incidents by comparing an event with past events that have the same features. Embodiments probabilistically determine if a velocity incident is malicious or benign based on a weighted multi-feature analysis. For each feature of an event, a probability is calculated based on past events that have the same feature. Then, each feature is associated with a weight based on a relative frequency of past events having that feature. A weighted average of probabilities is calculated, and the resulting probability is compared to a defined threshold to determine if the velocity incident is likely malicious or benign.