# US 2017/0249460 A1 · Provably secure virus detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0249460 A1
- Document ID: US20170249460A1
- Status: Published application
- Kind: A1
- Application number: 15/513,556
- Filed: 2015-09-23
- Published: 2017-08-31
- Earliest claimed: 2014-09-23
- Assignees: The Regents of the University of California
- Applicants: The Regents of the University of California; Georgia Tech Research Corporation
- Inventors: Richard J. Lipton; Rafail Ostrovsky; Vassilis Zikas
- Web page: https://patentgrep.com/patent/US20170249460A1

## CPC

- G06F 21/54: by adding security routines or objects to programs
- G06F 21/566: {Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities}
- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 2221/2103: Challenge-response
- G06F 2221/2115: Third party
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

We present the first provably secure defense against software viruses. We hide a secret in the program code in a way that ensures that, as long as the system does not leak information about it, any injection of malware will destroy the secret with very′-high probability. Once the secret is destroyed, its destruction and therefore also the injection of malware will be quickly detected.

## Claims

### Claim 1

A computer-implemented method for compiling an original program into a modified program that is resistant to virus injection, the original program stored as words in a computer memory, the method comprising:
inserting a plurality of key shares for a key set at memory locations between the original program words, wherein the key set comprises one or more secret keys, and the key set is lost if any of the key shares are modified; and
modifying the original program so that execution of the modified program produces a same result as execution of the original program;
wherein virus injection into a contiguous block of words will modify at least one key share with high probability, and executing a challenge-response protocol based on the key set will verify whether any of the key shares has been modified.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 wherein the modified program can be proven to detect any virus injection into a contiguous block of N or more words, where N is a preselected integer greater than or equal to 3.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2 wherein N=3.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1 wherein inserting the plurality of key shares comprises inserting key shares between original program words so that not more than N original program words will be contiguous in the modified program, where N is a preselected integer.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4 wherein inserting the plurality of key shares comprises inserting key shares between original program words so that no original program words are contiguous in the modified program.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1 wherein inserting the plurality of key shares comprises inserting key shares at random memory locations between original program words.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 wherein inserting the plurality of key shares comprises:
spreading out the original program words to create unused memory locations between the original program words; and
inserting key shares at the unused memory locations.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1 wherein inserting the plurality of key shares comprises inserting key shares so that not more than M key shares is inserted between original program words, where M is a preselected integer.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8 wherein inserting the plurality of key shares comprises inserting key shares so that not more than two key shares is inserted between original program words.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8 wherein inserting the plurality of key shares comprises inserting key shares so that not more than one key share is inserted between original program words.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1 wherein modifying the original program comprises inserting instructions to jump over memory locations storing key shares.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11 wherein inserting instructions to jump over memory locations storing key shares comprises inserting jump instructions immediately after original program words.

### Claim 13 (depends on 1)

The computer-implemented method of claim 1 wherein modifying the original program comprises modifying addresses for jump instructions in the original program to account for changes in addresses resulting from insertion of the key shares.

### Claim 14 (depends on 1)

The computer-implemented method of claim 1 wherein the key set comprises at least two secret keys, and the challenge-response protocol prevents simultaneous existence of all secret keys.

### Claim 15 (depends on 1)

The computer-implemented method of claim 1 further comprising:
inserting message authentication codes (MACs) at memory locations between the original program words, each MAC authenticating associated program words using associated key shares.

### Claim 16 (depends on 15)

The computer-implemented method of claim 15 wherein, upon execution of the modified program, a fetch cycle of the program execution will fetch one or more program words, the associated MAC and the key shares associated with the MAC, wherein the fetched program words can be authenticated using the fetched MAC and key shares.

### Claim 17 (depends on 16)

The computer-implemented method of claim 16 wherein the fetch cycle fetches a predefined number of words from memory, the predefined number of words including a fixed number of program words, a fixed number of words of key shares, and the MAC.

### Claim 18 (depends on 15)

The computer-implemented method of claim 15 wherein the MAC is a hash of a combination of the associated program words with a hash of the associated key shares.

### Claim 19 (depends on 1)

The computer-implemented method of claim 1 wherein the original program is binary code, inserting the plurality of key shares comprises inserting the plurality of key shares between words of the binary code, and modifying the original program comprises modifying the binary code.

### Claim 20 (depends on 1)

The computer-implemented method of claim 1 wherein the program includes instructions and data.

### Claim at position 21

21-40. (canceled)
