The present invention relates to a method and system for the automated construction of application signatures. In one example, an approach for automatically constructing accurate signatures for individual applications, with minimal human involvement or application domain knowledge, is provided. Given a training data set containing the application traffic, the Automated Construction of Application Signatures (ACAS) system uses a combination of statistical, information theoretic and combinatorial optimization techniques, to derive application-layer signatures from the payload of packets, e.g., IP packets. Evaluations with a range of applications demonstrate that the derived signatures are very accurate and scale to identifying a large number of flows in real time on high-speed links.