{'fraction_non_alphanumeric': 0.02655071571494536, 'fraction_numerical': 0.005387101739264276, 'mean_word_length': 4.906590909090909, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Control Flow Graph Modifications for Improved RF-Based Processor Tracking Performance

Many dedicated embedded processors do not have memory or computational resources to coexist with traditional (host-based) security solutions. As a result, there is interest in using out-of-band analog side-channel measurements and their analyses to accurately monitor and analyze expected program execution. In this paper, we describe an approach to this problem using externally observable multi-band radio frequency (RF) measurements to make inferences about a program's execution. Because it is very difficult to identify individual instructions solely from their RF emissions, we compare RF measurements with the constrained execution logic of the program so that multiple RF measurements over time can effectively track program execution dynamically. In our approach, a program's execution is modeled by control flow graphs (CFG) and transitions between nodes of such graphs. We demonstrate that tracking performance can be improved through applications program modifications such as changing basic block transition properties and/or adding new basic blocks that are highly observable. In addition to demonstrating these principled approaches on some simple programs, we present initial results on the complexity and structure of real-world applications programs, namely gzip and md5sum, in this modeling framework.


Introduction
All digital logic and data in a computing system are subject to compromise by an attacker. As a result, any security monitoring or analysis done within the same communications and computational fabric is also subject to compromise. Moreover, many embedded processors do not have the additional memory or computational resources to provide their own security solutions. As a result, there is interest in using analog side-channel measurements and their analyses to monitor expected program execution [6,4]. We describe an approach to this problem that exploits measurements of involuntary/unintended electromagnetic emissions from commodity processors and which analyzes those measurements to estimate aspects of the embedded software execution. It is of particular importance to detect deviations from the logically constrained execution paths determined by the expected program structure.
To detect deviations in program execution at fine granularity (e.g., changes of a single basic block) requires understanding of the embedded program's control flow graph (CFG) and the limits on our ability to correctly map the measured electromagnetic features to the currently executing block. In particular we explore the dynamic relationship between the unique classified features (or "color" as they map to a given code block or graph node) and the theoretical limitations on correctly identifying the traversal of the CFG. Towards this end we describe a hierarchy of CFG models in which different models have different execution tracking performance properties. We then describe approaches to modifying the program and hence the CFG such that the overall program functionality is retained with limited impact on execution time while dramatically enhancing the ability to correctly track the program and hence detect deviations from expected behavior.
Detecting cyber agents using intrusion detection systems (IDS) running in the same machine creates new vulnerabilities and is therefore inherently risky. In such situations, cyber agents could have full access to the machine state and can circumvent common detection checks. To address this problem, applications programs are often sandboxed within virtual machines in which a hypervisor can inspect the execution within the sandbox, thereby separating the IDS software outside the sandbox from the cyber agent execution space within the sandbox. Unfortunately, low-powered embedded devices prevalent in the Internet-of-Things (IoT) and industrial control systems (ICS) lack the computational horsepower to implement such safe guards [2].
The authors and their respective organizations are jointly conducting research into methods for providing cyber defenses through analysis of involuntary analog emissions. Our method provides a principled approach to analyze and exploit all available information sources and inform about achievable performance bounds and quantify analog side-channel information. We analyze individual and combined contributions of analog emissions and propagation physics, signal and interference levels and waveforms, and code structure information. Figure 1 depicts a notional high-level description of our real-time system. This approach consists of three key areas of innovations: • Measurements suite that consists of instantaneously broad band high fidelity measurements, as well as using cost efficient software defined radios (SDRs) and multi-modality collections. These provide comprehensive depth and breadth of data collected under multiple conditions, providing accurate waveforms and distribution of signals-of-interest and interference. Signal quality as measured by signal-to-noiseratio (SNR) and signal-to-interference-and-noise (SINR) can be be compared against the theoretic bounds provided by an analog link analysis parameterized by emission source, distance, modality, and channel conditions.
• Novel data adaptive signal processing methods that utilize annotated test vectors to exploit side information about measurements, devices, and embedded code to generate a stream of (probability weighted) features related to internal device state and operations. In addition, this can find optimal bands of operation and filters to separate signals from interference and noise while retaining classification information. Our approach quantifies available information at the raw data level and the incremental information provided by the side-information using pre-and post-processing SNR and SINR.
• Machine learning algorithms using multiple resolution dynamic models that first learn models that link known program execution to observed measurements. State tracking over time is used to validate the  By focusing primarily on RF/EM emissions, our approach isolates the security functionality by an "air gap" from the target host. A major challenge that must be overcome, however, is obtaining sufficient state information via unintended emissions to accurately characterize the threat.
In this paper, we describe a modeling and analysis approach that allows us to model programs through their control flow graphs so that the RF measurements can be regarded as noisy observations of the basic blocks executing within the program. Section 2 outlines the modeling framework, Sec. 3 describes experiments and analyses we have performed on notional and real-world programs and finally Sec. 4 is a summary with discussion of future work we intend to conduct in this general problem space.

Model Framework
In this section we describe in detail the model framework that captures program execution at the basicblock level. This allows us to address the control flow graph tracking problem that must be solved before confronting the issue of cyber intrusion detection using sensor measurements of RF emissions. Then, we outline a taxonomy of "observability classes" of CFGs. We find that even though in many cases the CFG is not "observable" (in a technical sense that is explained later), the CFG can be modified in appropriate ways so as to significantly improve its tracking performance with no effect on program functionality and minimal effect on real-time and memory constraints.

Colored graphs and the hidden Markov model
Software execution is modeled as a series of transitions between states on a control flow graph (CFG), where the nodes can be modules, functions, or basic blocks (depending on the desired level of granularity) and the edges are the allowed transitions between states. While each node is executing, a particular pattern of RF emissions occurs. The sequence of states X t cannot be observed directly, instead the states must be inferred from the observed sequence of RF emissions ("symbols") Y t . A natural formalism describing such a situation is the hidden Markov model (HMM) shown in Fig. 2 [7,9].
It is important to note that the concept of "state" as used in systems theory does not correspond necessarily to a basic block in a program's CFG because the true state of a program includes the memory values as well as the program counter and the reader is encouraged to understand this difference. We address the question of how closely basic blocks approximate system state in the more formal sense in Sec. 3.2.3 when we empirically investigate some real-world programs.
In this model, the sequence of hidden states X t forms a (first order) Markov chain: with transition matrix (c) Featuregram with associated colors Figure 3: An emission matrix (a) which has only one highly-probable symbol per state can be described as assigning a "color" to each state on the CFG (b). The featuregram (c) shows the four-dimensional, continuous-valued feature vector and the corresponding colors assigned by a classifier.
The symbol Y t emitted at any point depends only on the current state X t : In the case of discrete symbols, the emission matrix is defined as While much of the literature on HMMs focuses on discrete scalar symbols Y t , this formalism can handle the more general case where Y t is a multidimensional, continuous random variable simply by replacing P (Y t |X t ) with the relevant joint probability density function (PDF). Furthermore, it is often convenient to assign a discrete scalar symbol to a general measurement using a classification or clustering algorithm. As a further abstraction, the discrete symbols may be taken to correspond to "colors" emitted by each state. If the emission distribution preferentially emits a single color for each state, the model may be described as a node-colored directed graph. An example of this is shown in Fig. 3. When multiple colors may be emitted by a state, the graph is said to be multi-colored, and can be reduced to a simple node-colored directed graph by splitting each multi-colored node. As will be seen, node-colored directed graphs provide a useful framework for reasoning about the properties of control flow graphs.

Observability classes of colored graph models
As mentioned earlier, a node-colored directed graph (corresponding to a CFG) can be identified by a state model in which the nodes of the graph represent states and the edges represent allowed transition between states. The most general description of such a state model is provided by an HMM. The structure of the underlying colored graph may not permit unique reconstruction of the state sequence in general. There are, however, restricted classes of models that enable more accurate tracking in various use cases: • In a trackable model the number of hypotheses consistent with an observation sequence grows polynomially in the length of the observation sequence [3].
• In a unifilar model the next state X t+1 is uniquely determined given the current state X t and the next symbol Y t+1 [11].
• In an observable model the state X t can be uniquely determined given the observation sequence Y 1 , . . . , Y t , after some fixed initial burn-in [5].
This hierarchy of graph classes is shown in Fig. 4.

Graph modification to improve observability
In principle, it is possible to change the observability class of a graph by adding or deleting states, by adding or deleting transitions between nodes, or both. Given that the specific way in which a control flow graph is connected as well as the transition probabilities between different nodes determines software functionality, removing states or modifying transition probabilities significantly is not guaranteed to preserve program function.
On the other hand, the addition of states (nodes) constructed to have no effect on program function (e.g., a short loop of no-op instructions), but which emit a distinct color, can be very useful. Inserting such "indicator blocks" at strategic points in a program can change the observability class and improve tracking performance, which we demonstrate in Sec. 3.1.
It is important to remark that such program modifications, while not changing program semantics, could change a program's memory footprint and/or its real-time performance characteristics. Such modifications must accordingly be done with such constraints in mind.

Experiments and Results
In this section, we describe the experiments conducted on test programs and real software programs and the results obtained. In particular, in Sec. 3.1 we describe the experimental setup and data collection procedure for simple test programs, and then demonstrate the efficacy of our CFG modification approach. We show that impressive results for CFG tracking can be obtained for such test programs.
Carrying out a similar analysis for real software programs is considerably more difficult, however. For example, in many cases the source code may not be available and, even if it is, low-level program structure may be significantly altered by an optimizing compiler so that information on the program's structure may be difficult to obtain. Therefore tools must be used to extract the control flow graph of the program as it will be executed.
Many dynamic profiling and tracing tools also have limited support on embedded platforms. Also, as we will see later, the time scale for transitions between different basic blocks of realistic CFGs is typically much smaller than that of the observation model corresponding to RF emissions. Hence "coarse-graining" techniques must be applied to the original CFG to extract a coarsened version that corresponds accurately to the observation model. In Sec. 3.2 we show some results related to the extraction of control flow graphs and their properties for some simple realistic software programsgzip and md5sum. We also find the appropriate model framework to track execution of these programs. In the near future, we intend to apply our CFG modification and tracking techniques to real software programs such as these and also study use cases for cyber intrusion detection as described in Sec. 4.

Experimental demonstration of pathology mitigation
Our first experiment utilized the Arduino Uno, a common Internet-of-Things (IoT) device which exemplifies the security challenges and motivations. The Uno, with a 16 MHz processor clock, 32 kB of program flash memory, and no tractable ability to execute parallel execution threads, is unequipped to perform any hostbased security activities. Furthermore, the performance capabilities of this board and processor are very similar to millions of deployed hardware devices.
This first experiment, designed to facilitate the development of control flow graph tracking algorithms and pathology mitigation, was composed as follows: • create basic blocks, b 1 , . . . , b n , where each basic block is a loop that performs a unique set of instructions as shown in Fig. 5; • individually execute and perform RF measurements on each basic block, using the measurements to train a classifier; • create a control flow graph that utilizes a subset of these basic blocks; • perform random walks through this control flow graph, such that at each time step, the next basic block to execute will be randomly selected from the available legal transitions from the presently executing block, with probabilities shown in Fig. 7a.  We started with the unobservable CFG in Fig. 6a and the transition matrix in Fig. 7a, where the blocks are composed of loops of between 20 and 105 instructions. We set the number of loop executions in each block such that each "step" through a block lasted 5 ms. We then added indicator blocks to produce the unifilar CFG in Fig. 6b.
The RF emissions were measured at a range of 10 mm, using a near field probe sensitive to the magnetic field from 300 kHz to 1 GHz. This probe was sampled at 4 GHz using a Texas Instruments ADC12J4000 analog-to-digital conversion system. The measurement setup is shown in Fig. 8. We computed the short-time Fourier transform using a 66 µs window length, applied a random forest classifier to each time point in the resulting spectrogram, then binned the results to a 5 ms time resolution by taking the mode in each bin. The emission matrix from the classifier (but prior to binning) is shown in Fig. 7b. The effect of binning is to make all of the states except T140 single-colored. The test with indicator blocks added used the same path through the CFG as the test without indicator blocks -the indicator blocks were simply added at the appropriate transitions.
The results are shown in Fig. 9. In the figure, the "no CFG tracking" curve is the state inferred directly by the classifier with no knowledge of the CFG and the "with CFG tracking" curve was constructed by applying the Viterbi algorithm to find the most likely path given knowledge of the transition matrix, the classifier confusion matrix, and the entire symbol sequence. Without indicator blocks, CFG tracking has no effect, and the error rate (number of blocks wrong divided by total number of blocks) is 10.8%. With indicator blocks, CFG tracking obtains perfect reconstruction of the sequence of states, as is expected for a unifilar graph.

CFG extraction and model framework for real software
In order to assess the prognosis for basic block-level tracking in real software, we have begun collecting instruction-level execution traces from common Linux tools using GDB [1]. Presented here are the results from the gzip and md5sum programs on Ubuntu running on x86 64 applied to 100 randomly-generated 1 kB files. The instruction-level traces are post-processed into basic blocks based on jump, call, and return instructions. The CFG is then extracted based on which transitions are observed in the 100 runs -no static analysis of possible jump targets has been performed. The resulting CFG has many blocks with in-degree and/or out-degree of one. To make the subsequent analysis tractable, whenever a block's in-degree and its parent's out-degree are both one, we merge the block and its parent into a "reduced block."

Blocks, reduced blocks have few instructions
The distribution of the number of instructions per block is shown in Fig. 10. In both programs, the median number of instructions per basic block is about 3, which is comparable to (if not slightly lower than) what     In the CFG with tracking blocks added, the Viterbi algorithm provides perfect tracking performance, as is expected for a unifilar graph. was reported in [8]. Working in terms of reduced blocks increases the median number of instructions to 7 and the right-hand tail of the distribution is pulled out to include reduced blocks with a few hundred instructions. The shortness of basic and reduced blocks indicates that time resolution will be a key obstacle to overcome to obtain block-level tracking of real software -7 instructions is about 0.4 µs on an Arduino Uno, and will be even shorter on more powerful platforms.

Control Flow Graphs have very sparse transition matrices
The joint distribution of in-and out-degree for the reduced block CFG is shown in Fig. 11, and some properties of the basic and reduced CFGs are given in Tab. 1. Even in the reduced CFG, there are still many nodes with in-degree = out-degree = 1; as suggested by the fact that the number of edges in the reduced CFG is ∼ 1.6× the number of reduced blocks, the transition matrices are very sparse. This improves the prognosis for observability, because a lower average out-degree means there are fewer opportunities for the conditions for observability, unifilarity, or trackability to be violated.

A first-order Markov chain best describes the datasets
When the HMM was introduced in Sec. 2.1, Eq. (1) defined a first-order Markov chain: the next state only depends on the current state. However, computer programs have memory, and the next state (basic block) may depend on several of the previous states (basic blocks) as well as the memory state of the program. A   In the joint distribution, the shading is proportional to logarithm of the counts in the bin, and the black points indicate which bins are populated -the distributions are both very strongly concentrated at in-degree = out-degree = 1. Also of note is that some nodes have high in-degree or high out-degree, but none have both -the tails of the joint distribution form an "L" shape. Markov chain with memory (or order) m has the transition distribution Such a model has |S| m (|S| − 1) parameters, where |S| is the number of states. Table 2 gives the number of states, number of observations, and number of parameters for the gzip and md5sum datasets. Because of the exponential growth in the number of parameters, the m = 2 case has substantially more parameters than observations. Therefore, it is reasonable to expect that the data will only support m ≤ 1. This assertion can be made rigorous using model selection tools, including [12]: • Akaike information criterion: where n θm is the number of parameters for the model with memory m and L m = max θm P (D|θ m , m) is the probability of the data D under the maximum likelihood estimate. A lower AIC m indicates a better model.
• Bayesian information criterion: where n D is the number of observations. A lower BIC m indicates a better model.
• Model evidence (also known as marginal likelihood): which is the probability of the data averaged over the possible values of the parameters, and P (θ m |m) is the prior distribution representing any prior knowledge about the parameters θ m . In this application, we use a Dirichlet distribution with α ij = 1 as our prior distribution when computing Z m . A higher Z m indicates a better model.
In the limit of n D n θm [10], so we report −2 ln Z m so that all quantities are on the same scale. All three of these metrics implement a tradeoff between the model complexity (the number of parameters relative to the number of observations) and the how well the model fits the data. The three model selection metrics are shown in Fig. 12. All three metrics prefer a first-order Markov chain, m = 1: the m = 0 model (states are independently and identically distributed (IID)) is too simple to explain the observed behavior, and the m ≥ 2 models have too many parameters relative to the number of observations to be adequately constrained.   6) and (7) (model complexity penalty) dominates the second term (goodness of fit). Note that the approximation in Eq. (9) breaks down for m ≥ 2 because nD < n θm .

Similarities may arise from shared code
The similarities observed between gzip and md5sum in the previous sections may be explained by the code they share for initialization, finalization, input, output, and loading of shared libraries. In order to characterize this, we constructed two simple C programs: • "return 0;" consists of "int main() {return 0;}" and hence only involves the code to initialize and finalize an executable.
• "hello, world" additionally exercises the code to write to the standard output. Table 3 summarizes the degree of overlap with these programs, where the fraction of shared instructions is defined as (# instructions in shared functions)/(total # instructions). These results indicate that about 20% of the functions in gzip and md5sum are there for initialization and finalization, and another 10-20% of the functions are for output. Also of interest is that about 50% of the function in gzip are also in md5sum, though only about 16% of the instructions are spent in these shared functions. This substantial overlap illustrates why knowledge of the CFG is essential for malware detection: many benign (and malicious) programs may call the same functions but in different sequences. Therefore, the only way to determine if the software being executed has been altered is to have knowledge of what sequences of function calls are structurally possible.

Summary and Future Work
In this paper we described a general framework for detecting unintended and possibly malicious code running on processors via measurements of unintended RF emissions on a sensor separated by an air-gap. In terms of analysis, we primarily focused on the ability to track program progression at fine granularity as it traverses its control flow graph. This is a prerequisite to addressing the issue of cyber intrusion detection within this context. The approach requires principled understanding of the CFG as observed via the measurements and the fundamental limits on the ability to track the program's execution. Moreover we developed and described a principled approach for modifying the CFG of the program to dramatically enhance this tracking capability such that the program functionality is preserved and with minimal impact on overall latency of its execution. Finally, we reported some results on the extraction of CFGs and their properties, as well as the model framework describing tracking execution, for some real-world software programs. Significant further enhancements to these methods are possible and are being investigated by our team. These include the following: • Developing a general taxonomy of colored graph models and their mitigation approaches; • Applying CFG modification and tracking techniques to real software programs; • Understanding the trade-offs between tracking granularity and limits on tracking performance, adding new constraints to the program modification to minimize various metrics related to undesired impact on program operation; • Leveraging the above techniques for cyber intrusion detection (using RF emissions) for a variety of relevant use cases; • Exploring use cases involving more complex multi-threaded and otherwise time-shared computing environments; • Additional analyses of fundamental mathematical descriptions of CFG tracking in more complicated environments.