Schneier on Security

Clive Robinson • February 2, 2023 6:50 PM

@ Bruce, ALL,

Re : Faster v Smarter.

If we look at humans and computers we see that traditionaly,

Humans = Smart but slow.
Computers = dumb but fast.

That is why humans do research and come up with models and the computers do the grind of the mathmatical models, often at an accuracy well beyond human ability.

As long as this holds true then AI is not actually going to be able to do something new.

The difference is the first two steps of the “goal seeking” procedure. Which are,

1, Select a usefull goal.
2, Come up with a test for that goal.

The first is an unbounded problem and based on the wants of society within an environment and the desires to forefill them.

The second can be bound or unbound and it is dependent not just on the goal but the environment and the rules that it and the society within it imposes on agency within the environment.

The rules of an environment including a society within it have to some how be learned which are found by the same goal seeking proceadure or taught based on a previous runs of the proceadure.

A game such as chess has an object that can be not just described but easily tested for. The environment is strongly bound and the rules precicely defined.

Thus we know a solution can be found all be it slowely by iterating through every move untill the goal is met. Given sufficient time and resources an optimum solution can be found.

However the hard part is “learning” about what an opponent will do either randomly or as a sacrafice to obtain a better position. Whilst there is little that can be done about random, sufficient observation of an opponents play will show their general strategies.

Interestingly in a bound environment the same observation will show what the rules are all be it inefficiently. Likewise the goals of the game.

So in a bound environment with fixed rules and a defined outcome, just observing sufficient game play will allow what is at it’s base simple computational analysis to find the rules, and goal and find an optimum strategy against a set of consistent players.

The interesting thing though is on limited data can it find all the rules? And likewise see all the winning options? But more subtle is can it tell the difference between rules of the game and stratagies of a consistant player or group of players.

So we can see that basic analysis and a sufficient data set will get us to finding ways to win in an optimal way. As the computer in effect comes up with it’s own play stratagies it might appear as though it has “learned” but has it? or has it simply “recognized” paths that are predefined by the environment and the rules and just picked what is in effect one of the shorter ones.

Basically treating it as a “Traveling Salesman Problem” and using “simulated annealing algorithms”.

A solution I know works well for “cutting glass” to get minimum wastage. The basic rule of the game being all cuts have to go fully across a piece, and the resulting two pieces are then independent pieces thus the rule is applied to them and so on. Whilst it might look like walking a binary tree problem it’s actuall not as you are doing the inverse from an unknown starting position.

There are other algorithms that can be used based on metaphors of what we consider “natural processes” but they all have problems, as described in this more than tw decade old –but still relevant– IEEE article,

https://www.cse.unr.edu/~bebis/CS477/Papers/Nature'sAlgorithms.pdf

The problem with cutting glass is finding the balance between local and global maxima. If you have lots of small pieces a greedy algorithm using local optomisation tends to work, but with few large pieces a different approach is needed. As a rough rule “start with the largest” can be close to optimal, however starting with grids of small pieces that become variable sized large pieces can prove better.

The thing you learn is that as the game progresses the optimal stratagy changes, that is each move in chess and each cut of the glass changes the environment, even though the rules remain the same.

So the trick in a bound predictable rule environment becomes knowing when to use any given strategy to get you to the desirable end in the least number of moves or cuts.

But that is only one of several optimums, in manufacturing you generally trade work –effort energy– with cost. That is there is a trade off in terms of the time taken cost, and the wastage cost in cutting glass. But the wastage from one job is not necessarily “waste” but can become smaller sized stock and that in turn depends on “storage cost” as whilst sufficiently large off-cuts from one job can be used as stock for a later job, getting it back into and out of storage have their own costs, as does the use of storage space. You quickly realize that “optimum” has limitations.

The classic being,

“Asume the traveling sales man is doing his route in one working day. You could by searching every possability find the optimal path. But it takes a week of computation to find it.”

Is it of any use?

The answer is it depends on how often the route will be used. The computer can not work that out it is an unknown. And it can not usually be found from past data as the future changes in most environments.

Which brings us onto the fact that paths change based on previous actions and thus an adaptive response is required especially if there are two or more independent players with agency. This gives rise to the notion of not “following paths” but using localised algorithms running in parallel as a way to adapt to the changing environment. A simple visable example is “Conway’s game of life” where very simple cellular automata produce what appear to be very complex behaviours. But it is actually a “zero player game” that is no matter how complex the behaviour the starting conditions predefine everything. In effect it is a chaotic not random system.

Thus it can now be seen that without a random input AI is nothing other than “preordained” or “fully determanistic” in it’s behaviour and at best has no true agency. Something Alan Turing was apparently aware of as he insisted on a random generator being added to the Faranti Mk1 and the Manchester Computer design prior to his now famous 1950 paper “Computing Machinery and Intelligence”, which anticipated the whole subject of AI.

So, to attack a system an AI would have to include some random element, the most obvious from an external system attacker perspective is a “fuzzing tool”[1].

The problem with using fuzzing tools is that they “make a lot of noise”. That is to work malformed input is sent to the system under attack. The idea is that this input causes vulnarabilities to be activated and a fault to occur which is visable in the system output. However two issues arise,

1, Only a small subset of faults appear at the output.
2, Of those most are a catastrophic fault that halts the system.

Thus are just as easily detected by a defender, as the attacker.

Thus a threshold rule is needed on the generation of the malformed input, which in most cases will not cause a recognisable fault at the output.

The reality of fuzzing tools is that they’re most useful use is when you control the system under test / attack and you can halt the system and do a delta check on it’s state.

In most of the few “capture the flag” games I’ve observed the attackers bring attacks they have already developed against known software that are “quiet”. As such they are looking not for “new faults” but excercising “known faults” to step their way along a path to a goal as quietly as possible. Especially if the game is adverserial and the defender has agency.

Thus fuzzing or random acts are not all that usefull in an adverserial situation.

So it can be seen that for an adverserial game / attack, the attaker has to use “known attacks” –to the them– that have low or no visability to the defender. Otherwise the defender will simply shut the attacker out.

Thus the best use of AI + Fuzzing is not for “captutre the flag” games, but be used in a controled environment to automate finding new attack methods that are quiet.

Thus whilst “capture the flag” games might be fun as with real warfare the important activity is off of the battlefield in the equivalent of the R&D dept of the armaments manufacturer.

Whilst trying new tactics with the weapons at hand can and even sometimes does work on a battlefield. You very very rarely if ever create new weapons on the battlefield.

So not seeing AI at “capture the flag” games might not be such a loss as it might appear.

My chosen use for developing tactics would be to get two different teams be they human or AI to “table top” in a more controled or “lab” environment, out of sight.

[1] Fuzzing tools are seen by many –sales people– as an excellent technique for locating vulnerabilities in software. Fuzzing’s basic premise is to deliver intentionally malformed input to a target system and detect system failure (which is why it’s noisy). Generally a fuzzing system is seen as having three main parts,

1, The “Poet” which creates the malformed inputs.
2, The “Courier” which sends the malformed input to the target system.
3, The “Oracle” that monitors the target system looking for indicators of failure.