Method of detecting malicious code

Malicious code in a code-executing device is detected by generating test data, which is substantially unsusceptible to compression without reducing its information content, and storing it as image data in memory external to the device. The test data is stored into memory of the device. A checksum calculation is performed on the test data stored in the memory of the device to generate a first checksum value. A corresponding checksum calculation is performed on the image data to generate a second checksum value. The first value is compared with the second value to determine whether or not the test data in the memory of the device has been corrupted. These steps are repeated until sufficient test data in the memory of the device is checksum tested to determine whether or not malicious code is present in the device. The malicious code is difficult to conceal itself from the checksums. Hence, it is possible to determine whether or not the device has been compromised.

The present invention is concerned with a method of detecting malicious code in a code-executing device, in particular but not exclusively in a computer. The invention also relates to a test apparatus operating according to the method.

Malicious code, for example computer viruses, frequently causes severe problems in contemporary code-executing systems. Such malicious code can remain dormant after initially being loaded and then, when activated, potentially result in extensive damage to the integrity of data and executable software stored in the systems.

There are presently available a number of techniques for verifying the authenticity of executable code, for example by encrypting the executable code and then decrypting it before use, and by the use of authentication signatures using private or public key cryptography. These techniques are employed to prevent unauthorised executable code being loaded into systems and executed therein. However, if an encryption code or a private key is stolen from its legitimate owner and comes into the possession of a third party, the third party can generate malicious code which will verify correctly against decryption codes and corresponding public keys.

The inventors have appreciated that malicious code gives rise to first and second problems. The first problem is concerned with countermeasures to prevent malicious code being loaded into code-executing systems. The second problem is concerned with determining whether or not a code-executing device loaded with executable code has been compromised where doubt exists regarding the authenticity of the code. For example, in a scenario where it is suspected that malicious code has been loaded into a code-executing system, proceeding to execute the code could wreak costly damage to valuable databases accessible from the code-executing system. Conversely, resetting and subsequently reprogramming the code-executing system could itself be a costly exercise entailing the return of the system to its manufacturer. Moreover, in many circumstances, it will be essential to know whether or not an attempt has been made to distribute malicious code which has passed authentication procedures such as public keys so that other protection measures can be pursued, for example purging devices of malicious code.

The inventors have also appreciated that malicious code can often be constructed in cunning ways to occupy very little memory space in code-executing devices and only use significant internal device memory, or external memory accessible from the device, when the malicious code is active. Trying to detect such malicious code can be very difficult especially when it becomes embedded in seemingly bona fide executable code which, for a majority of the time, appears to be functioning correctly.

Thus, the invention sets out to provide a method of detecting when malicious code has been loaded into code-executing devices.

According to a first aspect of the present invention, there is provided a method of detecting malicious code in a code-executing device, the method characterised in that it includes the steps of:(a) generating test data which is substantially unsusceptible to compression without reducing its information content and storing it as image data in memory external to the device;(b) loading the test data into memory of the device;(c) performing a checksum calculation on the test data stored in the memory of the device to generate a first checksum value, performing a corresponding checksum calculation on the image data to generate a second checksum value, and then comparing the first value with the second value to determine whether or not the test data in the memory of the device has been corrupted;(d) repeating step (c) until sufficient test data in the memory of the device is checksum tested to determine whether or not malicious code is present in the device.

The method provides the advantage that calculating checksum values for the test data in the memory of the device and comparing with corresponding checksum values calculated for the image data enables malicious code residing in the memory of the device to be detected.

Insusceptibility of the test data to compression prevents any malicious code residing in the memory of the device from concealing its existence by compressing the test data. It is especially preferable that the test data includes one or more random number sequences; random number sequences are by their nature not capable of being compressed without loss of associated information.

Conveniently, the method additionally includes a step of interrogating the device to make it divulge names of software applications stored therein prior to performing step (b) to overwrite the applications in the memory of the device.

When the method has been applied to establish that the device is devoid of malicious code, it is preferable that uncorrupted versions of the software applications divulged by the device are loaded into the device after step (d). Such loading of uncorrupted software enables the device to be returned to its former state prior to applying the method.

In order to make it more difficult for any malicious code residing in the device to predict checksum values required when executing the method, it is beneficial that checksum calculations performed in step (c) are performed on one or more sequences of memory locations of the memory of the device in response to challenges issued to the device, each challenge specifying memory locations of the device to be checksummed using a cryptographic checksum calculation and also one or more associated initialization vectors with which to commence the calculation. Because the malicious code cannot predict the memory locations chosen or the initialization vector used in the method, it is more difficult for the malicious code to pre-compute checksum values and then compress the test data to conceal its presence.

Advantageously, to make it more difficult for the malicious code to conceal itself, the aforementioned one or more sequences may skip memory locations therein. Such location skipping provide the benefit that the memory of the device can be tested in several different ways, thereby making it more difficult for the malicious code to conceal itself.

It is preferable that at least one checksum calculation in step (c) is performed on interfacing software residing in the memory of the device, the interfacing software operable to communicate the test data to the memory of the device and to output data from the memory of the device, the interfacing software also being included in the image data for comparison. Such testing of the interfacing software assists to reduce a risk of malicious code residing therein.

Beneficially, the method makes use of the rapidity with which the device outputs checksum calculations to determine whether or not the memory of the device includes malicious code. If malicious code is present, more processing steps will often be required for the code to conceal its identity from checksum calculations.

Preferably, when testing the device according to the method, the device should be hindered from accessing memory external thereto during calculation of the checksums in step (c). If the device is capable of communicating with such external memory, it is possible for malicious code to conceal its identity by residing in such external memory or, alternatively, to store test data in the external memory to conceal the code's presence within the device.

In step (c), it is preferable that a cryptographic hash algorithm is used for calculating the checksums. Checksums generated by cryptographic hash algorithms are difficult to mimic and hence the use of such algorithms makes it more difficult for malicious code to hide its presence within the device. Examples of suitable cryptographic hash algorithms are:(a) “MD5” defined in an Internet Engineering Task Force (IETF) document RFC 1321, “The MD5 Message-Digest Algorithm” (1992); and(b) “SHA-1” defined in National Institute of Standards and Technology (NIST) documents “FIPS Publication 180: Secure Hash Standard (SHS)”, (1993) and also in “Announcement of Weakness in the Secure Hash Standard” (1994).

In a second aspect of the invention, there is provided a testing apparatus operable to apply a method according to the first aspect of the invention to interrogate a code-executing device to determine whether or not the device includes malicious code.

Referring now toFIG. 1, there is shown hardware of a code-executing device indicated by10. The device10includes an enclosure20, a main memory30, a code-executing processor40and an associated random access memory (RAM)50. The RAM50, the processor40and the main memory30are electrically or optically interconnected such that the processor40can access and store data in the RAM50and the main memory30. The device10further includes an electrical or optical interface60for communicating to a network70external to the device10. The network70can, for example, be a testing device or, alternatively, be a network of interconnected computing devices.

When the device10is a portable code-executing device, the RAM50typically includes 256 bytes of data storage capacity. Moreover, the main memory30is typically implemented in the form of an E2PROM non-volatile memory including 8 Mbytes of data storage capacity. Furthermore, the processor40is typically implemented as an 8-bit or 16-bit microcontroller including a bidirectional buffer port providing the interface60.

The device10can also, alternatively, be a large computer where the processor40comprises an array of interconnected digital processors, the RAM50comprises many Gbytes of solid state data storage capacity, and the main memory30includes optical, magnetic and solid state data storage media of many Gbytes storage capacity.

In operation, the external network70communicates to the device10through the interface60. When the network70sends executable-code to the device10, the device10stores the code in the main memory30. Additionally, the processor40can be instructed to store specific items of data or output specific items of data from its main memory30, with or without processing applied thereto depending upon circumstances. The main memory30is operable to retain data stored therein, for example even in the event of power to the device10being removed.

The manner in which the device10is configured with regard to executable code, namely software, will now be described with reference toFIGS. 1 and 2. Executable code, namely applications1to n where n is a positive integer not including zero, is stored in the main memory30and loaded into the device10through the interface60which operates under software control of an executable-code object100known as a handler. The handler100handles all flow of data and executable code between the network70and the main memory30and RAM50.

When the device10is operating in conjunction with the network70, the network70can access the main memory30via the handler100. Alternatively, the network70can instruct the handler100to start execution of one or more of the applications on the processor40, the handler100executing concurrently with the one or more executing applications for handling data flow to and from the device10.

It is thus only possible for the network70to communicate to and from the device10via the handler100in normal circumstances.

Prior to loading an application into the device10, the application is signed by its supplying party using the party's private key to ensure its authenticity. The network70, and also if necessary the handler100, is then operable to verify the application using a public key corresponding to the private key. Such a procedure of authentication reduces a risk of the device10loading into its main memory30unauthorised rogue applications.

The use of private and corresponding public key pairs for authenticating software is well known, the keys being in the from of codes. The codes are such that one code of the pair cannot reasonably be generated merely from knowledge of the other code of the pair. When a supplying party supplies a software application to the network70for recording into the device10, the supplying party “signs” the application using one of its keys, the supplying party retaining this key secret as its “private key” which it does not divulge to the network70. However, the supplying party divulges the other of its keys of the pair to the network70and therefrom to the device10, this being known as the supplying party's “public key”. Thus, the public key provided by the supplying party can be used by the network70and the device10for verifying authenticity of applications signed using the private key belonging to the supplying party.

Generation of private and public keys is known from a U.S. Pat. No. 4,200,770 which is hereby incorporated by reference with regard to the generation of complementary keys. The private and public keys are usually of about 200 bytes in length and can be generated using a mathematical transformation described in the U.S. patent.

Conventional “signing” of software applications using private keys will now be described in further detail.

In a first approach, “signing” involves encoding a software application in its entirety using a private key to generate a corresponding encoded application. The encoded application can be decoded using a corresponding public key to the private key. Other unrelated public keys will not be able to successfully decode the encoded software application to generate viable executable code for use in the device10. If the handler100discovers such non-viable executable code when performing decoding, the handler100thereby determines that the executable code is not authentic and should not be executed or retained in the main memory30.

In a second approach, “signing” involves calculating a cryptographic checksum for a software application using a checksum generation program known to both the supplying party and to the network70and the device10; known cryptographic checksum generating programs include “Message Digest 5” (MD5) and “Secure Hash Algorithm” (SHA or SHA-1). The checksum is relatively short, usually in a range of 16 to 20 bytes in length. The supplying party can use its private key for encoding a checksum generated using a public checksum generation program for its software application and then supply the software application unencoded together with the encoded checksum, sometimes referred to as a Message Authentication Code (MAC), to the network70and therefrom to the device10. When the network70receives the software application from the supplying party, the network70, and likewise the device10, can apply the public checksum generation program to generate an operator checksum for the unencoded software application. The network70and the device10can then decode the encoded checksum provided by the supplying party using the supplying party's public key to generate a decoded checksum which the network70and the device10then compare with their operator checksum. If the decoded checksum is identical to the operator checksum, the network70and the device10will thereby have determined that the software application is authentic. If the decoded checksum and the operator checksum are not identical, the network70and the device10will have identified that the software application is suspect.

The second approach to “signing” software applications is faster and involves less computation than the first approach because checksum generation is a computationally quick operation to perform and encoding a checksum of 16 to 20 bytes is easier than encoding software and data in its entirety which can be, for example, several tens of Megabytes in size.

When the term “signing” is used by the inventors to describe their invention, this is intended to refer to either signing by the first approach or signing according to the second approach as described above.

A problem can arise where a private key of a software application supplying party to the network70, and therefrom to the device10, is stolen by a third party. The third party is then able to prepare malicious code and sign it using the private key and supply the malicious code as a software application to the network70. Neither the network70nor the device10when checking the application for authenticity using their corresponding public key will be able to detect the malicious code.

If it subsequently becomes known that the private key has been stolen, software applications signed by the private key then become suspect as being malicious code. There then arises a problem of how to test the device10to determine whether or not its one or more software applications stored in its main memory30include malicious code.

When malicious code is loaded via the interface60and processor40into the device, the code can be stored in a number of ways, namely:(a) the malicious code can overwrite the handler100, or co-exist therewith in the main memory30, and function as a rogue handler mimicking the operation of the handler100but also performing functions to the benefit of the third party, for example transferring money from a bank account of a legitimate owner of the device10into a bank account held by the third party;(b) the malicious code can be stored as a software application and invocable from the network70by way of the handler100, the software application operable to perform an unauthorised function to the detriment of the owner of the device10; and(c) the malicious code can be stored as data which is operated upon by bona fide applications and the handler100stored in the main memory30, the data resulting in an unauthorised function being performed.

When the handler100is replaced by a malicious handler, the malicious handler is capable of concealing the presence of one or more third party malicious applications stored in the memory30when interrogated through the interface60from the network70. In such a situation, the device10will appear to be functioning correctly from the viewpoint of the network70. Continued use of the device10could result, for example, in expensive corruption of the network70and its associated databases. There is therefore a need for a method of detecting when suspect malicious code has been loaded into the device10, especially when private-public key authorisation procedures have been circumvented by the theft of private keys.

A method according to the invention of detecting when malicious code has been loaded into the device10will now be described with reference toFIGS. 3 and 4. InFIG. 3, the device10is shown in a configuration connected through the interface60to a testing apparatus200. In the configuration, the device10is deliberately arranged so that it is only capable of communicating with the apparatus200. Such a restricted communication is used to prevent malicious code present it the device10from communicating with other devices or using memory external to the device for concealing itself from the apparatus200.

In STEP A of the method, the device10including its handler100and its one or more software applications are connected to the apparatus200. The apparatus200then communicates through the interface60to the handler100and requests it to divulge a list210of applications stored within it. In some circumstances, the network70will itself keep a record of applications that have been loaded into the device10; however, such a record is not essential for performing the method of the invention. The handler100thus responds to the apparatus200by communicating the list210of the applications stored in the device10.

If the handler100has been corrupted to become a malicious handler, it could lie to the apparatus200and conceal the presence of one or more rogue applications stored in the device10as well as bona fide applications.

When the apparatus200has received the list210from the handler100, the apparatus200stores the list210in its own memory.

In STEP B of the method, the apparatus200transmits through the interface60a software application known as a testing handler220to the device10which stores it in specific locations of its main memory30. At this stage, the device10should only include its handler100, the testing handler220and any applications that the device has declared in the list210to the apparatus200.

If the device10has been compromised by malicious code, it may include applications not declared in the list210to the apparatus200and the handler100itself may comprise malicious code.

If the network70has its own list of applications that should be stored in the device10and this network70list is not in conformity with the list210, the apparatus200will thereby determine therefrom that the device10has been compromised by inclusion of presumed malicious additional code.

The apparatus200then proceeds to instruct the device10to run the testing handler220. Moreover, the apparatus200will know in advance which main memory30locations the handler100and the testing handler220should occupy. Memory30locations not occupied by these handlers100,220should therefore be available for storing software applications.

The apparatus200then generates a reference image230within its memory of how the main memory30of the device10should appear. Following the generation of the reference image230, the apparatus200generates a sequence of random numbers R0to Rmand fills locations of the reference image230not occupied by the handlers100,220with the random numbers. The apparatus200also passes these random numbers through the interface60to the testing handler instructing it to store the random numbers in locations in the main memory30corresponding to those of the reference image230.

Random numbers have the characteristic that they cannot be compressed without losing information content. Thus, if rogue applications are stored in the main memory30of the device10, and the handler100is a malicious handler, the malicious handler cannot compress the random numbers to conceal the presence of rogue applications because, as will be described later, such attempts at compressing the random numbers can be detected by the apparatus200.

The apparatus200continues to supply the random numbers to the device10via the testing handler210until all locations of the main memory30are filled except for those locations occupied by the handlers100,220.

In STEP C of the method, the apparatus200uses a procedure involving initialization vectors (IV) to interrogate the device10to test whether or not the random numbers R0to Rmhave been correctly recorded in the main memory30. If incorrect recording of the numbers is identified, such incorrect recording is indicative of the action of a rogue application or that the handler100has been compromised.

When interrogating the device10, the apparatus200sends a challenge via the interface60to the testing handler220. The challenge specifies a sequence of start locations within the main memory30and an initialisation vector (IV). The testing handler220then initializes its cryptographic hash algorithm with the supplied IV before feeding the contents of the sequence of specified locations in turn to this algorithm. The algorithm of the testing handler220calculates a resulting first checksum which is typically in the order of 128 or 160 bits in length. The testing handler220then, using an identical IV and an identical cryptographic hash algorithm to that supplied to the testing handler220, calculates a corresponding second checksum based on data stored in the reference image230. If the first and second checksums are not identical, the apparatus200determines thereby that the device10has been compromised. Conversely, if the first and second checksums are identical, the apparatus200interrogates the device10using other challenges. If necessary, the apparatus200can interrogate the whole of the main memory30include locations occupied by one or more of the handler100and the testing handler220. If the handler100has been compromised to be a malicious handler, the apparatus200will be able to detect such a compromise.

The apparatus200preferably interrogates the device10using numerous different initialization vectors and, if necessary, also specifies sequences of varying lengths for use in calculating associated checksums. Such multiple interrogation is effective to prevent a malicious handler in the device attempting to pre-compute checksums and then compress the random numbers as they are supplied to the device10in order to try to conceal the presence of rogue applications.

The sequences preferably include locations occupied by at least one the handler100and the testing handler220. Moreover, the sequences can optionally alternately skip one or more locations to make it more difficult for malicious code to conceal itself within the device10. Such skipping is illustrated by Sequences1and3inFIG. 4. Sequence2inFIG. 4corresponds to consecutive memory locations in the main memory30. Sequence3includes locations occupied by the handlers100,220.

If, after interrogating the device10with numerous mutually different initialization vectors, it is determined that the device10has not been compromised, the method proceeds to STEP D. If the device10has been compromised, an alarm is raised.

In STEP D of the method, the apparatus200optionally overwrites the testing handler220stored in the device10to prevent the executable code of this handler220being subsequently disclosed to an application subsequently executing on the device10, and then proceeds to load bona fide approved versions of applications as recorded in the list210. Such loading results in the device10including an uncompromised version of the handler100, one or more bona fide applications with remaining locations in the main memory30being filled with random numbers. The apparatus can, if required, optionally purge the memory30of random numbers prior to loading the one or more bona fide applications.

The method provides the benefit that the presence of malicious code within the device10can be detected even if applications signed by a stolen private key corresponding to a public key stored in the device10have been loaded into the device10. Moreover, the method also enables bona fide uncompromised applications to be reloaded into the device10at termination of the method thereby rendering the device10again useable.

The method of the invention will not be able to detect all possible malicious code. For example, where malicious code is capable of operating upon the handler100in uncompromised form, compressing it and then storing the compressed handler and the malicious code in memory space originally occupied by the uncompressed handler100, the method can be circumvented. However, the malicious code would have to be capable of interfacing with the testing handler to provide it with sequences of location values normally occupied by the uncompressed handler100when tested during Step C of the method. The testing apparatus200could, if necessary, be made sensitive to such compression by timing interrogation response from the device10; uncompressing code will take more time hence malicious code operating in such a manner can be detected by virtue of its slower than normal response.

It will be appreciated as described above that the device10can take many different forms. The aforementioned method of the invention is applicable to both where the device10is a portable personal item as well as where it is a complex computer installation.

It will also be appreciated to those skilled in the art that modifications can be made to the method of the invention without departing from the scope of the invention. For example, in Step B, the main memory30of the device10can be filled with alternative data other than random numbers provided that the alternative data is not susceptible to being undetectably compressed by any malicious code that may be present in the device10; compression of the alternative data would potentially provide the malicious code with memory space to continue its existence. Moreover, in Step C, the sequences of locations read for generating the checksums need not necessarily map out the main memory30in its entirety if a less thorough interrogation of the device10is acceptable. Furthermore, although use of a cryptographic hash algorithm for generating the checksums in Step C is described, other approaches for generating checksums can alternatively be used in combination with or in substitution for the cryptographic hash algorithm.

Although loading of the testing handler220into the device10is described, it is feasible for the handler100itself to be adapted so as to be capable of loading random numbers supplied from the testing device200into the main memory30in Step B, thereby circumventing a need for the testing handler220to be loaded into the device10.