A method and system for characterizing application layer flood denial-of-service (DDoS) attacks carried by advanced application layer flood attack tools. The method comprises receiving an indication on an on-going DDoS attack directed toward a protected entity; analyzing requests received during the on-going DDoS attack to determine a plurality of different attributes of the received requests; generating a dynamic applicative multi-paraphrase signature by clustering at least one value of the plurality of different attributes, wherein the multi-paraphrase signature characterizes requests with different attributes as generated by an advanced application layer flood attack tool executing the on-going DDoS attack; and characterizing each incoming request based on the multi-paraphrase signature, wherein the characterization provides an indication for each incoming request whether a request is generated by the attack tool.