text: a static analyzer is used on the client side to perform a basic block level data flow analysis of the binaries of the program whose remote execution has to be authenticated . this analysis derives and uses control flow probabilities into basic blocks as is routinely done in many modern optimizing compilers . ( a basic block is a set of consecutive instructions that does not have any branch .) the frequently called functions (“ call blocks ”) are first identified , and then the basic blocks within each such call block are analyzed . a call block is a series of basic block starting from the call instruction and ending with a ret instruction . detecting the dynamically linked functions is easy but deciding the critical local functions that are called frequently is not as easy . to identify the most critical basic blocks ; that is blocks with the higher execution frequencies , a jump tree that holds calls and indirect jump sequences for each call block is generated . an automated utility is provided to implement this step . this utility program generates the basic blocks , their call frequencies and constructs the jump table . for added flexibility , the framework permits the programmer to modify the critical basic block list produced by the analyzer . this static analysis identifies a full set of checkpoints within the most - likely control paths , located at the entry point to the most frequently executed basic blocks and ensures an acceptable level of coverage for verifying the control flow within the program as it executes . this analysis also generates information that can be incorporated into verifiable signatures at each of these checkpoints . this module is implemented as a system call , “ sys_startcheck ”, which selects a random subset of the checkpoints from the full set of such checkpoints , with the random selection specified by the verifier . this random selection also ensures that a good coverage of the control flow path . sys_startcheck ( ) is invoked once before application is run to request a challenge from the verification server . the verification server will respond with challenge that includes a randomly generated tag value ( hereafter called the session tag ) and a list of checkpoint locations . after receiving the checkpoint list , the original codes at checkpoints will be substituted with system call for signature generation and the original binary contents at each such location will be saved . these original contents are restored after successful signature generations and verifications at the checkpoints to enable the original executions to continue . the signature generator is implemented as another system call , “ sys_checkpoint ”, which is inserted , along with one or more additional instructions , by the call to “ sys_startcheck ” at each of the randomly - chosen checkpoints . a call to sys_checkpoint ( ) does the following : a ) collects the signature - specific information and generate the signature for the current checkpoint location . the exact nature of the signature can be chosen as described in section 4 . b ) encrypts and sends the signature combined with the session tag to the authentication server . c ) receives the response from the authentication server and take appropriate action depending on the response . the authentication server can send a new list of the checkpoint locations , or modify the existing list of checkpoint locations by adding or deleting checkpoint locations . d ) patches the original code in the previously passed checkpoint with a call to “ sys_checkpoint ” to permit signatures to be generated correctly if a signature generation is required at a future time at this previous checkpoint . the original bit sequence at the previous checkpoint &# 39 ; s location is saved before this patchup . e ) copies back the original binary contents to the current checkpoint location , change the processor &# 39 ; s program counter register &# 39 ; s ( e . g ., x86 eip register ) value appropriately and let the original execution continue until the next checkpoint . the challenge generator is called by the signature verifier component when needed . when the verification commences , the cs will wait on a challenge from the as . as this initial challenge , the as will send a list of randomly selected checkpoint locations , as described earlier . this random selection and enabling of checkpoints makes it very difficult to predict the sequence of signatures expected as responses to subsequent challenges by the as . in effect , the possibility of pre - executing the program on a remote host and generating the signatures in advance for later replay by the untrusted cs , in an effort to deceive the as , is dramatically reduced . to see this , suppose n call blocks are provided , and each call block has m basic blocks that are critical — that is , have high execution frequencies . the challenge generator will randomly select k basic blocks from these m basic blocks at the beginning of the challenge . therefore , the total number of different checkpoint locations in the checkpoint list will be equal to c ( m , k ) n where c ( x , y ) stands for the combination function . as an example if n = 200 , m = 10 , and k = 3 ( which are fairly representative of a small to medium - sized application ) then , the total number of different outcomes is ( 10 !/ 3 !×[ 10 − 3 ]!) 200 ≈ 1 . 2 × 10 400 . this low probability of predicting a specific random sequence of signatures makes it possible for the framework to certify typical remote executions as genuine . if this is not enough , the framework permits the as to alter the list of enabled checkpoints dynamically . in fact , as described in section 8 , a similar mechanism is used to handle checkpoint within loops and for reducing the associated performance penalty . according to one embodiment of the invention , the granularity of checkpoint insertion can be controlled based on responses from the signature verifier . thus , a response from the signature verifier may trigger insertion of additional checkpoints , or removal of checkpoints , from the series of instructions comprising the program . software code executing at the cs is therefore operative to modify the program , as appropriate . the as has corresponding signatures against which to verify execution in dependence on the controlled dynamic state of the cs . the crux of the authentication mechanism lies in the ability to characterize the unique , expected control flow signatures at dynamically and randomly chosen checkpoints from a set of pre - generated checkpoints . the signature at a checkpoint is multi - dimensional in nature and has various components that identify the execution path taken to the checkpoint as well as components that are indicative of the state of execution at the checkpoint . to derive a signature , a variety of information maintained in msr registers can be used , such as number of cache hits , stall cycle count , sequence of past few system calls and other such information . contents of general purpose registers can also be used as signature components . in general , a signature has some exact components ( specific register values , last few branch instruction addresses , last system call id ), as well as components (“ inexact values ”) that can be matched to expected values within a given range of deviations ( such as number of cache hit , committed instruction counts , stall cycle counts etc .). ( committed instruction counts are not exact ; program branches can cause variations .) because of these two diverse class of components in the signature , signature verification is not just a comparison for equality but rather a mix of comparison for equality and comparison for matched within a pre - specified range . the actual signature generated can also use constraints based on specific register values ( regular registers , not msrs ) and verify , for example , if the value of register x is strictly greater than the value of register y . in general , the more the number of components used in a control flow signature , the better are the chances of producing a unique signature for the control flow path to the point of verification . given the features of contemporary hardware , a variety of practically viable , robust and unique signatures may be defined for a checkpoint . a number of approaches for identifying and using exact and “ inexact ” components for a control flow signatures , that allow a unique control flow signature to be associated with a control flow path , are possible . the framework incorporating the present technology is , in fact , a generic framework , applicable to many different types of programmable devices with sufficient complexity to meet the presumption of a low probability that a specific state can be predicted and that specific state then counterfeited . typically , the class of problems addressed encompasses programmable systems in which the software environment is subject to change , and that unauthorized or unknown changes can prove hazardous or detrimental . systems which do not employ open software environments may use the technology , since these systems , which may be appliances , routers , or other pre - programmed devices may require authentication when they interoperate with other devices , or may within their own environment cause harm if tampered with , are modified , or suffer from hardware or software error . users are free to choose signature components and verification functions depending on the target application &# 39 ; s need . in the current implementation signature components chosen are unaffected by a context switch or process migration to another core . if components affected by a context switch are present , one solution will be to reinitialize them on context switches . the framework also permits dynamic changes to be made to the signature . the authentication server can change the signature generation function on the computation server at random intervals , adding to the overall resiliency of the scheme . an additional advantage of the ability to change the signature generating function has to do with improving both the coverage and the overall performance of the validation mechanism . for example , a low overhead signature may be used in non - critical parts of the code while detailed , high - coverage signatures are be used in critical portions of the code . one naïve way to implement assumption ( 3 ) of sec . 3 . 1 is to statically link the library modules with the binaries of the program being validated and validate the resulting binary using the framework . although , this approach works , it is not completely desirable , as all the advantages of dynamically linked libraries are lost . an alternative approach is to set up an interrupt handler to generate a signature on every m committed instructions where m is chosen at random and small enough for a good coverage and big enough for an acceptable performance penalty , as in [ cm 05 ]. this , of course , requires the timer interrupt mechanism to be validated using a dynamic root of trust or similar mechanisms . yet another approach for validating library functions will be to use the per - branch tracing mechanisms supported in some modern hardware to track each and every branch executed in the library code ( sec . 7 ). the implementation of the framework for which tests are reported below does not validate the library functions , though this of course could be done . note that this approach to validate the execution of library functions does rely on the use of some smaller ( and fixed ) components that are certified using a dynamic root of trust mechanism . this is still significantly better than validating these libraries before their execution using a dynamic root of trust mechanism that leaves out any run - time checks . finally , it is preferred not to verify the actual program using the approach just described for library functions , as the signature validation approach for the program is at a more finer - grained level and thus more robust . where a similar level of validation is necessary for the library functions , the practical choice will be to link them in statically with the program binaries and validate them like the rest of the program itself . 1 . ( cs side ) prior to commencing the actual execution , the cs connects to the verifier ( as , authentication server ) over a secure channel and sends a challenge request message to the as . 2 . ( as side ) as the initial challenge , the as will send a randomly generated tag and a list of the checkpoint locations which are selected from a full - set of pre - generated checkpoint locations ( sec . 3 . 3 . 1 ). 3 . ( cs side ) after receiving the checkpoint list , the cs will enable the specified checkpoints and patch the original program code with a call to “ sys_startcheck ”, as described in sec . 3 . 3 . 2 and starts the program execution 4 . ( cs side ) when a checkpoint location has been reached , the cs will generate a signature , combine the signature with the randomly generated session tag received in step 2 , encrypt this signature and send it to the as for verification . the encryption key is stored securely in the cs ( sec . 3 . 1 ). 5 . ( as side ) if the signature verification component in the as validates the signature sent by the cs , it sends a go - ahead message to the cs . this go - ahead message can optionally change the set of currently enabled checkpoints and re - initialize variables / system - level activity counters when necessary . if the validation fails , the as can enable additional checkpoint locations to scrutinize any suspicious behavior ( or rule out false positives ) through a more frequent challenge - response exchanges or abandon server - side execution and mark the server execution as compromised ( or untrusted ). the client decides on actions that have to be taken when validation fails . 6 . ( cs side ) after receiving a go - ahead message , the server side system call restores the original binary contents for the current checkpoint and returns . before returning to the original execution , the original code in the previously validated checkpoint location will be re - substituted with a call “ sys_checkpoint ” ( sec . 3 . 3 . 3 ) to permit a validation of the signature at this previous checkpoint , should it be required subsequently . a flowchart showing the method according to an embodiment is shown in fig2 . during the initial aspect of the process the client analyzes executables to derive control flow signatures along a complete set of locations ( called checkpoints ) on the possible control flow paths within the executable of the program p whose execution is to be validated and sends these to authentication server ( as ) on trusted channels 101 . the client then transfers executables to remote computation server ( cs ) 103 . the remote server waits for a control signal from authentication server , before it can preprocess the executables from the client 105 . the as sends a control message on a secure channel to the cs to preprocess the client &# 39 ; s executable , specifying a list of checkpoint addresses at which the control flow signatures may be verified as the program p executes on the cs 107 . on receiving the preprocessing direction from the as , the cs executes a trusted system function to insert calls to the signature verification functions at the checkpoints specified by the as , after saving the original contents of the locations within the executables of the program p where the calls to the signature verification function are inserted . these original contents of the executables of p are saved as a list in secure storage locations within the cs 109 the as dynamically selects a checkpoint location c within the control flow path of the program p , and sends a challenge message on a secure channel along with a randomly - generated session key , specifying the chosen checkpoint c at which the control flow signature has to be verified 111 . the cs executes the program p up to the checkpoint c specified in the last challenge message , and calls the trusted signature verification function ( sf ) 113 which does the following : a ) it re - inserts the call to the signature verification function at the immediately prior checkpoint location in the control flow path , if any , at which a signature was generated . b ) it generates the control flow signature at the checkpoint c and signs it with the session key specified in the last challenge message and sends the signed signature back to the as on a trusted channel as the cs &# 39 ; s response to the challenge message from the as . c ) it restores the original contents of the program p at checkpoint c ( from secure storage locations ) and returns control to the instruction at checkpoint c within the program p . the as receives the encrypted signature from the cs , decrypts it and verifies the generated signature against the expected signature . if these two signatures mismatch , the client is notified and appropriate corrective actions are taken . if the signatures match , steps 111 , 113 and 115 are carried out in sequence till the program execution terminates or if a signature mismatch occurs 115 . first , the impact of compromising the two functions calls installed at the cs are examined . if a different executable is run at the cs and these two system calls are compromised — either by substitution or through trapping and emulation — the signature generated will not match the expected signature , as the contents of the msr registers cannot be reproduced . the signature produced at the checkpoint is very likely to have both exact and inexact components ( sec . 4 ) that will fail to match the expected signature . there is , of course , a pathological case , where the signature of a bogus code will match the expected control flow signature at a checkpoint . note , however , that even with such a highly improbable “ accidental ” signature match at a specific checkpoint , it is practically impossible to have such matches consistently for a series of randomly chosen checkpoints . put in other words , such accidental matches are not likely to continue across a contiguous series of checkpoints , making it possible for the scheme to easily identify bogus , unauthenticated execution at the cs on behalf of a client . what if the signature generation functions are compromised ? here again , following arguments similar to the one just made , it can easily be see that even if a single signature can be made to match the expected signature , producing a series of such matches is practically impossible . it is also not possible to trap to an emulator from the system call for signature generation and generate the signatures correctly . to correctly reproduce some of the inexact signature components such as number of cache hits and number of stall cycles , the entire execution has to be emulated . this is because the emulation on traps cannot reproduce the states of internal hardware components such as caches , branch predictors and load miss predictors . the framework is highly resistant to buffer overflow attacks , direct code injection or library substitution attacks since : the framework works on basic blocks , and these attacks limit the malicious user to compromise only one basic block without any branch , seriously limiting the extent to which the attacker can compromise the application . if the malicious code injects a branch out of the compromised block , the execution of the branch is recorded in the msrs that keep track of branches . if one basic block produces unexpected results ( as values stored in general registers ), this basic block will be assumed as suspicious and the as can dynamically generate additional challenges , with an increased frequency to get a higher coverage for the control flow and thus detect if the unexpected results are a consequence of compromise or a false positive . these attacks , in general , will affect components of the global program state , as reflected in the contents of msrs that store cache access statistics , tlb statistics , system call statistics and other similar information . the framework can thus detect these attacks , as it includes these msrs in the “ variable ” part of the signature ( sec . 4 ). provided that the assumptions of section 3 . 1 are implemented as described in that section , replay attacks are not possible , as unique session tags are used for each challenge - response pair on secure channels . also , as explained in section 3 . 3 . 2 , the use of randomly and dynamically chosen checkpoints makes it practically impossible to generate a sequence of fake signatures that match the expected signatures . the accuracy with control flow is a function of the number of checkpoints that are dynamically enabled as the code executes . however , one has to note that the ratio of the average number of checkpoints at which signatures are verified to the number of basic blocks in the program being verified is not an indicator of the control flow coverage achieved . this is because at each checkpoint , the record of the last four braches executed ( in the pentium ® 4 and the intel ® xeon ® processor family cpus , this number is 16 ) are stored , so that an actual record is made of control flow through the 4 preceding basic blocks ( recall that a basic block is a sequence of code with one entry point and one exit point , with no branches in - between the entry and exit points ). many new intel processors also permit the logging of all executed branches in a branch trace stack in memory [ int 08 ]. if finer - grained control flow checking is necessary , this branch tracing mechanism can be optionally used at the cost of performance . in addition , global state information such as cache miss statistics , instruction commit rates , tlb miss rates , user - level variables provide an indirect coverage of control flow across several basic blocks and potentially for the entire control flow path up to that checkpoint . from a performance perspective , authenticating an execution as described can have a large overhead if signatures are generated at closely spaced checkpoints . this is so as the generation of a signature requires a system call to read and update msr registers , signature encryption and possible network communication with the as . the return from this system call requires memory - to - memory copying to restore the bytes of the original binary that were overwritten to insert the code to call sys_checkpoint ( ) before execution continues . to reduce the communication and verification overhead , the framework buffers the generated signatures and verifies a set of signatures at each challenge but that reduction is not enough by itself for each application so the framework supplies optional performance enhancement method . the optional approach of reducing the signature generation and verification overhead is to reduce the number of checkpoints at which signatures are generated . there is a price to be paid for this — longer sections of code are executed between verifications . the approach here is to disable signature checking at some specific checkpoints temporarily : if a specific checkpoint location is trapped and verified n times , this checkpoint location will be disabled for the execution of the next m instructions . here , the values of n and m are highly depended to the applications and may be chosen empirically for each checkpoint or a common set of values for m and n can be used globally . the key idea is to choose m and n in a manner that keeps the verification overhead to an acceptable level . to control the number of instructions executed after disabling a checkpoint location , the elapsed instruction counters in the current intel processors [ int 07 ] are used ; similar counters can be used on other platforms . the application is thus allowed to run for a while without the signature generation / validation overhead associated with a checkpoint location . this is very important for long running loops in the code . a malicious user cannot exploit this fact since it is very unlikely for such a user to guess when a checkpoint location will be disabled and for how long it remains disabled . in the current prototype , specific checkpoints are temporarily disabled by the sys_checkpoint call in response to a request from the as that is piggybacked to the validation message from the as to the cs . a disabled checkpoint is re - enabled by the running process itself , based on the value of the elapsed instruction counter . the framework for validating remote execution directly addresses the limitations of existing techniques , as described in section 2 . the advantages of the framework are as follows . the framework provided herein is a generic framework that can be customized to use a variety of signatures , permit users to take optional actions to change global information that form part of the signature after each validation , change the frequency of challenges and responses dynamically to tailor the tradeoff between performance and coverage . automated , high - coverage checkpoint generation : unlike other approaches , a set of checkpoints can be generated into a pool of checkpoint addresses automatically . dynamic checkpoint selection and trapping : dynamic checkpoint selection and dynamic breakpoint insertion allows us to overcome a fundamental security hole in existing solutions such as [ boy 03a , boy 03b , hfs 98 , kj 03 , xdc 04 ]. use of secure control flow signatures : to prevent the attacks like guessing the signature by using simulator like programs and / or replaying previous communication messages , the control flow specific properties are used to generate the signature of execution at each checkpoint . localized performance impact : from the view of performance , while the function call sequence including system call sequence for the monitored code can be checked , the framework affects only the target process / monitored code , unlike the techniques of globally intrusive mechanisms such as those of [ xdc 04 ] and [ hfs 98 ]. transparency : a good security mechanism should be fully transparent to the user and also to the programmer . the framework is fully transparent to both in this respect . the programmer does not need to decide on the checkpoint list , function calls for monitoring ; nor does the programmer need to worry about the configuration of the authentication entity . a generic framework with a new approach for validating the remote execution of a program is presented , having a broad range of application in various environments . this generic framework can be applied to a large class of systems , and the presumptions made are compatible with many common systems . the present framework differs from existing approaches in its use of dynamic checkpoint selection and dynamic generation of signatures based on the control flow path and the side effects of execution . these signatures are generated using the model specific registers used for cpu and system monitoring as found in most contemporary microprocessors . for example , the implementation of a prototype system in linux is described herein ; however , other operating systems and operating environments may also be employed . a technique is provided for reducing the overhead of execution authentication on a programs run time by temporarily disabling signature generation at heavily encountered checkpoints . an important consideration in the present execution mechanism has to do with the exact nature of the signature for control flow . in most modern desktop / laptop / server processors , the msrs hold statistics of cache misses , accuracy of branch prediction , committed instruction count , tlb miss rates etc . the of these measures , along with explicit control flow information held in the msrs ( such as last few branches and system calls executed ) are investigated to get generalized signatures of control flow that can be matched stochastically against a set of reference signatures . such generalized signatures can possibly reduce the number of checkpoints needed and may well hold the promise of reducing the runtime overhead of the present scheme . last but not the least ; the provided execution authentication mechanism is robust . many variations of the invention will occur to those skilled in the art . some variations include operating on general purpose processors , embedded processors , asics , fpgas , parallel processors , graphic processors , communications processors , communcations through wired , radio frequency or optical means , and in some cases , acoustic or wireline communications , various levels of cryptographic protection and authentication of communications , fixed , context - sensitive or adaptive tolerance to deviations from nominal verification conditions , cooperation with other types of systems and / or other security features of the system , use of the profiling technology to improve system performance by , for example , detecting inefficiencies , and the like . the security system encompassed by the claims may be integrated in a single device , or distributed , and , for example , may be part of communications devices or appliances . all such variations are intended to be within the scope and spirit of the invention , which is limited only by the claims . the examples presented herein are not intended to limit the scope of the invention . it is understood that the present invention may be executed on a variety of computing platforms , both general and special purpose , implementing specific functionality as described herein . each of the following reference is incorporated herein by reference as if set forth in their entirety . [ amd 05 ] advanced micro devices , secure virtual machine architecture reference manual , 2005 . [ ba 02 ] bill arbaugh , “ improving the tcpa specification ,” computer , vol . 35 , no . 8 , pp . 77 - 79 , august , 2002 [ boy 03a ] mario baldi , yoram ofek , moti yung , “ the trustedflow protocol : idiosyncratic signatures for authenticated execution ”, in proc . ieee workshop on information assurance , 2003 . [ boy 03b ] mario baldi , yoram ofek , moti yung , “ idiosyncratic signatures for authenticated execution , the trustedflow , protocol and its application to tcp ”, in proc . sym . on comm . systems and networks ( csn ), 2003 . [ cm 05 ] simon p . chung , aloysius k . mok , “ on random - inspection - based intrusion detection ”, in proc . of the 8 - th int &# 39 ; l symp . on recent advances in intrusion detection ( raid 2005 ). [ hfs 98 ] steven a . hofineyr , stephanie forrest , anil somayaji , “ intrusion detection using sequences of system calls ”, journal of computer security , vol . 6 , no . 3 , 1998 . [ hwu + 93 ] w . hwu et al , “ the superblock : an effective technique for vliw and superscalar compilation ”, the jrnl of supercomputing , 1993 , pp . 229 - 248 . [ int 04 ] intel corpn ., trusted platform module ( tpm ): quick reference guide , 2004 . [ int 07 ] intel corporation , model - specific registers and functions . available at : http :// www . intel . com / design / intarch / techinfo / pentium / mdelregs . htm , 2007 . [ int 08 ] intel corporation , intel ® 64 and ia - 32 architectures software developer &# 39 ; s manual , available at http :// www . intel . com / products / processor / manuals / [ ka 07 ] kauer , b ., “ oslo : improving the security of trusted computing ”, in proc . of the 16th usenix security symposium , 2007 . [ kj 03 ] rick kennell and leah h . jamieson , “ establishing the genuinity of remote computer systems ”, in proc . 12th usenix security symposium , usenix association , 2003 . [ mpp + 07 ] jonathan m . mccune , bryan parno , adrian perrig , michael k . reiter , hiroshi isozaki , flicker : an execution infrastructure for tcb minimization , in proc . eurosys , 2008 [ mpprs 07 ] jonathan m . mccune , bryan parno , adrian perrig , michael k . reiter , arvind seshadri , minimal tcb code execution , in proc . ieee symposium on security and privacy , 2007 [ mwr 99 ] f . monrose , p . wyckoff , and a . rubin , “ distributed execution with remote audit ”, in proc . of isoc network and distributed system security symposium ( ndss 99 ), february 1999 [ slqp 07 ] arvind seshadri , mark luk , ning qu , adrian perrig , secvisor : a tiny hypervisor to provide lifetime kernel code integrity for commodity oses , symposium on operating systems principles , 2007 [ spd 04 ] arvind seshadri , adrian perrig , leendert van doom , “ using software based attestation for verifying embedded systems in cars ”, in proc . embedded security in cars conference ( escar ), 2004 [ spd 05 ] elaine shi , adrian perrig , leendert van doom , “ bind : a find - grained attestation service for secure distributed systems ”, proc . of the ieee symposium on security and privacy , 2005 . [ sls + 05 ] arvind seshadri , mark luk , elaine shi , adrian perrig , leendert van doom , pradeep khosla , “ pioneer : verifying code integrity and enforcing untampered code execution on legacy systems ”, acm symposium on operating systems principles , 2005 . [ spec 06 ] standard performance evaluation corporation . spec cpu2000 benchmark suite , 2000 . [ tri 07 ] tripwire product pages at : http :// www . tripwire . com / products / enterprise / ost /, 2007 . [ tcg 07 ] home page of the trusted computing group at : http :// www . tcg . org . [ uct 04 ] umesh shankar , monica chew , j . d . tygar . “ side effects are not sufficient to authenticate software ”, in proc . 13th usenix security symposium , 2004 . [ xdc 04 ] haizhi xu , wenliang du , and steve j . chapin , “ context sensitive anomaly monitoring of process control flow to detect mimicry attacks and impossible paths ”, in proc . 7 - th int &# 39 ; l . symp . on recent advances in intrusion detection , 2004 raid 2004 ).