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

multivariate dependencies of complex problems in acceptable amount of time and
with admissible computational complexity.
2 Background
In this section, Deterministic Hill Climbers (DHC) which will be used later in our
algorithm and challenging problems which are used to explain and test the proposed
algorithm are described. Firstly, some terms should be defined. A partial solution
denotes specific bits on a subset of string positions. For example, if we consider 100-
bit binary strings, a 1 in the second position and a 0 in the seventh position is a partial
solution. A building block is a partial solution which is contained in an optimum and
is superior to its competitors. Each additively separable problem is composed of
number of partitions each of which is called a "linkage group".
In this study, DHC [10] are used to search for local optimums. In each step, the
DHC flips the bit in the string that will produce the maximum improvement in fitness
value. This process can be allowed to iterate until no single bit flip produces
additional movement. DHC starts with a random string.
2.1 Challenging Problems
Deficiencies of GAs were first demonstrated with simple fitness functions called
deceptive functions of order k . Deception functions of order k are defined as a sum of
more elementary deceptive functions of k variables. In a deceptive function the global
optimum (1, ,1) is isolated, whereas the neighbors of the second best fitness solution
(0, ,0) have large fitness values. Because of this special shape of the landscape, GAs
are deceived by the fitness distribution and most GAs converge to (0, ,0). This class
of functions has a great theoretical and practical importance. An n -bit Trap5 function
has one global optimum in the string where the value of all the bits is 1, and it has
( 2 n/5 ) - 1 local optimums. The local optimums are those individuals that the values of
the variables in a linkage group are either 1 or 0 (they are all 1, or they are all 0) [8].
Also another additively separable function called deceptive3 [8]. An n -bit
Deceptive3 function like an n -bit Trap3 function has one global optimum in the string
where the value of all the bits is 1, and it has ( 2 n/3 ) - 1 local optimums.
For yet another more challenging problem we use an additively separable function,
one bit Overlapping-Trap5. An n -bit Overlapping-Trap5 function has one global
optimum in the string where the value of all the bits is 1 just similar to Trap5
function, and it has ( 2 (n-1)/4 ) - 1 local optimums. The local optimums are those
individuals that the values of the variables in a linkage group are either 1 or 0 (they
are all 1, or they are all 0) again similar to Trap5 function [8].
2.2 Linkage Learning
There are lots of approaches in the class of linkage adaptation techniques. Linkage
learning GA [2] uses a special probabilistic expression mechanism and a unique
combination of the (gene number, allele) coding scheme and an exchange crossover
operator to create an evolvable genotypic structure. In [4] punctuation marks are
added to the chromosome representation. These bits indicate if any position on the