Binary search of byte sequences using inverted indices
View Patent ↗Techniques for searching an inverted index associating byte sequences of a fixed length and files that contain those byte sequences are described herein. Byte sequences comprising a search query are determined and searched in the inverted index, and an intersection of the results is determined and returned as a response to the search query. Further, search queries in the form of expressions including search terms and logical operators are searched in the inverted index and evaluated using a syntax tree constructed based on the logical operators. Also, byte sequences comprising a file are searched in the inverted index and results of the search are used to generate signatures and fuzzy hashes.
1. One or more non-transitory computer-readable media having stored thereon programming instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:
for each byte sequence of a fixed length comprising a file, searching an inverted index which specifies byte sequences of the fixed length and, for each specified byte sequence, file identifiers of files that include the specified byte sequence;
identifying a subset of search results of the searching that are associated with the fewest numbers of file identifiers; and
constructing a fuzzy hash from byte sequences comprising the subset of the search results.
2. The one or more non-transitory computer-readable media of claim 1 , wherein the byte sequences of the fixed length are n-grams with a length of four bytes.
3. The one or more non-transitory computer-readable media of claim 1 , wherein the searching further comprises determining the byte sequences of the fixed length comprising the file.
4. The one or more non-transitory computer-readable media of claim 1 , wherein the identifying is based at least in part on a relatedness confidence threshold.
5. The one or more non-transitory computer-readable media of claim 4 , wherein the relatedness confidence threshold is determined based on a desired level of confidence that a particular byte sequence appears in a particular file and one or more variants of the particular file but not in other files.
6. The one or more non-transitory computer-readable media of claim 1 , wherein the operations further comprise providing the fuzzy hash to a security service.
7. The one or more non-transitory computer-readable media of claim 1 , wherein the fewest numbers of file identifiers are greater than zero.
8. The one or more non-transitory computer-readable media of claim 1 , wherein the byte sequences comprising the subset of the search results used to construct the fuzzy hash have a second length that is different than the fixed length.
9. A computer-implemented method comprising:
for each byte sequence of a fixed length comprising a file, searching an inverted index which specifies byte sequences of the fixed length and, for each specified byte sequence, file identifiers of files that include the specified byte sequence;
identifying a subset of search results of the searching that are associated with the fewest numbers of file identifiers; and
constructing a fuzzy hash from byte sequences comprising the subset of the search results.
10. The computer-implemented method of claim 9 , wherein the byte sequences of the fixed length are n-grams with a length of four bytes.
11. The computer-implemented method of claim 9 , wherein the searching further comprises determining the byte sequences of the fixed length comprising the file.
12. The computer-implemented method of claim 9 , wherein the identifying is based at least in part on a relatedness confidence threshold.
13. The computer-implemented method of claim 9 , further comprising providing the fuzzy hash to a security service.
14. The computer-implemented method of claim 9 , wherein the byte sequences comprising the subset of the search results used to construct the fuzzy hash have a second length that is different than the fixed length.
15. A computing device comprising:
one or more processors; and
memory storing computer-executable instructions that, when executed by the one or more processors, perform operations comprising:
for each byte sequence of a fixed length comprising a file, searching an inverted index which specifies byte sequences of the fixed length and, for each specified byte sequence, file identifiers of files that include the specified byte sequence;
identifying a subset of search results of the searching that are associated with the fewest numbers of file identifiers; and
constructing a fuzzy hash from byte sequences comprising the subset of the search results.
16. The computing device of claim 15 , wherein the byte sequences of the fixed length are n-grams with a length of four bytes.
17. The computing device of claim 15 , wherein the searching further comprises determining the byte sequences of the fixed length comprising the file.
18. The computing device of claim 15 , wherein the identifying is based at least in part on a relatedness confidence threshold.
19. The computing device of claim 15 , wherein the operations further comprise providing the fuzzy hash to a security service.
20. The computing device of claim 15 , wherein the byte sequences comprising the subset of the search results used to construct the fuzzy hash have a second length that is different than the fixed length.