WIXLIB

Journal of Internet Technology and Secured Transactions (JITST), Volume 7, Issue 2, June 2018and VT is the set of variables and CT is the set ofsymbolic constants that appear in IT. An “executioncontext” of a template T (IT, VT, CT) is anassignment of values to the symbolic constants of theset CT.For a given program P, they say that P satisfies atemplate T (denoted by P T) if P contains aninstruction sequence I such that I contains a behaviorspecified by T. The problem of deciding whether agiven piece of code contains such a templatebehavior (i.e., P T) is modeled as the “TemplateMatching Problem”.The Template Matching Problem turns out to beundecidable. Christodorescu et al. [5] gave areduction from the Halting Problem to the TemplateMatching Problem, and stated that a precise solutionfor the general Template Matching Problem isimpossible.2.4. Automatic Unpacking for MalwareDetectionAn obfuscation mechanism that is much used bymodern malware is to hide the malicious portion ofthe payload as data at compile time, and thentransform it into an executable at run time, abehavior known as “unpack and execute”. Theunpack transformation can be something simple,such as an XOR by a block of random-looking data,or something more complex, such as decryption by acipher like AES.Royal et al. [21] worked on detecting suchpolymorphic viruses by focusing on the result of theunpack operation. The idea is to compare theexecutable code during the run time with that beforethe run time. When a change is detected, it is writtenout for further analysis.The code and the data sections of a program areformally modeled as a Turing machine M and itsinput w. Then the unpack detection problem becomeswhether w contains another program in it that will beemulated by M during computation. This problemcan be formulated as the following formal language:UnpackExTM { M, w : M is a UTM, and Msimulates a Turing machine on its tape in itscomputation on w}Royal et al. [21] gave a theorem which stated thatthe UnpackExTM language is undecidable. Theyproved this result by a reduction from the HaltingProblem. Their proof can be summarized as follows:A mapping reduction HALT TM UnpackExTMwill be given to prove that UnpackExTM isundecidable.Let f be a function that takes M,w as input andcomputes M',w' as output where M,w HALTTM if and only if M',w' UnpackExTM. TheTuring machine F given below computes f:Copyright 2018, Infonomics SocietyF “On input M,w , a valid encoding of a Turingmachine M and an input string w:1. Construct a Turing machine T:T “On input x:1. Ignore x and halt.”2. Construct the following UTM M' from M:M' is the same as M, except:for all q Q, if (q, ) goes to a halting state thenReplace this transition with a transitionthat begins simulating T on the inputtape. I.e., change the transition to (q, ) (qstart,T, — , —).3. Output M', T, w .”The output of the mapping F, a UTM M', willexecute a Turing machine T in those cases where Mwill halt on w. A decider for UnpackExTM coulddecide whether M' will execute T and so decideHALTTM. But HALTTM does not have a decider.Hence, a decider for UnpackExTM cannot exist.Therefore, UnpackExTM is undecidableHence, it turns out that determining preciselywhether a given program contains some unpackexecute behavior in it is impossible.2.5. Automatically Identifying Trigger-BasedBehaviorA common feature found in modern malware is tocontain some hidden malicious behavior that isactivated only when triggered; such behavior iscalled trigger-based behavior. Various conditions areused for triggering, such as date and time, somesystem event, or a command received over thenetwork.Brumley et al. [2] studied how to automaticallydetect and analyze trigger-based behavior inmalware. Their approach employs mixed symbolicand concrete execution to automatically exploredifferent code paths. When a path is explored, aformula is constructed representing the condition thatwould trigger execution down the path. Then a solveris employed to see whether the condition can be true,and if so, what trigger value would satisfy it.Like many other problems in malware analysis,an exact, automatic identification of trigger-basedbehavior turns out to be undecidable by a reductionfrom the halting problem. Brumley et al. [2]observed that “Identifying trigger-based behaviors inmalware is an extremely challenging task. Attackersare free to make code arbitrarily hard to analyze.This follows from the fact that, at a high level,deciding whether a piece of code contains triggerbased behavior is undecidable, e.g., the triggercondition could be anything that halts the program.Thus, a tool that uncovers all trigger-based behaviorall the time reduces to the halting problem.”590

Journal of Internet Technology and Secured Transactions (JITST), Volume 7, Issue 2, June 20182.6. Self-ModifyingGrammarsCodeandFormalFiliol [11] studied the complexity of detectingself-modifying code (i.e., polymorphic andmetamorphic viruses) using formal grammars. Heworked on the formalization of metamorphism bymeans of formals languages and grammars. Heshowed how code mutation techniques can bemodelled by formal grammars, and how theirdetection can be converted to the problem ofdeciding a language.He modelled a self-modifying program as agrammar G2 whose language consists of grammarsthat are produced from a starting grammar G1according to the derivation rules specified by G2.This definition was used to describe the fact that thevirus kernel changes from one metamorphic form tothe other: It is both the virus code and the set ofmutation rules that change. (This view ofmetamorphic viruses resembles two-level 2VWgrammars, as Filiol pointed out.)In this context, detecting whether a given programis a form of a given metamorphic virus is an instanceof the language decision problem for Class 0 (free)grammars. Filiol showed that this problem can bereduced from the Halting Problem and hence isundecidable.2.7. NP-Complete ProblemsAlthough the general cases of the aforementionedproblems are undecidable, it turns out that it ispossible to obtain their decidable versions byassuming some bound on the time or memoryavailable to the malware.Spinellis [24] showed that a length-boundedversion of Cohen’s problem is decidable and NPcomplete, by a reduction from the BooleanSatisfiability Problem (SAT).Borello and Mé [1] showed that detecting whethera given program P is a metamorphic variant ofanother given program Q is decidable and NPcomplete.On a related venue, Fogla and Lee [12] showedthat detecting a polymorphic blending attack, whichcan blend in with normal traffic and can evade ananomaly-based IDS, is also NP-complete, by areduction from the 3-SAT problem.Song et al. [23] studied the strengths andweaknesses of polymorphic shellcode. Theydeveloped metrics to measure the capabilities ofpolymorphic engines. In the end, they concluded thatpolymorphic behavior in general is too greatly variedto be modelled and detected effectively.Bueno et al. [3] showed that the space- and timebounded versions of the unpacking problem aredecidable, and the time-bounded version is NPcomplete.Copyright 2018, Infonomics SocietyOf course, a problem’s being NP-complete ishardly good news. It is usually interpreted as that noefficient solution exists for the worst case of thatproblem. However, efficient solutions may exist forthe average case, or it can be possible to obtainreasonably good solutions by heuristics orapproximation algorithms.3. Practical SolutionsDespite the negative theoretical results onundecidability of some fundamental questions inmalware analysis, practical tools have been in actionsince the very early days of computer viruses. Bytolerating some degree of inaccuracy (i.e., toleratingsome degree of false positives or negatives, orallowing inconclusive results), it is possible to buildalgorithms that are very effective in practice. In thissection, we summarize some of the tools developedfor the problems reviewed in Section 2.3.1. DetectingMatchingMalwarebyTemplateDespite the fact that the general TemplateMatching Problem is undecidable, it is possible todetect malware using template matching algorithmsthat are mostly accurate. Christodorescu et al. [5]developed a toolkit for that purpose. The toolkitworks in two phases: First, the binary program to beanalyzed is disassembled, a control graph isconstructed, one per program function, and anintermediate representation (IR) is generated. The IRis further processed and put into an architecture- andplatform-independent form. In the second phase, theIR is compared against a given set of malwaretemplates. Each comparison either returns “yes” or“don’t know”. Suggested malware templates forcomparison include procedures such as a decryptionloop or mass mail sending.Christodorescu et al. [5] tested their tool on a realworld malware sample consisting of seven variantsof Netsky (B, C, D, O, P, T, and W), seven variantsof Bagle (I, J, N, O, P, R, and Y), and seven variantsof Sober (A, C, D, E, F, G, and I), all being emailworms with many diverse forms found in the wild.The authors tested the malware against templatescapturing the decryption loop and mass mailingfunctionalities. The tool detected all Netsky andBagle variants with 100% success. The Sober wormwas not detected due to a limitation in the prototypeimplementation, related to matching calls into , their test demonstrated the success oftheir template matching algorithm on diverse formsof malware.The tool was tested on a benign sample as well inorder to test its false positive rates. 97.78% of theprograms in the given sample were detected as591

Journal of Internet Technology and Secured Transactions (JITST), Volume 7, Issue 2, June 2018benign after successful disassembly, while 2.22%could not be disassembled.Kwon et al. [16] developed a technique calledBinGraph, in which they leveraged the semantics inAPI call sequences of different malware families astemplates and detected metamorphic malwaresamples using signatures and template matching.They extracted signatures from subgraphs of APIcalls and used them to represent semantic behaviorsof metamorphic malware. In first phase, using theImport Address Table (IAT) from executable theyconstructed initial behavior graph with edgesrepresenting API call sequences. Followed bysubgraph extraction and graph abstraction, theystored the abstracted semantic graphs in a 128x128adjacency matrix. At the final step of sematicsignature extraction, they applied graph miningtechniques using a greedy strategy to select candidatesignatures.Kwon et al. [16] used 166 malware programs(randomly selected 20% of their malware collection)and generated 32 semantic signatures representingthis set. They compared these signatures against theset of remaining 661 (unseen) malicious and 1,202safe binaries. They achieved a 98.18% detection rateon the malicious sample and detected 649 malwareprograms, with no positive matches on the benignsample.Luh et al. [17] used sentiment analysis techniqueby collecting kernel level events in order to modelmalicious and benign behaviors. Timestampedprocess, thread, image load, file, registry andNetwork event logs were collected from theWindows kernel and runaway entries wereeliminated. Log-likelihood ratio scores for each preprocessed bi-gram event traces were calculated andused in compilation of malicious and safe semanticdictionaries. At the final step, score normalizationand adjustment was applied to calculated valuesusing whether monitored trace is a part of somemalicious event sequence or not.Safe event logs are collected from standardWindows users having more than 80 OS session andover 500 processes in each. Different types ofmalware samples like MyDoom, Zeus, Koobface,etc. were used to infect machines in controlledenvironments and their respective event traces wereused in bi-gram extraction from malicious behaviors.Luh et al. [17] achieved 98.2% accuracy formalicious behavior detection with low false positiverates. Moreover, it is reported that thresholdoptimization on determined confidence values couldincrease the performance of related classificationtechnique up to 100.0% for this particular test setused in conducted experiment.Copyright 2018, Infonomics Society3.2. Detecting Unpack-Execute BehaviorAlthough the general problem of unpack-executebehavior is undecidable, Royal et al. [21] gave analgorithm for a bounded version of this problem. Letn denote the number of instructions of a givenprogram P to execute before it halts. The programExtractUnpackedCode(P,n) works in two phases: Phase 1: Static Analysis. Program P isdisassembled to identify code and data. Blocksof code that are separated by non-instructiondata are partitioned into sequences ofinstructions. These sequences form the set I,which will be queried repeatedly in the nextphase to detect if P is executing unpacked code. Phase 2: Dynamic Analysis. Program P isexecuted one instruction at a time. The currentinstruction sequence is captured by in-memorydisassembly starting at the current value of theprogram counter until some non-instruction datais encountered. The current instruction sequenceis compared against each instruction sequence inthe set I. If the current sequence is not asubsequence of any instruction sequence in I,then it did not exist in P.Royal et al. [21] developed this algorithm into apractical tool for MS Windows systems, calledPolyUnpack. They tested the tool on the OARCmalware suspect repository and compared itsperformance with that of the Portable ExecutableIdentifier (PEiD), a popular reverse-engineering toolwhich uses a specific set of signatures to ed very well and was able to identify manysamples with unpack-execute behavior which PEiDwas unable to detect.Another technique developed by Korczynski [15]helped reconstructing packed binaries with selfmodifying code blocks up to some accuracy, easingfurther analysis on them by malware analysts. Bothstatic and dynamic analysis were used in relatedwork and binaries having self-modifying propertyand IAT destruction are focused for binaryreconstruction. Tough it is not directly related withmalware detection, Korczynski’s [15] techniquehelps further methods and algorithms to bedeveloped for bounded version of undecidableunpack-execute behavior.There are mainly two phases in general unpackingtechnique of developed by Korczynski [15]: First phase: Self-modifying code detection,where dynamically loaded modules are beingtracked and several snapshots are being nces and memory writes Second phase: Recovering import address tableusing dynamically loaded function branchesusing a heuristic filtering method592

Journal of Internet Technology and Secured Transactions (JITST), Volume 7, Issue 2, June 2018Korczynski [15] carried out two experiments toverify that the developed technique improves selfmodifying code discovery and IAT reconstructioncompared with the clean memory dumps. 117malware samples belonging to 9 different malwarefamilies were used in the first experiment. Initially,35% of the malware had no IAT in the clean memorydumps. This sample was analyzed and successfulIAT reconstructions up to some degree wereperformed on 66% of them. In the secondexperiment, a simple so-called hello worldapplication was developed and packed with 21different packers. IAT reconstruction was partiallydone on 61% of the packed binaries.Kim et al. [14] studied distinctive properties ofobfuscation techniques applied on safe and malicioussamples and developed a technique named asDynODet, first to detect dynamic obfuscation andthen use features of present obfuscation to classifyunknown sample as either clean of malware.DynODet uses both static and dynamic analysisresults while determining whether any obfuscation ispresent or not. Static analysis leverages finding theexpected path of the program before its executionand using this discovery to compare seen actualpaths in dynamic analysis. Six different obfuscationtechniques were tracked and used by Kim et al. [14]:self-modification, section mislabel obfuscation,dynamically generated code, unconditional toconditional branch obfuscation, exception-basedobfuscation, and overlapping code sequences.Kim et al. [14] used 6,192 safe Windowsprograms in their experiment and using distinctiveobfuscation features they reduced the false positiverate nearly 70% in terms of one or more falseobfuscation detection on these safe samples. Totally100,208 malware samples used for malicious data setand using distinctive obfuscation features, one ormore of the tracked obfuscation techniques weredetected on 32.74% of the malware set with adetection rate of 2.5% on the clean set. Findingsfrom the DynODet research showed its usefulness todevelop a new detection technique using thepresence of distinctive obfuscation techniques inunknown samples.3.3. Detecting Trigger-Based BehaviorDetection of trigger-based behavior by manualanalysis is a virtually impossible task due to theintensive labor required. On the other hand, a preciseautomatic analysis is not possible either; as explainedin Section 2.5, the general problem of automaticidentification of trigger-based behavior isundecidable. Nevertheless, a great deal of help canbe obtained from automatic analysis to alleviate theburden of manual analysis. Brumley et al. [2]designed a tool for this task. Their approachconsisted of several phases: First, the different typesCopyright 2018, Infonomics Societyof triggers of interest are specified. Then, differentcode paths are explored using mixed symbolic andconcrete execution. For a path explored by thisprocess, a formula is constructed representing thecondition that would trigger execution down thepath. Then a solver is employed to see whether thecondition can be true, and if so, what trigger valuewould satisfy it.Brumley et al. [2] developed this approach into aprogram called MineSweeper. They testedMineSweeper on real-world malware containingtrigger-based behavior. On every case, MineSweeperwas able to detect the trigger condition and thetrigger-based behavior. The analysis time varieddepending on the complexity of the malware, from 2to 28 minutes. In general, MineSweeper is notguaranteed to detect every piece of malwarecontaining trigger-based behavior, but it candefinitely be used as a tool of great assistance overthe impractical alternative of manual analysis.Kang et al. [13] researched specifically botnetmalware samples and developed a trigger-basedbehavior detection technique called BotMelt. In anapproach different from [2], they used dynamicsymbolic execution (also known as symbolpropagation) where network packets were used tomark the data flow. This technique allows revealingoutbound trigger conditions different from locallydecided trigger conditions. Authors evaluated theirtechnique in terms of validness of executed codes,malicious activity detection rate and behaviordetection ratio among all possible behavior branches.four different botnet malware samples, HwDoor,Bisonal, KeyBoy, and Plez were used in evaluationexperiments, and BotMelt yielded successful resultsin all evaluation criteria.Papp et al. [18] developed a framework to detecttrigger-based malicious behavior in source code levelusing a semi-automated approach. First, automatedsource code instrumentation technique is beingapplied to discover function calls and variables thatinteract with running environment. Then freshsymbolic values are given via replaced dummyfunctions and mixed concrete and symbolicexecution tool is used to generate potentiallymalicious test cases that could trigger hiddenmalicious behavior of malware. At the final step,execution traces for each generated test case inputwere generated and passed to analysts for manualanalysis in order to classify them as either maliciousor benign.In the experiment phase, Papp et al. [18] collectedfive real-world malware samples, all written in C andincluding some kind of trigger-based behavior inimplementation.Thedevelopedframeworksucceeded in revealing trigger-based behaviors inthree of them. Moreover, unsuccessful cases ofhidden behavior detection were reported as faileddue to limitations of the open-source tools used.593

Journal of Internet Technology and Secured Transactions (JITST), Volume 7, Issue 2, June 20183.4. Malware Protection by Whitelisting andDefault Deny ApproachGiven that some fundamental problems inmalware analysis and detection are undecidable, analternative solution applied by practical securitytools (e.g., Comodo’s Endpoint Security [9]) is thedefault deny approach to protect users from malwareinfections: Rather than blocking only blacklistedmalware applications and allowing all other safe andunknown applications, only whitelisted applications[22] are permitted to run on a host’s real operatingsystem (OS). Samples blacklisted as malware areblocked by default. And, unknown programs arepermitted to run in some virtualized environmentssuch as containments, sandboxes, etc. Creating theseshadow file systems, registries, and communicationports helps blocking most damages caused bymalicious application, and correctly defining aprogram for virus detection [10].Although the default deny approach provides ahigher level of protection compared to the defaultallow approach, one of the current problems usingthese virtualized environments is encountered inapplicatio

Intractable Problems in Malware Analysis and Practical Solutions Ali Aydın Selçuk Dept. of Computer Engineering TOBB University of Economics and Technology Ankara, Turkey Fatih Orhan, Berker Batur Comodo Security Solutions, Inc. Clifton, NJ, U