Deriving malware signatures by training a binary decision tree using known malware and benign software samples, each tree node representing a different software feature set and having one descending edge representing samples that are characterized by the node's software feature set and another descending edge representing samples that are not characterized thusly, selecting multiple continuous descending paths for multiple subsets of nodes, each path traversing a selected one of the edges descending from each of the nodes in its corresponding subset, deriving, based on the nodes and edges in any of the paths, a malware-associated software feature signature where the malware samples represented by leaves that directly or indirectly descend from an end of the continuous descending path meets a minimum percentage of the total number of samples represented by the leaves, and providing the malware signatures for use by a computer-based security tool configured to identify malware.