Google patents malware scanner that maps software call patterns

1. A method comprising: generating API-call graphs from binaries of a software package, wherein generating the API-call graphs comprises converting control flow graphs of the binaries into directed acyclic graphs by condensing mutually recursive functions into nodes; computing n-grams of a customizable length from the API-call graphs, wherein computing the n-grams comprises: merging nodes of each API-call graph that are connected by epsilon transitions to form an acyclic graph, topologically ordering the nodes of the acyclic graph, and recursively annotating each node with arrays of n-grams representing sequences of API calls along paths in the acyclic graph; adding the n-grams to an inverted index that maps each of the n-grams to a respective identifier of the API-call graphs to enable locating of individual API-call graphs; identifying, from among the API-call graphs based on the n-grams, a set of candidate API-call graphs that match a signature, the signature comprising a set of n-grams that represents a sequence of calls and is represented as a non-deterministic finite automaton (NFA) with epsilon-moves, the signature representing behavior of potentially harmful code; retrieving the set of candidate API-call graphs from the inverted index; comparing, using a matching algorithm, the set of candidate API-call graphs to the NFA representing the behavior of potentially harmful code by computing, for each candidate API-call graph, a synchronized product automaton whose set of states is the cartesian product of the states of the NFA and the states of the candidate API-call graph, and whose transitions comprise: (i) epsilon moves for either automaton, and (ii) synchronized transitions on matching input symbols; and determining, via a graph traversal of the synchronized product automaton, whether any candidate API-call graph matches the behavior of potentially harmful code, and in response to a match, indicating that the software package potentially contains harmful code.