Behavior based signatures for identifying applications are generated. An application is monitored as it runs. Specific behaviors concerning the execution of the application are detected, and a behavior based signature representing detected behaviors is created, such that the behavior based signature can be used subsequently to identify instances of the application. Behavior based signatures identifying known malicious and/or non-malicious applications can be used to determine whether other applications comprise malware. To do so, a running application is monitored, and specific behaviors concerning the execution of the application are detected. The detected behaviors are compared to one or more behavior based signatures. Responsive to whether the detected behaviors match, a behavior based signature, it can be determined whether the application comprises malware. An additional malware detection test, such as a heuristic analysis, can also be performed and used in determining whether the application comprises malware.