Divya Arora

Srivaths Ravi
email: sravi@nec-labs.com

Anand Raghunathan

Niraj K Jha
email: jha@princeton.edu

Secure Embedded Processing through Hardware-assisted Run-time Monitoring

Security is emerging as an important concern in embedded system design. The security of embedded systems is often compromised due to vulnerabilities in "trusted" software that they execute. Security attacks exploit these vulnerabilities to trigger unintended program behavior, such as the leakage of sensitive data or the execution of malicious code.

In this work, we present a hardware-assisted paradigm to enhance embedded system security by detecting and preventing unintended program behavior. Specifically, we extract properties of an embedded program through static program analysis, and use them as the bases for enforcing permissible program behavior in real-time as the program executes. We present an architecture for hardware-assisted run-time monitoring, wherein the embedded processor is augmented with a hardware monitor that observes the processor's dynamic execution trace, checks whether the execution trace falls within the allowed program behavior, and flags any deviations from the expected behavior to trigger appropriate response mechanisms. We present properties that can be used to capture permissible program behavior at different levels of granularity within a program, namely inter-procedural control flow, intra-procedural control flow, and instruction stream integrity. We also present a systematic methodology to design application-specific hardware monitors for any given embedded program. We have evaluated the hardware requirements and performance of the proposed architecture for several embedded software benchmarks. Hardware implementations using a commercial design flow, and architectural simulations using the SimpleScalar framework, indicate that the proposed technique can thwart several common software and physical attacks, facilitating secure program execution with minimal overheads.

I. INTRODUCTION

As embedded systems pervade various aspects of our lives, they are often required to deal with sensitive information or perform critical functions, making security an important concern in embedded system design. Security has been the subject of extensive research in the context of general-purpose computing and communications systems, leading to many advances such as cryptographic algorithms, security protocols, etc. [START_REF] Schneier | Applied Cryptography: Protocols, Algorithms and Source Code in C[END_REF], [START_REF] Stallings | Cryptography and Network Security: Principles and Practice[END_REF]. While such "functional" security measures provide a strong basis for securing embedded systems, recent trends in security attacks have made it abundantly clear that most attacks target weaknesses in a system's implementation. It is now well accepted that a secure system implementation is as critical to a system's overall security as the strength of the theoretical security measures employed. Consequently, recent years have seen an increasing awareness that security needs to be considered at various stages of the embedded system design process, including system architecture and hardware/software implementation.

A notable trend in embedded systems has been a drastic increase in embedded software content in order to support increasing end-user functionality and performance requirements (on an average, embedded software content has been increasing by 140% per year -even faster than Moore's law). It is therefore not surprising that the most common security attacks on embedded systems are software-based, or exploit weaknesses in embedded software. Together with increasing complexity, features such as network connectivity and extensibility (ability to extend installed software or download new software onto the embedded system) have only increased the vulnerabilities to software attacks.

In this work, we address the problem of secure software execution in embedded systems. Software security can be compromised in a variety of ways, e.g., through the execution of programs that originate from untrusted or unknown sources, or through the corruption of binaries while they are being downloaded or stored on the embedded system. However, a recurring theme among many recent software security attacks is that they exploit weaknesses in "trusted" code (operating system (OS), middleware, applications) that is already present in the system. For example, 66% of the vulnerabilities reported by CERT are based on exploiting buffer overflow behavior in trusted programs [START_REF]Vulnerability Notes Database[END_REF]. Such attacks are especially dangerous when they are used to subvert programs that have special privileges, e.g., access to sensitive data or system resources. In this work, we propose a hardware/software solution to address the above problem based on the paradigm of hardware-assisted run-time monitoring.

A. Paper Overview and Contributions

In this paper, we address secure program execution by focusing on the specific problem of ensuring that the program does not deviate from its intended or "permissible" behavior. We address this problem by using the notion of a dedicated hardware monitor that enforces permissible behavior as the program executes. We describe the architecture of a hardware monitor that can be connected to any embedded processor to observe its dynamic execution trace as it executes the program, check whether the trace conforms to the definition of permissible behavior, and flag violations by triggering appropriate response mechanisms.

We propose to define permissible behavior by identifying suitable program properties or invariants that are indicators of untampered execution (i.e., will be violated if a software attack occurs). We identify properties that capture both coarse-grained and fine-grained program behavior in a hierarchical manner, including (i) the inter-procedural control flow of a program, as represented by its function call graph, (ii) the intra-procedural control flow for each function, represented by a basic-block control-flow graph (CFG), and (iii) the integrity of the instruction stream within each basic block.

We propose techniques to extract the above properties from any given program, and automatically synthesize a hardware monitor for it. The hardware monitor can be implemented as a programmable unit that can be configured for each application that executes on the embedded system.

We have evaluated the area and delay overheads associated with the proposed architecture using several embedded software benchmarks. Hardware implementations using a commercial design flow, and architectural simulations using the SimpleScalar framework, demonstrate that the proposed hardware-assisted monitoring technique can eliminate a wide range of common software and physical attacks, facilitating secure program execution with minimal overheads.

The remainder of this paper is organized as follows. We present a survey of relevant past work in Section II. Section III describes a typical software attack and motivates the need for the proposed technique. Section IV presents the details of the proposed hardware-assisted monitoring architecture. Section V describes a systematic methodology to design hardware monitors for any given application. We present our experimental methodology and results in Section VI and conclude in Section VII.

II. RELATED WORK

A wide range of techniques has been proposed to enhance software security in the context of general-purpose computing systems. Most of them address problems such as verifying the identity of the provider of a program, checking the integrity of program binaries, ensuring isolation between different programs running on a system, etc. These techniques are complementary to our work, which focuses on eliminating unintended behavior in trusted programs that have already been authenticated, but may potentially contain vulnerabilities that can be exploited for attacks. We examine research related to secure program execution in three categories -static checking, software-based program monitoring, and processor architectures for secure execution.

Static techniques include source code scan tools and code review tools that attempt to strengthen security by eliminating vulnerabilities during the software design phase [START_REF] Howard | Writing Secure Code[END_REF], [START_REF] Hoglund | Exploiting Software: How to Break Code[END_REF]. Studies have been performed to model vulnerabilities that open doors for security exploits [START_REF] Chen | A data-driven finite state machine model for analyzing security vulnerabilities[END_REF]. Although these techniques are useful, the protection they offer is not complete, since they are typically rule-based and attempt to match the target program with specific known classes of vulnerabilities.

Software-based monitoring has also been explored along various dimensions. In [START_REF] Ko | Execution monitoring of security-critical programs in distributed systems: A specification-based approach[END_REF], the authors provide formal specifications of securitycritical programs and check for access rights violations through an analysis of their execution traces. Efficient methods for automatically embedding software security checks in a program, in order to perform security-related actions (e.g., checksumming and repair) during execution are explored in [START_REF] Horne | Dynamic self-checking techniques for improved tamper resistance[END_REF]- [START_REF] Chen | Oblivious hashing: A stealthy software integrity verification primitive[END_REF]. In these studies, the focus is on the efficiency and stealth of the security checks. Program shepherding [START_REF] Kiriansky | Secure execution via program shepherding[END_REF] proposes a software-based run-time environment that monitors control flow during program execution, and enforces user-specified security policies, such as restricted code origins and control transfers. The main drawback of software schemes is that the security checks are also pieces of code which are themselves vulnerable to corruption. Also, the granularity of checking is limited due to the overhead imposed by the additional code.

The basic concept of using a hardware unit or co-processor to facilitate secure execution has roots dating back to tamper-resistant cryptoprocessors that were used to store cryptographic keys and execute cryptographic algorithms [START_REF] Kuhn | The TrustNo 1 Cryptoprocessor Concept[END_REF], [START_REF]Secure Coprocessing[END_REF]. However, a significant difference in our work is that the monitor does not execute any program itself -it only ensures that the program running on the host processor does not display unintended behavior. The application of a secure co-processor to perform intrusion detection (to monitor critical OS data structures, check the integrity of files on disk, perform virus scanning, etc.) was proposed in [START_REF] Zhang | Secure coprocessor-based intrusion detection[END_REF]. Recently, enhanced processor architectures, such as XOM and AEGIS, have been proposed [START_REF] Lie | Architectural support for copy and tamper resistant software[END_REF], [START_REF] Suh | AEGIS: Architecture for tamper-evident and tamper-resistant processing[END_REF], which attempt to provide code integrity and privacy in the presence of untrusted memory. The authors of XOM use the ideas of eXecute-Only-Memory (allowing instructions to be executed but not modified), ciphered-code execution (decrypting code on-the-fly), and tagged data (associating a process identifier tag with all architectural data) to achieve these goals. However, these techniques do not safeguard an application from its own vulnerabilities. In [START_REF] Suh | Secure program execution via dynamic information flow tracking[END_REF], the authors propose a hardware-supported scheme to track the use of input data that are captured from untrusted input channels, and ensure that such data are never used to affect program control flow. In addition to the above general techniques, a number of attack-specific mechanisms have been developed [START_REF]Non-Executable User Stack[END_REF]- [START_REF] Mcgregor | A processor architecture defense against buffer overflow attacks[END_REF], mostly in response to the increasing number of exploits involving buffer overflows and format string vulnerabilities.

Our work can be differentiated from previous work along several dimensions, including the overall approach to enforcing security, as well as the hardware/software architecture used to implement it:

• Our approach does not require users to explicitly specify security policies -instead, properties indicative of permissible program behavior are extracted from the application itself. The extracted properties are application-specific, yet our approach has wide applicability since the process of deriving the properties can be incorporated into a compiler tool flow. • Unlike the purely static or purely dynamic approaches described above, we partition the burden of ensuring security between static analysis and dynamic (run-time) monitoring and enforcement. • The use of hardware-assisted monitoring enables the checking of fine-grained, application-specific properties, resulting in higher levels of security and lower detection latencies, while incurring minimal delay overheads. • The proposed hardware-assisted monitoring architecture does not require any changes to the embedded processor, and hence can be directly applied to existing embedded systems. Due to the above factors, we believe that our technique offers a practical approach to counter a broad range of attacks including, for example, buffer overflows, spurious control transfers, and run-time code corruption.

III. MOTIVATION

A large number of security breaches are effected by software exploits that take advantage of weaknesses present in "trusted" code. In this section, we illustrate how a simple vulnerability in a benign application program can be exploited to achieve undesirable side-effects, such as the execution of arbitrary malicious code, motivating the need for solutions such as the one proposed in this paper.

We consider a program that is part of a popular audio format conversion utility, called the SoX (Sound eXchange) toolkit. Fig. 1(a) presents a code snippet from a file that contains functions related to the reading and writing of "wav" files. The function st wavstartread() shown in Fig. 1(a) reads len bytes from an input file into a local array text[ ], where parameter len is read from the file header. Fig. 1(b) shows the layout of the stack frame for function st wavstartread(), when the function is called during the program's execution. The stack frame contains copies of the function's arguments, the return address in the calling function, as well as storage space for local variables such as the text[ ] array. In order to execute a successful exploit, an attacker creates an input wav file that contains a payload of malicious code and a large value of len (len > 256). When the program is executed with this malicious input file, it causes a buffer overflow for array text[ ], resulting in corruption of the local variables and the function's return address stored on the program stack. When the function st wavstartread() returns, program flow is directed to the corrupted return address. Through appropriate construction of the input file, the corrupted return address can easily be made to point to the start of the malicious code to be executed.

While the vulnerability in the above example was a lack of input validation, vulnerabilities in large, complex programs can be much more subtle and difficult to catch. Numerous variants of similar exploits (return-into-libc, format string attacks, heap overflow) on securitycritical programs have been reported in the literature [START_REF]Vulnerability Notes Database[END_REF], [START_REF] Hoglund | Exploiting Software: How to Break Code[END_REF]. In addition, embedded systems are also highly susceptible to physical attacks that involve tampering with system properties such as voltage levels, clock frequency, and memory contents. Irrespective of how they originate, most attacks eventually manifest themselves as a subversion of "normal" program execution -violation of control flow behavior, execution of corrupted instruction sequences, etc. Instead of trying to block all sources of attack, we concentrate on defining permissible program behavior and monitoring program execution to catch these aberrations. However, the overhead of tracking execution flow at a fine granularity makes a software-based solution infeasible, and presents a compelling case for designing an efficient, hardware-assisted run-time monitor.

IV. HARDWARE-ASSISTED MONITORING ARCHITECTURE

In this section, we provide an overview of the proposed hardwareassisted monitoring architecture. We then describe in detail the properties that model permissible program behavior and the design of the corresponding hardware monitors that check them.

A. Architecture Overview

Fig. 2 shows the conceptual block diagram of the proposed hardware-assisted monitoring architecture. For ease of illustration, we depict the embedded processor as an in-order five-stage pipeline 1 . The inputs to the monitor include the program counter (PC) and instruction register (IR) of the completing instruction, and the pipeline status from the pipeline control unit. Effectively, the monitor is provided with a cycle-by-cycle trace of the executing instructions and their program addresses. The monitor's outputs include a stall signal and an invalid signal. When the monitor detects a violation of permissible program behavior, it asserts the invalid signal, which results in a nonmaskable interrupt to the processor. This signal can be used to trigger a response mechanism, such as termination of the program or transfer of the processor to a secure mode. The stall signal is asserted if the monitor is unable to keep pace with processor execution (this happens in very rare cases). This is handled as a normal processor stall, and all the pipeline stages are "frozen" until the stall signal is de-asserted. The three sub-blocks within the monitor handle checking of the three different classes of program properties mentioned earlier. The design of these sub-blocks is described in detail later in this section.

B. Modeling Permissible Program Behavior

There are several factors to be considered when selecting program properties to be monitored. They should be accurate indicators of invalid behavior, i.e., very likely to be violated when system security is compromised. They should also be easily derivable through automatic program analysis for a wide range of programs. They should lend themselves to a concise representation for scalability to large programs. Finally, the hardware overheads involved in checking them at run-time should be reasonable. Based on these considerations, we have chosen three key properties to provide protection at varying granularities, which we describe next. By default, all user-defined and library functions that are part of the application program are included in the function call graph. Potentially, this can be done for system calls (OS functions) as well. Alternatively, if the kernel is assumed to be secure, system calls can be treated as leaf functions in the function call graph. The extraction of the function call graph should also include indirect function calls with function pointers, by adding an edge from the calling function to each function whose address can be assigned to the function pointer.

2) Intra-procedural control flow: A logical succession to the above scheme is to also track control flow within each function in the program. The control flow within a function can be represented using the function's CFG, and translated into an FSM, or equivalently, a basic block information table. Each basic block bi has a corresponding row Procedure 1 FSM extraction for inter-procedural control flow checking

1: Inputs: Function Call Graph G(F, E) 2: F ← set of all functions f i , 1 ≤ i ≤ N 3: E ← set of directed edges e ij ∈ E ⇐⇒ f i includes a direct or indirect
call to f j 4: Output: FSM (Z, S, T, s, A), where Z: input alphabet, S: set of states, T : S × Z → S: transition function, s: initial state, A: accept states 5: s ← index(main) 6: for all f i ∈ F do 7: Add state i to S and A 8: for all f j : e ij ∈ E do 9:

Add the following transitions to T : 10: Nested switch statements are handled by directing the compiler to compile them as a sequence of if-then-else statements. To facilitate easy detection of end of basic blocks in hardware, the procedure requires that all basic blocks end with an explicit control transfer instruction. Hence, extra jump instructions (to the next basic block) are appended to fall-through blocks. Our experiments indicate that this does not lead to significant overheads in terms of code size increase (≤ 1%). In our investigations, intra-procedural control flow checks are performed for basic blocks in all user-functions. In practice, these fine-grained checks may be restricted to only security-sensitive parts of the application.

Z 0 = CALL, Z 1 = j → Nextstate [i] = j 11: Z 0 = RET U RN , Z 1 = i → Nextstate [j] = i 12: for all i : Nextstate [i] = unassigned do 13: Nextstate [i] = N + 1 /*
3) Integrity of the executed instruction stream: Some security attacks may not result in a control flow violation, e.g., alteration of a basic block in the program code segment during execution. In order to detect such attacks, we explore a complementary approach by checking the integrity of the dynamic instruction stream with the aid of cryptographic hash functions. Given a message x and its cryptographic hash H(x), it is computationally infeasible to find another message y such that y = x and H(y) = H(x). Hence, given a sequence of instructions, it is extremely hard for an adversary to find another sequence of instructions such that both hash to the same value. Hash values of each basic block in the program are computed beforehand, loaded into the hardware monitor when the application is loaded for execution, and subsequently checked during program execution. Hashing is computationally intensive and requires dedicated highspeed hardware to keep up with the processor pipeline. Moreover, most well-known hash algorithms map a variable-sized input to a fixed-sized output (16-20 Bytes). To keep the monitor's hardware requirements low, a user-specified number of bits of the pre-computed hash value are randomly selected at program start-up and loaded into the monitor for checking. It is worth noting that the proposed technique is complementary to static hash checking, since it detects program corruption during execution. C. Architectural Details Fig. 3 shows the detailed architecture of the monitor. The monitor is delineated into its three major constituent sub-blocks -the interprocedural control flow checker, the intra-procedural control flow checker, and the basic block level instruction integrity checker. Although the three checks are logically independent, in the implementation described here, the three sub-blocks share hardware and hence communicate with each other.

1) Inter-procedural control flow checker:

The inter-procedural control flow checker consists of two look-up tables, T ABstart and T ABret, that store function start and return addresses, respectively, and an FSM F SMIP that verifies the validity of function calls and returns.

The function start address table, T ABstart, takes an instruction address as input. If the instruction address corresponds to the start of a function, it asserts a match signal, and outputs a unique function index. The number of entries in T ABstart equals the number of functions in the application program. The contents of this table are generated by enhancing the compiler tool flow and the run-time application loader, as described in Section V.

The return address table, T ABret, performs a similar mapping from instruction addresses that correspond to return locations, to the index of the function that they are located in (i.e., the calling function). However, there is a notable difference in how its contents are generated. T ABret is updated dynamically by the monitor hardware as the program executes. At any point in time, it contains an entry corresponding to the return location for each function that has been called but not yet returned. Note that the number of distinct return locations is bounded by the number of function call instances, which is, in general, larger than the number of functions in a program. The return address table is similar to the use of a hardware return address stack on which return addresses are pushed on a call and popped on a return. The only difference is that recursive functions are handled more efficiently -only one entry is maintained for each distinct call site. For example, if the call sequence is B → A → A • • • → A → B, the table could contain only two return addresses for function A -one entry for the return address corresponding to the call B → A, and a second entry for the return address corresponding to the call A → A.

In hardware, each of the two lookup tables can be directly implemented using a content addressable memory (CAM), which is basically a read-writable memory with additional logic circuitry (comparators) to provide fast table look-up.

The function indices output from T ABstart and T ABret are input to the FSM F SMIP , which keeps track of program control flow by executing corresponding state transitions. At each state transition, the FSM checks whether the incoming function index is equal to the index of one of the valid next states. If so, it executes the state transition. The invalid detection circuitry is signaled in case there is no match in address look-up, or if there is an FSM transition into the INVALID state.

2) Intra-procedural control flow checker: The intra-procedural control flow checker consists of a basic block table, T AB bb , which stores the information necessary to track control flow within each function. The basic blocks are grouped according to the function that they belong to. The function start address table, T ABstart, which is part of the inter-procedural control flow checker, is augmented with an additional field that is a pointer to a location in T AB bb . This additional field tells the intra-procedural control flow checker where it should start when a function is called. When control enters a function, the function start address is copied into a special register and used to calculate offsets for all future branches within the function. In addition, on each function call, the basic block index within the calling function is also saved in T ABret, and restored upon return.

3) Instruction integrity checker: In order to check instruction stream integrity, each row in the basic block table, T AB bb , is augmented to contain another field that stores the statically-computed cryptographic hash of the instruction sequence in the basic block. During program execution, the monitor buffers the instruction stream corresponding to a basic block until a branch/jump instruction is encountered. At this point, it switches to an empty buffer and signals the hardware hash unit to compute the hash of the buffered basic block. The computed hash value is then compared against the value stored in T AB bb . When the buffers are full, the processor is stalled in order to allow the instruction integrity checker to catch up.

Many popular hash algorithms, such as MD4, MD5, and SHA-1 [START_REF] Schneier | Applied Cryptography: Protocols, Algorithms and Source Code in C[END_REF], incur a high latency, since the input is processed through several rounds wherein the result of the i th round is input to the i + 1 th round. Data dependencies within a round limit the amount of parallelism that can be achieved by adding more hardware. Moreover, if the input size is greater than 512 bits, the output from the last round is fed back to the first round and included in further computation. We break this feedback loop by imposing a limit lmax on the maximum basic block length. Basic blocks that exceed this limit are split into sub-blocks of length ≤ lmax and an XOR of the hash values of all constituent sub-blocks is checked. This allows us to pipeline the hashing unit at a fine-grained level (each round is a pipeline stage). In practice, this implies that the hardware monitor stalls the processor only in very rare cases, leading to minimal performance impact, as demonstrated in our experimental results.

V. DESIGN FLOW Fig. 4 shows the compilation and execution flow for hardwareassisted run-time monitoring. Given an application and user-specified options, program models, namely the function call graph and CFGs for each function, are extracted during compilation. Depending on the security requirements, the user can specify options to define the granularity of checks (e.g., the depth to which the function call graph is tracked, selected functions for which intra-procedural checking and hash checking are done, etc.). Function addresses, basic block offsets, and hashes are computed after linking. The extracted information is translated into the data required to configure the hardware monitor (FSM state table, function start address table, basic block table, hash values), and appended to the program's binary code.

Configuration of the security monitor is performed when the application is loaded for execution. Security technologies such as ARM TrustZone [START_REF]ARM TrustZone Technology Overview[END_REF] can be used to provide a secure mode during configuration, while the remaining application is run in a non-secure mode. The contents of lookup tables T ABstart, T ABret, and T AB bb are loaded into the monitor, and the FSM in the monitor is configured. There are multiple implementation options for the FSMs in the hardware monitor, including reconfigurable logic (e.g., FPGA cores), or explicit state-table based implementations using memories. After configuration of the monitor, the loader initiates application execution. The flow described in this section can be extended to the case when the application uses dynamically-linked libraries. For such applications, addresses of the functions contained in the dynamic libraries are available only when the application is loaded or when the function is invoked ("lazy evaluation"). Addresses of such functions are marked null in the function start address table when the program is compiled. The dynamic loader is responsible for updating these addresses and loading them into the function start address table in the hardware monitor.

VI. EXPERIMENTAL RESULTS

In this section, we present the hardware (area) overheads incurred by the proposed hardware-assisted monitoring architecture, as well as the impact of hardware-based monitoring on performance (program execution time). For the purpose of our experiments, we selected applications from the MediaBench [START_REF] Lee | Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems[END_REF] and MiBench benchmark [START_REF] Guthaus | Mibench: A free, commercially representative embedded benchmark suite[END_REF] suites, which represent typical workloads for embedded processors. The information necessary to generate the hardware monitor was extracted using the GNU compiler gcc. We developed tools to postprocess this information and generate the contents of the memories in the hardware monitor, as well as Verilog hardware descriptions of the monitor's FSM and control logic.

A. Area Overheads

The key functional blocks in the monitor can be categorized into the FSM and CAMs that are part of the inter-procedural checker, SRAM for the intra-procedural checker, the buffers and hardware hash engine for the instruction integrity checker, and miscellaneous control logic. For estimating the area of hash engines, we implemented Verilog RTL descriptions of two commonly used hash algorithms, MD4 and MD5 [START_REF] Schneier | Applied Cryptography: Protocols, Algorithms and Source Code in C[END_REF]. The hash engines and the FSM (for each application) were synthesized into technology-mapped gate-level netlists using Synopsys Design Compiler [24] with NEC's 0.13µ CB-130M CMOS standard cell library. Memory models from [START_REF] Mulder | An area model for on-chip memories and its application[END_REF] were used to estimate the area of the CAM and SRAM. In order to compute area overheads, we used as the base case an ARM920T 32-bit processor core that has separate 16kB instruction and data caches, runs at 250MHz , and occupies an area of 4.7mm 2 in a 0.13µ technology [START_REF]ARM920T Embedded Processor Core[END_REF].

Table I reports the area overheads for different benchmarks, for three monitoring scenarios that correspond to increasing levels of security. The second, third, and fourth columns list the number of functions (#Fns), the number of function call locations (#Fn calls), and the number of basic blocks (#Basic blocks) in each benchmark program. The fifth column (labeled AO% level1) reports the total percentage area overhead when only the inter-procedural control flow checker is used. The sixth column (AO% level2) reports the total percentage area overhead when both inter-and intra-procedural checkers are used, and the last column (AO% level3) represents the case when an instruction integrity checker is also employed in addition to control flow checkers. The two minor columns (unpipe and pipe) under the last column represent the cases when the hash engine within the instruction integrity checker is un-pipelined and pipelined, respectively. The table indicates that for all the benchmarks considered, inter-procedural checking alone can be implemented with a maximum area overhead of 1.20% and an average overhead of 0.72%. Adding intra-procedural checking raises the maximum overhead to 5.17% and average overhead to 2.44%. For the case with the highest hardware requirements (inter-and intra-procedural control flow checking together with pipelined hash checking), the maximum overhead is 9.07% and the average overhead is 5.59%. Clearly, the area overhead is quite low in all cases, when viewed as a percentage of the area of the processor. When employed as part of a system-on-chip that includes an embedded processor and other components, the relative area overheads are likely to be much lower.

B. Performance Impact

We evaluated the performance impact of the proposed architecture using the SimpleScalar 3.0/PISA architectural simulation toolset [START_REF] Burger | The simplescalar tool set, version 2.0[END_REF]. The micro-architectural parameters of SimpleScalar were configured to model a typical embedded processor such as the ARM920T. The parameters used for the simulated processor are shown in Table II. We built our simulator within the framework of the existing cycle-accurate simulator sim-outorder and used it to evaluate program execution statistics when the monitor is running in parallel and performing various checks. The clock frequency of hash engines was determined from the hardware implementations, as discussed in the previous subsection. Each benchmark was simulated for five million instructions. We considered two different implementation scenarios for the memories that are part of the hardware monitor -in one case, we assumed that they were implemented as on-chip memories, and in the second case, we assumed that they were implemented off-chip. The main difference between these cases is the access latency.

For inter-and intra-procedural checks, we experimented with two different modes for flagging invalid behavior. In the detection mode, the processor is allowed to continue while the monitor is running and is stalled only if a control instruction (call/branch) completes before the previous control instruction has been verified. In the prevention mode, no new instruction is allowed to commit after a control instruction until the latter has been checked. For dynamic hashing, the latency of hash computation does not permit stalling the processor for each basic block. Therefore, the processor and hashing units are allowed to run in parallel and the former is stalled only if the instruction buffer in the hash unit becomes full. When on-chip memories were used for the hardware monitor's CAMs and SRAM, performance degradation for inter-procedural checks was found to be negligible (< 1%) for all benchmarks tested, for both detection and prevention modes. This is expected since most applications have sparse call graphs and their FSMs can be synthesized to operate at or above processor speeds. The same is true for intraprocedural checks, assuming an on-chip SRAM is used to store the FSM state table for each function.

When off-chip memories were used, as expected, we observed slightly higher performance penalties. Fig. 5(a) plots the average cycles per instruction (CPI) for all benchmarks, for both the detection and prevention modes. The figure demonstrates that even in this case, the impact is fairly small (average of 1.77% for detection mode and 4.94% for prevention mode). illustrates the impact of instruction integrity checking on CPI, for different hash algorithms and their implementations. As expected, the performance penalty for an un-pipelined MD5 hash engine, with a latency of 64 clock cycles, is substantial. The performance penalty using an un-pipelined MD4 engine (latency of 48 cycles) is lower, but still considerable. However, with pipelining, the penalty can be virtually eliminated, as shown by the last bar in the graph. In most cases, the original CPI is maintained with the use of pipelined hash engines. With the use of pipelining, there is negligible performance difference between the MD4 and MD5 algorithms.

Fig. 6 shows how the average CPI is affected by varying the number of basic blocks that are hash-checked when an un-pipelined MD4 hash engine is used. In most cases, 50-60% of basic blocks can be hashchecked without any observable decline in performance, even without a pipelined implementation.

In summary, the results demonstrate that the proposed hardwareassisted run-time monitoring technique is viable and imposes minimal area and execution time overheads.

Fig. 1 .

 1 Fig. 1. A simple example of a "stack smashing" security attack

Fig. 2 .

 2 Fig. 2. Proposed hardware-assisted monitoring architecture: Conceptual block diagram

1 )

 1 Inter-procedural control flow: At the highest level of granularity, we verify the correctness of a program's inter-procedural control flow. It is common to represent inter-procedural control flow using a function call graph. For the purpose of hardware implementation, a function call graph of a program with N functions is translated into a finite-state machine (FSM) with N + 1 states -one state corresponding to each function in the program, and an additional INVALID state. The functions are associated with a unique index from 1 to N . For convenience, the FSM state corresponding to a function is also labeled with the same index. A transition between two states in the FSM (except the INVALID state) represents a valid control transfer (call or return) between the corresponding functions. Any invalid call or return transitions the FSM to the INVALID state. The input alphabet Z of the FSM consists of two distinct inputs: Z0 = {0, 1}, which is set to 0 or 1 depending on whether the executing instruction is a function call or return, and Z1 = {1, 2, . . . , N}, which is the index of the target function of the call/return. Procedure 1 describes how the FSM is automatically extracted from the function call graph.

Fig. 3 .

 3 Fig. 3. Architectural details of the run-time monitor

Fig. 4 .

 4 Fig. 4. Design flow for hardware-assisted run-time monitoring

Fig. 5 .

 5 Fig. 5. Performance analysis of (a) intra-procedural control flow checking and (b) dynamic hash checking

Fig. 6 .

 6 Fig.6. Performance estimation when the percentage of basic blocks hashed is varied Fig.5(b) illustrates the impact of instruction integrity checking on CPI, for different hash algorithms and their implementations. As expected, the performance penalty for an un-pipelined MD5 hash engine, with a latency of 64 clock cycles, is substantial. The performance penalty using an un-pipelined MD4 engine (latency of 48 cycles) is lower, but still considerable. However, with pipelining, the penalty can be virtually eliminated, as shown by the last bar in the graph. In most cases, the original CPI is maintained with the use of pipelined hash engines. With the use of pipelining, there is negligible performance difference between the MD4 and MD5 algorithms.Fig.6shows how the average CPI is affected by varying the number of basic blocks that are hash-checked when an un-pipelined MD4 hash engine is used. In most cases, 50-60% of basic blocks can be hashchecked without any observable decline in performance, even without a pipelined implementation.

  INVALID STATE*/ in the table, expressed as a tuple rowi(index, of f set, s0, s1), where of f set is the address offset of bi from the start of the function and s0, s1 are indices of its possible successors. Procedure 2 describes how to create the basic block information table. If the code does not contain any indirect jumps, each basic block can have at most two successors listed in fields s0, s1 (corresponding to the branch at the end of the basic block being taken or not taken). The procedure shows how a single level of indirect jumps (e.g., switch statements) is handled. Field s0 in this case carries a special code to denote an indirect jump and s1 contains the number of possible jump targets, which appear in the rows immediately following the current row. Hence, a jump to the s1 fields in any of these rows is considered valid.

			taken target
	16: else
	17:	row i .s 0 = NULL	/*unconditional jump*/
	18:	row

Procedure 2 Transition table generation for intra-procedural control flow checking

1: Inputs: Control Flow Graph G(B, E) 2: B ← set of all basic blocks b i , 1 ≤ i ≤ n 3: E ← set of directed edges e ij ∈ E ⇐⇒ b j is

a successor of b i 4: Output: T = {row 0 , row 1 , . . . , rown} where row i is a tuple (index, of f set, s 0 , s 1 ) 5: for all b i ∈ B do 6: row i .index = i 7: row i .offset = address (b i )function start address 8: if b i ends with indirect jump then 9: Targets ← b j : e ij ∈ E 10: row i .s 0 = Special code 11: row i .s 1 = T argets 12: Process all b j : b j ∈ Targets 13: else if b i ends with a direct conditional jump then 14: row i .s 0 = j : b j is the branch-not-taken target 15: row i .s 1 = k : b k is the branchi .s 1 = k : b k is the jump target

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

The proposed technique is fairly independent of the processor microarchitecture, and can be easily adapted to more complex architectures such as superscalar and VLIW.Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

VII. CONCLUSIONS

In this paper, we presented a scalable, application-specific methodology to safeguard the execution of programs running on embedded processors. We formulated a hierarchical run-time monitoring framework including program attributes such as inter-procedural control flow, intra-procedural control flow and instruction contents within a basic block, which provides protection at different granularities for applications and systems with diverse security requirements. Run-time monitoring is performed by a configurable hardware monitor to ensure minimal performance degradation. Our studies reveal that the proposed architecture is capable of facilitating secure execution of programs in the face of a wide variety of security threats. We believe that such techniques will be useful in addressing the increasing security concerns in embedded system design.

This work was supported by NSF under Grant No. CCR-0326372.


Arijit Ghosh
email: arijitg@ics.uci.edu

Tony Givargis
email: givargis@ics.uci.edu

LORD: A Localized, Reactive and Distributed Protocol for Node Scheduling in Wireless Sensor Networks *

Keywords: Wireless Sensor Network, Coverage, Set Cover

The lifetime of wireless sensor networks can be increased by minimizing the number of active nodes that provide complete coverage, while switching off the rest. In this paper, we propose a distributed and scalable node-scheduling algorithm that conserves overall system energy by minimizing the number of active nodes, localizing the execution to the dying sensor(s), and minimizing the frequency of execution by reacting only to the occurrence of a sensing hole. This effects an increased system lifetime while maintaining coverage over an application-defined threshold value. We compare our algorithm to a network with a centralized nodescheduling algorithm. Our results show equivalent coverage degree over a wide range of sensor networks.

Introduction

The technological advancements in the areas of microelectro-mechanical systems, wireless communications and digital microelectronics have ushered in the era of wireless sensor networks (WSN). The potential applications of these WSNs are innumerable. Geographical applications include detecting environmental hazards, monitoring remote terrain, wildlife observation and provide vigil over battlefield and disaster areas. Personal and societal applications include integrated patient monitoring, diagnostics and drug administration, real-time traffic patterns and personalized shopping amongst others. Other applications include

The diversity in application and the variation in operating conditions necessitate the formulation of new system design approaches. In particular, energy is a major design bottleneck and power-aware system design techniques are required at all levels of the system [START_REF] Chandrakasan | Design considerations for distributed microsensor systems[END_REF] [START_REF] Min | Low-power wireless sensor networks[END_REF]. One of the critical design objectives is to increase the overall network lifetime [START_REF] Tian | A node scheduling scheme for energy conservation in large wireless sensor networks[END_REF]. It is highly impractical to achieve this by battery replacement/recharge as sensors are usually inaccessible. Instead, system energy conservation by reduction of active nodes has been proposed [START_REF] Shih | Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[END_REF] [START_REF] Wang | Integrated coverage and connectivity configuration in wireless sensor networks[END_REF]. The high degree of redundancy is exploited to activate a reduced subset of nodes that provide the same degree of coverage.

In this work, we propose a distributed node-scheduling protocol that achieves all of the following goals. First, the protocol maintains coverage over an application-specific threshold value. Second, the number of scheduled nodes is minimized. Third, the protocol is localized. It is executed only at the point of the dying sensor. This precludes unnecessary participation of most sensors that have not had a change in their state in protocol execution, thereby saving more energy. Fourth, the protocol is reactive. It is scheduled to execute only when a change in the network state could potentially lead to a decrease in the coverage degree. This is very important as computation (in finding the schedule) and the ensuing communication (required for sending the schedule), causes a drain in the overall system energy. By minimizing the number of runs of the algorithm, we contribute an additional degree of energy saving of the whole system that helps in further extending the system lifetime.

The rest of the paper is organized as follows. In Section 2 we discuss previous work. In Section 3, we outline our proposed protocol. In Section 4, we present our experimental results. Finally, we present our conclusions in Section 5.

Previous work

Conserving energy by minimizing active nodes to increase system lifetime has been an active area of research. There have been two objectives for node-scheduling: providing coverage and maintaining connectivity.

Several coverage algorithms have been proposed in literature. In [START_REF] Chakrabarty | Grid coverage for surveillance and target location in distributed sensor networks[END_REF], [START_REF] Meguerdichian | Low power 0/1 coverage and scheduling techniques in sensor networks[END_REF], the authors propose a linear programming based technique for a choice of a minimal set of active nodes. In [START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF], the authors combine computational geometry and graph theoretic techniques for coverage calculation. The maximal breach path and the maximal support path in a sensor network are computed using Voronoi diagram and Delaunay Triangulation techniques. In [START_REF] Meguerdichian | Exposure in wireless ad-hoc sensor networks[END_REF], the same problem has been solved by computing the minimal exposure path. The authors in [START_REF] Clouqueur | Sensor deployment strategy for target detection[END_REF] discussed strategies for node deployment that provide distributed detection. In [START_REF] Ye | Energy efficient robust sensing coverage in large scale sensor networks[END_REF], a probing-based density control algorithm is proposed. Sleeping nodes wake up occasionally to probe their local neighborhood and start working if no live sensors are detected. In [START_REF] Tian | A node scheduling scheme for energy conservation in large wireless sensor networks[END_REF], a coverage-preserving node-scheduling algorithm is proposed. A basic model for coverage-based off-duty eligibility rule is presented which allows a sensor to see if its sensing area is covered by the union of the sponsored sectors of its neighbors.

Similarly, many algorithms have been proposed that maintain connectivity. In [START_REF] Cerpa | Ascent: Adaptive self-configuring sensor network topologies[END_REF], each node assesses its connectivity and adapts its participation in the multi-hop network topology based on the measured operating region. In [START_REF] Chen | Span: An energy efficient coordination algorithm for topology maintenance in ad-hoc wireless networks[END_REF], nodes are turned off based on the necessity for neighbor connectivity. In [START_REF] Xu | Adaptive energy conserving routing for multihop ad hoc networks[END_REF], nodes turn off their communication unit when they are not involved in sending, forwarding or receiving data phases. In [START_REF] Xu | Geography-informed energy conservation for ad hoc routing[END_REF], the proposed algorithm uses geographic location information to divide the sensing area into fixed square grids. Within each grid, there is just one node that is awake and participates in data forwarding. Some other algorithms have been proposed for node scheduling which maintains both coverage and connectivity. In [START_REF] Ye | Peas: A robust energy conserving protocol for long-lived sensor networks[END_REF], the authors proposed an algorithm that allows a configurable approach to maintain both coverage and connectivity, without any guarantee on the degree. In [START_REF] Wang | Integrated coverage and connectivity configuration in wireless sensor networks[END_REF], the protocol can dynamically configure the network to provide different degrees of coverage while maintaining connectivity. It proposed an eligibility rule in which sensors can turn themselves off if all intersecting points between the borders of its sensing radii are covered with the desired degree.

Finally, in addition to coverage and connectivity, some work have considered the impact a node-scheduling algorithm will have on other sensors in the network, notably from a routing perspective. In [START_REF] Gupta | Connected sensor cover: Selforganization of sensor networks for efficient query execution[END_REF], the algorithm considers an additional set of routers over a minimum set of sensors necessary to both cover a region and forward the data. In [START_REF] Perillo | Dapr: A protocol for wireless sensor networks utilizing an application-based routing cost[END_REF], the algorithm used the concept of "application cost", which is based on a sensor's as well as its neighbors' residual energy, and used it to decide the set of active sensors.

While the above-mentioned algorithms achieve coverage or connectivity or both, they run at random times. Depending on when this is invoked, it could result in either sensing holes or unnecessary drain of energy. In addition, all sensors execute the algorithm, thus causing a further reduction of overall system energy. In our approach, we optimize the location and frequency of execution. The protocol runs, at the point where and at the instance when, the sensing hole is about to appear. These optimizations are added advantages inasmuch that we minimize the number of active sensors and maintain both coverage and connectivity.

Technical approach

Preliminaries

We consider a sensor network with η sensor nodes deployed over a continuous, arbitrary shaped area A. Let F be the set of sensor nodes, F = {s 1 , s 2 , . . . , s η }. Let s i .area be the finite, continuous and arbitrary-shaped area that can be sensed by sensor s i .

We present a model to quantize a continuous region in a 2-D space. A 2-D space is partitioned into an imaginery grid with an arbitrarily chosen point of origin. Given the grid, any arbitrary shaped area is represented as a set, containing the coordinates of the cells that are fully or partially covered by the area. The set representation allows many operations on the area (e.g. overlap) to be expressed in terms of set operations (e.g. intersection). This improves on space and time complexity as sets can be efficiently represented and manipulated in computer systems. Additionally, it eliminates the imposition of any restriction on the shape of the sensing area or the deployment area. Further, the granularity of the grid is application-specific and can be varied to trade off between accuracy and computational complexity.

Problem formulation

The node-scheduling problem is to identify a minimal subset C of F that covers A. More specifically, compute C:

A ⊆ si ∈ C and C ⊆ F and |C| is minimal s i .area.
This problem closely resembles the set-covering problem which is a generalization of the NP-complete vertexcover problem and is therefore NP-hard [START_REF] Cormen | Introduction to Algorithms[END_REF]. There are well-known centralized heuristics for the set-cover problem. However, none of those solutions scale well when applied to large sensor networks. As such, we propose a localized, reactive and distributed network coverage protocol (LORD), that despite being a heuristic, scales extremely well with the network size producing comparably good results. We compare our heuristic to an efficient centralized approximation algorithm.

The LORD protocol

LORD consists of two phases, the set-up phase and the steady phase. In the set-up phase, all the sensors individually run a heuristic algorithm to decide their initial state. Every ON sensor continues running until it either dies or receives an intimation to be turned off. In the steady phase, all dying sensors run a localized heuristic algorithm and nominate the sleeping sensors that can cover for themselves. The simple protocol of neighbor set-up and immediate participation ensures that scalability, both in terms of the monitored area and the number of sensors, can be achieved. We will consider the example area A as shown in Figure 1. We consider 5 nodes, s 1 . . . s 5 , deployed over A.

Our protocol assumes a perfect and reliable communication layer. Communication is achieved by three primitives. Send allows communication between any two sensors in the network. Broadcast allows communication between two sensors who are one hop away. Two sensors whose sensing areas overlap are considered to be one hop away from each other and can communicate with each other directly [START_REF] Tian | A node scheduling scheme for energy conservation in large wireless sensor networks[END_REF]. Receive allows messages to be received at any sensor. The primitives together implement a synchronization mechanism, the details of which have been excluded for brevity.

Set-up phase.

When the network is being deployed, the set-up phase runs at each sensor s i to determine its initial state (Algorithm 2). The current state of a sensor is denoted by s i .state, and is either OFF or ON.

Each sensor first builds up its list of neighbors, s i .NL (Algorithm 2, Line 5). A sensor s i is a neighbor of sensor s j , iff their sensing areas overlap.

s i .NL = si.area ∩ sj.area = ∅ i = j {s j }.
This is achieved by broadcasting a mesage containing its sensing area and listening for similar messages. Every sensor s j , from which s i receives a message, is added to its neighbor list s i .NL (Algorithm 1). The sensor s i saves all its neighbors' sensing areas as they are used subsequently in the set-up phase as well as the steady phase. For example, s 1 .NL = {s 3 ,s 4 ,s 5 }.

s i .NL ← s i .NL ∪ {s j } 7:
save(s j .area) 8: end while

The sensor s i defers its decision on its intial state until all sensors s j such that s j ∈ s i .NL and j < i have made their decisions (Algorithm 2, Lines 13-26). This simple heuristic serializes the decision making amongst sensors thereby completely eliminating assumptions between sensors on their respective states. The ordering amongst sensors can be easily imposed by leveraging the underlying grid, making it easily scalable to addition of new nodes. Simultaneously, the sensor s i also updates its Unique Area, s i .UA (Algorithm 2, Lines 20-21). At any time t, s i .UA represents that part of the sensing area of s i which is not covered by any of its "ON" neighbors. The sensor s i decides to turn itself ON iff its sensing area covers some part of the coverage area A that is not covered by any other sensor at that instance of time, i.e., s i .UA > 0 (Algorithm 2, Lines 27-31). In our example, s 1 and s 2 can make their decisions as soon as they build up their neighbor lists. However, s 3 has to wait for both s 1 and s 2 , s 4 has to wait for s 1 , s 2 and s 3 etc. From our definition of Unique Area, we note that all sensors from s 1 to s 4 have to turn themselves ON while s 5 can turn itself OFF.

Once all the remaining neighbors of sensor s i have determined their states (Algorithm 2, Lines 33-41), it is possible that sensor s i is redundant as all of its sensing area is covered by some combination of its neighbors. To eliminate this redundancy, each ON sensor s i reevaluates its initial decision. Again, to remove ambiguity, sensor s i waits till all its ON neighbors s j such that j < i have completed their reevaluation (Algorithm 2, Lines 42-50). This ensures that no two sensors make any assumptions about the state of the other, thereby eliminating the possibility of a sensing hole. Sen- broadcast(s i .state) 54: end if sor s i recomputes its s i .UA and if that is equal to zero, s i can turn itself off. (Algorithm 2, Lines 51-54). In our example, s 2 , on reevaluation, finds that s 2 .UA is equal to zero and hence, turns itself off. In our protocol, we assume that all OFF sensors periodically wake up so that they can receive messages from their ON neighbors [START_REF] Wang | Integrated coverage and connectivity configuration in wireless sensor networks[END_REF].

By serializing this minimization step and restricting it to ON sensors, it is guaranteed that the minimization always ends after one iteration as only the sensors s i for which s i .UA is greater than zero is on.

Steady phase.

The steady phase algorithm is invoked, at and when, each sensor s i dies. We assume that s i can internally monitor its energy state and run its own replacement algorithm before it dies completely. The algorithm generates a set, s i .replace, consisting of a minimum number of sleeping neighbors, that can cover s i .UA. In our example, s 3 dies at t=3. Hence the steady phase algorithm is invoked at s 3 at t=3. Algorithm 3 find replacement()

s j .area
The minimum set cover(MSC) algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] is used to generate a close approximate solution. It then sends a message to all s j ∈ s i .replace (Algorithm 3). In our example, s 2 and s 5 are the sleeping neighbors of s 3 . By running the MSC, we compute s 3 .replace = {s 5 }.

The waking up of one or more sensors could now generate redundant active sensors. Hence, the same reevaluation as outlined in the in the set-up phase is run at only the ON neighbors of every s j ∈ s i .replace, thereby turning OFF all redundant sensors. In our example, the waking up of sensor s 5 as a replacement for s 3 makes sensor s 4 redundant. Hence, the sensor s 4 can turn itself off to conserve energy. By providing a strict upper bound (equal to the total number of dying sensors) on the number of invocations of the steady phase algorithm and by localizing the execution, significant energy savings can be done by reducing both communication and computation.

Experimental results

For our experiments, we consider an area 50m × 50m. We set the granularity of the grid to 1 cm which produces a quantization error of less than 1%. We consider circular sensors placed randomly over this area. The sensing area of each is equal to its communication area and both are set to be a circle of radius 10m. This is done to simplify the experiments and has no effect on the protocol. We deploy 80, 90, 100, 110, 120 and 130 sensors. We assume that the communication is reliable and that all sensors lose their energy at a uniform rate. Observing that certain applications might require a "best-effort" coverage, we set a coverage threshold T, that represents the percentage of the total number of grids that can be covered by the available sensors.

We compare our algorithm to a highly efficient centralized MSC algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] that runs in an imaginary super node which has unlimited power and complete global knowledge. MSC is a greedy approximation algorithm with a logarithmic ratio bound and returns a set cover not too much larger than the optimal set cover.

Our comparisons are made on three points. First, we compare the life of the network. This directly reflects the energy saved. Second, we compare the cumulative communication cost, which is the number of message transmissions T x , over the entire life. While T x is the number of hops between source and destination for MSC, it is the sum of the neighbors of all s i that change state in LORD. Since the payload of the transmitted message is constant in both cases, we ignore this for our comparisons. Third, we com- Owing to the grid model, all computations in our system are mere set operations. Assuming constant time for all setoperations of same sizes, our computation costs can be expressed as the number of set operations.

Figures 2,3, 4 represent the lifetime, communication and computation costs of the two algorithms with each sensor having different energy and T equal to 80%, 85%, 90%, 95% and 100% respectively.

It is observed that LORD provides the same degree of coverage for comparable time duration. The communication costs of LORD is higher than MSC as the latter communicates only with the sensors that need to change state while the former requires all sensors changing state to communicate with all of their respective neighbors. However, more than 50% of LORD's cost is incurred only once, during the set-up phase (Figures 5), indicating that the overhead during the steady phase is minimal, thereby ammortizing the communication cost over the entire lifetime. This results in overall savings in system energy. The computation costs of MSC, however, exceeds that of LORD, since MSC tries to generate a cover for the entire area A, from the list of all available sensors, while LORD generates a cover for only the dying sensor from the list of its OFF neighbors.

Conclusion

In this paper, we have presented a distributed, localized and reactive protocol for node-scheduling in a sensor network. The protocol has a two phase algorithm in which it first decides the sensors that need to be turned on and then it turns off any redundant active sensors, thereby minimizing the number of on sensors. We compared our algorithm to a highly efficient centralized algorithm and have shown that our results are comparably good. As future work, we intend to incorporate other system dependent parameters, like routing and communication, in our protocol.

Figure 1 .

 1 Figure 1. Coverage area with 5 sensors.

  s i .UA = s i .areasj ∈ si.NL and sj.state = ON s j .area

Figure 2 .

 2 Figure 2. System lifetime: random life.

Figure 4 .

 4 Figure 3. Communication: random life.

Figure 5 .

 5 Figure 5. Communication overhead.

  Algorithm 2 self determination() 1: temp LOW ← ∅ 2: temp HIGH ← ∅ 3: temp ON ← ∅ 4: s i .UA ← s i .area 5: create neighbor list() 6: for every s j in s i .NL do temp LOW ← temp LOW -{s j } temp HIGH ← temp HIGH -{s j } temp ON ← temp ON ∪ {s j }

	7:	if j < i then
	8:	temp LOW ← temp LOW ∪ {s j }
	9:	else
	10:	temp HIGH ← temp HIGH ∪ {s j }
	11:	end if
	12: end for
	13: while |temp LOW | > 0 do
	14:	s j .state ← receive()
	15:	if s j ∈ temp LOW then
	16:
	17:	else
	18:
	19:	end if
	20:	if s j .state = ON then
	21:	s i .UA ← s i .UA -s j .area
	22:	if j < i then
	23:
	24:	end if
	25:	end if
	26: end while
	27: if |s i .UA| > 0 then
	28:	s i .state ← ON
	29: else
	30:	s i .state ← OFF
	31: end if
	32: broadcast(s i .state)
	33: while |temp HIGH | > 0 do
	34:	s j .state ← receive()
	35:	if s j ∈ temp HIGH then
	36:	temp HIGH ← temp HIGH -{s j }
	37:	end if
	38:	if s j .state ← ON then
	39:	s i .UA ← s i .UA -s j .area
	40:	end if
	41: end while
	42: while |temp ON | > 0 do
	43:	s j .state ← receive()
	44:	if s j .state = OFF then
	45:	s i .UA ← s i .UA + s j .area
	46:	end if
	47:	if j < i then
	48:

temp ON ← temp ON -{s j } 49: end if 50: end while 51: if s i .state = ON and |s i .UA| = 0 then 52: s i .state ← OFF 53:

  .replace ← compute MCS(s i .UA, temp) 13: for each s j ∈ s i .replace do

	8:	else
	9:
	10:	end if
	11: end for
	12: s 14:	send(s j , "ON" );
	15: end for
		s i .UA ⊆
		sj ∈ si.replace and
		sj .state = OF F and
		si.replace ⊆ si.NL and
		|si.replace| is minimal

1: At: Each dying sensor s i 2: temp ← ∅ 3: s i .replace ← ∅ 4: s i .UA ← s i .area 5: for each s j ∈ s i .NL do 6: if s j .state = OFF then 7: temp ← temp ∪ {s j } s i .UA ← s i .UAs j .area i

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work was supported by NSF Grant # CCR-0205712.

robotic control in manufacturing process, warehouse inventory and environmental control in public places [7][16].


Saibal Mukhopadhyay

Swarup Bhunia
email: bhunias@ecn.purdue.edu

Kaushik Roy
email: kaushik>@ecn.purdue.edu

Modeling and Analysis of Loading Effect in Leakage of Nano-Scaled Bulk-CMOS Logic Circuits*

In nanometer scaled CMOS devices significant increase in the subthreshold, the gate and the reverse biased junction band-toband-tunneling (BTBT) leakage, results in the large increase of total leakage power in a logic circuit. Leakage components interact with each other in device level (through device geometry, doping profile) and also in the circuit level (through node voltages). Due to the circuit level interaction of the different leakage components, the leakage of a logic gate strongly depends on the circuit topology i.e. number and nature of the other logic gates connected to its input and output. In this paper, for the first time, we have analyzed loading effect on leakage and proposed a method to accurately estimate the total leakage in a logic circuit, from its logic level description considering the impact of loading and transistor stacking.

INTRODUCTION

Aggressive scaling of CMOS devices in each technology generation has resulted in significant increase in the leakage current in CMOS devices. In nano-scaled devices the three major leakage components can be identified as: Subthreshold leakage, Gate leakage and reverse biased drain-substrate and source-substrate junction Band-To-Band-Tunneling (BTBT) leakage [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. In a transistor, the relative magnitudes of these components depend on the device geometry (namely, channel length, oxide thickness and transistor width), the doping profiles and the operating temperature. In a CMOS device the different leakage components interact strongly with each other. On the other hand, the different leakage components depend on the terminal voltages of a transistor. Hence, in logic circuits leakage components interact with each other through the node voltages. If the output node (say, N 0 ) of a gate (say, G) is connected to the input of the other gates (G out1 , G out2 , ..,G outn ), the gate leakage from these other gates change the voltage at OUT1 (Fig. 1). This effect can be defined as the "loading effect" and it modifies the leakage of the gate G, G out1 , …, G outn . In this work, we have analyzed the impact of "loading effect" on the leakage of a logic gate and logic circuit. In particular, in this paper:

We have described the interaction of different leakage components in a device and in a circuit.

We have evaluated effect of loading on the individual leakage components and the total leakage of a logic gate.

We have proposed a methodology to efficiently and accurately estimate the total leakage of a logic circuit from its gate-level description considering loading effect.

LEAKAGE COMPONENTS IN A DEVICE

Device Structures

Leakage analysis presented in this work is based on the transistors of 50nm gate length designed using the device simulator MEDICI [START_REF] Medici | Two-dimensional semiconductor device simulation program[END_REF]. The device structure and "super halo" doping profiles given in [START_REF]Well-Tempered[END_REF] were used in designing the transistors. The parameter extraction tool, AURORA [START_REF]AURORA: Device characterization and parameter extraction system[END_REF] was used to extract BSIM4 SPICE model parameters of the designed devices to do SPICE simulations.

Leakage Components

In nano-scaled CMOS devices the major leakage components are shown in Fig. 2. The details of individual leakage components are given below:

(1) Subthreshold current (I ds ):

The subthreshold current in a transistor is caused by the diffusion of the minority carriers from the source to the drain.

The subthreshold current depends exponentially on the threshold voltage of a transistor. In nano-scaled devices the short channel effects (penetration of the drain electric field into the channel) (SCE) reduces the threshold voltage thereby increasing the subthrshold current [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. Due to SCE, the subthreshold current increases with an increase in the drain bias (Drain Induced Barrier Lowering) and reduction in the channel length (Vth-roll off). At a high oxide electric field (sub-100nm regime), the quantization of the electron energy in the channel region tends (2) Gate Direct Tunneling Current (I gate ) At ultra-thin gate oxide regime, due to the high electric field and low oxide thickness, electrons can tunnel through the gate oxide. This is known as the direct tunneling of electrons and results in a large gate leakage in nano-scale transistors. An increase in the supply voltage and/or reduction in the oxide thickness, result in an exponential increase in the gate tunneling current [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF][START_REF][END_REF]. Major components of gate tunneling in a scaled MOSFET are: (3) Junction Band-To-Band-Tunneling current (I JN ) Application of a reverse bias across the highly doped p-n junction results in the tunneling of electrons from the valence band of p-side to the conduction band of n-side [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. This is known as junction band-to-band-tunneling (BTBT) current. In nano-scale MOSFETs due to the use of high junction doping ("Halo" implants used to suppress SCE), large junction BTBT occurs at "off" state with drain at V DD and substrate at ground (at high drain-to-substrate reverse bias) [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. The junction BTBT exponentially increases with an increase in the junction doping and supply voltage. [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]

Reverse Biased Junction BTBT

Gate

Total Leakage in a Transistor

The total leakage in a device is the summation of the three major leakage components (I total =I BTBT + I sub + I gate ). For leakage estimation the device can be modeled as a combination of voltage controlled current sources where each current source represents a current component (Fig. 3) [START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF].

INTERDEPENDENCE OF LEAKAGE COMPONENTS IN A DEVICE

The subthreshold, the gate and the junction BTBT leakage depend on each other through device geometry (particularly oxide thickness), doping profile and temperature. Increasing the Halo doping concentration increases the junction BTBT (by increasing the junction field) whereas it reduces the subthreshold current (by reducing the short channel effect) [1-3] (Fig. 4(a)). The gate leakage is insensitive to halo doping concentration. Increasing the oxide thickness reduces the gate leakage. Higher oxide thickness also increases the short channel effect, thereby increasing the subthreshold leakage in nanoscaled transistors [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF] (Fig. 4(b)). The junction BTBT is not a strong function of the oxide thickness. The different leakage components show different temperature dependence. Subthreshold current increases exponentially with temperature whereas the gate tunneling current is almost insensitive to temperature variation. Due to the reduction of the band-gap at a higher temperature, junction BTBT increases (marginally) with temperature (Fig. 4(c)) [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF][START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF][START_REF] Taur | Fundamentals of Modern VLSI Devices[END_REF]. It can be observed that, at room temperature (T=300K) the gate leakage and the junction BTBT dominate over subthreshold current, while at an elevated temperature, subthreshold leakage is the dominant component of the overall leakage. Hence, in active mode, subthreshold is the major component of leakage.

INTERACTION OF DIFFERNENT LEAKAGE COMPONENTS IN CIRCUITS

In a logic circuit different leakage components interact with each other through the internal nodes. Such an interaction changes the internal node voltages in a circuit and hence, modifies the leakage of individual logic gates and a logic circuit. The interaction of different leakage components determines the leakage of a logic gate due to "stacking effect" [START_REF] Mukhopadhyay | Gate leakage reduction for scaled devices using transistor stacking[END_REF], [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF]. It has been shown in [START_REF] Mukhopadhyay | Gate leakage reduction for scaled devices using transistor stacking[END_REF] that the leakage of a logic gate at different input vectors depends on the relative strength of the different leakage components in a device. For example, for a subthreshold leakage dominated device, the minimum leakage vector in a 2input NAND gate is "00", while, for a gate leakage dominated device it is "10". In [START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF], authors have discussed the method to estimate the leakage of a logic gate considering the interaction of leakage components within a logic gate (intra-gate interaction). However, it does not consider the interaction of leakage components of different logic gates (inter-gate interaction). To understand the impact of inter-gate interaction of leakage at the circuit level, let us consider the circuit shown in Fig. 1. The leakage of inverter G can be evaluated by solving Kirchhoff's Current Law (KCL) at the node N 0 (i.e. output node of G), given by (Fig. 1). Voltage at N 0 (V N0 = f(I ddP , I ddN )) can be obtained by solving [START_REF] Roy | Leakage Current Mechanisms and Leakage Reduction Techniques in Deep-Submicron CMOS Circuits[END_REF]. However, since node N 0 is also connected to the inputs of inverters G 1 to G n , the gate leakage from these inverters will be added to the node N 0 . Hence, the KCL at node OUT will modify to:

0 d dP d dN ga teN G i ga teP G i i load gates I I I I (2)
Hence, V N0 also depends on the gate leakage of the NMOS (I gateN-Gi ) and PMOS (I gateP-Gi ) of the inverters 1) will be different from the V N0 obtained from [START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF]. The modification of V N0 has following effects:

G 1 to G N (V N0 =f(I ddP , I ddN , I gateN-Gi , I gateN-Gi )). If 0 ) ( Gi gateP Gi gateN I I , V N0 obtained from (
A change in the output voltage (V OUT-G V N0 ) of inverter G will modify its gate, subthreshold and junction BTBT leakage.

A change in the input voltage (V IN-Gi V N0 ) of inverters G 1 to G N will also modify their subthreshold (principally) and gate leakage. Hence, the leakage of a gate depends on its input loading (i.e. total gate leakage of other gates connected to its input node I L-IN ) and output loading (total gate leakage of other gates connected to its output node I L-OUT ). Thus we can define the input (LD IN ) and output (LD OUT ) loading effect as the change in the leakage of a logic gate due to its input and output loading, respectively. LD IN and LD OUT can be expressed as:

( ) ( ) ( ) ( ) G L I N N O M IN L IN N O M G L O U T N O M O U T L O U T N O M L I L L D I L L I L L D I L (3)
where, L NOM is the nominal leakage of a gate in isolation (i.e. without any output and input loading); L G (I L-IN ) is the leakage of the gate with input loading I L-IN ; and L G (I L-OUT ) is the leakage of the gate with output loading I L-OUT . The overall loading effect (LD ALL ) depends on both input and output loading and given by: ( , ) ( , )

G L I N L OU T NO M ALL L IN L OUT NOM L I I L LD I I L (4)
For the logic gates with multiple inputs, there will be a LD IN associated with each input. Hence, the LD ALL for a multiple input gate is given by:

( , ) ( , ) 1, 2, ..., , , # G L IN k L O U T N O M AL L L IN k L O U T N O M L I I L L D I I L k N w h ere N is th e o f in p uts ( 5
)
Fig. 5 shows the variation of LD IN , LD OUT and LD ALL of an inverter with a variation in the I L-IN and I L-OUT at different input conditions for the 25nm device. It can be observed that, the impact of loading increases with increase in the loading currents. Moreover, LD values strongly depend on the input condition of the inverter. The total leakage of the inverter with input '0' and '1' is given by:

_0 _ _ _ _ _ _ _ _1 _ _ _ _ _ _ _ 0, 1: ( ) 1, 0 :
( ) Input loading effect (both on the total leakage and on the subthreshold leakage) is more observable with input '0' (Fig. 5). This is due to the fact that, with input '0' the subthreshold leakage is principally contributed by the 'off' NMOS transistor, whereas 'off' PMOS transistor determines the subthreshold leakage with input '1'. Since short channel effect is more serious in PMOS [START_REF]AURORA: Device characterization and parameter extraction system[END_REF], the subthreshold leakage in PMOS is less sensitive to V gs than NMOS. V ds sensitivity of PMOS subthreshold leakage is higher than that of NMOS subthreshold current. Since the output loading modifies the V ds of a transistor it has a stronger impact on PMOS (i.e. when input='1' and output='0') subthreshold leakage. The impact of output loading on junction BTBT is also stronger with output '0' (PMOS contributes to junction BTBT) than with output '1' (NMOS determines junction BTBT). This is due to the fact that, PMOS has a larger junction BTBT current [START_REF] Mukhopadhyay | Accurate Estimation of Total Leakage Current in Scaled CMOS Logic Circuits Based on Compact Current Modeling[END_REF]. Consequently, effect of output loading is higher with output at '0'. Fig. 6 shows the loading effect considering both the input and output loading (i.e. LD ALL ). It can be observed that LD ALL is normally higher with input = '0'. Analysis of loading effect on the 2-input NAND gate shows the input vector dependence of the loading effect (Fig. 7). From Fig. 7 it can be observed that, input loading is higher if at least one of the inputs is at '0' (i.e. with vectors '00', '01', '10'). This is because of the fact that, the input loading has a stronger effect on the subthreshold leakage of an 'off' NMOS. Due to the reduction in the subthreshold leakage by the stacking effect [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF], input loading has less effect with input '00' compared to the inputs '01' or '10'. As observed in the case of the inverter, the effect of output loading is higher with the output equal to '0'. Moreover, depending on the input vector the loading effect may increase or reduce the total leakage of the gate.

INV
From the above discussion it can be concluded that:

The loading of a logic gate changes the different leakage components and the total leakage. The gate leakage is the cause of the loading effect. However, its effect is mostly observed in the subthreshold and the junction BTBT leakage. The loading effect depends on the input and output logic levels, the magnitude, and the relative strength of the different leakage components in PMOS and NMOS.

VARIATION IN THE LOADING EFFECT

In this section, we discuss the impact of change in relative strengths of different leakage components with device design, temperature and process parameter variations on loading effect.

Effect of relative strengths of leakage components

Fig. 8 shows the input and output loading effect of an inverter designed with devices with different relative strengths of the leakage components. The subthreshold leakage, the gate leakage and the junction leakage dominates the total leakage in device D 25-S , D 25-G and D 25-JN , respectively (total leakage is same in the three devices). It has been discussed earlier that, the input loading has the strongest impact on the subthreshold leakage. Hence, the input loading effect is most pronounced in the inverter designed with D 25-S (subthreshold leakage dominated device). Input loading has a weaker impact on the inverters designed with D 25-JN (junction leakage dominated device) and D 25-G (gate leakage dominated device). On the other hand, output loading effect is most pronounced in the inverter designed with D 25-JN (since, junction BTBT is the strongest function of the output loading among the three different leakage components). In general the loading has least impact on the gate leakage dominated device.

Impact of temperature on the loading effect.

Since the gate leakage is a weak function of temperature (Fig. 4c), it can be concluded that the "cause of the loading" does not increase significantly with temperature. But, the "effect of loading" (i.e. the subthreshold and the junction tunneling current) are strong function of temperature. With the increase in the temperature the effect of loading on the subthreshold leakage significantly increases (Fig. 9). An increase in temperature exponentially increases the subthreshold leakage in device. This has a two fold impact on the loading effect. First, the increase in the subthreshold leakage due to an increase in the |V GS | of the NMOS in the inverter G is higher at a higher temperature. Second, the contribution of the subthreshold current and the junction current of the PMOS of the inverter D to node IN (i.e. input of G and output of D), increases at a higher temperature. Hence, the voltage-rise in the node IN (i.e.

|V GS | of NMOS) increases, thereby increasing the subthreshold current considerably. However, the increase in the input voltage of the inverter G reduces its output voltage (due to larger subthreshold current of NMOS). This reduction in the output voltage coupled with the increase in the input voltage, reduces the gate and the junction BTBT current (as explained in section. 4). Thus, the loading effect for the gate and the junction BTBT also increases with the temperature. However, since the subthreshold, the gate, and the junction BTBT moves in the reverse direction with the increase in the temperature, the impact of the temperature on the loading-effect of the total leakage is less significant.

Impact of process variation

The variation in the process parameters (e.g. channel length (L), oxide thickness (T ox ), threshold voltage (V th ), supply voltage (V DD ) etc.) result in a large variation in the leakage in transistors and logic gates [START_REF] Mukhopadhyay | Modeling and estimation of total leakage current in CMOS devices considering the effect of parameter variation[END_REF]. The subthreshold leakage is extremely sensitive to process variation, whereas, the gate leakage and the junction BTBT leakage are less sensitive [START_REF] Mukhopadhyay | Modeling and estimation of total leakage current in CMOS devices considering the effect of parameter variation[END_REF]. The application of the random variation in L, V th , and T ox of different transistors and in V DD results in the significant variation in the different leakage components and the total leakage (Fig. 10) (obtained through 10,000 Monte-Carlo simulations in SPICE). It can be observed that, the loading effect considerably modifies the leakage distributions. The maximum modification can be observed in the subthreshold leakage. It can be observed that with an increase in the inter-die variation loading effect on the mean and the standard deviation increases (Fig. 11). Particularly, consideration of the loading significantly increases the standard deviation (with Vt=50mV, loading increases the standard deviation by more than 40%). This indicates that the maximum value of leakage significantly increases due to the loading effect (almost by 2X) considering parameter variation. The observations from the previous discussion can be summarized as follows:

Increase in the subthreshold leakage (due to device design or increase in temperature or parameter variations) has a strong impact on the overall loading effect. Consideration of the loading effect significantly increases the leakage spread of a circuit under parameter variation.

LOADING EFFECT AT CIRCUIT LEVEL

Traditionally, leakage current in a circuit is calculated by determining individual leakage values for each gate and accumulating them. This procedure is valid assuming that leakage current in a gate is independent of the circuit topology i.e. it is not affected by the leakage in other gates. However, due to loading effect, the leakage of gate depends on the leakage of the other gates. Hence, we need to consider propagation of loading effect across logic gates for accurate circuit-level estimation of leakage current in nano-scale CMOS. This is similar to the propagation of slope changes for delay calculation, Leakage of a logic gate is related to the voltage difference in its input and output nodes due to the loading effect. The cause of the loading effect is the gate leakage and its effect is observed in the subthreshold, the junction BTBT, and the gate leakage. Let us look into the case of output loading effect for the simple circuit shown in Fig. 1 (i.e. a driver D1 that drives gates Gin1, G in1 ,…, G inm and fanout gates G out1 , G out2 ,…, G outn ). Also consider that, G out1 is connected to the input of the inverters H out1 , H out2 ,..., Houtp. For the inverter G, output voltage difference due to loading effect is determined by the leakage of the fanout gates G out1 ,…,G outn . However, leakage of the gates G out1 …, G outn is again determined by the leakage current of H out1 ,…,H outp .

Leakage current of H out1 ,..,H outp are, again, related to the leakage of following gates. Similar relation holds through input loading.

Hence, in order to estimate circuit leakage, we need to simultaneously solve a set of KCL equations with n variables, where n is the number of internal nodes of the circuit. We can, however, avoid the need for solving simultaneous equations and come up with a simple method for circuit-level leakage estimation in presence of loading effect. It has been observed that the effect of loading on the gate leakage is not very high. The gate leakage of the gates H out1 ,...,H outn in Fig. 1 will modify the voltage at the output of G out1 , thereby modifying its leakage. However, it can be observed from earlier figures that, the change in the output voltage of G out1 will not modify the gate leakage of G out1 strongly. Thus, the effect of the gate leakage of H out1 ,...,H outn on the voltage at the output of inverter G is minimal. Thus, the modification of the leakage of G due to the gate leakage of H out1 ,...,H outn is negligible. In other words, the propagation of the loading effect (output loading effect in this case) beyond one level is negligible. A similar argument can also be made to explain that input loading effect does not propagate strongly beyond one level. Based on the above observation, we have developed an efficient algorithm that estimates different components of leakage considering loading effect. Leakage values generated by the algorithm closely matches results obtained from spice simulations (Fig. 12a), while being about 1000X faster than spice in run time. Flow chart for the algorithm is presented in Fig. 13. We start with a graph representing the circuit, with each vertex representing a logic gate and each edge representing a net. First, the vertices in the graph are topologically sorted [START_REF] Cormen | Introduction to Algorithms[END_REF] and the leakage values are initialized to zero. Logic values are propagated through the circuit nodes for the input pattern. Then, for each node in the graph in topological order, we compute the total input and output loading current due to the gate leakage of the corresponding gates. The algorithm is implemented in C programming language and tested on six ISCAS89 benchmark circuits, a multiplier and an 8-bit ALU and run for 100 random vectors at T=300K. The results of the leakage estimation using the proposed algorithm are presented in Fig. 12b and13c. The Fig. 12b shows that the average increase in total leakage due to loading effect is about 5%. However, the variation is the sub-threshold leakage much higher (~8%) followed by the junction BTBT (~4.5%) and the gate leakage (~3.6%) (for a subthreshold leakage dominated device). Fig. 12(c) shows the respective leakage values for maximum variation due to loading over 100 vectors. The observations about the impact of loading on circuit level analysis can be summarized as follows Loading effect depends on circuit topology. The loading effect in a circuit strongly depends on the applied input pattern. The input pattern for which we obtain the minimum total leakage changes due to the loading effect. This has significant impact on the input vector control based leakage control techniques [START_REF] Johnson | Models and algorithms for bounds on leakage in CMOS circuits[END_REF]. It should be noted due to the loading effect, the subthreshold leakage tends to increase while the gate and the junction BTBT tend to reduce. Moreover, in a large circuit, loading effect increases the total leakage of some logic gates while reduces that of some other gates. This is due to the input vector dependence of the loading effect (Fig. 7). Due to these factors, the overall change in the total circuit leakage due to loading is not very high (~5%).

CONCLUSIONS

In this paper, we have analyzed loading effect (caused by the voltage difference at the input/output nodes of a logic gate due to gate leakage of the gates connected to its input/output) on different leakage components of a circuit. Interaction of leakage components in a circuit through loading effect is investigated. We have demonstrated that loading effect varies with temperature and parameter fluctuations. We have presented an algorithm for fast and accurate estimation of circuit leakage considering the loading effect. Our analysis shows that, the loading effect modifies the leakage of a logic gate by 8-10%. However, in a large circuits, depending on the input vector, leakage of different logic gates moves in different directions (some increases and some reduces). In our experiments, we observed that, due to this cancellation effect, the net change in the overall leakage due to loading effect is about 5% in large circuits.

Fig. 2 *

 2 Fig.2 Leakage components Fig.3. Leakage current sources in a device in a transistor Fig 1. Illustration of loading effect for the logic gate G.

  (a) gate to S/D overlap region current components (I gso & I gdo ), (b) gate to channel current (I gc = I gcs + I gcd ), and (c) gate to substrate current (I gb ) [7].

Fig. 4 :Fig. 5 :

 45 Fig. 4: Variation of different leakage current components with the (a) Halo doping and (b) device geometry, and (c) temperature.

( 6 )

 6 Due to input loading, the voltage at the input node of the inverter gets modified. If input of G in Fig. 1 is at '0' (i.e. V IN =0V), the gate currents of input loading gates G IN1 ,…,G Inn increases V IN from 0V. If the input is at '1' (i.e. V IN =V DD ) the gate leakage through G IN1 ,…, G INn reduces the voltage from V DD . This increases the |V GS | of the 'off' transistor (i.e. NMOS at input='0' and PMOS at input='1') thereby increasing the subthreshold leakage of the inverter G. On the other hand, it marginally reduces the gate currents of the PMOS and NMOS by reducing the |V GD | (PMOS and NMOS) and |V GS | (of PMOS at input='0' and NMOS at input='1'). Since the junction leakage is a weak function of the gate voltage, input loading has minimal impact on the junction leakage [2]. Similarly, for output loading, V OUT increases from 0V when output is '0' and decreases from V DD when output is '1'. This reduces (a) the |V DS | of the 'off' transistor (PMOS when output= '0' and NMOS when output='1'), thereby reducing the subthreshold leakage; (b) |V GD | of the PMOS and NMOS thereby reducing the gate leakage; and (c) |V DB | of the transistor contributing to the junction BTBT (e.g. PMOS when output is '0' and NMOS when output is '1'), thereby reducing the junction leakage. Hence, due to input loading subthreshold leakage increases while gate leakage reduces and junction leakage remains almost constant (Fig.5). On the other hand, due to output loading all the three components of the leakage reduces (Fig.5). It can also be observed from Fig.5that, the input loading effect (LD IN ) is most pronounced in the subthreshold leakage as it changes the V gs of the 'off' transistor. Output loading (LD OUT ) has the strongest impact on the junction leakage by changing |V DB | of the transistor which contributes to the junction BTBT. The gate leakage experience minimum change due to the loading effect.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Variation of leakage due to loading at both input and output with: (a) input '0' and (b) input '1'.

Fig. 8 :Fig. 9 :

 89 Fig. 8: Loading effect for different devices: (a) input & (b) output loading effect with input '0'; and (c) input & (d) output loading effect with input '1'.

Fig. 11 :

 11 Fig. 11: Effect of loading on the mean (left) and standard deviation (right) of the total leakage in an inverter (input='0').

Fig. 10 :

 10 Fig. 10: Distribution of different leakage components of an inverter (input='0' and output='1') with and without loading (input loading of 6 inverters and output loading of 6 inverters).

Fig. 13 :Fig. 12 :

 1312 Fig. 13: Flowchart to estimate leakage components for a circuit considering the loading effect.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE