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

Therefore in the analysis phase, each two local optimum solutions in the
HighModals set are XORed with each other and the results are stored in XORed set.
Therefore XORed is an array of arrays. The strings with least number of ones are
found. Number of 1s ( r ) in these strings is considered the length of linkage group.
And these strings (string with length r ) are put in the set DiscoveredBBs which is an
array of arrays and contains the ultimate results (all the identified linkage groups). All
of the other members of XORed set with more than r 1s are put in the set XsArray
which is again array of arrays. After identifying some of the linkage groups, the
algorithm is recursively called for finding linkage groups in other parts of the string
which are not identified yet. The undiscovered parts are the XORed strings which
their length is more than r or those variables of the problem which are not in the
XORed set. Therefore those bits in the Xs which are not in the XORed set are added as
a separate member to the XsArray (step A.4 in the algorithm).
As it is mentioned before we need a mechanism to balance the time spent in the
search phase. For this reason a parameter, sp is contrived which determines when to
leave the search phase. Leaving the search phase takes place with the probability sp .
If sp is small, the set HighModals will become bigger because the search phase takes
longer and as a consequence more local solutions are found. Analysis of huge number
of solutions is difficult and unnecessary. On the other hand by comparison of too few
local solutions there is a little chance of identifying all the linkage groups of the
problem. So sp parameter should be determined wisely considering the length of the
problem. If the length of the problem is more, the number of local solutions needed to
identify the linkage groups is more. If each variable of the problem is assigned to at
least one linkage group, the LOLL algorithm terminates. The pseudo code of LOLL
algorithm is shown in Algorithm 1.
Xs is an array with length n containing the indexes of the problem variables.
DiscoveredBBs is an array of arrays, containing the discovered linkage groups. Each
linkage group is shown with an array containing the indexes of the variables in the
linkage group. HighModals is an array containing the local optimums of the problem.
XORed is an array of arrays containing the result of XOR operation on local solutions.
Each XOR result is shown with an array containing the indexes of bits which their
value is 1 after doing XOR operation. DeterminedBits is an array which contains the
indexes of the variables which their corresponding linkage group is identified.
XsArray is an array of arrays containing those parts which should be searched again
for identification of the remaining linkage groups.
As it is obvious, the only parameter which should be set wisely is sp . In the future
work, we address solutions to adjust this parameter automatically. Complexity of the
algorithm will be discussed later. Now, we go back to our simple example: Xs is here
the array Xs = {1, 2, …, 12} HighModals set is in Table 1.
XORed set of our simple example: [1,2,3,4,5,6] , [1,2,3,7,8,9] , [7,8,9,10,11,12] ,
[4,5,6] , [1,2,3,7,8,9,10,11,12] , [1,2,3]
DiscoveredBBs set so far: [4,5,6] , [1,2,3]
DeterminedBits set: [1,2,3,4,5,6]
XsArray : [1,2,3,7,8,9] , [7,8,9,10,11,12] , [1,2,3,7,8,9,10,11,12]