Structural Feature Based Anomaly Detection for Packed Executable Identification - Computational Intelligence in Security for Information Systems - page 288

In additively separable problems there are lots of these local optimum solutions.
Actually number of such solutions is directly dependant on length of the problem and
number of partitions (or sub-problems or linkage groups) of the problem. It can be
said that each local solution contains at least one building block (except the one with
all 0s) and therefore comparison of the optimum solutions can lead us to identification
of the linkage groups.
The following example can reveal this concept more clearly. Consider a 12 bit
Trap3 function. This function has one global optimum 11111111111 and (2 12/3 ) - 1 =
(15) local optimums. The strings are local optimum if the bits corresponding to each
trap partition are equal, but the value of all the bits in at least one trap partition is 0.
Some of local optimums are shown in table 1: A simple comparison between first
local solution and fifth local solution helps us find the second linkage group and
comparison between third local solution and fourth local solution helps us find the
first linkage group.
Now, the algorithm can be explained and the example is continued later. In an
overall view, there are two phases of search and analysis. In search phase some local
optimums are found and in analysis phase the comparisons between these local
solutions are done. If number of local solutions is not enough to discover all the
linkage groups of the problem, the local solutions for the remained bits of the problem
that are not assigned to a linkage group yet are to be found by the comparison of the
newly found local optimums. This process repeats until remained undiscovered
linkage groups of the problem are identified. The process will end if all the variables
of the problem are assigned to a linkage group. In the search phase, K DHCs are
initialized randomly and set to search the landscape (with length ( Xs ) number of
variables). When each DHC finds a peak in the landscape and no movements are
possible, that solution which is a local optimum will be saved in a set named
HighModals .
After the search phase, analysis phase starts. In the analysis phase, linkage groups
should be identified by comparing different local optimum solutions.

Table 1. Some of the local optimums for Trap3 size 12

1 1 1 0 0 0 0 0 0 1 1 1

0 0 0 1 1 1 1 1 1 0 0 0

0 0 0 1 1 1 0 0 0 1 1 1

1 1 1 1 1 1 0 0 0 0 0 0

1 1 1 1 1 1 0 0 0 1 1 1

A comparison method is needed for the analysis phase. The comparison method
should be able to segregate the BBs of the local solutions and yet be simple and
uncomplicated. XOR operation is a good candidate for this purpose. This is due to the
fact that the local and global solutions of a decomposable function are the two strings
with the most differences in their appearance and binary strings are used to code the
individuals.