Randomized Algorithm in Cybersecurity Penetration Testing — Unpredictable attack paths.

A few weeks ago, while I was looking into red teaming and penetration testing, I came upon a comment which caused me to think. The fact is that most automated penetration testing tools follow rather similar procedures because they begin by scanning for open ports, then identify the services running on those ports, check for any known vulnerabilities and default credentials, and only afterwards move on to the next host.

There is no fundamental fault in taking a systematic approach; on the contrary, it is a reasonable method to adopt. It does, though, raise an important question namely, what exactly is the object of simulating an actual penetration test?

An attacker need not follow a well-defined sequence consisting of reconnaissance, scanning, enumeration, exploitation, privilege escalation and lateral movement. It is possible for them to look into one system, then give up on that effort, turn to another system and later choose to use a completely different set of exploits before finding new vulnerabilities. The course of their attack may differ depending on the circumstances, on what they do find, on what they do not find and on the opportunities that present themselves.

That is the reason why our penetration testing tools always show such predictable behaviour.

A possible way to deal with this would be to make use of randomised algorithms.

→ → Randomized Algorithms Explained

An algorithm which is random is one that makes some of its decisions by means of randomness. Instead of always taking the same decision, it selects from a number of previously determined options or makes use of values that are generated at random when deciding.

The idea is in fact very simple: suppose that your algorithm has three possible decisions it can make. A deterministic algorithm (that is, one which always follows the same set of instructions) will always carry out the same action, while a randomized algorithm, on the other hand, might choose any of the three possible options when making a decision, the choice being determined by a value generated at that moment by random selection.

Randomized algorithms are by no means a foreign concept in the field of computer science; for instance, certain versions of Quicksort make use of randomized pivot selection, hash tables use randomized hashing in order to reduce the likelihood of hash collisions, and load balancers employ randomized algorithms when distributing traffic between servers in order not to overload any one of them. The notion of taking random decisions in order to achieve a desired outcome is not new — at all — it's merely that such methods are not very common in the area of penetration testing.

The fact that this is true for the field of cybersecurity means that there is a way of randomising the route that an automated penetration testing tool follows.

→ → The Problem with Predictability

In the case of penetration tests — whether they are manual or automated — they follow a methodology composed of a series of general stages, which begin with reconnaissance and scanning, then move on to exploitation and privilege escalation, and finally involve lateral movement, in accordance with the objective of the penetration test.

This approach does help to a certain extent since it provides the penetration tester or testing tool with a general idea of what to look for; yet, just as in all the other cases, blind spots will still occur when a strict methodology is followed.

If the defensive team in question is fully aware of the attack patterns that your pentesting team or their tools will employ, and your tools always select the same systems to test, always look for the same set of vulnerabilities and always attempt privilege escalation in the same way, then your penttest could be compromised long before you realise it.

That does not mean that the defenders are making any errors; on the other hand, security teams typically prepare and make use of threat models as well as defensive automation that is designed to detect known attack patterns. Automated detection and response systems are also susceptible to the same mistake, the reason for the problem being predictability.

Should the tool you are employing always check the same systems, always search for the same type of vulnerabilities and always attempt to escalate its privileges in the same manner, your penetration test could be compromised well before you realise this. It might begin by picking a specific system, might continuously use the same exploit, and might always select the same technique for escalating privileges because it has been programmed to look for that particular vulnerability first.

Maybe there is some other vulnerability in the system as well — could it be that the various systems have different privileges? Or maybe the methods of carrying out lateral movement differ?

It is there that randomization proves to be useful.

→ → Building It Into a Pentesting Tool

A randomised penetration testing tool needn't be completely random. The object is not to make the penetration testing tool behave in an erratic way, but rather to give it a certain amount of controlled randomness so that it can examine various possibilities at different decision points.

The places where randomness can be brought into the pentesting process include:

Which system to target first

The order in which to scan or probe ports or services

The attack vector to try

The payload to attempt

The method to attempt privilege escalation

The lateral movement vector to use

The order of operations

The intervals between different operations

The actual method used will obviously depend on the type of penetration testing tool, and the degree and scope of randomisation can be changed in line with the tool; in some instances actions which have a higher weight or probability may still be carried out more frequently than being completely random.

The reason for employing controlled randomness is to consider all the different possible options while at the same time adhering to certain constraints.

It is important to note that the word 'controlled' is opposite to the term 'unpredictable', and the fact that a process is random does not mean that the pentesting tool should be left to act freely.

→ → Randomness Does Not Equal Recklessness

A randomized penetration test should always remain well within clearly defined boundaries.

For example, if your network includes ten systems of which only five have been given permission to be tested, your penetration testing tool should not randomly choose the other five.

The same rule applies to actions: a penetration testing tool should not be allowed to perform destructive actions such as deleting a database, launching a denial of service attack or modifying important files merely because such actions are available. It is essential to specify what a pentesting tool is permitted to do when defining the scope of the engagement.

There should be more strict controls concerning destructive actions, extensive logging should be carried out and, where possible, there should be a separate system which is capable of immediately halting a penetration test if any problems occur.

This once again shows that randomness can be regarded as a controlled experience.

→ → An Example

Let's imagine a small network that consists of several systems:

A web server that faces the Internet

An employee's workstation

An authentication server

A database server

A cloud service that hosts the company's backups

should develop, within the limits of a set of established rules.

A deterministic penetration testing tool will first aim at the web server, then move on to the database, afterwards target the authentication server, and finally focus on the employee's workstation and the cloud storage.

Instead the random penetration testing tool could show this network in the form of an attack graph. Each of the systems in the network will be represented as a node, the links between them showing the different methods in which the penetration test can be carried out, and each step of the penetration test corresponds to an action that the pentesting tool is capable of taking. At each junction the tool has a number of options.

A single run of the pentesting tool might start off by examining the web server, but it could then proceed to the employees' workstations if the tool judges that this is possible. In another instance, the tool might begin by looking at the cloud storage and thus discover a completely different means of gaining access to the network.

That doesn't imply that one of the runs is better than the other; instead, each run focuses on different systems, proceeds through different steps, and tries various methods of escalating privileges and moving laterally.

→ → A Simple Implementation

The general decision making process for such a tool can be summarized in a simple block of pseudocode:

function select_next_action(current_state, attack_graph, rng_seed):

rng = initialize_random_generator(rng_seed)

available_actions =

attack_graph.get_valid_actions(current_state)

allowed_actions =

filter_by_scope(available_actions, rules_of_engagement)

if allowed_actions is empty:

return no_action_available

weights =

assign_weights(allowed_actions, current_state)

chosen_action =

rng.weighted_choice(allowed_actions, weights)

return chosen_action

The key factor in this case is the random seed, since it sets up the random number generator.

A random number generator needn't be completely random since weights can be assigned to it; in the example mentioned, the possible actions are selected on the basis of the current engagement rules and then prioritised according to the current state before being passed on to the random number generator, which chooses one of the available actions by using the probabilities as weights.

Here, randomness does not imply unpredictability; it means that it is possible to consider new options while staying within the given constraints.

That is to say that at least in theory a pentesting exercise can be reproduced at a later date if the random seed is kept record of; it has the advantage when it comes to debugging since the same penetration testing exercise can be replayed to see exactly what took place.

Debugging randomized penetration testing would be much more difficult in the absence of such an option.

→ → The Advantages

A clear advantage of such a tool is that it increases the amount of attack path coverage.

If a deterministic penetration test is run multiple times, it does not have to produce different results. On the other hand, if a randomized penetration test is run several times, it may reveal different attack chains, each one aiming at different systems.

This has several advantages.

In the first place, it decreases the chance that a penetration test will be compromised since the same attack pattern is used every time. Second, it makes sure that the test includes a greater number of different attack paths, thereby enabling the defensive team to get a better understanding of the kinds of attacks they should be on the lookout for. Lastly, it lowers the possibility that a penetration test will fail to identify a vulnerability as a result of the way the test is organised.

It is not necessary for a security team's defenses to be effective against each possible exploit by itself; what is required is that they should be effective when those exploits are combined with one another.

The advantage of having a random attack path is clearly seen here: it is possible to establish that a single weakness in one system does not pose an immediate threat, but that when combined with a weakness in a different system it can allow an attacker to cause a great deal more damage.

→ → The Downsides and Constraints

There are obviously certain disadvantages to adopting such an approach.

A clear disadvantage is that carrying out a randomized penetration test is more difficult to reproduce.

The test taker should carefully examine what has taken place if the test fails or gives unexpected results.

This can take a lot of time, particularly when dealing with a complex attack graph.

You must also keep all of the relevant logs since the run can be quite different depending on the random seed that has been selected.

On the contrary, a randomized attack path might need more computational power than a deterministic attack path.

A deterministic penetration test will always focus on the same system and will always identify the same vulnerability, whereas a randomised one might have to go through a large number of possible attack paths before it finds a vulnerability.

Another disadvantage of the same importance is that there might be more false positives.

An algorithm, when it selects one of a large number of possible actions, could end up picking out attack methods which are not likely to occur statistically although they are still theoretically possible.

This could lead to problems when carrying out tests, especially if the results of one penetration test are to be compared with the results of another.

In such a situation it could prove difficult to compare attack chains since one penetration test might identify a number of exploitable vulnerabilities while another discovers a totally different set.

That is why logging is so important.

The random seed together with the attack graph state and all the decisions made and the actions carried out must be logged so that they can be reviewed.

A penetration testing tool that is effective should be capable of detecting vulnerabilities as well as supplying adequate logs to account for what has occurred.

→ → Randomization and Reinforcement Learning

There is also an interesting similarity between applying randomization to attack paths and reinforcement learning, particularly when it comes to the exploration-exploitation dilemma.

An attack graph is essentially a state machine in which the current node shows the state and the edges represent the actions that the penetration testing tool can carry out; reinforcement learning operates in a manner similar to that of a randomised penetration testing tool since the agent has a number of possible actions but must first explore them and determine the reward associated with them before it can make use of them.

What this means is that it is not always possible to select the most rewarding action since you won't know the rewards linked to all the possible actions until you have explored them.

The same principle can be applied in the context of penetration testing: instead of always choosing the most obvious course, a penetration test that is carried out at random should look into paths that might be rewarding before exploiting them.

It by no means follows that you must always choose your actions at random; on the contrary, what is meant is selecting from among the best options that are available, based on your knowledge of the situation, within reasonable limits.

→ → The Human Touch

It is true that a randomized automatic penetration testing tool has obvious advantages, but that does not mean it should be seen as a replacement for human ability and insight.

A person is usually better at picking up on fine connections and circumstances than can be achieved even with a great deal more computational power and is able to make the most of opportunities that a tool was not designed to handle.

On the contrary, an automatic penetration testing tool is able to systematically look at all the different possibilities, since it won't get tired from trying to discover vulnerabilities in a particular system or from giving up, as it does not have the necessary privileges.

All methods have their advantages and their disadvantages.

A person could detect an opportunity and recognize it, but an automatic tool would never search for it unless it had been built to do so.

Maybe the best thing to do wouldn't be to choose one or the other, but instead to make use of the advantages of both.

→ → Legal and Ethical Implications

The fact that a randomization method is employed does not release the penetration tester from their duty of acting within the legal and ethical boundaries; the same rules apply.

You should only carry out a penetration test on a system or network for which you have been given permission, and the rules of engagement must be agreed upon before the test starts, specifying the duration of the test, the scope and the actions which are permitted, all of this being within the context of a testing environment.

The rules do not change even when a random attack path is employed.

A penetration test carried out with a tool that selects its actions at random has no greater authorization than one that you perform yourself or one that you carry out using another tool which follows a deterministic approach; even if the tool chooses its actions randomly, it remains unauthorized unless you have been authorized to carry out a penetration test.

You should therefore apply authorization restrictions and safety rules to a tool that makes use of randomized attack paths.

→ → Conclusion

With regard to the limitations of automated penetration testing, the use of randomized algorithms is an interesting solution. Instead of the tool carrying out the same sequence over and over again, controlled randomness in the decision-making process allows it to consider a wide range of possibilities, attack vectors, targets, and paths. Attack graphs are a good way of introducing such variations since they enable the tool to display different options as nodes and to move from one node to another by means of different actions. Furthermore, the use of recorded random seeds also results in greater consistency within a given environment without impairing the tool's ability to explore.

Conducting randomized penetration tests requires extra resources, makes it more difficult to compare the test results, and entails some additional debugging aspects which have to be considered.