Computer Security Symposium 2012
30 October – 1 November 2012

マルウェアの部分コードによる類似度判定および機能推定法
大久保諒 †森井昌克 †伊沢亮一 ‡† 神戸大学大学院工学研究科657-8501 兵庫県神戸市灘区六甲台町 1-1
okubo.1@stu.kobe-u.ac.jp

井上大介 ‡

中尾康二 ‡‡ 独立行政法人情報通信研究機構
184-0015 東京都小金井市貫井北町 4 丁目 2-1{isawa},{dai},{ko-nakao}@nict.go.jp

mmorii@kobe-u.ac.jp
あらまし
マルウェアの類似度判定では，検体を入手する度にデータベースに保存されている大量の検体に対して類似度を求める必要があり，計算量の削減が課題として挙げられる．従来の類似度判定
法では LCS(Longest Common Strings) や n-gram を用いるものが多い．LCS と n-gram の計算量はともに O(m×n) であり，大量の検体かつ頻繁に類似度を求める状況においては計算量が小さいとは言い難い．本研究では高速な類似度判定を目的とし，マルウェアのバイトコードの出現頻度を利用する方法を提案する．提案方式の要点は，各マルウェアのバイトコードの出現頻度をデータベース化するところにある．出現頻度のデータベースを作成した後は，正規化相互相関を用いることで類似度の計算量が O(1) となる．また類似度から機能毎にポイントを与え，マルウェアの機能を推定する手法を提案する．

Function Estimation Method for Malwares based on part ofBinary Code
Ryo Okubo†

Masakatu Morii†
Ryoichi Isawa ‡Koji Nakao ‡Daisuke Inoue ‡†Graduate school of Engineering, Kobe University
1-1 Rokkodai-cho, Nada-ward, Kobe 657-8501, JAPANokubo.1@stu.kobe-u.ac.jp
mmorii@kobe-u.ac.jp‡National Institute of Information and Communications Technology
4-2-1 Nukuikitamachi, Koganei-city, Tokyo 184-0015, JAPAN{isawa},{dai},{ko-nakao}@nict.go.jp

Abstract
Because malware analysis using similarities between malwares needs to make a lot of comparison, calculation amount is an important factor. Existing methods use LCS(Longest CommonStrings) or n-gram to calculate similarity. The calculation amount of them is O(m×n). This
calculation amount is not appropriate for making a lot of comparison. We propose a fast method
for calculating similarity between malwares. We focus on distribution of byte code. To calculate
a similarity between the two of malwares, we apply Zero-mean Normalized Cross-Correlation.
Once we get the distribution of byte code, the calculation amount is O(1). Because this method
does not inﬂuenced by ﬁle size, we can calculate similarity at short times in any case. Moreover
we estimate function by adding point to each function according to similarity.

-9-

1

Introduction

These days a great number of people use
the Internet for shopping or on-line banking.
These services deal with their important personal information. Once a user’s information
leaks, the user will suﬀer a loss. If an Internet user’s computer is infected by malware,these information will be easily stolen. Antivirus vendors provide antivirus softwares toprevent the Internet users from such damage.
To protect the users from malwares, the antivirus vendors must analyze each malware.
Symantec reported that 403 million malwares
were created in 2011[2]. With various malwares increasing rapidly, a burden on malware
analysts cannot be ignored. Many researchers
propose new methods for eﬃcient analysis toease this burden. There are two methods foranalyzing malware, one is dynamic analysis,
and the other is static analysis. In dynamicanalysis, researchers actually execute a malware and observe its behavior. Because thismethod just reports the behavior that the malware has done, the result will be precise. However, malwares infect the computer on which
they execute, and we have to recover the computer system after analyzing malwares. On
the other hand, static analysis does not require
executing malware. In this paper, we propose
a fast method for static analysis to calculate alot of similarities at short times. We focus on
the distribution of byte code to calculate similarities between malwares. The distributionof byte code is a simple characteristic and iseasy to compare. We make use of ZNCC(Zeromean Normalized Cross-Correlation) to calculate similarity. Because our method needs only
the distribution of byte code, it can fast calculate the similarities regardless of the ﬁle sizesof malwares. Moreover we use the similarity
to estimate function of malwares. We apply
this method for MWS dataset.

2Related Works

that calculate similarity by static analysis.
Higashi et al.[3] calculate similarities basedon functions such as Windows APIs or subroutines. They extract functions from disassembled code. They calculate similarities between
functions of an unknow malware and functionsof an analyzed malware to estimate the function of the unknown malware. Suppose that
we have a target malware that we try to analyze and an analyzed malware. The target
malware has functions a, b, and c. The analyzed malware has function e, f , and g which
are known. If the similarity between functiona and function e is high, Higashi et al. assume that the target malware have function e.
They use 3-gram and LCS (Longest CommonStrings) to calculate similarities. Both methods are used for extracting common part oftwo strings. 3-gram makes factors of 3 lengthfrom strings and compare the factors. LCS
extracts the longest common strings from twostrings, according to eq. 1, where both ai andbi denote strings.

0 (a = 0 or b = 0)L(ai , bj ) =max(L(ai−1 , bj ), L(ai , bj−1 ))(ai ̸= bi )L(ai−1 , bj−1 ) + 1 (ai = bi )(1)

Their method outputs a lot of data for comparing one pair of malwares. Therefore, theproblem is that how to deal with these data.
Iwamura et al.[4] calculate similarity fromdisassembled code using LCS. Because LCS
requires a large amount of memory, they propose a contraction algorithm for disassembled
code. One of the major problems is that calculating similarity with LCS requires computational costs.
The number of malwares is increasing
rapidly. Since we considered the fast algorithm
for malware analysis is needed in these days.
In this paper we propose the fast method tocalculate similarities between malwares and to
estimate function of malwares.

We calculate similarities between malwares bystatic analysis, and use it for function estimation. In this section we introduce two works- 10 -

Distribution

DOS MZ header(MZ・・・)
DOS stab(This program cannot ・・・)
PE header
Section Table

Bytecode.text section
Figure 2: PE File structure

Execute/readonly3

Similarity
wares

betweenDistribution

Figure 1: PE File structure

Mal-We use similarities between malwares to estimate function of malwares. We focus on thedistribution of byte code to calculate similarities. The distribution of byte code is the simplest character of a malware, and we can easily
compare two malwares using their distributionof byte code. Moreover once we get the distribution of byte code, we can calculate similarity without inﬂuence of ﬁle size. To calculate
similarity according to malware function, weextract the executable section. PE executableﬁle consists of several sections. Figure 1 showsa structure of PE executable ﬁle. Section table is available to decide which section is executable. Section table includes section information such as Name, Virtual Size, andwe can also get section Characteristics fromsection table. Section Characteristics consists of 4 byte code. Characteristics is logicalsum of ﬂags. If a section includes executablecode, the characteristics has 0x00000020 ﬂag
or 0x20000000 ﬂag. We extract executable sections or sections that have executable code tocalculate similarity. Moreover, we consider 2byte opcode as a trait. Because 2 byte opcode
begins with 0x0f, we extract the byte just after0x0f and get the distribution. Figure 2 shows

Bytecode

Figure 3: PE File structure
a distribution of all byte code in executablesection, on the other hand ﬁgure 3 shows a
distribution of the byte code just after 0x0f.
We can expect that deviation of similarity using ﬁgure 3 is greater than that of ﬁgure 2. We
make use of ZNCC to calculate similarity bydistribution of byte code. Eq. 2 shows how toderive similarity R between I and T by ZNCC.
∑N −1

i=1 (I(i) − I)(T (i) − T̄ )N −1
¯ 2 ∑N −1 (T (i) − T̄ )2i=1 (I(i) − I) ×i=1

R = √∑¯(2)Similarity calculated by ZNCC runs from -1
through 1. In this work, if similarity is near to1, we assume that there is a certain relationship between malwares. Finally in this section
we give a procedure for calculating similarity.

- 11 -

Step1 Extract section information from section table．

Step2 Obtain section which characteristicsincludes 0x00000020 or 0x20000000 ﬂag.

Table 1: Functions
Function
addRegcreate,delReg
executealterFilecreateFile(system dir)search(Microsoft Phonebook ﬁle)moveﬁlealterTxtFile
newHashreadFile
open,attrFile
openProcesscreateDir
addReg(auto start)
copyFile
createService
alterFilecreateFile(connect to Microsoft RPC service)deleteFile(delete itself)
searchcreateMutex
openwindow
alterProcessconnect(web)connect(DNS)
sendMailbackdoor

Step3 Determine the distribution of byte
code that are just after 0x0f.
Step4 Calculate similarity by ZNCC.

4Function Estimation

We make use of similarity to estimate functions of a malware. To estimate function of unknown malware, we calculate hundreds of similarities between unknown malwares and analyzed malwares. Functions of analyzed malware is supposed to be known. We add point
to functions that analyzed malware have according to similarities between the target malware and the analyzed malware. The added
point is calculated by eq. 3. If a point of afunction was higher than that of other functions, that function is estimated to be possessed by the analyzing malware.
∑P (k) =m |r(m)f (m, k)| r(m)f (m, k)√∑m f (m, k)(3)

We put the case that we estimate functionof unknown malware A, and we have analyzed
malwares B and C. We suppose that Malware
B have function a and function b, Malware C
have function a and function c. We consider
the distribution of A as I in eq. 2 and that ofB as T to calculate similarity RAB . The pointsof functions Pa , Pb , and Pc are calculated asbelow.
Pa =RAB |RAB | + RAC |RAC |√2Pb = RAB |RAB |Pc = RAC |RAC |(4)(5)(6)

In this work, we use NICT’s dynamic analysis result for function estimation. Table 1
shows all function that we use for function estimation.

5Experiment

We used MWS dataset for this experiment.
Table 2 shows the malware names by McAfee

and the number of each malware in MWS
dataset.
We estimated the functions of two malwares. Their hash values are 0ea635* and6acb0c*, one is named W32/RAHack and theother is named BackDoor-DOQ.gen.e. A lot ofW32/RAHack are in the dataset, whose hashvalues are distinct from each other, and one
BackDoor-DOQ.gen.e is in the dataset. Figure 4 and ﬁgure 5 present distributions of similarities between target malwares and analyzed
malwares.
In Figure 4, we can clearly divide similarities
into two. While in ﬁgure 5, we cannot. Thismeans that estimating function of 6acb0c* isharder than that of 0ea635*. Table.3 is theresult of function estimation of 0ea635*. We
can see that the points of the functions in ‘Pos-- 12 -Distribution of Similarity

Table 2: MWS dataset Classiﬁed by McAfee
Namenumber
W32/Conﬁcker.worm.gen.b
134
W32/Conﬁcker.worm.gen.a
440
W32/Conﬁcker.worm
106
BackDoor-DOQ.gen.e
1
W32/RAHack9828
Generic Dropper.acj
6
W32/Virut.n.gen
1
W32/IRCbot.gen.b
W32/Sdbot.worm!mj
2
W32/Conﬁcker.worm.gen.d3
W32/Autorun.worm.h1
W32/Virut.gen.a , W32/RAHack 8
UNKNOWN1
W32/Sdbot.worm.gen.ax
1
W32/Virut.n.gen
1
W32/IRCbot.gen.b
Generic.dx!bcqz
1
W32/IRCbot.gen.a1
W32/Sdbot.worm!mh1Generic BackDoor!1cj
1W32/Sdbot.worm!mc
1

10.8

Similarity

0.6
0.4
0.2
0050

100

150

200

250-0.2
Analyzed malware

Figure 4: 0ea635* simlirality distribution

Distribution of Similarity
10.8

Similarity

0.6
0.4
0.2
0050

100

150

200

250-0.2
Analyzed malware

Figure 5: 6acb0c* simlirality distribution
session’ are clearly higher than those of ‘Nonpossession’. This means that we can estimate
function of 0ea635*. While 6acb0c* has only
two functions, add register and delete itself.
This malware seems to detect analyzing environment and delete itself. 6acb635* is named
BackDoor-DOQ.gen.e, which original malware
is BackDoor-DOQ. We make use of report ofBackDoor-DOQ for function estimation. Table.4 shows its result. From this table, thepoint of copyFile is higher than that of twoof possessed functions. While points of othernon-possessed functions are lower than that ofpossessed functions. From this result, we canestimate the functions of the malware.
On the other hand, we have several malwares that function cannot be estimated. Thereason is that we do not have a suﬃcient
database to estimate function of malwares.
Because the database we have now consists ofmalwares that occurred in a speciﬁed period,
samples are biased. In this method, if all similarities between the target malware and analyzed malwares are low, the estimation cannot

be succeeded. The database is the most important part for this method.

6Conclusion

In this work, we proposed a method for estimating function of malwares. We also proposed a fast algorithm for calculating similarity between two malwares to estimate functions. We made use of distribution of byte
code that is just after 0x0f, which is used fortwo byte opcode. We calculated similarity using Zero-mean Normalized Cross-Correlation
between the two of malwares. Using thismethod, we can fast calculate similarity. Thismethod allows us to calculate a lot of similarities in a short time. Making use of thischaracteristic, we proposed a method for estimating function of malware. Our method
estimates unknow malware’s function by calculating similarities between target malware
and a lot of analyzed malwares which function is known. We estimated function of two- 13 -Table 3: Function Estimation of 0ea635*
Possession
Non-possession
Function Point
Function Point
createService 3.662
readFile 1.420
search 2.893 open,attrFile 1.388
copyFile 2.341 openProcess 0.874
alterFile 2.300
search 0.790
execute 2.097
backdoor 0.771
deleteFile 1.911
connect 0.771
alterTxtFile 1.749 alterProcess 0.763
addReg 1.734
createFile 0.021
newHash 1.727
moveﬁle 0.018
createFile 1.726
sendMail 0.009
createMutex 1.718 openwindow 0.003
create,delReg 1.686
createDir 0.003

malwares from MWS dataset. One was correctly estimated function, the other was notcorrectly estimated but was suﬃcient for estimation. In our method, the database of analyzed malwares is the most important factor
for estimation. Because we do not have suﬃcient database for this method, creating it is
one of our future works.

Acknowledgement
It is a pleasure to acknowledge the hospitality and encouragement of the members, especially Dr. Masashi Eto, of the Cybersecurity
Laboratory in Network Security Research Institute, NICT

References[1] Intel 64 and IA-32 Architectures Software Developer’s Manual，‘‘http://www.intel.com’’[2] Symantec Security Response，‘‘http://www.symantec.com/’’[3] Yuka Higashi，You Nakatsuru，Takashi
Manabe，Atsuo Inomata，Kazutoshi Fujikawa，Hideki Sunahara，“Proposal offunction estimation by malware code’sfunction similarity，”SCIS2011

Table 4: Function Estimation of 6acb635*
Possession
Non-possession
create,delReg 2.695
copyFile 2.120
createMutex 2.486 open,attrFile 1.975
createFile 2.477
alterTxtFile 1.974
addReg 2.450
readFile 1.973
execute 2.414 openProcess 1.846
connect 2.352
search 1.788
backdoor 2.352 openwindow 0.950
alterProcess 2.345 createService 0.809
deleteFile 2.210
moveﬁle 0.725
alterFile 2.170
createFile 0.663
newHash 2.073
sendMail 0.643
search 1.981
createDir 0.502- 14 -[4] MAKOTO IWAMURA，MITSUTAKA
ITOH，YOICHI MURAOKA，“Automatic Malware Classiﬁcation System
Based on Similarity of Machine CodeInstruction，”Journal of Information
Processing，vol.51，No.9，pp1-11，2010[5] Yuko Ozasa，Souma Katsute，Masakatu
Morii，Koji Nakao，“Estimated Functionof Malicious Code by Memory Dump
Analysis，”CSS2009[6] Yuu Arai，Makoto Iwamura，Yuhei
Kawakoya，Kazufumi
Aoki，YujiHoshizawa，“Analyzing Malware Fighting against infection incidents with freetools，”O’REILLY Japan, Inc.