17

Security and Privacy

17.1 Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . . . 461
17.1.1 Encryption and Decryption . . . . . . . . . . . . . . . . . . . 461
17.1.2 Digital Signatures and Secure Hash Functions . . . . . . . . . 465
Sidebar: Implementation Matters for Cryptography . . . . . . . . . . 466
17.2 Protocol and Network Security . . . . . . . . . . . . . . . . . . . . 469
17.2.1 Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . 469
Sidebar: Reverse Engineering Systems to Improve Security . . . . . . 472
17.2.2 Cryptographic Protocol Design . . . . . . . . . . . . . . . . . 473
17.3 Software Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
17.4 Information Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
17.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
17.4.2 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
17.4.3 Analysis and Enforcement . . . . . . . . . . . . . . . . . . . 484
17.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
17.5.1 Sensor and Actuator Security . . . . . . . . . . . . . . . . . . 486
17.5.2 Side-channel Attacks . . . . . . . . . . . . . . . . . . . . . . 488
17.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

Security and privacy are two of the foremost design concerns for cyber-physical systems
today. Security, broadly speaking, is the state of being protected from harm. Privacy is the
state of being kept away from observation. With embedded and cyber-physical systems
being increasingly networked with each other and with the Internet, security and privacy
concerns are now front and center for system designers.
In a formal sense, there are two primary aspects that differentiate security and privacy
from other design criteria. First, the operating environment is considered to be signif-
icantly more adversarial in nature than in typical system design. Second, the kinds of
properties, specifying desired and undesired behavior, are also different from traditional
system specifications (and often impose additional requirements on top of the traditional
ones). Let us consider each of these aspects in turn.
The notion of an attacker or an adversary is central to the theory and practice of security
and privacy. An attacker is a malicious agent whose goal is to subvert the operation of
the system in some way. The exact subversion depends on characteristics of the system,
its goals and requirements, and the capabilities of the attacker. Typically, these charac-
teristics are grouped together into an entity called the threat model or attacker model.
For example, while designing an automobile with no wireless network connectivity, the
designers may assume that the only threats arise from people who have physical access
to the automobile and knowledge of its components, such as a well-trained mechanic.
Transforming an informal threat model (such as the preceding sentence) into a precise,
mathematical statement of an attacker’s objectives is a challenging task, but one that is
essential for principled model-based design of secure embedded systems.
The second defining characteristic of the field of security and privacy are the distinctive
properties it is concerned with. Broadly speaking, these properties can be categorized into
the following types: confidentiality, integrity, authenticity, and availability. Confidential-
ity is the state of being secret from the attacker. A good example of confidential data is
a password or PIN that one uses to access one’s bank account. Integrity is the state of
being unmodified by an attacker. An example of integrity is the property that an attacker,
who does not have authorized access to your bank account, cannot modify its contents.
Authenticity is the state of knowing with a level of assurance the identity of agents you
are communicating or interacting with. For instance, when you connect to a website that
purports to be your bank, you want to be sure that it indeed is your bank’s website and
not that of some malicious entity. The process of demonstrating authenticity is known as
authentication. Finally, availability is the property that a system provides a sufficient
quality of service to its users. For example, you might expect your bank’s website to be
available to you 99% of the time.
It is important to note that security and privacy are not absolute properties. Do not believe
anyone who claims that their system is “completely secure”! Security and privacy can
only be guaranteed for a specific threat model and a specific set of properties. As a
system designer, if security and privacy are important concerns for you, you must first

460 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

define your threat model and formalize your properties. Otherwise, any solution you
adopt is essentially meaningless.
In this chapter, we seek to give you a basic understanding of security and privacy with a
special focus on concepts relevant for cyber-physical system design. The field of security
and privacy is too broad for us to cover it in any comprehensive manner in a single chapter;
we refer the interested reader to some excellent textbooks on the topic, e.g., (Goodrich
and Tamassia, 2011; Smith and Marchesini, 2007). Instead, our goal is more modest: to
introduce you to the important basic concepts, and highlight the topics that are specific to,
or especially relevant for, embedded, cyber-physical systems.

17.1 Cryptographic Primitives

The field of cryptography is one of the cornerstones of security and privacy. The word
“cryptography” is derived from the Latin roots “crypt” meaning secret and “graphia”
meaning write, and thus literally means “the study of secret writing.”
We begin with a review of the basic cryptographic primitives for encryption and de-
cryption, secure hashing, and authentication. Issues that are particularly relevant for the
design and analysis of embedded and cyber-physical systems are highlighted. The reader
is warned that examples given in this chapter, particularly those listing code, are given at
a high level of abstraction, and omit details that are critical to developing secure crypto-
graphic implementations. See books such as (Menezes et al., 1996; Ferguson et al., 2010)
for a more in-depth treatment of the subject.

17.1.1 Encryption and Decryption

Encryption is the process of translating a message into an encoded form with the intent
that an adversary cannot recover the former from the latter. The original message is
typically referred to as the plaintext, and its encoded form as the ciphertext. Decryption
is the process of recovering the plaintext from the ciphertext.
The typical approach to encryption relies on the presence of a secret called the key. An
encryption algorithm uses the key and the plaintext in a prescribed manner to obtain the
ciphertext. The key is shared between the parties that intend to exchange a message se-
curely. Depending on the mode of sharing, there are two broad categories of cryptography.

Lee & Seshia, Introduction to Embedded Systems 461

17.1. CRYPTOGRAPHIC PRIMITIVES

In symmetric-key cryptography, the key is a single entity that is known to both sender
and receiver. In public-key cryptography, also termed asymmetric cryptography, the
key is split into two portions, a public part and a private part, where the public key is
known to everyone (including the adversary) and the private key is known only to the re-
ceiver. In the rest of this section, we present a brief introduction to these two approaches
to cryptography.
One of the fundamental tenets of cryptography, known as Kerckhoff’s principle, states
that a cryptographic system (algorithm) should be secure even if everything about the sys-
tem, except the key, is public knowledge. In practical terms, this means that even if the
adversary knows all details about the design and implementation of a cryptographic algo-
rithm, as long as he does not know the key, he should be unable to recover the plaintext
from the ciphertext.

Symmetric-Key Cryptography

Let Alice and Bob be two parties that seek to communicate with each other securely. In
symmetric-key cryptography, they accomplish this using a shared secret key K. Suppose
Alice wishes to encrypt and send Bob an n-bit plaintext message, M = m1 m2 m3 . . . mn ∈
{0, 1}n . We wish to have an encryption scheme that, given the shared key K, should en-
code M into ciphertext C with the following two properites. First, the intended recipient
Bob should be able to easily recover M from C. Second, any adversary who does not
know K should not, by observing C, be able to gain any more information about M .
We present intuition for the operation of symmetric-key cryptography using a simple,
idealized scheme known as the one-time pad. In this scheme, the two parties Alice and
Bob share an n-bit secret key K = k1 k2 k3 . . . kn ∈ {0, 1}n , where the n bits are chosen
independently at random. K is known as the one-time pad. Given K, encryption works
by taking the bit-wise XOR of M and K; i.e., C = M ⊕ K where ⊕ denotes XOR. Alice
then sends C over to Bob, who decrypts C by taking the bit-wise XOR of C with K;
using properties of the XOR operation, C ⊕ K = M .
Suppose an adversary Eve observes C. We claim that Eve has no more information about
M or K than she had without C. To see this, fix a plaintext message M . Then, every
unique ciphertext C ∈ {0, 1}n can be obtained from M with a corresponding unique
choice of key K — simply set K = C ⊕M where C is the desired ciphertext. Put another
way, a uniformly random bit-string K ∈ {0, 1}n generates a uniformly random ciphertext

462 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

C ∈ {0, 1}n . Thus, looking at this ciphertext, Eve can do no better than guessing at the
value of K uniformly at random.
Notice that Alice cannot use the key K more than once! Consider what happens if she
does so twice. Then Eve has access to two ciphertexts C1 = M1 ⊕ K and C2 = M2 ⊕ K.
If Eve computes C1 ⊕ C2 , using properties of XOR, she learns M1 ⊕ M2 . Thus, Eve
receives partial information about the messages. In particular, if Eve happens to learn
one of the messages, she learns the other one, and can also recover the key K. Thus, this
scheme is not secure if the same key is used for multiple communications, hence the name
“one-time pad.” Fortunately, other, stronger symmetric key cryptography schemes exist.
Most common symmetric key encryption methods use a building block termed a block
cipher. A block cipher is an encryption algorithm based on using a k-bit key K to
convert an n-bit plaintext message M into an n-bit ciphertext C. It can be mathemati-
cally captured in terms of an encryption function E : {0, 1}k × {0, 1}n → {0, 1}n ; i.e.,
E(K, M ) = C. For a fixed key K, the function EK defined by EK (M ) = E(K, M )
must be a permutation from {0, 1}n to {0, 1}n . Decryption is the inverse function of
encryption; note that the inverse exists for each K as EK is invertible. We denote the
−1
decryption function corresponding to EK by DK = EK . Note that for simplicity this
model of encryption abstracts it to be (only) a function of the message and the key; in
practice, care must be taken to use a suitable block cipher mode that, for example, does
not always encrypt the same plaintext to the same ciphertext.
One of the classic block ciphers is the data encryption standard (DES). Introduced in
the mid-1970s, DES was the first block cipher based on modern cryptographic techniques,
considered to be “commercial-grade,” with an open specification. While the details of
DES are beyond the scope of this chapter, we note that versions of DES are still used
in certain embedded devices. For instance, a version of DES, known as 3DES, which
involves applying the DES algorithm to a block three times, is used in certain “chip and
PIN” payment cards around in the world. The basic version of the DES involves use
of a 56-bit key and operates on 64-bit message blocks. While DES initially provided
an acceptable level of security, by the mid-1990s, it was getting easier to break it using
“brute-force” methods. Therefore, in 2001, the U.S. National Institute of Standards and
Technology (NIST) established a new cryptographic standard known as the advanced
encryption standard or AES. This standard is based on a cryptographic scheme called
Rijndael proposed by Joan Daemen and Vincent Rijmen, two researchers from Belgium.
AES uses a message block length of 128 bits and three different key lengths of 128, 192,
and 256 bits. Since its adoption, AES has proved to be a strong cryptographic algorithm
amenable to efficient implementation both in hardware and in software. It is estimated

Lee & Seshia, Introduction to Embedded Systems 463

17.1. CRYPTOGRAPHIC PRIMITIVES

that the current fastest supercomputers could not successfully mount a brute-force attack
on AES within the estimated lifetime of the solar system!

Public-Key Cryptography

In order to use symmetric-key cryptography, Alice and Bob need to have already set up
a shared key in advance. This is not always easy to arrange. Public-key cryptography is
designed to address this limitation.
In a public-key cryptosystem, each principal (Alice, Bob, etc.) has two keys: a public key,
known to everyone, and a private key, known only to that principal. When Alice wants
to send Bob a secret message, she obtains his public key KB and encrypts her message
with it. When Bob receives the message, he decrypts it with his private key kB . In
other words, the encryption function based on KB must be invertible using the decryption
function based on kB , and moreover, must not be invertible without kB .
Let us consider the last point. Encryption using a public key must effectively be a one-
way function: a publicly-known function F such that it is easy to compute F (M ) but
(virtually) impossible to invert without knowledge of a suitable secret (the private key).
Remarkably, there is more than one public-key cryptographic scheme available today,
each based on a clever combination of mathematics, algorithm design, and implementa-
tion tricks. We focus our attention here on one such scheme proposed in 1978 (Rivest
et al.), known as RSA for the initials of its creators: Rivest, Shamir and Adleman. For
brevity, we mostly limit our discussion to the basic mathematical concepts behind RSA.
Consider the setting where Bob wishes to create his public-private key pair so that others
can send him secret messages. The RSA scheme involves three main steps, as detailed
below:

1. Key Generation: Select two large prime numbers p and q, and compute their prod-
uct n = pq. Then compute ϕ(n) where ϕ denotes Euler’s totient function. This
function maps an integer n to the number of positive integers less than or equal
to n that are relatively prime to n. For the special case of the product of primes,
ϕ(n) = (p − 1)(q − 1). Select a random integer e such that 1 < e < ϕ(n) such that
the greatest common divisor of e and ϕ(n), denoted GCD(e, ϕ(n)) equals 1. Then
compute d, 1 < d < ϕ(n), such that ed ≡ 1 (mod ϕ(n)). The key generation
process is now complete. Bob’s public key KB is the pair (n, e). The private key is
kB = d.

464 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

2. Encryption: When Alice wishes to send a message to Bob, she first obtains his
public key KB = (n, e). Given the message M to transmit, she computes the
ciphertext C as C = M e (mod n). C is then transmitted to Bob.

3. Decryption: Upon receipt of C, Bob computes C d (mod n). By properties of

Euler’s totient function and modular arithmetic, this quantity equals M , allowing
Bob to recover the plaintext message from Alice.

We make two observations on the above scheme. First, the operations in the various
steps of RSA make heavy use of non-linear arithmetic on large numbers, especially mod-
ular multiplication of large integers and modular exponentiation. These operations must
be implemented carefully, especially on embedded platforms, in order to operate effi-
ciently. For instance, modular exponentiation is typically implemented using a version of
the square-and-multiply technique outlined in Example 16.1 of Chapter 16. Second, the
effectiveness of the approach depends critically on infrastructure to store and maintain
public keys. Without such a public-key infrastructure, an attacker Eve can masquerade
as Bob, advertising her own public key as Bob’s, and thus fooling Alice into sending her
messages intended for Bob. While such a public-key infrastructure has now been estab-
lished for servers on the Web using so-called “certificate authorities,” it is more challeng-
ing to extend that approach for networked embedded systems for a variety of reasons: the
large scale of devices that may act as servers, the ad-hoc nature of networks, and the re-
source constraints on many embedded devices.1 For this reason, public-key cryptography
is not as widely used in embedded devices as is symmetric-key cryptography.
17.1.2 Digital Signatures and Secure Hash Functions

The cryptographic primitives for encryption and decryption help in providing confiden-
tiality of data. However, by themselves, they are not designed to provide integrity or au-
thenticity guarantees. Those properties require the use of related, but distinct, primitives:
digital signatures, secure hash functions, and message authentication codes (MACs). This
section provides a brief overview of these primitives.
1
Let’s Encrypt, an ongoing effort to develop a free, automated, and open certificate authority might miti-
gate some of these challenges; see https://letsencrypt.org/ for more details.

Lee & Seshia, Introduction to Embedded Systems 465

17.1. CRYPTOGRAPHIC PRIMITIVES

Secure Hash Functions

A secure hash function (also known as cryptographic hash function) is a deterministic

and keyless function H : {0, 1}n → {0, 1}k that maps n-bit messages to k-bit hash
values. Typically, n can be arbitrarily large (i.e., the message can be arbitrarily long) while
k is a relatively small fixed value. For example, SHA-256 is a secure hash function that

Implementation Matters for Cryptography

Embedded platforms typically have limited resources such as memory or energy, and
must obey physical constraints, for instance on real-time behavior. Cryptography can
be computationally quite demanding. Such computations cannot simply be offloaded
“to the cloud” as secret data must be secured at the end point before being sent out
on the network. Thus, cryptographic primitives must be implemented in a manner that
obeys the constraints imposed by embedded platforms.
Consider, for example, public-key cryptography. These primitives involve modu-
lar exponentiation and multiplications that can have large timing, memory, and energy
requirements. Consequently, researchers have developed efficient algorithms as well
as software and hardware implementations. A good example is Montgomery mul-
tiplication (Montgomery, 1985), a clever way of performing modular multiplication
by replacing the division (implicit in computing the modulus) with addition. Another
promising technology is elliptic curve cryptography which allows for a level of se-
curity comparable with the RSA approach with keys of smaller bit-width, reducing the
memory footprint of implementations; see, for example, Paar and Pelzl (2009) for de-
tails. Due to the costs of public-key cryptography, it is often used to exchange a shared
symmetric key that is then used for all subsequent communication.
Another important aspect of implementing cryptographic schemes is the design and
use of random number generation (RNG). A high-quality RNG requires as input a
source of randomness with high entropy. Many recommended high entropy sources
involve physical processes, such atmospheric noise or atomic decay, but these may not
be easy to use in embedded systems, especially in hardware implementations. Alter-
natively, one can use on-chip thermal noise and the timing of input events from the
physical world and network events. Polling the physical world for many such sources
of randomness may consume power, leading to implementation trade-offs; see Perrig
et al. (2002) for an example.

466 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

maps messages to a 256-bit hash, and is being adopted for authenticating some software
packages and for hashing passwords in some Linux distributions. For a message M , we
term H(M ) as the “hash of M.”
A secure hash function H has certain important properties that distinguishes it from more
traditional hash functions used for non-security purposes:

• Efficient to compute: Given a message M , it should be efficient to compute H(M ).

• Pre-image resistance: Given a hash (value) h, it should be computationally infeasible
to find a message M such that h = H(M ).
• Second pre-image resistance: Given a message M1 , it should be computationally infea-
sible to find another message M2 such that H(M1 ) = H(M2 ). This property prevents
attackers from taking a known message M1 and modifying it to match a desired hash
value (and hence find the corresponding message M2 ).
• Collision resistance: It should be computationally infeasible to find two different mes-
sages M1 and M2 where H(M1 ) = H(M2 ). This property, a stronger version of
second pre-image resistance, prevents an attacker from taking any starting message
and modifying it to match a given hash value.

A common use of secure hash functions is to verify the integrity of a message or a piece of
data. For example, before you install a software update on your computer you might want
to verify that the update you downloaded is a valid copy of the package you are updating
and not something modified by an attacker. Providing a secure hash of the software update
on a separate channel than the one on which the update file is distributed can provide such
assurance. After separately downloading this hash value, you can verify, by computing
the hash yourself on the software, that the provided hash indeed matches the one you
compute. With the growing trend for embedded systems to be networked and to receive
software patches over the network, the use of secure hash functions is expected to be a
central component of any solution that maintains system integrity.

Digital Signatures

A digital signature is a cryptographic mechanism, based on public-key cryptography, for

the author of a digital document (message) to authenticate himself/herself to a third party
and to provide assurance about the integrity of the document. The use of digital signatures
involves the following three stages:

Lee & Seshia, Introduction to Embedded Systems 467

17.1. CRYPTOGRAPHIC PRIMITIVES

1. Key generation: This step is identical to the key generation phase of public-key
cryptosystems, resulting in a public key-private key pair.

2. Signing: In this step, the author/sender digitally signs the document to be sent to
the receiving party.

3. Verification: The recipient of a signed document verifies, using the digital signature,
that the sender of the document is indeed who he/she purports to be.

We now illustrate how the basic scheme works for the RSA cryptosystem. Suppose
Bob wishes to digitally sign a message M before sending it to Alice. Recall from Sec-
tion 17.1.1 that, using RSA, Bob can generate his public key as KB = (n, e) and private
key kB = d. One simple authentication scheme is for Bob to use his key-pair in reverse:
to sign M , he simply encrypts it with his private key, computing S = M d (mod n), and
sends S to Alice along with M . When Alice receives this signed message, she uses KB
to recover M from the signature S and verifies it by comparing it with the received mes-
sage. If they match, the message has been authenticated; otherwise, Alice has detected
tampering either in the message or its signature.
The above scheme is simple, but flawed. In particular, given the signatures S1 and S2 for
two messages M1 and M2 , notice that an attacker can construct the signature for message
M1 · M2 by simply multiplying together S1 and S2 (mod n). In order to guard against
this attack, one can first compute a secure hash of M1 and M2 before computing the
signatures on the resultant hashes rather than on the messages.

Message Authentication Codes

A message authentication code (MAC) is a cryptographic mechanism, based on

symmetric-key cryptography, for providing integrity and authenticity to a document. It is
thus the symmetric-key analog of a digital signature. As in other symmetric-key schemes,
the use of a MAC requires first setting up a shared key between sender and receiver that
each of them can use to authenticate messages sent by the other. For this reason, MACs
are best suited to settings where such a shared key can be easily set up. For instance,
modern automobiles comprise multiple electronic control units (ECUs) communicating
with each other on an on-board network such as a controller-area network (CAN) bus.
In this case, if each ECU is pre-programmed with a common key, then each ECU can
authenticate messages sent from other ECUs on the CAN bus using MACs.

468 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

17.2 Protocol and Network Security

An attacker typically gains access to a system via its connection to a network or some
other medium used to connect it with other components. Additionally, it is increasingly
the case that a single embedded system comprises many distributed components con-
nected over a network. Thus, one must address fundamental questions about security
over a network and using various communication protocols, a field termed protocol se-
curity or network security. In this section, we review basic ideas related to two topics
of particular relevance for embedded systems: key exchange and cryptographic protocol
design.

17.2.1 Key Exchange

We have already seen how secret keys are critical components of both symmetric and
asymmetric cryptosystems. How are these keys established in the first place? In a sym-
metric cryptosystem, we need a mechanism for two communicating parties to agree on a
single shared key. In an asymmetric cryptosystem, we need infrastructure for establish-
ing and maintaining public keys so that any party on a network can look up the public
key of any other party it wishes to communicate with. In this section, we discuss a classic
method for key exchange and some alternative schemes customized to specific embedded
system design problems, with a focus on symmetric cryptography.

Diffie-Hellman Key Exchange

In 1976, Whitfield Diffie and Martin Hellman introduced what is widely considered the
first public-key cryptosystem (Diffie and Hellman, 1976). The crux of their proposal was
a clever scheme for two parties to agree on a shared secret key using a communication
medium observable by anyone. This scheme is commonly referred to as Diffie-Hellman
key exchange.
Suppose there are two parties Alice and Bob that wish to agree on a secret key. Everything
Alice sends to Bob, and vice-versa, can be viewed by an attacker Eve. Alice and Bob wish
to agree on a key while ensuring that it is computationally infeasible for Eve to compute
that key by observing their communication. Here is how Alice and Bob can use Diffie-
Hellman key exchange to achieve this objective.

Lee & Seshia, Introduction to Embedded Systems 469

17.2. PROTOCOL AND NETWORK SECURITY

To begin with, Alice and Bob need to agree on two parameters. In doing so, they can use
various methods including a hard-coded scheme (e.g., a parameter hard-coded into the
same program they use) or one of them can announce the parameters to the other in some
deterministic fashion (e.g., based on a fixed ordering between their network addresses).
The first parameter is a very large prime number p. The second is a number z such that
1 < z < p − 1. Note that an attacker can observe z and p.
After these parameters p and z are agreed upon, Alice randomly selects a number a from
the set {0, 1, . . . , p − 2} and keeps it secret. Similarly, Bob randomly selects a number
b ∈ {0, 1, . . . , p − 2} and keeps it secret. Alice computes the quantity A = z a (mod p)
and sends it to Bob. Likewise, Bob computes B = z b (mod p) and sends it to Alice. In
addition to z and p, the attacker Eve can observe A and B, but not a and b.
On receiving B, Alice uses her secret number a to compute B a (mod p). Bob performs
the analogous step, computing Ab (mod p). Now, observe that

Ab (mod p) = z ab (mod p) = B a (mod p)

Thus, amazingly, Alice and Bob have agreed on a shared key K = z ab (mod p) simply
by communicating on a public channel. Note that they have revealed neither of the secret
numbers a or b to the attacker Eve. Without knowledge of a or b, Eve cannot reliably
compute K. Moreover, it is computationally very difficult for Eve to compute a or b sim-
ply by knowing p, z, A or B, since the underlying problem is one known as the discrete
logarithm problem, for which no efficient (polynomial-time) algorithm is known. Put
another way, the function f (x) = z x (mod p) is a one-way function.
Diffie-Hellman is simple, elegant, and effective: unfortunately, it is typically not practical
for resource-constrained embedded systems. Computing it involves modular exponen-
tiation for large primes (typical key sizes range to 2048-bits), and thus impractical for
energy-constrained platforms that must obey real-time constraints. We therefore discuss
next a few alternative schemes.

Timed Release of Keys

Many networked embedded systems use a broadcast medium for communication — one
where senders send data over a public channel where all receivers, intended and unin-
tended, can read that data. Examples include on-board automotive networks using the
CAN bus and wireless sensor networks. A broadcast medium has many advantages: it
is simple, requires little infrastructure, and a sender can quickly reach a large number of

470 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

receivers. However, it also has certain disadvantages, notably that malicious parties can
eavesdrop and inject malicious packets with ease. Reliability of the broadcast medium
can also be concern.
How can one achieve secure key exchange in such a broadcast medium, under constraints
on timing and energy consumption? This question was studied in the early 2000s, when
the first work was done on deploying wireless sensor networks (e.g., see Perrig et al.
(2004); Perrig and Tygar (2012)). One of the novel ideas is to leverage timing properties
of these networks, an idea whose roots go back to a paper by Anderson et al. (1998).
The first property is that of clock synchronization, where different nodes on the network
have clocks such that the difference between the values of any two clocks is bounded by
a small constant. Many sensor nodes can have synchronized clocks via GPS or protocols
such as the precision time protocol (PTP) (Eidson, 2006).
The second property is that of scheduled transmission. Each node in the network transmits
packets at pre-determined times, following a schedule.
The combination of the above two properties permits the use of a secure broadcast pro-
tocol called µTESLA (Perrig et al., 2002). This protocol is designed for broadcast net-
works comprising two types of nodes, base stations and sensor nodes. A key property
of µTESLA is secure authentication — a node receiving a message should be able to
determine who the authentic sender is, discarding spoofed messages. It performs this by
using a message authentication code (MAC) in each message, which is computed using
a secret key. This secret key is broadcast some time after the original message was sent,
allowing the receiver to compute the MAC for itself, and determine the authenticity of
the received message. Since each message is timestamped, upon receiving a message the
receiver verifies that the key used to compute the MAC has not yet been disclosed based
on this timestamp, its local clock, the maximum clock skew, and the time schedule at
which keys are disclosed. If the check fails, the message is discarded; otherwise, when
the key is received, the authenticity of the message is checked by computing the MAC
and checking against the received MAC. In this way, the timed release of keys is used to
share keys between a broadcast sender and its receivers, for the purpose of authenticating
messages.
A similar approach has been adopted for CAN-based automotive networks. Lin et al.
(2013) have shown how to extend the µTESLA approach for the CAN bus where the
nodes do not necessarily share a common global notion of time. Timed delayed release

Lee & Seshia, Introduction to Embedded Systems 471

17.2. PROTOCOL AND NETWORK SECURITY

of keys has also been implemented for Time Triggered Ethernet (TTE) (Wasicek et al.,
2011).

Other Schemes

In certain application domains, customized schemes have been developed for key ex-
change using special characteristics of those domains. For instance, Halperin et al. (2008)
discuss a key exchange scheme for implantable medical devices (IMDs) such as pace-
makers and defibrillators. They propose a “zero-power” security mechanism on the im-
planted device based on radio-frequency (RF) power harvesting. The novel key exchange
scheme involves a “programmer” device initiating communication with the IMD (and
supplying an RF signal to power it). The IMD generates a random value that is commu-
nicated as a weak modulated sound wave that is perceptible by the patient. The security

Reverse Engineering Systems to Improve Security

Several embedded systems were designed at a time when security was a secondary
design concern, if one at all. In recent years, researchers have shown how this lack of
attention to security can lead to compromised systems in various domains. The chief
approach taken is to reverse engineer protocols that provide access to systems and the
working of their components.
We present here three representative examples of vulnerabilities demonstrated in
real embedded systems. Halperin et al. (2008) show how implantable medical devices
(IMDs) can be read and reprogrammed wirelessly. Koscher et al. (2010) demonstrate
for automobiles how the on-board diagnostics bus (OBD-II) protocol can be subverted
to adversarially control a wide range of functions, including disabling the brakes and
stopping the engine. Ghena et al. (2014) study traffic light intersections and show
how their functioning can be partially controlled wirelessly to perform, for example, a
denial-of-service attack causing traffic congestion.
Such investigations based on reverse engineering “legacy” embedded systems to un-
derstand their functioning and uncover potential security flaws form an important part
of the process of securing our cyber-physical infrastructure.

472 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

of this scheme relies on a threat model based on physical security around the patient’s
immediate vicinity, one that is plausible for this particular application.
17.2.2 Cryptographic Protocol Design

Some of the most-publicized vulnerabilities in networked embedded systems, at the time

of writing, arise from the fact that the communication protocols were designed with little
or no security in mind (see the box on page 472). However, even protocols designed for
security using cryptographic primitives can have vulnerabilities. Poor protocol design can
compromise confidentiality, integrity, and authenticity properties even if one assumes per-
fect cryptography and the presence of key exchange and key management infrastructure.
We explain this point with an example.

Example 17.1: A replay attack on a protocol is one where an attacker is able to

violate a security property by replaying certain messages in the protocol, possibly
with modifications to accompanying data.
We describe here a replay attack on a fictitious wireless sensor network protocol.
This network comprises a base station S and several energy-constrained sensor
nodes N1 , N2 , . . . , Nk communicating via broadcast. Each node spends most of
its time in a sleep mode, to conserve energy. When S wants to communicate with
a particular node Ni to take a sensor reading, it sends it a message M encrypted
with a suitable shared key Ki pre-arranged between S and Ni . Ni then responds
with an encrypted sensor reading R. In other words, the protocol has a message
exchange as follows:

S → Ni : E(Ki , M )
Ni → S : E(Ki , R)

This protocol, on the face of it, seems secure. However, it has a flaw that can
hinder operation of the network. Since the nodes use broadcast communication,
an attacker can easily record the message E(Ki , M ). The attacker can then replay
this message multiple times at a low power so that it is detected by Ni , but not by
S. Ni will keep responding with encrypted sensor readings, possibly causing it
to run down its battery much faster than anticipated, and disabling its operation.
Notice that there was nothing wrong with the individual cryptographic steps used
in this protocol. The problem was with the temporal behavior of the system —

Lee & Seshia, Introduction to Embedded Systems 473

17.3. SOFTWARE SECURITY

that Ni had no way of checking if a message is “fresh.” A simple countermeasure

to this attack is to attach a fresh random value, called a nonce, or a timestamp
with each message.
This attack is also an example of a so-called denial-of-service attack, abbre-
viated DoS attack, indicating that the impact of the attack is a loss of service
provided by the sensor node.

Fortunately, techniques and tools exist to formally model cryptographic protocols and ver-
ify their correctness with respect to specific properties and threat models before deploying
them. More widespread use of these techniques is needed to improve protocol security.

17.3 Software Security

The field of software security is concerned with how errors in the software implementa-
tion can impact desired security and privacy properties of the system. Bugs in software
can and have been used to steal data, crash a system, and worse, allow an attacker to obtain
an arbitrary level of control over a system. Vulnerabilities in software implementations
are one of the largest categories of security problems in practice. These vulnerabilities
can be especially dangerous for embedded systems. Much of embedded software is pro-
grammed in low-level languages such as C, where the programmer can write arbitrary
code with few language-level checks. Moreover, the software often runs “bare metal”
without an underlying operating system or other software layer that can monitor and trap
illegal accesses or operations. Finally, we note that in embedded systems, even “crashing”
the system can have severe consequences, since it can completely impair the interaction
of the system with the physical world. Consider, for example, a medical device such as a
pacemaker, where the consequences of a crash may be that the device stops functioning
(e.g. pacing), leading to potentially life-threatening consequences for the patient.
In this section, we give the reader a very brief introduction to software security problems
using a few illustrative examples. The reader is referred to relevant books on security
(e.g., Smith and Marchesini (2007)) for further details.
Our examples illustrate a vulnerability known as a buffer overflow or buffer overrun.
This class of errors is particularly common in low-level languages such as C. It arises from

474 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

the absence of automatic bounds-checking for accessing arrays or pointers in C programs.

More precisely, a buffer overflow is a error arising from the absence of a bounds check
resulting in the program writing past the end of an array or memory region. Attackers can
use this out-of-bounds write to corrupt trusted locations in a program such as the value
of a secret variable or the return address of a function. (Tip: material in Chapter 9 on
Memory Architectures might be worth reviewing.) Let us begin with a simple example.

Example 17.2: The sensors in certain embedded systems use communication

protocols where data from various on-board sensors is read as a stream of bytes
from a designated port or network socket. The code example below illustrates one
such scenario. Here, the programmer expects to read at most 16 bytes of sensor
data, storing them into the array sensor data.
1 char sensor_data[16];
2 int secret_key;
3
4 void read_sensor_data() {
5 int i = 0;
6
7 // more_data returns 1 if there is more data,
8 // and 0 otherwise
9 while(more_data()) {
10 sensor_data[i] = get_next_byte();
11 i++;
12 }
13
14 return;
15 }

The problem with this code is that it implicitly trusts the sensor stream to be no
more than 16 bytes long. Suppose an attacker has control of that stream, either
through physical access to the sensors or over the network. Then an attacker can
provide more than 16 bytes and cause the program to write past the end of the
array sensor data. Notice further how the variable secret key is defined
right after sensor data, and assume that the compiler allocates them adja-
cently. In this case, an attacker can exploit the buffer oveflow vulnerability to
provide a stream of length 20 bytes and overwrite secret key with a key of
his choosing. This exploit can then be used to compromise the system in other
ways.

Lee & Seshia, Introduction to Embedded Systems 475

17.3. SOFTWARE SECURITY

The example above involves an out-of-bounds write in an array stored in global memory.
Consider next the case when the array is stored on the stack. In this case, a buffer overrun
vulnerability can be exploited to overwrite the return address of the function, and cause it
to execute some code of the attacker’s choosing. This can lead to the attacker gaining an
arbitrary level of control over the embedded system.

Example 17.3: Consider below a variant on the code in Example 17.2 where
the sensor data array is stored on the stack. As before, the function reads
a stream of bytes and stores them into sensor data. However, in this case,
the read sensor data is then processed within this function and used to set certain
globally-stored flags (which can then be used to take control decisions).
1 int sensor_flags[4];
2
3 void process_sensor_data() {
4 int i = 0;
5 char sensor_data[16];
6
7 // more_data returns 1 if there is more data,
8 // and 0 otherwise
9 while(more_data()) {
10 sensor_data[i] = get_next_byte();
11 i++;
12 }
13
14 // some code here that sets sensor_flags
15 // based on the values in sensor_data
16
17 return;
18 }

Recall from Chapter 9 how the stack frame of a function is laid out. It is possi-
ble for the return address of function process sensor data to be stored in
memory right after the end of the array sensor data. Thus, an attacker can
exploit the buffer overflow vulnerability to overwrite the return address and cause
execution to jump to a location of his choice. This version of the buffer overflow
exploit is sometimes (and rather aptly) termed as stack smashing.
Moreover, the attacker could write a longer sequence of bytes to memory and
include arbitrary code in that sequence. The overwritten return address could be

476 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

tailored to be within this overwritten memory region, thus causing the attacker
to control the code that gets executed! This attack is often referred to as a code
injection attack.

How do we avoid buffer overflow attacks? One easy way is to explicitly check that we
never write past the end of the buffer, by keeping track of its length. Another approach
is to use higher-level languages that enforce memory safety — preventing the program
from reading or writing to locations in memory that it does not have privileges for or that
the programmer did not intend it to. Exercise 1 gives you some practice with writing code
so as to avoid a buffer overflow.

17.4 Information Flow

Many security properties specify restrictions on the flow of information between princi-
pals. Confidentiality properties restrict the flow of secret data to channels that are readable
by an attacker. For example, your bank balance should be viewable only by you and au-
thorized bank personnel and not by an attacker. Similarly, integrity properties restrict the
flow of untrusted values, controlled by an attacker, to trusted channels or locations. Your
bank balance should be writable only by trusted deposit or withdrawal operations and not
arbitrarily by a malicious party. Thus, secure information flow, the systematic study of
how the flow of information in a system affects its security and privacy, is a central topic
in the literature.
Given a component of an embedded system it is important to understand how informa-
tion flows from secret locations to attacker-readable “public” locations, or from attacker-
controlled untrusted channels to trusted locations. We need techniques to detect illegal
information flows and to quantify their impact on the overall security of the system. Addi-
tionally, given security and privacy policies, we need techniques to enforce those policies
on a system by suitably restricting the flow of information. Our goal, in this section, is to
equip the reader with the basic principles of secure information flow so as to be able to
develop such techniques.

Lee & Seshia, Introduction to Embedded Systems 477

17.4. INFORMATION FLOW

17.4.1 Examples

In order to motivate the secure information flow problem, we present a series of examples.
Although these examples focus on confidentiality, the same approaches and concerns ap-
ply for integrity properties as well.

Example 17.4: Medical devices are increasingly software-controlled, personal-

ized, and networked. An example of such a device is a blood glucose meter, used
by doctors and patients to monitor a patient’s blood glucose level. Consider a hy-
pothetical glucose meter that can take a reading of a patient’s glucose level, show
it on the device’s display, and also transmit it over the network to the patient’s
hospital. Here is a highly-abstracted version of the software that might perform
these tasks.
1 int patient_id; // initialized to the
2 // patient’s unique identifier
3 void take_reading() {
4 float reading = read_from_sensor();
5
6 display(reading);
7
8 send(network_socket, hospital_server,
9 reading, patient_id);
10
11 return;
12 }
The function take reading records a single blood glucose reading (e.g., in
mg/dL) and stores it in a floating-point variable reading. It then writes this
value, suitably formatted, to the device’s display. Finally, it transmits the value
along with the patient’s ID without any encryption over the network to the hospital
server for analysis by the patient’s doctor.
Suppose that the patient wishes to have his glucose level kept private, in the sense
that its value is known only to him and his doctor, but no one else. Does this
program achieve that objective? It is easy to see that it does not, as the value
of reading is transmitted “in the clear” over the network. We can formal-
ize this violation of privacy as an illegal information flow from reading to
network socket, where the former is a secret location whereas the latter is a
public channel visible to an attacker.

478 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

With the knowledge of cryptographic primitives presented earlier in this chapter, we know
that we can do better. In particular, let us assume the presence of a shared key between the
patient’s device and the hospital server that permits the use of symmetric-key encryption.
Consider the following new version of the above example.

Example 17.5: In this version of the program, we employ symmetric-key cryp-

tography, denoted by AES, to protect the reading. The encryption process is ab-
stractly represented by the function enc AES, and send enc differs from send
only in the type of its third argument.
1 int patient_id; // initialized to the
2 // patient’s unique identifier
3 long cipher_text;
4
5 struct secret_key_s {
6 long key_part1; long key_part2;
7 }; // struct type storing 128-bit AES key
8
9 struct secret_key_s secret_key; // shared key
10
11 void take_reading() {
12 float reading = read_from_sensor();
13
14 display(reading);
15
16 enc_AES(&secret_key, reading, &cipher_text);
17
18 send_enc(network_socket, hospital_server,
19 cipher_text, patient_id);
20
21 return;
22 }

In this case, there is still a flow of information from reading to

network socket. In fact, there is also a flow from secret key to
network socket. However, both these flows passed through an encryption
function denoted by enc AES. In the security literature, such a function is termed
a declassifier since it encodes the secret data in such a way that it becomes accept-
able to transmit the encoded, “declassified” result to an attacker-readable channel.
In other words, the declassifier serves as a “dam” blocking the flow of secret infor-
mation and releasing only information that, by the properties of the cryptographic

Lee & Seshia, Introduction to Embedded Systems 479

17.4. INFORMATION FLOW

primitives, provides attackers with no more information than they had before the
release.

While the above fix to the code blocks the flow of information about the reading of the
patient’s blood glucose, note that it does not completely protect the program. In particular,
notice that the patient’s ID is still being sent in the clear over the network! Thus, even
though the attacker cannot tell, without the secret key, what the patient’s reading is, he/she
knows who transmitted a reading to the hospital (and possibly also at what time). Some
private data is still being leaked. One solution to this leak is fairly obvious – we can
encrypt both variables reading and patient id using the secret key before sending
them over the network.
So far we have assumed an implicit threat model where the attacker can only read in-
formation sent over the network. However, for many embedded systems, attackers may
also have physical access to the device. For instance, consider what happens if the patient
loses his device and an unauthorized person (attacker) gains access to it. If the patient’s
readings are stored on the device, the attacker might be able to read the data stored on it
if such an illegal information flow exists. One approach to guard against this attack is to
have the patient create a password, much like one creates a password for other personal
devices, and have the device prompt one for the password when turned on. This idea is
discussed in the example below.

Example 17.6: Suppose that a log of the past 100 readings is stored
on the device. The code below sketches an implementation of a function
show readings that prompts the user for an integer password, and displays
the stored readings only if the current password stored in patient pwd is en-
tered, otherwise displaying an error message that has no information about the
stored readings.
1 int patient_id; // initialized to the
2 // patient’s unique identifier
3 int patient_pwd; // stored patient password
4
5 float stored_readings[100];
6
7 void show_readings() {

480 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

8 int input_pwd = read_input(); // prompt user for

9 // password and read it
10 if (input_pwd == patient_pwd) // check password
11 display(&stored_readings);
12 else
13 display_error_mesg();
14
15 return;
16 }

Assuming the attacker does not know the value of patient pwd, we can see
that the above code does not leak any of the 100 stored readings. However, it
does leak one bit of information: whether the input password provided by the
attacker equals the correct password or not. In practice, such a leak is deemed
acceptable since, for a strong choice of patient password, it would take even the
most determined attacker an exponential number of attempts to log in success-
fully, and this can be thwarted by disallowing more than a small, fixed number of
attempts to provide the correct password.

The above example illustrates the concept of quantitative information flow (QIF). QIF
is typically defined using a function measuring the amount of information flowing from
a secret location to a public location. For instance, one might be interested in computing
the number of bits leaked, as illustrated by the example above. If this quantity is deemed
small enough, the information leak is tolerated, otherwise, the program must be rewritten.
However, the code in Example 17.6 has a potential flaw. Once again, this flaw stems
from a corresponding threat model. In particular, consider the case where an attacker not
only has physical possession of the device, but also has the knowledge and resources to
perform invasive attacks by opening up the device, and reading out the contents of main
memory as it executes. In this case, the attacker can read the value of patient pwd
simply by booting up the device and reading out the contents of memory as the system is
initialized.
How can we protect against such invasive attacks? One approach involves the use of se-
cure hardware or firmware coupled with secure hash functions. Suppose the hardware
provides for secure storage where a secure hash of the user password can be written out,
and any tampering detected. Then, only the secure hash need be stored in main memory,
not the actual password. By the properties of a secure hash function, it would be compu-

Lee & Seshia, Introduction to Embedded Systems 481

17.4. INFORMATION FLOW

tationally infeasible for an attacker to reverse engineer the password simply by knowing
the hash.
A similar flaw exists in Example 17.5, where the secret key is stored in memory in the
clear. However, in this case, simply taking a secure hash of the key is insufficient as the
actual key is required to perform encryption and decryption to facilitate secure commu-
nication with the server. How do we secure this function? In general, this requires an
additional component such as a secure key manager, e.g., implemented in hardware or by
a trusted operating system, one that uses a master key to encrypt or decrypt the secret key
for the application.
Finally, although our examples illustrate the flow of information through values of vari-
ables in software, information can also be leaked through other channels. The term side
channel is used to refer to a channel that involves a non-traditional way of communicat-
ing information, typically using a physical quantity such as time, power consumption, or
the amplitude and frequency of an audio signal, or a physical modification to the system,
such as a fault, that induces a traditional information leak. We cover some basic concepts
on side-channel attacks in Section 17.5.2.

17.4.2 Theory

So far we have spoken of confidentiality and integrity properties only informally. How
can we state these properties precisely, similar to the notation introduced in Chapter 13?
It turns out that specifying security and privacy properties formally can be quite tricky.
Various formalisms have been proposed in the literature over the years, and there is no
consensus on a common definition of notions such as confidentiality or integrity. How-
ever, some foundational concepts and principles have emerged. We introduce these basic
concepts in this section.
The first key concept is that of non-interference. The term non-interference is used
to refer to any of a family of (security) properties that specify how actions taken by one
or more principals can or cannot affect (“interfere with”) actions taken by others. For
instance, for integrity properties, we require that actions of an attacker cannot affect the
values of certain trusted data or computations. Similarly, for confidentiality properties, we
require that the actions taken by an attacker cannot depend on secret values (thus implying
that the attacker has no information about those secrets).

482 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

There are several variants of non-interference that are useful for expressing different kinds
of security or privacy properties. In defining these, it is customary to use the terms high
and low to denote two security levels. For confidentiality, the high level denotes secret
data/channels and the low level denotes public data/channels. For integrity, the high level
denotes trusted data/channels while the low level denotes untrusted data/channels. Non-
interference is typically defined over traces of a system, where each input, output, and
state element is classified as being either low or high.
The first variant we introduce is observational determinism (McLean, 1992; Roscoe,
1995) which is defined as follows: if two traces of a system are initialized to be in states
in which the low elements are identical, and they receive the same low inputs, then that
implies that the low elements of all states and outputs in that trace must be identical. Put
another way, the low parts of a system’s trace are deterministic functions of the low initial
state and the low inputs, and nothing else. This, in turn, implies that an attacker who
only controls or observes the low parts of a system’s trace cannot infer anything about the
high parts.
Another variant is generalized non-interference (McLean, 1996) which requires a sys-
tem to exhibit a set of traces with a special property: for any two traces τ1 and τ2 , there
must exist a newly-constructed trace τ3 such that, at each time step in τ3 , the high inputs
are the same as in τ1 and the low inputs, states, and outputs are the same as in τ2 . Intu-
itively, by observing the low states and outputs, an attacker cannot tell if she is seeing the
high inputs as in τ1 or as they occur in τ2 .
The different variants of non-interference, however, share something in common. Math-
ematically, they are all hyperproperties (Clarkson and Schneider, 2010). Formally, a
hyperproperty is a set of sets of traces. Contrast this definition with the definition of
a property as a set of traces, as introduced in Chapter 13. The latter is more accurately
called a trace property, as its truth value can be evaluated on a single, standalone trace of
a system. The truth value of a hyperproperty, in contrast, typically2 cannot be determined
by observing a single trace. One needs to observe multiple traces, and compute a relation
between them, in order to determine if they together satisfy or violate a hyperproperty.

Example 17.7: Consider the two state machines in Figure 17.1. In both cases,
the state machine has one secret input s and one public output z. Additionally,

2
Clearly, every (trace) property has an equivalent hyperproperty, which is why we use the adverb “typi-
cally.”

Lee & Seshia, Introduction to Embedded Systems 483

17.4. INFORMATION FLOW

inputs: s, x : {0,1} input: s : {0,1}

output: z : {0,1} output: z : {0,1}

x=1 / 0 s=1/0
s=0/1
s=0/1

x=0 / 1

s=1/0

(a) M1 (b) M2

Figure 17.1: An example of a state machine satisfying observational determinism

(a) and one that does not (b). Input s is a secret (high) input, and output z is a
public (low) output.

M1 has a public input x. An attacker can directly read the value of x and z but
not s.
State machine M1 satisfies observational determinism (OD). For any input se-
quence, M1 produces a binary output sequence that depends solely on the values
of the public input x and not on s.
However, M2 does not satisfy OD. For example, consider the input sequence
1010ω . Then, the corresponding output sequence of M2 will be 0101ω . If the in-
put sequence is switched to 0101ω , then the output will correspondingly change to
1010ω . The adversary can gain information about the input s simply by observing
the output z.

17.4.3 Analysis and Enforcement

Several techniques have been developed to analyze and track the flow of information in
software systems, and, in some cases, to enforce information flow policies either at design
time or run time. We mention some of these methods below, with the caveat that this is a
rapidly evolving area and our selection is meant to be representative, not exhaustive.

484 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

Taint analysis. In taint analysis, the flow of information is tracked using labels (“taint”)
attached to data items and by monitoring memory operations. When an illegal informa-
tion flow is detected, a warning is generated. Taint analysis has been mainly developed for
software systems. It can be performed statically, when software is compiled, or dynam-
ically, at run time. For instance, for the code in Example 17.4, taint analysis can detect
the flow of secret data from reading to network socket. At run time, this can be
detected before the write to the network socket, and used to raise a run-time exception or
other preventive action. Static taint analysis is a simple concept, and easy to apply, but
can generate false alarms. Dynamic taint analysis is just as easy and more precise, but im-
poses a run-time overhead. System designers must evaluate for themselves the suitability
of either mechanism for their contexts.
Formal verification of information flow. Techniques for formal verification, such as the
model checking methods covered in Chapter 15, can also be adapted to verify secure infor-
mation flow. These methods usually operate after the original analysis problem has been
reduced to one of checking a safety property on a suitably constructed model (Terauchi
and Aiken, 2005). Compared to taint analysis, such methods are much more precise, but
they also come at a higher computational cost. As these methods are still rapidly evolving,
detailed coverage of these methods is beyond the scope of this chapter at the present time.
Run-time enforcement of policies. The notion of taint allows one to specify simple
information flow policies, such as disallowing the flow of secret data to any public location
at all times. However, some security and privacy policies are more complex. Consider,
for example, a policy that a person’s location is public some of the time (e.g., while they
are at work or in a public space such as an airport), but is kept secret at selected other
times (e.g., when they visit their doctor). Such a policy involves a time-varying secret tag
on the variable storing the person’s location. The problem of specifying, checking, and
enforcing such expressive policies is an active area of research.

17.5 Advanced Topics

Certain problems in security and privacy gain special significance in the context of cyber-
physical systems. In this section, we review two of these problems and highlight some of
the key issues.

Lee & Seshia, Introduction to Embedded Systems 485

17.5. ADVANCED TOPICS

17.5.1 Sensor and Actuator Security

Sensors and actuators form the interface between the cyber and physical worlds. In many
cyber-physical systems, these components are easily observed or controlled by an at-
tacker. Detecting attacks on these components and securing them is therefore an impor-
tant problem. Central to both efforts is to develop realistic threat models and mechanisms
to address those threats. We review two representative recent efforts in the area of sensor
security.
Recent work has focused on attacks on analog sensors, i.e., developing threat models
for these attacks as well as countermeasures. The main mode of attack is to employ
electromagnetic interference (EMI) to modify the sensed signal. Two recent projects
have studied EMI attacks in different applications. Foo Kune et al. (2013) investigate
EMI attacks at varying power and distances on implantable medical devices and consumer
electronics. Shoukry et al. (2013) study the possibility of EMI attacks that spoof sensor
values for certain types of automotive sensors. We present here some basic principles
from both projects.

Threat Models

In the context of sensor security, EMI can be classified along multiple dimensions. First,
such interference can be invasive, involving modification to the sensor components, or
non-invasive, involving observation or remote injection of spurious values. Second, it
can be unintentional (e.g., arising from lightning strikes or transformers) or intentional
(injected by an attacker). Third, it can be high-power, potentially injecting faults into or
disabling the sensor, or low-power, which simply injects false values or modifies sensor
readings. These dimensions can be used to define informal threat models.
Foo Kune et al. (2013) describe a threat model for intentional, low-power, non-invasive
attacks. This combination of characteristics is amongst the hardest to defend against,
since the low-power and non-intrusive nature of the attacks makes it potentially hard to
detect. The researchers design two kinds of EMI attacks. Baseband attacks inject signals
within the same frequency band in which the generated sensor readings lie. They can be
effective on sensors that filter signals outside the operating frequency band. Amplitude-
modulated attacks start with a carrier signal in the same frequency band of the sensor and
modulate it with an attack signal. They can match the resonant frequency of a sensor,
thus amplifying the impact of even a low-power attack signal. They demonstrate how

486 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

these attacks can be performed on implantable cardiac devices, injecting forged signals
in leads, inhibiting pacing, causing defibrillation, etc. from 1 to 2 meters away from the
device.
The threat model considered by Shoukry et al. (2013) is for intentional, non-invasive
attacks, with a focus on anti-lock braking systems (ABS) in automobiles. The magnetic
wheel speed sensors are attacked by placing a malicious actuator in close proximity of
the sensor (mountable from outside the vehicle) that modifies the magnetic field measured
by the ABS sensor. One form of the attack, in which the actuator disrupts the magnetic
field but is not precisely controllable by the attacker, can be “merely” disruptive. Its
impact is similar to unintentional, high-power EMI. The trickier form of the attack is
a spoofing attack, where the ABS system is deceived into measuring an incorrect but
precise wheel speed for one or more of the wheels. This is achieved by implementing
an active magnetic shield around the actuator. The reader is referred to the paper for
additional details. The authors show how their attack can be mounted on real automotive
sensors, and demonstrate, in simulation, how the ABS system can be tricked into making
an incorrect braking decision in icy road conditions, causing the vehicle to slip off-road.

Countermeasures

Both of the projects mentioned above also discuss potential countermeasures to the at-
tacks.
Foo Kune et al. (2013) consider a range of defenses, both hardware-based and software-
based. Hardware or circuit-level approaches include shielding the sensor, filtering the
input signals, and common mode noise rejection. However, these methods are reported to
have limited effectiveness. Thus, software-based defenses are also introduced, including
estimating the EMI level in the environment, adaptive filtering, cardiac probing to see if
the sensed signals follow an expected pattern, reverting to safe defaults, and notifying
the victim (patient) or physician about the possibility of an attack to allow them to take
suitable actions to move away from the EMI source.
Shoukry et al 2015; 2016 take a somewhat different approach that is rooted in control
theory and formal methods. The idea is to create a mathematical model of the system and
of sensor attacks, and devise algorithms to identify subsets of sensors that are attacked,
isolate them, and use the remaining (unattacked) sensors to perform state estimation and
control.

Lee & Seshia, Introduction to Embedded Systems 487

17.5. ADVANCED TOPICS

17.5.2 Side-channel Attacks

Many embedded systems are accessible to an attacker not just over a network but also
physically. These systems are therefore exposed to classes of attacks not possible in other
settings. One such class are known as side-channel attacks, which involve illegal infor-
mation flows through side channels. Since the seminal work by Kocher (1996), attacks
have been demonstrated using several types of side channels, including timing (Brumley
and Boneh, 2005; Tromer et al., 2010), power (Kocher et al., 1999), faults (Anderson and
Kuhn, 1998; Boneh et al., 2001) memory access patterns (Islam et al., 2012), acoustic sig-
nals (Zhuang et al., 2009), and data remanence (Anderson and Kuhn, 1998; Halderman
et al., 2009). Timing attacks involve the observation of the timing behavior of a system
rather than the output values it generates. Power attacks involve the observation of power
consumption; a particularly effective variant, known as differential power analysis, are
based on a comparative analysis of power consumption for different executions. In mem-
ory access pattern attacks, observing addresses of memory locations accessed suffices
to extract information about encrypted data. Fault attacks induce information leaks by
modifying normal execution via fault injection.
While an exhaustive survey of side-channel attacks is outside the scope of this book,
we illustrate, using the example below, how information can leak through a timing side
channel.

Example 17.8: Consider the C implementation of modular exponentiation given

as the modexp function of Example 16.1. In Figure 17.2 we show how the exe-
cution time of modexp varies as a function of the value of exponent. Recall
how the exponent usually corresponds to the secret key in implementations of
public-key cryptosystems such as RSA or Diffie-Hellman. Execution time is de-
picted in CPU cycles on the y axis, while the value of exponent ranges from
0 to 15. The measurements are made on a processor implementing the ARMv4
instruction set.
Notice that there are five clusters of measurements around 600, 700, 750, 850,
and 925 cycles respectively. It turns out that each cluster corresponds to values of
exponent that, when represented in binary, have the same number of bits set to
1. For example, the execution times for values 1, 2, 4 and 8, each corresponding
to a single bit set to 1, are clustered around 700 CPU cycles.

488 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

Modular Exponentiation Timing Graph

950

900

850

800
Runtime (cycles)

750

700

650

600

550
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Exponent

Figure 17.2: Timing data for the modexp function of Example 16.1. The graph
shows how execution time (in CPU cycles on the y-axis) for modexp varies as a
function of the value of the 4-bit exponent (listed on the x-axis).

Lee & Seshia, Introduction to Embedded Systems 489

17.6. SUMMARY

Thus, from simply observing the execution time of modexp and nothing else,
and with some knowledge of the underlying hardware platform (or access to it),
an attacker can infer the number of bits set to 1 in exponent, i.e., in the secret
key. Such information can significantly narrow down the search space for brute-
force enumeration of keys.

In Example 17.8, it is assumed that an attacker can measure the execution time of a fairly
small piece of code such as modexp, embedded within a larger program. Is this realistic?
Probably not, but it does not mean timing attacks cannot be mounted. More sophisticated
methods are available for an attacker to measure execution time of a procedure. For
instance, Tromer et al. (2010) show how AES can be broken using a timing attack where
an attacker simply induces cache hits or misses in another process (by writing to carefully
chosen memory locations within its own memory segment), along with an indirect way of
measuring whether the victim process suffered a cache hit or a cache miss. This can allow
the attacker to know if certain table entries were looked up during the AES computation,
thereby allowing him to reconstruct the key.
Side-channel attacks remind us that security compromises are often achieved by breaking
assumptions made by system designers. In designing an embedded system, careful con-
sideration must be given to the assumptions one makes and to plausible threat models, in
order to achieve a reasonable level of assurance in the system’s security.

17.6 Summary

Security and privacy are now amongst the top design concerns for embedded, cyber-
physical systems. This chapter gave an introduction to security and privacy with a focus
on topics relevant for cyber-physical systems. We covered basic cryptographic primitives
covering techniques for encryption and decryption, secure hash functions, and digital sig-
natures. The chapter also gave overviews of protocol security and software security, as
well as secure information flow, a fundamental topic that cuts across many sub-areas in
security and privacy. We concluded with certain advanced topics, including sensor secu-
rity and side-channel attacks.

490 Lee & Seshia, Introduction to Embedded Systems

 17. SECURITY AND PRIVACY

Exercises

1. Consider the buffer overflow vulnerability in Example 17.2. Modify the code so as
to prevent the buffer overflow.

2. Suppose a system M has a secret input s, a public input x, and a public output z.
Let all three variables be Boolean. Answer the following TRUE/FALSE questions
with justification:
(a) Suppose M satisfies the linear temporal logic (LTL) property G ¬z. Then M
must also satisfy observational determinism.
(b) Suppose M satisfies the linear temporal logic (LTL) property G [(s ∧ x) ⇒ z].
Then M must also satisfy observational determinism.

3. Consider the finite-state machine below with one input x and one output z, both
taking values in {0, 1}. Both x and z are considered public (“low”) signals from a
security viewpoint. However, the state of the FSM (i.e., “A” or “B”) is considered
secret (“high”).

input: x : {0,1}
output: z : {0,1}
x=1/0
x=0/1
x=0/1

x=1/0

TRUE or FALSE: There is an input sequence an attacker can supply that tells him
whether the state machine begins execution in A or in B.

Lee & Seshia, Introduction to Embedded Systems 491