Research on SCADA system security reinforcement method based on distributed Pareto algorithm

Abstract

As the SCADA system develops continuously, the dissemination of malicious network behaviors has brought great risk to the normal operation of enterprises, meanwhile resulting in huge economic burden to personal work and life. Therefore, the security reinforcement strategy is crucial to the field of network security management and analysis of the SCADA system. Some researchers have started to investigate on how to minimize the cost of realizing the SCADA system reinforcement strategy. However, the SCADA system administrators are facing a very challenging problem, that’s the reinforcement budget is less than the minimal input of SCADA system security reinforcement. The core of this problem lies on how to choose a subset from massive security reinforcement strategies, so as to minimize the risks from not patching all essential security vulnerabilities within the budget. Based on a deep comparative analysis of existing multi-objective optimization technologies, this paper proposes a multi-objective optimization method based on system attack tree model, and uses Pareto algorithm to solve this problem. The experimental results demonstrate that the Pareto algorithm can effectively make the multi-objective decision in security reinforcement strategy, and can solve practical issues in actual SCADA system security reinforcement practice.

Keywords

Multi-objective optimization risk assessment SCADA Pareto Top-k

1. Introduction

At present, the network-based computer system has become an important component of any information technology infrastructure, and the interconnection between each system is beneficial to inter-organization information exchange, which reduces the waiting time of information transfer and promotes the total system throughput. Since the service capability of an organization increasingly depends on the network-based computing system, it has become an essential need to maintain the accessibility to system resources. Therefore, any network malfunction resulted from system vulnerability directly affects the management cost of an organization. On the contrary, the organization should consider not only using the advantage of network system but also the cost of managing this system.

As the effect analysis has become a key factor that an enterprise or an organization constantly inputs in network security field, their requirements can’t be truly satisfied by merely detecting whether a vulnerability exists or adopting security measures to modify, but it is required to further analyze and understand the destruction that a vulnerability may bring to the assets of an organization. Normally, a vulnerability is not used independently, but multiple vulnerability groups are used to control the same one system. Similarly, the security policy can cover and repair multiple vulnerabilities. Hence, regarding the security management effect, the researchers shall evaluate different scenarios resulting in the destruction of fixed assets, and then put forward an optimized security strategy set to protect such kind of assets.

In the research of network system security model research, the researchers have made in-depth study, proposed such models as attack graph and attack tree, found out the attack path through these models, and finally determined the attack scenarios that may lead to destruction. However, though it is effective to determine the possible attack paths, it still couldn’t solve the problems that system administrators are facing. Obviously, they pay more attention to how to protect network from being invaded and to the determination of optimal reinforcement set. Furthermore, due to the limitations of financial budget, the system administrators can’t deploy all possible reinforcement strategies, or even cover all system vulnerabilities. Thus, they have to balance between the cost of realizing the security reinforcement measures subset and the destruction that may arise from leaving vulnerabilities. Besides, they also want to determine an optimal steady scheme. The security reinforcement set has the following characteristic, i.e. even if some reinforcement measures of the set fail, the system is still not been invaded successfully.

We believe that the security reinforcement problem can be solved in a more systematic manner by using various optimization tools. Through constantly exploring optimization method at different hierarchies, the administrative staffs can make better decisions rather than merely accepting an existing optimization scheme. For this purpose, the main contributions of this paper is as below:

The paper improves and formalizes the definition of attack tree, which can encode different security strategies that result in controlled system;

The paper proposes a kind of model, which quantizes the attack leading to potential system destruction described by attack tree model. Meanwhile, it also quantizes the security measures cost paid to realize a security reinforcement strategy set;

The paper models the system administrator’s decision problem, and realizes three gradually refined optimization processes in the system’s attack tree model;

Finally, the proposed reinforcement method is discussed, especially the robust scheme generated in the optimization process. This process will help system administrator to determine the selected reinforcement scheme.

The reminder of the paper is organized as follows: Section 1 introduces the work related to security reinforcement optimization method; Section 2 briefs the background of multi-objective optimization; Section 3 proposes a simple network model used to construct attack scenarios; the attack tree model, cost model and their multi-objective optimization schemes will be elaborated in Sections 4 and 5. Section 6 will perform an experimental verification, and make a summary and prospect.

2. Related work

In the field of network security managment, there are many research achivements related is proposed. In Literature [1], Noel et al. used the dependency graph to compute the minimal reinforcement cost. According to the initial condition set in the graph structure, the Boolean values allocated to these conditions are calculated, and then some reinforcement strategies are used to strengthen them, so as to minimize the implementation cost of reinforcement strategies. The author points out that these initialization conditions rely on artificial accurate control. However, an attacker can use a different attack path to bypass the reinforcement measures of key assets. In Literature [2], Jha et al. don’t consider the cost of reinforcement measures, but find out the minimal atom attack set to achieve the coral assets, and finally search for the reinforcement measures on this minimal set. Above research aims to providing scheme for complete network security. Nevertheless, an enterprise always inputs limited fund, so the reinforcement strategy set still couldn’t fully cover the vulnerabilities. So the decision-makers should make a cost-benefit analysis to balance between the reinforcement cost and the coral network assets security. Moreover, a minimal-cost reinforcement measure set merely means that the coral assets are safe, but some residual destructions still exist in the network. On account of these real requirements needed to be attended, the network vulnerability management should not be simply interpreted as a single objective optimization problem. In Literature [3], the network vulnerability management has been formalized as a multi-objective optimization problem and officially put forward. Gupta et al. take the security strategy covering one or multiple common vulnerabilities as a set for consideration. A security strategy can also introduce possible vulnerabilities. Even if a security strategy is applied, there may be some residual vulnerabilities in the network as well. When considering to weight the residual vulnerabilities, multi-objective optimization problem can minimize the cost of realizing these security strategies. At last, the author adopts objective relative weight to combine two objectives into one.

3. Multi-objective optimization

In practical application scenarios, a problem is often formally described as multiple codes or design objectives, and the decision problem will be transfered to a problem for searching for optimal solution in multiple objectives, saying a multi-objective optimization problem, or called a vector optimization problem. Normally, considering from the cardinal number of scheme optimization set, a multi-objective optimization problem is different from a single-objective optimization problem. The ultimate goal of single-objective optimization is to find out a globally optimal solution, while the multi-objective optimization doesn’t have such concept. In the multi-objective optimization process, optimizing one objective may not affect other objectives as expect. Therefore, an optimization process taking all objectives into consideration doesn’t always exist. In such circumstances, it is required to use domain knowledge and make a decision from multiple trade-off analysis schemes, and this process often thinks more about realizing feasibility.

Because of the conflict feature of objective function, regarding the multi-objective optimization problem, a simple single-objective value can’t solve such problem. Thus, the majority of multi-objective optimization algorithms use the concept of “control” to compare feasibility schemes.

Definition 1: Pareto optimal set.

Regarding a given K-dimensional object set S, for feasible schemes $\vec{x}$ and $\vec{y}$ , if they satisfy the following conditions:

$\forall i\in\left\{{1,2,\ldots,K}\right\},f_{i}(\vec{x})\leqslant f_{i}(\vec{y})$ ;

$\forall j\in\left\{{1,2,\ldots,K}\right\},f_{j}(\vec{x})<f_{j}(\vec{y})$ .

that’s to say, the eigenvalues of scheme $\vec{x}$ at all dimensions are no worse than those of scheme $\vec{y}$ , and at least at one dimension, its eigenvalue is superior to that of scheme $\vec{y}$ , then it is called that the scheme $\vec{x}$ leads (controls over) the scheme $\vec{y}$ . If above condition is not satisfied, it indicates that there is no control relationship between $\vec{x}$ and $\vec{y}$ . In the set S, all schemes without control relationship or parallelism are called the Pareto optimal set. In the target space, the optimal plane generated by Pareto optimization scheme is also called the Pareto-front or Pareto-surface, and the query process is called the Pareto query.

With regard to the network security optimization problem, particularly the problem of minimizing security reinforcement cost and network destruction in this paper, the concept of “control” plays a critical role in scheme assessment. A scheme may reduce an objective but promote another objective. A “control” based comparison could balance these two objectives to obtain a global optimal scheme. Next, let us see a typical case of network security optimization – the selection of security reinforcement scheme. Assume a network administrator of an enterprise plans to protect the enterprise intranet, and would like to find out a scheme with low reinforcement cost and minimal network risk left. In Fig. 1, every dot represents a reinforcement scheme, axis X denotes to the cost of reinforcement scheme, and axis Y denotes to the leaving risks (vulnerabilities) after adopting such reinforcement scheme. It can be seen that, the administrator only has to consider those red dots (reinforcement scheme) in the figure. Those non-red dots (reinforcement scheme) are not necessary to consider, because there is always a red dot (reinforcement scheme) with smaller reinforcement cost or less leaving risks. At this time, we can say that the red dots control all other black dots, while there is no control relationship between red dots. All red dots constitute the Pareto optimal set.

Figure 1.

Pareto optimal set for safety reinforcement.

The study of Pareto query can be traced up to the year of 1975 at the earliest, when Kung et al. raised in Literature [4] the 2-dimensional and 3-dimensional data algorithm. The time complexity of this algorithm is $O\left({n\log_{2}^{n}}\right)$ , and the time complexity of the algorithm proposed for above 3-dimensional data is $O\left({n(\log_{2}^{n})^{d-2}}\right)$ . In Literature [5], Balke et al. classified Pareto query into multi-objective optimization problem. Afterwards, the researchers divided Pareto algorithm into internal storage algorithm and external storage auxiliary algorithm according to the scale of query dataset. Regarding the internal storage algorithm, Bentley et al. supposed that data were distributed independently at all dimensions and put forward a query algorithm with linear time complexity. All research of internal storage algorithm are on the premise that the assumed solution dataset is small enough to be saved in the internal storage. But in practical application, large datasets widely exist, and the methods that researchers use to handle such problems [6] can be divided into non-index algorithm [7, 8, 9, 10] and index algorithm [7, 11, 12, 13, 14, 15]. Regarding non-index algorithm, in Literature [7], Borzsonyi raised four algorithms: BNL, D&C, Using B-trees, and Using an R-tree algorithms. Among them, both the BNL algorithm and D&C algorithm are non-index algorithms, and the Using B-trees and Using an R-treealgorithms are two index algorithms. The BNL algorithm can be universally applied but dissatisfy the gradualness, which may result in misjudgment. The D&C algorithm only applies to small datasets. When the dataset is large and exceeds the memory, the I/O cost will be huge in the partition process which dissatisfies gradualness and may bring about misjudgment. In Literature [8], Chomicki et al. proposed the SFS classical algorithm, which can guarantee effective pruning by preprocessing, accelerate the calculation process, and ensure the output of flow line mode. In Literature [11], Tan et al. proposed the Bitmap algorithm and Index algorithm for the index and non-index schemes, respectively. The Bitmap algorithm can generate Bitmap by preprocessing, which is featured by short response time and gradual generation, but this algorithm is not applicable to dynamic database and distinct query conditions. In Literature [10], Godfrey et al. integrated with the BNL algorithm [7] and SFS algorithm [8] to raise an improved algorithm of SFS, that’s LESS. Its average time complexity is $O(kn)$ , optimal time complexity is $O(kn)$ , and the worst time complexity is $O(kn^{2})$ . Regarding the index algorithms, in Literature [7], Borzsonyi put forward the Using B-trees algorithm and Using an R-tree algorithm, used for 2-dimensional and above 2-dimensional space respectively. Neither of these two algorithms has universality, and they all need a preprocessing process to generate indexes. In Literature [9], the author established an index through preprocessing, which algorithm had the merit of fast response time and satisfying gradualness, but it is not applicable to subspace query with different query conditions and dimensions. In Literature [12], aiming at dynamic database, different query conditions and gradualness, Kossmann et al. raised an NN algorithm, which had evident shortcomings: low algorithmic performance, and higher spatial complexity for above 3-dimensional data. In Literature [13], Papadias et al. brought forward the BBS algorithm, which has obvious advantages: satisfying gradualness, applicable to subspace query with dynamic database, different query conditions and different dimensions, and higher I/O performance, but it is merely suitable for feature domain total order condition. In Literature [14], Yang et al. raised a transfer holding Pareto algorithm suitable for partial order domain, which can retain the optimal point and meanwhile clipping bid dataset into a reasonable scale for calculation. In Literature [15], Yang et al. put forward a novel index algorithm – LMB algorithm, and utilized this algorithm to achieve multi-dimensional recommendation application. In Literature [16], Chan et al. raised the BBS ${}^{+}$ , SDC and SDC ${}^{+}$ algorithms. Among them, BBS ${}^{+}$ is the improvement of BBS algorithm, which is more suitable for feature domain with partial order, but it dissatisfies gradualness and may leads to misjudgment. While both SDC and SDC ${}^{+}$ algorithms can be applied to feature domain with partial order, with good gradualness and fast response.

4. Simple network model

In order to validate the validity of the method proposed, a network scenario as shown in Fig. 2 is considered. The network includes 4 host computers, and the firewall is configured as preset strategy, to ensure that FTP server and SMTP server are allowed to link with external network. In addition, FTP and SSH are two services only allowing external users to access to internal server. Suppose that an external user wants to endanger a server within the protection range of firewall, and the firewall has been preset with strong rule set to protect the safety of internal host computer. In Fig. 2, according to the vulnerabilities listed in Table 1 and the network topography provided in Table 2, there may be six different attack scenarios to obtain the ultimate objective.

Table 1
Host initialization vulnerabilities in network models

Host	Vulnerability	CVE#
FTP Server 196.216.0.10	Ftp .rhost attack Ftp Buffer overflow Ssh Buffer oveflow	1999–0547 2001–0755 2006–2421
SMTP Server 196.216.0.1	Ftp .rhost attack	1999–0547
Terminal 196.216.0.3	LICQ remote-2-user “at” heap corruption	2001–0439 2002–0004
Data Server 196.216.0.2	LICQ remote-2-user suid Buffer oveflow	2001–0439 2001–1180

Table 2

Connections between hosts in a network model

Host	Host	Port
...	196.216.0.1	21,25
...	196.216.0.10	21,22
196.216.0.1	196.216.0.2	ANY
196.216.0.1	196.216.0.3	ANY
196.216.0.3	196.216.0.2	ANY
196.216.0.10	196.216.0.2	ANY

Figure 2.

Network model example.

To control data server, the attacker used ftp/.rhost to attack and infiltrate FTP server and SMTP server. The ftp service version that these two servers were running had vulnerabilities that may be used. Furthermore, the rhost catalogue of this server didn’t correctly perform write-protection. The results of ftp/.rhost being utilized is a credible relationship established between victim host and attacker and the import of a vulnerability that can bypass authorization. After that, the attacker made use of user access right to login in these two servers. From this point, the attacker can use the connections between data server and FTP and SMTP servers, to further control data server. Likewise, the attacker could also choose controlling the terminal host to delay an attack. The terminal host can be controlled by the following method: “LICQ remote to user” and “local buffer overflow” vulnerabilities. At the end, through the two vulnerabilities, the attacker can not only select FTP and SMTP servers, but also select the connections between terminal host and data server to further control data server. Above depicted attack scenario can be represented by attack tree and will be detailed in the next section.

5. Attack tree model

Due to the structure complexity of SCADA system, making a successful network attack offen needs to exploit multiple vulnerbilites and to combine multiple attacks to reach the goal of attacker. Therefore, in terms of attack prevention, it is very important to express the scenarios that different assets are attacked. The expression of attack scenarios could not only describe the possible way of controlling a system, but also help the administrator to determine a minimal attack prevention behavior set. According to the normal operation state of a network and its vulnerability presence circumstance, an attacker is able to easily use vulnerability to initiate an attack, and further approaches to the target he/she would like to control. The exact status of a network, especially the access right and network topology are the prerequisite that an attacker can make use of vulnerabilities. Once a vulnerability is used successfully by an attacker, the network status will be tampered so that he/she can continue to initiate the next attack. A pre-considered attack order may form an attack scenario. It is worth noting that such a progressive attack could trigger the transfer relationship between vulnerabilities in a network, which can be used to determine the network security scheme. In network vulnerability management, the attack graphs [1, 3, 17, 18] and attack trees [19, 20, 21] have already been proposed to express the causal relationship between vulnerabilities. In these data structures, the node represents a certain network status that the attacker is interested in, and the side represents the causal relationship of these statuses. In an attack graph, though different attack scenarios can be easily perceived, they are facing the status space explosion problem. In Literature [7], Ammann et al. became aware of this problem and raised an alternative solution based on the monotonicity hypothesis. This monotonicity characteristic indicates that a successful attack results can be acquired, and this hypothesis can greatly reduce the number of nodes in attack graph, but lose the possibility of further analyzing feasible attack scenarios. In accordance with the structure of attack graph or attack tree, the vulnerability dependency graph can be extracted to represent the connection and non-connection relationship between nodes. In this paper, the attack tree structure is used to represent the relationship between vulnerabilities. Such expression can use the different hierarchies of tree structure to represent the relationship between attacker’s sub-goals. One attack tree is capable of using explicit branches to decompose the subsequent connections and separation so as to reduce the visual complexity of an operation sequence. This expression mode is also helpful in effective calculation of the cost factor of points of interest.

For an attacker, different network features will let him/her to use different modes to control the system. First, to further analyze, the paper defines a feature template to uniformly classify these network features.

Definition 2: Feature Template.

A feature template is a feature set of hardware and software configurations included in a network structure, as below (not limited to these):

System vulnerability. This vulnerability is normally reported by vulnerability database such as BugTraq, CERT/CC or NetCat, etc.;

Network configuration, such as open port, unsafe firewall configuration, etc.;

System configuration, such as data access right, unsafe default setting, read-write right to key files, etc.;

Access configuration, such as user account, visitor account, root account, etc.;

Networking topology.

A feature template can be used to classify the most atom features of network, and those atom features are always used by the attacker. For example, FTP server runs SSH1 with a version of v1.2.23, which can be taken as an instance of system vulnerability template. Likewise, an user uses terminal to access which can be taken as an access right template. In propositional logic, a template is allowed to self-define the feature, definition is as below:

Definition 3: Features.

A feature is the propositional case of a feature template, with its value to be true or false.

Whether an attacker can achieve his/her goal depends on that the eigenvalue of feature template in the network is true or not. This mainly relies on the feature modified by network administrator according to security strategies. Based on these features, the paper formally defines an attack model. Since the paper takes the atom feature of a network as a feature and defines its value as true or false, so all definitions related to these features can be expressed by propositional logic.

Definition 4: Attack.

Let S be a feature set, and define Att as a mapping, $\textit{Att:S}\times S\to\left\{{\textit{true,false}}\right\}$ . Meanwhile, the value of $s_{p}$ is $\textit{Att}\left({s_{c},s_{p}}\right)=\textit{true}$ .

If it satisfies $s_{c}\neq s_{p}\wedge\alpha\equiv s_{c}\leftrightarrow s_{p}$ , then $\alpha=\textit{Att}\left({s_{c},s_{p}}\right)$ can be considered as an attack. In which, $s_{c}$ is called the precondition of attacking $\alpha$ , $s_{p}$ is the post-condition of attacking $\alpha$ , which are expressed by $\textit{pre}\left(\alpha\right)$ and $\textit{post}\left(\alpha\right)$ , respectively. If a non-empty set $S^{\prime}$ exists, it satisfies $S^{\prime}\subset S\left|{\left[{s_{c}\neq s_{p}\wedge\textit{Att}\left({s_{c}% ,s_{p}}\right)\equiv\wedge s_{i}\wedge s_{c}\leftrightarrow s_{p}}\right]}\right.$ , $S_{i}\in S^{\prime}$ .

The attack relative to the true values of $s_{c}$ and $s_{p}$ with different features may often form the causal relationship of the two. For example, for the feature $s_{c}=\text{``vulnerable to sshd BOF on machine A''}$ and $s_{p}=\text{``root access privilege on machine A''}$ , then $\textit{Att}\left({s_{c},s_{p}}\right)$ is an attack, that’s sshd buffer overflow attack. It is needed to clarify that the two-way conditional logical connector “ $\leftrightarrow$ ” of $s_{c}$ and $s_{p}$ doesn’t mean that only using $\textit{Att}\left({s_{c},s_{p}}\right)$ could set $s_{p}$ as true, but that for an sshd BOF attack, the method of making $s_{p}$ as true is only by making $s_{c}$ as true. In practice, $\textit{Att}\left({\text{vulnerable to local BOF on setuid daemon on machine A% },s_{p}}\right)$ is also a potential attack. $\Phi$ -attack can be interpreted as that there is no direct relationship between the true values of features. However, a non-direct relationship can be jointly established. For example, the feature $s_{c1}=\text{``running SSH1 v1.2.25 on machine A''}$ and the feature $s_{c2}=\text{``connectivity}\left({\text{machine B, machine A}}\right)\!\text{% ''}$ can’t affect the true value of $s_{c}$ separately, but jointly make $s_{c}$ to be true, that’s to say $s_{c1}$ and $s_{c2}$ are true respectively. Thus, both $\textit{Att}\left({s_{c1},s_{c}}\right)$ and $\textit{Att}\left({s_{c2},s_{c}}\right)$ are $\Phi$ -attack.

Definition 5: Attack Tree.

Let A be the attack set, and include $\Phi$ -attack. An attack tree is a tuple $\textit{AT}=\left({s_{\textit{root}},S,\tau,\varepsilon}\right)$ , and can satisfy the following conditions:

$s_{\textit{root}}$ is a feature that attack tree becomes true;

$S=N_{\text{internal}}\cup N_{\text{external}}\cup\left\{{s_{\text{root}}}\right\}$ , is a multi-set of multiple feature sets. Among them, $N_{\text{external}}$ denotes to that the feature $s_{i}$ satisfies the multi-set of the condition $\Box\alpha\in A|s_{i}\in\textit{post}(\alpha)$ . $N_{\text{internal}}$ denotes to that the feature $s_{i}$ satisfies the multi-set of the condition $\exists\alpha_{1},\alpha_{2}\in A\left|{\left[{s_{j}\in\textit{pre}\left({% \alpha_{1}}\right)\wedge s_{j}\in\textit{post}\left({\alpha_{2}}\right)}\right% ]}\right.$ ;

$\tau\subseteq S\times S$ . In case that $\exists\alpha\in A\left|{\left[{s_{\textit{pre}}\in\textit{pre}\left(\alpha% \right)\wedge s_{\textit{post}}\in\textit{post}\left(\alpha\right)}\right]}\right.$ is satisfied, then an ordered pair $\left({s_{\textit{pre}},s_{\textit{post}}}\right)\in\tau$ . Furthermore, if $s_{i}\in S$ , for the diversity $n$ , $\exists s_{1},s_{2},\ldots,s_{n}\in S\left|{\left({s_{i},s_{1}}\right)}\right.% ,\left({s_{i},s_{2}}\right),\ldots,\left({s_{i},s_{n}}\right)\in\tau$ ;

In addition, for all $s_{j}\in N_{\text{internal}}\cup\left\{{s_{\textit{root}}}\right\}$ and $d_{j}\in\left\{\textit{AND,OR}\right\}$ , $\varepsilon$ is a decomposed tuple set of $\left\langle{s_{j},d_{j}}\right\rangle$ . When $\wedge_{i}\left[{s_{i}\wedge\left({s_{i},s_{j}}\right)\in\tau}\right]% \leftrightarrow s_{j}$ is true, $d_{j}$ will be “AND”. When $\vee_{i}\left[{s_{i}\wedge\left({s_{i},s_{j}}\right)\in\tau}\right]% \leftrightarrow s_{j}$ is true, $d_{j}$ will be “OR”.

Figure 2 shows an attack tree case, which $s_{\textit{root}}$ is the feature “root access on machine A”. The multi-set S constitutes the nodes of the tree. The multi-set $N_{\text{external}}$ determines the leaf nodes of attack tree. These nodes reflect the initial vulnerabilities that exist in the network and are easily used. Moreover, a feature maybe a preset condition that exceeds the attack, which can be used again and again to form a multi-set. In Fig. 2, the feature “machine B can connect to machine A” is exactly such a feature. The ordered pair set $\tau$ is the side of attack tree. If there is a side between the nodes of two attack trees, it indicates that there is direct or indirect relationship before the node attribute becomes true, and it also indicates the decomposition value at each node. Regarding the “AND” decomposition of a node, it is required that a node can be true only if all its children nodes are true. For the “OR” decomposition of a node, it is required that a node can be true only is at least one child node is true. After using these decomposition to distribute a true value set for the feature $s_{i}\in N_{\text{external}}$ , the true value of the feature $s_{j}\in N_{\text{internal}}\cup\left\{{s_{\textit{root}}}\right\}$ can be evaluated.

6. Cost model

To eliminate the effect of network attack, a network administrator must choose appropriate security reinforcement technology according to cost and coverage. For example, in order to prevent ftp/.rhost vulnerability being used, it is needful to consider using a security patch, closing FTP service, or simply adding write-protect to .rhost catalogue, and every selecting behavior means different costs. Besides, some methods have wider coverage but with larger cost. To maximize the resource use ratio, the security administrator has to make decision and selectively realize those security reinforcement subsets. However, considering n strategies, the decision always needs to be made from $2^{n}$ subsets, which still signifies a great difficulty in decision-making.

Security plan starts from risk assessment, while the objective of risk is threats determination, loss anticipation, potential precaution scheme and installation cost. In brief, an security administrator should analyze the relative loss degree and reinforcement cost through risk assessment [22]. Nevertheless, the relative cost assessment method can’t provide sufficient information for top-priority strategy, which is particularly serious when an organization or institution faces restricted resources. In this article, Butler’s [23] multi-feature risk assessment framework is introduced to quantify the risk assessment features for security optimization. The framework proposed by Butler can conduct aggregation expression of multiple factors of commercial models of the controlled enterprise, which facilitates to extract the safety assets information relative to critical businesses.

First, define the concept of security measures in attack tree.

Definition 6: Security Measures.

For an attack tree $\left({s_{\textit{root}},S,\tau,\varepsilon}\right)$ , if its satisfies $\exists s_{i}\in N_{\text{external}}\left|{\textit{SC}\left({s_{i}}\right)=% \textit{false}}\right.$ , then the mapping $\textit{SC}:N_{\text{external}}\to\left\{\textit{true,false}\right\}$ is a security measure.

In other words, the security measure is a precaution method used to prove that one or more features in the attack tree are false. And, under the condition of multiple security measure strategy $\textit{SC}_{k}$ , the true value of a feature $s_{i}\in N_{\text{external}}$ can be expressed as $\wedge_{k}\textit{SC}_{k}\left({s_{i}}\right)$ . Regarding a security measure SC, all sets of $s_{i}\in N_{\text{external}}\left|{\textit{SC}\left({s_{i}}\right)=\textit{% false}}\right.$ are called the coverage of control SC. Thereby, for a security measure set, every control coverage matrix has been defined. For a set covering m security measures, the Boolean vector $\vec{T}=\left({T_{1},T_{2},\ldots,T_{m}}\right)$ is used to denote whether a security measure has been selected by the security administrator. It is worth noting that the selection of vector $\vec{T}$ indirectly designates the feature with initial value as false in the attack tree.

6.1 Potential destruction assessment

A potential destruction $P_{j}$ represents the no-unit destruction value suffered by an organization when a feature $s_{j}$ in the attack tree is true. Based on Butler framework, this paper puts forward four steps to figure out the potential destruction value of the feature $s_{j}$ .

Confirm the consequence of feature true value induced by some attack trees. In the proposed case, we have confirmed five outputs, and the loss earnings (fund), non-productive halt (time), destruction restore (fund), public crisis (serious) and legal punishment (serious) are represented by $x_{1j}$ , $x_{2j}$ , $x_{3j}$ , $x_{4j}$ and $x_{5j}$ , respectively;

Evaluate the anticipated quantity $\textit{Freq}_{j}$ of attack occurred and the consequence. According to public historical attack data and the intra-organization historical data of being attacked, the security administrator is capable of assessing the anticipated attack quantity;

For each possible consequence, use a univalent function to evaluate, $V_{ij}\left({x_{ij}}\right)$ . This function aims to generalizing the assessment results of different units, so that it is feasible to use a single standard to perform summation. $V_{ij}\left({x_{ij}}\right)={x_{ij}}\mathord{\left/{\vphantom{{x_{ij}}{Max_{j}% x_{ij}*100}}}\right.\kern-1.2pt}{Max_{j}x_{ij}*100}$ , $1\leqslant i\leqslant 5$ ;

Allocate a preference weight factor $W_{i}$ for each possible consequence. The security administrator may allocate a ranking from 1 to 100 for each output, in which the most attended feature is ranked as 100, and other features are given a value in sequence. At last, the rankings will be generalized, set as $W_{i}$ .

Relying on the following formula, the potential destruction to a feature can be calculated:

$\displaystyle P_{j}=\textit{Freq}_{j}\times\sum\limits_{i=1}^{5}{W_{i}V_{ij}% \left({x_{ij}}\right)}$ (1)

When an attack tree is used, by considering the residual destruction after realizing the security strategy, we can obtain a better quantization expression. Hence, as the residual destruction in the subtree rooted as features increases, such features in the attack tree also increase.

Definition 7: Magnify Attack Tree.

Let $\textit{AT}=\left({s_{\textit{root}},S,\tau,\varepsilon}\right)$ be an attack tree. A magnified attack tree $AT_{\textit{aug}}=AT\left|{\left\langle{I,V}\right\rangle}\right.$ can be acquired by connecting every $s_{i}\in S$ with a tuple $\left\langle{I_{i},V_{i}}\right\rangle$ , in which,

$I_{i}$ is the index variable of the feature $s_{i}$ ,

$\displaystyle I_{i}=\left\{{\begin{array}[]{ll}0,&\textit{if}\ s_{i}\ \textit{% is false}\\ 1,&\textit{if}\ s_{i}\ \textit{is true}\\ \end{array}}\right.;$ (2)

$V_{i}$ is a value associated with the feature $s_{i}$ .

In the work of this paper, the feature $s_{i}$ of $s_{i}\in N_{\text{external}}$ is given a value of zero. For the value related to $s_{j}\in N_{\text{internal}}\cup\left\{{s_{\textit{root}}}\right\}$ , the following iterative calculation is carried out:

$\displaystyle V_{j}\left\{{\begin{array}[]{l}\mathop{\sum}\nolimits_{k\left|{% \left({s_{k},s_{j}}\right)\in\tau}\right.}V_{k}+I_{j}P_{j},\textit{if}\ d_{j}% \ \textit{is the AND}\\ \mathop{\max}\nolimits_{k\left|{\left({s_{k},s_{j}}\right)\in\tau}\right.}V_{k% }+I_{j}P_{j},\textit{if}\ d_{j}\ \textit{is the OR}\\ \end{array}}\right.$ (3)

In an ideal circumstance, in a multi-set, all same features have the same $P_{j}$ . Use “OR” to decompose a feature and obtain all subtrees rooted as such feature, figure out the value of every subtree, and then choose the maximal as the value of this feature. This is because an attacker’s capability and preference can’t be known in prior.

The residual destruction of a magnified attack tree is defined as below:

For an given magnified attack tree $\left({s_{\textit{root}},S,\tau,\varepsilon}\right)\left|{\left\langle{I,V}% \right\rangle}\right.$ and the vector $\vec{T}=\left({T_{i}}\right),T_{i}\in\left\{{0,1}\right\},1\leqslant i\leqslant m$ . Then, the residual destruction is defined as a value related to $s_{\textit{root}}$ , that’s $\textit{RD}(\vec{T})=V_{\textit{root}}$ .

6.2 Security cost assessment

Similar to potential destruction, the security administrator will firstly list a possible security cost required to realize a security measure, allocate its weight, and compute the generalized value. The sole difference between this calculation process and the residual destruction assessment is that the security cost assessment doesn’t need to anticipate the occurrence times. In our study, to realize a security measure, it is necessary to consider five different costs: installation cost (fund), operation cost (fund), system crash cost (time), incompatibility cost (range), and training cost (fund). For the security strategy $\textit{SC}_{j}$ , the total cost $C_{j}$ can be figured out in a manner similar to that of potential destruction, but the anticipated frequentness should be set as 1. Regarding a security measure implementation set, its total security cost is defined as follows:

Definition 8: Total Security Measure Cost.

In terms of a given set including m security measures, each measure has its own cost $C_{i}$ , the vector $\vec{T}=\left({T_{i}}\right)$ , $T_{i}\in\left\{{0,1}\right\}$ , then the total security measure cost is defined as:

$\displaystyle\textit{SCC}\left(\vec{T}\right)=\sum\limits_{i=1}^{m}{\left({T_{% i}C_{i}}\right)}$ (4)

7. Problem formalization

In the paper, for an attack tree exampled by the network model in Fig. 1, it needs to study the total security measure cost and residual destruction. As shown in Table 3, through placing patches and closing different services, 19 different security strategies are affirmed. After permutation and combination, there maybe more than 500,000 choices, and this requires to design valid algorithms to search for the optimal solution. In a real network environment, when there is a necessity to work out potential destruction and security measures, we should make clear of the relative priority between different services.

Table 3
Security measures for the network model in Fig. 1

Security control	Action
SC1/SC2	Disable/Patch suid @ 196.216.0.2
SC3/SC4	Disable/Patch LICQ @ 196.216.0.2
SC5	Disable $\backslash$ at" @ 196.216.0.3
SC6/SC7	Disable/Patch LICQ @ 196.216.0.3
SC8	Disable Rsh @ 196.216.0.1
SC9	Disable Ftp @ 196.216.0.1
SC ${}_{10}$	Disconnect Internet @ 196.216.0.1
SC11	Chmod home directory @ 196.216.0.1
SC12/SC13	Disable/Patch Ftp @ 196.216.0.10
SC14/SC15	Disable/Patch SSH @ 196.216.0.10
SC16	Disconnect Internet @ 196.216.0.10
SC17	Disable Rsh @ 196.216.0.10
SC18	Patch FTP/.rhost @ 196.216.0.10
SC19	Chmod home directory @ 196.216.0.10

Problem 1: Single-target optimizaton

With respect to a magnified attack tree $\left({s_{\textit{root}},S,\tau,\varepsilon}\right)\left|{\left\langle{I,V}% \right\rangle}\right.$ and m security measures, find out a vector $\vec{T}^{\ast}=\left({T_{i}^{\ast}}\right),T_{i}^{\ast}\in\left\{{0,1}\right\}% ,1\leqslant i\leqslant m$ , then the minimal residual destruction and total security measure cost function is defined as $\alpha.\textit{RD}(\vec{T})+\beta.\textit{SCC}(\vec{T})$ . Therein, $\alpha$ and $\beta$ are the preference weights of residual destruction and total security measure cost, respectively. They satisfy $1\leqslant\alpha,\beta\leqslant m$ , and $\alpha+\beta=1$ .

The single-target optimization scheme is most possible to be adopted by the security administrator. For two targets, the preference-based methods generally coincide with intuition. However, as it’s discovered from network model, the effect of a scheme is very sensitive to weight. To express such kind of influence, this paper uses different $\alpha$ and $\beta$ to test. Normally, for $\alpha$ and $\beta$ , it is feasible to merely change $\alpha$ , $\beta=1-\alpha$ .

Problem 2: Multi-objective optimization

For a magnified attack tree $\left({s_{\textit{root}},S,\tau,\varepsilon}\right)\left|{\left\langle{I,V}% \right\rangle}\right.$ and m security measures, find out a vector $\vec{T}^{\ast}=\left({T_{i}^{\ast}}\right),T_{i}^{\ast}\in\left\{{0,1}\right\}% ,1\leqslant i\leqslant m$ , to minimize the total security measure cost and residual destruction.

Such problems have to be solved by multi-objective optimization, thereby increasing the complexity of formulation. The multi-objective optimization method is able to relieve the demand for designated weight, so that a better solution can be obtained.

This paper uses a simple top-k algorithm to solve the problem 1 and Skyline algorithm to solve problem 2, as shown in Table 4.

Table 4

The security hardening scheme obtained by Skyline algorithm

	Robust-optimum security controls	RD	SCC
R1	SC9, SC11, SC13, SC15, SC16, SC19	0.0	26.0
R2	SC3, SC4, SC9, SC11, SC18, SC19	10.5	21.0
R3	SC3, SC4, SC7, SC11	13.5	12.0
R4	SC3, SC4	22.8	8.0
R5	SC7, SC11	49.5	4.0
R6	null	58.8	0.0

8. Conclusion

In this paper, through introducing the Skyline algorithm and attack tree model, it solves what troubles the system administrator in practice. That’s how to choose a subset from the given security reinforcement measures and minimize residual destruction with a minimal budget. In addition, introducing modularized idea to solve this problem enables decision-makers to compare various possible cost schemes and make a decision most conforming to the real situation ultimately.

The paper assumes the decision-making process only related to the realizing cost but doesn’t take other factors into consideration. It is hypothesized that every security measure is mutually independent, and the administrator makes his/her decision without being impacted by the cost of breaking the system. Actually, in a real organization’s network environment, this cost model seems too simple. By the way, during system operation, the administrator shall constantly adjust the security strategy of a model according to the emerging safety problems. Once there are more and more security strategies for this model, the serial multi-objective optimization algorithm can no longer satisfy the handling demands, so the distributed multi-objective optimization algorithm needs to be solved in future. The methods mentioned in this paper can be used not only in SCADA system, but also in most of IT systems. We hope this paper will provide a foundation for interested readers and inspire them to use this method in a wider range of systems.

References

Noel

Jajodia

O’Berry

Jacobs

. Efficient minimum-cost network hardening via exploit dependency graphs. In 19th Annual Computer Security Applications Conference, 2003. Proceedings. 2003 Dec 8 (pp. 86-95). IEEE.

Jha

Sheyner

Wing

. Two formal analyses of attack graphs. In Proceedings 15th IEEE Computer Security Foundations Workshop. CSFW-15 2002 Jun 24 (pp. 49-63). IEEE.

Gupta

Rees

Chaturvedi

Chi

. Matching information security vulnerabilities to organizational security profiles: a genetic algorithm approach. Decision Support Systems. 2006 Mar 1; 41(3): 592-603.

Kung

Luccio

Preparata

. On finding the maxima of a set of vectors. Journal of the ACM (JACM). 1975 Oct 1; 22(4): 469-476.

Balke

Güntzer

. Multi-objective query processing for database systems. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, 2004 Aug 31 (pp. 936-947).

Wei

Yuying

. Multi-objective optimization of sheet metal forming process using Pareto-based genetic algorithm. Journal of materials processing technology. 2008 Nov 21; 208(1-3): 499-506.

Borzsony

Kossmann

Stocker

. The skyline operator. In Proceedings 17th international conference on data engineering, 2001 Apr 2 (pp. 421-430). IEEE.

Chomicki

Godfrey

Gryz

Liang

. Skyline with presorting. In ICDE 2003 Mar 5 (Vol. 3, pp. 717-719).

Tan

Kumar

Srivastava

. Indirect association: Mining higher order dependencies in data. In European Conference on Principles of Data Mining and Knowledge Discovery, 2000 Sep 13 (pp. 632-637). Springer, Berlin, Heidelberg.

10.

Godfrey

Shipley

Gryz

. Maximal vector computation in large data sets. In VLDB 2005; Aug 30 (Vol. 5, pp. 229-240).

11.

Tan

Kumar

. Mining indirect associations in web data. In International Workshop on Mining Web Log Data Across All Customers Touch Points, 2001 Aug 26 (pp. 145-166). Springer, Berlin, Heidelberg.

12.

Lin

Zhang

. General spatial skyline operator. In International Conference on Database Systems for Advanced Applications 2012 Apr 15 (pp. 494-508). Springer, Berlin, Heidelberg.

13.

Papadias

Tao

Seeger

. Progressive skyline computation in database systems. ACM Transactions on Database Systems (TODS). 2005 Mar 1; 30(1): 41-82.

14.

Yang

Karamanoglu

. Flower pollination algorithm: a novel approach for multiobjective optimization. Engineering optimization. 2014 Sep 2; 46(9): 1222-1237.

15.

Yang

Fung

Zhou

Chen

. Finding superior skyline points for multidimensional recommendation applications. World Wide Web. 2012 Jan; 15(1): 33-60.

16.

Chan

Eng

Tan

. Stratified computation of skylines with partially-ordered domains. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, 2005 Jun 14 (pp. 203-214).

17.

Ammann

Wijesekera

Kaushik

. Scalable, graph-based network vulnerability analysis. In Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002 Nov 18 (pp. 217-224).

18.

Sheyner

Haines

Jha

Lippmann

Wing

. Automated generation and analysis of attack graphs. In Proceedings 2002 IEEE Symposium on Security and Privacy, 2002 May 12 (pp. 273-284). IEEE.

19.

Schneier

. Attack trees. Dr. Dobb’s Journal. 1999; Dec 24; 24(12): 21-29.

20.

Ray

Poolsapassit

. Using attack trees to identify malicious attacks from authorized insiders. In European Symposium on Research in Computer Security 2005 Sep 12 (pp. 231-246). Springer, Berlin, Heidelberg.

21.

Kordy

Pouly

Schweitzer

. Computational aspects of attack–defense trees. InInternational Joint Conferences on Security and Intelligent Information Systems, 2011 Jun 13 (pp. 103-116). Springer, Berlin, Heidelberg.

22.

Lee

Fan

Miller

Stolfo

Zadok

. Toward cost-sensitive modeling for intrusion detection and response. Journal of computer security. 2002 Jan 1; 10(1-2): 5-22.

23.

Butler

. Security attribute evaluation method: a cost-benefit approach. In Proceedings of the 24th international conference on Software engineering, 2002 May 19 (pp. 232-240).