US-12619401-B2 - Protecting and attesting program executions through shadow programs

US12619401B2US 12619401 B2US12619401 B2US 12619401B2US-12619401-B2

Abstract

A computer-implemented method for remotely attesting program executions includes obtaining, by a verifier computing entity, a program associated with an original program, for example a shadow program. The method further includes obtaining, by the verifier computing entity, collected information associated with control-flow operations executed by an instrumented program, wherein the instrumented program is a variation of the original program. The verifier computing entity executes the program associated with the original program based on the collected information, and checks an output of the program associated with the original program.

Inventors

Felix Klaedtke

Assignees

NEC Laboratories Europe GmbH

Dates

Publication Date: 20260505
Application Date: 20240116

Claims (16)

1 . A computer-implemented method for remotely attesting program executions, comprising: obtaining, by a verifier computing entity, a program associated with an original program; obtaining, by the verifier computing entity, collected information associated with control-flow operations executed by an instrumented program, wherein the instrumented program is a variation of the original program; executing, by the verifier computing entity, the program associated with the original program based on the collected information; and checking, by the verifier computing entity, an output of the program associated with the original program.
2 . The computer-implemented method of claim 1 , wherein obtaining the program associated with the original program comprises obtaining a shadow program that mimics a control flow of the original program, and wherein executing the program associated with the original program comprises executing the shadow program based on the collected information.
3 . The computer-implemented method of claim 2 , wherein a prover computing entity comprises a first execution environment and a second execution environment, wherein the first execution environment executes the instrumented program and invokes a tracer from the second execution environment to collect the collected information in an attestation blob, and wherein the prover computing entity provides the attestation blob comprising the collected information to the verifier computing entity.
4 . The computer-implemented method of claim 2 , further comprising: building the instrumented program by incorporating one or more trampolines into the original program, wherein each of the one or more trampolines is associated with the control-flow operations of the original program; and building the shadow program by modifying the control-flow operations of the original program.
5 . The computer-implemented method of claim 4 , wherein building the instrumented program comprises: including a new initialization step within the original program, wherein the new initialization step is configured to establish a connection to a tracer of a trusted environment of a prover computing entity; including one or more attestation steps within the original program, wherein the one or more attestation steps are configured to notify the tracer of a request and notify the tracer of completion of the request; and modifying a server request step by incorporating the one or more trampolines.
6 . The computer-implemented method of claim 5 , wherein the one or more trampolines is associated with a conditional branch instruction from the original program, and wherein the collected information indicates a truth value of the conditional branch that is obtained based on the one or more trampolines calling a first library function and invoking the tracer.
7 . The computer-implemented method of claim 5 , wherein the one or more trampolines is associated with an indirect call or jump instruction from the original program and a return instruction from the original program, and wherein the collected information indicates a target address that is obtained based on the one or more trampolines a second library function and invoking the tracer and a return address that is obtained based on the one or more trampolines a third library function and invoking the tracer.
8 . The computer-implemented method of claim 2 , wherein executing the shadow program comprises: initializing one or more memory address mappings between the shadow program and the instrumented program; awaiting an attestation blob comprising the collected information; and based on receiving the attestation blob from the verifier computing entity, attesting execution of the instrumented program by a prover computing entity.
9 . The computer-implemented method of claim 8 , wherein initializing the one or more memory address mappings comprises: obtaining a first mapping that translates target addresses of indirect calls and jumps of the instrumented program to corresponding target addresses of the shadow program; and obtaining a second mapping that translates return addresses of the shadow program to corresponding return addresses of the instrumented program.
10 . The computer-implemented method of claim 9 , wherein attesting the execution of the instrumented program comprises: translating one or more addresses between the shadow program and the original program based on at least one of the first mapping and the second mapping, and wherein checking the output of the shadow program is based on translating the one or more addresses.
11 . The computer-implemented method of claim 8 , wherein attesting the execution of the instrumented program comprises: based on detecting a conditional branch instruction, executing a first call function to obtain a truth value associated with the conditional branch instruction from the attestation blob; performing a test-and-branch instruction based on the truth value to test the conditional branch; and determining a result of the test of the conditional branch, wherein the output of the shadow program indicates the result of the test.
12 . The computer-implemented method of claim 8 , wherein attesting the execution of the instrumented program comprises: based on detecting an indirect call or jump instruction, executing a second call function to read a next target address into a register from the attestation blob, translate the next target address into a corresponding target address of the shadow program, and return the corresponding target address in a register; based on detecting a return instruction, executing a third call function to translate a return address of the shadow program into a corresponding return address of the instrumented program, update a hash value with the corresponding return address, and comparing the hash value with a hash value from the attestation blob; and determining one or more results of the indirect call or jump instruction and the return instruction based on executing the second call function and the third call function.
13 . The computer-implemented method of claim 2 , wherein the verifier computing entity is a controller that coordinates operation of at least one of: a plurality of robotic devices, a plurality of internet of things (IoT) devices, and a cloud server, and wherein, based on the output of the shadow program, one or more instructions are provided to reset the at least one of: the plurality of robotic devices, the plurality of IoT devices, and the cloud server.
14 . The computer-implemented method of claim 1 , wherein obtaining the program associated with the original program comprises: obtaining the original program or the instrumented program; and using an interpreter that directly uses the original program or the instrumented program, and wherein executing the program associated with the original program comprises using the interpreter that replays and checks an execution of the instrumented program based on the collected information.
15 . A computer system for remotely attesting program executions, the system comprising one or more hardware processors, which, alone or in combination, are configured to provide for execution of the following steps: obtaining a program associated with an original program; obtaining collected information associated with control-flow operations executed by an instrumented program, wherein the instrumented program is a variation of the original program; executing the program associated with the original program based on the collected information; and checking an output of the program associated with the original program.
16 . A tangible, non-transitory computer-readable medium having instructions thereon which, upon being executed by one or more processors, alone or in combination, provide for execution of a method for remotely attesting program executions comprising the following steps: obtaining a program associated with an original program; obtaining collected information associated with control-flow operations executed by an instrumented program, wherein the instrumented program is a variation of the original program; executing the program associated with the original program based on the collected information; and checking an output of the program associated with the original program.

Description

CROSS-REFERENCE TO PRIOR APPLICATION Priority is claimed to U.S. Provisional Application Ser. No. 63/602,669 filed on Nov. 27, 2023, the entire contents of which is hereby incorporated by reference herein. FIELD The present invention relates to a method, system, data structure, computer program product and computer-readable medium for protecting and attesting program executions. BACKGROUND In Internet-of-Things (IoT) deployments and in cloud computing, computations are often carried out on various devices that are remote to each other and many of them operate in untrusted environments. For instance, in IoT applications, devices are often deployed at untrusted locations, where they record data or perform actions that are requested by a remote controller. Analogously, in cloud computing, data centers often host services from multiple entities, which neither trust each other nor the data center owner. These services may store and analyze sensitive data. A compromised device or service may forge data or hijack operations, which can lead to all sorts of system malfunctions, including data leakage, ill-classifications, outages, and device defects. SUMMARY In an embodiment, the present disclosure provides a computer-implemented method for remotely attesting program executions. The method includes obtaining, by a verifier computing entity, a program associated with an original program, for example a shadow program. The method further includes obtaining, by the verifier computing entity, collected information associated with control-flow operations executed by an instrumented program, wherein the instrumented program is a variation of the original program. The verifier computing entity executes the program associated with the original program based on the collected information, and checks an output of the program associated with the original program. BRIEF DESCRIPTION OF THE DRAWINGS Embodiments of the present invention will be described in even greater detail below based on the exemplary figures. The present invention is not limited to the exemplary embodiments. All features described and/or illustrated herein can be used alone or combined in different combinations in embodiments of the present invention. The features and advantages of various embodiments of the present invention will become apparent by reading the following detailed description with reference to the attached drawings which illustrate the following: FIG. 1 illustrates a setting of an embodiment of the present invention; FIG. 2 illustrates a system and threat model according to an embodiment of the present invention; FIG. 3 illustrates the components of the system according to an embodiment of the present invention; FIG. 4 illustrates the build process of an instrumented program and a shadow program according to an embodiment of the present invention; FIG. 5 illustrates the flow diagram of the original program; FIG. 6 illustrates the flow diagram of the instrumented program; FIG. 7 illustrates the flow diagram of the shadow program; FIG. 8 illustrates the target and return address mappings between the instrumented program and the shadow program according to an embodiment of the present invention; FIG. 9 illustrates the control-flow graph (with its basic blocks) of the function apply of the original program; FIG. 10 illustrates the apply function of the instrumented program; FIG. 11 illustrates the control-flow graph with its basic blocks of the abstracted apply function from the shadow program; FIG. 12 illustrates the first example of the monitor's underlying finite-state machine; FIG. 13 illustrates the second example of the updated finite-state machine; and FIG. 14 is a block diagram of an exemplary processing system, which can be configured to perform any and all operations disclosed herein. DETAILED DESCRIPTION Embodiments of the present invention provide an approach to protect and attest the executions of programs, which can detect control-data attacks as well as non-control-data attacks. During program execution, information about the execution is collected, which is then checked with a so-called shadow program by a trusted entity. Shadow programs are program abstractions with a matching control-flow graph, but with a much simpler state space omitting irrelevant details and using less computational resources. Embodiments of the present invention provide solutions to the technical challenge of verifying that requested operations are performed properly to protect remote entities against manipulations from compromised devices and services. In particular, embodiments of the present invention enable to identify disruptive operations and allow entities to take appropriate countermeasures. For instance, data from the respective service or device can be flagged as potentially corrupted. Additionally, and/or alternatively, the device or service can be reset or quarantined. The approach for attesting the operations of a remote device or service accordin