Device and method for providing code blocks to a client during execution of software code

TECHNICAL FIELD

0001The present disclosure relates generally to computer systems and in particular to providing software code for execution on a client.

BACKGROUND

0002This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present disclosure that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present disclosure. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.

0003The frequency of patching of software code - i.e. modification of deployed software code to implement new features, correct errors, etc. - has increased over the last few years. While some patches may have little importance, other patches like security patches can be critical and be implemented immediately.

0004Hot swapping enables modification of the code of a program without having to interrupt execution. This technique however is used for hardware components such as disks, memory, USB components and is thus not suitable when the hardware is not changed.

0005Patching software that is not currently executed is easy as it may suffice to simply put the patch in place after which the code has been updated. However, patching software code that is executed is trickier. This may be a big problem as it is relatively common for software to run for a long time, for example game consoles are often used for hours on end, or even without end such as on gateways, security systems and even because the user does not switch off the computer to avoid wasting time when it starts again.

0006A known way to patch running code is to require restart of the machine the code runs on. An obvious drawback is that this interrupts program execution.

0007Hot patching and memory injection are hacking techniques that allow partial modification of running code by injection of code in the memory. The technique is described, in French, by Fred Raynal and Jean-Baptiste Bedrune in "Malicious Debugger!" Sogeti IS/ESEC. However, there is a high risk of program crash, mainly due to the use of a so-called ptrace system call and the overwriting of previous memory space. In addition, languages with dynamic call dispatching (e.g., Java) are able to support redefinition of the code supporting some classes, but only at the granularity of classes. Hence, some code like main loops of threads cannot be hot patched.

0008The game consoles PS4 and XBoX1 allow "play without all game", which means that game execution can start before all of the code has been downloaded. While this in a sense can be said to modify the code that is executed, it does not allow patching of the downloaded code. Similar possibilities exist with P2P progressive download.

0009None of the techniques allows fine grained modification of code during execution without restart. In particular, many of these techniques require user patience during the update. Further, some techniques require that the program is either stop or aware of the on-going patching operation.

SUMMARY OF DISCLOSURE

0010In a first aspect, the present principles are directed to a server device for providing blocks of code of a program to a client device executing the blocks of code. The server device comprises an interface configured to relay messages between the client device and a processor of the server device and the processor configured to receive from the client device a request comprising an identifier of a block of code, obtain a subsequent block of code corresponding to the identifier, obtain at least one transition for the subsequent block of code, the transition enabling the client to calculate an identifier of a block of code to request following execution of the subsequent block of code, and send the subsequent block of code and the transition for the subsequent block of code to the client.

0011Various embodiments of the first aspect include: <ul id="ul0001" list-style="bullet" compact="compact"><li>That the server device further comprises memory configured to store blocks of code and identifiers of blocks of code provided to the client and transitions provided to the client, and that the processor is configured to store identifiers of blocks of code provided to the client in the memory. The processor can be configured to send the subsequent block of code and the transition for the subsequent block of code to the client if the memory does not store the identifier of the request, and, if the memory stores the identifier of the request, to send to the client an indication that a block of code corresponding to the identifier has been provided. The processor can also be configured to determine whether the subsequent block of code has been replaced by an updated block during the client's execution of the program and, in this case, to determine whether a memory patch is needed at the client, wherein if no memory patch is needed, the subsequent block is the updated block, and, if a memory patch is needed, the subsequent block of code is a block configured to patch the memory when executed and for which the transitions lead to the updated block.</li><li>That the processor is further configured to compute a set of blocks of code that can be requested by the client and to provide the subsequent block to the client when the identifier in the request corresponds to one of the blocks of the set of blocks. The processor can be configured to compute the set of blocks of code using at least one method from the group of: partial evaluation, block prediction, speculative execution and memoization.</li><li>That the processor is further configured to communicate with the client device over an encrypted channel.</li></ul>

0012In a second aspect, the present principles are directed to a method for providing blocks of code of a program to a client device executing the blocks of code, the method comprising at a server device comprising a processor: receiving from the client device a request comprising an identifier of a block of code, obtaining a subsequent block of code corresponding to the identifier, obtaining at least one transition for the subsequent block of code, the transition enabling the client to calculate an identifier of a block of code to request following execution of the subsequent block of code, and sending the subsequent block of code and the transition for the subsequent block of code to the client.

0013Various embodiments of the first aspect include: <ul id="ul0002" list-style="bullet" compact="compact"><li>That the server device further comprises memory configured to store blocks of code and identifiers of blocks of code provided to the client and transition provided to the client, and that the method further comprises storing an identifier of the subsequent block of code in the memory. The sending the subsequent block of code and the transition for the subsequent block of code to the client can be performed if the memory does not store the identifier of the request, and the method comprises, if the memory stores the identifier of the request, sending to the client an indication that a block of code corresponding to the identifier has been provided. The method can further comprise determining whether the subsequent block of code has been replaced by an updated block during the client's execution of the program and, in this case, determining whether a memory patch is needed at the client, wherein: if no memory patch is needed, the subsequent block is the updated block, and, if a memory patch is needed, the subsequent block of code is a block configured to patch the memory when executed and for which the transition lead to the updated block.</li><li>That the method further comprises computing a set of blocks of code that can be requested by the client and wherein the subsequent block is sent to the client when the identifier in the request corresponds to one of the blocks of the set of blocks. Computing the set of blocks of code can include using at least one method from the group of: partial evaluation, block prediction, speculative execution and memoization.</li></ul>

0014In a third aspect, the present principles are directed to a client device for receiving blocks of code of a program from a server device, the client device comprising an interface and a processing unit configured to execute a block of code, calculate, using at least one transition for the block of code received from the server device, an identifier of a subsequent block of code, transmit to the server device, via the interface, a request comprising the identifier of a subsequent block of code, receive from the server device, via the interface, the subsequent block of code and at least one transition for the subsequent block of code, the at least one transition enabling the processing unit to calculate an identifier of a block of code to request following execution of the subsequent block of code.

0015In a fourth aspect, the present principles are directed to a method for receiving blocks of code of a program from a server device, the method comprising at a client device executing by a processing unit a block of code, calculating by the processing unit, using at least one transition for the block of code received from the server device, an identifier of a subsequent block of code, transmitting by the processing unit, via an interface of the client device, to the server device, a request comprising the identifier of a subsequent block of code, and receiving from the server device, via the interface, the subsequent block of code and at least one transition for the subsequent block of code, the at least one transition enabling the processing unit to calculate an identifier of a block of code to request following execution of the subsequent block of code.

BRIEF DESCRIPTION OF DRAWINGS

0016Preferred features of the present principles will now be described, by way of non-limiting example, with reference to the accompanying drawings, in which <ul id="ul0003" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> illustrates an example system implementing an embodiment in accordance with the present principles; and</li><li><figref idref="f0002">Figure 2</figref> illustrates an example method for execution of code in an embodiment in accordance with the present principles.</li></ul>

DESCRIPTION OF EMBODIMENTS

0017It should be understood that the elements shown in the figures may be implemented in various forms of combinations of hardware and software. Preferably, these elements are implemented in a combination of hardware and software on one or more appropriately programmed general-purpose devices, which may include a processor, memory and input/output interfaces. Herein, the phrase "coupled" is defined to mean directly connected to or indirectly connected with through one or more intermediate components. Such intermediate components may include both hardware and software based components.

0018The present description illustrates the principles of the present disclosure. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the disclosure and are included within its scope.

0019All examples and conditional language recited herein are intended for educational purposes to aid the reader in understanding the principles of the disclosure and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions.

0020Moreover, all statements herein reciting principles, aspects, and embodiments of the disclosure, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.

0021Thus, for example, it will be appreciated by those skilled in the art that the block diagrams presented herein represent conceptual views of illustrative circuitry embodying the principles of the disclosure. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

0022The functions of the various elements shown in the figures may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" or "controller" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, read only memory (ROM) for storing software, random access memory (RAM), and nonvolatile storage.

0023Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the figures are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context.

0024In the claims hereof, any element expressed as a means for performing a specified function is intended to encompass any way of performing that function including, for example, a) a combination of circuit elements that performs that function or b) software in any form, including, therefore, firmware, microcode or the like, combined with appropriate circuitry for executing that software to perform the function. The disclosure as defined by such claims resides in the fact that the functionalities provided by the various recited means are combined and brought together in the manner which the claims call for. It is thus regarded that any means that can provide those functionalities are equivalent to those shown herein.

0025<figref idref="f0001">Figure 1</figref> illustrates an example system 100 implementing an embodiment in accordance with the present principles. The system 100 comprises a client 110 configured to execute software code and a server 120 configured to provide the software code to the client 110. Although only illustrated for some of the devices, each device 110, 120 comprises at least one hardware processing unit ("processor") 111, 121, memory 112, 122 and at least one communications interface 113, 123 configured to communicate with the other device. The skilled person will appreciate that the illustrated devices are very simplified for reasons of clarity and that real devices in addition would comprise features such as internal connections and power supplies. The client processor 111 is configured to request and execute blocks of code, the server processor 121 is configured to respond to such requests, as will be described. A non-transitory storage medium 130 stores instructions that, when executed by a processor, perform the TCP handshake method at the terminator device described hereinafter.

0026The processor 111 of the client is configured to execute the software code. The software code is arranged in a series of blocks B, preferably so-called basic blocks, and the software code is arranged so that it is sufficient for the client 110 to store only the presently executed basic block at a given time.

0027Formally, the code can be represented as a Control Flow Graph (CFG) comprising all possible paths that can be traversed through the code during execution. The code is split into a set of disjoint blocks B and a set of oriented transitions between blocks <i>T: int</i> x <i>int.</i> With this definition, a CFG is defined by <i>CFG: B</i> × <i>T</i> where(<i>B_i</i>, <i>T_i</i>) ∈ <i>CFG</i> wherein <i>B_i</i> is a block of code corresponding to the program and <i>T_i</i> is set of available transitions from this block.

0028<figref idref="f0002">Figure 2</figref> illustrates an example method for execution of code in an embodiment in accordance with the present principles. When the client 110 wants to start execution of a program, it requests, step S20, the first block <i>B</i>₀ and the corresponding transitions <i>T</i>₀ towards blocks that will be available after executing <i>B</i>₀ from the server 120 that responds, step S21, with the first block <i>B</i>₀ and the transitions <i>T</i>₀. The client 110 then executes, step S22, block <i>B</i>₀ and, sometime during execution (preferably at the end the block), calculates, step S23, the next block <i>B_i</i> using one transition in the set <i>T</i>₀.

0029More generally, at any time (except for during transitions between blocks), the client 110 has the current block <i>B_i</i> and the set of corresponding transitions <i>T_i</i> where all t ∈ <i>T_i</i> have the form (<i>i,*</i>)<i>,</i> calculates the next block <i>B_k</i>, requests this from the server 120 that in turn provides the requested block <i>B_k</i> and the corresponding transition in the set <i>T_k</i>. In each t = (<i>i</i>,<i>*</i>) ∈ <i>T_i</i>, the <i>i</i> is the index of the source block and the asterisk is an identifier for a possible target block <i>B_k</i>. While the number of available transitions usually is greater than one (|<i>T_i</i>| > 1), it may also be zero if execution stops with the current block (<i>T_i</i> = 0̸) or one if the next block is predetermined (|<i>T_i</i>| = 1) (an example being shown hereinafter).

0030The server 120 is configured to store, for each client c, the spatial indices (or other identifier) of each block already executed by the client X<i>_c</i>: {<i>int</i>}. Initially, X<i>_c</i> = {0}. The memory 122 advantageously also stores the blocks of software code, but it will be appreciated that the blocks can also be stored in external memory (not shown) accessible by the server 120.

0031Thus, the client 110 requests, step S24, block <i>B_k</i> from the server 120 that sends, step S25, <i>B_k</i> and <i>T_k</i>, and updates, step S26, X<i>_c</i> u= {<i>j</i>}. The client 110 executes, step S27, the received block <i>B_k.</i>

0032Now, in order to patch code running on a client, it is sufficient to patch (i.e. modify) the corresponding block(s). For ease of illustration, it is assumed that a single block <i>B_p</i> is modified to block <i>B_p'</i>. Ψ:int x int is the set of patches, where (<i>p,p'</i>) means that block <i>B_p</i> has been replaced by block<i>B_p'</i>. The server receives the new block <i>B_p'</i> and modifies the transition system to integrate the new block <i>B_p'</i> in place of the old block <i>B_p:</i> all (_*,<i>p</i>) are replaced by (_*, <i>p'</i>), and all (p,*) are replaced by (<i>p'</i>,_*). Depending on the block modifications, it may be necessary to patch the memory 112 of the client 110 too. In this case, a complement block <maths id="math0001"><math display="inline"><mrow><msub><mi>B</mi><mrow><msubsup><mi>p</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub></mrow></math><img file="EP3086226A1_D0001.tif" /></maths> to <i>B_p'</i> is added in order to modify the client memory 112 to be compatible with the new block <i>B_p'.</i>

0033Then, whenever a client requests a block <i>i</i>, there are a number of possibilities: <ul id="ul0004" list-style="bullet" compact="compact"><li><i>B_i</i> has not been patched (since the client started execution of the program), i.e. ∄ (i,*) ∈ Ψ. In this case, the server sends<i>B_i</i> and <i>T_i</i> and computes X<i>_c</i> u= {<i>i</i>} as already described.</li><li><i>B_i</i> has been patched during the client's execution of the program, i.e ∃ (<i>i, i'</i>) ∈ Ψ: <ul id="ul0005" list-style="dash" compact="compact"><li>In case the client has executed the memory patch block <maths id="math0002"><math display="inline"><mrow><msub><mi>B</mi><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub><mo>,</mo></mrow></math><img file="EP3086226A1_D0002.tif" /></maths> i.e. <maths id="math0003"><math display="inline"><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup><mo>∈</mo><msub><mi mathvariant="normal">X</mi><mi>c</mi></msub><mo>,</mo></mrow></math><img file="EP3086226A1_D0003.tif" /></maths> then the server sends <i>B_i'</i> and <i>T_i'</i>, and computes X<i>_c</i> u= {<i>i'</i>}.</li><li>In case the client has not executed the memory patch block <maths id="math0004"><math display="inline"><mrow><msub><mi>B</mi><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub><mo>,</mo></mrow></math><img file="EP3086226A1_D0004.tif" /></maths> i.e. <maths id="math0005"><math display="inline"><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup><mo>∉</mo><msub><mi mathvariant="normal">X</mi><mi>c</mi></msub><mo>,</mo></mrow></math><img file="EP3086226A1_D0005.tif" /></maths> then the server sends <maths id="math0006"><math display="inline"><mrow><msub><mi>B</mi><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub></mrow></math><img file="EP3086226A1_D0006.tif" /></maths> and the transition <maths id="math0007"><math display="inline"><mrow><msub><mi>T</mi><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub><mo>=</mo><mfenced open="{" close="}"><mfenced separators=","><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup><mi mathvariant="italic">iʹ</mi></mfenced></mfenced><mo>,</mo></mrow></math><img file="EP3086226A1_D0007.tif" /></maths> and computes <maths id="math0008"><math display="inline"><mrow><msub><mi mathvariant="normal">X</mi><mi>c</mi></msub><mo>∪</mo><mfenced open="{" close="}"><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mfenced><mn>.</mn></mrow></math><img file="EP3086226A1_D0008.tif" /></maths>X<i>_c</i></li></ul></li></ul>

0034It will be understood that in the last case, using the notation of the example before, the client will execute the memory patch block <maths id="math0009"><math display="inline"><mrow><msub><mi>B</mi><mrow><msubsup><mi>i</mi><mi>m</mi><mi>ʹ</mi></msubsup></mrow></msub><mo>,</mo></mrow></math><img file="EP3086226A1_D0009.tif" /></maths> from which the transition will be <i>T_i'</i>, which will cause the client to request basic block <i>B_i'</i> from the server.

0035Thus, since the client can have a single block to execute at a time, the program can be patched without stopping the program or rebooting. A possible exception is if there is a need to patch a block that is currently executed and in which execution is at least temporarily stuck in a loop, which may occur if the execution idles such as when the client waits for some input that has not yet arrived.

0036It will be appreciated that if there is no need to patch the memory patch, then there is no need to store the indices of executed blocks X<i>_c</i>, to verify if the client has executed the block or to send the memory patch to the client.

0037It will also be appreciated that it is possible for the client to use a cache for the blocks, in particular those it has executed. Using cache techniques can help to optimize the transmission. For example, the client can then indicate in its request for a block that the block is stored in its cache, and the server can respond with OK (to use the version in cache) or, if for example the block has been patched, with a block to execute (which can be a patched version of the block or a block to patch the memory).

0038It will further be appreciated that the server can be configured to compute a set of possible blocks that the client can request (with <i>T_i</i> when it has sent the block <i>B_i</i>) and to verify that the requested block is in this list. A requested block is sent only if it is in the set of possible blocks. This measure can help against hacking.

0039It will further be appreciated that various conventional optimization methods including partial evaluation, block prediction, speculative execution and memoization (see for example http://en.wikipedia.org/wiki/Memoization) can be used by the server in order to optimize the selection and evaluation of blocks that are to be sent.

0040It will further be appreciated that it is preferred to provide authentication and confidentiality of exchanges using an encrypted channel such as the Secure Authenticated Channel (SAC) described in <patcit id="pcit0001" dnum="WO2006048043A"><text>WO 2006/048043</text></patcit>.

0041The following example further illustrates the present principles using a simple evolution of a program during execution. The evolution operates within the body of a loop, which stresses the fine granularity level allowed by an embodiment of the present principles.

Source code

0042<pre listing-type="program-listing"> public class XXX { public static void main(String[] args) { // TODO Auto-generated method stub int i=0,j=0; boolean b=true; while(b){ i++; if(j==3){ j++; i--; } } } }</pre>

Byte code

0043<pre listing-type="program-listing"> Compiled from "XXX.java" public class XXX { public XXX(); Code: 0: aload_0 1: invokespecial #8 // Method java/lang/Object."<init>":()V 4: return public static void main(java.lang.String[]); Code: 0: iconst_0 // i 1: istore_1 // i 2: iconst_0 // j 3: istore_2 // j 4: iconst_1 // b 5: istore_3 // b 6: goto 23 9: iinc 1, 1 // i++ 12: iload_2 // if (j 13: iconst_3 // 3 14: if_icmpne 23 // == 17: iinc 2, 1 // j++ 20: iinc 1, -1 // i-- 23: iload_3 24: ifne 9 27: return }</pre>

0044In the example, instruction 17 in the body of the loop is changed and new instructions are inserted. The set of blocks B is the set of instructions 17 to 21. The set of transition corresponds to the sequential execution: 17→18, 18→19, until 20→21. <ul id="ul0006" list-style="none" compact="compact"><li>17: iinc 2, 2 // j++</li><li>18: iload_1</li><li>19: iconst_2 // 2</li><li>20: imul // *2</li><li>21: istore_1</li></ul>

0045Each time an instruction is added, all subsequent instructions and instruction references are renumbered accordingly. It is noted that the machine executing the code does not need to be aware of the renumbering when instruction caching techniques are not used.

0046In the most basic version of an embodiment of the present principles, each instruction is requested from the server before execution; in other words, a block equals one instruction. The code can evolve on the instruction level at the price of a penalty on the execution speed. It will be appreciated that common caching techniques can mitigate the speed penalty. For instance, the code evolution can be requested every two instructions, in association with a rollback mechanism.

0047The skilled person will appreciate that the present principles can be used in various contexts: <ul id="ul0007" list-style="bullet" compact="compact"><li>They can allow continuous code update of network connected devices. This can be advantageous for network connected devices with embedded code, typically home gateways and set-top-boxes. Without the present principles, such devices apply network updates using for instance the TR-069 protocol. This may induce unavailability and reboot of the devices. The present principles apply particularly well to network devices with embedded code because they are always connected to the network (when switched on) and because the embedded code is small: replacement blocks can be small as well, thus mitigating the execution speed penalty.</li><li>The present principles can be advantageous for casual console gamers. Video game consoles liked Microsoft Xbox, Sonny PS4, etc. spend time updating code and rebooting. The user must wait for the patch, even though the code contained in this patch will not be executed in the subsequent gaming session. Using the present principles: the patched code can be downloaded only when necessary and no reboot is then necessary. As mentioned, the cost is a longer execution time, which can be mitigated through the use of common caching techniques.</li><li>The present principles can be used for anti-dumping. Some security contexts require that the memory never stores the full program code. This requirement is sometimes called anti-dumping and is common with obfuscated programs. The present principles can be used as an anti-dumping measure, by constantly replacing executed sequences of instructions. In particular, the size of the code section of a program executed according to the present principles can be constant and relatively small.</li><li>The present principles can allow starting code execution as soon as the first instruction is received, whereas, generally, software code is fully downloaded before its execution starts.</li><li>The present principles can be used to save memory since the memory footprint of the code can be reduced. Some devices, like small computing devices such as, for example, the raspberry pi, have network connectivity but very constrained memory (e.g. 512 Mb). The present principles can then be used to reduce the size of code in memory, at the price of an increased number of network requests. Doing so can allow execution of a code that virtually exceeds the memory size of the device.</li></ul>

0048It will thus be appreciated that the present principles provide a solution for code execution that, at least in certain cases, can improve on the prior art code execution solutions.

0049Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features described as being implemented in hardware may also be implemented in combinations of hardware and software, and vice versa. Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.