Keywords

information security countermeasures; resident threats; countermeasure effectiveness

• Knapsack problem

• Optimal security countermeasure selection issues

• A binary knapsack approach using dynamic programming

• Application in a practical case

Introduction

As a result of the extension of information technology into all aspects of business, information security became one of the most important issues in all types of organizations. The vast usage of information systems and computer networks in organizations has provided them with immense benefit. Yet alongside the benefits they offer, these systems can be faced with many new threats that can interrupt, spy upon, or take personal advantage of them. Even the best systems are not completely impervious, since there are always a way to target and penetrate the system’s weaknesses. These weaknesses are known as vulnerabilities. “How to find these vulnerabilities?” “How to identify the threats that could exploit these vulnerabilities?” and “How to formulate the best plan to confront the threats and not to let them become serious attacks?” are the questions for which organizations seek answers.

All of these questions can be answered through the task of risk management [1]. This task includes several subtasks and concepts like risk assessment, which tries to answer the first two questions, and risk mitigation, which is looking for the answer to the last question. In risk assessment, organizations look at threat list and the probability and severity of occurrences and related costs if these threats lead to attacks. Risk mitigation implements the appropriate countermeasure for each asset the organization owns to save them from probable loss. How are these tasks accomplished? For organizations with lots of information assets, such as personal computers, network components, data bases, and so on, these tasks become very complicated.

To face this issue appropriately, major organizations like the National Institute of Standards and Technology (INST) [2],, the International Organization for Standards (ISO) [3], and the Australian/New Zealand Standard (AS/NZS 4360) [4] have defined systematic frameworks as standards, in which they classify most of the information attacks that have occurred and introduce best plans and related technologies in order to prevent probable loss. Each plan and its related technology are defined as a countermeasure. However, considering and implementing all proposed countermeasures defined by these standards is not feasible for business in all types and sizes.

In this regard, many researchers have proposed frameworks and tools to simplify this task. In order to assess the information risk and decide on mitigation strategies with respect to the afore-mentioned standards, [5] proposed a system called OCTAVE, which utilizes qualitative information to assess risk. CRAMM (CCTA Risk Analysis and Management Method), an ISO-based method, was established in 1985 by the Central Computing and Telecommunications Agency (CCTA) of the United Kingdom, tried to manage information risk in three stages as detailed in [6]. The European Union conducted an information security project in 2001 that led to CORAS, an approach that utilizes UML and XML technologies and combinations of standards and best practices to provide a complete and reliable tool for risk management [7]. However, these approaches are still complicated and general, so there remains a need for more agile frameworks. Moreover, how to answer the third question above and choose the optimal countermeasure portfolio should be the primary focus.

Getting serious about developing a best countermeasure portfolio, GAO/AMID [8] proposed a risk assessment matrix that represents risk level by assessing a threat’s severity and the probability of occurrence in a qualitative way. [9] tried to develop a checklist in table form that enables IT experts to plan a coverage strategy. [10] used defense trees and conditional preference networks (CP-nets) to select sets of countermeasures. [11] applied a Multi-Objective Tabu Search (MOTS) algorithm to find the best solution for choosing a countermeasure portfolio on a limited budget. Following [12], a paper on mitigating information security risks within the available budget, [13] tried to develop a knapsack-based algorithm to get to the best subset of countermeasures. However, the author defined control groups and a scoring system in order to calculate countermeasure effectiveness that does not fit all organizations. As a result, IT experts have to decide whether to use this grouping and scoring system as well. [14] conducted a quantitative data set based on the threat set reported on the IT security forum EndpointSecurity.org [15], and proposed a model to find the optimal solution out of all the possible countermeasure options, with respect to a given limited budget. [16] proposed a mixed-integer programming model, similar to Rakes et al.’s, taking advantage of two popular concepts, Value at Risk and Conditional Value at Risk, to make the expert decisions more risk-aversive.

The present research was inspired by [14]’s work. Following their risk modeling approach, I propose a knapsack-based approach that tries to solve a similar model and results in the same optimal solution, which is discussed in the following sections.

The rest of the chapter is organized as follows: The knapsack problem as a NP-hard problem and the best solution for small search spaces is discussed in the next section. In the section after that, a description of a countermeasure selection problem in IT security planning is presented. The subsequent section describes the simple knapsack-based solution and the pseudo code. Numerical examples and some computational results are illustrated in the final section, which is followed by a conclusion.

The Knapsack problem and a dynamic programming solution

The knapsack problem is a problem in combinatorial optimization: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items [17]. The most famous knapsack problem is the binary (0–1) knapsack problem, where the decision maker is allowed to pick (1) or not to pick (0) the item, in other words, the items are not dividable.

The problem can be formulated as follows:

Let there be items, to where has the value and weight . The maximum weight the knapsack can carry is . It is common to assume that all values and weights are non-negative. To simplify the representation, it is also assumed that the items are listed in increasing order of weight.

(1)

(2)

Many algorithms have been proposed to arrive at the optimal subset of items [18]. A simple dynamic programming algorithm with polynomial time complexity for a small search space was proposed in [19]. Dynamic programming algorithms try to solve complex problems by dividing them into smaller sub-problems. A matrix is used to store the answers to sub problems, and the final answer is found after the matrix is filled.

To illustrate, assume are strictly positive integers. Define to be the maximum value that can be attained when the weight is less than or equal to using items up to The definition of is then as follows:

The solution can then be found by calculating The pseudo code is shown in Figure 19.1

The algorithm takes value and weight arrays, number of items, and knapsack capacity as inputs. From line 6 to line 8, the first row of matrix is set with value “0,” which means that when no items are picked, no value is gained. Lines 9 to 17 repeat for all items (filling matrix rows, with index in each iteration) so that at the last cell () will get the maximum value. Following iterations for the loop that starts at line 10, the algorithm considers the situation that we have unit(s) capacity in our knapsack and will return the maximum value that can be taken. This solution will therefore run in time and space. Additionally, if we use only a 1-dimensional array to store the current optimal values and pass over this array times, rewriting from to every time, we get the same result for only space.

There are many practical applications for the binary knapsack theory. For example, assume that projects are available to an investor; each one will cause a specific profit and will cost money unit to invest in project. The investor has limited capital for this investment. The optimal investment plane would result by mapping this problem as a binary knapsack problem and solving it [20]. Another common application is for cutting stock problems. For example, paper factories produce huge rolls of paper that are not fit to customer order at the first place, so they have to slice these rolls into smaller rolls. The value of the smaller rolls depends on the selling price. Fiber optic cable manufacturers are faced with a similar problem; they must decide how to cut lengths of cable to satisfy customer orders while extracting the greatest value from each length of cable. The knapsack idea also applies to solving problems that warehouses or distribution centers (DC) have with space. The main concern among DCs is filling customer orders as fast as possible. On the other hand, they have limited warehouse space for holding their inventories [21]. All of the above problems can be modeled as knapsack problems and solved by the dynamic programming algorithm in a reasonable time.

The dynamic programming algorithm discussed in this section, not only runs in polynomial time complexity but also provides a definite solution. For this reason, this theory is used in our proposed approach to get to the optimal solution for our problem, A described in next section.

Problem description

In this section, the algorithm and its inputs and variables are illustrated, using the notation shown in Table 19.1:

Defined the set of m threats and the set of n countermeasures. Denote by the proportion of threat that will survive if countermeasure is implemented and, respectively, the proportion of this threat that will successfully be blocked. We are looking for maximum block by choosing the optimal countermeasure portfolio. This will cost equal to summation of countermeasures’ cost, which belong to this portfolio, which is denoted by . By , we mean the frequency of threat that occurs each year and , the financial cost imposed by each occurrence of threat .

We now want to determine the optimal subset of possible solutions. For this purpose, an effectiveness score is assigned to each countermeasure. To describe the effectiveness of each countermeasure, we look for other countermeasures’ state of implementation and then calculate the following formula in algorithm:

Let be the total blocked proportion of threat if countermeasure is implemented, considering other countermeasures’ state, calculate as:

(3)

For countermeasure effectiveness we have:

(4)

Our objective function to determine the maximum countermeasure effectiveness is as follows:

(5)

(6)

To illustrate how these variables work, assume we have the following data for , and :

Calculating the blocked proportion of threats 1 and 2 for countermeasure () and its effectiveness, we have:

To illustrate the logic behind this formula, consider the above example, in case of implementation of first countermeasures, that the number of occurrences of first threat, if countermeasure # 3 is implemented, would not be any more, since the first countermeasure blocked 198(0.99 * 200) of its occurrences. As a result, countermeasure # 3 will only block of its occurrences. Having each countermeasure’s cost, it is feasible to find the optimal subset of countermeasures whose total cost does not exceed the budget limits.

As shown, in each step of making the decision about remained countermeasures, we must have the decision that was made about the previous countermeasures (). This may seem like a limitation, but by applying the dynamic programming solution to resolve the binary knapsack problem, it becomes a less complex problem for which a definite solution can be found.

The proposed binary knapsack-based approach and its dynamic programming algorithm

In this section, we introduce our proposed binary knapsack–based approach and its dynamic programming algorithm. This approach begins with the first countermeasure and calculating its effectiveness, in case it is going to be implemented and no other countermeasures have been decided on (). This action takes place at the first if condition (line 11 in Figure 19.1). In order to record the decision about the countermeasures, it’s enough to insert a matrix with “” rows and “number of items” columns. This is simple, as shown in Figure 19.2. The last row in this matrix shows the final decision, which corresponds to , which contains the maximum effectiveness.

The pseudo code for the proposed algorithm is shown in Figure 19.3. In this algorithm, the decision about implementing countermeasures is in . As a result we can calculate current countermeasure effectiveness with respect to other chosen countermeasures’ state of selection. We discuss the logic behind the algorithm and its structure in the following.

Assume , are strictly positive integers corresponding to each countermeasure implementation cost. Define , to be the maximum effectiveness that can be attained with cost less than or equal to money using countermeasures up to This can be defined as follows:

If adding countermeasure in this step would cause the maximum, change form 0 to 1

The can be calculated as described in previous section, and the maximum effectiveness can then be found in . Countermeasures are selected where the corresponding indexes have the value “1” in the last row of matrix.

The algorithm takes the number of countermeasures and their related cost of implementation, the number of threats and their cost of a successful attack, matrix that contains the survival proportion of each attack episode for each countermeasure and available budget as inputs. variable at line 10 is set with value “1” to prevent any wrong calculation in the equation in line 33. The for loop in lines 16 to 20 makes the matrix with initial values “0”. From the 22nd line, the algorithm starts to make a decision about each countermeasure implementation. In lines 24 and 25, matrix changes its upper half rows, which is about status for each money(0 to budget), with its bottom half, which is about status for each money (0 to budget), and puts “0” for all bottom half rows, in order to put the decision about countermeasure in each step for money value (0 to budget) in the for loop that starts at line 27. This exchange happens for each iteration on index. This is necessary, since we want to calculate the effectiveness of the countermeasure, and this value is related to other countermeasures that are selected for implementation by this step. This value is calculated in lines 31 to 35, based on Eq. (3) and Eq. (4). The rest of for loop started at line 27 follows the simple steps in the algorithm in Figure 19.1.

To understand how this algorithm works, two shots of algorithm operations using a simple example are shown in Figure 19.4.

As can be seen in Figure 19.4, in each step in the loop on index , the matrix changes to keep the last decision about countermeasure #1 to Countermeasure #j−1. A computational example with reliable and practical data is discussed in the next section.

Computational example and comparison

In this section, a computational example is presented to show the proposed binary knapsack–based approach and its related dynamic programming algorithm results. The parameters used for the example problem can be seen in Table 19.2.

Table 19.2

Quantitative Data About Current Risk and Countermeasures Effectiveness [14]

The above data set is the same one presented in [14], which was conducted based on a threat set reported on the IT security forum EndpointSecurity.org [15]. This 8*8 matrix is a tabulation representation of the survival proportion of each threat for each countermeasure. The diagonal cells where , represent the primary relationship between threats and countermeasures, that is, the related countermeasure is specifically designed to prevent the related threat. However, other cells where which is less than one, indicate countermeasures that prevent their primary threat as well as other threats.

Briefly describing the [14] model, we show that we can provide the same results in an algorithmic approach. The comparison is shown in Table 19.3. In [14], the authors defined the problem input parameters as we defined them in the preceding section. They defined their model as follows:

This is almost the same model we have utilized in this paper, except that they tried to minimize the risk, while in contrast, we were looking for maximum effectiveness. In concept these are the same, but our definition of problem led us to knapsack problem modeling. In addition, the strength of our approach is that it takes advantage of a dynamic programming algorithm, which does not need any extra variables or linearization. For linearization and solving the non-linear formula in Eq. (7), [14] proposed an integer programming model that finds the optimum solution using multilevel variables in this order. As an example to support this claim, we have defined one level variable for our decision variable , which gets 1 if the countermeasure j is in the optimum portfolio and 0 if it is not. However, in [14], a two-level variable y_jl is presented as the decision variable. y_jl is defined as binary variable that is 1 if the j^th countermeasure is implemented in the l^th level. There are two levels of implementation for each countermeasure: 1 if it is implemented, 0 if it is not. This means that countermeasure j is selected for implementation if y_j1=1 and y_j0=0, otherwise y_j1=0 and y_j0=1. Four multilevel variables are defined in [14] in order to solve the integer programming model. The authors state that without this added level, the linearity of the formulation would not be possible.

As shown in Table 19.3, the proposed binary knapsack–based approach results in the same portfolio as in [14], by using an algorithmic solution in dynamic programming. In other words, using a dynamic programming method that breaks the problem into sub-problems yielded a systematic process for decision-making and arriving at a reliable solution.

This approach is being pursued in a software development company categorized as an SME (small or medium-sized enterprise). Pre-conditions for establishing the proposed model are as follows, according to priority:

Having these inputs and the Budget for firming up security as desired by the organization’s leaders, the proposed approach can be followed to arrive at the best decision. One important feature of this approach is that as the dynamic programming algorithm runs, the most effective solution it comes up with may even be under budget. For example, the budget may be $1,000 but the most effective portfolio costs $800.

Conclusion

Making a risk-based decision about a collection of countermeasures having various degrees of effectiveness is a complicated task that affects the continuity of business in organizations. As a result, IT security planners are always looking for a way to conduct a systematic analysis in order to make sure their final decision is the best one.

Despite the many existing frameworks and models in this regard, decision-making in this area remains confusing and complicated. All the countermeasures presented in standards or guidelines are not always effective for a given organization. Some security controls even cost more than the loss they are supposed to prevent. In this chapter, we propose a binary knapsack–based approach for choosing the best countermeasures for IT security, following recent research by [14]. Inspired by their reasoning and risk-based model to find the optimal countermeasure portfolio, a new approach is proposed that results in the same solution in different situations, using their input parameters.

A brief road map for employing the proposed algorithm is explained in the previous section. After assessing the resident risk on assets and estimating security control effectiveness, the most preventive portfolio of countermeasures can be chosen for implementation.

References

1. Bornman WG. Information security risk management: A holistic framework [dissertation submitted for MS]; Rand Afrikaans University; 2004.

2. Stoneburner G, Goguen A, Feringa A. Risk management guide for informationtechnology systems. NIST Special Publication; 2002;800–830.

3. ISO/IEC 27005. Information security risk management. International Standard Organization; 2008.

4. AS/NZS. Risk management. Australian/New Zealand Standard. 3rd ed; 2004.

5. Albert C, Dorofee A. Introduction to the OCTAVE approach. Carnegie Mellon Software Engineering Institute; 2003;4–16.

6. Yazar Z. A qualitative risk analysis and management tool–CRAMM. SANS InfoSec Reading Room White Paper; 2002.

7. Lund MS, Solhaug B, Stølen K. Model-driven risk analysis: The CORAS approach Springer 2011.

8. US Government Accountability Office. Information security risk assessment: Practices of leading organizations. United States General Accounting Office; 1999.

9. Egan M. The executive guide to information security Indianapolis: Symantec Press; 2005.

10. Bistarelli S, Fioravanti F, Peretti P. Using cp-nets as a guide for countermeasure selection. ACM Symposium on Applied Computing Seoul; 2007.

11. Viduto V, Maple C, Huang W, López-Peréz D. A novel risk assessment and optimisation model for a multi-objective network security countermeasure selection problem. Decision Support Systems. 2012;53(3):599–610.

12. Lenstra A, Voss T. Information security risk assessment, aggregation, and mitigation. Lect Notes Comput Sci 2004;391–401.

13. Altena JA. ISO/IEC 27002 baseline selection Nijmegen: Radboud Universiteit Nijmegen; 2012.

14. Rakes TR, Deane JK, Rees LP. IT security planning under uncertainty for high-impact events Omega: International Journal of Management Science; 2012; 79–88.

15. Security breaches and the cost of downtime. Endpoint security. [Internet]. Available from: http://www.endpointsecurity.org/Documents/Security_Breaches_and_the_Cost_of_Downtime.pdf.

16. Sawik T. Selection of optimal countermeasure portfolio in IT security planning Elsevier 2013.

17. Kellerer H, Pferschy U, Pisinger D. Knapsack problems; 2004.

18. Martello S, Toth P. Knapsack problems: Algorithms and computer interpretations; 1990.

19. Andonov R, Poirriez V, Rajopadhye S. Unbounded knapsack problem: Dynamic programming revisited. Eur J Oper Res. 2000;123(2):168–181 http://dx.doi.org/10.1016/S0377-2217(99)00265-9.

20. Pisinger D. Algorithms for knapsack problems [Ph.D thesis] Copenhagen, Denmark: Dept of Computer Science; University of Copenhagen; 1995.

21. Bartholdi III JJ. The knapsack problem. In: Building Intuition Springer 2008; p. 19–31.

22. Sonnenreich W, Albanese J, Stout B. Return on security investment (rosi)-a practical quantitative model. J Res Practice Inf Technol. 2006;45–56.