We ask the question: can network problems experienced by applications be identified based on symptoms contained in a network packet trace? An answer in the affirmative would open the doors to many opportunities, including nonintrusive monitoring of such problems on the network and matching a problem with past instances of the same problem. To this end, we present Deja vu, a tool to condense the manifestation of a network problem into a compact signature, which could then be used to match multiple instances of the same problem. Deja vu uses as input a network-level packet trace of an application’s communication and extracts from it a set of features. During the training phase, each application run is manually labeled as GOOD or BAD, depending on whether the run was successful or not. Deja vu then employs a novel learning technique to build a signature tree not only to distinguish between GOOD and BAD runs but to also sub-classify the BAD runs, revealing the different classes of failures. The novelty lies in performing the sub-classification without requiring any failure class-specific labels. We evaluate Deja vu in the context of the multiple web browsers in a corporate environment and an email application in a university environment, with promising results. The signature generated by Deja vu based on the limited GOOD/BAD labels is as effective as one generated using full-blown classification with knowledge of the actual problem types.