Indexing software packages and detecting malicious or potentially harmful code using API-call n-grams

A computing device comprising a processor configured to:

• generate 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;
• compute 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;
• add then-grams to an inverted index that maps each of then-grams to a respective identifier of the API-call graphs to enable locating of individual API-call graphs;
• identify, 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;
• retrieve the set of candidate API-call graphs from the inverted index;
• and
• compare, 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.

A non-transitory computer-readable storage medium comprising instructions that, when executed, configure a processor of a computing device to:

• generate 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;
• compute 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;
• add then-grams to an inverted index that maps each of then-grams to a respective identifier of the API-call graphs to enable locating of individual API-call graphs;
• identify, 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;
• retrieve the set of candidate API-call graphs from the inverted index;
• and
• compare, 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.