extfieldsofstudy:
Computer Science
Medicine

text:
Fever Time Series Analysis Using Slope Entropy. Application to Early Unobtrusive Differential Diagnosis

Fever is a readily measurable physiological response that has been used in medicine for centuries. However, the information provided has been greatly limited by a plain thresholding approach, overlooking the additional information provided by temporal variations and temperature values below such threshold that are also representative of the subject status. In this paper, we propose to utilize continuous body temperature time series of patients that developed a fever, in order to apply a method capable of diagnosing the specific underlying fever cause only by means of a pattern relative frequency analysis. This analysis was based on a recently proposed measure, Slope Entropy, applied to a variety of records coming from dengue and malaria patients, among other fever diseases. After an input parameter customization, a classification analysis of malaria and dengue records took place, quantified by the Matthews Correlation Coefficient. This classification yielded a high accuracy, with more than 90% of the records correctly labelled in some cases, demonstrating the feasibility of the approach proposed. This approach, after further studies, or combined with more measures such as Sample Entropy, is certainly very promising in becoming an early diagnosis tool based solely on body temperature temporal patterns, which is of great interest in the current Covid-19 pandemic scenario.

Introduction
The current Covid-19 pandemic has demonstrated once more how important it is to closely monitor body temperature at a very large scale, remotely, and continuously. Unfortunately, a suitable scheme that addresses simultaneously all these issues is still unavailable. Only some progress in terms of thermal imaging has been made and is currently in use. However, at a general clinical level, and for disease detection, infra-red single temperature readings are still the standard practice. This is a very poor approach that will have to change in the coming years in order to improve, not only readiness against other possible future pandemics, but also the treatment of any other pathology where body temperature can play an important role in early diagnosis and prognosis [1].
Although the infra-red clinical temperature measuring technology is very convenient in terms of non-obtrusiveness and lack of contact (distance), in its current form it is certainly not more than a plain fever/no fever assessment tool [2]. It still overlooks the richer physiological information yielded by the output of the thermo-regulatory system that can be obtained from a temporal continuum perspective patterns [19]. Using a training set, it is also possible to accomplish this task using tools such as neural networks [20]. In a more general way, other works studied fever patterns from a descriptive point of view [21]. This line of research is still a rather unexplored field that certainly deserves more attention.
This paper proposes a scheme for assessing the differences between body temperature records coming from a variety of pathological backgrounds, as in [17]. The analysis was based on body temperature records of 24 h, 1 min sampling period, from patients that specifically developed a fever due to malaria or dengue diseases. The analysis was not only focused on the global differences of the entire records, but also on quantifying the differences along or at some temporal windows. This way it would not be necessary to monitor for 24 h before the differences became detectable, and diagnosis could be anticipated several hours, triggering earlier patient isolation and/or treatment, if necessary. The entropy measure employed was Slope Entropy (SlopEn), a recently proposed method [22] based on gradient patterns between consecutive samples. The results achieved demonstrated a high disease classification potential that could be re-assessed using also other pathologies in order to achieve an additional inexpensive and unobtrusive diagnosis tool. A block diagram of the study is shown in Figure 1. Each step in this diagram will be described in detail in the next Sections.  Figure 1. Block diagram of the study. Body temperature records from dengue and malaria patients were recorded over 24 h. The corresponding time series were processed using Slope Entropy, and then classified using a single threshold obtained from the Receiver Operating Characteristic (ROC) Curve. The performance was assessed using the Matthews Correlation Coefficient.

Dataset
The experimental dataset included 31 body temperature time series of dengue (DE) patients (18 males) , and 16 of malaria (MA) patients (12 males), diagnosed according to specific clinical findings. Subjects with undifferentiated fever, a febrile illness accompanied by non-specific symptoms, admitted to the hospital and who met the following criteria were included in the study:

1.
Fever of more than or equal to 7 days duration.

2.
Individuals with an intact tympanic membrane.
The Institutional Ethics Committee approval was obtained for the study on 15/01/2014 (IEC KMC MLR 01-14/13). Written informed consent was obtained from each participant after explaining the study in the language they understand. Confidentiality was maintained about their identity.
The time series were acquired once over 24 h, starting at 9:00, with a sample per minute, 1440 temperature readings in total. Before starting the continuous tympanic temperature recording, subjects' auditory canals were examined and any ear wax, if present, was removed from the auditory canal using normal saline. After the auditory canal was dried, the probe was fixed for recording. A temperature probe was gently inserted into the auditory canal which projected towards the tympanic membrane. Another end of the temperature probe was connected to the temperature monitoring device and the recorded temperature was stored. Prior to temperature recording, the study subjects were informed not to take a shower and not to perform any strenuous exercises. Temperature of the subjects was recorded when the ambient temperature was in the range of 22 to 40 • C.
All the records were normalized before the classification analysis: zero mean and unit variance. No other preprocessing took place. An example of one record of each class is shown in Figure 2. These records have not been used in any other prior study yet, although they were acquired in the same clinical setting as the dataset used in [17]. The clinical contributors of this paper from Kasturba Medical College (India) are conducting an ongoing effort of recording body temperature data from a disparity of pathologies: dengue, malaria, tuberculosis, leptospirosis, thyroiditis, enteric fever, pyogenic sepsis, and others, and when a significant number of records of each type becomes available, we study their properties and the best methods to yield a differential diagnosis based solely on time series analysis, as was the case in [17][18][19][20] and in the present paper.

Slope Entropy
SlopEn was first described in [22]. It is based on computing relative frequencies of subsequences, as many other entropy methods, but instead of using amplitude or ordinal information, it uses as symbols the representation of the slope between two consecutive samples.
Given an N-length input time series x = {x 0 , x 1 , . . . , x N−1 } and m-length subsequences of x, x m j = x j , x j+1 , . . . , x j+m−1 , a symbolic pattern is obtained for each x m j by thresholding each difference d = x j+1 − x j as: being γ and δ two input parameters, with γ > δ > 0. Once all the symbols are computed for a subsequence, a pattern-matching process takes place in order to update the relative frequency of each one in a list dynamically filled with the patterns found so far. The final vector of relative frequencies is used to compute the result using a Shannon approach [23]. An algorithm for computing SlopEn is shown below (Algorithm 1): (Compute relative frequency of each pattern, #=sizeof operator) The final values were normalized by the maximum SlopEn obtained in order to keep their range between 0 and 1. A more detailed SlopEn algorithm is described in [22]. The SlopEn result of each record was the single classification feature to be used in the performance analysis carried out in Section 3.
For comparative purposes, SampEn was also computed in the experiments. This measure is one of the most successful methods for time series classification [24][25][26][27], including temperature records [17], and it is therefore a good cornerstone on which to build the conclusions for SlopEn.

Performance Assessment
The Matthews Correlation Coefficient (MCC) [28] was used in the present work in order to quantify the performance of the method described. This is a binary classification performance metric based on considering the Positives (P, dengue in this case) and Negatives (N, malaria) as two different variables (the classification labels for the two classes under analysis), and computing their correlation. The closer the correlation is to 1, the better is the classification. It is initially smaller than others, reaching 0.5 when 75% of the predictions are correct. It is based on the also well known phi-coefficient [29].
The MCC is better suited for imbalanced classes than other methods or variables. It ranges between −1 and +1, with +1 accounting for a perfect classification, 0 for a random classification, and −1 for a complete reverse classification. No class is more important than the other, however unbalanced the partition is. The MCC results are symmetric. In a binary case, this measure can be easily computed as: with TP = True Positives (actual positives that are correctly labelled as P), FN = False Negatives (actual positives that are incorrectly labelled as N), TN = True Negatives (actual negatives that are correctly labelled as N), and FP = False Positives (actual negatives that are incorrectly labelled as P). For balanced sets, there is a good correspondence between accuracy and MCC [30], whereas for imbalanced cases, accuracy can be overoptimistic. It is then where MCC exhibits its superior robustness and reliability [28]. For a highly truthful classification, MCC should be as close to 1 as possible, at least above 0.5, in general. Scores in the vicinity of 0 account for mediocre classifications (random guess) that should not be considered as good prediction tools. The classification threshold was obtained from the Receiver Operating Characteristic (ROC) Curve in each experiment, as the point on the curve closest to coordinates (0,1), a standard procedure in many similar works [31].
In order to compare the results of the present paper with previous studies that did not use MCC but the classification accuracy instead, in some cases the results were also quantified in terms of sensitivity (true positive rate, correctly classified dengue patients), specificity (true negative rate, correctly classified malaria patients), and accuracy (ratio or percentage of total records correctly classified).

Input Parameter Configuration
The first step of the experiments was to find a suitable input parameter configuration for SlopeEn and the two diseases under analysis, dengue and malaria. This search was confined to parameters m and γ, with δ = 1 × 10 −6 in all cases. The results of this preliminary step are shown as a heat map in  It can be stated that the classification performance in terms of MCC was reasonably quite stable, with almost the entire grid above 0.5 (or its reverse), and many regions around 0.8-0.9, making the selection of the input parameter values less critical. For stability, we chose m = 6 and γ = 0.25.

Classification Performance
With the specific parameter configuration stated in the previous section, the MCC value obtained was 0.9066 (98 % of time series correctly classified, a sensitivity of 1, and a specificity of 0.93), in other words, DE and MA records were clearly separable using SlopEn. This discriminant power is illustrated in Using SampEn, the highest performance was achieved using m = 3, 4, and r = 0.25-0.50, yielding MCC = 0.6347, sensitivity = 0.81 and specificity = 0.87. This was also a good performance that confirms the suitability of SampEn to this task, as demonstrated in [17].
A Leave One Out (LOO) cross validation analysis was also carried out for a more robust demonstration of the separability of the two classes, DE and MA. Since the number of instances of each class was not very big, this method was considered better suited to this case [32]. This analysis was based on removing one time record from each class, computing a classification threshold from the remaining records using their ROC curve, and then applying the threshold obtained to the initially removed records for their classification. This process was repeated until all the time records were left-out once in the majority class, DE (imbalanced dataset), although some instances of the minority class might have been used more than once [33] due to random oversampling [34]. This LOO analysis yielded the following results: 94% of the time series correctly classified, with a standard deviation of 0.0185. As usual, the performance with LOO was worse than using the entire dataset for classification (98% vs. 94% correctly classified instances), but still very high.

Window Analysis
From a prompt diagnosis perspective, and taking into account that fever frequently undergoes chronobiological variations, it would be convenient to assess the separability between the temperature records again, but using shorter time windows. This way, it will not necessary to wait 24 h, and it could be hypothesized that intervals of greater differences could be identified for better temperature time series characterization.
The experiments were therefore repeated using the same parameter configuration, using increasing lengths in 1 h steps (60 samples), as depicted in Figure 5. This last experiment offered a clear but incomplete picture of the possible effect of temporal windows. In order to get the full picture, it was also necessary to assess the effect of a sliding window of fixed size instead, related to possible chronobiological changes in the dynamics of the temperature data of each disease, some of which have already been reported in the scientific literature [21,35].
Using a sliding window of 240 samples (4 h), for which MCC achieved a high MCC value of at least 0.70 ( Figure 5), the classification experiment was repeated moving the starting point in 60 samples steps. These results are depicted in Figure 6.

Generalization Analysis
The comparison between DE and MA temperature records has provided clear evidence of the possible separability of both diseases based solely on the SlopEn analysis of the corresponding time series. However, it could be stated that these two diseases are not more than a successful example that does not necessarily demonstrate any generalization capability when applied to other diseases.
In order to avoid this possible overfitting or misinterpretation, the experiments in this subsection were devised to explore the behaviour of the method when used with fever time series coming from other diseases. It is important to note, though, that there are not publicly available body temperature continuous time series databases (as far as we know), the additional data used here were also acquired in the same clinical setting as the main experimental database, and these experiments were not as far-reaching as for the initial database.
The first additional disease studied was leptospirosis (LE), since we already had 15 records of this type. The separability analysis between leptospirosis and dengue was carried out in the same way, with a parameter optimization stage based on MCC computation. The highest performance was achieved at region m = 3, 4, and γ = 0.25-0.50, with MCC = 0.8500 (sensitivity = 1, specificity = 0.87), quite stable, with half the parameter space above 0.60 at least (sensitivity and specificity above 0.80). The MCC result achieved using the same parameter configuration as for DE and MA was 0.6604. The results obtained with SampEn for LE and DE were sensitivity = 0.90, specificity = 0.86, and MCC = 0.7163, using other input parameter values specifically optimized for this method.
In the case of leptospirosis and malaria, the performance achieved was slightly lower but still very significant. In the parameter region of m = 5, 6 and γ > 0.6, MCC≥ 0.5557 (sensitivity = 0.73, specificity = 0.85), with a maximum of 0.6310. The MCC result achieved using the same parameter configuration as for DE and MA was 0.2996 (sensitivity = 0.8, specificity = 0.56). Therefore in this case this configuration should be replaced by a more suitable one as described before. SampEn failed in this case to find significant differences, with best MCC = 0.3133, sensitivity = 0.80, and specificity = 0.56, clearly imbalanced, whatever were the parameter values employed.
We also used seven records of body temperature corresponding to malignancy (ML). When compared to dengue, the MCC achieved was greater than 0.82, for m = 3, 4 and γ = 0.70-0.80, sensitivity = 1, specificity = 0.85. For m = 6 and γ = 0.25, MCC was 0.4814 (sensitivity = 0.77, specificity = 0.85). The highest performance for SampEn was sensitivity = 0.83, specificity = 0.85, with MCC = 0.5534. Comparing malignancy and malaria, the MCC results were 0.5635 for m = 3 and γ > 0.7 (sensitivity = 0.81, specificity = 0.85), with MCC = 0.2441 using the initial parameter configuration. Again, it would be better to choose a more optimal input parameter configuration in this case. SampEn achieved an MCC = 0.4377, with a sensitivity of 0.75, and a specificity of 0.85. All these results using only seven ML records should be taken with caution due to the low number of records, but they were included since at least a general trend could still be observed. The results of all these experiments are depicted in Figure 7.
In another group of experiments, the same database of body temperature records as in [17] was used, with additional diseases: tuberculosis, fevers of non-tubercular origin, and fevers without evidence of infection (dengue was not used again). In that case, Sample Entropy (SampEn) was the entropy measure applied, and the records were also low-pass filtered. Trace segmentation [36], used as an additional feature selection method in [17], was not used here. Further details of these datasets can be found in the original paper.
Some of those additional diseases were analyzed for separability using SlopeEn. They were not compared with the present dataset of MA or DE since they were not filtered as in [36]. For comparative purposes with results from that previous study, sensitivity and specificity were the important metrics in these cases.  Figure 7b, the performance is lower and more than a single point falls almost in the same spot, giving the impression the classification error is higher, despite having only two incorrectly classified records for malaria, and 1 for malignancy.
For non-tubercular and tuberculosis fevers, the maximum MCC obtained was 0.6849, when m = 4, and almost for any γ. This was a relatively low performance value, but in the original paper it was even lower, since this was a difficult classification case. In [17], the maximum sensitivity and specificity were 0.61 and 0.68 respectively (MCC was not used there), whereas in the present case were 0.75 and 0.61, or 0.68, 0.67, depending on the specific parameter configuration, higher than using SampEn anyway.
When comparing non-infectious with tuberculosis records, the MCC achieved using SlopEn was 0.6607, with 0.61 and 0.71 for sensitivity and specificity (with m = 6, 7, and for almost any γ). In this case the performance using SampEn was higher, with 0.78 for the sensitivity, and 0.75 for the specificity.
Finally, the analysis using non-infectious and non-tubercular records yielded non-significant results for the MCC based on SlopEn (around 0.05, for specificities and sensitivities in the vicinity of 0.50). However, SampEn was able to find differences, with 0.64 sensitivity, and 0.75 specificity [17].

Results Summary
The results of all the previous classification experiments described in this Section are summarized in Table 1. The method, SlopEn or SampEn, that achieved the highest performance, is highlighted.

Discussion
Finding a method to quantify the differences of body temperature curves among diseases can be a first step towards a new inexpensive diagnosing tool that fulfils the current and future needs of mass-analysis, patient isolation, and continuous and long-term monitoring. Recent efforts have been devoted successfully to accomplish this goal [17][18][19][20], although this is still a research field in its infancy.
Specifically, the present study is mainly based on [17]. However, as [17] employed SampEn as the discriminating feature, when SlopEn was not available yet, and since SlopEn seemed very promising as it outperformed SampEn in many comparative analyzes [22], it was necessary to assess the capability of this new method in the framework of temperature time series. The present study used a more diverse experimental dataset, implemented a novel windowing approach, analyzed the influence of record duration, and did not use any feature extraction method such as Trace Segmentation [17]. Using or combining other approaches based on more features or more sophisticated classification schemes could arguably improve the accuracy achieved, but we leave that approach for future studies.
The first step was to find a suitable input parameter configuration using a grid search for parameters m and γ, keeping δ constant. The results are shown in Figure 3. It is important to note that this optimization was not really necessary, since almost all combinations yielded an MCC higher than 0.5, and only a very narrow region for γ < 0.15, γ > 0.85 or some areas of m = 5, yielded MCC results below |0.5|. However, as a general step, this optimization is advisable in every case until there are some recommendations or guidelines in this regard, as there are for other methods more widely characterized [37][38][39][40][41].
The segmentation between DE and MA records was very successful, with a percentage of correctly classified instances of 98%. This performance was confirmed with the LOO analysis, with an averaged performance of 94%. The window analysis provided support to the hypothesis that differences between pathologies can become apparent in a relatively short term, and that those differences can not be uniformly distributed across the time series. Obviously, these temporal variations should be studied on a pathology by pathology basis, but it can arguably be concluded that DE and MA records can be robustly segmented using the method proposed and only 3-4 h of data.
For example, 4 h window at 800 min appears to yield high accuracy. It corresponds to time between 10 pm and 2 am. This corresponds to sleep time and might reduce other interfering factors like physical activity and autonomic changes. It is likely to represent the true basal state of the temperature pattern. It would be logistically convenient to record night temperature patterns. Even blood pressure monitoring, nocturnal blood pressure patterns, are important compared to day time readings.
Unfortunately, there are not many body temperature time series representative of a wide set of pathologies available for a more ambitious study, but it was of paramount importance to demonstrate that the results of DE-MA were not a kind of experiment of one. One of these few additional time series corresponded to 15 patients with leptospirosis, and seven with malignancy, recently acquired by the clinical coauthors of this paper from Kasturba Medical College.
The analysis with the leptospirosis records involved a comparison with DE and MA on a pair-by-pair basis, as done with DE-MA. With LE and DE, the performance was still very high, although the maximum was achieved at a different input parameter configuration. For LE and MA, the performance decreased but still above what can be considered an acceptable performance threshold in MCC, 0.5.
Although seven records do not usually suffice for a statistically significant analysis, we thought the comparison in broader terms would still be worth. In principle, the results followed the same pattern as for the previous diseases, with MCC > 0.82 for ML and DE, and MCC = 0.5635 for ML and MA, not so high. It will be necessary to acquire more records of this kind in order to confirm in future studies if this pathology is so easily distinguishable, but MCC is more robust than plain accuracy and it is reasonable to assume the trend will be the same with a greater number of time series.
The rest of the records used for classification, taken from the [17] study, were a different temperature time series since they were low-pass filtered. The results of the experiments using non-tubercular, tuberculosis, and non-infectious records were not as good as in the previous cases, but still very significant, except for non-infectious and non-tubercular records, the only case where SlopEn was unable to find differences. Others records and combinations in [17] were not addressed in the present paper because, as in the reference study, neither SlopEn nor SampEn were able to find any difference. These records will probably require additional features (average temperature, number of peaks), for a successful classification, or a combination of more methods, as in [42]. Diagnostic accuracy will increase further when clinical details and basic laboratory data are also included in the analysis.
Not all the records were analyzed in the same depth, since that is not possible in a single paper, but of the seven pairs assessed, SlopEn exhibited a high discriminating power in seven. Moreover, SlopEn outperformed SampEn in six pairs. Taking into account that SampEn already exhibited a very high performance in [17] outperforming itself other entropy methods, SlopEn can probably be considered a good choice for this kind of analysis. Besides, there is an input parameter that was not optimized at all, δ, and also the symmetry of the SlopEn thresholds, which could have contributed to a better disease detection. However, a balance between method customization and possible overfitting should be kept.

Conclusions
SlopEn can be a promising tool for assessing differences among fever patterns in body temperature time series. Frequently, a fever symptom entails additional clinical and lab tests to find out the specific disease causing the fever. These tests can be expensive, time consuming, or not available in many contexts (lack of enough resources, remote or rural locations, ambulatory monitoring). Therefore, a prompt and inexpensive diagnosis would be of great help.
In order to achieve a very robust tool to be applied in real clinical scenarios, further studies will be necessary, adding more temperature time series features, and more entropy related methods that look into amplitude or ordinal patterns, in a complementary way. In addition, more records of each disease, and more diseases, should be included in the experimental set. We are currently addressing this data gap, but it entails a huge effort, and it would be great if other researchers also acquired and shared temperature records to speed up the number of studies related to body temperature with a long term perspective.
Of extraordinary interest are Covid-19 temperature records, but they are currently too difficult and risky to acquire by the clinical staff, specially in overwhelmed healthcare systems. The approach introduced in this and previous papers could be probably be applied not only to patients that have developed the disease, but also to those in a sub-clinical stage, pre and post disease, in order to gain a deeper insight into the evolution of the disease. Another objective of the present paper is precisely to lay the foundations for the analysis of any body temperature record and obtain actionable data for an earlier diagnosis, treatment, or patient isolation if required.
Temperature pattern is likely facilitating the diagnostic work-up by enhancing the pretest probability in one direction. Final diagnosis for therapeutic purposes will be decided by specific tests. Hence, even a moderate degree of accuracy is sufficient for treating physicians in deciding the specific tests instead of ordering broad range of multiple tests. Accuracy will further improve as more and more data sets are collected which will include many more disease conditions. In summary, despite the possible limitations in terms of number of features, number of signals or number of diseases, this preliminary work provides sound evidence that the analysis of body temperature time series has a huge potential as an inexpensive and unobtrusive diagnosis tool, since SlopEn, and also other methods such as SampEn, have the potential to find differences among records from a varied and diverse set of diseases. The only thing needed is a change in the way body temperature is monitored, from manual isolated readings to continuous high-frequency long-term wireless digital data.
Author Contributions: D.C.-F. implemented and customised the SlopEn method, conducted the signal analysis experiments, and wrote the paper. P.H.D., C.M., and A.R.G. recorded the experimental dataset, generated the idea of differential diagnosis based on fever patterns, and provided the clinical perspective. All authors have read and agreed to the published version of the manuscript.


extfieldsofstudy:
Medicine
Computer Science

text:
A Comprehensive Evaluation Method of Sensor Selection for PHM Based on Grey Clustering

Sensor selection plays an essential and fundamental role in prognostics and health management technology, and it is closely related to fault diagnosis, life prediction, and health assessment. The existing methods of sensor selection do not have an evaluation standard, which leads to different selection results. It is not helpful for the selection and layout of sensors. This paper proposes a comprehensive evaluation method of sensor selection for prognostics and health management (PHM) based on grey clustering. The described approach divides sensors into three grey classes, and defines and quantifies three grey indexes based on a dependency matrix. After a brief introduction to the whitening weight function, we propose a combination weight considering the objective data and subjective tendency to improve the effectiveness of the selection result. Finally, the clustering result of sensors is obtained by analyzing the clustering coefficient, which is calculated based on the grey clustering theory. The proposed approach is illustrated by an electronic control system, in which the effectiveness of different methods of sensor selection is compared. The result shows that the technique can give a convincing analysis result by evaluating the selection results of different methods, and is also very helpful for adjusting sensors to provide a more precise result. This approach can be utilized in sensor selection and evaluation for prognostics and health management.

Introduction
With the rapid development of industrial technology, the complexity of engineering systems has increased significantly [1][2][3][4]. The increase in the failure cost of the system prompts people to pay more attention to the reliability and safety of the system [5]. Therefore, prognostics and health management (PHM) technology are widely studied and applied in the industry [3,4,6]. PHM is a method that allows for an assessment of the reliability of a system under actual application conditions. It uses the sensors to monitor the health status of a system for fault diagnosis, life prediction, and condition-based maintenance, which guides the decision making and reduces the usage and maintenance costs [7,8].
The sensor plays a significant role in PHM technology [7,[9][10][11]. It is the basis of data for state evaluation and life prediction, and its selection result has a direct influence on the application effect of PHM [12]. Therefore, it is vital to optimize sensor selection to reduce the scale of sensors and obtain the same or an even better monitoring effect. The existing sensor selection methods can be grouped into two categories: the model-based method [10,[13][14][15][16] and the optimization method considering testability constraints [17,18]. The former establishes a graph or mathematical model to describe the relationship between the sensors and failure modes, such as the dependency model, heuristic graph, and state diagram. Based on the models, the sensor selection results can be output through automatic traversal or matrix operation. The procedure of the later can be summarized in four steps: (1) determining an optimization goal (cost or time minimization); (2) defining testability indexes to describe testability requirement; (3) constructing the mathematical relationship between the goal and testability indexes; (4) using or designing an algorithm to solve the optimization problem under the constraints of the testability indexes. Usually, the testability indexes contain a fault detectable rate, a critical fault detectable failure rate, a fault isolation rate, and a fault prognostic rate [18][19][20]. The heuristic algorithm is commonly used to solve the optimization problem, such as particle swarm and genetic algorithm [20,21].
However, a common weakness of the existing methods is that these methods do not have a standard to select sensors, which leads to a hard choice, facing the different selection results given by these methods. In the model-based way, it cannot give a proper selection for the equivalent sensors, which have the same testing response. In the optimization way, the parameter setting of the heuristic algorithm has a vital effect on the optimization, resulting in an unstable selection result [22]. Meanwhile, the mathematical relationship is hard to be constructed because different types of parameters are difficult to be unified and processed. Therefore, it is necessary to form a principle to evaluate sensor selection of different methods, which helps to choose a better result by contrast and even adjust sensors based on the evaluation result to give a more convincing and reasonable result.
In this paper, we propose a comprehensive evaluation method of sensor selection for PHM based on grey clustering. This method is dedicated to evaluating the sensor selection according to its multiple relevant factors to give a more reasonable and convincing selection result. Sensor selection is a process full of uncertainty, and its result depends on expert advice, similar product experience, or measured data. For eliminating or reducing the uncertainty, the grey clustering is introduced and applied. Grey clustering is an important part of the grey theory, and it mainly studies the uncertainty of the system, which is suitable and active for evaluating sensor selection. Based on the method, the key factors are considered based on the previous studies, and they are quantized, manifested, and whitened, which can give a criterion for the evaluation of sensor selection. In the calculation process of grey clustering, the data in different types can be unified. The process also expands the range of evaluation indexes, which improves the comprehensiveness of evaluation result. Meanwhile, the weight in the grey clustering is extended to a combination weight considering subjective and objective factors, which is helpful to give a more valid result.
The workflow of the proposed method is shown in Figure 1. Firstly, we divide the sensors (clustering object) into three grey classes: extraordinary, good, and normal, which learns from the state division of equipment [23]. Based on the previous work on sensor selection, we determine three clustering indexes: the detection time, diagnosis expense, and importance value [15,18], which covers the factors related to sensor selection, and the indexes are quantified based on the dependency model. Then, we determine the whitening weight function to define the extent to which the clustering index belongs to a grey class, and propose a new and reasonable combination weight of the index to grey class considering the objective data and subjective factors. Finally, we obtain the sensor evaluation result by analyzing the clustering coefficients, which is calculated by the whitening weight function and the combination weight. To improve the selection result, we evaluate the selection result given by the dependency model and genetic algorithm (GA) because the two methods are commonly utilized in sensor selection. The evaluation principle is the proportion of good and extraordinary sensors. An electronic control system is taken as an example to illustrate the effectiveness of the proposed method.  The rest of this paper is organized as follows. Section 2 gives the grey clustering model of sensors evaluation. Section 3 describes an example in which the proposed method is applied. Finally, conclusions are drawn in Section 4.

The Grey Clustering Model for Sensor Evaluation
Grey clustering is widely utilized in system analysis and assessment, and it is very good at processing multi-type parameters, which is suitable for the evaluation of sensor selection. The purpose of the proposed method is to attribute the clustering object to a grey class [24,25].
In the evaluation method based on grey clustering, there are n clustering objects and m clustering indexes. We define the sensors

Clustering Index
It is essential to identify a fault in the design accurately and in a timely fashion for the testability of equipment [26], so the detection time and the failure rate is worth considering as the clustering indexes. Based on the previous analysis, the cost is usually taken as the objective function in the optimization method. Therefore, we define the detection time, diagnosis expense, and importance value as the clustering indexes, which is extensive and comprehensive. The detection time is used to measure the timeliness of a sensor, diagnosis expense is to measure the economic attribute, and the importance value is to describe the degree of failure mode detection by a sensor. These three indexes are defined and quantified as follows.

Detection Time
We define the maximum value of the time that a sensor spends on the different detectable failure modes as the detection time using the following equation: where ij t  is the detection time that the ith sensor spends on the jth failure mode. The rest of this paper is organized as follows. Section 2 gives the grey clustering model of sensors evaluation. Section 3 describes an example in which the proposed method is applied. Finally, conclusions are drawn in Section 4.

The Grey Clustering Model for Sensor Evaluation
Grey clustering is widely utilized in system analysis and assessment, and it is very good at processing multi-type parameters, which is suitable for the evaluation of sensor selection. The purpose of the proposed method is to attribute the clustering object to a grey class [24,25].
In the evaluation method based on grey clustering, there are n clustering objects and m clustering indexes. We define the sensors SO = {so 1 , so 2 , . . . , so n } as the clustering object, and define three grey classes: extraordinary (E), good (G), and normal (N). The grey classes are denoted as s = {s 1 = E, s 2 = G, s 3 = N}. The clustering indexes are the key factors to evaluate the clustering objects, and they are denoted as c = {c 1 , c 2 , . . . , c m }.

Clustering Index
It is essential to identify a fault in the design accurately and in a timely fashion for the testability of equipment [26], so the detection time and the failure rate is worth considering as the clustering indexes. Based on the previous analysis, the cost is usually taken as the objective function in the optimization method. Therefore, we define the detection time, diagnosis expense, and importance value as the clustering indexes, which is extensive and comprehensive. The detection time is used to measure the timeliness of a sensor, diagnosis expense is to measure the economic attribute, and the importance value is to describe the degree of failure mode detection by a sensor. These three indexes are defined and quantified as follows.

Detection Time
We define the maximum value of the time that a sensor spends on the different detectable failure modes as the detection time using the following equation: where ∆t ij is the detection time that the ith sensor spends on the jth failure mode. We define the average expense that a test spends on the detectable failure modes as the diagnosis expense. To quantify the diagnosis expense, we introduce the dependency matrix from the dependency model. The dependency matrix describes the relationship between the sensors (SO) and failure modes (F), and it is expressed as follows: where d ij = 1 if the ith sensor can detect the jth failure mode, or d ij = 0.
Based on the dependency matrix, the diagnosis expense of a sensor is as follows: where e ij is the expense that the ith sensor spends on jth detectable failure mode detection, and l is the number of detectable failure modes.

Importance Value
We define the failure rates' sum of the failure modes that a sensor can detect as the importance value. Based on the dependency matrix, the importance value is as follows: where λ i is the failure rate of the ith failure mode. After determining the indexes, we can obtain the observation matrix of the clustering object to indexes, which can be expressed as follows:

Whitening Weight Function
The whitening weight function is utilized to describe the extent to which the clustering index belongs to a grey class. The whitening weight function of the jth index belonging to the kth grey class is denoted as f k j (x ij ). A typical whitening weight function is shown in Figure 2. In Figure 2 are the turning points. A whitening weight function can be represented using these points [27,28], and it is expressed using the following equation: A whitening weight function can be divided into three types, as shown in Figure 3. They are the trapezoid whitening function (type I and type II) and the triangle whitening weight function (type III).

Whitening Weight Function
The whitening weight function is utilized to describe the extent to which the clustering index belongs to a grey class. The whitening weight function of the jth index belonging to the kth grey class is denoted as ( ) k j ij f x . A typical whitening weight function is shown in Figure 2. Figure 2. The typical whitening weight function. Figure 2. The typical whitening weight function.
Sensors 2020, 20, x 5 of 15 In Figure 2, are the turning points. A whitening weight function can be represented using these points [27,28], and it is expressed using the following equation: A whitening weight function can be divided into three types, as shown in Figure 3. They are the trapezoid whitening function (typeⅠand type Ⅱ) and the triangle whitening weight function (type Ⅲ ).
type Ⅲ ( Figure 3. The whitening weight function types.
It is obvious that the less detection time is helpful to improve the health assessment capability of a system, so we choose Type I as the whitening weight function of the detection time index belonging to E class. That means if the detection time of a sensor is too long, then the degree to which it belongs to E will decrease. If the value of the detection time continues to increase, its attribution will move away from E and towards G. That means the degree to which it belongs to E decreases and the degree to which it belongs to G increases. When its value is higher than a certain level, its attribution will move away from G and towards N. Therefore, we choose Type III as the whitening weight function of the index belonging to G class. Similarly, the whitening weight function's selection of other indexes to the grey class is shown in Table 1. Index S1 S2 S3 Detection time Type Ⅰ Type Ⅲ Type Ⅱ Diagnosis expense Type Ⅰ Type Ⅲ Type Ⅱ Importance value Type Ⅱ Type Ⅲ Type Ⅰ

Combination Weight
The weight  in grey clustering is utilized to calculate the clustering coefficient, and it represents the weight of the index to grey classes. The weight has a direct effect on the clustering result. The methods for weight determination contain the subjective and objective approach, and both of them have its advantages. However, the subjective method depends on the expert experience, and the data size has a direct effect on the objective method. The results given by the subjective and objective approach sometimes are different, and then both of them bring uncertainty to clustering analysis. Therefore, we propose a combination value integrating the advantages of the objective and subjective methods, which can give a more convincing and comprehensive weight. The combination weight includes the objective weight and subjective weight. The subjective weight s  is determined by the analytic hierarchy process (AHP), and the objective weight o  is determined by information entropy theory (IE). AHP is a commonly utilized subjective method, and IE is a dimensionless method, which can improve the comprehensiveness of weights. To synthesize the subjective and objective factors, we use a typical normalization method to process the product of the weights, and it can be expressed as follows: It is obvious that the less detection time is helpful to improve the health assessment capability of a system, so we choose Type I as the whitening weight function of the detection time index belonging to E class. That means if the detection time of a sensor is too long, then the degree to which it belongs to E will decrease. If the value of the detection time continues to increase, its attribution will move away from E and towards G. That means the degree to which it belongs to E decreases and the degree to which it belongs to G increases. When its value is higher than a certain level, its attribution will move away from G and towards N. Therefore, we choose Type III as the whitening weight function of the index belonging to G class. Similarly, the whitening weight function's selection of other indexes to the grey class is shown in Table 1.

Combination Weight
The weight η in grey clustering is utilized to calculate the clustering coefficient, and it represents the weight of the index to grey classes. The weight has a direct effect on the clustering result. The methods for weight determination contain the subjective and objective approach, and both of them have its advantages. However, the subjective method depends on the expert experience, and the data size has a direct effect on the objective method. The results given by the subjective and objective approach sometimes are different, and then both of them bring uncertainty to clustering analysis. Therefore, we propose a combination value integrating the advantages of the objective and subjective methods, which can give a more convincing and comprehensive weight. The combination weight includes the objective weight and subjective weight. The subjective weight η s is determined by the analytic hierarchy process (AHP), and the objective weight η o is determined by information entropy theory (IE). AHP is a commonly utilized subjective method, and IE is a dimensionless method, which can improve the comprehensiveness of weights. To synthesize the subjective and objective Sensors 2020, 20, 1710 6 of 14 factors, we use a typical normalization method to process the product of the weights, and it can be expressed as follows: The objective weight η o is obtained by the observation matrix of the clustering object to the indexes, and the matrix is as follows: Then, we calculate the objective weight as follows [29]: We can obtain the subjective weight η s by a judgment matrix, and the matrix is as follows: a 12 , . . . , a 1m  a 21 , a 22 , . . . , a 2m . . . a m1 , a m2 , . . . , a mm where a ij is determined as shown in Table 2. Based on the judgment matrix, we can calculate the subjective weight as follows [30]: Sensors 2020, 20, 1710 7 of 14

Clustering Coefficient and Clustering Result
For every clustering object, the clustering coefficient σ k i is utilized to measure the degree of the ith object belonging to the kth grey class, and it is as follows: For the entire clustering objects, we can obtain a coefficient matrix, which can be expressed as follows: In the matrix, every row is a coefficient vector. The grey class with the maximum coefficient in every vector is judged as the class of its corresponding object.

Case Study
To illustrate the effectiveness of the proposed method, we take an electronic control system as an example. The system is the control part of a radar prototype, and it is designed to demonstrate the target tracking characteristics. The composition of the radar prototype is shown in Figure 4.

Clustering Coefficient and Clustering Result
For every clustering object, the clustering coefficient k i  is utilized to measure the degree of the ith object belonging to the kth grey class, and it is as follows: For the entire clustering objects, we can obtain a coefficient matrix, which can be expressed as follows: In the matrix, every row is a coefficient vector. The grey class with the maximum coefficient in every vector is judged as the class of its corresponding object.

Case Study
To illustrate the effectiveness of the proposed method, we take an electronic control system as an example. The system is the control part of a radar prototype, and it is designed to demonstrate the target tracking characteristics. The composition of the radar prototype is shown in Figure 4. The target can be moved automatically on the sliding rail, and the radar receives and processes the signal to control the trace motion. The controller of the radar is a piece of complicated electronic equipment, and it has a high requirement for PHM. The failure detection rate FD  is not less than 90%, the key failure mode FDkey  is 100%, and the failure isolation rate FI  is not less than 90% (ambiguity is less than 2). Based on the composition of the radar, we can obtain the dependency graphic model of the controller by the dependency model theory, which is shown in Figure 5. The The target can be moved automatically on the sliding rail, and the radar receives and processes the signal to control the trace motion. The controller of the radar is a piece of complicated electronic equipment, and it has a high requirement for PHM. The failure detection rate γ FD is not less than 90%, the key failure mode γ FDkey is 100%, and the failure isolation rate γ FI is not less than 90% (ambiguity is less than 2). Based on the composition of the radar, we can obtain the dependency graphic model of the controller by the dependency model theory, which is shown in Figure 5. The dependency graphic model is used to illustrates the relationship between the failures and sensors. In the graphic model, the fault information flows with the arrows.  In Figure 5, F represents the failure mode, and SO represents the alternative sensors (voltage sensor and signal sampler). The concrete information about the failure modes and sensors is shown in Table 3. Based on the graphic model, we obtain the dependency matrix, and it is shown in Table 4.
We obtain the detection time by circuit simulation. From the price list of the bill of material (BOM), we obtain the diagnosis expense, which is the cost of the replacement of the faulty part detected by the sensor. From the reliability prediction results based on the standards (MIL-HDBK- In Figure 5, F represents the failure mode, and SO represents the alternative sensors (voltage sensor and signal sampler). The concrete information about the failure modes and sensors is shown in Table 3. Based on the graphic model, we obtain the dependency matrix, and it is shown in Table 4.
We obtain the detection time by circuit simulation. From the price list of the bill of material (BOM), we obtain the diagnosis expense, which is the cost of the replacement of the faulty part detected by the sensor. From the reliability prediction results based on the standards (MIL-HDBK-217F in U.S.A or GJB299C in China), we obtain the failure rates. The information is shown in Table 5, Table 6, and Table 7.   From the basic information above, we obtain the observation matrix X of clustering object to the clustering index. For eliminating the effect of the index dimensions, the matrix is equalized and denoted as X * .
Then, we determine the whitening weight function, and we take the function f 1 1 as an example to illustrate the process. The function f 1 1 describes the relationship between detection time and the extraordinary class (E). Obviously, the sensors tend to the extraordinary class, as the value decreases. Therefore, we choose the type I function as the type of the detection time. The determination of the turning points mainly relies on historical data and subjective adjustments. In the historical records of testing and maintenance, there are many effect evaluations (very good, good, and normal) for every testing and maintenance activity of the operators. Based on the records, we count the range of the detection time on different evaluation levels, and then we slightly adjust the range by experience. The purpose of the adjustment is to make the different whitening functions of the index intersect because the attribution of the index is a continuous transition state, not a hard separation. The adjustment range is usually no more than 0.1 by experience. Thus, we finally obtain the turning points and the whitening weight function. Similarly, other function results are determined, as shown in Table 8.
In the following equation, we obtain the subjective weight η s by subjective assessment. The judgment matrix is as follows: Based on the previous mathematical analysis, we obtain the objective weight η o from Equations (8) and (9), and the subjective weight η s from Equations (10) and (11). Thus, we obtain the combination weight η using subjective and objective weight from Equation (7) Finally, we obtain the coefficient matrix from Equations (12) and (13), and the matrix is as follows: From the coefficient matrix, we obtain the clustering result, and it is shown in Table 9. It is seen that SO 7 and SO 8 are attributed to the extraordinary class, SO 4 and SO 6 are attributed to normal class, and the rests are attributed to the good class. Thus, we can evaluate not only the sensor selection based on the results, but also every single sensor. Table 8. Whitening weight function. Table 9. Clustering result.

Sensor
Grey Class To evaluate the different selection methods, we choose the dependency model and GA as the evaluated subject. We construct the dependency model of the controller by a software (Testability modeling and analysis system, TMAS), and the model is shown in Figure 6. SO 7 S1 E SO 8 S1 E To evaluate the different selection methods, we choose the dependency model and GA as the evaluated subject. We construct the dependency model of the controller by a software (Testability modeling and analysis system, TMAS), and the model is shown in Figure 6. Then, we use the GA to achieve sensor selection, and the GA is commonly utilized and a typical one in the optimization method. Firstly, we construct the optimization problem, which is as follows: By the software analyzing, we obtain the sensor selection result SO = {SO 1 , SO 5 (SO 6 ), SO 7 , SO 8 }, and SO 5 and SO 6 are the equivalent sensors.
Then, we use the GA to achieve sensor selection, and the GA is commonly utilized and a typical one in the optimization method. Firstly, we construct the optimization problem, which is as follows: where e j is the expense of the jth sensor, FDR is the required value of thefailure detection rate, and FIR is the required value of tfailure isolation rate.
γ FD is the failure mode rate that the chosen sensors can achieve, and it can be expressed as follows: where ch j=1 λ j is the failure rate sum of the failure modes that can be detected by the chosen sensors, and n i=1 λ i is the failure rate sum of all the failure modes. Therefore, γ FI has the similar expression, and it can be expressed as follows: where is j=1 λ j is the failure rate sum of the failure modes, which can be isolated by the detection.
Then, we use the GA to solve the optimization problem. The initial population size of the GA is determined as 30, the crossover probability is 0.8, the mutation probability is 0.02, and other parameters are set up by software (MATLAB) automatically. Finally, we obtain the selection result SO = {SO 1 , SO 4 , SO 5 , SO 7 }. The valuation principle is the proportion of good and extraordinary sensors. If the proportions of the good and extraordinary sensors (P 1 ) of different methods are the same, the proportions of extraordinary sensors (P 2 ) are compared. If the two kinds of proportions are the same, the different selection methods are defined as equivalent. It is seen that the selection result of the dependency model is better than the GA synthetically because P 1 and P 2 of the dependency model are more than the GA, and then the dependency model method is recommended.
The contrast result can be explained in two ways. From the perspective of the algorithm itself, the selection result given by the GA is under an expense constraint, and the constraint reduces the influence of other factors on sensors, resulting in an expense-oriented result. From the perspective of physical meaning, the result difference between the dependency model and the GA is that the former selects SO 8 and the later selects SO 4 . SO 8 samples the characteristic signal and SO 4 obtains the calculation validity test result. From Figure 4, it is seen that the calculation result directly affects the characteristic signal output, which means the characteristic signal output is in the later position in the control chain. Thus, the characteristic signal output can reflect more information. Therefore, the proposed method is effective and can give a comprehensive evaluation result.
Moreover, it is noted that SO 5 and SO 6 are the equivalent sensors for their same testing response because F 4 and F 5 form a closed loop. It can be seen from the dependency model and the dependency matrix as shown in Figure 7. Then, we use the GA to solve the optimization problem. The initial population size of the GA is determined as 30, the crossover probability is 0.8, the mutation probability is 0.02, and other parameters are set up by software (MATLAB) automatically. Finally, we obtain the selection result SO = {SO1, SO4, SO5, SO7}.
The valuation principle is the proportion of good and extraordinary sensors. If the proportions of the good and extraordinary sensors (P1) of different methods are the same, the proportions of extraordinary sensors (P2) are compared. If the two kinds of proportions are the same, the different selection methods are defined as equivalent. It is seen that the selection result of the dependency model is better than the GA synthetically because P1 and P2 of the dependency model are more than the GA, and then the dependency model method is recommended.
The contrast result can be explained in two ways. From the perspective of the algorithm itself, the selection result given by the GA is under an expense constraint, and the constraint reduces the influence of other factors on sensors, resulting in an expense-oriented result. From the perspective of physical meaning, the result difference between the dependency model and the GA is that the former selects SO8 and the later selects SO4. SO8 samples the characteristic signal and SO4 obtains the calculation validity test result. From Figure 4, it is seen that the calculation result directly affects the characteristic signal output, which means the characteristic signal output is in the later position in the control chain. Thus, the characteristic signal output can reflect more information. Therefore, the proposed method is effective and can give a comprehensive evaluation result.
Moreover, it is noted that SO5 and SO6 are the equivalent sensors for their same testing response because F4 and F5 form a closed loop. It can be seen from the dependency model and the dependency matrix as shown in Figure 7. In the dependency model theory, SO5 or SO6 will be chosen equivalently. However, we will choose SO5 instead of SO6 for the evaluation of SO5 (G class) as it is better than SO6 (N class) (see Table  9). From the perspective of physical meaning, it is reasonable because SO5, the signal sampler, can obtain more useful information and is more sensitive than SO6, which is the voltage sensor to monitor In the dependency model theory, SO 5 or SO 6 will be chosen equivalently. However, we will choose SO 5 instead of SO 6 for the evaluation of SO 5 (G class) as it is better than SO 6 (N class) (see Table 9). From the perspective of physical meaning, it is reasonable because SO 5 , the signal sampler, can obtain more useful information and is more sensitive than SO 6 , which is the voltage sensor to monitor the actuator range. Then, the final selection result is SO = {SO 1 , SO 5 , SO 7 , SO 8 }. Therefore, we can improve the selection result to make a more precise choice by adjusting sensors based on the proposed method, which is more convincing and reasonable.

Conclusions
Sensor selection is a process full of uncertainty, and the selection result usually depends on the expert advice, algorithms, the measured data, and other factors, which brings difficulties to sensor selection and layout. For eliminating or reducing uncertainty, a comprehensive evaluation approach of sensor selection based on grey clustering is proposed. We divide the sensors into three grey classes: extraordinary, good, and normal, and propose three clustering indexes and the combination weight. The indexes are quantified based on a dependency matrix, and the combination weight is determined by considering objective and subjective factors. Based on the proposed method, the key indexes are fully considered, and the different dimensional data is unified, which significantly reduces the uncertainty of sensor selection and gives a standard to evaluate the selection results. An electronic control system of a radar prototype is taken as an example. We use the proposed method to evaluate the effectiveness of different methods of sensor selection, and the evaluation contrast between the dependency model and GA shows that the dependency model gives a better selection result. The evaluation result can be explained from the perspective of an algorithm and physical meaning, which proves the reasoning and effectiveness of the proposed method. Meanwhile, the proposed method is also helpful in improving the selection result by adjusting sensors, which is more reasonable and convincing. Besides that, the proposed method offers the following advantages: (1) This method is good at processing data with different dimensions and is helpful for multidimensional information fusion. (2) This method is simple and easily operated. (3) This method can give a more precise and useful result based on the accurate evaluation of every single sensor. (4) This method is more convincing when one considers objective data and subjective tendency. Therefore, the proposed method can be widely utilized in sensor selection and evaluation for prognostics and health management and be beneficial to the setting and layout of sensors.


s2fieldsofstudy:
Computer Science
Mathematics

text:
DynUnlock: Unlocking Scan Chains Obfuscated using Dynamic Keys

Outsourcing in semiconductor industry opened up venues for faster and cost-effective chip manufacturing. However, this also introduced untrusted entities with malicious intent, to steal intellectual property (IP), overproduce the circuits, insert hardware Trojans, or counterfeit the chips. Recently, a defense is proposed to obfuscate the scan access based on a dynamic key that is initially generated from a secret key but changes in every clock cycle. This defense can be considered as the most rigorous defense among all the scan locking techniques. In this paper, we propose an attack that remodels this defense into one that can be broken by the SAT attack, while we also note that our attack can be adjusted to break other less rigorous (key that is updated less frequently) scan locking techniques as well.

I. INTRODUCTION
Many threats have risen as a result of outsourcing in the IC supply chain. Untrusted entities such as foundry and end-user can use tools at their disposal, to steal intellectual property (IP) by reverse engineering, insert hardware Trojans, counterfeit or overproduce the chip [1], [2], [3]. To thwart these attacks, logic locking is considered a viable design-for-trust solution. Earlier logic locking schemes were implemented with high output corruptibility in mind; with an incorrect key the chip should produce most erroneous results for the given input patterns [4], [5]. However, this property was exploited by boolean satisfiability based attack known as the SAT attack in retrieving the secret key of logic locking [6].
SAT attack identifies a distinguishing input pattern (DIP) which prunes the key search space; the attack continues till no such DIP is found and terminates with the correct key. High output corruptibility assists this attack as a larger portion of the key search space is pruned with each DIP. To thwart this attack scan obfuscation/encryption approaches [7], [8] were proposed which obfuscates the scan-in and scan-out data based on a key. As all the successful attacks, such as (App)SAT [9], [6], in logic locking literature relies on scan access, these defenses can be said to thwart logic locking attacks. However, they incur significant area and delay overheads, and mainly find applications in Crypto chips. To protect against IP piracy attacks, more general and scalable solutions are required.
Recently, XOR/MUX based scan obfuscation techniques have been proposed [10], [11], [12], [13] to obfuscate the scan data via XOR/MUX operations based on a secret key through key gates inserted between the scan flops. In [10], a static key is used to obfuscate the scan chain content during scan in and out of patterns, effectively hindering unauthorized scan access. However, this defense was also recently broken by ScanSAT attack [14]. In [11], scan-out ports are blocked whenever the chip is in functional mode or upon a mode switch between functional and test mode, thereby, thwarting SAT-based attacks. However, this defense was also broken recently by shift-and-leak attack [15]. Further, in [12], [13], a dynamic scan locking key is used to obfuscate the scan data; the keys are generated using a Linear Feedback Shift Register (LFSR) based on a secret seed. In [12], the key is updated upon scanning in and out a constant number (p) of patterns, while in [13], the key is updated in every clock cycle. The defense in [13] can be viewed as the most rigorous, and thus, the most secure, dynamic scan locking defense. Indeed, the defense in [12] was broken recently even for its most rigorous version where the key is updated for every pattern (p=1) [16]. Yet, the defense in [13] remains unbroken. The evolution of scan locking defenses and attacks, focusing on the most recent years, is shown in Table I, illustrating the attention this area has been attracting lately.
Contributions: In this paper, we propose a state-of-the-art attack which can break all dynamic scan locking defenses [12], [13]. We present our DynUnlock attack on the most rigorous case of dynamic locking [13] where the scan data gets obfuscated with a new key in every clock cycle. The contributions of this paper are as follows: • We propose DynUnlock that can break all scan locking defenses. • We demonstrate our attack on a small ISCAS-89 dynamically scan locked circuit in Section III-A and perform it on six ISCAS-89 [17] and four ITC-99 [18] benchmarks for 10 different LFSR seeds each. • We aim to recover the secret LFSR seed generating the dynamic keys. We recover the unique seed for 70% of the circuits, and for the remaining 30% we obtain at most 128 seed candidates out of 2 128 , which can be further refined very quickly via brute-force to recover the secret seed. • The execution times of attack are maximum for s38584, s38417, and s35932 benchmarks (< 7 minutes) as they have the maximum number of scan flops post-synthesis.
c 2020 IEEE. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record is published in Proc. Design, Automation and Test in Europe Conference (DATE), 2020.

II. BACKGROUND
SAT attack was a turning point for logic locking research; researchers have now started exploring approaches to thwart this fatal attack. Based on the observation that the success of SAT and other oracle-guided attacks relies on scan access, one promising approach is to obfuscate the scan data as it is delivered in and out of the scan chains.
The defense in [13] obfuscated the scan data dynamically by updating the key in every clock cycle (even within a pattern), resulting in the ultimate dynamic scan locking technique. In this paper, we propose an attack which will, break all versions of dynamic scan locking, including the most rigorous one [13]. We use [13] as a case study to showcase our attack methodology while we note that it is guaranteed to be successful on all other dynamic scan locking versions that are less rigorous than [13], where the key updates less frequently [12].

A. Case Study
Dynamic Encrypt Flip-Flop (EFF-Dyn) [13] combines scan locking approach from [10] and a PRNG, to introduce dynamicity in the defense. During functional mode or the capture operation in test mode (scan enable (SE) signal is low), the secret scan locking key that is stored in the Tamper-Proof Memory (TPM) controls the key gates. During testing, an externally provided test key is expected. When this test key matches the secret scan locking key, the key gates receive this correct key during the scan shift operations (SE signal is high) as well; in case of a mismatch, however, the PRNG that updates the key in every clock cycle controls the key gates dynamically. This is illustrated in Fig. 2.
With an incorrect scan locking key, the chip outputs will be highly corrupted. A testing facility, if trusted, can provide the scan locking secret key as the external test key to have this key (known to them) drive the key-gates during both shift and capture operations during test. Without the knowledge of this secret key, the access to the scan chains is locked based on a very dynamic scan locking key generated by the PRNG.
Security Properties. A dynamically obfuscated scan access is meant to prevent an attacker from applying the generated DIPs through the scan chains, as the PRNG would be updating the key in every clock cycle, thereby, providing resilience against the SAT attack. As a defense that thwarts both SAT and AppSAT attacks, EFF-Dyn seems to be a promising design IP protection technique.

III. PROPOSED ATTACK
In this section, we discuss an attack approach on dynamically locked scan chains with EFF-Dyn as a case study. In our attack, DynUnlock, we aim to recover the seed of the PRNG which produces the key sequence. With the secret seed known, an attacker can gain scan access without the knowledge of the scan locking secret key; an arbitrary test key can be used to leave the scan access control to the PRNG, which can be easily modeled by the attacker as long as its seed is known (see threat model below).
Threat Model. Consistent with the logic locking literature, we assume that the attacker can obtain the design netlist by reverse-engineering the GDSII files or a fabricated chip. This gives her access to all the structural information including the test authentication scheme, the location of key gates, and the PRNG structure and thus, its polynomial function. We also assume that the attacker has access to a working oracle (functional IC). Though she also has access to scan ports physically, the attacker needs to get past the scan obfuscation defense.

A. Attack Methodology
Flowchart. As discussed before, we aim to recover the PRNG or LFSR seed and not the secret key (SK) for this particular case. 1 But, the methodology can be extended to other dynamic scan locking techniques whose seed is the secret 1 Here we assume that the PRNG is designed using an LFSR. c 2020 IEEE. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record is published in Proc. Design, Automation and Test in Europe Conference (DATE), 2020.   Fig. 1 into a SAT attack compatible combinational circuit. s0, s1, and s2 are the seed bits. key [12]. We first start by reverse-engineering the LFSR circuit and obtaining the equations corresponding to each clock cycle. Next, we determine the location of key gates inserted between the scan flops and model this sequential logic circuit into a combinational circuit with scan flops replaced with inputs and outputs. As per the architecture, scan patterns are shifted in and out serially whereas key inputs are applied in parallel. Figure 3 explains the attack methodology in a flowchart.
Combinational Modeling. Consider scan locking on s208 ISCAS-89 benchmark shown in Fig. 1, where the key gates are inserted after 1 st , 2 nd , and 5 th scan flops. The scan-in patterns are denoted by a and scan-out patterns are denoted by b; a denotes the pattern delivered into an obfuscated scan chain and applied to the circuit, and b is the response of the circuit captured in the obfuscated scan chain. During shift operations where dynamic scan obfuscation is in place, a turns into a ; and post-capture, b turns into b, both due to scan obfuscation. Input: seed, a, b Output: a , b F F = number of scan flops in the circuit; seed = number of LFSR bits; cycles = number of LFSR rounds; k y = dynamic key for y th round; Algorithm 1 shows the construction of LFSR keys from a seed, and a relationship between aa and bb in terms of the dynamic key bits. The first for loop corresponds to the LFSR equations, the second for loop corresponds to the relation between aa , while the third for loop corresponds to the relation between bb . This completes our modeling step which results in a combinational locked circuit with seed bits acting as primary key inputs.
SAT attack. Once modeling is complete, the combinational locked circuit is fed to a SAT tool [6] as shown in Fig. 3, which provides a DIP and its corresponding output pattern. We modify the code-base to dump a conjunctive normal form (CNF) after each iteration, which may reveal some of the seed bits. Unlike [16], we can carry out our attack for just one capture cycle. To recover more bits, we restart the LFSR circuit and obtain a new DIP and its corresponding output pattern II: Results for scan locked circuits with 128-bit dynamic keys fed by an LFSR based on a secret seed. All ten benchmarks can be broken to obtain the complete 128-bit seed. For s5378, the attack recovers 16 seed candidates, whereas for s13207, it recovers 128 seed candidates, both of which can be easily brute forced to obtain the correct seed.  s5378  160  128  16  17  41  s13207  202  128  128  4  27  s15850  442  128  2  4  89  s38584  1,233  128  1  3  219  s38417  1,564  128  1  7  342  s35932  1,728  128  1  1  254  b20  429  128  1  1  63  b21  429  128  1  1  54  b22  611  128  1  1  99  b17  864  128  1  1  86 from the SAT tool, and recover more seed bits. We repeat the restart step until all the seed bits have been recovered, or the remaining seed bits can be brute-forced. Even if the number of remaining seed bits is large for brute force, we can obtain a combinational locked circuit for a new capture cycle and carry over the seed information recovered from previous capture cycles to either recover the entire seed or reduce the brute force effort. We, however, have not come across any benchmark, locked with a key of a practical size, where a second capture was required, as can be seen in Section IV.

IV. EXPERIMENTAL RESULTS
Setup. We conducted our DynUnlock attack on six ISCAS-89 [17] and four ITC-99 [18] benchmarks with dynamically locked scan chains with a 128-bit key. Synopsys Design Compiler was used to synthesize these benchmarks. All the experiments have been carried out on a 24-core Intel Xeon processor running at 3.33 GHz with 96 GB RAM.
Attack results. Our attack results are given in Table II which shows the number of seed candidates recovered, number of iterations required by the lingeling SAT solver, and the attack execution time. As we can see, DynUnlock successfully unlocks all the circuits by recovering the 128-bit seed. For benchmarks s5378, s13207, and s15850, the attack obtains more than one seed candidate, which highlights that with just one capture cycle, SAT tool was not able to resolve all the CNF equations. However, these seed candidates are very few in number which can be easily brute forced to obtain the correct seed. For the rest of the benchmarks, we directly obtain the correct seed. All these benchmarks are run for 10 different LFSR seeds, and the number of seed candidates, number of iterations, and the execution times are averaged over these 10 runs.
Attack scalability. In our attack, we include the LFSR structure in the combinational modeling. All the seed bits are correlated with other seed bits as shown in Fig. 4. Hence, the SAT attack sometimes resolves only these clauses and leaves with multiple values for the variables in these clauses, thereby, increasing the seed candidates. For larger circuits, we obtain only one seed candidate. Intuitively, in a larger circuit with a larger number of scan flops, attack success should be higher as the seed bits will repeat for a larger number of times. We confirm this intuition from the results in Table II. Furthermore, for larger circuits (s38584, s38417, and s35932), even if the key-size is 240 bits, we still recover one seed as shown in Table III, and upto key sizes of 368, we obtain at most 16 seed candidates, which can be easily brute forced to recover the correct seed. Thus, our attack is scalable with number of scan flops as well as with increasing key sizes.

V. DISCUSSION AND CONCLUSION
Among the scan locking solutions that follow the same threat model used in logic locking, the only defenses that our attack cannot circumvent are those that incorporate cryptographic functions [7], [8] or PUF structures [19] to generate dynamic keys. Our attack cannot model such modules into their combinational logic equivalent. While this is a limitation of our attack, we note that cryptographic functions incur significant area and power cost, limiting the use of such defenses to chips that have these blocks already.
In this paper, we present a novel attack which circumvents the most dynamic case of scan locking proposed in [13]. We model the sequential circuit into a locked combinational circuit on which the SAT attack [6] can be applied. We conducted experiments on large circuits in ISCAS-89 and ITC-99 benchmark suites and recovered the LFSR seed within seven minutes for all the benchmarks under consideration. We also evaluated the scalability of our attack with increasing key sizes and recovered the seed using at most 27 iterations and within 23 hours for all the 15 cases for key sizes as large as 368 bits. Our attack can break any version of dynamic scan locking. With our attack process, we will never run out of iterations, as the attack will always provide seed candidates, if not the correct unique seed. III: Results for s38584, s38417, and s35932 benchmarks locked using larger keys. We observe that even for a key size as large as